# Question
Title: Build-Max-Heap: Why Start i at floor(A.length/2) rather than A.length?
Taken from CLRS third edition, a procedure is given for Build-Max-Heap

```
function a = build_MaxHeap(a)
for i = floor(length(a)/2): -1 : 1        // i = n downto 1
     a = max_heapify(a,i);
end

```

My question is why use floor(length(a)/2)? How is it different than using length(a)? Is this the same thing?

```
function a = build_MaxHeap(a)
for i = length(a): -1 : 1        // i = n downto 1
     a = max_heapify(a,i);
end

```

# Answer
It isn't, neither from a complexity nor from a correctness point of view, however, by starting the counter at $n$ you are doing useless work.

Heapify is a procedure that, if invoked on a node $v$ such that the trees rooted in its children are binary heaps, turns the tree rooted in $v$ into a binary heap. Trees that contain only one node are trivially binary heaps, therefore, you may just start running the algorithm from the first non-leaf node: invoking heapify on the leaves wouldn't have done anything, anyway.
> 3 votes

# Answer
There are already some answers, but I wanted to provide a maybe more straightforward explanation.

Inside your `max_heapify` function, you compare the value of the root node (this is the `i` parameter) with the values of its children. The children are located at indices like `2*i+1`, `2*i+2`.

So what happens in `max_heapify` if `2*i`\+ is outside the bounds of the array?

It won't swap anything or continue down the tree at all, it'll likely just be a no-op. So, there's no difference effectively.
> 3 votes

# Answer
In a binary max-heap, each node at a index $\lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \cdots , n$ is a leaf and is thus root of a trivial max-heap.

I am assuming that max-heap representation is like below.

*PARENT($i$)*

1 **return** $\lfloor i / 2 \rfloor$

*Left($i$)*

1 **return** $2i$

*Right($i$)*

1 **return** $2i + 1$
> 1 votes

# Answer
> My question is why use floor(length(a)/2)? How is it different than using length(a)? Is this the same thing?

Since every node at index $⌊/2⌋+1,⌊/2⌋+2,⋯,$ is a leaf node, it is also a root of a subtree max-heap. So no difference.

However, I want to point to another question, perhaps more interesting:

> Why do we go backwards and don't start from 1 up to floor(length(a)/2)?

The answer lies in the assumptions made by `max-heapify` procedure:

```
When it is called, MAX-HEAPIFY assumes that the binary trees rooted at LEFT(i)
and RIGHT(i) are max-heaps, but that A[i] might be smaller than its children,
thus violating the max-heap property.

```

Example: `A = [5, 3, 4, 9, 6, 1, 2]`, if you start from the first element (`5`), it's left subtree (`3->9, 3->6`) is not itself a max-heap. Since the assumption is violated, you're not guaranteed to get correct max-heap data structure if you don't start backwards from the middle.
> 0 votes

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


title: Find shortest path of R,G,B Graph

text:
# Question
Title: Find shortest path of R,G,B Graph
Let $G=(V,E)$ be a directed graph, $ω:E→\mathbb{R}$ a weight function, and $s,t\in V$ a pair of different nodes. It's given that $G$ doesn't have a negative cycle. Each edge has the color R or G or B. Find the shortest path under the condition:

1. we can use green edge after using at least one red edge
2. we can use blue edge after using at least one red edge and at least one green edge.

The shortest path do not have to be colorful.

# Answer
Let's look at the form of the allowed paths. As a regular expression, it looks like:

$$r^\*\ |\ r(r|g)^\*\ |\ rr^\*g(r|g|b)^\*$$

We can test the three cases separately and then choose the shortest path found among the three cases.

The first case is easy: just remove all the green and blue edges and then find the shortest path from $s$ to $t$ as normal. Of course, there may not be a path from $s$ to $t$ in this red-only subgraph; if this happens, we can say the distance for this case is $\infty$.

For the second case, start with the original graph and remove all the blue edges, leaving only red and green edges. Then add a new vertex $s^\prime$, which has a directed edge to each vertex $v$ exactly when there is a *red* edge from $s$ to $v$ in the original graph. Then check for the shortest path from $s^\prime$ to $t$ in this modified graph; this corresponds exactly to the shortest path from $s$ to $t$ in the original graph that has the form $r(r|g)^\*$. Again, if no such path exists, we can return $\infty$ from this case.

See if you can figure out the third case now.

I have asked and answered a more general form of this question here.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: How hard is finding the shortest path in a graph matching a given regular language?
Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some alphabet $\Sigma$. We are also given a description of an NFA $M$ (or DFA, or regular expression) accepting some regular language $L(M) \subseteq \Sigma^\*$, and two vertices $s, t \in V$.

The problem is to find the shortest path in $G$ from $s$ to $t$ whose edge labels form a string that is a member of $L(M)$. That is, we only consider paths $e\_1, e\_2, \dots, e\_k$ where $\ell(e\_1) \ell(e\_2) \dots \ell(e\_k) \in L(M)$.

Can this problem be solved in time polynomial in $|V|$, $|E|$, and $|M|$?

*This question was inspired by these other questions about special cases of this problem.*

# Answer
This problem can be solved in polynomial time by a product construction. Construct the graph $G^\prime$ as follows:

* The vertices of $G^\prime$ are $(V \times M) \cup \\{\\#\\}$, i.e. all pairs of a vertex of $G$ and a state of $M$, together with an extra vertex identified by the arbitrary symbol $\\#$.
* For each edge in $e \in E$ from $v\_1$ to $v\_2$, add an edge in $G^\prime$ from $(v\_1, m\_1)$ to $(v\_2, m\_2)$ with weight $w(e)$ if and only if there is an edge in $M$ from $m\_1$ to $m\_2$ that is labeled $\ell(e)$.
* For each accepting state $m$ in $M$, add an edge in $G^\prime$ from $(t, m)$ to $\\#$ with weight 0.

Then the shortest path in $G^\prime$ from $(s, m\_0)$ to $\\#$ (where $m\_0$ is the initial state of $M$) gives the shortest path in $G$ from $s$ to $t$ matching $L(M)$. There cannot be a negative cycle in $G^\prime$, since dropping the $m$ states from the vertex labels would give a negative cycle in $G$, which we are assuming does not exist.

This also answers the question if $M$ is a DFA or regular expression instead of an NFA, since these can be converted to an equivalent NFA in polynomial time. We can also directly handle NFAs with $\varepsilon$-transitions: if $M$ contains an $\varepsilon$-transition from $m\_1$ to $m\_2$, add an edge in $G^\prime$ with weight 0 from $(v, m\_1)$ to $(v, m\_2)$ for each $v \in V$.

For fixed $M$, the product graph $G^\prime$ has only linearly more vertices and edges than the original graph $G$. This means that any fixed problem of the form "find the shortest path that visits edges in such-and-such order", such as the problems linked in the question, can be solved just as fast as the ordinary shortest path problem asymptotically.

As an implementation detail, note that there is no need to actually write down the whole product graph in memory. The vertices and edges can be generated dynamically while running the shortest path algorithm, which allows unused vertices to be skipped entirely.
> 6 votes

---
Tags: graphs, regular-languages, regular-expressions, shortest-path
---


# Question
Title: Complexity of list coloring $K_n$ with $n$ colors
The list coloring problem is, given a set $L(v)$ colors for each vertex $v \in G$, is there a proper vertex coloring, $c$, of $G$, such that $c(v) \in L(v), \forall v$.

I was wondering, for complete graphs $K\_n$, is list coloring NP-complete? Does this change if $\bigcup\_{v \in K\_n} L(v) = \\{1,2\dots n\\}$?

# Answer
> 3 votes
Consider list coloring the complete graph, where the available colors for vertex $v$ are $L(v)$.

Form a bipartite graph in which the left-hand side corresponds to vertices and the right-hand side corresponds to colors. Connect $v$ on the left-hand side to all colors in $L(v)$ in the right-hand side.

There is a list coloring iff there is a matching saturating the left-hand side. You can decide whether this is the case by running an algorithm for bipartite perfect matching.

# Answer
> 2 votes
To complement Yuval's answer, the problem is solvable in polynomial-time more generally for block graphs which generalize complete graphs and trees. See the algorithm of Jansen \[1\].

On the other hand, the problem (as you probably know) remains NPC for many graphs that are close to being complete in some sense. This includes complete bipartite graphs, complete graphs minus a matching and complete split graphs (see \[2, Table 1\] for an overview).

---

\[1\] Jansen, Klaus. "Complexity results for the optimum cost chromatic partition problem." Universit¨at Trier, Mathematik/Informatik, Forschungsbericht 96–41 (1996).

\[2\] Bonomo, Flavia, Guillermo Durán, and Javier Marenco. "Exploring the complexity boundary between coloring and list-coloring." Annals of Operations Research 169.1 (2009): 3.

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


# Question
Title: A microkernel fully hardcoded in hardware?
Does there exist a (micro-)kernel of an operating system that is fully implemented in hardware? That is, a kernel that is not stored in RAM, and loaded into CPU registers after an interrupt or system call, but is instead a fully hardcoded part of the CPU itself, so that a system call/interrupt never leads to a context switch?

# Answer
> 3 votes
The key search terms here are FPGA and ASIC, since at this point the OS is no longer running on instructions executed by a CPU in the conventional sense.

Here is a relevant result I found with a quick Google search on `microkernel fpga` and `os kernel fpga`:

Susanna Nordström et al. Application Specific Real-Time Microkernel in Hardware.

> In the RTU, the scheduling, inter process communication, interrupt management, resource management, synchronization and time management control are implemented in hardware (using VHDL).

This paper goes a step further and describes an OS-like environment for FPGA programs themselves: Kermin Fleming et al. The LEAP FPGA Operating System.

> Like a software operating environment, LEAP provides both basic device abstractions for FPGAs and a collection of standard I/O and memory management services.

---
Tags: cpu, os-kernel
---


# Question
Title: Regular expression to show that all strings contain each symbol atleast once
I'm studying for my exam and I came across the following exam question from last year, the only way I know how to solve this is build a regex that accounts for all six different series of letters so for example to recognize a string that has the letters a,b and c occur in that order:

$(a+b+c)^\*a(a+b+c)^\*b(a+b+c)^\*c$

The question: Give a regular expression r over the alphabet A = {a, b, c} such that the language determined by r consists of all strings that contain at least one occurrence of each symbol in A. Brieﬂy explain your answer.

# Answer
Your solution looks good to me, and it is probably what they expect of you.

It is interesting to consider the more general question: how large does a regular expression for this language be, as a function of the size of the alphabet? Denoting the size of the alphabet by $n$, Theorem 9 here shows a lower bound of $\Omega(c^n)$ for some (explicit) $c \> 1$. (The theorem is for context-free grammars, but a regular expression can be translated to a context-free grammar.) Your construction is $O(n\cdot n!) = 2^{O(n\log n)}$, so there is a some gap here.
> 5 votes

# Answer
Spelling out the six alternatives in their most symmetrical form:
(a+b+c)\* a (a+b+c)\* b (a+b+c)\* c (a+b+c)\* +
(a+b+c)\* a (a+b+c)\* c (a+b+c)\* b (a+b+c)\* +
(a+b+c)\* b (a+b+c)\* a (a+b+c)\* c (a+b+c)\* +
(a+b+c)\* b (a+b+c)\* c (a+b+c)\* a (a+b+c)\* +
(a+b+c)\* c (a+b+c)\* a (a+b+c)\* b (a+b+c)\* +
(a+b+c)\* c (a+b+c)\* b (a+b+c)\* a (a+b+c)\*
> 0 votes

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


# Question
Title: How can i modify Dijkstra algorithm for equal situation?
I have a question below

In Dijkstra’s Algorithm, if there is more than one possible shortest path from u to any vertex v, any one of the paths can be the output of the algorithms as a shortest path. Assume now that if that is the case for any vertex v, i.e.there are many paths of the same minimum weight, you want to find the path with minimum number of edges. If there are stil ties then they can now be broken arbitrarily. Describe how to modify Dijkstra’s Algorithm to solve this problem

# Answer
> 0 votes
Step 1: Multiply the original weights by a large constant $L$ so that new edge weights are scaled, and become greater than $n$.

Step 2: Add 1 to each edge weight.

Step 3: Run Dijkstra with new weights.

You can test and verify yourself on small examples that this will give the shortest path with minimum edges.

---
Tags: algorithms
---


title: S/Kademlia dynamic crypto puzzle

text:
# Question
Title: S/Kademlia dynamic crypto puzzle
In S/Kademlia two crypto puzzles is used, one static and dynamic. The static is used to generate a key pair that makes an eclipse attack difficult to achieve, the dynamic to make Sybil attacks harder.

In the dynamic, I am very confused about the *x* which is found, since I can’t find any evidence for this ever being used again in the system, is it send along in a signature or what is it used to?

I do not think the paper mentions any use of it, I at least have not been able to find it, why I ask here for the use of *x*.

# Answer
> 1 votes
It's part of the solution to the cryptopuzzle. The goal is to find $x$ that makes $P$ satisfy the criterion; once you've found such an $x$, you can verify that it is a valid solution (and so can anyone else).

---
Tags: computer-networks
---


# Question
Title: Why have quantum circuits won out over quantum Turing machines?
As I understand it, quantum circuits as a model are equivalent to quantum Turing machines, or at least they can be simulated on each other.

So my question is, why have quantum circuits become the chosen implementation rather than quantum Turing machines, such as in the IBM Q?

Is it related to entanglement and reversible gates? I wondered if quantum Turing machines could not take full advantage of entanglement.

# Answer
I've popped up here 7 months too late but in response to the question here's my short-ish answer: Quantum Turing machines are physically unreasonable. Prof. Peter Shor originally wrote his factoring algorithm using a Turing machine and so from a theoretical perspective they work just fine. However, it requires the tape heads to be entangled, which is why you couldn't realistically make it work. The Circuit model (which has been around longer than Turing machines) also has it's own problems which is why Turing needed his machine. One main reason (there are others) is that circuits are designed for a given input size whereas Turing machines are independent of input size. Therefore the circuit model is better suited to quantum computation as it is a more realistic reflection of the devices we could build.
> 1 votes

---
Tags: quantum-computing
---


# Question
Title: Dynamic testing of down casts as explained in TAPL
On page 195 of Pierce's TAPL book, he states that one can replace a down-cast operator by some sort of dynamic type test. Then he gives the following rules:

T-Typetest:

$\dfrac{\Gamma \vdash t\_1:S \\;\\; \Gamma,x:T \vdash t\_2:U \\;\\; \Gamma \vdash t\_3:U}{\Gamma \vdash \text{if } t\_1 \text{ in } T \text{ then } x \to t\_2 \text{ else } t\_3 \to t\_3: U}$

E-Typetest1:

$\dfrac{\vdash v\_1:T}{\text{if } v\_1 \text{ in } T \text{ then } x \to t\_2 \text{ else } t\_3 \to \[x \mapsto v\_1\]t\_2}$

E-Typetest2:

$\dfrac{\nvdash v\_1:T}{\text{if } v\_1 \text{ in } T \text{ then } x \to t\_2 \text{ else } t\_3 \to t\_3}$

There is no further explanation and I'm unaware of how to interpret these rules. Reviewing them, I realize that the first is a typing rule and the second and third are evaluation rules. However, the syntax is a bit strange. What are the arrows in each branch of the if? Why the if includes the `in`syntax?

# Answer
The first rule T-Typetest is a type-checking rule. Let's read it together. Firstly, $\Gamma$ is not important (on a first reading at least). We have the following premises:

1. $t\_1$ has type $S$
2. if $x$ has type $T$ then $T\_2$ has type $U$
3. $t\_3$ has type $U$

The conclusions is, that we get an expression of type $U$ (I think your transcription should have "$: U$" instead of $\to t\_3$ the conclusion): $$\mathrm{if}\\; t\_1 \\;\mathrm{in}\\; T \\;\mathrm{then}\\; x \to t\_2 \\;\mathrm{else}\\; t\_3 \tag{1}$$ The meaning of this expression can be undrstood by looking at the other two rules, which are small-step operational semantics. Here is an incorrect explanation, which we will make correct in a moment:

1. If $t\_1$ has type $T$ then (1) evaluates to $t\_2$ with $x$ replaced by $t\_1$. This is the case of "downcast", i.e., $t\_1$ is downcast from $S$ to $T$, the downcast value is bound to $x$ and then $t\_2$ is executed.
2. If $t\_2$ does not have type $T$ then (1) evaluates to $t\_3$. This is the "default" which we use when the downcast is not possible.

The above explanation is incorrect because we should use $v\_1$ instead of $t\_1$, by which the author is telling you: first evaluate $t\_1$ to $v\_1$, and then perform the downcast.

In an imaginary OO language the same thing might be written somewhat like this:

```
S t1 = ...;
...
if (t1 instanceof T) {
  T x = (T)t1;
  t2;
} else {
  t3;
}

```
> 1 votes

---
Tags: programming-languages, type-theory, type-checking, types-and-programming-languages
---


title: TM1 accepts w1 vs TM1 halts on w1

text:
# Question
Title: TM1 accepts w1 vs TM1 halts on w1
What is difference between following two problems, their decidability and recognizability status:

1. Given Turing Machine TM "accepts" given string w.
2. Given Turing Machine TM "halts on" given string w.

I feel first problem means,

> whether given TM "halts by accepting" given string

and second problem means,

> whether given TM "halts by accepting or rejecting" given string

If I am correct, then is their any difference between their decidability and recognizability status?

For 2nd language, if TM accepts w, then it will eventually halt, but if it does not accept w, then it may keep looping infinitely. Hence its undecidable but recognizable.

I believe 1st problem is subset of 2nd problem and hence it is definitely recognizable. But I am confused about decidability of 1st problem, since it eliminates "halt by rejecting" criteria from 2nd problem. Does that make it decidable?

# Answer
Your intuition is correct in defining the two problems. In fact ***accepting*** also means ***halting*** but *halting* does not necessarily mean *accepting* (it could also *reject*). Remember that when a *Turing Machine* is run on an input it can do three things: *Accept*, *Reject*, *Loop Forever*. In the first two cases the machine stops, in the third obviously not.

As for *decidability*, note that both problems are the ***Halting Problem*** because the first case implies a *halting*, even if it excludes the fact that the arrest is due to *reject*, therefore they are both *undecidable*.
> 2 votes

---
Tags: formal-languages, undecidability, halting-problem
---


# Question
Title: Error lower-bound for an algorithm for vertex cover
I have the following randomized-algorithm for the vertex cover problem. Let $B\_0$ be the output set:

* Fix some order $e\_1, e\_2, . . . , e\_m$ over all edges in the edge set E of G, and set $B\_0 = \emptyset$.
* Add to $B\_0$ all isolated vertices, i.e. the ones without any incident edges.
* For every edge $e$ in $e\_1, e\_2, . . . , e\_m$
    + if both endpoints of $e$ not contained in $B\_0$, then
    + flip a fair coin deciding which of the endpoints to choose, and add this endpoint to $B\_0$.

How can I prove that, for every constant $c \geq 1$, the algorithm might produce a $B\_0$ with $|B\_0 | \ge c|OPT|$?

# Answer
Fix a star graph of $c + 1$ vertices. A star graph is a vertex connected to all other vertices in the graph (a universal vertex called the center), and all other vertices are pairwise **not** adjacent. Here is a visual example. $c$ is the center of the star.

Now an optimal solution is to pack the center of the star. The size of this solution is equal to 1. For each edge, suppose our algorithm packs the other end of the edge (the non-universal vertex), then we need to pack all vertices of the graph except for the center and hence, we need to pack $c$ different vertices. In total we get $|B\_0| = C |OPT|$ for any arbitrary but fixed value of $c$.

---

**Note** A simple modification of the algorithm yields a derandomized approximation algorithm with answer size at most twice as large as the optimum. It goes as follows: if both endpoints of the edge are not in $B\_0$, then add **both** endpoints to $B\_0$ and iterate.

The reason why this works is simple. The edges, who get their endpoints added for a maximal matching and hence, we add twice the number of vertices in a maximal matching to the cover. Note that the size of a matching in a graph is a lower-bound on the size of a minimum vertex cover and hence, we add at most twice many vertices as the size of the minimum vertex cover.
> 1 votes

---
Tags: algorithms, graphs, randomized-algorithms, vertex-cover
---


# Question
Title: Choosing an independent hash function, given hash function value
Supposed we have a function $h:U\to \[m\_1\]$. Given this hash function, can we generate **without using randomization or a universal hash collection** another hash $h':U \to \[m\_2\]$, which depends on $h$ and the values of $h'(x)$ are uniform? i.e., for every value $y\in \[m\_2\]$ we have $\Pr\_{x} (h'(x)=y|h(x)=t)=1/m\_2$ ($x$ is chosen at random).

I know that if $U=\[2^t\]$, $m\_1=2^{n\_1}$, $m\_2=2^{n\_2}$, $t\>n\_1+n\_2$ and $h(x)$ is the first $n\_1$ bits of $x$ this problem is easy: we can select $h'(x)$ to be the bits $n\_1+1$ till $n\_2$ of $x$. My question is how to generalized this approche.

# Answer
From what I have understand from your question, I think you are looking for a way to transform a probability distribution to another probability distribution. For example, if your first hash function distributes your data into a gaussian/normal form into the buckets, then you need a function that takes the index of this bucket as input and gives you another bucket which must be chosen uniformally. This post may be helpful if I ve understand correctly what you are trying to achieve: https://stats.stackexchange.com/questions/223317/how-to-transform-one-pdf-into-another-graphically My personal opinion is that a successful transformation depends a lot in your data. A hash function tries to distribute the data uniformally in the first place. But, even if you have a function G that distributes your data in a "weird" way then you can make a transformation T: G -\> F so that F is whatever distribution you like.

**\[EDIT\]** I don't think that this is achievable **without using randomization**. For example, if you have a hash function that maps all your data into one bin (for example the bin 0) then this function is constant. So, you are trying to create a function that takes a constant value and maps it uniformally, which cannot be done if you don't use any randomness or internal memory. By internal memory, I mean that your function "should remember" what kind of inputs has already "seen", and map them in a different value each time.
> 1 votes

---
Tags: hash, hash-tables
---


# Question
Title: Is "capability-based security" vs "hierarchical-protection-domain based security" a false dichotomy?
The wikipedia page on capability-based security states:

> Capability-based security is to be contrasted with an approach that uses hierarchical protection domains.

However, in order to implement capability-based security, we still need a kernel that ensures that user processes are only able to use the capabilities they have been assigned. Hence we still need a distinction between kernel mode and user mode, which is exactly what hierarchical protection domains are. In fact, as far as I know, most OS'es use only 2 hierarchical protection domains (user and kernel) in practice (I think Windows 10 has domains 0,1,2,3, but that 2 and 3 are only rarely used).

So it seems to me that kernels that implement capability-based security do not make *less* use of hierarchical protection domains than other operating systems.

Isn't it more accurate therefore to say that capability-based security is **one way** of using hierarchical protection domains to achieve security? (rather than fundamentally different from hierarchical protection domains)

# Answer
> 0 votes
No. I don't think that would be a good summary, as it doesn't get to the heart of what I consider important about capability-based systems. Your rephrasing is putting a focus on how the restrictions are enforced, but that is not the interesting part of capability-based models; the more interesting part is how we express our security goals as capabilities, and what advantages and disadvantages such an approach has.

First off, understand that the notion of capability-based security is not a precisely well-defined concept; it's a broad phrase that could cover multiple possible meanings. Different people use that phrase to mean different things. So take everything here with a grain of salt.

I suggest that the best way to understand the phrase "capability-based security" is "a security architecture that relies heavily on capabilities". So, then you need to understand what capabilities are, and why they might be useful.

If you keep reading that Wikipedia article, it contains some explanation of what capabilities are and some ways that they might be useful.

If you want to dive into the details of one particular view on capabilities, I recommend looking at https://en.wikipedia.org/wiki/Object-capability\_model and Mark Miller's PhD thesis. I think you'll find that to have a coherent, principled, and focused view. It's not necessarily what everyone means when they use the word "capability", but it's one take on the subject that is internally consistent and interesting.

---
Tags: operating-systems, security, os-kernel
---


title: Counting big enough elements

text:
# Question
Title: Counting big enough elements
Let $v$ be a vector of positive integers of length $n$. I want to find the highest $k$ such as there are at least $k$ elements of $v$ that are greater or equal to $k$.

What would be the best algorithm for finding $k$?

Examples:

* $v = (1, 2, 3, \ldots, 100) \rightarrow k = 50$, because there are at least 50 elements that are greater or equal to 50 (there are even 51 of those, fifty through a hundred, but that doesn’t matter); but there are only 50 (so—less than 51) elements greater or equal to 51.
* $v = (100, 101, 102, 103, 104) \rightarrow k = 5$, because all five elements are greater or equal to five, and there cannot possibly be six elements greater or equal to six.
* $v = (1, 1, 1, 100, 100, 100) \rightarrow k = 3$

---

Any ideas how to approach this?

My initial idea is this:

* Sort the vector in descending order in $O(n \log n)$
* Starting with the median (it seems, intuitively, as a good place to start), check if a number on a set position $i$ is greater or equal than $i$—since everything to the left of it is greater to equal to it (the vector is sorted), we know there are at least that many elements that are greater or equal to $v\[i\]$.
* Go right or left accordingly to what was found—if we found that there are not enough values greater to $v\[i\]$, let’s try with the smaller-or-equal number, $v\[i+1\]$. If it was big enough, go the opposite direction, checking $v\[i-1\]$.
* Our work is done when there is some $i\_m$ for which the requirement holds, but it doesn’t hold for $i\_{m} + 1$. That would require at most $O(n)$ checks.
* Thus, the slowest part is the sort itself, making the algorithm $O(n \log n)$ total.

I’m curious if this is the best we can do, or can we possibly make it even faster.

# Answer
> 3 votes
You can do it in linear time, using an efficient selection algorithm.

Find the median, and partition the array into numbers below the median and numbers above the median. Check whether the number you're looking for is above or below the median. Then, recurse on the appropriate partition.

The running time satisfies the recurrence $T(n)=T(n/2)+O(n)$, since you can find the median and partition the array in $O(n)$ time. The solution to this recurrence is $T(n)=O(n)$, so the total running time is $O(n)$. This is faster than your $O(n \log n)$ time algorithm.

---
Tags: counting
---


# Question
Title: Are DFAs with a unary alphabet strictly less powerful than DFAs with a binary alphabet?
Are DFAs with a unary alphabet strictly less powerful than DFAs with a binary alphabet? Is this even a meaningful question?

For example, if $\Sigma = \\{\texttt{0}, \texttt{1}\\}$, we can encode any larger alphabet using $\Sigma$, but if $\Sigma = \\{\texttt{0}\\}$, this can define a DFA (that say, recognizes $L = \\{ \texttt{0}^k \mid k \> 0\\}$)... but such a DFA would never be able to recognize more "complex" regular expressions. For example, there is no way to encode $\texttt{0011}$ using a unary alphabet that a DFA would recognize (we could use, say, Godel numbering, but that would require a more powerful machine that could "count").

If DFAs with a unary alphabet less powerful than DFAs with a binary alphabet, is there a name for this language/grammar? I recognize this is kind of an odd question, since the DFA that recognizes $L = \\{ \texttt{0}^k \mid k \> 0\\}$ recognizes all unary languages... but technically there still are a countably infinite number of DFAs in this class ($L = \\{ \texttt{0}^1 \\}$, $L=\\{\texttt{0}^2\\}$, etc.)

Note I am of course assuming that for $\Sigma = \\{ \texttt{0} \\}$, that it does not contain the empty symbol $\varepsilon$.

# Answer
Take the set $A=\\{2^k \mid k \ge 1\\}$. The language $$ L=\\{ \text{bin}(a) \mid a \in A\\} = \\{10^k\mid k \ge 0 \\}$$ is clearly a regular language, whereas $$L=\\{ 1^a \mid a \in A\\} $$ is not regular. Proving the latter is a standard textbook application of the regular pumping lemma.
> 4 votes

# Answer
It appears as if they are indeed less powerful.

Consider the language $L = \\{1 b (0|1)^\* b \mid b \in \\{0,1\\}\\}$ for a binary alphabet.

The language can be recognized by a five-state DFA.

It shouldn't be too hard to show that $L' = \\{0^i \mid i \text{ is the unary encoding of some string in } L\\}$ cannot be recognized by a DFA, as the states reached for some $0^i \neq 0^j$ cannot be merged for $i \neq j$. The basic idea is that a DFA for $L'$ has to keep track of how many digits the word encoded by $i$ and $j$ has already to not forget the second digit. But then merging states for $i$ and $j$ would lose this information.

This is not a formal proof, but it should be a suitable starting point for a formal proof.
> 0 votes

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


# Question
Title: How many RAW dependencies are present in these instructions?
What is the number of RAW dependencies in below set of instructions?

```
I1: R1 = R2 - R3
I2: R2 = R1 + R3
I3: R3 = R1 + R2
I4: R1 = R2 - R2

```

I can see the following RAW dependencies in it:

> $I\_2-I\_1\ for\ R\_1$ ......... (a)
>
> $I\_3-I\_1\ for\ R\_1$ ......... (b)
>
> $I\_3-I\_2\ for\ R\_2$ ......... (c)
>
> $I\_4-I\_2\ for\ R\_2$ ......... (d)

I think taking (a) and (b) implies that (c) has already been included. So, should this be counted as 4 RAW dependencies or 3 RAW dependencies?

https://en.wikipedia.org/wiki/Hazard\_(computer\_architecture)#Read\_after\_write\_(RAW)

# Answer
> 1 votes
TL;DR: According to a 5-stage pipeline scenario, there are just two true RAW hazards:

```
1. I2 to I1 for R1
2. I3 to I2 for R2

```

---

Explanation

The answer might depend on the pipeline stages. For the sake of this question, let's consider a basic 5-stage pipeline: Instruction Fetch (IF), Decode (DE), Execute (EX), Memory Op (MEM) and Writeback (WB).

```
    Instr\Cycle      C1   C2   C3    C4    C5    C6    C7    C8
 ------------------ ---- ---- ----- ----- ----- ----- ----- -----
  I1: R1 = R2 - R3   IF   DE   EX1   MEM   WB1
  I2: R2 = R1 + R3        IF   DE    EX2   MEM   WB2
  I3: R3 = R1 + R2             IF    DE    EX3   MEM   WB3
  I4: R1 = R2 - R2                   IF    DE    EX4   MEM   WB4

```

At first, it may seem like there are many RAW dependencies in this instruction sequence but let's analyze how the pipeline behaves with this sequence. The above table might indicate the following:

1. `EX2` depends on `WB1` (`WB1->EX2`)
2. `EX3` depends on `WB1` (`WB1->EX3`)
3. `EX3` depends on `WB2` (`WB2->EX3`)
4. `EX4` depends on `WB2` (`WB2->EX4`)

After the first stall in the pipeline by `EX2`, the scenario changes a bit. `WB1->EX2` (1) was a true dependency. But, `WB1->EX3` (2) is no more a dependency:

```
    Instr\Cycle      C1   C2   C3    C4    C5    C6    C7    C8    C9    C10
 ------------------ ---- ---- ----- ----- ----- ----- ----- ----- ----- -----
  I1: R1 = R2 - R3   IF   DE   EX1   MEM   WB1
  I2: R2 = R1 + R3        IF   DE    EX2   EX2   EX2   MEM   WB2
  I3: R3 = R1 + R2             IF    DE    DE    DE    EX3   MEM   WB3
  I4: R1 = R2 - R2                   IF    IF    IF    DE    EX4   MEM   WB4

```

After the second stall in the pipeline by `EX3` (3) (which truly waits for `WB2`), the scenario changes again. Clearly, `WB2->EX4` (4) is revealed to be no more a dependency.

```
    Instr\Cycle      C1   C2   C3    C4    C5    C6    C7    C8    C9    C10   C11   C12
 ------------------ ---- ---- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
  I1: R1 = R2 - R3   IF   DE   EX1   MEM   WB1
  I2: R2 = R1 + R3        IF   DE    EX2   EX2   EX2   MEM   WB2
  I3: R3 = R1 + R2             IF    DE    DE    DE    EX3   EX3   EX3   MEM   WB3
  I4: R1 = R2 - R2                   IF    IF    IF    DE    DE    DE    EX4   MEM   WB4

```

Therefore from our original list above, only following true RAW hazards are revealed:

1. `EX2` depends on `WB1` (`WB1->EX2`)
2. `EX3` depends on `WB2` (`WB2->EX3`)

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


# Question
Title: What strategy should I use to sovle this interview problem? May I apply DP on this?
The problem description is as below and it feels like a DP problem but I am not sure, thank you for helping!

You have a certain dose of a drug, say, 200 milliliters, and now some patients need this drug. The doses for each patient may vary from person to person, for example, 2.5 milliliters for A, B, C, 5 milliliters for D, E, and 7 milliliters for F, and so on. The question is, in short, how can you allocate the drugs so that you have the least amount of drugs left? Example input: total drug dose 10 (milliliters). A needs 3, B needs 5, C needs 2, D needs 4, E needs 2. Output: A, B, C or A, B, E (perfect allocation with no drugs left). Note: there may be decimals.

I appreciate any hints or solutions to this problem.

# Answer
This problem is NP-hard. The decision problem, whether a perfect allocation exists, it self is NP-hard. The decision variant is actually the same as the subset sums problem. Given a set of numbers $S$ and a target number $k$, is there a subset of $S$ that sum up to $k$. The problem itself is a variation of the Knapsack problem.

However, the subset sum problem and the knapsack problem are both weak NP-hard problem. Both admit pseudo polynomial dynamic programming solutions (polynomial in the values of the input). So here is a dynamic programming solution for your problem. For each $i \in \\{0, \dots n\\}$, let us define the function $dp\_i : \[M\] \rightarrow {0, 1}$, where $M$ is the sum of all needs of drugs from all patients. Now set $dp\_0(0) = 1$. And for each $i$, we compute $dp\_i$ as $dp\_i(k)$ equals to 1 if and only if there is a subset of the first $i$ patients that need exactly $k$ units. The transitions are as follows: $$dp\_i(s) = \max\\{dp\_{i-1}(s), dp\_{i-1}(s) - \mathrm{need}(i)\\}.$$

An efficient way to implement it is by using bitwise operations on bitsets (a standard trick), where $dp\_i = dp\_{i-1} | (dp\_{i-1}\<\< \mathrm{need}(i))$, where $|$ is logical or-operator and the $\<\<$ is left-shifting.
> 0 votes

---
Tags: algorithms, optimization
---


title: BlockChain: Always get a new Hash

text:
# Question
Title: BlockChain: Always get a new Hash
I am asking a simple question. Why we say that we would always get a new hash in a blockchain? Why we can't have collisions?

One way of collision is that the hard disk becomes full and there is no more space to store a transaction.

Some body please guide me.

Zulfi.

# Answer
Blockchain uses a cryptographic hash function that is designed to have collision resistance. Thus, while it's *possible* you might run into a pair of inputs that produce the same output... it's very very unlikely to happen by chance; and it is believed to be very difficult to intentionally find such a pair of inputs.

Disk space has nothing to do with collisions in the hash function.
> 1 votes

---
Tags: blockchain
---


# Question
Title: Clarifying what it means to be Strongly NP-Complete
Wikipedia defines strongly NP-Complete as:

> A problem is said to be strongly NP-complete, if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the input.

What I interpret this to mean is this:

Let's consider the 3-partition problem, with our numerical paramater being $\sum\_{x \in S} x = B$. Since this problem is strongly NP-Complete, there exists a polynomial $p(N)$, such that if we restrict ourselves to only sets $S$ such that $B \< p(|S|)$, this problem is still NP-Complete. (i.e. finding an algorithm with complexity polynomial in $|S|$ for this restriction would prove P=NP)

Is this the correct interpretation? If so, where could I find upper bounds of such polynomials $p$ for famous problems, such as the 3-partition problem? Also, if I'm not mistaken, this implies that the 3-partition problem is NP-complete in terms of $B$, as well as $|S|$, right?

# Answer
Yes, that's correct. You'll probably have to figure out the polynomial yourself. The way to find the polynomial is to look at the reduction, and from that you should be able to deduce a polynomial.

In your case, I believe there is a reduction from 3D-MATCHING to 3PARTITION, so you would analyze that reduction to find the polynomial. Given an instance of 3D-MATCHING, the reduction explicitly constructs an instance of 3PARTITION whose solution can be used to solve the 3D-MATCHING instance; so you'd analyze how large the parameter of 3PARTITION instance could possibly be, as a function of the size of the set, and that would tell you the polynomial $p$ you are looking for.
> 1 votes

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


title: Integrality gap and LP-rounding

text:
# Question
Title: Integrality gap and LP-rounding
I have a doubt about integrality gap. If I know that there is no integrality gap for a given problem, i.e.:

$$\frac{\mathrm{OPT}(\mathrm{ILP})}{\mathrm{OPT}(\mathrm{LP})} = 1 \text{ (right?)},$$ then, does it have sense to do an approximation-algorithm with LP-rounding? I mean, by definition of $\alpha$-approximation, I know that this is true for an algorithm, in case of minimization problem, that:

$$\mathrm{SOL} \le \alpha \mathrm{OPT}.$$

But since I want to do an approximation with LP-rounding, isn't $\mathrm{SOL}$ equal to $\mathrm{OPT}(\mathrm{ILP})$? This will mean that $\alpha = 1$ (?).

So, if I can design an approximation-algorithm for this given problem, what is the best approximation factor that I can get, given there is no integrality gap?

# Answer
For first question: No, it doesn't make sense. If there is no ratio between OPT(ILP) and OPT(LP-relax) (i.e. integrality gap is 1) which is very rarely to happen (only happen with problem that is in $P$), then this means that you reach the optimal solution for this problem. It is known that LP-relax cannot give the optimal solution for a problem (except for problems in P as I said), and this is why we define integrality gap to see how far it from the optimal solution of the problem (or optimal solution of the ILP).

For second question: Yes, it is true, $\alpha = 1$.

For third question: if you design an approximation algorithm for a given a problem, then I believe you are talking about problem that lies in NP-hard. Then the best factor you hope for max/min problem is 1 (Note that max problem has ratios between \[0-1\], whereas min problem has ratios between \[1,$\infty$)). In reality, all NP-hard problems cannot get a polynomial approximation algorithm with ratio 1 unless P=NP "since ratio 1-approximation algorithm is the same as exact algorithm". So, it should be closer to 1 for both max/min problems but not equal 1.
> 3 votes

---
Tags: algorithms, approximation, linear-programming, integer-programming, rounding
---


# Question
Title: Linear programming: reduce a contstraint that includes minimun
I have an *almost* linear programme. However one of the constraints has a form $z = min(x,y)$ (all the other things are linear in the model). Is there a way to substitute this with something (or introduce additional variables) to turn this into a linear programme?

In other words, I have the problem that looks like the following: $$ \mathbf c' \mathbf x \to \min, $$ s.t. $$ A \mathbf x = \mathbf b,\quad x\_1 = \min(x\_2, x\_3). $$

**Update:** I thought about substituting the constraint with $\min$ to the following pair: $x\_1 \le x\_2$ and $x\_1 \le x\_3$. However, this doesn't work if $x\_1$ has a positive coefficient in $\mathbf c$, which is exactly the case for me. In fact, all the entries are positive in $\mathbf c$.

# Answer
Solve two linear programs. The first has the constraints $$ A \mathbf x = \mathbf b,\quad x\_1 = x\_2 \le x\_3. $$ The second has the constraints $$ A \mathbf x = \mathbf b,\quad x\_1 = x\_3 \le x\_2. $$ Choose whichever solution gives you a smaller value for $\mathbf c' \mathbf x$.

This works for your particular situation. It doesn't scale to a case where you have a large number of $\min$ constraints.
> 3 votes

# Answer
You can use a binary variable z in {0,1}:

x\_1 \<= x\_2 x\_1 \<= x\_3 x\_1 \>= x\_2 - Mz x\_1 \>= x\_3 -M(1-z)

It gives you a PLNE. If you have one min inequality, it's better to use the previous answer.
> 2 votes

---
Tags: optimization, linear-programming
---


# Question
Title: How does $n^c \lg n, 0<c<1$ compare to other common time complexities
Between what two common time complexities would you place $n^c lg n, 0\<c\<1$?

The following table illustrates the common time complexities. Source: wikipedia

# Answer
> 2 votes
$O(n^c \log n)$ is above $O(n^c)$ but below $O(n^{c+\varepsilon})$ for any $\varepsilon \> 0$. This is true for any $c \geq 0$, including $c \< 1$.

For example, $n^{0.5} \log n$ is not in $O(n^{0.5})$ but is in $O(n^{0.500001})$.

This is one of the reasons for the invention of the "soft O" notation $\tilde{O}(n^c)$, defined as the union of $O(n^c (\log n)^d)$ for all $d \geq 0$. Soft O allows you to fudge log factors and focus on the most important part, which is the highest-order polynomial exponent.

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


# Question
Title: How is the set of functions from ${\{a,b\}}$ to $N$ countable?
Assume a set of functions from ${\\{a,b\\}}$ to $N$

Where $N$ is the set of Natural numbers.

Let us assume that the size of $N$ is $n$.
i.e $|N|=n$

The first element $a$ have $n$ choices for mapping.
The second element $b$ have $n$ choices for mapping as well.

So the number of functions = $n.n$ = $n^2$. which is strictly greater than $n$ and hence the size of $N$. So "Set of functions from ${\\{a,b\\}}$ to $N$", should not be countable. But it is. I am just a beginner in discrete maths, so this might be a stupid question for some. But please explain.

# Answer
> 4 votes
You are confusing countable and finite. A finite set is always countable, however a countable set can be infinite.

You only need to find an injection from your set and $\mathbb{N}$, it means that you can identify each element of your set using a natural number (a code if you prefer). For instance you can code the set of functions from $\\{a,b\\}$ to $\mathbb{N}$ using the injection $\alpha$ below:

$\alpha : \mathbb{N}^{\\{a, b\\}} \rightarrow \mathbb{N} : f \mapsto 2^{f(a)}(2f(b)+1)$

# Answer
> 2 votes
Saad Balbiyad's answer is correct. This answer spells out some of the ideas in more detail.

A set is countably infinite if its elements can be paired up with natural numbers so that (a) no elements are paired up with the same number, (b) no element is paired with two numbers, (c) there are no numbers or elements left unpaired. In other words, a set is countably infinite if there is a one-to-one correspondence between the elements of the set and the elements of the natural numbers. In this case, we consider the size (cardinality) of the set to be the same as the size $|\mathbb{N}|$ of the natural numbers.

Consider the set of ordered pairs of natural numbers $(n,m)$. Your intuition that the number of elements in this set is $|\mathbb{N}|\times|\mathbb{N}|$ is correct, but the intuition that this quantity is greater than $|\mathbb{N}|$ is incorrect: we can pair the elements of the set of pairs of natural numbers with the natural numbers according to a one-to-one correspondence.

Think of the pairs as placed in a two-dimensional array extending indefinitely to the right and indefinitely down. At the upper left corner is $(0,0)$, with $(1,0)$ to its right, $(0,1)$ below it, and $(1,1)$ diagonally down and two the right. I think you can figure out how to arrange all of the pairs in this form. (It might be easier to draw the following on paper:) Now consider walking through this array so that no pairs are missed, and none are encountered twice. Start at $(0,0)$ and then go one element to right, then diagonally down-left until you get to the left edge, then down one, then diagonally up-right, then right one, then diagonally down-left, and so on. You are placing all of the pairs in a determinate order with none left out and none considered twice. You can therefore map each pair, as it is encountered, with the next natural number. Thus there is a one-to-one-correspondence between pairs of natural numbers and single natural numbers. These two sets have the same size. (Yes, it's weird that when $n$ is the size of the natural numbers, $n\times n = n$, but infinities are weird. That's life. Or math.)

The size of the real numbers is greater than the size of the natural numbers, however. The real numbers are uncountable; they can't be paired up with the natural numbers without leaving some out (nearly all of them). For more on this, search for "Cantor's diagonal argument". It's not very difficult to understand, it's beautiful, and it's mind-blowing, if you've never encountered the idea.

---
Tags: discrete-mathematics, sets, counting, uncountability
---


# Question
Title: Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)
# The Problem

There is no easy way to get a permutation with a regex.

* **Permutation:** Getting a *word* $$w=x\_1…x\_n$$ ("aabc") to another order, without changing number or kind of letters.
* **Regex:** Regular expression.

## For verification:

# The kind of solution I am searching for

It should have the form:

* »aabc« (or anything else you could use a opening and closing parentheses)
* (aabc)! (similar to (abc)? but with another symbol in the end)
* \[aabc\]! (similar to \[abc\]+ but with another symbol in the end)

## Advantages of these solutions

They are:

* easy
* adaptable
* reusable

# Why this should exist

* Regexes are a way to describe a grammar of a regular language. They have the full power to be any kind of regular language.
* Let's say, regular languages are powerful enough for permutations (proof below) – why is there no easy way to express this?

# So my question is:

* (Why) Is my proof wrong?
* If it is right: Why is there no easy way to express permutations?

# The proof

* Regular expressions are one way to note the grammar of a regular language. They can describe any regular languages grammar.
* Another way to describe any regular languages (that have a finite number of letters within their alphabet) grammar are non-deterministic Automatons (with a finite number of states).

Having a finite number of letters I can create this automaton: (Example. Formal: see below)

**Grammar that accepts permutations of "abbc":**

(sry for numbers on top, maybe someone knows how to make this part looking better)

s -\> ah¹

s -\> bh²

s -\> ch³

h¹ -\> bh¹¹

h¹ -\> ch¹²

h² -\> ah¹¹ (no typo! equivalence)

h² -\> bh²²

h² -\> ch²³

h³ -\> ah¹²

h³ -\> bh²³

h¹¹ -\> bc

h¹¹ -\> cb

h¹² -\> bb

h²² -\> ac

h²² -\> ca

h²³ -\> ab

h²³ -\> ba

**More formal: (using a finite-state-automaton but this could be made with grammar as well)**

* A word q (with finite length) to which any permutation should reach an accepting state.
* X is the finite alphabet.
* Set of states S contains any order of letters up to the length of q. (So the size of S is finite.) Plus one state of "any longer word".
* state transition function d which takes a letter and moves on the state that corresponds to the now read part of the word.
* F is a set of that states that are exact permutations of q.

So it is possible to create a finite-state automaton for accepting permutations of a given word.

## Moving on with the proof

So I have proven that regular languages have the power to check for permutations, haven't I?

So why is there no approach to reach this with Regexes? It's a useful functionality.

# Answer
The fundamental theorems of formal language theory are that regular expressions, regular grammars, deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs) all describe the same kinds of languages: namely the regular languages. The fact that we can describe these languages in so many completely different ways suggests that there's something natural and important about these languages, in the same way that the equivalence of Turing machines, the lambda calculus and all kinds of other things suggests that the computable languages are natural and important. They're not just an artifact of whatever random decisions the original discoverer made.

Suppose we add a new rule for creating regular expressions: if $R$ is a regular expression, then $\pi(R)$ is a regular expression, and it matches every permutation of every string matched by $R$. So, for example, $L(\pi(abc)) = \\{abc, acb, bac, bca, cab, cba\\}$. The problem is that this breaks the fundamental equivalences described above. $L\big(\pi((ab)^\*))\big)$ is the language of strings that contain an equal number of $a$s and $b$s and this isn't a regular language. Compare this with, for example, adding a negation or reversal operator to regular expressions, which doesn't change the class of languages that are accepted.

So, to answer the title question, regular expressions *can't* do permutations and we don't add that ability because then regular expressions wouldn't match regular languages. Having said that, it's possible that "regular expressions with permutations" would also be an interesting class of languages with lots of different characterizations.
> 40 votes

# Answer
> **So my question is:**
>
> * (Why) Is my proof wrong?
> * If it is right: Why is there no easy way to express permutations?

Your "proof" only looked at permutations of single words, which are finite languages.

Every finite language is regular (e.g. just by listing all of the members with a `|` inbetween), but there are infinite regular languages (and those are generally the more interesting ones).

As soon as you get a regular expression (or grammar/automaton) which accepts an infinite language (i.e. an expression with the `*` operator, or an automaton with a loop), your construction doesn't work anymore (you get an infinite grammar/automaton).

The answer by David Richerby provided an example of a regular language whose permutation language is not regular anymore – all such examples are infinite languages.
> 17 votes

# Answer
Let $\Sigma$ be an alphabet of size $n$. A regular expression describing all permutations of $\Sigma$ must have exponential size. This follows from Theorem 9 in Lower bounds for context-free grammars, which gives an exponential lower bound on the much stronger model of context-free grammars (a regular expression of size $m$ can be converted to a context-free grammar of size $O(m)$).

So in some sense, there is no succinct way to specify all permutations of a word.

---

Here is a simple proof for a $\tilde\Omega(2^n)$ lower bound on the size of a regular expression for the language of all permutations of an alphabet $\Sigma$ of size $n$. Since a regular expression of size $m$ can be converted to an NFA with $O(m)$ states, it suffices to give a lower bound on NFAs.

We will use the *fooling set* method, which we now describe. Let $L$ be a language, and let $(x\_i,y\_i)\_{1 \leq i \leq N}$ be a collection of pairs of words such that:

* $x\_iy\_i \in L$.
* If $i \neq j$ then either $x\_i y\_j \notin L$ or $x\_j y\_i \notin L$.

Then every NFA for $L$ contains at least $N$ states. Indeed, consider any NFA for $L$. For each $i$, consider some accepting computation of $x\_iy\_i$, and let $q\_i$ be the state that the NFA is in after reading $x\_i$ in this accepting computation. I claim that $q\_i \neq q\_j$ for $i \neq j$. Indeed, if $q\_i = q\_j$ then a "cut-and-paste" argument shows that both $x\_iy\_j$ and $x\_jy\_i$ are in $L$, contrary to assumption.

Now we can prove the lower bound on NFAs for the language $L\_n$ of all permutations of the symbols $\sigma\_1,\ldots,\sigma\_n$; we assume for simplicity of exposition that $n$ is even. For each subset $S$ of $\sigma\_1,\ldots,\sigma\_n$ of size $n/2$, let $x\_S$ consist of all symbols in $S$ in some arbitrary order, and let $y\_S$ consist of all symbols not in $S$ in some arbitrary order. Clearly $x\_Sy\_S \in L\_n$. Conversely, if $S \neq T$ then $x\_S y\_T \notin L\_n$. This shows that every NFA for $L\_n$ contains at least $\binom{n}{n/2} = \Omega(2^n/\sqrt{n})$ many states.
> 8 votes

# Answer
# Why there is no way to write "permutation of" in Regexes

A permutation of a regular, infinite language (infinite amount of words) is not necessarily regular. Thus, it can't be written as regex.

## Proof

Think of of the language `(ab)*`. (Example inspired by David Richerby.) One of its permutations is `a*b*`. This is not a regular language. qed.
> 0 votes

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


# Question
Title: Dijikstra's algorithm with "hull" value catch
Whilst preparing for the CCC(Canadian Computing Competition), I encountered CCC 2015 Seniors problem 4, linked here.

Anyway, the problem describes a set of vertices(points) numbered from $1$ to $N$, and a set of pathways $1$ to $M$, with pathway $p\_i$ connecting two points $a\_i,b\_i$, taking time $t\_i$. The goal of the problem is to find and print out the minimum time required to get from a specific point of $a$ to point $b$, along the pathways.

This looks like a Dijkstra's algorithm implementation... however there is a catch.

For every such pathway $p\_i$ connecting two points $a\_i,b\_i$, not only is there a time $t\_i$, there is also a hull value $k\_i$. You travel by water along the pathways, and your ship has a hull $K$ to begin with. From point $a$ to point $b$, the sum of the hull values along your chosen pathway must not be greater than $K$, otherwise your ship will sink, i.e the pathway is no longer valid.

For this problem, what I first tried to do was to implement it similar to how a normal Dijikstra's algorithm would be implemented.

This passed $9/15$ test cases on the grader, which I am quite proud of for a first attempt. Time wasn't an issue as it usually was, but I am getting **Wrong Answer**.

I then realised that I cannot just save the minimal hull value for each vertex, as each valid path has a different hull value sum. I have to implement a sort of queue/stack like structure and distinguish between each path.

However, the second I do that, I get codes that score even fewer points than my initial attempt. Time Limit becomes an issue, and I get even more **Wrong Answer** test cases on the practice CCC grader.

I spent two days already on this problem, and don't seem to be making any progress.

Any help will be appreciated.

# Answer
Use the product construction to build a graph on $NK$ vertices and $MK$ edges, where each vertex records both which island you are at and how much hull you have left. Then, use Dijkstra's algorithm on that graph. The graph can be built on the fly and does not need to be constructed explicitly.
> 2 votes

---
Tags: algorithms, graphs, algorithm-analysis, shortest-path, programming-contest
---


title: How does a GPU get data from a CPU?

text:
# Question
Title: How does a GPU get data from a CPU?
From what I’ve read, the CPU has to send the data to the GPU before the GPU can do anything with it. But, if that’s the case, won’t any time saved using the GPU be negated by the time taken to transfer that data? Wouldn’t that kind of defeat the whole purpose of a GPU?

# Answer
It depends. If it's a lot of data and a little bit of computation, yes, there is no net savings. If it's a little bit of data and a lot of computation, no, there is a net savings. It all depends. Normally a GPU is used for situations where the amount of computation time saved greatly outweighs the time to transfer the data -- such as training machine learning models, or rendering complex graphics.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: What are system clock and CPU clock; and what are their functions?
While reading a book, I came across a paragraph given below:

> In order to synchronize all of a computer’s operations, a system clock—a small quartz crystal located on the motherboard—is used. The system clock sends out a signal on a regular basis to all other computer components.

And another paragraph:

> Many personal computers today have system clocks that run at 200 MHz, and all devices (such as CPUs) that are synchronized with these system clocks run at either the system clock speed or at a multiple of or a fraction of the system clock speed.

Can anyone kindly tell:

* What is the function of the system clock? And what is meant by “synchronize” in the first paragraph?
* Is there any difference between “system clock” and “CPU clock”? If yes, then what is the function of the CPU clock?

# Answer
The *system clock* is needed to synchronize all components on the motherboard, which means they all do their work only if the clock is high; never when it's low. And because the clock speed is set above the longest time any signal needs to propagate through any circuit on the board, this system is preventing signals from arriving before other signals are ready and thus keeps everything safe and synchronized. The *CPU clock* has the same purpose, but is only used on the chip itself. Because the CPU needs to perform more operations per time than the motherboard, the CPU clock is much higher. And because we don't want to have another oscillator (e.g. because they also would need to be synchronized), the CPU just takes the *system clock* and multiplies it by a number, which is either fixed or unlocked (in that case the user can change the multiplier in order to over- or underclock the CPU).
> 23 votes

# Answer
The answer provided by @Benjoyo is not accurate. The *CPU clock* can be lower than the *system clock*, at least in microcontrollers.

As seen in this link, the *PIC* microcontrollers have the *CPU clock*, with a rate of $f\_{cy}$ (also called instruction cycle frequency), and the *system clock*, with a rate of $f\_{osc}$ (oscillator frequency).

Physically, what provides the clock "ticks" to the microcontroller is a *crystal oscillator*. The oscillator basically has a crystal (`X1` in the figure below) that when energized vibrates at a constant frequency.

\[image ref\]

The name "oscillator frequency", suggests that $f\_{osc}$ is the input frequency of the microcontroller, that comes from the crystal oscillator. However, $f\_{osc}$ usually refers to a **scaled version of the crystal oscillator frequency**, with PLL. The actual crystal oscillator frequency can be named as `XTFREQ`.

> Fosc is the clock eventually with PLL, so with an 8MHz crystal and 4xPLL you would have an Fosc of 32MHz.

\[quote ref\]

On the other hand, the CPU clock $f\_{cy}$ is obtained by dividing $f\_{osc}$ by 2 as seen in the image below (this depends on the microcontroller).

\[image ref\]

So a more precise statement would be that the "CPU clock can be much higher than the input crystal oscillator clock (`XTFREQ`)". Also, depending on the system the *CPU clock* can actually be lower than the *system clock* (as mentioned above) or higher \[ref\].
> 7 votes

---
Tags: computer-architecture, clocks
---


# Question
Title: Dijkstra shortest path yields unintuitive results
Considering the following nodes with edge weights in red, Dijkstra's shortest path algorithm seems to return incorrect results, at least by the definition of the steps on wikipedia. By those rules, the distance from `0` to `2` will be calculated by passing through `1` instead of `3`.

The final distances (from `0`) would come out to:

`0` -\> 0

`1` -\> 0.2

`2` -\> 1000.2

`3` -\> 0.5

The weights in this case are bi-directional but I don't see a way for information of the connection between `2` and `3` to ever affect the final distance between `0` and `2`. Am I missing something about the limitations of this algorithm on this type of graph or are the steps listed incorrect?

# Answer
> 0 votes
In the wikipedia article you linked, the *final* distance is only computed when the node is visited (step 6). The *tentative* distance is (re)calculated each time to visit a parent of a node, and overwritten if it's smaller (step 3).

So in your example,

1. We visit node 0. We set tentative(1) = 0.2, tentative(3) = 0.5
2. We visit node 1, since it has the smallest tentative distance. We set tentative(2) = 1000.2
3. We visit node 3. Since 0.6 \< 1000.2, we set tentative(2) = 0.6
4. We visit node 2. Its final distance is tentative(2), which is currently 0.6

---
Tags: graphs, shortest-path, weighted-graphs
---


title: Efficient n-choose-k random sampling

text:
# Question
Title: Efficient n-choose-k random sampling
Is there an efficient method of sampling an n-choose-k combination at random (with uniform probability, for example)?

I have read this question but it asks for generations of all combinations, not combinations at random.

I general I'm aware of rejection sampling, however it's very inefficient.

I also came across reservoir sampling, but that appears to be primarily geared towards very large or unknown n. I'm more interested in large but finite n (definitely not large enough to not be able to fit in memory. Well. An n-sized array itself will fit in memory, but the state space of all n-choose-k combinations might not).

Is there any survey/review on this topic? Does Knuth cover random n-choose-k sampling in his TAOCP texts?

Thanks in advance.

**Edit**: To be a bit more specific, a 5-choose-3 space over the string 'ABCDE' would look like this:

\['ABC', 'ABD', 'ABE', 'ACD', 'ACE', 'ADE', 'BCD', 'BCE', 'BDE', 'CDE'\]

(Note: this is combination without replacement). And I want to be able to sample from this space with uniform distribution, using a general algorithm (one that works with arbitrary n and k).

# Answer
Here is the simplest algorithm, which is efficient when $k$ is much smaller than $n$ relatively.

---

Input: two positive integers $n$ and $k$ with $k\le n$
Output: a random permutation of $k$ integers from $1,2,\cdots,n$
Algorithm:

1. Let `arr` be an array of size $n$ and a default value that is not `True`.
2. Let `out` be an empty array.
3. Let `i` be a random integer in $\[0,n)$. If `arr[i]` is not `True`, append `i+1` to `out` and set `arr[i]` to `True`.
4. Go back to 3 unless we have selected $k$ elements.
5. return `out`.

---

If $k\le n/2$, then the algorithm above runs in $O(k)$ average time. For example, if $n=1000$ and $k=50$, it will use the random number generator less than 55 times in average. This is much better the reservoir sampling that will use the random number generator about 1000 times.

---

How to speed up the algorithm if $k$ is not much smaller than $n$?

We will let each element in `arr` be a pair `(i, False)`. After we have selected $n/4$ elemented, we will compactify `arr` by removing the elements whose second entries have been changed to `True`. We will set $n$ to $n-n/4$ and $k$ to $k-n/4$. Repeat the algorithm.
> 4 votes

# Answer
Reservoir sampling solves exactly this problem in $O(n)$ time. When $n$ is really large, but you can calculate the $i$th element just from the index $i$ in $O(1)$ time then you can simulate the sampling by getting the first $k$ elements from a random permutation of $\\{1, \dots, n\\}$ in $O(k \log n)$ time using Sometimes-Recurse Shuffle.
> 2 votes

# Answer
> Is there any survey/review on this topic? Does Knuth cover random n-choose-k sampling in his TAOCP texts?

I first looked at *The Art of Computer Programming* Volume 4A ("Combinatorial Algorithms Part 1"), specifically Section 7.2.1.3 "Generating all combinations" (which comes under Section 7.2.1 "Generating Basic Combinatorial Patterns", itself under 7.2 "Generating All Possibilities"). This is focused on ways to generate *all* the n-choose-k combinations (so it turns out not to be in that section, though you can, for instance, look up how to generate the $m$th of the $\binom{n}{k}$ combinations), but the very first paragraph says "and we learned in Section 3.4.2 how to choose \[combinations\] at random".

This Section 3.4.2 "Random Sampling and Shuffling" is in Chapter 3 "Random Numbers", which opens Volume 2 "Seminumerical Algorithms" of TAOCP. It's a short section, and the very first page has an "Algorithm S" (so outside this section it will be referred to as "Algorithm 3.4.2S"), which is the following (rewriting to the notation here):

* Set $m$ to $0$ (this denotes the number of items we have selected so far).
* For $t$ from $0$ to $n-1$,

+ With probability $p = (k - m)/(n - t)$ (which is the number of items that still need to be selected, divided by the number of items still available to consider), select the current item $t$ (and thus increment $m$).
    + If $m$ is now equal to $k$, we are done: terminate.

This may call the random-number generator up to $n$ times, and in fact on average (see Exercise 5 of that section) will call it $(n + 1) k/(k+1)$ times. If we don't know $n$ in advance, we can use the algorithm on the next page (Algorithm 3.4.2R = reservoir sampling), as you mentioned.

But the section also says "Significant improvements to both Algorithms S and R are possible, when $k$/$n$ \[*in the notation of the question here on StackExchange*\] is small, if we generate a single random variable to tell us how many records should be skipped instead of deciding whether or not to skip each record. (See exercise 8.)", and if you look at exercise 8, it gives the algorithm due to Jeffrey Vitter (incidentally, a PhD student of Knuth), which is more efficient.

Rewriting in current terminology, the algorithm is basically:

* Compute the (random) index $X$ of the first item that will be picked.
* Pick the $X$th item, then repeat for the remaining subproblem (picking $k-1$ items from $n - X - 1$ items).

The details of how to compute $X$ in constant time (if it's worth it) are in that exercise and its solution, which also makes external references to:

1. "Precise details are worked out carefully in *CACM* **27** (1984), 703–718," (Vitter, "Faster methods for random sampling")
2. "and a practical implementation appears in *ACM Trans. Math. Software* 13 (1987), 58–67." (Vitter, "An efficient algorithm for sequential random sampling")
3. "A similar approach speeds up the reservoir method; see ACM Trans. Math. Software 11 (1985), 37–57." (Vitter, "Random sampling with a reservoir")

---

Anyway, regardless of all this, Knuth himself thinks that the best solution is simply rejection sampling (when $k$ is "reasonably large yet small compared to" $n$). Namely:

* We can assume that $k \le n/2$ (otherwise the problem of sampling $k$ items out of $n$ items reduces to that of selecting the $n - k \le n/2$ items that are *not* in the sample).
* Maintain a set $S$ of items we have picked.
* While we have generated fewer than $k$ items (i.e. size of $S$ is less than $k$),

+ Pick one of the $n$ items uniformly at random.
    + If we had already picked it earlier then do nothing, else add it to the set $S$ of picked items.

That's it. (Note that if we don't ensure $k \le n/2$ we might end up needing to try about $n$ times towards the end; see coupon collector's problem).

The remaining question is how to maintain the set $S$. The answer here by John L. suggests using a boolean array of size $n$, which is great if you can afford it. Else you may still be able to use your language library's standard hash set or equivalent. In Exercise 16 of that section and its solution, Knuth describes a way to do it in (on average) $O(k)$ time (specifically, fewer than $2k$ random numbers generated) using $O(k)$ units of memory (in fact, an array of $2k$ integers), using a data structure he calls an ordered hash table. The solution is described tersely there, but it refers to *CACM* **29** (1986), 366–367, which is the *Programming Pearls* column in which Jon Bentley introduced Knuth's "Literate Programming" and has Knuth's 2-page Pascal program for the problem.
> 2 votes

---
Tags: combinatorics, randomized-algorithms, sampling
---


# Question
Title: Textbook for understanding formal grammars
I am looking to understand the Chomsky Hierarchy. I've read some textbooks that *touch* on formal grammars (textbooks on computability, which relate automata to specific sets of formal grammars, notably context-free grammars and regular grammars), but not one that specifically deals with formal grammars as an object.

Is there a good textbook for this?

# Answer
> 5 votes
Probably the most-used textbook today is:

* Hopcroft, Motwani, & Ullman, *Introduction to Automata Theory, Languages, and Computation* (3rd edition).

A couple of other common ones are:

* Sipser, Introduction to the Theory of Computation.
* Linz, An Introduction to Formal Languages and Automata.

And a couple of older ones:

* Michael Harrison, *Introduction to Formal Language Theory*. Many learned from this 1978 classic. Even though it's older, it has the advantage that you can pick up a very inexpensive used copy from online retailers.
* Thomas Sudkamp, *Languages and Machines: An Introduction to the Theory of Computer Science*. It's up to the 3rd edition now, but the first edition was my textbook when I was an undergraduate. The exercises are excellent, but it's light on examples.

---
Tags: formal-languages, formal-grammars, reference-request, books
---


# Question
Title: In the reduction from HALT to ALLHALT, why does the constructed Turing machine loop indefinitely when the inputted Turing machine rejects?
> Let HALT be the language $\\{\langle M, w\rangle : M\text{ is a TM that halts on }w \\}$. Let ALLHALT be the language $\\{\langle M\rangle : M\text{ is a TM that halts on all inputs}\\}$. Use a reduction from HALT to show that ALLHALT is not decidable.

Online (link) I found this (simular) solution:

> $D$ = on input $s$:
>
> * Check that $s$ is of the form $\langle M, w\rangle$, where $M$ is a Turing machine and $w$ is a string over the input alphabet of $M$. If not, reject $s$. Otherwise continue.
> * Define a new machine $M\_2$ corresponding to the pair $M, w$ as follows.
>
> $M\_2$ = on input $v$:
>
> 1. If $v$ is not the same as $w$, halt. Otherwise continue.
>     2. Feed $v$ (meaning $w$ in this case) to $M$ and let $M$ compute on $w$.
>     3. If $M$'s computation on input $w$ halts and rejects $w$, loop indefinitely. If $M$'s computation on input $w$ halts and accepts $w$, halt. Otherwise continue looping like $M$ is doing.
>
> Notice that we've designed $M\_2$ in a clever way so that the result of $M$'s computation on input $w$ is encoded in the halting behavior of $M\_2$. Namely, $M$ accepts $w$ if and only if $M\_2$ halts on all inputs. In terms of language membership, this means that $\langle M, w\rangle$ belongs to Halt if and only if $\langle M\_2\rangle$ belongs to Halt2. In light of this fact, finish the description of $D$'s computation as follows.
>
> * Feed the string $\langle M\_2\rangle$ into the decider $D\_2$.
> * Return $D\_2$'s decision.

I don't understad the point 3: *If $M$'s computation on input $w$ halts and rejects $w$, loop indefinitely.* Why does $M\_2$ need to loop indefinitely?

# Answer
> 1 votes
Because the problem HALT defined in the online source is different from yours. Their HALT is defined as:

\begin{align} \\{ \langle M, w\rangle \mid{} &M\text{ is a Turing machine, $w$ is a string,}\\ &\text{and $M$ }accepts\text{ $w$ after a finite computation}\\} \end{align}

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


title: Phrase generation approaches

text:
# Question
Title: Phrase generation approaches
In generating reports, sometimes there is a need to produce quite involved phrases in one of natural languages given numerical or boolean parameters.

To get a feel of it, it is enough to take a look at convert integers into words or time ago algorithms.

These solutions use (procedural/OO/functional) programming and Turing-complete computations, but the question is, whether there is some declarative approach, or hybrid approach, which can be more generic for this class of algorithms? By hybrid I understand decomposed into preparation phase (calculating or defining all necessary units, tuples and conditions), and phrase generation phase, which works with declarative definitions (some kind of domain-specific language)?

The current approach I see in Open Source projects is like the above-mentioned questions: conditional statements interspersed with string interpolations or concatenations. I guess, there are more optimal ones.

What I am searching for is some right term for the problem. I am sure there is a lot of research on the topic, but I have so far failed to come with good keywords to find suitable theory. This is something in between of constant phrases and arbitrary text generation. Ideally, the declarative part should be something easy for domain experts, like a grammar.

In practice, there is also table-driven approach, but what about theories?

Also found this oldish work A flexible shallow approach to text generation by S. Busemann and H.Horacek, but it goes too fast into too specific cases.

# Answer
I've found a survey on natural-language generation approaches by Albert Gatt, Emiel Krahmer, 2018. According to that, my question is about *linguistic realization*. And the paper mentions three most common ones:

* human-crafted templates
* human-crafted grammar-based systems
* statistical approaches

If I remember correctly, there may also be rules-based NLG systems, which may be overlapping with the grammar-based in the above classification.

And I am sure there may be more approaches.
> 1 votes

---
Tags: natural-language-processing
---


# Question
Title: Structure for getting $| \{ a,b \} \subset S : a+b \le d|$ in O(1)
I am struggling with exercise from the old algorithmic exam:
$d$ is const for the whole structure. Propose a structure for which you can do:

* Init(S) //called only 1 time
* Insert(x, S):: $ S := S \cup \\{x\\}$ in O(log(|S|)
* Delete(x, S):: $ S := S \setminus \\{x\\}$ in O(log(|S|)
* Get(S) = $| \\{ a,b \\} \subset S : a+b \le d|$ in O(1)

I am trying to that with AVL Tree with additional members like number of nodes such that $v.value+u.value \le d$.
Could somebody give me some hint?

# Answer
> 2 votes
It is on the right direction to try some kind of tree augmented with a global counter that stores the number of all unordered pairs of nodes $\\{u,v\\}$ such that $v.value+u.value \le d$.

The kind of tree you are looking for is a balanced (binary) search tree. Being balanced such as an AVL tree, it supports insertion, deletion and lookup of a number with $O(\log|S|)$ time. Being sorted as well, it can also update that global counter in $O(\log|S|)$ time if we can maintain some extra information on each node of the tree.

What should be those extra information? One approach is that each node $v$ will have a member $lcount$ that stores the number of nodes in its left subtree as well as a member $rcount$ that stores the number of nodes in its right subtree.

To simplify the explanation, let us use AVL tree. We will assume all values are distinct; otherwise, we can add a duplicity counter to each node.

Each insertion or deletion involves at most two tree rotations. Each rotation changes the edges between at most several nodes. So we can update all $lcount$ and $rcount$ in $O(\log|S|)$ time.

Before the insertion of node $n$, we should compute the number of nodes whose values are not greater than $d - n.value$, which is one plus the number of nodes to the left of the node $m$, whose value is the greatest but no greater than $d-n.value$. With the insertion of $n$, we will keep the global\_counter intact if there is no such node $m$. Otherwise, letting $ancestor$ be $m$, we will do the following.

```
while ancestor is not null:
  if anc.value < m.value:
    global_counter := global_counter + ancestor.lcount + 1
  ancestor := ancestor.parent

```

The case of deletion is similar to the case of insertion.

Further explanation will be omitted.

---

Thanks to OP, who contributed to this answer.

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


title: File size and screen recording

text:
# Question
Title: File size and screen recording
First and foremost, I would like an academic reference on how screen recording "works." I have tried searching online, but I only get results for the software itself.

Exactly how does screen recording work, and to what extent does the content one records effect filesize? For instance, if I were to record my screen playing an (x) resolution video, would the final output size be proportionally larger? Why or why-not?

If this question is closed, please, I would appreciate a reference, or a better way to phrase it (or a referral to a more appropriate sub-forum). Thanks.

# Answer
Conceptually, screen recording works by taking a screenshot of the screen many times per second. Taking a screenshot works by taking a copy of what is displayed on the screen. To understand how that works, you need to understand how things are displayed on the screen; for that, I recommend reading about framebuffers. The screen capture might then be stored in a compressed or uncompressed format. The file size will be influenced by the resolution of the screen, the length of the video, and what compression is used (if any).
> 1 votes

---
Tags: video
---


# Question
Title: Encoding set of At-Most-One constraints as a MAX-SAT problem
Assume a set of variable $V$ = $\\{v\_1,...,v\_m\\}$.

Given total $n$ at-most-one (AMO) constraints (at most one element in a given set is *true*) set \[of the below form\], over the variable set $V$,

$$ AMO \\, (v\_1, v\_4, \neg v\_6, v\_{10}) \\ ... \\ AMO \\, (v\_2, \neg v\_3, v\_7)$$

```
Problem: Find an assignment to $V$ that maximize
         the number of satisfiable AMO constraint set.

```

I'm unable to represent it as MAX-SAT problem.

Tried so far (Attempt 1): Using hard constraint for each of At-Most-One constraint. This will not work as encoding of $AMO (v\_i,...,v\_w)$ will have multiple clauses for each $AMO$ and all of them have assigned same weight (top weight). A solution to this set may not be the maximal one.

Attempt (2): To fix the above problem, I tried relative clause weight; i.e., for each clause assign weight proportional to size of the clause. This will give preference of assigning satisfying shorter clause. But this do not work in extreme situations like if all clause have same length.

I have experience with SAT solvers but this is my first MAX-SAT problem attempt.

# Answer
The standard way to create soft constraints in MaxSAT is to use label variables:

For each $AMO\_j$ constraint, create a new variable $l\_j$. Then create an unit clause $(\lnot l\_j)$ with weight $1$ and add the literal $l\_j$ to every clause of the standard $AMO\_j$ encoding that contains only hard (infinite weight) clauses.

Now the label variable $l\_j$ acts as a switch: setting $l\_j = true$ will "turn off" the $AMO\_j$ hard constraint, but does not satisfy the unit clause $(\lnot l\_j)$.
> 3 votes

---
Tags: optimization, satisfiability, discrete-mathematics, maxsat
---


# Question
Title: Assume that NP = DTIME(2^sqrt(n)), prove that DTIME(2^sqrt(n)) = DTIME(2^n)
I tried using the padding argument to prove such a thing (as it appeared in Arora's book), but I am not sure how this technique will help me here. I am trying to get to a contradiction to the Time Hierarchy Theorem.

After the assumption, I want to prove that $\mathsf{NP} = \mathsf{DTIME}(2^{n})$.

The first case $\mathsf{NP} \subset \mathsf{DTIME}(2^{n})$, is trivial.

For the second case, let $L \in \mathsf{DTIME}(2^{n})$ and $M$ be a deterministic TM that can decide it, let $$L\_{\mathrm{pad}} = \left\\{\left\langle x,1^{2^{\sqrt{|x|}}} \right\rangle : x \in L\right\\}.$$ I am not sure how, using $L\_{\mathrm{pad}}$, I can reach a conclusion that $\mathsf{NP} = \mathsf{DTIME}(2^{n})$, I feel like I am missing something and that my method is not in the right direction, or it is lacking an extra detail.

# Answer
It is enough to pad a special delimiter (say a comma) and $(|x|^2-|x|-1)$ 1's. Suppose $L\_\mathrm{pad}= \left\\{\left\langle x,1^{|x|^2-|x|-1} \right\rangle : x \in L\right\\}$. Since $L\in\mathsf{DTIME}(2^n)$, there is a TM that can determine whether $x\in L$ in $O(2^{|x|})$ time. We then construct a new TM: given a string $y$, it first checks whether $y$ has the form $\left\langle x,1^{|x|^2-|x|-1} \right\rangle$, then simulates $M$ on $x$. This new TM determines whether $y\in L\_\mathrm{pad}$ in $O(2^{|x|})=O\left(2^{\sqrt{|y|}}\right)$ time, so we have $L\_{\mathrm{pad}}\in \mathsf{DTIME}\left(2^{\sqrt{n}}\right)$, thus $L\_{\mathrm{pad}}\in\mathsf{NP}$ by your assumption. This means there exists a non-deterministic TM $M'$ that decides $L\_{\mathrm{pad}}$ in polynomial time. Hence, we can construct a new non-deterministic polynomial-time TM that decides $L$ by first padding a comma and $(|x|^2-|x|-1)$ 1's to the input then simulating $M'$, which means $L\in\mathsf{NP}$.
> 1 votes

---
Tags: complexity-theory, turing-machines, time-complexity, np, complexity-classes
---


# Question
Title: Why are not programs already in binary code?
First of all, please forgive me if this question shows ignorance on my behalf. What I'm asking is not why we don't program in languages written in binary code, I know the answer for that. What I would like to ask instead is: considering all information we input into a computer is registered as binary code, and all data is stored in binary code, are not common programming languages already binary code, and what we see as instructions or variables just a translation? If that is so, why are assemblers or compilers necessary?

# Answer
> 2 votes
The short answer to your question is "for productivity and portability".

Let me expand on this. The very first generation of computers were indeed programmed directly in binary, either by entering each binary instruction using physical switches on the computer itself or by some simple bulk loading mechanism such a reading and loading instructions from a paper tape. This was first generation programming (although at the time it was just called "programming").

Programmers soon realised that it would be simpler and quicker to write programs use mnemonics instead of binary instruction codes. So instead of having to remember or look up the binary code for "load the next byte into register A", they could use the mnemonic "LDA". Translating mnemonics into binary instructions required a program called an assembler. Once someone had invested the time and effort into writing an assembler on a particular computer, programs could be written in mnemonics or "assembly language". This was much quicker than working out all the binary codes for yourself, and it also made it much easier to debug and update programs. This was second generation programming.

As more and more programs were written on different machines, programmers realised that the underlying concepts of programming were similar, regardless of which type of computer the program was being written for. Programmers would be even more productive if they could use a language that implemented concepts like variables, loops, case statements and sub-routines. It would also be convenient to be able to write complex instructions like "print the following string of characters to the screen" or "multiply A+1 by B+2, divide the result by C and store the final result in a variable called D" in one line of code instead of multiple assembly language instructions. So programmers invented higher-level languages such as FORTRAN and BASIC (and eventually C and Java) and wrote compilers and interpreters which would translate code written in a higher level language into assembly language instructions or directly into binary instructions. Not only did this make programmers even more productive, but also by creating compilers for different types of computer, the same FORTRAN program could be translated and run on different computers. So programs became portable and programmers did not have to learn lots of different different assembly languages. This was third generation programming.

Mainstream development in programming languages and computer architectures have continued in this direction, with more and more layers of abstraction between the languages that programmers write in and the machine code instructions that a CPU executes directly. Programming languages have become more specialised, with languages specifically designed for implementing user interfaces; processing data in large databases; creating management information reports; running simulations; processing graphics; developing video games etc. Developments in computer architecture design have concentrated on running a relatively small, simple and general set of machine code instructions more rapidly. Increasing CPU speeds and falling memory costs mean that it is more cost effective to translate each line of high level language into hundreds of machine code instructions than it would be to develop more complex CPUs that could execute higher level language code more directly.

# Answer
> 1 votes
You ask a good question. Why doesn't a CPU just execute say C++ directly? Why go to the trouble of translating it first (i.e. compiling or interpreting) into some arcane machine language (Intel x86)?

The answer is all to do with flexibility. Computer hardware architectures are designed to be able to execute a broad range of programs. To enable this flexibility there needs to be a kind of lowest common denominator - a common language to execute all those different programs.

The biggest hurdle to flexibility is that hardware is fixed in terms of operation. This means that the possible range of instructions it can execute is fixed. Yes, you could have a system whereby a microcoded CPU is reprogrammed on the fly, but there would still need to be a core set of immutable instructions that could do the re-programming.

Once you have have a fixed set of instructions, there's no possibility for upgrade or bug fixing and so on. You would have to release new hardware for every upgrade. This does happen, but constantly upgrading hardware is expensive. In other words for every new release of say the C++ standard, you would need a new C++ CPU and hardware. And for every different type of language you would need a different processor: a Pascal or C or Erlang processsor.

Of course, the way to improve the flexibility of a fixed instruction set architecture is to use emulation. Turing said that all computing machines are equivalently powerful (i.e. can run the same programs), as long as they can be made to emulate a Turing Machine. This is called Turing Completeness.

This means that one language (as long as it is Turing Complete) can emulate another language without loss of fidelity. The consequence being that all languages can be emulated by a generic CPU no matter what instruction set architecture it has, as long as it is Turing Complete.

So in practice the CPU instruction set is chosen so that it most closely fits the hardware model (bits and bytes) and then languages (C++ etc.) are emulated by it principally through a translation process (either compilation or interpretation). This gives you the most bang for your buck. You can upgrade and tweak and bug fix your translator to your heart's content and all the time keep the same hardware.

In practice this works both ways, hardware is made so that it is backwards compatible, so even new hardware can run older languages. It's win win.

But. My own personal opinion is: why not have a C language CPU? The whole world runs on C right? Compilers would then be very simple, but CPUs orders of magnitude more complex. Software is cheap, hardware is not.

# Answer
> 0 votes
Though the programs are in binary code, they are not still in the form of most basic operations that a CPU's logical unit can perform. The assemblers and compilers would remove the for loops, functions, etc that is our way of interpretation, and convert the code into one that comprises of more fundamental operations. These can then be processed by the logical unit of CPU.

# Answer
> 0 votes
That would be akin to reading a natural language in another with the same character set, "Hello" is meaningless in Italian even though the letters are in the Italian alphabet. Interpreting the code as we see it with English words and mathematical symbols into CPU instructions is meaningless for the CPU.

---
Tags: programming-languages
---


# Question
Title: maximum coverage version of dominating set
The dominating set problem is :

> Given an $n$ vertex graph $G=(V,E)$, find a set $S(\subseteq V)$ such that $|N\[S\]|$ is exactly $n$, where $$N\[S\] := \\{x~ | \text{ either $x$ or a neighbor of $x$ lies in $S$}\\}$$

My question is if the following (new problem) has a definite name in literature, and if not what should be the most appropriate name.

> **New Problem:** Given an $n$ vertex graph $G=(V,E)$ and an integer $k$ , find a set $S(\subseteq V)$ of size $k$ such that $|N\[S\]|$ is maximized.

For the second problem, some of the names I have seen in the literature are maximum-graph-coverage; partial-coverage; k-dominating-set, (however, the exact same names are also used in other contexts).

# Answer
The problem in which you must select $k$ vertices to maximize the number of vertices dominated is known as the *budgeted dominating set problem*. The problem or its connected variant is studied at least by Lamprou, Sigalis and Zissimopoulos \[1\] and Khuller, Purohit and Sarpatwar \[2\]. It also appears in the recent survey of Narayanaswamy and Vijayaragunathan \[3\].

---

\[1\] Lamprou, Ioannis, Ioannis Sigalas, and Vassilis Zissimopoulos. "Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination." arXiv preprint arXiv:1907.06576 (2019).

\[2\] Khuller, Samir, Manish Purohit, and Kanthi K. Sarpatwar. "Analyzing the optimal neighborhood: Algorithms for budgeted and partial connected dominating set problems." Proceedings of the twenty-fifth annual ACM-SIAM Symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2014.

\[3\] Narayanaswamy, N. S., and R. Vijayaragunathan. "Parameterized Optimization in Uncertain Graphs—A Survey and Some Results." Algorithms 13.1 (2020): 3.
> 5 votes

---
Tags: graphs, np-complete, terminology, np-hard, set-cover
---


# Question
Title: does a non-terminated string count as a token in c?
so, I am preparing for an exam which includes lexical analysis from compiler design. I was wondering what is the number of tokens in the following code-

```
int main() {
  /* comment
  printf("Hello */ There ");*/
  return 0;
}

```

so, I am thinking upto first "\*/" it will be a multiline comment, so, after "there" a string will start without terminating. will the last string is counted as a token?

# Answer
> 4 votes
No, in C unterminated strings are not tokens. The C language definition precisely describes what a token is; among other things, they include (complete) string literals and a fallback category of "single non-whitespace characters" which are not otherwise matched by the lexical grammar. This latter category does not, however, include `"` and `'` characters; if these characters are not matched as part of a longer token, the result is specifically flagged as undefined behaviour.

So your text is invalid precisely because it cannot be divided into tokens. A conforming implementation must respond by providing at least one diagnostic message.

All of the above is specific to the C language standard. It is not a "principle of computation" and should not be applied to any other programming language.

---

For additional precision, the C standard defines two categories of tokens. Initial program text analysis (in phases 1 and 2) splits the text into *preprocessing tokens* and whitespace (whitespace includes comments, which are not tokens). The translation process then passes the stream of preprocessing tokens through phases 3 to 6, commonly known as "the preprocessor" although it is an integral part of program translation.

Preprocessing leaves most tokens intact but there are features which allow adjacent tokens to be fused or converted into a string literal token. Also, macros may ignore their arguments causing those tokens to vanish. It is not possible to split a token into multiple tokens.

In phase 7, the preprocessing tokens which survive preprocessing must be converted to *tokens*. Although this is described as a conversion, no textual modification is made; what is converted is the category of the token. Not every character sequence which qualified as a preprocessing token can be treated as a token; phase 7 conversion of such a token will fail and a diagnostic message will be produced.

So it can make sense to talk about an "illegal token" (`@`, for example) which is still a token. But unterminated string and character literals do not all into that category. They really are not tokens at all.

See §5.1.1.2 of the C standard for a precise description of the translation phases. Tokens are defined in §6.4, which includes the prohibition on unmatched `"` and `'` in paragraph 3:

> A *token* is the minimal lexical element of the language in translation phases 7 and 8. The categories of tokens are: keywords, identifiers, constants, string literals, and punctuators. A preprocessing token is the minimal lexical element of the language in translation phases 3 through 6. The categories of preprocessing tokens are: header names, identifiers, preprocessing numbers, character constants, string literals, punctuators, and single non-white-space characters that do not lexically match the other preprocessing token categories. If a `'` or a `"` character matches the last category, the behavior is undefined.

---
Tags: compilers, c, lexical-analysis
---


# Question
Title: Proof for clustering in a network of friendship
Consider an undirected graph $G = (V, E)$ representing the social network of friendship/trust between students. We would like to form teams of three students that know each other. The question is to decide whether the network allows for enough such teams, without checking all the triples of graph $G$. For this reason, we use random sampling to design an efficient estimator of the number of connected triples. We partition the set of node triples into four sets $T\_0, T\_1, T\_2$, and $T\_3$. A node triple $v1, v2, v3$ belongs to

* $T\_0$ iff no edge exists between the nodes $v1, v2$, and $v3$,
* $T\_1$ iff exactly one of the edges $(v1, v2)$, $(v2, v3)$, and $(v3, v1)$ exists,
* $T\_2$ iff exactly two of the edges $(v1, v2)$, $(v2, v3)$, and $(v3, v1)$ exist,
* $T\_3$ iff all of the edges $(v1, v2)$, $(v2, v3)$, and $(v3, v1)$ exist.

$|T\_3|$ denotes the number of connected triples in the graph that is the quantity we need to estimate. Consider the following algorithm:

• Sample an edge $e = (a, b)$ uniformly chosen from $E$

• Choose a node $v$ uniformly from $V \ {a, b}$

• if $(a, v) ∈ E$ and $(b, v) ∈ E$ then $x = 1$, else $x = 0$

Show that $|T1| + 2|T2| + 3|T3| = |E|(|V | − 2)$

Any solution?

# Answer
> 1 votes
To prove the euqality : Let e=(v,w) be an of the graph G=(V,E), to construct a triple with "e" you can choose any vertex from "a" in the set V{v,w} this will give you either a triple in the set T1 or T2 or T3. This is the algorithm explained in your text, For every "e" edge in E, 3 cases are possible :

1- (a,e)=(a,v,w) in T1 =\> we will count it one time.

2- (a,e)=(a,v,w) in T2 =\> we will count it twice, first time with the edge e and the vertex "a", second time when we will choose one of the possible edges (a,w) (or (a,v)) (only one exist because (a,e) is in T2) with the vertex v (or respec w).

3- (a,e) in T3 =\> we will count it 3 times like the previous case.

The number of triples generated by this algorithm is : |E|(|V|-2) because of every edge we test all possible |V|-2, the triples in T1 will be generated one time, in T2 two times, in T3 3 times due to the 3 possibles options showen before. Thus the equality : |T1|+2|T2|+3|T3|=|E|(|V|-2)

I hope it was usefull :D

---
Tags: algorithms, graphs, clustering
---