# Question
Title: Examples of Analysis of Branch and Bound Method
I am solving a graph problem, which can be formulated as an integer programme. Based on computer experiments, it seems that the branch and bound method works well. I would like to analyse the running time, and wonder whether there have been other problems where branch and bound method was used and the theoretical bounds on the running time has been established?

On another note, if anyone knows any examples of problems where the range of possible values that a variable in a linear programme can take, I'd also be interested in.

# Answer
Branch-and-bound is a heuristic. In this context, my impression is that typically analysis of the worst-case running time of such heuristics is not enlightening: the worst-case running time is typically exponential. On some problems in practice branch-and-bound may run significantly faster than that, but my sense is that worst-case running time analysis usually isn't very helpful for predicting when that will happen.
> 1 votes

# Answer
A good example of non-trivial algorithmic analysis of a practical braching algorithm is the vertex cover problem. It can be proven that if the answer is $k$, then a simple branching algorithm has time complexity $O(2^k n)$. The analysis uses "bounded search tree" technique.
> 1 votes

---
Tags: linear-programming, branch-and-bound
---


# Question
Title: repository of test cases of hard, combinatorial, NP problems
I'm sure there are standard test cases of hard, combinatorial, NP problems, ... (like knapsack, bin packing, partitioning, ...) that practitioners or algorithm developers use when they compare a new algorithm against existing ones (as I often see in papers), but where can I find them ? (a single repository is more preferable than many scattered)

# Answer
If a paper experimentally compares algorithms, it should state the source of the test cases. Therefore a good way to find test cases would be to read the papers where practical algorithms for the particular problem are compared.

Some test case repositories that have been used in research papers (in graph algorithms):
> 1 votes

# Answer
somehow I found the following

OR-Library at http://people.brunel.ac.uk/~mastjjb/jeb/info.html (many datasets for many problems)

Bin Packing page at https://www2.wiwi.uni-jena.de/Entscheidung/binpp/index.htm (datasets for bin packing)
> 0 votes

---
Tags: algorithms
---


# Question
Title: Why the most dominant programming languages didn't follow CSP thread model?
> I was trying to ask this question in StackOverflow, but later realized that this question is more relevant to general computer science, not specific engineering problems. If you think it's not, please let me know.

Recently I've found out what CSP(Communicating Sequential Processes) is.

According to the article Bell Labs and CSP Threads:

> Most computer science undergraduates are forced to read Andrew Birrell's “An Introduction to Programming with Threads.” The SRC threads model is the one used by most thread packages currently available. The problem with all of these is that they are too low-level. Unlike the communication primitive provided by Hoare, the primitives in the SRC-style threading module must be combined with other techniques, usually shared memory, in order to be used effectively...

Another article Share memory by communicating from Golang blog says:

> Traditional threading models (commonly used when writing Java, C++, and Python programs, for example) require the programmer to communicate between threads using shared memory (...)
>
> Go's concurrency primitives - goroutines and channels - provide an elegant and distinct means of structuring concurrent software. (These concepts have an interesting history that begins with C. A. R. Hoare's Communicating Sequential Processes.)

Based on what I've seen so far, because Hoare proposed CSP in 1978, it seems that there was no reason to use SRC thread model in programming languages like C++(1985), Java(1995) or Python(1990).

So my question is, **why the most dominant programming languages didn't follow Hoare's thread model?**

Here's my guesses:

1. Most programmers back then didn't know about Hoare's thread model.
2. Most programmers are used to traditional thread model.

What do you think?

# Answer
> 2 votes
Practically speaking, the C++ threading (memory) model is directly inspired by the Java Memory Model, and C followed. Hans Böhm was closely involved with the process and has a great resource list. (\*)

You'll quickly note that your dates are pretty optimistic - this memory model did not exist in 1985 when the first C++ implementations were created. There's a practical reason for this. Even in 2000, it wasn't clear which model of parallel computing was going to win. Parallel extensions to mainstream languages were first defined as ad-hoc extensions by the hardware vendors, and later partially standardized by such things as POSIX threads and MPI.

Because of the challenges involved, you see that parallelism support is added first to languages used in high-performance computing. Even C++ was a bit late to the party; C and FORTRAN were the main languages. Java, by virtue of being late, had a chance to learn lessons from those. And since it was designed as a portable language, Java needed a clean memory model not tied to a particular hardware vendor's implementation.

So the common memory model can be traced to various actual hardware implementations that could be unified by a single definition. And this led to a secondary effect: because this was now a standard, software started to use it, and hardware vendors generally followed suit.

There's another winner in the parallelism space: GPGPU's. They entered the competition via a different way. NVidia's CUDA is a similar vendor-extension to C, C++ and FORTRAN. This was possible because the GPU market justified independent development, and the general-purpose use of GPU's was a lucky coincidence.

** This development can be dated pretty accurately, the use of the Java memory model for C++ was presented at the 2001-10 ISO C++ meeting in Redmond, WA.*

# Answer
> 3 votes
There are many approaches for concurrency, with different tradeoffs. We have threads with shared mutable state (e.g., SRC-style threading). We have coroutines (like Go). We have actor models with independent processes communicating via message passing (like Erlang or E).

I would put CSP on a different level. It's not the same sort of thing. The form of CSP that I am familiar with is a mathematical, theoretical formalism that can be used to model concurrent systems. It's not really a model of programming that can be directly used in programming languages. It's more like the lambda calculus. You can build programming language APIs inspired by CSP, just like Lisp and Scheme are inspired by the lambda calculus, but it's not directly a design of a thread API itself.

Why did early languages choose to follow the SRC model rather than something inspired by CSP? Well, all I can share with you is speculation. The SRC model is a low-level model that maps pretty closely to the primitives provided by processors: it is a thin level of abstraction over that. Just like C is a thin layer over assembly language (and doesn't use, say, functional or declarative paradigms), it's not surprising that early languages would provide a thin layer over processor primitives (rather than, say, other theoretical paradigms). Also, the SRC model works well with existing code and existing programming languages. You can take existing sequential code and then add threads. When you're writing threaded code, the sequential part of the computation looks just like code written for a non-threaded language. That backwards compatibility and familiarity was probably significant. The SRC model could be deployed as a library, without requiring changes to programming language syntax or compilers. I have to imagine that might have been a significant factor in its adoption. Also, the SRC model is somewhat similar in many ways to existing Unix primitives for running code in parallel in multiple processes, which I imagine might also have been beneficial for adoption. This is just my speculation. Perhaps someone else will be able to provide a more researched answer.

---
Tags: formal-languages, parallel-computing, concurrency, threads
---


# Question
Title: How does the memory of a 64bit and 32bit processor work
In this article, the author states that a 64bit processor can theoretically reference 2^64 bytes of memory. What does he mean by this statement, or rather the word, *reference*?

Also, I visualize the entire RAM to be divided into little memory cells, each having an n-bit binary number that represents a given instruction or value that is needed for running any program in the computer. ***Is this visualization right?***

If it is, then for a 64bit processor, what would be the number of memory cells in the RAM?

# Answer
No, the author is wrong.

I have used 32 bit processors that could address 64 GB of RAM. Memory is restricted by the number of address lines, multiplied by the number of bytes addressed by each individual value of address lines.

Address space of one application was limited to 4GB, but you could have a dozen applications running at the same time, each using several GB.

The author also seems to be quite ignorant of what processors and operating systems exist.
> 2 votes

# Answer
First of all, the physical memory chips are no different between a 32 and 64 bit computer.

The article talks about how the processor can reference (or address) the memory. In all modern architectures memory is byte-addressable, which means that every byte-sized memory cell has a number (its address), which the CPU uses to identify that cell. A simple 32 bit processor has 32 bit registers, and a 32 bit number can range from 0 to 4 billion, so it can address 4 GB of memory. A 64 bit number ranges up to 18 quintillion something, or 16 exabyte.

As gnasher states, actual processors do not necessarily match simple models, and most x86 32 bit processors had extensions to address more than 4 GB of memory. However older models without these extensions can literally not use more than 4 GB of memory. If you would be able to put in more memory, these processors would not be able to see it.

That does not mean that the article is entirely wrong, but to see that you need to distinguish between virtual memory and physical memory. Virtual memory is the memory that one program sees, physical memory is the memory that is physically installed in your system, and that only the operating system can access directly. The addressing extensions for 32 bit processors (PAE) only apply to physical memory. A single 32-bit program can only access 4 GB virtual memory, while a single 64-bit program can access a lot more.

The article also mentions the advantage of 64 bit multi core processors, but that doesn't have anything to do with the 64-bit-ness, multi core 32 bit processors also exist. That 64 bit and multi core were introduced around the same period was because both are ways to make use of the ever rising number of transistors that fit on a single chip, which was becoming more than was useful for a single core.
> 0 votes

---
Tags: memory-hardware, memory-access, memory-allocation
---


# Question
Title: Does the callback concept of programming have any basis in computer science?
Although I seriously code with computer languages in general since 2010 and as an amateur programmer with programming languages in particular since 2015 (primarily Bash and JavaScript imperative scripts) and codes I wrote are scattered through my Stack Exchange accounts, as in my Code Review SE account,
I think I still misunderstand what a **Callback** is;
I feel that the term itself might be misleading, as I understand that callback functions doesn't "call back" anything, but rather "called back" as a reaction to a condition (event).
I understand the alternative term **Callafter** as significantly controversial between programmers, so I stay with "Callback" or its semantic siblings;
Any Stack Exchange session I read about "Callback" contained answers that I either recognized as contradicting or controversial by other programmers commenting in comments.

## My question

Because the particular examples I read of this concept in Bash and JavaScript are not remembered to me as clear, I ask:

> Does the callback concept of programming have any basis in computer science?

That is to ask; is there, as part of a computer science theory, some `logical formula` that can simulate all possible "callback functions" (similarly to as a Turing machine can simulate all possible functions of a computer) that might help understanding the purpose of this concept?
An answer might help me understand what is the common denominator (if there is one) between different "callback" **terms** in programming.

# Answer
(I might be wrong, but this is my understanding.)

Callbacks, especially as seen in JS, are analogous to a semantic model known as Continuation-passing style (CPS). In CPS, a program’s flow is modeled as a series of functions, each of which takes in a continuation, and calls the continuation with the function’s result when finished.

As stated, this is also a form of higher-order programming, where functions are used as values.
> 3 votes

# Answer
Yes, callbacks belong to to the family of Higer-order functions. Because they're one of the simplest members of the family, they're often encountered in practice.
> 2 votes

---
Tags: terminology, programming-languages, logic, functional-programming, simulation
---


title: Separating the snakes

text:
# Question
Title: Separating the snakes
In a two-dimensional grid, there are $n$ "snakes" (sets of contiguous grid-blocks). The snakes do not touch each other. The goal is to cut the grid into $n$ rectangles using $n-1$ "fences" (horizontal or vertical lines along grid lines, from edge to edge or to a previously-built fence). It is allowed to "trim" at most a single sqaure from each snake (by all fences together).

Below is an example with $n=3$ snakes. Fence #1 runs from edge to edge and trims a square from the bottom snake. Fence #2 runs from the leftmost edge to fence #1 and trims a square from the upper-left snake.

Below is another example with $n=4$ snakes.

Finally, here is an example where the snakes cannot be separated, since each initial fence would trim at least two squares from one of the snakes.

QUESTION: Is there a polynomial-time algorithm for deciding whether or not it is possible to separate the snakes?

<sub> NOTE: without the option to trim a single square from each snake, there is a simple greedy polynomial algorithm: at each step, find a horizontal or vertical fence that can be built without trimming any snake. If such a fence exists, build it; otherwise, declare that it is impossible. </sub>

# Answer
> 3 votes
This can be solved in polynomial time.

Say that in the input we are given the number of snakes $n$ and for every snake the squares it occupies. Let $m$ denote the total number of squares in all snakes. Assume every snake occupies at least three squares.

If no square has $x$-coordinate in some interval $\[a, b\]$, we can compress that interval into a single point. Then, the squares have coordinates in range $\[0, 2m - 1\]$. We will do DP in $\mathcal{O}(m^{5})$.

We calculate a DP with a state for every rectangle $(x\_{0}, y\_{0}), (x\_{1}, y\_{1})$.

We say that some snake is inside the rectangle if at least two of its squares are inside the rectangle. If at least two of some snake's squares are outside the rectangle, we say it is outside the rectangle. Notice that a snake can be both inside and outside the rectangle.

Say there are $k$ snakes inside the rectangle. The DP will represent whether we can separate the $k$ snakes with at most $k-1$ fences while obeying the trimming rules.

If any snake is both inside and outside the rectangle, we automatically fail and set $DP\[x\_{0}, y\_{0}, x\_{1}, y\_{1}\] = 0$. If only one snake is inside the rectangle, we set $DP\[x\_{0}, y\_{0}, x\_{1}, y\_{1}\] = 1$.

Otherwise, for every $x\_{0} \< x \< x\_{1}$, we will try to add a fence at this $x$-coordinate. If $DP\[x\_{0}, y\_{0}, x, y\_{1}\]$ and $DP\[x, y\_{0}, x\_{1}, y\_{1}\]$ and no snake inside the rectangle is outside of both of the two rectangles the fence splits our rectangle to, the fence works and we set the value of the DP to true. We similarly loop $y$-coordinates inside the rectangle. If no working fence was found, we set the DP to false.

In the end, the algorithm outputs $DP\[0, 0, 2m-1, 2m-1\]$

This DP can be optimised to $\mathcal{O}(n^{5} + m)$ by trimming states from the DP. We can assume that the DP-box doesn't start or end with an empty column or row, therefore there has to exist some snake with the leftmost square in the box, and we can store $x\_{0}$ as the index of that snake, and whether the leftmost square in the box is the leftmost or second leftmost square of that snake (It cannot be any square after that, since then the snake would be outside the box). Storing $y\_{0}, x\_{1}, y\_{1}$ similarly gives us $\mathcal{O}(n^{4})$ dp-states. We can further loop the $x$-coordinate of a fence over just the first and last $x$-coordinates of squares of snakes in the rectangle plus minus at most one, as every other fence either trims too much from a snake or would be equivalent to a fence placed directly to the left of it. Loop similarly over $y$. The number of such coordinates is $\mathcal{O}(n)$.

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


title: Similarly colored paths in a DAG

text:
# Question
Title: Similarly colored paths in a DAG
Is there an algorithm that can efficiently solve the following question?

Given a directed acyclic graph G with n vertices each assigned a random color from a set of size \<= n - 1 colors, a source vertex s, and two distinct vertices a and b both having the same color and reachable from s.

Determine if there exists at least one path from s to a and one path from s to b that have the same sequence of vertex colors.

# Answer
> 2 votes
Hint:

> Use the techniques in How hard is finding the shortest path in a graph matching a given regular language?.

# Answer
> 2 votes
Let's take the initial graph $G=(V, E)$ and create a new graph $G'=(V', E')$ where every vertex $x$ is a state representing a pair ($i$, $j$) of vertices of $G$. So basically, for $N$ vertices in $G$, there are $N^2$ vertices in $G'$

In $G'$, there is an edge from $x\_1 = (i\_1, j\_1)$ to $x\_2 = (i\_2, j\_2)$ iif there are both an edge from $i\_1$ to $i\_2$ **and** an edge from $j\_1$ to $j\_2$ in $G$. Thus, a path in $G'$ of length $k$ corresponds to two different paths in $G$ having the same length $k$.

Now, let's resolve the problem, the same color sequence has to be followed by the two paths. So in $G'$, only vertices representing a pair of identical color vertices in $G$ are *allowed*. By running a BFS/DFS from $(s, s)$ to $(a, b)$ in this new graph, using only the *allowed* vertices, one can find if there is a solution to the problem.

The time complexity is $O(|E|^2)$ at worst case (all vertices having the same color). But if there are $c$ colors having rather equivalent populations in $G$, it falls to $O(|E|^2/c)$.

Also note, that you do not have to build explicitely $G'$ to explore it !

---
Tags: algorithms, graphs
---


# Question
Title: Count total number of k length paths in a tree
This is a question from a competitive programming competition. Given a tree with n nodes and a number k, find the total number of paths of length k in that tree.

I know for a fact that a solution can be found by using a centroid decomposition, however I am simply not sure on the exact relationship between the original tree and the tree we got from decomposition other than the fact that the length of path A -\> B in the original tree can be decomposed into a sum A -\> C + C -\> B in the decomposed tree. Where C is the LCA(A, B). All distances being in the original tree.

# Answer
> 12 votes
This can be solved in $\mathcal{O}(n \log n)$ by using the smaller-to-larger merging technique. Root the tree at an arbitrary vertex. We will calculate for every subtree an array where the $d$th position indicates the number of nodes at depth $d$ in the subtree. Of course, the total size of these arrays could be $\mathcal{O}(n^{2})$, so we will not store them, instead building the array at every node by "scavenging" the arrays of its children.

To calculate the number of nodes at depth $d$ in the subtree of $i$, calculate the arrays for all children of $i$, then prepend zero to them, and sum them up, then finally add 1 to the number of nodes at depth $0$ (to count node $i$). For fast prepending, we store the arrays as dynamic arrays with inverted indexing. When we add two arrays together, we only care about the result, not about what happens to the orignal arrays, so we can just add the numbers in the smaller array to the numbers in the larger array and return the larger array.

Thus, if node $i$ has children $c\_{1}, \dots, c\_{m}$ and $T\_{i}$ denotes the subtree of node $i$, we do an amount of work proportional to $w\_{i} = |T\_{i}| - \max\_{j} |T\_{c\_{j}}|$. Therefore the total complexity is $\mathcal{O}(\sum\_{i = 1}^{n} w\_{i})$. Note that if $p$ is the parent of $i$ and $|T\_{p}| \< 2|T\_{i}|$ then $|T\_{i}|$ does not appear in the sum. Therefore, on any path from the root to some node $x$, at most $\log n$ sets we count appear, and those are exactly the sets $x$ appears in. Since every vertex appears in at most $\log n$ sets, their total size is $\mathcal{O}(n \log n)$. This is tight: consider the perfect binary tree of size $n = 2^{h} - 1$.

It remains to show how to calculate the number of paths of length $k$ from the depth information. To do this, when combining two arrays $A$ and $B$ at some node, just add $\sum\_{i} A\[i\] B\[k-i\]$ to the answer. If $A$ is the sum of the arrays of previous children, and $B$ is the array of the current child we are handling, this corresponds to counting the paths with one endpoint in the current child's subtree, and the other in some earlier child's subtree. This can be done in $\mathcal{O}(\min(|A|, |B|))$ so it does not affect the runtime.

Here is a C++ implementation of the algorithm:

```
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
using ll = long long;

ll combine(deque<int>& a, deque<int>& b, int k) {
    if (a.size() < b.size()) swap(a, b);
    int as = a.size();
    int bs = b.size();

    // Count paths of length k
    ll res = 0;
    for (int i = max(0, (k - bs) + 1); i < min(k + 1, as); ++i) {
        res += a[i] * b[k-i];
    }

    // Combine a and b
    for (int i = 0; i < bs; ++i) a[i] += b[i];
    return res;
}

pair<ll, deque<int>> solve(int i, int k, int p, const vector<vector<int>>& g) {
    pair<ll, deque<int>> res = {(k == 0), {1}};
    for (int t : g[i]) {
        if (t == p) continue;
        auto sub = solve(t, k, i, g);
        sub.second.push_front(0);
        res.first += sub.first + combine(res.second, sub.second, k);
    }
    return res;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> g(n);
    for (int i = 0; i < n-1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    ll res = solve(0, k, -1, g).first;
    cout << res << '\n';
}

```

---
Tags: graphs, trees, recursion, counting
---


# Question
Title: Why doesn't Dijkstra's use a shortest-path first search?
When using BFS search on an unweighted graph to find the single-source shortest paths, no relaxation step is required because a breadth-first search guarantees that when we first make it to a node, we have found the shortest path to it.

However, my understanding is that Dijkstra's algorithm has no such guarantee because the neighbours of each node are checked in no specific order. Therefore, we need a relaxation step to update the shortest path of each node if we later find a shorter path.

Instead of choosing a random neighbour, why not always follow the neighbour with the shortest path? I think that would guarantee we have always found the shortest path and no relaxation step is required. I implemented this in Python and it seems to work. Am I missing something?

```
from heapq import heappop, heappush

def shortest_path_lengths(graph, source):
    dist = {}
    q = [(0, source)]
    while q:
        source_to_v1_dist, v1 = heappop(q)
        if v1 in dist:
            continue
        dist[v1] = source_to_v1_dist
        for v2, v1_to_v2_dist in graph[v1].items():
            if v2 not in dist:  # check it hasn't been visited already
                heappush(q, (source_to_v1_dist + v1_to_v2_dist, v2))
    return dist

graph = {
    'a': {'b': 3, 'c': 5},
    'b': {'c': 1},
    'c': {'d': 4},
    'd': {},
}
print(shortest_path_lengths(graph, 'a'))

```

# Answer
Congratulations! You have discovered an interesting variation of Dijkstra's algorithm.

---

However, it is misleading to state the standard version of Dijkstra's algorithm (stDA) described here as mentioned in the question does not use a shortest path first search. You might have overlooked the following statement in that article

> We now need to pick a new *current node*. That node must be the unvisited node with **the smallest minimum distance**.

In fact, using a shortest path first search so that the weight of each edge is checked at most once is the hallmark of Dijkstra's algorithm. That is the main reason that your algorithm can be labelled as a variation of Dijkstra's algorithm.

---

While the neighbours of each node are selected in no specific order in stDA, the same unorderly selection is also done in your algorithm in the following lines

```
        for v2, v1_to_v2_dist in graph[v1].items():
            # code to record the distance to v2 via v1.

```

---

Instead of including each vertex exactly once in the priority queue of unvisited vertex as in stDA, your algorithm pushes each vertex multiple times, once for every path that could possibly be the shortest path to that vertex at the moment that path is found. (This might make your algorithm slightly slower than stDA, since the number of operations to insert a new distance-vertex pair into the bigger min-heap in your algorithm will probably be more than the number of operations in the stDA needed to update the shortest distance so far to that vertex. For example, when the new distance is not shorter than the shortest distance so far.)

---

Instead of the separate relaxation step as in the stDA, your algorithm cleverly accomplished the object of the relaxation step in the same step that selects the shortest path to an unvisited vertex by also ignoring all other paths to visited vertices. It is fair to say your algorithm includes the relaxation step implicitly.

Overall, your algorithm is slightly easier to code than the stDA.
> 2 votes

# Answer
Dijkstra's already *does* follow the shortest pah found so far to one of the remaining nodes at each step.

I think your confusion lies in the "enqueue each neighbor of the current node" step: we can't just follow the shortest one of these to get the next node because the next shortest path might not be to a neighbor of the current node.

Thus we enqueue it as a *potential* shortest path for future consideration, and if we later find an even shorter path to that same neighbor-node, we replace it.
> 2 votes

---
Tags: shortest-path, dijkstras-algorithm
---


title: Deletion of record from B+ tree

text:
# Question
Title: Deletion of record from B+ tree
I was going through the B+ tree deletion operation from the book ***Database System Concepts, 6th Edition*** by Henry F. Korth. One particular thing caught my attention.

A B+ tree is given. We have to delete the record *"Gold"* from this tree.

So we first locate the record by going down the tree and once we find the node, we delete the record. But this deletion leaves the node underfull, because a leaf node has to be at least half full or it has to have at least $\lceil{\frac{n - 1}{2}}\rceil$ values, where $n$ is the maximum number of pointers in each node.

So we merge the rightmost two nodes. But this leaves their parents left pointer pointing to nothing. We again have a violation. Because the internal nodes need to have at least two pointers. To get around this, we merge the parent with its sibling. Resulting tree is given below:

Now the problem I'm having is that, why the record *"Gold"* has been moved down? We could have just as easily moved the record *"Katz"* up without violating anything. And it makes more sense to me, because we've just deleted *"Gold"*. So can anyone explain to me why this has been done like this in the book? And would I be right in saying that things would be the same if *"Katz"* had been moved up?

# Answer
> 1 votes
Yes and yes.

Any key that doesn't mess up the sort order can be used. Typically (in my experience), this is the minimum value from the right subtree. However, I'm not aware of any specific scenario where this would cause a problem either way.

When you delete a key (one practice I have seen is that) you delete the key along with the value. So, if you delete "Gold" you also delete all the keys with the value "Gold", so that no "Gold" remain. This wasn't done in this case and it's perfectly fine.

The thing about B tree and variants is that there are several ways you can implement them without violating any of the B tree properties. This leads to subtle differences like the one you've observed.

---
Tags: data-structures, search-trees, b-tree
---


# Question
Title: What computational model supports arbitrarily sized integers?
I want to do some research, but I don't think it's important the number of bits it takes to represent the integer input and arithmetic on the abstract machine. So what is the model that addresses this?

Specifically, I want to prove that integer factorization is not in P. If the above is a bad idea, then what model should I be using? Clearly, I would be needing add, sub, mul, and divide instructions.

Or, should something else be used such as algebraic complexity theory?

# Answer
> 2 votes
I suspect you're looking for either the RAM model or the transdichotomous model. They differ primarily in how they take into account the size of integers and their effect on the time of various operations. See What's the difference between transdichotomous model and RAM?.

If you want your results to have any applicability at all, the main thing is to pick a model that avoids treating the time to do arithmetic on exponential-length integers as polynomial, otherwise you can end up with absurd results. If you count each arithmetic operation as $O(1)$ time, no matter how large the numbers are, then you end up with absurd results like polynomial-time algorithms for factoring and indeed all of #PSPACE. See https://cs.stackexchange.com/a/53885/755.

Note that proving a problem is in P is not the same as proving it runs in polynomial time on some strange model of computation. P is defined as problems that have an algorithm that run in polynomial time *on a Turing machine*. As mentioned in the previous paragraph, if you change "on a Turing machine" to some other model of computation, that statement might no longer hold.

It's a famous open problem with factorization is in P or not. The problem is likely to be very difficult, with our current state of understanding. I would not recommend taking on such an ambitious goal.

---
Tags: turing-machines, computability, integers, primes, factoring
---


# Question
Title: Why is the run time with a loop of this structure considered O(log n)
I used the search function and a good amount of google searches, but wasn't able to get a straight answer on how a loop of the form below, is translated to a proper summation where the function derived from the summation is: $O(\log n)$.

**Example of the for loop:**

```
int j = 0;
for (int i = 2; i <= n; i *= 2) {
    j = j + n * 2;
}

```

So I understand within the loop we have 3 operations (multiplication, addition, then assignment).

I understand that the index $i$ ranges from $\[1, 2, 4, 8, 16, 32, 64, 128, 256\]$... ($i$ is only equal to powers of 2, up to $n$).

So essentially the range of $i$ seems to be from $\[2^m, n\]$ and $m \in \[0, \log\_2n\]$ right?

Also, $i^m \< n$ so the loop executes $\log\_2n - 0 + 1 = \log\_2n + 1$ times right? How do we go about expressing this in summation notation?

Is it this (just taking a guess, not sure if it's right):

$$\sum\limits\_{i = 0}^{log\_2n + 1} 3$$ since we have 3 operations? If this is the answer, why do we keep the upper bound of the summation to $\log\_2n$ instead of $n$? Also, I know typically we'd use $\log n$ but just put in the base 2 to help clear things up in my own head.

Could someone please show how the summation of the for loop is properly written?

# Answer
Assuming the model of computation is RAM(Random Access Machine). Which means the cost of addition, multiplication,division etc is constant. Now your program is

```
int j = 0;
for (int i = 1; i <= n; i *= 2) {
    j = j + n * 2;
}

```

Inside the loop, you are doing addition, multiplication, comparison etc which takes *constant* time. Let $k$ denotes the number of iterations of the loop. Let $c\_i$ denotes the cost at $i$th iteration of loop. The total cost is

$$ = c\_1+c\_2+\ldots + c\_{k}$$ $$ = \sum\_{ j =1 \text{ to } k}c\_i$$

It is easy to see that above summation gives $\mathcal{O}(\log n)$.
> 0 votes

---
Tags: algorithms, asymptotics, runtime-analysis
---


# Question
Title: Union of halting-like problem and non-halting-like problem
I came across the following problem:

> Define languages $L\_0$ and $L\_1$ as follows :
>
> $L\_0=\\{⟨M,w,0⟩∣M\text{ halts on }w\\}$
> $L\_1=\\{⟨M,w,1⟩∣M\text{ does not halt on }w\\}$
>
> Here $⟨M,w,i⟩$ is a triplet, whose first component $M$ is an encoding of a Turing Machine, second component $w$ is a string, and third component $i$ is a bit.
>
> Let $L=L\_0∪L\_1$. Which of the following is true?
>
> **A.** $L$ is recursively enumerable, but $\overline{L}$ is not
> **B.** $\overline{L}$ is recursively enumerable, but $L$ is not
> **C.** Both $L$ and $\overline{L}$ are recursive
> **D.** Neither $L$ nor $\overline{L}$ is recursively enumerable

I first felt that despite the bit as a third member of triple, $L\_0$ is still equivalent to halting problem and $L\_1$ is non halting problem. Union of halting and non halting problem is recursive as can be seen here. So, same will apply to the languages in the problem and their union will also be recursive, that is option C. But the answer given was D. So am guessing if its correct or not. I was not able to guess how that extra bit in the triple makes it different from halting problem.

# Answer
Let's write formally what $L$ and $\overline{L}$ are:

$$L=\\{\langle M,w,b \rangle| (b=0 \wedge M(w) \mbox{ halts}) \vee (b=1 \wedge M(w) \mbox{ does not halt}) \\}$$

$$\overline{L}=\\{\langle M,w,b \rangle| (b=1 \vee M(w) \mbox{ does not halt}) \wedge (b=0 \vee M(w) \mbox{ halts}) \\}$$ The latter is confusing, so let's rearrange it:

$$\overline{L}=\\{\langle M,w,b \rangle| (b=1 \wedge M(w) \mbox{ halts}) \vee (b=0 \wedge M(w) \mbox{ does not halt}) \\}$$

(Note that we ignore malformed inputs, but that can be easily circumvented and does not effect the answer).

From this, you can easily see that $L$ and $\overline{L}$ are basically the same idea -- the bit at the end determines whether you're looking at the halting problem or at its complement. In either case, neither $L$ nor its complement are recursively enumerable.

One thing that can trigger you to suspect this is the answer, even without formally writing $\overline{L}$, is the fact that both the halting problem and its complement easily reduce to $L$. Thus, $L$ is not recongnizable nor co-recognizable, and so neither is its complement.
> 1 votes

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


# Question
Title: Dijkstra and A* Algorithms: Why is A* faster?
I am learning about Dijkstra's Algorithm and the A\* Algorithm and I have manually worked through the graph attached here, which is supposed (I think) to demonstrate that the A\* Algorithm is faster than the Dijkstra one. The sequence in which I chose the nodes is indicated by the circled numbers. I can see that the process is fairly simple but there are plenty of possibilities for human error, so please bear with me.

My course book says that the A\* will be quicker.

I can't see why this is true. Have I worked through the graph incorrectly?

It seems to me that both methods require that all nodes must be visited so where is the increase in efficiency?

I have read what I can on Stack Overflow about this so please don't point me at earlier posts unless there is a very good reason.

# Answer
> 2 votes
I absolutely don't understand the attached images and what you try to do on it. What I can say is that Dijkstra an A\* algorithm are pathfinding methods:

**Dijkstra algorithm** is an exploration method that let you find the shortest path to any vertex of the graph. The idea is to always consider the vertices that you reach from the cheapest (closest) node of the queue.

You may run this algorithm to find the shortest path from a specific node $s$ to a specific node $t$. But you can also use it to determine global properties of the distances from $s$. Or for instance, build a tree that let you backtrack the path from $s$ to any vertex.

**A\* algorithm** is basically a Dijkstra method that use an additional heuristic to sort the nodes of the queue. On distance problem, this heuristic is generally based on the euclidian distance from the node to the aim. It favorises the exploration of the nodes that are more likely to go in the good direction. So this specialization of Dijkstra algorithm is only used to go from a specific node $s$ to a specific node $t$. It is generally largely faster but does not guarantee to find the optimal path (in the ver).

I suggest you play with this **pathfinding simulation tool**

# Answer
> 0 votes
Yes, I find it difficult to explain my problem. After some reflection I think I must be doing the A\* process incorrectly. I'm guessing that the node queue (as you call it) must be determined by the least sum of (distance to adjacent node + heuristic ). Maybe that's where I have got it wrong.

Actually Wikipedia states:

At each iteration of its main loop, A\* needs to determine which of its paths to extend. It does so based on the cost of the path and an estimate of the cost required to extend the path all the way to the goal. Specifically, A\* selects the path that minimizes

```
f ( n ) = g ( n ) + h ( n )

```

where n is the next node on the path, g(n) is the cost of the path from the start node to n, and h(n) is a heuristic function that estimates the cost of the cheapest path from n to the goal. A\* terminates when the path it chooses to extend is a path from start to goal or if there are no paths eligible to be extended. The heuristic function is problem-specific. If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A\* is guaranteed to return a least-cost path from start to goal.

So I think I've answered my own question.

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


# Question
Title: Coloring a graph with odd number of vertices with $k$ (which is close to $\Delta$) colors in linear time
We have an undirected simple connected graph with odd number of vertices. We also know the number $k$ which is actually the closest odd number greater than or equal to $\Delta$. (So if $\Delta$ is even, $k = \Delta +1$ else $k=\Delta$.) i.e $k$ is the least odd number that is greater than or equal to degrees of all vertices.

We want to find a linear time algorithm that colors the graph with $k$ colors.

I am very new to graph coloring algorithms. I know that a greedy algorithm is actually linear time and can color the graph with $\Delta +1$. But I can't guarantee I can color it with $k= \Delta$ when $\Delta$ is odd. Also, we probably should use all the information the question gives us. i.e using odd number of vertices somehow, but greedy algorithm don't use this extra information.

How can I solve this?

# Answer
Brooks' theorem states that every connected graph $G$ with maximum degree $\Delta$ can be colored (in linear time) using at most $\Delta + 1$ colors. In fact, the graphs that require $\Delta + 1$ colors are precisely complete graphs and odd cycles.

You state that we have a connected graph $G$ with an odd number of vertices and we want to color $G$ with $k$ colors, where $k = \Delta + 1$ when $\Delta$ is even and $k = \Delta$ otherwise. Let's break this down into cases:

* $G$ is complete (i.e., $G$ is $K\_n$ for $n = 3,5,7,\ldots$). By definition, $\Delta = n-1$ and since $n$ is odd, we have that $\Delta$ is even. Thus, we can color $G$ with $k = \Delta+1$ colors.
* $G$ is a cycle (i.e., $G$ is $C\_n$ for $n = 3,5,7,\ldots$). Clearly, for any non-trivial cycle we have that $\Delta = 2$ which is even. Again, we can color $G$ with $k = \Delta+1$ colors.
* $G$ is not complete nor a cycle. By Brooks' theorem, we have that $\chi(G) \leq \Delta \leq k$, so we are done.
> 2 votes

---
Tags: graphs, time-complexity, greedy-algorithms, colorings
---


# Question
Title: Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems
I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences.

The first problem I solved was longest palindromic substring and I managed to solve it successfully using the following logic: I have a function f(i,j) which returns the longest palindromic substring between characters at positions i,j in the string. I came up with the following recurrence:

```
f(i,j) = true // if(s[i] = s[j])
f(i,j) = true // if(i>j)
f(i,j) = true // if(s[i] = s[j] and f(i+1, j-1) == true)
f(i,j) = false // otherwise

```

Using this recurrence I managed to solve the problem successfully.

---

The second problem I wanted to solve was Longest valid parentheses (which I want to do using DP not stacks). The question is: Given a string containing just the characters '(' and ')', find the length of the longest valid parentheses substring.

My initial thought process was that this was similar to the longest palindromic substring problem that I already solved. So I defined f(i,j) as a function that returns longest valid parenthesis between elements i,j. The recurrence I came up with is as follows - here I use -1 to indicate that f(i,j) does not form a valid parenthesis:

```
f(i,j) = -1 // if i == j
f(i,j) = -1 // if j=i+1 and ! (s[i] = '(' and s[j] = ')')
f(i,j) = 2 // if j = i+1 and s[i] = '(' and s[j] = ')'
f(i,j) = 2 + f(i+1, j-1) if s[i] = '(' and s[j] = ')' and f(i+1, j-1) > 0;
f(i,j) = -1 // otherwise

```

My code (written in java) for the top-down version of the above is (note: dp\[\]\[\] was initialized to -2 indicating state i,j is not processed yet):

```
private int topDown(String s, int i, int j, int[][] dp) {
    if(dp[i][j] != -2)
        return dp[i][j];

    if(i == j)
        dp[i][j] = -1;
    else if(j == i+1 && (s.charAt(i) != '(' || s.charAt(j) != ')' ) )
        dp[i][j] = -1;
    else if(j == i+1 && (s.charAt(i) == '(' && s.charAt(j) == ')' ) )
        dp[i][j] = 2;
    else if(s.charAt(i) == '(' && s.charAt(j) == ')' && topDown(s, i+1, j-1, dp) > -1)
        dp[i][j] = 2 + topDown(s, i+1, j-1, dp);
    else
        dp[i][j] = -1;

    return dp[i][j];
}

```

This does not work for inputs like `()()` as it will return 2 instead of 4.

---

I was unable to come up with a solution of my own so I looked it up online. I found a solution here.

In this case the author defines f(i) as the length of the longest longest valid, balanced parentheses substring which begins at index i. He then describes the recurrence as follows:

```
f(i) = 2 + f(i+2)   // if s[i] = "(" and s[i+1] = ")"
f(i) = f(i+1) + f(i + f(i+1) + 2)   // s[i]="(" AND s[i+1]="(" AND s[i+f(i+1)+1]=")"
f(i) = 0    // otherwise

```

I have not written/tested the code for the recurrence but I assume it is correct.

---

**My questions are as follows:**

1. When I was solving the problem initially I had not thought of writing it as a function of f(i). I only thought of it as a function of f(i,j) and that turned out to be wrong. So is there an easy way to tell just by looking at a problem what states should be computed? For example why can't I solve the longest palindromic substring problem as a function of f(i)? similarly why can't I solve the longest parenthesis problem as a function of f(i,j)?
2. Is there a way to solve the longest valid parenthesis problem as a function of f(i,j) where f(i,j) represents the length of longest valid parenthesis between i and j? It is ok if the runtime complexity is higher I am just curious about this.

Thanks.

# Answer
Here is a way to solve the problem of longest valid parentheses by dynamic programming as you had hoped. Or almost.

For simplicity, a string is called valid if it consists of well-formed opening and closing parentheses.

The critical observation is that a string is valid if it is the empty string, a concatenation of two valid strings or "(" followed by a valid string followed by ")". In fact, that observation is the usual recursive definition of well-formed opening and closing parentheses! That observation indicates that a suitable set of subproblems are `s[i...j]`.

---

Let `s` be the given string of length `L`.

* Let `dp` be an `L` by `L+1` array of booleans.
`dp[i][j]` will become true iff the substring `s[i,j]` is valid. Here `s[i,j]` means the substring with indices from `i` inclusive to `j` exclusive, `0 <=i <= j < L`. In particular, `s[i,i]` means the empty string.
* Initially, all `dp[i][j]` are false.
* The base case is the empty string, `dp[i][i] = true` for all `i`.
* The recurrence relation is, according to the observation above, `dp[i][j] = true` for `i < j` if `s[i] == '('` and `dp[i+1][j-1] == true` and `s[j-1] == ')'` or there is an index `k`, such that both `dp[i][k] == true` and `dp[k][j] == true`. We can stipulate that `i < k < j`.

---

Here is the top-down version of the above approach, following the style in the question.

```
private static boolean topDown(String s, int i, int j, Boolean[][] dp) {
    if (i > j) return false;
    if (dp[i][j] != null) return dp[i][j];

    if (i == j) {
        dp[i][i] = true;
    } else {
        if (s.charAt(i) == '(' && s.charAt(j - 1) == ')' && topDown(s, i + 1, j - 1, dp)) {
            dp[i][j] = true;
        } else {
            for (int k = i + 1; k < j; k++) {
                if (topDown(s, i, k, dp) && topDown(s, k, j, dp)) {
                    dp[i][j] = true;
                }
            }
        }

    }

    if (dp[i][j] != null) {
        return true;
    } else {
        dp[i][j] = false;
        return false;
    }
}

```

---

Here is the bottom-up version. The code is sped-up a bit by the observation that a string can be valid only when its length is even.

```
private static int longestValidSubstring(String s) {
    final int L = s.length();

    // isValid[i][j] is true iff s.substring(i,j) is valid.
    boolean[][] isValid = new boolean[L][L + 1];

    // empty string is valid.
    for (int i = 0; i < L; i++) {
        isValid[i][i] = true;
    }
    for (int l = 2; l <= L; l += 2) {  // l is the length
        for (int i = 0; i <= L - l; i++) {
            // determine isValid[i][i+l]
            if (s.charAt(i) == '(' && s.charAt(i + l - 1) == ')' && isValid[i + 1][i + l - 1]) {
                isValid[i][i + l] = true;
            } else {
                for (int j = 2; j < l; j += 2) {
                    if (isValid[i][i + j] && isValid[i + j][i + l]) {
                        isValid[i][i + l] = true;
                        break;
                    }
                }
            }
        }
    }

    for (int l = L & 0xfffffffe; l >= 2; l -= 2) {
        for (int i = 0; i <= L - l; i++) {
            if (isValid[i][i + l]) {
                return l;
            }
        }
    }
    return 0;
}

```

---

The iterative version should be faster than the top-down version. However, even the iterative version is not fast enough when `L` is large since it computes `L * L` entries, which is pretty large once `L` is greater than 10000. Moreover, the two dimensional array `isValid` uses lot of memory as well.

Here is an improved solution of $O(n)$-time and $O(n)$-space. Here is the most brilliant solution, also of $O(n)$-time and $O(n)$-space. I will not discussion them, since they are out of the scope of this answer.

---

> Is there a way to solve the longest valid parentheses problem as a function of f(i,j) where f(i,j) represents the length of longest valid parentheses between i and j? It is ok if the runtime complexity is higher I am just curious about this.

The fundamental quality of the subproblems in dynamic programming is that you can solve a larger subproblem more easily once you have the solution to the smaller subproblem. Or, you can extend or combine the solutions to the smaller subproblems to build a solution to the larger problem.

In this particular problem, if we know whether all shorter substrings are valid or not, then it is easy to know a longer substring that is slightly longer is valid or not. On the other hand, if we know all f(i,j), which represent the length of longest valid substring between i and j, the lack of specific location of those longest valid substrings does not help us determine whether a substring of a longer substring is valid or not. The difference is critical, although might be subtle to untrained eyes. You will learn to appreciate the difference.

> When I was solving the problem initially I had not thought of writing it as a function of f(i). I only thought of it as a function of f(i,j) and that turned out to be wrong. So is there an easy way to tell just by looking at a problem what states should be computed? For example why can't I solve the longest palindromic substring problem as a function of f(i)? similarly why can't I solve the longest parenthesis problem as a function of f(i,j)?

As I have shown above, it is not necessarily wrong to use f(i,j) although we should give f(i,j) a slightly different meaning. Solving a problem efficiently might not be easy, even if it is known to be solvable by dynamic programming. Quite a few problems puzzle me for a long time even if I consider myself experienced. It requires some intelligence and experience to identify or formulate the proper set of subproblems (which are not necessarily in the exact form of the original problem).

To extend a palindromic substring to a longer palindromic substring, you need to extend it from both sides. That indicates it may not easy to solve the longest palindromic substring problem as a function of a single variable that stands for the one end of the palindromic string in a simple and efficient way. However, if we analyze the fine structure of palindromes, we could arrive at the Manacher's algorithm, which basically use a map from a single variable that stands for the center point of palindromic substrings.
> 4 votes

---
Tags: algorithms, dynamic-programming, recurrence-relation, recursion
---


# Question
Title: If I walk through list and delete every out-of-order element I come across, on average how many elements will be left?
I have a uniformly randomly permuted list of length $n$. I walk through the list element-by-element, and delete an element if it's out-of-order (compared to the previous in-order elements of the list). What I'm left with is a shorter list that's guaranteed to be in-order.

Example: The starred elements of this list would be deleted during the walk through.

\[1, 4, 2\*, 3\*, 5, 7, 6\*\] -\> \[1, 4, 5, 7\]

My question is: On average, what will be the length of the remaining list? And is there some simple/obvious form of the distribution of this?

And as one follow-up: if we used this for a sorting algorithm (called Drop Sort), what would the run-time be? To be clear, the algorithm would be something like this: $$\textit{DropSort}(\text{list}) = \textit{Merge}(\text{Remaining list}, \textit{DropSort}(\text{Rejected list}))$$

This question was inspired by this r/ProgrammerHumor post.

# Answer
You can compute the average using linearity of expectation.

Let the random variable $X$ denote the number of elements that are retained. Let $X\_i$ be an indicator r.v. that is 1 if the $i$th element is retained, or 0 otherwise. Then $X = X\_1+\dots + X\_n$, so

$$\mathbb{E}\[X\] = \mathbb{E}\[X\_1\] + \dots + \mathbb{E}\[X\_n\] = \Pr\[X\_1=1\] + \dots + \Pr\[X\_n=1\].$$

Now the $i$th element is retained if and only if it is the largest number among the first $i$ elements in the list. Therefore, $\Pr\[X\_i=1\]=\frac{1}{i}$, so

$$\mathbb{E}\[X\] = \frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n} \approx \log(n) + \gamma$$

In other words, the average length of the remaining list is $O(\log n)$.

I don't know what the distribution is.

As a heuristic, the expected running time of Drop Sort would satisfy a recurrence something like $T(n) \approx T(n-\log(n)) + O(n)$, which corresponds to $O\left(\frac{n^2}{\log n}\right)$ time.
> 2 votes

---
Tags: runtime-analysis, sorting, probability-theory, randomized-algorithms, permutations
---


title: Redistribute users over (chat)rooms

text:
# Question
Title: Redistribute users over (chat)rooms
I'm working on some kind of multiplayer game and for the best experience for the users I want to make sure the rooms are somewhat balanced at all time. By balancing I just mean the amount of users in the room (not score based or anything). I already figured out what the size of rooms should be and how many users there should be per room (based on a fixed maximum number of users per room). For a maximum of 4 users per room I came to the following distributions:

```
(total users) | (array of rooms (number is amount of users in room))
----------------------------------------------------------------------
4:              [4]
5:              [3, 2]
7:              [4, 3]
9:              [3, 3, 3]
13:             [4, 3, 3, 3]
...

```

I use the following code/algorithm to determine the distribution:

```
function calculateRoomDistribution(numUsers, maxUsersPerRoom) {
  const numRooms = Math.ceil(numUsers / maxUsersPerRoom)
  let distribution = []
  for (let i = 0; i < numRooms; i++) {
    distribution[i] = 0
  }
  for (let i = 0; i < numUsers; i++) {
    distribution[i % numRooms]++
  }
  return distribution
}

```

What I couldn't figure out however, is how to transition from one state to another. Let's say I have 13 users, divided over 5 rooms, respectively 4, 2, 2, 3, 2 users... I want to redistribute them into 4 rooms, with 4, 3, 3, 3 users. How would I approach such a problem? I was thinking of first removing the rooms that already have the right amount of users (4 and 3). That would leave me with \[2, 2, 2\]. But I noticed I would have to write a lot of edges and exceptions and I have a feeling there must be a smarter way. What type of algorithm am I looking for?

# Answer
> 2 votes
Here is one simple algorithm. Pick one room that has too many people in it, and one room that has too few people in it, and move one person from the first room to the second room. Repeat until convergence.

# Answer
> 0 votes
I think I've been really overthinking and came up with a bit of an awkward solution, but it seems to work! I've tried to limit the amount of modifications to the rooms as much as possible (without making it super complicated) by using the following strategy:

We know the amount of rooms we need, and we know their sizes. We loop over each room and try to adapt the current rooms to get the required size. We do this with the following steps:

1. if we already have a room of the required size, move to the next
2. if we have rooms bigger than required size: move users to smaller room until we reach required size
3. then we only have rooms left that are smaller than the required size:
    * first we try if we combine 2 of them to create 1 room of the required size
    * in case we can't we will move clients from smaller rooms to a bigger one until we get the required size

---
Tags: algorithms
---


# Question
Title: Find all edges of G contained in some MSP
I have the following question in a homework:

Let $G = (V,E)$ be an undirected graph, and let $$A = \\{ e \in E \mid \text{ s.t. exists an MSP $T$ containing } e\\}.$$

We were asked to find $A$ in $O(m \log n)$ time.

Any suggestions?

# Answer
> 1 votes
We call an edge superheavy if it is the unique heaviest edge in some cycle. This post shows that an edge $e\in A$ if and only if $e$ is not superheavy.

To find all edges that are not superheavy, we can first sort the edges according to their weights from small to large. Then, we remove all edges, re-add them in this order, and track the connected components by a disjoint-set data structure.

Now we can check whether an edge $e$ is superheavy by checking whether it connects two vertices in different connected components in the graph with edges whose weights are less than $w(e)$: If $e$ is superheavy, then the two endpoints of $e$ are connected by a path on which the edges have weights less than $w(e)$, so the two endpoints must lie in the same connected components in the graph with edges whose weights are less than $w(e)$. On the other hand, if $e$ connects two vertices in the same connected components in the graph with edges whose weights are less than $w(e)$, then we can find a path connecting the two endpoints of $e$ on which the edges have weights less than $w(e)$, so $e$ along with this path forms a cycle and $e$ has the largest weight in this cycle, so $e$ is superheavy.

---
Tags: algorithms, graphs, weighted-graphs, minimum-spanning-tree
---


title: Semantics for de Bruijn levels

text:
# Question
Title: Semantics for de Bruijn levels
There is an exceptionally simple way to embed simply typed lambda calculus with de Bruijn indices in a functional host language (discussed by Carette, Kiselyov & Shan, and by Kiselyov). The construction here, expressed in Haskell, is from Kiselyov's paper:

```
z :: (a, b) -> a
z (x, _) = x

s :: (a -> b) -> (c, a) -> b
s v (_, h) = v h

lam :: ((a, b) -> c) -> b -> a -> c
lam e h x = e (x, h)

app :: (a -> b -> c) -> (a -> b) -> a -> c
app e1 e2 h = e1 h (e2 h)

eval :: (() -> a) -> a
eval e = e ()

```

So, for example `eval (lam (lam (app z (s z)))) 2 succ` evaluates to `3`, as our `lam` expression `eval`'s to the Haskell value `\x -> \f -> f x`.

This embedding uses de Bruijn *indices*: to find the binder of a variable, count upward from the variable. I am curious about whether there is an analogous embedding of de Bruijn *levels*, where to find a variable's binder we count *downward*. Concretely, `\x -> \f -> f x` would be represented in such an embedding as `lam' (lam' (app' (s' z') z'))`.

The above embedding uses (as Kiselyov notes) nothing beyond the Hindley-Milner subset of Haskell 2010. It is not obvious to me whether de Bruijn levels can be implemented in such a simple type system. Indeed, it seems quite difficult: the environment tuples built by `lam` would need to be turned inside-out, or our variables would need to behave differently depending on the depth of the environment tuple. If we only had variables of one type, we could use lists; given that our variables have multiple types, do we require `HList`s?

======

Late edit to expand on the points in the last paragraph...

One way to think about de Bruijn levels is that `lam` `append`'s (rather than `cons`'s) to the environment. This way, from the perspective of a variable, the `head` of the environment (in a closed term) will always correspond to the highest `lam`. In terms of homogeneous lists:

```
zL :: [a] -> a
zL (x:h) = x

sL :: ([a] -> b) -> [a] -> b
sL v (_:h) = v h

lamL :: ([a] -> b) -> [a] -> a -> b
lamL e h x = e (h++[x])

appL :: ([a] -> b -> c) -> ([a] -> b) -> [a] -> c
appL e1 e2 h = e1 h (e2 h)

evalL :: ([a] -> b) -> b
evalL e = e []

```

This models de Bruijn levels, in the sense that `lamL (lamL (sL zL)) [] 2 3` evaluates to `3`. But it isn't simply typed lambda calculus, since it only allows variables of one type -- e.g., `lamL (lamL (appL (sL zL) zL))` is a type error.

To allow variables of multiple types, we can use `HList`:

```
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeOperators #-}

import Data.HList

zH :: HList (a ': b) -> a
zH (HCons x h) = x

sH :: (HList a -> b) -> HList (c ': a) -> b
sH v (HCons _ h) = v h

lamH :: HAppendList a '[b] =>
        (HList (HAppendListR a '[b]) -> c) -> HList a -> b -> c
lamH e h x = e (hAppendList h (HCons x HNil))

appH :: (HList a -> b -> c) -> (HList a -> b) -> HList a -> c
appH e1 e2 h = e1 h (e2 h)

```

Then `lamH (lamH (appH (sH zH) zH)) HNil 2 succ` evaluates to `3`, as desired. But this is a significantly heavier-duty approach than the embedding we began with. Do de Bruijn levels require all this artillery?

# Answer
> 1 votes
Here is a provisional answer. The de Bruijn index and level of a bound variable sum up to the number of enclosing lambdas: $i+l=n\_\lambda$. Since the index can be recovered from the level by subtraction, levels can be implemented as 'predecessor' indices `p`:

```
z :: (a, b) -> a
z (x, _) = x

s :: (a -> b) -> (c, a) -> b
s v (_, h) = v h

-- ^^^ as above

p :: (((), a) -> b) -> a -> b
p v h = v ((), h)

-- (p . s) v == v

app :: (a -> b -> c -> d) -> (a -> b -> c) -> a -> b -> d
app e1 e2 v h = e1 v h (e2 v h)

-- app manages an extra bit of context: the number of enclosing lambdas

lam :: (((a, b) -> c) -> (d, e) -> f) ->
       (b -> c) -> e -> d -> f
lam e v h x = e (s v) (x, h)

-- lam increments that context

eval :: (((a, env) -> a) -> () -> b) -> b
eval t = t z ()

-- evaluating closed terms...the starting context is z

```

This seems reasonable, and terms with just one variable (and arbitrary numbers of lambdas) behave as expected. But the type-checker chokes on terms with distinct variables -- e.g., `app (p . p) p`, our representation of the open term $21$, gives an 'infinite type' error.

To see why, let's consider a concrete evaluated closed term, `eval $ lam (lam (app (p . p) p))`. If you churn through the reductions by hand, eventually you end up with the following:

```
\x f -> s (s z) ((), ((), (f, (x, ())))) (s (s z) ((), (f, (x, ()))))

```

If both occurrences of `s (s z)` are polymorphic, this appears well-typed, and can be further simplified, to `\x f -> f x`, as desired (well, our de Bruijn level representation of this term is $\lambda\lambda 21$... close enough!). The problem, it seems, is that the Haskell type-checker insists that the two occurrences of `s (s z)` have the same monomorphic type, and therefore seems related to the absence of 'first-class polymorphism' in Haskell.

It is not obvious to me how 'deep' the problem here goes -- whether it can be massaged in Haskell; and if not, whether the implementation here can be coherently stated in, e.g., System F (Hindley-Milner seems out due to the need for first-class polymorphism).

---
Tags: haskell, functional-programming
---


# Question
Title: If L is a regular language then the language replace(L,σ,τ) is also regular
I am stuck at the following problem:

---

Prove that if $L$ is a regular language over some alphabet $\Sigma$ and that $\sigma, \tau \in \Sigma$, Then the language $replace(L,\sigma,\tau)$ is regular.

Where $replace(L,\sigma,\tau)$ is defined as:

$replace(L,\sigma,\tau) = \\{x\tau y\in \Sigma^\*| x\sigma y\in L\\}$.

---

My try:

Since $L$ is a regular language there exists a deterministic finite automaton $A=(\Sigma, Q, q\_0, F, \delta\_A)$ such that $L(A)=L$.

Now for each state $s\in Q$ we will define a non deterministic finite automaton $B\_s=(\Sigma\cup\\{\gamma\\}, Q\times \\{1,2\\}, q\_s, F\times \\{2\\}, \delta\_{B\_s})$ where $\gamma\notin \Sigma$ such that:

$\forall p\in Q,\mu\in\Sigma, \delta\_{B\_s}((p,1),\mu)=\\{(\delta\_A(p, \mu),1)\\} $

$\forall p\in Q-\\{s\\}, \delta\_{B\_s}((p,1),\gamma)=\emptyset$

$\delta\_{B\_s}((s,1),\gamma)=\\{(\delta\_A(s,\sigma),2)\\}$

$\forall p\in Q,\mu\in\Sigma, \delta\_{B\_s}((p,2),\mu)=\\{(\delta\_A(p, \mu),2)\\} $

$\forall p\in Q, \delta\_{B\_s}((p,2),\gamma)=\emptyset$

Now we'all define a new non deterministic finite automaton with $\epsilon$ moves $B$ by linking he starting state of this automaton to all of the starting states of the automatons $B\_{s}$ for every state $s$, And we will also link the final states of all of the $B\_{s}$ automatons to the final state of the automaton $B$.

The automaton $B$ will satisfy the property $L(B)=\\{x\gamma y|x\sigma y\in L\\}$ ( This is probably incorrect!!!)

Now we will define an homomorphism $h:\Sigma\cup\\{\gamma\\}\longrightarrow\Sigma$ such that:

$\forall \mu\in\Sigma,h(\mu)=\mu$

$h(\gamma)=\tau$

Since regular languages are closed under homomorphisms we can conclude that $h(L(B))$ is regular, But $h(L(B))=h(\\{x\gamma y|x\sigma y\in L\\})=\\{x\tau y|x\sigma y\in L\\}$ and so $replace(L,\sigma,\tau)$ is regular over $\Sigma$.

---

Thanks for any hint or help.

# Answer
Let $A$ be the alphabet and let $a$, $b$, $c$, ... be the letters (this is easier to type).

**Hint**. Consider the (non-deterministic) transducer $A^\* \to A^\*$ defined by $1 \xrightarrow{c \mid c}1\xrightarrow{a \mid b} 2 \xrightarrow{c \mid c} 2$ (more precisely, there are transitions $1 \xrightarrow{c \mid c} 1$ and $2 \xrightarrow{c \mid c} 2$ for any letter $c$ of $A$, including $a$ and $b$, but there is a single transition form $1$ to $2$). For each transition, the left hand part of the label is the input letter, the vertical bar is a separator and the right hand part is the output letter.
> 2 votes

# Answer
Use closure properties. Define homomorphisms $h\_1$ and $h\_2$ as follows:

$\begin{align\*} h\_1(x) &= \begin{cases} x & x \in \Sigma \\ \sigma & x = A \text{ (a new symbol)} \end{cases} \\ h\_2(x) &= \begin{cases} x & x \in \Sigma \\ \tau & x = A \end{cases} \\ \end{align\*}$

Then $h\_2(h\_1^{-1}(L) \cap (\Sigma^\* A \Sigma^\*))$ does the trick.
> 0 votes

---
Tags: formal-languages, regular-languages, automata, finite-automata, closure-properties
---


# Question
Title: Registers of Control Unit and Arithmetic Logic Unit
For an Instruction fetch cycle we have the flowing registers in a CPU.

1. Memory Address Register (MAR)
2. Memory Buffer Register (MBR)
3. Program Counter (PC)
4. Instruction Register (IR):
5. Accumulator Register:
6. Stack Control Register:
7. Flag Register:

Out of these I have come to know that PC and IR registers belong to control unit and accumulator belong to ALU but I do not know about rest of the registers. Either they also belong to CU or ALU or they exist separately not as apart of ALU OR CU ?

# Answer
They are part of the memory interface between the CPU and the memory subsystem.

The MAR (Memory Address Register) is closely associated with the memory ***address bus***, and the MBR (Memory Buffer Register) is closely associated with the memory ***data bus***.

Some CPUs choose to connect their general purpose registers more or less directly to those busses, thus eliminating these specialized registers, but this is not usually the case in accumulator machines that you're describing in your question.

Some CPUs have a secondary ~ALU dedicated to addressing computation (so probably just add and some specific shifts, e.g. by 0, 1, 2, or 4); such a secondary ALU might also work in conjunction with the MAR or in replacement of an MAR.

On some processors, the CU will have to interleave requests for instructions from memory with requests by the program for data from memory. The instruction address (found in the PC) may first go through the MAR during fetch, or the PC value may be sent directly to the address bus during fetch, depending on the CPU design.

If the processor has a separate instruction cache and data cache, then it has two memory subsystem interfaces. Typically the PC will then serve directly as the MAR for the instruction memory interface rather than creating a second MAR for that.

---

Note that the MAR, MBR, and the IR are internal registers that are generally not visible to the program or programmer, and so only visible if you're looking inside a particular processor's design. The same instruction set architecture can be implemented in different ways, and in these alternative implementations, the discussions of the above considerations may vary; this happens in a processor family, like x86.
> 4 votes

# Answer
To complement Erik Eidt's answer, the *Flag Register* conceptionally gets input from the ALU and is heavily used by the CU.
("The Memory Interface Registers" typically do *not* feature in the programming model.)
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Is O(n log n) exponential speedup over O(n^2)?
I would like to know if $O(n \log n)$ is an exponential speedup over $O(n^2)$?

# Answer
$O(n \log n)$ is a *polynomial* speedup over $O(n^2)$, in particular almost a *quadratic* speedup. $O(n \log n)$ is big-O of $O(n^k$) for all $k \> 1$. Its runtime is therefore between linear and any powerfunction whose exponent is strictly greater than 1.

Let $f(n)=n \log n$. Raise it to a power of some value slightly less than 2 to approximate the original runtime. We conclude $f(n) \approx n^{2-\varepsilon} (\log n)^{2-\varepsilon}$ and in $O(n^2)$. If we square $f(n)$, we have $n^2 (\log n)^2$, slightly less efficient than the original $n^2$, hence it is basically a quadratic speedup.

Instead, $O(\log n^2) = O(\log n)$ is an exponential speedup over $O(n^2)$. If $g(n) = 2\log(n)$, then $e^{g(n)} = n^2$.
> 2 votes

---
Tags: complexity-theory, polynomials, big-o-notation
---


# Question
Title: Set which is easy to sample, but difficult to sample from its complement
Given a set $S \subseteq \\{0,1\\}^\*$, the algorithm $A$ is a generator for $S$ if given $n$ random bits $x \in \\{0,1\\}^n$, $A$ generates an element of $S$ of size $n$, and $A$ can generate at least $\frac{2}{3}$ members of $S$ of size $n$ (for all $n$). $A$ does not have to be uniform.

Is there a set $S$ such that there exists an efficient algorithm $A$ such that for all $n$, $A$ generates at least $\frac{2}{3}$ members of $S$ (of size $n$), but any efficient algorithm for $S^C$ can only generate at most $\frac{1}{3}$ elements from $S^C$ of size $n$ (under complexity asuumptions)?

# Answer
We can construct $S$ such that polynomial-time generators for $A$ exist, while no generator exists for $S^{c}$. Pick $S$ such that all strings starting with $1$ are in it, and exactly half of all strings starting with $0$ are in it.

A sampler that sets the first bit of $x$ to $1$ and outputs it always generates an element in $S$, and generates exactly $\frac{2}{3}$ of the elements in $S$.

However, sampling from the complement of $S$ in the general case is even harder than you require: there exist sets $S$ such that there exists no Turing machine that given $n, x = 0^{n}$ as input outputs any string in $S$ of length $n$ starting with $1$. Furthermore, we can explicitly construct such a set $S$.

This is easy to prove by a diagonalisation argument. Let $K\_{w, n}$ be the set of strings of length $n$ starting with $w$. There is a countable number of Turing machines, so let $M\_{i}$ be the $i$th Turing machine. For $n \geq 2$, if $M\_{n-1}$ on input $n, x = 0^{n}$ doesn't halt or outputs a string in $K\_{00, n}$, set $S\_{n} = K\_{1, n} \cup K\_{00, n}$. Otherwise set $S\_{n} = K\_{1, n} \cup K\_{01, n}$. Then $S = \\{\epsilon, 1\\} \cup \bigcup\_{i = 2}^{\infty} S\_{i}$ is one such set.
> 2 votes

---
Tags: complexity-theory, discrete-mathematics, randomized-algorithms, pseudo-random-generators, sampling
---


title: Maximum flow on a tripartite graph

text:
# Question
Title: Maximum flow on a tripartite graph
I have to solve an assignment problem between $\\{1,\dots, N\\}$ agents and $\\{1,\dots, M\\}$ objects, which comes to maximize : \begin{equation} \sum\_{ij}\beta\_{ij}x\_{ij} \end{equation} where $x\_{ij}$ equals one if object $j$ is assigned to $i$, $0$ otherwise. The benefit of such an assignment is the non-negative value $\beta\_{ij}$.

This problem usually comes wih some constraints : \begin{equation} \sum\_i x\_{ij} = 1~,~~\sum\_j x\_{ij} = 1 \end{equation} stating that an object can only be assigned once and that an agent can only assign one object.

As far as I understand, this problem can also be viewed as a maximum flow on a bipartite graph and can be efficiently solved by an auction algorithm (see Bertsekas et al.)

I have to implement additional constraints labeled $k=1,\dots, K$ which are all of the same form : the $k^{th}$ one imposes that on a subset of object $\mathcal{J}\_k$, only a limited number of them, say $P\_k$, can be assigned in the same time : \begin{equation} \sum\_{j\in \mathcal{J}\_k}\sum\_i x\_{ij} \le P\_k \end{equation}

My question is that I find quite difficult to solve former problem with these new constraints on a bipartite graph and I wonder if a tripartite graph would be more convenient.

**Here is below how I would do, I would like to call upon more experienced people in this field to assess whether this approach is well suited or if there is a simpler one.**

I put the former problem with the additional constraints in the form of a tripartite graph : the first column is still that of agents and the third one that of objects, except that agents and objects are no more directly linked.

Between first and third column, I insert the column of the $\\{1,\dots,K\\}$ constraints. Let $y\_{ik}\in\\{0,1\\}$ be the link between agent $i$ and constraint $k$. The additional constraint $k$ now reads : \begin{equation} 0\le\sum\_i y\_{ik} \le P\_k \end{equation} The flow of agents onto constraint $k$ is limited.

Furthermore, let $z\_{kj}\in\\{0,1\\}$ be the link between constraint $k$ and object $j$.

That is to note, an object $j$ can be linked to several constraints, let $\mathcal{K}\_j$ be the subset of constraints in which object $j$ is involved, i.e. $j\in \mathcal{J}\_k$.

The flow from constraint $k$ to objects must equal that of agents to this constraint :

\begin{equation} \sum\_i y\_{ik} = \sum\_j z\_{kj} \end{equation} which means that an agent $i$ is connected to constraint $k$ because there is some object $j$ linked to it, and conversely.

Then, coming back to the bipartite graph, the link $x\_{ij}$ between agent $i$ and object $j$ is now given by: \begin{equation} |\mathcal{K}\_j| x\_{ij} = \sum\_{k\in\mathcal{K}\_j} y\_{ik} \end{equation} There is equality only if the agent $i$ is connected to all constraints $k$ in which object $j$ is involved.

Because $P\_k\< |\mathcal{J}\_k|$ there will always remain at least $|\mathcal{J}\_k| - P\_k$ unassigned objects due to constraint $k$.

Let's define a virtual agent $s$ to which we attach all objects (at zero benefit) not linked with any constraint $k$, $\forall k~~ z\_{kj} = 0$. The link is denoted $x\_{sj}\in\\{0,1\\}$ because it is a direct link between an agent and an object.

Each object $j$ must fulfill : \begin{equation} \sum\_{k\in\mathcal{K}\_j} z\_{kj} + |\mathcal{K}\_j| x\_{sj} = |\mathcal{K}\_j| \end{equation} Then, either object $j$ is connected to all its constraints, $\forall k\in\mathcal{K}\_j~,~z\_{kj} = 1$, or it is connected to the virtual node, $x\_{sj}=1$.

It is clear that if the flow on all constraints reach its maximum, there will remain at least : \begin{equation} \sum\_k (|\mathcal{J}\_k| -P\_k) - \sum\_j (|\mathcal{K}\_j| - 1) \end{equation} objects unassigned. The second term accounts for objects that belong to more than one constraint. Thus : \begin{equation} \sum\_j x\_{sj} \ge \sum\_k (|\mathcal{J}\_k| -P\_k) - \sum\_j (|\mathcal{K}\_j| - 1) \end{equation}

I assume now that each agent $i$ must be granted $M\_i \ge 1$ objects : \begin{equation} \sum\_j x\_{ij} = M\_i \end{equation}

So, for the problem to be feasible, I need at the least : \begin{equation} \sum\_i M\_i \end{equation} objects whereas there are at least \begin{equation} \sum\_k P\_k - \sum\_j (|\mathcal{K}\_j| - 1) \end{equation} of them available. The difference between both will also remain unassigned at the end : \begin{equation} \begin{split} \sum\_j x\_{sj} &\ge \sum\_k (|\mathcal{J}\_k| -P\_k) - \sum\_j (|\mathcal{K}\_j| - 1) +\sum\_k P\_k - \sum\_j (|\mathcal{K}\_j| - 1)- \sum\_i M\_i\\ &\ge \underbrace{\sum\_k |\mathcal{J}\_k| - \sum\_j (|\mathcal{K}\_j| - 1)}\_M - \biggl(\underbrace{\sum\_i M\_i + \sum\_j (|\mathcal{K}\_j| - 1)}\_N\biggr) \end{split} \end{equation} where $M$ is the true number of objects and $N$ is the true number of objects required by agents.

Then, each time the links between an object and its constraints are broken, the object becomes unassigned, so that : \begin{equation} \sum\_j x\_{sj} - (M-N) = \sum\_k y\_{sk} \end{equation}

where $y\_{sk}$ is the link between the virtual agent and the constraint $k$, whose capacity is $\\{0,\dots,P\_k\\}$ and checks : \begin{equation} \sum\_i y\_{ik} + y\_{sk} = P\_k~,~~0\le y\_{sk}\le P\_k \end{equation}

I would like then to write the dual formulation of this problem in order to solve it with an auction algorithm. Coming back to the assignment problem, its lagrangian is :

\begin{equation} \begin{split} \mathcal{L} = & \underbrace{\sum\_{ij} (-\beta\_{ij})x\_{ij}}\_A \+ \underbrace{\sum\_i \pi\_i \biggl(\sum\_j x\_{ij} - M\_i \biggr)}\_B \+ \underbrace{\sum\_j p\_j \biggl(\sum\_{k\in\mathcal{K}\_j} z\_{kj} \+ |\mathcal{K}\_j| x\_{sj} - |\mathcal{K}\_j| \biggr)}\_C\\ & + \underbrace{\sum\_k \mu\_k \biggl(\sum\_i y\_{ik} - \sum\_{j\in\mathcal{J}\_k} z\_{kj} \biggr)}\_D \+ \underbrace{\sum\_k ( -\lambda\_k) \biggl(\sum\_i y\_{ik} + y\_{sk} - P\_k\ \biggr)}\_E\\ & + \underbrace{(-\lambda)\biggl(\sum\_j x\_{sj} - (M -N) - \sum\_k y\_{sk} \biggr)}\_F \end{split} \end{equation}

\begin{equation} A = \sum\_{ij} (-\beta\_{ij})x\_{ij} = \sum\_{ij} (-\beta\_{ij})\frac{1}{|\mathcal{K}\_j|}\sum\_{k\in\mathcal{K}\_j} y\_{ik} = \sum\_{ik}\biggl(-\sum\_{j\in\mathcal{J}\_k}\frac{\beta\_{ij}}{|\mathcal{K}\_j|}\biggr)y\_{ik} \end{equation}

\begin{equation} B = \sum\_i \pi\_i \biggl\[\sum\_j\biggl(\frac{1}{|\mathcal{K}\_j|}\sum\_{k\in\mathcal{K}\_j} y\_{ik}\biggr) \- M\_i \biggr\] = \sum\_{ik}\pi\_i \biggl(\sum\_{j\in\mathcal{J}\_k}\frac{1}{|\mathcal{K}\_j|} \biggr)y\_{ik} - \sum\_i \pi\_i M\_i \end{equation}

\begin{equation} C = \sum\_k\sum\_{j\in\mathcal{J}\_k} p\_j z\_{kj} + \sum\_j p\_j |\mathcal{K}\_j| x\_{sj} - \sum\_j p\_j |\mathcal{K}\_j| \end{equation}

\begin{equation} D = \sum\_{ik} \mu\_k y\_{ik} - \sum\_k\sum\_{j\in\mathcal{J}\_k}\mu\_k z\_{kj} \end{equation}

\begin{equation} E = -\sum\_{ik} \lambda\_k y\_{ik} - \sum\_k\lambda\_k y\_{sk} + \sum\_k\lambda\_k P\_k \end{equation}

\begin{equation} F = -\sum\_j \lambda x\_{sj} + \lambda (M -N) + \sum\_k \lambda y\_{sk} \end{equation}

Finally : \begin{equation} \begin{split} \mathcal{L} = & \sum\_{ik}\biggl\[\pi\_i \biggl(\sum\_{j\in\mathcal{J}\_k}\frac{1}{|\mathcal{K}\_j|}\biggr) \+ \mu\_k - \lambda\_k -\sum\_{j\in\mathcal{J}\_k}\frac{\beta\_{ij}}{|\mathcal{K}\_j|}\biggr\] y\_{ik}\\ &+\sum\_k\sum\_{j\in\mathcal{J}\_k}(p\_j - \mu\_k) z\_{kj} + \sum\_k(\lambda - \lambda\_k)y\_{sk} \+ \sum\_j (p\_j|\mathcal{K}\_j| - \lambda)x\_{sj}\\ &- \sum\_i \pi\_i M\_i -\sum\_j p\_j |\mathcal{K}\_j| + \sum\_k\lambda\_k P\_k+ \lambda (M -N) \end{split} \end{equation}

The dual formulation consists then in minimizing : \begin{equation} \sum\_i \pi\_i M\_i +\sum\_j p\_j |\mathcal{K}\_j| - \sum\_k\lambda\_k P\_k - \lambda (M -N) \end{equation}

under the constraints : \begin{align} \pi\_i \biggl(\sum\_{j\in\mathcal{J}\_k}\frac{1}{|\mathcal{K}\_j|}\biggr) \+ \mu\_k &\ge \lambda\_k +\sum\_{j\in\mathcal{J}\_k}\frac{\beta\_{ij}}{|\mathcal{K}\_j|}\\ p\_j &\ge \mu\_k \\ p\_j|\mathcal{K}\_j| &\ge \lambda \end{align} and

* if $\lambda \> \lambda\_k$ then $y\_{sk} = 0$
* if $\lambda = \lambda\_k$ then $y\_{sk} \in\\{1, \dots, P\_k -1\\}$
* if $\lambda \< \lambda\_k$ then $y\_{sk} = P\_k$

Then, how to perform the auction algorithm ? agents now bid on constraints.

# Answer
Your problem is NP-hard. With the extra constraint, it is at least as hard as max independent set.

In particular, suppose we have an undirected graph $G$. Let there be one object per vertex in $G$. For each edge in $G$, we'll have a constraint saying that at most one of the two endpoints of that edge can be assigned (using your new constraint type). We'll then have one actor per object, and the $\beta\_{ij}$ can be all 1 (or you can have $\beta\_{ii}=1$ and $\beta\_{ij}=0$ for $i \ne j$). Now the maximum assignment corresponds to the maximum independent set. So, any efficient algorithm for your problem would also provide an efficient algorithm for max independent set -- something which we expect probably does not exist.

So, I wouldn't expect any efficient algorithm for your problem. Instead, I would suggest using heuristics, an ILP solver, or looking for an approximation algorithm or some kind of parametrized-complexity algorithm.
> 1 votes

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


title: PTAS vs. FPTAS input

text:
# Question
Title: PTAS vs. FPTAS input
I am trying to understand what is the PTAS, FPTAS and what is the difference between them.

I found this analysis:

PTAS definition vs. FPTAS

but I cannot understand what do we mean by saying:

"....time complexity is polynomial in the input size and also polynomial in 1/ϵ" ?? Ok n has to do with the linear O(n) worst case that the algorithm runs. But O(1/ε) how does it work?

# Answer
> 4 votes
For example, the running time $O(2^{1/\varepsilon} \cdot n^2)$ corresponds to a PTAS, since the running time depends polynomialy on $n$, but not on $1/\varepsilon$ since it is in the exponent. The running time $O(1/\varepsilon \cdot n \log{n})$ depends polynomialy on $n$ and $1/\varepsilon$, so it corresponds to a FPTAS.

NB, you also need to show that your algorithm has an approximation ratio of $(1 + \varepsilon)$ (or -) to show the algorithm is in fact a (F)PTAS.

---
Tags: time-complexity
---


title: Is this truth table possbile

text:
# Question
Title: Is this truth table possbile
I am trying to figure out if this truth table is possible. I've tried inverting the numbers, adding them, subtracting them, but I still cant find anything that works. I am starting to think that this is not possible.

# Answer
What's wrong with `A AND (NOT B)`?
> 1 votes

---
Tags: circuits, digital-circuits
---


# Question
Title: How to find percentage of CPU time consumed during DMA operation?
**Q)** Consider 1MBps hard-disk is interfaced to the processor in a cycle stealing mode of DMA whenever $64$ bytes of data is available in the buffer,then it is transferred to main memory (1 word = 64 bits) and machine cycle time is 2 micro sec. Then,

1.) Percentage of CPU time consumed for DMA operation is ?
2.) Percentage of CPU time consumed for DMA Operation if burst mode is used?

**Given Solution :**
**1.)** For ***Cycle Stealing Mode***
1 word = 64 bits = 8 bytes is transferred in one cycle.
Since total 64 bytes is to be transferred So total number of cycles $= 64/8 =8 $,
1 cycle time = 2µs , So time for 8 cycles is = 16µs
Now time taken by disc to transfer 64 B is $(64)/10^{6}=64µs$
Hence % of CPU Time consumed = Data Preparation Time / Data Transfer time $= (16 / 64)\*100\\% = 25\\%$
**My Doubt :** How does the above formulae give the % time consumed by CPU or basically where CPU spends time during a DMA transfer and why are we dividing by the disk transfer time.

**2.)** For ***Burst Mode*** : Since all data is transferred at once so only 1 cycle is needed for data transfer i.e. 2 µs So % CPU time consumed = Data Preparation Time / Data transfer Time
=$(2/(2+64))\*100\\%$ =~ $3\\%$
**My Doubt :** Why are we adding the 2 in burst mode.

# Answer
1 word=64 bit=8 B

64 B=8 word

machine cycle time=2 microseconds =\> 1 word is transferred from io buffer to memory by cpu in 2 microseconds =\> data preparation time by cpu 64 B data and io bandwidth is 1MBps

so 64/10^6 seconds = 64 microseconds = transfer time by io device = time to dump data from io device to io buffer

now in cycle stealing mode generally data is transferred byte wise..but here word size is given so we assume data is transferred word wise..

64B data in 64 microseconds

=\> 8 word data in 64 microseconds

=\> 1 word data in 8 microseconds = this is word transfer time by io to buffer

so % cpu blocked= % cpu time consumed = % time CPU is actually transferring data from io buffer to main memory= (2/8)\*100%=25%

in burst mode its ( 2 / (2+8) )\*100%=20%\>\>\>\>\>\>\>

in burst mode all data is transferred once as a block...so we wait for io to dump all of 64 B data in its buffer which is 64 microseconds

now cpu will fully transfer this data from io buffer to main memory..64 B data meaning 8 word data meaning 8\*2 microseconds meaning 16 microseconds..

so 16\*100/(16+64) % = 2\*100/(2+8) = 20%
> 0 votes

---
Tags: computer-architecture, cpu, memory-hardware, memory-access
---


# Question
Title: Do theorem provers demonstrate their own correctness?
I am not very well-versed in the world of theorem proving, much less automated theorem proving, so please correct me if anything I say or assume in my question is wrong.

Basically, my question is: are automated theorem provers themselves ever formally proven to work with another theorem prover, or is there just an underlying assumption that any theorem prover was just implemented really really well, extensively tested & reviewed, etc. and so it "must work"?

If so, does there always remain some underlying doubt in any proof proven by a formally verified automated theorem prover, as the formal verification of that theorem prover still lies on assuming that the non-formally verified theorem prover was correct in its verification of the former theorem prover, even if it might technically be wrong - as it was not formally verified itself? (That is a mouthful of a question, apologies.)

I am thinking of this question in much the same vein as bootstrapping compilers.

# Answer
I recommend reading Pollack's How to believe a machine-checked proof. It explains how proof assistants are designed to minimize the amount of critical code.

There are many levels of formal verification (that's the phrase you're looking for in place of "proven") of a proof assistant:

1. Verify that the algorithms used by the proof assistant are correct.
2. Verify that the implementation of (the critical core of) the proof assistant is correct.
3. Verify that the compiler for the language in which the proof assistant is implemented is correctly designed and implemented.
4. Verify that the hardware on which the proof assistant runs is correctly designed and built.
5. Compute the probability that a cosmic ray passes through the CPU and tricks your proof assistant every time you run it.
6. Estimate the likelihood that you are insane.

People put serious effort into these (well, at least the first four). For example, steps 1 and 2 are addressed in Coq Coq Correct!, and steps 3 and 4 in the amazing award-winning CompCert project.
> 46 votes

# Answer
What you need is the idea of "the trusted core". Quoting "A verified runtime for a verified theorem prover":

> In many theorem provers, the trusted core—the code that must be right to ensure faithfulness—is quite small. As examples, HOL Light is an LCF-style system whose trusted core is 400 lines of Objective Caml, and Milawa is a Boyer-Moore style prover whose trusted core is 2,000 lines of Common Lisp. These cores are so simple we may be able to prove their faithfulness socially, or perhaps even mechanically as Harrison did for HOL Light.

Once you assure yourself the core is correct, it can be used to verify the correctness of some extensions, and then those extensions can be used...
> 10 votes

# Answer
While this may trend close to self-advertisement, this is essentially the topic of my recent paper Metamath Zero: The Cartesian Theorem Prover (video), and the analogy with bootstrapping compilers is spot on. The introduction of the paper lays out what is needed to make this happen, and it's only a problem of engineering.

As Andrej says, there are several components that go into a "full bootstrap", and while many of the parts have been done separately, the theorem provers that are used by the community are only correct in the sense that linux is correct: we've used it for a while and there are no bugs we have found so far, except the bugs that we did find and fix.

The issue, as ever, is that because the cost of producing verified software is high, verified programs tend to be simplistic or simplified from the "real thing", and so there remains a gap between what people use and what people prove theorems about. A "small trusted kernel" setup is necessary but not sufficient, because unless you have a full formal specification (with proofs) of the programming language, the untrusted part can still interfere with the trusted part, and even if the barrier is air-tight, you have communication problems when the untrusted part is in control - for example, the kernel may flag an error that the untrusted part ignores, or the kernel may never be shown some apparent assertion at the source level.

The good news is that projects of this scale have become feasible in the past few years, so I am very hopeful that we can get production quality theorem provers with verified backends soon-ish.

* The CakeML project should get a mention here: they have a ML compiler verified in HOL4, that is capable of running a HOL verifier written in ML. (Unfortunately HOL4 is more than just its logical system, so there is some work to be done to make this realistic.)
* The Milawa kernel is written in a subset of ACL2, with a bunch of bootstrapping stages before closing the loop (being able to prove theorems about this same ACL2 subset). This is the only actual theorem prover bootstrap I know, but it doesn't go down to machine code, it stays at the level of Lisp, and from what I understand it's not actually performant enough for production work. It has since been verified down to machine code, but that part of the proof was done in HOL4 so it's not actually bootstrapping at the machine code level.
* Coq recently made some strides towards this with Coq Coq Correct!, but it doesn't cover the full Coq kernel (including recent additions such as SProp, and the module system). (Aside, if there are any Coq experts reading this: if you know any place where the *complete* formal system implemented by Coq is written down, I would really like to see it. Formalized is nice but informal might even be better, as long as it is complete and precise.) You also can't connect it to CompCert as Andrej suggested, because the typechecking algorithm is only described abstractly, and certainly not in C, which is what CompCert expects as input.
* Metamath Zero is still under construction but the goal is to prove correctness down to the machine code level, inside its own logic. (I also can't help but mention it's currently about 8 orders of magnitude faster than "the other guys" but we'll see if that holds up until the end of the project.)
> 6 votes

# Answer
In case you are not aware, there is a possibility that a theorem prover is implemented 100% correctly and run on a faultless machine and proves itself arithmetically inconsistent, even though it is not. The other existing answers focus on the issue of verifying that the theorem prover runs exactly as it was designed to run, but do not address this aspect of "correctness".

More precisely, every theorem prover is based on some underlying foundational system $S$. For $S$ to be considered a reasonable foundational system, $S$ must interpret arithmetic, meaning that there is a computable translation $ι$ of sentences over PA to sentences in the language of $S$ such that for every arithmetical sentence $Q$ we have that if PA proves $Q$ then $S$ proves $ι(Q)$. Godel's incompleteness theorem can be easily extended to any such (computable) foundational system $S$, and states the following: $ \def\con{\text{Con}} $

> If $S$ does not prove $ι(0=1)$, then $S$ does not prove $ι(\con(S))$.

Here $\con(S)$ is the arithmetical sentence that encodes the (arithmetical) consistency of $S$. Namely, $S$ does not prove $ι(0=1)$ iff $\mathbb{N} ⊨ \con(S)$.

So first of all, this implies that $S$ cannot possibly prove its own consistency unless it is inconsistent. In this sense **it is impossible for any theorem prover to prove that itself is correct**. It may be able to prove that its execution on a particular machine satisfies certain specifications (as mentioned in other answers), but that is far from proving correctness of the theorems that it proves. In other words, anyone who wants confidence in a theorem prover's outputs still must examine those specifications and be somehow convinced that they ensure correctness of the outputs. That part can never be covered by the theorem prover itself.

Secondly, if $S$ is deductively closed for arithmetical sentences, meaning that if $S$ proves $ι(Q)$ and $ι(Q⇒R)$ then $S$ also proves $ι(R)$, then let $A(S)$ be the arithmetical theorems of $S$, namely all arithmetical sentences $Q$ such that $S$ proves $ι(Q)$, and let $S'$ be a formal system that proves the same theorems of $S$ plus $ι(R)$ for every arithmetical sentence $R$ such that $A(S)+¬\con(S)$ proves $R$. Then $S'$ is still deductively closed for arithmetical sentences, but $S'$ proves $ι(¬\con(S))$ and hence $ι(¬\con(S'))$.

Note that $S'$ proves everything that $S$ does, and **if** $S$ is consistent **then** $S'$ is also consistent but proves that itself is inconsistent. Now how can we know that the foundational system we started with was not like such an $S'$? We cannot know, without assumptions beyond $S$. Simply put, **it is possible that a theorem prover proves that it proves nonsense including $0=1$, even though it does not**!

To summarize:

1. Any reasonable theorem prover cannot prove that itself produces only consistent outputs.
2. One cannot determine without assumptions beyond those coded into a theorem prover that it does not produce false theorems.

I also wish to say a bit about verification according to specifications. This is necessarily **conditional**; all you can prove is that, **if** the theorem prover is run on a machine that satisfies certain properties, **then** the theorem prover produces outputs that satisfy certain specifications. Can you know for sure whether the machine on which you run the theorem prover **actually** satisfies those properties? No. At some point, you are just going to have to trust or believe something that you cannot prove.
> 3 votes

# Answer
This depends on the underlying axioms of the theorem prover. If a prover is based on primitive set theory, it will have few axioms. It can also have optional axioms such as the axiom of choice, which may or may not be useful for higher level proofs. From these primitive axioms and theorems such as Peano arithmetic, we can build up the familiar algebra of ordinary and complex and floating point arithmetic. A further feature is the use of abtract types to represent theorems. If you have not proved a theorem, you cannot make use of it because that type will not exist yet. A further level of complexity is to write the core of the prover inside the prover itself. This may be used to give confidence that the prover written in itself satisfies the same proof traces as the prover running on a general purpose computer.
> 0 votes

---
Tags: formal-methods, software-verification, automated-theorem-proving
---


# Question
Title: Analysing worst-case time complexity of quick-sort in different cases
I am trying to understand worst case time complexity of *quick-sort* for various pivots. Here is what I came across:

1. When array is already sorted in either ascending order or descending order and we select either leftmost or rightmost element as pivot, then it results in worst case $O(n^2)$ time complexity.
2. When array is not already sorted and we select random element as pivot, then it gives worst case "expected" time complexity as $O(n \log n)$. But worst case time complexity is still $O(n^2)$. \[1\]
3. When we select median of \[2\] first, last and middle element as pivot, then it results in worst case time complexity of $O(n \log n)$ \[1\]

I have following doubts

**D1.** Link \[2\] says, if all elements in array are same then both random pivot and median pivot will lead to $O(n^2)$ time complexity. However link \[1\] says median pivot yields $O(n \log n)$ worst case time complexity. What is correct?

**D2.** How median of first, last and middle element can be median of all elements?

**D3.** What we do when random pivot is $i$th element? Do we always have to swap it with either leftmost or rightmost element before partitioning? Or is there any algorithm which does not require such swap?

# Answer
> 0 votes
There is no one QuickSort. There is one original, which we only care about for historical reasons, and many variations, all different.

In the case of n identical items, different implementations will run in O(n log n) or O (n^2). Since this *is* a practical case, the latter kind of algorithm should be avoided.

Your point (3) is wrong. Worst case for n different items is always O(n^2). In case (2) it doesn’t matter if the array is already sorted.

Taking a random element as the median makes sure that an opponent cannot create an array that takes n^2 steps to sort. Median of three random elements will usually partition the array better and therefore will be faster.

But apart from the case of taking the first or last element with a sorted array, and problems with all or many identical items, bad behaviour won’t happen unless you have an attacker that can create the data to be sorted, or with extraordinarily bad luck.

# Answer
> 1 votes
The usual rule here is only one question per post.

Link \[2\] doesn't say that random pivot and median pivot lead to $O(n^2)$ time complexity.

The median of first, middle, and last element is not the median of the whole array. Writing "median pivot" is probably a bad idea, unless you have carefully specified what that's a median of.

Link \[1\] says that taking the median *of all elements* leads to $O(n \log n)$ time complexity. That's different than taking the median of first, middle, and last. Also, it's rare for practical implementations to take the median of all elements, as that link already states.

---
Tags: algorithms, runtime-analysis, sorting, quicksort
---