# Question
Title: Designing an algorithm to choose the minimum number of sets containing line segments
Let's say we have some distinct sets each containing a number of line segments. I want to choose the minimum number of sets such that I will obtain a line from 0 to L with the largest gap being X long.

For example, let's say we have the sets A, B, and C as given below. L is 45 and X is 4.

If we take A, there is a gap from 10 to 15 that is greater than 4, and from 32 to 45. Notice that picking B covers the gap from 10 to 15, but there's still a gap between 40 to 45 so we need to pick C as well. However, we can pick C without picking B and reach our goal.

Is there any way to formulize this? If the problem was to pick the least number of segments I'd use a greedy approach but we are trying to minimize the number of sets here. I can only think of removing a set, inspecting if the goal can be met, and if so, removing another set. Maybe I can make this into a tree to see the effect of removing each set? Or is there another solution with less complexity?

Thanks

# Answer
> 1 votes
The problem is NP-hard in general. Consider the setting where X=0, and each line segment has length 1. Then this becomes an instance of the set cover problem, which is well-known to be NP-hard. So, you can't expect any efficient algorithm that always solve this problem and has good worst-case running time.

You could try applying any of the standard methods for set cover, e.g., using an ILP solver, or adapting the greedy algorithm.

# Answer
> 1 votes
In addition to D.W.'s answer, notice that the constraint on the gap is irrelevant since you can always extend each interval endpoint by $X/2$ (and shorten the endpoints of the line by $X/2$).

Then the problem can be reduced to set cover: create an item for each maximal (w.r.t. inclusion) sub-interval of $\[0,L\]$ that is covered by the same set of segments; each set of the set cover instance corresponds to a set of your instance and contains all items (i.e., sub-intervals) that are covered by some segment in that set.

The optimal measure and the number of sets of the two problems coincide, while the number of items is at most twice the number of segments (each segment endpoint creates at most one item, and you can't have uncovered portions of the line).

This provides you with a concrete strategy for using any approximation algorithm for set-cover (as D.W. suggested) to approximate your problem within the same asymptotic approximation ratio.

---
Tags: algorithms, selection-problem
---


# Question
Title: Can a static pre-shared database reduce communication size?
Is the problem of communication with a pre-shared database studied? If yes, what field studies it, or which researchers work on it?

Let there be two parties that want to share multiple yet-to-be-defined messages. These parties want to compress future communication as much as possible. For that, they first define some pre-shared knowledge: some database that will be used as a reference for constructing the messages. The size of the database is much bigger than the size of each specific message. Does the database help to compress or reduce the size of sent messages?

Here's an example: aliens from our nearest star, Proxima Centauri, come to visit Earth. They stay here for a while, which provides an opportunity to understand each other's language, define algorithms and construct a common database of some form. The time they stay here isn't sufficient to share all our knowledge, and we want to ease the future knowledge exchange (or even one-sided sharing) when they are back at Proxima Centauri.

While they are here, it's easy to share communication, and construct a big pre-shared database. However, Proxima Centauri is about 4.2 light years away from Earth, so sending a message from us to them takes about 4.2 years to reach the destination. We have lots of data to share, and we want to reduce the size of the sent messages. We can compress the sent messages with any available methods, but the question is, can this database help? For example, instead of writing a full message of size $n$, find the first $n/k$ bits in the database, and if they are there, call the address of the first bit $A$, do the same for the rest and call the address $B$. With that, instead of sending the whole message, send just the addresses of $A$ and $B$, and the length of the message (or, send more than two addresses, if the message can't be split into two addresses because there are no such strings in the database).

Is this question studied in any way? Can such a database help, or sending the addresses of $A$ and $B$ won't be shorter than the message itself? Various models come to mind: the database can be just a long array of random bits, pre-structured, or calculated (e.g.: take $k$ bits starting from the $m$-th digit of $\pi$). It can be static, or grow over time according to some algorithm or even by using the exchanged messages. For a database of size $O(n)$, the messages can be of size $O(log(n))$ or $O(sqrt(n))$ or some other function of $n$ that is significantly smaller than $n$. The allowed messages can include any string or only strings of some form. The number of sent messages can be infinite or be defined as some function of n. The message exchange algorithm can use only the database addresses or any combination of database data with message unique data.

The main idea is to check if some formatted (even if randomized) pre-shared database can reduce the messaging size (even if probabilistically): per message, or cumulatively for multiple or all messages.

Thanks in advance.

# Answer
> 0 votes
I will assume you are looking for an information-theoretic view, where the goal is to come up with an encoding/compression scheme to minimize the length of the encoded data, without worrying about computational issues (how efficiently the data can be encoded or decoded). I'll also assume that you want lossless compression. In that case, this should be covered by standard information-theoretic notions.

The answer depends on the nature of the process that generates the data you want to transmit. If this process is independent of the database, then the database won't help. More precisely, let $X$ denote the message that you are sending. In information theory, we model $X$ as a random variable. If $X$ is independent of the database (i.e., the process that generates $X$ is independent, in terms of probability theory, from the process that generates the database), then the database doesn't help. The best you can do is to use the best code for $X$ in isolation. Shannon's source coding theorem states that you need approximately $H(X)$ bits to send $X$ in encoded form, where $H(X)$ is the Shannon entropy of $X$.

In the general case, where the two aren't necessarily independent, then the database can help. Let the r.v. $X$ model the (process for generating the) message you want to send and $D$ model the (process for generating the) database. Then the number of bits needed is approximately $H(X|D)$. In other words, in this case we need to use the conditional entropy.

How much does the database help? It reduces the number of bits needed from $H(X)$ to $H(X|D)$. Thus, it helps by saving us $H(X)-H(X|D)$ bits per message. This value is so important it has a name: it is called the mutual information, and is denoted by $I(X;D)$.

The information-theoretic view has some limitations. It assumes that the probability distributions that generate $X$ and $D$ are known, perfectly, to both the sender and the receiver. It also ignores the computational costs of encoding and decoding. Both of these might be issues in practice. Nonetheless, it is helpful for understanding limits on what is achievable.

---
Tags: complexity-theory, information-theory, communication-protocols, communication-complexity
---


title: Which system has higher entropy?

text:
# Question
Title: Which system has higher entropy?
Suppose that I have two random processes. Process $X$ has probability 0.5 to be in state A and probability 0.5 to be in state B. Process $Y$ has probability 0.4 to be in state A and probability 0.6 to be in state B.

State B has two substates: $B\_1$ and $B\_2$. For both processes, the two substates are equally likely.

Now if I choose to only consider the states $A$ and $B$, then process $X$ has higher Shannon entropy. But if I consider states $A$, $B\_1$ and $B\_2$, then process $Y$ has higher Shannon entropy.

What is the correct way to chose the states for which you calculate the Shannon entropy?

# Answer
> 2 votes
Shannon entropy computes the average number of bits needed to represent the outcomes.

Your first probability distributions are: D1: 0.5, 0.5 and D2: 0.4, 0.6, the first of which has higher shannon entropy (maximal in fact).

In the second situation your distributions are: D3: 05, 0.25 and 0.25 and D4: 0.4, 0.3 and 0.3.

The situation is now reversed: fewer bits are needed to represent a process with outcomes following distribution D3 (0.5, 0.25 and 0.25).

The intuition is that a more optimal encoding (using bits) exploits the highest frequencies (= highest probabilities of occurrence) equipping those outcomes with shorter codes (i.e. shorter binary numbers) so that the overall average encoding cost (the average number of bits used) is lower.

---
Tags: information-theory, entropy
---


# Question
Title: Is there an algorithm that causes a straight line and a circle to collide and bounce?
I used a vector to determine the collision between a line and a circle. Here's the way I thought of it in the beginning.

1. When the ball collides with a straight line, it finds a normal line passing through the center point.

2. Take the coordinates before the ball collides and move symmetrically with respect to the normal.

The results were similar to those intended, but unstable. Since then, I have tried to find the angle using the vector, but it has not progressed since then.

# Answer
> 1 votes
Find the intersection point between the parallel to the line at distance R and the trajectory of the center of the ball.

Now notice that the sum of the incoming and outgoing direction vectors (let I and O) is parallel to the line, corresponding to a vector α.D of unknown length.

```
I + O = α.D

```

The by expressing that I and O have the same length,

```
(α.D - I)² = I²

```

and

```
α.D² = 2 D.I

```

which gives α and `O = 2 (D.I/D²).D - I`.

---
Tags: algorithms
---


# Question
Title: Context free grammar for $L= \{0^i1^ic0^j1^j | j = i+1 \}$
## Description

This is an exercise for Formal Language course, I'm asked to find a grammar for language:

$L = \\{ 0^i1^ic0^j1^j | j = i+1 \\}$

As an example: 01c0011 can be generated using this language, so does 0011c000111.

## What I've tried

The difficulty is around the `j = i + 1` controlling, I've tried something like this:

```
S -> 0A11
A -> 0A1 | 1B00
B -> 1B0 | c

```

Although it can generate all strings that L can generate, but if you take `B -> c` to terminate the generation early, the string such as "001c00111" doesn't belong to L anymore.

Can somebody give me some advice on this? Better yet, can you tell me what is the correct way to solve such problems? (given language, find CFG)

# Answer
> 1 votes
It is to be expected that you have difficulties finding a context-free grammar since the language is not context-free.

Indeed, suppose it is; it should verify the pumping lemma for context-free languages. Let $n$ be the pumping length and $u = 0^n1^nc0^{n+1}1^{n+1} \in L$. The pumping lemma states that there exists a decomposition $u = vwxyz$ such that:

1. $|wxy| \leqslant n$;
2. $|wy| \> 0$;
3. for all $k\geqslant 0$, $vw^kxy^kz\in L$.

Now suppose the first two points are verified. Let us distinguish:

* if $wxy$ is composed of only $0$'s or $1$'s, then $vxz$ does not contain as many $0$'s as $1$'s, so $vxz\notin L$;
* if $w$ or $y$ contains $c$, then $vxz$ does not contain $c$, so $vxz\notin L$;
* if $x$ contains $c$, then $w$ contains only $1$'s and $y$ contains only $0$'s (given $|wxy| \leqslant n$), and $vxz = 0^n1^mc0^k1^{n+1}$, with $m\neq n$ or $k\neq n+1$, so $vxz\notin L$;
* if $w$ or $y$ contains $0$'s AND $1$'s, then $vw^2xy^2z$ contains $010101$ as a subsequence, so $vw^2xy^2z\notin L$;
* given the previous cases, the only possibility is that $wxy$ is a subword of the $0^n1^n$ part or the $0^{n+1}1^{n+1}$ part. Since $wy\neq \varepsilon$, it means that $vxz = 0^i1^jc0^k1^{\ell}$ with either $k \neq i + 1$ or $\ell \neq j + 1$, so $vxz\notin L$.

In each case, we proved that the property 3. cannot be verified. We conclude by contradiction that $L$ is not context-free.

# Answer
> -1 votes
@Nathaniel has actually given a nice proof and standard one. (Wanted to write my answer as comment but having less points.) I would like to conclude with a short point while you continue with your course it'll be helpful.

To identify RL: if language is finite =\> then it's regular else if its infinite , single alphabet language(unary language) is regular and if it is resulting in an Arithmetic progression kind of string length. And if more than one alphabets are there in the language but aren't dependent on each other , the language is Regular.

To identify CFL , it must be having :

```
language is regular

```

or

```
it's a language in which there's no such comparison with the bottom of the stack,

```

since comparison is done with the top of the stack in PDA or

```
there are not more than two dependent alphabets

 or
there are not more than two independent alphabets

```

---
Tags: formal-languages, automata, context-free, formal-grammars
---


# Question
Title: Alpha beta pruning does not detect a candidate
My minimax graph search has considered three options at the root level of a graph.

* The first option, `A`, yields a solution with cost 10.
* The second option, `B`, was not fully investigated. It has a solution with cost 20, and the lower limit to any possible solution is 15.
* The third option, `C`, was also not fully investigated. It has a solution with cost 20, but the lower limit is only 5, so it may still be possible to find a better solution.

Alpha-beta pruning kicks in and removes option `B`, which is clearly inferior to option `A`. This is the search tree at this point:

```
Root: 5 to 10
 |-- A: 10
 |   `-- AA: 10 [solution]
 |
 |-- B: 15 to 20 [pruned]
 |
 `-- C: 5 to 20
     |-- CA: 5 to +inf
     `-- CB: 12 to 20
          |--- CBA: 12 to 40
          `--- CBB: 20 [solution]

```

It's good that option `B` was removed. Now, when looking more closely at option `C`, it has two children: `CA`, with cost 5 to +inf, and `CB`, with cost 12 to 20. Considering that there is a global optimum at cost 10 already, `CB` cannot be better and should also be pruned. However, nobody told `CB` of that. It's parent, `C`, only knows that there might be a solution with cost 5 (in branch `CA`), and (rightfully) refused to be alpha-beta pruned. It did not transmit this information to its children.

My questions are:

* Did I misunderstand alpha-beta pruning and it should actually detect `CB`?
* Which pruning algorithms support this scenario?
* Is a forward sweep in addition to backpropagation unavoidable, or can one do better?

# Answer
You want a solution with the lowest cost, your opponent wants a solution with the highest cost. You examined A and it gave you a cost of 10. You examined B. You tried to find the worst move that the opponent could do on you, but any opponent move with a worst cost of "more than 10" can be ignored. There was no opponent move worse than 15, so this branch is pruned.

Then you examine C. Again, we examine moves of the opponent. If the opponent moves CA, it only costs you 5. So the opponent would hate to do that. If the opponent moves CB, you will try to get the move with the lowest cost. CBA has a cost of 12, CBB has a cost of 20, so you would move CBA. So CB has a cost of 12, which is better for your opponent than CA with a cost of 5. So when you move C, the opponent will move CB with a cost of 12. The cost of C is 12, not 5. You move A.

How A-B pruning works: You examine all your moves, assuming that your opponent will do its worst, and you want the move with the lowest worst-case cost.

You found A has a cost of 10, and you examine B. The opponent will try all its moves to find the one that is worst for you. But if a move has cost "higher than 10" then it can be ignored - you wouldn't choose move B if there is a counter move worse than 10; you would do move A.
> 0 votes

---
Tags: pruning
---


# Question
Title: Can distance from source to any of the vertex decrease during the run of Ford Fulkerson algorithm?
During the run of Ford Fulkerson algorithm if we label each vertex with d(v) where it means the shortest path distance from source to vertex v in residual graph. Is it possible that for some vertex this value decreases at any execution stage? I tried to find such an example, but it seems the vertices are getting away after each iteration from the source. Could you provide some example or at least starting point how to prove it?

# Answer
> 1 votes
Consider the following flow graph and associated residual graph:

In this graph, $d(3) = 3$.

If you saturate the augmenting path $(s, 1, 2, 3, 4, t)$, then the graph and residual graph become:

In this graph, $d(3) = 2$, so it decreased.

---
Tags: network-flow, ford-fulkerson
---


# Question
Title: In two unsorted arrays A and B such that all items of A belong to B (A ⊂ B), find the smallest item in B that doesn't occur in A in linear time?
> In two unsorted arrays (say $A$ and $B$) such that all items of $A$ belong to $B$ ($A \subset B$), find the smallest item in $B$ that doesn't occur in $A$ in linear time.

No hashing or linear time sorting is allowed.

I can solve this question when $A$ and $B$ are sorted.
However, the question states $A$ and $B$ are unsorted, and I cannot think of a solution that solves this in O(n) time.

# Answer
> 2 votes
I'm going to assume that all elements in $A$ and $B$ are distinct (this assumption can be removed with some care), that elements possess a linear order, and that they can be compared in constant time.

Consider the following recursive algorithm: if $|A|=0$, return the minimum in $B$ (in time $O(|B|)$). Otherwise, find the median $x$ of the multiset obtained by unioning $A$ and $B$ and partition the elements of $A$ in $A\_{\le x}$ and $A\_{\> x} $ (resp. the elements of $B$ in $B\_{\le x}$ and $B\_{\> x} $) depending on whether they are at most $x$ or larger than $x$. This requires time $O(|A|+|B|)$.

If $|A\_{\le x}|=|B\_{\le x}|$ then $A \subset B$ implies $A\_{\le x}=B\_{\le x}$ and you can recurse on $A\_{\> x} $ and $B\_{\> x}$.

If $|A\_{\le x}| \< |B\_{\le x}|$ then the minimum element in $B \setminus A$ must be at most $x$ and hence it is in $B\_{\le x} \setminus A\_{\le x}$ and you can recurse on $A\_{\le x}$ and $B\_{\le x}$.

Let $n = |A| + |B|$. By the choice of $x$, the input size of the recursive call will be at most $\left\lceil \frac{|A|+|B|}{2} \right\rceil = \lceil n/2 \rceil$, showing that the algorithm eventually terminates (since $n \le 2$ implies $|A|=0$).

To bound the running time we notice that it is described by the recurrence $ T(n) = T(\lceil n/2 \rceil) + O(n) $, which has solution $T(n)=O(n)$.

# Answer
> 1 votes
Reasoning:

* you are asked the *smallest* in $B$; this hints that the solution will be comparison-based.
* with an $O(n)$ budget, no comparison-based sort is possible; the best you can do with comparisons is to heapify !
* wonder what happens if you heapify the two arrays and compare them.

Notice that after a heapify operation, every array element is the smallest among the subtree of which it is a root. So when you compare the heaps formed from $A$ and $B$, the first discrepancy you will meet when scanning the elements will reveal the solution.

E.g.

$$A= \[1,2,3,4,6\],\\ B= \[6,2,4,7,1,5,3\]$$

heapify as

$$A=\[1, 2, 3, 4, 6\],\\B= \[1, 2, 3, \color{green}7, 6, 5, 4\].$$

---
Tags: algorithms, time-complexity
---


# Question
Title: Understanding the logic for finding the count of same-element-pair
There's this problem that I was solving and even though I have an O(n) solution but still trying to make sense of the pattern.

The problem being: determine the number of pairs of the same numbers. For e.g for an array `[1,2,3,1,2,1]`. The 4 possible pairs include:

```
[1,1]  // index (0,3)
[1,1]  // index (0,5)
[1,1]  // index (3,5)
[2,2]

```

**The solution:**

```
std::unordered_map<int,int> mp;
int res = 0;
for (auto& elem : nums)
{
   res += mp[elem]++;
}
// res contains the number of possible pairs

```

**Question:**

How does continuously adding the frequency of each element to `res` tell us about the possible pairs between the same numbers?

Is this a valid way of looking at it?

* The first `1` has 0 pairs
* The second `1` has 1 pair
* The third `1` has 2 pairs
* the first `2` has 0 pairs
* The second `2` has 1 pair

---

=\> `0 + 1 + 2 + 0 + 1 = 4`

# Answer
> 1 votes
the number of pairs for each number of duplicates is

| number of numbers | number of pairs |
| --- | --- |
| 1 | 0 |
| 2 | 1 |
| 3 | 3 |
| 4 | 6 |
| 5 | 10 |

If we have N identical numbers then the first can pair with the other N-1 values, the second with N-2 because we've counted it's pairing with the first value already and so on. So it's N-1 + (N-2) + ... + 1 and that we know from Gauss that comes to N(N-1) / 2

And that's what the map loop does.

The first time we hit an element we add nothing to res but we increment the value in the map for that key by 1. The next time we see that same value the map value is 1 so we add that and increment the map value again. And so on so res goes from

0 -\> 1 -\> (1 + 2) -\> (1 + 2 + 3) -\> (1 + 2 + 3 + 4) ...

or

0 -\> 1 -\> 3 -\> 6 -\> 10

which is exactly the same thing i.e. the sum of the numbers up to that point.

---
Tags: algorithms, time-complexity
---


# Question
Title: Randomly build a binary search trees with simple modification
Let $X=x\_1,x\_2,x\_3,\dots,x\_n$ be set of $n$ distinct keys. I read this posts about Randomly build binary search trees like this and now I encounter the following question in my mind, suppose we generate a random permutation $X'$ from $X$ and we insert first half of $X'$ in empty binary search tree $T$. Also we sort second half of $X'$ and then insert them, can we conclude that the expected height of $T$ is $O(\log n)$. I sense the answer is yes, because we know that the expected height of $T$ after inserting first half is at most $\log \frac{n}{2}$ but I can't convince myself that after inserting second half the average height remain $O(\log n)$.

# Answer
> 0 votes
Suppose for simplicity that $n$ is even and let $S$ be the sorted list of elements. Let the elements that end up in the first half of your permutation be "red", while the others are "blue".

Consider a leaf $v$ of the tree $T$ built on the first half of the elements in the permutation, and notice that $v$ stores some red element $x$. After inserting the second half of the elements, the height of the subtree of $T$ rooted in $v$ will be upper bounded by the maximum number of contiguous blue elements immediately preceding or following $x$ in $S$.

Therefore, we just need to bound the length of the longest run of blue elements in $S$.

To this aim let $\ell=\lceil 2 \log n \rceil-1$ and fix an element $y$ in $S$ (we don't care whether $y$ will be red or blue) that is followed by at least $\ell$ elements. Let $Y\_i$ be the event "the $i$-th element following $y$ is blue". We want to estimate the probability that $y$ is the first element of a run of $\ell+1$ blue elements. Formally, we want to upper bound the probability of the event $ \bigcap\_{i=0}^\ell Y\_i$. $$ \Pr\left(\bigcap\_{i=0}^\ell Y\_i\right) = \prod\_{i=0}^\ell \Pr(Y\_i \mid Y\_1, \dots, Y\_{i-1}) \le \prod\_{i=0}^\ell \Pr(Y\_i) = \frac{1}{2^{\ell+1}} \le \frac{1}{2^{2\log n}} = \frac{1}{n^2}. $$

Taking the union bound over all possible elements $y$ (i.e., over all possible starting positions of the run), we can conclude that the probability that there exists some run of at least $2\log n$ blue elements in $S$ is at most $n \cdot \frac{1}{n^2} = \frac{1}{n}$.

As a consequence, the height of the tree will be at most $\log \frac{n}{2} + 2 \log n \< 3 \log n$ with high probability (i.e., with probability at least $1-\frac{1}{n}$).

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


title: Languages and Turing Machine

text:
# Question
Title: Languages and Turing Machine
Since strings are finite by definition, then it follows that languages are enumerable because they are finite string sets and we know that finite string sets are enumerable. Turing Machines are enumerable, because each Turing Machine has a finite string description. Therefore:

1. If all languages are enumerable, and we know that if there is an enumerator (which is also a Turing Machine) then the language is recognizable, then all languages are recognizable.
2. If Turing Machines are enumerable and languages are enumerable, we can have a bijection between Turing Machines and languages.
3. If Turing Machines are enumerable and languages are innumerable, we conclude that all languages are recognizable because each language has an associated Turing Machine (and enumerator).

Where are the errors of this question? Item 1? Item 2? Item 3?? Explain each of the alternatives, even it is correct.

# Answer
> 0 votes
Your sentence "languages are enumerable" could be ambigous.

A given language is enumerable, because it is a set of finite strings, but the set of languages is not enumerable, because it is the powerset of an infinite set ($\Sigma^\*$).

That means that all your 3 items are false.

---
Tags: turing-machines, turing-recognizable
---


# Question
Title: Convolutional neural network for non-image data
I am working on a project for the prediction of preeclampsia, and one of the algorithms to be used is the convolutional neural network. I am a beginner in machine learning, and I am struggling to find out "**whether is it applicable to use the convolutional neural network for numerical data. without the need to convert it to images first?**". if yes, please provide me with some resources to know how.

thank you.

# Answer
Yes, the input to a neural network is just a bunch of numbers. An image is treated as a bunch of numbers, one number for each pixel.

That said, a convolutional neural network might or might not be the right tool, depending on the nature of your data. CNNs are good for working with 1D sequences of numbers or 2D arrays/matrices of numbers, especially if you expect that they should have some time-invariance or translation-invariance properties (e.g., a pattern that occurs this week is also interesting if it occurred last week). It's not the right tool if you have a feature vector that is an assortment of unrelated features; in that case, a fully connected neural network is probably more appropriate.

There is *lots* of basic information about CNNs available on the Internet. I suggest finding yourself some tutorials and studying how they work.
> 0 votes

---
Tags: algorithms, machine-learning, artificial-intelligence, neural-networks
---


# Question
Title: Can you define a complexity class by giving a language and declaring that the language is complete for the class?
Can I define a complexity class $\mathsf{C}$ by giving a language $L^\prime$ and stating that $L^\prime$ is $\mathsf C$-complete? Specifically, a language $L$ is in $\mathsf C$ if there is a reduction from $L$ to $L^\prime$.

If so, are there any common (i.e., well-studied) complexity classes that are usually defined this way? If not, why not?

# Answer
Yes, complexity classes can be defined this way. $GI$ is a well-studied example. From Wikipedia:

> Since the graph isomorphism problem is neither known to be $NP$-complete nor known to be tractable, researchers have sought to gain insight into the problem by defining a new class $GI$, the set of problems with a polynomial-time Turing reduction to the graph isomorphism problem.
> 4 votes

---
Tags: complexity-classes
---


# Question
Title: Is it possible to randomly allocate items to bins such that each distinct allocation has equal probability?
I'm trying to randomly allocate N indistinguishable items over B indistinguishable bins with unlimited capacity. Each allocation should occur with equal probability. An allocation identifies the number of balls in each bin, and two allocations are equivalent if you can obtain one by permuting the other.

At first, I thought that I could successively pick a random bin for each item. But this has two problems:

1. Even though the bins are indistinguishable, they need to be indexed during the selection process to be adressable. But that introduces order. There are more distinct allocations when there's order, but they don't map uniformly to the ones from the orderless case. Thus, some allocations are more likely to occur.
2. If we look at the sequences of indices selected for each item in the allocation process, we see that allocations differ by how many different index sequences they can be reached. The allocation where all items fall into the same bin will be much more unlikely to occur than the one where they are distributed perfectly even.

I found out that my problem can also be understood through partitions from number theory, but didn't get very far with that, either.

The only solution I could think of, is to enumerate all allocations explicitly, then sort the bins by size to filter out duplicates, and then randomly pick one of the remaining allocations. But due to memory explosion, this obviously quickly becomes infeasible for non-toy problem sizes.

# Answer
It appears your question is equivalent to sampling uniformly at random from the integer partitions of $N$, but constrained so that your partition has $\le B$ parts.

If that is correct, there are standard methods to sample uniformly at random from the integer partitions of $N$. See, e.g., https://stackoverflow.com/q/2161406/781723, https://stats.stackexchange.com/q/497858/2921. One approach to solve your problem is to use rejection sampling: generate a random integer partition, and if it has more than $B$ parts, throw it away and repeat.

Another way is to adapt the method of https://stats.stackexchange.com/q/497858/2921 to enforce this constraint, so rather than sampling from the distribution $\Pr\[K=k\] \propto k^n/k!$, sample from the conditional distribution $\Pr\[K=k|K\le B\]$. Note that $\Pr\[K=k|K\le B\] \propto k^n/k!$ for $k\le B$, so one way to sample from this distribution is to let $S=\sum\_{k=0}^B k^n/k!$, sample $x$ uniformly at random from $\[0,1\]$, then let $j$ be the smallest $k$ such that $\sum\_{k=0}^j k^n/k! \ge Sx$ and output $j$.

Another way is to take advantage of the recurrence relation for counting the number of integer partitions. You can convert any such recurrence relation into an algorithm for sampling uniformly at random. Let $p(Z,B;N)$ denote the number of integer partitions of $N$ into at most $B$ parts, such that each part is at most $Z$ (or equivalently, the number of distinct ways of throwing $N$ indistinguishable bins into $B$ indistinguishable bins, such that no bin contains more than $Z$ balls). Then there is a recurrence relation for this quantity:

$$p(Z,B;N) = p(Z,B-1;N) + p(Z-1,B;N-B).$$

The recurrence is obtained as follows. Each partition of $N$ falls into one of the following two cases: (1) it uses fewer than $B$ (non-zero) parts, or (2) it uses exactly $B$ (non-zero) parts. In case (2), if you subtract 1 from each part, you obtain a partition of $N-B$ using at most $B$ parts. This immediately gives an algorithm to sample uniformly at random from the set of all integer partitions of $N$ with $\le B$ parts and all parts having values $\le Z$:

Sample($Z,B;N$):

1. Compute $p(Z,B;N)$.
2. Sample an integer uniformly at random from $0,1,2,\dots,p(Z,B;N)-1$. Call it $x$.
3. If $x \< p(Z,B-1;N)$, then call Sample($Z,B-1;N$) and return whatever it does.
4. Otherwise, call Sample($Z-1,B;N-B$), add 1 to each part of the partition it returns, append 1's until the partition has exactly $B$ parts, and return that modified partition.

(You'll need to add some appropriate base cases to ensure the recursion terminates, e.g., for the cases $B=1$ and $Z=1$.)

This generates the appropriate distribution. Also, if you compute $p(\cdot,\cdot;\cdot)$ using memoization and the recurrence relation above, this will be a relatively efficient algorithm. Its running time will be something like $O(ZBN)$.

Finally, given this algorithm, you can generate an integer partition of the desired form by invoking Sample($N,B;N$).
> 7 votes

---
Tags: algorithms, combinatorics, probability-theory, randomized-algorithms, partitions
---


title: Finite Automata Mixture Combinatorics

text:
# Question
Title: Finite Automata Mixture Combinatorics
Hello Folks, I am facing hard time in understanding this, basic question which says, how many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with alphabet a and b, that accepts everything?

What i understand is:

Number of possible inputs possible: (a,X), (a,Y), (b,X), (b,Y) i.e. 4;

so each input has option of going on 2 states, which sums up to be: 2^4;

I know to find total number of DFA, we need is Total number of transition * number of final state.

so, according to me answer need to be 2^4 * 2^2 = 2^6; but actual answer is 20 ? How it can be? Please throw some light on this !! Thankyou!!

# Answer
Notice that the question also requires the automaton to accept everything. This means that if e.g., $X$ is not accepting, then you need to discount it.

Your count of the number of transition functions is correct, $2^4$. However, it's not true that the total number is $2^4$ times the number of final states, but rather the number of *options* for final states. Naively, this would be $4$: either both $X,Y$ are accepting, neither, just $X$ or just $Y$.

However, $X$ must be accepting, otherwise the empty word is not accepted. We now have to reason about whether $Y$ is accepting. If it is, then all transition functions are ok, and the automaton will accept everything. Thus, you have $2^4$ automata with $Y$ accepting.

If $Y$ is not accepting, then not all is lost - maybe $Y$ is not reachable from $X$. This happens when both transitions from $X$ are back to $X$. In this case, you can still point the transitions from $Y$ wherever you want, so you get $4$ additional DFAs.

So in total, you have $16+4=20$ options.
> 1 votes

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


title: Scoring the postal code mismatch

text:
# Question
Title: Scoring the postal code mismatch
I have two postal codes (fixed size of 6 digits) to compare and return the mismatch score. where the mismatch weight of initial indexes is higher, then keep reducing.

Example postal code 123456, with index\[0\] ==\> 1 is northern region, and if index\[0\] ==\> 2 is southern region. so it should have very high mismatch score 123456 and 223456. index\[1\] represents sub-region like state, index\[3\] is like county/district, and so on..

But maybe 111156 and 111160 are nearer sub locality should be having less mismatch score.

The output of my result should match the score in the percentile.

To achieve this, if I take weights like this Sum\[0.45, 0.15, 0.1, 0.1, 0.1, 0.1\] == 100% but fixed weights cannot differentiate index base, e.g. for input source postal 111111 than searching with 111152 is greater mismatch than searching with 111125 as if we sum the mismatch scores. Mismatch weights percentile \[0.45, 0.15, 0.1, 0.1, 0.1, 0.1\] states, if there is a mismatch, happens at index 2, 3, 4, 5 all has a penalty of 10%, but this results in 111152 and 111125 will have same mismatch score for actual postal code 11111. So we cannot differentiate between 111152 and 111125. But you see 111125 is closer to 111111.

This makes me think of cumulative percentile index percentile like \[1, 0.55, 0.4, 0.3, 0.2, 0.1\] but this also doesn't work. As the sum of mismatch score going more than 1.

Also, it is not worthy to rely on the difference of postal code, like \`111000 - 110999\`, though it has a difference of 1, this difference same for \`111000 - 111001\`. Hence \`(((double)diff/Math.pow(10, diff.length()))\` is also not working to compute. So taking diff between two postal code as 123 then 123/1000 * (penalty\[diff.length()\]) wont work, as we cannot directly rely on difference.
```
Examples:
If i prefer mismatch penalty like { 0.8d, 0.7d, 0.6d, 0.3d, 0.15d, .05d }
0.05% penalty if the last char is not matched.
0.80% penalty if the first char is not matched.
Apply some minor penalty for every mismatch; after the first mismatch.

{"input" , "toBeCompared", "matchScore"}
{"999999", "989999", 0.29}, //71% mismatched, 29% matched
{"999999", "998999", 0.39},
{"999999", "999899", 0.7 },
{"999999", "999989", 0.85},
{"999999", "999998", 0.95}, //95% matched

```

Also should be able to differentiate scores between varying numbers.

```
{"111225", "111223", 0.949},
{"111225", "111229", 0.948},

```

How to achieve this? Kindly help.

# Answer
> 1 votes
Just get a list of post codes and their locations - for example, the UK has a list of about 1,100,000 post codes and their location, basically down to street level. That way you can check if a post code is valid, and how far away it is from another post code, at least the direct distance (driving distance would be more complex).

Looking at the letters and digits is pointless. Change the first letter and you are in a different part of the country. Change the last letter and you might be 50 or 200 meters from my home, or a few kilometres, depending on how the postcodes are arranged on the map.

# Answer
> 0 votes
If I understand you correctly, a minor modification of the *absolute value* should work, where you do digit-wise absolute difference and keep the magnitude:

$$ \sum\_i \left| x\[i\] - y\[i\] \right| \cdot 10^{i} $$

or in Python:

```
def dist(x, y):
    xs, ys = str(x), str(y)
    l = len(xs)
    diff = lambda a, b, i: abs(int(a[i]) - int(b[i])) * 10**(l-i-1)
    return sum(diff(xs,ys,i) for i in range(len(xs)))

```

To illustrate with your examples:

```
dist(111111, 111152) = 41 > dist(111111, 111125) = 14

```

```
dist(111000, 110999) = 1999 > dist(111000, 111001) = 1

```

You say (south v north) that this should be a very large diff, and that it is:

```
dist(123456, 223456) = 100000

```

# Answer
> 0 votes
If your codes have structure, such as a format $abbbccd$ where different letters correspond to different levels in a hierarchy (state/province/county/city/post office or whatnot) you can assign weights to the differences of the respective levels. Then inside a level, the difference could be binary (same or different), or linear (assuming that the numerical values correspond to some "proximity" order) or even nonlinear.

There is no need for the weights to sum to one, as you are comparing values on the same scale.

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Are all non-context-free language infinite?
Are all non-context-free language infinite?

# Answer
> 3 votes
Any finite language is regular, so yes.

---
Tags: regular-languages, context-free, regular-expressions
---


# Question
Title: What is the "shortest path heuristic" for the Steiner problem in graphs?
I keep encountering citations of the following article:

> Takahashi and A. Matsuyama, “An approximate solution for the Steiner problem in graphs,” Math. Japonica, vol. 24, no. 6, pp. 573–577, 1980

For example, Yahui Sun refers to it here as "a widely-used Steiner tree approximation algorithm".

**But... what is the actual algorithm?**

The website of Mathematica Japonica only goes back to 1994, and I can't find the article anywhere else either.

Wikipedia contains this description, but without a citation:

> The general graph Steiner tree problem can be approximated by computing the minimum spanning tree of the subgraph of the metric closure of the graph induced by the terminal vertices. The metric closure of a graph G is the complete graph in which each edge is weighted by the shortest path distance between the nodes in G. This algorithm produces a tree whose weight is within a 2 − 2/t factor of the weight of the optimal Steiner tree where t is the number of leaves in the optimal Steiner tree; this can be proven by considering a traveling salesperson tour on the optimal Steiner tree. The approximate solution is computable in polynomial time by first solving the all-pairs shortest paths problem to compute the metric closure, then by solving the minimum spanning tree problem.

Is this the algorithm that Sun and others refer to?

# Answer
> 3 votes
Let *G* = (*V*, *E*) be our graph, and *S* be the set of vertices that must be in the Steiner tree. Let *t* be the number of leaves in the optimal Steiner tree.

It seems that Takahashi and Matsuyama's algorithm (1980) is indeed the "shortest path heuristic" since it actually uses shortest-path searches. Starting from a single vertex, it simply grows the tree *T* by finding the closest vertex *v* in *S \ T* that hasn't been added yet, and adding the shortest path from *T* to *v* until all vertices have been added, similar to Prim's algorithm for the minimum spanning tree.

The algorithm I cited from Wikipedia, based on the metric closure, is due to Kou, Markowsky and Berman (1981), and boils down to: compute the metric closure, find the minimum spanning tree of the metric closure, turn this back into a subgraph (not necessarily a tree) of the original graph, find the minimum spanning tree of that subgraph, then repeatedly remove leaves that are not in *S*.

I didn't read Gilbert and Pollak (1968) fully (it's mostly about the geometry of Steiner trees in the plane). I presume they did something similar to Kou et al., but without the final pruning step, which might explain why they only got within a factor 2 from the optimal cost, rather than the 2 - 2/*t* by Kou et al..

I made some edits to Wikipedia to record all this, and added a summary of an algorithm by Wu, Widmayer and Wong (1986), which is more efficient and also easier to implement than both of the above, while retaining the same optimality bound.

# Answer
> 0 votes
There is actually an even faster implementation of the metric closure heuristic than that of Wu et. al. See the paper "A faster approximation algorithm for the Steiner problem in graphs" by Kurt Mehlhorn.

# Answer
> 0 votes
The paper originally loacted here:http://www.cs.haifa.ac.il/~golumbic/courses/seminar-2010approx/takahashi80.PDF. But the url is too often down, after too many tries, I finally downloaded it. Now I upload it to my google drive:https://drive.google.com/file/d/1hK7YzECtThnbXcp7MviXM5U7QuaMOsdx/view?usp=sharing.

I think this algorithm is simple and elegant.

Question: A set of $S$ and a root $r$ and you want to build the min-cost tree to connect them together.

Step 1, you pick a vertex $v\_0$ from $S$ and find its shortestpath to $r$ as the first branch of the solution tree.

Step 2, you find the next $v \in S$ with minimum $cost(v,T)$ to the tree, where $cost$ is defined as the smallest length among all the shortest paths to the nodes in the already decided tree. Repeat this until all nodes in $S$ is dealt with.

---
Tags: graphs
---


title: 3-SAT with 3 variable occurences

text:
# Question
Title: 3-SAT with 3 variable occurences
3-SAT with at most 3 occurences per variable is $\mathsf{NP}$-hard.

Now I'll try to solve it using these:

1. Theorem: SAT where all clauses have length 3 and variables occur 3 times, is satisfiable.
2. Double propagation. If there is a clause $(a\lor b)$ and no clause $(\overline a\lor\overline b)$: change all occurences of $\overline a$ by $b$ and $\overline b$ by $a$. Also, remove clause $(a\lor b)$. This will result in two occurences for $a$ and $b$.
3. If there is a pair of clauses $(a\lor b)\land(\overline a\lor\overline b)$, replace occurence (there will be only one) of $b$ to $\overline a$. Remove that pair of clauses. This will result in two occurences of $a$ and no occurences of $b$.

Using this technique we either must get an empty clause or all clauses will have length 3 and formula will be satisfiable. It is also possible that formula will become 2-SAT.

Can this even work?

# Answer
Your second step isn't sound.

Take any unsatisfiable $3$-SAT formula (without restriction on the number of variable appearances) and perform the standard reduction to a formula where each variable occurs at most three times. That is, for each variable $X$ that occurs $k\>3$ times, replaces the occurrences respectively with $X\_1, \dots, X\_k$ and add the new clauses

$$(\overline{X\_1}\lor X\_2) \land(\overline{X\_2}\lor X\_3) \land \dots \land (\overline{X\_{k-1}} \lor X\_k) \land (\overline{X\_k}\lor X\_1)$$

to ensure that $X\_1, \dots, X\_k$ have the same value in any satisfying assignment.

Now, we have the clause $\overline{X\_1}\lor X\_2$ but not $X\_1\lor\overline{X\_2}$ so we can use your second step, taking $A=\overline{X\_1}$ and $B=X\_2$. So we must delete the first clause and replace any instance of $X\_1$ with $X\_2$ and any instance of $\overline{X\_2}$ with $\overline{X\_1}$. This replaces the clauses above with

$$(\overline{X\_1}\lor X\_3) \land (\overline{X\_3}\lor X\_4) \land \dots \land (\overline{X\_{k-1}} \lor X\_k) \land (\overline{X\_k}\lor X\_2)\\,,$$ i.e., $$(X\_1\rightarrow X\_3)\land (X\_3\rightarrow X\_4) \land \dots \land (X\_{k-1}\rightarrow X\_k)\land (X\_k\rightarrow X\_2)\\,.$$

This no longer requires all the the $X\_i$ variables to have the same value. There are formulas that will become satisfiable when you make this transformation.

But, further, we can now apply the transformation again to the clause $\overline{X\_1}\lor X\_3$, resulting in $$(\overline{X\_1}\lor X\_4) \land (\overline{X\_4}\lor X\_5)\land\dots\land (\overline{X\_{k-1}} \lor X\_k) \land (\overline{X\_k}\lor X\_2)\\,.$$ Note that the variable $X\_3$ has completely disappeared and can take any value. Iterating, we see that *all* the clauses relating $X\_1, \dots, X\_k$ disappear!

What have we done? We've taken a formula that mentioned $X$ more than three times and replaced these occurrences with successive new variables $X\_1, \dots, X\_k$, plus the constraint that all these new variables must take the same value. We then deleted all the constraints, so $X\_1, \dots, X\_k$ can take any value at all, independently of each other and, by the way, each of the variables $X\_1, \dots, X\_k$ now only occurs once. So, if we started with an unsatisfiable formula in which every variable occurred more than three times, we end up with a formula where every variable occurs exactly once. That formula is always satisfiable.
> 4 votes

# Answer
You can show a reduction in polynomial time from the standard 3-SAT problem where the number of variable occurrences are unrestricted to the specific version of 3-SAT with utmost three occurrences per variable in order to prove it's NP-Hard. This reduction is explained well in the classic paper by Craig A. Tovey in section-2. As @DavidRicherby explained, this will never become 2-SAT. You are essentially trying to prove P=NP. Please go through this excellent video titled P vs NP and the computational complexity zoo to understand the basics of computational complexity theory as that would help you understand why it's not possible (currently).
> 1 votes

# Answer
Your first statement is wrong: 3-SAT with at most 3 occurrences per variable is **not** NP-hard, in fact it is trivial in the sense that any instance of this problem is satisfiable (see this paper).
> 1 votes

---
Tags: 3-sat
---


# Question
Title: Maximum the result from multiple functions which share an input amount
I have multiple functions as shown in the image. For a fixed x value, I need to distribute it into f, g, and h functions for getting the maximum output (y). In other words, having a fixed x value, find a, b, and c in which these conditions are satisfied:

1. a + b + c = x
2. a \>= 0 and b \>= 0 and c \>= 0
3. f(a) + g(b) + h(c) has max value. Given the functions are continuous and monotonic. How should I write code to find out a, b, and c? Thanks in advance!

# Answer
> 1 votes
As I have not enough reputation yet to comment I just wanted to point out @Yves Daoust's answer is wrong. See my answer on SO for a correct one https://stackoverflow.com/a/74139926/8923995.

Otherwise, here is a counter example to the other answer :

Let f be the red function and g the green one. If x is the blue cross, he tells you to answer f(x), the blue point. But if you pick instead f(a)+g(b) where a and b are the purple crosses, you end up with a better result.

# Answer
> 0 votes
For a given x, determine the largest among f(x), g(x), h(x), let f(x), and fully utilize this function (a = x, b = c = 0).

---
Tags: algorithms, optimization
---


# Question
Title: NP-hard (3-)SAT variant with $n$ clauses and $f(n)$ variables
With the purpose of proving my problem NP-hard, I'd like to reduce from a SAT variant (which of course should remain NP-hard) in which not two parameters are present (typically $n$ clauses and $m$ variables) but only one, so $n$ clauses and $f(n)$ variables, for some function $f$.

I've tried to look up 3-SAT (SAT with exactly 3 literals per clause) with exactly 3 occurrences of a variable, as this would imply I'd have $n$ clauses and $n$ variables which would be perfect. Alas, this paper proves 3-SAT with **at most** 3 occurrences per variable is trivial, including my specific case of exactly 3 occurrences.

All hope is not lost though, as in the same paper, it is proven that 3-SAT with at most $k$ occurrences per variable, with $k \> 3$ is NP-hard. I'm looking into the details of the reduction to see if by chance they have proved the specific case of exactly $k$ occurrences per variable to be NP-hard (which would extend to the general case of at most $k$ occurrences per variable), but wanted to ask this question here while searching:

**Does there exist an NP-hard SAT variant with $n$ clauses and $f(n)$ variables?**

EDIT: the answer is yes, there exists such an NP-hard SAT variant, see this post, so I'd like to modify this question just for the sake of it:

**Does there exist an NP-hard 3-SAT variant with $n$ clauses and $f(n)$ variables?**

(As a reminder, In this post 3-SAT means exactly 3 literals per clause, as opposed to the more common meaning of at most 3 literals per clause, used in the solution for my first question.)

# Answer
> 2 votes
General 3-SAT is reducible to 3-SAT with $n$ clauses and $3n$ variables, as more variables would mean one isn't even present in some clause and can be removed, which can be done linearly.

Conversely it's also equivalent to 3-SAT with $m$ variables and $m(m+1)(m+1)/6$ clauses, as otherwise some clauses would be redundant, and again this can be checked in linear time.

---
Tags: reductions, np-hard, 3-sat
---


# Question
Title: What is the point of Bloom's filter if its false positive rate is so high?
This and this agree that there will be near 100% false positive rate with Bloom's filter should number of elements in the set ($n$) be greater than the number of bits in the filter ($m$).

E.g. if $n=100$, $m=10$ with a single hashing function $k=1$, then we get a probability of false positives worth:

$$\begin{split} p &= \left(1-e^{kn/m}\right)^k\\ &= \left(1-e^{k100/10}\right)^1\\ &= 0.9999546000702375\\ \end{split}$$

I.e. almost every query will be a false positive.

I find this to be useless, as such small filters are meant to reduce set membership queries to a database with much larger number of elements that there are bits in the filter.

In this example ($n=100$, $m=10$), I can achieve a much lower false positives rate if I simply use the first $10$ bits of a cryptographically secure hash function. E.g.

```
for i in 0,1,...,99:
  print(hash10bit(i))

```

where `hash10bit(i)` returns the first $10$ bits of a cryptographically secure hash function, such as ChaCha20, when given $i$ as input. This implies a logarithmic growth in number of bits.

---

***Question:***

So, why would one use Bloom's filter, if simply using the few bits of a cryptographically hashing function does a much better job?

Or is it that I'm missing something fundamental? What is it?

# Answer
> 4 votes
$m$ is the total size of the filter in bits, not the number of bits per entry. With $m=1000$ the formula gives a false positive rate of around 10%, roughly the same as the 1000-bit list of hashes (whose false positive rate is 100/1024 if all hashes are distinct).

With $k=3$ and $m=500$ you get a false positive rate of around 9% at half the size of the list of hashes. The advantage is larger for larger $n$ because the (approximate) false positive rate only depends on $m/n$. E.g., with 1,000,000 items, a list of 10-bit hashes would be useless, but you can still get a 9% false-positive rate at 5 bits per item with the Bloom filter.

# Answer
> 2 votes
No, your proposed scheme with cryptographic hash functions does not do a better job than Bloom filters. Your scheme outputs $10n$ bits, which is way more than $m$ bits. You are comparing a Bloom filter that uses just 10 bits to your scheme, which uses 1000 bits. Obviously those two are not comparable. Obviously a scheme that uses 1000 bits can achieve a far lower false positive rate than a Bloom filter.

Your scheme uses 1000 bits, because it outputs 100 values, and each value is 10 bits long (it is the first 10 bits of a cryptographic hash).

# Answer
> 1 votes
Sure, you can store an approximate representation with only log storage, but the error rate will be insanely high, so it will likely be useless in practice. For instance, one approximate representation is to store the first $\log |\mathcal{S}|$ entries of $\mathcal{S}$.

Note that, at least with the most natural representation, the space complexity of $f$ is $O(|\mathcal{S}| \log n)$, not $O(|\mathcal{S}|)$, since you have to store $\mathcal{S}$ entries and each entry takes $\lg n$ bits to store.

I recommend reading about Bloom filters.

# Answer
> 0 votes
Bloom's filter has a high false positive rate because it only detects whether an element is in the set or not, without providing any information about the position of the element.

However, despite its high false positive rate, Bloom's filter can be very useful in certain situations. For example, if you only need to know whether an element is in a set or not, and you don't need to know its position, then Bloom's filter is a good choice. Additionally, Bloom's filter can be more efficient than other data structures when storing large sets of data.

---
Tags: space-complexity, bloom-filters
---


# Question
Title: Does the halting problem belong to NP class of problems?
On the one hand it does not belong to NP problems because it simply is not solvable and is undecidable and on the other hand it is an NP problem because there are claims that it is NP-hard and therefore can be reduced to NP and is an NP problem.

My question, does the halting problem belong to NP?

# Answer
"NP" means: We could solve this problem in polynomial when the answer is "Yes" and we are given a hint how to solve it. Every problem in NP can be solved (in a very very very long time) by trying all possible hints. But that's not the case here. It is undecidable. No hint would allow you to prove that the answer is "Yes".

On the other hand, it is quite obviously NP-hard. Given a different problem that is in NP, for example the "travelling salesman" problem, I can write a program that systematically generates all possible hints until it finds one that allows to solve the TSP instance. If that program halts, then the answer to the NP problem is "Yes". If it doesn't halt, then the answer to the NP problem is "No". So deciding that the program halts allows us to find the solution to the NP problem. Any problem in NP can be reduced to the question whether my "hint-guesser" halts or not.
> 1 votes

---
Tags: computability, np-hard, np, decision-problem, halting-problem
---


# Question
Title: NP-hard $k$-SAT variant with exactly $\ell$ occurrences per variable
For the purpose of this post, let $k$-SAT be SAT with exactly $k$ literals per clause, as opposed to the more common meaning of at most $k$ literals per clause.

With the purpose of proving some problem NP-hard, I'd like to reduce from a $k$-SAT variant (which of course should remain NP-hard) in which each variable occurs exactly $\ell$ times in the formula.

I've tried to look up 3-SAT with exactly 3 occurrences of a variable, but this paper proves 3-SAT with at most 3 occurrences per variable is trivial, which includes my specific case of exactly 3 occurrences. (In fact, this is the case whenever $k = \ell$.)

All hope is not lost though, as in the same paper, it is proven that 3-SAT with at most $\ell$ occurrences per variable, with $\ell\>3$ is NP-hard. I'm looking into the details of the reduction to see if by chance they have proved the specific case of exactly $\ell$ occurrences per variable to be NP-hard (which would extend to the general case of at most $\ell$ occurrences per variable), but wanted to ask this question here while searching:

**Does there exist an NP-hard $k$-SAT variant with exactly $\ell$ occurrences per variable?**

# Answer
> 3 votes
The problem of deciding the satisfiability of 3CNFs in which each variable occurs exactly 5 times is NP-complete (and even NP-hard to approximate), see Uriel Feige, A threshold of $\ln n$ for approximating Set Cover.

---
Tags: reductions, np-hard, satisfiability, 3-sat
---


title: Does quantum computing imply LPO?

text:
# Question
Title: Does quantum computing imply LPO?
The binary expansion of a given real number can be encoded as an amplitude using the inverse QPE. Together with Amplitude Amplification, I wonder if this could indicate that the (some weakened?) trichotomy of the real numbers is physically effective.

---

I think the crux of the question is that these assumptions that

* "the amplitudes and probabilities in quantum field theory are *fake* complex or real numbers and therefore cannot imply **LPO**"
* "Turing machines can evolve to a pure state that does not-not-stop and is not identical to the any stop state"
* Anti-Markov's principle ...

It is inexplicable in terms of the field equations and which are never observed in experiments.

---

\[1\] **LPO**: Limited principle of omniscience

\[2\] QPE: Quantum Phase Estimation

# Answer
> 1 votes
No, this is not possible. It is known that Turing machines can simulate quantum machines (albeit very inefficiently). If there were a quantum machine that realized LPO then we could simulate it on a Turing machine – but a Turing machine cannot realize LPO, because doing so would give us the Halting Oracle.

---
Tags: logic, quantum-computing
---


title: Context Free Language Twist

text:
# Question
Title: Context Free Language Twist
I am trying to recognize a particular language,

L= {a^n b^k | n\<=k\<=2n}

and according to me it should not be CFL, as i can see two comparision i.e. firstly number of a is compare to keep count less than equal to k, and secondly for count of b that should be less than twice n. My question then how it is still CFL??

Thankyou in advance for sharing your wisdom!! :)

# Answer
If you're using grammars, then this is easy to see: $$S\to aSb\mid aSbb\mid \epsilon$$ That is, each $a$ corresponds to either 1 or 2 $b$'s.

If you're thinking about it from the automata perspective, then a PDA can push to the stack $n$ symbols while reading $a^n$, and then start popping those symbols upon reading $b^k$, with the following change: it may nondeterministically choose not to pop a symbol, but the it moves to a new state from which it must pop a symbol after reading $b$. This ensures that the number of $b$'s that are read is between $n$ and $2n$.
> 0 votes

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


# Question
Title: What are the actual costs $c_i$ in the potential method?
In "Introduction to Algorithms" by Cormen et al. the *Potential Method* is explained. For example, we have the following representation for the amortized costs of the i-th operation with respect to the potential function $\Phi$:

$$\hat{c\_i} = c\_i + \Phi(D\_i) - \Phi(D\_{i-1})$$

The book also states that for each $i = 1,2,...,n$ we let $c\_i$ be the actual cost of the i-th operation.

---

**Question**:

My question is, what exactly are the actual costs ($c\_i$) of the i-th operation? Are this runtime cost, or how can we think of it? How exactly is this determined/measured? Unfortunately, this point remains unanswered to my mind.

Also interesting is the stack example with the push operation, in the book the cost of $c\_i$ is given with 1. This assumption is not justified there, which I find a bit ambiguous (Because otherwise one could have set this arbitrarily high).

For helpful answers/comments I would be very grateful!

# Answer
> 2 votes
The value of $c\_i$ is the runtime cost of an operation. Understand that in doing analysis you can simplify the assignment of runtime cost by focusing only on important aspects. As for your stack example, they might have simplied things and assume that the cost of a push/pop is based on the number of elements processed, ignoring other factors.

Indeed, you are right that you can assign some other value for the cost of a push by being more detailed. Say assign a value of 2 because you count 1 for inserting the element and 1 for updating the top pointer of the stack. This amount of detail might not be necessary since it does not change the overall analysis.

---
Tags: runtime-analysis, amortized-analysis
---


# Question
Title: Which of the following cache designer guidelines are generally valid?
Which of the following cache designer guidelines are generally valid?

1. The shorter the memory latency, the smaller the cache block
2. The shorter the memory latency, the larger the cache block
3. The higher the memory bandwidth, the smaller the cache block
4. The higher the memory bandwidth, the larger the cache block

As per my understanding, 4 stands valid since larger memory bandwidth leads to a large cache block size. However what is the relation between cache block and latency?

# Answer
> 1 votes
None of the guidelines are *generally* valid in the sense of providing strong guidance in the absence of other considerations.

Presumably the intent of the exercise was to recognize that increasing block size is a crude form of prefetching which tends to reduce the number of misses at the cost of wasting memory bandwidth (and cache capacity) when the extra memory data is unused.

When memory bandwidth is abundant, the cost of wasting bandwidth is lower making larger cache blocks less expensive. When cache miss latency is lower the cost of a cache miss is lower, reducing the benefit of prefetching; this reduces the benefit of larger cache blocks.

Lower memory latency also reduces the benefit of a larger cache when performance is limited by latency as is often the case (assuming performance is the primary goal). A smaller cache will tend to favor smaller cache blocks since the prefetching from larger blocks wastes capacity and also increases cache conflict (a larger cache block links the cache way for sub-blocks, so cache replacement is less flexible potentially increasing misses even if all sub-blocks are accessed before eviction, i.e., when the prefetching is accurate).

Since increasing the size of memory requests facilitates increasing memory bandwidth, larger cache blocks can be more attractive for the sake of increasing bandwidth.

Larger cache blocks (memory access chunks) reduce per block metadata overhead. Standard SECDED ECC only adds one bit for each doubling of size (at modest reduced protection) and the per-block size of some metadata (such as directory storage for large-scale cache coherence) is independent of block size.

Larger blocks also reduce tag overhead; for a given capacity doubling the block size halves the number of tags. Tag overhead can be more significant if the tag storage is implemented in a less dense but faster technology than the data storage (e.g., SRAM vs. DRAM) or if tag storage is on the processor chip while data storage is off-chip (adding chips to increase capacity is less expensive than adding area to a chip). (A similar effect is *theoretically* possible if reducing tag overhead reduces chip area just enough to fit on a maximum-sized chip or even to meet a chips per wafer goal, but the benefit of increasing last-level cache capacity by less than 10% is small.)

Since the miss reducing benefits of larger block size can be provided by very slightly more intelligent prefetching, the benefit of larger block size is typically more constrained to increasing memory bandwidth (e.g., GPUs typically have a larger memory fetch block size) and/or reducing tag overhead (from number of tags or metadata per stored byte). A simple adjacent block prefetcher can provide the same effect as doubling block size with the advantage of being able to be turned off when such prefetching seems not worthwile. A next block prefetch would avoid fetching a likely less useful adjacent but lower-addressed chunk (the next in address order chunk is often more likely to be accessed than the previous chunk).

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: How can computers tell where the beginning and end of file/packet/frame headers are?
I'd like to know how a computer can determine the beginning and end of certain file components (attributes, headers, frame/packet/segment headers etc.) when these components can be omitted or added in optionally, *on top of being of variable length*, and how it can even recognise files and protocol packets within an ocean of 1s and 0s at all.

Part of this questions stems from a theoretical about how you'd go about reading binary data from a storage medium that has been physically broken into multiple pieces. **If, say, there was a text file stored within a broken piece, and if a computer could physically read the binary data successfully, could it find the start+end of this text file then read its contents?**

I read over the answers provided in this question and this question, which (from my understanding) explains that data is stored in "blocks"/"sectors"/"clusters" of a minimum size based on the file system, and that the OS needs to know the sector associated with the data it needs (to pull up a file, load a program etc.), and the storage medium controller needs to know where this sector is physically loaded in order to read it and send it up the protocol stack. If there was only one file in each "sector" this would make sense, the OS would just read the sector from start to finish to read the file, and the remaining space left in the sector would be wasted space (all 0s) - the intuitive sense breaks down for me if there are multiple files per sector, though.

The other part of this question stems from the fact that an Ethernet frames (and other protocols, for that matter, I just have a background in Network Engineering, hence why I chose Ethernet for this question) can have varying header lengths - between 14 bytes at base, 18 if a single 802.1Q tag is used, and up to 22 bytes if 802.1ad tagging is used. Including or omitting certain optional headers actually changes the amount of bits a computer has to read when receiving the Ethernet frame (it changes the length of the frame header) - **how would a computer know when to begin reading the Payload after the Source MAC address ends, if the 802.1Q tag between these two fields is optional AND of variable length?**

If this question should be asked as two separate questions, and/or in different Stack Exchange Sites, please let me know.

# Answer
> 2 votes
If you click on the link you provided you'll see that the word 802.1Q is itself a link and when you read that page you'll see that the field uses a special value, a magic number if you like for the first 16 bits.

> Tag protocol identifier (TPID) A 16-bit field set to a value of 0x8100\[b\] in order to identify the frame as an IEEE 802.1Q-tagged frame. This field is located at the same position as the EtherType field in untagged frames, and is thus used to distinguish the frame from untagged frames.

So if the parser encounters this value it knows that it's an 801.1Q header, and if not it interprets the value as an EtherType/Size. Presumably that particular value is not a valid EtherType/Size.

---
Tags: memory-hardware, memory-access, communication-protocols, filesystems, storage
---


# Question
Title: How to index a table for fast intersection?
For example (and this is not my use case), imagine there is a set of 50 000 random natural numbers represented in decimal with 8 digits (in the range 00 000 000 to 99 999 999). We could index the set with an index for each digit position (i.e. an array of pointers to all numbers ordered by their fist digit, another one ordered by the second digit, etc.). Imagine we wanted to know what numbers are in the list with at most 2 digits differing from 01 234 567.

We could start by finding the combinations of positions where the digits could differ. Then, for each combination, we could search the set for numbers with all the digits equal to 01 234 567 except for the 2 digits we chose. While it is fast to find the set of numbers where the first digit is 0 thanks to the index, it is, AFAICT, very inefficient to intersect that set with the set of numbers where the second digit is 1, and it is more efficient to directly check what numbers that start with 0 also match the rest of the condition. This is also not very efficient since it only reduces the search space to around one tenth of the entire set. In this case, we only need to do this search 3 times with 3 different indexes since any combination of 3 positions will never be completely covered by the combination of 2 positions where the digits could differ, but it's still quite slow.

For my use case:

* The number of "digits" is variable but less than 30
* The number of "digits" which can be different can be any number from 0 to the number of "digits"
* There are around 400k "numbers" in total
* The smaller the search time and memory/storage usage, the better.

Is there any way to perform the intersection efficiently? Or is there a more appropriate data structure for indexing the list?

# Answer
The name that I normally use for this is "Hamming distance search".

So... 50,000 numbers isn't that many, and probably the simplest solution is to store them in a trie. Hamming distance search on a trie is extremely easy: you conceptually traverse all paths in the trie, pruning when the Hamming distance between the query and the path exceeds the threshold (2 in your case).

Note that if the key is a number (as it is in your case), each node in the trie represents a *range* of numbers. So if you had a data structure which queries intervals (i.e. it tells you how many numbers are in the set that are between two given query numbers), you can essentially do the same type of search that you would do on a trie. A rank/select index would be appropriate here, but even a sorted array with binary search might be efficient enough on 50,000 numbers.
> 1 votes

# Answer
You haven't listed any constraints on the amount of space used, so a simple solution is to build ${8 \choose 2} = 28$ indices. Each index lets you find whether a number is in the set, based on the value of 6 of the 8 digits. Each index could be stored as a hashtable, that given a 6-digit number (the value of the digits in those 6 positions) tells you whether that number is in the set; or it could be stored as a sorted array, with lookups done by binary search.

This enables fast lookup. Given a 8-digit number like 01234567, you enumerate over all 28 possibilities for the pair of digits that might differ, and look it up in each index. This requires 28 index lookups, which should be very fast.

There are more sophisticated solutions available, e.g., if you have very long strings, but this might be good enough for the parameters you list.
> 0 votes

# Answer
With 8 digits you can probably use a 8-dimensional index where you assign one digit to every dimension. You also need a custom distance function.

Let's assume you want all numbers with 3 differing digits.

On the 8-dimensional index you can perform a nearest neighbor search. This will first return numbers with one differing digit, then all with two differing digits, and so on. You simply discard all numbers with \< 3 differing digits and stops once you you get 4 differing digits. This should give you all number with 3 differing digits.

You need a distance function that works like this:

```
double distance(double[] p1, double[] p2) {
   double sum = 0;
   for (int i = 0; i < p1.length; ++i) {
      if (p1[i] != p2 [i]) {
         ++sum;
      }
   }
   return sum;
}

```

In effect the distance depends only on whether the digit differs, not on how much it differs.

The lookup time should be something like $O(dim * log(n) * r)$ with $n=50000$ and $r$ the result size (=number of matching entries).

Note that there is the "curse of dimensionality", so this approach will become less efficient with increasing dimensionality. You are probably fine with up to 100 digits (=dimensions) or so.
> 0 votes

# Answer
I see that you've edited the question to ask about a more general case. There are two techniques worth knowing about: nearest neighbor search with the Hamming distance, and locality sensitive hashing.

A locality-sensitive hash $H$ is one where, if $x,y$ are close to each other, then there is a good chance that $H(x)=H(y)$. Then you can build several hashtables, each indexed using a different locality-sensitive hash, and containing all 50,000 items in your set; to test whether there is any item in the set near $x$, you look up $x$ in each hashtable using the appropriate hash. In this case, we want "close" to be measured in Hamming distance. There is a very simple locality-sensitive hash function for the Hamming distance. In particular, we pick a random subset of the digit positions; then the hash of a number is the values of the digits in those positions. If two numbers differ in only a few digit positions, then with good probability, they will have the same hash. By repeating this with multiple hashtables, we have an extremely high probability of detecting any match.

I don't know much about data structures for nearest neighbor search with the Hamming distance, but you could do a literature search to see what is known. See also Using k-NN for Exact Match in Hamming Space (after Multi-index Hashing). You might also look at metric trees to see if they can be adapted for your situation.

That said, these problems become very hard if the allowable Hamming distance is large, so don't expect too much if you want to find matches with a large number of digits that differ.
> 0 votes

---
Tags: data-structures, database-theory
---


# Question
Title: Checking if a graph contains a (not necessarily simple) cycle of length more than k
I'm struggling with question 7-38 from Skiena's Algorithm Design Manual:

> Let G be a directed graph. We say that G is k-cyclic if every (not necessarily simple) cycle in G contains at most k distinct nodes. Give a linear-time algorithm to determine if a directed graph G is k-cyclic, where G and k are given as inputs. Justify the correctness and running time of your algorithm.

(For context, this is in the unweighted graphs chapter, so this is an unweighted graph.)

Can anyone give me pointers for where to start? Here are a couple of ideas I've had, but can't turn into a solution:

* I can find any cycle with a DFS, and looking for a back edge. This isn't enough to find a long enough cycle though, as there's no guarantee a cycle just consists of a chain of tree edges and a back edge.
* If I find any cycle $C$ in the graph, I wondered if I could "compress" $C$ down to a single node, with a weight, and then represent this as finding a cycle in a weighted graph. I think this doesn't work, as it's not guaranteed a long cycle either is disjoint, or fully contains $C$. For example, consider a big cycle, plus another node with a triangle off the edge.

Also, is there another name for this property? I found a different definition of $k$-cyclic here - https://mathworld.wolfram.com/k-CyclicGraph.html \- which says a graph is $k$-cyclic when it's a closed walk of length $k$. I can't find another name for Skiena's definition.

Thanks!

# Answer
> 1 votes
Notice that:

* Any (not necessarily simple) cycle in $G$ contains only vertices that belong to a single strongly connected component of $G$.
* Given any strongly connected component $C$ of $G$, there is always a (not necessarily simple) cycle that visits all vertices in $C$.

The problem now becomes the following: do all strongly connected component in $G$ contains at most $k$ vertices? This can be solved by finding all strongly connected components of $G$ in linear time using, e.g., Tarjan's algorithm.

---
Tags: algorithms, graphs, algorithm-analysis
---


# Question
Title: Applying merge sort: Would the value in the box with the red cross be $71$? Does it matter whether we start at the bottom-left or bottom-right?
I have the following diagram showing a case of merge sort:

I am trying to find the value that would be in the box with the red cross when applying merge sort in ascending order.

It seems to me that it would be $71$. If we start at the bottom-right, we have $\[30, 71\]$ for the first array. We then have the sorted arrays $\[24, 30, 71\]$ and $\[49, 97\]$. And then we combine these last two sorted arrays to get $\[24, 30, 49, 71, 97\]$. Therefore, the value in the box with the red cross would be $71$, right? And does it matter whether we start at the bottom-left or bottom-right? The result should be the same, right?

# Answer
You don't need to simulate merge sort to figure out what that value will be. Since you know that mergesort is correct, and you're looking for the 4-th element in that subarray, you just need to find the element with rank $4$ among $\\{71, 30, 24, 49, 97\\}$, i.e., $71$.

This value is independent of the order in which you choose to execute the recursive calls (as long as you execute all the child calls before the parent one).
> 1 votes

---
Tags: algorithms, mergesort
---


# Question
Title: Please check my answer to a pseudocode CASE statement question
This is a pseudocode question in my IGCSE CompSci textbook:

> Use a `CASE` statement to display the day of the week if the variable `DAY` has the value 1 to 7 and an error otherwise.

This is my answer to it:

```
CASE Day OF
    1 : OUTPUT "Monday"
    2 : OUTPUT "Tuesday"
    3 : OUTPUT "Wednesday"
    4 : OUTPUT "Thursday"
    5 : OUTPUT "Friday"
    6 : OUTPUT "Saturday"
    7 : OUTPUT "Sunday"
    OTHERWISE OUTPUT "Day invalid"
ENDCASE

```

Is this answer correct?

(I realise this is a very rudimentary question for a Year 10/11 CompSci class but I’m homeschooled with no teaching guidance whatsoever. So a big cheers to anyone who would take the time to check my answer for me.)

# Answer
This problem is about switch-case statements. So, if you can do a pseudo-code of such a statement with the case being a DAY variable and the steps are clear, that would be correct. So, your answer is totally correct and the steps are clear. There's no one way of doing pseudo code.

```
switch(DAY)
    case 1:
        print("Monday")
    case 2:
        print("Tuesday")
    case 3:
        print("Wednesday")
    case 4:
        print("Thursday")
    case 5:
        print("Friday")
    case 6:
        print("Saturday")
    case 7:
        print("Sunday")
    default:
        print("Invalid Day!")

```

Above is another possible way to a case statement for the **DAY** variable as your question expects.
> 0 votes

# Answer
Speaking in pseudo-code terms, it looks OK. Speaking in syntax terms, as the answer from @Geeth Sandaru looks to be correct. In C/C++ however, you would need `break` statements after each `print` (apart from the last one).

@Apoorv is right though, this might be more suited to stack overflow.
> 0 votes

# Answer
Yes, correct but should be specifying 'break' in every case expect the last one because in the switch case the following statement also gets executed.
> 0 votes

---
Tags: pseudocode
---


title: Inequality about External path length

text:
# Question
Title: Inequality about External path length
First of all LPL is Leaf path length & IPL is internal path length. While i was studying algorithm analysis for average complexity of binary search , i saw that inequality. Before that, i proved by induction for any full binary tree T, LPL(T) = IPL(T) + 2\*I where I is the number of internal nodes . Now after that i tried to understand that inequality but i could not understand the idea.

Some definitions(a bit informal): external path length is the same thing with leaf path length. Leaf path length is the sum of depths of the all leaf lengths, assuming root node has 0 depth. Internal path length is the sum of the all depths of internal nodes. Internal node is a node that has child. In question tree is full binary tree thus all internal nodes have 2 children.

# Answer
> 0 votes
Let $\varphi(L) = L \log\_2 L$ and notice that $\varphi$ is a convex function. Let $T$ be a tree with $L$ leaves. You can show by induction on $L$ that $LPL(T) \ge \varphi(L)$.

If $L = 1$, then $LPL(T)=0 = \varphi(1)$.

If $L\>1$ then let $T\_1$ and $T\_2$ be the left and right subtrees of the root and call $L\_i$ the number of leaves of $T\_i$. Using the induction hypothesis on $L\_1$ and $L\_2$: $$ \begin{align\*} LPL(T) &= L + LPL(T\_1) + LPL(T\_2) \ge L + \varphi(L\_1) + \varphi(L\_2) \\ &\ge L + 2\varphi\left(\frac{L\_1+L\_2}{2}\right) = L + 2 \varphi\left(\frac{L}{2}\right) \\ &= L + 2 \frac{L}{2} \log \frac{L}{2} = L + L(\log L - 1) = \varphi(L). \end{align\*} $$

This completes the proof by induction. Now let $L' = 2^{\lfloor \log L \rfloor}$ and consider the tree $T'$ obtained from $T$ by iteratively deleting two maximally deep leaves that are siblings until the number of leftover leaves is exactly $L'$. Notice that there will be $L-L'$ iterations, that the depth $d$ of the two leaves deleted by each iteration will be at least $1+\log L'$, and that such deletion decreases the value of LPL by at least $2d-(d-1)=d+1 = 2+ \log L'$. Then: $$ \begin{align\*} LPL(T) &\ge LPL(T') + 2(L-L') + (L-L') \log L' \\ &\ge \varphi(L') + 2(L-L') + (L-L') \log L' \\ &= L' \log L' + 2(L-L') + (L-L') \log L' \\ &= L \log L' + 2(L-L') \\ &= L \lfloor \log L \rfloor + 2(L - 2^{\lfloor \log L \rfloor} ). \end{align\*} $$

---
Tags: algorithms, algorithm-analysis, binary-trees, binary-search
---


# Question
Title: How to argue that an $A$-covering matching exists in this bipartite graph?
In lecture the following was mentioned in the context of matchings in bipartite graphs:

> Let $U$ be a finite set and let $\mathcal{S}$ be a family of subsets of $U$. For $u \in U$ let $r(u) := \lvert \\{S \in \mathcal{S} \mid u \in S\\}\rvert$ and let $n := \lvert \mathcal{S} \rvert$ and $N := \sum\_{S \in \mathcal{S}} \lvert S \rvert = \sum\_{u \in U}r(u)$. Assume that $\lvert S \rvert \< \frac{N}{n-1}$ for all $S \in \mathcal{S}$ and $r(u) \< \frac{N}{n-1}$ for all $u \in U$. Then there exists an injective function $f: \mathcal{S} \rightarrow U$ with $f(S) \in S$ for all $S \in \mathcal{S}$.

I recognise that we can represent this as a the problem of finding an $\mathcal{S}$-covering matching in the bipartite graph $G(V,E)$ with $V(G) = \mathcal{S} \uplus U$ and $E(G) := \\{ \\{u,S\\} \mid u \in U, S \in \mathcal{S}, u \in S \\}$. Now I tried induction over $n$. The induction basis is clear, so let us assume as induction hypothesis that there exists a matching covering all of $\mathcal{S}$ for $\lvert \mathcal{S} \rvert = n$. Now to the induction step. We assume that $\lvert \mathcal{S} \rvert = n+1$. In case that $S\_{k+1} \not\subset \cup\_{i=1}^kS\_k$ the claim is clear since there exists one $u \in U,S\_{k+1}$ that is not yet matched. But I do not know what to do with the case $S\_{k+1} \subset \cup\_{i=1}^kS\_k$. I suppose that we somehow need to apply the assumption $\lvert S\_i \rvert \< \frac{N}{n-1}$ for all $S\_i \in \mathcal{S}$ here, but I do not see how. Could you please give me a hint?

# Answer
> 1 votes
The inequality $|S| \< \frac{N}{n-1}$ indeed is very important. Suppose $\mathcal{S} = \\{S\_1, S\_2, …, S\_n\\}$, where $|S\_1| \leqslant |S\_2| \leqslant … \leqslant |S\_n| \< \frac{N}{n-1}$.

* First, $N = \sum\limits\_{S\in \mathcal{S}}|S| = |S\_1| + \sum\limits\_{i=2}^n|S\_i| \leqslant |S\_1| + (n-1)|S\_n| \leqslant |S\_1| + (n-1)\left(\frac{N}{n-1}-1\right)$.

That means that for all $i\in \\{1, …, n\\}$, $|S\_i|\geqslant|S\_1| \geqslant n-1$.
* Now we will use Hall's theorem to prove the result. Suppose $X\subseteq\mathcal{S}$ and distinguish:

+ if $|X| = 0$, then $|N(X)| = 0 \geqslant |X|$;
    + if $1\leqslant |X| \leqslant n-1$, then since $X$ is not empty, it means it contains a certain $S\_i$, and using the previous inequality, $|N(X)| \geqslant |S\_i| \geqslant n-1\geqslant |X|$;
    + if $|X| = n$, then $X = \mathcal{S}$. If $|N(X)| \< |X|$, that means that $|N(X)| = n-1$ and that $S\_1 = S\_2 = … = S\_n$ (all subsets have the same $n-1$ elements $u$). If thats the case, that means that for all $u\in S\_i$, $r(u) = n = \frac{N}{n-1}$, which is not possible given the inequality $r(u) \< \frac{N}{n-1}$.

In all cases, we proved that $|X| \leqslant |N(X)|$. Using Hall's theorem, there exists a matching covering $\mathcal{S}$, which proves the wanted property.

---
Tags: graphs, sets, matching, bipartite-matching
---


# Question
Title: Minimize max subtree weight among spanning trees
Suppose we have an undirected, connected graph $G$ where vertices have positive integer weights. Let $\bar{v}$ be a given vertex in $G$. Take a spanning tree $T$ of $G$ rooted at $\bar{v}$ and define its cost as the maximum total weight among all proper subtrees. (Since weights are positive the proper subtree(s) with maximum total weight will be rooted at children of $\bar{v}$.) Is there an efficient algorithm to determine the minimum cost over all spanning trees $T$?

Some motivation: Imagine vertices are cities, weights are population, edges are roads. Everyone wants to travel to $\bar{v}$. A spanning tree is a way of telling people what path to take. The cost of a spanning tree is the max possible traffic on any one road into $\bar{v}$.

# Answer
This problem is NP-complete. There exists a reduction from the bin packing problem to this problem.

For a set of items $I$ and the number of bins $k$, create a complete bipartite graph of size $k + |I|$. Each left vertex corresponds to a bin and has weight $0$ (or an appropriately small number if strictly-positive weight is required). Each right vertex corresponds to an item and has the item's weight. Finally, a root vertex is added and connected to all $k$ left vertices.

A proper subtree of a spanning tree of the constructed graph corresponds to a set of items packed in a bin. The subtree weight corresponds to the total item weight. A bin packing solution with bin capacity $C$ corresponds to a spanning tree with maximum subtree weight $C$.
> 3 votes

---
Tags: algorithms, graphs, optimization, np-complete, weighted-graphs
---


# Question
Title: Saving Process State by Writing Pages to Blocks
Why don’t operating systems save process state (registers, page tables, pages) by writing state to storage in blocks? Wouldn’t this allow for a seamless restoration of state when the process needs to continue? Specifically, in graphics intensive processes (ie video games), wouldn’t this make load time way quicker?

# Answer
> 2 votes
Operating systems already do that when they need to. See, e.g., https://en.wikipedia.org/wiki/Context\_switch, https://en.wikipedia.org/wiki/Memory\_paging, https://en.wikipedia.org/wiki/Process\_control\_block, https://en.wikipedia.org/wiki/Virtual\_memory.

More specifically, if there is plenty of RAM, there is no need to write anything to storage. You can keep it in RAM, and save registers etc. to RAM, and switch to a different process. Then, when you're ready to switch back, everything is already in RAM. So, operating systems only save to storage (SSD, hard disk, etc.) when necessary, i.e., when they're running out of available space in RAM. Most operating systems today do that via paging, but some older operating systems used swapping.

Some operating systems use hibernation to save the state of all processes to storage/disk when they shut down or go to sleep. This is similar to what you mention, but is done for all processes, not just one process.

---
Tags: operating-systems
---


title: Probability of this random selection

text:
# Question
Title: Probability of this random selection
Suppose we have an array of $n$ integers. Suppose that we pick one of these elements uniformly at random and call it $x$. Suppose that $\log n$ elements are also sampled (uniformly at random) from the $n$-size array and we call $A$ this sampled array. What is the probability that $x$ lies in the middle third of the sorted version of the array $A$?

Initially I thought that this probability was $1/3$, but I think it's more complex than that. I believe that this probability should be $$ \text{Pr}\[x \geq z\]^{\frac{\log n}{3}}\cdot \text{Pr}\[x \leq z\]^{\frac{\log n}{3}},$$ where $z$ is an element sampled from the original size $n$ array. I don't know if this is correct or how to compute these probabilities.

# Answer
> 1 votes
$$ \def\P{{\mathbb P}} \def\E{{\mathbb E}} \def\I{{\mathbb I}} $$

The probability is approximately $\frac 13$. "Approximately" depends on $n$, your definition of "third" (i.e. what to do if $3$ doesn't divide $1 + \log n$), and on whether you sample without or with replacement (and in this case, how you handle multiple appearances of the same element). To give an extreme example, if $\log n = 0$, then the probability is either $0$ or $1$ depending on how you define "in the middle third".

**Intuitively**. Your process is equivalent to the following: sample $\log n + 1$ elements ($A$ and $x$), sort them, choose the random element among them, and ask what's the probability that its position is in the middle third. Clearly, the answer is approximately $1/3$ (the exact answer depends on the clarifications above).

**Formally**. Let's introduce the following notation: $A = (a\_1, \ldots, a\_k)$ and $a\_0 = x$. I assume that $3$ divides $k+1$. I say that the element is in the middle third if the number of elements that are less than it is in range $\[\frac{k+1}{3}, \frac{2k - 1}{3}\]$. Let $C\_i$ be an event that $a\_i$ is in the middle third.

The problem asks about $\P\[C\_0\]$. Since $a\_0, \ldots, a\_k$ are sampled from the same distribution, by symmetry we have $\P\[C\_0\] = \cdots = \P\[C\_k\]$. Let $C\_i$ be the random variable denoting the number of elements less than $x$. Clearly, for any specific sample, exactly $\frac 13$ of $C\_0, \ldots, C\_k$ hold: namely, if $\I$ is the indicator function, then $\sum\_{i=0}^k \I\[C\_i\] = \frac{k+1}{3}$. Using $\P\[C\_i\] = \E\[\I\[C\_i\]\]$, we have: \begin{align\*} \P\_{a\_0,\ldots,a\_k}\[C\_0(a\_0,\ldots,a\_k)\] &= \frac{1}{k+1}\sum\_{i=0}^k \P\_{a\_0,\ldots,a\_k}\[C\_i(a\_0,\ldots,a\_k)\] \\ &= \frac{1}{k+1}\sum\_{i=0}^k \E\_{a\_0,\ldots, a\_k} \I\[C\_i(a\_0,\ldots, a\_k)\] \\ &= \frac{1}{k+1} \E\_{a\_0,\ldots, a\_k} \sum\_{i=0}^k \I\[C\_i(a\_0,\ldots, a\_k)\] \\ &= \frac{1}{k+1} \E\_{a\_0,\ldots, a\_k} \frac{k+1}{3} \\ &= \frac 13 \end{align\*}

---
Tags: combinatorics, probability-theory, probabilistic-algorithms
---


# Question
Title: how to get the high 32-bit of the answer of two 32-bit integer multiple?
Recently, I study the instruction set of riscv32 and face a order as "mulh" which tends to multiply two 32-bits signed integers and store the high 32 value into the register.

And here comes the problem, there are two integer src1 and src2, I want to implement these instruction in C language by using shift operation but failed. So I came to another method which divide src1 and src2 as A(the high 16 bits)B(the low 16 bits) but here appears an another question, how can I know the correct carry number from low 32-bits to high 32-bits, which I came here for help.

# Answer
You are computing

$$(2^{16}A\_1+B\_1)(2^{16}A\_2+B\_2)$$

which is

$$2^{32}A\_1A\_2+2^{16}(A\_1B\_2+A\_2B\_1)+B\_1B\_2.$$

If we decompose

$$A\_1B\_2+A\_2B\_1=2^{16}A\_3+B\_3$$

where $A\_3$ is at most $17$ bits and $B\_3$ is $16$ bits, this turns to

$$2^{32}A\_1A\_2+2^{32}A\_3+2^{16}B\_3+B\_1B\_2.$$

So the carry from the least significant $32$ bits is the carry out of $2^{16}B\_3+B\_1B\_2$.
> 0 votes

---
Tags: algorithms, mathematical-programming, c, instruction-set
---