# Question
Title: Complexity of zero-one loss vs logistic loss functions
In *Machine Learning: The Basics*, Alexander Jung, Spinger, the author states that using the zero-one loss function defined by:$$\mathit{L}((\mathbf{x}, y), h)= \begin{cases} 1, y \ne \hat{y}\\ 0\ otherwise, \end{cases}\\ (with\ \hat{y}=1\ for\ h(\mathbf{x}) \ge 0, and\ \hat{y} = −1 \ for \ h(\mathbf{x})\lt0). $$

results in computationally challenging problems and the *logistic loss* is a computationally attractive alternative.

However, consider(ing) that the logistic function defined as follows:

$$L((\mathbf{x}, y), h) := log(1 + exp(−yh(\mathbf{x}))),$$

I don't see any "disadvantages" of the zero-one loss in terms of computational efficiency. To my understanding, for each training example (or instance), the zero-one loss function needs only 2 operations (1 comparison and 1 assignment) and it's done. Meanwhile with the logistic loss, it's a bunch of operations (1 multiplication and exponentiate with base *e* and then 1 addition, and taking log). And not only the number of operations is larger the complexity of those operations is also higher.

Can someone help to point out what I'm missing here?

# Answer
> 3 votes
Training is a crucial step of machine learning, where You take Your model (hypothesis) and find values for its parameters such that it fits Your training data well enough. The error between model and data is measured by a loss function. Training boils down to minimizing the loss function with respect to the parameters. It is a mathematical optimization problem.

The most efficient optimization algorithms are all gradient-based. The gradient of the zero-one loss function (w.r.t. its parameters) is zero for almost all inputs, making it useless for gradient-based optimization. The logistic loss function, on the other hand, is continuously differentiable and very well suited for gradient-based optimization.

You are absolutely right that the logistic function is computationally more expensive, but gradient-based optimization (usually) requires much fewer iterations than any evolutionary algorithm, which makes training with the logistic loss function faster in the end.

---
Tags: complexity-theory
---


# Question
Title: Uniquness of a graph. Why do we need to add e1 to B to create a cycle?
If each edge has a distinct weight then there will be only one, unique minimum spanning tree. This is true in many realistic situations, such as the telecommunications company example above, where it's unlikely any two paths have exactly the same cost. This generalizes to spanning forests as well.

Proof:

1. Assume the contrary, that there are two different MSTs A and B.
2. Since A and B differ despite containing the same nodes, there is at least one edge that belongs to one but not the other. Among such edges, let e1 be the one with least weight; this choice is unique because the edge weights are all distinct. Without loss of generality, assume e1 is in A.
3. As B is an MST, {e1} ∪ B must contain a cycle C with e1.
4. As a tree, A contains no cycles, therefore C must have an edge e2 that is not in A.
5. Since e1 was chosen as the unique lowest-weight edge among those belonging to exactly one of A and B, the weight of e2 must be greater than the weight of e1.
6. As e1 and e2 are part of cycle C, replacing e2 with e1 in B therefore yields a spanning tree with a smaller weight.
7. This contradicts the assumption that B is an MST.

Question: Can't we just skip adding e1 to B and just get the smallest edge from B, and state that e1 \< e2, since all edges are unique? Thus, it implies that there is only one MST possible.

# Answer
> 2 votes
If $e\_2$ is the lightest edge from $B$ then the weight of $e\_2$ could be smaller than the weight of $e\_1$ (when $e\_2$ also belongs to $A$).

Even if such $e\_2$ was in $B$ but not in $A$ and had a larger weight than $e\_1$ (which is implied from the choice of $e\_1$), this still doesn't prove that you can get a lighter MST by replacing $e\_2$ with $e\_1$ since $(B \setminus \\{e\_2\\}) \cup \\{e\_1\\}$ might be a disconnected graph with two connected components: a tree, and a unicyclic graph.

However, if you choose $e\_2$ as the heaviest edge of the unique cycle of $B \cup \\{e\_1\\}$ (which cannot be $e\_1$ itself), then $(B \setminus \\{e\_2\\}) \cup \\{e\_1\\}$ is necessarily a tree, and this tree must be lighter $B$.

---
Tags: graphs, trees
---


# Question
Title: Why, for $f(n) = n \cdot \sqrt n$ and $g(n)=n(\log n)^5$, we have $f = \omega(g)$? log is base 2
Could you please explain me why that's the case?

# Answer
$f(n) = \omega(g(n))$ if, for every constant $c$, there is some value $n\_0$ (possibly depending on $c$) such that the following is satisfied by all $n \ge n\_0$: $$ f(n) \ge c g(n). $$

Intuitively, $f(n)$ grows faster than any scaled-up (by a multiplicative constant) version of $g(n)$.

This is the case with your particular choice of $f$ and $g$, as you can check by taking the limit of their ratio: $$ \lim\_{n \to \infty} \frac{f(n)}{g(n)} = \lim\_{n \to \infty} \frac{n \sqrt{n}}{n \log^5 n} = \lim\_{n \to \infty} \frac{\sqrt{n}}{\log^5 n} = \lim\_{n \to \infty} \left( \frac{n^\frac{1}{10}}{\log n} \right)^5 = +\infty, $$ since, by L'Hôpital's rule: $$ \lim\_{n \to \infty} \frac{n^\frac{1}{10}}{\log n} = \lim\_{n \to \infty} \frac{\frac{1}{10} n^{-\frac{9}{10}}}{\frac{1}{n \ln 2}} = \lim\_{n \to \infty} \frac{\ln 2}{10} n^{1/10} = +\infty. $$
> 0 votes

---
Tags: algorithms, asymptotics
---


# Question
Title: Question about step in proof that predecessor subgraph forms a breadth-first tree
Given the following theorem and definitions from *Introduction to Algorithms* 3rd edition by CLRS:

**Theorem 22.5: (Correctness of breadth-first search**)

Let $G = (V, E)$ be a directed or undirected graph, and suppose that $BFS$ is run on $G$ from a given source vertex $s \in V$. Then, during its execution, $BFS$ discovers every vertex $v \in V$ that is reachable from the source $s$, and upon termination, $v.d = \delta(s, v)$ for all $v \in V$. Moreover, for any vertex $v \neq s$ that is reachable from $s$, one of the shortest paths from $s$ to $v$ is a shortest path from $s$ to $v.\pi$ followed by the edge $(v.\pi, v)$.

$\delta(s,v) \rightarrow \text{length of the shortest path from s to v} \\\ v.d\rightarrow \text{distance assigned to vertex $v$ from $s$ by BFS}\\\ v.\pi\rightarrow \text{predecessor of $v$ in the path from $s$ to $v$ in the BFS}$

For a graph $G = (V, E)$ with source $s$, the **predecessor subgraph** of $G$ is $G\_{\pi} = (V\_{\pi}, E\_{\pi})$, where $V\_{\pi} = \\{ v \in V : v.\pi \neq NIL\\} \cup \\{s\\}$ and $E\_{\pi} = \\{ (v.\pi, v) : v \in V\_{\pi} - \\{s\\}\\}$

The predecessor subgraph $G\_{\pi} = (V\_{\pi}, E\_{\pi})$ is a **breadth-first tree** if $V\_{\pi}$ consists of the vertices reachable from $s$ and, for all $v \in V\_{\pi}$, the subgraph $G\_{\pi}$ contains a unique simple path from $s$ to $v$ that is also a shortest path from $s$ to $v$ in $G$

I have a question about the following proof:

**Lemma 22.6:**

When applied to a directed or undirected graph $G = (V, E)$, procedure BFS constructs $\pi$ so that the predecessor subgraph $G\_{\pi} = (V\_{\pi}, E\_{\pi})$ is a breadth-first tree.

Line 16 of BFS sets $v.\pi = u$ iff $(u, v) \in E$ and $\delta(s, v) \< \infty$ \- that is, if $v$ is reachable from $s$\- and thus $V\_{\pi}$ consists of the vertices in $V$ reachable from $s$. Since $G\_{\pi}$ forms a tree, it contains a unique simple path from $s$ to each vertex in $V\_{\pi}$. By applying **Theorem 22.5** inductively, we conclude that every such path is a shortest path in $G$.

I'm not sure I understand the last sentence of this proof. Can anyone elaborate on how to "apply **Theorem 22.5** inductively" to "conclude that every such path is a shortest path in $G$"?

**Update:**

One interpretation might be that we need to use induction to prove the last claim and the last part of Theorem 22.5 about a shortest path from $v.\pi$ to $v$is used in the proof.

For example, we can order the vertices in $V\_{\pi}$ in non-decreasing order of distances from $s$. The base case would be the first vertex in $V\_{\pi}$, which is $s$. We then assume that it holds for the first $n$ vertices in $V\_{\pi}$ and we show that it holds for $v\_{n+1}$ by appealing to the last part of Theorem 22.5.

# Answer
Your update is correct. On first reading I thought it was wrong because distances can be negative. It's early here for me ... then I remembered that CLRS defines distance from $s$ to $v$ to be the minimum number of edges on any path from $s$ to $v$ when discussing BFS. Indeed, here is a simple proof:

The proof is by induction on the length (number of edges) of a path from $s$ in $G\_\pi$, with hypothesis $H(n)$ that for any path $P = s \leadsto v \in G\_\pi$ such that the length of $P$ is at most $n$, $P$ is a shortest path in $G$. The base case when $n = 0$ is trivial. For the step assume $H(k)$ for some $k \in \mathbb{N}$, let $n=k+1$ and let $P = s \leadsto v.\pi \leadsto v \in G\_\pi$ be a path of length $k+1$, where $s$ and $v.\pi$ may be the same vertex. $H(k)$ implies that the path $P' = s \leadsto v.\pi$ is a shortest path in $G$. Applying *Theorem 22.5*, we conclude that $P$ is also a shortest path in $G$, which completes the induction.
> 2 votes

---
Tags: algorithms, graphs, algorithm-analysis, shortest-path, check-my-answer
---


# Question
Title: how to do incremental construction of the minimal model in logic programming?
I was reading a book titled "Essentials of Logic Programming.", most parts of the book are easy to understand. but now having a problem with Theme 45: incremental constructions of the minimal model. The relevant parts are shown below.

Some notations: $P$ is a definite program, $B(P)$ is the Herbrand base of $P$, $G(P)$ is a ground instantiation of $P$, $MM(P)$ is a minimal model of $P$.

Theme 45 explains the incremental constructions of the minimal model as follows.

> The method starts by choosing some interpretation $I\_1 \subseteq B(P)$. Later on, we shall see that there is a preferred choice of $I\_1$ and that not all choices are adequate. Choosing $I\_1$ can be viewed as guessing which atoms have to be true in any model of $P$. Now consider any clause in $G(P)$ kind(Chris) q if body

> if our guess assigns true to all atoms in this body then an immediate consequence of that guess is that q should also be made true, for otherwise the clause as a whole would be made false. Our next iterate $I\_2$ comprise just those heading atoms q made true by this argument. This new iterate will not necessarily contain all those body atoms which justified the introduction of the new atoms q; this does not matter - successive iterates will eventually introduce and retain all of these atoms which must be true in any model of the program. Consider this example of a program $P$ on the domain $H=\\{ dov,chris\\}$:

> kind(X) if nice (X)

> nice(X)

> whose ground instantiation $G(P$ is highly abbreviated form is

> kind(dov) if nice(dov)

> kind(Chris) if nice(Chris)

> nice(dov)

> (where K=kind, N=nice, D=dov,C=Chris)

> and suppose we choose $I\_1= \\{ kind(dov),nice(Chris)\\}$. Applying the above method yields $I\_2= \\{ nice(dov), kind(Chris)\\}$ and $I\_3= \\{ nice(dov), kind(dov)\\}$ All further iterates merely replicates $I\_3$, which is accordingly referred to as a fixpoint. We have, in fact, converged upon the minimal model $MM(P)$.

Let me explain how I understand or did not understand this example.

1. is $I\_1$ a guess? why not just make $I\_1 = \\{ nice(Chris)\\}$?
2. nice(Chris) leads to kind(Chris) is true, so "kind(Chris) if nice(Chris)" is true. So, we have kind(Chris) in $I\_2$. But why there is nice(dov) in $I\_2$?
3. as said further iterates will replicate $I\_3$, but I did not see how this works because I did not see the iterate from $I\_1$ to $I\_2$.

I just did not get this example. Could anyone clarify it to me?

Thanks in advance!

# Answer
this paragraph describes the immediate consequences operator $T\_P(I) = \\{ a \mid \text{there exists a rule } r \in G(P) \text{ with } head(r)=a \text{ and } body(r) \subseteq I \\}$ for some interpretation $I$ modelled as a set of ground terms.

What is the significance of this operator ? We start from an interpretation and try to find a model. Now it might be the case that there are rules where the body is true, but the head is not yet true. In order to create a model we have to add the new head to the interpretation which is done by $T\_P$. Since we are especially interested in the least model, we also don't want unnecessary items, i.e. elements for which is no rule with a true body. This is the second effect of this operator.

Now we look at the example. They start with $I\_1 = \\{ kind(dov),nice(Chris)\\}$ and we will check every rule from $G(P)$ to compute $I\_2 = T\_P(I\_1)$

1. kind(dov) if nice(dov): nice(dov) is not in $I\_1$, so we don't need kind(dov) in $I\_2 = \emptyset$
2. kind(Chris) if nice(Chris): nice(Chris) is inside $I\_1$ we need kind(Chris) in $I\_2 = \\{ kind(Chris)\\}$
3. nice(dov): This rule has no body so is always true. So we also need this in the body. Now $I\_2 = \\{kind(Chris), nice(dov) \\}$

Now we repeat this process with $I\_2$ and compute $I\_3 = T\_P(I\_2)$. At the start $I\_3 = \emptyset$ as previously.

1. kind(dov) if nice(dov): Now nice(dov) is in $I\_2$, so $I\_3 = \\{kind(dov) \\}$
2. kind(Chris) if nice(Chris): nice(Chris) is not in $I\_2$ so $I\_3$ stays the same.
3. nice(dov): is the same as previously

So $I\_3 = \\{ kind(dov), nice(dov) \\}$. Try it with this again and you will notice that $I\_4 = T\_P(I\_3)$ equals $I\_3$ is a fixed-point of $T\_P$. This is significant as we can now stop our computation.

Now is this dependent on the program and we were lucky ? If you analyse the operator $T\_P$ on interpretations, you will notice that it is monotonouos and by the Knaster-Tarski-fixed-point-theorem exists always a least fixed point. This can be proven to be the same as the minimal model of a definite logic program.

The interpretation $I\_1$ was choosen arbitrarly. Does it matter which interpretation we start with ? Consider the following logic program $P\_2$ (which is already grounded):

$ p \leftarrow q \\ q \leftarrow p $

You will notice that it has two fixed-points $\emptyset$ and $\\{ p,q\\}$. Each of them is a model, but $\emptyset$ is the least model. This is the result by starting with $\emptyset$. In fact, the Kleene-fixed-point-theorem tells us that starting with the minimum element is the way to calculate the least fixed-point (if some conditions hold).

If you would start however with $\\{p\\}$ you would alternate between $\\{p\\}$ and $\\{q\\}$ and would never reach a fixed-point, so the choice matters.
> 2 votes

---
Tags: programming-languages, logic, first-order-logic
---


# Question
Title: Is communication between processes really important for a OS or is it just a convenience?
One of the services of a OS is communication between processes.However how much important is that?I dont think it is that important just for example if we saved a .txt file the file explorer wouldnt give back the name of the file to the text processor .Am I missing something here?

# Answer
Here are some examples of communication between processes that may not have occurred to you:

* Terminal I/O. Any text-based program needs to communicate with a terminal program somehow.
* Application control. Almost all modern operating systems have a way to communicate important information to running programs. This could be low-level information, such as if the system entered a low-power state, to high-level, such as if the global system colour scheme changed.
* System services, such as device drivers. Drivers usually have to interface with some kind of hardware, but they also need to communicate with the rest of the operating system in both directions.
* Debugging. A debugger needs to be able to control a debugged task in certain ways. (And just as an aside, OS textbooks almost *never* explain this.)
> 2 votes

# Answer
> Am I missing something here

Yes, you are.

> However how much important is that?

It is one of the most important problems when you write a multi-process program. It is quite complicated topic in programming and it is one of the most frequent sources of errors.

> I dont think it is that important just for example if we saved a .txt file the file explorer wouldnt give back the name of the file to the text processor

It is not communication between processes. The process is not a program you run from your desktop. Text processor or web browser uses many separate processes, task or threads. Communication between them and between them and OS is something we call IPC (interprocess communication).
> 1 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: How do you convert this x86 assembly program to binary
I'm trying to convert a x86 assembly language program to binary. I have read a 1979 Intel 8086 manual and so understand the basic architecture, however I am still unsure as to how to convert this. Here's the code:

```
MOV BX, 1300H                          ; Load the Base Address 1st input Matrix in BX
MOV BP, 1400H                          ; Load the Base Address 2nd input Matrix in BP
MOV SI,0001H                           ; Initialize pointer for element of matrix
MOV DI,1501H                           ; Set DI register as pointer for sum matrix
MOV CL,09H                             ; Set CL as count for element in Matrix
REPEAT:
MOV AL,[BX+SI]                         ; Get the element of 1st Matrix in AL
ADD AL,[BP+SI]                         ; Add corresponding element of 2nd Matrix to AL
MOV [DI],AL                            ; Store the Sum of element in Memory
INC SI                                 ; Increment the Pointers
INC DI                                 ;
LOOP REPEAT                            ; Repeat the Addition until count is zero
HLT

```

# Answer
The process of converting assembly to actual machine code is carried out by the joint work of the assembler and the linker. The former is responsible for converting the assembly listing to object code, that is, actual instructions; the latter is responsible for linking together two or more objects and eventually produce the final executable code.

For answering your question, knowing what the assembler does is sufficient. It basically is responsible for translating the listing to a sequence of opcodes, while doing so it keeps track of the address of each instruction and is consequently responsible for resolving label names. Let's pretend the address of the first instruction was 0, then the address of `repeat:` corresponds to the size of all instructions starting from 0.

The listing you provided requires two passes to be assembled correctly (due to backreference); informally, you first emit all opcodes and mark the label as `uncomputed` and only once the lenght of the code following it is known the assembler decides what to write. You provided a listing employing the `LOOP label` instruction that translates to `E2 cb`, where `cb` is an 8-bit immediate value. (I am using this reference for translating.) Note that it must range over \[-128,127\], in case the number of bytes distantiating the `LOOP` instruction and the `repeat:` label was bigger than 128 the assembler would be unable to assemble and terminated with an error.

Let's say you had to jump 8 bytes backward using the `LOOP` instruction, you would translate it as `E2 F8`, that is `E2 dec(-8)`.
> 2 votes

# Answer
You can launch an emulator (VirtualBox, VMware...) and run an old MS-DOS install.

You will be able to run the "debug" program which can assemble this code (just replace the REPEAT label with the address). "debug" can also execute that program step by step.

If you only want to see machine code, there are online assemblers/disassemblers which can automatically translate your code, for example : https://disasm.pro/ (select x86 16bits)
> 1 votes

---
Tags: binary, assembly
---


title: Device Controllers in OS

text:
# Question
Title: Device Controllers in OS
According to this article, we have the following:

> The device controller gets data from a connected system device and temporarily saves such data in a special purpose register inside the controller known as a local buffer.

So according to the above statement, the local buffer is a part of the special purpose registers of the controller. However, according to operating systems concepts, ninth edition, page 12, we have :

> A device controller maintains some local buffer storage and a set of special-purpose registers. The device controller is responsible for moving the data between the peripheral devices that it controls and its local buffer storage.

This means that a local buffer is a separate component from the set of special purpose registers of the controller, and hence, the local buffer is not a register. This makes more sense to me, since if we implement the local buffer as a register, the buffer will be limited in size as a register is limited in size. So my question is whether the local buffer of a device controller is implemented as a register or a separate memory module ?

# Answer
> 2 votes
It depends on the device and, specifically, how much data needs to be buffered.

Some devices, such as GPIO or SMBus (used for things like temperature sensors on the motherboard), have such a low bandwidth that the maximum amount of data that needs to be "buffered" is a small number of bytes. A hardware register or two is probably enough here.

Others, such as disk or ethernet, do not. In this case, using a more complex local buffer that isn't visible as a register may make more sense. Such a device would typically use DMA to transfer the contents of the buffer into core. However, computers sometimes boot from disk or over a network, so providing a slow register-based mechanism for reading the contents of the buffer can help simplify bootstrap loaders, both firmware and software.

As an example, on PC hardware, SATA disks are typically controlled through the Advanced Host Controller Interface, or AHCI for short, which interfaces drives with the rest of the computer through DMA. However, they are still required to support what is known as ATA PIO Mode, which reads the contents of the memory buffer through register-based port I/O. This is not recommended for operating systems in their steady state, but is very convenient for booting.

---
Tags: operating-systems
---


# Question
Title: How is this example sequentially consistent but not linearizable?
**Background information that I know(But not understand with examples, I will be glad if you could explain it to me with examples)**

A replicated service is said to be linearizable if for any executin there is some interleaving of operations that

1. Meets the specifications of a non replicated service
2. Matches the real time order of operations in actual execution.

A replicated service is said to be sequentially consistent if for any execution there is some interleaving of operations that

1. Meets the specifications of a non replicated service
2. Matches the program order of operations in actual execution.

**Here is what is written in Colouris's distributed system book about the example I have shown in image-**

> This execution is possible under a naive replication strategy even if neither of the computers A or B fails but if update of x that client 1 made at B hasn't reached A when client 2 reads it. The real time criterion for linearizability is not satisfied, since $getBalance\_A(x)\to 0$ occurs later than $setBalance\_B(x,1)$: but the following interleaving satisfies both criteria for sequential consistency: $getBalance\_A(y)\to 0$,$getBalance\_A(x)\to 0$, $setBalance\_B(x,1)$,$setBalance\_A(y,2)$

I am failing to comprehend anything written here. I think it is mainly because of my failure to understand the example of linearizability and sequential consistency. Can you shed some light here and help me out here? I will be really grateful for any help.

# Answer
The key difference between linearizability and sequential consistency is that linearizability needs to respect the real-time order (nobody should be able to prove the real-time order wasn't respected) and sequential consistency does not.

So when when client1 calls setBalance(x,1) and client2 later calls getBalance(x), it should return the value 1. But client2 returns the value 0; the value before setBalance(x,1) was called. So at least one of these methods isn't respecting the real-time order and hence the example is not linearizable.

So why is the example sequential consistent? Since the real time order doesn't need to be respected, the getBalance(x) and getBalance(y) can be skewed before the calls to setBalance(x,1) and setBalance(y,2). So for both client1 and client 2 the program order has not been violated.
> 1 votes

# Answer
I believe that it is obvious that linearizability is not satisfied here, because real time order of operations is not preserved. In linerizable system, once Client 1 set the balance, Client 2 must have been immediately seen this on his next read.

With sequential consistency it is a bit more tricky. For sequentially consistent system there is no requirements at all for mutual order of operations between different processes. That's why it is perfectly possible that write by client one on one replica is not reflected in the read from the second replica.

In this video, I explain the definitions of linearizability and sequential consistency and differences between them and I hope that after watching it you would be able to fully understand answer on your question.
> 0 votes

---
Tags: distributed-systems, computer-networks, parallel-computing
---


# Question
Title: Can Dijkstra's algorithm outperform A star, in terms of vertices checked?
I know Dijkstra's algorithm can be seen as a specific case of A star, when the estimation heuristic used simply returns 0, so I know that A star with this specific heuristic can not check more vertices than Dijkstra's algorithm. What I'm asking however is the following. Given an A star algorithm with some heuristic which is not the heuristic returning 0, could it possibly check more vertices than Dijkstra's algorithm?

My intuition is yes, and I will show why. Consider the Figure underneath, in which we consider a large amount of discrete points in this plane, representing the vertices of the graph, and connecting arcs with cost 1 between all adjacent points, creating a grid graph. Suppose the heuristic used by A star is euclidean distance, and suppose many curved walls like the ones I drew in the middle exist in this fashion, not only the three I drew. A star in this situation would be "tricked" to go in between the walls, since the heuristic would guide it close to the point, only to find out it's a dead end (or a local optimum of some sorts if you will), and this would happen as many times as there are walls. Dijkstra would not be tricked this way. The only problem with my example here, is that Dijkstra will probably **not** outperform A star here. So, is my intuition wrong, or do more clever instances than this one exist in which Dijkstra can in fact outperform A star in terms of vertices checked?

# Answer
No,

Dijkstra will explore all nodes with cost less than the cost of the completed path. While A\* will explore all nodes with cost+heuristic less than the cost of the completed path.

Thus if the heuristic is always positive then A\* will expand less or equal nodes.
> 1 votes

# Answer
I don't see why not. A\* is heuristic based, if your heuristic is completely wrong the algorithm can end up preferring the search in a wrong direction in the solutions space. You could even design a heuristic that only ever brings the algorithm to a place in the solutions space without ever bringing it closer to the actual goal.

I don't see how this algorithm, which is quite literally heuristics-based Dijkstra, has any mathematical limitation in terms of how much worse it can be than Dijkstra.
> -1 votes

---
Tags: algorithms, search-algorithms, a-star-search
---


# Question
Title: Hungarian method: seemingly different algorithms from different sources?
When I look online for examples of the Hungarian method for solving the min-weight assignment problem, for example here, it involves iterating on the cost matrix; subtracting entries from the rows and columns.

However, in section 17.2 of the book, Combinatorial optimization polyhedra and efficiency by Schrijver, a seemingly different algorithm is presented. Here, we start with a matching $M$, assign $W\_M$ and $U\_M$ as the edges on the left and right of the bi-partite graph that haven't been covered by the matching, describe path lengths as $l\_e=w\_e$ if the edge is in $M$ and $l\_e=-w\_e$ otherwise and find a min path from $U\_M$ to $W\_M$. Then, reset $M$ to $M'$, the symmetric difference between the path $P$ and $M$.

These two algorithms seem very different to me. Are they somehow the same under the cover?

# Answer
> 1 votes
Full disclosure, my understanding is kind of vague, and I don't have access to the book you mentioned, so my graph based variant is probably a little different from yours. But I spent several days trying to find out how the different variants of this algorithm relate to each other, and a post like this would have really helped me. Hopefully it does help someone.

The matrix based algorithm goes as follows:

1. Subtract (and note) row minima from the rows; then subtract (and note) column minima from the columns; After this step, there is at least one zero in every row and every column. Note, that any optimal assignment in the original matrix is still optimal in the new one.
2. Cover the zeros with minimal number of lines.
3. If the minimal number of lines is $n$, the optimal solution has been found.
4. If the number of lines necessary is less than $n$, we need to manipulate the cost matrix. Find the minimum over the uncovered elements, then add this value to each covered column and subtract it from each uncovered row; then, go back to 2)

The graph based variant of the algorithm:

1. Label the vertices such that: $p(i) = min \left( c\_{i, j} \right) \forall i \in X$ and $p(j) = min \left( c\_{i, j} - p(i)\right) \forall j \in Y$.
2. Construct a new bipartite graph $G\_p$, where $(i, j) \in E$ if $c\_{i, j} - p(i) - p(j) = 0$
3. Find the perfect matching in $G\_p$.
4. If the size of the matching is $n$, the optima solution has been found.
5. If not, we need to change the labels of the vertices. Find a set in $G\_p$ $A \subset X$ such that $|A| \> N(A)$ where $N(A)$ denotes the neighbors of $A$ (such a set always exists, Hall theorem). Find $d = min \\{c\_{i,j} - p(i) - p(j) | i \in A, j \notin N(A) \\}$. Then we change the labels: $p(i) := p(i) + d \forall i \in A$ and $p(j) := p(j) + d \forall j \in N(A)$, and then continue with 3)

The greatest difference is in the covering of zeros vs. constructing a matching steps. But, since the cost matrix is still a representation of a graph, we can interpret the covering of zeros as an operation on that graph. Each zero in the graph corresponds exactly to an edge $(i, j)$ in the new graph $G\_p$ constructed by the graph based algorithm.

Covering the zeros then corresponds to construction of a vertex cover. If the zero is covered by a horizontal line, that means the vertex $i \in X$ has been added to the cover, if by a vertical line, the vertex $j \in Y$. Because each line corresponds to a specific task, covering a zero by a horizontal line means that the task has been assigned. Covering a zero by a vertical line means that the worker (column) has been assigned a task. Finding a minimal number of lines necessary corresponds to finding a minimal vertex cover, which in bipartite graphs is exactly equal to the size of the maximal matching (König theorem).

You could also cover by crosses instead of lines. Each cross then corresponds to an assignment of a worker to a task (1 to 1), and you have to maximize the number of crosses instead of minimizing. This then corresponds to a matching in the bipartite graph.

As far as I can tell, there are several ways to do the cost manipulation and I don't understand this enough to be able to explain why they work.

---
Tags: algorithms, graphs, assignment-problem
---


# Question
Title: Can a graph problem remain NP-hard when restricted to cycle graphs?
Does anyone have any examples of NP-hard graph problems which stay NP-hard on cycles, or is this class somehow not able to have NP-hard problems?

I found a similar post concerning trees here which answers affirmatively, but by using the fact that any $n$-size input can be encoded as a tree of order $n$. Cycles only have one member per order and thus this trick cannot be used. Due to this, I've started to think that the only parameter of a cycle graph is just the order $n$, and so perhaps graph problems restricted on cycle graphs don't really make sense as it's more of a problem on integers? However, since there are problems on integers which could be NP-hard, such as integer factorization, could it be that NP-hard problems on cycles do exist?

I checked on graphclasses but no \`\`cycle'' graph class exists, which further confirms my suspicion that there's just something inherently too simple about this class.

# Answer
> 10 votes
Assuming the problem instance is defined solely by the cycle itself (no labels or weights on the nodes, etc., no other inputs to the algorithm), then no, you should not expect any such problem to be NP-hard.

Any language containing just cycles is a sparse language. In other words, any question about cycles ("does this cycle have property $P$?", where $P$ is any property you care about) corresponds to a sparse language.

It is known that every sparse language is in $P/\text{poly}$, and if a sparse language is NP-complete, then $P=NP$. Since most people believe that, most likely, $P \ne NP$, it follows that, most likely, no problem about cycles will be NP-complete. Also, since every sparse language is in $P/\text{poly}$, any problem about cycles can't be "too hard", in some rough sense.

Or, to put it another way, if you find a problem about cycles that is NP-complete, then you will have found a proof that $P=NP$ and can claim the $1M Millenium Prize. Since no one has managed to do that so far, you shouldn't expect anyone to find such a problem about cycles, either.

The question about NP-hard is a little trickier because of complications with uniform vs non-uniform complexity classes and $P$ vs $P/\text{poly}$, but I hope that the above has addressed the core of your question. Incidentally, factorization is not believed to be NP-hard.

---
Tags: graphs, np-hard
---


# Question
Title: Problem identification: splitting string into tokens taken from a given, possible overlapping set
I am facing the following problem in a script I am trying to develop:

Given a string and a set of tokens, where the tokens are known and are overlapping (the set can contain the tokens 'a', 'b' and 'ab'), I need to split the string into a list of tokens from the set. I know there can be multiple ones, I don't need all of them, just a random one (obviously it is trivial to get an arbitrary one if I have all possible token lists).

The token set is known and guaranteed to have all possible characters of the input string, there is at a token which is equal to a single character for each possible input character.

Is it a known problem? If so, does it have known solutions? I am happy with adjacent literature I can use to jump-start my research.

# Answer
> 1 votes
This problem is often called the Word Break problem and is a classic exercise for dynamic programming.

Base case: if you don't have a string, it's a yes instance.

For every token, if the string ends with that token, remove that suffix from the string and recurse.

If no token is a suffix of your (non-empty) string, return false.

The running time is cubic (or more accurately the length of the string times number of tokens times length of the longest token). Perhaps.

---

A very simple recursive function with memoization in Python is given:

```
@cache
def wordbreak(string, tokens):
    if not string:
        return True
    canbreak = False
    for token in tokens:
        if string.endswith(token):
            if wordbreak(string.removesuffix(token), tokens):
                return True
    return False

```

Beware that it's slower than necessary.

---
Tags: algorithms, strings, substrings
---


# Question
Title: Sequence counter in a hardwired control unit
I have been studying the structure of a hardwired control unit and at 8:57 of this video

we get a basic block diagram.What does the sequence counter do exactly?

# Answer
For a basic cpu each instruction takes multiple clock cycles to execute. For example you could have steps that

1. first read the instruction into the instruction register,
2. then it reads operand 1 into the execution unit input register, and
3. then it reads operand 2 into the execution unit input register, and
4. then it reads from the output register into the destination register.

therefore you need a counter to keep track of which step of instruction execution you are in.
> 1 votes

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


# Question
Title: What is the purpose of padding bits in primitive integer types?
The C standard carves out room for implementations which have padding bits in their integer types. Padding bits affect the size of an integer but not the number of possible values they can contain. I understand the purpose of padding bits/bytes in structs to ensure that they are properly aligned but including padding bits in primitive integer types seems unnecessary and pointless. This question refers to padding bits in `int` as *'outdated.'* The answer refers to a 32-bit `short` stored in a 64-bit object making all the remaining 32 bits padding bits that serve no apparent purpose.

For what purpose would there be padding bits in integer types instead of just using all the bits in any given integer type as value bits or using a smaller integer type? What purpose did padding bits in primitive integers *ever* serve regardless how *'outdated'* they are?

# Answer
> 1 votes
IIRC, Crays had a 23 bits integer type. This was really just their 32 bits floating point type with the exponent set to zero/ignored. If this idea sounds outdated, AVX-512 recently introduced a 52 bits Integer Fused Multiply & Add (IFMA). Same idea: ignore the exponent of a larger FP type.

---
Tags: integers, c, numeral-representations
---


# Question
Title: Should I use linear programming for my timetable generator?
I am creating a timetabling software for a school, which given parameters for teachers/class sizes will output a timetable. There will be a list of classrooms per subject and a list of teachers per subject and I'll divide the students between the teachers.

The main focus is creating timetables for teachers, as opposed to the students, since the teachers will teach only one/two subjects so I believe it is a simper problem.

I aim to have a certain number of classes, which account for optimally ~20 students per class. Each class will require a teacher and each teacher can only be in one place at a time. Additionally, each subject will have a list of available rooms which they could take place in - e.g Computing cannot take place in a History classroom. As well as that, I hope to optimise the timetable so that a teacher is not forced to run across the whole school to get to their next lesson.

I have read a bit about Linear Programming, but I don't fully understand it all. Is it the best way to approach this problem, or should I use another algorithm? I will be using Python, combined with the use of an SQL database if that has any affect.

# Answer
> 2 votes
Linear Programming is a technique to model continuous optimization problems. Since a student cannot be divided in half (or a classroom shared by two half teachers at a time), this problem is not continuous and modelling it as a Linear Program does not appear possible.

What you might consider is modelling this problem as an Integer Linear Program (ILP). However, in contrast to Linear Programs, there are no algorithms with good worst-case running time for solving ILPs. There are good heuristic algorithms, which are good at solving many ILPs, but come without guarantee. You could try modelling your problem as ILP and feeding it to an ILP solver. If you are lucky it will turn out to be a feasible approach, if you are unlucky you will have to consider another approach (e.g., a heuristic such as simulated annealing).

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


# Question
Title: How to formally show computational equivalence or universality using encodings?
I want to formally show that a computational system $\mathcal M$ is *computationally universal* by showing it is *computationally equivalent* to some already known universal system, i.e. some UTM.

To show that system $\mathcal M$ is *computationally equivalent* I need to prove something along the lines of this following definition:

**Definition(Computationally Equivalent Systems)** Let $A, B, A\_0 , B\_0$ be alphabets and let $\mathcal M$ and $\mathcal N$ be computational systems with their computed functions being of the form $f\_M : A^\* \to B^\*$ and $f\_N : A\_0^\* \to B\_0^\*$. Then if there exist *encoding functions* $e\_1 : A^\* \to A\_0^\*$ and $e\_2 : B^\* \to B\_0^\*$ such that $e\_2 \circ f\_M = f\_N \circ e\_1$ holds we say $\mathcal M$ and $\mathcal N$ are computationally equivalent w.r.t. the encodings $e\_1$ and $e\_2$.

The problem is I can't find a useful definition for **encodings**. They obviously should be total and Turing computable (and possibly reversible) functions. However, they must not be too powerful since if the encodings partake in the actual computation any systems can be "equivalent" and that is not what we want.

Example: If you want to compare a machine that computes addition on a pair of numbers (in base 10) with a machine that computes addition on a pair of binary numbers those should be equivalent in their computation since only the representation they use for input and output changes. However, if you now consider an "encoding function" that it self performs the addition and returns the result, the first machine would be "equivalent" to a machine that simply performs the identity function. This is obviously not an intended result of the definitions above. In this example it is easy to see intuitively that the "encoding" was to "strong". But how can I describe that formally? **How can I further restrict the computational power of encodings to be lower than the computation that I am studying?**

The same problem arises when comparing machines regarding computational universality. How can I define encodings that are not able to perform universal computations themselves (so that they don't interfere in the results I am trying to prove), but that are still powerful enough to be useful for actual translations of complex representations of inputs and outputs?

My initial idea was to restrict the encodings to functions that can be computed by some kind of automata that is provably less powerful than a TM. For example a linear-bounded TM. However (if I am not mistaken) such a linear-bounded TM would already be to weak, since it can not compute functions like $\text{DecToBin}: \\{0,1,2,...,9\\}^\* \to \\{0,1\\}^\*$ since the length of the output grows exponentially compared to the input.

> Edit: I am mistaken. A linear-bounded TM CAN compute functions like decimal to binary conversion, since their growth is linear and NOT exponential. So maybe functions computable by linear-bounded TMs would be a solution?

An other idea I think might be useful to incorporate is some semantic preservation property. I.e. if the if the words over the input and output alphabets are equipped with some notion of semantic we require that the encodings preserve this semantic.

However this does feel like "cheating" at feels not at all formally sound.

This leads me to the question: How can one formally restrict the computational power of encodings such that a formally sound study of universality is possible?

All proofs of universality I've read so far simply brush over the fact that some kind of encoding is happening. If you know of a work where this was explicitly discussed I would be very interested.

Thank you!

# Answer
> 1 votes
Excellent question. I'm not aware of any formal way to define this, to my knowledge. Instead, as far as I'm aware, in cases where computational equivalence comes up in practice, usually this issue doesn't arise, as the encoding are so obviously weak compared to the notion of computational power we care about, that it's obvious that everything is fine.

There are some specific instances where we can provide a formal definition for what encodings are allowable. For instance, when proving NP-completeness, we require the reductions (which are essentially encodings, in the sense of the definition you gave) to run in polynomial time.

A similar issue arises in complexity theory, when we translate an informally stated problem into something that can be analyzed using complexity theory. We typically have to pick a representation of the inputs and outputs (a way that they are encoded in binary), to turn that into a precisely defined problem (specifically, a formal language). Complexity theory ultimately proves theorems about the resulting formal language. In principle, a particularly obtuse choice of representation might make a very hard problem easy. In practice, people use 'the obvious' representation, which is obviously so easy to implement efficiently that just don't bother about it. But from a pedantic or formalistic perspective, what we have actually proven theorems about are the formal languages, not the informal problem statements. We then treat those theorems as telling us something useful about the informal problem statements, making use of our recognition that the representation is obviously reasonable.

---
Tags: turing-machines, computability, automata, computation-models, encoding-scheme
---


# Question
Title: How to enforce convexity of triangulation output?
I implemented an incremental Delaunay triangulation algorithm. It basically works except it has this weird issue.

The algorithm starts by creating a bounding triangle that it then splits recursively as new points are inserted. Then the 3 extra points are deleted. This yields these kind of meshes before deleting the point:

There's 2 edges in there, which are 100% delaunay, flipping them would make the triangulation non delaunay.

But when I take these points out, I will delete the edges, creating a non convex triangulation.

I could just grab the convex hull of the result and try to add the missing edges but that's very inelegant. I am wondering if there is a better way. For what is worth I implemented the algorithm described here.

# Answer
I went about this problem as follows:

Find the centroid of the point set as well as the largest distance from the centroid to any of the points.

This yields a circle, compute a triangle that fully contains the circle (and thus fully contains the point set).

When testing for the Delaunay criterion to decide if an edge needs to be flipped, check if the point opposite to the edge is one of the 3 new points, if it is, ignore the test and return that the point is not in the circumcircle.
> 0 votes

---
Tags: graphs, computational-geometry, discrete-mathematics, triangulation
---


# Question
Title: Efficient solution for dominating set with two neighbors instead of one
The dominating set problem asks us to find a set of nodes $S$ such that for a graph $(V, E), \forall v \in V$, $v$ has a neighbor in $S$ or is in $S$ itself.

I'm looking for an algorithm which finds $S$ such that any $v$ has at least *two* neighbors in $S$ instead. It doesn't have to be optimal, as I'm using this algorithm in network design where a somewhat suboptimal solution is extra redundancy. Ideally it would be straightforward to implement, though—working in Rust if that changes anything—and performance matters given the size of these networks.

Intuitively, I want to say I could just use a prebuilt algorithm (like so) to calculate the dominating set, then eliminate all nodes which have two neighbors in the dominating set before running the calculation on the resultant graph. Then you'd just rinse and repeat if necessary. I'm not sure if there's a more performant solution out there, though, hence the question.

**Edit:** To add some characterisation to the graphs I'm looking at:

* These graphs are currently unit disk graphs. I expect this will change once topographic concerns are taken into line of sight calculations: for the time being all I care about is the distance between points. As such, I'd prefer a graph algorithm over a geometric one.
* The graphs are very dense, with max neighbors of around 20-30, and total edges of around $10N$ in bad cases. There are usually a few 'straggler' nodes that either have no or very few neighbors, but these can also be trimmed or processed in some other way.

# Answer
> 2 votes
In *Parameterized Complexity for Domination Problems on Degenerate Graphs*, Golovach and Villanger give an algorithm for the Dominating Threshold et problem, which is defined as follows:

**Dominating Threshold Set**
**Input:** A graph $G$, and two integers $k$ and $r$
**Question:** Does there exist a set $S$ of at most $k$ vertices such that for every vertex $v \in V(G)$, $|N\[v\] \cap S| \geq r$, i.e., every vertex has at least $r$ neighbors in $S$ (including themselves), i.e., dominators need only have one additional neighbor in $S$.

They give an algorithm running in time $O(k^{O(dkr)} \cdot n^{O(1)})$, where $d$ is the *degeneracy* of the graph.

The problem is often called **Double Domination** in the literature.

Your problem is also sometimes referred to as a *sigma-rho*-domination problem, with $\sigma \geq 2$ and $\rho \geq 0$. This is simply saying that every vertex needs two neighbors in $S$ ($\sigma$) and however many they wish ($\rho$) in $V \setminus S$ (see Telle, Nord. J. Comput., 1994).

It is also known as the $\[2,k\]$-domination number (see Chellali et al., Discrete Applied Mathematics, Volume 161, Issue 18, December 2013, Pages 2885-2893).

---
Tags: graphs
---


# Question
Title: Exponential sized graph 3-coloring is in MIP
I was watching a talk by Anand Natarajan on $\text{NEEXP} \subseteq \text{MIP\*}$, and he uses $\text{3-coloring}$ as an example problem for $\text{NEXP} = \text{MIP}$ (timestamp 3:50). He mentioned that a two-prover interactive system could solve an exponential-sized graph's $\text{3-coloring}$ problem. I have two questions regarding this:

1. If this proves $\text{NEXP} = \text{MIP}$, then is this problem $\text{NEXP-complete}$?
2. By inputting an exponential-sized graph, will it not make the input exponential-sized by default?

# Answer
> 1 votes
2. This is meant to use a *succinct encoding* of the graph. That is, a graph on $2^n$ vertices $V=\\{0,1\\}^n$ with an edge set $E\subseteq\\{0,1\\}^n\times\\{0,1\\}^n$ is represented by a Boolean circuit $C$ in $2n$ variables such that $$(\vec a,\vec b)\in E\iff C(\vec a,\vec b)=1$$ for all $\vec a,\vec b\in\\{0,1\\}^n$. Ideally, you should think of $C$ having size polynomial in $n$. (Only a few graphs have a representation with such a small $C$, but this will be enough for the argument.)

1. Yes, 3-colourability of succinctly encoded graphs is NEXP-complete. This requires some work, but it can be shown using similar ideas as the NP-completeness of usual 3-colourability. (In particular, one has to show that the graphs expressing exponentially long computations of a Turing machine are sufficiently uniform so that they can be encoded by polynomially small circuits.)

---
Tags: graphs, interactive-proof-systems
---


title: Unique SAT is in DP

text:
# Question
Title: Unique SAT is in DP
I am an engineer learning about the complexity class DP, and I am looking at a number of sources that mention that UNIQUE-SAT and CRITICAL-SAT are both in DP. Is there a proof of this fact somewhere that I can learn from?

# Answer
> 5 votes
Just use the definition: $\phi$ is in UNIQUE-SAT if and only if $$\underbrace{\phi\in\mathrm{SAT}}\_{\text{NP property}}\text{ and not }(\underbrace{\text{$\phi$ has at least two satisfying assignments}}\_{\text{NP property}}).$$

Likewise: a CNF $\phi=\bigwedge\_{i\<n}C\_i$ is in CRITICAL-SAT if and only if $$\Bigl(\underbrace{\text{$\bigwedge\_{i\ne j}C\_i$ is satisfiable for each $j$}}\_{\text{NP property}}\Bigr)\text{ and not }\underbrace{\phi\in\mathrm{SAT}}\_{\text{NP property}}.$$ To see that the property in brackets is in NP, it can be witnessed by a sequence of $n$ assignments, where the $j$th assignment satisfies all clauses except $C\_j$.

# Answer
> 3 votes
They are defined and proved to be in $D^P$ in the original article by Papadimitriou and Yannakakis, *The complexity of facets (and some facets of complexity)* published in JCSS in 1984 (Volume 28, Issue 2, April 1984, Pages 244-259).

Critical-SAT is defined in a follow-up article by Papadimitriou and Wolfe *The complexity of facets resolved* published in JCSS in 1988 (Volume 37, Issue 1, August 1988, Pages 2-13).

---

The complexity class $D^P$ is essentially languages that are the intersection of a language in $\text{NP}$ and a language in $\text{co-NP}$.

A couple of $D^P$-complete problems:

* SAT-UNSAT: Input is two SAT formulae $\Phi\_S$ and $\Phi\_U$ and the question is whether $\Phi\_S$ is satisfiable and $\Phi\_U$ is unsatisfiable.
* Minimal unsatisfiability: Input is a 3-CNF-SAT formula $\Phi$. Question: Is it true that $\Phi$ is unsatisfiable, but removing any clause at all makes the resulting formula satisfiable?
* Exact clique: Input is a graph $G$ and an integer $k$. Question: Does the largest clique in $G$ have size $k$?
* Critical clique: Input is a graph $G$ and an integer $k$. Question: Is it true that $G$ does not have a $k$-clique, but if you add any edge at all, then the resulting graph will have a $k$-clique?
* Maximum non-hamiltonian graph: Input is a graph $G$. Question: Is it true that $G$ is non-hamiltonian but adding any edge at all to graph results in a hamiltonian graph?
* Minimal 3-colorability: Input is a graph $G$. Question: Is it true that $G$ is not 3-colorable, but deleting any vertex at all results in a 3-colorable graph?

---
Tags: complexity-theory
---


# Question
Title: Is the flexible bin packing problem NP-complete?
I am currently trying to figure out whether a flavor of the bin packing problem, which I call the "flexible bin packing problem" (F-BPP), is NP-complete.

Here are the definitions for the traditional bin packing problem (BPP) and the flexible bin packing problem (F-BPP):

**Bin packing problem (BPP):**

*Optimization problem:* Given a set of n items and their corresponding volumes (the volume of each item is between 0 and 1), pack the n items into the minimum number of bins (each with capacity 1) such that the capacity of each bin is not exceeded (https://ics.uci.edu/~goodrich/teach/cs165/notes/BinPacking.pdf).

*Decision problem:* Given a set of n items and their corresponding volumes (the volume of each item is between 0 and 1), and an integer k, determine if it is possible to pack all n items into at most k bins, each with capacity 1, such that the capacity of each bin is not exceeded. This problem is NP-complete (https://ics.uci.edu/~goodrich/teach/cs165/notes/BinPacking.pdf).

**Flexible bin packing problem (F-BPP):**

*Decision problem:* Given n item types, m bin types, and a mapping between compatible item type and bin type pairs (the pairs are keys in the mapping) and the volume (between 0 and 1) of an item of that type in a bin of that type (the volumes are values in mapping), and an integer k \>= m, determine if it is possible to pack at least one item of each type in at most k bins, where each bin has capacity 1, the capacity of each bin is not exceeded, and all bin types are used at least once. Items and bin types can be used more than once.

# Answer
Here is a potential solution that I came up with for the above problem.

Could someone please verify my explanation for why F-BPP is in NP and my reduction of BPP to F-BPP?

**Proof:**

*F-BPP is in NP:* Suppose that a solution to F-BPP is a list of 2-tuples, where each 2-tuple corresponds to a bin. The first value of the 2-tuple is the bin type, and the second value of the 2-tuple is a key-value mapping between each item type and the number of items of that type that are in the bin.

A solution to F-BPP in this form can be verified in polynomial time by iterating through each bin and the items in those bins. As we iterate, we can count the number of bins. If the number of bins exceeds k, then the solution is invalid. Hence, iterating through the bins takes O(k) time. For each bin, we can iterate through the n key-value pairs in its mapping, and check that the collective volume of those items does not exceed the capacity of the bin. This takes O(n) time. The total time complexity of iterating through the bins and items in each bin is O(nk) time. As we iterate, we can keep track of the unique item types and bin types observed. Once the iterations are done, it takes O(n) time to check that all unique item types have been used and it takes O(m) time to check that all unique bin types have been used. Hence, it takes polynomial time to verify a solution to F-BPP, so F-BPP is in NP.

*Reduction from BPP to F-BPP:* Given the inputs to BPP, each of the n items corresponds to its own item type (n item types). Keep the same integer k. All bins are of one type, so m = 1. Create the mapping between each item type and the one bin type, where the volume for each item type under the one bin type is the same as the volume of the corresponding item in BPP. The BPP inputs, the one bin type, the mapping, and the integer k are now the inputs to the F-BPP problem. The capacity of each bin is still 1.

If the answer to F-BPP is yes, then the answer to BPP is also yes, since there is only one type of bin used, items of all types were packed, and the item volumes and bin capacities remained the same.

Since each item in BPP can only be used once, items can be removed from the F-BPP packing such that only one item of each type remains, and this will not increase the bin count (number of bins is still at most k). By design, since only one bin type is used, the F-BPP bin packing should not need to use more than one item of a given type (since the one bin type will be covered from using each item type once), but in case such duplicate items exist, they can simply be removed without increasing the bin count.

The resulting bin packing is the bin packing for BPP. Hence, BPP is reducible in polynomial time to F-BPP.

*Result*: Since F-BPP is in NP and BPP is polynomial-time reducible to F-BPP, F-BPP is also NP-complete.
> 2 votes

---
Tags: complexity-theory, np-complete, np-hard, packing
---


# Question
Title: Finding an element in array, whose index number and element value same
Given a sorted array of distinct integer $A\[1,2.....n\]$ the tightest upper bound to check the existence of any index $I$, for which $A\[I\]=I$ is equal to \_______________ ?

---

I thought here answer that mean time complexity will be $O(1)$, because directly getting the searching index and then checking if $A\[I\]=I$, but answer given as $O(log n)$.

Please help me out, which will be correct answer?

# Answer
> 3 votes
If the array had $A\[i\]=i, \forall{i}$, then the complexity would have been $\theta(1)$ as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't.

But the array isn't like that. Array could be like $1,3,4,8,9,12$ as well.

The question is asking to find an element $A\[i\]$ in the sorted list which is situated at the index $i$.

The algorithm to find such element is mere a slight modification of binary search where you update low & high based on $i\<A\[i\]$ \- if it's true update `high=mid-1` else if $i\>A\[i\]$ update `low=mid+1`. The complexity is indeed $\theta(log\_2n)$

# Answer
> 1 votes
Take the hints. The integers can be positive or negative, but they are *distinct*. The array is sorted, which usually means a1 ≤ a2 ≤ a3 ... But the are distinct, so a1 \< a2 \< a3 \< ... And they are integers, so they are at least 1 apart. So we have a2 ≥ a1 + 1, a3 ≥ a2 + 1, a4 ≥ a3 + 1 and so on. What does that mean for ai - i?

(If you figure that out, the solution is trivial).

# Answer
> 0 votes
The best searching method for this problem will be binary search and in binary search time complexity of avg or worst case is logn.
and if in question it is not mentioned distict intergers then we can't apply binary search then it we go with linear so in that case time complexity will be o(n).

---
Tags: algorithms
---


# Question
Title: What is the difference between Application Programs and System Programs?
In Operating Systems, What is the difference between Application Programs and System Programs? Also, what are examples of each?

# Answer
There aren't hard and fast definitions for this, but here's the basic idea.

A "system program" is a user program (i.e. it does not have kernel privileges) that manages some aspect of the operating system or operating environment. It typically comes installed with the operating system and cannot be uninstalled. It is typically started by the system, and not as the result of a user interaction. It may or may not have a user interface.

Some examples include:

* A login program. On a multi-user operating system, there needs to be some way to log in. This could be a command-line program or a GUI program, but it's still a program.
* A shell. The term "shell" originally referred to the command-line, but can also refer to the part of the graphical user interface that exposes the file system (e.g. Windows Explorer). All of these are programs.
* A service manager. System services need to be started and stopped, possibly as required, and there is typically a program to perform this housekeeping task. Some examples SvcHost in Windows, launchd in macOS, and systemd in Linux.
* Parts of the GUI operating environment, such as the window manager, or system widgets such as the display settings or system volume control.

An "application program", on the other hand, is a program that is user-installable and typically corresponds to a task to which the operating system is "applied". An application program is typically explicitly started by the user, and stops when the user exits the program.

Some examples:

* Game.
* Word processor, spreadsheet, etc.
* Compiler/IDE.

There is a fuzzy line between them; some operating environments require a web browser to function, for example.
> 1 votes

---
Tags: operating-systems
---


# Question
Title: Iterate over a range randomly without any duplicate or storing the full range in memory
I'm trying to create (or find) an algorithm to iterate over a range (e.g.: 1-100, etc) but randomly, without any duplicate values (similar result to random sort, etc) but without actually storing the full range in memory (such as using list(range(1, 100)) in Python, etc).

Problem is, I'm not sure how to tackle this. As mentioned, I know about random sort as mentioned, but I would need to store the full range in memory (or large part of the range). Besides that, there are many other way, but they all depend on the full range being stored in memory too.

Now how random it should be? I don't really mind the quality of the randomness. For comparison’s sake, I want it to be as random as using `randrange` from the random module in Python. As long as it "look" random and does not have any duplicate.

Is there any way to do this?

# Answer
> 4 votes
One approach is to use the sequence of values $E(1), E(2), E(3), E(4), \dots$ where $E$ is a format-preserving encryption cipher with a random key. This ensures the sequence won't repeat and that each element in the sequence will be in the desired range.

See also Pseudo random, unqiue integer numbers in a given range, Shuffling a collection too large for memory.

---
Tags: random-number-generator, iteration
---


# Question
Title: Runtime of weighted interval scheduling dynamic programming algorithm
Consider this implementation of a dynamic programming algorithm for weighted interval scheduling:

```
M-Compute-Opt(j)
    If j=0 then
        Return 0
    Else if M[j] is not empty then
        Return M[j]
    Else
        Define M[j] = max(v_j + M-Compute-Opt(p(j)), M-Compute-Opt(j − 1))
        Return M[j]
    Endif

```

Here we have a set of requests $\\{1, 2, \ldots , j\\}$. We're assuming they're ordered by finishing time in nondecreasing order. I.e., $j$ finishes last, $j-1$ second last, etc. $v\_j$ is the weight assigned to interval $j$. Also, $p(j)$ is the interval to the left of $j$ that ends as close to the beginning of $j$ as possible without overlapping. We're assuming these were also computed beforehand.

The textbook I'm looking at says the runtime is $O(n)$ because a single call to M-Compute-Opt is $O(1)$ and we call it twice for every *empty* entry in array M. I almost buy it except it seems to me that we could end up calling it more often for some $i \in \\{1, \ldots , j\\}$ if the function $p$ maps lots of elements to that $i$. For example, if there is some interval $i$ where right after it ends a ton of intervals start, $p$ would map lots of intervals to it. And of course M-Compute-Opt wouldn't be called from within those instances since the value would be stored the first time, but it seems they would run nonetheless.

I guess in general I understand the argument given in the book, but I was wondering if there is a good one way to understand the linear time from a more intuitive standpoint. I'm not used to calculating runtimes and I feel like if I saw a different problem like this one I wouldn't come up with the "trick" used.

# Answer
> 0 votes
If I understand your concern correctly, you are right in that many $p(j)$ may give the same $i$. But that means that other $i$s don't get many $p(j)$s (the total of them is $n$).

# Answer
> 0 votes
The solution you sketched is using *recursion with memoization*. One of the reasons to prefer dynamic programming over recursion is because it is much simpler to analyze. Let us analyze the running time of the following snippet (the recusive function is the same as yours, I just renamed it `opt`):

```
def opt(j):
    if j == 0:
        return 0
    elif M[j] is not None:
        return M[j]
    else:
        M[j] = max(v_j + opt(p(j)), opt(j - 1))
        return M[j]

for i in range(n + 1):
    opt(i)

print(opt(n))

```

Observe that it first calls `opt(0)`, which is the base case, which is constant time. Now, `opt(1)` results in two recursive calls, both being `opt(0)`. But this we know is two calls, each with constant time complexity.

Now, consider any `j` in the `for`-loop. Since every smaller `j'` is already computed, when we call `opt(j)`, the two values `opt(p(j))` and `opt(j-1)` corresponds to a single lookup in `M`. Hence to compute `opt(j)` when we already have all smaller values, we need only constant time.

It follows that the entire body above runs in time $O(n)$.

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


# Question
Title: Queries regarding simulation of multi-tape turing machine using single tape turing machine
I was going through the classic text *"Introduction to Automata Theory, Languages, and Computation"* by Jeffrey Ullman,John Hopcroft and Rajeev Motwani, where I came across the simulation of MULTI-TAPE turing machine using SINGLE-TAPE turing machine as follows.

Before the simulation the MULTI-TAPE turing machine is defined as follows:

> A multitape TM is as suggested by Figure below. The device has a finite control (state), and some finite number of tapes. Each tape is divided into cells, and each cell can hold any symbol of the finite tape alphabet. As in the single-tape TM, the set of tape symbols includes a blank, and has a subset called the input symbols, of which the blank is not a member. The set of states includes an initial state and some accepting states. Initially:
>
> 1. The input, a finite sequence of input symbols, is placed on the first tape.
> 2. All other cells of all the tapes hold the blank.
> 3. The finite control is in the initial state.
> 4. The head of the first tape is at the left end of the input.
> 5. **All other tape heads are at some arbitrary cell.** Since tapes other than the first tape are completely blank, it does not matter where the head is placed initially all cells of these tapes "look" the same.
>
> Fig.1: A multitape TM

Now the simulation is as follows:

> $Theorem$ $1$: Every language accepted by a multitape TM is recursively enumerable.
>
> PROOF: The proof is suggested by $Fig.2$. Suppose language $L$ is accepted by a $k$-tape TM $M$ . We simulate $M$ with a one-tape TM $N$ whose tape we think of as having $2k$ tracks. Half these tracks hold the tapes of $M$ , and the other half of the tracks each hold only a single marker that indicates where the head for the corresponding tape of $M$ is currently located. We assume $k = 2$. The second and fourth tracks hold the contents of the first and second tapes of $M$ , track $1$ holds the position of the head of tape $1$, and track $3$ holds the position of the second tape head.
>
> Fig.2: SIMULATION OF MULTI-TAPE TURING MACHINE USING SINGLE TAPE TURING MACHINE
>
> To simulate a move of $M$ , $N$ 's head must visit the $k$ head markers. So that $N$ not get lost, it must remember how many head markers are to its left at all times that count is stored as a component of N 's finite control. After visiting each head marker and storing the scanned symbol in a component of its finite control, $N$ knows what tape symbols are being scanned by each of $M$ 's heads. $N$ also knows the state of $M$ , which it stores in $N$ 's own finite control. Thus, $N$ knows what move $M$ will make.
>
> $N$ now revisits each of the head markers on its tape, changes the symbol in the track representing the corresponding tapes of $M$ , and moves the head markers left or right, if necessary. Finally, $N$ changes the state of $M$ as recorded in its own finite control. At this point, $N$ has simulated one move of $M$ .
>
> **We select as $N$ 's accepting states all those states that record $M$ 's state as one of the accepting states of $M$** . Thus, whenever the simulated $M$ accepts, $N$ also accepts, and $N$ does not accept otherwise.▄

My query is : In the first line of the last paragraph of $Theorem$ $1$ what does the author mean by- `We select as N's accepting states all those states that record M's state as one of the accepting states of M.` I feel that it means -*all those states of $N$ are marked as accepting states which simulates one of the many accepting states of $M$.* I don't know, may be I am wrong, please correct if I am.

Then the author moves on to say,

*Why one cannot store tape-head positions as integers in the finite control?*

He says:

> One could argue that after n moves, the TM can have tape head positions that must be within n positions of original head positions, and so the head only has to store integers up to n. **The problem is that, while the positions are finite at any time, the complete set of positions possible at any time is infinite.**

My query is as follows : When the author considers the question,*Why one cannot store tape-head positions as integers in the finite control?* He justifies it by saying that `The problem is that, while the positions are finite at any time, the complete set of positions possible at any time is infinite.` Now the position number is finite. Now as per me, number of moves is also finite,so on adding or subtracting a finite number(due to the moves) to the position, we get a finite number as position. But is it so that the infiniteness described above is due to the fact that we do not possibly know the maximum number of finite moves exactly.

The author then derives the time-complexity of operation of the simulation as:

> $Theorem$ $2$: The time taken by the one-tape TM $N$ of previous theorem to simulate $n$ moves of the $k$-tape TM $M$ is $O(n^{2})$.
>
> PROOF: **After $n$ moves of $M$ , the tape head markers cannot have separated by more than $2n$ cells.** Thus, if $N$ starts at the leftmost marker, it has to move no more than $2n$ cells right, to find all the head markers. It can then make an excursion leftward, changing the contents of the simulated tapes of $M$ , and moving head markers left or right as needed. Doing so requires no more than $2n$ moves left, plus at most $2k$ moves to reverse direction and write a marker $X$ in the cell to the right (in the case that a tape head of $M$ moves right). Thus, the number of moves by $N$ needed to simulate one of the first $n$ moves is no more than $4n + 2k$. Since $k$ is a constant, independent of the number of moves simulated, this number of moves is $O(n)$. To simulate $n$ moves requires no more than $n$ times this amount, or $O(n^{2})$.▄

Now my query is when the author is considering the derivation of the time complexity of the simulation he says that after $n$ moves of the MULTI-TAPE turing machine, the relative position of the head markers in the simulation is at most $2n$ (i.e. worst case). Now the tape-head markers are arbitrary distance apart before any move of the multi-tape TM. Let the distance be $d$. So after the said $n$ moves of the multi-tape turing machine, the left head marker can go at most $n$ cells left and the right head marker can go at most $n$ cells right. So the relative worst case distance is $2n+d$. Now in each move the relative distance is obviously upper bounded by the term $2n+d$ and then we do the later calculation. The way I am thinking I am getting an extra term $d$ , which is not considered by the author.

# Answer
> 1 votes
Let me answer the two later questions: When simulating a concrete M, the number of tapes (or head markers) is a constant. Therefore I can afford to store the number of markers seen it in the state.

When starting the simulation, we simply call the cells on all the tapes where the head is standing as cell 0. Therefore, the initial distance is 0.

---
Tags: complexity-theory, turing-machines, computability, automata, simulation
---


# Question
Title: Understanding the Relationship Between CPU Registers Amounts and Maximum RAM in 32-bit Architectures
To my knowledge,

The number of CPU registers can tell us the maximum RAM we can have. I am only talking about physical memory, no virtual memory or virtualization in my question.

A 32-bit CPU architecture with 32 registers, each one bit, can give us `2^32 = 4GB RAM (a bit, which is either true or false, times how many registers we have)`

What confuses me is that, for example, Intel 32-bit CPUs have 8 General Purpose Registers, which is not equal to `2^32`, but `2^8`, because 4GB is user data; that is why it should be general purpose registers in my opinion.

What also confuses me is that `2^32 = 4GB RAM` does not consider any `single register from the 32 registers` to be used as an `instruction set` to manipulate register data, as all 32 registers are for 4GB RAM data usage.

I do not hold a CS degree, but I am curious about low-level stuff that is usually abstracted from the user.

Thanks!

# Answer
> 3 votes
There is absolutely no causal relation between number of registers and maximum amount of RAM. Relation between register size and RAM is limited because x86 16 bit processors had segment registers which made much more addres space available. And then the RAM that you have can exceed the address space, for example some Intel processors allowed 4GB address space per process, but up to 64 GB of RAM. That would make sense for a server chip that has 100 processes running at the same time.

---
Tags: computer-architecture, operating-systems, cpu, memory-hardware
---


# Question
Title: Abstract Interpretation: prove that the sign subtraction is increasing in each of its parameters
I need to prove that the binary operator $-\_\pm: \mathbb{P}^\pm\times\mathbb{P}^\pm\rightarrow\mathbb{P}^\pm$ is increasing in each of its arguments, where

$$ \mathbb{P}^\pm = \\{\top\_\pm, \leq0,\neq0, \geq0,\<0,=0,\>0,\bot\_\pm\\} $$

are the abstract properties it operates on. They represent the "signs" of values in $\mathbb Z$.

Their concretizations are, resp.,

$$ \mathcal{P}^\pm = \\{ \mathbb Z, \\{z \in \mathbb Z \mid z \leq0\\}, \\{z \in \mathbb Z \mid z \neq0\\}, \\{z \in \mathbb Z \mid z \geq0\\}, \ldots, \emptyset \\} $$

The concretization of a sign property $s$ is given by $\gamma(s)$, where $\gamma$ is an isomorphism between the posets $(\mathcal{P}^\pm, \subseteq)$ and $(\mathbb{P}^\pm, \sqsubseteq)$, and

$$ \forall s\_1,s\_2\in\mathbb{P}^\pm . s\_1 \sqsubseteq s\_2 \iff \gamma(s\_1)\subseteq\gamma(s\_2). $$

I couldn't find any smart way to prove the monotonicity of $-\_\pm$, so I just built an $8\times8$ "subtraction table" with $s\_1-\_\pm s\_2$ for every possible pair of signs. For each valid $i$, let $r\_i$ be the $i$-th row, and $s\_i$ the property associated with $r\_i$. I simply verified that if $s\_i \sqsubseteq s\_j$ then, for all valid $k$, $r\_{ik}\sqsubseteq r\_{jk}$. I did the same for the columns.

This is quite bruteforc-y, although it didn't take long thanks to the table. I'd just like to know whether this is the correct way to solve this exercise or not.

# Answer
If $P$ is a property, let $\alpha(P)$ be its best sound abstraction. *"Sound"* means that $P\subseteq \gamma(\alpha(P))$, that is, $\alpha(P)$ *overapproximates* $P$. *"Best"* means that if $p$ is another sound abstraction of $P$, then $\alpha(P)\sqsubseteq p$, that is, $\gamma(\alpha(P))\subseteq \gamma(p)$, that is, $\alpha(P)$ is more *precise*.

The operator $-\_\pm$ was naturally defined such that it's optimal w.r.t. the abstract properties, that is

$$ s\_1 -\_\pm s\_2 = \alpha\_\pm (\\{x-y \mid x\in \gamma\_\pm(s\_1) \wedge y\in \gamma\_\pm(s\_2)\\}) $$

For instance:

\begin{align} (\>0) -\_\pm (\<0) &= \alpha\_\pm(\\{x \mid x\>0\\} -^\* \\{y \mid y\<0\\}) \\ &= \alpha\_\pm(\\{x \mid x\>0\\} +^\* \\{y \mid y\>0\\}) \\ &= \alpha\_\pm(\\{x \mid x\>0\\}) \\ &= (\>0) \end{align}

where I introduced the two star operators for convenience. (I leave the trivial definition to the reader.)

Let's define $f$ as follows:

$$ f(s, t) = \\{x-y \mid x\in \gamma\_\pm(s) \wedge y\in \gamma\_\pm(t)\\} $$

Note that $s\_1\ -\_\pm s\_2 = \alpha\_\pm(f(s\_1, s\_2))$.

It's now easy to see that, for all valid $s\_2$:

\begin{align} s\_1 \sqsubseteq s\_1' &\implies \gamma\_\pm(s\_1) \subseteq \gamma\_\pm (s\_1') \\ &\implies f(s\_1, s\_2) \subseteq f(s\_1', s\_2) \\ &\implies s\_1 -\_\pm s\_2 \sqsubseteq s\_1' -\_\pm s\_2 \end{align}

The last implication follows from the fact that $\alpha$ is also increasing. Indeed, for every properties $P$ and $Q$ such that $P \subseteq Q$, we must have $P \subseteq Q \subseteq \gamma(\alpha(Q))$, which means that $\alpha(Q)$ is also a *sound* abstraction for $P$. For the optimality of $\alpha$, we must thus have $\alpha(P) \sqsubseteq \alpha(Q)$, which proves the monotonicity.

We can reason analogously for $s\_2$, which concludes the proof.
> 3 votes

---
Tags: formal-methods, static-analysis
---


# Question
Title: Searching for a Connected Graph with Vertex Count $n$ and Path Lengths Less Than $k$
**Question:**

I'm looking for a type of connected graph where the number of vertices is $n$ and every pair of vertices is connected by a path with a length less than $k$, where $k$ is a constant. Are there any types of graphs that satisfy this property, apart from complete graphs?

If anyone has insights or suggestions on different types of graphs or specific properties that meet these criteria, I would greatly appreciate it.

# Answer
The diameter of a graph is the length of the longest shortest path. Thus, you are describing graphs of bounded diameter, or graphs diameter $k-1$ in your case. Complete graphs you mention have diameter one.
> 2 votes

---
Tags: graphs
---


# Question
Title: how do universal turing machines actually work
a TM has states and a tape, and a set of symbols that can get put on the tape. when it 'reads' a symbol on the tape, it's current 'state' tells it what to do next; write a new symbol, where to move next, and what state to transition to.

i do not understand how 'reading' one set of symbols out of the limited set the UTM can already read, can lead it to 'invent' new states and new symbols of potentially unlimited scope.

I get in theory, humans can use symbols to represent other more complex symbols or instructions, e.g. i can represent 'train' by the letter 't' or i can use '1111' to represent 17' - but how can a UTM, upon reading a set of familar symbols, know that it needs to use that set of symbols to stand in for a set of states it does not already have in its library?

# Answer
Actually, UTM's work just the same way as actual, physical computers -- they store their instructions in memory.

Therefore it's easiest to conceptualize a UTM with two tapes: one (read-only) that holds the description of the TM to be simulated (in some standardized format), and one that holds the data to be manipulated. The rules of the universal TM says that the tapeheads should work according to the rules of the input TM.

Of course, everything that can be done with two tapes can be achieved with one as well, but single-tape UTM's have to jump between code and data constantly, thus spending longer time.
> 2 votes

---
Tags: algorithms, complexity-theory, turing-machines
---


# Question
Title: Why is handling word sizes smaller than the native size of a processor sometimes slower?
For example on modern (32-64 bit CPUs), some sources say that manipulating a 32-bit or 64-bit integer will actually be faster than manipulating an 8-bit or 16-bit integer. This the reason for the `(u)int_fastN_t` types to be defined in C. Somehow the 8-bit instructions or 16-bit instructions are *'slower.'*

Other sources say that loading a 16-bit number on a 32-bit machine would require a 32-bit load and a shift to extract the relevant bits. In the cast of having to shift, this would imply that some/all 16-bit instructions **do not exist at all** so they have to be emulated. (Because if, for example, a 16-bit load existed, this 32-bit load and shift would not be necessary).

But if they do, is there any reason why a CPU could not have opcodes for smaller sizes than the CPU native word size? And if they did is there any reason why they would be slower? If an 8-bit add instruction exists, why would the 8-bit adder circuit in the chip somehow be slower?

# Answer
> 3 votes
It depends entirely on the CPU. Adding an instruction costs transistors, as does making an instruction run faster, and those transistors then can't be used to improve the CPU in some other way.

As far as I know, the 8-bit adders on CPUs that support 8-bit addition are not any slower than 32-bit adders. The problem isn't the arithmetic operation but all of the bookkeeping that surrounds it: instruction decoding and scheduling and register management.

On x86, 16-bit instructions require a 1-byte prefix that 8- and 32-bit instructions don't, and I think that made 16-bit operations somewhat slower in the past, though I also think that difference has largely vanished on newer chips. Another problem with x86/x64 is that, for historical reasons, 8-bit and 16-bit operations leave the other bits of the 32-bit or 64-bit target register unchanged. That means in some cases the CPU has to wait for the previous instruction that wrote the register to finish in order to get the high bits, which limits parallelism. Older Intel CPUs, all the way back to the Pentium Pro in 1995, had fancier register tracking that avoided that problem, but newer CPUs have lost the ability. I don't know why, but it was probably to save transistors. For x64, AMD defined 32-bit instructions to clear the high 32 bits of the target register instead of preserving them, so 32-bit operations don't have this problem. They didn't change the behavior of the 8-bit and 16-bit instructions—probably to save transistors—so they are still slower on x64.

x86/x64 have no instructions that load or store less than 8 bits, so if you want to store 4- or 2-bit values space-efficiently you have to do it by hand. Some architectures bottom out at 32 bits instead, so 16- and 8-bit values have to be packed and unpacked by hand.

---
Tags: cpu
---


# Question
Title: Finding the Largest Partition of Non-Connected Nodes in a Graph in polynomial time
I have a graph, and I want to determine the largest possible set (or partition) of nodes such that no two nodes within this set have an edge between them. I am looking for an efficient algorithm to solve this problem.

For instance, given the following graph:

1: \[2\] 2: \[1, 3, 5, 6, 4\] 3: \[2, 4\] 4: \[3, 5, 6, 2\] 5: \[4, 2\] 6: \[4, 2\] The largest partition of non-connected nodes would be {1, 3, 5, 6}.

My current approach is brute-force: I generate all combinations of nodes and then verify if any of the nodes within a combination share an edge. This method, however, is not efficient for larger graphs.

Graphically, I intuitively group unconnected nodes together, and as I add nodes to this group, I can easily identify the largest possible set of non-connected nodes. Is there a way to replicate this intuition algorithmically?

# Answer
> 3 votes
No, the intuition doesn't really scale very well, especially not if you want the optimal solution.

The problem is known as Independent Set and is not only NP-complete, but even W\[1\]-complete.

You can try the following *greedy algorithm*: pick the smallest degree neighbor into your solution, delete the neighborhood, and rinse and repeat. Of course this is not guaranteed to give a very good answer, but it does give a solution which is not more than a factor $1/\Delta$ smaller than the optimal, where $\Delta$ is the maximum degree of the input graph.

Another alternative is to use LP rounding for finding the smallest vertex cover. The complement of a vertex cover is an independent set. You can also experiment with using randomized rounding:

LP relaxation for I.S.: maximize $\sum\_{v \in V} x\_v$ constrained to $x\_u + x\_v \leq 1$ for every edge $uv \in E$, and $0 \leq x\_v \leq 1$ for all $v \in V$. With randomized rounding, we take the variable $x\_v$ as the *probability of selecting* $v$ to the solution. Finally clean up the solution by removing arbitrarily endpoints of edges in the solution.

---
Tags: algorithms, complexity-theory, graphs, np-complete, discrete-mathematics
---


title: Randomizing pairing in "gift swawp"

text:
# Question
Title: Randomizing pairing in "gift swawp"
# The problem

I'm arranging a "gift swap" for Christmas with N people involved (N \> 2).

I want to create an algorithm that generate the pairing gifter-\>giftee so that:

1. everyone receives a gift
2. no one sends gift to themselves
3. no pair end in a "gift-closed loop" (person 1 sends gift to person 2, person 2 sends gift to person 1)

**Is there an algorithm that satisfies these 3 requirements?**

# My approach (so far)

For the following tests/examples, I use N = 4. So the involved people are 0, 1, 2 and 3.

## Easy approach

An easy way to satisfy all the 3 requests is to create a list of the involved people, where person\[i\] sends the gift to person\[i + 1\] (at the end of the list, person\[N - 1\] sends gift to person\[0\]). In our 4 people example, we have the list:

```
0 1 2 3

```

and we have that

```
0 sends gift to 1
1 sends gift to 2
2 sends gift to 3
3 sends gift to 0

```

Easy and functional. Win-win. But...

## Need more randomness

Participants will subscribe to the event. There will be the first subscriber, then the second, ... Given the nature of the group that will participate, it is quite likely that the first X participants will subscribe to the event in the same chronological order in the next years. So, next year, I'll have the same gifter-\>giftee pairs for them. I don't like it.

To overcome the problem, I've added a preliminary "list scrambling" step. So, from the original list

```
0 1 2 3

```

I generate a scambled version of the list

```
1 3 2 0

```

so now we have that

```
1 sends gift to 3
3 sends gift to 2
2 sends gift to 0
0 sends gift to 1

```

Note: it can happen that I get the exact same scrambled list next year, so I still have the "same pairing" problem. But it's quite unlikely. Or better, unlikely enough for me.

Due to the "person\[i\] sends the gift to person\[i + 1\]" algorithm, this still satisfies requests (1) and (2). But...

## The "gift-closed loop" problem

It can happen that the randomized list will be

```
1 0 3 2

```

so we have that

```
1 sends gift to 0
0 sends gift to 1
3 sends gift to 2
2 sends gift to 3

```

So we have a "gift-closed loop" between 0 and 1, and between 2 and 3.

NOTE: there are a couple more examples that produce this problem

My main questions are: **How do I prevent this problem? Is there a randomizing algorithm that avoid this?**

## Iterative method

There is an iterative method to avoid this, that is:

* check if a closed loop exists
* if it exists, do one of the following:
    + generate a new random list (brute force method)
    + take one of the people in the closed loop from the list and swap with another random person in the list
* loop until the problem is solved

This will work...eventually... I really don't like the iterative approach.

# Answer
> 4 votes
Shuffle the numbers $0,1,2,\dots,n-1$ into a random order. Then each person finds their place in this order and gives a gift to the next person in this order. This meets all of your requirements, and introduces plenty of randomness.

For instance, the sequence $1,0,3,2$ means that 1 gives to 0, 0 gives to 3, 3 gives to 2, and 2 gives to 1. There is no "gift-closed loop".

---
Tags: algorithms, sorting
---


title: How does a CPU do function calls?

text:
# Question
Title: How does a CPU do function calls?
Besides basic instructions for a general-purpose computer (binary arithmetic, move instruction, and jump on condition), it seems you can't implement a *universal* turing machine (is that even the right term?) without something more. That something is the ability to do arbitrary levels of function calls, I believe, yet how does a CPU implement them?

Setting a return address before jumping to the function code works for one call, but what if there are nested function calls? How will the CPU keep track of all the return addresses?

Is there a return address **stack** on the CPU (limited to memory on chip), or is it emulated in software at the assembler using regular RAM?

(In case it matters, I'll ask on behalf of Intel 8088 or 80x86 CPUs.)

Thanks!

# Answer
> 5 votes
Note that Turing machines don't have *any* function calls, and they work just fine as Turing machines. Function calls are not a necessity for Turing-completeness. All non-recursive function calls can simply be inlined. Recursive functions can be translated to loops using an explicit stack, the same way the CPU actually executes them (see below).

---

A typical 32-bit CALL instruction simply does the following:

* Decrement the stack pointer by 4
* Write the address of the next instruction at the address stored in the stack pointer (i.e. `WriteMemory(ESP, EIP);` \- EIP having already been incremented to the next instruction)
* Set the program counter to the address being called (i.e. `EIP := Operand;`)

and the RET (return) instruction does the following:

* Set the program counter to the value stored in memory at the address stored in the stack pointer (i.e. `EIP := ReadMemory(ESP);`)
* Increment the stack pointer by 4

(On a general-purpose CPU) There is no special hardware stack. There *are* instructions designed for use with a stack in normal memory (`PUSH`, `POP`, `CALL`, `RET`, `ENTER`, `LEAVE`, and the `ESP` and `EBP` registers and associated addressing modes). It's the software's responsibility to set aside some memory space for the stack. Software is also mostly responsible for deciding how to use it - if you want to write a program with no function calls, more power to you. There are some cases where the CPU will use the stack anyway - like interrupt handling - so even if you didn't use the stack in your software you'd want to set aside a small amount of space for interrupts. Interrupts are not required for Turing-completeness. Other architectures, like ARM, don't need a stack for interrupts - it's purely a design choice.

---

Modern CPUs do *also* remember the last several return addresses in a special stack memory unit on the CPU. However, this is purely for speculative execution - an optimization. The CPU will start speculatively executing the code at the address stored in its own stack, while it waits to read the real address from memory. If it gets the address right, it has a head start.

Some *non-von-Neumann* machines, like some small microcontrollers, do have a special stack memory unit that is the *only* place the return addresses are stored. However, those aren't the general-purpose CPUs you're thinking of.

# Answer
> 3 votes
> Is there a return address stack on the CPU (limited to memory on chip), or is it emulated in software at the assembler using regular RAM?

**Yes.**

* Some processors do not have a stack (and need to emulate it using RAM for everything)
* Some have a fixed size stack
* Most use general purpose ram via a stack register
* Some have a stack that is partially in CPU cache and partially in RAM.

80x86 uses a stack pointer register SS:(E)SP

# Answer
> 1 votes
Worth mentioning is what POWER and PowerPC do: These processors have a special register intended for returning from a call. There is an instruction BL (Branch and Link) which jumps to the address of a subroutine, and leaves the address of the instruction after the BL instruction in the "Link" register. The function that was called can store that address on the stack and later read it from the stack and return.

However, you always end up with a function that doesn't call any other function, a so-called "leaf" function. So if you call a leaf function that function will not do anything with the contents of the Link register other than using it to return to the caller, so calling leaf functions is quite a bit faster. (These processors use another trick: They *always* have something like 100 byte or so reserved on the stack beyond what is actually needed. So if a leaf function doesn't need more than these 100 bytes on the stack, it just uses the spare space and doesn't bother allocating or deallocating any stack space. So that saves quite a bit of space again).

The effect of this is that especially for small functions, there is practically no overhead for calling them instead of inlining. The total cost can be just a "branch and link" instruction plus an instruction to jump back through the link register. And because this is all done by the independent branch unit, it basically takes no time whatsoever.

---
Tags: turing-machines, computer-architecture, cpu, assembly
---


# Question
Title: Why boolean value in Python is 24/28 bytes?
What is the reason for this behavior? Usually, in other programming languages, it is either 4/8 bytes, if I am correct.

# Answer
> 2 votes
A boolean value can be represented with just one bit, but are usually four or eight bytes long in most statically typed languages because dealing with values smaller than the register size (four or eight bytes) can be inconvenient. But Python is object-oriented and dynamically typed, meaning that every value is an object and that every value carries information about its type. So you need a lot of metadata you otherwise wouldn't need.

Looking at Python' source code, you'll see that bools are actually implemented as long integers having the values 0 or 1. And "long objects" are defined as follows:

```
typedef struct _PyLongValue {
    uintptr_t lv_tag; /* Number of digits, sign and flags */
    digit ob_digit[1];
} _PyLongValue;

struct _longobject {
    PyObject_HEAD
    _PyLongValue long_value;
};

```

`PyObject_HEAD` is an alias for `PyObject`, defined as:

```
typedef struct {
    Py_ssize_t ob_refcnt;   /* object reference count */
    PyTypeObject* ob_type;  /* object type */
};

```

If we sum the sizes of all the structs' members, we get 28 bytes in total; 8 for `ob_refcnt`, 8 for `ob_type`, 8 for `lv_tag` and 4 for `ob_digit[1]`.

Isn't using 28 bytes for a single boolean wasteful? Probably not since memory allocators allocate memory in chunks to reduce bookkeeping. I haven't checked, but I guess that the smallest chunk Python can allocate is 32 bytes. So it doesn't matter if the object is one byte or 28 bytes. Furthermore, there will never be more than two boolean values in the runtime since every reference to true and every reference to false points to the same object.

---
Tags: data-structures, python
---