# Question
Title: How to prove that average complexity is N/2 for linear search in the unsorted array
All tutorials on algorithms show the complexity for the linear search in the unsorted array in the average case as `N/2`. I understand that the average case means the items in the list are randomly distributed.

Can anyone show how I would arrive at `N/2` if I have items randomly distributed? Or does it come out of randomly shuffling array bazillion times and recording the number of operations?

# Answer
> 7 votes
First assume input is uniformly distributed. More precisely it is $\frac{n+1}{2}$. When you search for a particular element $x$ in an array of size $n$, that element may be located at the position either $1$, or $2$, $\dots$ or $n$. When we search we check each element in the array and compare it with $x$, and so when we reach $k^\text{th}$ element of the array we have already done $k$ comparisons.

If it is at $1$ then you find it in 1 comparison, if it is at $2$, you find it in 2 comparisons, $\dots$, if it is at $n$ then you do $n$ comparison in order to find it. In order to average it you sum the total number of comparisons $1+2+\dots + n = \frac{(n+1)n}{2}$ and divide it by $n$ (size of the array) resulting in $\frac{n+1}{2}$.

---

More formal proof: Assume that the input has uniform probability and the the size of the array is $n$. Let $X$ be a random variable denoting the number of comparisons. Then $p(X=x)$ will denote the probability that we do $x$ comparisons. Since the distribution is uniform, $p(X=x) =\frac{1}{n}$. Once we formally defined our probability distribution now we can calculate the average number of comparisons in the linear search. What we do is compute the expected value $$E\[X\] = \sum\_{x=1}^{n}{xp(x)} = \sum\_{x=1}^{n}{\frac{x}{n}} = \frac{1}{n}+ \frac{2}{n} + \dots +\frac{n}{n} = \frac{n+1}{2}$$

---
Tags: algorithm-analysis, runtime-analysis, arrays, average-case, searching
---


# Question
Title: Equivalance of NFAs, understanding the solution
This solution comes from https://people.eecs.berkeley.edu/~luca/cs172-07/solutions/practicefinal-sol.pdf

> Consider the language
>
> $$ EQ\_{NFA} = \\{ \langle N, N^\prime \rangle \mid N, N^\prime \text{ are NFA's with the same alphabet and } L(N) = L(N^\prime) \\} $$ show that $EQ\_{NFA} \in \textbf{PSPACE}$.
>
> (hint: Can you convert this to a appropriate reachability problem?)
>
> ***Solution Outline:*** Suppose $N$ and $N^\prime$ both have at most $n$ states. We can then convert them into DFAs $D\_N$ and $D\_{N^\prime}$ with at most $m = 2n$ states each using space polynomial in $n$. Finally, we can construct a DFA $S$, which is the product of $D\_N$ and $D\_{N^\prime}$ (with at most $m = 2^n$ states) and accepts $L(D\_N)\Delta L(D\_{N^\prime})$ (strings that are in exactly one of the languages). Now, $L(N) = L(N^\prime)$ iff $L(S) = \emptyset$ i.e. none of the final states are reachable from the start state in $S$.
>
> Since this is a reachability problem, it can be decided nondeterministically using space logarithmic in the size of the graph (because $PATH \in NL$). Thus, this problem can be decided in $NSPACE(\log{(m^2)}) = NSPACE(n) \subseteq NSPACE(n^2) \subseteq PSPACE)$.

I see that it works and I see that the last paragraph try to convince that it is actually $PSPACE$. But, I have a doubt:

After all, the solution constructs two **exponential** automats. How is it possible?

My intuition is that: We can compute DFA for NFA using $\log n$ memory on **working** tape. Obviously, we have to use exponential size of memory but on the **output (readonly)** tape.

Now, when we construct it we can use it in reachability problem which works in $NL$. We know that composition of $LOG$ function is $LOG$. Is my understanding correct? Does the same apply (I mean a composition of functions) when it comes to $NLOG$?

# Answer
> 8 votes
Your confusion is understandable. The solution outline you've quoted misses an important point and suggests the opposite of that point.

The DFAs are, as you say, exponentially big. We *can* construct them, but *not* in polynomial space. However, the key point is that we don't need to construct and store the whole automaton. The reachability algorithm doesn't need that. All it needs is the ability to know what state it's in at the moment and construct the list of states it could move to next. Both of these can be done easily, on the fly, from the description of the NFAs. Likewise, we don't need to literally construct the product automaton: we can do that implicitly as well, by just tracking our position in each automaton separately.

---

Let's do a simplified example. Suppose that we just want to know if a particular NFA $N = (Q, \Sigma, \Delta, q\_0, A)$ accepts at least one string, i.e., if an accepting state is reachable from the initial state. In this simplified scenario, we could just work directly with the NFA but we'll ignore that and convert to a DFA, $M$. If $N$ has $n$ states, then $M$ will have $2^n$ states so, if we were to write out its full transition graph, we'd need exponential space.

However, the reachability algorithm doesn't require us to write out the whole graph. As it runs, it says things like, "OK, I'm at vertex $v$. Where can I go next?" Normally, we imagine that it looks up that vertex in the graph's adjacency matrix to answer this question, but that's not the only way. It could calculate what vertices can be reached, using the rules of the subset construction that generates $M$ from $N$. Specifically, if we're at vertex $v$ then $v = \\{s\_1, \dots, s\_\ell\\}\subseteq Q$ and the vertices we can move to are the vertices of the form $\Delta(s\_1,a)\cup\dots\cup\Delta(s\_\ell,a)$ for each symbol $a\in\Sigma$. Each such vertex is a subset of $Q$, which we can write down in $n$ bits, and there are at most $|\Sigma|$ different possibilities, so you can write all of them down in $n|\Sigma|$ bits, which is polynomial in the size of $N$. Once the reachability algorithm has decided what to do next, it can forget this list of vertices and re-use the space. If it needs to access the list of $v$'s neighbours again, it can recalculate it.

The reachability algorithm never needs the whole adjacency matrix of the graph to be written down at the same time. Pretend, for a moment, that we did have the graph written down. Since the graph has $2^n$ vertices, we would need working space $O(\log 2^n) = O(n)$ to run the algorithm. Now, instead of writing the adjacency matrix down, we'll calculate it on the fly. That will require additional working space $O(n)$ for the calculations of what the adjacency matrix is. So the total space used is still $O(n)$, even though the graph can't be stored in that little space.

---

By the way, this trick of calculating things on the fly is a common trick in logarithmic space computations. Another prominent example is showing that logspace reductions compose (i.e., if there are logspace reductions $A\to B\to C$ then there's a logspace reduction $A\to C$). What you'd like to do is just do the first reduction, store the result on a tape and then apply the second result to that; but you can't because the result of the first reduction might be too big to store. So, instead, you start with the *second* reduction. Every time you need to know some character of the output of the first reduction, you recompute it from scratch.

---
Tags: complexity-theory, finite-automata
---


# Question
Title: Given a low resolution video, is it possible to create a higher resolution image
This question is purely theoretical as I've not been able to find anyone who's done such a thing, so my question is - is it possible, and if not why?

Say you have a short video (CCTV) of a face, or number (car licence) plate, and that video is of too poor quality to discern who that person is or what the number plate says, would it be possible to combine details from several frames of video to interpolate and thus make a clearer image than can be gained from a single frame?

Surely some frames would contain detail that others lack (due to pixel boundaries, shadows etc)? Are there any examples of machine learning or CV that do this?

# Answer
> 3 votes
It heavily depends on the setting, accuracy and goal, but shortly, yes, even considering practical application.

Theoretically of course it is possible, with various (or used together) techniques like sharpening, noise removal, scene reconstruction, frames merging, geometry reconstruction or even motion blur removal. The last one works by solving optic equation and could be used with success if you treat consecutive frames as one speeding object, applying frames as artificial motion blur, for example Practical Layered Reconstruction for Defocus and Motion Blur.
The most straightforward technique would use shifted grids (frames) and after applying constraints from "big pixels" and how they round at the discrete domain the result is in the "reconstruction domain" - all pixels represent ranges of possible chrominance / luminance. The accuracy increases with the number of frames used. Here are two problems: the additional processing is needed to estimate the repative position of frames (which in the case of static camera gets easier - the equivalent of motion capture of smart objects) and the number of frames. If these came from different cameras (angles, coordinates, intrisinc camera setting) the scene reconstruction with possibly light oblivious merge (the light condition may vary, it must be equalized).

As stated earlier it depends, the plate recognition is easier, it reduces to contours extraction of low resolution data / blurred setting or image reconstruction discarding colours (which are known and not interesting), with some degree of certainty - the numbers under noise should be matched with patterns.

For the face recognition it gets harder due to unknown pattern, possibly 3D reconstruction from frames, which are low resolution, and hopefully with full colour after processing. This is a part of active research, because many powerful algorithms yield grayscale images.

Generating perceptualy clearer images is quite established field, heavily dominated by SSIM derivative techniques (the theoretical-empirical model for images compression, that could be fed with "reconstruction domain" image and return the most plaussible one), but reconstruction beyond doubt is harder task.

Here are some good to read articles about it:
Super resolution algorithm

An Algorithm for Repairing Low-Quality Video Enhancement Techniques Based on Trained Filter

Video Superresolution Reconstruction Using Iterative Back Projection with Critical-Point Filters Based Image Matching

VIDEO SUPER RESOLUTION RECONSTRUCTION FROM LOW RESOLUTION IMAGES USING SPLINE INTERPOLATION

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


# Question
Title: What's the most efficient way to print all paths from root to leaves in a directed graph?
I have a directed graph created in matlab. I am trying to print all paths from root to leaves. I used stack to implement my algorithm but it seems very slow when I have large number of nodes and edges.

Is it possible to solve this problem in O(nlogn) time ?

```
%This is my graph:
output =
   edges: {[0 1]  [0 2]  [1 3]  [1 4]  [1 5]  [2 6]  [3 6]  [2 7]  [3 7]  [4 7]}
vertices: [0 1 2 3 4 5 6 7]

%I am traversing with this code
maximal_sets = {};
stack=java.util.Stack();
stack.push(0);
CP = [];
Q = [];
labels = ones(1,size(output.vertices,2));
while ~stack.empty()
    flag = 0;
    x = stack.peek();
    for e = 1:size(output.edges,2)
        if output.edges{e}(1) == x && labels(output.edges{e}(2)+1) == 1
            flag = 1;
            w = output.edges{e}(2);
            stack.push(w);
            CP = union(CP,w);
            break
        end
    end
    if flag == 0
        Q = [];
        % PRECEDES are leaves of the graph
        if any(PRECEDES{end}==x)
            for v=1:size(CP,2)
                Q = union(Q,CP(v));
            end
        end
        if size(Q,2) > 0
            maximal_sets{end+1} = Q;
        end
        for ed = 1:size(output.edges,2)
            if output.edges{ed}(1) == x
                labels(output.edges{ed}(2)+1) = 1;
            end
        end
        labels(x+1) = 0;
        stack.pop();
        CP = CP(find(CP~=x));
    end
end

for i = 1:size(maximal_sets,2)
    disp(maximal_sets{i})
end

%The paths from root to leaves (not including root which is 0) are listed:
 1     3     7

 1     4     7

 1     5

 2     6

 2     7

```

This works well with toy examples, but when I have 403 vertices, and 6717 edges. It does not stop. I think it is exponential.

The traversing code was taken from \[http://drum.lib.umd.edu/bitstream/handle/1903/4638/TR\_87-130.pdf?sequence=1&isAllowed=y\] and modified.

# Answer
> 1 votes
In a directed graph with $n$ vertices there may be $(n-2)!$ different simple paths (paths without cycles) between any two vertices. Just consider a complete directed graph. So its running time is $O(n!)$ and hence it is impossible to solve the problem in $O(n\log{n})$.

---
Tags: algorithms, graphs, graph-traversal, enumeration
---


title: Big O proving for increasing functions

text:
# Question
Title: Big O proving for increasing functions
Please help me to prove:

If $f, g ∶ \mathbb{N} \rightarrow \mathbb{N}$ and $f$ and $g$ are increasing $(f(n+1)\>f(n),g(n+1)\>g(n)$).

Need to prove $g=O(f)$ or $f=O(g)$.

Thanks

# Answer
The claim is false. Let $f(n) = n^{1.75}$ and $g(n) = 2^{\lfloor \log\_2 n \rfloor} n$, and note that both are increasing. When $n = 2^t$, we have $g(n) = n^2$, while when $n = 2^t-1$, we have $g(n) \approx n^{1.5}$. This shows that $$ \liminf\_{n\to\infty} \frac{f(n)}{g(n)} = 0, \quad \limsup\_{n\to\infty} \frac{f(n)}{g(n)} = \infty. $$ In particular, it is not the case that $f = O(g)$, nor is it the case that $g = O(f)$.
> 2 votes

---
Tags: asymptotics
---


title: Why does this not prove $P\neq NP$?

text:
# Question
Title: Why does this not prove $P\neq NP$?
Fiorini, Massar, Pokutta, Tiwary and De Wolf (*Exponential Lower Bounds for Polytopes in Combinatorial Optimization*, *Journal of the ACM* 62(2):article 17, 2015; PDF, ArXiv) show any linear program that solves travelling salesman needs super-polynomially many constraints.

Suppose $P=NP$ by 'some' method then we can solve the optimal tour explicitly and trivially setup a LP that 'solves' the TSP problem. So $P=NP$ implies that TSP has a poly-size LP formulation. The contrapositive is that TSP has no poly-size LP formulation implies $P\neq NP$. This paper shows TSP needs super-polynomially many constraints.

So why doesn't this show that $P\neq NP$?

# Answer
What Fiorini et al. show is the following:

> The *TSP polytope* $P\_n$ over $n$ points is a polytope in $\binom{n}{2}$ dimensions whose vertices correspond to all Hamiltonian cycles in $K\_n$ (the complete graph on $n$ vertices). (That is, it is the convex hull of the indicator vectors of all Hamiltonian cycles.)
>
> Suppose that $X\_n$ is a polytope whose projection over the first $\binom{n}{2}$ dimensions is $P\_n$, and let $d\_n$ be the number of constraints needed to define $X\_n$ (i.e., the number of facets of codimension 1). Then $d\_n \geq f(n)$ for some function $f(n) = 2^{\Omega(\sqrt{n})}$.

In other words, they show that TSP cannot be solved using LPs in one particular way. There could be some other way of using LPs to solve TSP which isn't ruled out by their result.

For example, perhaps you could use iterative rounding to solve TSP, at each step solving an LP. This is consistent with the result of Fiorini et al.

The method in your argument is likewise not ruled out by Fiorini et al.
> 8 votes

# Answer
What you're proposing isn't "a linear program for TSP", so it doesn't come into the scope of the proof.

You've observed that, if $\mathrm{P=NP}$, then TSP can be *reduced to* polynomial-sized linear programs. You're using a polynomial-time Turing machine to perform a slightly more complicated version of the following reduction:

* if the input graph $G$ has a tour of length at most $\ell$, then output the program $x\>1$;
* otherwise, output the program $x\>1$ and $x\<1$.

A linear program that solves TSP is one whose only inputs are variables $x\_{uv}$ giving the weight of every edge in the graph and $\ell$, giving the target distance. These variables must be instantiated with exactly the TSP instance you're trying to solve (not with some graph produced by a reduction) and the LP must output a valid tour if one exists. Fiorini *et al*. prove that any such LP must have exponentially many variables.
> 5 votes

---
Tags: complexity-theory, proof-techniques, linear-programming, p-vs-np, traveling-salesman
---


# Question
Title: Does every 3CNF propositional formula has an equivalent 2CNF propositional formula?
Does every 3CNF propositional formula has an **equivalent** 2CNF propositional formula?

Definitions:

3CNF propositional formula is conjunctive normal form propositional formula, which is just conjunction $\land$ of clauses, where each clause is disjunction $\lor$ of at most **3** literals, where each literal is just boolean variable either with or without not $\lnot$ operator/connective.

2CNF propositional formula is conjunctive normal form propositional formula, which is just conjunction $\land$ of clauses, where each clause is disjunction $\lor$ of at most **2** literals, where each literal is just boolean variable either with or without not $\lnot$ operator/connective.

# Answer
The single clause 3CNF:

$\varphi = a\lor b\lor c$

does not have an equivalent 2CNF. Suppose $\psi=\bigwedge\limits\_{i=1}^m \psi\_i$ is an equivalent 2CNF. Let $\psi\_i$ be one of its clauses, and assume it involves the variables $a,b$. An assignment which sets $c=1$, but does not satisfy $\psi\_i$, satisfies $\varphi$ but not $\psi$, hence they are not equivalent.
> 4 votes

---
Tags: logic, first-order-logic, propositional-logic
---


title: SAT to knapsack vs. ETH

text:
# Question
Title: SAT to knapsack vs. ETH
Theorem states that every problem in $\mathsf{NP}$ can be reduced to another $\mathsf{NP}$-complete problem in polynomial time. Also you can only make a problem polynomially longer using polynomial time.

Thus SAT of length $n$ can be reduced to knapsack with length $n^k$ for some fixed $k\in\mathbb{R}^+$. We don't need to show that reduction, we only need to know that it exists.

Knapsack has quasipolynomial algorithm, in other words running time is $O(\alpha^{\log^p q})$ where $\\{p,\alpha\\}\in\mathbb{R}^+$ are some fixed numbers and $q$ is length of knapsack problem.

Now assuming we have converted SAT to knapsack we get runtime $O(\alpha^{\log^p n^k})=O(\alpha^{k^p\log^p n})=O(\beta^{\log^p n})$ where $\beta\in\mathbb{R}^+$ is some fixed number. So, the runtime is quasipolynomial.

Why doesn't this simply negate ETH?

# Answer
Knapsack does not have any known quasipolynomial time algorithm (one which runs in $n^{poly(\log n)}$ time, with $n$ being the inputs length).

What it does have is a pseudo-polynomial time algorithm, i.e. an algorithm which requires polynomial time in the **numeric value** of the input, but exponential in the length of its description. The dynamic programming algorithm for knapsack runs in time $O(nW)$, however the input $W$ when given in binary representation requires $\log W$ bits, so the algorithm is actually exponential (and not quasipolynomial).
> 3 votes

---
Tags: np-complete, satisfiability, knapsack-problems
---


# Question
Title: Decision if there exists a path between $s$ and $t$ of length $k$
I conisder a problem:

> It is given a graph $G$, vertices $s,t$, $k$- length of the graph. Prove that decision whether there is a path between $s$ and $t$ of length $k$ is NP-complete.

Please note that in our problem we have a **path**, not a \**simple path\* \**

\*It is trivial when we have a simple path (define as sequence of vertices where every vertice occurs at most once (there is no cycle) ).

I don't know how to start. I cannot come up what's problem I should reduce. Please hint me.

# Answer
I think you (or whoever asked you this question) probably *does* mean "simple path" (that is, a path that does not contain any vertex more than once), since this problem is indeed NP-hard.

If paths that may repeat vertices (often called "walks") are permitted, the problem is not NP-hard any more: It can be solved in polynomial time using matrix multiplication. Specifically, if $A$ is the adjacency matrix of the graph, then $A^k\[i, j\]$ (the element at row $i$, column $j$ in the matrix $A$ raised to the $k$-th power) is the number of walks of length exactly $k$ from $v\_i$ to $v\_j$. You can compute $A^k$ in $O(n^3 \log k)$ time using exponentiation by squaring.
> 2 votes

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


# Question
Title: Graph isomorphism in BPP implies it is also in RP
$$L=\\{\langle G\rangle \\#\langle H\rangle : H, G \text{ are directed isomorphic graphs }\\}$$
$\langle G\rangle$ is adjacency matrix written row by row. Show that if $L\in BPP$ then also $L\in RP$.
Can you help me ?
I have no idea how to do it.

# Answer
> 2 votes
The important observation here is that $GI$ (the language of isomorphic graphs) is self reducible. This means that you can solve the corresponding search problem (finding an isomorphism) using a solution to the decision problem. You can find such a reduction in these notes of Jonathan Katz. Now, suppose $A$ is a polynomial time machine with access to an oracle for $GI$, such that when given two isomorphic graphs, $A$ produces an isomorphism.

To put $GI$ in $\mathsf{RP}$, you need to be able to answer "yes" only when you are certain the graphs are isomorphic. Suppose $M$ is a probabilistic polynomial time machine which agrees with $GI$ with high probability (its existence follows from $GI\in\mathsf{BPP}$, with some success amplification). Given graphs $G,H$ as input, execute $M$. If $M$ outputs "no", answer "no". However, when $M$ answers "yes", execute $A$ (the algorithm for finding an isomorphism), while replacing oracle calls with calls to $M$. If $A$ produces a valid isomorphism from $G$ to $H$, output "isomorphic", otherwise output "non-isomorphic".

If $G,H$ are isomorphic, then conditioning on the event that $M$ outputs the correct answer in all of the oracle calls raised by $A$, $A$ finds an isomorphism and the above procedure outputs the correct answer. Since $A$ runs in polynomial time, if the error probability of $M$ is small enough (I leave the details for you), you can use the union bound to bound the probability of having an error in at least one of the oracle calls. If $G,H$ are non isomorphic, then you always output no, which puts $GI$ in $\mathsf{RP}$.

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


# Question
Title: Does this behavior have a formal name, and if so, what is it?
This is related to the issue asked about in this other question.

For the sake of this question, let's assume that we have a variable v that can have any value from the set of values

> "a", "b", "c", ..., "z"

In this case then the programmers wants to have specific code executed when the value of `v` is **not** `"x"`, `"y"`, or `"z"`.

So the following IF statement is constructed:

> if (v != "x" || v != "y" || v != "z") {//do something}

Above statement would always return true, due to that the 3 conditions using negation are checked independently of each other.

Consequently, at any given time, any single one of the 3 conditions can evaluate to TRUE, leading to the entire IF statement evaluating to TRUE.

Anyway so the question I wanted to ask is, does this behavior or situation have a formal name, and if so, what is it?

# Answer
> In many programming languages above statement always returns true, due to that the 3 conditions using negation are checked independently of each other.

It returns true not just due to "that the 3 conditions using negation are checked independently of each other", but because the expression `(v != "x" || v != "y" || v != "z")` is always necessarily true. In logic such expressions are called *tautology*, i.e. a formula that is true in every possible interpretation (Wikipedia).

But "this behavior or situation" does not have a special name in programming and is usually considered as a programming error.
> 4 votes

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


# Question
Title: A commonly-used symbol for the set of all heads of directed edges?
Let $G = (V, E)$ be a digraph, and consider the set $\left\\{ v \in V \\; \middle| \\; \left(\\{v\\} \times V \right) \cap E \neq \varnothing \right\\}$, the set of vertices which form edges with other vertices; or if you will, the set of "heads of edges".

Is there a commonly-used term for this set?

# Answer
In *Graphentheoretische Konzepte und Algorithmen* by S. Krumke and H. Noltemeier, they introduce for an edge $e = (u,v)$ two functions

$\qquad\alpha(e) = u$ and
$\qquad\omega(e) = v$.

The inspiration is probably alpha = beginning and omega = ending. I have no idea if they invented it, or where they took it from, or how widely adapted this notation is.

But then, which symbol or name you use for the function does not matter. Just define it -- I doubt *anybody* would reference something that basic.

Using the standard lifting of functions to sets, we get

$\qquad\displaystyle \alpha(E) = \bigcup\_{e \in E} \alpha(e)$

for any set $E$ of edges; similarly for $\omega$.
> 2 votes

---
Tags: graphs, reference-request, notation
---


# Question
Title: Algorithm for arranging elements into different sized buckets
I have a set of items. For each item, there is a list of buyers I can sell it to and a corresponding price they will pay me. For example:

```
item1:        item2:       item3:       item4:
  john: 17      john: 19     bob:  42        ...
  bob:  23      mick: 22     mick: 44
  sue:  19      liz:  24     sue:  38
  liz:  20                   joe:  45

```

I need to assign each item to one buyer so as to maximise the amount of money I make. If it were as simple as this, the assignments would go

```
item1: bob
item2: liz
item3: joe
          ...

```

However, I also need to try to meet quotas of items for the buyers.

So these quotas might be:

```
bob:  99
sue:  30
john: 45
        ...

```

i.e. I need to sell a total of 99 items to Bob, 30 to Sue etc.

The quotas will not cover all items, so it could be that of a total of 1000 items, only 800 are forced to follow the quotas and the remainder can go to whichever buyer pays the highest amount.

The problem then, is to assign the items in such a way as to maximise revenue while still filling the quotas.

In some cases it will not be possible to meet the quotas because not every item can be assigned to every buyer - for example, if there were only the 3 items above and Joe had a quota of 2, I wouldn't be able to meet it as only item3 can be sold to him. It seems to me two types of solution are available in this case, either of which I'm open to.

1. Find a solution that minimises the number of unfilled quota positions and maximises revenue.
2. Run a preliminary algorithm that checks if the quotas are fillable. If they aren't, simply fail at that point (under the assumption that some user will then manually tweak the quotas and run the process again). If they are, then find a solution that fills them and maximises revenue.

I've thought of a few strategies, but none that has the mathematical rigour I'd like.

Also, I'm not really sure what flavour of problem this is, so if anyone can suggest a better title for this question, feel free to edit :)

For context, this is a work-related requirement for an energy broker that wants to assign customers (the 'items' in my example) across its pool of energy suppliers.

Edit: If this can be thought of as a form of the Generalized Assignment Problem (as per @fade2black's) answer, it may be helpful to tweak things in this way: items that can't be sold to a particular buyer are assigned a revenue of 0 with respect to that buyer.

So in other words, every item can be sold to every buyer, but some have a revenue of 0. Presumably any optimisation algorithm will then tend to filter these 0-revenue combinations out.

# Answer
Your problem is very similar to the Generalized Assignment Problem which is $NP$-complete.

The Generalized Assignment Problem states, using the terminology of the Knapsack Problem: given $n$ items and $m$ knapsacks with profit $p\_{ij}$ and weight $w\_{ij}$ if the item $i$ is assigned to the knapsack $j$. Also, each knapsack $j$ has capacity $c\_j$. The goal is to put each item into a knapsack so that the total profit would be maximum and the total items capacity in each knapsack $j$ would not exceed $c\_j$. Mathematically $$\text{Maximize } \sum\_{j=1}^{m}\sum\_{i=1}^{n}{p\_{ij}}x\_{ij}$$ $$\text{Subject to } \sum\_{i=1}^{n}{w\_{ij}}x\_{ij} \leq c\_j \text{ for each } j = 1,\dots, m$$ $$x\_{ij} = 0 \text{ or } 1$$

Your problem has similar structure. You have $n$ items and $m$ buyers (or knapsacks) with buying ability (or capacity). You also want to maximize the profit. The difference is that in your case capacities are equal to profits $w\_{ij} = p\_{ij}$, however you may have additional requirement such as not all buyers can buy all items (or not all items can be assigned to all knapsacks).

My guess is that additional requirements wouldn't make it solvable in polynomial time. So, you may try, for instance, Greedy approximation algorithm, or formulate it as an Linear (Integer) Program and solve it yet another approximation algorithm.
> 2 votes

# Answer
Your problem can be solved in polynomial time.

You mention two possible goals and say you'd be happy with a solution to either. The first goal isn't well-defined, so I'll describe a solution to the second goal. I can see two possible approaches: (a) use integer linear programming (ILP), (b) use network flow. The former will be simple to implement, and is flexible (if you later have new constraints it'll be easy to add them), but if you're unlucky, the running time could be exponential. The second has the advantage of running in polynomial time, but it might be more work to implement. fade2black described the ILP approach well, so I'll describe the network flow approach.

To solve the problem with network flow, formulate this as a minimum-cost network circulation problem. In network flow, each edge has a capacity: an upper bound on the amount of flow through that edge. Minimum-cost circulation also allows you to specify a lower bound on the amount of flow through that edge, and the per-unit cost of sending flow through that edge.

We'll construct a directed graph with a source node $s$, a node $u\_i$ for each item, a node $v\_j$ for each buyer, and a sink node $t$. Add edges $s \to u\_i$ with cost 0, lower bound $1$, and upper bound (capacity) $1$. Add edges $u\_i \to v\_j$ with cost equal to the negative of the amount buyer $j$ will pay for item $i$, lower bound $0$, and upper bound (capacity) $1$. Add edges $v\_j \to t$ with cost 0, lower bound equal to the quota for buyer $j$, and upper bound $\infty$. Finally, add an edge $t \to s$ with cost 0, lower bound 0, and upper bound $\infty$. Now look for the minimum-cost circulation in this graph. That will correspond to a solution that maximizes the revenue, subject to the requirement that all quotas must be filled.
> 3 votes

---
Tags: algorithms, optimization, assignment-problem
---


# Question
Title: Find all disconnected directed (cyclic) subgraphs and transform them into stars
I have a graph $G=(V,E)$ that consists of many disconnected directed subgraphs, some of them may be cyclic. (Basically a "forest" consisting of directed trees and some directed disconnected cyclic graphs added into it).

I want to find all of these disconnected subgraphs and turn them into stars given by the key of the node.

I've built a directed graph (using Python's `networkx` library) and now I am kinda stuck how to find those disconnected subgraphs, because some of those subgraphs will have source and some of those wont.

How to proceed? Thanks!

# Answer
> 2 votes
Probably you want to compute *weakly connected components*, a subgraph having a path between every two vertices in the underlying undirected graph. Computing the weakly connected components is easy: first transform the directed graph into undirected by removing "directions" of each edge and run DFS/BFS on that graph (by looping on vertices!). Alternatively, if you're interested in the *strongly connected components* then you should run one of the algorithms computing SCCs. This gives you components $C\_1, \dots, C\_n$.

Then you can do whatever you want to do on these components.

---
Tags: algorithms, graphs
---


# Question
Title: Does every 3CNF propositional formula has an equisatisfiable 2CNF propositional formula
Does every 3CNF propositional formula has an **equisatisfiable** 2CNF propositional formula?

# Answer
> 3 votes
Yes. If the 3CNF formula is satisfiable, here is an equisatisfiable 2CNF formula: True. If the 3CNF formula is not satisfiable, here is an equisatisfiable 2CNF formula: False. So yes, every 3CNF formula has an equisatisfiable 2CNF formula.

If you want to actually *find* that formula in a reasonable amount of time, then we don't know of any way to find such a formula in polynomial time (existence of such a method would prove that P = NP).

---
Tags: logic, first-order-logic, propositional-logic
---


title: create new data from trained ANN

text:
# Question
Title: create new data from trained ANN
I use a very simple neural network to make classification between classes. Once my ANN is trained I'm able to present new and unknown data, and get a good classification.

Is there a simple way to reverse the process and create an artificial data, knowing at which class it should belong ?

What would be the method name ?

Thanks a lot !

# Answer
> 1 votes
Of course you can create artificial data. Simply pick the inputs to the neural network randomly; that's an artificial instance. You can run it through the neural network and tell what class the neural network will assign to it. That doesn't mean you know what class it *should* be given, or what is the *correct* class; there's no way to get that (you can't get something from nothing).

---
Tags: neural-networks
---


# Question
Title: What is the relation of complexity class $L^L$ to other complexity classes?
What is the relation of complexity class $L^L$ to other complexity classes?

(Here $L^L$ is the complexity class of decision problems solvable by a TM in logspace with an oracle for a language in logspace.)

# Answer
$L$ is self-low, i.e. $L^L=L$. The reason being that you can compute each oracle call yourself, using additional logarithmic space.
> 3 votes

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


# Question
Title: Weighted Matching with multiple assignments and min assignments
I need to do a weighted matching between two sets (say students and professors). The set of students is much larger than set of professors. So multiple students can be matched to professors. However, each professor also has a minimum number of students he needs. So even though all students maybe matched best with one professor, some need to distributed amongst the rest, as long as they can be matched of course -- since not all professors and students will have edges between them.

Standard Bipartite matching won't work since they match one to one. Max Flow won't work since they don't consider weights.

# Answer
> 1 votes
Your problem can be solved with minimum-cost network flow, by solving a circulation problem. The circulation problem is a variation on network flow where edges have an upper bound on the amount of flow through that edge (called the capacity of the edge), a lower bound on the amount of flow through the edge, and a per-unit cost for sending flow through the edge. In your problem, you have a source vertex $s$, a vertex $v\_i$ for each professor, a vertex $w\_j$ for each student, and a sink vertex $t$. You have edges $s \to v\_i$, $v\_i \to w\_j$, and $w\_j \to t$. You put a lower bound on the edge $s \to v\_i$ corresponding to the number of students who professor $i$ must be matched with, an upper bound of $1$ on each edge $v\_i \to w\_j$, and a cost on the edge $v\_i \to w\_j$ that corresponds to the negative of the weight. There exist polynomial-time algorithms to solve this variant of network flow.

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


# Question
Title: Verifying execution of code in trustless environment
Let us assume I have a Program P running on remote computer generating output O. Without trusting the remote environment and not having to verify the output O, is there is a way to validate that Program P has indeed been executed and resulted in output O ?

Let me know if the question is too vague. I will clarify.

# Answer
> 1 votes
This is the problem of securely outsourcing computation. There's lots of work on this problem in the cryptographic literature; if you do a search at \[Crypto.SE\] and \[Security.SE\], you should find some references. Many of the schemes are probabilistic: if you the remote computer cheats, you have some chance of detecting that fact. I know of two general approaches: one based on cryptographic commitments, and another based on SNARKs. You should be able to turn up papers on how SNARKs work.

---
Tags: computation-models, distributed-systems, logical-validity
---


# Question
Title: The use of binary search when determining whether a point lies inside a given convex hull
In an answer to the problem of determining whether or not a point lies inside a given convex hull, a thesis is mentioned, which says :

> For repeated queries with preprocessing allowed, we develop a special method that relies on the convexity of the polygon. Recalling Theorem 3.5, the vertices of a convex polygon occur in angular order about any interior point. Find such a point O and consider the N rays from O that pass through the vertices of P. (Figure 4.8.) These rays partition the plane into N pie-shaped wedges. Each wedge is divided into two pieces by a single edge of P. One of these pieces is wholly interior to P, the other wholly exterior. Treating O as the origin of polar coordinates, we may find the wedge in which z lies by a single binary search, since the rays occur in angular order.

How would one do the binary search (assuming the convex hull's vertices are given in counter-clockwise order)?

# Answer
So, the situation is that you have the vertices $\mathbf{v}\_i$ of a polygon that defines a convex hull and a point $\mathbf{O}$ inside this polygon. Furthermore you have the vectors connecting $\mathbf{O}$ with each vertex of the polygon and the vertices are ordered. To construct a binary search algorithm that determines in which wedge the point $\mathbf{z}$ lies you have to find out on which side of a line connecting $\mathbf{O}$ and a given vertex $\mathbf{v}$ the point is.

Consider $\mathbf{r}\_v$ to be the connecting vector from $\mathbf{O}$ to vertex $\mathbf{v}$. A normal vector $\mathbf{n}\_v$ to $\mathbf{r}\_v$ is simply given by

$\mathbf{n}\_v = \left(\matrix{-{\mathbf{r}\_v}\_y \\ {\mathbf{r}\_v}\_x}\right)$.

Let us now project the vector $\mathbf{r}\_z$ connecting $\mathbf{O}$ and $\mathbf{z}$ on the normalized $\mathbf{n}\_v$:

$d\_z = \frac{\mathbf{n}\_v \mathbf{r}\_{z}}{|\mathbf{n}\_v|}$.

With the sign of $d\_z$ we can now decide on which side of the line z lies.

Just draw down the situation and this construction and this will become obvious. There may be a more elegant way to do this but this approach will work.

You probably have to construct some more logic because the vertices actually are in a cyclic arrangement but that should not be too difficult.
> 4 votes

---
Tags: algorithms, binary-search, convex-hull
---


# Question
Title: Examples of problems for each class in $L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE$
Given that $L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE$ and that it is commonly believed that all these inclusions are strict can you provide examples of problems that are believed to be in each class and not in the preceding ones?

To try to narrow the scope of the question, could you provide paradigmatic examples of problems that are believed to be in each class and why they are so?

# Answer
> 4 votes
You can take complete problems for each class. Think of a complete problem as one which represents the "hardness" of this class, then under the assumption that all of the inclusions are strict, such a problem can not reside in the weaker classes.

If $\mathsf{L\neq NL}$, any $\mathsf{NL}$ complete problem (under logspace reductions) cannot lie in $L$ . An example for such a problem is deciding whether there exists a path between two given vertices in a directed graph.

If $\mathsf{P\neq NL}$, no $P$ complete problem (under logspace reductions) can lie in $\mathsf{NL}$ . One example for such a problem is $CVAL$, given a circuit and input, does the circuit outputs $1$ on the given input. You can find other examples of $P$ complete problems here.

If $\mathsf{P\neq NP}$, then NP-complete problems (under polynomial time reductions) cannot lie in $\mathsf{P}$. You can find hundreds of examples here, traveling salesman, hamiltonian path, SAT, just pick your favorite.

You probably got the point by now, but i'll say it anyway. If $\mathsf{NP\neq PSPACE}$ then PSPACE complete problems (under polynomial time reductions) cannot lie in $\mathsf{NP}$. Famous complete problems here are TQBF (checking if a CNF formula with quantifiers is true), and games (do I have a winning strategy in a game from a given position, of course you need to be careful and precisely define the language). You can find more examples on Wiki.

These were the easy examples, there are problems who are not complete for their class, but still believed to be hard. For example, FACTORING (deciding whether an integer has a factor smaller than some given number), is believed to be NP-intermediate (not NP complete but still not in P). See this question from cstheory about NL-intermediate problems. PSPACE is very far away from NP, and examples are easier here. If the polynomial hierarchy does not collapse, then any complete problem for $\Sigma\_i$ with $i\ge 2$ is in PSPACE but not in NP.

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Is this possible to find the maximum of differentiable and analytic function on finite and fixed interval in O(1) time using quantum computer?
$f$ is differentiable (continous) and analytic function.

If $x\in\mathbb{R} \land 0\le x\le1$ then $f(x)$ is **computable**, $f(x)\in\mathbb{R}$ and $0\le f(x)\le1$.

I have a conjecture that it is possible in O(1) constant time to find the maximum of $f$ in the interval \[0,1\] by using quantum computer.

Let some qubit be the domain of $f$ and all the values of $x$ where $0\le x\le1$ call this qubit *"input"* and there is quantum circuit that implements $f$.

At last we need another qubit to be the range of $f$ and call it *"output"*.

Now by using the quantum circuit we can make the *output* qubit depend on *input* qubit.

if $y=f(x)$ then $y$ depends on $x$.

The same thing can be done with bits:

Make some bit depend on another bit by using logic/boolean circuit/function.

Now the quantum computer modifies the *input* qubit so it starts at $x=0$ and changes state towards $x=1$ **gradually**.

At the same time that $x$ changes so $f(x)$ changes too, so the modification of *input* qubit also modifies the *output* qubit respectively.

The quantum computer will use third qubit that stores the maximum of $f$. The third qubit is initialized to zero and the state of *output* qubit is copied to the third qubit if and only if this operation will increase the value of the third qubit.

I think that this way the maximum of function $f$ can be found in O(1) constant time, maybe even 1 second.

Is my conjecture wrong?

# Answer
Yes, it's wrong.

First, you seem to be under the impression that you can say "hey, you qubits be the output of $f$ applied to these qubits" in some kind of permanent sense. Like, the output updates as the input is operated on. That's not how entanglement works. The best you can do is compute a superposition of many input/output pairs by applying $f$ to an input under superposition.

Second, you seem to think that you can do comparisons across different parts of the superposition or pull out information without weakening entanglement. You can't. You can interfere different parts of the superposition with each other, but that requires steps like uncomputing the input which you aren't taking into account.

Third, your algorithm has a step where "x changes gradually". That's a big red flag. In particular, this kind of thing always raises the question of "*how* gradually?". Does it have to get slower as the function get spikier? (Yes it always does.)

Fourth, there is a proof that no unstructured search over $N$ items can be done in less than $\Theta(\sqrt N)$ steps by a quantum computer. It's trivial to translate discrete search tasks into finding the maximum of an analytic function; your proposed $O(1)$ time bound is provably wrong before even looking at the details of your algorithm.

An example of a task somewhat similar to yours, that quantum computers can do faster than classical computers, is computing the gradient of an $N$-dimensional function at a point with one evaluation instead of $N+1$ evaluations.
> 3 votes

---
Tags: complexity-theory, time-complexity, quantum-computing
---


# Question
Title: Procedure to automatically solve field theorems in a SMT solver
I'm working with the Welder proof assistant. Basically, this system uses basic inference rules to modify the goal one wants to proof. At a latter step, the modified goals are passed to a SMT solver to see if it can prove them. I have already written automatic induction tactics that generate by themselves the induction hypothesis.

Now I want to write a procedure that will allow me to solve automatically the following problem:

> Proof basic field theory statements using the axioms of group and already proved lemmas.

Could you describe successful approaches to solve this problem?

Here I leave you the kind of axioms that I want to use:

And here you have the kind of goals I would like to proof automatically:

The idea is that the procedure is given the theorem, a list of lemmas (axioms of other proved theorems) and is able to **deduce by itself** the goal.

# Answer
> 3 votes
All of the theorems you want to prove (except uniqueAddNeutral) are of the form $\forall x . \phi(x)$ where $\phi(x)$ is quantifier-free. Herbrandization is typically the first step towards proving those theorems: replace $x$ with an arbitrary constant $c$, with no assumptions made about $x$, and prove $\phi(c)$ holds without making any assumptions about $c$.

The theorems you want to prove are simple enough that exhaustive search over candidate proof trees might suffice to find a proof. At each step, you apply one of the axioms, instantiating the universally-quantified variables in the axiom with appropriately chosen values. You have to choose which axiom to apply and how to instantiate the variables; typically you instantiate each variable in the axiom with one of the subexpressions in the current expression/goal, so there are only finitely many choices at each step, and you can simply exhaustively search over all possibilities (up to a given size/depth).

---
Tags: logic, proof-assistants, automated-theorem-proving
---


# Question
Title: Randomized linear search -- Why does reducing the sample size make the running time constant?
I have two search algorithms (for determining if an element $x$ is in a list $A$ of length $n$):

(1) Pick a random index $i$ from $L = \[1, \ldots n\]$. If $A\[i\] = x$, terminate. Otherwise, pick a new random index $i$, still in the list $L = \[1, \ldots , n\]$. Repeat until we've either found a $j$ such that $A\[j\] = x$ or until every index in $A$ has been exhausted.

(2) Similar to Algorithm $(1)$, except,for element $i$ at every iteration, we perform $L.\text{remove}(i)$ ($L$ has the index $i$ removed from it). This way, we're guaranteed to terminate within $n$ steps (as opposed to potentially running the algorithm forever, as in (1)).

Now, in (1):

> If we let $X = $ the number of iterations before Algorithm (1) terminates, we have $$X \sim \text{Geo}(1/n)$$ from which we get $E\[X\] = 1/(1/n) = n.$

In (2):

> Let Y = number of iterations before Algorithm (2) terminates. Let $Y\_i$ = event that the algorithm terminates after $i$ iterations.
>
> Then $$P(Y\_1) = \frac1n \\ P(Y\_2) = \frac{n-1}{n}\left(\frac1{n-1}\right) = \frac1n \\ P(Y\_3) = \underbrace{\left(\frac{n-1}n\right)\left(\frac{n-2}{n-1}\right)}\_{P(\text{two failures})} \ \underbrace{\left(\frac{1}{n-2}\right)}\_{P({\text{one success}})} = \frac1n \\ \vdots \\ P(Y\_n) = \frac1n$$
>
> hence $$E\[Y\] = \sum\_{i=1}^n iP(i \ \text{iterations are required to terminate}) = \sum\_{i=1}^n \frac1n = n \cdot \frac1n = 1$$ but this doesn't make any sense. How can the expected number of iterations be constant.

Shouldn't $E\[Y\]$ vary linearly with $n$? What's going on here? Also, when calculating the expected running time (of each of these algorithms), how do I take into account the possibility that the given list does **not** contain the element $x$? Obviously, it increases the expected running time, but by how much?

# Answer
> 1 votes
You made a simple algebraic error. You said $\Pr\[Y=i\] = 1/n$, then you wrote

$$E\[Y\] = \sum\_{i=1}^n i \Pr\[Y=i\] = \sum\_{i=1}^n {1 \over n},$$

but that is incorrect: you omitted the $i$ in the second sum, i.e., you didn't plug in the value of $\Pr\[Y=i\]$ correctly. Assuming that both indexing into the list and removing an item from the list can be done in one time step, the correct derivation is

$$E\[Y\] = \sum\_{i=1}^n i \Pr\[Y=i\] = \sum\_{i=1}^n i \cdot {1 \over n} = n(n+1)/2 \cdot {1 \over n} = (n+1)/2 = \Theta(n).$$

---
Tags: randomized-algorithms
---


# Question
Title: Algorithm to find the closest possible value among several combinations
I have the following problem and would like an orientation on which algorithms I can try to adapt to solve it in the best possible way.

***SCENARIO***

A company has a warehouse where it stores several products. A product can be stored in several packages, for example:

> 1 box with 10 units
>
> 1 box with 3 boxes of 10 units
>
> 1 box with 30 units
>
> 1 box with 5 boxes of 30 units

Eventually these products need to be dispatched for consumption in the company's stores. Each store makes its own request for products according to their needs.

However, such requests do not take into account the available packaging, ie the quantity requested may or may not coincide with the quantity of a particular packaging.

Example:

> 1 box with 8 lunits
>
> 2 boxes with 2 units
>
> 1 box with 4 units
>
> 1 box with 6 units

The store could request 13 units of product, and thus there would be no packaging combination that could total exactly 13 units.

However, there would be the following options to meet the store order:

> * 1 box of 8 units and 1 box of 4 units (total: 12)
> * 1 box of 8 units and 2 boxes of 2 units (total: 12)
> * 1 box of 8 units and 1 box of 6 units (total: 14)
> * 1 box of 8 units, 1 box of 4 units and 1 box of 2 units (total: 14)

In a scenario like this I need an algorithm that might find the packaging combination to be closer to the exact value.

In the real scenario, there are dozens of possible combinations, where I need to find 3 possible combinations:

* The combination that meets the exact requested quantity (requested: 20, combination: 20)
* The combination that gets as close as possible through a lower value than requested (requested: 20, closest combination: 18)
* The combination that answers as close as possible through a value greater than requested (requested: 20, closest combination: 23)

Is there an algorithm already known that can fit well into this scenario where I can just adapt to my context?

# Answer
This is a common problem so there certainly exist many approaches to solve it. Below I'll sketch such an approach. It probably has a name but I don't know it:

The approach essentially sets up an array of target order sizes with an array length of actual order size + largest available package size. In each array element we store the ID of the package that can be used to increase the overall combined package size from a known solution for some smaller order size to get to the order size related to the index of the array. When we filled up the array we can go back from a realizable solution to an order size of 0 by collecting all the packages that lead to the respective solution. So this will be some kind of a dynamic programming approach.

We start at an order size of 0, go through all available packages and set the array index given by the respective package size to the ID of the package. Now we repeatedly increase the order size by 1 up to the target order size and for each order size we do the following:

If there is an ID of a package in the respective array element we again go through all available packages and store their ID in the array element "order size + package size" if that array element does not yet contain an ID. Otherwise we do nothing and just go on.

When we filled up the array in this way we can search in the neighborhood of the target order size for the array element that best fulfills our needs and also contains a package ID. From there we add the stored package ID to our solution and go back in the array by the size of that package. We do this repeatedly until we are back at a test order size of 0.

Of course, the solution we obtained in this way is not necessarily unique. We can prioritize certain packages by the order in which we process them when filling up the array.
> 1 votes

---
Tags: algorithms, combinatorics
---


title: complexity theory NP

text:
# Question
Title: complexity theory NP
Ok, I really need help because I have read in so many books but still don't understand the complexity class NP.

These are the books:

1. Theoretische Informatik; Katrin Erk, Lutz Priese (german)
2. Grundkurs: Theoretische Informatik; Gottfried Vossen, Kurt-Ulrich Witt (german)
3. Theoretische Informatik; Ingo Wegener (german)

Links:

1. https://de.wikipedia.org/wiki/NP\_(Komplexitätsklasse) (german)
2. https://www.ibm.com/developerworks/community/blogs/jfp/entry/no\_the\_tsp\_isn\_t\_np\_complete?lang=en (english)

And I actually have more links but I can't post them here because I don't have enough reputation

So far I know:

1. A problem L is in NP when there exists a nondeterministic algorithm which solves problem L in polynomial time.
2. NP includes decision problems. If there exists a solution for these problems, it should be possible to check with a deterministic algorithm in polynomial time whether the solution is indeed a solution.

To 1.: is the calculated solution an exact match or is it just an approximation? To 2.: is it just necessary to be able to check in polynomial time? For example: the solution is not indeed a solution but I was able to check it in polynomial time. Is the problem still in NP?

For a problem to be in NP, I must have a nondeterministic algorithm which solves the problem in polynomial time. The solution is an exact match and I must be able to check in polynomial time with an deterministic algorithm that the solution is indeed a solution????????????????

Can someone please help me to understand.

Further thoughts: Let's take the TSP as an example. Question: Does a tour exist \<= k ?

Let's assume I wrote a nondeterministic algorithm, which calculates a tour \<= k. So my answer would be: Yes, a tour like that exists.

However Vladimir wrote in his answer: If this question can be answered by a polynomial time nondeterministic algorithm, then the language L is in NP.

So I gave an answer 'yes'; that means the TSP is in NP?! However what about if my answer would be: No, a tour like that does not exist! ? Then the TSP would not be in NP?

And looking on the other definition: Further I answered: Yes, a tour like that exists, because my nondeterministic algorithm calculated a tour like that. Now if I can check with a deterministic algorithm in polynomial time that the calculated tour is indeed verified to be correct, then TSP is in NP !?

# Answer
First of all note that a non-deterministic algorithm and a non-deterministic Turing machine are two different things.

A non-deterministic Turing machine is a computational model, while a non-deterministic algorithm "is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm" (Wikipedia). For example a QuickSort algorithm which partitions the array based on random choice of a pivot is a non-deterministic (probabilistic) algorithm.

So your definition 1 should be read as following

> A problem $L$ is in $NP$ when there exists a **nondeterministic Turing machine** which solves problem $L$ in polynomial time.

Similarly, the second definition should be read as following:

> NP includes decision problems. If there exists a solution for these problems, it should be possible to check on a **deterministic Turing machine** in polynomial time whether the solution is indeed a solution.

For the concept of $NP$ see this post.
> 1 votes

# Answer
I think you have misunderstanding with the word 'solution'. It seems that you use it both for an answer to the decision problem and for a certificate that is used in the verification algorithm.

A decision problem is specified by a language $L$, and the problem can be formulated as a question: "Does $L$ contain an input word $w$?"

In the definition of $\operatorname{NP}$ via nondeterministic machines, we consider only this question. If this question can be answered by a polynomial time nondeterministic algorithm, then the language $L$ is in $\operatorname{NP}$.

In the definition that uses verification algorithm, the input to the verification algorithm is different. The (polynomial time) verification algorithm receives the word $w$ and a certificate $z$. If $w$ is contained in $L$, then it should have a certificate (of polynomially bounded length) that the verification algorithm accepts, and if $w$ is not contained in $L$, then there should be no such certificate.

The two definitions are equivalent, because it is possible to guess bits of the certificate using nondeterministic choice, and one can take a sequence of nondeterministic choices that leads to the positive answer as a certificate.

Update:

Consider the TSP problem: Given a weighted graph and a number $k$, does there exist a hamiltonian cycle of weight $\leq k$?

To prove that it is in $\operatorname{NP}$, we can present a poly-time nondeterministic algorithm, which decides this problem. That is, algorithm takes a graph and a number $k$, and if there is a tour of length $\leq k$ in the given graph, then our algorithm has at least one computational path where it answers "yes"; and if there are no short tours, then every path answers "no"

Or we can use a second definition, say that the tour, which we can encode as a sequence of vertices of the graph, is itself a poly-size certificate for its existence. Then we need to present a poly-time deterministic algorithm that takes a graph, a number $k$ and a sequence of vertices and checks if the given sequence defines a tour and the length of this tour is less than $k$.
> 1 votes

---
Tags: complexity-theory, np, complexity-classes, traveling-salesman
---


# Question
Title: Using backtracking to find all possible permutations in a string
I came across this algorithm in a book, and have been struggling to understand the basic idea. The books says it uses backtracking to print all possible permutations of the characters in a string. In Python, the algorithm is given as:

```
def bitStr(n, s):
    if n == 1: return s
    return [digit + bits for digit in bitStr(1, s) for bits in bitStr(n - 1, s)]

print(bitStr(3, 'abc'))

```

I'm pretty weak in algorithmic thinking and am struggling for both an intuitive understanding of this, as well as tracing it. Can somebody explain what this algorithm does and how exactly is uses 'backtracking'?

# Answer
> 6 votes
Backtracking is a general algorithm "that **incrementally builds** candidates to the solutions, and abandons each partial candidate ("**backtracks**") as soon as it determines that the candidate cannot possibly be completed to a valid solution." (Wikipedia).

So, basically, what you do is build incrementally all permutations. As soon as as you build a single permutation, you backtrack and build another one, and so on until you generate all $n!$ possible permutations, say, on $n$ symbols.

**Example**: $n=3$, $S=\\{1,2,3\\}$.

You start with $1$. Then you move forward an choose $2$ (since $1$ has already been chosen), and then you choose $3$. At that point you have built the first permutation $123$. Then you backtrack and select $3$ instead of $2$, then select $2$, and you have $132$. You backtrack again, but you have already used $2$ and $3$, so you backtrack again (one level up where), and choose $2$ instead of $1$, then you select $1$, and finally $3$, so you have $213$.
The following picture should clarify the basic idea:

In other words, you simply traverse the tree, and when you reach the leaf you print the permutation. Then you backtrack one level up, and try another option. Moving one level up the tree is what we call the backtracking in this case.

As for implementation, the backtracking is usually implemented using recursive call(s) as in your example. I assume that you have necessary programming skills to implement this basic idea yourself, in particular solving problems using recursive calls.

# Answer
> 0 votes
Suppose that we have an alphabet $\Sigma$. Let $\Sigma^n$ denote all words of length $n$ over $\Sigma$. We can define $\Sigma^n$ inductively (for $n \geq 1$) as follows: $$ \Sigma^1 = \Sigma, \quad \Sigma^n = \\{ \sigma w : \sigma \in \Sigma, w \in \Sigma^{n-1} \\}. $$ This is exactly what you code is doing.

For example, running the procedure on $\Sigma = \\{a,b,c\\}$ and $n = 1$ will generate the set $\\{a,b,c\\}$. Running it with $n = 2$ will generate all concatenations of a symbol from $\Sigma$ and a word in $\Sigma^1 = \\{a,b,c\\}$. Running in with $n = 3$ will generate all concatenations of a symbol from $\Sigma$ and a word in $\Sigma^2 = \\{aa,ab,ac,ba,bb,bc,ca,cb,cc\\}$. And so on.

The given code generates these combinations in a specific order, but deciphering depends on specific features of the syntax of python.

---

As an aside, the word *permutation* has a different meaning in mathematics, which you can look up on Wikipedia or in discrete mathematics textbooks.

---
Tags: algorithms, permutations, backtracking
---


# Question
Title: Why is $\Sigma^*$ concatenated with some language regular?
Let $\Sigma=\\{a,b\\}$. Why is the concatenation of any language with $\Sigma^\*$ always regular? I found a problem where $(a+b)^\*$concatenated with $a^nb^n$ was regular?

# Answer
The claim is false. For example, if you concatenate $\\{ a^{n^2} b : n \geq 0\\}$ and $\Sigma^\*$ then you get a non-regular language (exercise).

In contrast, the concatenation of $\\{ a^n b^n : n \geq 0 \\}$ and $(a+b)^\*$ is regular, since it equals the latter; this is the case whenever the former language contains the empty word.

Finally, the concatenation of $\\{ a^n b^n : n \geq 1 \\}$ and $(a+b)^\*$ is again not regular, since intersecting it with $a^\*b^\*$ gives the non-regular language $ \\{ a^n b^m : m \geq n \geq 1 \\} $.
> 2 votes

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


title: Satisfiabililty sufficient condition?

text:
# Question
Title: Satisfiabililty sufficient condition?
The conjecture itself:

k-SAT formula is satisfiable if no pair of unit assignment $l$ and $\overline l$ imply the formula to contain unsatisfiable (k-1)-SAT.

Example (XOR-SAT has no edges and cycles in implication graph, so it's simple example):

$$(\overline x\oplus y\oplus z)\land(x\oplus y\oplus v)\land(x\oplus y\oplus w)\land(x\oplus z\oplus v)\land(x\oplus z\oplus w)\land(x\oplus v\oplus w)$$

If in this formula we'll put $x$, we get $(y\oplus z)\land(y\oplus\overline v)\land(z\oplus\overline v)$ which is unsatisfiable.

So, we only can put $\overline x$: this yields us $(y\oplus v)\land(y\oplus w)\land(v\oplus w)$ which is also unsatisfiable.

Now we conclude that formula is unsatisfiable.

My thoughts on it:

The rule surely works if $k = 2$: 2-SAT is unsatisfiable iff there are two unit assignments $l$ and $\overline l$ that make the formula to contain unsatisfiable 1-SAT (two opposing unit clauses).

In fact algorithm would be:

```
for i = 1..n
    assign x_i
    while unit clauses are presented
        apply unit propagation
    if opposing unit clauses found
        assign -x_i
            while unit clauses are presented
                apply unit propagation
            if opposing unit clauses found
                return UNSAT
return SAT

```

And it does actually the same as implication graph analisys (primitive, though).

But what about $k \> 2$?

For $k=3$ we'd need to change algorithm:

```
for i = 1..n
    assign x_i
    while unit clauses are presented
        apply unit propagation
    run algorithm for 2SAT
    if 2SAT returned UNSAT
        b_i = 1
    assign -x_i
    while unit clauses are presented
        apply unit propagation
    run algorithm for 2SAT
    if 2SAT returned UNSAT
        b_i += 2
    if b_i == 3
        return UNSAT
    else if b_i == 2
        add clause x_i
    else if b_i == 1
        add clause -x_i
    if b_i > 0
       i = 1
return SAT

```

Maybe this is not the best implementation, but this is the idea of algorithm. It applies unit assignment and then solves 2SAT for all 2-clauses, in fact it finds all connectivities between opposing literals (finding connectivity between $x$ and $\overline x$ means new unit clause).

# Answer
> -1 votes
taking the contrapositive, another stronger way of stating your question is "a SAT formula *f* is satisfiable iff either the sub-formulas *f1,* *f2* from the assignment of a variable *x* or *not x* are satisfiable". but this is exactly the idea behind the DPLL algorithm (originating as the simpler DP algorithm) provably guaranteed to find a SAT solution. your basic idea also shows the similarity of the method with Gaussian reduction; ie this is not usually remarked but DPLL algorithm appears to be like/ an analog of "boolean Gaussian reduction".

---
Tags: satisfiability
---


# Question
Title: Am I right about the differences between Floyd-Warshall, Dijkstra and Bellman-Ford algorithms?
I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you.

1. Dijkstra algorithm is used only when you have a single source and you want to know the smallest path from one node to another, but fails in cases like this.
2. Floyd-Warshall algorithm is used when any of all the nodes can be a source, so you want the shortest distance to reach any destination node from any source node. This only fails when there are negative cycles.
3. Bellman-Ford is used like Dijkstra, when there is only one source. This can handle negative weights and its working is the same as Floyd-Warshall except for one source, right? (This is the one I am least sure about.)

# Answer
> 30 votes
> Dijkstra's algorithm is used only when you have a single source and you want to know the smallest path from one node to another, but fails \[in graphs with negative edges\]

Dijkstra's algorithm is one example of a *single-source shortest path* or *SSSP* algorithm. Every SSSP algorithm computes the shortest-path distances from a chosen source node $s$ to *every* other node in the graph. Moreover, it computes a compact representation of all the shortest paths from $s$ to every other node, in the form of a rooted tree. In the Wikipedia code, `previous[v]` is the parent of $v$ in this tree.

The behavior of Dijkstra's algorithm in graphs with negative edges depends on the precise variant under discussion. Some variants of the algorithm, like the one in Wikipedia, always runs quickly but do not correctly compute shortest paths when there are negative edges. Other variants, like the one in Jeff Erickson's lecture notes always compute shortest paths correctly (unless there is a negative cycle reachable from the source) but may require exponential time in the worst case if there are negative edges.

> Floyd-Warshall's algorithm is used when any of all the nodes can be a source, so you want the shortest distance to reach any destination node from any source node. This only fails when there are negative cycles.

That's correct. Floyd-Warshall is one example of an *all-pairs shortest path algorithm*, meaning it computes the shortest paths between *every* pair of nodes. Another example is "for each node v, run Dijkstra with v as the source node". There are several others.

> Bellman-Ford is used like Dijkstra's, when there is only one source. This can handle negative weights and its working is the same as Floyd-Warshall's except for one source, right?

Bellman-Ford is another example of a *single-source* shortest-path algorithm, like Dijkstra. Bellman-Ford and Floyd-Warshall are *similar*—for example, they're both dynamic programming algorithms—but Floyd-Warshall is *not* the same algorithm as "for each node v, run Bellman-Ford with v as the source node". In particular, Floyd-Warshall runs in $O(V^3)$ time, while repeated-Bellman-Ford runs in $O(V^2E)$ time ($O(VE)$ time for each source vertex).

For further details, consult your favorite algorithms textbook. (You do *have* a favorite algorithms textbook, don't you?)

# Answer
> 3 votes
The Wikipedia page on the shortest path problem describes two different problems: SSSP and APSP.

Single source shortest path (SSSP):

* Dijkstra's algorithm: solves the single-source shortest path problem.
* + Constraints: Only Negative edges it cannot handle.
* + Unweighted graphs: Dijkstra's is the same as BFS.
* Bellman–Ford algorithm: solves the single-source problem if edge weights may be negative. This is improvement on Dijkstra where it is now able to handle negative weights as well.

All pair shortest path (APSP):

* Floyd–Warshall algorithm: solves all pairs shortest paths. Handles both positive and negative edges.
* + Constraints: Cannot handle negative cycles.

Hence, Floyd–Warshall is not the same as BFS, although the underlying methodology is same, dynamic programming.

# Answer
> 2 votes
All three algorithms are covered in the lecture slides by Prof. Jaehyun Park (Stanford University). Here is the link Shortest Path Algorithms

# Answer
> 2 votes
Perhaps this should be a comment rather than an answer, but it is a distinction between these algorithms that other answers don't mention.

People tend to call Floyd's algorithm *Floyd-Warshall*, but Floyd's and Warshall's algorithms are not the same.

Warshall's paper observes that if you use Floyd's algorithm on a binary incidence matrix, what you're doing is matrix multiplication; hence, it can actually be implemented that way, and e.g. if you can do the vector multiplication in $O(1)$, your algorithm becomes $O(n^2)$.

---
Tags: algorithms, graphs
---


# Question
Title: Why do functions containing `await` need to be `async`?
From what I understand, `async`/`await` enables to avoid the "callback pyramid of doom".
Let's say that I have `funcA()`, `funcB()` and `funcC()` that are `async` functions, now if I do something like that:

```
func someFunction() -> T {
let myValueA = await funcA()
let myValueB = await funcB()
let myValueC = await funcC()
return doSomething(myValueA, myValueB, myValueC)
}

```

Why do some languages (for instance JavaScript) require you to annotate your function with `async` ?
What would be the issue issue if the function wasn't asynchronous? I mean, since the function already contains `await`s, can't it be already considered as a non blocking function ?

Thank you

# Answer
The `async` annotation changes the way the body of the function is interpreted. Now you can clearly infer that if the body contains `await`, it must be `async`, but there are a couple of reasons why it makes sense to require an annotation.

The primary reason is, frankly, likely clarity. C# popularized this syntax and is a language that emphasizes declaring intent. My understanding (from vague recollections of blog posts) is that the C# designers view the fact that they didn't do a similar thing for generator syntax (i.e. `yield`) as a mistake or at least unpleasant compromise. Note that in JavaScript you *do* need to indicate a function is a "generator function" in much the same way as `async`. At any rate, both `async`/`await` and `yield` lead to dramatically different semantics, and you probably want to be clear that that is intended and understood. (A minor factor for C# was to make the `await` keyword contextual to avoid backwards compatibility issues.)

As a more technical reason, `async` and JavaScript's `function*` change the behavior of a function even if you *don't* use `await`/`yield`. In C#, an `async` method with no `await` will run synchronously, but it will still package up the result in a `Task` object. Similarly, in JavaScript, a generator function with no `yield` still returns an empty `Iterable` rather than `undefined`. If the `async`/`function*` aspect was inferred from usage of `await`/`yield`, then in these cases you would need to explicitly create a `Task` or `Iterable`. This isn't so bad in C# where the type system will require this, but in JavaScript there's a much greater chance for uncaught errors. Regardless, it's also bad for exploration since commenting out a line of code might dramatically change the behavior and type of the function.
> 3 votes

---
Tags: programming-languages, concurrency
---


# Question
Title: Tight bound on the number of divisors of n
The inner loop of this pseudocode runs only for the divisors of n

```
for i=1 to n:
   if(n%i==0):
      for j=1 to n:
         Do something in constant time

```

If I can get a bound on the number of divisor of n(The condition in the if statement) then I can get its time complexity.Please Help ?

# Answer
Assume your input is $n$. I also assume that you know that we measure the time complexity of an algorithm as a function of input length to this algorithm which is $\log\_2{n}$ in this case. Then even the following simple loop would take exponential time (as a function of input size)

```
for i=1 to n:
   print "hi"
end

```

since it loops $n$ times, where $n = 2^{\log\_2{n}} = 2^{\text{input size}}$.

More precisely, its running time (as Yuval Filmus commented) is roughly $O(nn^{1/{\log{\log{n}}}})$ which is still exponential. But since your algorithm is $O(n^2)$ it is pseudo polynomial (polynomial in the numeric value of the input, not input size).
> 1 votes

# Answer
Your test whether i is a divisor of n runs for all 1 ≤ i ≤ n, therefore the execution time is at least $\theta(n)$. You can easily reduce that to $\theta(n^{1/2})$ be finding divisors $i≤n^{1/2}$ and observing that with a divisor i, n / i is also a divisor.
> 0 votes

---
Tags: number-theory, mathematical-foundations
---


# Question
Title: Real-valued genetic algorithm offspring out-of-bounds
I have a fairly simple real-valued genetic algorithm that seems to work fairly well, however it currently has some issues that I'm hoping to get some help with. If we consider a 1-dimensional problem, I use the following method to produce 3 children/offspring $(c\_{1,2,3})$ from 2 parents $(p\_{1,2})$: $$c\_{1} = 0.5p\_{1}+0.5p\_{2}$$ $$c\_{2} = 1.5p\_{1}-0.5p\_{2}$$ $$c\_{3} = -0.5\_{1}+1.5p\_{2}$$

For example, if we consider a problem where the bounds are $0\leq x\leq 10$, and I have 2 parents with $x$-values given by $p\_{1} = 2.55$ and $p\_{2} = 9.92$, then we produce 3 children with the following $x$-values:

$$c\_{1} = 6.235$$ $$c\_{2} = -1.135$$ $$c\_{3} = 13.605$$

As can be seen, child 1 will always be within the problem bounds since it's simply an average of its parents, however children 2 and 3 have $x$-values that are outside the bounds of the problem $(0\leq x\leq 10)$. As such, what I then do is simply have a loop that adds 1 to the value of child 2 and subtracts 1 from the value of child 3 until they go back within bounds, and then carry on with the rest of the algorithm. But this seems like a "cheap trick". As such, I was wondering if better methods are used to deal with children/offspring that have values outside of the problem bounds, or if my method is actually acceptable.

# Answer
> 1 votes
Anything is acceptable. These are all heuristics; all that matters is results (i.e., whether it helps you find a good solution to the problem, and how quickly it does so).

One standard method is to "clip" all values to be within the bounds. In other words, if the value is smaller than 0, you replace it with 0; if it is larger than 10, you replace it with 10. This ensures that the value will be within bounds.

There are other methods as well. For instance, you could let $y = 10 \sigma(x)$ where $\sigma(x) = 1/(1+e^{-x})$. You apply genetic programming to the values $x$ (so you do mutation and crossover operations on the $x$ values), but then you calculate $y$ and use that as the actual output. Note that $x$ can be any real number ($-\infty \< x \< \infty$) and the definition of $y$ will ensure that $0 \le y \le 10$.

# Answer
> 1 votes
In GAs, there are two main strategies for generating new solutions:

1. Ensuring solutions are feasible (i.e. meet the problem constraints).
2. Allowing infeasible solutions to be generated and then repairing them.

The latter can often be preferable, particularly when good solutions lie on the boundaries of the feasible region.

Here is a survey of alternative methods for repairing infeasible solutions.

---
Tags: optimization, genetic-algorithms, numerical-algorithms
---


# Question
Title: Identifying set of longest time periods excluding overlapping time ranages
Suppose I have set of time records as follows

```
08:00 - 12:00
10:00 - 12:00
08:00 - 13:00
13:00 - 19:00
12:00 - 17:00

```

Now I want to select set of time records that are not overlapping and has the largest sum.

```
 08:00 - 13:00 + 13:00 - 19:00 = 12hours

```

My current approach is

1. Sort the records by start time
2. Select the first record and compare with each record and get the sum and store sum and the index of records.
3. Then select the second item repeat the process.
4. Loop through **sum** array and find the largest sum and indexes of records

Is there any better approach I can follow ? Is this a problem related to Dynamic programming ?

Thanks.

# Answer
Your problem is known as *weighted interval scheduling*, and can be solved using dynamic programming. It's a nice exercise. You can find the solution in these lecture notes as well as in many other places.
> 1 votes

---
Tags: optimization, dynamic-programming, greedy-algorithms
---


# Question
Title: Is this case of weighted 2SAT NP-complete?
Weighted 2SAT asks if it is possible to satisfy the formula with at most $k$ variables set as positive/negative. Trivially, every instance must be in 2CNF. It is known to be $\mathsf{NP}$-complete.

We have following additional restriction: each variable appears twice as positive and once as negative or vice versa.

Example of instance:

$(x\lor y)\land(x\lor z)\land(\overline x\lor t)\land(\overline y\lor z)\land(\overline y\lor \overline t)\land(\overline z\lor \overline t)$

Is this weighted 2SAT variant $\mathsf{NP}$-complete?

Of course, if vertex cover where each vertex has only 2 edges is $\mathsf{NP}$-hard, this also must be $\mathsf{NP}$-hard. So, if such result is known, then it also can be an answer. Ah, well, this does not help.

# Answer
> 4 votes
You can express the predicate "$x = y$" using one occurrence of each polarity: $$ (x \lor \lnot y) \land (\lnot x \lor y). $$ Consider now an instance of weighted 2SAT, in which each variable appears at most $M$ times. Duplicate each variable $M$ times, and enforce that all copies are the same using the gadget above. Replace each occurrence of each variable by a distinct copy of the variable. If the original instance asks for an assignment with at most $k$ positive variables, ask for at most $Mk$ positive variables. We obtain an instance of your problem which is equivalent to the original problem.

This shows that your problem is also NP-complete.

---
Tags: np-complete, 2-sat
---


# Question
Title: Splitting a set of points in the plane evenly and sorting it
Input: A set of points P(x,y). There are two versions of it - Px, sorted by x and Py, sorted by y.

Output: The two even halves of Px, sorted by y.

The trick here is that it has to work in linear time, otherwise, it's rather useless. What I've come up with so far is finding the midpoint of Px, let's call it Px\[mid\] and then iterating over Py, checking if each point's x coordinate is bigger than Px\[mid\] and then assigning it to the appropriate half.

Example:

```
Px = [(1,7),(2,3),(3,1),(4,-2)]
Py = [(4,-2),(3,1),(2,3),(1,7)]
Px[midpoint] = (2,3)
Ly = [(2,3),(1,7)]
Ry = [(4,-2),(3,1)]

```

This works quite well, if you account for points with equal x coordinates and compare said points by y instead (and vice versa), which sorts them in a way that avoids potential surprises. Where it fails is the following case:

```
Px = [(1,7),(2,-3),(2,-3),(4,-2)]
Py = [(2,-3),(2,-3),(4,-2),(1,7)]
midpoint = 2
P[midpoint] = (2,-3)
Ly = [(2,-3),(2,-3),(1,7)]
Ry = [(4,-2)]

```

I can't seem to think of a way to exclude non-distinct points from the left half, when they're equal to the midpoint. Again, keep in mind that this has to work in linear time, so I can't just split Px into two halves and search for points which might belong to it for the odd case.

# Answer
This is not so hard to fix. First, calculate the median $m$. Then calculate the number of points strictly left of the median $\ell$. Take all of them from Py, and take the first $n/2-\ell$ points whose $x$ value is $m$ (where $n$ is the total number of points). These form the first half, and the rest of the points form the second half.
> 2 votes

---
Tags: algorithms, euclidean-distance
---


# Question
Title: quicksort - Why is $\log_4 n$ used as an approximation instead of $\log_2 n$?
Below is an excerpt from Khan Academy's Quick Sort Analysis page.

In the average case of quicksort they assume that each time the partition function breaks the input array into the ratio 1:3 each time.

So why is it easier to assume $\log\_4 n$ levels when the $n$ elements are being partitioned ? Why not assume it to be $\log\_2 n$ levels ?

Wouldn't $\log\_4 n$ and $\log\_2 n$ mean the same thing here ?

# Answer
No, $\log\_4 n$ is not the same as $\log\_2 n$. $\log\_4$ is exactly $\frac{\log\_2 n}{2}$. At the end of the complexity computation you can obviously say that $O(\log\_4 n) = O(\log\_2 n)$. But at this point they aren't computing the complexity (yet). They are doing "exact" math. If you have an array with $n$ elements and you always divide it by $4$, it will take exactly $\lceil\log\_4 n \rceil$ iterations until you reach the size $1$, and not $\lceil \log\_2 n \rceil$.

One more thing. They don't proof, that the average runtime is $\Theta(n \lg n)$. Because the array will obviously not always split with a ratio of 1:3. They only give you some intuition, why the complexity makes sence. Like they mention in the article:

> Showing that the average-case running time is also $\Theta(n \lg n)$ takes some pretty involved mathematics, and so we won't go there.
> 4 votes

# Answer
You should forward this question to the authors of the document you refer to. What the text you quote provides is intuition on the performance of quicksort on random inputs. Actual *proofs* use different approaches (or a much more refined version of the same approach).

For the actual proof, you can refer to slides of Xi Chen, which start with a similar intuition, and then give an actual proof.

Finally, $\log\_2n$ and $\log\_4n$ are the same up to constant factors, that is $\log\_2n = \Theta(\log\_4n)$, but sometimes we are interested in the hidden constants; for example, we might be interested in the average number of comparisons, and use this to compare different algorithms.
> 3 votes

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


# Question
Title: How to understand the analysis of expected running time of randomized quick-sort in this paper?
I'm learning the book named Data Structures & Algorithms in Python.

On Page 557-558, there is a proof of the expected running time of randomized qucick-sort. I have some problems confusing me some days. I will note them in bold form.

Here's orginal text:

> **Proposition 12.3:** *The expected running time of randomized quick-sort on a sequence $S$ of size $n$ is $O(n \log n)$*.
>
> **Justification:** We assume two elements of $S$ can be compared in $O(1)$ time. Consider a single recursive call of randomized quick-sort, and let $n$ denote the size of the input for this call. Say that this call is “good” if the pivot chosen is such that subsequences $L$ and $G$ have size at least $\frac{n}{4}$ and at most $\frac{3n}{4}$ each; otherwise, a call is “bad.”
>
> Now, consider the implications of our choosing a pivot uniformly at random. Note that there are $\frac{n}{2}$ possible good choices for the pivot for any given call of size n of the randomized quick-sort algorithm. Thus, the probability that any call is good is $\frac{1}{2}$. Note further that a good call will at least partition a list of size $n$ into two lists of size $\frac{3n}{4}$ and $\frac{n}{4}$, and a bad call could be as bad as producing a single call of size $n−1$.
>
> Now consider a recursion trace for randomized quick-sort. This trace deﬁnes a binary tree, $T$, such that each node in $T$ corresponds to a different recursive call on a subproblem of sorting a portion of the original list.
>
> Say that a node $v$ in $T$ is in ***size group*** $i$ if the size of $v$’s subproblem is greater than $\left(\frac{3}{4}\right)^{i+1}n$ and at most $\left(\frac{3}{4}\right)^in$ Let us analyze the expected time spent working on all the subproblems for nodes in size group $i$. By the linearity of expectation (Proposition A.19), the expected time for working on all these subproblems is the sum of the expected times for each one. Some of these nodes correspond to good calls and some correspond to bad calls. But note that, since a good call occurs with probability $\frac{1}{2}$, the expected number of consecutive calls we have to make before getting a good call is $2$.

---

> ⓵ Moreover, notice that as soon as we have a good call for a node in size group $i$, its children will be in size groups higher than $i$.
>
> ⓶ Thus, for any element $x$ from the input list, the expected number of nodes in size group $i$ containing $x$ in their subproblems is $2$. In other words, the expected total size of all the subproblems in size group $i$ is $2n$.

---

> Since the nonrecursive work we perform for any subproblem is proportional to its size, this implies that the total expected time spent processing subproblems for nodes in size group $i$ is $O(n)$.
>
> The number of size groups is $\log\_{\frac{4}{3}}n$, since repeatedly multiplying by $\frac{3}{4}$ is the same as repeatedly dividing by $\frac{4}{3}$. That is, the number of size groups is $O(\log n)$. Therefore, the total expected running time of randomized quick-sort is $O(n\log n)$. (See Figure 11.13.)

Here are my problems:

1. According this sentence:
> ⓵ Moreover, notice that as soon as we have a good call for a node in size group $i$, its children will be in size groups higher than $i$.

Which size group does node $s(a)$ belong to? And why?

2. > ⓶ Thus, for any element $x$ from the input list, the expected number of nodes in size group $i$ containing $x$ in their subproblems is $2$. In other words, the expected total size of all the subproblems in size group $i$ is $2n$.

I can't really understand the meaning of this sentence.

# Answer
> 1 votes
The root node corresponds to a subproblem of size $n$. This is larger than $(3/4)^1 n$ and at most $(3/4)^0 n$, so the root node lies in group $0$.

Given any element $x$ and any integer $i$, the expected number of subproblems of group $i$ containing $x$ is at most $2$. This is because if $P$ is a subproblem of group $i$ containing $x$ and $Q$ is its child subproblem containing $x$, then $Q$ is of group $i+1$ with probability at least $1/2$. (Some calculation is needed here.)

Linearity of expectation shows that the expected total size of all subproblems of group $i$ is at most $2n$ — we get this by summing the expected number of subproblems of group $i$ containing $x$ over all possible elements. (You can only understand this if you know what *linearity of expectation* is.)

---
Tags: algorithm-analysis, runtime-analysis, sorting, randomness, quicksort
---


# Question
Title: A 2D Layout Algorithm for Small, Sparse, and Undirected Graphs with a Specific Edge Length
I would like to to draw a graph where every edge $e\_m$ has a predefined length of $l$. Given that the graph is small and sparse, it should be feasable. However, I did not manage to find an algorithm which does this (or one that is suitable to modify) yet I'm sure that this is a solved problem. Does anyone know of such a layout algorithm and could point me to an implementation or paper?

# Answer
"Planar Embeddings of Graphs with Specified Edge Lengths" by Cabello, Demaine, and Rote (or one of the references they cite) seems to solve your problem.

If you don't care about edges crossing too much, a simple heuristic approach could be gradient descent. Start with a random position and iteratively wiggle the nodes a bit to decrease the sum of differences of the current edge lengths to your desired lengths.
> 3 votes

---
Tags: graphs, reference-request, graph-drawing
---


# Question
Title: Is resolution complete or only refutation-complete?
Going through some knowledge representation tutorials on resolution at the moment, and I came across slide 05.KR, no77.

There it is mentioned that "the procedure is also complete".

I think this completeness can not mean that if a sentence is entailed by KB, then it will be derived by resolution. For example, resolution can not derive $(q \lor \neg q)$ from a KB with single clause $\neg p$. (Example from KRR, Brachman and Levesque, page 53).

Could anyone help me figure out what is meant in this slide? Is the completeness of slide refer to being refutaton-complete and not a complete proof procedure?

# Answer
> 13 votes
Resolution is complete as a refutation system. That is, if $S$ is a contradictory set of clauses, then resolution can refute $S$, i.e. $S \vdash \bot$.

This is sufficient since $T \vdash A$ is equivalent to $T \cup \\{\lnot A\\} \vdash \bot$. So if we want to see a formula $A$ is derivable from $T$, we only need to check if there is a refutation proof for $T \cup \\{\lnot A\\}$ which can be checked using resolution.

# Answer
> 8 votes
Resolution is only refutationally complete, as you mentioned. This is *intended* and very useful, because it drastically reduces the search space. Instead of having to eventually derive every possible consequence (to find a proof of some conjecture), resolution is only trying to derive the empty clause.

# Answer
> 2 votes
It is also implicationally complete in the following sense:

If a set of clauses $F$ implies a non tautological clause $C$, then it is always possible to derive a single clause $C'$ that subsumes $C$ (i.e. $C' \subseteq C$).

Source:
Christian G. Fermüller, Implicational Completeness of Signed Resolution, 2002

Note that the original result is refered to:
R.C.T. Lee. A completeness theorem and a computer program for nding theorems derivable from given axioms . Ph.D. Thesis, University of California, Berkely, 1967.

---
Tags: logic, first-order-logic
---


title: Merge Leaf labeled trees

text:
# Question
Title: Merge Leaf labeled trees
I have a set of leaf-labeled trees. I want to concatenate them into a single leaf labelled tree in such a way that the height of the resulting tree is smallest possible. Can somebody please help me to generate an algorithm for this task, with good performance?

Leaf labelled tree is a tree in which all the data is held at leaves.

# Answer
> 0 votes
You can solve this using dynamic programming. Given trees $T\_1,\ldots,T\_n$, for each $1 \leq a \leq b \leq n$ compute the best way of concatenating $T\_a,\ldots,T\_b$. Details left to you.

---
Tags: algorithms, graphs, algorithm-analysis, time-complexity, trees
---


# Question
Title: Are degree and order the same thing when referring to a B-Tree?
I know the term **order** of a B-tree. Recently I heard a new term: **B tree with minimum degree of 2.**

We know that the degree is related to a node but what is the degree of a tree?
Does degree impose any kind of a restriction on the height of a B-tree?

# Answer
I don't think that **degree** of a tree is a standard term in either graph theory nor data structures. A degree is usually a property of a node/vertex of a graph, which denotes the number of its incident edges. For trees you sometimes consider only the edges to the children.

I suppose "B-tree with minimum degree of 2" means that every node has at least two children. In other words it is a lower bound for the number of children. On the other hand the order of a B-tree denotes the maximal node degree, and is therefore an upper bound.
> 10 votes

# Answer
A B-Tree node can contain more than one key values whereas a BST node contains only one. There are lower and upper bounds on the number of keys a node can contain. These bounds can be expressed in terms of a fixed integer `t>=2` called the *minimum degree* of the B-tree.

* Every node other than the root must have at least `t-1` keys. Every internal node other than the root thus has at least `t` children.
* Every node can contain at most `2t-1` keys. Therefore, an internal node can have at most `2t` children. We say that a node is *full* if it contains exactly `2t-1` keys.

Please click This Link to have an excellent basic on B-Tree and This Link for a follow up and most easily written algorithm of B-Tree operations.
> 10 votes

# Answer
I have seen three ways to characterize B-tree so far:

1. With *degree of the B-tree* $t$ (either minimum, as in CLRS *Algorithms* book, or maximum as in B-tree Visualizer).

> The simplest B-tree occurs when $t=2$. Every internal node then has either 2, 3, or 4 children, and we have a **2-3-4 tree**.

The text referenced in Nasir’s answer closely follows B-tree definition as given in Algorithms with detailed explanation of minimum degree properties.
2. With $L$ and $U$ parameters, with lower (upper) bound on number of children inner node is supposed to have (e.g. B-tree with $L=3, U=6$ is equivalent to B-tree with $t=3$ (both allowing of 2–5 keys per node),
3. With *order of the B-tree* $m$, given by Knuth in *TAOCP, Vol. 3* such that any internal node has between $\left\lceil\frac{m}{2}\right\rceil$ and $m$ children.

To sum it up:

* With degree characterization the allowed number of children is bound to lie in $\[t,2t\]$ interval,
* while $L$ and $U$ allows for more precise specification of number of children (i.e. number of keys per node allowed).

With regard to second part of OP’s question there’s *Theorem 18.1* in Algorithms:

> If $n ≥ 1$, then for any $n$-key B-tree $T$ of height $h$ and minimum degree $t≥2$, $h≤\mathrm{log}\_t\frac{n+1}{2}$.
> 5 votes

# Answer
Order(m) of B-tree defines (max and min) no. of children for a particular node.

Degree(t) of B-tree defines (max and min) no. of keys for a particular node. Degree is defined as minimum degree of B-tree.

A B-tree of order m : All internal nodes except the root have at most m nonempty children and at least ⌈m/2⌉ nonempty children.

A B-tree of (minimum) degree t :

1. each node has at most 2t-1 keys
2. if node is not root, it has at least t-1 keys.
> 4 votes

# Answer
`Degree` represents the lower bound on the number of children a node in the B Tree can have (except for the root). i.e the minimum number of children possible. Whereas the `Order` represents the upper bound on the number of children. ie. the maximum number possible.

**B Tree properties with respect to the Order**

`NOTE`: Wikipedia also states these

**B Tree Properties with respect to the Degree**

B Tree Properties with respect to Degree

`NOTE`: `These can also be found in the CLRS book`
> 2 votes

# Answer
B-trees terminologies are not uniformly defined wherever I read, however the ambiguous question is *what is the order of a B-Tree?* and not much about *degree of a B-Tree*. Degree comes from the graph theory which states it as the sum of in degree and out degree of that node.

By which it can be inferred that *degree* is more closely related to number of pointers/child a B-Tree node can have instead of key values in the node.

According to Knuth and Michael J. Folk, a B-tree of order m is a tree with every node having at most m children. So very vaguely we can say that both are more or less equivalent terms in the context of B-Tree.
> 1 votes

# Answer
> B-tree of order 5 OR m=5
>
> max children = 5
>
> min children = ceil(m/2) = 3

---

> B-tree of degree 5 OR t=5
>
> max keys = 2t-1
>
> min keys = t-1
> 0 votes

---
Tags: data-structures, terminology, search-trees, balanced-search-trees, b-tree
---