# Question
Title: What is the complexity class of arranging $1,\ldots, n$ so that all neighbors sum to a perfect square?
I recently saw a problem from Numberphile here, where the goal is to arrange the numbers $1,\ldots,n$ so that the sum of adjacent numbers is a perfect square. This question from Mathematics Stack Exchange has a good analysis of the generalization of the problem for arbitrary powers, but I have been unable to find an analysis of the complexity class of the decision version of the problem. It is $NP$ since you can check if an arrangement satisfies the square sum condition efficiently, but I have been unable to come up with a better algorithm than creating the associated graph and solving the Hamiltonian path problem.

So my question is if this problem is $NP$-complete or if there is a polynomial time algorithm that can decide if $1,\ldots,n$ can be arranged to satisfy the square-sum condition.

Arranging the integers means to find a permutation $a\_1, \ldots, a\_n$ of $1,\ldots, n$ with the property that for all $1 \< i \< n$, $a\_i + a\_{i+1}$ and $a\_i + a\_{i-1}$ are perfect squares.

# Answer
Whether this problem is in NP or not (or rather, in NP or not known to be in NP) depends on how you encode the input. If you encode the input in binary (or in decimal), then the input "$N$" has length $n = O(\log N)$, whereas the obvious witness has length $\Theta(N\log N)$, which is exponential in $n$ (of course, there could be a more compact witness), giving a complexity upper bound of only NEXP. In contrast, if you encode the input in unary (that is, as $1^N$, i.e., $N$ times the symbol $1$), then the input length is $N$ as well, and so the witness has polynomial length, putting the problem in NP.

Even if you use the second encoding, it seems unlikely that the problem is NP-complete. Most NP-complete problems involve a lot of data, and even the few problems which have a constant number of integers as input have more than one integer as input. Of course, formally, speaking, you can think of the input to any problem as a single integer. But semantically, there is a big difference.

What is the complexity of the problem, then? If there is a nice characterization of the values of $N$ for which such an arrangement exists, then it is likely that implementing the characterization would put the problem in P (even using binary encoding). As an extreme example, if such an arrangement exists for all large enough $N$, or doesn't exist for all large enough $N$, then the problem can be solved in linear time. If there is no simple characterization, then the problem might indeed be difficult, but probably not NP-complete or NEXP-complete.
> 4 votes

# Answer
The following algorithm *might* solve the problem in constant time:

```
There is a solution iff n = 15, 16, 17, 23 or n >= 25.

```

(You asked for a yes/no answer only, not for an actual solution). I most definitely can't prove that this algorithm is correct. It might be unprovable for all I know. I doubt that it is incorrect (for n = 50, there are thousands of solutions starting with the smallest possible numbers 1, 3 and 6)

PS The lexicographically first solution for n = 60 is:

1 3 6 10 15 21 4 5 11 14 50 31 18 7 2 34 30 19 45 36 13 51 49 32 17 47 53 28 8 56 25 39 42 58 23 41 59 22 27 54 46 35 29 20 44 37 12 52 48 33 16 9 55 26 38 43 57 24 40 60
> 1 votes

# Answer
I doubt that it's NP-complete.

As this comment on the question you linked points out, heuristically it's very likely that such an arrangement exists if $n$ is sufficiently large. In particular, we can build a graph on $n$ vertices, with an edge between two vertices if they sum to a perfect square. The graph has $\Theta(n^{1.5})$ edges. If we model this as a random graph, then it is overwhelmingly likely to have a Hamiltonian path. In particular, a result by Posa shows that if there are $\Omega(n \log n)$ edges, then the probability that there exists a Hamiltonian graph is $1-o(1)$ as $n \to \infty$. Subsequent results (e.g., Angluin and Valiant) show that the probability is in fact $1-O(n^{-c})$ for all $c\>0$. This means that if the random graph is a good model for the structure of this graph, then once $n$ gets large enough, there almost surely exists such an arrangement.

In particular, this suggests that there is probably some number $n\_0$ such that there is a valid arrangement for all $n \ge n\_0$. This means there are only finitely many $n$ where no such arrangement exists. So, this immediately suggests a straightforward algorithm: it has hard-coded the list of all $n$ where such an arrangement does *not* exist. While finding the algorithm might be non-trivial, the algorithm does exist. Such an algorithm would run in $O(1)$ time.

So, the random graph model suggests that the problem can probably be solved by an $O(1)$-time algorithm. This makes it unlikely that the problem is NP-complete.

Disclaimer: None of this is a proof. The random graph model is a heuristic. The heuristic could fail if there is something that causes the structure of the graph to deviate significantly from that of a random graph. Personally, I don't really expect that to happen, but I don't have a proof that it doesn't happen.
> 0 votes

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


title: Algorithms for solving Flow game

text:
# Question
Title: Algorithms for solving Flow game
Lately I've been toying with an automatic solver for the Android/iPhone game Flow.

In this game, you start with several pairs of squares on a grid, and you have to connect each pair, without crossing the paths, and by using every square on the grid. Here's a simple 7x7 example (the hardest boards in the game are 11x13).

Beginning:

Finished:

In most cases, a few simple rules can all but solve the problem. For example, if a node only has one uncovered exit, it must extend that way, and if extending in a direction would make a part of the board unreachable, then that move is forbidden. But is there a more general way? I've been trying to figure out if it is a specific case of a general graph algorithm, perhaps some kind of Path Coloring.

Note that the game presents other variants of the problem, such as a hexagonal grid, and 'warps' that connect squares on opposite sides of the board. Also, as far as I can tell, there is only ever one correct solution. I'd also be interested in how they can generate the starting positions.

# Answer
I suggest formulating this as an instance of SAT.

You can formulate this as an instance of SAT by thinking of it as trying to color each square in the grid with a color. For each color, arbitrarily designate one of the two endpoints as the "starting position" for that color, and the other endpoint as the "ending position". Define boolean variables $x\_{i,j,c,k}$, with the intended meaning that $x\_{i,j,c,k}$ is true if grid square $(i,j)$ is colored $c$ and is the $k$th square along the path from the starting position for $c$ to the ending position for $c$.

You can write down a boolean formula representing the constraints on the variables $x\_{i,j,c,k}$ that must hold, for this to be a valid solution to the puzzle. For instance:

* If $x\_{i,j,c,k}$ is true, then either $(i,j)$ must be the end position for color $c$, or else $x\_{i',j',c,k+1}$ must be true for some square $(i',j')$ that is adjacent to $(i,j)$. Moreover, this is true for exactly two squares (not more, not less), unless $(i,j)$ is the starting position, in which case it is true for exactly one square.
* For each square $(i,j)$, exactly one of the $x\_{i,j,c,k}$ is true.
* If $(i,j)$ is the starting position for color $c$, $x\_{i,j,c,0}$ is true. If $(i,j)$ is the ending position for color $c$, one of $x\_{i,j,c,k}$ must be true.

And so on. This ensures that the solution to the formula contains a path that starts at the starting position for color $c$ and ends at the ending position.

Then, feel this boolean formula to an off-the-shelf SAT solver and ask it to find a solution.

This may be an effective solution for the puzzle sizes you mention. I expect it may be more effective than trying to write your own custom rules, as SAT solvers embody many clever strategies built up over decades of research to try to find solutions for these kinds of combinatorial questions. At least, it should be pretty easy to implement in just a few hours and see how well it works.

Apparently, this puzzle is NP-hard, so you should not expect to find a polynomial-time solution. This suggests to me that a SAT solver might be a reasonable approach.
> 1 votes

---
Tags: graphs, colorings
---


# Question
Title: Balanced weight distribution into buckets, but with a twist (aka sharding a list into k even shards)
Is there an existing algorithm that can solve the following problem?

**Problem**

Given an list N comprised of integers of various values, shard the list into k buckets such that:

1. The sum of the integers in each bucket are roughly evenly divided (as much as possible
2. Only consecutive integers are placed in the same bucket

**Example:**

Given k (the number of buckets) = `4`

List N = `[4 1 2 6 19 1 10 3 2 2]`

**A Valid Solution**

```
[4 1 2] [6] [19] [1 10 3 2 2]

```

(Since the bucket weights add up to `7, 6, 19, 18`)

**An Invalid Solution**

```
[1 1 2 2 2 3] [1 4 6] [10] [19]

```

(Where the bucket weights would add up to `11, 11, 10, 19`)

It's invalid because the buckets no longer contain only numbers that were adjacent in the original list.

Thanks!

# Answer
Yes, this can be solved as a straightforward application of dynamic programming, once you define an objective function to measure how "evenly divided" the buckets are. Let $A\[j\]$ denote the value of the objective function for the best way to split integers 1..j. Then you can compute the value of $A\[j\]$ given the values of $A\[1\],\dots,A\[j-1\]$ (you just consider all possibilities for how many integers go in the last bucket), so there is a dynamic programming algorithm with running time at most $O(n^2)$.

This problem is sometimes called the Linear Partition Problem, and a solution can be found in Section 8.5 of Skiena's "Algorithm Design Manual".
> 1 votes

---
Tags: algorithms
---


title: What does 'RTU' mean?

text:
# Question
Title: What does 'RTU' mean?
While I was reading about `Base & Bounds` memory protection mechanism, I noticed the use of the abbreviation *RTU* as indicated in the slide below:

However I didn't know what it means.

So after searching for 'RTU', I found only this article on Wikipedia; But I'm not sure whether it matches the term.

Does anyone have any idea?

# Answer
> 3 votes
RTU stands for Return To User. This is invoked when the OS first accesses a physical memory range, and upon doing so will return the memory range address (code).

---
Tags: computer-architecture
---


# Question
Title: How does the OS detect B&B violation from hardware?
After reading about `Base & Bounds` memory protection mechanism from Stanford CS140 lecture notes, I understood from the explanation below that there is an `integrated circuit` performing B&B checks somewhere in the CPU (correct me if I'm wrong):

> On each memory reference, virtual address is compared to the bound register, then added to the base register to produce a physical address. A bound violation results in a trap to the operating system.

However I didn't find any information about how the OS detects such violation from the hardware in order to handle the exception.

Does anyone have any idea?

# Answer
> 2 votes
When an invalid access is detected, the #BR exception is triggered, the CPU will switch to privilege mode and load the corresponding vector (Bounds range exceeded) from the IVT. The CPU also pushes the faulty EIP (as well as other things) to the kernel stack and updates the BNDSTATUS register to describe the fault.

Note: the #BR exception saves other purposes as well because Base & Bound works like paging: there is a 2-level hierarchy to store B&B values (since the CPU can only store 4 of them in registers), so it works a bit like a TLB but for B&B.

---
Tags: computer-architecture, operating-systems, virtual-memory
---


# Question
Title: Psedu-polynomial Time : Conflict with the definition of input size
From wikipedia

> In computational complexity theory, a numeric algorithm runs in **pseudo-polynomial** time if its running time is a polynomial in the length of the input (the number of bits required to represent it) and the numeric value of the input (the largest integer present in the input). In general, the numeric value of the input is exponential in the input length, which is why a **pseudo-polynomial** time algorithm does not necessarily run in polynomial time with respect to the input length.

From this SO post that was very helpful.

> An algorithm runs in **pseudo-polynomial** time if the runtime is some polynomial in the numeric value of the input, rather than in the number of bits required to represent it.

And this MIT OCW lecture on the knapsack DP running time and definition of pseudo-polynomial time.

They are all talking about the same thing in that a running time is pseudo-polynomial when it is a multivariate polynomial of $(x, k)$ where $x$ denotes the size of the input and $k$ is some integer(numeric value) involved. Since $k$ is often exponential in $x$, pseudo-polynomial time is not necessarily polynomial time in $x$, the number of bits needed to represent the input. Mathematically, $k = \Theta(2^{x})$, 2 is replaceable by a constant.

This works absolutely fine when we have a numeric value $k$ as the input with running time $\Theta(k)$. Then $x = \Theta(\log k)$ and we have running time $\Theta(2^{x})$. Everything is clean.

And then I start to see more complicated issues in other algorithms. For example, in the knapsack case, let $N$ denote the number of things or objects in the input. As described in the MIT video, the input is $x = \Theta(NlogS)$ and the running time is $\Theta(NS)$. The instructor describes that since $S$ is exponential in the **input size** $\log S$ (the number of bits needed to represent the numeric value), we can see how knapsack running time is not polynomial time. $\log S$ is only a part of $x$, so I don't see how $\Theta(N\cdot 2^{\log S})$ is exponential in $\Theta(N\log S)$. How is running time expressed in the form $O(c^{x})$ where $c$ is a constant?

Something similar happens for counting sort running time. The SO post gives running time $O(N + k)$. It gives the same logic as above to say that the running time is exponential in the input size $\log k$. But to me it seems like $x = \Theta(N\log K)$ since the input is a list of $N$ things with the maximum value $k$. I don't really see how $O(N + k)$ can be exponential in $x$ just because $k$ is exponential in the number of bits needed to represent it, since $\log k$ is definitely not $x$, only a part of it. Same thing: running time doesn't seem exponential in $x$, rather only in $\log S$.

So either I am still not getting what it means to have exponential **"length of the input"** is or there is some conflict with how people define **length of the input**. MIT video defines input size similar to how I think of $x$ while many other sources have a different opinion it seems. I see it as the **total number of bits needed to represent the whole input**, but some analysis just sees it as the number of bits needed to represent a numeric value that is only a part of the whole input. Is running time exponential in the input size if it is exponential in the size of a part of the input or the whole thing?? Please clarify!!

# Answer
> 2 votes
First, the size of the input is the number of bits required to represent the input. When talking about complexity, we often assume that our input is represented as some bit-string.

For the knapsack case, when we have $x= \Theta(N\log S)$ and running time $\Theta(N\cdot2^{\log S})$, we say that the algorithm is exponential in the size of the input, as $\Theta(N\cdot2^{\log S}) = \Theta(N\cdot2^{(N\log S)/N}) = \Theta(N\cdot 2^{x/N})$. For fixed $N$, the latter formula is exponential in $x$. However, when we fix $S$ instead, the formula is linear in $x$ (which then is $\Theta(N)$). Since we often do not assume bounds on $S$ in the general knapsack problem, we can consider the formula exponential.

A similar analysis can be done for the case of counting sort.

So, in summary, although the length of the input is indeed the full encoding of the input (usually as a bit-string), this doesn't change the fact that if you encode a number $N$ in your input $x$ with $\log N$ bits alongside perhaps other things, $\Theta(N)$ will be exponential in $x$.

---

Finally, let me make some comments on pseudo-polynomial time. Personally, I think that both the definition on Wikipedia and in the SO post lack generality and clarity. I prefer to take the definition alluded to in this answer: An algorithm is pseudo-polynomial if it is polynomial *only* in a specific encoding, such as unary. This implies the definition given on Wikipedia, as the unary encoding on the number $N$ has size $N$, but the binary encoding has size $\log N$.

I prefer the definition above, as it shows a bit more what is going on: it matters what sort of input encoding we use whether our algorithm is polynomial, which explains the name. The fact that this occurs precisely when we have a number in the input is a nice corollary, but hides a bit too much and is probably a reason for your confusion.

---
Tags: algorithm-analysis, time-complexity, runtime-analysis, knapsack-problems, pseudo-polynomial
---


# Question
Title: Generating bit sequence containing every possible of length 1...n
Generating sequence containing every possible bit sequence of lengths from $1$ to $n$ is trivial - just generate every possible sequence of length $n$.

But how do you generate the *shortest* sequence containing every possible bit subsequence of lengths from $1$ to $n$ (using the fact that subsequences may partially overlap)?

What complexity class does that problem belong to?

# Answer
Such a sequence (for arbitrary $k$-ary encodings) is known as a De Bruijn sequence. For the case of the binary encodings, the De Bruijn sequence has length $2^n$. As the output is exponential, this problem is clearly not in $P$, but it lies in $EXP$, as it can be constructed via a Hamiltonian path along the De Bruijn graph (see also here)
> 3 votes

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


# Question
Title: Making a NFA for accepting a string only if it contains the given substrings
First I'll introduce the problem with just two substrings. Say you are asked to construct a NFA which accepts the input string if it has both "bb" and "aba" as substrings.

The solution we came up with in class was that we'll make a NFA with multiple start states (a start state with $\epsilon$-transitions to each of our desired multiple start states). We'll have two cases, one where the substring "aa" occurs before the substring "aba" and one where the substring "aba" occurs before the substring "aa".

Following is the NFA diagram:

But the problem with that solution is that it doesn't generalize well (for example, now if I have to check that the given string contains 10 given strings as substrings, if I have to make a branch for every permutation, I'll have 10! branches).

Is there a simpler solution to this where the complexity of the NFA to be drawn does not increase as factorial of the number of substrings?

# Answer
> 2 votes
Given an alphabet $\Sigma = \\{\sigma\_1,\ldots,\sigma\_n\\}$, let us consider the problem of matching all strings which contain all of the letters as substrings, i.e. all the strings $\sigma\_1,\ldots,\sigma\_n$ as substrings. An NFA with $N$ states accepting this language can be converted to a context-free grammar in Chomsky normal form of size $O(nN)$ (this is the total size of all rules). It is known that any context-free grammar in Chomsky normal form for this language must have exponential size $\tilde{\Omega}((3/2^{2/3})^n)$ (see Theorem 9 here; we gain a quadratic factor since our grammar is in CNF), and so $N = \tilde{\Omega}((3/2^{2/3})^n)$.

Note that this is only an exponential lower bound, whereas the obvious construction has factorial complexity. However, you can improve on this construction. Given $n$ words, the idea is to guess which $n/2$ words will appear first and which $n/2$ words will appear last, and to recurse on each half. We obtain the recurrence $$ T(n) = \binom{n}{n/2}\cdot 2T(n/2) \leq 2^n T(n/2). $$ Expanding the recurrence and using a trivial base case $T(1) = 1$, we get $$ T(n) \leq 2^{n+n/2+\cdots} \< 4^n, $$ which is only exponential. In actuality, $T(1)$ is the size of the largest word to be matched, so the bound above should be multiplied by that.

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


# Question
Title: What is the point of selection step in a genetic algorithm?
I'm reading about genetic algorithms, and I'm not sure I understand the point of selection step.Let's say we have a population of size $N$.How many chromosomes should we select using any selection method and what's the point if the population size is fixed ?

From what I understood till now we select a number of chromosomes (I still don't know how many should we select) and let's say we use Proportionate Fitness selection method and we chose $k$ 'good' chromosomes, then only on those $k$ chromosomes we apply crossover and mutation and let the other unselected ones untouched to the next iteration ? I'm not sure I got it right.Someone can clarify this for me ?

Thank you !

# Answer
> 3 votes
I think the confusion can be isolated in this sentence: "From what I understood till now we \[...\] \[choose\] $k$ 'good' chromosomes, then only on those $k$ chromosomes we apply crossover and mutation and let the other unselected ones untouched to the next iteration?"

Selection plays the role of the hand of death. Unselected organisms correspond to those that died without reproducing. Far from being left "untouched for the next iteration", unselected organisms are *discarded*. Now, to maintain the population size, we need to create new organisms to replace the discarded ones. This is done by applying mutation and cross-over to the chromosomes of the *selected* organisms. The next generation will contain a mix of the *selected* organisms that are left untouched, and mutants of those selected organisms. Biologically, the idea is that the next generation is the organisms that survived and their children. As an optimization technique, the idea is to cull out bad solutions and consider only variations of the "best" current solutions.

# Answer
> 1 votes
> Let's say we have a population of size $N$.How many chromosomes should we select using any selection method and what's the point if the population size is fixed ?

There's not a generally correct solution to this.

In practice, students experimenting with this for the first time might pick values $\in\left\[0.1,~0.25\right\]N$, mostly because:

1. This retains a significant amount of diversity.
2. This allows for each of the selected chromosomes to have $4$-to-$10$ offspring each, enabling the algorithm to mutate each chromosome in a bunch of different ways.

In principle, it'd tend to vary. In fact there's no reason for it to be constant.

* **Example:** Say that all $N$ chromosomes do almost equally as-well despite having diverse genomes. Then, there'd be a stronger argument to maintain more of them (and perhaps grow the population).
* **Example:** Say that only $3$ chromosomes were any good at all, while the rest did horribly. Then, the algorithm might do well to disregard all but the $3$ good ones.

> let's say we use Proportionate Fitness selection method and we chose $k$ 'good' chromosomes, then only on those $k$ chromosomes we apply crossover and mutation and let the other unselected ones untouched to the next iteration ?

The "*good*" chromosomes have some effect on the next generation while the unselected ones tend to be discarded.

In general, the principle's that the good ones should have a stronger effect on the next generation. Beyond that, there's no general requirement for how things must be done.

A lot of this is really vague, which is what can make genetic algorithms a lot of fun to play with because there're all sorts of experimental schemes to try out!

---
Tags: genetic-algorithms
---


# Question
Title: Proving asymptotic notations for functions
I recently started learning about asymptotic notations. While I was doing practice questions (not HW) I found various question that stumped me totally. So I just want some pointers on how to go by solving these type of questions. So here is a basic question. Given the following,

> If $f(n) = \Omega(h(n))$ and $g(n) = O(h(n))$ then $f(n) = \Omega(g(n))$.

How can I solve this and see if that is true or false. Here is what I have tried so far, I tried to use definitions of big-$O$ and big-$\Omega$ on $f(n)$, $g(n)$ and $h(n)$ and then combining those resulting equations to prove/disprove the outcome but I got confused.

So I need explanation of this solutions so I can make it more clear for myself. Any help would be appreciated.

# Answer
The first thing to do is to try to develop an intuition for whether the claim is true or false. Very roughly, $f=\Omega(h)$ says that $f$ is bigger than $h$, and $g=O(h)$ says that $g$ is smaller than $h$. In both of those statements, "bigger" really means "at least as big as" and I've left off the conditions of "up to a constant factor" and "for large enough inputs".

So, if $f$ is bigger than $h$ and $g$ is smaller than $h$, is $f$ bigger than $g$? Intuitively, it ought to be. Since we've simplified, we might have gone wrong, but our intuition is that we should try to prove that the statement is true, rather than trying to find a counterexample.

Apply the definitions and you get that (try it on your own, first!)...

> ... there are constants $c$ and $d$ such that, for all large enough $n$, $f(n)\geq c\\,h(n)$ and $g(n)\leq d\\,h(n)$. Therefore, $f(n)\geq \tfrac{c}{d}g(n)$ for all large enough $n$, which is to say that $f=\Omega(g)$.
> 1 votes

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


title: Quantum oracle in Grover's problem?

text:
# Question
Title: Quantum oracle in Grover's problem?
Here's the exact problem I'm having with Grover's search algorithm.. Given a function f:{0,...,N-1} -\> {0,1}, Grover's problem is to find x such that f(x)=1, provided that there exists such x.

The phase inversion step: Invert the phase of the "key value".

So my question is, when we can already distinguish the key from the others, there is nothing to solve. Why do we need to solve the problem at all when we can already separate the key value? I am missing a point here but I don't understand what it is.

Many thanks for your help.

# Answer
When computing the oracle in Grover's algorithm, you prepare a qubit entangled with the search register such that the qubit is ON in the parts of the superposition where the search register contains a satisfying solution and OFF in the other parts of the superposition. This is not hard to do: you just use any old circuit that would determine if a given input was a solution, and apply that to the search register.

By preparing the solution qubit, applying a Z gate to it, then uncomputing the solution qubit, you negate the parts of the superposition corresponding to solutions. Having that qubit available is not the same thing as finding a solution. For example, if you measured it you'd almost always get an OFF result and find that your search register contained a non-solution. But, by using the prepared qubit as a tool to negate the phase of the solution space, Grover's algorithm can set up a gradual rotation towards the solution space.

More information: http://algassert.com/post/1719
> 1 votes

---
Tags: quantum-computing
---


title: Why call it 'Time Complexity'?

text:
# Question
Title: Why call it 'Time Complexity'?
P.S. I have added the tag 'history', if there is any historical connotation.

Also, I found this question What is running time of an algorithm? but I am not satisfied with answers.

# Answer
> 11 votes
Perhaps the earliest place in which time complexity appears is On the computational complexity of algorithms by Hartmanis and Stearns. Their goal is to study computation complexity, which they define as follows:

> The computational complexity of a sequence is to be measured by how fast a multitape Turing machine can print out the terms of the sequence.

Their first section, in which they prove (among else) a time-hierarchy theorem, is about "time-limited computations". They explicitly mention their concept of time:

> The machine operation is our basic unit of time.

The reference is to a multitape Turing machine, which they diligently define.

The intention here is to model the running time of algorithms using abstract machines, using number of steps as a proxy for time. Anticipating your criticism, they mention:

> Furthermore, the \[complexity\] classes are independent of time scale or of the speed of the components from which the machines could be built, as there is a "speed-up" theorem which states that $S\_T = S\_{kT}$ \[i.e., $\mathsf{TIME}(T(n))$ = $\mathsf{TIME}(kT(n))$\] for positive numbers $k$.

That is, multitape Turing machines can always be sped up by an arbitrary constant, and so there is no harm in associating number of steps with running time, since time complexity classes are "scale free".

# Answer
> 3 votes
I think, though I don't have any references to back this up, that it's just a convenient name that has a ring of truth to it.

If you imagine implementing a standard Turing machine, it does seem reasonable that every step of your actual, physical machine will take the same amount of time. So, for a Turing machine, time and number of steps are the same thing, up to a constant factor. That isn't true for more complicated machines – for example, a single step of a RAM could involve moving the tape heads an arbitrary distance – but the analogy is good enough.

All names seem to have disadvantages. "Time complexity" sounds like it's measured in seconds. Something like "step complexity", "operation complexity" or "instruction complexity" might be misunderstood as referring to the complexity of the individual steps, rather than to complexity measured by the number of steps. But these aren't big disadvantages: it only takes a moment to explain that "time" doesn't literally mean time or that "step complexity" doesn't mean the complexity of the steps.

If we were starting again from scratch, I think either "time complexity" or "step complexity" would be a reasonable name. I can't think of any other term that's both reasonably short and more accurately conveys the concept of complexity measured in terms of the number of computational steps.

And be thankful that we didn't call it "type 1" complexity. I'm looking at you, statistics and diabetes.

# Answer
> 2 votes
*Time complexity* is a formal model (an abstraction) of program running time. Although on the face of it you are right that it really measures the number of steps, it is *asymptotically* no different from the actual running time of the machine (Turing machine or any other model of computation). Therefore I disagree that there is any problem with the terminology.

Think about it from the programmer's perspective. When you write a piece of code, say

```
 for i = 1 ... n :
     for j = 1 ... i :
          print j
     print newline

```

you can't (as a programmer) actually predict how long the program will take to run in seconds, with accuracy. Moreover the number of seconds depends on the exact platform on which you run the code, level of parallelization, what file or output you are printing to, etc.

But what you *can* measure is the number of steps your code runs -- that is, its *time complexity*, as a function of $n$. You simply count the number of times a print statement is executed. This is -- *up to a constant* -- a good and correct estimate of the actual time the program will take to run, in seconds.

In summary, the concept of *time complexity* is exactly the same concept that programmers use to think about their code's performance, and the abstraction is the same as the actual running time up to a constant.

# Answer
> 0 votes
From what I can tell, your appeal to the terms "step complexity" and "operation complexity" are a way of attaining a more objective definition of an alogithm's behavior, without tying it down to the actual execution time of the algorithm on an arbitrary machine.

However, "step" and "operation" are not so objective, either. Different CPUs can have vastly different instruction sets. For example, in the `x86` instruction set, `MOV EAX, [EDX + EBX*4 + 8]` is a single instruction! That's despite it doing 1 multiplication, 3 additions, and 1 move.

Perhaps you could say "okay, well then we'll count it as 5 operations." Well that gets really complicated, too. These could very well be done in one shot by hardware, or perhaps as a decomposition of simpler instructions as orchestrated by the processor's microcode. Not only is it not defined which of these two approaches a processor uses, but the notion of these "simpler instructions" is also blurred. Who's to say multiplication is a single instruction? It could be implemented as a sequence of additions, for all you know (it's not, don't worry, but the point stands).

Anyhow, talking about "time complexity" makes sense, because we don't *really* care about steps or operations. What we really care about is how steps or operations can be used as a *proxy* for time. E.g. we don't care if one algorithm takes 10 steps or another takes 20, if the first algorithm takes 10 seconds and the other takes 2 seconds.

# Answer
> 0 votes
In practice an actual machine does not spend a particular time for each operation that is equal to any other machines length of time. Hence what we measure is a general trend of growth.

Consider addition on a machine nowadays.

Consider addition on a mechanical computer.

It is not unreasonable to use both as models to measure the length of time an algorithm takes to complete. However, the issue is that both have wildly different EXACT amounts. All we can reason is how changing the input changes the runtime of the algorithm.

A better way to consider is that runtime is a function of the length of time of each step you assume to take one unit of time. Then, time complexity is a result of analyzing that function. In particular because those times will vary from actual machine to actual machine.

I.E. give the abstract machine abstract times to complete each immutable step so that it can apply to any such machine implemented in the real world.

---
Tags: algorithm-analysis, time-complexity, terminology, runtime-analysis, history
---


# Question
Title: What do we do instead of DFS on directed graphs?
All the example of DFS I've seen so far are for undirected graph. In a directed graph the basic DFS algorithm won't work because some vertex will be unreachable.

The algorithm I'm talking about : https://en.wikipedia.org/wiki/Depth-first\_search

```
1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5          v = S.pop()
6          if v is not labeled as discovered:
7              label v as discovered
8              for all edges from v to w in G.adjacentEdges(v) do
9                  S.push(w)

```

Example :

##

So let's say I start with '1' I will never access 4,5,6 with this algorithm.

For directed graph it looks like we have to know all the vertex and iterate through them.

And so we cannot use a DFS for directed graph ?

Is there a DFS variant or another algorithm ?

# Answer
> 5 votes
The issue is not specific to DFS.

When looking at directed graphs, even for connected graphs not all nodes are reachable from everywhere. That's why the notion of a graph being *strongly* connected exists.

In a strongly connected graph, graph traversals starting in a single node will reach all nodes. In other graphs, it won't.

This affects all traversal algorithms. For some reason, (some) canonical BFS implementations include looping over all starting nodes but DFS implementations do not. I don't know why; I assume historical reasons. There certainly is no conceptual difference; you can just as easily restart DFS with new starting nodes until you cover the whole graph.

# Answer
> 4 votes
DFS suffers from the same problem in undirected graphs: if your graph is not connected, then starting DFS with an initial vertex $v$ will only explore the connected component of $v$. In a similar fashion, if the graph is directed, then DFS will only explore the vertices reachable from $v$.

The solution is the same in both cases: loop over all vertices, and start DFS with each of the vertices functioning as the initial vertex. If you skip vertices which you have already discovered, then the resulting algorithm will still run in linear time.

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


title: Variations of Omega and Omega infinity

text:
# Question
Title: Variations of Omega and Omega infinity
Some authors define $\Omega$ in a slightly different way: let’s use $ \overset{\infty}{\Omega}$ (read “omega infinity”) for this alternative definition. We say that $f(n) = \overset{\infty}{\Omega}(g(n))$ if there exists a positive constant $c$ such that $f(n) \geq c\cdot g(n) \geq 0$ for infinitely many integers $n$, whereas the usual $\Omega$ requires that this holds for all integers greater than a certain $n\_0$.

Show that for any two functions $f(n)$ and $g(n)$ that are asymptotically nonnegative, either $f(n) = O(g(n))$ or $f(n)= \overset{\infty}{\Omega}(g(n))$ or both, whereas this is not true if we use $\Omega$ in place of $\overset{\infty}{\Omega}$.

I am trying learn Algorithms. But I am unable to prove this. Can the experts help me ?

# Answer
> 6 votes
Hint: If $f(n) \notin \overset{\infty}{\Omega}(g(n))$ and $g(n)$ is asymptotically non-negative, then for all positive constants $c$, $f(n) \leq c \cdot g(n)$ for large enough $n$. This follows by ignoring the condition $c \cdot g(n) \geq 0$ and negating the definition of $f(n) \in \overset{\infty}{\Omega}(g(n))$. In fact, this way you get the stronger result that either $f(n) \in \overset{\infty}{\Omega}(g(n))$ or $f(n) \in o(g(n))$ (but not both).

Further hint: You can start by showing that the negation of "$P(n)$ for infinitely many $n$" is "$\lnot P(n)$ for large enough $n$".

# Answer
> 0 votes
I can give you an example so that you can better understand $\overset{\infty}{\Omega}(g(n))$. Imagine a binomial heap. The insert operation is $O(logN)$, but is it ${\Omega}(logN)$?

In cases when we have tree ranks of 4-3-2-1-0 and inserting a tree with rank 0 will be a ${\Omega}(logN)$ operation. But inserting a tree with rank 0 on the resulting heap from the previous operation (heap with having tree rank of 5) will be a $O(1)$ operation, since only pointers should be added and no extra merge work is necessary.

This is the essential difference between ${\Omega}$ and $\overset{\infty}{\Omega}$. For example the binomial heap insert operation is $\overset{\infty}{\Omega}(logN)$ for set of $n = \\{{1,3,7,...,2^k - 1}\\}$. It doesn't state that when $n \geq n\_0$ the complexity is ${\Omega}(logN)$ but rather for some infinite set of n, but not for all $n \geq n\_0$

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


# Question
Title: Representation of used space and free space in hard drives
I've read from this How data is physically stored in hard drives, that the North/South orientation of the magnetic medium represents data as 0 or 1 physically in the hard drive. Data is stored in binary, which means that it can be stored as either 0 or 1 in the hard drive. But what determines if that particular block of memory in the hard drive is "Used Space" or "Free Space".

In the OS, you can view how much memory is used, and how much is free.

Let's say i have a 1 TB hard drive. I stored 100 GB worth of data with the repeating pattern "1100 1100". This means that I have 100 GB of used space and 900 GB left of free space (does it?). How does it know that it is used or free? If both 1 and 0 can be used to represent the data in that block of memory, then what represents as a "Free Space"? What if i delete 50 GB of data? I'll have 50 GB more free space, but what represents this free space? And how is the data 1 or 0 of "Used Space" converted to "Free Space"?

# Answer
> 6 votes
Free space is a concept at the level of the filesystem, which is part of the operating system. It is up to the filesystem to determine what space is free, and how to exploit it.

Data is stored on the hard drive in a structured way. The filesystem divides the drive into *sectors* (basic units, usually 512, 1024, 2048, or 4096 bytes), and maintains data structures on the drive which store which sectors are used and which are available. These data structures also store the directory structure of the drive, which sectors comprise which file, file names, and other metadata (such as various file timestamps).

Your experiment, of storing a repeated pattern on the raw drive, doesn't constitute a legitimate use of the drive. The drive is usually used only via a filesystem. The filesystem presents to the user (i.e., the software programmer) a logical view of the hard drive. Physical details such as were different parts of a file are stored are the business of the filesystem rather than of the user (though sometimes the user would like to know more, for example in order to defragment the drive).

The same, by the way, is true for memory, which is maintained by the memory manager, another part of the operating system. The operating system allocated memory to the user, takes care of swapping, stores the memory when hibernating, and so on. On modern CPUs, the user can't just use unallocated memory - this will trigger an exception. The supporting data structures are perhaps more lightweight, but there is still an infrastructure supporting memory allocation and deallocation.

# Answer
> 4 votes
The operating system knows what parts of memory are free and what parts are in use by keeping track of all allocations to processes; anything that isn't allocated is free. Disks are exactly the same: the OS keeps track of what is allocated to each file. (Different structures are used, but it's the same principle.)

At all times, every bit of memory and every bit of disk stores either zero or one. Don't think of it as being like a piece of paper that can either have "0" or "1" or nothing at all written on it; think of it like a light switch: the light is either on or off.

---
Tags: data-compression, memory-hardware
---


# Question
Title: Show that the SAT Problem for CNF formulas with at most two occurences of each variable can be solved in polynomial time
Assuming, I have an arbitrary CNF Formula in which each variable has at most two occurences, how can I proof/show that this can be solved in polynomial time?

My first thoughts so far:

because each variable has at most two occurences, the formula contains at most 2\*n literals, where n is the amount of different variables, and so the amount of clauses are also at most 2\*n.

Not much, that's all I have so far :/

# Answer
Consider a variable $x\_i$. If it appears once, or if it appears twice but in the same polarity (i.e., both times as a positive literal or both times as a negative literal), then we can set it accordingly and satisfy all the clauses that contain it (more formally, any satisfying assignment can be converted into a satisfying assignment in which $x\_i$ has this value).

The remaining case is the in which $x\_i$ appears once positively and once negatively, that is, there are clauses $x\_i \lor C$ and $\lnot x\_i \lor D$. These two clauses are logically equivalent to the single clause $C \lor D$, which no longer contains $x\_i$.

In this way, we keep eliminating the variables one by one, until we either eliminate all of them (in which case the formula is satisfiable), or we reach an empty clause (in which case the formula is unsatisfiable), which happens when both $C$ and $D$ are empty in the second case.
> 5 votes

---
Tags: satisfiability, polynomial-time
---


# Question
Title: Is there a way to calculate exactly how many binary trees are possible if only one of the preorder, inorder and postorder traversals is given?
I am studying tree traversals and I've got to know that we can uniquely determine the binary tree if their:

Case 1. Preorder & inorder traversals are given or

Case 2. postorder & inorder traversals are given

We can not determine the tree if only one of the traversals are given because there will be finitely many trees possible.

My question is that, is there a way to calculate the number of trees possible?

# Answer
> 3 votes
Your question probably assumes that the nodes of the tree all contain different values. If we have a tree with $n$ nodes all of whose have the same label $x$, then we can't tell what tree we're looking at by observing the traversals, as we always get just a series of $x$'s, independent of what the tree shape is or what traversal we use. So I assume the labels are all different.

Use the traversal to generate a list of all the elements of the tree $\[x\_1, \ldots, x\_n\]$. Now, which trees are possible with this particular traversal? Pick *any* tree with $n$ elements and place the labels $x\_i$ into the nodes so that for that tree you'll get them back in the order $\[x\_1, \ldots, x\_n\]$. This shows that, if we only have one of the traversals available, *any* tree shape is possible, as long as it has the correct number of nodes $n$. So the answer is that there are $C\_n$ such trees, where $$C\_n = \frac{1}{n+ 1}{2 n \choose n}$$ is the $n$-th Catalan number.

# Answer
> -2 votes
Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)!/(n+1)!\*n!

For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …. So are numbers of Binary Search Trees.

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


# Question
Title: Probability of k-clique in a random graph
I need to find the order of the minimum k = k(n) such that the probability of having at least 1 k-clique in a random graph $G(n, \frac{1}{2}$) is $\mathcal{O}(\frac{1}{n})$. $X\_k$ is the random variable which count the number of k-cliques in a random graph. I already know $E\[X\_k\] = \binom{n}{k}(\frac{1}{2})^{\binom{k}{2}}$. I don't know exactly how to find the exact value of k. I know $P\[X\_k \geq 1\] \leq E\[X\_k\]$ for Markov inequality but I'm not sure that this is helpful. Thanks in advance

# Answer
The value is $2\log\_2 n - 2\log\_2\log\_2 n + O(1)$.

Let $k\_0$ be the maximal value such that the expected number of cliques of size $k\_0$ is at least 1. A boring calculation shows that $k\_0 = 2\log\_2 n - 2\log\_2\log\_2 n + O(1)$. It is a classical result that with high probability, $G(n,1/2)$ contains a $(k\_0-1)$-clique. This implies that $k \> k\_0-1$. On the other hand, it is known that the expected number of cliques of size $k\_0+1+C$ is $O((\log n/n)^C)$ for any constant $C$ (this is because the expected number of cliques drops by $\Theta(\log n/n)$ near $k\_0$). This shows that $k \leq k\_0+3$. We conclude that $k\_0 \leq k \leq k\_0+3$.

You can probably decrease the length of this interval by 1, following the proof of the classical result which shows concentration of the clique number of *two* values rather than *three*.
> 3 votes

---
Tags: probability-theory, clique, random-graphs
---


# Question
Title: How to produce all the numbers in a range [0,1,...,n] for which if 0<=k<=n, then for a positive integer x, the expression: k & x = k?
I am trying to figure out an efficient way to produce all the numbers in a given range for which, their **bitwise AND** with a positive integer (say x) gives the same number; that means k & x = k.

Is there a better way to do it so that I do not need to go through all the numbers from 0 to n and check for it?

# Answer
*This answer shows how to find all values of $x$ satisfying the equation for fixed $k$. The OP asked for all values of $k$ satisfying the equation for fixed $x$, but the same methods work for both problems.*

First of all, we have $k \\& x = k$ if $x\_i = 1$ whenever $k\_i = 1$. If we think of $k,x$ as sets whose elements are the 1 bits, then the equation becomes $k \cap x = k$, which is equivalent to $k \subseteq x$, and so if $i \in k$ (i.e., $k\_i=1$) then $i \in x$ (i.e., $x\_i=1$).

In order to generate all solutions $x$ in the range $0,\ldots,n$, it suffices to generate all solutions in increasing order; we can stop once reaching a solution which is larger than $n$. How do all solutions look like? Let the 0 bits of $k$ be $i\_0 \< i\_1 \< \cdots \< i\_\ell$. Then the solutions are $$ k + \sum\_{j=0}^\ell b\_j 2^{i\_j}, $$ where $b\_j \in \\{0,1\\}$; we can replace addition equivalently with bitwise OR. Moreover, if we think of $b\_\ell\ldots b\_0$ as a binary number, then the mapping from $b\_\ell \ldots b\_0$ to $k + \sum\_j b\_j 2^{i\_j}$ is *monotone*: as we go over all values of $b\_\ell \ldots b\_0$ in increasing order, the values of $k + \sum\_j b\_j 2^{i\_j}$ appear in increasing order. This leads to the following algorithm:

1. Let $b \gets 0$.
2. Compute $x = k + \sum\_j b\_j 2^{i\_j}$, where $b\_j$ is the $j$th bit of $b$.
3. If $x \leq n$, output $x$, increase $b$ by 1, and go back to 2. Otherwise, halt.
> 1 votes

---
Tags: algorithms, arithmetic
---


# Question
Title: Which language is produced by this grammar?
I was asked to define the language which is produced by the following grammar:

$G = (V, \Sigma, S, P)$

$V = \\{S, A, B\\}$

$\Sigma = \\{a, b, c\\}$

\begin{equation} P= \begin{cases} S \rightarrow cA | bB\\ A \rightarrow c \\ B \rightarrow aB|b \end{cases} \end{equation}

Obviously, you can produce $c^n$ and $b^n$, but since we can also produce $ccbab$ for example, I do not know how to find a formular for the language $L(G)$

Any help would be really appreciated!

# Answer
Let's start with the nonterminal $B$. Since all productions of the form $B \to \alpha$ involve only $B$ (and no other nonterminal), we can easily find $L(B) = a^\*b$ using Arden's rule. We also have $L(A) = c$. Finally, $$ L(S) = L(cA) \cup L(bB) = cc + ba^\*b. $$
> 1 votes

---
Tags: formal-languages, formal-grammars
---


title: L(G) = ∅ is undecidable?

text:
# Question
Title: L(G) = ∅ is undecidable?
For a grammar $G$, why is the problem of whether $L(G)=\emptyset$ is undecidable? I'm confused as, for recursive languages there exists a Turing machine which will halt every time and give an answer(accepted or rejected) for each and every string input. So we can decide whether it accepts strings or not.

# Answer
For any particular string $x$, the question of whether $x \in L(G)$ is decidable (if G is not unrestricted), and that's what you've described.

However, the problem you've given is not whether a *particular* string is in $L(G)$, but whether *any* string is in $L(G)$. There are infinitely many strings to try. We can test each one in sequence, and if it is in $L(G)$ then we know it is not empty. But if $L(G)$ is empty, how do we know when to stop? There are infinitely many strings, so we never know if the next string is the one that's in the language. So we never know when to stop.

That said, the decidability greatly depends on what type of language/grammar $G$ is. For context-free languages, this is decidable, since we can make a pushdown automaton and perform a search to see if an accepting state is reachable. But for other, more complicated types of languages this may very well be undecidable.
> 5 votes

---
Tags: computability, formal-grammars, undecidability
---


# Question
Title: Push-down automaton for a language with number of 1s double than 0s
This questions is taken from a complexity theory course.

> Design a push-down automaton that recognize $L = x \in \\{0,1\\}^\* $ such that $x$ contains a number of ones double than a number of zeros.

Example: x = 011011, 100011111, 011011110.

**My approach**

I tried to push on the stack a symbol "A" every time I read "0", than pop "A" from the stack when I read two consecutive "1" but this approach works not for every string $x$ in the language. Maybe the final PDA is non-deterministic. Any hints?

# Answer
Consider this algorithm:

* Initialize a variable $x := 0$.
* Scan the string, left to right. If you see $1$, set $x := x + 1$, if you see $0$, set $x := x - 2$.
* When you are done, accept iff $x = 0$.

It should be obvious that it recognizes your language. Can you figure out a way to implement it replacing the counter with the stack?
> 1 votes

# Answer
Here's an algorithm for what I think could be a solution:

```
program_recL(entry) is
    stack: type_stack
    while read(entry) != $ do
        if read(entry) == 0 then
            if empty(stack) then
                push(stack, 0)
                push(stack, 0)
            else
                if top(stack) == 0 then
                    push(stack, 0)
                    push(stack, 0)
                else
                    pop(stack)
                    push(stack, 0)
                endif
            endif
        else
            if empty(stack) then
                push(stack, 1)
            else
                if top(stack) == 1 then
                    push(stack, 1)
                else
                    pop(stack)
                endif
            endif
        endif

        next(entry)
    endwhile

    if is_empty(stack) then
        accept()
    endif
end

```

The basic idea here is that every 0 has x2 value for each 1, meaning we need to push two 0s every time we read a 0 on our entry. This will translate into needing two 1s to get a 0 popped from the stack, in other words, a number of 1s double than a number of 0s.
> 1 votes

# Answer
You need a 2-stack PDA to solve this problem.

Since the language you've given is non-context free, it's more powerful than a single stack PDA. More specifically, your language the union of many CFLs and non-CFLs. The inputs that seem to be working with your way can be recognized by a single stack PDA. e.g.: S -\> 0A11 A -\> S which is the language {0^n1^2n, n\>=0} S -\> 11A0 A -\> S which is the language {1^2n1^n, n\>=0} . . . However, there is no way to describe others with a context-free grammar.
> -2 votes

---
Tags: context-free, pushdown-automata
---


# Question
Title: Why is a sequence of n Push, Pop, Multipop operations O(n²)?
From "*Introduction to Algorithms*" by Cormen, Leiserson, Rivest, Stein, Third Edition, page 453:

> Let us analyze a sequence of $n$ Push, Pop, Multipop operations on an initially empty stack. The worst-case cost of a Multipop operation in the sequence is $O\left(n\right)$, since the stack size is at most $n$. The worst-case time of any stack operation is therefore $O\left(n\right)$, and hence a sequence of $n$ operations costs $O\left(n^2\right)$, since we may have $O\left(n\right)$ Multipop operations costing $O\left(n\right)$ each. Although this analysis is correct, the $O\left(n^2\right)$ result, which we obtained by considering the worst-case cost of each operation individually, is not tight.

Part of this seems badly written:

> \[...\] since we may have $O\left(n\right)$ Multipop operations costing $O\left(n\right)$ each.

Why would they count the number of some items in terms of running time, $O\left(n\right)$? The way I interpret this is that a sequence of only $n$ multipops(n) will result in $O\left(n^2\right)$, but after the first one, I imagine the stack is empty.

Someone try and explain how the worst case cost of a sequence of $n$ push, pop, multipop is $O\left(n^2\right)$. Or perhaps what may help is if you can rewrite the problem statement... maybe that's what is confusing.

**Question:** Do the push, pop, and multipop cumulatively add up to $n$, or is it $n$ push, $n$ pop, and $n$ multipop operations?

# Answer
> 9 votes
First, let me comment on 2 misconceptions I see in your question:

1. Landau notation ('Big $O$ notation') does not exclusively refer to running times, we can use it to describe any function we wish.
2. The fact that the worst case running time is $O(n^2)$ doesn't mean the running time isn't also $O(n)$.

The second part comes close to the point of this part in the book. The authors first show that a (crude) analysis of executing the multi-pop operation $n$ times: worst case of a single multi-pop is $O(n)$, we pop $n$ times, so we spend at most $O(n^2)$.

However, do *all* of our $n$ multi-pop operations require $O(n)$ time? The authors continue to show that using the aggregate analysis that this isn't the case, by which they obtain a sharper bound of $O(n)$ for $n$ multi-pop operations.

So, in this section, the authors show the utility of aggregate analysis by the multi-pop example.

As for the part labeled as 'question': yes, the total running time of all $n$ operations is $O(n)$, as the book describes in the next section:

> We can pop each object from the stack at most once for each time we have pushed it onto the stack. Therefore, the number of times that POP can be called on a nonempty stack, including calls within MULTIPOP , is at most the number of PUSH operations, which is at most $n$

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, amortized-analysis, stacks
---


# Question
Title: How to construct the objective function for genetic algorithm optimization?
I am trying to optimize a coefficients of filter by minimizing sum-squared error. I want to use a *genetic algorithm* (GA) optimization wherein the coefficients of filter form the GA's chromosome (a vector).

How can I construct the objective function, given that I want it to use least-squares minimization?

# Answer
> 1 votes
***tl;dr*-** Objective functions are supposed to quantify how good a set of parameters is. It doesn't matter how you got the parameters; for example, it doesn't matter that you're using genetic algorithms. You just need to create some function that says how well the parameters work.

---

So you're designing a filter, which requires that the filter's parameters be optimized to fit its application, and you'd like to use genetic algorithms for the optimization?

You're correct that the filter's parameters should be used to construct the chromosomes in the genetic algorithm. The genetic algorithm then does its work by:

1. Calculates how well its chromosome (combination of parameters) performs.
2. Discards the chromosomes that didn't perform well.
3. Modifies (mutates) the parameter sets (chromosomes) that did perform well.
4. Goes back to Step (1), looping until either it finds a parameter set that's good enough or it gives up (fails to converge).

However, how should the algorithm assess how "*good*" the parameter sets are? That's what the objective function's for. The objective function takes the chromosome as input, then produces a result that quantifies how good that chromosome is.

Since chromosomes are sets of parameters, they're often represented as a vector (array). For example, if your filter's, say,$$ f\left(x\right)=ax^2+bx+c, $$then the chromosome's the array of the parameters $\left\\{a,b,c\right\\}$.

The question statement doesn't specify your filter or exactly what sort of problem you're working on. However, since you want to use sum-squared error, that implies that your filter produces an output with quantifiable error.

So, presumably, your objective function would be$$ \text{error}=\sum\_{{\forall}\text{data}~i}{\left(f\_{\text{measured}}\left(x\_i\right)-f\_{\text{model}}\left(x\_i\right)\right)}^2, $$or something like that. Some folks prefer to use the root-mean-square, i.e.$$ \text{error}=\sqrt{\sum\_{{\forall}\text{data}~i}{\left(f\_{\text{measured}}\left(x\_i\right)-f\_{\text{model}}\left(x\_i\right)\right)}^2}, $$but that shouldn't matter here.

In general, I'd suggest seeing genetic algorithms as stepping functions. Their core duty is to produce new guesses during an optimization process. Objective functions live elsewhere in the optimization process's structure; this is, objective functions don't care how you're stepping - whether you're using genetic algorithms, Newton's method, Simplex, gradient descent, bisection, random guessing, or whatever else - it doesn't matter to the objective function. All the objective function has to do is say how good a guess is, regardless of how that guess was generated.

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


# Question
Title: Which sorting algorithm is most efficient to 'continuously' sort a vector again and again?
I have an uncommon use case

I have a vector, which contains a fixed number of taxi's real-time fees (the red/green number that keeps bumping up when you sit in the back).

This vector is continuously updated by message sent back from taxis. I need to find the top 10 taxis every time when there is an update.

if I only need to do this once, then std::sort() or std::partial\_sort would easily solve the problem. However, since the vector is largely the same after only a few updates, the sorting result from step T should be largely the same as sorting result of step T+1

I am wondering if the std::partial\_sort will be 'smart' enough to 'incrementally' sort the vector, rather than start-over again from scratch.

Can anyone share any ideas here?

Thanks!

# Answer
Look at what your problem actually is: Your problem is not sorting the list, but finding the largest ten items. That's a much easier problem, which can be solved without sorting the list again and again.

Start by finding the top ten items once. Let $X\_{10}$ be the value of the tenth largest item.

If an item outside the top ten is changed to a value ≤ $X\_{10}$, ignore it. If it is changed to a value \> $X\_{10}$, then drop the tenth item and insert the changed item in the array in the right position.

If an item in the top ten is changed then move it up or down according to the new value. If the new value is less than \< $X\_{10}$ then remove it from the top ten leaving you with the top nine, find the largest item that is currently not in the top nine, and put it into the tenth position.

So most of the time you do no work at all, a lot of the time very little work, and occasionally it takes linear time.
> 1 votes

# Answer
If your list of taxi numbers has only a few 'incorrect' positions that are close to their 'correct' sorted position, you could try to use insertion sort.

Although insertion sort is not very efficient to sort tributary lists, it works pretty well for almost sorted lists: if all elements in the list have distance of at most $k$, insertion sort takes only $O(kn)$ time to sort the list, for instance. Additionally, insertion sort is a rather simple algorithm, so you should be able to implement it yourself if there is no library function available.
> 0 votes

# Answer
As Billiska suggests, very good idea is to keep the balanced tree (Red Black, AVL), which gives $\mathcal O(\log n)$ per update. In case of monotonous increments, using the max-heap would be also viable option. If there is any known rate, it may be good idea to keep two separate trees, one with say twice amount of last top items and keeping those that would not bump into top-10 any time soon. It is more manual handling of the data, but it benefits vastly in the terms of time.
> 0 votes

---
Tags: sorting
---


# Question
Title: Need a polynomial time reduction from 3SAT to INDEPENDENT-SET
In order to show that a problem is NP hard one must provide a reduction from a known NP hard problem to this problem. My question is how to reduce 3SAT to INDEPENDENT-SET?

3SAT is a satisfiable 3 literals in a clause Boolean conjunctive normal formula. INDEPENDENT-SET is a set of vertices in a graph, no two of which are adjacent. I do know how to reduce 3SAT to a Clique, would that help?

# Answer
The simplest is to reduce Clique to Independent Set using the complement graph, as discussed in the comments.

Alternatively, you can construct a graph to directly reduce 3SAT to Independent Set using "gadgets". One possible start is to do the following: for each clause, construct one node for each of the three variables in the clause. Now, we want to place edges such that:

* No two variables in the same clause can be members of the same independent set.
* No two variables which are the negations of each other can be members of the same independent set.

If you can accomplish this, then for a boolean formula with $m$ clauses, there is an independent set of size $m$ in your constructed graph if and only if the boolean formula is satisfiable, thus giving the desired reduction.
> 2 votes

# Answer
Reduction from 3SAT to Independent-Set: 1. Turn each clause of literals from formula to a group of vertices where each vertex has the name of it's corresponding literal and all vertices are connected with each other, giving triangles or pairs or single vertices. 2.Now connect each two vertices in the new created graph that represent a literal and it's complement. 3. The new graph will have independent-set of size m, when m is the number of clauses from the original CNF formatted formula, if and only if the original formula is satisfiable. Running time: o(n^2) --\> polynomial
> 0 votes

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


title: 3 * O(n^2) vs O(n^3)

text:
# Question
Title: 3 * O(n^2) vs O(n^3)
Currently while I was coding, I got a doubt.

While I was solving a particular type of problem I found it to be solved in $O(n^3)$.

I have broken that problem and solved it in $O(n^2)$.

But to solve it I have broken that $O(n^3)$ to $3$ * $O(n^2)$

Is it a better solution than $O(n^3)$ or will it matter the number of $O(n^2)$ also?

# Answer
> 4 votes
Multiplying $O\left(n^2\right)$ by $3$ doesn't change it. Literally, it remains the same thing:

$$3{\cdot}O\left(n^2\right)~=~O\left(3n^2\right)~=~O\left(n^2\right).$$

This is because such complexity qualifications don't track scalar multipliers.

The reason that we discard scalar multipliers is pretty simple: the actual run time will depend on how fast particular computer instructions work, such that if we cared about scalar factors, our complexity qualifications would become extremely context-specific.

For example, many real-world systems will speed up as they run a long-running algorithm due to optimizations that kick in as an algorithm runs (e.g., branch profiling CPU's and hot-spot code optimizations in VM's). So, any scalar projection of run-time behavior would have to account for these factors. Such an analysis could still be quite helpful and worth studying when appropriate, but that's not the role that complexity classes intend to fill.

So, as general performance analyses qualifications, complexity classes tend to focus on the largest order-affecting factors while hand-waving the scalar stuff as implementation-dependent.

# Answer
> 3 votes
It is impossible to say which is *better* with only the given information. For large values of n, $O(n^3)$ will be slower. But there are situations in which the algorithm in question will only be executed with such small values of n that the one with the highest order might work better.

I actually implemented an exponential algorithm once as part of an important program since the expected size of the data set was too small to matter.

So, what is slower in general, may be faster in practice. But if you are programming the general case, use the quadratic algorithm, not the cubic one.

If you graph the two polynomials on the same axis this will be very clear.

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


title: Why must a Primary Index be sparse?

text:
# Question
Title: Why must a Primary Index be sparse?
Reading *Fundamentals of Database Systems 7th Edition*, on Page 603, it says,

> Indexes can also be characterized as dense or *sparse*. A dense index has an index entry for every search key value (and hence every record) in the data file. A sparse (or nondense) index, on the other hand, has index entries for only some of the search values. A sparse index has fewer entries than the number of records in the file. **Thus, a primary index is a nondense (sparse) index, since it includes an entry for each disk block of the data file and the keys of its anchor record rather than for every search value (or every record).**

Is that true though? As far as a database is concerned, if there are no sparse-indexes provided, is it said that all data-files have no *"primary index"*? I get that a specific designation for a sparse unique index on a block may be required, but is that what *primary* means? What does this mean for a database, like PostgreSQL, that implements Primary Keys on a dense btrees, and stores its rows in an unordered heap? Does it, technically, not have a *"Primary Index"*?

# Answer
Without the context of the excerpt, I found it confusing since it seemed to depend on fairly specific implementation details. This is, in fact, the case. These course notes give a decent overview of this and related terminology.

A primary index refers to an index stored in sorted order on the sorting key of data stored in blocks. To look up a value, you do a binary search on the index which will produce a pointer to the block, and then you can do a binary search on the data in the block. If the data wasn't in blocks, there would be no point to this as you could just do binary search directly on the data file. (With a primary index, while the *contents* of the blocks need to be in sorted order, the blocks themselves don't necessarily need to be.) This index is not dense since it stores a pointer to a block which will typically contain multiple records, so there is not a one-to-one correspondence between index entries and records.

If you wanted to lookup data based on a key that the records are not sorted on, then you couldn't rely on records between index entries being in the same block, thus an index entry would be required for each specific record. This would be a dense index.

So the thing to note is that this terminology is referring to a specific way of storing and indexing data, namely as a collection of sorted blocks. "Primary index" has nothing to do with "primary key" in this terminology. A primary index depends on how the data is actually sorted (assuming it *is* sorted) which doesn't at all need to be based on the primary key, e.g. you may sort by a timestamp. There is no need for a "primary index" to exist at all.

A B-tree (and its variations) is just a different indexing approach entirely. You can still potentially apply the "dense index"/"sparse index" terminology to it. For example, if your data is sorted on the key the B-tree index is indexing, then it could just as well store only pointers to blocks and then perform a binary search within the block once fetched. This arrangement would produce a sparse index. You could easily imagine different arrangements that would produce a B-tree index that is dense.

I think you are viewing "primary index" as being more widely applicable than it is. I know I was at first which was the source of my confusion. In the context in which it applies, it is a reasonable term, but "primary index" is way too uninformative to stand alone.
> 3 votes

---
Tags: terminology, databases
---


title: Does 2NF require 1NF?

text:
# Question
Title: Does 2NF require 1NF?
From Database System Concepts, by Silberschatz, Korth and Sudarshan :

> A domain is atomic if elements of the domain are considered to be indivisible units. We say that a relation schema `R` is **in ﬁrst normal form (1NF)** if the domains of all attributes of `R` are atomic.
>
> A functional dependency `A →`B is called a partial dependency if there is a proper subset `C` of `A` such that `C → B`. We say that `B` is partially dependent on `A`. A relation schema `R` is **in second normal form (2NF)** if each attribute `X` in `R` meets one of the following criteria:
>
> • It appears in a candidate key.
>
> • It is not partially dependent on a candidate key.

If I am correct, the definition of 1NF in the book is the same as in Wikipedia which says

> A relation is **in first normal form** if and only if the domain of each attribute contains only atomic (indivisible) values, and the value of each attribute contains only a single value from that domain.

Is the definition of 2NF in the book the same as in Wikipedia which says

> a relation is **in 2NF** if it is **in 1NF** and no non-prime attribute is dependent on any proper subset of any candidate key of the relation.

?

Specifically:

1. I don't think the definition of 2NF in the book requires a relation schema being in 1NF, and I wonder if I am wrong and why?
2. While 2NF is related to functional dependency, is 1NF related to functional dependency between attributes in a relation schema? (I don't see the definition of 1NF involves functional dependency.)
3. Does the definition of 2NF in Wikipedia require that there can't be duplicate rows?

Does the definition of 2NF in Wikipedia rely on a different definition of 1NF? For example, see Does 1NF require that there can be no duplicate rows?

Thanks.

# Answer
> 3 votes
I will focus on questions 2 and 3, mainly by recalling a little bit of history of the Relational Data Model.

The first foundamental paper on the Relational Model was published in 1970 by the Turing Award Edgar F. Codd, Codd, E. F. “A Relational Model of Data for Large Shared Data Banks.” Communications of the ACM 13, no. 6 (June 1, 1970): 377–87. (bibliographic description, search pdf).

In that paper it is expressed clearly that relations are **sets**:

> The term *relation* is used here in its accepted mathematical sense. Given sets S1, S2, ... , Sn, (not necessarily distinct), R is a relation on these *n* sets if it is a set of *n*-tuples each of which has its first element from S1, its second element from S2 , and so on ...

So, the requirement of the unicity of the tuples precedes each possible definition of normal form.

Noting that the Codd’s definition leaves open the possibility that the elements of the domains (the Si) can be complex, for instance repeated, Codd introduced the first normal form (1NF) in a 1972 paper: “E. F. Codd (Oct 1972), Further normalization of the database relational model, Courant Institute: Prentice-Hall, ISBN 013196741X,”. In such paper it is said that:

> A relation is in first normal form if it has the property that none of its domains has elements which are themselves sets.

As you have noted, this has nothing to do with functional dependencies, neither with other forms of dependencies (multivalued, join, etc.), and for this reason, it has been considered an essential requirement of the “normal” Relational Data Model. Other data models, the so called non-1NF model, abandon this requirement, and constitute a sort of bridge towards late object-oriented data model (but this is another subject...)

Only later, C.J. Date, a collaborator of Codd, wrote in the paper: “What First Normal Form Really Means,” in “Date on Database: Writings 2000-2006. Berkeley, Calif., Apress (2006)”:

> A **table** is in first normal form if and only if it is "isomorphic to some relation" ... There are no duplicate rows...."

The emphasis is mine, note that he’s talking about tables, not relations, specifying what are the characteristics that tables should have to be considered relations.

So, to summarize:

1. The relational model is based on the mathematical concept of relation, which is a set.
2. The 1NF has nothing to do with functional dependencies, and in the original definition has only to do with complex values (i.e. relations) inside tuples.
3. The other normal forms are defined *ony* in the context of the relational data model, in which relations are set.
4. Relational Database Management Systems (RDBMS) manage “tables”, which are loosely modeled on the mathematical concept of relation as defined in the Relational Data Model, but the normalization theory (functional dependencies, other kind of dependencies, normal forms, etc.) is only partially applicable to them, since it is defined *only* on the Relational Data Model.

# Answer
> 1 votes
You have asked multiple questions and it becomes very difficult to focus on each questions.

So, I will concentrate on your original questions: Does 2NF require 1NF?

Theoretically, when you translate your ER-Diagram to Relational model you normally achieve 1NF because you are required to have separate table(s) for every multivalued table(s).

Functional dependency play a active part in 2NF (and beyond) because it dictates that there should be no partial dependency. That is, if proper subset of candidate key determines non-prime attribute, it is called partial dependency.

Now, can you tell me that how you will resolve for 2NF if values of your attributes are not atomic? How will you check value(s) of some column A to value(s) of some column B for dependency if you have multivalued or composite attribute in it? In functional dependency, we should be able to map each single value of attribute X to each single value of attribute Y.

1NF is not only necessary for 2NF, but 3NF, BCNF and beyond.

So, yes it does required for 2NF to hold it should be in 1NF and partial dependency should be eliminated.

---
Tags: database-theory, databases
---


# Question
Title: Virtual Memory: "Page Table or Page Tables?"
I am having a bit of a tough time grasping whether a computer system contains several page tables or just one page table.

Some sources speak of page tables in plural others in singular.

Intuitively it makes most sense to me that there is only one Page table containing all the physical addresses especially considered these addresses are to change over time. But I am not sure?

# Answer
Each process has a different page table (since each process has a different address space). Each processor (or core if you want to be specific) can only have one active page table at a time, but the processor switches which table is used when it switches between processes.

I am also simplifying here because there are more tables used for IOMMU and hardware assisted virtualization.
> 2 votes

---
Tags: memory-management, virtual-memory
---


title: Coloring a cubic-graph with 2 colors

text:
# Question
Title: Coloring a cubic-graph with 2 colors
Given a cubic graph, I want to color its vertices in 2 colors (Say A & B).

A vertex is considered "Good" iff the majority of its neighbors is colored differently than that vertex. (For example, vertex colored A has neighbors A B B is considered Good, and a vertex colored A has neighbors A A B is considered "Bad")

I suggest the following algorithm:

* Pick a random uncolored node
* Color it in a way that 2 of its neighbors are X, and the last one is Y (Sometimes of course the neighbors are already colored and we determine from that what color the node needs to be and its neighbors also)
* Color the node Y

Running this algorithm seems to work, but I couldn't find an example that it doesn't. And even worse - I cannot even understand how to even begin the proof that this algorithm is correct (if at all)

I feel like I need to use the fact that this is a cubic-graph. But I cannot seem to understand how would that help me here.

**EDIT (Observations):**

* It seems that if I get to pick X uncolored nodes, may graph would have at least X "good" nodes (According to the algorithm)
* That X would be at least |V|/4

I want to start by proving that there can be more than |V|/4 "Good" nodes, because in all of my examples there are at least |V|/2 "Good" nodes.

# Answer
> 3 votes
A 2-coloring of a cubic graph in which all vertices are good is known as an unfriendly partition. Such a coloring *always* exists, and the following algorithm finds it:

* Start with an arbitrary coloring, say everything is colored blue.
* While there exists a bad vertex: pick some bad vertex, and flip its color.

Why does the algorithm terminate? Consider the number of monochromatic edges. Flipping the color of a bad vertex decreases the number of monochromatic edges. Since there are $1.5n$ edges, the algorithm terminates after at most $1.5n$ steps.

In fact, the entire algorithm can be implemented in $O(n)$ time, essentially since every step only affects $O(1)$ vertices. The basic idea is to maintain a stack or queue of bad vertices.

---
Tags: algorithms, approximation, randomized-algorithms
---


# Question
Title: Algorithm to extract line-like contour in 3d
Hello people on the internet,

I'm currently searching for some kind of fast algorithm that allows me to extract curves in three dimensional space that arise as the intersection of two level sets of smooth functions, i.e. \begin{align\*}\mathcal{C} = \\{\vec{x} \in \mathbb{R}^3 | \\; F(\vec{x})= l \\; and \\; G(\vec{x})=s \\} \end{align\*}

I was thinking that something similar to marching cubes might work, but not having a computer science background I'm struggling to make out if and how that would look. Does anyone have a suggestion on what I could do?

**Edit**: I currently use a very inefficient solution where I compute one isosurface with a preimplemented python method on a 3d grid, then check the isosurface for wanted values of the other function (walking along curves in slices of the surface and checking for crossings of the value) and collect all such points. In the end I group them with a clustering algorithm.

**Edit2**: In my specific case, the functions are defined with a few random parameters for some finite natural $N$, which are $\varphi\_n \in \[0,2\pi), A\_n \in \[0,1\], \vec{k}\_n \in S^2$ (the unit sphere) and are restricted to a three-dimensional cube of some size $a$. \begin{align\*}F(\vec{r}) &= \frac{1}{T} \sum\_{n=1}^N A\_n \cos(2\pi \vec{k}\_n \cdot \vec{r} + \varphi\_n) \\ G(\vec{r}) &= \frac{\partial\_z F}{|| \nabla F ||} \end{align\*} for some normalization constant $T$. I want to work with the intersection curves (that I made out to generally be several disconnected ones) for different parameters.

# Answer
Here is a generic approach:

1. Find a point on the intersection of these two curved planes, i.e., on the intersection of $F(\vec{x})=l$ and $G(\vec{x})=s$. Call that point $\vec{x}\_0$.
2. Trace along the intersection curve, starting at $\vec{x}\_0$, and continuing as far as you can. Then do the same starting from $\vec{x}\_0$ in the opposite direction.
3. Find a new point $\vec{x}\_0$ on the intersection of $F(\vec{x})=l$ and $G(\vec{x})=s$ that's not part of what you've traced so far, and go back to step 2.

To instantiate this, we need to know how to implement each of these steps.

To find a point on the intersection of $F(\vec{x})=l$ and $G(\vec{x})=s$, you can use any method for solving a system of nonlinear equations. There are many. If you're not familiar with the subject, one simple approach is to minimize the objective function

$$\Phi(\vec{x})= \\|F(\vec{x})-l\\|^2 + \\|G(\vec{x})-s\\|^2$$

using, e.g., gradient descent.

To trace along the intersection curve, you can use the gradient to help you. Suppose that $\vec{x}\_0$ is a point on the intersection curve, and expand the Taylor series for $F$ and $G$. We get

$$F(\vec{x}) = F(\vec{x}\_0) + \nabla F(\vec{x}\_0) \cdot (\vec{x}-\vec{x}\_0) + \dots \approx l + \nabla F(\vec{x}\_0) \cdot (\vec{x}-\vec{x}\_0)$$

and similarly

$$G(\vec{x}) \approx s + \nabla G(\vec{x}\_0) \cdot (\vec{x}-\vec{x}\_0).$$

So, for $\vec{x}$ to be on the intersection curve, we require $ \nabla F(\vec{x}\_0) \cdot (\vec{x}-\vec{x}\_0) = 0$ and $\nabla G(\vec{x}\_0) \cdot (\vec{x}-\vec{x}\_0)=0$ (assuming $x$ is very near $x\_0$). Since $\nabla F(\vec{x}\_0)$, $\nabla G(\vec{x}\_0)$, and $\vec{x}\_0$ are known and computable, this gives us two linear equations in three unknowns, so we can solve for $\vec{x}$ using a linear equation solver. In particular, compute the two vectors $\nabla F(\vec{x}\_0)$ and $\nabla G(\vec{x}\_0)$, then find a unit vector $\vec{d}$ that is orthogonal to both of them. Now you can trace out the intersection curve from $\vec{x}\_0$ by preceding in the direction $\pm \vec{d}$; in other words, the line $\vec{x}\_1=\vec{x}\_0 + c \vec{d}$ is approximately on the intersection curve, when $c$ is close to 0. (If you want, you can generate $\vec{x}\_1$ in this way, then "fine-tune" it by using it as the starting point for gradient descent with objective function $\Phi$ to compute $\vec{x}\_1$ more precisely and to make sure you stay on the intersection curve.) This gives you a way to step along the intersection curve, one point at a time.

How to implement step 3? This might depend on the specific functions $F,G$. One approach is to modify the objective function $\Phi$ to penalize points that are near the part of the curve you've already found, e.g.,

$$\Phi(\vec{x}) = \\|F(\vec{x})-l\\|^2 + \\|G(\vec{x})-s\\|^2 + \sum\_i {1 \over \\|\vec{x}-\vec{x}\_i\\|^2},$$

where the $x\_i$'s are points you've previously found (or some well-spaced-out subset of them). Another approach might be to do step 1 (gradient descent on $\Phi$, without the penalty term) starting from many different starting points (e.g., spaced on a coarse grid). There may be a better way in your specific situation; I don't know.

I expect this should be more efficient than enumerating all grid points and evaluating $F,G$ at every grid point, especially as the spacing of your grid points gets small. It does require you to be able to compute the gradients of $F,G$, but in your situation that seems to be no problem.
> 1 votes

---
Tags: algorithms
---


# Question
Title: An efficient algorithm to decide if a triangulation is 3-colourable
I don't know how to start with the following exercise:

> Design an efficient algorithm to decide whether a given triangulation with $n $ points is $3$-colourable. The triangulation is given by a sorted edge list, where every edge is given by the indices of its two end points. Further, for every edge there are given the indices of the points with which the edge forms a triangle in the triangulation (two indices for interior edges and one index for edges on the boundary of the convex hull). Give proof for the correctnesss of your algortihm.

Below is an example.

I've heard about the BFS and DFS algorithms in lecture, but I don't see how I could apply this here. I'd be thankful for any help.

# Answer
Let us assume that the dual graph is connected, which means that if you connect any two faces which share an edge, then you get a connected graph on the triangular faces.

Pick an arbitrary triangular face $F$ and color its 3 vertices with 3 distinct colors. If $F'$ shares an edge with $F$, then there is only one choice for the color of the remaining vertex of $F'$. Continuing in this way, attempt to color all vertices. If you're successful, the graph can be 3-colored. Otherwise, the graph cannot be 3-colored.

This algorithm is very similar to the one for deciding whether a given graph can be 2-colored.
> 7 votes

---
Tags: algorithms, graphs, colorings
---


# Question
Title: Similarly structured loops with different big-O time complexities?
I have a function:

```
int sum = 0;
for (int i = 1; i < n; i*= 2)
  for (int j = 0; j < n; j++)
    sum++;

```

From my understanding this is $O(n\log(n))$ because the inner loop runs $n$ times for every time the outer loop runs, and the outer loop is running $\log(n)$ times. Putting them together gives me $O(n\log(n))$, which I understand. However, the following loop:

```
int sum = 0;
for (int i = n; i > 0; i/= 2)
  for (int j = 0; j < i; j++)
    sum++;

```

I see this as $O(n\log(n))$ because the outer loop is running $\log(n) + 1$ times still and the inner loop runs $n + n/2 + n/4...$ whose sum will be some coefficient $c$ times $n$. Together with the outer loop simplifying to $O(n\log(n))$ but it turns out it is actually $O(n)$ however I don't see how it is?

# Answer
> 0 votes
The first version increments `sum` $$ \underbrace{n + n + \dots + n}\_{\log n \text{ terms}} = n\log n $$ time; the second does it $$ \underbrace{n + \frac{n}{2} + \frac{n}{4} + \dots + 1}\_{\log n \text{ terms}} \leq 2n $$ times (use the formula for a geometric series).

By the way, it's not actually *wrong* to say that the second is also $O(n\log n)$: it's just that you can give a more precise answer of $O(n)$.

# Answer
> 0 votes
In the second algorithm, the total number of increment operations would be $$\sum\_{i=0}^{\lceil\lg n\rceil } \frac{n}{2^i}$$, which is $\leq 2n$. See this Wikipedia article about infinit geometric series and the inequallity should be clearer.

---
Tags: algorithms, asymptotics
---


# Question
Title: Hamiltonian path and minimum spanning tree
Suppose i have a graph and i want to find minimum-spanning-tree. As in imperative languages we have to take specific steps from everynode(example ,we use kruskal's algorithm or prim's algorithm) to find the Minimum spanning tree

but

in declarative language(specially prolog, we can apply same algorithm but those are limited) , If i want to find a minimum spanning tree on the same graph, If i collect all possible hamiltonian paths using `findall/3` predicate then chose the one with smallest accumulated cost, is it then also a minimum-spanning-tree?

More specifically , Can we transform the problem of `finding minimum spanning tree` to the hamiltonian path finding problem but not in other direction? Because normal algorithms return one specific `minimum spanning tree` of a graph but i am more interest in finding more than one minimum spanning trees.

# Answer
> 2 votes
No. Every path is a tree, but not every tree is a path. Therefore, the minimum spanning path might be more expensive than the minimum spanning tree.

If you work through some examples you should be able to find an explicit counterexample. I'll let you have the joy of finding it on your own.

---
Tags: graphs, shortest-path, hamiltonian-path, prolog
---


# Question
Title: Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free?
Is the language $L = \\{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\\}$ context free? I should probably use Ogden's lemma, but I don't know how to do that in this case.

# Answer
> 0 votes
If $L$ is context-free, then according to Parikh's theorem, the set $\\{(p,q) : p,q \geq 1, p \geq q^2 \text{ or } q \geq p^2\\}$ is semilinear, say it is the union of the linear sets $L\_i$. Each linear set is either a singleton or of the form $(a,b) + \mathbb{N}(x,y)$. In the latter case, I claim that either $x = 0$ or $y = 0$. Otherwise, for large $n$ we have $\frac{a+nx}{b+ny} \approx \frac{x}{y}$, and in particular it isn't the case that $a+nx \geq (b+ny)^2$ or $b+ny \geq (a+nx)^2$.

It follows that there exists a finite set $F$ such that $$ \bigcup\_i L\_i = F \cup \bigcup\_j (p\_j+\mathbb{N}t\_j,q\_j) \cup \bigcup\_k (p'\_k,q'\_k+\mathbb{N}t'\_k). $$ Let now $z \geq 2$ be some integer larger than all indices in $F$ and all $p\_j,q\_j,t\_j,p'\_k,q'\_k,t'\_k$, and consider the point $(z^2,z)$, which should be contained in this union. By construction, it is not contained in $F$ or in any $(p\_j+\mathbb{N}t\_j,q\_j)$. If $(z^2,z) = (p'\_k,q'\_k+nt'\_k)$ and $(p,q) = (p'\_k,q'\_k+(n+1)t'\_k)$, then we must have $q \geq p^2$, which implies that $z+t'\_k \geq z^2$. This again contradicts our choice of $z$. It follows that $(z^2,z)$ is missing from the union, and we reach a contradiction.

---
Tags: formal-languages, context-free, pumping-lemma, pushdown-automata
---


title: Checking if the mimimum is unique

text:
# Question
Title: Checking if the mimimum is unique
We have a finite poset and its subset $S$.

We can enumerate elements of $S$ using an iterator.

I need to check if there are more than one minimal elements of $S$ (regarding the above poset).

The best thing I came up with is to construct the graph of all elements of $S$ and then check it for minimal elements. But this:

1. requires to enumerate all elements of $S$ (while I would prefer to interrupt the calculating in the middle as soon as we get $2$ minimal elements);
2. may use much memory.

Is there a better way (without enumerating all $S$)?

# Answer
You cannot avoid enumerating all elements. Consider the following two posets, with elements $x,y,z\_1,\ldots,z\_n$:

1. $x,y \< z\_i$ for all $i$.
2. $x,y \< z\_i$ for all $i \< n$, and $z\_n \< x,y$.

The first poset has two minima, and second only one. You can only tell the difference by enumerating over all elements.

---

If there is a unique minimal element $z$, then $z \< w$ for all other elements $w$ (since there is a minimal element below any given element). This allows us to use the following constant space algorithm, which assumes that the elements of the poset are $z\_1,\ldots,z\_n$:

* Initialize $t \gets z\_1$.
* For $i=2,\ldots,n$: if $z\_i \< t$, let $t \gets z\_i$.
* Go over all elements again, and verify that $t \leq z\_i$ for all of them.

There is a unique minimal element iff the verification succeeds.
> 3 votes

---
Tags: algorithms, decision-problem, sets, enumeration, partial-order
---


# Question
Title: Lower bound of complexity of simple problem
Consider the simple problem:

Given a list of objects *L* of length *n*, and an object *O*, determine if *O* is in *L*.

It is intuitive that there cannot exist an algorithm a with worst-case time complexity less than O(*n*) to correctly solve this problem. But without considering individual algorithms, how can one mathematically prove that no faster algorithm exists?

# Answer
> 2 votes
The informal argument is that you need at least $n$ steps to read all the input assuming you can only read at most one element of the input per "step". Of course, you might state that maybe there's an algorithm that doesn't need to read all the input. The argument against that is an adversarial argument which produces an input where such an algorithm will get the wrong answer.

Let $x$ be an input of length $n$ that doesn't contain $O$, and $A$ an algorithm that completes in less than $n$ steps correctly reporting that the input does not contain $O$. There is necessarily an element of the list that $A$ did not look at. Pick one and call that the $i$th element. Running $A$ on $x'$ which is identical to $x$ except that the $i$th element is $O$ then produces the incorrect result. Since $A$ is deterministic and all the inputs $A$ actually reads are the same, then $A$ must behave in the same manner and so it will incorrectly report that the list does not contain $O$.

---
Tags: complexity-theory, time-complexity, proof-techniques
---


# Question
Title: Fastest (fast enough to compute) algorithm for finding permutations
I have a set of letters, and a list of words, and I'd like to find all the possible "sentences" that can be built using the words from the list, while using up all the letters in the process. (A word can be used more than once.) The maximum amount of words in a sentence is also given.

For example, my letters are {"a","a","a"}, and for the sake of simplicity, my words are {"a","aa","aaa"}, and I'm looking for sentences of maximum 3 words (cannot be more in this case anyway).

The order of the words in a sentence doesn't matter, so "a aa", and "aa a" would be considered duplicate sentences, so the output would be the following:

{"a a a", "a aa", "aaa"}

I need an algorithm that finds and lists these sentences (no matter how many there might be) for larger sets. Right now I have 9000 words, and 24 letters. (I know the amount of words is way too much, but let's just disregard that in this case.)

I'm really new to this kind of problem solving, and algorithms in general, so I tried several approaches on my own (and with the help of the internet) with obviously not much success.

The closest I could come up with was the following:

I assigned a prime to each character, and then each word would be the product of them, then considering the letters is together are also a "word", I could find out whether a word was a part of it with congruency, then after dividing the set of letters by word after word would eventually end up being 1, which means, I found a sentence.

So with this in mind, my approach was the following:

I start a sentence with each word, then then I find the next possible words for each one. Then I take all the valid (now 2 word) sentences, and find a next word for each of them as well. And I repeat this until I reached the maximum amount of words I'm looking for.

*By "valid" sentences, I mean the ones that can be used in the next iteration, which means that their "letters" are not 1 (in which case no more words can be found, and the sentence is done), and a word was found in the previous iteration, no further validation takes place.*

The problem with this is that it takes way too much time to be usable, e.g if I start with 3 words, for finding all the 3 word sentences in the worst case I would have to go through the list of words 3+3^2+3^3 times if I'm not mistaken, but I'm looking for sentences with a maximum of 6 words, and I'm supposed to start with a lot more words. Another problem is that with this approach I end up with duplicatons, and I'd need to filter the result in the end.

Are there any algorithms that are suitable for this kind of problem, or can it even be solved in polynomial time?

Thanks in advance

# Answer
> 1 votes
Suppose you are working with an alphabet of size $d$. Then each word can be represented as its characteristic vector. A characteristic vector $v \in \mathbb{N}^d$ is a vector, where the $i$th entry counts the number of times the $i$th letter appears in the word. For instance, the word $abbad$ would have characteristic vector $(2,2,0,1)$ if the alphabet is $a,b,c,d$.

As Yuval explains, you want to find all strings which satisfy the following two properties: (1) they are a rearrangement of the list of letters, (2) they are a concatenation of up to $n$ words from the list of words (the same word can be used several times).

Looking at characteristic vectors, you can think of the problem as follows: you are given vectors $v\_1,\dots,v\_k$ (corresponding to the list of words) and a vector $w$ (corresponding to the characteristic vector for the list of letters), and you want to find non-negative integers $a\_1,\dots,a\_k$ such that

$$a\_1 v\_1 + \dots + a\_k v\_k = w.$$

You also want $a\_1 + \dots + a\_k \le n$ (to satisfy requirement (2) above). You want to enumerate all solutions $a\_1,\dots,a\_k$ that satisfy these requirements.

This turns out to be an instance of enumerating lattice points in a convex polytope, for which there are well-studied algorithms. See the following paper for an overview:

You could try applying one of those algorithms to your problem to see how well they work.

---

Alternatively, it's also possible to solve the problem by repeatedly invoking an ILP solver. You can use an ILP solver to test whether any solution exists, and the largest value of $a\_1$ such that a solution exists. Then, if at least one solution exists, you enumerate $a\_1=0,1,2,\dots$, and for each value of $a\_1$, plug in the value of $a\_1$ and recursively invoke the same algorithm to enumerate all solutions for $a\_2,\dots,a\_k$ (such that $a\_2 v\_2 + \dots + a\_k v\_k = w - a\_1 v\_1$ and $a\_2 + \dots a\_k \le n - a\_1$). This might be inefficient, though.

---
Tags: time-complexity, combinatorics
---