# Question
Title: What is the difference between transmission delay, queuing delay, and processing delay?
My book defines queuing delay as the time the packet waits to be transmitted onto the link. It defines transmission delay as the amount of time required to push all of the packet's bits onto the link. It defines processing delay as "the time required to examine the packet’s header and determine where to direct the packet". I do not completely understand the difference. The first two sound very similar and processing delay sounds like it is part of one of the other two. Can anyone explain me the difference?

# Answer
> 3 votes
There's some similarity. In the end, they all get bundled up into one big "delay" factor, but the size of the delays depends on different factors so it makes sense to break them apart.

* Transmission delay is a delay based on how long it takes to send the signal down the transmission line. This includes costs like the time it takes for an EM signal (or other signal) to propagate from one side to the other. It also includes costs like training signals that are often put on the front of a packet to help the receiver synchronize clocks. The important factor to transmission delays is that the packet is in motion. Once the transmission period starts, bits have to keep appearing on the wire one after another, without unexpected delays.
* Queuing delay is a delay based on how long the packet has to sit around in the router. Quite often the wire is busy, so we can't transmit a packet immediately. In these cases, the packet sits, ready to go, in a queue. These delays are almost entirely defined by the amount of traffic on the network (often queuing delay is the only traffic dependent part of the puzzle!). The more traffic there is, the more likely a packet finds itself stuck behind another packet in the queue, just sitting in memory, waiting.
* Processing delay is the delay based on how long it takes the router to figure out where to send the packet. Once it figures it out, it will queue the packet for transmission. These costs are predominantly based on the complexity of the protocol. The router must decode enough of the packet to figure out which queue to put the packet in. Sometimes that's easy, sometimes it's not. Typically the lower level layers of the stack have simpler protocols. If a switch doesn't already know which physical port to send a packet to, it will typically send it to all ports, queuing the packet in many queues immediately. On the other hand, at a higher level such as those which come into play in IP protocols, the processing may include making an ARP request to find out the physical address of the destination *before* queuing the packet for transmission. One may choose to call that a processing delay.

# Answer
> 2 votes
Late answer, but hopefully I can add something to what the others have already said.

**Processing delay**

The name is pretty self-explanatory, but I feel like the main hurdle to understanding this is that one might find it difficult to put their finger on what exactly 'processing' consists of. What does, for example, a router do, that would fall under 'processing' a packet? This also depends on the routing protocol employed as well as the IP protocol involved (the structure of an IPv6 datagram is quite different from that of IPv4 and different actions might be required when processing them), but some examples might be (I'm writing these with IPv4):

* decapsulating the ethernet frame into an IP datagram
* computing the Internet checksum (not in ipv6)
* decrementing the TTL field value
* acting on the possible options in the options field of the datagram header, if any (no such field in Ipv6)
* performing a routing decision, determining the appropriate output port, based on a certain routing protocol
* getting the packet from the input port buffer into the output port buffer via the switching fabric of the router
* splitting a datagram into smaller datagrams if the original one is too big to fit the MTU of the outgoing link (this is IP fragmentation, which isn't a thing in ipv6)
* encapsulating the datagram into a frame to be sent out onto the link

**Transmission delay**

The difficulty I find a lot of people have here is with understanding the difference between processing delay and transmission delay. The answer is that they measure different things. Processing, as seen above, measures the time it takes to process a packet (as exemplified above), whereas transmission has relatively nothing to do with processing, simply measuring the time it takes to push a packet onto the link.

At this stage, the packet is ALREADY PROCESSED, and it's just waiting for transmission. Put another way, imagine we have left off at the last bullet point in the previous 'processing delay' section. The packet is ready to go. What could be limiting this 'transmission' action if the packet (frame, here) is already processed? It's hardware. The action is bound by hardware. Specifically, the transmission delay is determined by the speed of the output line card. The transmission delay is how fast the line can push out the packet.

**Queuing delay**

Queuing delay is the most difficult one to estimate. It hinges on the other factors (e.g. the processing speed of the router), and so it's inextricably tied to the other types of delays that occur. Primarily, it's determined by how and how much traffic arrives at the queue, the so-called 'traffic intensity', and it can vary from packet to packet.

If traffic is highly congested and the speed of the switching fabric is much higher than the speed of transmission, for example, say 5 times as fast, and you have 50 packets arriving at the input ports and most happen to be pushed to the same output port, then the buffer of the output port will fill up faster than packets can be pushed out. If enough packets get queued up to overflow the buffer, packets start getting dropped.

# Answer
> 0 votes
Roughly speaking, *queuing delay* depends on the queue, how many packets are there in the system. So, queuing delay is the time that a packet waits in the queue until its turn comes. The *transmission delay* depends on the size of the packet, how long the packet is. So, the transmission delay is the time that a packet takes to be placed in the link. (After that comes the propagation delay which is the time that a packet takes to move in the link, which depends on the speed of light.) Finally, *processing delay* is like the time it takes to read the packet. The packet is arrived at destination and is waiting for processing, that's the processing delay.

# Answer
> 0 votes
### Explanation by Analogy

I'm using firearms analogy. Even if your culture has zero firearm education, you probably can still intuit from movies etc.:

* I have a gun.
* 6 bullets.
* I can only fire one after the other.

### Queuing Delay

Bullet number 6 is the last in the chamber. It has to wait until I fire all the bullets preceding it. This time period is the queuing delay.

### Propagation Delay

After they are fired, it takes a certain amount of time to hit a bullseye. This time period is the "propagation delay". If the target is far away, then the bullet will take a little more time to reach its destination, even though a bullet travels pretty quickly.

* If I fire in a vacuum - then the propagation will be the speed of the bullet itself.
* If I fire in the air: then it's still quick, but the air is viscous - the air actually slows a bullet down! This is called "drag".
* If I fire through water - the water makes the bullet slow down considerably. The propagation delay is very high.

The same concept applies when transmitting signals through a medium.

If you transmit using sound waves - the propagation delay will be slow. However, we transmit using electrical pulses and light: most signals travel just under the speed of light, because we are transmitting through mediums - e.g. fibre optic cables, and not a vacuum.

(According to Einstein, we cannot transmit faster than the speed of light. If you find out a way to do this: congratulations: you have won yourself a Noble prize).

### Transmission Delay

The time taken to load a bullet into a chamber. This is analogous to:

> ...the amount of time required to push (that is, transmit) all of the packet's bits into....\[a link\] (Computer Networking: A Top-Down Approach, 7th Edition)

Analogy ain't perfect, but I'm hoping (at least for some) that it helps conceptualise the concepts.

---
Tags: computer-networks
---


# Question
Title: Minimizing the number of distinct elements by picking one set from each set of sets
I have a problem as follows. Given a set of sets $U = \\{S\_1, S\_2, … S\_N\\}$ where $S\_i = \\{s\_1, s\_2, ... s\_m\\}$. Each $s\_j \in S\_i$ contains a set of distinct elements. I need to pick one $s\_j \in S\_i$ to form $N$ sets in total such that $|\bigcup\_{j=1}^N s\_j|$ is **minimized**.

Is there an efficient algorithm to solve this problem. I feel that this problem is $NP-hard$ as it is somewhat similar to the *maximum coverage problem*. I have yet to be able to formally prove this intuition by reduction from the maximum coverage problem.

# Answer
Your problem is NP-hard by a reduction from the (decision version of the) hitting set problem. Given a set $X = \\{x\_1, \dots, x\_n\\}$ of elements, a collection $A\_1, A\_2, \dots, A\_h$ of subsets of $X$, and an integer $k$, is there a subset $X'$ of at most $k$ elements from $X$ such that $A' \cap A\_i \neq \emptyset$ for all $i=1, \dots, h$?

To reduce an instance of hitting set to an instance of your problem you can choose $N=h$ and $S\_i = \\{ \\{ a \\} \mid a \in A\_i \\}$.

If there is a hitting set $A'$ of size at most $k$, then each set $S\_i$ contains at least one set $\\{a\\}$ for some $a \in A'$. Choosing one such set per $S\_i$ yields a solution to your problem of size at most $k$.

If there is a solution to your problem of size at most $k$, then the union of the selected sets contains at least one element in each $A\_i$ (since the sets in $S\_i$ contain only elements in $A\_i$), i.e., it is a hitting set.
> 1 votes

---
Tags: complexity-theory, optimization, np-hard
---


# Question
Title: Correctly compare names with different romanization?
I am running into a problem in which I have names with different romanization methods, and I need to correctly compare them to see which names match.

An example is romanized Korean variants: Seong vs Sung vs Song are all romanized variants of the same Korean character. A Levenshtein ratio would say that these are all different, but a human would be able to see that they're pretty much the same, i.e. Kyung Sung vs Kyeong Seong. I'd need the method to be able to go beyond just Levenshtein ratio and confidently say that they are an exact match (~1.0) instead of the ~0.8-0.9 that Levenshtein ratio would output.

I read a paper on Thai romanization that suggests Monge-Elkan is quite good if you have names without many typos in them, but goes down drastically if the names have typos. I can't guarantee that the data won't have typos unfortunately, so not sure if there is a better method? Any thoughts are appreciated!

# Answer
> 0 votes
You cannot address this without a complete list of character variants. Then you can precompute the legit combinations of all names and perform the comparison against all groups so obtained, keeping the shortest distance.

E.g. to match Kyong to Kyung, perform comparisons to Kyung and Kyeong, resulting in 1 substitution and 1 deletion respectively. Keep the one considered best.

# Answer
> 0 votes
The Soundex algorithm, or some variant of it tailored to the particular features of the Romanisation schemes, could be a good place to start.

Certainly some algorithm that is informed by phonetics and so on, is likely to perform better than an arbitrary algorithm designed to compare strings generally.

---
Tags: algorithms, natural-language-processing
---


title: 1's and 2's complement of 0

text:
# Question
Title: 1's and 2's complement of 0
In the Morris Mano's book on Digital Circuits Edition 3, it is defined that r's complement for N=0 is 0 and r-1 complement is not even defined.

But lets say r = base = 2

Then 2'd complement of 0, based on his formula is $r^n - N$ where $n$ is number of digits is $2^1 - 0 = 2$. This also makes sense because $(0)'' = (0)' + 1 \to 1 + 1 \to 10$ in binary and $2$ in decimal

Now coming on to 1's complement, the formula is $r^n - r^{-m} - N$ where $n$ is same as in 2's complement and $m$ is the number of digits after decimal. So, $2^1 - 2^0 - 0$ gives $2 - 1 - 0 \to 1$ which is also correct.

Does that mean that first line which is in the book is incorrect? For your information, I am reading the book addressed for Indian students.

# Answer
Zero in 1's complement is the same as zero in normal binary `0000 00000` but there's a weird quirk of 1's complement. In 1's complement you can get the negative version a number by flipping all of its bits so that means you can flip all the bits in zero to get `1111 1111` which has a value of -0.

2's complement avoids this problem by changing how you convert a number to negative. In 2's complement you make a number negative by flipping all the bits then adding 1. Here's what happens when you try to convert zero to a negative number with 2's complement:

1. you start with `0000 00000`
2. you flip all the bits to get `1111 1111`
3. you add 1 which overflows it back to `0000 00000`

**So to answer your question:**

The 1's complement of 0 is `0000 00000` and `1111 1111`

The 2's complement of 0 is `0000 00000`
> 2 votes

# Answer
> I see, so main thing is to disregard the overflown bit.

No, we don't ignore the "sign" digit. Like positive numbers having an infinite number of leading zeros, negative numbers in ***r*** and ***r - 1*** format have an infinite number of leading ***(r - 1)***'s. That is why we sign extend when storing a signed number into a larger storage object.
> 0 votes

---
Tags: binary
---


# Question
Title: Does an algorithm's space complexity include input?
Consider the Kadane's algorithm for finding maximum subarray within an array:

```
def max_subarray(numbers):
    """Find the largest sum of any contiguous subarray."""

    best_sum = 0
    current_sum = 0
    for x in numbers:
        current_sum = max(0, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum

```

The algorithm requires constant space to execute, apparently. But still, it accepts a list of `n` elements as input. So is its space complexity `O(n)` or `O(1)`?

# Answer
> 25 votes
It depends on the chosen convention. I often prefer the convention that considers that the input is not part of the space complexity, for different reasons:

* the space complexity of a function answer the question "do I have enough memory to finish my computation?". In that aspect, I consider that when calling a function, its argument is already written somewhere in the memory, and therefore there is no need to consider it for the future computation (we already know that there is enough space for the input).
* the complexity classes  and NL (problems that can be solved deterministically and non-deterministically respectively in logarithmic space) make no sense if you consider the input as part of the space complexity (otherwise any space complexity would always be at least linear).

# Answer
> 6 votes
> Auxiliary Space: The extra space that is taken by an algorithm temporarily to finish its work
>
> Space Complexity: Space complexity is the total space taken by the algorithm with respect to the input size plus the auxiliary space that the algorithm uses.

Referred from here

i.e., space complexity of a program on the whole also includes the space taken up by the input values. Space Complexity = Auxiliary space + Space used up by input values.

But when we compare two algorithms that have the same end goal with similar input types, often the space taken up by the input is disregarded. Only the auxiliary space of the algorithm is considered.

Hence it is said that Kadane's algorithm runs in constant space i.e. `O(1)`

# Answer
> 4 votes
No, the input does not count in the space complexity. The data has to be supplied anyway and if we counted it, no $o(n)$ complexity (in particular $O(1)$) would be possible.

# Answer
> 1 votes
Complexity analysis is usually done to compare algorithms that process the same input. In this case, it makes little sense to include the space of the input data, because it's the same for all algorithms being compared and doesn't affect the comparison.

However, we might want to compare algorithms that process different forms of input, e.g. arrays versus linked lists. In this case, the space used by the input is a function of the algorithm, so we should include the input space.

# Answer
> 0 votes
While the question has been mostly answered by other people, I want to make a note that in the algorithm described, you have to keep track of the index you are at to iterate to the next array element. This index tracker, at last position, grows as input grows, so it is not quite O(1) in terms of space, but O(lg(n)) (since you can keep the binary representation of the index).

Although, again, saying O(1) is convention in some places.

---
Tags: algorithms, space-complexity, python, space-analysis
---


# Question
Title: Time complexity of using BFS to find shortest path within k stops
I'm referencing this Leetcode question: https://leetcode.com/problems/cheapest-flights-within-k-stops/solution/, which asks you to find the length of the shortest path from source to dest using less than or equal to K intermediate nodes.

Since the solution is behind a paywall, I've taken screenshots of the solution and copy/pasted the solution code. Here it is (fyi, "price" and "distance" are synonymous -- they just mean the weights of the graph):

> ***Approach 1: Breadth First Search***
>
> **Intuition**:
>
> A breadth-first search is a good algorithm to use if we want to find the shortest path in an unweighted graph. The property of BFS is that the first time a node is reached during the traversal, it is reached at the minimum distance from the source. The same cannot be said for a weighted graph. For a weighted graph, a path having more edges does not necessarily mean the path is more expensive. Thus, we cannot employ a normal breadth-first search for weighted graphs.
>
> A breadth-first search has no way of knowing if a particular discovery of a node would give us the cheapest path to that node. The only possible way for BFS (or DFS) to find the shortest path in a weighted graph is to search the entire graph and keep recording the minimum distance from the source to the destination node.
>
> However, our problem limits the number of stops to $k$. As a result, we need not search the paths with lengths greater than $k + 1$. A breadth-first search can be used for this problem because the number of levels to be explored by the algorithm is bounded by $k$.
>
> In this approach, we will perform a level-wise iteration over the nodes. We will explore all the nodes at the present level (say $l$) before moving on to the nodes at the next level ($l + 1$). This level would correspond to the number of stops that would be limited by $k$. When we move from a level of $l$ to $l + 1$, we will increase the stops by 1. We are allowed a maximum of $k$ stops, which means we could go up to a maximum level of $k + 1$ from the src node, trying to reach dst at the minimum price.
>
> We can maintain an array dist which stores the minimum price to reach each node. When we want to move to a node, we will only consider edges where the total price after traversing the edge is less than the currently calculated dist\[node\]. This optimization helps us avoid TLE.
>
> **Algorithm:**
>
> 1. Create an adjacency list where adj\[X\] contains all the neighbors of node X and the corresponding price it takes to move to a neighbor.
> 2. Intialize dist array, storing the minimum price to reach a node from the src node. Intialize it with large values.
> 3. Initialize a queue storing {node, distance} pairs. Initially, the queue should have only {src, 0}.
> 4. Create a variable called stops and set its value to 0.
> 5. Perform BFS until the queue is empty or stops \> k:
>     * Iterate over all the nodes at a particular level. This will be done by starting a nested loop and visiting all the nodes currently present in the queue.
>     * At each pair {node, distance}, iterate over all the neighbors of node. For each neighbour, check if dist\[neighbor\] is less than distance + the price of the edge. If it is, then update dist\[neighbor\] and push {neighbor, dist\[neighbor\]} onto the queue.
>     * After iterating over all the nodes in the current level, increase stops by one. We've visited all the nodes at a particular level and are ready to visit the next level of nodes.
> 6. Once we reach a condition where either the queue is empty or stops == k, we have our answer as dist\[dst\]. If dist\[dst\] hasn't changed from the initial large value, then we never reached it, so return -1.
>
> **Solution code (in Java):**

```
class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<int[]>> adj = new HashMap<>();
        for (int[] i : flights)
            adj.computeIfAbsent(i[0], value -> new ArrayList<>()).add(new int[] { i[1], i[2] });

        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { src, 0 });
        int stops = 0;

        while (stops <= k && !q.isEmpty()) {
            int sz = q.size();
            // Iterate on current level.
            while (sz-- > 0) {
                int[] temp = q.poll();
                int node = temp[0];
                int distance = temp[1];

                if (!adj.containsKey(node))
                    continue;
                // Loop over neighbors of popped node.
                for (int[] e : adj.get(node)) {
                    int neighbour = e[0];
                    int price = e[1];
                    if (price + distance >= dist[neighbour])
                        continue;
                    dist[neighbour] = price + distance;
                    q.offer(new int[] { neighbour, dist[neighbour] });
                }
            }
            stops++;
        }
        return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
    }
}

```

> **Complexity Analysis:**
>
> Let $E$ be the number of flights and $N$ be the number of cities.
>
> *Time complexity:* $O(N + E \cdot K)$. Depending on improvements in the shortest distance for each node, we may process each edge multiple times. However, the maximum number of times an edge can be processed is limited by $K$ because that is the number of levels we will investigate in this algorithm. In the worst case, this takes $O(E \cdot K)$ time. We also need $O(E)$ to initialize the adjacency list and $O(N)$ to initialize the dist array.
>
> *Space Complexity:* $O(N + E \cdot K)$. We are processing at most $E \cdot K$ edges, so the queue takes up $O(E \cdot K)$ space in the worst case. We also need $O(E)$ space for the adjacency list and $O(N)$ space for the dist array.

The worst case time complexity of Leetcode BFS solution is stated as $O(N + E \cdot K)$. However, I'm confused why it isn't a factorial time complexity.

Imagine a strongly-connected directed graph with 4 nodes (numbered 1 to 4) and $K = 2$. If you draw a BFS tree with the following levels:

Level 1: Node 1 (the source node)

Level 2: Nodes 2, 3, 4

Level 3: Nodes 3, 4 (under Node 2 from previous level); Nodes 2, 4 (under Node 3 from previous level); Nodes 2, 3 (under Node 4 from previous level)

... (you can fill in level 4)

Then its clear the number of nodes in this tree is $O((N-1) \cdot (N-2)...(N-K-1))$. That is a factorial complexity. Why is the actual worst case time complexity written in the solution $O(N + E \cdot K)$ instead?

# Answer
Too long; did not read.

The easy solution: Let $w' = w + 10^{12}$. Now, find a solution of cost less than $k \cdot 10^{12}$

---

The more involved solution, but which in fact solves a more general problem:

From an input instance $G, s, t$ (assuming here the graph is directed, but it doesn't really matter).

Create $k$ copies $G\_1, G\_2, ..., G\_k$ of the original graph.

However, for every vertex $v\_i^j$ in $G\_i$, make the edges out of $v\_i^j$ point to its neighbors in $G\_{i+1}$ instead.

And then, create a new $t'$ such that every copy of $t$, $t\_1, t\_2, ..., t\_k$ points to $t'$, and then run BFS from $s$ to $t'$ in $G' = \bigcup {G\_1, ..., G\_k}$.

Now, $G'$ has at most $kn + 1$ vertices and $m + k$ edges.

---

Ps, the reason I say it solves a more general problem, is that you can use this technique to solve the version where you are allowed to use at most $k$ of a specific set $U \subseteq V$ of the vertices. In this case, whenever you use a vertex from $U$, you transport to the next layer, otherwise you are allowed to remain in the same layer.
> 1 votes

# Answer
Reminder ; when doing a BFS, you are keeping track of vertices you already visited. If you see a node that you already visited, you do not consider it and you "stop" there. This explains how the algorithm is not $N!$. Now as for the complexity given by the website, considering that BFS is $O(|V| + |E|)$, an "easier" version of it (the algorithm is just a BFS with an early stop) will clearly not be $O(|V| + k \cdot |E|)$, because $$ O(|V| + |E|) \subset O(|V| + k \cdot |E|)$$ for $k \geq 1$
> 0 votes

---
Tags: graphs, time-complexity
---


# Question
Title: How do I multiply 2 signed 4 bit numbers in a logic circuit?
I've been experimenting with making a binary calculator lately, and I've got the addition and subtraction working. I now want to start making a multiplier, but I have no idea where to even start. I know how to multiply two binary numbers. After all, it's the same as how we used to learn how to multiply. Observe this `-5 * 7` operation as an example.

```
        1011
      x 0111
------------
    11111011
    1111011X
    111011XX
------------
(10)11011101

```

This would result in `-35` written as decimal, which is correct. The first two bits are discarded as a result of overflow, hence the brackets. This works fine, but I don't see an obvious and concise way to put this in a logic circuit. Which leads me to my first question:

> How do I multiply 2 signed *(2's complement)* 4 bit numbers in/using a logic circuit?

If I find out a way to do that, I can try to fit it into my "calculator". But there's another problem: I have two signed 8 bit inputs but only one mere 8 bit output to work with. So I'll need some way of knowing that the output (or input(s)) is too big to fit in an 8 bit number, so my second (but less important) question is:

> How do I know if the output is too big to fit in an 8 bit number? And, is this already possible using the multiplier we just made?

# Answer
> 0 votes
As a basic block, you take an eight bit adder producing a nine bit result. You need seven of these.

Create eight 8-bit numbers Z0 to Z7. Zk is the AND of X AND bit k of Y, shifted left by k bit position, so the result is the sum of the Zk. Use the first adder to add Z0 and Z1. The lowest bit of Z0 is taken unchanged. Then you add 7 and 8 bits with a 9 bit result. Then you add Z2; you keep the lowest bit of the first sum unchanged and get 9 more bits. You continue and get the full 16 bit result. To detect overflow, you check if any of the highest 8 bits is non-zero.

It’s not a difficult circuit, it’s just BIG. And it’s almost what a modern CPU would do for a 64x64 bit multiplier. The difference is that you wouldn’t perform 63 additions in a row, but for create 64x64 bits, then use (4096 / 3) full adders which each take 3 bits of input and produce two bits of output, giving you about 2750 output bits. Then 920 full adders to reduce this to 1840 output bits and so on. This only takes logarithmic time.

---
Tags: arithmetic, binary, multiplication
---


# Question
Title: A program that solves the Halting Problem for programs with N states
My question relates to the conclusions drawn from the Halting Problem. I understand that the Halting Problem proves that no program H(P,i) exists that determines if P(i) halts or not for P in *general*. However, I think that this does not show that there is no program HN(P,i) that computes the Halting problem for a program P with exactly N states. If we take HN to be the program that does this computation with the fewest states possible, the proof does not necessarily work:

Defining the program X(A) that halts when HN(A,A) returns "Does Not Halt" and loops forever when it returns "Halts" does not necessarily imply a contradiction. This is because when we compute HN(X, X), we only get defined behavior if X has exactly N states, which is something that must be shown to continue the proof.

In fact, it could very well be the case that there are no programs that do this computation using N states, and that HN just returns some undefined output if we were to run this simulation.

Is there something I'm missing? I am not super knowledgeable on this topic.

edit: This would not imply a flaw in the reasoning behind the Halting Problem as a counterexample, but it shows that the Halting Problem does not show that programs that solve the Halting Problem for any arbitrary program with fixed states.

# Answer
> 0 votes
With the halting problem, the class of programs whose halting you determine, and the class of programs that we use to solve the problem, are the same.

If you examine programs with n states, you can’t in general find whether they are halting *using a program with n states*. We can find a program that determines if programs wig n states halt. But that doesn’t give us the contradiction.

---
Tags: turing-machines, undecidability, halting-problem, decidability
---


# Question
Title: Partitioning a graph into connected pairs and triplets
We need to partition an undirected graph into connected subgraphs of size between $2$ and $k$, where $k$ is an integer.

When $k=2$, the problem is equivalent to the perfect matching problem which is known to be solvable in polynomial time.

When $k=3$, the problem is similar to the partition into triangles problem, which is proved to be NP-complete by reduction from 3-dimensional perfect matching problem. But there are two differences: first, we allow subgraphs of size 2; And second, we allow subgraphs of size 3 that contain only two edges (i.e. paths).

Is there a polynomial-time algorithm for this problem, assuming $k=3$? Assuming $k$ is fixed? Assuming $k$ is part of the input?

# Answer
> 3 votes
The problem can be solved in the polynomial time for $k = 3$.

There is this paper by Chen *et al.*. The authors design an approximation algorithm for the *minimum $3$-path partition problem*. The *minimum $3$-path partition problem* is similar to your problem. It aims to partition the graph into minimum number of vertex disjoint paths each of size at most $3$. The only difference between this problem and your problem is that it allows a partition of size $1$, i.e., a singleton vertex.

In Section $2$, of the paper, authors design a polynomial time algorithm for computing *$3$-path partition with the least number of $1$-paths* ($1$-path means a singleton vertex). They further use this algorithm to design an approximation algorithm for the minimum $3$-path partition problem. However, this polynomial time algorithm gives a straightaway solution to your problem. If the algorithm returns a solution with non-zero number of $1$-paths, then the graph can not be partitioned into connected subgraphs of size between $2$ and $3$. And, if the algorithm returns a solution with no $1$-paths, then the graph can be partitioned into connected subgraphs of size between $2$ and $3$.

---
Tags: graphs, matching, partitions
---


# Question
Title: Time complexity of an uneven binary search
I have a concept binary search which doesn't split at the midpoint of a list, but at a ratio of 1:2.

If we abstract the search function time complexity into $T(n)$ then the function can recurse into two options:

* $T(n/3) + C(n)$
* $T(2n/3) + C(n)$

I am unable to understand how to properly find this time complexity using the methods I've learned so far, which doesn't include randomization or means or whatnot. I have been taught the master method, iteration method and perturbation method.

I was thinking that I just take the worst case, i.e. $T(2n/3) + C(n)$ and use that with the methods I know, but I don't feel like this would work for finding $\Theta(n)$ i.e. the tightest bound, but rather only for the upper bound. Would it be possible to find $\Theta(n)$ using the information given?

# Answer
We have $T(n) = \max(T(\frac n3), T(\frac {2n}3)) + C(n)$. If $C$ is non-decreasing (which is usually the case), we have $T(n) = T(\frac {2n}3) + C(n)$, so using the master theorem if $C(n) = \Theta(\log^k (n))$ (for $k \geq 0$) the solution is $T(n) = \Theta(\log^{k+1} (n))$. If $C(n) = \Omega(n^c)$ for some $c \> 0$ and it satisfies the regularity condition then $T(n) = \Theta(C(n))$.
> 1 votes

---
Tags: time-complexity, binary-search
---


# Question
Title: Computing the index of the n^{th} ancestor of a node in a perfect binary tree / heap
I *think* you can compute the index of the n^{th} ancestor of the node at index i using the formula: $\lfloor i / 2^n \rfloor$ where $n \in \mathbf{Z}^+$. Note that I am assuming that the parent node is at index 1 for this. Left child nodes have even indexes, and right child nodes have odd indexes. Nodes are number from top to bottom, left to right, with the root node being at the very top and the tree extending downwards.

I know that you can get the index of the parent via $\lfloor i / 2 \rfloor$. The only question is whether the rounding errors can potentially throw off the computation such that I need to compute the ancestor's index like: $\lfloor \cdots \lfloor \lfloor i / 2 \rfloor / 2 \rfloor \cdots / 2 \rfloor$.

My google-fu is failing me at the moment, so hoping one of you can verify one way or the other; extra points for a reference :)

EDIT: Of course, if you shift instead of divide its a moot point. However, I'm attempting to use this equation as part of a mathematical proof about how something can be modeled as a perfect binary tree; and dividing feels a little more appropriate in that context.

# Answer
For any node $i$, its children are $2i$ and $2i+1$.

Using induction, you can prove that its $n^{th}$ level descendants are: $2^{n} \cdot i + j$ for $j \in \\{0,\dotsc,2^n-1\\}$.

Equivalently, you can say that any descendant $d$ has its $n^{th}$ ancestor $\lfloor d/2^n \rfloor = i$
> 1 votes

---
Tags: binary-trees, heaps
---


# Question
Title: Is there a good way to hash abstract binding trees?
The hash function should be invariant under alpha-renaming. Using de Bruijn notation seems to be possible, but it requires alpha-converting the whole tree when a binding is created, and has the unhappy consequence that a substructure of an abt is not a well-formed abs (since the de Bruijn indices are broken). So, is there a good (neat, elegant and/or efficient) way to construct such a function? By the way, is there any study on this matter? Any help is appreciated!

# Answer
I found a paper published two years later. Hashing modulo alpha-equivalence. This provides an asymptotically faster way to achieve the goal, improving from $O(n^2)$ to $O(n \log^2 n)$.
> 0 votes

---
Tags: hash, variable-binding, syntax-trees
---


# Question
Title: Prove $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})=\Theta(n\log^2{n})$ using induction
Please first take a brief look at my previous question. Here I want to do something similar but for $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})$. I know the answer is $T(n)=\Theta(n\log^2{n})$ and I want to prove it using induction. I reached this assuming for $m\<n$, we have $T(m)\leq cm\log^2{m}$:

$\begin{align\*} T(n)=2T(\frac{n}{2})+\Theta(n\log{n})&\leq 2(c\dfrac{n}{2}\log^2{\frac{n}{2}})+\Theta(n\log{n})\\ &= cn(\log{n}-1)^2+\Theta(n\log{n})\\ &=cn(\log^2n-2\log{n}+1)+\Theta(n\log{n})\\ &=cn\log^2n+cn-2cn\log{n}+\Theta(n\log{n}) \end{align\*}$

At this point I can't go further. Also maybe we can reach $T(n)\leq cn\log^2n+cn+\Theta(n\log{n})$. But how can I reach $T(n)\leq cn\log^2n$? I tried to use stronger induction hypothesis like $T(m)\leq cm\log^2m-dm$ but I couldn't succeed. How can I show that? Any help is appreciated!

# Answer
> 1 votes
Let $c$ be the constant for the $\Theta$ expression, and show that $T(n) \leq c n \log^2 n$.

By induction, assume $n \geq 2$.

$\begin{align} T(n) &= 2T(n/2) + cn \log n\\ &\leq 2(c \frac n 2 \log^2 \frac n 2)) + cn \log n \text{ (by I.H.)}\\ &= cn \log \frac n 2 \log \frac n 2 + c n \log n\\ &= cn (\log n - 1)(\log n - 1) + cn \log n\\ &= cn (\log^2 n - 2\log n + 1) + cn \log n\\ &= cn \log^2 n - 2cn\log n + cn + cn \log n\\ &= cn \log^2 n - cn\log n + cn\\ &= cn \log^2 n + cn (1- \log n)\\ &\leq cn \log^2 n \end{align}$

# Answer
> 0 votes
Define S(m) = T(2^n). Write down a recursive formula for S(m) and solve it. Use the result to solve T(n).

---
Tags: time-complexity, algorithm-analysis, recurrence-relation, recursion, induction
---


# Question
Title: Why is Dyck-2 so important for the Chomsky-Schützenberger theorem?
I have read a lot of times, that models that can parse Dyck-2 are of great importance. It appears that Dyck-2 is interchangeably used like Dyck-N.

Afaik the Chomsky-Schützenberger representation theorem states that you can convert and context-free language into a Dyck-N language, using a homomorphism and a intersection to regular language.

It appears that Dyck-2 is already enough for that? Or is Dyck-2 simply necessary, but not sufficient, so it is just used to disprove a models ability to learn Dyck-N?

I thought maybe you can represent any Dyck-N language by a Dyck-2 language that uses "binary" representations of brackets. This would theoretically be also possible for Dyck-1 by unary encoding, but decoding there would not be suffix-free, which breaks the homomorphism, I guess? Maybe someone could validate this approach, because I have never seen it formulated out.

Thank you very much.

# Answer
> 3 votes
Whether 2-bracket Dyck is equivalent to $n$-bracket Dyck ($n\ge2$)? Short answer: that depends which operations one allows.

The Chomsky–Schützenberger Theorem states that every context-free language $L\subseteq \Sigma^\*$ can be written as $L=h(D\_{T}\cap R)$, where $D\_T$ is the Dyck language over the bracket pairs on $T\cup \overline T$, $R\subseteq (T\cup \overline T)^\*$ a regular language, and $h: (T\cup \overline T) \to \Sigma^\*$ a homomorphism.

Some intuition here. We can prove the CST using a representation of $L$ as a pushdown automaton. Each transition is represented as a sequence of brackets. These brackets represent both the input letter that is read and the symbols that are popped and pushed during that instruction. It is possible to show that two different pushdown symbols suffice for the PDA. On the othet hand $\Sigma$ is not bounded. As we use a homomorfism to decode $\Sigma$ from $T$, in general $T$ must be as least as large as $\Sigma$. Hence we cannot bound the number of bracket-pairs.

In the theory of Abstract Families of Languages one studies language families and their closure properties. We have the result that the context-free languages are a cone, the smallest family of languages that includes $D\_2$ (the Dyck language over two bracket pairs) and is closed under homomorphisms, inverse homomorphisms, and indersection with regular languages.

Basically the CST construction works to obtain such a result. The inverse homomorphism however can be used to code both input letters and pushdown symbols into two pairs of brackets. The context-free language is of the form $L = h( g^{-1} (D\_2) \cap R)$.

**PS**. Below an old slide I have. (*note*. The roles of $g$ and $h$ are reversed.) It illustrates that we can see a PDA diagram as a finite state automaton, which defines regular sequences of instructions: the set $R$. Whether such a sequence is allowed as a computation has to be verified by checking that the pop and push instructions are legal. Legal sequences are Dyck sequences (with matching brackets). Thus we map the instructions to $D\_2$ here using $h$. Finally the language of the PDA is the sequence of input letters, which is obtained from the instructions using the second morphism $g$.

---
Tags: formal-languages, formal-grammars, chomsky-hierarchy, algebra
---


# Question
Title: Sumcheck protocol - how are these 2 polynomials different?
I am going through Justin Thaler's book - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf \- "Proofs, Arguments, and Zero-Knowledge"

He is describing the Sumcheck Protocol on Page 34

$H = \sum\_{b\_1 \in \lbrace 0,1 \rbrace} \space \sum\_{b\_2 \in \lbrace 0,1 \rbrace} \space ... \space \sum\_{b\_v \in \lbrace 0,1 \rbrace} g(b\_1, b\_2,...,b\_v)$

> At the start of the sum-check protocol, the prover sends a value $C1$ claimed to equal the true answer (i.e., the quantity H defined in Equation (4.1)). The sum-check protocol proceeds in $v$ rounds, one for each variable of $g$. At the start of the first round, the prover sends a polynomial $g1(X1)$ claimed to equal the polynomial $s1(X1)$ defined as follows:
>
> $s1(X1) = \sum\_{(x\_2,...,x\_v)\in {\lbrace 0,1\rbrace}^{v−1}} g(X1, x\_2,...,x\_v) \in {\lbrace 0,1\rbrace}^{v−1}$ \- $Eq (4.2)$

Further ahead on Page 35, he writes

> The remaining issue is the following: can $V$ efficiently compute both $g1(r1)$ and $s1(r1)$, in order to check that the Equation $g(r1) = s(r1)$ holds? Since $P$ sends $V$ an explicit description of the polynomial $g1$, it is possible for $V$ to evaluate $g1(r1)$ in $O(deg1(g))$ time. In contrast, evaluating $s1(r1)$ is not an easy task for $V$, as $s1$ is defined as a sum over $2^{v−1}$ evaluations of $g$.

---

I understand how the Prover creates polynomial $g1$ from $g$ (Eq 4.2). What I don't understand is the difference between $g1$ & $s1$. Prover sends Verifier only $g1$ \- where does Verifier get $s1$ to evaluate it at $r1$?

# Answer
> 1 votes
Your question is answered in the book itself, in the sentence you quote and the next few sentences thereafter. The Verifier doesn't get $s\_1$. As the book says:

> evaluating $s\_1(r\_1)$ is not an easy task for $\mathcal{V}$ \[...\]
>
> rather than evaluating $s\_1(r\_1)$ on her own, $\mathcal{V}$ instead *recursively* applies the sum-check protocol to evaluate $s\_1(r\_1)$.

Moreover if you look at the specification of the protocol on p.34, you will see that the Verifier never computes or receives $s\_1$.

---
Tags: polynomials, interactive-proof-systems
---


# Question
Title: Fast way to know if deleting an edge will disconnect a fully connected undirected graph
Given a fully connected undirected graph, is there a quick way for me to know if the graph will remain fully connected if I delete a given edge from the graph?

Quick = O(lg V) or something like that. O(V) is not quick.

Fully connected = every node is reachable from every other other node in the graph. i.e., given any two nodes in the graph, there is always a path connecting these two nodes.

# Answer
> 5 votes
No, because in the worst case you have to examine every edge (at least, under standard graph representations).

If you can preprocess the graph ($O(|V|+|E|)$ time), you can decompose it into strongly connected components and build a data structure that lets you answer this question in $O(1)$ time.

If you are repeating this many times, alternatively deleting edges and then checking whether deletion will disconnect the graph, see algorithms for decremental graph connectivity.

See also Incremental strongly connected components, Split-Find: maintaining dynamic graph connectivity information, under edge deletion, https://cstheory.stackexchange.com/q/27269/5038.

---
Tags: graphs
---


# Question
Title: GNI public coin interactive proof: why randomize y?
I've read this scribe that provides a public coin interactive proof for graph non-isomorphism.

In the proof, the verifier samples both a pairwise-independent hash function **and a target $y$**. Then it continues to show bounds for the probability that there's a pre-image of $y$ w.r.t. the hash function that's also inside a given subdomain $S$.

In all calculations carried out in page 5 (lemma 3), I couldn't find a single instance that used the fact that $y$ is random. It seems as if randomizing the hash function is enough.

This is also the case for any other source I found that shows a specific public-coin interactive proof for GNI.

Why do we need to randomize $y$?

# Answer
> 0 votes
I agree. I believe you are correct. As far as I can see, $y$ does not need to be random.

---
Tags: complexity-theory, graphs, graph-isomorphism, interactive-proof-systems
---


# Question
Title: How to avoid global delaunay check in conforming triangulation?
I implemented a conforming (i.e. it creates Steiner points using Ruppert's algorithm) delaunay triangulator, which is working, but there is one step I am doing that I straight up don't understand and suggests something is broken.

After introducing a circumcenter of a triangle, I am having to check the entire mesh and restore the Delaunay property manually. I don't understand why I would need to do this?

I have tested all the subroutines the algorithm depends on, so I know the issue is coming from the logic of the algorithm itself.

This is my implementation in rust:

```
pub fn conforming_delaunay_triangulation_as_mesh(
    points: &dyn Fn(usize) -> Vec3,
    point_count: usize,
    segments: &dyn Fn(usize) -> [usize; 2],
    segment_count: usize,
    angle_constraint: f32,
    area_constraint: f32,
) -> HalfMesh<Vec3, (), ()>
{
    // Compute a triangulation.
    let mesh = constrained_delaunay_triangulation_hollow_as_mesh(
        points,
        point_count,
        segments,
        segment_count,
    );

    // Sort all *bad* faces from worst to best in apriority queue.
    // === 1. Score all triangles and filter the bad ones ===
    let mut bad_face_queue = PQueue::new();
    for triangle in mesh
        .iter_faces()
        .filter(|t| triangle_is_bad(t, angle_constraint, area_constraint))
    {
        let weight = triangle_weight(&triangle);
        bad_face_queue.push(triangle.id(), weight);
    }

    // Find all constrained and boundary segments.
    let mut segment_set: BTreeSet<GeomId<1>> = (0..segment_count)
        .map(|i| {
            let [v1, v2] = segments(i);
            mesh.vert_handle(GeomId::from(v1))
                .shared_hedge(GeomId::from(v2))
                .unwrap()
        })
        .map(|e| e.id().select_even())
        .collect();
    segment_set.extend(
        mesh.iter_edges()
            .filter(|e| e.is_in_boundary_edge())
            .map(|e| e.id()),
    );

    // === Algorithm ===
    while !bad_face_queue.is_empty()
    {
        // === 2. Pop current worst triangle ===
        let (fid, _w) = bad_face_queue.pop().unwrap();
        let points = mesh.face_handle(fid).vertices_tri();
        let circumcenter = osculating_circle(&points[0], &points[1], &points[2]);

        // === 3. Check if the circumcircle encroaches an edge ===
        let mut segment_encroached = false;
        let mut edge = mesh.hedge_handle(GeomId(0));
        for segment in &segment_set
        {
            edge = mesh.hedge_handle(*segment);
            if encroaches(&edge, &circumcenter)
            {
                segment_encroached = true;
                break;
            }
        }

        // === 4. If it encroaches the edge, split the edge ===
        if segment_encroached
        {
            let new_edges;
            let vid;
            // Split the edge (check is needed because boundary edges must use special
            // logic).
            if !edge.is_in_boundary_edge()
            {
                (vid, _, new_edges) = edge.split::<f32>();
            }
            else
            {
                (vid, _, new_edges) = edge
                    .get_non_boundary_hedge()
                    .unwrap()
                    .split_boundary::<f32>();
            }

            // Restore Delaunay criterion.
            lawsons_algorithm(vid, &mesh, |e| e.is_in_boundary_edge());
            // We added new faces and changed existing ones, update the queue.
            for face in mesh
                .vert_handle(vid)
                .iter_hedges()
                .filter(|e| !e.is_boundary_hedge())
                .map(|e| e.face())
            {
                if !triangle_is_bad(&face, angle_constraint, area_constraint)
                {
                    continue;
                }
                let weight = triangle_weight(&face);
                bad_face_queue.push(face.id(), weight);
            }
            segment_set.insert(new_edges[1]);
        }
        // === 5. If it does not encroach the edge, split the face ===
        else
        {
            let face = find_containing_triangle(&circumcenter, &mesh);
            if face.is_none()
            {
                continue;
            }
            let face = face.unwrap();
            let vid = face.split_triangle_face::<f32>();
            // Set face to circumcircle:
            let v = mesh.vert_handle(vid);
            v.mutate_data(&circumcenter);

            // Restore Delaunay criterion.
            lawsons_algorithm(vid, &mesh, |e| e.is_in_boundary_edge());
            // TODO(low): why is this necessary?
            for v in mesh.iter_verts()
            {
                lawsons_algorithm(v.id(), &mesh, |e| e.is_in_boundary_edge());
            }

            // We added new faces and changed existing ones, update the queue.
            for face in mesh.vert_handle(vid).iter_hedges().map(|e| e.face())
            {
                if !triangle_is_bad(&face, angle_constraint, area_constraint)
                {
                    continue;
                }
                let weight = triangle_weight(&face);
                bad_face_queue.push(face.id(), weight);
            }
        }
    }

    mesh
}

/// Recursively flips triangles around a determined vertex until all pass the
/// delaunay test (or are constrained).
pub fn lawsons_algorithm<F>(
    source: GeomId<0>,
    mesh: &HalfMesh<Vec3, (), ()>,
    is_constraint_edge: F,
) where
    F: Fn(&HEdgeHandle<Vec3, (), ()>) -> bool,
{
    let mut queue = VecDeque::from_iter(
        mesh.vert_handle(source)
            .iter_hedges()
            .map(|e| e.next().id()),
    );
    while !queue.is_empty()
    {
        let edge_id = queue.pop_front().unwrap();
        let edge_handle = mesh.hedge_handle(edge_id);
        if delaunay_test(&edge_handle)
            && edge_handle.can_flip()
            && !is_constraint_edge(&edge_handle)
        {
            edge_handle.flip();
            queue.push_back(edge_handle.next().id());
            queue.push_back(edge_handle.pair().prev().id());
        }
    }
}

```

The summarizing pseudo code would be:

* Compute a constrained Delaunay triangulation.
* Create a priority queue of bad triangles from worst face to least bad
* Create a set of segments
* While there are bad triangles:

+ Pop the worst triangle
    + If its circumcenter encroaches a segment in the set, split that segment, add the new segment created by the split to the existing set, restore the Delaunay condition, update face queue.
    + Else, find the face containing the circumcenter, split the face at the circumcenter, restore the Delaunay condition around the circumcenter.
    + *HACK!!!!!* restore the Delaunay cirterion globally across the mesh
    + Update the triangle queue with the faces surrounding the circumcenter.

I don't understand why I need to do the hack. Either my lawson algorithm is incorrect, or I have miss understood something key about the algorithm. I am hoping someone can lend me a hand.

# Answer
> 1 votes
I figured it out. The implementation of lawson's algorithm I had was incorrect, this is the right one:

/// Recursively flips triangles around a determined vertex until all pass the
/// delaunay test (or are constrained).
pub fn lawsons_algorithm<F>(
    source: GeomId<0>,
    mesh: &HalfMesh<Vec3, (), ()>,
    is_constraint_edge: F,
) where
    F: Fn(&HEdgeHandle<Vec3, (), ()>) -> bool,
{
    let mut queue = VecDeque::from_iter(
        mesh.vert_handle(source)
            .iter_hedges()
            .map(|e| e.face().id()),
    );

    let find_opposite = |face: &FaceHandle<Vec3, (), ()>| {
        face.hedge()
            .iter_loop()
            .find(|e| e.source().id() != source && e.dest().id() != source)
            .unwrap()
    };
    while !queue.is_empty()
    {
        let face_id = queue.pop_front().unwrap();
        if face_id == ABSENT()
        {
            continue;
        }
        let edge_handle = find_opposite(&mesh.face_handle(face_id));
        if delaunay_test(&edge_handle)
            && edge_handle.can_flip()
            && !is_constraint_edge(&edge_handle)
        {
            edge_handle.flip();
            queue.push_back(edge_handle.face().id());
            queue.push_back(edge_handle.pair().face().id());
        }
    }
}
```

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


# Question
Title: Struggling with Recurrence Relation using Telescoping Approach
I have the following recurrence relation that I am trying to solve using the telescoping approach: $T(n) = \begin{cases} T(\frac{n}{4})+ n^2 & \text{for } n \geq 4 \\ 1 & \text{otherwise} \end{cases}$

I have this so far:

$T(n) = T(\frac{n}{4}) + n^2$

$T(\frac{n}{4}) = T(\frac{n}{16}) + (\frac{n^2}{16})$

$T(\frac{n}{16}) = T(\frac{n}{64}) + (\frac{n^2}{256}) $ ... up to $T(n) = 1$

I know I am supposed to now write $T(n)$ as a sum of these expansions but I dont seem to be doing it right. I have:

$T(n) = n^2 + (\frac{n}{4})^2 + (\frac{n}{16})^2 + (\frac{n}{64})^2$ and so on.

Sorry for the poor formatting of my question, I am new to Stack Exchange. Please give me suggestions on formatting so I can edit it.

# Answer
I am not so sure what the problem is: is it a problem on writing the formula with the sum, or finding a closed formula for the sum?

In the first case, you could write either: $$T(n) = n^2 + \left(\frac{n}4\right)^2 + \left(\frac{n}{16}\right)^2 … + 1$$

but that hides the number of terms.

Another possibility is writing:

$$T(n) = \sum\limits\_{k=0}^{\log\_4 n}\left(\frac{n}{4^k}\right)^2$$

Now for solving this, you just need to note that $T(n) = n^2\sum\limits\_{k=0}^{\log\_4 n}\frac{1}{16^k}$.

You can either find a formula for the sum: $$\sum\limits\_{k=0}^{\log\_4 n}\frac{1}{16^k} = \frac{1-\frac{1}{16^{\log\_4 n + 1}}}{1 - \frac{1}{16}} = \frac{16-\frac{1}n}{15}$$ or simply an upper bound: $$\sum\limits\_{k=0}^{\log\_4 n}\frac{1}{16^k} \leqslant \sum\limits\_{k=0}^{+\infty}\frac{1}{16^k} = \frac{1}{1- \frac{1}{16}} = \frac{16}{15}$$
> 0 votes

---
Tags: algorithms, complexity-theory, recurrence-relation, big-o-notation, mathematical-analysis
---


# Question
Title: How does paxos algorithm handle partial failures of accept messages?
I've been reading the basic paxos algorithm from the "Paxos Made Simple" paper. I can't understand how paxos algorithm maintains the safety properties under partial failures of the accept messages, meaning cases where the proposer receives prepare responses from a majority, but the subsequent accept message does not reach all the acceptors. It seems to me this could lead in a violation of the safety properties, where there will be no majority that has agreed on the same value.

I created a contrived example of the use-case I am thinking about. In every round, the proposer sends a prepare message to a majority of nodes, gets a response from all of them, but then the accept message arrives only to one of them (the other ones get lost). More specifically, as shown in the image below:

* in round 1, the proposer sends a propose (1) message. The acceptors haven't received any prepare message yet, so they all reply with a promise. The proposer gets a majority in phase 1, so sends an accept(1, A) message. This message reaches the first node that accepts it.
* in round 2, the proposer sends a propose (2) message to a majority, which does not contain the node that has accepted a value. As a result, the proposes gets a majority and sends an accept(2, B) message, which reaches only the second node.
* the round 3 is similar, where none of the selected acceptors during the first phase have accepted any value yet. As a result, the proposer picks a value and sends an accept(3, C) message, which reaches only the third node.
* in round 4, the majority has to contain at least one of the acceptors that has accepted a value. Let's say this is the first node that has accepted the value A, which returns the number of the proposal (1) as a reply to the prepare(4) message the proposer sent. Since there's only one accepted value, the proposer uses this one and sends an accept(4, A) message, which reaches the fourth node.
* in round 5, the proposer sends a propose(5) message to a majority that contains the first 2 nodes, which have accepted the values A and B. They both return the associated proposal numbers (1 and 2). The proposer picks the value corresponding to the highest one, B. The proposer then sends an accept(5, B) message, which only reaches the fifth node.

At this point, there is no way to satisfy the safety property, since we would need a majority (6/2 + 1 = 4) of acceptors to have accepted the same value.

Where is the flaw in my thinking ?

# Answer
> 2 votes
The paper's specification for the phase 2(b) of the algorithm, which is how an acceptor responds to an accept message is the following:

> If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

This means that **acceptors are allowed to accept multiple proposals** (even with different values) in a single instance of Paxos, as long as they have not responded to a prepare request with a number greater than the number of the accept message. As a result, even after the last row of the example, a proposer could bring the system to an agreement, by making some of the nodes accept a different value.

For example, the proposer could send a subsequent prepare(6) message to nodes 1,2,5,6, followed by an accept(6, B) that reaches everyone, thus reaching a majority and concluding the consensus. The important thing to note is that after this point, it's impossible to form a majority with a different value, because any potential majority quorum would contain at least one node returning (6, B) during the prepare phase.

# Answer
> 0 votes
This would be resolved in round one, as the paper also says "When the leader (distinguished proposer) fails to receive the expected response to its phase 2 (accept request) messages \[...\], it will retransmit those messages."

Unless the proposal round is abandoned and the leader sends a new (higher) proposal id.

The paper also says that these proposal rounds can occur simultaneously (corresponding to state changes in a replicated 'state machine'; commands in ATM software). And values can be chosen later.

---
Tags: distributed-systems, consensus
---


# Question
Title: Finding the error probability of a Monte Carlo algorithm
Let's say I have a Monte Carlo algorithm $A$ that gives the correct answer with a probability $p$ \> $1/2$. I don't have any information on if it's decisional or not.

I understand that I can make another algorithm $A'$ that runs $A$ for a number of times $k$ and returns the average (or the most repeated answer of $A$). Considering this, I need to find the value of $k$ so that the error probability is at most $\epsilon$.

What I don't fully understand is what the error probability of $A'$ would be in this case. I have done other Monte Carlo exercises where the error probability would be $(1-p)^k$ after repeating $k$ times, but those were biased in the way that you could know that if $A$ returned specifically true or false, depending on the problem, the answer would be correct. Would the error probability still be $(1-p)^k$ in this case?

I've seen in other questions that I can use the Chernoff bounds for this, but since this is an exercise for my algorithmics class in university, and I don't recall having seen the Chernoff bounds or anything similar at all, I'm somewhat reluctant to using it. Also, I don't really understand how to work from that. I would like to know if I need to use Chernoff in this case to find $k$ for the error probability to be at most $\epsilon$ or if there's another simpler way.

Thank you in advance.

Edit 1: Looking at some old classes from my teacher it looks like she says that we could use the Chebyshev inequality for this same case, but she never showed how to continue with that, and my statistics and probability theory knowledge is very rusty.

# Answer
> 1 votes
Run the algorithm $A$ a total of $2k$ times and take the most popular answer. Then if this aggregate answer is wrong, this means that at least $k$ answers were wrong. This happens with probability: $$r:=\sum\_{i=k}^{2k}\binom{2k}{i}(1-p)^{i}p^{2k-1}$$.

You could also bound that by $r\leq e^{-k(2p-1)^2}$, for example.

To do so, let $S$ be the random variable denoting the number of wrong answers. Then $S$ is a sum of $2k$ i.i.d. variables with values in $\[0,1\]$ and $S$ has expected value $\mu = 2k(1-p)$.

We have $$r = \Pr(S\geq k) = \Pr(S-\mu \geq k-\mu) = \Pr(S-\mu \geq k(2p-1)).$$

Let $t = k(2p-1)$. Hoeffding's inequality tells us that $$\Pr(S-\mu \geq t) \leq e^{-\frac{2t^2}{2k}} = e^{-\frac{t^2}{k}} = e^{-k(2p-1)^2}.$$

With this bound, we can conclude that taking $k\geq -\frac{\ln(\epsilon)}{(2p-1)^2}$ gives you an error probability of at most $\epsilon$.

---
Tags: algorithms, probabilistic-algorithms, monte-carlo
---


# Question
Title: Fast measurement of distance from point to mid segment?
Say you have a segment defined by 2 points $a,b$ and a third point $p$. You want to know the distance from $p$ to the midpoint of the edge.

This is very straightforward:

$$d = \\|\frac{a + b}{2} - p\\|$$

I am wondering if it is possible to do this faster. Asymptotically you cannot do better than $O(n)$, where $n$ is the dimension in which the points are embedded, but I wonder if it is possible to reduce the constant in the complexity by reducing the amount of arithmetic computations needed to be done.

# Answer
> 2 votes
If you use an under-/overflow-safe euclidean norm implementation along the lines of LAPACK's dnrm2, your line-to-point distance function will look something like the following Scala code:

```
def linePointDistance( a: Array[Double], b: Array[Double], p: Array[Double] ): Double =

  require(a.length == b.length && a.length == p.length)

  var sum,mag = 0.0

  for i <- a.indices do
    var x = abs( p(i) - 0.5*(a(i) + b(i)) )
    if  x > mag then
      val s = mag/x
      sum *= s*s
      sum += 1
      mag  = x
    else if x != 0 then
      x /= mag
      sum += x*x
    end if
  end for

  if mag.isFinite then mag * sqrt(sum) else mag

end linePointDistance

```

You can see that for each of the $n$ dimensions You have:

* 1 division
* 1 multiplication
* A few additions/subtractions
* 1 shift (Division by 2)

A division is usually more expensive than a multiplication. A multiplication is more expensive than an addition/subtraction. Even an integer division is relatively cheap compared to a memory read (see itHare.com). This means that, arithmetically speaking, `linePointDistance` is already fairly efficient.

Pre-computing the mid-points of each line will reduce memory access by 1/3 and remove 1 addition, 1 subtraction and 1 shift operation. This may result in a small performance improvement, maybe ~5% to 15%.

Your best chance for performance improvement might be vectorization. With Java's experimental Vector API, You could vectorize the Scala code as follows:

```
import jdk.incubator.vector.DoubleVector
import jdk.incubator.vector.VectorOperators.{ADD, MAX}

def linePointDistanceVectorized( a: Array[Double], b: Array[Double], p: Array[Double] ): Double =

  val n = a.length
  require(n == b.length && n == p.length)

  val vSpec = DoubleVector.SPECIES_PREFERRED
  var vMag  = DoubleVector.zero(vSpec)
  val vLen = vSpec.length

  // Find Magnitude
  // --------------
  var   i = 0
  while i <= n-vLen do
    val ai = DoubleVector.fromArray(vSpec, a,i)
    val bi = DoubleVector.fromArray(vSpec, b,i)
    val pi = DoubleVector.fromArray(vSpec, p,i)
    val ci = ai.add(bi).mul(0.5).sub(pi).abs
    i += vLen
    vMag = vMag.max(ci)
  end while

  var mag = vMag.reduceLanes(MAX)

  while i < n do
    val ci = abs( p(i) - 0.5*(a(i) + b(i)) )
    mag = max(mag,ci)
    i += 1
  end while

  if mag == 0 || ! mag.isFinite then return mag

  // Compute Squared Sum
  // -------------------
  var vSum = DoubleVector.zero(vSpec)

  i = 0
  while i <= n - vLen do
    val ai = DoubleVector.fromArray(vSpec, a, i)
    val bi = DoubleVector.fromArray(vSpec, b, i)
    val pi = DoubleVector.fromArray(vSpec, p, i)
    val ci = ai.add(bi).mul(0.5).sub(pi).div(mag)
    i += vLen
    vSum = ci.mul(ci).add(vSum)
  end while

  var sum = vSum.reduceLanes(ADD)
  while i < n do
    var ci = p(i) - 0.5 * (a(i) + b(i))
    ci /= mag
    i += 1
    sum += ci*ci
  end while

  if mag.isFinite then sqrt(sum)*mag else mag

end linePointDistanceVectorized

```

According to my quick and dirty benchmarks, the vectorized code is up to 2x faster on a machine with AVX2 support. You might be able to gain another 2x-4x by using black assembly code magic, but it will be very time consuming, error prone and result in code that is unreadable, hard to port and not future proof.

Using other information about your specific application may allow for further, more frugal optimizations. If you perform many nearest point to line queries, for example, You could use spatial data structure, like a KD-Tree to massively improve performance.

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


# Question
Title: Processes with communication exclusive from the OS
Most OSes use the message passing system to let 2 processes communicated with each other.This works by a shared mailbox between the OS and each process loaded in the RAM however are there processes which have their own shared mailbox and can communicate without the OS acting as a middleman?

# Answer
Two isolated processes need some OS support for passing messages between each other, but there need not be a system call for every message.

One simple way is to use virtual memory. You could, for example, use shared memory or a memory-mapped file to share a piece of memory between two processes, and communication can then proceed using shared data structures for communication.

Many operating systems also provide cross-process synchronisation objects if waiting is needed.
> 2 votes

---
Tags: operating-systems, applications, message-passing
---


title: Are all DFAs also NFAs?

text:
# Question
Title: Are all DFAs also NFAs?
Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons?

# Answer
> 11 votes
That depends on how pedantic you are. Morally and semantically speaking, every DFA is an NFA in which there is a unique arrow exiting every state for every character in the alphabet, and there are no $\epsilon$ transitions.

Syntactically speaking, it depends on your definition: the transition function could be encoded differently, so that the transition function of a DFA might not be "legible" for an NFA simulator.

I would not worry too much about the syntactic viewpoint.

# Answer
> -1 votes
if you write a DFA that generates lets say sigma star it wont be possible on an NFA some languages can not be converted efficiently or youll be just adding epsilons everywhere

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


title: Linked Lists, Ordered Pairs?

text:
# Question
Title: Linked Lists, Ordered Pairs?
I would like to model linked lists using set theory similar to that in Scheme and LISP.

There is a set theoretic definition of the ordered pair:

$p = \\{\\{a, 1\\}, \\{b, 2\\}\\}$

My question is how does one distinguish a value from a pointer to another list? Should I just use more types like $3$ for value and $4$ for pointer?

So in LISP:

$l= ((('a').()), (('c'.'d').()))$

In set theory beginning of above list:

$l = \\{\\{h, 1\\}, \\{i, 2\\}\\}$

$h = \\{\\{a, 1\\}\\}$

$a = \\{\\{b, 4\\}\\}$

$b = \\{\\{'a', 3\\}\\}$

Without distinguishing pointer from value I'm not sure how a distinction can be made.

# Answer
Now that you have defined ordered pairs, you can do what LISP does: $\operatorname{NIL}$ is a list and if you have a list $l = (a, b)$ then $a$ is a value and $b$ is a list. Of course, lists can be used as value themselves.

For example, the list $(a.b.c)$ is defined to be the ordered pair $(a, (b, (c, \operatorname{NIL})))$.

Thus $$l = ((('a') . ()) . (('c' . 'd'). ()) = (x\_1, (y\_1, \operatorname{NIL}))$$ where : $$x\_1 = (('a') . ()) = (x\_2, NIL)$$ $$x\_2 = ('a', \operatorname{NIL})$$ $$y\_1 = (('c' . 'd') . ()) = (y\_2, (\operatorname{NIL}, \operatorname{NIL}))$$ $$y\_2 = (c . d) = ('c', ('d', \operatorname{NIL}))$$
> 1 votes

---
Tags: graphs, data-structures, sets, linked-lists
---


# Question
Title: Classifying vectors that only contains 1001110101 numbers - Is Support Vector Machine the solution?
Assume that you are given a vector `0b1101001001011001` etc. And you are going to classify it. One can use Support Vector Machine, but is that method good for classifying data that are spare and binary?

Assume that you are given a real vector $x$ with dimension $N$. The vector contains only ones and zeros. $x = \[0, 1, 0, 0, 0, 1, 1\]^T$

You are not given one vector $x$, instead you are given a matrix of vectors e.g $X = \[x\_1, x\_2, x\_3, \dots , x\_M\]$ where $N$ is constant but $M$ can vary.

From the matrix $X$, you are also given a vector called labels $y$. The labels are labled either with -1 or +1. The labels $y$ is one vector with the same length as $M$.

So, from the labels $y$ and matrix $X$, you can find weights $W$ and bias $b$ on the form

$$y\_i = Wx\_i^T + b$$

But is SVM a good way to classify this type data?

# Answer
> 1 votes
If I understand your question correctly, the features in your case are exclusively categorical. Support Vector Machines might work, but they would not be my model of choice for such data. SVMs try to separate the classes by a plane¹ with maximum distance to the closest samples in (transformed) feature space. That distance, however, is pointless with categorical data.

I would suggest that You try Decision Trees which give well-interpretable results. If Decision Trees are not working for you, give Random Decision Forests a try.

¹ In some high-dimensional kernel space.

---
Tags: binary, classification, svm, sparse-matrices
---


# Question
Title: Showing this scheduling problem is NP-hard
I've been reading up on scheduling problems and the class of them that is NP-complete. Specifically, this is a foundational text on such problems, but the reductions are not clear to me. Can someone help identify the reduction from 3-partition, if I am trying to show the problem is NP-hard when I am scheduling tasks on $m$ processors, with precedence constraints on a DAG, and $e(v)$ execution requirement.

# Answer
> 1 votes
The problem is strongly NP-Hard as it can be seen by reducing from the $3$-partition problem: given a set $X = \\{ x\_1,\dots,x\_{3n} \\}$ of $3n$ positive integers, is there a partition of $X$ into $n$ sets $X\_1, X\_2, \dots, X\_n$ such that (i) the sum of the elements in each set $X\_i$ is exactly $T=\frac{1}{n} \sum\_{i=1}^{3n} x\_i$, and (ii) each set $X\_i$ has size $3$?

This problem remains NP-Hard even if every $x\_i$ is in the open interval $(T/4, T/2)$, which makes condition (ii) redundant.

Given an instance of 3-partition with every $x\_i \in (T/4, T/2)$, you can build an instance of your problem as follows:

* There are $m=n$ processors.
* Each $x\_i$ corresponds to a job $v\_i$ with $e(v\_i) = x\_i$ and $\pi(v\_i) = \\{1, \dots, m\\}$ (i.e., the job can be assigned to any processor).
* The deadline $D$ is equal to $T$.
* The graph is $(\\{v\_1, \dots, v\_{3n} \\}, \emptyset)$, i.e., there are no edges (jobs can be executed in any order).

If there is a solution $X\_1, \dots, X\_n$ to the 3-partition instance you can get a feasible scheduling by assigning the jobs corresponding to the $3$ integers in the generic set $X\_i$ to processor $i$.

If there is a feasible scheduling, you can get a solution $X\_1, \dots, X\_n$ to the 3-partition instance by choosing $X\_i = \\{ x\_j, x\_k, x\_\ell \\}$ where $v\_j, v\_k, v\_\ell$ are the jobs assigned to processor $i$ (notice that each processor must have exactly $3$ jobs assigned since any $4$ jobs would exceed $D$, and less than $3$ jobs imply the existence of a processor with more than $3$ jobs).

---
Tags: reductions, scheduling
---


title: Two-Level Threading Model

text:
# Question
Title: Two-Level Threading Model
In multithreading models, we have a two-level model in which we multiplexes many user-level threads to a smaller or equal number of kernel threads but also allows a user-level thread to be bound to a kernel thread.

Why we need such a model ? Can someone give an example where we need to use this model?

# Answer
> 1 votes
In modern systems, we typically don't need this, because OS kernels provide adequate support for threads so that there can be a one-to-one mapping between user threads and kernel threads.

In some past systems, OS kernels didn't have support for creating multiple threads in a single process, or creating a new kernel thread was very expensive (slow). Therefore, the only way to provide threads with good performance was to multiplex multiple user-level threads, all running within a single kernel thread. This is no longer necessary in most modern OS's, under normal situations.

See also https://stackoverflow.com/q/39185134/781723, https://en.wikipedia.org/wiki/Thread\_(computing)

---
Tags: operating-systems, threads
---


# Question
Title: If the virtual address space can be larger than the physical address space, how are the address mappings stored in memory?
Let's say we are working with a system that has 40 physical address bits. The total physical address space (assuming byte-addressable memory) is $2^{40}$ bytes, or 1 TiB. And if virtual addresses are 48 bits in length, that means there are more addresses available to virtual memory than there are locations in physical memory.

This makes sense to me, because the "excess" addresses could refer to hard disk locations as well. However, what I don't understand is how the translation between virtual and physical addresses occurs. I assume there is a mapping stored somewhere which links VAS locations to the physical locations. If there are more virtual address locations than physical locations, how can all of these mappings possibly be stored in memory? At minimum you would need 48 bits to store each virtual address, and then another 40 to store the physical location it maps to. So obviously you cannot just store a 1:1 mapping of each virtual address to its physical counterpart, as mapping every location would take more memory than physical memory itself.

What exactly am I missing here?

# Answer
The trick to making this work is "paging." When bringing data from a hard disk into physical memory, you don't just bring a few bytes. You bring an entire page. 4k bytes is a very common page size.

If you only need to keep track of pages, not each individual byte, the mapping becomes much cheaper. If you have a 48 bit address space and 4096 byte pages, you only need to track which of the 2^36 pages (roughly 69 billion pages). That's much easier! The record of where all of the pages are found is known as a "page table."

If you actually need 1-256 TiB of memory, then giving up a few gigabytes to store this page table isn't a big deal. In practice however, we'll do things like use multi-level page tables, which lets us be a bit more efficient, keeping pages only for regions of the address space that we are actually using.
> 27 votes

# Answer
Cort Ammon's answer says

> multi-level page tables \[let\] us be a bit more efficient, keeping pages only for regions of the address space that we are actually using.

and gnasher729's answer says

> 1 GB of page table could handle 512 GB of address space.

I think they both overlooked, or at least didn't make clear, an important point: the page table only contains the virtual-to-physical address mapping for pages that have a physical address. Its size is therefore a function of the amount of physical RAM in use, not the amount of virtual address space in use.

For example, if you have 8 GB of RAM and you mmap a 10-terabyte file, the OS most likely won't modify the page table at all at first; it will just record information about the mapping in some other private data structure. That data structure doesn't need to have an entry for every page of virtual address space covered by the file. It may be an interval tree in which the entry for the whole file takes just a few tens of bytes.

Later, when the user process tries to access a part of the mmapped file, the CPU will find no page table entry for the virtual address and will generate a page fault. The OS's page-fault handler will look up the virtual address, find that it's backed by the disk file, and start the process of reading a portion of the file into physical RAM. After the read completes, it will update the page table and restart the faulting instruction.

The user process may eventually read the entire 10 terabytes of data, but long before it finishes doing that, the OS will have started evicting earlier pages from RAM to make room for new ones. When the pages are evicted, the corresponding entries in the page table can also be freed. So the page table never grows to 10 TB / page\_size * entry\_size. Its size is closer to 8 GB / page\_size * entry\_size.

---

Also not mentioned in other answers is that the virtual address isn't stored in the page table entry. The table is indexed by the virtual address, so it's coded implicitly by position. With a 40-bit address bus and 212-byte pages, each leaf entry only needs to contain the high 28 bits of the physical address and some metadata like write and execute permission bits.

---

In a comment, Nate Eldredge said

> When actual memory is large, another way of reducing the memory needed for page tables is to allow for larger pages. x86 has an option to mix 4 KiB pages with 2/4 MiB pages.

As far as I know, the motivation for large pages is to save time, not space. CPUs since the earliest days of paging have had a specialized cache for page table entries, the TLB. This cache isn't very large, and misses require an expensive lookup in the in-RAM page table. If the pages are 512 times larger then it's like your TLB has 512 times more entries.

Larger pages do save page table space, but the overhead for 4K pages is already only 0.2% assuming a 8-byte entry size. Large pages also waste space to coarser allocation granularity.
> 1 votes

# Answer
Your processor typically uses 8 bytes to store the information for 4,096 byte table. So 1 GB of page table could handle 512 GB of address space. Yes, there is a limit where it might be impossible to use all of the theoretically possible address space. But then many processors now have 64 bit of address space (256 billion billion bytes), so it is to be expected that you can't use all of it.

What is often possible is to have *used* logical address space that is at random places within that 64 bit space; this can be used to prevent attacks from hackers because they cannot know where in that huge logical space your data is. (So for example malloc might return addresses anywhere in the 64 bit space, but only for a total of say 64 GB of data).
> 0 votes

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


# Question
Title: Why Random Access Machine could only have $N \leq 2^{W}$ memory slots? Is it general theorem of informal rule?
Here:
$W$ is "bitness" - number of bits in one machine word, that could be stored in memory slots
$N$ \- number of memory slots (each has bitness equals $W$)

**My solution:**
If max length of machine word is $W$ so there are $2^{W}$ different machine words. Suppose, that each possible machine word works like an address of appropriate slot. Hence if $N \> 2^{W}$ there will be slot, that couldn't be accessed by address of machine word.

**Problem:**
I don't actually like my solution, because you may use RAM like an assembler and if $W$ is relatively small. For example if $W=1$ and $N=6$, what will be wrong if we manually will LOAD data to 6th slot of RAM? But on the other hand real systems are much more reliable and addressing is really important (it isn't safe to use manual indexing).

# Answer
> 0 votes
Your initial solution sounds correct to me.

The problem with your second idea of switching between RAM sticks, using a "select RAM stick" instruction, is that it technically is not random-access anymore:

* Reading data from only one DIMM requires 1 op per access (switch address)
* Switching between DIMMs requires up to 2 ops per access (switch address + switch RAM stick)

Even if you were to use a single instruction that reads 2 registers at once, it will require 2 ops to set the registers. If you add an operation that writes two registers at once you have arguably increased the effective word/register length.

It is worth pointing out that modern computers are *not* true random-access machines anymore. RAM DIMMs consist of banks of rows, each coming with switching overhead. Modern CPUs try to predict and prefetch memory regions that are going to be required next which makes predictable memory access faster than random-access. Memory is read in chunks (cache lines) which makes sequential access faster than strided access.

---
Tags: algorithms, data-structures, computation-models
---


# Question
Title: Calculating cells encompassing points in a grid
I have a sequence of points over time, and a grid of X by Y cells to which I need to calculate the cells in which the points fall, as depicted in the diagram below

Another point now arrives (as depicted by the red dot to the right), the grid is stretched to fit the new data, and the containing cells recalculated

Known aspects of the problem

* The number of X and Y cells is decided up front and does not change over time
* Time between points is irregular
* When a new point arrives it may have a higher or lower Y value than the current grid range, and here the grid Y will stretch to accommodate, just as it does in the X direction.
* The first and last point on the X axis form the X range of the grid
* The maximum and minimum point Y values form the Y range of the grid
* The maximum number of points is unbounded and an get large

I have thought in depth about this problem and I cannot see if it is possible to recalculate the yellow cells upon the arrival of a new point, without needing to repeatedly iterate through the sequence of points and performing the math to identify the cell it is bounded by. Given the number of points is unbounded the computation time will grow to be inefficient.

Is there another way to solve the problem, but which does not grow in computational time as points are added ?

# Answer
> 1 votes
I'm assuming you want a data structure storing a set of points where you can:

* Insert a new point
* Get the list of all cells which contain at least one point (this is your query).

You can do this by storing the points in a 2D range tree. These allow you, for any given orthogonal range, to test if they contain at least one point in $O(\log^2 n)$ time (where $n$ is the total number of stored points). You can also make them dynamic (i.e. allow for insertions and deletions of points) by standard dynamization methods. (In short: insert and delete stuff without worrying about your trees becoming unbalanced, and after every $O(n)$ updates rebuild the whole structure)

Now you can simply do the following: keep track of the maximum and minimum x/y coordinates. Each time a point is inserted, insert it into the 2D range tree and update the min/max coordinates as needed. To perform a query, loop through your cells (which you can compute knowing the min/max coordinates) and for each cell test if there is a point inside in $O(\log^2 n)$ time.

This will give you $O(\log n)$ amortized update time and $O(XY\log^2 n)$ query time. You could even make this worst-case instead of amortized with a bit more work, and use more sophisticated data structures to replace the $\log^2 n$ with $\log n$.

# Answer
> 0 votes
Based on your clarification to the question, it appears the task is as follows: you are given a list of all points; the algorithm should process this list and then output the list of all cells that contain at least one point.

If that is right, it is not possible to do better than linear time. Why? Because in the worst case each point can land in its own cell, so the output has linear size, so it takes at least linear time to generate that much output. Therefore the worst-case running time of any correct algorithm will be at least linear in the number of points.

If that is not right, please edit your question to state the problem to be solved more clearly.

---
Tags: algorithms
---


# Question
Title: Round-robin tournament scheduling, with teams that may share their home field
I need to implement an algorithm to create schedules for round-robin tournaments (where each team faces each other team exactly once), but with the constraint that up to 2 teams – that may play in different leagues – might share the same field on the same time slot of the week, so they must never be scheduled to play at their home field in the same round of their league schedule.

Simple example:

```
leagueA = [
  TeamA(plays at **FieldA on Sunday**),
  TeamB(plays at FieldB on Sunday),
  TeamC(plays at FieldA on Saturday),
  TeamD(plays at FieldD on Saturday)
]
leagueB = [
  TeamE(plays at **FieldA on Sunday**),
  TeamF(plays at FieldF on Sunday),
  TeamG(plays at FieldG on Saturday),
  TeamH(plays at FieldF on Saturday)
]

```

I was thinking of generating the schedule for leagueA with the circle method, alternating home and away teams at each round as described in the linked article, and then to approach the scheduling for leagueB by prefilling the slots for the teams that share the field with teams in the other league somehow, but I'm not sure whether it's the right approach and how to actually implement it in a way that is guaranteed to produce schedules not containing conflicts.

# Answer
This sounds like a operations research problem. I suggest using a standard hammer for that kind of problem: use a SAT solver or ILP solver. For instance, you might have a boolean variable for each tuple of team/location/time, which is true if that team plays at that location at that time; then use boolean/linear constraints to encode all of the requirements for this to count as a valid solution. Then, use an off-the-shelf SAT solver or ILP solver to search for a solution that meets all of those constraints.
> 0 votes

---
Tags: algorithms, scheduling
---


# Question
Title: (how) is assignment or binding possible in purely functional languages?
i can't seem to find much info on the following question:

*how (if at all) is the fixing of names to values (by binding or assignment) possible in a purely functional system like the lambda calculus?*

i've seen examples of this being done in haskell, lisp etc. by using the 'let' or '=' operators. to me it always reads like "kicking the can down the road" to a place where, out of sight, something non-functional is happening to make the language more practical/easy to use.

i am fairly new to the world of functional programming, so i may well be overlooking something obvious. if anyone here can point me to some material on the topic or give a basic explanation, i'd be very grateful :)

# Answer
> 1 votes
The lambda calculus has names for the parameter (bound variable) to a lambda abstraction. That is the only mechanism or introducing names. Apart from that, there are no names in the lambda calculus. Notice that there is no assignment within the lambda calculus.

There is nothing non-functional being hidden here.

If you are new to functional programming, I would not recommend starting with the lambda calculus. It is elegant from a theoretical perspective, but hard to develop intuition for from the perspective of a practical programmer.

# Answer
> 1 votes
I suspect you're imagining $\text{let } x = E \text{ in } E'$ as describing a sequence of steps: take the thing described by $E$ and put it in the box labeled $x$, then proceed to the thing labeled $E'$. It will seem less imperative if you take a less imperative view of it. Real functional languages are of necessity compiled/interpreted on hardware that has a non-functional design, so it's likely that at some point a machine instruction will execute that puts a value representing $E$ into a register or RAM location representing $x$, and then later instructions will be related to $E'$, but that's not really the fault of the high-level language, and you don't have to conceptualize the high-level language in terms of those low-level details.

A traditional view is that $\text{let } x = E \text{ in } E'$ means $(λx.E')\\,E$. In LISP-family languages, it may literally desugar to that. $(λx.E')\\,E$ is then ("beta-")equivalent to $E'\[E/x\]$, meaning $E'$ with $E$ substituted for $x$ wherever $x$ appears. This is a true mathematical equivalence: you can just as well start with $E'\[E/x\]$ and turn it into $(λx.E')\\,E$. The desugaring of $\text{letrec}$ is more complicated and requires a Y combinator or something like it.

What I wrote in the last paragraph only applies to a pure functional language in the LISP family, and I don't know if any such exists. In real LISPs, the desugaring of $\text{letrec}$ uses `setq`/`set!`, and beta-equivalence doesn't work because of side effects. Haskell is purely functional, but $\text{let}$ and $λ$ bindings aren't equivalent in Haskell or other ML-family languages because there are special typing rules for $\text{let}$.

My favorite way of understanding $\text{let}$ and $\text{letrec}$ is that they generalize expression trees to rooted expression graphs. Without them, every expression is a tree (its abstract syntax tree). With $\text{let}$, you can also describe dags. For example, $\text{let } x = E \text{ in } x\*(x+1)$ means this dag, with all edges pointing downward:

```
 *
/ \
|  +
| / \
 E   1

```

The symbol $x$ is needed by the $\text{let}$ notation, but it doesn't appear in the dag, where $E$ is not assigned or bound to anything. Roughly speaking, in this view, $\text{let } x = E \text{ in } E'$ means $E'\[E/x\]$, except that if $x$ appears more than once, you imagine that $E$ is shared rather than textually duplicated. Adding $\text{letrec}$, you can also represent graphs with cycles. No Y combinator is involved: all of the edges point to their referents directly.

---
Tags: lambda-calculus, functional-programming, variable-binding
---


# Question
Title: What is point of calling syscalls in the kernel?
If syscalls are meant to transition into kernel mode from user mode, what is the point of calling syscalls in the kernel?

Reference: https://stackoverflow.com/questions/15841327/can-we-call-system-call-in-kernel-space

# Answer
> 0 votes
OS also adheres to the DRY principle, reusing code that has already been implemented by developers. For example, the kernel could open/close/write to the log file, allowing it to reuse the syscall implementation rather than re-implementing it wherever it is needed.

"Write the core implementation once, reuse it when needed" is a good software engineering. Be it either in user space or kernel space.

Reference: https://www.reddit.com/r/compsci/comments/17incss/what\_is\_point\_of\_calling\_syscalls\_in\_the\_kernel/

# Answer
> 2 votes
Most modern operating systems have threads that run in kernel mode. Some typical examples include:

* Device drivers. Some operating systems even go to the trouble of implementing interrupt handlers as very-high-priority tasks.
* Determining page frames that haven't been used recently so they can be dealt with (e.g. writing dirty buffer cache, freeing clean page frames, recalculating user process working set sizes).
* Periodic housekeeping tasks such as balancing interrupts between CPUs in a multiprocessor system.
* An idle thread, which "runs" (if you can call sleeping in a lower-power mode "running") when nothing else can run on a CPU. Not all operating systems idle this way, but many do.

Such threads may not perform "system calls" as such, but might still use the system call entry points so that, as far as scheduling is concerned, they are just another thread and don't need special treatment.

---
Tags: operating-systems
---


# Question
Title: How many percentage of total transistors in a CPU are used in each component?
I'm learning the basics of computers, and now trying to get some oversight of complexity of a CPU. Is there a rough trend for how transistors are allocated in a CPU? Intel 8008 for example, has 3500 transistors. In this image of it, I can see the space each component occupies. The ALU as example, each ALU slice is 20 transistors, and, the ALU has 8 slices. I guess that is 20\*8 = 160 transistors for the ALU? Carry lookahead looks like it occupies same amount of space, another 160? ALU registers, 200? Registers, 160? Shifter, 80? That's 600 in total. Assuming I am somewhat correct on those numbers, is the remaining 2900 just the rest of the surface that is not marked in the image? It looks like it could be 5x as large surface area as the marked components.

# Answer
You're looking at an ancient CPU. Back then, IC technology greatly limited the number of available transistors on each chip. As it became easier and easier to add transistors, we started seeing big shifts in the use of these transistors.

One of the most obvious shifts is the fact that a large number of CPU designs are multi-core nowadays. Also, a modern CPU may have 200 or more registers, each of which stores 64 bits. Considering it takes 6 transistors in a standard SRAM cell, the register bank alone requires around 80.000 transistors *per core*, way more than the entire 8008 in your example.

Another well-known feature of modern CPU's is the cache. Again, these are SRAM cells, and 4 MB takes about 200 *million* transistors just to store the cache content - you need about 50 million more to read and write.

Since transistors have shrunk so much, we've used them a lot more aggressively. The shifter on the 8008 could shift by one bit. If you wanted to shift by 3 bits, you'd repeat that three times. A modern CPU can shift over any number of bits in a single operation - much faster, at the expense of more transistors.

The 8008 doesn't even have a multiply operation; modern CPU's have hardware to multiply, divide, and do square roots.
> 3 votes

# Answer
Your estimation of the number of transistors allocated to each function seems way off to me.

As you can see from the schematic, the 8008 has three 8-bit registers, two pointer registers, 7x8-bit registers for accumulators and scratchpad memory and 8x14-bit address stack registers.

That adds up to 208 bits of memory, each cell requiring 3 transistors and one capacitor for a total of 832 elements. And that count has yet to include any logic required for addressing.

As for the CLA I couldn't find details about the exact implementation, but your 160 estimate would be more in agreement with something a bit more sophisticated like the Brent-Kung adder, which wouldn't be invented for another 10 years. For a run-out-the-mill PMOS 8-bit CLA I have seen estimates ranging anywhere from 80 up to 300 transistors, depending on the maximum acceptable gate delay for the application.

And either way, I am not fully convinced you bounded the CLA area correctly.
> 0 votes

---
Tags: cpu
---