# Question
Title: How AlphaDev improved sorting algorithms?
On the 7th of June 2023, Google DeepMind released an article about AlphaDev. AlphaDev is an evolution of AlphaZero (used to beat world champions at Go, Chess and Shogi), and it can produce assembly code for a task if said task is represented as a game. All of this information can be found here.

Now, they tested AlphaDev on sorting algorithms and it discovered new algorithms as well as improved already existing ones. Here are the improvements made compared to the original code in assembly pseudo-code. The two algorithms improved are for sorting sequences of 3 and 4.

Can someone explain (or link to resources explaining) what concretely is different and why the specific modification in assembly code in the figure is an improvement to the sorting algorithm?

# Answer
> 6 votes
The improvement in the figure consists of the removal of one instruction. In a branch-less assembly program, this usually leads to a performance improvement. How much of a practical improvement it would be depends on how the subroutine is used.

Of course, the program should still be correct after this modification. The figure alone doesn't make this very clear, but this fragment describes only the final part of the implementation of a sorting network for 3 elements (the part inside the red ellipse). The first part guarantees that $B\leq C$, as noted in the paper. So, in the second part, instead of computing $\min(\min(A,C),B) = \min(A,B,C)$ for $P$ as in the program on the left, the program on the right computes $\min (A,B) = \min(A,B,C)$ (since $B\leq C$). This saves one assignment of $\min(A,C)$ to $P$ (initially, $P=A$), which is the instruction that is removed.

# Answer
> 23 votes
This is not a new sorting algorithm. It's much more interesting than that. AlphaDev appears to have produced a new technique for superoptimisation.

You can think of the superoptimisation problem as trying to take a code fragment, and finding the optimal sequence of instructions that does the same thing. The idea goes back at least to the 1970s; tools like BONSAI would start with a description of machine code expressed as some kind of formal logic, and then use heuristic search to find optimal code sequences.

The term "superoptimisation" was introduced by Henry Massalin in 1987. His was the first system to use exhaustive search, but it was made practical by using a limited subset of machine instructions. For many years, GCC was tuned using superoptimisations discovered by GNU superopt.

Superoptimisation is useful for discovering instruction selection templates and peephole optimisations, but the huge search space makes full optimisation prohibitive. Modern algorithms tend to use stochastic search and goal-directed search to allow for more instructions and longer instruction sequences.

What the AlphaDev appears to have achieved is the start of a new way to get even longer instruction sequences: use deep learning techniques to propose sequences, which would then presumably be automatically verified using a theorem prover like Z3.

This is a very interesting approach. Forget sort algorithms, it could revolutionise the way we construct compiler back-ends. It won't be feasible to run an ANN plus theorem prover on every compilation any time soon, but compiler developers could take larger patterns found in real code and generate special-purpose optimisations for them.

# Answer
> 12 votes
Check out Grady Booch's tweet on the matter:

> there is no "new sorting algorithm" here.

Coming up with assembly level tricks is not the same as finding a new sorting algorithm. That would be my two cents on it.

# Answer
> 6 votes
The article says it. They focused on short sequences of $3$ to $5$ elements using the sorting network technique. They say they achieved $70\\%$ speedup on these cases. But when you look closely to the detailed benchmarks, you see that $70\\%$ is a unique extreme case, and speedups are more commonly like $+30\\%$, $0\\%$ and even down to $-35\\%$.

Even more interesting is the fact that the speedup is of $+1.7\\%$ on sequences of more than $250000$ elements (also best case ?). Last but not least, this "performance" is only available for sorting integers, a pretty ad-hoc case.

IMO, much fuss about nothing as regards the improvement of sorting algorithms, and even assembly optimization in general.

# Answer
> 2 votes
As written in other answers, the contributions of AlphaDev are:

* A branch-less implementation of sort for short vectors (from which most of the speedup over std::sort comes)
* A reduction in the number of instructions to be executed.

In the meantime, others have provided even shorter/faster instruction sequences than AlphaDev, either developed by hand, or using a combination of human work and machine-based tools. See:

https://export.arxiv.org/abs/2307.14503v1

https://www.mimicry.ai/faster-sorting-beyond-deepminds-alphadev

Disclaimer: I was involved with the work on the side of mimicry, so take that with a grain of salt.

The key achievement of AlphaDev is that it achieved its improvement largely without human input (depending on how you consider the needed setup of AlphaDev to solve this particular problem). It remains to be seen how quickly AI alone can beat humans in coming up with great code.

# Answer
> 1 votes
I can’t properly explain what the concrete differences are here or why they work. I’ll leave that to someone who is an expert on sorting algorithms. The comments in the pseudo-code though do explain somewhat tersely what each instruction is doing in high-level terms, so looking through those (and possibly experimenting in some language where you can step through the individual operations and watch the states of the variables) is probably a solid starting point for understanding how they work.

I can, however, rather succinctly explain why they are an improvement in just two words: fewer instructions.

The updated code uses fewer instructions than the original code does, and it does not use any *different* instructions than the original. This means, barring questionable speculative execution or caching behavior, that the new code *will* run faster on identical hardware when compared to the old code. The big thing that makes this a certainty is that the changes *only remove operations* instead of replacing them with different operations. IOW, timings for every other part of the code will remain (theoretically) unchanged, so the algorithm as a whole will run faster.

---
Tags: algorithms, sorting, assembly
---


# Question
Title: Call by value is known as pure function how ?give reason
I think call by value may be pure function or impure function...

And pure function can be written through call by value or call by reference....

So according to the facts (c) should be correct ans...

# Answer
The source does not seem to talk about pure in a functional programming sense. Note it says "pure method" and not "pure function".

Call-by-value is not really a type of method either. It is a way of passing arguments. A better name might be pass-by-value. In some programming languages, like C++, one function can have both pass-by-name and pass-by-value parameters.

This leads me to speculate: Maybe "pure method" in this context is meant to say "a pure-ish/purer way of passing arguments".

I agree with your assessment that both pass-by-value and pass-by-reference can used in pure functions. In Java, passing an immutable `java.lang.String` instance does not violate purity. C++ support const parameters, that prevent the function from modifying the referenced object (within reason).

The question which You are quoting seems sketchy to me. In order to reason that something is *known* as something, You would have to quote or make a survey. And why are answer (c) and (d) identical?
> 0 votes

---
Tags: functional-programming
---


# Question
Title: If $B$ is worse than $A$ on some inputs, how do their worst-case time complexities compare?
You are given two algorithms $A$ and $B$, with worst-case time complexity $f\_A(n)$ and $f\_B(n)$, respectively.

Assume:

(i) For each $n$ there exists an input $x$ of size $n$ such that the number of steps of algorithm $A$ on $x$ is half the number of steps of $B$ on $x$.

(ii) $f\_A(n) = \Omega(h(n))$ for some positive function $h(n)$.

* Is it possible that $f\_B(n) = \Omega(h(n))$
* Is it necessary that $f\_B(n) = \Omega(h(n))$?

Explain your answers.

# Answer
> 0 votes
You are essentially asking the following question:

> Suppose that $f(n) \geq g(n)$ for some $n$. Is there a universal constant $C$ such that $\min\_n f(n) \geq C \min\_n g(n)$?

Hopefully this formulation makes it easier to answer.

# Answer
> 0 votes
Consider A, B where for problems of size n they both take n log n and n steps respectively, except there is always exactly one problem of size n where A takes n/4 and B takes n/2 steps. Answer your question for these A, B.

---
Tags: complexity-theory
---


# Question
Title: Understanding this PDA for non-palindromes over {0,1}
I found this PDA online that accepts all non-palindromes over {0,1}. However, I can't seem to understand how it would accept, say "01011", and not accept "101101". Can someone help me understand how "01011" reaches the final state, and why "101101" doesn't by running through the states with me?

Source: Source

# Answer
> 0 votes
You can use this Automaton Simulator which has a Debug/Trace feature to help you understand the PDA for non-palindromes. Testing the PDA with pen and paper is a bit more challenging. It is best to first understand the logic behind the PDA.

### Algorithm for non-palindromes

> We can use the PDA for the language of all palindromes over {a, b} to create a PDA for this language. To change the PDA accepting all palindromes into one that accepts all non-palindromes, we simply insist in the new machine that there is at least one inconsistency between the first and second half of input string `n`. So the new PDA can essentially be the same, except when we are popping symbols off the stack and matching them with inputs, we must make sure that there is at least one `a` where there should have been a `b` or vice versa.
>
> We first mark the bottom of the stack with a `$`, push the first half of the string (excepting the middle symbol if the string has odd length) onto the stack in $q\_1$, guess non-deterministically where the middle of the string is and switch to state $q\_2$. If $w^R \ne w$, then at some point there will be a mismatch between what is on the stack and in the input; when this is true, the machine can take the transition from $q\_2$ to $q\_3$. Otherwise, any match or mismatch of inputs symbols to symbols on the stack is allowed. Finally, the machine accepts when the input is exhausted **and** the stack is empty.
>
> Reference

PDA simulator for non-palindromes (does not work on mobile)

### Trace table for `01011`

| Input | Stack | State |
| --- | --- | --- |
|  | \[ \] | $q\_0$ |
| $\epsilon$ | \[\\$\] | $q\_1$ |
| 0 | \[\\$, 0\] | $q\_1$ |
| 1 | \[\\$, 0, 1\] | $q\_1$ |
| 0 | \[\\$, 0, 1\] | $q\_2$ |
| 1 | \[\\$, 0\] | $q\_2$ |
| 1 | \[\\$\] | $q\_3$ |
| $\epsilon$ | \[ \] | $q\_4$ |

PDA ends in an accept state $q\_4$.

### Trace table for `101101`

Since PDA is non-deterministic, I will show the trace table for only 1 path. Basically, the first half of the string is pushed to stack in $q\_1$ and then the rest of the inputs causes the PDA to get stuck in $q\_2$.

| Input | Stack | State |
| --- | --- | --- |
|  | \[ \] | $q\_0$ |
| $\epsilon$ | \[\\$\] | $q\_1$ |
| 1 | \[\\$, 1\] | $q\_1$ |
| 0 | \[\\$, 1, 0\] | $q\_1$ |
| 1 | \[\\$, 1, 0, 1\] | $q\_1$ |
| $\epsilon$ | \[\\$, 1, 0, 1\] | $q\_2$ |
| 1 | \[\\$, 1, 0\] | $q\_2$ |
| 0 | \[\\$, 1\] | $q\_2$ |
| 1 | \[\\$\] | $q\_2$ |

PDA ends in a non-accept state $q\_2$.

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


# Question
Title: Time complexity for searching $k-th$ element from starting and ending of a linked list
> What are the time complexities of finding $8th$ element from beginning and $8th$ element from end in a singly linked list? Let $n$ be the number of nodes in linked list, you may assume that $n \> 8$.

The answer is given as $O(1)$ and $O(n)$.
What I learnt till now is that searching operation in linked lists takes linear time since it doesn't have indexes like arrays. Then why does searching the $8th$ element would take constant time?
Further explanation for the answer is as follows :

> Finding 8th element from beginning requires 8 nodes to be traversed which takes constant time. Finding 8th from end requires the complete list to be traversed.

Can someone explain me the concept behind this?

# Answer
If you start from the beginning, it does not matter how big the list is, you have to go through the links a constant number of times no matter what.

n = 100, n = 1000, does not matter, you just have to follow exactly 7 links (independent of n).
> 1 votes

# Answer
The concept has been explained above by Anders for the 8th element from the beginning.

For the 8th element from the end of the list we can use two pointers. Both of them start from the beginning of the list and then we move one of the two by following 7 nodes so that the two pointers have a difference of 8 nodes (including the nodes where they are pointing to).

From that point and on you iterate so that in every step we move each pointer by one position; first we are moving the pointer that is further ahead of the two. When we can not move that pointer further (say because the next pointer is null), then we stop. At that point, the other pointer is pointing to the 8th element of the list counting from the end.

So, total complexity is the number of assignments that we have performed to the pointers by following the \`next' links of the list which is $n + (n-8) = 2n - 8$, which is $O(n)$.

**Side note:** It is assumed that you have a proper linked list; i.e. not a cycle, but I guess you consider this as a given.

**Also note** that if you had a doubly-linked list and you also had a pointer for the last node of the list, then you could start from there and start counting backwards. In that case, finding the 8th element from the end of the list, the complexity would be $O(1)$.
> 1 votes

# Answer
It’s a trick question. Finding the k-th number takes O(k). Finding the 8-th item can be done in a constant number of steps so it takes O(1).

But with this kind of question, you are unlikely to do this just once. As an example, if you want the k-th item for each 1 \<= k \<= n, that only takes O(n) steps. If you want item $k\_i$ for each 1 \<= k \<= n, you sort the $k\_i$ in O(n log n), then find all items in O(K) where K is the largest of the $k\_i$.
> 0 votes

# Answer
lets talk of each case one by one: (**finding from the start**) since question has asked us to find the element from the start and has to reach particulary to a place that is 8 th from the start . actually many of us becomes that we have to traverse the link list a long but actually we dont have to because **since it has asked for the only to traverse the count of uptill the 8 th element so whatever be the length of the list we have to end our searchtill the 8 th element only during traverse so no matter how many nodes are given to us but it wont affect our **time complexities hence it will take constant time o(1)****

(**finding the 8 th element from the end**) this we can find either we use the formula to get the count of nodes in the linklist and n-l+1 from the beginning is the position of the element from the beginning ,since here we have found that it is linearly dependent on the length ****of the list hence it answers with the o(n) or another approach is that we can reverse the list and again traverse to the 8 th element from the beginning in reversing the cost is o(n) and finding the lement from the beginning is o(1)=o(n)*o(1)=o(n)****
> -2 votes

---
Tags: time-complexity, linked-lists
---


title: Specialized SAT solver (?)

text:
# Question
Title: Specialized SAT solver (?)
(Context)

Given two byte arrays of length 16, say $L$ and $H$, one can define a mapping $M$ from the set of all bytes to itself in the following way.

If $0 \le b \lt 256$ is a byte, let $\text{lo}(b)$ denote the lower 4 bits of $b$ and let $\text{hi}(b)$ denote the higher 4 bits of $b$.

Let $L\_i$ (resp. $H\_i$) denote the $i$-th byte of $L$ (resp. $H$). Also let $L\_{i,j}$ (resp. $H\_{i,j}$) denote the $j$-th bit of the $i$-th byte of $L$ (resp. $H$).

$$ M: \\{0,\dots,255\\} \to \\{0,\dots,255\\} \\ b \mapsto L\_{\text{lo}(b)} \land H\_{\text{hi}(b)} $$

Where $\land$ is bitwise logical conjunction.

If we want $M$ to satisfy $M(b\_0) = m\_0, \dots, M(b\_p) = m\_p$ for bytes $b\_k$ and bytes $m\_k$ with $0 \le k \lt p$. Then $L$ and $H$ have to be chosen accordingly (if possible). Note that while the $b\_k$ bytes are known, the $m\_k$ bytes are not. Hence why they persist as propositional variables in the following clauses.

A constraint of the form $M(b\_k) = m\_k$ can be translated to:

$$ L\_{\text{lo}(b\_k)} \land H\_{\text{hi}(b\_k)} = m\_k $$

Or more precisely:

$$ L\_{\text{lo}(b\_k), j} \land H\_{\text{hi}(b\_k), j} = m\_{k,j} $$

Where $m\_{k,j}$ is the $j$-th bit of $m\_k$.

In general, any equation of the form $X \land Y = Z$ where $X, Y, Z$ are bits (or booleans) is equivalent the following boolean clauses in propositional logic:

$$ \bar{X} \lor \bar{Y} \lor Z \\ X \lor \bar{Z} \\ Y \lor \bar{Z} \\ $$

Where $\bar{X}$ is the negation of $X$.

The last remaining piece of the problem is the fact that all $m\_k$ bytes should be distinct. Two bits $X$ and $Y$ are non-equal iff the following clauses hold:

$$ X \lor Y \\ \bar{X} \lor \bar{Y} $$

Hence this problem can be solved using 3-SAT. I have three question with regards to this:

1. Is my problem equivalent to 3-SAT, i.e. can an arbitrary 3-SAT problem be reduced to it? Or is it further simplifiable into something less difficult?
2. If not, do you see an algorithm for solving it efficiently?
3. If yes, would a "simple" CDCL-based solver suffice? (We're dealing with around 3000 clauses and 300 variables).

I have already tried a basic backtracking solver and it failed to terminate even after multiple hours. I'm writing this after having spent multiple weeks thinking about this, and having failed to come up with a specialised algorithm. I could of course just use an off-the-shelf SAT solver but I'm interested in solving this as efficiently as possible.

Thank you in advance.

# Answer
The best solution I know of is to use a SAT solver.

I don't know whether there is a better solution. I don't see any proof that an arbitrary 3SAT problem can be reduced to it. (OK, strictly speaking, this is impossible for the concrete problem you list with arrays of size 16, because that is a finite problem, and 3SAT involves problems of unlimited size; but we can generalize your problem to replace 16 with a parameter, and then there is no such barrier.)

I suspect the most promising approach might to represent this as a SAT instance and apply an off-the-shelf SAT solver, as SAT solvers implement many heuristics that are not likely to be part of your simple back-tracking solver.

I want to correct one detail in the post. I believe it requires a lot more than 300 variables to encode this as a SAT problem. Your post states a condition for two *bits* $X,Y$ to be non-equal, but you actually require that two *bytes* be non-equal, which is a different problem and requires many more clauses, or more variables and more clauses. So I will describe below several ways to represent "distinctness of a bunch of bytes" in SAT.

# Distinctness of two bytes, with no new variables

If $x\_0,\dots,x\_7$ and $y\_0,\dots,y\_7$ are two bytes, you can represent the constraint that they are different via a conjunction of 256 clauses:

$$\bigwedge\_{c\_0,\dots,c\_7} (x\_0 \ne c\_0 \lor \dots \lor x\_7 \ne c\_7 \lor y\_0 \ne c\_0 \lor \dots \lor y\_7 \ne c\_7),$$

where the "and" is taken over all bytes $c\_0,\dots,c\_7$. Notice that $x\_i \ne c\_i$ has either the form $x\_i$ (if $c\_i=0$) or $\neg x\_i$ (if $c\_i=1$), so each of the 256 conjuncts is itself a CNF clause.

Then, you can add constraints that $m\_k,m\_\ell$ are distinct for every pair of indices $k,\ell$ with $k\<\ell$, representing each such constraint as above. This will add about ${p \choose 2} 256$ clauses, and no new variables.

# Distinctness of two bytes, with eight new variables

If $x\_0,\dots,x\_7$ and $y\_0,\dots,y\_7$ are two bytes, you can represent the constraint that they are different via the clause $t\_0 \lor \dots \lor t\_7$ and the constraint $t\_i \implies x\_i \ne y\_i$, where $t\_0,\dots,t\_7$ are fresh new variables (different for each pair of bytes to be compared). This can be represented with 3 clauses and 8 new variables. Doing this for all pairs of bytes requires $3 {p \choose 2}$ additional clauses and $8 {p \choose 2}$ additional variables.

# Distinctness of two bytes, with three new variables

Let $u,v,w$ be three fresh new variables. Then to enforce distinctness, we enforce the constraint that $x\_{4u+2v+w} \ne y\_{4u+2v+w}$, or equivalently,

$$(u\ne a \lor v \ne b \lor w \ne c \lor x\_{4a+2b+c} \lor y\_{4a+2b+c}) \land (u\ne a \lor v \ne b \lor w \ne c \lor \neg x\_{4a+2b+c} \lor \neg y\_{4a+2b+c}).$$

This can be enforced with 16 clauses (two for each possible combination of $a,b,c$) and 3 new variables (for $u,v,w$). Doing this for all pairs of bytes requires $16 {p \choose 2}$ additional clauses and $3 {p \choose 2}$ additional variables.

# Distinctness of $p$ bytes, with a batch sorting network

Build a bitonic sorting network that maps the bytes $0,1,\dots,255$ to 256 outputs, except you replace each byte-comparator with a unit that --- instead of sorting the two byte values -- either swaps or doesn't swap those two values, under the control of a fresh random boolean variable. Treat the first $p$ outputs from this sorting network as the values of $m\_1,\dots,m\_p$.

Then, use the Tseitin transform to convert this circuit to a SAT instance. If you use a bitonic sorting network, the sorting network uses about 4096 byte-comparators, and each byte-comparator requires 32 clauses and 1 additional variable. In all, this requires about 4096 additional variables and $2^{17}$ clauses. This might be a bit better when $p$ is large.

# How to compare these alternatives

It's hard to know which formulation in SAT will work best with existing SAT solvers. A standard heuristic is that solutions that involve fewer variables often are easier to solve, and solutions that involve fewer clauses might be quicker to solve, but these heuristics are imperfect, and it's hard to predict which formulation might be most effective.
> 2 votes

---
Tags: algorithms, complexity-theory, satisfiability, sat-solvers
---


# Question
Title: Why can't we mount multiple filesystem in same mountpoint?
> Systems impose semantics to clarify functionality. For example, a system may disallow a mount over a directory that contains files; or it may make the mounted file system available at tha directory and obscure the directory's existing files until the file system is unmounted, terminating the use of the file system and allowing access to the original files in that directory. As another example, a system may allow the same file system to be mounted repeatedly, at different mount points; or it may only allow one mount per file system.

* Galvin et al, Operating System Concepts

> When a file system is mounted, the contents of the directory at that mount point are unavailable to users unitl the file system is unmounted.

* Deitel et al, Operating System

So, basically this means we're trying to say at one mount point we can have only one file system. i.e a directory can have only one filesystem.

But why?

In a tree structured directory, I see no reason to allow a mount point to have multiple filesystems.

When I asked this to my professor, he asked me this question.

> So to which file system would you store a resource that goes to a directory with multiple mounts?

I didn't understand what he meant. The below figure is how I visualize my system would look like.

PS can we call an umounted file system as "device"?

Source: https://warwick.ac.uk/fac/sci/physics/research/condensedmatt/imr\_cdt/students/david\_goodwin/teaching/operating\_systems/l5\_filemgt2013.pdf

# Answer
Perhaps your confusion comes from the fact that you're imagining the filesystem being mounted as a subdirectory of the mount point. That's not the case.

If you mount what you call `file_system_1` at, say, `/something/mount_point` then the path that refers to root of the file system will be `/something/mount_point` and not `/something/mount_point/file_system1` as you seem to imply. (How would the OS even know the name `file_system_1`?).

As you see it doesn't make sense to have two file systems mounted on the same mount point (which one are you expecting to see when you access `/something/mount_point`?\*). Of course nothing prevents you from mounting one file system on the mount point `/something/mount_point/file_system_1` and the other on the mount point `/something/mount_point/file_system_2`.

\*If you were imagining the directory structures of both file-systems to be combined into one, look at overlay file systems. Notice that handling path collisions and writes becomes much more tricky in this case.
> 1 votes

# Answer
SunOS 4.1 supported something like what I think you're getting at, called the Translucent File System. The idea is you could stack multiple filesystems in the same location.

When searching for a file, searching was performed from the top of the stack downwards, until the first file with that name is found.

However, mutations of the filesystem could only be done on the topmost filesystem. For example, writing to a file created a new copy on the topmost filesystem, and removing a file created a "whiteout" in the top-level filesystem which effectively hid that file in any filesystems that were underneath.

TFS was removed in SunOS 5.7.

Linux, FreeBSD, and NetBSD have varying support for union-mount filesystems that are based on the broad same ideas: UnionFS, aufs, and OverlayFS.

The idea has turned out to be useful for lots of applications in the modern era, such as:

* Containerisation, e.g. Docker. The same mechanism supports snapshots and rollback during container building, as well as stacking a live running container over a read-only image.
* Embedded devices which overlay read-write storage over EPROM.
* Flash memory devices with limited write cycles.
> 3 votes

---
Tags: operating-systems, filesystems
---


# Question
Title: Parallel reductions with complex objects
Typically (from what I can tell) reduction operations produce a "number". This makes them easy to deal with since there isn't really any memory overhead.

However, I have something that I'm working on where I want to combine instances of a nontrivial data structure. That is, if `x` and `y` are instances of some class `C`, I have an operation that combines `x` and `y` into another object `z` of class `C`. Let's write `z=a+b` where `+` is my operation from pairs of `C` to `C` (mathematically, `+:C x C -> C`).

I already have an efficient implementation of `+`, but I'm struggling to get my memory allocations under control when doing a (parallel) reduction on a list of instances of `C`.

Are there some standard approaches or research related to this problem? In essence I want to reuse memory without reallocating as much as possible.

# Answer
> 2 votes
If you use MPI to implement your parallel program, you can define your own reduction operator (besides using standard, predefined operators). This allows implementation of complex, user's defined reduction.

In particular, your object instances A and B are respectively the first and the second parameters of the function required to implement your reduction, and the result is returned through the second parameter. So, the second parameter is used for both input and output, and you can avoid allocating a temporary object that will contain the result to be returned, since you can modify on the fly the second object.

You may still need a few temporary variables to compute the intermediate partial results to be stored in the fields of your object, but the memory required should not be that much.

Anyway, it is worth recalling here that you can not use a C++ object for this: you will neeed to build a custom derived datatype to represent your C++ object (MPI provides many different APIs for this purpose), and you will need to serialize your objects into custom derived data types for the reduction and to deserialize the custom derived data type which is the result of the reduction back to your C++ object.

---
Tags: parallel-computing
---


# Question
Title: Finding min s-t cut of network with flow on the nodes
Given a network with flow on the nodes. How can we find min s-t cut in a network with flow on the nodes?

We know how to find min s-t cut whenever there’s a network with flow on the edges (Ford Fulkerson, Edmonds Karp)

# Answer
> 2 votes
Given a directed graph, you can construct a new graph $G'$ where you replace each vertex $v$ with two vertices $v\_{\text{in}}$ and $v\_{\text{out}}$. Then you add the edge $v\_{\text{in}}v\_{\text{out}}$ with capacity equal $v$'s capacity in $G$. Then for each edge $vu$ in $G$, you add the edge $u\_{\text{out}}v\_{\text{in}}$ with capacity $+\infty$.

Let $C$ be any set of vertices in $G$ and $C'$ the corresponding *edges* in $G'$. Then the cost of $C$ and $C'$ is the same, and $C$ is an $s$-$t$-separator if and only if $C'$ is as $s$-$t$-cut.

---
Tags: algorithms, graphs, weighted-graphs, network-flow
---


# Question
Title: Determine if a vertex is a part of a cycle in O(m+n) complexity
I am trying to apply BFS to the following problem, but I'm not sure how to do it

> *Input*: directed graph $G$ defined by the array of adjacency lists with n vertices and m edges, and a vertex $v$ in $G$
>
> *Output*: $true$, if $v$ is a part of a cycle, $false$ otherwise

Can someone explain in pseudocode or in words how to do this?

# Answer
Simply apply Strongly connected components algorithm , Kosaraju's algorithm has complexity $O(m+n)$. Now, read through the SCC components and check if $v$ is part of a component with size $\geq$ 2. The second step is $O(n)$. Actually, the second step can be interleaved with the first step to get your required complexity result.

A simpler algorithm may be just to to use DFS on the graph. Have a look at Cormen's Introduction to algorithms, chapter 22. Your exact problem is solved there using DFS.
> 1 votes

# Answer
Algorithm:

1. Recursively keep removing degree 1 nodes from the graph.
2. Now, there are only either degree 0 nodes, or nodes with degree \>= 2.
3. Now, check the degree of *v*. If its degree is 0, then *false*, otherwise *true*.
> 0 votes

---
Tags: graphs, graph-traversal
---


# Question
Title: How to evaluate an arbitrary mathematical expression
For Instance, if I allowed the user to pass in expressions like "35 + 2 * 5" as strings, how would I go about writing such a program? Also, what topics does this question fall under?

# Answer
Well, this is a common problem, that is used similarly for making a programming language. I do not know exactly what branch is belongs to, my guess would be something similar to computational linguistics, but this is of course, a simpler case I believe.

Anyways, I would probably go ahead and make a token system and a parser. So you make a program, maybe something along the lines of a parse tree. All leafs, except for the bottom ones are operators like +, -, \*, /, and only the bottom leafs of the tree is the numbers. This gives a systematic way to figure out how to want to evaluate the expression, by using some conversion etc.

Its not entirely simple, I saw something similar being done when a guy on youtube tried to make a programming language using C#. I can give you a link if you are interested?
> 2 votes

---
Tags: programming-languages, semantics
---


# Question
Title: swapping between sorting algorithms for small input size left over
Is it suggested to swap between sorting algorithms? Merge sort certainly performs better on large input size however Insertion sort performs better on small input size

> Analysis based on there graph comparison of running time of Insertion sort and merge sort

How often people swap the algorithms they are using? For example sorting problem of size 100K with merge sort and then switching to insertion sort when problem size reached to 500 input size?

Is is advisable to follow such techniques? For small input size the constants(c) does matter and insertion sort having small constant size than merge sort will certainly perform better. I guess

# Answer
> 4 votes
People don't usually program their own sorting routines, and I would advise against it, unless you're implementing a non-comparison-based sort such as counting sort. Library sorting routines are optimized beyond what the casual programmer can achieve.

If you're interested in the best practices of the field, you'll have to look at library sorting routines. For example, python uses Timsort, which switches to insertion sort for small arrays. The GNU implementation of Quicksort also switches to insertion sort for small arrays. So it seems switching to insertion sort for small arrays is indeed advisable.

# Answer
> -1 votes
Insertion sort is quadratic. You would never, ever consider doing insertion sort for 500 input items. Not even 50.

You can only ever discuss this matter with an actual implementation on an actual machine. So Big-O is totally irrelevant. You don't get to the stage where it is relevant. The average time to sort n items using insertion sort on a particular machine with a particular implementation with particular data, and a given cost of moving data, and a given cost of comparing data, is an interesting function. It can have big jumps, for example 4 items might take a lot less time than five and six takes the same time again. So what you do is this: For k = 1, 2, 3 etc. you implement your "switching sort": If you have more than k items then you split the data into say 3 streams that you first sort then merge, and if you have k or fewer items than you sort them with insertion sort. And then you measure how long it takes to sort 100,000 items are whatever is an interesting number, with different values of k. And you measure this, check how the time needed changes with k, and pick the best k. Be careful: If you sort 100,000 items, with merge sort splitting the data into 3, you will only ever decide for n = 33,333, n = 11,111, n = 3,703, n = 1,234, n = 411, n = 137, n = 45, n = 15, n = 5, n = 1 or 2. So be careful.

And check with different data. Don't compare integers, but real world data. For example, if you compare names, then comparing "Smith, James" and "Abraham, John" makes the decision fast, after one character. Comparing "Smith-Johnson, Abraham" and "Smith-Johnson, Abigail" takes much longer. Now compare merge sort and quick sort. Will they pass different data to your insertion sort? Absolutely. Merge sort passes consecutive data from the unsorted array. Quicksort passes data that is almost in the correct place. So "insertion sort for merge sort" can afford to do some unnecessary comparisons that "insertion sort for quick sort" can't afford.

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


# Question
Title: Find max total revenue in a directed graph
***Problem:***

Imagine you are an agent with a knapsack, who travels a known route of cities. All cities are different: $C\_1 \rightarrow C\_2 \rightarrow \dots \rightarrow C\_n$. Each city offers you to buy fixed commodity or to sell it (but only to buy or to sell, never both). Prices are known and available; available volume is also known for each city: $Vol\_{C\_i}, Price\_{C\_i}$. So, each city has three values: volume, price and offer\_side $\in \[ buy, sell \]$.

***Question:***

1. What is an algorithm to decide, in which cities to buy this commodity and in which to sell and with what volume to maximize total revenue? The constraint is that you cannot carry more than 100 of volume in a knapsack at each point of time.

***Methods:***

1. I was thinking about knapsack problem, but it is not the case, because I can choose, which volume to put in a knapsack and I can "throw things away" from a knapsack by selling the commodity.
2. I was also thinking about flow algorithms, but they usually maximize the flow with given edge capacity, but flow algorithms do not have constraints on "total flow" at each time. Moreover, flow algorithms do not have a revenue, but only the max flow...

# Answer
> 6 votes
Your problem can be solved by reducing it to a min-cost max-flow problem where a unit of flow represents one unit of commodity. A negative cost represents a profit.

Create a directed graph containing $n+3$ vertices in total: there are three vertices named $s$, $t$ and $t'$, and the remaining $n$ vertices are $C\_1, \dots, C\_n$ (each representing a city).

The edges are as follows:

* For ever $i=1, \dots, n-1$ add an edge from $C\_i$ to $C\_{i+1}$. This edge has capacity $100$ and cost $0$.
* Add an edge $(s, C\_i)$ for ever city $C\_i$ in which you can buy the commodity. The capacity of this edge is $\text{Vol}\_{C\_i}$ and the cost is $\text{Price}\_{C\_i}$.
* Add an edge $(C\_i,t)$ for ever city $C\_i$ in which you can sell the commodity. The capacity of this edge is $\text{Vol}\_{C\_i}$ and the cost is $-\text{Price}\_{C\_i}$.

If we were to look for a min-cost max-flow from $s$ to $t$ in the above graph, we would find the solution that maximizes the profit **among the ones that trade the maximum amount of the commodity**. This is clearly not what we want, as it could force us to trade the commodity at a loss. We can avoid this problem with a technicality:

* Let $F$ be an upper bound on the amount of flow from $s$ to $t$ (for example the sum of all $\text{Vol}\_{C\_i}$). Add an edge $(t, t')$ with capacity $F$ and cost $0$, and an edge $(s,t)$ with capacity $F$ and cost $0$.

Now you can always attain a min-cost max-flow from $s$ to $t'$ by "padding" the most profitable (but not necessarily maximum) flow from $s$ to $t$ in the previous graph. Indeed, if the amount of such flow is $\phi$, you can route $F-\phi$ additional "free" units of flow along the newly added edge $(s,t)$. The overall flow of $\phi + (F-\phi) = F$ reaching $t$ can then go from $t$ to $t'$ via the edge $(t, t')$.

# Answer
> 2 votes
The following answer assumes that volumes are integers.

You can solve the problem in time $O(n)$ using dynamic programming. For $i=0, \dots, n$ and $v=0, \dots, 100$, let $r\[i,v\]$ be the maximum revenue that you can obtain when you only visit the first $i$ cities and you need to end your journey with a volume of exactly $v$ in your knapsack. If that's impossible, let $r\[i,v\] = -\infty$.

You have the following base cases for $i=0$: $$ r\[0,0\]=0 \quad \text{and} \quad r\[0,v\] = -\infty \\; \forall v \neq 0. $$

When $i=1,\dots, n$ and you can buy the commodity in city $i$ you have: $$ r\[i,v\] = \max\_{ x = 0,1,\dots, \min(v, \text{Vol}\_{C\_{i}})} \left( r\[i-1, v-x\] - x \cdot \text{Price}\_{C\_i} \right). $$

When $i=1,\dots, n$ and you can sell the commodity in city $i$ you have: $$ r\[i,v\] = \max\_{ x = 0,1,\dots, \min(100-v, \text{Vol}\_{C\_{i}})} \left( r\[i-1, v+x\] + x \cdot \text{Price}\_{C\_i} \right). $$

Notice that each of the above formulas for $r\[i,\cdot\]$ can be evaluated in constant time once the values of $r\[i, \cdot\]$ are known ($x$ can only take constantly many values), and that there are only $O(n)$ subproblems ($v$ can only take constantly many values).

The maximum revenue for the instance will be in $r\[n, 0\]$ (since it is never convenient to have leftover commodity). The actual amounts to buy/sell can be found by retracing the optimal choices backwards.

---
Tags: graphs, linear-programming, network-flow, knapsack-problems
---


# Question
Title: What is the difference between variables and pointers?
Whist reading an article outlining differences in OO and Functional programming I came across function pointers. It has been a while since I completed my Computer Science degree (2003) and so I looked up pointers to refresh my memory.

Pointers are variables that contain a reference to a memory address. They can be considered to point to the data that is contained in that memory address if such data exists. Or, as in the case in the article, they might indicate the entry point to a section of code and can be used to call that code.

Why is this different from a variable? Variables are symbolic names for memory addresses and compilers will replace the name with the actual address. This means that variables contain references to memory locations and can be considered to point to the data at that address if such data exists.

If the difference is in behaviour (maybe a pointer cannot be reassigned at runtime, or can only be assigned a symbolic variable name, not any other value) doesn't that mean it is just a variable of a particular type, the pointer type? In just the same way a variable declared to be of type integer is restricted by the compile in what it can be used for.

What am I missing here?

# Answer
> 8 votes
Your question is interesting in several ways, as it requires careful distinctions for several issues. But your vision seems to me to be essentially correct. I did not read your reference before writing most of this answer to avoid biasing my answer.

First, your statement `Variables are symbolic names for memory
addresses`, it is almost correct, but confuses the concept and its usual implementation. A variable is actually just a container that can contain a value that can be changed. Usually, this container is implemented on a computer as a bock of memory space, characterized by and address *and a size* since variables may contain object that require representations with more or less information.

But I will consider mostly a more abstract point of view of the semantics of languages, independently of implementation techniques.

So variables are just containers from an abstract point of view. Such a container need not have a name. However, languages often have variables that are named by associating to it an identifier, so that uses of the variable can be expressed by the identifier. A variable can actually have several identifiers through various aliasing mechanism. A variable can also be a subpart of a larger variable: an example is a cell of an array variable, which can be named by specifying the array variable and the index of the cell, but could as well be also associated with identifiers through aliasing.

I am deliberately using the word *container* that is somewhat neutral, to avoid invoking other words that may be semantically loaded technically. It is actually close to the concept of reference described in wilipedia, which is often confused with a memory address. The word pointer itself is often understood as a memory address, but I do not think that is meaningful when considering most high-level languages, and probably inappropriate in the discussion paper you refer to (though addresses can be used), as it is inappropriately referring to a specific implementation. However, it is appropriate for a language like C, which is supposed to be much closer to implementation concepts and the machine architecture.

Actually, if you look at variables or values at the implementation level, there may be several complex systems of indirection, of "machine level pointers", but that are (and should be) invisible to the user, so that the abstract point of view I develop can be valid. For most programming languages, the user should not have to worry, or even know, about implementation, as implementation can vary a lot for a given language. This may not be true for some languages, such as C, that are intentionally close to the machine architecture, as an advanced substitute for assembly languages that are in almost direct relation to explicit binary coding, but far too low level for convenient use in most situations.

What the user of a language should know, and sometimes it should be even less than that, is what are values and associated operations, where they can be contained, how they can be associated to names, how the naming system works, how can new kinds of values be defined, etc.

So another important concept is identifiers and naming. Naming an entity (a value) can be done by associating an identifier with a value (usually in a declaration). But a value can also be obtained by applying operations to other named values. Names can be reused, and there are rules (scoping rules) to determine what is associated to a given identifier, according to context of use. There are also special names, called litterals, to name the values of some domains, such as integers (e.g. $612$) or boolean (e.g. *true*).

The association of an unchanging value with an identifier is usually called a constant. Litterals are constants in that sense.

"Value containers" can also be considered as values, and their association with an identifier is a variable in the usual "naive" sense that you have been using. So you might say that a variable is a "container constant".

Now you might wonder what is the difference between associating an identifier with a value (constant declaration) or assigning a value to a variable, i.e. storing the value in the container defined as a container constant. Essentially, declaration may be seen as an operation that defines a notation, that associate an identifier which is a syntactic entity to some value which is a semantic entity. Assignment is a purely semantics operation that modifies a state, i.e. modifies the value of a container. In some sense, declaration is a meta concept with no semantic effect, other than providing a naming (i.e. syntactic) mechanism for semantics entities.

Actually, assignments are semantic operations that occur dynamically as the program is executed, while declarations have a more syntactic nature and are usually to be interpreted in the text of the program, independently of execution. This is why static scoping (i.e. textual scoping) is usually the natural way to understand the meaning of identifiers.

After all this, I can say that a pointer value is just another name for a container,and a pointer variable is a container variable, i.e. a container (constant) that can contain another container (with possible limitations on the containing game imposed by some type system).

Regarding code, you state `[pointers] might indicate the entry point
to a section of code and can be used to call that code`. Actually this is not quite true. A section of code is often meaningless alone (from high level or implementation point of view). From a high-level point of view, code usually contains identifiers, and you have to interpret these identifiers in the static context where they were declared. But there is actually a possible duplication of the same static context, due essentially to recursion which is a dynamic (run-time) phenomenon, and the code can only be executed in an appropriate dynamic instance of the static context. This is a bit complex, but the consequence is that the proper concept is that of a closure that associate a piece of code and an environment where the identifiers are to be interpreted. The closure is the proper semantic concept, i.e. is a properly definable semantic value. Then you can have closure constants, closure variables, and pointers to closures, which are containers that can contain another container containing a closure.

A function is a closure, usually with some parameters to define or initialise some of its entities (constants and variables).

I am skipping many variations on the uses of these mechanisms.

Closures can be used to define OO structures in imperative or functional languages. Actually, early work on OO style (probably before the name) was done that way.

The paper you reference, which I skimmed quickly, seems to be an interesting one, written by a competent person, but possibly not an easy reading if you do not have significant experience with a variety of languages and their underlying computational models.

But remember: many things are in the eyes of the beholder, as long as he preserves a consistent view. Points of view may differ.

Does this answer your question?

PS: This is a long answer. If you consider some part of it inadequate, please be explicit about which it is. Thank you.

# Answer
> 2 votes
The difference is by definition and application, a pointer is a specialized variable to hold a memory address of another variable; in OO terms a pointer would perhaps be considered to inherit its behavior from a general class called variable.

# Answer
> -1 votes
variables take one or more location in memory, depend on variables type, pointers contain address just for one memory location only.

---
Tags: terminology, programming-languages
---


# Question
Title: In a directed graph, efficiently determine node reached after traveling k edges from the starting node
I am trying to solve a problem where I am given a directed graph with $n$ nodes where, from any given node, I can reach one and exactly one node. Nodes contain integers from $1$ to $n$. Starting at node $1$, the problem consists in writing an algorithm which determines on which node we end up after moving along $k$ edges.

Here is an example graph:

If $k=2$, then the final node will be $3$. If $k=9$, then we will reach node $5$ instead.

In order to solve this problem, I chose to represent the graph as a one-dimensional array, where the index of the array represents the current node and the value at said index the node which we can reach. Since in Python, arrays are 0-indexed, the first value is 0.

The following array represents the graph above:

```
# indexes:  0  1  2  3  4  5
my_graph = [0, 2, 3, 5, 1, 3]

```

From here on, I utilized a naive approach to determine the final node:

```
current_node = 1

while k > 0:
  k -= 1
  current_node = my_graph[current_node]

print(current_node)

```

This code works fine and outputs the correct answer, however it is obviously too slow for huge values of $k$ (upwards of $10^{15}$). I am guessing that dynamic programming could be of help in order to produce faster results, but I am having a hard time determining the "smallest subproblem" here...

I would appreciate any help or hints towards an efficient algorithm which solves the described problem.

# Answer
If you keep moving from node to node like that, you will end up visiting a node that was visited before. That's the point when you've entered a cycle, and the task becomes trivial.

Since the question was tagged with `dynamic-programming`, you may be interested in this alternative approach. To simplify things, let's assume that $k$ is a power of $2$, which means that $k = 2^p$ for some $p \ge 0$. To reach the $2^p$-th node from the initial node $U$, you can first move by $2^{p-1}$ edges to reach node $V$, and then from $V$, you can go along another $2^{p-1}$ edges to reach the destination.

Here are the subproblems you need: for each node $u$, denote $dp(u, p)$ as the node you reach after moving along $2^p$ edges. You may want to derive the formula for this yourself. To tackle the problem for the general case of any $k$, you can partition $k$ into powers of $2$, and move along each power of $2$ one by one.

For instance, if $k = 13$, then

$$k = 13 = 2^3 + 2^2 + 2^0$$

The number of powers of $2$ in the partition of $k$ is at most $\lfloor \log\_2 k \rfloor$, hence the complexity is $O(\log k)$ (excluding the cost of calculating the dp table).
> 1 votes

---
Tags: algorithms, graphs, optimization, dynamic-programming
---


# Question
Title: Does there exist an algorithm / software that finds optimal graph partition while enforcing contiguity on a subgraph?
I am interested in the traditional graph partitioning problem, which roughly speaking seeks to obtain a partition of a graph into a number of components, in which each component has about the same size (either in terms of number of nodes or sum total of node weight), and the sum total weight of edges that cross between components is minimized. Problems of this nature are generally NP-hard, but I am aware of the software METIS which can obtain good quality partitions very quickly. METIS also has the feature that it can enforce the constraint that each component in the resulting partition be contiguous ("connected").

What I am looking for is an algorithm or some sort of software package that is similar to METIS, but can also enforce the constraint *that each partition is still contiguous when only a certain subset of edges from the original graph are considered*.

Here is an example:

The graph on the left is the original graph. All nodes have the same weight. If I want to partition the graph into two components, while enforcing contiguity constraints, I would choose the highlighted groups. This partition has a "cost" of 5. But what I actually want to do is partition the graph on the left, while enforcing the constraint that each component be contiguous if it only had the edges in the graph in the middle. This obviously results in a different partition (which is actually the only feasible partition in this small example). This partition has a cost of 9 (note I am still counting the edges from the original graph), but it satisfies the constraints.

I would be interested in algorithms that solve this problem directly, or that transform the problem into something that can be solved by currently-existing software, e.g. METIS.

It is not sufficient to just perform graph partitioning on the middle graph, because that ignores the potential cost of the additional edges that may or may not cross between different components in the resulting partition.

(For those wondering the use case, I am interested in redistricting. I have a graph that quantifies the relationships between different precincts, but I need to enforce a contiguity constraint on the graph that represents which precincts actually border each other, which is much smaller than my input graph.)

# Answer
> 0 votes
If your graphs aren't too large, you could try to solve this using an integer linear programming (ILP) solver.

Introduce 0-or-1 variables $x\_{i,v}$, to indicate that vertex $v$ is part of the $i$th component. You can enforce that each component is connected ("contiguous") using the techniques in Boolean constraints for a connected component of a graph. You can enforce that the components partition the graph with a linear equality $\sum\_i x\_{i,v}=1$ for all $v$. You can enforce that the components are all about the same size by introducing a new variable $w$ and constraining $w-10 \le \sum\_v x\_{i,v} \le w+10$ for each $i$ (you can change 10 to whatever constant you find acceptable; this requires them to be all about the same, +/- 10). You want to minimize the sum of the edges that cross between different components. This can be expressed by introducing new 0-or-1 variables $y\_{u,v}$, one for each edge $(u,v)$ in the graph, and requiring $x\_{u,i} + x\_{v,j} - 1 \le y\_{u,v}$ for every $i,j$ with $i\ne j$. Then, minimize the sum $\sum \text{wt}(u,v) y\_{u,v}$. This is a linear objective function, with a set of linear inequalities as constraints, so you can solve this with an off-the-shelf ILP solver.

Whether this will work well or not will likely depend on the size of the graph. You've have to try it to see how well it works in practice.

# Answer
> 0 votes
I do not have a good answer for you, as this is an active research area and we simply don't know any good algorithms, or indeed if there exists any, but here are some pointers.

1. The problem is NP-complete, even with 2 sets where one set has size 2 (Van 't Hof et al., 2009)
2. The problem is NP-complete, even on planar graphs (Grey et al., 2012)
3. The problem for 2 partitions on planar graphs is fixed-parameter time tractable parameterized by the sum of the sizes of the partitions, which in your case would be $n$, so that's not really great (Bentert et al., 2023)
4. You can try to use idea's from Karger's algorithm, similarly to what was done for multiway cut. (Calinescu et al., 1999)

A small observation, for planar graphs, there's a duality between a *minimal cut* in $G$ and a *simply cycle* in $G^\*$, the dual graph of $G$. A 3-way cut corresponds to two simple cycles in $G^\*$, unfortunately, they do not necessarily behave so nicely; either $C\_1$ and $C\_2$ are disjoint, $C\_1$ is contained inside $C\_2$, or $C\_1$ and $C\_2$ share a path.

Keywords here are: *cut-uncut*, $k$-way cut, multiway cut.

---
Tags: graphs, optimization, partitions, minimum-cuts
---


# Question
Title: Number of maximal induced trees in a connected planar graph
An induced subgraph $G’$ of a graph $G$ is a subset of its vertices along with all the edges that are present in $G$ among those vertices. For $G’$ to be a tree, all vertices of a cycle in $G$ cannot be in $G’$. The tree composed of bold edges in the illustration given below shows an induced tree $T$. Vertex $u$ cannot be included in $T$ because u brings with itself edges $(u, v)$ and $(u, w)$ which completes a cycle $u-v-w-u$ and $T$ no longer remains a tree. $T$ is also a maximal induced tree because no more vertices can be included in $T$ without violating it being a tree.

The question is, what is a tight upper bound on the number of maximal induced trees in a connected triangulated planar graph.

# Answer
Consider the following planar triangulated graph $G$. There are $n+2$ vertices: $\\{x,y,u\_1,\dotsc,u\_n,v\_1,\dotsc,v\_n\\}$. The edge set is $\\{(x,y),(x,u\_1),\dotsc,(x,u\_n),(y,v\_1),\dotsc,(y,v\_n),(u\_1,v\_1),\dotsc,(u\_n,v\_n),(u\_1,u\_2),\dotsc,(u\_{n-1},u\_n),(v\_1,v\_2),\dotsc,(v\_{n-1},v\_n), (y,u\_1),(v\_1,u\_2),\dotsc,(v\_{n-1},u\_n)\\}$.

Suppose your algorithm initially picks $x$ and $y$ in $S$. Thereafter, suppose the algorithm picks the even numbered vertices $u\_{2i}$ and $v\_{2i}$ for $i \in \\{1,\dotsc,\lfloor n/2 \rfloor\\}$. Then, the algorithm can construct $2^{\lfloor n/2 \rfloor}$ possible induced trees depending on whether $u\_{2i}$ or $v\_{2i}$ is included in the induced tree for each $i \in \\{1,\dotsc,\lfloor n/2 \rfloor\\}$. Therefore, there are $2^{\Omega(|V|)}$ possible induced trees for this graph.

Note that this is asymptotically tight bound in the exponent since in a planar graph, the number of edges are linearly bounded by the number of vertices, i.e., $|E| = O(|V|)$ (see here for the properties of a planar graph). Therefore, the number of subgraphs of any planar graph are at most $2^{O(|V|)}$.
> 2 votes

---
Tags: algorithms, graphs, combinatorics, discrete-mathematics, planar-graphs
---


title: What does the data field store?

text:
# Question
Title: What does the data field store?
This semester we have a class related to Operating Systems.The class itself is not obligatory but the class is done at the same time with a core class and I will simply not waste a year for 1 class so I have decided to access the resources of the Operating Systems class and study on my own.

A process is any program loaded into the main memory currently being executed or which awaits execution.Any process is made of :the code where the instructions are stored , the call stack and the data field.However what exactly is the data field.After a brief search the data field stores any process related data(input or output) so I guess it stores any parameters or temporary variables used by the process?

# Answer
"Data field" is not the usual term. The usual term that we use is "segment".

There are essentially five kinds of "data" that a process can use:

* *Stack*. You know what the stack is: it's memory that is implicitly or explicitly allocated by the program as calls occur. This can be a little more complex in its detail than some textbooks would have you believe, because of multithreading, but let's not get into that.
* *Heap*. This is memory that is explicitly allocated by the program using system calls. You probably know what heap is.
* *Read-only data*. This is data (i.e. not executable code) that is loaded from the executable file, and cannot be modified by the program. Examples include static strings, run-time type information, and virtual function dispatch tables.
* *Read-write data*. This is data that is loaded from the executable file, but *can* be modified by the program. This is, typically, initialised global variables.
* *BSS*. This is an archaic term, but it's stuck. It means data that can be modified by the program, but doesn't need to be stored in the executable file because it is initialised to zero bytes. This is, typically, *uninitialised* global variables.

So, in summary:

* Read-only data is loaded from the executable file, and is typically mapped by a modern operating system as being read-only and non-executable. Different instances of the same program can share these pages.
* Read-write data is loaded from the executable file, and is typically mapped by a modern operating system as being read-write and non-executable. Different instances of the same program might share these pages, if they are copy-on-write.
* BSS data is *not* loaded from the executable file, and is typically mapped by a modern operating system as zero-fill pages.
> 1 votes

---
Tags: process-scheduling, os-kernel
---


title: Valid Lambda Expressions

text:
# Question
Title: Valid Lambda Expressions
I have two questions about the validity of lambda expressions.

First, is a variable on it's own a valid lambda expression (ex: λx)

Second, take for example these two lambda expressions (λx.fxya and λz.fxya). They're identical besides the fact that the bounded variable is different. Does this affect it's validity?

Also, if these are all valid, is there a way to see some invalid lambda expressions so I can get an idea between what a valid and invalid one looks like?

# Answer
What do you call a *valid* λ-expression? This is not a standard concept.

Anyways, λ-expressions are the terms built inductively as follows:

* given a fixed set $V$ of variables, all $x \in V$ are λ-expressions,
* for any variable $x$ and λ-expression $M$, $λx.M$ is a λ-expression,
* for any λ-expressions $M$ and $N$, $MN$ is a λ-expression.

Thus $λx$, which is of none of these forms, is not a λ-expression (not even an “invalid” one).

The two other expressions you give, $λx.fxya$ and $λz.fxya$, are not identical in any of the following meanings.

* Strictly speaking, they are different (since the abstracted variable differs): they are **not equal**.
* One often considers terms up to *α-equivalence*, i.e. up to renaming of bound variables. (You can look to any standard reference for details.) But in your example the bound variable $x$ is not replaced with $z$ in the body of the abstraction, so the two expressions are **not α-equivalent**.
(Or equivalently, if you define λ-terms as α-equivalence classes of λ-expressions, the two λ-terms are not equal.)
> 2 votes

---
Tags: lambda-calculus
---


# Question
Title: How can I organize groups of people, who don't know each other, on a regular cadence?
I'm trying to figure out an algorithm for this specific problem.

**The problem**: I have N people (say 60 but could be far more) that I want to organize into groups of 4 on a monthly cadence.

**The constraints**:

1. Each month, groups should contain people that haven't been grouped before (until they've been in a group with everyone)
2. Since these people all work for the same company, people in a group should never be on the same team (as in, reporting to the same manager).

# Answer
Here's one potential approach. First, partition all people who work at the company according to their team. This way, you get sets $T\_1, \ldots, T\_k$. Now, for every 4-tuple $(a,b,c,d)$, with $1 \leq a \< b \< c \< d \leq k$, you can enumerate the groups $g\_1, \ldots, g\_m$ where the first person belongs to $T\_a$, the second one to $T\_b$, third to $T\_c$ and last to $T\_d$. Initialize an empty graph $G$ over $n$ nodes, each representing a person, where edges will represent who has been grouped with whom. For each group $g\_i$, check if you can actually create it by verifying it's not a $4$-clique in $G$. If you can create it, then print it and add edges between every pair of people in $g\_i$.

There might be better approaches, but that will depend on how large you expect $n$ to be, what the team-structure is like, and what properties are you trying to optimize in your algorithm; e.g., minimizing enumeration delay, memory, etc.
> 2 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: I want to find the number of steps it takes to find the GCD by Euclidean Algorithm
Let's say I have two numbers a and b. I want to find the number of steps it takes to find the GCD by Euclidean Algorithm by a closed formula which includes parameter a and b. If I go by this implementation , in how many steps will I reach gcd:

```
 public static int gcd(int a, int b)
    {
        if (a == 0)
            return b;

        return gcd(b%a, a);
    }

```

# Answer
There are plenty of examples of the algorithm implementation online.
Here is one such example which also has it in Java.

From there modifying your code to count the steps should be trivial.
> 0 votes

# Answer
In case someone with real interest runs into this problem:

Start with a and b, then perform two steps. Observe how both a and b become smaller. Assume the result after two steps is a'', b'', then find a constant c \< 1 so that you can guarantee a'' \< c\*a, and b'' \< c\*b.

With that you can easily find an upper bound to the number of steps, and for some pairs of numbers that upper bound will be achieved. (Try gcd (55, 34) and what do you observe? )
> 0 votes

---
Tags: number-theory
---


# Question
Title: Why is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently?
First of all, I have just started studying computer science by myself and maybe I just need some clarification of what "polynomial time" means regarding the time complexity of an algorithm and references to study it well.

As I have understood it, whether integer factorization can be done in polynomial time is still an open question and, as this article in wikipedia (https://en.wikipedia.org/wiki/Integer\_factorization) puts it,

> When the numbers are very large, no efficient, non-quantum integer factorization algorithm is known; an effort by several researchers concluded in 2009, factoring a 232-digit number (RSA-768), utilizing hundreds of machines took two years and the researchers estimated that a 1024-bit RSA modulus would take about a thousand times as long.

So, trying to see that for myself, I have written a very naive code in MATLAB checking it with prime numbers up to 15 digits; the reasoning being that if I can check if a number is prime fast, I can easily modify the code to give me the factorization fast.

The time it takes the code to check if a number is prime doesn't grow exponentially with the input.

```
function[]=prime(n)
tic
f=floor(sqrt(n));
for i=2:f
    if rem(n,i)~=0
        b=0;
    else
        b=1;
        disp(i)
        break
    end
end
if b==0
    disp('prime')
else
    disp('not prime')
end
toc
end

```

And so I go back to the question in the title. What is wrong with my reasoning?

# Answer
> 31 votes
Since your algorithm is "fast", why did you only try it with a 15-digit number and not with a 232-digit one? There's serious money to be made if you indeed have a "fast" algorithm.

Your algorithm takes time (if we count "div" as taking constant time) proportional to $\sqrt{n}$. A $d$-digit number can be as large as $10^d$, so your algorithm takes time proportional to $\sqrt{10^d} \approx 3.16^d$, i.e. exponential in $d$, the number of digits. That is by no means "fast" and grows very quickly as the numbers get larger.

It is polynomial with respect to the *value* of $n$, but not with respect to the *size* of $n$. This behavior is called pseudopolynomiality.

The "fast" prime testing algorithms use much more sophisticated approaches which can not be modified (easily) to also give a factorization. They just report yes/no whether the number is prime. The AKS primality test uses time proportional to $d^6$.

# Answer
> 12 votes
The point is that the complexity of an algorithms is measured in the *size* of the input. For a number $n$ its size, the length of its representation, is $\log n$ bits.

# Answer
> 2 votes
There can be different algorithms to solve a problem and there is no reason that all of them should follow some particular structure. It is a common mistake to assume that to check if a number is not a prime an algorithm needs to find a non-trivial factor of the number. This is not true. The AKS algorithm does not find any factors when it reports a number is not prime.

AKS is rather complicated so let's look at the simpler Miller–Rabin algorithm (ignoring the fact that it is a probabilistic algorithm). Let $n$ be the number we want to check if it is prime or not. The case of even numbers is easy so we consider the case of odd $n$. Let $n-1 = d2^s$ where $d$ is an odd number.

The idea is:

> $n$ is not prime iff for all $0 \< a \< n$ and $0 \leq r \< s$, $$a^d \not\equiv 1 \ (\text{mod } n)$$ and $$a^{2^rd} \not\equiv -1 \ (\text{mod } n)$$

Assume that we checked these conditions, then we know $n$ is not a prime without finding a nontrivial factor of $n$.

# Answer
> 0 votes
When a know fast primality finds that its input is not a prime, it has a proof that there must be a non-trivial factor hidden somewhere, but it doesn't have the slightest clue what that factor would be (unless a primality tester first does a quick check if its input is even. or divisible by 3, 5 or 7).

So the best you can do if you try to find a non-trivial prime factor, is to make a guess "if there was a non-trivial prime factor then it is likely that I would have found it by now". And in that case, you do a primality check, and if the primality checker says "prime" then the number is factored.

(You do that in Pollard-rho. It finds a factor in about $c \cdot \sqrt p$ steps, where p is the smallest prime factor. That means for composite numbers it will find a factor in $c \cdot n^{1/4}$, but if n is prime it will proudly announce after $c \cdot \sqrt n$ steps that n has the factor n. So after more than say $10 \cdot \sqrt n$ steps you add a primality test. )

The worst case for all the easily understandable algorithms are composite numbers n with exactly two prime factors not for away from $\sqrt n$.

# Answer
> -1 votes
If one uses N%D to denote the remainder after dividing N by D, and B^E to denote B raised to the power E, then for any integer N and X with no common factors greater than 1, there will exist some integer Y less than N-1 such that (X^Y)%N equals 1. If N is prime, the smallest such integer will be Y=N-2. For most non-prime values of N, however, most values of X will cause (X^(N-2))%N to yield something else.

If one could identify the Y values for which (X^Y)%N equals 1, that information could be used to factor N fairly easily (and likewise knowing the factors one could compute Y values), but there's no known generally-useful way to find such values without knowing or guessing at the factorization of N.

---
Tags: algorithms, complexity-theory, time-complexity, factoring
---


# Question
Title: Curry-Howard isomorphism and non-constructive logic
My understanding of the Curry–Howard correspondence is that it shows an isomorphism between constructive logic (also called intuitionistic logic) and computer programs in appropriate typed languages.

Basically, a (logical) proposition corresponds to a type, a proof (of that proposition) is an inhabited type, a function of type $A \to B$ is an implication $A \implies B$ (regarding the corresponding proposition) an so on...

What I don't understand, is that it is often said that this CH correspondence is crucial in how proof assistant (e.g. Coq or Lean) work, whereas those proof assistant support classical (non-constructive) logic.

My question is: how can this correspondence (about constructive logic) be helpful for proof assistant in the context of classical (non-constructive) logic?

(An explanation in simple words — without too many assumptions on any general knowledge about type systems or proof assistant would be much appreciated)

# Answer
> 7 votes
I think people sometimes disagree on what exactly Curry-Howard is. But, one way to look at it is an exact correspondence between the syntactic rules for logic and for type theory.

For the presentations type theory is usually based on, this continues to hold for classical logic. Typically type theories are written using natural deduction, and the way excluded middle typically works in that frameworks is as an axiomatic rule:

$$\frac{}{Γ ⊢ A ∨ ¬ A}$$

This is essentially no different from just adding some uninterpreted term of the appropriate type to the corresponding type theory. And that is how classical reasoning is usually enabled in the proof assistants you mention (maybe with another term for the axiom of choice).

Maybe I should also say: the correspondence continues to hold for classical logic in any case. But some presentations of classical logic differ considerably from the presentations usually encountered in type theory. There are studied type theories that correspond to these other presentations, but they're not the ones that are typically used for proof assistants (at least the ones I'm familiar with).

# Answer
> 3 votes
While proof assistants typically use constructive mathematics, the Curry-Howard-Correspondence does not necessarily require constructivism. The important aspect of the correspondence is that the logical rules correspond to the type-checking rules of your programming language of choice.

The "natural" correspondence is constructive, since Curry/Howard were interested in types that were added to the λ calculus to bypass Curry's paradoxon. However, one can add additional features to the programming language at hand with respective typechecking rules that may correspond to a logical axiom not part of constructive mathematics. While the proof assistants you mentioned, like Coq, simply add these axioms as "uninterpreted symbols" (a feature in the programming language without computation), it is actually possible to support classical reasoning without giving up on a computational interpretation: `call/cc`, as seen in programming languages like Scheme.

To see this, it is instructive to first look at the dynamic and at the static semantics of `call/cc`. `(call/cc f) + 2` will apply `f` to the "outer context". Essentially, the part `(call/cc f)` in the whole expression `(call/cc f) + 2` will become a "hole" that is to be filled, which is applied to `f`: `(f (λh. h + 2))` Trying to typecheck this, as done in Typing First-Class Continuations in ML, will lead to the type: $$\operatorname{call/cc}:\forall\alpha,((\alpha\to\forall\beta,\beta)\to\alpha)\to\alpha$$ This looks eagerly similar Peirce's Law, which is equivalent to the law of excluding middle, the core feature of classical reasoning! So, even when you are allowed to time-travel, you can establish a feature in your programming language that has a computational interpretation while fulfilling the Curry-Howard-Correspondence.

The correspondence itself is "disconnected" from the concrete logic or programming language at hand, i.e., it does not matter whether you look at classical logic, constructive logic, linear logic, minimal logic, ultrafinitist logic, ..., whatever logic and likewise for programming languages. And moreover, the correspondence itself is "disconnected" from the computation of the programming language, i.e., we can add "compiler intrinsic functions" or "custom axioms without computational meaning" that nonetheless typecheck (after all, not everything has to compute in a proof assistant, since it is not a programming language). The key point is really that "whatever typechecks in your programming language has an interpretation in (some) logic". In turn, the correspondence is helpful for proof assistants in the context of whatever logic you are interested in.

# Answer
> 3 votes
The Curry-Howard correspondence is **not crucial** for functioning of a proof assistant. Unforunately, the term "Curry-Howard correspondence" seems to be misused nowadays for all sorts of things.

My understanding is that a Curry-Howard correspondence arises when one exhibits a translation (in both directions!) between a logic and a type theory that converts proofs to terms and vice versa.

However, Lean and Coq use a different approach, as they are both type theories equipped with a universe `Prop` of propositions, thereby *embedding* logic into type theory. In the case of Lean, the logic is classical. I would call such a setup an *embedding* of logic into type theory, not an "isomorphism".

# Answer
> 0 votes
I understand the statement that "Curry-Howard is important to proof assistants" as simply a statement that proof assistants work by creating a proof term in a suitable dependently-typed lambda calculus. Once a proof term is created and type-checked, the proof assistant accepts the proof as valid.

So, the whole idea that a proof of a mathematical proposition is equivalent to some "proof term", i.e., to just an expression in a suitable lambda-calculus, is central to how proof assistants work. "Proofs are programs", or more precisely "proofs are lambda-terms". A proof assistant is an interface for people to work with those (very complicated) lambda-terms more easily.

This is not in contradiction to the fact that proof assistants can validate proofs about classical logic. The lambda calculus on which the proof assistant itself works might be based on constructive logic, like most functional programming languages today. But the proof terms can express reasoning about arbitrary axioms and derivation rules.

---
Tags: logic, type-theory, proof-assistants, curry-howard
---


# Question
Title: BIT: What is the intuition behind a binary indexed tree and how was it thought about?
A binary indexed tree has very less or relatively no literature as compared to other data structures. The only place where it is taught is the topcoder tutorial. Although the tutorial is complete in all the explanations, I cannot understand the intuition behind such a tree? How was it invented? What is the actual proof of its correctness?

# Answer
> 229 votes
Intuitively, you can think of a binary indexed tree as a compressed representation of a binary tree that is itself an optimization of a standard array representation. This answer goes into one possible derivation.

Let's suppose, for example, that you want to store cumulative frequencies for a total of 7 different elements. You could start off by writing out seven buckets into which the numbers will be distributed:

```
[   ] [   ] [   ] [   ] [   ] [   ] [   ]
  1     2     3     4     5     6     7

```

Now, let's suppose that the cumulative frequencies look something like this:

```
[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
  1     2     3     4     5     6     7

```

Using this version of the array, you can increment the cumulative frequency of any element by increasing the value of the number stored at that spot, then incrementing the frequencies of everything that come afterwards. For example, to increase the cumulative frequency of 3 by 7, we could add 7 to each element in the array at or after position 3, as shown here:

```
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

```

The problem with this is that it takes O(n) time to do this, which is pretty slow if n is large.

One way that we can think about improving this operation would be to change what we store in the buckets. Rather than storing the cumulative frequency up to the given point, you can instead think of just storing the amount that the current frequency has increased relative to the previous bucket. For example, in our case, we would rewrite the above buckets as follows:

```
Before:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

After:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
  1     2     3     4     5     6     7

```

Now, we can increment the frequency within a bucket in time O(1) by just adding the appropriate amount to that bucket. However, the total cost of doing a lookup now becomes O(n), since we have to recompute the total in the bucket by summing up the values in all smaller buckets.

The first major insight we need to get from here to a binary indexed tree is the following: rather than continuously recomputing the sum of the array elements that precede a particular element, what if we were to precompute the total sum of all the elements before specific points in the sequence? If we could do that, then we could figure out the cumulative sum at a point by just summing up the right combination of these precomputed sums.

One way to do this is to change the representation from being an array of buckets to being a binary tree of nodes. Each node will be annotated with a value that represents the cumulative sum of all the nodes to the left of that given node. For example, suppose we construct the following binary tree from these nodes:

```
             4
          /     \
         2       6
        / \     / \
       1   3   5   7

```

Now, we can augment each node by storing the cumulative sum of all the values including that node and its left subtree. For example, given our values, we would store the following:

```
Before:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
  1     2     3     4     5     6     7

After:
                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [ +5] [+15] [+52] [ +0]

```

Given this tree structure, it's easy to determine the cumulative sum up to a point. The idea is the following: we maintain a counter, initially 0, then do a normal binary search up until we find the node in question. As we do so, we also do the following: any time that we move right, add the current value to the counter.

For example, suppose we want to look up the sum for 3. To do so, we do the following:

* Start at the root (4). Counter is 0.
* Go left to node (2). Counter is 0.
* Go right to node (3). Counter is 0 + 6 = 6.
* Find node (3). Counter is 6 + 15 = 21.

You could imagine also running this process in reverse: starting at a given node, initialize the counter to that node's value, then walk up the tree to the root. Any time you follow a right child link upward, add in the value at the node you arrive at. For example, to find the frequency for 3, we could do the following:

* Start at node (3). Counter is 15.
* Go upward to node (2). Counter is 15 + 6 = 21.
* Go upward to node (4). Counter is 21.

To increment the frequency of a node (and, implicitly, the frequencies of all nodes that come after it), we need to update the set of nodes in the tree that include that node in its left subtree. To do this, we do the following: increment the frequency for that node, then start walking up to the root of the tree. Any time you follow a link that takes you up as a left child, increment the frequency of the node you encounter by adding in the current value.

For example, to increment the frequency of node 1 by five, we would do the following:

```
                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
      > 1     3     5     7
      [ +5] [+15] [+52] [ +0]

```

Starting at node 1, increment its frequency by 5 to get

```
                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
      > 1     3     5     7
      [+10] [+15] [+52] [ +0]

```

Now, go to its parent:

```
                 4
               [+32]
              /     \
         > 2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

```

We followed a left child link upward, so we increment this node's frequency as well:

```
                 4
               [+32]
              /     \
         > 2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

```

We now go to its parent:

```
               > 4
               [+32]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

```

That was a left child link, so we increment this node as well:

```
                 4
               [+37]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

```

And now we're done!

The final step is to convert from this to a binary indexed tree, and this is where we get to do some fun things with binary numbers. Let's rewrite each bucket index in this tree in binary:

```
                100
               [+37]
              /     \
          010         110
         [+11]       [+80]
         /   \       /   \
       001   011   101   111
      [+10] [+15] [+52] [ +0]

```

Here, we can make a very, very cool observation. Take any of these binary numbers and find the very last 1 that was set in the number, then drop that bit off, along with all the bits that come after it. You are now left with the following:

```
              (empty)
               [+37]
              /     \
           0           1
         [+11]       [+80]
         /   \       /   \
        00   01     10   11
      [+10] [+15] [+52] [ +0]

```

Here is a really, really cool observation: if you treat 0 to mean "left" and 1 to mean "right," the remaining bits on each number spell out exactly how to start at the root and then walk down to that number. For example, node 5 has binary pattern 101. The last 1 is the final bit, so we drop that to get 10. Indeed, if you start at the root, go right (1), then go left (0), you end up at node 5!

The reason that this is significant is that our lookup and update operations depend on the access path from the node back up to the root and whether we're following left or right child links. For example, during a lookup, we just care about the right links we follow. During an update, we just care about the left links we follow. This binary indexed tree does all of this super efficiently by just using the bits in the index.

The key trick is the following property of this perfect binary tree:

> Given node n, the next node on the access path back up to the root in which we go right is given by taking the binary representation of n and removing the last 1.

For example, take a look at the access path for node 7, which is 111. The nodes on the access path to the root that we take that involve following a right pointer upward is

* Node 7: 111
* Node 6: 110
* Node 4: 100

All of these are right links. If we take the access path for node 3, which is 011, and look at the nodes where we go right, we get

* Node 3: 011
* Node 2: 010
* *(Node 4: 100, which follows a left link)*

This means that we can very, very efficiently compute the cumulative sum up to a node as follows:

* Write out node n in binary.
* Set the counter to 0.
* Repeat the following while n ≠ 0:
    + Add in the value at node n.
    + Clear the rightmost 1 bit from n.

Similarly, let's think about how we would do an update step. To do this, we would want to follow the access path back up to the root, updating all nodes where we followed a left link upward. We can do this by essentially doing the above algorithm, but switching all 1's to 0's and 0's to 1's.

The final step in the binary indexed tree is to note that because of this bitwise trickery, we don't even need to have the tree stored explicitly anymore. We can just store all the nodes in an array of length n, then use the bitwise twiddling techniques to navigate the tree implicitly. In fact, that's exactly what the bitwise indexed tree does - it stores the nodes in an array, then uses these bitwise tricks to efficiently simulate walking upward in this tree.

Hope this helps!

# Answer
> 17 votes
I think that the original paper by Fenwick is much clearer. The answer above by @templatetypedef requires some "very cool observations" about the indexing of a perfect binary tree, which are confusing and magical to me.

Fenwick simply said that the responsibility range of every node in the interrogation tree would be according to its last set bit:

E.g. as the last set bit of `6`==`00110` is a "2-bit" it will be responsible for a range of 2 nodes. For `12`==`01100`, it is a "4-bit", so it will be responsible for a range of 4 nodes.

So when querying `F(12)`==`F(01100)`, we strip the bits one-by-one, getting `F(9:12) + F(1:8)`. This is not nearly a rigorous proof, but I think that's it's more obvious when put so simply on the numbers axis and not on a perfect binary tree, what are the responsibilities of each node, and why is the query cost equals to the number of set bits.

If this is still unclear the paper is very recommended.

# Answer
> 1 votes
I think that Fenwick trees/binary indexed trees are much easier to understand *and prove* if you don't think of them as trees at all.

### Partial Sum Array

Given a subject array $A\_0 ... A\_{N-1}$ of length $N$, that we want to track prefix sums of, a Fenwick tree is just an array $F$ of $N+1$ partial sums, such that:

$$F\_0 = 0,and\\ F\_i = \sum\_{j=p(i)}^{i-1}{A\_j} $$

...where $p(i)$ is the "prefix" of $i$ formed by turning off its lowest 1 bit.

The sum of the first $i$ elements of $A$ is then just $F\_i + F\_{p(i)} + F\_{p(p(i))} ...$ until you get to $F\_0$.

This would actually work for *any* definition of $p(i)$ that iteratively decreases to 0, but Fenwick's definition is special because it enables both quick queries and updates.

Since each application of the function $p$ reduces the number of bits set in $i$, it takes at most $log\_2 i$ applications to get to 0, and any prefix sum of $A$ can be queried in $O(log N)$ time.

### Updates

To update the partial sum array, we can just follow the above definition. If an element in the subject array changes like $A\_j \leftarrow A\_j+x$, then we need to update *all* the partial sums $F\_i$ such that $p(i) \le j \< i$.

For each $0$ bit in $j$, there is exactly one pair of matching $i$ and $p(i)$. If $j$ is $xxx0yyy$ in binary, then $i = xxx1000, p(i) = xxx0000$ works, and we have $xxx0000 \le xxx0yyy \< xxx1000$.

So to find all the $F\_i$ to update, we just need to find the 0 bits in $j$ and construct the corresponding indexes $i$.

### Bit Hacks

Fenwick tree implementations rely on a few bit hacks that simplify the code.

First, to calculate $p(i)$, we can use `p(i) = i & (i-1)`. This turns off the lowest bit 1 of `i`, because `(i-1)` flips the low-order 0 bits in `i`, as well as the lowest 1 bit due to borrow.

To find the 0 bits in `j` to update, and construct the corresponding indexes, two similar bit-hacks are used:

* `i = j+1` creates the first valid `i`, because it flips the low-order 1 bits to 0, and then sets the first 0 bit to 1 via carry.
* `i += (i & -i)` finds next valid `i` by doing the same thing, but starting at `i`s lowest 1 bit.

Putting it all together, the implementation is simple:

def updateFT(F, index, delta):
    index += 1
    while index <= len(F):
        F[index] += delta
        index += index&-index;

def queryFT(F, n):
    sum = 0
    while n > 0:
        sum += F[n]
        n &= n-1
    return sum
```

---
Tags: algorithms, binary-trees, trees
---


# Question
Title: Matching points on a plane with maximum total weight
I have a set of points $P = \\{p\_1, \dots, p\_m \\}, \\; 0 \le m \le 10^4$ on a plane of two colors (red and green). Each point has integer x-coordinate (all x-coordinates are different), and non-negative y-coordinate (y-coordinate can be non-integer). In addition, each point has a weight $w \in \mathbb{R}^+$.

I can match two points **only of different colors** $p\_1 = (x\_1, y\_1, w\_1)$ and $p\_2 = (x\_2, y\_2, w\_2)$ with a vector $v = \vec{p\_1 p\_2}$ of any weight $0 \le w \le min(w\_1, w\_2)$, if $x\_1 \< x\_2$. This vector will be assigned with a value

$$f\_v = w \frac{y\_1 - y\_2}{y\_1}$$, if $p\_1$ is green, and $-f\_v$ vice versa.

**Problem:**

What is an algorithm to find a set of vectors $V = \\{ v\_1, \dots, v\_s \\}$ (described above) with proper weights $w\_1, \dots, w\_s$, that will maximize total value of $F = \sum\_{v \in V} f\_v$?

**Constraints:**

1. Sum of weights of outgoing and incoming vectors (together) for each point should be less or equal than the weight of this point.
2. For each horizontal line $x=val$, total weight of vectors that are intersected by this line is $\le 1$.

**Methods:**

1. I was thinking about dynamic programming approach, where I will calculate the max value of $F$ for each $i \le m$, but it doesn't support floating weights $w$ of vectors.

# Answer
This can be expressed as an instance of linear programming and then solved with a LP solver. The unknowns are the weights on all possible vectors (at most $\sim m^2/2$ of them), the constraints provide linear inequalities, and the objective function to maximize is a linear function of the unknowns.
> 0 votes

---
Tags: graphs, dynamic-programming, computational-geometry, linear-programming
---


title: CSES problem Two Sets II

text:
# Question
Title: CSES problem Two Sets II
> Your task is to count the number of ways numbers $1,2,…,n$ can be divided into two sets of equal sum. For example, if n=$7$, there are four solutions: ${1,3,4,6}$ and ${2,5,7}$, ${1,2,5,6}$ and ${3,4,7}$, ${1,2,4,7}$ and ${3,5,6}$, ${1,6,7}$ and ${2,3,4,5}$ Input The only input line contains an integer n. Output Print the answer modulo $1e9+7$. $1$$n$$500$

Source: cses

My approach: It's a pretty straightforward DP problem, where we follow a loop from $1$ to $n$ and for each such i in $1$ to $n$, we fill the sum DP.

```
    int s=sum/2;
    vector<int>dp(s+1);
    dp[0]=1;
    for(int i=1;i<=n;++i){
        for(int k=s;k>=0;--k){
            if(k-i>=0){
                dp[k] = (dp[k] + dp[k-i])%mod;
            }
        }
    }
    int ans=dp[s]/2;

```

My question is, if I change here the loop from $1$ to $n-1$ and then output $dp\[s\]$, then the answer is correct, however if I loop from $1$ to $n$, then output $dp\[s\]/2$, it is incorrect. I think both should be correct since in the second method, I am counting all the possibly ways of making sum=$n\*(n+1)/4$ and then simply dividing by $2$ since we take only $1$ out of the $2$ sets.

# Answer
I have figured this out after experimenting some time with the code. The issue was that we cannot divide $dp\[sum\]/2$ since we need modulo inverse to calculate the quotient.
> 1 votes

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Why, for $f(n) = n \cdot \sqrt n$ and $g(n)=n^2/\log n$, we have $f(n) = o(g(n))$?
Let $f(n) = n \cdot \sqrt n$ and $g(n)= \frac{n^2}{\log n}$. Why is $f(n) = o(g(n))$?

Could you please explain to me why this is so? I have tried l'Hôpital's rule but it doesn't add any clarification.

# Answer
> 2 votes
$f(n) = n^{1.5}$ and $g(n) = n^2/\log n$.

Note that $\log n$ grows slower than any polynomial function.

Try to compute $$\lim\_{n \to \infty} \frac{f(n)}{g(n)}$$

Which grows faster, $\log n$ or $\sqrt n$?

---

More details: By dividing by $n^{1.5}$, we get

$$\lim\_{n \to \infty} \frac{f(n)}{g(n)} = \lim\_{n \to \infty} \frac{n^{1.5}}{n^2/\log n} = \lim\_{n \to \infty} \frac{1}{\sqrt n/\log n} = \lim\_{n \to \infty} \frac{\log n}{\sqrt n}$$

It should be quite clear that this limit is 0, but if not, you may see that both of them go to $+\infty$, and you may use l'Hôpital's rule and you get $$\lim\_{n \to \infty} \frac{\log n}{\sqrt n} = \lim\_{n \to \infty} \frac{\log n'}{\sqrt n'} = \lim\_{n \to \infty} \frac{c/n}{1.5} = \lim\_{n \to \infty} \frac{2c}{3n}$$ for some $c$ depending on the base of your logarithm.

Now, it is the case that $f(n) = o(g(n))$ if and only if $\lim\_{n \to \infty} \frac{f(n)}{g(n)} = 0$, which is the case here.

---
Tags: big-o-notation
---


# Question
Title: Why when we use DMA , Read/Write operations on I/O devices are faster?
I am wondering why are read/write operations on I/O devices much faster when we use DMA?I must be that when using DMA we have 1 less clock cycle to access the local buffer of a IO device since it is already part of the main memory.Am I correct?

# Answer
DMA is expensive. It is used in more expensive devices. More expensive devices are faster. There is a correlation but not a causal relationship.

And in the 2020s you want nobody, not even a trusted external device, to have the ability to write directly to your RAM. Too much of a security risk.
> 1 votes

---
Tags: computer-architecture, operating-systems, memory-management
---


# Question
Title: How to prove that $L=\{0^m1^n\;|\; \mathbf{gcd}(m,n)=1\}$ is not regular
The pumping lemma is allowed to be used in this assignment, so I have tried to make $|0^{m+b|y|-|y|}| = |xy^b| = a!, a\ge |y|,a\ge n$ so that $gcd(|0^{m+b|y|-|y|}|,n) \neq 1$.

# Answer
This sounds like homework so I will just give a high level idea. The idea behind the pumping lemma is that regular languages are so structured that any long enough word in the language has a sub-word that you can “pump” as many times as desired without exiting the language. In your case, we want to use this to show that your language is not regular, and therefore we should find a long enough word in the language that doesn’t allow for pumping.

Let’s think of examples of long words in the language.

Example 1) $0^m 1$, for a large $m$. Can you take a subword of this and pump it without exiting the language? Yes, just take a subword consisting only of 0s.

Example 2) Let $p$ be a large prime, and consider the word $0^p1^{p+1}$. Why is this word in the language? Prove that no matter what subword you choose, if you pump it the right amount of times the result will exit the language. Here you can proceed by cases; what if the chosen subword has only 0s, what if has only 1s, and what if it has a mixture of both.
> 2 votes

# Answer
Instead of using the pumping lemma, you can prove directly that a finite state machine cannot work.

Assume you have a state machine with k states. And you just parsed 0^p 1 for some prime. So you are in a state where n\*p-1 1s will get you to an accepting state. After parsing a 1, you are in a state where parsing n\*p-2 1s gets you to an accepting state. That state must be different. And every 1 you parse gets you to another state that must be different from the others, until you parsed p+1 1s and are back in the first state.

So you need at least p states. If p \> k then your state machine with k states cannot parse it. That’s true for any finite state machine and any number of states. Therefore the language is not regular.
> 1 votes

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