# Question
Title: Are there competitions for integer programming?
Are there competitions for integer programming like there are for SAT and MAXSAT?

# Answer
> 5 votes
There are competitions for constraint satisfaction solvers. Some problems there can be readily translated to IP solvers as well. See e.g., MiniZinc challenge which has taken place yearly since 2008 or the XCSP competition.

# Answer
> 6 votes
There are no competitions targeting general integer programming or mixed integer programming, but there are (or were) benchmarks, such as the MIPLIB (linear) and the MINLPLIB (nonlinear).

There are competitions for subsets (PB, SAT, max-SAT) and for constraint programming, as you and other answers pointed out. You can find many competitions (DIMACS challenges, for example) with NP-hard problems that can be formulated as IP, too.

So, why are there no such competitions? My personal guess is that it comes down to:

* Implementation complexity. A good integer programming solver is HUGE and COMPLEX. SAT competitions and the like are interesting because many (small) teams can compete and a few tricks could get you quite far. There are only a few IP solvers, and all of them are many years of work.
* Too general. There are many many IP instances with different properties. It would be difficult to create a balanced benchmark set.
* Mature field. The solvers are mostly commercial, and the companies have no interest in organizing or taking part in such competitions.

# Answer
> 3 votes
There was a Pseudo-Boolean solver competition from 2005-2012, but (as far as I can tell) nothing since then. Integer Linear Programming is a subset of Pseudo-Boolean programming. See the 2012 competition page for results and links to other competition results.

# Answer
> 2 votes
It is not really a competition, but there is the well-known Mittelmann benchmark, which lists results for some of the best solvers (including commercial ones) for mixed-integer programming and related problem classes:

http://plato.asu.edu/bench.html

http://plato.asu.edu/ftp/milp.html

---
Tags: satisfiability, integer-programming, sat-solvers, mips, programming-contest
---


# Question
Title: Why can't 3-SAT be solved efficiently if you convert all clauses (x ∨ y ∨ z) into (u ∨ z) by introducing a variable?
Let $a\_i$, $b\_i$, etc., be a literal, i.e., a variable or the negation of a variable.

3-SAT concerns formulas in CNF form: $(a\_1 \vee a\_2 \vee a\_3) \wedge \dots \wedge (b\_1 \vee b\_2 \vee b\_3)$ (3-CNF). The problem of whether or not such a formula has an assignment of its Boolean variables such that it evaluates to $1$ is NP-complete.

But if we can convert the 3-CNF formula into a 2-CNF efficiently, then using implication graphs, we know that 2-SAT is in the complexity class P, which would make 3-SAT lives there as well.

So I'm wondering what are the obstacles to doing this?

For example, why can't we do this to remedy it (working with a clause at a time):

$$F := (a \vee b \vee c) \\ u := (a \vee b) \\ \text{But, this assignment (equality) is true} \iff \\ G := (u \vee \bar{a}) \wedge (u \vee \bar{b}) \wedge (\bar{u} \vee a) \wedge (\bar{u} \vee b) =1. \\ \text{ So, } F = 1 \iff \exists u~(u\vee c) \wedge G = 1. $$

And all we've done is swapped out one 3-CNF clause in favor of 5 2-CNF clauses.

I'm not seeing why this wouldn't make 3-SAT polynomial time.

# Answer
> $u = (a \vee b) \iff (u \vee \bar{a}) \wedge (u \vee \bar{b}) \wedge (\bar{u} \vee a) \wedge (\bar{u} \vee b) =1 $

Unfortunately, the equivalence above does not hold.

Let $a=\text{false}$, $b=\text{true}$, $u=\text{true}$.

* the LHS is $\text{true}$.
* the RHS is $\text{false}$ since $\bar u\lor a=\text{false}\lor\text{false}=\text{false}$.

---

In fact, we can prove the following.
**Claim**: there is no 2-CNF formula $\varphi(a,b,c,x\_1,\cdots,x\_m)$ such that $\forall a, b, c\in\\{\text{false, true}\\}$, $$a\lor b\lor c \iff \exists x\_1 \cdots \exists x\_m ~\varphi(a,b,c,x\_1,\ldots,x\_m).$$
> 9 votes

---
Tags: complexity-theory, satisfiability, boolean-algebra, 3-sat, 2-sat
---


# Question
Title: Are there any formal systems or programming languages in which its only possible to define functions that have inverses?
Consider an algorithm $f(x)$.

Are there formal systems or programming languages that only allow $f(x)$ to be defined if $f^-1(x)$ exists?

# Answer
Yes, there are. See reversible computing. You could of course design a programming language that only allows using reversible operations (e.g., Toffoli gates), though I'm skeptical whether this would be useful in practice. Searching on "reversible programming language" finds a bunch of academic work on the subject. See, e.g., the Janus programming language.

I'm skeptical that you're going to find this useful for practical applications.
> 3 votes

---
Tags: turing-machines, decision-problem, functional-programming, decidability, reversible-computing
---


title: Execution Time in Stage Pipeline

text:
# Question
Title: Execution Time in Stage Pipeline
**Exam Question:** A five-stage pipeline has stage delays of 150,120,150,160 and 140 nanoseconds. The registers that are used between the pipeline stages have a delay of 5 nanoseconds each. The total time to execute 100 independent instructions on this pipeline, assuming there are no pipeline stalls, is \_______ nanoseconds.

**Solution:** k(stage)=5, n(instruction)=100

where k=number of pipeline stages, n=number of instructions,tp=pipeline cycle time.

Total time=(k+n-1)\*tp

tp=max(stage delays) + register delay tp=max(150,120,150,160,140)+5ns tp=160+5=165ns

Total time =(5+100-1)*165=104*165=17160 ns.

**My Question** In the above solution why we are using the formula for total time is like that. We can use something like:

tp\*(n-1) + (sum of delays in all stages)

Can anyone tell me why total time formula is given as "(k+n-1)\*tp" ? If we put n as 1 we will get wrong answer.

Thanks,

# Answer
Read it like this: total time = $n\*tp + (k-1)\*tp$

$n\*tp$ is the time the instructions take .. sort of. But it would be the time between when the first instruction starts, and when the last instruction *starts*. That means the program has not finished yet, some instructions are still in the pipeline, we have to wait a little bit longer. Those instructions that are still in the pipeline at that point stick around for $k-1$ more cycles (not $k$, that would allow a whole extra instruction to run, that's too much) and only then is the program done.

> If we put n as 1 we will get wrong answer.

If we put $n$ as 1 then we get $k\*tp$, which seems fine to me. Any less than that would mean the instruction has not made it all the way through the pipeline, and so far there is no concrete reason to say that it will take longer (a more detailed model may reveal such reasons, but then the original formula for the time would also be modified).

---

Consider 5 instructions being executed by a 5-stage pipeline (pictured below). How many cycles does that take? The answer isn't 5, after 5 cycles only the first instruction is done, and 4 instructions are still in the pipeline. It takes another 4 cycles to finish them.

Multiply the number of cycles by the length of a cycle, $tp$.
> 1 votes

# Answer
Let's brush up pipelining a bit. To summarize, the goal of pipelining is to make the ***clocks per instruction (CPI)*** approach $1$, which means that as you keep **increasing the number of instructions they take only $1$ clock cycle(which is the time taken by the slowest stage in the pipeline) to complete**.

**Assume you have a single instruction**. Now, to complete it's execution this must go through all the $k$ stages of the pipeline(including the buffer delays & in this case $5$ stages) so it takes **$k$ clock cycles to complete**. **Now lets take $2$ instructions**, naturally both of them have to pass through the complete pipeline to complete their execution. Here is where the pipelining shows its benefits. **As the first instruction moves from $stage$ $1$ to $stage$ $2$, simultaneously the second instruction enters $stage$ $1$. Its easy to infer that when the first instruction would be at stage $k$, the second would be right behind it at stage $k-1$ (assuming no stalls). So now the first instruction completes at $kth$ clock cycle and the second instruction at $k+1th$ clock cycle**.

***Generalizing it, when you have n instructions, the $1st$ one will always be completed at the $kth$ clock cycle, and the remaining $n-1$ instructions would get completed at subsequent $n-1$ clock cycles as each of them would take only $1$ clock cycle to complete, giving a total of $k+n-1$ clock cycles. $tp$ is the multiplicative factor, which here is the time taken by $1$ clock cycle.*** Take note that all the instructions take the complete time of the whole pipeline to execute, but since we do not let the pipeline sit idle, the overall completion time is greatly reduced, which is what pipelining aims at.

> My Question In the above solution why we are using the formula for total time is like that. We can use something like:
>
> tp\*(n-1) + (sum of delays in all stages)

Well you are correct, as I mentioned the $1st$ instruction would be completed at the $kth$ clock cycle, which is after passing through all the $k$ stages and their delays, which turns out to be $k\*tp$, and the complete expression becomes $tp\*(n-1)+k\*tp$ which is the same as $(k+n-1)\*tp$.
> 0 votes

# Answer
The longest stage takes 160ns + 5ns = 165ns. That means one instruction can leave the fourth stage every 165ns, not quicker. You just calculate the time until the first instruction leaves the 4th stage, then the time until the 100th instruction leaves the 4th stage, and the time until the 100th instruction exits the pipeline.

Instruction 1 leaves stage 4 after (155 + 125 + 155 + 165)ns. Instruction 100 moves from exiting stage 4 to the end of the pipeline in after 145ns.

So the total is (n-1)\*tp plus the time for the k stages. If we round the time for the stages up to the times of the longest stage, that adds 80ns, and the total time is now (n + k - 1) * tp. So there is a tiny difference (80ns) between the given answer and your answer.

In practice, having stages at different lengths *and saving time because of it* would be a horror to implement. It is much easier to have one 165ns clock to control everything. So in practice your CPU will behave as if it had five stages of (160 + 5)ns each. Which of course makes the different times for different stages irrelevant, and the (k + n - 1) * tp answer correct.
> 0 votes

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


title: Are integers an abstract data type?

text:
# Question
Title: Are integers an abstract data type?
I'm trying to understand whether integers are an abstract data type.

The Wikipedia article starts out by saying that integers are *not* an ADT:

> In practice, many common data types are **not** ADTs, as the abstraction is not perfect, and users must be aware of issues like arithmetic overflow that are due to the representation. For example, integers are often stored as fixed-width values (32-bit or 64-bit binary numbers), and thus experience integer overflow if the maximum value is exceeded.

But then says integers *are* an ADT (see here):

> For example, **integers are an ADT**, defined as the values ..., −2, −1, 0, 1, 2, ..., and by the operations of addition, subtraction, multiplication, and division, together with greater than, less than, etc., which behave according to familiar mathematics (with care for integer division), independently of how the integers are represented by the computer \[...\] but for most purposes the user can work with the abstraction rather than the concrete choice of representation, and can simply use the data as if the type were truly abstract.

**Which paragraph is correct?**

The literature defines an ADT as a class of abstract objects which is *fully* characterised by the operations that can be performed on them. I take this to mean that an ADT is a type that is representation independent.

While integers can be defined by the operations that you can perform on them (e.g. arithmetic, comparison), they are not representation independent as the first quote points out.

**On the other hand, does full representation independence even exist in practice?** If we go by the first quote, then even the list type would not qualify as an ADT, since users need to be aware of implementation-dependent space constraints.

# Answer
> 1 votes
The first paragraph is written in a way that is a bit confusing. It doesn't mean that integers are not an ADT. It means that fixed-width ints are not a faithful/valid/correct implementation of integers. Fixed-width ints are presumably the common datatype it is referring to.

# Answer
> 1 votes
An abstract data type is defined by a domain (possible values taken by the type) and the operations that are defined on it. Usually, one lists the minimal set of operations sufficient to achieve a given task.

**First example:**

We define the ADT "parity". The underlying set is the naturals, and the following operations must be supported:

* zero: returns the smallest natural;
* inc(n): returns the successor of the natural;
* even(n): tells if the naturalis even;
* we don't require a way to get the "value" of the natural, it can be kept secret.

**Second example:**

We define the ADT "natural16". The underlying set is the integers in \[0, 65535\].

The operations to be supported are

* get(n): returns the value as a binary number;
* set(n): assigns the value as a binary number;
* inc(n): returns the successor of n;
* add(m, n): returns the sum of n and m, provided n+m ≤ 65535.

**Third example:**

We define the ADT "natural". The underlying set is the natural numbers.

The operations to be supported are

* get(n): returns the value as a binary number;
* set(n): assigns the value as a binary number;
* inc(n): returns the successor of n;
* add(m, n): returns the sum of n and m.

---

Even though computer implementations of these come naturally to mind, the implementation details are irrelevant and need not be disclosed. The third type cannot be "fully" implemented on a physical machine, but approximations by computers are quite sufficient for real applications.

# Answer
> 0 votes
**On the other hand, does full representation independence even exist in practice?**

**It depends on the domain you are working with.*

In the case of integers as mentioned, being of fixed width makes them prone to conditions like overflow. This is because the notion of integer addition in mathematics(which operates on the set of integers) is associated with the implementation of integers. But actually what the implementation does work on is a fixed set of values and modular arithmetic(more precisely a Ring of size $2^w$ for w bit width). If you follow this model, then (modular)addition over integers does have a perfect abstraction(for argument's sake).

***Shortly put, it depends on what ADT you are implementing, and on what platform, as all of it eventually needs to be realized on actual hardware.***

> but for most purposes the user can work with the abstraction rather than the concrete choice of representation, and can simply use the data as if the type were truly abstract.

Same as what I said at the beginning. Unless you come across a situation, where the implementation of integers doesn't satisfy your needs, its safe to assume the integers as *truly abstract*.

**Which paragraph is correct?**

Both of them are, in their own ways. The first one reflects the physical limits we have while implementing ADTs, and the second one stresses the fact that given a scenario, an imperfect abstraction would do just as good as a perfect one.

**TLDR;**

ADT's are as abstract as needed.

# Answer
> 0 votes
My first impression was that the source you've quoted is contradictory nonsense.

Having spent a bit of time reading up, I've come to the following conclusion.

The notion of an "abstract data type" makes sense only to the extent that we recognise certain data types can have different but equivalent implementations.

What might be abstract about an "integer" is that part of the type that doesn't seem to depend on whether a machine is big-endian or little-endian, two's complement or one's complement, and so on.

It's worth bearing in mind that Barbara Liskov, who apparently coined this term, was writing in 1974, when these sorts of storage details loomed large.

However, what exactly the full "abstract" definition of any given type is, may be something that is itself open to different interpretations. It's not always clear that programmers are dealing in rigorous abstractions, or merely in imprecise definitions and sloppy thinking.

I would be inclined to say that an "abstract" integer, free of all storage details like field size, is not something that is widely known to programmers. Probably because integers with variable-size storage (and thus, bounds limited only by the total available storage, which is a kind of limitation that applies only to the machine, not to a data type) don't commonly exist, and are probably extremely slow to process.

So we programmers might deal with the abstract Int32, and the abstract UInt8, but not the abstract integer that has no fixed bounds.

It's also not clear that "fixed-width integers", as a general concept encompassing a family of fixed-width integer types, meets the criteria of being an ADT in its own right, because each different fixed-width integer type do not differ merely by their implementation details, but by having a different fundamental specification of the range of values that can be represented by each fixed-width type.

I would also say the general usefulness of the distinction between "abstract" and "implemented" has probably reduced since 1974, as the use of compilers means that probably all types are conceived of by the programmer in a way that is abstract from the minutiae of their binary implementation.

---
Tags: data-structures, type-theory, object-oriented, abstract-data-types
---


title: What defines a byte?

text:
# Question
Title: What defines a byte?
I am asking this question because for some reason ascii codes from range `128 - 255` have a size of 2 bytes but their composition is 8 bits which makes them a "byte". So I am confused as to why this certain ranges have 2 bytes when all of them only consist of 8 bits for example :

**127 → 01111111 (1 byte)**

```
>>> len(chr(127).encode('utf-8'))
1

```

**255 → 11111111 (2 bytes)**

```
>>> len(chr(255).encode('utf-8'))
2

```

# Answer
> 3 votes
A "byte", as defined by the C and C++ standard, is the accessible unit of memory, and exactly large enough to hold one char, signed char, or unsigned char. It must be at least 8 bits, but can be larger.

A "byte" that is exactly 8 bits in size is also called an "octet". Octets are always 8 bit, bytes are not.

Ascii-codes from 128 to 255 don't exist. ASCII only has code points from 0 to 127. Unicode code points range from 0 to 0x10ffff. Unicode code points from 0 to 127 have a one-to-one mapping to ASCII-codes. Unicode code points from 0x80 to 0x7ff use two bytes in UTF-8 encoding; code points from 0x800 to 0xffff use three bytes, and code points from 0x10000 to 0x10ffff use four bytes.

UTF-8 is an *encoding* of code points, other encodings are UTF-16LE and UTF-16BE, and UTF-32LE and UTF-32BE. An encoding has different properties from the unencoded values. There are many other encodings for subsets of Unicode, but they are falling out of fashion.

---
Tags: logic
---


# Question
Title: Complexity of solving two different LP problems
I have one LP problem (LP1) to solve, where a term in a constraint is to be substituted after solving another LP problem (LP2) (with a different variable vector). Suppose I call the dimension of the variable vector in LP1 as $n$ and in LP2 as $m$. I know that the complexity of solving an LP problem is $O(n^3L)$ ($L$ is the input length).
My doubt is : 1. Is it correct that the total complexity of solving the two LP problems together is $O((n^3+m^3)L)$? (I am worried that since I am substituting the optimal value of LP problem and thus, order is to be maintained, maybe it is to be multiplied)
2. $L$ here is the input size, so should it differ for the two problems? Or I should take it as the maximum of input size of LP1 and LP2?
e.g. suppose the problem is $$\min c^Tx \\,\text{s.t.} \\, a\_1^Tx\leq b\_1, a\_i^Tx\leq b\_i,i=2,\ldots n.$$ Here $a\_1$ is the optimal value of another LP problem. So we solve that LP to get $a\_1$, substitute in this LP.

# Answer
> 1 votes
We measure the running time of an algorithm $A$ as a function of the input *to that algorithm*, not as a measure of the length of inputs to any subroutines or subalgorithms that $A$ might invoke.

Let $L\_1$ be the size of the input to LP1, $L\_2$ be the size of the input to LP2 before substitution, and $L\_3$ be the size of the input to LP2 after substitution.

By your assumptions, the time to solve LP1 is $O(n^3 L\_1)$. If this is true, it follows that the length (number of bits) needed to express the solution can be at most $O(n^3 L\_1)$. Therefore, $L\_3 = L\_2 + O(n^3 L\_1)$, so the time to solve LP2 is $O(m^3 L\_3) = O(m^3 L\_2 + n^3 m^3 L\_1)$, and the total time to solve both is $O(n^3 L\_1 + m^3 L\_2 + n^3 m^3 L\_1)$. The length of the input to the overall algorithm is $L\_1 + L\_2$, so as a function of $L\_1 + L\_2$, the best bound we can give on the total running time is $O(n^3 m^3 (L\_1+L\_2))$.

This assumes you are measuring running time in the bit-complexity model or the word RAM model. However, I am not sure whether your $O(n^3 L)$ bound is actually in those models, or if it is an arithmetic model where it is assumed it is possible to do an operation on unlimited-length integers in $O(1)$ time. If the latter, then the reasoning above is not valid.

---
Tags: complexity-theory, time-complexity
---


# Question
Title: How to Draw the planar embedding of a graph?
I am very interested to know how to draw the planar embedding of a graph.

For this graph:

I cannot find the planar embedding because it is a Peterson graph, which is not planar;

but for the following graph:

I am unable to draw the planar embedding.

Isn't the graph itself the planar embedding?

# Answer
The graph pictured in your link is almost a planar embedding, except for the three pairs of crossed lines in the outer subgraphs. Move them and you'll have a planar embedding.

Also a word of advice: one intent of this site is to provide an archive of questions and answers for subsequent readers. Links have a way of breaking or vanishing so we discourage their use.
> 1 votes

# Answer
Simply avoid all the crossings.
> 0 votes

---
Tags: graphs, planar-graphs
---


# Question
Title: Decimal To Binary Conversion: Predicting Numbers With No Zeros
Just a fun puzzle that occurred to me. Given the function below which converts decimal integers to binary strings, is it possible to predict which decimal numbers will lead to binary strings with no zeros?

I.e. is there a way to ensure this function only returns strings of 1s *without building the string and checking*?

```
std::string toBinary(int n){
    std::string r;
    while(n!=0) {r=(n%2==0 ?"0":"1")+r; n/=2;}
    return r;
    }

```

Function source.

# Answer
> 0 votes
A binary string with only 1's represents a number that is a power of 2 minus one.

So if the rules allow to test whether a decimal number is a power of two then the solution is to add one to the number and keep deviding it by two and checking whether the remainder is zero in each step.

---
Tags: binary
---


# Question
Title: Find the largest segment within a queried range?
We are given $k$ segments $(s\_1,e\_1),(s\_2,e\_2),(s\_3,e\_4),...,(s\_k,e\_k)$ where $s\_i\le e\_i$. Now we are given a query interval $\[L,R\]$ to find the largest segment $(s\_i,e\_i)$ contained within $\[L,R\]$.

By the term **largest** we mean among all the segments contained within $\[L,R\]$ return the one whose $e\_i-s\_i$ is maximum.

And by term **contained** we mean $L\le s\_i\le e\_i\le R$

I am looking for an approach to answer the query in $O(\log n)$ where $n = \max(R\_i)-min(L\_i)$

after some precomputation/tree-building etc costing no more than $O(k~\log n)$. So if I have to answer $q$ such queries my overall complexity should be $O(k~\log n\ +\ q~\log n)$.

All the above values are integers.

My thoughts:

Note that overall complexity I require is for online query ie lets just focus on solving for one query for now. For offline queries I found a solution here There it's mentioned that it can be solved for online too using Fractional cascading but doesn't quite explain it in detail.

The other related problem where I am trying to draw ideas from is this. For anyone who thinks they have something in mind please do refer these two resources.

# Answer
Your problem can be solved in $O(\log k)$ time per query by augmenting layered range trees. Let me start with a slower solution first, and then I discuss how the time complexity can be improved.

Consider each segment $\[s\_i, e\_i\]$ as a $2$-dimensional point $(s\_i, e\_i)$ with an associated weight $w\_i$. In your case $w\_i = e\_i - s\_i$, but the following solution works in general.

A 2D-range tree consists in a logarithmic-height outer binary-search tree in which each leaf represents the $x$-coordinate of a point, which can be thought of as a trivial interval. Each internal vertex $v$ having $u$ and $z$ as children represents the interval of the $x$-axis going from the left endpoint of $u$'s interval to the right endpoint of $v$'s interval.

A vertex $v$ of the outer tree points to an array $A(v)$ storing exactly the points whose $x$-coordinate lies in $v$'s interval. This array is sorted according to the points' $y$-coordinate.

Let $k$ be the number of points in the range tree. Given an interval $\[x\_a,x\_b\]$ of the $x$-axis and an interval $\[y\_a, y\_b\]$ of the $y$-axis, we can navigate the outer tree to find a set $V$ of $O(\log k)$ vertices such the union of their intervals covers exactly $\[x\_a,x\_b\]$. In your case $x\_a = y\_a = L$, $x\_b = y\_B = R$.

For each vertex $v \in V$ we can further binary search the array $A(v)$ to find the range of indices $i\_v, j\_v$ of $A(v)$ containing the points that simultaneously have their $x$ coordinate in $\[x\_a,x\_b\]$ (from the choice of $v$) and their $y$ coordinate in $\[y\_a, y\_b\]$ (from the binary search). Each binary search requires $O(\log k)$ time. Therefore, the total time spent so far is $O(\log^2 k)$.

To find the point with the largest weight, the trivial solution would be to inspect all points $(s\_i,e\_i)$ in the discovered ranges and return the one maximizing $w\_i$, however this would be too costly since there can be many candidates. Instead, we can build a satellite range minimum query (RMQ) oracle $\mathcal{O}(v)$ attached to each $A(v)$. A range minimum query oracle preprocesses an array $B$ and, given two indices $i$ and $j$, is able to report an index $h$ such that $i \le h \le j$ and $B\[h\]$ is maximized. These oracles can be built in linear time and support constant-time queries. For each $A(v)$ consider the array $B(v)$ such that the $i$-th entry of $B(v)$ is the weight of the $i$-th point in $A(v)$ and then build a RMQ oracle $\mathcal{O}(v)$ on $B(v)$.

You can now query each oracle $\mathcal{O}(v)$ with $v \in V$ using the indices $i\_v, j\_v$ to find the point with maximum weight. Querying all oracles requires $O(\log k)$ time, and hence the overall time spent is $O(\log^2 k + \log k) = O(\log^2 k)$ per query.

To reduce the query time further, you can use the cross linking idea from fractional cascading. This is a known technique and the resulting data structure is known a layered range tree. Essentially, you are able to simultaneously find the set $V$ and, for each $v \in V$, all the indices $i\_v$ and $j\_v$ in time $O(\log k)$ (instead of $O(\log^2 k)$). This brings down the overall time needed to answer a query to just $O(\log k)$.

The building time of a layered range tree with two dimensions and $k$ points is $O(k \log k)$, and so is the time needed to build the satellite RMQ oracles (since the overall size of all the arrays is also $O(k \log k)$).

---

Here is a C++ implementation of a 2D Layered range tree that can be augmented by defining custom node types via dependency injection. The relevant file is `TwoDLayeredRangeTree.h` and is heavily commented.

In the same repository there is an implementation of a RMQ oracle via jump pointers. The building time of such an oracle is $O(n \log n)$ (more complex oracles having a linear building time exist) and the query time is $O(1)$ as long as `std::bit_width` runs in constant time (modern processors can report the number of leading 0s in a single instruction).

Finally, there is also an an example program defining a custom range tree node that uses the above RMQ oracle and (essentially) solves the problem mentioned above (more precisely it shows how to find the lightest point in a specified 2D query range).

A compiler supporting C++20 is required.
> 1 votes

---
Tags: complexity-theory, time-complexity, data-structures, segment-trees
---


# Question
Title: fastest algorithm for rectangular linear assignment problem
I want to optimally assign $m$ jobs equally to $n$ workers, where $m\>n$. Assume $m = an$ for some integer $a$, so that each worker must get exactly $a$ jobs. (The rectangular linear assignment problem, as defined here). I know this can be done by duplicating the workers to have $a$ copies of each, and then solving using the Kuhn-Munkres algorithm, which would result in $O(m^3)$.

This is an upper bound on the complexity of my problem. Is it also a lower bound? Is my problem in fact $\Theta(m^3)$? I.e., is the method of duplicating workers and using Kuhn-Munkres (as fast as) the fastest algorithm for solving the rectangular linear assignment problem (RLAP)?.

I want to know because I have a reduction of RLAP to another problem, and I want to lower-bound the complexity of this other problem.

# Answer
No, $\Omega(m^3)$ is not a lower bound. Your problem can be solved in $O((nm)^{1 + o(1)} \log a)$ time, by reducing to max flow and then using a state-of-the-art min cost max flow algorithm, such as the recent algorithm by Chen et al. See also https://en.wikipedia.org/wiki/Maximum\_flow\_problem#Algorithms.

There is a trivial $\Omega(nm)$ lower bound, since you have a weight for each pair of worker and job, and it requires $\Omega(nm)$ just to read in all of those weights.

These two bounds are nearly matching.
> 1 votes

---
Tags: time-complexity, assignment-problem
---


# Question
Title: Enumerate all superincreasing subsequences
A sequence of positive real numbers **S1, S2, S3, …, SN** is called a superincreasing sequence if every element of the sequence is greater than the sum of all the previous elements in the sequence. E.g: 1, 3, 6, 13, 27, 52.

Given a sorted list **A**, I want to iterate over all combinations of **A**, which are superincreasing.

How example:

> A = \[28, 34, 44, 60, 71, 150, 167, 212, 230, 239, 415, 431, 434, 559, 688\]

Valid examples of subsequences:

```
34, 44, 239, 434
34, 212, 434, 688

```

Here is a simple brute force example:

```
def is_superincreasing(seq):
 total = 0
 test = True
 for n in seq:
    if n <= total:
        test = False
        break
    total += n
 return test

def combinations(A):
    N = len(A)
    for i in range(2**N):
        combo = []
        for j in range(N):
            if (i >> j) % 2 == 1:
                combo.append(A[j])
        if is_superincreasing(combo):
         yield combo

```

I'd like to know if there is a better algorithm than O(2^n).

# Answer
May not be the best solution in terms of complexity, because of duplicate summation operations with further elements, but much better in the general case.

```
def superincreasing_combinations(g):
  ln = len(g) - 1
  operate = {}
  ret = set()

  for i, e in enumerate(g):
    operate[(e,)] = (i, e)

  while operate:
    o, v = operate.popitem()
    last_index, sumo = v

    while last_index < ln:
     last_index += 1
     next = g[last_index]
     if next > sumo:
      operate[(*o, next)] = (last_index, sumo + next)

    ret.add(o)
  return ret

```
> 0 votes

---
Tags: algorithms, complexity-theory, dynamic-programming
---


# Question
Title: Efficiently covering a finite set of points in $\mathbb{Z}^3$ by fixed size, axis-aligned cubes?
In my problem of interest I have an arbitrary, finite set $S \subset \mathbb{Z}^3$. And I would like to cover $S$ with a set $C \subset \\{T | T \subset \mathbb{Z}^3 \textrm{ is an axis-aligned cube of size } \ell\\}$ of minimal cardinality.

I know there exist approximation algorithms with logarithmic-ish approximation factors for the covering problem in general, but I was hoping to squeeze some extra power out of the structure I have here (having the choice of any $\ell$-sized cubes $\subset \mathbb{Z}^3$ I like, as well as having $S$ sitting on the integer lattice). But I haven't had any success. Do these restrictions give us any extra advantage?

# Answer
The problem is NP-hard. Fowler et al. proved it is NP-hard in two dimensions; it follows that it is NP-hard in three dimensions as well. See the following paper:

Optimal Packing and Covering in the Plane are NP-complete. Robert J. Fowler, Michael S. Paterson, and Steven L. Tanimoto. Information processing letters 12.3 (1981): 133-137.

See also Matrix covering by squares.
> 2 votes

---
Tags: approximation, set-cover
---


# Question
Title: How to handle Insert and Delete requests arriving out of order?
Entries need to be stored in a database. There is `Insert(entry)` RPC, which adds a new entry in a database, and `Delete(entry)` RPC, which deletes an existing entry from a database. Neither RPC can be blocking, because that adds undesired latency. Both RPCs are scheduled to run asynchronously when required, from different places in code, thus one RPC doesn't know if another has succeeded.

The problem happens, when `Insert(entry)` RPC is supposed happen before `Delete(entry)` RPC, but due to various reasons (e.g. network latency), the RPCs arrive out of order. First `Delete(entry)` deletes a non-existing entry (no op), then `Insert(entry)` request arrives, sees that the entry does not exist, and inserts it. The end result is that we have an orphaned entry which wasn't supposed to be in the database.

What are typical solutions to prevent this from happening?

# Answer
The obvious thing is that both Insert and Delete report exactly what has happened, so the caller can react.

Second, design the Delete call so that it needs to pass for example the ID of a record. The Insert call would insert the record, create a new ID for it, and report that ID. As a result, you cannot call Delete until after you received the ID from a successful Insert call.

If Insert / Delete use some external key that is unique, then a Delete for a record that hasn't been inserted yet is possible. The Delete call could return that it failed because there was no record with that key, and the caller could retry the Delete sometime later.

As a complex alternative, Delete checks if the record is there and either deletes it, or stores a marker in the database that some key needs to be deleted. The Insert operation first looks for this marker, and if present, removes the marker instead of inserting the key. Insert and Delete would return what exactly happened, so after an error free "Insert" call the caller knows whether or not the record is there.
> 1 votes

---
Tags: distributed-systems, concurrency
---


title: What is storing an instruction like?

text:
# Question
Title: What is storing an instruction like?
Texts on microprocessors use lines like the following ones :

"The instructions in an instruction set of a microprocessors have their own address "

"In the first clock cycle the instruction is fetched from its address and then the operands (variables)

"It was a breakthrough to realize that both the instructions and variables can be stored in the memory "

In all these lines what is meant by "storing an instruction at a particular address " ?

I tried thinking about it and deconstruct it and it was alog the following lines : In case of an instruction like say ,ADD, when the address bus of the microprocessor assumes the values as in the bits of the address of an instructor , an adder circuit is activated and the values in the next two registers,following the one pointed by program counter ,are transferred to the adder circuit for computation .

I realize that Thinking along these lines result in complicated structures to facilitate a larger set of instructions but that is all I can come up with at present .

Please help me understand what exactly does it mean to store an instruction at an address . (I hope it's a bit confusing because an instruction by definition is not a number but a process or some action to be followed)

# Answer
There are many theoretical ways to express an (arbitrarily complex) function in numbers, historically starting with the abstract model known as the Turing Machine. Those aren't always efficient for real problems, and in engineering we've settled on a pretty straightforward model.

Microprocessors (CPU's) have an associated memory which holds instructions. (1) Instructions are discrete operations, which change the CPU is a well-defined way. There is a finite and numbered set of instructions. Instructions may have operands, such as registers to operate on, or constants to use, and these operands are also encoded as number.

The instruction pointer (or program counter) indicates where exactly in memory the next instruction is stored. It normally increments if an instruction finishes, but a jump or branch instruction can change it in different ways.

As instructions are stored as numbers, they must be decoded when the numbers are retrieved from memory. As you correctly assume, this is non-trivial. The instruction decoder will map an instruction number to a particular bit of hardware to implement the actual instruction.

Let's assume a new CPU design, not compatible with an existing CPU, to keep this simple. As a designer, we know have the freedom to choose which numbers are associated with which instructions. We're still talking CPU's, so a number is a bitstring. We can therefore decide that an instruction is a 32 bit number. We can say that the first bit decides whether the instruction is some type of jump instruction. If so, we send off the number bits to the hardware that changes the instruction pointer. Here we look at the 2nd bit to decide whether it's an unconditional jump. For simplicity, let's assume it is. The third bit may decide whether it's a branch (push IP on stack) or not. Decoding this bit is simple: if set, push. The 4th bit may indicate whether it's an absolute or relative jump. A relative jump would require us to use the arithmetic hardware of the CPU, so for simplicity assume we have an absolute jump. The 5th bit can decide whether to take the destination address from a register, or from an operand. Assuming we use an operand, we see that another number is needed from the instruction stream. This means we issue another read, using the **incremented** instruction pointer (operand follows instruction). The fetched operand value becomes the new instruction pointer.

1) It's irrelevant here whether this memory is shared with data, or if it's augmented with caches.
> 2 votes

# Answer
> an instruction by definition is not a number but a process or some action to be followed)

Yes you are right, it is *some kind of action to be followed* but definitely *every action has some code associated with it* that tells CPU what to do.

> what exactly does it mean to store an instruction at an address .

You can think it like , for example,a register has some opcode which tells CPU to add `5` to accumulator, that would be ,say like, `ADD A,#5`

This `ADD A,#5` is actually a instruction that instructs `Algorithmic unit` to do `addition` and no doubt this instruction would be stored in some register, before it is executed.
> 1 votes

# Answer
You say "If there is an ADD instruction in memory, then the adder is activated"...

You're missing something very important here: Your CPU doesn't *know* that there's an ADD instruction. So Step 1: Read the first byte or bytes of the instruction. Step 2: Figure out from the bytes read that it is an ADD instruction (or a JUMP instruction or whatever other instruction). Step 3: Knowing which kind of instruction it is, read however many further instruction bytes are needed. Step 4: Use the adder to perform the instruction. Step 5: Change the program pointer to point to the next instruction. And start all over again.
> 0 votes

# Answer
The text alludes to the fact in the early days of computing machines, the "program" was hard-wired, for instance via a board of switches or via electric wires drawn between terminals, or even directly read from punched tape/cards. Only data was stored in the working memory, instructions were... elsewhere.

But the engineers soon understood that the program itself could be handled like data and stored in memory instead of by separate hardware means. This is indeed how it universally works now, instructions being represented by numerical opcodes, kept in RAM at contiguous addresses and indexed by the Program Counter.

This is how the concept of a stored program emerged. Among the benefits, this gives the architecture much flexibility, allows very large programs and even lets the computer generate programs itself by transformation from other forms.
> 0 votes

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


# Question
Title: Are there problems in $P$, long suspected to be $NPC$ (or $NPI$)?
One of the most compelling arguments people cite for believing $P \ne NP$ is that there are many problems of both theoretical and practical significance for which an efficient solution has eluded many intelligent people's concerted efforts for a very long period of time.

The strength of this argument seems to depend on the precise details of the history of algorithmic discovery$^1$. Consider these two extremes:

* if for all problems now known to be in $P$, a deterministic polynomial algorithm was found without much difficulty soon after someone started studying them, this seems compelling evidence that there simply isn't a deterministic polynomial algorithm to solve $SAT$
* if there are a lot of problems now known to be in $P$ for which many attempts to find a deterministic polynomial algorithm failed for many years, this seems to weaken the argument

So are there any problems which were, for a significant amount of time, suspected to be $NPC$ (or $NPI$) and were later finally proven to be in $P$?

---

$^1$ with which I'm not familiar

# Answer
> 4 votes
There are a few problems where we were not sure whether they were in P or not, and then later were found to be in P. Not a lot, but a few.

Probably the leading example is primality testing. Even before it was known to be in P, I think many computer scientists still suspected that it was likely to be in P (based on an expectation that BPP = P), but a proof seemed well out of our reach.

Linear programming is another problem where it took a little while to find a polynomial-time algorithm. For a little while, we knew about the simplex algorithm, which was often efficient in practice but which is not polynomial-time in the worst case. Then Khachiyan proved that the ellipsoid algorithm runs in polynomial time, leading to new methods for solving linear programming problems.

There are some problems where a polynomial-time algorithm is not entirely trivial to find. For example, maximum matching or 2SAT are two examples where a new undergrad who looks at the problem might not immediately see a polynomial-time algorithm.

---
Tags: complexity-theory, p-vs-np
---


# Question
Title: Floyd's Cycle Detection Algorithm Proof In Laymen
I came across the algorithm question of detecting a cycle in a linked list, but the solution has to be constant space O(1).

I have looked through various proofs proving that:

* If there is a cycle, at some point the tortoise and the hare will meet. I understand that at some point, both will be within the cycle, but how do we know that they will eventually meet?
* The time complexity will equal O(N), where N = # of nodes.

I do not care about the case where we want to find the START of the cycle, only about proving that if there is a cycle, then the two pointers will meet at a point within the cycle, and that the time complexity is O(N).

None of these proofs make intuitive, logical sense to me.

Can someone PLEASE explain the two bullet points above in an intuitive manner?

If there is math in the proof, it would be great if you could explain all parts of the proof that would not make logical sense to someone without a CS degree. Thanks!

# Answer
> 5 votes
The easiest way to understand this is really to draw it out and move your fingers on a graph, so I recommend literally pulling out a piece of paper to follow along.

Picture the part before the cycle as a line, and the cycle is a circle. So we have a straight line of arrows pointing into a circle of arrows. The length of the line is X steps, and the length of the circle is Y steps.

After X steps, the tortoise has gotten into the cycle, and the hare is further ahead, so it definitely is in the cycle too.

To understand why the tortoise and hare meet after they get into the cycle, think about the distance between the two in the circle. Assume the hare is BEHIND the tortoise--it's a circle, so while the hare is ahead, it's also fine to think of it as behind. It's at most Y steps behind in the circle, because the circle is only size Y.

At each step, the hare moves two steps, and the tortoise only moves one step, so the hare "catches up" one step. Eventually it will catch up to the tortoise. It catches up in the number of steps the hare started behind the tortoise, again at most Y steps.

So it does catch up, and it catches up in at most X + Y steps.

# Answer
> 2 votes
**1. Detecting cycle using Floyd's cycle detection algorithm** \- for this we need answer to the question: what's the guarantee that the hare and the tortoise will meet?

**2. Detecting the starting point of the cycle (in a linked-list)** \- As per the behavior of Floyd's algorithm, i.e., from the meeting point (`µ`) of the hare `H` and tortoise `T`, `T` starts moving 1 step at a time from `µ` and `H` starts moving 1 step at a time from the starting point `b` of the linked-list and they meet up at the starting point `c` of the cycle, it is evident that the distance between `µ` and `c` is equal to that between `b` and `c`. We will have to prove this.

---

To answer point 1, let's assume that there **is a cycle**. We know that `H` moves twice as fast as `T`. Let's say `T` is at some arbitrary point ahead of `H`, e.g., `H` is at point 1 and `T` is at point 5 on a number line as shown below:

Since, `T` takes 1 step at a time and `H` takes 2 steps at a time, the distance between `T` and `H` keeps decreasing by 1 in each step. That means they **will converge** after some definite number (4 in this case) steps.

Now, in Floyd's algorithm, once both of them enter the cycle, at some point in time `H` will either fall behind `T` or simply meet at some point without falling behind. Also, due to the cycle, it can be treated as an infinite sequence now and the above logic of convergence will hold, which means the hare and tortoise will meet at some point `µ`.

---

To answer point 2, let's refer to this diagram:

`L` is the length of the cycle. `c` is the beginning of the cycle. `µ` is the point where `H` and `T` meets.

We need to prove that: \begin{equation} L - ∂ = x \end{equation}

Let the distance travelled by `T` be: \begin{equation} D\_T = x + nL + ∂ \end{equation}

where `n` is an integer representing some number of times the tortoise has completed the cycle before meeting at `µ`.

Let the distance travelled by `H` be: \begin{equation} D\_H = x + mL + ∂ \end{equation} where `m` is an integer representing some number of times the hare has completed the cycle before meeting at `µ`.

We know that `H` moves twice as fast as `T`, hence \begin{equation} D\_H = 2D\_T \end{equation}

Therefore, \begin{equation} x + mL + ∂ = 2x + 2nL + 2∂ \Rightarrow x = L(2n - m) - ∂ \end{equation}

Since, the length of the cycle doesn't actually change, hence we can ignore the factor of \begin{equation} (2n-m) \end{equation}

Which means, we can say that: \begin{equation} x = L - ∂ \end{equation}

Therefore, when the hare pointer and the tortoise pointer meet at some point in the cycle, one of them can be put back to the beginning of the list and then both can be moved one step at a time and the point they meet will be the start of the cycle.

# Answer
> 1 votes
Assume there is a cycle of length r, which is entered after m steps. Once you enter the cycle, you stay in the cycle. After either m steps, or after 1 step if m = r, both tortoise and hare are in the cycle. Either they are in the same position, or the hare is k steps behind the tortoise for some 1 ≤ k ≤ r-1. With every step for the tortoise, the hare gets one step closer, and after k steps they meet for the first time.

(The case m = 0 had to be handled carefully because meeting after 0 steps doesn't count obviously).

Or easier: Let k be the smallest multiple of r which is ≥ m and ≥ 1. After k iterations, the tortoise is at position k which is in the cycle, and the hare is k positions further. Since k is a multiple of r, he is an integral number of cycles further, so he is in the first place.

---
Tags: algorithms, correctness-proof, linked-lists
---


title: Rank in a Convex Combination

text:
# Question
Title: Rank in a Convex Combination
Given vectors $A, B \in \mathbb{R}^{n}$, $w \in \[0,1\]$ and $x \in \mathbb{R}$, let

$$ Rank(A,B,w,x)=\sum\_{i=1}^{n} \boldsymbol 1 \\{w A\_{i} +(1-w) B\_{i} \< x\\} $$

denote the number of elements in the $w$-weighted convex combination of $A$ and $B$ that are smaller than $x$. I would like to compute $Rank(A,B,w,x)$ for different values of $w$ and $x$ while $A$ and $B$ remain fixed.

Is there a data structure $S(A,B)$ that helps compute $Rank(A,B,w,x)$ in less than $O(n)$ time?

# Answer
> 2 votes
By duality, this problem is equivalent to the halfplane range query problem.

For the worst-case complexity, there is a known space-time tradeoff of \[1\]:

* $O(n^2/\log^2 n)$ data structure size and $O(\log n)$ query time.
* $O(n)$ data structure size and $O(\sqrt n)$ query time.

\[1\] Agarwal, P. K. (2017). Range searching. In *Handbook of discrete and computational geometry* (pp. 1057-1092). Chapman and Hall/CRC. https://www.csun.edu/~ctoth/Handbook/HDCG3.html

# Answer
> 0 votes
You can answer each query in $O(\log n)$ time, using a sweepline algorithm combined with a persistent self-balancing binary tree.

Since $wA\_i+(1-w)B\_i$ is a linear function of $w$, each $i$ corresponds to a line in the 2D $wx$ plane. In this way we obtain $n$ lines in the plane. During preprocessing, use the Bentley-Ottmann algorithm on these $n$ lines and save the persistent self-balancing binary tree it constructs. Augment each node in each binary tree with a count of the number of leaves below it (this can be made to work with a persistent data structure too).

Now, given $w,x$, in $O(\log n)$ time we can find the appropriate instance of the persistent tree that corresponds to $w$; then look up $x$ in this tree (which can be done in $O(\log n)$ time), and find the number of leaves that fall before $x$ in the ordering (which can also be done in $O(\log n)$ time, thanks to the augmentation).

The running time for the precomputation is $O((n+k)\log n)$, where $k$ counts the number of intersections between these lines. In practice, I would expect that typically $k=O(n)$ (e.g., for random problem instances), so typically precomputation can be done in $O(n\log n)$ time.

---
Tags: algorithms, time-complexity, data-structures, probability-theory
---


# Question
Title: Greibach Normal Form: Proof every sentential form is of the form xy with x terminals and y variables
*For any grammar in Greibach normal form, every sentential form obtained from S by a partial left-most derivation is of the form xy with x terminals and y variables.*

I think that this can be proven inductively based on the length of the derivation.

Base case: length 1

S -\> a with 'a' being a terminal. This follows from the definition of Greibach Normal Form.

Induction step: Let's assume that it is true for all derivations of length n, and imagine I have a derivation of length n + 1.

S =\>\* xABC... =\> xadBC... if A -\> ad with 'a' being a terminal and d being some variables. Since a grammar in Greibach Normal Form only contains variables to the right of a single terminal symbol, this induction step is also proven and so xa are terminals and dBC... are variables.

I'm not sure about my reasoning and wanted to ask if someone could correct/finish my proof?

# Answer
Management frowns upon "check my proof" questions, but this is a good exercise on induction.

Your answer is basically correct, except for a little tuning at the base case. We are not necessarily dealing with succesful derivations, so we cannot restrict to terminal productions in the first step. In fact, if this would the only case we could not find longer derivations at all.

Actually we can start with derivations of length 0 as our base case. Obviously we now only have $S \Rightarrow\_\ell^0 S$, and $S$ is of the proper form (to be pedantic: with $S=xy$ where $x=\varepsilon$ consisting of terminals and $y=S$ consisting of variables).

The inductive step is then as you describe, but I would replace the "ABC..." by more abstract symbols.

Given a leftmost derivation in $n+1$ steps $S \Rightarrow\_\ell^{n+1} \alpha$ we apply inductive hypothesis on the first $n$ steps and have $S \Rightarrow\_\ell^n xAy \Rightarrow\_\ell \alpha$, where $x$ consists of terminals, $y$ consists of non-terminals, and $A$ is (the leftmost) nonterminal. Productions in GNF are of the from $A\to a v$ with terminal $a$ and a string of nonterminal variables $v$ (that might be empty). If we apply such a production to $A$ in the last step of the above derivation we get $\alpha = xavy$. This is of the proper form $\alpha = x'y'$ with $x'= xa$ consisting of terminals and $y'= vy$ consisting of variables. Done.
> 1 votes

---
Tags: formal-languages, context-free, formal-grammars, normal-forms, derivation
---


# Question
Title: What is the optimal algorithm for merging an arbitrary number of convex hulls?
Preparata & Shamos in "Convex Hulls: Basic Algorithms" (1985), give a linear algorithm for merging two convex hulls in $O(n+m)$ time, where $n$ and $m$ are the numbers of vertices in each input hull. Now, if you had a third convex hull to merge of size $l$, you could do that in $O(x+l)$ time, where $x \le n + m$, which should generalize to finding the merge of an arbitrary number of hulls in $O(N)$ time where $N$ is the total number of vertices in all the hulls to be merged.

However, this suggests an obvious $O(N)$ algorithm for finding the convex hull of an arbitrary set of points: iterate through the vertices once to group them into arbitrary triangles, then merge them all in $O(N)$ time.

But finding the convex hull of an arbitrary point set is supposed to have a lower bound of $O(n\log h)$, and I feel like, if it is correct, this construction is too obvious to have been missed for the last 40-ish years!

So, what have I gotten wrong, and what is the most efficient way to merge convex hulls? Does it make a difference if all members of the initial set of convex hulls are non-overlapping?

# Answer
> 2 votes
the result will not be linear.

Doing the merge between partial result and the next hull will be $O(x\_{i-1}+m\_i)$ where $x\_{i-1}$ is the amount of points in the partial result.

So doing the merge iteratively means you end up with $$O(\sum{(x\_{i-1}} + {m\_i}))$$ $$O(\sum{x\_{i-1}} + \sum{m\_i})$$

that first sum of $x\_i$ will count the resulting points multiple times. This leads to a super linear algorithm up to quadratic in the worst case

To prove this last bit let's create an input set that is a convex hull. Doing your proposed iteration means that $x\_i$ grows linearly and $\sum{x\_{i}} = O(n^2)$

---
Tags: algorithm-analysis, computational-geometry, convex-hull
---


title: Is ANF-SAT P or NP?

text:
# Question
Title: Is ANF-SAT P or NP?
Given a finite set of equations in ANF, for example: $$ \begin{cases} (x\_1 \land x\_2) \oplus (x\_1 \land x\_3 \land x\_4) \oplus 1 = 0 \\ x\_3 \oplus (x\_2 \land x\_3 \land x\_4) = 0 \\ (x\_1 \land x\_4) \oplus (x\_1 \land x\_2) \oplus (x\_3 \land x\_4) = 0 \end{cases} $$

Is this P or NP?

The only assumption is that number of variables is finite.

I know it can be converted to CNF and become NP-Complete, but I can't find an algorithm for converting a general ANF to CNF which is P (so this does not imply it is NP-Complete)

This is also different from XOR-SAT as it is not linear and so Gaussian elimination is not an option.

The answer might be using Schaefer's dichotomy theorem, but I'm not sure if it applies or not.

This is similar to this question but the OP was not clear about question and there is also no clear answer, so I'm asking a clear one here.

# Answer
If you are asking about the problem where the input is a system of equations in ANF (algebraic normal form) and the output is whether the system of equations is satisfiable, this problem is NP-complete.

There is a reduction from 3SAT. Suppose we have a 3CNF formula $\varphi = C\_1 \land \cdots \land C\_m$, where $C\_i$ is the $i$th clause in $\varphi$, with variables $x\_1,\dots,x\_n$. We'll create a system of ANF equations that are satisfiable iff $\varphi$ is satisfiable, as follows.

First, let's take care of any negations in $\varphi$. For each variable $x\_i$, introduce another variable $y\_i$, along with the ANF equation

$$1 \oplus x\_i \oplus y\_i = 0.$$

Then, we can replace each negated literal $\neg x\_j$ in $\varphi$ with $y\_j$. In this way we obtain a 3CNF formula with only non-negated literals.

Next, we will introduce one ANF equation per clause, as follows. Introduce variables $z\_1,\dots,z\_m$. Suppose clause $C\_i$ has the form $a \lor b \lor c$ (after removing negations). Then we will generate the ANF equation

$$z\_i + abc + ab + bc + ac + a + b + c = 0.$$

Notice that this forces $z\_i$ to be true iff clause $C\_i$ is satisfied.

Finally, add the ANF equation

$$1 + z\_1 z\_2 \cdots z\_m = 0.$$

This forces all of the $z\_i$ to be true, i.e., all of the clauses $C\_i$ to be satisfied.

Now the system of all ANF equations generated in this way is satisfiable, iff $\varphi$ is satisfiable.
> 1 votes

---
Tags: complexity-theory, satisfiability, p-vs-np
---


# Question
Title: Disjoint Set Constant Time Union Operation
I am following a LeetCode tutorial for Disjoint sets I have trouble understanding why the so called "Quick Find" method needs to take O(n) time. I have implemented an data structure that has an optimised Union operation and it is O(1).

```
// Base class for all types of disjoint sets.
class DisjointSet {
public:
  DisjointSet(int n) : _n(n), vertices(new int[n]) {
    for (int i = 0; i < n; i++) {
      vertices[i] = i;
    }
  }

  /* Finds the root node of a given vertex */
  virtual int find(int vertex) const = 0;

  virtual void union_(int vertex1, int vertex2) const = 0;

  bool connected(int v1, int v2) const {
    return find(v1) == find(v2);
  }
protected:
  int _n;
  int* vertices;
};

```

And the concrete implementation:

```
class FastUnionSlowFindSet : public DisjointSet {
public:
    FastUnionSlowFindSet(int n) : DisjointSet(n) {}

    int find(int vertex) const {
      while (vertices[vertex] != vertex) {
        vertex = vertices[vertex];
      }

      return vertex;
    }

    void union_(int v1, int v2) const {
      vertices[v2] = v1;
    }
  };

```

The idea is that we are keeping track of each vertex's parent and when finding we are going 'up' until we have a vertex whos parent is itself. For the union operation we are just changing the parent of the second node and the find will work because it is going one parent at a time.

Why do we need to check for the rank and whether the roots are the same in the official implementation? I fail to see the logic discrepancy in my approach.

# Answer
Unfortunately, your implementation of disjoint sets does not work.

For example, consider the following calling sequence.

```
s = FastUnionSlowFindSet(3);

s.union_(0,1);
s.union_(2,1);

```

After two union operations, all three vertices `0, 1, 2` should be in the same set.

However, the only relation we have is `vertices[1] = 2`, as it has overwritten `vertices[1] = 0`. So `s` contains two disjoint sets, `{1, 2}` and `{0}`.

---

To avoid such a bug, it is necessary to implement `union_` as something like the following.

```
void union_(int v1, int v2) const {
    vertices[find(v2)] = find(v1);
}

```
> 0 votes

---
Tags: disjoint-sets
---


# Question
Title: Algorithm that finds 4 "O"s or 4 "X"s on a diagonal, horizontal, or vertical
My algorithm homework revolves around matching 4 `"O"`'s or 4 `"X"`'s on a diagonal, horizontal, or vertical. Hopefully that makes sense...

This is what the data looks like below (2D tuples) where I need to recreate a function that returns `"O"` or `"X"` or `False` depending on what is found.

```
xwins = ((None, None, None, None, None, None, None),
         (None, None, None, None, None, None, None),
         (None, None, None, None, "X" , None, None),
         (None, None, None, "X" , "O" , "O", None),
         (None, "O" , "X" , "X" , "O" , "X", None),
         ("O" , "X" , "O" , "O" , "O" , "X" , "X"))

owins = ((None, None, None, None, None, None, None),
         (None, None, None, None, None, None, None),
         ("O" , "O" , "O" , "O" , None, None, None),
         ("O" , "X" , "X" , "X" , None, None, None),
         ("X" , "X" , "X" , "O" , "X" , None, None),
         ("X" , "O" , "O" , "X" , "O" , None, None))

nowins =(("X" , "X" , None, None, None, None, None),
         ("O" , "O" , None, None, None, None, None),
         ("O" , "X" , "O" , "O" , None, "O" , "O" ),
         ("O" , "X" , "X" , "X" , None, "X" , "X" ),
         ("X" , "X" , "X" , "O" , "X" , "X" , "O" ),
         ("X" , "O" , "O" , "X" , "O" , "X" , "O" ))

```

Can someone give me a tip on if I should change the data structure? Originally I went at this creating a numpy array out of the data but am having a hard time dealing with the `None` items in numpy as well as trying to convert the `X` and `O` strings to an int...and now I don't know what to do...need to start over from scratch.

Would anyone have any tips or pseudo-code I can glance at, not solve this but some tips would be useful what data structure to use and methods to the madness, ha. What sort of search algorithm would the solution be considered? Not a lot of wisdom here...

# Answer
As suggested in comments, the task can be done directly without having to modify values to ints or change the structure of the input.

Input: A tuple `A` of `n` rows and `m` columns.
Output: Whether there is matching $4$ "O"'s or 4 "X"'s on a diagonal, horizontal, or vertical line.
Procedure:

```
# horizontal lines
For i in range(n):
    For j in range(m-3):
        Find if A[i][j], A[i][j+1], A[i][j+2], A[i][j+3] are 4 "0"s or 4 "X"s. Return accordingly if yes.

# vertical lines
For j in range(m):
    For i in range(n-3):
        Find if A[i][j], A[i+1][j], A[i+2][j], A[i+3][j] are 4 "0"s or 4 "X"s. Return accordingly if yes.

# diagonal lines
For i in range(n-3):
    For j in range(m-3):
        Find if A[i][j], A[i+1][j+1], A[i+2][j+2], A[i+3][j+3] are 4 "0"s or 4 "X"s. Return accordingly if yes.

# other diagonal lines
For i in range(3, n):
    For j in range(m-3):
        Find if A[i][j], A[i-1][j+1], A[i-2][j+2], A[i-3][j+3] are 4 "0"s or 4 "X"s. Return accordingly if yes.

Return False, since no $4$ "O"'s nor 4 "X"'s has been found.

```

One common difficulty is how we can figure out the ranges of the possible indices of the starting "O" or "X".

The basic technique is, for example, if `A[i-3][j+3]` will be used, then it means "0 \<= i-3 \< n" and "0 \<= j+3 \< m", which means "3 \<= i \< n+3" and "-3 \<= j \< m -3". Together with "0 \<= i \< n" and "0 \<= j \< m", we have "3 \<= i \< n" and "0 \<= j \< m-3". That is how we can write "i in range(3, n)" and "j in range(m-3)" in the case of "other diagonal lines".
> 0 votes

# Answer
There is a way, with a little pre-processing that you can do each test in a constant $O(1)$ number of operations, assuming that you have large enough numbers that can store many bits.

---

You can actually store the values as bits:

* Store X's as 11
* Store O's as 00
* Store None as 01.

We will store the entire table as a string of bits this way, with padding depending on whether there are more rows or columns. The idea is that, to detect a row of X's, you will shift the table to the right. For example, suppose our table is the following:

$$\begin{array}{ccc} X & X & O \\ X & X & \text{None} \\ O & O & \text{None} \end{array}$$

We encode the table as the bits:

$$\begin{array}{ccc} 11 & 11 & 00 \\ 11 & 11 & 01 \\ 00 & 00 & 01 \end{array}$$

We have to then pad the table with extra "None" values (or 01):

$$\begin{array}{cccc} 11 & 11 & 00 & 01 \\ 11 & 11 & 01 & 01 \\ 00 & 00 & 01 & 01 \\ \end{array}$$

Now, the next step is to "wrap" the 0's and 1's around, to create a single string. For example, the table above becomes

$$\begin{array}{ccc} \underbrace{11 \\; 11 \\; 00 \\; 01}\_\text{row 1} & \underbrace{11 \\; 11 \\; 01 \\; 01}\_\text{row 2} & \underbrace{00 \\; 00 \\; 01 \\; 01}\_\text{row 3} \\ \end{array}$$

Let's say we want to detect if there is a column with 2 O's in it. We first shift this bit string to the right by 2 bits, and perform a logical "and" or what is called conjunction:

$$\begin{array}{ccccc} 11 \\; 11 \\; 00 \\; 01 & 11 \\; 11 \\; 01 \\; 01 & 00 \\; 00 \\; 01 \\; 01 & & \text{original string}\\ \land \\; \land \\; \land \\; \land & \land \\; \land \\; \land \\; \land & \land \\; \land \\; \land \\; \land & & \\ 01 \\; 11 \\; 11 \\; 00 & 01 \\; 11 \\; 11 \\; 01 & 01 \\; 00 \\; 00 \\; 01 & 01 & \text{shifted string}\\ \hline 11 \\; 11 \\; 11 \\; 01 & 11 \\; 11 \\; 11 \\; 01 & 01 \\; 00 \\; 01 \\; 01 & 01 & \text{RESULT}\\ \end{array}$$

Then we perform a logical "or", also known as disjunction, with a string of all "10" values, which will convert the remaining "None" values to "11":

$$\begin{array}{ccccc} 11 \\; 11 \\; 11 \\; 01 & 11 \\; 11 \\; 11 \\; 01 & 01 \\; 00 \\; 01 \\; 01 & 01 &\text{previous result}\\ \lor \\; \lor \\; \lor \\; \lor & \lor \\; \lor \\; \lor \\; \lor & \lor \\; \lor \\; \lor \\; \lor & \lor & \\ 10 \\; 10 \\; 10 \\; 10 & 10 \\; 10 \\; 10 \\; 10 & 10 \\; 10 \\; 10 \\; 10 & 10 & \text{row of "10"s}\\ \hline 11 \\; 11 \\; 11 \\; 11 & 11 \\; 11 \\; 11 \\; 11 & 11 \\; 10 \\; 11 \\; 11 & 11 & \text{FINAL RESULT}\\ \end{array}$$

Finally, compare the bit string to a string of all "11" values. Note that there is a single zero in the string, which indicates that there are two "O" = "00" values next to each other.

To see how this works, we are taking bit values and performing some logic on them:

$$\begin{array}{c|c|c} \text{original value} & \text{value and "11"} & \text {next value and "10"} \\ \hline 00 & 00 & 01 \\ 01 & 01 & 11 \\ 11 & 11 & 11 \end{array}$$

To detect X = "11" values, we simply have to perform a logical and (conjunction) with "10":

$$\begin{array}{c|c} \text{original value} & \text{value and "10"} \\ \hline 00 & 00 \\ 01 & 00 \\ 11 & 10 \end{array}$$

Then we simply compare the string with a string of all zeros, and if there are any 1's in the string, we know that there are two X="11" values next to each other.

You can repeat this operation if there is more padding. This will allow you to compare 3, 4, or more positions in a line.

For different directions, simply pad and shift accordingly.

---

One point to make is that you can limit the number of extra padding bits slightly. If there are more rows than columns, you want to pad to the left and to the right, and below. Then you can test both diagonal directions by shifting down, since there will be extra padding below.

Otherwise, pad above, below, and to the right. Then test both diagonal operations by shifting right, since there will be extra padding on the right.
> 1 votes

# Answer
I realized that you can actually detect a line of at least $n$ "X" values in $\Theta \left( \lceil \log{(n)} \rceil \right)$ operations, and the same with $n$ "O" values.

---

The idea is to keep two "tables", and you perform tests by bit shifts. In one table, you record a bit 1 for every "X" value, and a 0 for "O" values, "None", and padding. In the other table, you record a bit 1 for every "O" value, and a 0 for "X" values, "None", and padding. Now we just have to detect $n$ ones in a row, either horizontally, vertically, or diagonally.

So on to the task of detecting $n$ ones in a row. We will first show how to detect at least $2^y$ bits in a row that are all equal to 1.

Say the string has a sequence of $2^y$ ones (in a row). If we shift the sequence by $2^{y-1}$ and take the bitwise "and" operation, logical conjunction, we will get a sequence that has at least $2^{y-1}$ ones in a row. Here is this situation:

$$\begin{array}{cccc} 111 \dots 111 & 111 \dots 111 & ??? \dots ??? & \text{original bit string}\\ \land & \land & \land \\ ??? \dots ??? & 111 \dots 111 & 111 \dots 111 & \text{shifted bit string}\\ \hline ??? \dots ??? & 111 \dots 111 & ??? \dots ??? & \text{RESULT} \end{array}$$

...Here we don't care about the bits that are question marks. The takeaway is that the middle bits will be all ones, and that there are exactly $2^{y-1}$ of them in the middle. If any of the rightmost $2^{y-1}$ bits are zero, then the top bit string will force one of the bits in the middle of the result to be zero. If any of the leftmost $2^{y-1}$ bits are zero, the bottom bit string will force at least one of the bits in the middle result to be zero.

So now we have a bit string that will contain $2^{y-1}$ bits in a row if and only if the original bit string contained at least $2^y$ bits in a row. So now we repeat this step by logical conjunction with (the result string shifted by $2^{y-2}$. So we use a loop to do this until we are left with a single bit as the result. It is 1 if and only if there were at least $2^y$ 1's in a row in the original bit string.

This only works if there are at least $2^y$ 1's in a row, for some $y$. So how do we use this for other values?

Say we have $n = 2^y + c$ for some $c$. We first modify the bit string by turning $2^y$ ones into $2^y$ zeros.

The function essentially adds 0 to each side of a string of ones while shortening the string by 1, then 00 to each string of ones while shortening the string by another 2 ones, then 0000 by shortening the string by another 4 ones, etc.

To do this, observe the general step:

$$\begin{array}{cc} 00001111110000???? & \text{original bit string}\\ 000000001111110000 & \text{shifted bit string}\\ \hline 000000001100000000 & \text{RESULT} \end{array}$$

After we have added enough zeros to the string, we proceed similarly to the task when there are (possibly) $2^y$ ones in a row. Assume that we are testing for at least $n = 2^y+c$ ones in a row. We will have already switched $2^{y-1}$ ones into zeros, so we are left with $n\_1 = 2^{y-1} + c$ or more ones. We will "half" the number of (possible) ones. We do this by shifting by $\lfloor n\_1 / 2 \rfloor$ and conjoining the values, so that we are left with $n\_2 = \lfloor n\_1 / 2 \rfloor$ or more possible ones. Then we proceed like the last step, we shift by $\lfloor n\_2 / 2 \rfloor$ and conjoin. Repeat until there is only one value left, similarly to above.

The function of padding with zeros takes $\Theta \left( \lceil \log{(n)} \rceil \right)$ operations, and the combining of possible ones also takes time $\Theta \left( \lceil \log{(n)} \rceil \right)$, so the total time is $\Theta \left( \lceil \log{(n)} \rceil \right)$.

---

The rest of the algorithm functions in a way similar to my other answer. If you want to find only the rows that have *exactly* $n$ values in a row, find at least $n$ values in a row, and subtract the result with at least $n-1$ values in a row.
> 0 votes

# Answer
Final Answer in Python which could probably be written better:

```
def check_winner(A):

    n = 6 # rows
    m = 6 # columns

    Os = ["O","O","O","O"]
    Xs = ["X","X","X","X"]

    # horizontal lines
    row_check = []
    for i in range(n):
        for j in range(m-2):

            row_check.append(A[i][j])
            row_check.append(A[i][j+1])
            row_check.append(A[i][j+2])
            row_check.append(A[i][j+3])

            if row_check == Os:
                return "O"

            if row_check == Xs:
                return "X"

            row_check.clear()

    # vertical lines
    col_check = []
    for j in range(m + 1):
        for i in range(n-2):

            col_check.append(A[i][j])
            col_check.append(A[i+1][j])
            col_check.append(A[i+2][j])

            #print(col_check)

            if col_check == Os:
                return "O"

            if col_check == Xs:
                return "X"

            col_check.clear()

    # diagonal lines
    diag_check = []
    for i in range(3):
        for j in range(4):

            diag_check.append(A[i][j])
            diag_check.append(A[i+1][j+1])
            diag_check.append(A[i+2][j+2])
            diag_check.append(A[i+3][j+3])

            if diag_check == Os:
                return "O"

            if diag_check == Xs:
                return "X"

            diag_check.clear()

    # diagonal lines
    diag_check2 = []
    for i in range(3):
        for j in range(4):

            diag_check2.append(A[i][j+3])
            diag_check2.append(A[i+1][j+2])
            diag_check2.append(A[i+2][j+1])
            diag_check2.append(A[i+3][j])

            if diag_check2 == Os:
                return "O"

            if diag_check2 == Xs:
                return "X"

            diag_check2.clear()

#The code below tests your function on three Connect-4
#boards. Remember, the line breaks are not needed to create
#a 2D tuple; they're used here just for readability.
xwins = ((None, None, None, None, None, None, None),
         (None, None, None, None, None, None, None),
         (None, None, None, None, "X" , None, None),
         (None, None, None, "X" , "O" , "O", None),
         (None, "O" , "X" , "X" , "O" , "X", None),
         ("O" , "X" , "O" , "O" , "O" , "X" , "X"))

owins = ((None, None, None, None, None, None, None),
         (None, None, None, None, None, None, None),
         ("O" , "O" , "O" , "O" , None, None, None),
         ("O" , "X" , "X" , "X" , None, None, None),
         ("X" , "X" , "X" , "O" , "X" , None, None),
         ("X" , "O" , "O" , "X" , "O" , None, None))

nowins =(("X" , "X" , None, None, None, None, None),
         ("O" , "O" , None, None, None, None, None),
         ("O" , "X" , "O" , "O" , None, "O" , "O" ),
         ("O" , "X" , "X" , "X" , None, "X" , "X" ),
         ("X" , "X" , "X" , "O" , "X" , "X" , "O" ),
         ("X" , "O" , "O" , "X" , "O" , "X" , "O" ))

print(check_winner(xwins))
print(check_winner(owins))
print(check_winner(nowins))

```
> 0 votes

---
Tags: algorithms, arrays, python
---


# Question
Title: Is there a notation for boolean algebra complexity?
To represent complexity of an algorithm, Computer Scientist is used to using big-O notation.

How about complexity of boolean algebra?

Boolean algebra is commonly used in digital circuit design with using logic gates, practically useful in FPGA programming. Speaking about logic gates circuit, This topic maybe looks like Computer Engineering question, but I think it's okay to ask in Computer Science. Actually Computer Scientist and Computer Engineer doesn't need to know about Electrical Engineering at all to know about it, because logic gates already an abstraction of electrical stuff, all we just need to know is `Input->Logic->Output` where Input/Output are just bunch of `0` and `1`.

What I mean about complexity of boolean algebra is actually complexity of logic gates circuit. As we know, if an input propagate to a logic gate for example a `NOT` gate, it needs time to propagate, if there's `NOT` gate again (more step), then more time to consume, hence that's circuit is going to complex.

Look this case for example,

* #1 `Z = NOT(X)` is equivalent with
* #2 `Z = NOT(NOT(NOT(X)))`
* Where Z is output and X is an input.

But they are different in complexity. Practically (eg: FPGA programming), #2 is slower than #1 due to three steps to propagate while #1 is just one step to pass.

# Answer
This is called *Circuit Complexity*: https://en.wikipedia.org/wiki/Circuit\_complexity

> The size of a circuit is the number of gates it contains and its depth is the maximal length of a path from an input gate to the output gate.
>
> There are two major notions of circuit complexity. The *circuit-size* complexity of a Boolean function f is the minimal size of any circuit computing f. The *circuit-depth* complexity of a Boolean function f is the minimal depth of any circuit computing f.

These are usually measured in big-O notation. Since the difference in the number of gates (1 vs 3) in your example is only a constant, the two are considered the same w.r.t. big-O complexity.
> 1 votes

---
Tags: complexity-theory, boolean-algebra, boolean-complexity
---


# Question
Title: Time complexity for finding the number of triangles in a graph
In our class we considered the problem written in the title. The below given time complexities where simply given, but not derived or explained. Therefore I tried myself to derive them, while I using math or simply intuition. I am able to explain, how one of the complexities comes about, but not the other one. I haven't the slightest clue as to how, and I have been trying for hours now to understand that. So if someone could help me with a step by step explanation as to how the 2nd time complexity is what it is, I'd very much appreciate it.

We have a Graph $G=(V,E)$ where $|V|=n$ (nr. of nodes) and $|E|= m$ (nr.of edges)

We use the following pseudo-code initially, where `G[u][v]` is `true` iff there is an edge between `u` and `v`.

```
 1  function count_triangles (Adjacent Matrix G[][])
 2    count:=0
 3    for u in V do
 4      for v in V do
 5        for w in V do
 6          if (G[u][v] and G[v][w] and G[u][w]) then
 7              counter = counter + 1
 8          end
 9        end
10        end
11      end
12    return count / 6
13  end

```

In the worst case scenario, that of a complete graph, we'd get a time complexity of $\Theta(n^3)$ in order to find all the triangles. The reason being: You have a set of $n$ nodes. You consider an initial one out of $n$. Then for the next one you have $n-1$ possibilities to choose, and for the 3rd one you have $n-2$ possibilities to choose from. That means: $n\*(n-1)\*(n-2)$, which belongs to $\Theta(n^3)$.

Now a second pseudocode was given, as follows:

```
function count_triangles_2 (Adjacent Matrix)

 1  function count_triangles_2 (Adjacent Matrix)
 2    count:=0
 3    for u in V do
 4      for v in V do
 5         if not G[u][v] then continue
 6         for w in V do
 7           if (G[v][w] and G[u][w]) then
 8              counter = counter + 1
 9           end
10         end
11       end
12    end
13    return count / 6
14  end

```

Now regarding this pseudo-code. Like the above one, in the worst case scenario, that of complete graph, the time complexity is the same. But when the graph is thin, i.e the number of edges is linear compared to the nr. of nodes, maybe a bigger value then $n$ but still linear, in this case the time complexity is $\Theta(n\*m)$.

I want to know how the fact that we consider a thin graph, must help me into find $\Theta(n\*m)$. I want to understand the thinking process that goes behind this. How should my view of this problem change, with the information that the graph is thin, where $m\>n$. What I see in the 2nd pseudo-code is that we have 2 for loops, one is nested. The first one iterates at least through $\frac n 2$ elements, and the 2nd loop, iterates at least through $\frac n 2 -1$ elements. This means that we get something proportional to $n^2$.

And one more thing: Initially we said for the 2nd pseudo-code that the time complexity is $\Theta(n^2 + n\*m)$. I understand that this is the case where we have nodes that are not adjacent to other nodes, or that the number of nodes is compare-able to the nr. of edges, because we are having a forest and not a tree. But if we consider the case that the graph is connected and that $m\>n$, then $\Theta(n^2 + n\*m) \rightarrow \Theta(n\*m)$. But as I said, I don't understand how we find $\Theta(n\*m)$.

# Answer
Let us look at the `count_triangles_2`.

The time it takes to run the function is spent mostly on executing line $5, 6, 7, 8, 9$ and $10$.

So, the time-complexity is about $$n\_5 * \text{time}(\text{line 5}) + n\_{678910} * \text{time}(\text{line 6, 7, 8, 9, 10})$$ where $n\_5$ is the number of times line 5 will be executed and $n\_{678910}$ is the number of times lines $6, 7, 8, 9$ and $10$ as a block will be executed.

$n\_5 = n^2$.
$\text{time}(\text{line 5})=\Theta(1)$
$n\_{678910}=2m$ since line 6 will be run iff `(u,v)` is an edge.
$\text{time}(\text{line 6, 7, 8, 9, 10})=\Theta(n)$

Hence, the time-complexity is $$n^2\Theta(1) + 2m\Theta(n)=\Theta(n^2+2mn)=\Theta(mn),$$ where the last step assumes $m\ge n$.
> 1 votes

---
Tags: algorithms, time-complexity, runtime-analysis, loops
---


# Question
Title: proving a step in the proof of regular intersection
Let $L\_1$ be a context-free language and $L\_2$ be a regular language. Then $L\_1 \cap L\_2$ is context-free.

Part of a proof given in the book "Formal languages and automata": Let $M\_{1}=\left(Q, \Sigma, \Gamma, \delta\_{1}, q\_{0}, z, F\_{1}\right)$ be an npda that accepts $L\_1$, $M\_{2}=\left(P, \Sigma, \delta\_{2}, p\_{0}, F\_{2}\right)$ be a dfa that accepts $\mathrm{L}\_{2}$. We construct a push-down automaton $\widehat{M}=\left(\widehat{Q}, \Sigma, \Gamma, \widehat{\delta}, \widehat{q\_{0}}, z, \widehat{F}\right)$ that simulates the parallel action of $M\_{1}$ and $M\_{2}$ : Whenever a symbol is read from the input string, $\widehat{M}$ simultaneously executes the moves of $M\_{1}$ and $M\_{2}$. To this end we let $$ \begin{aligned} \widehat{Q} &=Q \times P \\ \widehat{q\_{0}} &=\left(q\_{0}, p\_{0}\right), \\ \widehat{F} &=F\_{1} \times F\_{2}, \end{aligned} $$ and define $\widehat{\delta}$ such that $$ \left(\left(q\_{k}, p\_{l}\right), x\right) \in \widehat{\delta}\left(\left(q\_{i}, p\_{j}\right), a, b\right) $$ if and only if $$ \left(q\_{k}, x\right) \in \delta\_{1}\left(q\_{i}, a, b\right) $$ and $$ \delta\_{2}\left(p\_{j}, a\right)=p\_{l} . $$ In this, we also require that if $a=\lambda$, then $p\_{j}=\mathrm{p}\_{1}$. In other words, the states of $\widehat{M}$ are labeled with pairs $\left(q\_{i}, p\_{j}\right)$, representing the respective states in which $\mathrm{M}\_{1}$ and $M\_{2}$ can be after reading a certain input string. **It is a straightforward induction argument to show that $$ \left(\left(q\_{0}, p\_{0}\right), w, z\right) \vdash\_{\widehat{M}}^{\*}\left(\left(q\_{r}, p\_{s}\right), \lambda, x\right), $$ with $q\_{r} \in F\_{1}$ and $p\_{s} \in F\_{2}$ if and only if $$ \left(q\_{0}, w, z\right) \vdash\_{M\_{1}}^{\*}\left(q\_{r}, \lambda, x\right), $$ and $$ \delta^{\*}\left(p\_{0}, w\right)=p\_{s} $$**

Now, my question: I am not really sure how to do that "straightforward induction". I thought to do an induction on the length of the string, with the base case being 0. The base case means that we have lambda as our word. For the induction step I thought of assuming that it holds for strings of length n, and proving for strings of length n + 1. Do I have to prove it in both directions separately, or can I do both directions at once? Could someone help me write formally down why this statement is true, even though it seems quite straightforward?

**SOLUTION**:   **SOLUTION IN WORDS**

For the base case, we have 0 steps. The proof just follows from the definition of what 0 steps actually is (doing nothing).

For the inductive case: We say that the statement holds for steps of length n, and proof for steps of length n + 1. We should not say anything about the length of the strings, so they could be of length 0 or longer. From the induction hypotheses we have everything done and have 1 step left. This step is proven by the definition of $\widehat{\delta}$. For the DFA, I made the distinction between lambda-transition and actually consuming a letter.

# Answer
> 1 votes
In order to prove the statement by induction it has to be generalized somewhat. Observe that the current statement refers to final states of the automata involved. To be able to extend arbitrary computations we will have to consider arbitrary states as last state of the computations, so we consider also non-accepting computations.

Also note that the computation ends with no remaining symbols on the input tape. Also that has to be generalized, as we must be able to read a next symbol. Luckily
$(q\_{0}, w, z) \vdash\_{M\_{1}}^{\*} (q\_{r}, \lambda, x)$ if and only if $(q\_{0}, w{\cdot} u, z) \vdash\_{M\_{1}}^{\*} (q\_{r}, u, x)$: the computation does not change if we add more symbols on the input tape.

For the induction it is probably best to use the number of steps used by both pushdown automata. The length of the input word disregards long computations on the empty string possible for a pda.

The inductive step probably strings this together as follows, but I did try not all details.

$$ \left(\left(q\_{0}, p\_{0}\right), w{\cdot}a, z\right) \vdash\_{\widehat{M}}^{\ell}\left(\left(q\_{r}, p\_{s}\right), a, x\right) \vdash\_{\widehat{M}}\left(\left(q'\_{r}, p'\_{s}\right), \lambda, x'\right) $$ if and only if $$ \left(q\_{0}, w{\cdot}a, z\right) \vdash\_{M\_{1}}^{\ell}\left(q\_{r}, a, x\right) \vdash\_{M\_{1}}\left(q'\_{r}, \lambda, x'\right), $$ $$ \delta^{\*}\left(p\_{0}, w\right)=p\_{s},\text{ and } \delta^{\*}\left(p\_{s}, a\right)=p'\_{s} $$

Probably it is best to have "if and only if" in the inductive hypothesis, but in the proof for the additional step check both directions separately, unless upon writing the proof arguments turn out to be symmetric.

---
Tags: formal-languages, regular-languages, automata, context-free
---


# Question
Title: Why do we retain A->.aA,a/b in I3 stage of LALR parsing of S->AA, A->aA|B?
The question is LALR(1) parsing of the following:

```
S->AA
A->aA
A->b

```

The link to the question is on this page:https://www.javatpoint.com/lalr-1-parsing

My question concerns I3, where despite a being read there is another production A-\>aA, a/b, where the a is *not* read.

I wish to know the reasons for this. If anyone can clarify it to me, please help. Why is this extra production there?

# Answer
Summarizing the comment thread:

The state $I\_3$ is reached by processing a SHIFT action on the item $A\to \bullet a A$, resulting in the item $A\to a\bullet A$. The original item, with the $\bullet$ at the beginning of the right-hand side, is not "retained". But the new item has the $\bullet$ immediately before the non-terminal $A$ (which happens to be the same non-terminal, but that's irrelevant). So when closure is performed on the itemset, the productions for $A$ are added, with the $\bullet$ at the beginning of each one. Thus, the itemset for $I\_3$ will include both the shifted $A\to a\bullet A$ and a new $A\to \bullet aA$, along with the other production for $A$, $A\to \bullet b$.
> 1 votes

---
Tags: compilers, parsers
---


# Question
Title: Lambda body reduction in Lambda calculus
I'm studying lambda calculus with De Bruijn indexes, and have these functions.

$$ zero := (\lambda\lambda.1)\\ succ := (\lambda\lambda\lambda.2 (3 2) 1) $$

Now I want an algorithm to reduce $succ\ zero$

$$ \beta\ succ\ zero \\ \beta\ (\lambda\lambda\lambda.2 (3 2) 1)\ (\lambda\lambda.1)\\ \beta\ \lambda\lambda.2 ((\lambda\lambda.1) 2) 1 $$

where $\beta$ is the beta reduction function.

I tried to come up with an algorithm but it stops here because the head of the expression is not an application it wouldn't go further. I will continue the reduction that I like to implement

$$ \beta\ \lambda\lambda.2 ((\lambda\lambda.1) 2) 1\\ \beta\ \lambda\lambda.2 (\lambda.1) 1\\ \beta\ \lambda\lambda.2 1\\ $$

The problem that I'm facing is that in my program the application is a data type with two parameters `App term term` and this term $2 (\lambda.1) 1$ corresponds to this in code `App (App 2 (Lamb 1 1)) 1)`. By recursing on this structure I will never match the term $(\lambda.1) 1$ and will never be able to reduce it

I need this to compare numbers, for example

$$ one := (\lambda\lambda.2 1) \\ one' := \beta\ (succ\ zero) $$

If I want $one$ to be syntactically equal to $one'$ I need to be able to normalize the function body, any ideas on how to approach this?

# Answer
My definition of `succ` is wrong, the correct is $\lambda\lambda\lambda.2 (3 2 1)$ not $\lambda\lambda\lambda.2 (3 2) 1$
> 1 votes

# Answer
The PL Zoo has a programming language lambda which uses de Bruijn indices (see the type `term`) and explicit substitutions (described here) to implement reduction, see norm, which actually implements four different strategies, depending on what flags it is given.
> 1 votes

---
Tags: lambda-calculus
---


# Question
Title: If two states of a DFA are k-equivalent and k+1 equivalent
Consider a DFA $A$ and $k\geq 0$. For states $q$ and $p$ of $A$, we say that $p\equiv\_k q$ when $p$ and $q$ agree on all words of length at most $k$; that is, $p\equiv\_k q$ when for all words $w$ of length at most $k$, it holds that $p$ has an accepting run on $w$ iff $q$ has an accepting run on $w$. Then, we say that $q\equiv p$ when $q\equiv\_k p$ for all $k\geq 0$.

Is the following claim correct?

**Claim:** Consider a DFA $A$. If $q$ and $p$ are states of $A$ such that
$p\equiv\_kq$ and $p\equiv\_{k+1}q$, for some $k$, then $p \equiv q$.

I don't think so, because if the minimization algorithm can continue, $q$ and $p$ might be separate at a later iteration, am I correct?

# Answer
Right, but you need to suggest a counter-example. Saying that the states might separate in the operation of a minimization algorithm is not a proof.

$p\equiv\_k q$ means that for all words $w$ of length at most $k$, there is an accepting run from $p$ on $w$ iff there is an accepting run from $q$ on $w$. In words, there is no word of length at most $k$ that *separates* between $q$ and $p$. Back to your claim, can you suggest a DFA that has two states that are $k$-equivalent and $(k+1)$-equivalent, yet are not $(k+2)$-equivalent?

**Hint:** Start by considering $k=0$ and note that all accepting states are $0$-equivalent, and all rejecting states are $0$-equivalent.
> 1 votes

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


# Question
Title: show for any Languages $L_1$ and $L_2$ exists a Language $L$ with $L_1 \leq_{log} L$ and $L_2 \leq_{log} L$
This is an old exam question, but I never found a solution or somebody who could explain it to me. Here is the problem statement:

Let $\Sigma$ be an alphabet with |$\Sigma$| $\geq 2$. Show that for any Languages $L\_1 \subseteq \Sigma^\*$ and $L\_2 \subseteq \Sigma^\*$ there is a Language $L \subseteq \Sigma^\*$ and the following holds true: $L\_1 \leq\_{log} L$ and $L\_2 \leq\_{log} L$.

So $L\_1$ and $L\_2$ are both logspace reducible to $L$

This question gives just 5 out of 60 points for the correct answer, so I assume it shouldn't be too hard to solve. But I don't have any idea on how to approach this problem...

Thank you!

# Answer
Just take $L = \\{ 0x \mid x \in L\_1 \\} \cup \\{ 1y \mid y \in L\_2\\}$.
> 1 votes

---
Tags: reductions
---


title: Loop Transforms to Increase Parallelism

text:
# Question
Title: Loop Transforms to Increase Parallelism
I have the need to parallelize as much as I can (in order to make it run fast) the following part of an algorithm:

```
do i=1, n
  do j=1, n
    A[i, j] = A[i-4, j-4] + A[i-3, j-3] + B[i, j]
  end do
end do

```

I was thinking that the best i could do here is a loop skewing (but with what factor?) and loop interchange that would allow me to finally have a DOALL on the inner loop. Any feedack and help regarding those thoughts?

# Answer
This is very similar in principle to an h.264 decoder where each cell depends on the cell above and the cell to the left.

Let k = i + j. Then some A with i + j = k only depends on A with i + j = k-8 and i + j = k-6. Assuming your indices start at 1, you need to define the result for i \<= 4, j \<= 4 first.

Loop for k = 2 to 2n. For each k, loop for i, and let j = k - n; you restrict the range for the i's is so that 1 ≤ j ≤ n. Then all the results for k to k+5 can be calculated in parallel.

```
do k = 2 to 2n
    do i = max (1, k - n) to min (n, k-1)
        A[i, k - i] = A[i-4, k - i - 4] + A[i-3, k - i - 3] + B[i, k - i]
    end do
end do

```

The inner loop can be executed fully in parallel because setting A\[i, j\] only affects results for k+6. Just make sure the calculation is finished before you start the loop for k + 6. It should also be reasonably cache friendly. And make sure you handle i, j ≤ 4 correctly.
> 1 votes

# Answer
This is an incomplete question because you have no base case; `A[-3, -3]` is not defined, for example. But let's assume we're looking at a window into a larger array, so those values have some consistent, distinct and independent value.

Denote those predetermined values with `#`, and look at the top-left corner. The values we can fill in are those three topmost rows and three leftmost columns, denoted by `·`.

```
# # # # # # # # # # # # # #
# # # # # # # # # # # # # #
# # # # # # # # # # # # # #
# # # # # # # # # # # # # #
# # # # · · · · · · · · · ·
# # # # · · · · · · · · · ·
# # # # · · · · · · · · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·

```

Doing those in parallel means that you need to take `n / 3` sequential steps. Since the matrix is square, exclusively going down balances the costs better, but still gives you `n / 3` sequential steps with parallelism of `3n`.

This is remarkably excessive for a typical CPU for significantly sized `n`; rather you should be streaming memory into SIMD operations as fast as possible. You can do a straightforward `N`-wide SIMD loop over the x-axis.

```
A[i:i+N, j] = A[i-4:i-4+N, j-4] + A[i-3:i-3+N, j-3] + B[i:i+N, j]

```

This probably won't max out your bandwidth entirely, but it will get pretty darn close and it's unlikely you can get more from a multicore algorithm, though you are free to try partitioning the work along diagonals.
> 0 votes

---
Tags: algorithms, parallel-computing, loops
---


# Question
Title: How can I understand the proof of the VC dimension of half-spaces in d-dimensions?
**Statement :** A half space is set of all points on one side of a linear separator, i.e., a set of the form $\\{x \mid w^{T}x \ge t\\}$. The VC-dimension of half spaces in $d$-dimensions is at least $d+1$.

**Proof Idea.** There exists a set of size $d+1$ that can be shattered by half-spaces. Select the $d$ unit-coordinate vectors plus the origin to be the $d+1$ points. Suppose $A$ is any subset of these $d+1$ points. Without loss of generality assume that the origin is in $A$. Take $0-1$ vector $w$ which has $1$'s precisely in the coordinates corresponding to vectors not in $A$. Clearly $A$ lies in the half-space $w^{T}x\le 0$ and complement of $A$ lies in the complementary half-space.

The overall idea is to show that a set of size $d+1$ can be shattered. My understanding is that they are adding origin into the set of points. So the set size will be $d+1$ but I am not getting the last two lines:

> Take $0-1$ vector $w$ which has $1$'s precisely in the coordinates corresponding to vectors not in $A$. Clearly $A$ lies in the half-space $w^{T}x\le 0$ and complement of $A$ lies in the complementary half-space.

# Answer
> 1 votes
Let us understand the proof by example.

Suppose $d=3$.
Select $d+1=4$ points, which are the 3 unit-coordinate vectors $(1,0,0)$, $(0,1,0)$, $(0,0,1)$ and the origin $(0,0,0)$.
Let $C$ be the set of these 4 points.

Suppose $A$ is any subset of these 4 points. There are two cases.

* The origin is not in $A$.
Let $0{-}1$ vector $w$ be the sum of all points (vectors) in $A$. For examples, if $A$ contains $(1,0,0), (0,0,1)$, then $w=(1,0,0) + (0,0,1)=(1,0,1)$.
Then $A = C\cap \\{x \mid w^{T}x \ge 1\\}$.
* The origin is in $A$.

> Take $0{-}1$ vector $w$ which has $1$'s precisely in the coordinates corresponding to vectors not in $A$.

For example, if $A=\\{(1,0,0\\}$, then $A$ does not contain $(0,1,0)$ nor $(0,0,1)$.

+ $w$ has $1$ at second coordinate since $(0,1,0)$ is not in $A$.
    + $w$ has $1$ at third coordinate since $(0,0,1)$ is not in $A$.

So $w=(0,1,1)$. (This construction of $w$ is the same as letting $w$ be the sum of all points not in $A$.) Check that

> Clearly $A$ lies in the half-space $w^Tx\le0$ and complement of $A$ lies in the complementary half-space.

Note that $\\{x\mid w^Tx\le0\\}$ is indeed of the form $\\{x \mid w^{T}x \ge t\\}$ since $\\{x\mid w^Tx\le0\\}=\\{x\mid (-w)^Tx\ge0\\}$.

---

> Without loss of generality assume that the origin is in $A$.

This "without loss of generality" does not imply that author will adapt the case of the origin not in $A$ by "adding origin into" the subset $A$.

It means "let us deal with one of the cases. The other case is more or less similar." simply.

---
Tags: machine-learning, vc-dimension
---