# Question
Title: Recursion Time Complexity (Half n' Half)
This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity:

* Input: string $s = s\_1,\ldots,s\_n$, integer $k$
* Go over all symbols $s\_1,\ldots,s\_n$, one by one
* For each symbol $s\_i$, check whether it appears less than $k$ times in $s$
* If all symbols appeared at least $k$ times, return $n$
* Otherwise, let $i$ be the first index such that $s\_i$ appears less than $k$ times
* Call the procedure recursively on $s\_1,\ldots,s\_{i-1}$ and on $s\_{i+1},\ldots,s\_n$, and output the maximum

Here is a C++ implementation:

```
int longestSubstring(string s, int k) {
        for (int i = 0; i < s.length(); i++) {
            if (count(s.begin(), s.end(), s[i]) < k) {
                string left = s.substr(0,i);
                string right = s.substr(i+1,s.size()-1);
                return max(longestSubstring(left,k),longestSubstring(right,k));
            }
        }
        return s.length();
    }

```

The `count` method runs in $O(n)$.

I'm new to asymptotic complexity, but from what I understand, "half n' half" recursion has time $T(n) = 2T(n/2)+f(n)$ where $f(n)$ is the time the rest of the execution takes. At this point, we'd induct, and get a general pattern. Then, given that we usually know $T(0)$ and $T(1)$, we can get an expression in $n$, which would be our time complexity.

Now, my problem is that my implementation doesn't split the string into exact halves (in the same way a BST traversal splits the input in halves, for example), so I can't really write $T(n/2)$, correct? Are $T(0)$ and $T(1)$, $O(1)$ and $O(n)$ respectively?

Is there, perhaps, a faster way to solve this problem? Leetcode says it runs in 0ms, but I find that dubious. It takes a longer time to execute than one of the highest upvoted Python implementations, which is supposedly $O(n)$.

# Answer
I can offer one simple optimizations to your code.

At the moment your code will take $\Omega(n^2)$ time even on a string in which each symbol appears at least $k$ times. This can be avoided using counting sort: using a single pass, you can compute how many times each letter appears. If every letter appears either 0 or at least $k$ times, then the current string is good. This takes linear time.

(This uses the fact that it is known that all letters of the string are lowercase letters. If the letters are arbitrary, you can still speed this up by sorting the array.)

Even after this optimization, your code suffers from a problem. Suppose that $k = n/2 + 1$, and let the string consist of $n/2$ copies of `a` followed by $n/2$ copies of `b` (as an aside, you can immediately return 0 in this case – a further optimization). Your code will recurse on the substring $s\_2,\ldots,s\_n$, the on the substring $s\_3,\ldots,s\_n$, and so on, not giving up at any point. Therefore it will take time $\Theta(n^2)$ (or, without the first optimization mentioned above, $\Theta(n^3)$).

In order to avoid this, suppose that you found out that $s\_i$ appears fewer than $k$ times. Find all occurrences of $s\_i$, partition the string accordingly, and recurse on each such substring. This will guarantee that each substring won't have the letter $s\_i$. Each time you recurse, you have one fewer letter appearing, and so the depth of the recursion tree is at most 26. Therefore the algorithm will run in *linear* time.
> 0 votes

# Answer
Starting from the leftmost position, maintain a histogram of the symbol frequencies. All entries initially zero. Every time you process a symbol, check if it is a new one (frequency still zero), and increment a count of "lacunary" symbols in the string; also increment the frequency for this symbol and if it reaches exactly $k$, decrement the count of lacunary symbols. Then keep the value of the length of the last string with zero lacunarity, which is perforce the longest. This process takes linear time in the length of the string (plus the size of the alphabet).

Then repeat the whole process, starting from the second symbol, and so on. So far I see no way to make it faster.
> 0 votes

---
Tags: time-complexity, asymptotics, runtime-analysis, recursion
---


# Question
Title: Regular grammar such that it rejects keywords
I want to write a regular grammar that follows the C language. I almost wrote the grammar, but was not able to resolve how to define a variable.

Def: A variable can be any combination of characters, but it should not be an existing keyword.

I tried writing something like this but not sure how to write it:

```
<Var> -> {a-z}+ (!b<Kew1>|<Kew2>|<Kew3>|<Kew4>)

```

Here `<Kew1>.. <Kew4>` are already defined keywords like `int`, `for`, `while`, `read`, ...

# Answer
> 2 votes
Actual compilers cheat here, instead of doing a full per character grammar they instead do a per token grammar.

This means that there is a tokenizer which will preparse the character stream with a regular language parser and emit a stream of tokens. These tokens are then the whitespace, operators, keywords, identifiers, etc.. This has the guarantee that a Identifier token is never going to be a keyword.

```
<Var> -> Identifier

```

If you really want to have the per character grammar you will need to implement the DFA for parsing the keywords as a grammar:

```
<Var> -> (all letters that aren't the start of a keyword) {a-z}*
<Var> -> i ({a-mo-z} {a-z}*)?
<Var> -> in ({a-su-z} {a-z}*)?
<KeyWordINT> -> int
etc.

```

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


# Question
Title: Approximating the median of the complement of a set
Given an integer $n$ and a tree set $S$, I would like to find the *approximate* median $x$ of the integer set $T := \\{i \in \mathbb N : i \< n \wedge i \notin S\\}$. There are no constraints to the distribution of $S$, so it is not possible to assume that $S$ is uniformly distributed over $(0,n)$. This problem can be found in linear time with this algorithm:

```
def find_median(n, S):
    counter = 0
    for i in range(n):
        if i not in S:
            counter += 1
            if counter * 2 >= n - len(S):
                return i
    panic("n is smaller than len(S)")

```

I would define "approximate median" as follows:

> Let $k$ be the index of $x$ in $T$. Then $\left|\frac{|T|}2-k\right| \in O(\log n)$.

If anyone is interested in my original goal: I wanted to bisect a set of tasks (where $S$ is the set of tasks I don't need to execute) to two workers, so I wish to find the splitting point, where off by a few elements is acceptable compared to the scope of the whole task set.

To illustrate with an example, for $n=11$ and $S=\\{6,7,8,9,10\\}$, we have $T = \\{1,2,3,4,5\\}$, so the median is $3$. We cannot simply find this by taking $\frac n2$ because $S$ may be biased.

The opposite of this problem (where $i \in S$ instead of $i \notin S$) can be trivially found in $O(\log n)$ time by finding the $\frac{|S|}2$th vertex in the tree set; even in tree set implementations where the cardinality of each subtree is not stored, for a balanced B-tree, we are only off by $O(\log |S|)$ elements in the worst case by selecting the middle node in every vertex (for odd B-trees) or the leftmost vertex in the $\frac n2+1$th topmost subtree (for even B-trees).

So, is it possible to achieve the same time complexity for the $i \notin S$ case? Or is it possible to prove the lower bound of this algorithm? And if possible, is it possible to achieve an ideal time complexity by just storing $O(\log |S|)$ extra metadata (e.g. on the $S$ tree set itself)?

# Answer
> 2 votes
### $T$ as the union of subintervals

Let $U = \[1,n-1\]$. In your problem, you can think of $S$ as elements removed from $U$. Removing an element splits $U$ into several smaller subintervals. The union of all these subintervals generates $T$.

Let $S' = S \cup \\{0,n\\}$. Working with $S'$ instead of $S$ will make some definitions more consistent and simpler.

Now assuming that elements of $S'$ are stored in a BST $S'\_\tau$, then each node $y$ of the BST induces a **left interval** $L\_y = \[y\_p+1,y-1\]$ where $y\_p$ is the predecessor of $y$ in $S'\_\tau$. Note that since $0 \in S'\_\tau$, all elements of $S$ have predecessors in $S'\_\tau$.

The left intervals of all $y \in S'\_\tau$ are exactly the subintervals that generates $T$.

### Median Finding

The algorithm that will be described here is a modification of the order statistic tree.

First note that if we write down all the elements of $T$ in sorted order, the position of the median of $T$ in $T$ is $m = \left\lceil{\frac {n - |S|} 2}\right\rceil$.

Now, for each node $y \in S'\_\tau$, let $size(y) = size(y\_{l}) + size(y\_{r}) + |L\_y|$, where $y\_{l}$ and $y\_{r}$ are the left and right children of $y$, respectively, and $|L\_{y}|$ is the size of the left interval of $y$. If $y\_{l}$ does not exist then $size(y\_{l}) = 0$. Similarly $size(y\_{r}) = 0$, if $y\_{r}$ does not exists.

Essentially, $size(y)$ gives the number of elements of $T$ in $y$'s subtree.

Let **rank** of $y$ be the number of elements of $T$ that is less than $y$.

To find the median, we first select $x$, the minimum node in $S'$ with rank greater than or equal to $m$.

1. Initialize $y$ to be the root of $S'\_\tau$ and $m' = m$.
2. Let $r = size(y\_l) + |L\_y|$.
3. If $r \ge m'$ and $size(y\_l) \lt m'$ then $x = y$ and stop.
4. Else if $r \ge m'$ and $size(y\_l) \ge m'$, let $y = y\_l$ and go to step 2.
5. Otherwise, let $m' = m' - r$ and $y = y\_r$ and go to step 2.

Once $x$ is found the median of $T$ is equal to $x\_p + (m - size(x\_l))$.

### Notes

The algorithm can be implemented by augmenting a BST such that each node $y$ stores $size(y)$. This value can easily be updated in $O(1)$ time per node in the path during insert and delete. When the number of elements $n$ increases, it is also trivial to find node $n$ in the BST and update its value. It is assumed that $n$ is the initial element of the BST, prior to any insert.

If the BST is balanced the running-time of the median finding algorithm is $O(\log n)$.

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


title: BSTs with repeating keys

text:
# Question
Title: BSTs with repeating keys
The problem is to count number of unique binary search trees with keys $a\_1,a\_2,...,a\_n$, given that some of the keys are not unique. For example, $a$ could be 2, 1, 1, 4, 3, 4.

We could try an approach that is similar to the case when keys are unique - choose some root node from $a$ and then solve two subproblems - one on the prefix before the root and, similarly, on the suffix after the root. Then we sum over all chosen roots and multiply prefix and suffix subproblem answers. For the example above, there are six prefix subproblems:

* 1 (answer is 1)
* 1, 1 (answer is 1)
* 1, 1, 2 (answer is 3)
* 1, 1, 2, 3 (???)
* 1, 1, 2, 3, 4 (???)
* 1, 1, 2, 3, 4, 4 (???)

The answers are obvious in case when prefix contains just \[1, 1, ..., 1\] or \[1, 1, .., 1, 2\], but how can we solve next ones?

# Answer
> 0 votes
Any tree structure can be labeled with keys to make a BST. This property does not need for the keys to be different.

That means that there are as many BST over $n$ keys (some not unique) as there are binary trees over $n$ nodes: the $n$-th Catalan number, $C\_n = \frac{1}{n+1}\binom{2n}{n}$.

---
Tags: trees, combinatorics, binary-trees, search-trees, counting
---


# Question
Title: Instances of simulating lambda calculus?
There are a ton of resources on the web devoted to proving some esoteric language is Turing complete by simulating arbitrary turing machines. I have an esoteric language I want to prove is complete, but I'm pretty sure the easier way to do it would be to prove that you can express any untyped lambda calculus term in it; i.e.

Recursively, it can represent a name, x. Given a lambda term E1 and E2 and a name v, it can represent lambda v.E1 as well as (E1)(E2).

Are there any existing examples of trying to prove a language is Turing complete through reduction to untyped (or any other Turing-complete) lambda calculus rather than through reduction to whether a Turing Machine halts?

# Answer
> 3 votes
Yes, I think the most famous example is the $\pi$-calculus, which Milner showed to be complete by such a reduction in Functions as Processes.

---
Tags: computability, lambda-calculus, turing-completeness
---


# Question
Title: Is it correct to state the decision problem Clique can be solved in time $O(\min(n^kk^2, 2^{n/4}))$?
With the decision problem Clique, I mean:

Given a graph $G$, does $G$ admit a clique of size at least $k$?

From Wikipedia, one finds that the brute force algorithm of testing all possible subsets of size $k$ results in a complexity of $O(n^kk^2)$. On the other hand, Wikipedia also states that a maximum size clique can be obtained in time $O(2^{n/4})$.

It seems to me that these complexities are incomparable, meaning that in some cases the former would outperform the latter and vice versa. Would it thus be correct to state that Clique can be solved in time $O(\min(n^kk^2, 2^{n/4}))$?

# Answer
> 1 votes
Yes. You can just compute which is the smallest between $n^kk^2$ and $2^{n/4}$ and run the corresponding algorithm.

Alternatively, you could run both algorithms in parallel (alternating one step of each) and stop when one finishes.

---
Tags: time-complexity, clique
---


# Question
Title: How to prove that this problem is NP Complete
I have a problem set about NP Completeness proofs and I'm struggling to approach this problem:

An organizer would like to arrange all the participants in a circle where neighboring two students must have taken the same class last semester.

How to prove that this is an NP complete problem?

Any hints/tip would be very helpful! Thank you!

# Answer
* Same class last semester: an edge between two vertices.
* Students in a circle: an hamiltonian cycle.

I think you should be able to do the rest.
> 4 votes

---
Tags: np-complete, np-hard, np, traveling-salesman, vertex-cover
---


# Question
Title: Confusion about asymptotic notations in math and computer science
The last times i was searching a lot to understanding Big O notation or in general asymptotic notations concepts because i didnt hear about it or them before starting studying in computer science.

* (In computer science) Since to get asymptotic notation of a function we must get firstly the function itself. And because functions can be sometimes complex therefore dificult to compare between each other, we find their asymptotic notations. So asymptotic notations are used because we don't want to deal with complex functions, and their purposes is only comparing between two or more algorithm's efficiency for large values of `n` in a simplest way. Am i right?
* In math thoes notations can be used for n approaching to some real number a `[n-->a]` (not only to infinity), but in computer science is used only for large n (`n--> approcah to infinity`). Am i right?
* (In computer science) When we have `f(n)=O(g(n))` this means that `for all n>n0` when we multiply `g(n)` to `some constant c` we get `f(n)` : `f(n) = c * g(n)`. So my question is, this `constant c` is constant only for given `n` and will change for every different value of `n` (case 1), or `c constant` is constant for all values of `n` which therefore means that after `n0 point` `f(n)` graphic will be parallel to `g(n)` graphic (case 2)?

I asked this question to myself, my head give me this answer: "If case 1 is true `c constant` will not be a constant, and it will vary according to `n`, Else if case 2 is true, why some `g(n) functions` that is said to be `big O of f(n)` are not really parallel to `f(n)`." As you see there is where i was confused.

# Answer
Asymptotics is indeed a way to compare the performance of algorithms, and to attest whether they are usable in practice. However, asymptotics are not everything: in the big-o notation, the value of the constant matters in many cases. For example:

* Fibonacci heaps are one of the best way to implement heaps in terms of asymptotic complexity of different operations. However, the leading constant is too big for it to be efficient for input sizes in practice;
* many sorting algorithms have the same $\mathcal{O}(n\log n)$ complexity, but some of them are faster than others;
* big integer multiplication use different algorithms depending on the size of integers multiplied: as the size increase, so do the multiplicative constant in the $\mathcal{O}$, but the function is asymptotically smaller.

Note that $\mathcal{O}(g)$ is a set of function, not a function itself, though we often write $f(n) = \mathcal{O}(g(n))$ instead of $f\in \mathcal{O}(g)$ for convenience. In computer science, this asymptotic notation is indeed mainly used for $n$ being an integer, and $n\longrightarrow +\infty$.

Also, $f(n) = \mathcal{O}(g(n))$ does **NOT** mean that there exists $n\_0\geqslant 0$ and $c\>0$ such that $n\geqslant n\_0 \Rightarrow f(n) = cg(n)$.

The $\mathcal{O}$ notation gives an upper bound, not an equality. Using the same notations, it means that there exists $n\_0\geqslant 0$ and $c\>0$ such that $n\geqslant n\_0 \Rightarrow f(n) \leqslant cg(n)$. Also, $c$ is a constant that does **NOT** depend on $n$ (otherwise any function would be a $\mathcal{O}$ of any other).

What that means is that the function $g$ is ultimately increasing at least as fast as $f$. That's why function graphs are not necessarily parallel.
> 1 votes

# Answer
Asymptotic analysis is used mainly for two reasons

* because of technical difficulties one can meet when evaluating some functions (for instance, we can't easily evaluate $\sum\_{i=1}^n\frac1n$ but we know that it is well approximated by $\log(n)+\gamma$);
* because when we want to compare functions, we prefer to look at the general trend rather than local details that can make the formulas cumbersome. For instance, $n\log n$ and $\log n!$ have the same asymptotic behavior, and the first form can be easier to handle.

Furthermore, in the case of computer programs, we want to abstract away the performance of a particular machine and we are only interested in running times to an arbitrary factor. (In pure mathematics, it makes more sense to avoid this factor.) This is why the notations $O$, $\Omega$, $\Theta$... have been introduced. They are a tradeoff between accuracy and simplicity.
> 1 votes

---
Tags: complexity-theory, time-complexity, asymptotics, big-o-notation
---


# Question
Title: Reducing problems to solve easier problems
Is there any instance where a problem $A$ can be reduced to a problem $B$ where $B$ is easier to solve than $A$?

I've been learning about NP-Hardness recently and seems that the answer is no. Whenever we show $ A \leq\_p B$ its also said that $B$ must therefore be at least as hard as $A$. If this is always the case then is reducing a problem into another only useful for proving NP-Hardness/NP-Completeness? Is there no way to leverage reductions to find an easier problem to solve than the one you originally start out with?

# Answer
Roughly speaking, no. One way to solve A is by using the method for solving B combined with the reduction from A to B. So if that reduction is efficient, then solving A can't be too much harder than solving B.

If I'm pedantic, yes, B might be a little bit easier to solve than A. If the reduction is very expensive (takes a long time, or significantly increases the size of the problem instance), then B might be a lot easier to solve than A. Normally in study of NP-completeness we address this by requiring the reduction to run in polynomial time, and we ignore any differences that are at most a polynomial factor.
> 0 votes

---
Tags: np-complete, reductions, np-hard, np
---


# Question
Title: Compare list of parameters with each other and sort them from most to least selected
I want to sort the list of parameters (p1, p2, p3, p4, ..., pn) according to their importance. All parameters have to be compared with each other at best once, but not less than once.

The person will be asked to select the winner of the comparison, so for every comparison, there is only 1 winner.

The workflow should be similar to this:

1. Compare p1:p2, p1:p3, p1:p4, p2:p3, p2:p4, p3:p4, ... as seen in the table below. Compare that many times that we can make an order without a doubt.
2. Sort the parameters from most to least winning.

```
|    | p1 | p2 | p3 | p4 |
| p1 | xx | xx | xx | xx |
| p2 | p1 | xx | xx | xx |
| p3 | p3 | p2 | xx | xx |
| p4 | p1 | p4 | p3 | xx |

```

Sorted example (not in correct order): p4, p2, p3, p1

The problem with the comparison above is that there is not enough data to sort them all, so we need to compare further.

I don't know how to write an algorithm that will be suitable for the human comparison of a list with around 10 parameters.

# Answer
I will assume that the importance relation is transitive, and in fact, forms a partial order.

If the algorithm is not free to choose which comparisons are done, but that was chosen by someone else and the algorithm just sees the results of those comparisons, then build a directed graph (with an edge from p1:p2 if you compared p1,p2 and p2 was more important), then perform a topological sort of this graph. The last item in the sorted list will be a candidate for which item is most important. Note that it might not be possible to determine uniquely which item is most important. For instance, if you compare p1:p2 and p1:p3 and find that p1 is less important in both cases, then you won't know whether p2 or p3 are the most important, but the topological sort will show you one possible ordering that is consistent with all of the comparisons you've done so far.

If the algorithm is free to choose which pairs are compared, use any comparison-based sorting algorithm. See https://en.wikipedia.org/wiki/Comparison\_sort.
> 1 votes

# Answer
As "all parameters have to be compared with each other at best once\*, but not less than once", you must perform at least $\frac12 n(n-1)$ comparisons and you can do it in the systematic way, like in your example. There is no shortcut.

\*If you perform the same comparisons several times, there are two possibilities:

* all comparisons come to the same conclusion, then this was useless extra work;
* the results differ, then you are stuck, you can't sort the parameters.
> 0 votes

---
Tags: algorithms, sorting, comparison
---


# Question
Title: Desirable fraction of non-parallelizable code in Amdahl's law
I read that if $\alpha$ is the fraction of the code that cannot be made parallel then it is desirable that $\alpha \< \frac 1 p$ where $p$ is the number of processors.

Why is it the case?

The speed-up is $S(p) = \frac{T\_1}{T\_p} = \frac{p}{1+(p-1)\alpha}$

# Answer
When $\alpha=\dfrac1p$, the speedup is $$\dfrac{p^2}{2p-1}\sim50\\%\\,p$$ so the processors are well utilized.
> 1 votes

# Answer
An example: You have 10 processors, and 1000 items that can be handled by any processor. So you let any processor handle 100 items, and you are finished after 100 time units. With a single processor, that processor would have to do all thousand tasks and take 1000 time units, 10 times more.

Now you have another kind of task y. Y can only be handled by one processor at a time. If you have 100 of these tasks, you give them to 1 processor which takes 100 time units. Meanwhile the other nine processors do 900 of the other task. So you’ll need another ten time units for 100 tasks and finally you finish 1100 tasks after 110 time units. 10 times faster.

Now assume you have 200 tasks y. You give them to one processor which takes 200 units. The other nine processors finish their 1000 tasks in 112 time units and then do nothing. It takes you 200 time units to do 1200 tasks, so your gain went down from 10 to 6.

So as long as task y takes only a fraction of 1/p of all work, you still get the speed up. Above that your speed up goes down.

PS. The "speed-up" formula seems to assume that "non-parallelizable" means all other processors need to be idle. That is rarely the case. Unless told otherwise I would always assume that "parallelizable" code can run simultaneously on the p-1 other processors.
> 0 votes

---
Tags: parallel-computing
---


# Question
Title: Does Amdahl's law apply to modern multi-code processors?
I was reading about Amdahl's law and it state that value of Amdahl's law always lies between 0 and 1. My question is, is it still true in today's case/scenario? When we have system like core i7?

# Answer
Yes, it's still true. The speedup can't be less than zero (if parallelizing your code makes it slower, just run the serial version) or more than 100% (because saving more than 100% of the runtime would make the runtime negative).

Multicore processors are essentially just a matter of terminology changing over time. If you think you have one processor with four cores, Amdahl thinks you have four processors.
> 4 votes

# Answer
There are many different aspects to this.

It is quite common that you can perform an algorithm on one processor doing an amount x of work, and you can distribute it to several processors but do more work. Which is fine if your machine is otherwise idle. Unless it is a mobile device where a single core at lowest possible speed is fast enough and using multiple cores at top speed doing more work eats substantially more of your battery. Or if you have n cores and n or more independent tasks, then doing each task with the minimal amount of work is better.

Then you have effects where using multiple cores means communication between them takes longer. Then you have effects when your cores are not all the same. Or virtual cores where you can either use one core at 100% speed or two cores at 60% speed each. Your cores may have one route to memory only, so eight cores can do 8 times more computations but cannot read/write 8 times more data. Then you can have the effect that multiple cores fully used produce more heat, making the processor to hot and force it to slow down.

It's difficult and complicated.
> 0 votes

---
Tags: computer-architecture, parallel-computing
---


# Question
Title: Algorithm to distribute group of connected nodes in a graph
Given something similar to this.

Where you have **blocks** (the squares) and **entries** (the circles). Each block has a rating (the number inside the blocks) and is connected to other blocks. This topology is always fixed and **cannot** change, the ratings neither.

An entry can ask for a given rating. The algorithm then should try to assign N connected blocks to that entry so the rating provided is above or as close as possible to what the entry requires. It needs to be considered that the block to which the entry is 'conected' will always be asigned to him. An example:

We have two entries requiring a limit (green and blue entry). Green requires 300, and he receives 300 (3 blocks of 100 assigned to him), while blue asks for 275 and receives 250 (125+75+25). This solution is the optimal one; deviations are of all entries are minimized. Green has |1-(300/300)|=0 and blue |1-(250/275)|=0.09.

Mind that the third entry is not active, so his 'entry block' can be used by another entry group of asigned blocks. If we activate the third entry and require 200 as follows.

Note that the optimum solution changes. Green cannot use the 'entry block' from orange (as orange is connected).

The algorithm should assign to each entry the best possible connected path, **taking into account the other paths too**. And the best path is the one with a value (sum of blocks) equal, above or closest to the entry desired value.

The algorithm should output the solution that minimizes the deviation `|1-(recived/required)|` in each entry. In other words, the blocks assigned to each entry such that the rating received per entry is the closest to the desired value (for all the entries combined).

```
minimize: |1-(recived_1/required_1)| + |1-(recived_2/required_2)| + ...

```
* What could be an algorithm to solve such a problem. I am quite sure it involves linear/constraint programming. But I cannot see a clear way of doing it.

**Edit**: Context of question: Circles are EV charge stations, the squares are energy blocks connect between each other. When a car is connected to a station, the car requires some energy to charge (in the diagram, they ask for 300kW, 250kW and 200kW), and the blocks have ratings of 125kW, 100kW, 100kW, ... The algorithm has to say which group of power blocks go to which station. Aiming at satisfing as much as possible every car (i.e. kW provided by the sum of blocks is closest to how much kW the car wants, i.e the value in the circles in the diagram).

In real life, each edge has a contactor, it is either opened or closed to drive the energy of the blocks to the stations (but this can be ignored, knowing which blocks go to which station is enough). The doted line is the acces connection of the station to the networks of blocks. If the station has a car charging, the block to which the station is conected (doted line) will always be closed (i.e. that block assigned to him). This way every station when active has at least one block asigned so the car can charge.

# Answer
I think the problem might be $\mathsf{NP}$-difficult. Consider the decision version:

> Input: an undirected graph $G = (V, E)$, a value function $f:V\to \mathbb{N}$, a subset $E = \\{e\_1, …, e\_m\\} \subseteq V$ of entries, vertices of degree $1$ and a rational $q$.
>
> Question: does there exists $m$ disjoint paths $p\_1,…,p\_m$, each $p\_i$ starting in $e\_i$, such that $\sum\limits\_{i=1}^n\left|1-\frac{f(e\_i)}{f(p\_i-e\_i)}\right|\leqslant q$, where $f(p\_i-e\_i) = \sum\limits\_{\substack{v\in p\_i\\v\neq e\_i}}f(v)$?

Here is a reduction from $\texttt{Hamiltonian Undirected Path}$. Consider an undirected graph $G = (V, E)$. Construct a graph $G' = (V', E')$ where:

* $V' = V\cup \\{e, b\\}$ (add one block and one entry);
* $E' = E \cup \\{\\{e, b\\}\\} \cup \\{\\{b, v\\}\mid v\in V\\}$ (add one edge between the block and each other vertex, entry included).

Define $f$ such that $f(v) = 1$ if $v\in V$, $f(b) = 0$ and $f(e) = |V|$. Define $E = \\{e\\}$ and $q = 0$.

Then there exists a Hamiltonian path in $G$ if and only if $(G', f, E, q)$ is a positive instance of the problem. The idea is that to create a path of sum $f(e)$, there needs to exist a path crossing each vertex once.

For this reason, your problem is difficult to solve (though I do not know about approximations).
> 0 votes

---
Tags: algorithms, graphs, optimization, linear-programming
---


# Question
Title: Some questions regarding asymptotic notation of ${n \choose k}$
Is it always the case that ${n \choose k} = O(n^k)$?

If it is, then why does the comment from Clement C. in this post state it is only the case when $k$ is a constant?

If it is not, then why is the asymptotic time complexity of the brute force algorithm for the Clique decision problem denoted as ${n \choose k}O(k^2)O(1) = O(n^kk^2)$ even though $k$ may not be a constant?

Also, supposing ${n \choose k} = O(n^k)$, wouldn't it be more precise to state ${n \choose k} = O(n^{\min(k, n-k)})$?

# Answer
It is always true that $\binom{n}{k} =\mathcal{O}(n^k)$, even if $k$ depends on $n$.

As a proof:

$$\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{(n-k+1)(n-k+2)…(n-1)n}{k!}\leqslant \frac{n^k}{k!}\leqslant n^k$$

Since the complexity of the algorithm you talk of is an upper bound, the majoration is correct.

What is wrong, however, is that $\binom{n}{k} = \Theta(n^k)$, when $k$ depends on $n$ (meaning that $n^k$ is not necessarily a lower bound).

For example, $\binom{2n}{n} \sim \frac{4^n}{\sqrt{n\pi}}$ (see here) is not a $\Theta((2n)^n)$.
> 4 votes

# Answer
In terms of $n$, $$\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k!}$$ is indeed a polynomial in $n$ of degree $k$ (and not of degree $\min(k,n-k)$).

In terms of $k$ (and constant $n$), there is no asymptotic expression as $k\le n$ is required.

If both parameters are variable, the expression is complicated:

$$\Theta\left(\frac{\sqrt{\dfrac n{k(n-k)}}}{\left(\frac kn\right)^k\left(1-\frac kn\right)^{n-k}}\right).$$

---

A post stating that the brute force algorithm takes time $O(n^kk^2)$ would be misleading because either $k$ is fixed and the asymptotic complexity is just $O(n^k)$, or $k$ is variable and the complexity depends on the above factor.
> 0 votes

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


# Question
Title: Reduction of the diagonalization language to the universal language
I'm going through Jeffrey D. Ullman's Introduction to Automata Theory, Languages, and Computations. The author reduces an instance of the membership problem in $L\_d$ (diagonalization language) to a membership problem in $L\_u$. Those are defined as follow:

> $L\_d = \\{\langle M\rangle \mid \langle M\rangle \notin L(M)\\}$
>
> $L\_u = \\{\langle M, u\rangle \mid u \in L(M)\\}$

We start off with assuming $L\_u$ is recursive, reduce the problem in $L\_d$ to a problem in $L\_u$, and solve $L\_d$ using the assumption that $L\_u$ is recursive, now since $L\_d$ is not even recursively enumerable, our assumption that $L\_u$ is recursive turns out to be wrong, and since $L\_u$ has a TM which accepts it, we conclude $L\_u$ is a RE but not recursive language. A few pages later, the books says:

**Theorem 9.7**: If there is a reduction from $P\_1$ to $P\_2$ then

a) If $P\_1$ is undecidable then so is $P\_2$

b) If $P\_1$ is non RE then so is $P\_2$

I'm confused about the part b) of this theorem, it says reducing a non RE problem to another problem gives you a non RE problem, but having reduced an instance of $L\_d$ to an instance of $L\_u$, we have reduced a non RE problem to a RE but not recursive problem.

# Answer
> 1 votes
If you look closely at the proof to show that $L\_u$ is not recursive, the autor is using a reduction to $\overline{L\_u}$ (which is not RE), not to $L\_u$, and explain that a reduction to $L\_u$ cannot work since $L\_u$ is RE.

# Answer
> 0 votes
$L\_d$ is general reducible to $L\_u$ but not map reducible to $L\_u$. To show a language is not decidable, use general reduction is good enough. To show a language is RE or non-RE, you need to apply map reduction. In general reduction, $A\leq \bar{A}, A\leq B \Rightarrow A\leq \bar{B}, etc.$ However, in map reduction, $A\leq\_m B \Rightarrow \bar{A}\leq\_m \bar{B}$ only. In Jeffrey's book, the above two reductions are not clearly distinguished. His reduction after Theorem 9.7 means map reduction.

---
Tags: turing-machines, computability, reductions, undecidability
---


title: Layout algorithm for resource timings

text:
# Question
Title: Layout algorithm for resource timings
I'm trying to come up with a performant layout algorithm for web resources timings. For now, all that is relevant is that resource timings include a `startTime` timestamp and a `duration` and the goal of this layout algorithm is to assign each resource timing to a lane. A resource timing cannot be assigned to a lane if it overlaps another resource timing.

The goal of this layout algorithm is to:

1. minimize the number of lanes created (primary objective)
2. minimize the gaps between resource timings (secondary objective to break ties)

Informally, I'm looking to create an aesthetically pleasing rendering of all the resource timings but I want it to be determinate and use the output for other stats like the number of tracks and the highest count of timings within a track.

I've tried a few brute force ideas but I'm having trouble creating something performant. I'm thinking there's probably a clever way to frame this as a DP problem but I'm not seeing it

**Edit:** I'm also trying to render these timings and lanes on a screen so I don't just need the number of lanes, I need where the timings should go as well.

---

Edit: Illustrations

Here is drawing of a set of resource timings. Each box represents a resource timing. The position from the left represents the start time and length of each box represents the duration.

I'm trying to write a layout algorithm that assigns each resource timing to a "lane". That…

…minimizes the number of lanes needed

…and minimizes the gaps between resource timings

Note that the last example is a better layout because it removes a gap.

# Answer
> 1 votes
While this problem can be represented as interval graphs, it is not necessary to solve it. Moreover, an efficient algorithm to solve the problem directly on interval graphs is LexBFS, but it is quite hard to implement. Of course, it is simpler if you already know the corresponding intervals set, but in this case, working directly on intervals without graph is simpler in my opinion.

A greedy algorithm to solve it can be described as follow:

* creating a list of events, corresponding to the beginning or the end of a task. An event is a triple `(time, task, type)`;
* computing the number of necessary lanes;
* assigning lanes to tasks.

```
Input: list [(s1, d1), (s2, d2), …, (sn, dn)]
       containing couples (starting time, duration).
Output: mapping f : {1, …, n} to {1, …, m}, m being
        the necessary number of lanes

//Creating a list of events
events ← empty list
for i = 1 to n do
    add (si, i, true) to events
    add (si + di, i, false) to events
sort events by increasing order of first component

//Computing the necessary number of lanes
lane ← 0
m ← 0
for (time, i, type) in events do
    if type then
       lane ← lane + 1
       m ← max(m, lane)
    else
       lane ← lane - 1

//Assigning lanes to tasks
available ← min-heap containing all values {1, …, m}
for (time, i, type) in events do
    if type then
       lane ← extract_min(available)
       f(i) ← lane
    else
       insert(available, f(i))
return f

```

Since we use a priority queue to find the minimal available lane, and $m\leqslant n$, the algorithm is overall $\mathcal{O}(n\log n)$. I think it also satisfies the second constraint, since you always try to assign the smallest lane when possible.

# Answer
> 1 votes
The problem of minimizing the number of lanes is the problem of graph coloring (with the fewest number of colors) of an interval graph, namely, the graph with one vertex per resource timing and an edge between each pair of resource timings whose times overlap. Wikipedia says you can find such a graph coloring in linear time using "a greedy coloring algorithm that colors the intervals in sorted order by their left endpoints". Then, you should be able to use binary search on the number of colors, to find the minimal number of lanes needed.

---
Tags: algorithms
---


# Question
Title: How do I prove correctness of my algorithm that finds a pair of integers in an array that have a sum of 0?
I have designed an algorithm (up to making a pseudocode) that accepts a sorted array as input and finds in $O(n)$ time if there's a pair of elements (integers) in the array that have a sum zero.

What my algorithm basically does is:

1. set index $i$ = 0
2. set index $j$ = length(array) - 1
3. while $i\<j$ : if $a\[i\]+a\[j\]=0$ then it returns the pair, if $a\[i\]+a\[j\]\<0$ it does $i++$ and if $a\[i\]+a\[j\]\>0$ it does $j--$.
4. if at some point $i=j$ it stops and returns that the pair was not found.

I read that when making an algorithm you need to prove its correctness, but the methods that I've read don't seem fitting to me. I can't think how to use induction - for example - past the "assume it works for $n=m$" because I feel like I'd be explaining how the algorithm works again.

Can someone indicate how I can prove the correctness?

# Answer
> -1 votes
You can prove this property using a loop invariant. Naming the array $a$ and $n = |a|$, consider the following property $(P)$:

> There exist $(k,\ell)\in \\{0, …, n-1\\}, k\neq \ell$, such that $a\[k\] + a\[\ell\] = 0$ if and only if There exist $(k,\ell)\in \\{i, …, j\\}, k\neq \ell$, such that $a\[k\] + a\[\ell\] = 0$

Meaning that the two indices you are searching for are necessarily between $i$ and $j$ (included).

Then, the property $(P)$ is a loop invariant of your algorithm:

* it is trivially true before the loop;
* it stays true at each step of the loop, considering all three cases (proof left to you).

Now, you can use this loop invariant to prove the correctness of your algorithm.

---
Tags: algorithms, search-algorithms, correctness-proof, search, program-correctness
---


# Question
Title: What is the minimum and maximum value of Counter when the two threads are executed concurrently?
I'm studying for an exam and have run into a problem that I do not understand. The main program starts two threads that execute the following program concurrently, whenever both threads terminate the program will print the result of counter. I am assuming that the maximum value of counter will be 10? But what will the minimum value be? 1?

The following image shows the pseudocode for the program.

# Answer
> 1 votes
First of all, lets clarify the functional difference between

```
i = i+1

```

and

```
cnt = counter
counter = cnt+1

```

There is none! Both segments must first read a value from global memory into a register, operate on/with said register and write the result back to global memory. So both execute three instructions; a **read**, an **add**, and a **write**.

With that said, the rest of the problem is an exercise of arranging blocks in a way that one thread "undoes" the work of the other, either for `i` or for `counter`.

For the **minimum** value of `counter`, see the execution flow below. The grey box represents a single iteration of the loop. The value of `counter`, after both threads finish, will be **1**.

For the **maximum** value of `coutner`, see the execution flow below. Again, the grey boxes represent a single iteration of the loops. If all iterations are executed with the alignment shown, at the end, `counter` will be **20**.

# Answer
> 1 votes
While I was initialy convinced by the two previous answers, a colleague of mine showed me the light about this exercise.

He claims that the maximum value of the counter is $65$, not $20$.

As proof, consider the following execution :

* Thread $t$ reads $i = 0$; `counter = 0`
* Thread $u$ executes $10$ loops in total; `counter = 10`
* Thread $t$ writes $i = 1$;
* Thread $u$ enters the loop and reads $i = 1$;
* Thread $t$ executes $10$ loops in total; `counter = 20`
* Thread $u$ writes $i = 2$;
* Thread $t$ enters the loop and reads $i = 2$;
* Thread $u$ executes $9$ loops in total; `counter = 29`
* Thread $t$ writes $i = 3$;
*
* Thread $t$ writes $i = 9$;
* Thread $u$ enters the loop and reads $i = 9$;
* Thread $t$ executes $2$ loops in total; `counter = 64`
* Thread $u$ writes $i = 10$;
* Thread $u$ finishes the loop; `counter = 65`
* Both tests $i \< 10$ are false and both threads exit.

The value $65$ is $10 +10 + 9 + 8 + … + 2 +1$.

# Answer
> 0 votes
The minimum cannot be $0$, because $\text{cnt}\ge0$, and some assignment $\text{counter}=\text{cnt}+1$ will inevitably be performed.

But the minimum can be $1$, as follows:

* the left process executes with $i=0$, until the assignment $\text{cnt = counter;}$ (hence $\text{i}==1$ and $\text{cnt}==0$).
* the right process executes all iterations with $i= 1, \cdots9$ and exits.
* the left process finishes processing and performs the assigment $\text{counter = 0 + 1;}$ and terminates.

Then, unless the incrementation of $i$ is done atomically, the maximum is $20$, as follows:

* both processes execute the $\text{while}$ test and the RHS of the assignment $\cdots=\text i+1$.
* both processes perform the LHS of the assignment, $\text i=\cdots$.
* both processes execute the rest of the loop without overlap.

This way, both loops run $10$ times, for a total of $20$.

If the incrementation is atomic, the maximum is $10$.

---
Tags: concurrency, threads
---


# Question
Title: How to reduce universal language to language of all turing machines that deduce all palindromes?
Let $S$ be language $$\\{\langle M\rangle \mid(\forall x \in \Sigma^\*)\[x \in L(M) \iff x^R \in L(M)\]\\}.$$

How can I show that $L\_U \le\_m S$ and $L\_U \le\_m \bar S$ where $L\_U$ is universal language and $\le\_m$ means it is m-reducible (or simply reducible)? Can it be done via Rice's theorem?

# Answer
#### Show $L\_U \le\_m S$

Let $v=\langle T, w\rangle$, where $T$ is a Turing machine and $w$ is an input string to $T$. Fix two different input symbols $a$ and $b$. Construct Turing machine $M\_v$ that upon input $x$, check whether $x$ is $aww^Rb$.

* If it is, accept.
* Otherwise, check whether $x$ is $bww^Ra$.
    + If it is, simulate $T$ upon input $w$.
    + Otherwise, accept.

It is straightforward to check that $v\in L\_U$ $\iff$ $\langle M\_v\rangle\in S$. The construction from $v$ to $M\_v$ is computable. Hence $L\_U \le\_m S$

#### Show $L\_U \le\_m \bar S$

Let $v=\langle T, w\rangle$, where $T$ is a Turing machine and $w$ is an input string to $T$. Fix two different input symbols $a$ and $b$. Construct Turing machine $M\_v$ that upon input $x$, check whether $x$ is $aww^Rb$.

* If it is, loop forever.
* Otherwise, check whether $x$ is $bww^Ra$.
    + If it is, simulate $T$ upon input $w$.
    + Otherwise, accept.

It is straightforward to check that $v\in L\_U$ $\iff$ $\langle M\_v\rangle\in \bar S$. The construction from $v$ to $M\_v$ is computable. Hence $L\_U \le\_m \bar S$
> 1 votes

---
Tags: turing-machines, reductions
---


# Question
Title: System Identification vs Machine Learning for dynamic system modelling
So I found another discussion regarding this, but the answers did not fully separate the differenced between SID and ML. Hopefully a discussion here can shed some light on some larger differences both in design and use case situations between the two.

SID and ML seem very similar. They both use known input and output data to identify a model from the data. A few things I notice that set them apart (and correct me if I'm wrong):

1. Structure - SID has a given model structure according to the input parameters, while ML models don't necessarily have a structure like this.
2. A machine learning model will predict values accurately (according to the model training) where input data is within a range of the training data. Input data points entering outside the training data range won't necessarily produce the correct output, if the system's dynamics are different outside the training data set values. On the other hand, a sub-space identification model with an optimal estimator like Kalman filter, would capture any changes in the model's dynamics on-the-go.
3. SID is more specific in it's use case, where the aim is to identify dynamic models from data. ML covers a wider range of use case (regression and classification).

Feel free to add more points if I missed something. So for it's domain specific use in process control, SID methods excel by being computationally lightweight. But if we look away from process control as a domain, and look at other use cases for SID - such as economics, finance, and other empirical modelling domains: is there a clear distinction between SID and ML, and situations where one would be preffered over the other?

Does SID + Kalman filter capture (and predict) the behavior of Dynamic systems and latent variables better? Or has the ML field advanced past the performance of SID in these cases? What are some situations where SID methods would be preffered over ML models, outside of process control?

# Answer
At a high level, conceptually, they are very similar.

When one gets into the details, they come from different communities and were initially designed to solve different tasks, so there are many differences in the specifics.

One difference is that system identification is often most concerned with the particular model (the relationship between input and output), whereas machine learning is often most concerned with making accurate predictions and the model is only a means to an end. Also, system identification is often focused on systems where there is a relatively simple relationship between the input and output, because of the domains where it has typically been used. Also, a very important difference is that system identification is usually focused on stateful systems, whereas machine learning is focused on learning an input-output relationship that is stateless. In system identification, we often have a strong prior on what kinds of relationships are plausible (e.g., because we are dealing with a physical system, that is subject to the laws of physics).
> 1 votes

---
Tags: machine-learning, modelling
---


title: MAX-SAT approximation factor

text:
# Question
Title: MAX-SAT approximation factor
I am stuck on an exercise that ask the approximation factor of a MAX-SAT approximated algorithm generalized from a MAX-3SAT algorithm

MAX-3SAT:

1. set every variable with a random value ($0$ or $1$ each with probability $\frac12$)
2. check how many clauses are satisfied

This algorithm has a $\frac78$-approximation factor since:

* to get all $3$ variable to false we have a $\frac1{2^3}$ probability
* to get all $3$ variable true we have a $1 - \frac1{2^3}$ probability (since a clause to be satisfied need at least 1 variable true)

Now I am confused about the generalization to MAX-SAT Since we have N variables i'm inclined towards a $\left(1 - \frac1{2^N}\right)$-approximation factor since

* to satisfy the clauses we have a $\frac1{2^N}$ probability
* to negate the clauses we have a $1 - \frac1{2^N}$ probability

However, I'm not sure about that since in a SAT problem there is no guarantee that all clauses will have exactly $N$ variables since $N$ here represent only an upper bound on the number of variable per clause.

# Answer
> 0 votes
You are right in your analysis: this algorithm has a $\left(1-\frac{1}{2^N}\right)$ approximation factor only when each clause has at least $N$ independant litterals (independant means on different variables).

In the general case, you could have some clauses with exactly one litteral. But that means that the approximation factor is at least expected to be $\frac12$. However, since the algorithm is randomized, it cannot guarantee to get at least half of the clauses to be satisfied.

One interesting fact is that this algorithm can be derandomized to guarantee a $\geqslant \frac12$ approximation factor (the idea is to choose each assignation of a variable to maximize the expected approximation factor).

---
Tags: satisfiability, approximation, decision-problem, 3-sat, maxsat
---


# Question
Title: Is returning pointers to nodes for a list (doubly linked list) implementation a leaky abstraction? and is it bad?
I've been studying closely about the **List** abstract data type - As I understand it can be implemented with linked-list and/or arrays, and really maybe with any other data types as well.

But to satisfy a list, it means to have methods:

1. that allow for insertion at desire 'position'.
2. removal at desired 'position'.
3. access data at nth position.
4. prepend on the list
5. append on the list
6. size
7. empty check.
8. search by value. (necessary or not?)
9. delete at end (necessary or not?)
10. delete at front (necessary or not?)

(note: different sources seem to omit some or have additional ones - makes it extra frustrating without some standardization of what is core except assumptions)

I primarily use javascript. What I've noticed is a lot of JS implementation uses front-back nodes for doubly-linked lists to implement List ADT. Their implementation of removal/insertion is done by passing an index. Then iterate with for-loop to get to the that target node. This perplexes me, because it does not use the best features of linked lists, which is getting delete/insertion @ front, back, middle at O(1) given the pointers/reference. For middle, couldn't this be done with Javascript returning that Node Object? Then again I suppose, computational complexity isn't part of the requirement to satisfy an ADT (arguable at least).

To compare against Javascript, I looked at C++ and Java implementations. They have implementation such that it return a **pointer** when they **search** by nth item or by value. this pointer can be reused later to pass down on removal/insertion methods, making for-loop iterations not necessary, in other words O(n) =\> O(1). Surely this is better implementation maybe? again, its beyond just satisfying an ADT's requirement.

However, this all brings the title of the question. Is the pointer actually more preferred or it is actually more of an leaky abstraction and maybe should be discouraged? Javascript's common implementation leading to O(n) doesn't leak any implementation details by always returning value than the reference to Node object.

If I have to answer, maybe it makes sense for Javascript to use the O(n), because its such a high level language - it won't reap more benefit than all the optimization its done under the hood for its applications. Whereas lower language like C++ or Java covers more spaces where application of O(1) matters much more than a bit of leaky abstraction.

Additionally for practice/interviews, these are things I could point out in words.

---

Sources:

Javascript Implementation: https://www.tutorialspoint.com/The-Doubly-Linked-List-class-in-Javascript

Java Implementation: https://brilliant.org/wiki/linked-lists/

C++ Implementation (last couple pages): https://math.hws.edu/eck/cs327\_s04/chapter2.pdf

# Answer
> 1 votes
Returning a pointer is not leaky, and is generally prefered, as it always permits more operations: access to the corresponding value, insertion at position and deletion in $\mathcal{O}(1)$.

Considering that a linear complexity is ok because the language is higher level is also wrong: lower complexity is better (unless the leading constant increases, but that is not the case here).

What could change between high level language and low level language is garbage collection and handling memory allocation of dereferenced pointers. However, not returning a pointer will not magically handle memory liberation for you.

My guess (I could not see the implementation for research) is that the tutorial is just that: a tutorial. It does not aim to create a super efficient data structure (which linked lists are not, it is often prefered when possible to use arrays in C or C++) but to teach elementary data structures.

---
Tags: algorithms, complexity-theory, data-structures, linked-lists
---


# Question
Title: Can an unconnected graph contain a euler trail?
Looking online I found two different definitions for euler trail. I am wondering if one of them just implicitly assumed what the other definition explicitly stated or whether one is not generally accepted and if so which the general accepted one is:

**All edges exactly once, all vertices at least once**

Source: https://www.tutorialspoint.com/graph\_theory/graph\_theory\_traversability.htm

Following this definition an unconnected graph never contains an euler trail.

**All edges exactly once**

Source: https://en.wikipedia.org/wiki/Eulerian\_path

Following this definition an unconnected graph can contain an euler trail if a sub-graph is connected and all nodes that aren't part of the sub-graph have no edges.

If you have a solid source (preferably a book), please share it.

# Answer
> 1 votes
The definition I often use is the second one: a disconnected graph could contain an euler path.

However, that does not mean that the first definition is wrong.

Unfortunately, Computer Science is a young field (in comparison to maths/physics/other sciences), and its vocabulary is still not well defined. The same name can be described for different (though similar) notions.

In my opinion, the worst examples are often found on trees, where "complete" or "perfect" can designate different kind of trees, where the height can begin at $0$ or $1$ for the empty tree, etc.

What is important is to clearly define used notions so that this kind of ambiguity is cleared.

As for sources, the second definition coincides with the one found in Bondy and Murty (Graph Theory); Jungnickel (Graphs, Networks and Algorithms) and Erickson (Algorithms) agree with this definition; CLRS (Cormen et al., Introduction to Algorithms) defines an Euler **tour** only for directed strongly connected graph.

---
Tags: graphs
---


# Question
Title: What is the relationship between virtual address and physical address?
I am recently studying the operating system, and I found the paging system a little bit confusing, for example, what will happen when there is a 52-bit virtual address and a 40-bit physical address, with 4KiB page size, so there are 2^40 pages and 2^28 frames, how pages are mapped in this case (the pages are more than frames) and how would the page table look like? Any help would be appreciated.

# Answer
> 2 votes
Physical addresses refer to existing RAM memory. At any time, virtual pages can be mapped to physical pages (frames), or be swapped out on disk. Usually, just a subset of the virtual space is mapped (the rest being completely ignored by the process). That part is mapped to frames as long as they are available (possibly in competition with other processes). The rest is mapped to disk.

The mapping being quite dynamic, there is no particular relation between the virtual and physical addresses, and even less between their sizes. In theory, a single frame of RAM could be enough.

---
Tags: operating-systems, memory-management, virtual-memory, paging
---


# Question
Title: Big O analysis of a sorting algorithm that counts smaller elements
How do I prove the runtime of an algorithm with Big O notation? I don't know much about O notation, I just I know how to compare sets of functions with each other and I'm also familiar with the master theorem.

But how do I do this? Is it just $O(n^2)$ because there are $2$ loops? That doesn't sound right. The loop in COUNTSMALLER doesn't have else so it's less expensive than the other one. I just know that cnt \<- 0 is $O(1)$ but I don't know exactly about the loops. Am I supposed to do something with $T(n) = a T(n/b) + f(n)$? I could do that if you give me $a$ and $b$ but I have to idea how to get those or if this even makes sense.

This algorithm doesn't terminate if some elements are equal btw, I guess we can assume that all elements in the array $A$ are unique.

SORT(A)
1 i <- 1
2 while i < len(A) do
3    j <- COUNTSMALLER(i, A) + 1
4    if i = j then
5       i <- i + 1
6    else
7       A[i] <-> A[j]
8    end if
9 end while

COUNTSMALLER(i, A)
1 cnt <- 0
2 for j <- 1 to len(A) do
3    if A[i] > A[j] then
4      cnt <- cnt + 1
5    end if
6 end for
7 return cnt

```

# Answer
The big-$O$ analysis of an algorithm consists of two part in practice.

* A quick and rough estimate, which works often.
* Rigorous analysis as well as refinement when necessary.

---

We assume that the algorithm works. That means on any valid input (i.e., no duplicate numbers), it returns the correct result in finite time.

As a first guess, the time-complexity is probably $O(n^2)$ since there is a nested loop, where each loop seems contributing a factor of $n$.

---

Now let us take a closer look.

It takes $O(n)$ time to run `COUNTSMALLER(i, A)`.
So, it takes $O(n)$ time to run line 3 to line 8, the loop body of the while loop in `SORT(A)` once.

Now the question is how many times will that loop body be run? Each time the loop body is run, either $i$ will increase by $1$ or one more position of the `A` stores the expected value. Since $i$ can increase at most $n$ times and there are $n$ position in `A`, the loop body runs at most $2n$ times. Hence it takes $O(n\times n) = O(n^2)$ to run the while loop in `SORT(A)`.

It takes less time comparatively to run all other code such as line $1$. Hence the time-complexity is $O(n^2)$.
> 1 votes

---
Tags: algorithms, time-complexity, algorithm-analysis, loops
---


title: Information sharing in group

text:
# Question
Title: Information sharing in group
I have a group with n members. These are distributed members. It is basically a group chat. A new member is added to the group and the existing members are informed about this.

Now I want the new member to obtain some information about the group that the existing members all know. This could be the name of the group. There is no centralised place where this information can be obtained. Also, messages sent in the group will go to every member of the group.

My current implementation is that all the existing members send the information to the new member, but this is causing everyone to receive many messages. I would like the number of messages to be as low as possible, which I guess would mean that one message should be enough.

I cannot just make the member with the lowest ID be the one to send the message, as that person might not be online.

So, is this problem, a problem with a known solution? And what might that be?

I hope the explanation makes sense.

# Answer
Let's say that the expected time a message takes in transit is $t$, and typically $ t \leq 100\\;\text{ms}$.

Your group has $n$ members. When a new member enters the group, each existing member draws an integer $w\_i$ at random from $\[1, q \cdot n\]$ for some $q \geq 1$. Then each member waits for $t \cdot w\_i \\; \text{ms}$. If no message has been sent to the group, then that member sends a message.

According to the answer by Raskolnikov on maths.sx, the probability that more than one member will be chosen to send a message is $$ 1- \frac{1}{ q (e^{1/q} - 1) }, $$ which interestingly does not depend on $n$.

If you choose $q$ to be large (e.g. 100), then the probability that two members will be chosen to send the message is very small (\<0.5%), but the waiting time will be larger. If you choose $q$ to be small (e.g. 5), the probability will be larger, but still less than 10%, and the waiting time will be much smaller.

Ps., compute the probability of a collision using

```
def prob_coll(q):
    return 1 - (1 / (q * (math.e ** (1 / q) - 1)))

```
> 2 votes

---
Tags: algorithms, distributed-systems
---


# Question
Title: How can we get small test error reducing only train error?
My question is about mathematical part of machine learning algorithms, especially about using it in neural networks. We train network reducing train error and I was thinking about how then test error is also small (discarding overfitting and underfitting), what is mathematical proof for it. I found about that in this book http://www.deeplearningbook.org, chapter 5.2. Here is a part of that chapter:

> How can we affect performance on the test set when we can observe only the training set? The field of statistical learning theory provides some answers. If the training and the test set are collected arbitrarily, there is indeed little we can do. If we are allowed to make some assumptions about how the training and test set are collected, then we can make some progress. The training and test data are generated by a probability distribution over datasets called the data-generating process. We typically make a set of assumptions known collectively as the i.i.d. assumptions. These assumptions are that the examples in each dataset are independent from each other, and that the training set and test set are identically distributed, drawn from the same probability distribution as each other. This assumption enables us to describe the data-generating process with a probability distribution over a single example. The same distribution is then used to generate every train example and every test example.

I want to transfer this theoretical part to a more concrete example for better understanding. Assume we have images and we need to select train and test datasets. My questions are

1. What the author means by "example"? Is it every image? If yes, is that mean, that we consider every image as a random variable and every time it selected or not?
2. I totally can't understand why we need to do this assumption: *"the examples in each dataset are independent from each other"*. Maybe I misunderstood the example part in my first question and it's come from that.
3. If the training set and test set are identically distributed why always in practice the training set is about 90% of all data and the test set is 10%, I can't see identical distribution in this situation.

Also, I would be glad if you will give me some references to read about this in other books/topics.

# Answer
Well, I have to say that the question is rather complicated. I also spent considerable time investigating this issue. Other SE questions (see here, here and here) are strongly related to this one and specially this answer is very enlightening but, at least for me, not completely satisfactory. Also bare in mind that I am an ANN expert, not a statistician. So, here goes my attempt:

What we really want when we train a learning algorithm is that it can generalize well, that means, being able to perform well in unseen examples. The problem is that we have a finite set of collected examples, e.g., pictures where cats or dogs can be present. So, we have here a contradiction, if we want to assess generalization we need **unseen examples**, but we have only *seen examples*, namely, the ones we collected. The solution to this contradiction is that we cannot assess generalization, period. But maybe we insist that we do want to assess generalization because we can split the examples we collected in seen examples (we will call these **training set**) and unseen examples (we will call these *test set*). Now the problem became (hopefully) more concrete, and the question is:

**How do we split the examples, such as the training set can be *a good simulation* of the seen examples and the test set can be *a good simulation* of the unseen examples?**

At this point, we can start answering your concrete questions. The easiest is

1. > What the author means by "example"? Is it every image? If yes, is that mean, that we consider every image as a random variable and every time it selected or not?

Answer: Yes, every example, that is, every image is a random variable (RV). In my favorite AI book (AIMA), page 708, first paragraph, says exactly that: "Each example data point (before we see it) is a random variable". The same book explains intuitively what a RV is, so we can check if every cat/dog image is indeed a random variable. Let us see: a RV has a domain (the set of possible values it can take on), the domain of the RV example 1, $X^{(1)}$ is $\\{cat, dog\\}$ and so is the domain of every other example $X^{(i)}$.

Now that we know that we are dealing with random variables, we can continue with our discussion. Let us say we split randomly the collected examples in train and test set. Is the test set that we obtain a good simulation of unseen examples? Not with certainty. For example, let us say our collected examples are mostly images of our cat and one image of the neigbor's dog, i.e, $\\{cat, cat, cat, dog, cat\\}$ and we obtain (because we had really bad luck) a training set $\\{cat, cat, cat, cat\\}$ and a test set $\\{dog\\}$. Obviouly, our learning algorithm will generalize terribly bad: for all instances will predict the wrong class. So, we need more assumptions if we want to have some guaranties.

This is the point where the independence and identically distributed (i.i.d.) come in play. Rather than explaining what that means, I will image scenarios where these assumptions are violated and see what happens. This will help us to answer your second question.

**Scenario 1:** The examples in the dataset are not mutually independent. That means there are at least two examples that are mutually dependent. We can use here the same argument as above to dissection this scenario:

After splitting, the train set contains the two related examples, but in the test set all other examples are not related to eachother. We do not want this because the test set is not a very good simulation of the unseen examples.

After splitting, the test set contains the two related examples, but in the train set all other examples are not related to each other. We do not want this because the train set is not a very good simulation of the seen examples. Note that a good simulation of the seen examples would be a set that includes some degree (if not the exactly) of relation between the related examples.

Therefore, the only way we can be sure that the split produces the best seen/unseen split is assuming that all examples are independent of each other. That way, we know that no matter how we split our collected examples, we will always have a *perfect* method to assess generalization.

The above, I think, answers your questions:

> How can we get small test error reducing only train error?
>
> 2. I totally can't understand why we need to do this assumption: "the examples in each dataset are independent of each other". Maybe I misunderstood the example part in my first question and it's come from that.

We HOPE that we can get small test error by reducing the train error because we HOPE (actually is our goal) that the algorithm is going to generalize well, and we ASSUME that our examples are independent of each other, so we HOPE that, if we reduce the training error, the test error will be reduced as well, since we have ruled out with our independence assumption, a source of error from both sets.

So let us continue with of your third question:

> If the training set and test set are identically distributed why always in practice the training set is about 90% of all data and the test set is 10%, I can't see identical distribution in this situation.

Firstly, you have here a misconception (I have to say this is where my understanding starts to diminish, just like you). Not the train and test set are identically distributed, but again the examples in those sets. This completes the i.i.d. assumptions: the examples are identically distributed. This is extremely abstract.

Intuitively, this means that the collected examples must be of *similar nature*. In one of the answers I early mentioned, the example of students being tested in a class is given:

> The kids also need to be "identically distributed", so they cannot come from different countries, speak different languages, be in different ages since it will make it hard to interpret the results (maybe they did not understand the questions and answered randomly).

It appears to me that the matter has not been really grasped. Neither in the deep learning book, nor in AIMA or other probability/statistics books, we can find a *natural* explanation or treatment. But perhaps this could helps us:

Let us suppose we want to estimate the mean $\mu$ and variance $\sigma^2$ of a Gaussian distribution. Our collected examples are supposed to be drawn from this distribution $X^{(i)} \sim N(\mu, \sigma^2)$. Every example $X^{(i)}$ is distributed according to that specific distribution, that is, they are identically distributed. If we collect examples drawn from another normal with mean $\mu\_1$ and variance $\sigma^2\_1$ or from another distribution whatsoever, e.g, uniform distribution, **we will definitely have problems** when assessing generalization. So, we have to assume that our collected examples are indeed identically distributed.

Finally, the 10% and 90% has no theoretical background! The number 10 and 90 do not represent any distribution, it is just what all people do, most like a fashion. You can use 20%/80%, 30%/70% and even 40%/60%. Of course, intuition dictates that we should use most of the data we have to train and the rest to test. Following the example of the students, you want to teach the students most of the time and, eventually examine them, but not the other way around.
> 3 votes

# Answer
Yes, if you are classifying images, each example would be an image. There is some distribution on images that are likely to arise in practice.

We need independence and identical distributions because without it we can't learn. If we practice five times, but then are tested on something entirely different, our practice might not be useful.

The distribution refers to the distribution of each single image. That has nothing to do with how many images you draw from that distribution. Imagine flipping a biased coin. I could flip the coin 100 times; each outcome would be a sample from that (biased) distribution, and that's true whether we have 10 coin flips or 1000 coin flips.
> 0 votes

---
Tags: machine-learning, neural-networks, statistics
---


# Question
Title: Proof showing when Dijkstra’s algorithm fails for negative edge weights
How do I show the correctness proof of Dijkstra’s algorithm for negative edge weight $\textbf{indicating the point in the proof where it breaks or does not hold}?$

I tried proving it like this, but i know that i'm not correct.

1. Set $d\[s\] = 0$ (where $s$ is our source).
2. Set $d\[v\] = \infty$ for all $v \ne s$,$v \in V$.
3. Run some sequence of UPDATE$(u,v)$ procedures on the edges of $E$.

Let $SP(s,v)$ denote the length of the shortest path from $s$ to vertex $v$. If we execute steps 1, 2, and 3, then $d\[v\] \ge SP(s,v)$ at the end of the process (no matter what sequence we specify in step 3).

To argue why this claim is true, we will use a very similar strategy we used in the proof of correctness: Assume, for sake of contradiction, that $f$ is the first vertex to violate this property, i.e., at some point during the procedure $d\[f\] \< SP(s, f)$. Thus, there must have been some vertex $u$ such that we called UPDATE$(u, f)$, which resulted in $d\[u\] + w(u, f)$ being stored at $d\[f\]$ so that now $d\[f\] \< SP(s, f)$. But $f$ is the first violator of this property, and so it must be the case that $d\[u\] \ge SP(s,u)$ when this update is called. Combining these observations it follows that

$$d\[f\] = d\[u\]+ w(u,v) \quad \text{(since u caused the violating update)}$$

$$\ge SP(s,u)+ w(u, f) \quad \text{(since f is the first violator;}\quad d\[u\] \ge SP(s,u))$$

$$\ge SP(s, f).$$

To see why the last inequality is true, note that the shortest path from $s$ to $f$ has to travel through one of $f’s$ neighboring vertices (i.e., any vertex $v$ such that $(v, f) \in E)$. $u$ is a candidate for this vertex, and if it is the case that we travel through $u$ on the shortest path from $s$ to $f$, then the length of this path is exactly $SP(s,u)+ w(u, f)$. The only other case would be if there is some better path that uses a vertex other than $u$, but in this case we have that $SP(s, f) \< SP(s,u)+w(u, f)$, which proves the inequality.

Thus the last inequality show that $d\[f\] \ge SP(s, f)$, which contradicts the conditions we put on $f$ and therefore establishes our claim.

# Answer
> 1 votes
The proof is correct (modulo the typo I mentionned in the comment).

Why is that not a problem about Dijkstra's correctness for negative weights? Because what you proved is $d\[f\] \geqslant SP(s, f)$, not $d\[f\] = SP(s, f)$.

It is the inequality $SP(s, f)\geqslant d\[f\]$ at the end of the algorithm that fails with negative weights.

# Answer
> 0 votes
With the idea, I approached it as thus: An example below is used to show why Dijkstra's algorithm doesn't work in this case. The figure describes a directed graph that shows why Dijkstra’s algorithm does not work when the graph contains negative edges.

$\textbf{N.B:}$ The shaded vertices represent vertices that have been removed (dequeued) from the heap.\ In the proof of Dijkstra’s algorithm, the key property is that when a vertex $v$ is dequeued from the heap, its $d\[v\]$ value correctly stores the length of the shortest path from $s$ to $v$. Observe that in this example given in the graph, both $u$ and $w$ are violating this property, because both of these vertices have been removed from the heap, but we can attain shorter paths for both vertices by first travelling to $v$ and then taking the negative edge $(v,u)$. Even if we updated $d\[u\]$ to now be $1$ after dequeuing $v$ and calling UPDATE, $d\[w\]$ would still be incorrect.

$\textbf{Proof of failure with negative weights:}$ From lecture note 17 - "$\emph{Graph Algorithms}$", we could see that since both $y$ and $u$ were in $S$ when $u$ was chosen, so $f\[u\] \le f\[y\]$.

The two inequalities $f(u) \> d(s, u) \ge d(s, y)$ became equalities, $f\[y\] = d(s,y) = d(s,u) = f\[u\]$; So $f\[u\] = d(s,u)$ contradicts our hypothesis. Thus when each $u$ was inserted, $f\[u\] = d(s,u)$.

Hence the inequality $f(u) \> d(s, u) \ge d(s, y)$ fails if there is a negative weight because with negative weight introduced to the graph, $d(s, u)$ will not always be greater than $d(s, y)$, so Dijkstra’s algorithm fails here. Based on the proof by contradiction, there must be at least one more edge in the path after $y$, and the shortest path from $s$ to $y$ must be strictly smaller than the shortest path from $s$ to $u$. But with negative edge weight, this fails. So the inequality makes this contradiction invalid. QED

\[Image Credit: ece.mcmaster.ca\]

---
Tags: algorithms, graphs, dijkstras-algorithm
---


title: How to prove that it is NP-complete?

text:
# Question
Title: How to prove that it is NP-complete?
I was trying to do this exercise, but I don't know how to solve this problem is NP-complete, what reduction to do.

There is a network N of n people, in which every person i is associated with a subset of people Fi ⊆ N . For every i∈N, it holds that i∈Fi, and if person j is in Fi, then it must be that i is in Fj as well. Your goal is to advertise a product to every person in N. To do so, you need to choose a set of advertisers among N that will promote it, each will advertise it among his associates. Prove that the problem of finding whether there exists a set of size at most k of advertisers that can promote your product, is NP-Complete.

# Answer
This is exactly vertex cover.
> 0 votes

---
Tags: algorithms, np-complete, reductions, 3-sat
---


# Question
Title: Do Euler trails have to start and end at different vertices?
I am wondering whether every Euler graph is also traversable. I.e. are Euler circuits Euler paths, too? Therefore I am asking the question above.

I am explicitly asking "euler circuit ⇒ euler trail?".

# Answer
They are different. A walk is any sequence of vertices where every two consecutive vertices are connected via an edge. A trail is a walk where every edge is visited at most once. A circuit is a trail that starts and ends on the same vertex. A path is a trail where no vertex is visited twice and a cycle is a path that starts and ends on the same vertex.

So an Euler circuit is an Euler trail, but not necessarily vice versa.

Indeed, if your graph has two vertices with odd degree, it cannot have an Euler circuit, but it might have an Euler trail.
> 1 votes

---
Tags: graphs
---


# Question
Title: What is the associative operator ⊕ in graph matching? and How does it works?
I read a paper about Parallel Matching, and I didn't understand what the associative operator ⊕ in the following lemma/proof and how does it works in vertices and edges in the graph?

Lemma 3. Using our graph representation, each node v in the graph can apply an associative operator ⊕ to all edges incident on v in O(log|A|) time and O(|A|) work on the CREW PRAM model. Proof. First, we read for each entry (v,$e\_{k}$) ∈ A the value from E\[k\] on which to apply the operator. Next, we run segmented prefix sums with ⊕ operator on these values, where segments are the portions of A representing the neighbors of a single node. Finally, each entry of (v,$e\_{k}$) ∈ A applies its result of segmented prefix sums to the edge E\[k\], while using the technique of Lemma 2 to avoid write conflicts. Each step of the algorithm can be implemented in O(log|A|) time using O(|A|) work.

Any sources can help me understand these concepts?

# Answer
The idea is that if you have any associative operator at all, then you can use the lemma to apply it to all edges incident on $v$.

There are many possibilities for operators that are associative, including sum, min, max, and many more. You can use the lemma with any of them.
> 1 votes

---
Tags: parallel-computing, matching
---


# Question
Title: Finding minimal moves to move boxes into m floors
Assume a tower with $n$ floors.

Each floor contains $C\_i$ boxes such that $C\_i\>0$ for all $1\le i\le n $

Moving $C\_i$ boxes from floor $i$ to floor $j$ where $i\>j$ costs $C\_i\cdot(i-j)$ and we can only move all the boxes at once, and they all go to the same floor. (The boxes can only be moved downstairs) Given $C\_i$ for all $1\le i\le n$ and integer $m$, choose $m$ floors and a partition of the boxes so that all the boxes can be moved to the $m$ chosen floors with minimal move cost.

Input: $C\_1,C\_2,\dots C\_n$ and number of target floors $m\in \mathbb{N}$

An example: $n=4,C\_1=1,C\_2=2,C\_3=2,C\_4=3,m=2 $

So we need to choose 2 floors in which all the boxes will be after moving, we must choose the lowest floor as we cant take those boxes upwards, and another floor, the best floor is the 3rd floor here. (If we choose top floor we use $2$ moves to move from $F\_2\mapsto F\_1$ and $2\cdot 2$ moves to move from $F\_3 \mapsto F\_1 $)

How to find an algorithm to calculate the minimal cost of moving all the boxes to some $m$ floors? I tried doing a brute-force method of just choosing $\binom{n}{m}$ floors and calculating all the costs from each floor to the nearest target floor, but I need to do a dynamic programming approach here, yet can't find the formula or the data structure to use former results.

I also tried a greedy approach but it didn't seem to even work for simple cases.

# Answer
> 4 votes
The difficulty of solving many hard problems using dynamic programming is to create/imagine/formulate/decide/select the subproblems with the right number of dimensions/parameters.

While the subproblems cannot be too many to include all dimensions of the problem that we are basically applying brute force, they cannot be too few for us to establish the recurrence relations. The principle of more-subproblems suggests the more subproblems, the easier to solve the bigger subproblems. We want to describe/select subproblems with enough appropriate conditions/precision so that the solutions to smaller ones can be useful and extended to solutions to larger subproblems. $\newcommand{\F}{\mathscr F}$

#### Subproblems and recurrence relation

The subproblems for this problem are, I would propose, **what are the minimum moves to move all boxes to $f$ floors that include floor $h$ as the highest floor among them and floor $1$**, where $1\le f\le m$ and $f\le h\le n$. The specification of the highest floor enables us to take advantage of the optimal substructure hereof to establish some recurrence relation; in contrast, if the subproblems are the minimum moves to $f$ floors simply, we cannot establish a recurrence relation.

Denote the number of moves in those minimum moves by $\ell\[f\]\[h\]$.

The recurrence relation is, for $f\ge3$, $$\ell\[f\]\[h\]=\min\_{f-1\le h^-\le h-1}(\ell\[f-1\]\[h^-\]-s\[h\]\times(h-h^-)),\tag{\***}\label{\***}$$ where $s\[h\]$ is the total number of boxes at floor $h$ and above. The base case are $\ell\[1\]\[1\]=\sum\_{i=1}^nC\_i(i-1)$ and $\ell\[2\]\[h\]=\ell\[1\]\[1\]-s\[h\](h-1)$. The sought answer is the minimum among all $\ell\[m\]\[h\]$, where $m\le h\le n$.

Call a group of floors that includes floor $1$ a selection. Abusing $\ell$, for a selection $\F$, let $\ell(\F)$ be the number of total moves to move each given box to the nearest floor in $\F$, i.e., the highest floor not higher than the given box. Call a selection an optimal selection if it has the least $\ell(\cdot)$ among all selections with the same number of floors and the same highest floor as itself.

Let $\F$ be an optimal selection. Let $\F^-$ be $\F$ without its highest floor. Then $\F^-$ must be an optimal selection, too. Had it not been, we could have replaced $\F^-$ in $\F$ with an optimal selection with the same number of floors and the same highest floor as $\F^-$ while keeping the highest floor of $\F$ to obtain a selection that leads to less moves, which contradicts with $\F$ being an optimal selection.

Note that $\ell(\F)=\ell(\F^-)-s\[h\]\*(h-h^-)$, where floor $h$ and $h^-$ are the highest floor and the second highest floor in $\F$ respectively, since all boxes in $\F$ will be moved to the same floor as if in $\F^-$, except the boxes that are in floor $h$ and above, each of which will be moved to floor $h$ instead of floor $h^-$.

Suppose $\F$ has $f$ floors. Then $\F^-$ has $f-1$ floors. Letting $h^-$ range through all possible values, we obtain the recurrence relation $\eqref{\***}$.

The explanation above focuses on the minimum moves. Adding bookkeeping to track the floor selected along the computation, we can obtain the selection that attain the minimum moves.

#### Complexity

It takes $O(n)$ to compute all $n$ numbers $s\[h\]$.

The number of entries $\ell\[f\]\[h\]$ is at most $mn$. Thanks to $\eqref{\***}$ and memoization, it takes $O(h-f+1)=O(n)$ time to compute each entry $\ell\[f\]\[h\]$.

It takes $O(n)$ to compute the sought answer from $\ell\[m\]\[h\]$'s.

The total time-complexity is $O(n) + O(mn\\,n) + O(n) = O(mn^2)$.

The space-complexity is $O(mn)$.

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


# Question
Title: minimum number of 2d elements whose sums across both dimensions satisfy some threshold
I have the following problem formulated as a linear integer program:

\begin{align} & \text{minimize} && \sum\_{i \in n} x\_i\\ & \text{subject to} && \sum\_{i \in n}{a\_i}x\_i \ge \theta\_1, \\ & && \sum\_{i \in n}{b\_i}x\_i \ge \theta\_2, \\ & && a\_i \ge 0 \quad \forall i \in n , \\ & && b\_i \ge 0 \quad \forall i \in n , \\ & \text{and} && x\_i \in \\{0,1\\} \quad \forall i \in n , \end{align} for any given $\sum\_i a\_i \geq \theta\_1 \geq 0$ and $\sum\_i b\_i \geq \theta\_2 \geq 0$

Another way of looking at it, is that we have a number of 2d tuples and we want to select the minimum number of tuples such that the sums over both dimensions are greater or equal to two thresholds. Does anyone know anything about the complexity of this problem? If we only have the first constraint: $ \sum\_{i \in n}{a\_i}x\_i \ge \theta\_1 $, and we drop the second: $\sum\_{i \in n}{b\_i}x\_i \ge \theta\_2$ (1D variant) then the problem is easy, we can just sort all $a\_i$ in decreasing order, and pick the top ones until the threshold $\theta\_1$ is satisfied. However, it seems to me that once we add the second constraint the problem becomes much harder (possibly NP-hard). Still, the idea of sorting and greedily picking elements gives at least a 2-approximation. Any clues?

# Answer
Your problem is NP-hard, by reduction from the equal-cardinality partition problem.

Let $a\_1,\dots,a\_n$ be an instance of the equal-cardinality partition problem (so $n$ is even). The reduction works as follows. Choose a sufficiently large constant $C$. Define $b\_i = C-a\_i$, $\theta\_1 = (a\_1+\dots+a\_n)/2$, $\theta\_2 = nC/2 - \theta\_1$.

Now if there is a solution to the equal-cardinality partition problem, then there is a solution to your problem with $x\_1+\dots+x\_n \le n/2$. Proof: In particular, we can set $x\_i=1$ for each element in the first part; since both parts have equal cardinality, this sets $n/2$ of the $x\_i$'s to 1; and then since it is a solution to the partition problem, we have $\sum\_i a\_ix\_i = \theta\_1$ and

$$\sum\_i b\_ix\_i = \sum\_i Cx\_i - \sum\_i a\_ix\_i = nC/2 - \theta\_1 = \theta\_2,$$

hence this is a valid solution to your problem.

Also, if there is a solution to your problem with $x\_1+\dots+x\_n \le n/2$, then it yields a solution to the equal-cardinality partition problem. Proof: If $C$ is chosen to be sufficiently large, then the only way to satisfy $\sum\_i b\_i x\_i \ge \theta\_2$ is to have $x\_1+\dots+x\_n \ge n/2$, so we must have $x\_1 + \dots + x\_n = n/2$. Therefore we can put all $a\_i$'s where $x\_i=1$ into the first part, and all others into the second part, and the two parts will have equal cardinality. Now since $x\_1+\dots+x\_n = n/2$, we have

$$\sum\_i a\_i x\_i = nC/2 - \sum\_i b\_i x\_i \le nC/2 - \theta\_2 = \theta\_1,$$

which together with the constraint $\sum\_i a\_i x\_i \ge \theta\_1$ implies that $\sum\_i a\_i x\_i = \theta\_1 = (a\_1+\dots+a\_n)/2$, so these two parts form a solution to the partition problem.

This means that this yields a valid reduction, and thus a proof of NP-hardness.
> 3 votes

---
Tags: sorting, integer-programming
---


# Question
Title: Searching an algorithm to generate Tectonic/Seguru puzzle
I'm trying to write a program that generates a Tectonic/Seguru puzzle, and I'm struggling to find an algorithm that can generate them

The rules of the puzzle are here, but basically, it involves a grid that's divided into components, and the goal is to fill the grid with numbers according to these 2 rules :

* A component of n cells contains each integer from 1 to n exactly once
* Two adjacent cells (including diagonally) cannot have the same number in them

So far, the only method I could find for generating a grid is generating random grids (possibly unsolvable) and trying to solve them, until i find a grid that is solvable

Obviously that's a terribly inefficient algorithm, but i couldn't find anything that would be more powerful

Does someone knows of an algorithm that could be useful in this situation ?

# Answer
> 1 votes
One way that puzzles *like* this (not necessarily *exactly* this) are often generated is to use a solver to test candidate solutions.

We'll assume that you generate a polyomino tessellation first, and I'll assume that this isn't a challenge for you. The real difficulty is adding just enough clues to give the puzzle a unique solution.

What makes this style of puzzle tractable (as with Sudoku) is that each cell can only contain one of a small number of possible values. So if you have a solver which answers the yes/no question "can the grid be *completed* given these clues", you can in principle just test them all.

Taking the linked example:

What numbers could possibly go in row 1 column 6? It's in a pentomino, so you are limited to the values 1 through 5. You can test a value, say the value 1, by adding that as a "clue", and then asking the solver if the rest of the grid can be completed. If not, then 1 is not a possible value in that cell.

Once you have done this for a cell, then there are three possibilities:

1. There are no possible values that can go in the cell. Then the puzzle has no solution.
2. There is exactly one possible value that can go in the cell.
3. There is more than one possible value that can go in the cell. Then this gives you a cell which could be a potential new clue.

If all of the cells have only one possible value that can go into them, the puzzle has a unique solution.

Writing a solver can be straightforward if it can be reduced to a problem like exact cover, or you could use a drop-in SAT solver. As an optimisation, solvers often prove that a grid has a feasible completion by generating that completion, and any such completion gives you a collection of "possible values" for some grid cells that don't need to be tested.

---
Tags: algorithms
---


# Question
Title: Efficiency of Halting Problem on finite space TMs
This question is about the (Edit: universal) Halting Problem on a TM with finite space.

The Halting Problem is obviously decidable on those TMs. So my question now is how efficient we can decide it.

My intuition is, that there is now better way than brute force. Because, if we have a better algorithm than that (for an arbitrary TM with arbitrary much but limited space) we would have a better algorithm for the Halting Problem on any TM. (And I guess that such a strategy can not exist on the general problem)

But how can we prove this?

# Answer
Consider a Turing machine with alphabet $\Sigma$, states $Q$, a transition function $\delta$ and a tape with $k$ cells.

The configurations of this Turing machine (contents of the tape, current state, position of the read-write head) form a finite set $\Sigma ^k \times Q \times \[k-1\]$ if $\[k-1\] = \\{n \in \mathbb N : n \lt k\\}$ representing an index for the position of the read-write head.

Consider the directed graph where the nodes $m\_i$ are elements from $(\Sigma^k \times Q \times \[k-1\])$ and there is an edge between two nodes $m\_i$ and $m\_j$ if $(m\_i, m\_j) \in \delta$.

Look at the starting configuration. The question of whether this Turing machine halts is can be interpreted as whether the starting configuration has a path to a cycle or whether there is a path from the starting configuration to the halting state.

Both of these questions can be answered using a search algorithm in $O(|V| + |E|)$ time.

If the alphabet has $n = |\Sigma|$ elements and the Turing machine has $s=|Q|$ different states then the graph has $kn^ks$ nodes.

If the Turing machine is deterministic then the graph has one edge for every non-terminal state.

If the Turing machine is non-deterministic then there is an upper bound of $O((kn^ks)^2)$ edges.

So for deterministic Turing machines, you can solve the problem in $O(kn^ks)$ time and in $O((kn^ks)^2)$ time for non-deterministic Turing machines.
> 2 votes

---
Tags: time-complexity, turing-machines, halting-problem
---


# Question
Title: Expected value of maximum of a matrix of size $n$
I have a square matrix (call it $A$) of size $n$ ($n$ is a positive integer). Each column is a permutation of $\[1:n\]$.

I take the first row of $A$, i.e. $A(1,:)$ and wonder what will be the frequency of the mode. This is, how many times the most common element in the first row of $A$ will appear and whether the mode will be unique.

For example, if

```
A=
 1     2     5     4     1
 3     3     3     1     3
 5     5     2     2     5
 2     1     4     5     4
 4     4     1     3     2

```

Then the frequency of the mode is 2 (because 1 appears two times), and the mode is unique because the second most common element in $A(1,:)$ only appears once.

Simulations have shown me that if $n=100$, then the frequency of the mode is 4.23 and is unique in 51% of the cases.

If $n=500$, then the frequency of the mode is $5.14$ and is unique in 47% of the cases.

Any help understanding how these two numbers depend on $n$ would be appreciated.

# Answer
> 2 votes
This is the classical balls into bins problem with as many balls as bins. The maximum load is with high probability about $\frac{\log n}{\log \log n}$.

---
Tags: probability-theory, matrices
---


# Question
Title: Given a list of pairs (cost,points) and a number k, find the maximum sum of points with sum of costs less than or equal to k
> Given a list of $n$ pairs (cost,points) and number $k$ ($0 \le k$), find the maximum possible sum of points s.t their sum of costs no more than $k$. return the maximum possible sum of points and their corresponding sum of costs.

For example the list $\[(5,10),(1,2),(4,3),(6,12),(11,18)\]$ and $k=15$, the maximum sum of points with costs no more than 15 is 25 using the first,third and 4th pairs, and therefore we return (25,15).

Note that we can use each pair once but the same pair can appear more than once in the list(and then we can use each of its appearances once).

I was thinking about taking a dynamic programming approach here:
Let $dp\[i\]$ be the maximum possible of points we can get starting from index $i$ with sum of costs $\le k$, paired with the cost we used to get it.
For the example above: $dp = \[(25,15),(20,12),(21,15),(12,6),(18,11)\]$. After calculating $dp$ we can return the pair with highest first coordinate.

My problem here is how to calculate $dp$, The only way I tought of computing it was to go from the end towards the beginning while maintaining a second list containing all the possible pairs with costs $\le k$ and in each iteration try to add the current pair's cost to any of them and take the max of the points we found and put it in $dp$.
The problem with this approach is that it the 2nd list's size can be big and therefore the algorithm will be slow.
Is there a way to improve this approach or any other ways to solve this problem?
Thanks in advance.

# Answer
> 1 votes
Your problem is the Knapsack problem. It is already well documented. It has a pseudo-polynomial time algorithm, and a FPTAS.

The idea of the dynamic programming algorithm is that if that if $K(i, c)$ denotes the maximum sum of points with sum of costs lesser than $c$, using only elements of indices $\\{1, …, i\\}$, then: $$K(i, c) = \max (K(i - 1, c), K(i - 1, c - cost\[i\]) + points\[i\])$$ (you consider in both option whether to pick item $i$ or not).

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


title: Capacity of the Deletion Channel

text:
# Question
Title: Capacity of the Deletion Channel
Consider a Binary Deletion Channel with a deletion probability p of 1/2 and the channel has no error correction coding at all and that any given message can only be sent once. I want to conjecture that the capacity for the aforementioned channel is zero ( channel capacity for the Deletion Channel is presently unknown), can anyone point to any known complexity results that would point me in the direction of proving or disproving my conjecture?

# Answer
> 1 votes
The capacity of a deletion channel with deletion probability $p$ is still not fully understood, however it is known to be somewhere between $1-h(p)$ and $(1-p)/9$.

See a survey by Michael Mitzenmacher on deletion channels: A survey of results for deletion channels and related synchronization channels.

# Answer
> 0 votes
This is an old question, but let me give a final response for anyone who comes across it.

Your restriction is that we are not allowed to do any coding. In other words, every source codeword is transmitted directly across the channel. Since there is no redundancy being added, the transmission rate is 1 bit per symbol. As mentioned by Ran, we know that such a rate is not possible due to the channel capacity upper bound of $1/9(1-d)$ for deletion probability $d$.

A more direct way to show that such a rate cannot be achieved is to consider the block error. For a block length $N$ approaching infinity, there is *almost surely* at least 1 deletion in the channel output. WLOG, consider an input sequence $x = (x\_1,x\_2,x\_3\ldots,x\_N)$ that becomes $y = (x\_2,x\_3\ldots,x\_N)$ after deleting $x\_1$. Looking at $y$, there are multiple possible input sequences, only one of which is the transmitted $x$. The best decoder is guaranteed to make an error with non-zero probability, and hence the block error of this symbol is non-zero. For multiple deletions, this block error is only going to increase towards 1.

---
Tags: information-theory
---