# Question
Title: Breakdown of the Space Hierarchy Theorem
Say that we have two deterministic space complexity classes $SPACE(n^k)$ and $SPACE(f(n))$ where $f(n) = n^{k-1}$ when $n$ is odd and $f(n) = n^{k+1}$ when $n$ is even. Obviously, if $f(n)$ were always $n^{k+1}$, we would able to say $SPACE(n^k) \subseteq SPACE(f(n))$ by the Space Hierarchy Theorem, and I believe that as $n$ grows we can still generally say $SPACE(n^k) \subseteq SPACE(f(n))$ (correct me if I'm wrong), but given the condition when $n$ is odd, do we just have to say that always $SPACE(n^k) \neq SPACE(f(n))$?

# Answer
Here is a strengthening of the space hierarchy theorem.

> Suppose that $f(n) \geq \log n$ is space-constructible, that $g(n) = o(f(n))$, and that $h(n) = g(n)$ infinitely often (that is, for infinitely many $n$). Then $\mathrm{SPACE}(f(n)) \not\subseteq \mathrm{SPACE}(h(n))$.

Here $\mathrm{SPACE}(f(n))$ consists of all languages decided by multi-tape Turing machines which use $O(f(n))$ space.

**Proof.** We closely follow the Wikipedia proof of the space hierarchy theorem. Let $$ L = \\{ (\langle M \rangle, 1^m) : \text{when $M$ is run on $x = (\langle M \rangle, 1^m)$, it uses $\le f(|x|)$ space and rejects} \\} $$ Here $1^m$ is just $1$ repeated $n$ times, and we encode the input such that its size is *exactly* $C\_M + m$, for some constant $C\_M$ depending only on $M$.

The language $L$ is clearly in $\mathrm{SPACE}(f(n))$. Suppose that it is also in $\mathrm{SPACE}(h(n))$, say accepted by a machine $M$ which uses space $Ch(n)$. Since there are infinitely many $n$ such that $h(n) = g(n)$ and $g(n) = o(f(n))$, we can find $m$ such that $Ch(C\_M + m) = Cg(C\_M + m) \leq f(C\_M + m)$. When running $M$ on $x = (\langle M \rangle, 1^m)$, it uses at most $Ch(|x|) = Cg(|x|) \leq f(|x|)$, and so $(\langle M \rangle, 1^m) \in L$ iff $M$ doesn't accept $(\langle M \rangle, 1^m)$, contradicting the assumption that $M$ computes $L$. $\square$

Using this, you can check that $\mathrm{SPACE}(n^k)$ and $\mathrm{SPACE}(f(n))$, where $f(n)$ is the function defined in your post, are incomparable: none is contained in the other.
> 0 votes

---
Tags: complexity-theory, space-complexity, complexity-classes, memory-hierarchy
---


# Question
Title: Call-by-push-value vs Fine-grain Call-by-value
It seems to me that Fine-grain call-by-value already subsumes CBV and CBN, using lambdas as thunks. What does CBPV improve upon FG-CBV or in what way is it "better"?

# Answer
> 1 votes
Fine-grained CBV does *not* subsume call-by-name.

In Fine-grained CBV, the computations $\Gamma \vdash M: A \rightharpoonup B$ do not satisfy unrestricted $\eta$ equality $$ M \equiv \lambda x. M x$$ because $M$ is interpreted as a computation that performs effects and returns a thunk, so if $M$ is a printing or diverging computation the above equality is violated. Instead we have the call-by-value $\eta$ only, which says that this equality is true if we know $M$ to be a value.

This means for instance we cannot build up the type of two argument functions compositionally and have it satisfy $$A \rightharpoonup A' \rightharpoonup B \cong A \times A' \rightharpoonup B$$

However, there is some confusion about the terminology "call-by-name". Some treatments allow for observation of termination at function type (such as reduction to weak head normal form), but this is poorly behaved semantically as it admits neither the function $\eta$ nor the boolean/sum/tuple $\eta$. Levy distinguishes between these by calling the latter "lazy", and he shows in the CBPV monograph that lazy semantics *is* subsumed by (fine-grained) CBV. The lazy semantics is roughly what Haskell corresponds to because of `seq` so this does cause some confusion.

---
Tags: lambda-calculus
---


# Question
Title: is Kolmogorov complexity computable on a finite domain?
The proof in the wikipedia article for the uncomputability of Kolmogorov complexity uses the fact that there are strings of arbitrarily large Kolmogorov complexity. What if we restrict to a finite domain so this no longer holds? Specifically, what if I am only interested in strings of length $\le N$, is there an algorithm $M\_N$ for computing Kolmogorov complexity for all these strings? As long as $$ |M\_N| \ge max \\{K(s)| s \in \Sigma^i, i \le N\\}\\,, $$ it seems like it would at least escape the contradiction from Wikipedia.

# Answer
The answer is "yes", i.e., for every *fixed* $N$, there is an algorithm $M\_N$ that, given an input string $s$ (on some fixed alphabet $\Sigma$) of length at most $N$, returns the Kolmogorov complexity of $s$. You might find the argument a bit unsatisfactory though, as it is not constructive.

Let $s\_1, s\_2, \dots$ be the strings in $\bigcup\_{i=0}^N \Sigma^i$ and let $k\_i$ be the Kolmogorov complexity of $s\_i$. $M\_N$ determines which of the (finitely many) strings $s\_i$ matches the input string, and returns $k\_i$. Notice this approach only works because the set of input strings for which we need to answer correctly is finite (since algorithms are required to have a finite amount of instructions).
> 2 votes

---
Tags: kolmogorov-complexity
---


# Question
Title: How do distributed joins work in a distributed relational database system?
I have been looking around for a few days trying to find a clear and concise description of how, at a technical/implementation level, how distributed joins work, but haven't found much. The best so far is in Track Join: Distributed Joins with Minimal Network Traffic. In this though they seem to suggest that every joined attribute is sent over the network to every other node, sort of like this (from another presentation):

Is that really how distributed joins generally work? Say I have 100 billion records per "table" (type), and two tables/types, and want to join on them to find some resulting set of records (along with a filtering condition). "Find all employees where e.department\_id = department.id and department.category is 'design'" sort of thing. If there are billions of both types of records, scattered randomly (through hash-based partitioning) across 100 servers/nodes, how would the join typically work? Would you literally have to send all billions of nodes to every node in the network? That just seems like an enormous waste. What am I not interpreting correctly? Is there no other way to do it?

# Answer
To make effective joins you would need indexes. Indexes could be either local the the data (index is on the same node as data) or global - index is partitioned independently of data.

In a local index case, the coordinator node would send requests to every other node, as the coordinator can not do any better decisions.

In a global index case, the coordinator would first deduct which nodes may have the information and go just there.

At the end of the day, the data needs to be collected at some node to be pre-processed before getting back to the client.

I recommend to dive on this topic: how does ElasticSearch (distributed cluster) executes a query: find all docs with words Alpha and Beta in it. And find top 10, then next 10 etc.
> 1 votes

---
Tags: algorithms, search-algorithms, distributed-systems, computer-networks, database-theory
---


# Question
Title: What are good algorithms for distributed purchasing?
I'm looking for some algorithms/patterns to solve a distributed systems problem.

Lets say I have created a trading platform buying stock (I haven't), and I have a distributed system of 50 nodes that are making these purchases for me. I also know that I have a budget of $50k, and it needs to be spent by the end of the day. I have some set of rules that determines whether or not to make the purchase, and if thats the case I purchase the stock.

How do I ensure that I don't exceed my budget when these purchases occur quickly across every node? So node 49 doesn't get the memo that we are out of money, and spends $20K that I don't have.

Assume in this case, that a small amount overpurchase is acceptable, lets say 2% over time. We are also only concerned with the first discrete purchase beyond 50K, not a single purchase taking us from 49,999 to 50,100.

Are there good patterns that fit this sort of problem? Its seems similar to what Amazon or others might do for inventory management.

Thank you!

# Answer
> 0 votes
Your nodes will need to coordinate, otherwise the risk is unavoidable that they overspend. If you want there to be zero chance of overspending, then you might need a consensus algorithm, such as Paxos etc. If you are OK with a small amount of overspending (as it appears you are), you might be able to give each node a budget it can spend without coordination (e.g., up to \\$100 without coordinating), and have each node eagerly/optimistically spend up to that amount but waiting for the coordination algorithm to complete before spending more than that.

Some topics to learn about: https://en.wikipedia.org/wiki/State\_machine\_replication, https://en.wikipedia.org/wiki/Paxos\_(computer\_science), https://en.wikipedia.org/wiki/Raft\_(algorithm).

# Answer
> 1 votes
DW answer is awesome - you could get a linearizable fault tolerant system to get you going.

But you could get the desired outcome in a much simpler way: have a one single database which will track all spendings one by one. Single database is by definition linearizable - single copy of data. When a node will want to execute a trade, the node will have to run a transaction first:

update Account set balance = balance - MoneyToSpend where balance \>= MoneyToSpend and

Assuming your database executes these updates atomically (many dbs do, and if they don't you could use explicit SELECT FOR UPDATE), that will make sure you won't over spend.

Having a db is much simpler comparing to building or even understanding a consensus based strongly consistent system. But there is a trade off - singe db system is not 100% available, it can go down - the big question is if that's a real concern. Most system don't have 100% uptime SLA anyway

---
Tags: algorithms, distributed-systems
---


title: Proof of Fenwick Tree's correctness

text:
# Question
Title: Proof of Fenwick Tree's correctness
Unfortunately (like many other authors) Fenwick does a very bad job of explaining his work (the Binary Indexed Tree) in the original text. The paper lacks a proper formal proof of why this structure should work and only provides examples. This seems to be a very widespread issue regarding this topic and no tutorial or blog post out there seems to prove the correctness of this beast.

Just to be clear, I'm not looking for intuition or an explanation of how this data structure works, I already know that, what I am asking for is a formal proof that says a tree built this way will do what it is supposed to do correctly.

There is already another question here, with a very detailed and well-written answer that still doesn't provide a proof (though the question didn't really ask for proof either) and also seems to rely on a logic much different from what is presented in the original paper so please do not mark this as a duplicate.

# Answer
Both my formatting and proving techniques are a bit rusty. Please let me know if any of the following proof is done dirty.

In Fenwick's paper, which will be called paper for short in the rest of the proof, at least half of it is revolved around partial sums under logarithmic time. I think it is a good application but when it comes to wrapping your head around the intuition and nuance, there are still work to do.

The key idea of the paper, imo, is outlined in this statement in P.2

> The basic idea is that, just as an integer is the sum of appropriate powers of two, so can a cumulative frequency be represented as the appropriate sum of sets of cumulative 'subfrequencies'.

Suppose there are 2 mappings per each positive integer. First one being the indexed item

> $item(n)$

and second one being the partial sum starting from some weird indexed item to this indexed item. The only known fact is that the difference between them is $LSB - 1$

> $weird(n) = \sum\_{i=n - LSB + 1}^{n}item(i)$

if the positive integer is 1 LSB away from being all 0's, then

> $weird(n) = \sum\_{i1}^{n}item(i)$

With this weird mapping, $\sum\_{i=1}^{11}item(i)$ can be written in this way instead,

> $weird(1000\_2)+weird(1010\_2)+weird(1011\_2)$

Since this is almost everything of the paper, I will write in full detail of the indexes represented by each term. For $1011\_2$, there are at least 2 LSB away from all 0's, so

> $weird(1011\_2) = \sum\_{i=11 - 1 + 1}^{11}item(i) = item(11)$

For $1010\_2$, again, at least 2 LSB away from all 0's so,

> $weird(1010\_2) = \sum\_{i=10 - 2 + 1}^{10}item(i) = item(9) + item(10)$

For $1000\_2$, since it is 1 LSB away from all 0's so,

> $weird(1000\_2) = \sum\_{i=1}^{8}item(i)$

Together, you can see why the sum of the 3 terms are correct. That's the end of the foreplay and it will be full throttle from here on. I argue that the following algorithm will visit each term from 1 to that positive integer one time only, no more, no less and it applies to each positive integer.

```
n = positive integer
cumulation = 0

while n > 0
  cumulation += weird(n)
  strip LSB from n

return cumulation

```

Note that each positive integer can be written in binary form with at least one 1's in it. So there must exist a sequence wherein each preceding term is the successive term stripping of its LSB. This is just a convoluted way of saying

> $11\_{10}: 0000\_2, 1000\_2, 1010\_2, 1011\_2$.

This sequence, if viewed as half-interval, will cover the entire range from 1 to that positive integer. Again, one convoluted way of saying

> $(0000\_2,1000\_2\]\cup(1000\_2,1010\_2\]\cup(1010\_2,1011\_2\]=(0000\_2,1011\_2\]$

Each half-interval is covered entirely by a weird function indexed at the end of that interval. Again, one convoluted way of saying

> $weird(1000\_2)$ covers all indexes from $(0000\_2, 1000\_2\]$

Each term from 1 to n will be reached at least once. Suppose there exist a positive index which its mapped item is not reached. It must exist in $(0, n\]$ and it must fall into one of the half-intervals from the said sequence, which is covered by all weird functions. This contradicts that it is not reached. Hence, each term from 1 to that positive integer must be reached at least once.

By construction, each half-interval from the said sequence will be visited once only in each loop of the algorithm. By construction, weird function will only include all its member in the half-interval once only. Therefore, each item will be reached at most once.

Since each item is reached at most and at least once, I conclude each item is reached once only in this algorithm.

What follows will be the proof of the construction algorithm of weird function. For a while it has been taken for granted. No longer will it be the case. I argue the following algorithm makes weird function at each index cover whatever in their half-interval once only. Again and again, one convoluted of saying the following is indeed true in the construct of the coming algorithm.

> $weird(1010\_2) = \sum\_{i=1001\_2}^{1010\_2}item(i)$

The algorithm is

```
n = positive integer
for each index from 1 to n
  while index <= n
    weird[index] += item[index]
    add LSB to index

```

For each index, there exists a half-interval which the weird function should hit. Again and again, one convoluted of saying the following is indeed true in the construct of the coming algorithm.

> $weird(1010\_2) = \sum\_{i=1001\_2}^{1010\_2}item(i)$

For each index, if every member in its half interval hits weird\[index\] once only, then the proposition is correct.

Suppose, by contradiction, there exists an index such that there exists a member in its half interval which doesn't hit weird\[that index\]. I argue that this member must have at least 1 LSB as well as the fact that adding LSB will eventually equate the member to the index. Hence, the member will hit that index, contradicting it doesn't that index. By proof of contradiction, for each index, each member that should hit weird\[index\] will hit at least once.

**Why is there at least 1 LSB?**

Each index is at least 1. The least value after stripping of LSB is 0. Since 1 is added, the value is at least 1, which translates to have at least 1 LSB.

**Why adding LSB will eventually hit the index?**

In base case where there is no 0 bit on or after the LSB of the index, this is trivially true. For example,

> index = $1\_2$, half interval = (0, $1\_2$\]

Suppose, inductively, any members with less than or equal to k zero bits on or after the LSB will hit the index. Bits, if any, after the rightmost 0 bit must be 1. Regardless, adding 1 will turn the 0 bit to 1, which left a sum of k zero bits. By induction, it is correct.

I also argue that for each index, each member will not hit the index more than once because according to the algorithm, each value won't hit another index more than once. Addition does wonders.

The proposition is correct.

Fenwick, Peter M. "A new data structure for cumulative frequency tables." Software: Practice and experience 24.3 (1994): 327-336.
> 1 votes

---
Tags: data-structures, binary-trees
---


title: Remove number after duplicated number

text:
# Question
Title: Remove number after duplicated number
I created an algorithm which I cannot resolve.

Imagine you have list of number like:

```
val list = mutableListOf(1, 2, 3, 4, 5, 2, 6, 7, 2, 9)

```

And if some number is duplicated (in this case 2 is 3x times) we have to remove 3,6 and 9. I was trying to resolve it, but I can only remove 6 and 9 and even without whole solution it looks very bad:

```
val list = mutableListOf(1, 2, 3, 4, 5, 2, 6, 7, 2, 9)

        val indexes = mutableListOf<Int>()
        val uniqueList = mutableListOf<Int>()

        list.forEachIndexed { index, i ->
            if (!uniqueList.contains(i)) {
                uniqueList.add(i)
            } else {
                indexes.add(index)
            }
        }

        indexes.sortDescending()

        indexes.forEach {
            list.removeAt(it + 1)
        }

```

This task is not from popular websites so I am not able to find a solution. How to resolve it without too many loops ? My language is Kotlin but it can be java also.

# Answer
> 2 votes
As noted in the comment use a hash table (map). But to be more detailed, the keys of the map will be the integers in the list while the entries will be a list containing all positions where each integer occurred.

Let `L` be your original list of integers and `M` be the map. Finally let `L'` be the new list after the removal of elements. The solution will have three phases.

In the first phase, iterate over all elements of `L` such that for each element `e` at index `i` in `L`, check if key `e` exists in `M`. If it doesn't, create a new list containing `i` and insert it in `M` with key `e`. If it does exists, then let `l` be the list in `M` for key `e`. Add `i` to `l`.

For the second phase, iterate over all list `l` in `M`. In each iteration, if the size of list `l` is greater than one, iterate over the elements of `l` such that for each element `i` in `l` set to `null` the content of index `i+1` in `L` if `i+1` is not beyond the indices of `L`.

As for the last phase, copy all non-null entries of `L` to `L'`.

The resulting list `L'` should contain all the remaining elements in order that they appear in `L`.

---
Tags: algorithms, optimization
---


# Question
Title: Is [F(a, b, c) = a' + b] functionally or logically complete?
I'm having a problem determining whether \[F(a, b, c) = a' + b\] is functionally(logically) complete or not.
I would really appreciate it if you could help me.
P.S: I can't have 1 or 0 as input.

# Answer
If you are not allowed to have the constant $0$ as input then you cannot implement the constant function $0$ using only $F$.

To see this, let $C$ be a minimum (w.r.t. the number of gates) circuit that uses only $F$ gates and that computes $C(x) = 0$. We will show that this leads to a contradiction. Since $C$ must contain at least one gate (otherwise $C(1)=1$), we can consider the last gate $F(a,b,c)$ of $C$. In order for such a gate to return $0$ we must have that $b=0$. But then there must be a smaller circuit that computes $0$.

If you are allowed to use $0$, then the gate $F$ is universal. Indeed $1 = F(0,0,0)$ and we can simulate a NAND gate, which is universal: $$a \text{ NAND } b = \overline{a \cdot b} = \overline{a} + \overline{b} = \overline{a} + (\overline{b} +0) = F(a, F(b,0,0),0).$$
> 2 votes

---
Tags: boolean-algebra
---


# Question
Title: Regular Expression for Grammar = ({X, Y, Z}, {a, b}, X, {X → aY | bZ, Y → b | bZ, Z → a | aY})
2nd year college student here, I have trouble finding for the regular expression for that grammar, any help would help :D

Regular Language of the grammar:

X → aY → ab

X → bZ → ba

X → aY → abZ → aba

X → bZ → baY → bab

X → aY → abZ → abaY → abab

X → bZ → baY → babZ → baba

X → aY → abZ → abaY →ababZ → ababa

X → bZ → baY → babZ → babaY → babab

Regular Language: {ab, ba, aba, bab, abab, baba, ababa, babab, ...}

# Answer
You can apply Arden's lemma to solve your task even without constructing a DFA. The Arden lemma states that, given an equation $X = \Phi X\\,|\\,\Psi$, its minimal fixpoint (i.e., the minimal solution) is the regular expression $(\Phi)^\*\Psi$.

Below I use the $+$ notation rather than $|$ to underline the connection with the equation systems in the linear algebra. Your system of the regular equations is now:

$$\begin{array}{l} X = aY + bZ \\ Y = bZ + b \\ Z = aY + a \end{array} $$

The variable $X$ is not involved in any recursion, thus the regular expression for it is simply an alternative of the two regexps $aY\\,|\\,bZ$. To determine them, you can substitute the equation for $Z$ to the $Z$ occurrence in the equation $Y = bZ + b$ and apply Arden's lemma. The overall technique is exactly the same as in the linear algebra.
> 2 votes

---
Tags: regular-languages, automata, regular-expressions
---


# Question
Title: Building non-classical logics in Agda & Coq
Is it possible to construct different systems of logic in Coq or Agda?

I ask because I'm interested in using a proof assistant to construct (and verify) theorems in things like many-valued logics, relevant logics, and conditional logics in Graham Priest's 2nd edition of *An Introduction to Non-Classical Logic* (I keep going back to over the years in my free time).

It seems like intuitionistic logic is definitely possible in Coq given it was developed alongside the calculus of constructions, but I'm curious if Coq (or Agda) could be used for other logics.

A part of my gut says, "It wouldn't be possible to do logics that use fewer rules of inference or swap out intuitionistic rules for incompatible rules (eg, removing the principle of explosion)." However, another part of my gut says, "Machines using binary gates can still represent & simulate quantum processes, so it may be possible for Coq to represent logics incompatible with it's own implementation."

Any references to good papers/books/lectures/etc. are happily welcome.

# Answer
> 6 votes
You can define many non-classical logics in Coq (and I assume Agda too), even if they are incompatible with the logic of your proof assistant, but you need to define the concept of inference yourself. That is, you can't rely on Coq formulas, you need to define your own language. And you can't rely on Coq logic, you need to define what counts as a proof. You still use Coq as a meta-language though.

Here is a silly example in Coq with a very restricted language.

```
(* well-formed formulas *)
Inductive formula : Set :=
  | T : formula
  | AND : formula -> formula -> formula.

(* axioms and rules of inference *)
Inductive provable : formula -> Prop :=
  | TisProvable : provable T
  | ANDI : forall f1 f2, provable f1 -> provable f2 -> provable (AND f1 f2)
  | ANDEl : forall f1 f2, provable (AND f1 f2) -> provable f1
  | ANDEr : forall f1 f2, provable (AND f1 f2) -> provable f2.

```

You can now show, using the meta-theory of Coq, that `provable f` for some specific formulas `f`, or in other words, you can prove theorems of this logic I just made up.

```
Lemma ANDTTT : provable (AND (AND T T) T).
Proof.
  apply ANDI.
  - apply ANDI; exact TisProvable.
  - exact TisProvable.
Qed.

```

You can even make Coq automatically prove such simple lemmas:

```
#[export] Hint Resolve TisProvable ANDI ANDEl ANDEr : provableHints.

Lemma ANDTTT_auto : provable (AND (AND T T) T).
Proof. eauto with provableHints. Qed.

```

---

Some examples of non-classical logics implemented in Coq:

---
Tags: logic, proof-assistants, coq, automated-theorem-proving, agda
---


# Question
Title: Determine efficiently whether A can get infinitely larger than B by following a walk in the given graph
Person $A$ is chasing person $B$. Both people can only travel between $n$ vertices of a graph by running through one of $m$ one-way pipes labelled $1,2,\cdots, m$. For each pipe we know the starting and ending vertex. Each pipe has two values $A\_i, B\_i$ which are positive real numbers and represent the multipliers of person $A$'s and $B$'s heights as they run through the pipe. For example, if person $A$ and person $B$ currently both have height $2$, if they run through the pipe with $A\_i =1, B\_i = 2$, then person B will now have height $4$ while person $A$ will have height $2$.

$A$ starts running at a vertex $s$ while $B$ starts at s an instant later and will chase $A$ at the same speed later. You can treat $A$ and $B$ as a single object whose trajectory is entirely determined by $A$.

> Given the graph (with no duplicate edges or self-loops) and the starting vertex $s$, how can I determine in $O(nm)$ time or faster if it's possible for $A$ to lead $B$ through a sequence of pipes so that $A$ gets infinitely larger than $B$? Provide a justification for the algorithm.

I was thinking of creating a new graph where there is a negative weight cycle if and only if it's possible for $A$ to be infinitely larger than $B$ after travelling through a sequence of pipes. Then I could use the Bellman Ford algorithm to solve the problem in $O(nm)$ time. But I'm not sure how to find this graph.

# Answer
You've the right idea. Yuval's comment provides the missing trick. Here is the algorithm that connects the dots.

1. For each pipe $i$ with $A\_i$ and $B\_i$ from vertex $u$ to vertex $v$, we add an edge of weight $\log(B\_i/A\_i)$ from $u$ to $v$. Let $G$ be the graph with the given $n$ vertices and $m$ edges just added. It is the graph you were thinking of.
2. Apply Bellman–Ford algorithm with $s$ as the source to detect whether there is a negative-weight cycle in $G$ reachable from $s$.
3. If there is, it is possible for $A$ to lead $B$ through a sequence of pipes starting from $s$ so that $A$ gets infinitely larger than $B$. Otherwise, no.

The idea is that the sum of weights along a walk in $G$ corresponds to the logarithm of the change of ratios of $B$'s height to $A$'s height when $A$ and $B$ have walked that walk. A negative-weight cycle means the ratio of $B$'s height to $A$'s height becomes smaller when $A$ and $B$ have walked that cycle once.

The algorithm runs in $O(mn)$ time.
> 1 votes

---
Tags: algorithms, graphs, algorithm-analysis, reductions, shortest-path
---


# Question
Title: Boot Loaders, Boot Sectors, BIOS, and GRUB
Again, I must apologize if this is "easily googlable". I have tried.

My understanding is that the BIOS typically looks for the magic number 0x55aa at the end of a 512 byte sector (so bytes #511 and #512). Once it finds that, it begins executing that code. That code can then load the operating system. **It finds this by checking all bootable disks/drives until it finds that sector, right?**

I wrote a simple boot sector, and verified this mechanism on qemu and bochs.

My question is in regard to GRUB. Does BIOS find GRUB in the same way that it finds the boot sector I wrote? I did a hexdump on the binary GRUB file and was unable to find the magic number 0x55aa at the end of a 512 byte sector

Another way to ask the question, which really highlights my lack of understanding, would be as follows:

What is the purpose of the magic number 0x55aa in relation to BIOS and the booting process? What is the purpose of the magic number 0x1BADB002 in relation to GRUB and the booting process? Additionally:

* Does BIOS locate boot loaders via the magic number 0x55aa? If not, what **does it locate** with that magic number? My understanding was that the boot sector is the sector that contains the boot loader code, and that sector need have the magic number 0x55aa.

**I really felt like I was understanding everything writing my own boot sector in 16-bit real mode, entering 32 bit protected mode, and bootstrapping to C. Then when I learned about GRUB I felt like I don't understand anything anymore. i tried to read and google, please help**

Much love!

pls let me know if im thinking about this wrong

# Answer
It depends on what grub binaries you look at for finding the 0x55aa signature. GRUB has several files and has to be installed in several steps before it can be used.

The boot sector is meant to be the first sector of an hard-disk. It just happens that, with QEMU, you can specify any file type to be the hard-disk. This is a really great functionality because it allows to create a raw virtual hard-disk with `dd`.

When you boot with GRUB legacy, the first sector is loaded at 0x7c00 in RAM. This sector's code then uses the legacy BIOS services to load the second stage of GRUB to RAM and jumps to it.

Today, GRUB is an EFI app that is compiled probably by gcc using the gnu-efi framework. The UEFI firmware interprets a FAT32 hard-disk partition and jumps to the main function of /boot/efi/bootx64.efi. This executable is in the PE (Portable Executable) format.
> 2 votes

---
Tags: operating-systems, os-kernel, assembly
---


title: How can EXP^P be characterized?

text:
# Question
Title: How can EXP^P be characterized?
I had a question about EXP^P (EXPTIME with access to a P oracle). I thought I had read somewhere that EXP = EXP^P, and that seemed fairly intuitive to me: I thought "adding polynomial power to something that already has exponential power must not change a lot". Now I am questioning myself: I was searching for something that verified thar EXP equals EXP^P, but I can't find something like that. I am thinking that I probably just assumed those classes were equal and they actually are not (or it is still not known). Does anyone have some hints about how to characterize this class? Or if there is a known relationship between EXP and EXP^P?

# Answer
> 1 votes
You are right, EXP = EXP^P.

Suppose that you have an oracle $f$ that is in $P$. This means that whatever computation the oracle $f$ is doing, can be done by some polynomial-time algorithm, let's call it $B$. Consider any algorithm $A$ in EXP^P that uses the oracle $f$. We can modify $A$ so that any time it would have called $f$, it instead runs the polynomial-time algorithm $B$ (as a subroutine) without using the oracle.

In this way, we have obtained a new algorithm that doesn't use any oracle. What is the running time of this new algorithm? It is at most the running time of $A$, times the running time of $B$, or in other words, at most an exponential function times a polynomial function. One can easily show that this is also an exponential function (for example, $2^x \times x^7 = O(4^x)$, since $x^7 = O(2^x)$). Therefore, we have obtained a new algorithm that also runs in exponential time, and doesn't use an oracle, so this new algorithm must be in EXP.

In this way, we can convert any algorithm in EXP^P to an algorithm in EXP. This shows that every problem in EXP^P is also in EXP. The other direction (every problem in EXP is also in EXP^P) is trivial (just ignore the oracle and never use it), so this shows that EXP = EXP^P.

---
Tags: complexity-theory, np, complexity-classes, oracle-machines
---


# Question
Title: Tight analysis on a custom data structures with Insert and Remove-Min
I have a data structure supporting the operations `Insert(X)` and `Remove-Min()`. `Remove-Min()` is performed in $O(\sqrt{\log n})$. And I am supposed to show that the `Insert` is bounded by $\Omega(\log n)$.

I would like to ask how to approach this problem. $O(\sqrt{\log n})$ never really occured to me and I do not know how to start.

My attempt was: Since the best possible sorting is in $O(n \log n)$ one needs insertion in $\log n$ to be able to retrieve the current minimum element in $O(1)$. But then, this is not tight enough, plus the element should be removed.

# Answer
> 1 votes
Here is how to sort a list $a\_1,\ldots,a\_n$ using your data structure: insert all elements, and then repeatedly remove the minimum element.

You take it from here.

---
Tags: algorithms, data-structures, asymptotics, big-o-notation
---


# Question
Title: The distinct-vertex $\alpha$-edge variant of the all-pairs shortest paths problem
> The following problem is a variant of the all pairs shortest path problem: Given a weighted, directed graph $G=(V,E), |V| = n,|E| = m,$ and an integer $\alpha\ge 1$, how can I find an efficient algorithm to construct an $n\times n$ matrix where the entry corresponding to vertices $u$ and $v$ is the minimum weight path consisting of exactly $\alpha$ edges, or $\infty$ if no such path exists? A path is a walk that does not repeat any vertices. Assume the vertices of $G$ are numbered as $v\_1,\cdots, v\_n$ so that the $(i,j)$th entry of the output matrix corresponds to the min weight walk between vertices $v\_i$ and $v\_j$.

I know how to solve the problem when vertices can be repeated using dynamic programming, but I can't seem to solve this particular problem because vertices might be distinct.

If I ignore the condition that each such path must use exactly $\alpha$ edges, then I think the following would work, but it might be inefficient: do a breadth-first search for every possible starting vertex $s$ to find the minimum weight walk from $s$ to all other vertices. I could then store these $n$ distances for each vertex to obtain the required $n\times n$ matrix (each computation would add a new row). This would take $O(n(n+m))$ time.

The problem with using exactly $\alpha$ edges is that even though one can decompose a shortest path of length $\alpha$ between two vertices $u$ and $v$ into a shortest path of length $\alpha\_1$ between $u$ and $i$ and a shortest path of length $\alpha\_2$ between $i$ and $v$ for some intermediate vertex $i$, where $\alpha\_1 + \alpha\_2 = \alpha$. But one must check that the shortest (min weight) path of length $\alpha\_1$ doesn't share a vertex other than $i$ with the shortest path of length $\alpha\_2$.

> Correction: BFS obviously can't be used for the shortest paths of a weighted graph, but neither Dijkstra's nor Bellman ford can be used as no vertices can repeat.

# Answer
As you have noticed, the requirement of vertices in a path being distinct introduces significant difficulty and obstacle against an efficient algorithm.

That requirement has far-reaching impact both literally and figuratively.

Literally, each previous inclusion of a vertex in a path affects any later choice directly and independently, however distant those choices are.

Figuratively, that requirement makes this problem $\mathsf{NP}$-hard. If we have solved the special case when $\alpha=n-1$, i.e., finding the shortest path from $u$ to $v$ going through all other vertices, then we have solved Hamiltonian path problem, an $\mathsf{NP}$-hard problem. So this problem is $\mathsf{NP}$-hard as well.

In particular, people have researched intensively for decades to find a polynomial algorithm to solve Hamiltonian path problem and other $\mathsf{NP}$-complete problems. No success so far. If "an efficient algorithm" means a polynomial-time algorithm, it is safe to bet an efficient algorithm won't be found in many years. By a majority opinion of computer science community, there cannot be an efficient algorithm.
> 4 votes

---
Tags: algorithms, graphs, shortest-path, breadth-first-search
---


# Question
Title: finding an algorithm for creating a priority search tree in linear time with presorting
> A priority search tree is a binary tree satisfying the following:

* every node $u$ stores a point $p\_u = (x\_u,y\_u)$
* every nonleaf $u$ stores an x-coordinate $x\_u'$ called the split-line coordinate.
* If $v$ is a descendant of $u, y\_v\leq y\_u$.
* If $v$ is in the left subtree of $u$, then $x\_v \< x\_u$ and if $v$ is in the right subtree of $u$, then $x\_v \ge x\_u$.

Source: the above definition is a variant of the one used in this question: Creating a priority search tree to find number of points in the range \[-inf, qx\] X \[qy, qy'\] from a set of points sorted on y-coordinates in O(n) time

> I was wondering how, if given a set of $n$ points in general position sorted by $x$-coordinate, one could construct a priority search tree in worst case linear time?

I know how to create a priority search tree in $O(n\log n)$ worst case time. I thought of creating a BST of x-coordinates and then doing an in-place fix with rotations to ensure the heap property is maintained. For each node $u,$ we can then let $x\_u'=x\_u$, the x-coordinate of the point it stores. However, this algorithm doesn't seem to run in linear time (since while doing the in-place fix the number of rotations could be close to linear for many points).

# Answer
> 4 votes
What you are looking for is essentially a Cartesian tree:

> The Cartesian tree for a sequence of distinct numbers can be uniquely defined by the following properties:
>
> 1. The Cartesian tree for a sequence has one node for each number in the sequence. Each node is associated with a single sequence value.
> 2. A symmetric (in-order) traversal of the tree results in the original sequence. That is, the left subtree consists of the values earlier than the root in the sequence order, while the right subtree consists of the values later than the root, and a similar ordering constraint holds at each lower node of the tree.
> 3. The tree has the heap property: the parent of any non-root node has a smaller value than the node itself.

Just transform the $n$ points $p\_0,p\_1,\ldots,p\_n$ where $x\_0\le x\_1\le \cdots \le x\_n$ into an array $A$ where $A\[i\]=-y\_i$, and construct the Cartesian tree for this array. The Cartesian tree meets all your requirements.

There are several methods to construct a Cartesian tree in linear time. I quote a simple one from Wikipedia here:

> One method is to simply process the sequence values in left-to-right order, maintaining the Cartesian tree of the nodes processed so far, in a structure that allows both upwards and downwards traversal of the tree. To process each new value x, start at the node representing the value prior to x in the sequence and follow the path from this node to the root of the tree until finding a value y smaller than x. The node x becomes the right child of y, and the previous right child of y becomes the new left child of x. The total time for this procedure is linear, because the time spent searching for the parent y of each new node x can be charged against the number of nodes that are removed from the rightmost path in the tree.

---
Tags: algorithms, computational-geometry, trees, binary-trees, binary-search-trees
---


# Question
Title: How are I/O operations handled on a computer?
What does the computer do when an I/O operation needs to be done during the process? Does the message that we need to do some I/O operation directly reaches the device controller or device driver? What does the operating system have to do with this?

# Answer
I don't know how it is implemented in hardware but in software you have mostly MMIO PCI device registers. PCI devices all have a conventional PCI configuration space. The configuration space also have BAR registers that point to other portions of the configuration space which are specific to the device. Each device have a specification document that specifies how the device specific portion of the config space works.

PCI devices work with memory mapped IO (MMIO). The kernel writes to some portion of the virtual address space that is not cached to write to the registers of the device. This allows to configure the device.

In general, the kernel has the higher half of the virtual address space reserved for its code and data segment (and other things). The kernel must reside within 2GB due to limitations in RIP-relative machine code where the offset from code must be a maximum of 2GB. This is often easily done because the kernel doesn't require this much space. The rest of the higher half of the virtual address space can be accessed with 64 bits pointers This portion of the address space is marked as global in the page tables to avoid a TLB flush on context switch (when the page table base pointer is changed).

The kernel is invoked from user mode by using `syscall` which has a specific binary encoding specified in the manual (the software specification) of the processor. This instruction makes the processor jump to an address specified in a register that is specified by the kernel at boot.

If you write C/C++ code, the code makes calls in the lib/libc++ library which is a shared object that implements the C/C++ standard library. The standard library implementation is loaded alongside your executable and the symbols of the library are resolved before runtime by the dynamic loader.

Most operating-systems implement some form of virtual-filesystem where every device is presented to the upper layer of the OS as a file. For example, Linux has several categories of device drivers and a more broad category which is character devices. The character devices are general drivers that are implemented as virtual files that you can open to do file operations on them. The driver is thus free to do anything in the file operation implementation.

For example, if you use the write syscall on a device, it could write to the PCI registers of the device to trigger some operations. PCI devices are DMA so they directly read/write RAM with a separate bus. Now this must be managed by the OS by making sure the user mode buffer is not cached or swapped to the hard-disk. It comes with a lot of complexities.

The virtual-filesystem thus makes the driver model modular because it allows to add generic drivers in the kernel while it is running. You can also store the module in a specific directory to make sure it is loaded at boot.
> 1 votes

---
Tags: operating-systems
---


# Question
Title: How to prove cycle sort has the minimum swap times?
Copy from Wikipedia

> Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result.

Why does cycle sort have minimum write times (or minimum swap times)? I can't find such a claim in the paper *Cycle-Sort: A Linear Sorting Method*. I have met different variants of cyclesort, so I want to know the specific proof method.

**Edited**: I misunderstood minimum write times with minimum swap times, so the premise of the problem is wrong.

# Answer
> 6 votes
Cycle sort minimizes the number of times that a value is written to the array, as proved in the Wikipedia article:

> Each value is either written zero times, if it's already in its correct position, or written one time to its correct position. This matches the minimal number of overwrites required for a completed in-place sort.

Another implementation of cycle sort only uses swaps. Sorting a cycle of length $\ell$ requires $\ell-1$ swaps (this includes the special case of a fixed point, in which $\ell=1$), for a total of $n-c$ swaps, where $c$ is the number of cycles. This is optimal. Indeed, denote the initial permutation of the array by $\pi$, and the swaps applied to it by $\sigma\_1,\ldots,\sigma\_m$. Thus $$ \sigma\_m \cdots \sigma\_1 \pi = \mathsf{id}, $$ implying that $\pi = \sigma\_1 \cdots \sigma\_m$. It remains to show that if we write $\pi$ as a product of transpositions, then there at least $n-c$ transpositions in the product. Indeed, since the identity permutation has $n$ cycles and multiplying by a transposition reduces the number of cycles by at most $1$, any such product must contain at least $n-c$ transpositions.

---
Tags: algorithms, proof-techniques
---


# Question
Title: $\log_{2}{(\frac{1}{2}n)} + \log_{2}{(\frac{1}{4}n}) + \log_{2}{(\frac{1}{8}n)} + \ldots + \log_{2}{(\frac{1}{2^{log_{2}(n)}}n)} = O(\log_{2}(n))$?
I am trying to analyze a series that I found, in the analysis of an algorithm. And I was wondering if the following was true: $$\log\_{2}{\left(\frac{1}{2}n\right)} + \log\_{2}{\left(\frac{1}{4}n\right)} + \log\_{2}{\left(\frac{1}{8}n\right)} + \cdots + \log\_{2}{\left(\frac{1}{2^{log\_{2}(n)}}n\right)} = \mathcal{O}\left(\log\_{2}(n)\right)$$

It is basically the sum of the geometric series which converges to $1$, but each term is multiplied by $n$ and $\log\_{2}$ is taken.

Using the logarithm rule $\log\_{2}(a) + \log\_{2}(b) = \log\_{2}(ab)$ seems to give results that indicate this is not the case right? e.g. $$\log\_{2}(128) = 7$$ and $$ \log\_{2}\left(\frac{1}{2}128\right) + \log\_{2}\left(\frac{1}{4}128\right) \ldots = \log\_{2}(64) + \log\_{2}(32) + \log\_{2}(16) + \log\_{2}(8) + \log\_{2}(4) + \log\_{2}(2) = \log\_{2}(2097152) = 21 $$ So a difference of 14, when $n=128$, I suppose that there is no way that this series is upper bounded by like $\mathcal{O}(10\log\_{2}(n))$.

# Answer
> 5 votes
Using $\log a + \log b = \log (ab)$, we get: $$\sum\limits\_{k=1}^{\log\_2 n}\log\_2\left(\frac1{2^k}n\right) = \log\_2\left(\prod\limits\_{k=1}^{\log\_2 n}\frac{n}{2^k} \right) = \log\_2\left(\frac{n^{\log\_2 n}}{2^{\sum\limits\_{k=1}^{\log\_2 n}k}}\right) = \log\_2\left(\frac{n^{\log\_2 n}}{2^{\frac{\log\_2 n\times(\log\_2 n + 1)}{2}}}\right)$$

But: $$\frac{n^{\log\_2 n}}{2^{\frac{\log\_2 n\times(\log\_2 n + 1)}{2}}} = \frac{n^{\log\_2 n}}{n^{\frac{\log\_2 n + 1}{2}}} = n^{\frac{\log\_2 n - 1}{2}}$$

We conclude that the sum is equal to: $$\log\_2 \left(n^{\frac{\log\_2 n - 1}{2}}\right) = \frac{\log\_2 n - 1}{2}\log\_2 n \in \Omega((\log n)^2)$$

So the answer is no.

Another way to get this result is to say that half (so $\frac12\log\_2 n$) of the terms of the sum are greater than $\log\_2(\sqrt{n})$.

# Answer
> 2 votes
Let $k:=\log\_2 n$ then

$\sum\limits\_{j=1}^{\log\_2 n}\log\_2(\frac{1}{2^j} \cdot n) = \sum\limits\_{j=1}^{k}(\log\_2(\frac{2^k}{2^j})) = \sum\limits\_{j=1}^{k}\log\_2(2^j) = \sum\limits\_{j=1}^{k} j = \frac 1 2 k(k+1)$

so

$\sum\limits\_{j=1}^{\log\_2 n}\log\_2(\frac{1}{2^j} \cdot n) \in \Theta(k^2) =\Theta((\log\_2 n)^2)$

# Answer
> 1 votes
Yet another way to obtain the bound using the identity $\log \frac ab=\log a - \log b$ to have simpler sums.

$ \sum\limits\_{i=1}^{\log\_2 n} \log\_2 \left({\frac{n}{2^i}}\right) = \sum\limits\_{i=1}^{\log\_2 n} \left(\log\_2 n - \log\_2 2^i \right) = \sum\limits\_{i=1}^{\log\_2 n} \left(\log\_2 n - i \right) = \sum\limits\_{i=1}^{\log\_2 n} \log\_2 n - \sum\limits\_{i=1}^{\log\_2 n} i $

We now have,

$ \sum\limits\_{i=1}^{\log\_2 n} \log\_2 n - \sum\limits\_{i=1}^{\log\_2 n} i = (\log\_2 n)^2 - \left(\frac {\left(\log\_2n\right)^2}{2} + \frac{\log\_2 n}{2}\right) = \frac {\left(\log\_2n\right)^2}{2} - \frac{\log\_2 n}{2} = \Theta\left( \left(\log\_2 n\right)^2 \right) $

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


title: How to show that $A(3k, 2k)=4$?

text:
# Question
Title: How to show that $A(3k, 2k)=4$?
Denote by $A(n,d)$ the maximal size of a binary code of length $n$ with distance $d$.

How to show that $A(3k, 2k)=4$? From Plotkin bound: $$2k \> \dfrac{3k}{2} \Rightarrow A(3k, 2k) \leq 4$$ But I don't know why here equality. I also tried to use Gilbert–Varshamov lower bound. But it doesn't help to obtain $A(3k, 2k) \geq 4$.

# Answer
Here is a (linear) code attaining the bound: $$ 000\\011\\101\\110 $$ Each bit represents a block of $k$ equal bits.
> 2 votes

---
Tags: coding-theory
---


# Question
Title: Is DFS better than BFS for space complexity when finding path from root to a node in a tree?
For simplicity, and I think without loss of generality, we can consider a binary tree. Suppose that we want to find the path between the root node and some node in the tree (we don't know where it is and only that it exists in the tree).

Worst case scenario is if the node was a leaf node at the largest depth.

If we want to find the path to this node, is DFS a lot better memory wise? DFS would incur O(h) (h = height of tree) recursion space and the space used to store the current path is also O(h) (not certain of this, but I think this is right). So the space complexity is O(h) I believe.

If we used BFS, we'd end up storing like 2^h paths with each path being O(h) long. So the space complexity is O(2^h * h).

Is this analysis correct, or am I missing something here?

# Answer
> 1 votes
In the case of the binary tree, and assuming your binary tree is balanced, yes, I think you will be using more space at any given time in general with BFS. DFS would be allocating and releasing memory space, while BFS would be holding memory increasingly as it goes down the tree.

BFS would be simplified because you don't need really to mark visited nodes as you do with graphs, and if each node had a pointer to their parent, you wouldn't need to keep track of paths. That pointer to parent solution would also help your DFS, because it is a tree, and you can be sure that when you find the node, walking back to the root through the parent pointers is the shortest path.

If you binary tree is very unbalanced, your average case scenario could favor BFS at times because it could find the node quicker using less pointer references at any given time after all.

# Answer
> 1 votes
To keep it short and simple, the answer is **yes**.

BFS, in addition to the `set` of *visited* nodes, makes use of `queue` for unprocessed nodes (and at each step in the process, you enqueue the *unvisited* neighbors of the current node, etc.). Also, for the BFS that keeps track of the path, you've to store the pointer to the *predecessor* node.

Whereas DFS (which passes the `set` of *visited* nodes as a parameter to the recursive function) makes use of the recursive function to trace its path back to the source node. No additional `queue` is required here.

For more details, visit this question.

# Answer
> 0 votes
The answer to your question is it depends on the structure of the tree. Given a tree with n nodes, the worst-case space complexity for DFS is O(n). Similarly the worst-case space complexity for BFS is O(n).

DFS has O(n) space complexity because of the use of a stack (either call stack or manually managed stack). In the worst case a tree can have all nodes in a line from root to leaf giving the tree a height of n-1. And all nodes would be stored in the stack at the leaf level.

BFS has O(n) space complexity because in the worst case, the root is connected to all other nodes and BFS would create a 2-level tree with the root at level 0 and all other nodes at level 1. Hence the BFS queue would contain n-1 nodes which uses O(n) space.

To summarize for trees where height is less than max width, DFS uses less space asymptotically. For trees where max width is less than height BFS uses less space asymptotically.

---
Tags: binary-trees, depth-first-search, breadth-first-search
---


# Question
Title: (Leetcode; Dynamic Programming) Partition to K Equal Sum Subsets memoization
Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

This is leetcode problem #698.

Below is code that I have written with backtracking to solve the problem (it is correct and passes all test cases).

When we apply memoization for a DP solution shouldn't the current state we are in for memoization depend on all of: currSum, count, and taken? Instead, all we need is taken and not currSum and count to uniquely identify our state.

For clarification: taken tells us which numbers we've selected thus far (or havent selected), count tells us the number of subsets we've currently divided into subsets, and currSum tells us the current sum for the subset we're trying to solve.

So why do we only need taken to identify the memoization state, and not all of taken and count and currSum?

```
class Solution {
    bool helper(const vector<int>& nums, int k, int count, int currSum, int targetSum, int index, vector<int>& taken) {
        if (count == k - 1)
            return true;

        if (currSum > targetSum)
            return false;

        if (currSum == targetSum)
            return helper(nums, k, count + 1, 0, targetSum, 0, taken);

        for (int i = index; i < nums.size(); i++) {
            if (!taken[i]) {
                taken[i] = 1;
                if (helper(nums, k, count, currSum + nums[i], targetSum, i + 1, taken))
                    return true;
                taken[i] = 0;
            }
        }

        return false;
    }

public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), greater<>());
        vector<int> taken(nums.size(), 0);

        const int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum % k != 0 || *max_element(nums.begin(), nums.end()) > sum / k)
            return false;

        return k == 1 || helper(nums, k, 0, 0, sum / k, 0, taken);
    }
};

```

# Answer
Here is the signature of the recursive method,

```
bool helper(const vector<int>& nums, int k, int count, int currSum, int targetSum, int index, vector<int>& taken);

```

That means a state is implemented as a collection of 7 items, `nums`, `k`, `count`, `currSum`, `targetSum`, `index`, `taken`.

---

However, a state is completely determined by `nums`, `k` and `taken`. Once they are known, other items, `targetSum`, `currSum`, and `index` are determined.

* `targetSum` is the sum of all elements in `nums` divided by `k`.
* `count` is the integer quotient of the sum of all elements taken except the element taken at the largest index divided by `targetSum`.
* `currSum` is the sum of all elements taken minus the product of `count` and `targetSum`.
* `index` is $0$ if no element has been taken or one more than the largest index at which an element is taken.

Since `nums` and `k` are constants, we can also view a state as completely determined by `taken`, once the input `vector<int>& nums, int k` is given. That is why we only need `taken` to identify the state.

Given the constants `nums` and `k`, in math terms, we can view a state as having one independent variable `taken` and other dependent variables. In database terms, the table of all states has one primary key `taken` and other non-key columns.
> 1 votes

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


title: Minimum spanning tree using DFS and BFS

text:
# Question
Title: Minimum spanning tree using DFS and BFS
Can we construct minimum spanning tree for an undirected graph with distinct weights using bfs or dfs?

I have gone through many answers but each answer says something different and I am not convinced.

# Answer
Briefly, the answer is no, we cannot construct minimum spanning tree for an un-directed graph with distinct weights using BFS or DFS algorithm. This post provides a counterexample.

Computing MST using DFS/BFS would mean it is solved in linear time, but (as Yuval Filmus commented) it is unknown if such algorithm exists. However, there is an expected-linear-time randomized algorithm computing the MST.
> 1 votes

# Answer
Can not. Because we do not use any scenario to find minimum path in DFS or BFS. we just visit all the nodes considering depth first or breadth first. We visit the node when we first met it according to DFS OR BFS. But there may be easiest paths to visit those nodes that we will not have chance to try in BFS. SO finding shortest path also not possible there. But when considering unweighted graph then you can use BFS to find minimum spanning tree. To obtain minimum spanning tree of a weighted graph you can use prim's algorithm.
> 1 votes

# Answer
It is possible to find an MST of a connected, undirected, and weighted graph in linear time if you are given two facts:

1. There is exactly one cycle in the graph
2. You are given one of the vertices in this cycle

From here, you can use DFS and BFS to find the maximum weight edge (u, v) on the cycle, and return the edge set of G - (u, v) that represents the MST.

An MST of a graph with distinct weights will never include the max weight edge of a cycle.
> 0 votes

---
Tags: graphs, graph-traversal, spanning-trees, minimum-spanning-tree
---


# Question
Title: Research project problem on Computational Geometry
1. **(Most fair region)** Let $P$ be a set of $n$ points in the two-dimensional plane. Each point in $P$ is either colored red or blue. Given an axis-aligned rectangle $R\_{ab}$ of size $a\times b$ , design a fast algorithm to decide where to place $R\_{ab}$ in the plane so that the absolute difference between the number of red points and the number of blue points lying inside $R\_{ab}$ is minimized. As a motivating example, think of each point in $P$ as the geographical location of each person. The color of each person could be assigned based on either gender, or political affiliation, or native/non-native speaker, favourite hero etc. We look at the simple setting where there are only two groups/colors. The goal is to detect region(s) which has a fair representation of both groups. Fairness in general is a very popular topic in computer science these days.
2. **(Most unfair region)** Let $P$ be a set of $n$ points in the two-dimensional plane. Each point in $P$ is either colored red or blue. Given an axis-aligned rectangleRabof size $a \times b$, design a fast algorithm to decide where to place $R\_{ab}$ in the plane so that the absolute difference between the number of red points and the number of blue points lying inside $R\_{ab}$ is maximized. Following the previous motivating example, this could help detect a region where there is huge gender disparity or detect a region where a particular political party has a strong majority.

These are two related open problems which our course instructor on computational geometry has asked us to work on. Could anyone suggest some literature/resources related to these so that I am able to navigate and appreciate the problem better ? (I haven't been able to find anything related to this on google)

P.S.: I am a 2nd year undergrad student, and this is my first computational geometry course. This "research project problem" is to give us a better flavour of what it takes to be a CS researcher.

# Answer
> 1 votes
You might enjoy learning about dynamic programming: https://cs.stackexchange.com/tags/dynamic-programming/info

---
Tags: algorithms, computational-geometry, search-algorithms
---


# Question
Title: Which Turing Award winners have supervised the PhDs of other Turing Award winners?
John McCarthy won the Turing Award in 1971 \[\]. Two students whose PhD he supervised went on to win Turing Awards:

* Raj Reddy (1994) \[\]
* Barbara Liskov (2008) \[\]

What other Turing Award winners supervised the PhD theses of other Turing Award winners?

# Answer
Consulting with the Mathematics Genealogy Project, I was able to find the following thesis advisor relationships:
> 12 votes

---
Tags: history
---


# Question
Title: Could Gödel’s incompleteness theorem be circumvented with a quine?
As you all probably know, Gödel’s incompleteness theorem states, that it will never be possible for mathematics to prove its own correctness.
Mainly because that proof would be part of mathematics too, and hence need proving itself. And that leads to an infinite loop in logic.

But I realized that a quine, as in, a program that can output itself, seems to circumvent that problem: It really CAN output ALL of itself.

So I’m wondering, if the general tricks used in quines might be usable to “solve” that problem in mathematics too. At least to arrive at a different problem that might be solvable in a different way.
And if not, then I’m curious why exactly not, so I can lay this to rest in my head.

# Answer
> 39 votes
Here is the proof of Gödel's incompleteness theorem, in a nutshell, for a theory $T$. We construct a sentence $\Pi$ which states that "$T$ proves that $\Pi$ is false". The sentence mentions itself, just like a quine.

If $T$ proves $\Pi$ then $T$ also proves that $\Pi$ is false, and so $T$ cannot be sound. If $T$ proves that $\Pi$ is false then $\Pi$ is true, and so again $T$ is not sound.

# Answer
> 26 votes
> Mainly because that proof would be part of mathematics too, and hence need proving itself. And that leads to an infinite loop in logic.

No, that's not the flaw identified by Gödel’s incompleteness theorem. As you note, that can be addressed with a quine. Quines are, loosely speaking, the *cause* of the theorem, not the solution: if you can create a statement that outputs itself, then you can also create a statement that outputs a negation of its provability. That is, you have a statement that declares that it can't be proven. If the statement can be proven, then it's false, so you've proven a false statement, which means that your system is inconsistent. If it can't be proven, then the statement is true (since what the statement consists of is the declaration that it can't be proven), thus it is a statement that is true, but can't be proven to be true. Therefore, every sufficiently sophisticated mathematical system is either inconsistent or contains statements that are true, but can't be proven.

# Answer
> 12 votes
\[This is just my attempt to make Yuval Filmus's answer more mathematically accurate. Feel free to combine the answers, delete this one, or whatever seems best.\]

Here is the proof of Gödel's incompleteness theorem, in a nutshell, for a theory $T$. We construct a sentence $\Pi$ which states that "There is no proof of $\Pi$ in $T$". The sentence mentions itself, just like a quine, and exploits the fact that formulas and proofs can be encoded as numbers in such a way that the property of being a proof of a formula is expressible in arithmetic terms.

If $T$ is sound and proves $\Pi$ then $\Pi$ is true, so $T$ does not prove $\Pi$, a contradiction. We conclude that $T$ does not prove $\Pi$; but then $\Pi$ is indeed true, and $T$ provides no proof of it.

# Answer
> -1 votes
> Mainly because that proof would be part of mathematics too, and hence need proving itself. And that leads to an infinite loop in logic.

This is not the reason why Gödel’s incompleteness theorem proves that no set of rules (Mathematics, C++, Philosophy, Law, Religion etc.) can prove its own correctness. The actual reason is kind of a generalization of The Halting Problem in computing.

Gödel proved that for any set of rules you can formulate a statement (eg. program) that breaks the rules. Therefore it is impossible to fix rules (programming language, Mathematics etc.) to make them unbreakable (always true/applicable for all statements/programs). The Halting Problem can actually be interpreted as a reformulation of Gödel's Incompleteness Theorem in the context of Turing Machines/Computers (indeed there are papers written on the topic).

Whereas the Halting Problem proves that it is not always possible to write an algorithm that always generate a solution (proving that some problems are undecidable), the Incompleteness Theorem proves that it is not always possible to prove that all the rules in your system (Mathematics, C++, etc) can be proven to be always true.

But in practice this is not a problem. Just as we can write useful software even when some problems cannot be solved by software we can do useful problem solving even if we don't use all statements mathematics can produce.

One candidate for the incompleteness theorem may or may not be the twin prime conjecture, which states that there are infinitely many twin prime numbers (couples of prime numbers differing by 2). To this day, it could not be proved, which means that it is either false and we were not able to disprove it yet, or it may be true and we have not found a valid proof for it yet, or it may be one of those statements that Gödel talked about - that is, a statement that is true but unprovable.

---
Tags: logic, mathematical-foundations, theory, philosophy
---


# Question
Title: Can we meaningfully state for what proportion of possible programmes we can determine if they halt, do not halt, or wether it is still undetermined?
\[My apologies, I am not a computer scientist, merely an interested amateur. I apologise if this question does not make sense, is a known result, or a duplicate\]

To quote Wikipedia:

> The halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever.

This cannot be solved in general for all possible program-input pairs.

However, for a subset of programs/inputs we **can** determine by inspection, or simply running them, whether they will halt - e.g. I believe that a program with no looping or recursion will always halt, and a program with an impossible loop-ending condition will never halt.

One could imagine a program which when taking a program/input runs it for a length of time and reports 'halts' if it halts in that time, 'doesn't halt' if it has entered an infinite loop in that time, or 'undetermined' if neither has happened yet.

If we ran the program for increasing lengths of time, we must expect the proportion of programmes for which 'undetermined' is returned to reduce - i.e. 10% of programs may halt or enter an infinite loop when run for 1 hour, but 20% when run for 10 hours.

Can we, and do we know what the expected outputs of such a machine might be given a sufficient time? i.e. do 'almost all', 'most', 'some' or 'almost no' programs halt? Do 'more' programs enter an infinite loop than halt?

And if we cannot answer this question in general, can we answer it for a Turing machine with a limited number of states? e.g. do most 4-state Turing machines halt?

# Answer
There are infinitely many Turing machines, so the notion of 'most' is a bit tricky to define. But with a reasonable interpretation, the answer will depend on the programming language. So, the question cannot be answered in general terms.

To get some flavor for why this might be: consider an assembly language that has 10000 opcodes, where 9000 of them are "halt" instructions that when executed cause the program immediately to halt, 999 of them are arithmetic instructions (that don't trigger any control flow), and 1 is a conditional branch. Then in some sense, most programs halt, because a random program is likely to contain one of the halt instructions before its first branch instruction. Conversely, consider an assembly language that has 10000 opcodes, where 9000 of these are instructions that immediately enter an infinite loop, 998 are arithmetic instructions, one is a halt instruction, and one is a conditional branch. Then most programs don't halt, because most contain one of the infinite-loop instructions before the first halt or conditional branch.

This proportion is closely related to Chaitin's constant. The value of Chaitin's constant cannot be computed by any algorithm.

Finally, the question as you have posed it is in some sense not well-defined. "Halting" is a property of a program and an input. It doesn't make sense to ask whether a program halts, or calculate the proportion of programs that halt. So, we can't ask what proportion of 4-state Turing machines halt. We could ask what proportion of 4-state Turing machines halt on all inputs. This is tricky, though; given a Turing machine, checking whether it halts on all inputs is not computable.
> 5 votes

---
Tags: halting-problem
---


# Question
Title: having trouble understanding the proof of regular expression identities $(u + v)^* = (u^*v)^*u^*$
I am having trouble understanding the proof given below:

> \begin{align} (u \cup v)^\* &= (u^\* \cup v)^\* \\ &= u^\*(u \cup v)^\* = (u\cup vu^\*)^\* \\ &= (u^\*v^\*)^\* = u^\*(vu^\*)^\* \\ &= (u^\*v)^\*u^\* \end{align}

In more detail, why does $(u + v)^\* = (u^\* + v)^\*$ hold? Why can we just put a star on $u$? Is it a property?

Also, why can we extract the $u^\*$ from the $(u^\* + v)^\*$ and then put it after $v$? Why can the $+$ be eliminated from $(u + vu^\*)^\*$ to $(u^\*v^\*)^\*$?

# Answer
> 3 votes
How does one prove that two regular expressions represent the same language? One approach is using *axiomatizations of the equational theory of regular expressions*.

The equational theory of regular expressions consists of all statements $\alpha = \beta$ where $\alpha,\beta$ represent two equivalent regular expressions. In this context, an axiom is an equational identity such as $u \cup v = v \cup u$. Each such axiom is really an axiom scheme: you can substitute anything you want for $u$ and $v$. Furthermore, you can use the principle of substitution of equals by equals to apply this axiom in a larger context, for example deducing that $(u \cup v)^\* = (v \cup u)^\*$.

When designing an axiom system, we are looking for two properties: *soundness* and *completeness*. Soundness means that all the axiomatic identities are in fact true. Which axioms are true could depend on the alphabet: for example, if the alphabet is unary, then $uv = vu$, but this is not true over larger alphabets. Completeness means that if $\alpha = \beta$ then this can be proved in the system. Salomaa constructed two complete axiom systems in his classic paper Two Complete Axiom Systems for the Algebra of Regular Events.

The proof you are quoting seems to make use of some axiom system, whose axioms you seem not to believe. The proof is probably intended as a demonstration of the axiom system. The description of the axiom system should be accompanied by a soundness proof of the axioms. This suggests one course of action for you — looking up the description of the axiom system, and the proofs of the relevant axioms. Another course of action is to look for a different proof of the entire identity from first principles.

# Answer
> 2 votes
$(u+v)^\*$ denotes an arbitrary string made of $u$'s and $v$'s, which is the same as $(u^\*+v)^\*$ or $(u+v^\*)^\*$ or $(u^\*+v^\*)^\*$, as any character can be repeated anyway.

Now you can freely prepend or append the expression with $u^\*$ or $v^\*$ or another $(u+v)^\*$, outside the parenthesis, or even inside (in any case the $^\*$ terms can vanish, otherwise they may contribute *some part* of the string).

You will also agree that $u^\*v^\*$ is a superset of $u+v$, so that $(u^\*v^\*)^\*=(u+v)^\*$.

Finally, you can split a string in all pieces that start/end in a single $u$ or $v$ and complete with extra $v$'s or $u$'s before or after.

E.g. $uuvvvvuvuuuvuvuvuuvuvuvuv=uu\ v\ v\ v\ vu\ vuuu\ vu\ vu\ vuu\ vu\ vu\ v=u^\*(vu^\*)^\*$.

---
Tags: regular-languages, regular-expressions, proof-techniques
---


# Question
Title: Is it reasonable to assume modern computers can do hardware math with integers up to 2^64?
I was writing up an algorithm that involved knowing the size of integers my hardware can manage without having to resort to software implementations of math operations and the additional computational load that comes with them, and I realized that I've never given this much thought.

In theory, a 64-bit computer has 64 lines on the address/data bus, and thus can't send an integer to the CPU's ALU any higher than 2^64-1, making that the starting point. But I also know that some modern hardware has support for SIMD operations with 256-bit data, or even higher, and how that's possible I don't know (multiple operations to load in the data, 64 bits at a time, I assume?).

Without limiting this question to specific hardware, which would greatly diminish its usefulness, is there a reasonable rule of thumb for how large of an integer a typical modern computer (2015-2020 era) can handle in a single go?

# Answer
Yes, you can look at the instruction set for that CPU architecture. If it has (for example) an "add 64 bits to 64 bits" instruction then you know it can do that.

Current 64-bit CPUs do support the full set of ALU operations on 64-bit numbers. Add, subtract, multiply, divide, bitshift, bitwise operations, modulo, maybe some that I forgot. *All* of the usual instructions work on 64-bit numbers in one go. That's why we call them 64-bit CPUs.

The address and data bus paradigm is quite outdated. Nowadays CPUs transfer data in big chunks, up to the size of a cache line (usually 64 bytes). Actually, if you read just 1 byte, the CPU will read 512 bits from main memory into the cache, read 512 bits from the cache, and discard 504 of them. (or maybe 256 and discard 248) The data bus is *very* wide, and SIMD operations let you use its full potential.

If there's no "add 256 bits to 256 bits" instruction then you still can't do that in one go. SIMD operations will surely help you add lots of big numbers quickly, but if the instruction you want doesn't exist then you'll still need to write an addition algorithm yourself (using SIMD if you want)
> 1 votes

---
Tags: computer-architecture, space-complexity, computation-models, memory-hardware, bit-manipulation
---


# Question
Title: Is there a way to determine the LCS of three based on the LCS-s of all three pairs?
Let $\Sigma$ be an alphabet of some symbols, and let $\mathrm{lcs}$ denote the length of the longest common subsequence of two or more sequences defined on $\Sigma$. For some $A,B,C\in\Sigma^{\star}$, given $\mathrm{lcs}\\!\left(A,B\right)$, $\mathrm{lcs}\\!\left(B,C\right)$ and $\mathrm{lcs}\\!\left(C,A\right)$, what can be said about $\mathrm{lcs}\\!\left(A,B,C\right)$? Obviously, $\mathrm{lcs}\\!\left(A,B,C\right)\leqslant \mathrm{min}\\!\left\\{\mathrm{lcs}\\!\left(A,B\right),\mathrm{lcs}\\!\left(B,C\right),\mathrm{lcs}\\!\left(C,A\right)\right\\}$, but what else?

The standard DP approach reduces the LCS problem to *smaller* LCS problems, where *smaller* means **shorter** sequences. So here I ask if it can somehow be reduced to LCS problems with **fewer** sequences? Any research and/or known results on this question?

# Answer
> 3 votes
If $|\Sigma| \geq 3$, then for any non-negative integers $x \leq x\_{AB}, x\_{AC}, x\_{BC}$ we can find strings $A,B,C$ such that $\operatorname{lcs}(A,B,C) = x$, $\operatorname{lcs}(A,B) = x\_{AB}$, $\operatorname{lcs}(A,C) = x\_{AC}$, $\operatorname{lcs}(B,C) = x\_{BC}$: \begin{align} A &= a^x b^{x\_{AC} - x} c^{x\_{AB} - x} \\ B &= a^{x\_{BC}} c^{x\_{AB} - x} \\ C &= a^{x\_{BC}} b^{x\_{AC} - x} \end{align} where $a,b,c$ are different letters in $\Sigma$.

However, if $|\Sigma|=2$ and $\operatorname{lcs}(A,B) \ge 1$, $\operatorname{lcs}(A,C) \ge 1$, $\operatorname{lcs}(B,C) \ge 1$, then $\operatorname{lcs}(A,B, C) \ge 1$.

---
Tags: dynamic-programming, approximation, edit-distance
---


# Question
Title: Does $f(n) \in O(g(n))$ imply $2^{f(n)} \in O(2^{g(n)})$?
Is the following true: $$ f(n) \in O(g(n)) \text{ then } 2 ^ {f(n)} \in O(2^{g(n)})$$

# Answer
> 5 votes
An obvious counterexample is $f(n) = n$ and $g(n) = \frac{n}{2}$. We know that $f(n) \in O(g(n))$, but $2^{f(n)} = 2^n \not \in O(2^{g(n)}) = O(2^{\frac{n}{2}}) = O(\sqrt{2^n})$.

# Answer
> 0 votes
In general, you would ask: For a function h(n), if f(n) = O(g(n)), is h(f(n)) = O(h(g(n))?

We have f(n) \< c * g(n) for some constant c, and for large n. The function h(n) must be such that within the range of f(n) and g(n), h(f(n)) must not grow so fast that a linear change in f(n) creates a non-linear change in h(f(n)).

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


# Question
Title: Find the lowest line given the same x-axis
There are a bunch of lines in the 2D Plane. Is there an efficient algorithm to find the line that has the lowest y value given the same x? Thank you!

Could we also generate a list of ranges, where for each range, we know which line has the lowest y?

For example, for `y = x + 2` and `y = 2x` for `x` in `[0,100]`, we know that `y = 2x` is lower in the range `[0,2]`, and `y = x+2` is lower in the range `[2,100]`.

# Answer
> 1 votes
For the first question, if no preprocessing is allowed, there is no better way than computing all intersections with the vertical at $x$. This is an easy $O(n)$ process.

For the second question, refer to the link in the comments. The duality means that to find the relevant intersections of the lines of equations $y=m\_kx+p\_k$, you need to find the lower hull of the points $(m\_k,p\_k)$. This is efficiently solved by the Monotone Chain algorithm in time $O(n\log n)$. https://en.wikipedia.org/wiki/Convex\_hull\_algorithms#Algorithms

When you have obtained the intersections that define the envelope, solving for an arbitrary $x$ is done in time $O(\log n)$ by dichotomic search.

---
Tags: algorithms, computational-geometry
---


# Question
Title: Generate degree-bound LFSR to approximate given sequence
Given an output sequence, $S$, we can use the Berlekamp-Massey algorithm to find the shortest LFSR, of order $n \leq |S|$, which exactly generates that sequence. Is it possible to efficiently compute an LFSR, in $GF(2)$, of order $n \leq n\_0 \< |S|$, which best approximates $S$? Best approximation means with the fewest possible errors, and by errors we consider the element-wise discrepancies (i.e. no insertions/deletions are allowed).

I searched for similar papers and the only relevant one I could find was Modified Berlekamp-Massey algorithm for approximating the k-error linear complexity of binary sequences. However, it is an exponential algorithm (and I don't quite understand it).

# Answer
> 2 votes
The measure you are interested in is usually called $k-$error linear complexity. See this review in Asiacrypt 2003 by Niederreiter. There are unpaywalled versions of this paper around. The cryptanalytic goal (first described in the book *Stability Theory of Stream Ciphers* by Ding et. al.) is to determine (given some fixed $k\>0$) the *shortest* LFSR generating a sequence of length $N.$

There are various algorithms for computing it under various assumptions. For example if the sequence is assumed to have period $p^n$ and is over $GF(p)$ faster algorithms are possible. Keywords to look for include the Games-Chan algorithm (complexity $O(n)$ for sequence length $2^n$), Stamp and Martin algorithm (modification of Games-Chan). Look at Meidl's work hereaand elsewhere as well.

You can simply search the papers citing Niederreiter's review paper and find out more.

**Edit:** The OP has clarified the problem which I had slightly misunderstood. Indeed the paper by Lauder and Paterson is the way to go in this case.

---
Tags: algorithms, approximation, shift-register
---


# Question
Title: Fast algorithm for computing minimal closure of a set of sets under intersection?
A step of an algorithm I’ve designed requires computing the minimal closure under intersection of a set of sets of arbitrary size. By the "minimal closure (of a set $S$) under intersection", I mean:

Given a set $S$ containing sets $s\_1, \cdots , s\_k$, the smallest set $′$ such that $S\subseteq S'$ and $x\cap y \in S'$ for any two sets $x, y \in S'$.

While I can come up with a pretty straightforward naive approach (loop over the sets and store all the intersections in a new set, then update the set as the union of previous step’s set and the new set, and repeat this process until the new and old set are the same), I am looking for a faster method, but haven’t been able to find any papers working on a similar problem. Does anybody know if there are faster existing algorithms to solve this problem before I attempt to potentially reinvent the — or a worse version of — the wheel? Or if not exact solutions, maybe fast approximation algorithms on other data structures (e.g. sets of strings) that translate to this problem setup?

# Answer
> 1 votes
There is no polynomial-time algorithm. The output can potentially be exponentially large, so any algorithm will have inputs on which it must take exponential time. For instance, if $s\_i=\\{1,2,\cdots, k\\}\setminus\\{i\\}$, then $S'$ contains $2^k$ elements, so any algorithm must take $\Omega(2^k)$ time (it takes that much time even just to output $S'$, let alone to calculate it).

One simple approach is a workload algorithm, where you incrementally generate new sets that are in the closure. In particular:

* Set $W := S$. (The worklist is initialized to $S$.)
* Set $S' := S$.
* While $W \ne \emptyset$:

+ Pop an element from $W$, call it $s$.
    + Let $T := \\{s \cap s' \mid s' \in S', s \cap s' \notin S'\\}$.
    + Set $W := W \cup T$ and $S' := S' \cup T$.

---
Tags: algorithms, sets, algorithm-design
---


# Question
Title: Is $f(X)f^d(X) = 0$ for a Boolean function $f$?
I'm currently trying to understand a step in the proof for in the Crama and Hammer book on Boolean Functions. The proof is Proposition 4.12, which claims that the self-dualization of Boolean $f$ is bijective.

The specific statement that I am confused about is a step showing that:

$$f^d(X)f(X) \lor f(X) \bar{x}\_{n+1} \lor f^d(X) {x}\_{n+1} = f(X) \bar{x}\_{n+1} \lor f^d(X) {x}\_{n+1}.$$

Here $f(X)$ is a d-dimensional Boolean function, $X = (x\_1,x\_2,\ldots, x\_n) \in \mathcal{B}^n$, and $f^d(X) := \overline{f(\overline{X})}$ is the *dual* of $f$.

This equality above seems to require that $f^d(X)f(X) = 0.$ I am wondering why this is? I think that I am missing something simple, or maybe I've found a typo in the proof. If someone has a different proof for the broader claim that self-dualization is bijective, that would be fine.

---

I've copied the full proposition below in case it helps:

Here $f^{SD}(X)$ is the *self-dual extension* of $f$. This is a function over the (d+1)-dimensional Boolean hypercube such that $$f^{SD}(x\_1,x\_2,\ldots, x\_n, x\_{n+1}) = f(x\_1,x\_2,\ldots, x\_n)\bar{x}\_{n+1} \lor f^d(x\_1,x\_2,\ldots, x\_n)\bar{x}\_{n+1}.$$

# Answer
$$f^d(X)f(X) \lor f(X) \bar{x}\_{n+1} \lor f^d(X) {x}\_{n+1} = f(X) \bar{x}\_{n+1} \lor f^d(X) {x}\_{n+1}$$ The equality above comes from the general equality below. It has nothing to do with the context.

$\begin{aligned} &\quad\ yz\lor y\overline{x\_{n+1}} \lor z{x}\_{n+1}\\ &=yz(\overline{x\_{n+1}} \lor x\_{n+1})\lor y\bar{x}\_{n+1} \lor z{x}\_{n+1}\\ &=(yz\overline{x\_{n+1}} \lor yzx\_{n+1})\lor y\bar{x}\_{n+1} \lor z{x}\_{n+1}\\ &=(yz\overline{x\_{n+1}}\lor y\bar{x}\_{n+1})\lor (yzx\_{n+1}\lor z{x}\_{n+1})\\ &=y\bar{x}\_{n+1}\lor z{x}\_{n+1}\\ \end{aligned}$
> 4 votes

---
Tags: logic, boolean-algebra, boolean-complexity
---


# Question
Title: Why does this example of a Canonical Interval Decomposition contain keys and leaves that are outside of the interval?
I am reading *Advanced Data Structures* by Peter Brass for self-study, and was confused about the book's example of a Canonical Interval Decomposition for the Segment Tree section (section 4.2):

So, the key 3 is halfway between 2 and 4, the key 6 is halfway between 6 and 8, and the key 9 is halfway between 8 and 10. 4 is the "missing" number of \[2, 4\[, 8 is the "missing number" in \[4, 8\[, and 10 is the "missing number" in \[8, 10\[. I can kind of see where they got that.

However, I'm quite confused about why numbers like 11, 12, 13, 14, and 15 occur in this at all (given that this is a representation of the interval \[1, 10\]). Can someone explain this to me?

# Answer
> "Assume a set $X = \\{x\_1,...,x\_n\\}$ of key values and a search tree $T$ for $\\{−\infty\\}\cup X$."

Here $X=\\{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16\\}$. That graph illustrates the binary search tree $T$ for $\\{−\infty\\}\cup X$, where each leaf represents either $-\infty$ or an element in $X$ in the natural order.

The task is to find the canonical interval decomposition of the interval $\[1, 10\[\ = \\{1,2,3,4,5,6,7,8,9\\}$ with respect to that tree.

What we will get are

* the node that represents $\[1,2\[$,
* the node that represents $\[2,4\[$,
* the node that represents $\[4,8\[$, and
* the node that represents $\[8,10\[$.

---

**Exercise 1.** What is the canonical interval decomposition of the interval $\[6,13\[$ for the same $X$ above?

**Exercise 2.** What is the canonical interval decomposition of the interval $\[-\infty,10\[$ if $X=\[1,10\[$?
> 2 votes

---
Tags: data-structures, trees
---


# Question
Title: Minimum number of tree cuts so that each pair of trees alternates between strictly decreasing and strictly increasing
A gardener considers aesthetically appealing gardens in which the tops of sequential physical trees (eg palm trees) are always sequentially going up and down, that is:

```
|               |
|       |       |
|   |   |   |   |

```

On the other hand, the following configurations would be invalid:

```
|
|  |
|  |  |

```

reason: 3rd tree should be higher than the 2nd one

```
|  |
|  |
|  |

```

reason: consecutive trees cannot have the same height

Given a sequence of physical trees in a garden, what is the minimum number of physical trees which must be cropped/cut in order to achieve the pattern desired by that gardener?

First, the heights of the physical trees in the garden can be represented by a sequence of integers. For instance, the three examples above can be represented as (3 1 2 1 3), (3 2 1), and (3 3).

Mathematically speaking, the problem maps to find the minimum number of negative sums which must be applied to a sequence of integers (a0, a1, ..., aN) so that each pair of consecutive integers (ai, ai+1) in this sequence alternates between strictly decreasing (ai \< ai+1) and strictly increasing (ai \> ai+1) . Example: In (2, 3, 5, 7), the minimum number of negative sums is 2. A possible solution is to add -2 to the 2nd element and then add -3 to the last element, resulting in (2, 1, 5, 4).

My search model is a graph where each node represents a sequence of physical tree heights and each edge represents a decrease of the height of a tree (from now on called "cut"). In this model, a possible path from the initial node to the goal node in the above example would be

* initial node: (2,3,5,7)
* action: sum -2 to a1
* intermediate node: (2,1,5,7)
* action: sum -3 to a3
* goal node: (2,1,5,4).

I have used a breadth-first search to find the shortest path from the initial node to the goal node. The length of this shortest patch is equal to the minimum number of trees that must be cut.

The only improvement to this algorithm that I was able to think was using a priority queue that orders the possible nodes to be explored in increasing order 1st by number of cuts (as traditional BFS already does) and 2nd by the number of "errors" in the sequence of integers in the node: triplets which do not match the required up/down pattern, ie. (ai \< ai+1 and ai+1 \< ai+2) OR (ai \> ai+1 and ai+1 \> ai+2), plus the number of consecutive equal numbers pairs (ai == ai+1) . This increases the probability that the goal node will be reachable from the first nodes with N-1 cuts in the queue when the times come to evaluate them. However, it is only useful to reduce the search space of nodes with N-1 cuts and not the complexity of the whole search.

The time required to execute this algorithm grows exponentially with the number of trees and with the height of the trees. Is there any algorithm/idea which could be used to speed it up?

# Answer
I'll describe two ways you could solve this problem. Either works. In some sense they are basically the same algorithm, just viewed from two different perspectives.

# Dynamic programming algorithm

This can be solved in linear time with dynamic programming. Let $d\_i$ denote minimum number of $a\_i,\dots,a\_n$ that must be cut to produce an alternating sequence if you start in the downwards direction for the first pair (the pair $a\_i,a\_{i+1}$) and don't cut $a\_i$, and $u\_i$ the minimum number to produce an alternating sequence starting in the upwards direction if you don't cut $a\_i$, and $u'\_i$ the minimum number to produce an alternating sequence starting in the upwards direction if you do cut $a\_i$. Then you can write down a recurrence relation that expresses $d\_i,u\_i,u'\_{i+1}$ in terms of $d\_{i+1},u\_{i+1},u'\_{i+1}$, and you can evaluate it in $O(n)$ time using dynamic programming.

In particular, the recurrence relation is $u'\_i = 1 + d\_{i+1}$ and

$$d\_i = \begin{cases} \min(u\_{i+1},u'\_{i+1}) &\text{if }a\_i\>a\_{i+1}\\ +\infty &\text{otherwise.} \end{cases}$$

$$u\_i = \begin{cases} d\_{i+1} &\text{if }a\_i\<a\_{i+1}\\ +\infty &\text{otherwise.} \end{cases}$$

Once you've computed all these values, the final answer for the minimum number of cuts needed for the sequence $a\_1,\dots,a\_n$ is $\min(d\_1,u\_1,u'\_1)$.

# Graph search

Alternatively, we can solve this by building up a suitable graph and then finding the shortest path in this graph.

Label a tree as a "peak" if in it is higher than its neighbors in the final sequence, and a "valley" if it is lower than its neighbors in the final sequence. The final sequence will alternate between peaks and valleys. Here is the two key observations:

* The optimal solution will never cut any tree that ends up as a peak. (Any solution that involves cutting a peak will remain valid if you don't cut the peak, and that reduces the number of cuts by 1.)
* In the optimal solution, you can assume without loss of generality that every tree that ends up a valley is cut down to the ground, i.e., to the minimum height. (Any solution that involves cutting a valley only partway will remain valid if you cut it down to the ground.)

Since we want to find an optimal solution, we will consider only solutions that follow both rules.

Let $a\_1,\dots,a\_n$ be the sequence. We will build a graph with $3n$ vertices. Each vertex has the form $\langle i,t,c \rangle$ where $i \in \\{1,2,\dots,n\\}$ is an index that identifies a tree, $t$ indicates whether tree $i$ will be a peak or a valley in the final solution, and $c$ indicates whether tree $i$ is cut to the ground or uncut in the final solution. We'll have an edge from one vertex to the next if they can be adjacent in a final solution. Thus, we have the following edges:

* $\langle i, \text{peak}, \text{no}\rangle \to \langle i+1, \text{valley}, \text{no} \rangle$, with length 0, for those $i$ where $a\_i\>a\_{i+1}$
* $\langle i, \text{peak}, \text{no}\rangle \to \langle i+1, \text{valley}, \text{yes} \rangle$, with length 1, for all $i$
* $\langle i, \text{valley}, \text{no}\rangle \to \langle i+1, \text{peak}, \text{no} \rangle$, with length 0, for those $i$ where $a\_i\<a\_{i+1}$
* $\langle i, \text{valley}, \text{yes}\rangle \to \langle i+1, \text{peak}, \text{no} \rangle$, with length 0, for all $i$

Finally, find the shortest path in this graph from a start vertext to an end vertex, where the start vertices are those of the form $\langle 1, \*, \*\rangle$ and the end vertices are those of the form $\langle n, \*, \*\rangle$. The length of this path will correspond to the minimum number of cuts needed in the optimal solution, and the path itself can be used to reconstruct the final solution. This shortest path can be found in $O(n)$ time using breadth-first search (BFS) on the graph defined above.
> 6 votes

# Answer
I think it's pretty easy to solve in O(n) time with one iteration over the array of integers representing the tree heights.

You can only create valleys by your cuts, not hills, so you should count the existing number of valid valleys at even and odd positions and cut depending of the result. Like D.W. said, you can cut every tree down to the ground that you want to convert to a valley and not touch the ones you want to be a hill.

Initialize two counters with 0, evenValleyCount and oddValleyCount.

Now iterate over the array of numbers representing the tree heights and check every value for being a valley (lower than left and right neighbors). If it's a valley increment evenValleyCount if the index of the current element is even or oddValleyCount if the index is odd.

If the length of the array is odd add 0.5 to evenValleyCount and subtract 0.5 from oddValleyCount.

Your result is the length of the array divided by 2 minus the higher value of evenValleyCount and oddValleyCount.
> 3 votes

# Answer
I think cutting tree in sequence way has a problem itself. It's not always the minimum number of tree cuts if you do it in sequence.

Ex: With the tree array is (2,3,4,5,6,9). If you cut it in sequence, the result will be (2,**1**,4,**3**,6,**5**) it will return 3. But it is not the exactly answer, I think the answer for this case is 2 with (2,3,**2**,5,**4**,9). The problem is the longer the array length, the harder it is to check for nodes afterward.

So in my opinion, we can use a simpler way to approach it. Let create a new array contains the boolean value if that a tree taller than the previous one. And we all know that in aesthetically appealing gardens, this array will contains the interleaved value (Like (true, false, true, false,...) or (false, true, false, true,...)). We will need to compare the array of height-difference to two desired arrays (true, false, true, false, true and false, true, false, true, false) and note about how many difference items for each array. The bigger matching number of item, the less effort to cut tree.

Back to my example, with the tree array is (2,3,4,5,6,9), the height-difference array is (true, true, true, true, true) and we will compare it with two desired array ((true, false, true, false, true) and (false, true, false, true, false)). The bigger matching number of item is 3 when compare with (true, false, true, false, true) so the tree you need to cut is only the number of difference items between two array (In this case is 2, each array has 5 items and it has 3 items matched)

The java code:

```
public int solution(int[] A)
{
    int res = 0;
    int res1 = 0;
    boolean B = true;

    for (int i = 1; i < A.length; i++)
    {
        if ((A[i] > A[i - 1]) == B)
        {
            res++;
        }
        else
        {
            res1++;
        }

        B = !B;
    }

    return res > res1 ? A.length - 1 - res : A.length - 1 - res1;
}

```

Because two desired array will have opposite value at same index so I will only need to create one array (B)

That is my solution. I dont know if it is right or not. Sorry for my bad English
> 1 votes

# Answer
My answer for this was like below

```
function solution($A) {        // write your code in PHP7.0
   $res = 0;
   $h = 0;
   $i = 0;
   foreach ($A as $a) {
     if (isset($A[$i+1])) {

       if ($a == $A[$i+1]) {
           $res++;
           continue;
       }

       if ($h >= 2) {
           $res++;
           $h = 0;
       }
       if ($a < $A[$i+1]) {
           $h++;
       }

       if ($h <= -2) {
        $res++;
        $h = 0;
       }
       if ($a > $A[$i+1]) {
        $h--;
       }
     }
     $i++;
   }
   return $res;
}

```
> -1 votes

# Answer
Hii here is my approach using C++. You can follow it along with the comments.

```
int solution(vector<int> &A){
int count = 0;

//First checking if we can cut zero or not
if(A[1]-A[0] > 0 && A[2]-A[1] > 0){
    count++;
}

if(A[1]-A[0] < 0 && A[2]-A[1] < 0){
    count++;
}

//Checking if we can cut from first till last
for(int i =0; i<A.size()-2; i+=2){

    //If 4 consecutive trees are increasing order
    if(A[i] <=A[i+1] && A[i+1] <=A[i+2] && A[i+2] <=A[i+3])
    return -1;

    //If 4 consecutive trees are in decreasing order
    if(A[i] >=A[i+1] && A[i+1] >=A[i+2] && A[i+2] >=A[i+3])
    return -1;

    //checking whether we can cut the tree or not
    if(A[i+1] -A[i] >0 && A[i+2]-A[i] >0){
        if(A[i+3] - A[i+2] < 0)
        count++;
        if(A[i+3] - A[i+1] < 0)
        count++;
    }

    //checking whether we can cut the tree or not
    if(A[i+1] -A[i] <0 && A[i+2]-A[i] <0){
        if(A[i+3] - A[i+2] > 0)
        count++;
        if(A[i+3] - A[i+1] > 0)
        count++;
    }
}
return count;
}

```
> -1 votes

---
Tags: search-algorithms, search-problem
---


# Question
Title: In the theta notation definition, is it possible that $n_0$ could equal 0?
This is the definition of theta notation:

> The function $T(N)$ is $\Theta(g(N))$ if there exist positive constants $C\_1$, $C\_2$ and $N\_0$ such that $C\_1g(N) \le T(N) \le C\_2g(N)$ for all $N \ge N\_0$.

My calculation is below. When I solved the inequality, $N \ge 0$. Am I making a mistake or am I on the right track?

Assuming 1 time unit equals 1 memory read or write, I have counted the time units to get to the expression $T(N) = 4KN + 37N + 11K + 22$.

This is a sorting algorithm that uses hashing. The inputs are an array $A$ of non-negative integers of length $N$, $k$ is the largest integer value in $A$, and $a$ and $b$ are positive integers. I also implemented this in javascript and the output is wrong so I think whoever made this made a mistake.

```
function Sort(A,N,k,a,b)
    C=new array(N) of zeroes    // 4 time units
    R=new array(N) of zeroes   // 4 time units
    pos=0 // 3
    for 0 <= j < N          // 7N+5 time units
        C[(a*A[j]+b)%N]=C[(a*A[j]+b)%N]+1 // 20N time units
    for 0 <= i < N          // 7N+5 time units
        for pos <= r < pos+C[(a*i+b)%N] // 11K time units
            R[r]=i     // 4KN time units
        pos=r =       // 3N time units
    return R         // 1 time unit
end function

```

The function $T(N)$ is $\Theta(g(N))$ if there exist positive constants $C\_1$, $C\_2$ and $N\_0$ such that $C\_1g(N) \le T(N) \le C\_2g(N)$ for all $N \ge N\_0$.

We can prove that $T(N) = 4KN + 37N + 11K + 22 = \Theta(g(KN))$.

$$(T(N) = 4KN + 37N + 11K + 22) \le (g(N) =4KN + 37N + 11K + 22 + KN)$$

$$(T(N) = 4KN + 37N + 11K + 22) \le (g(N) = 5KN + 37N + 11K + 22)$$

Therefore, the value of $C\_2$ becomes 5. If we solve the above inequality for $N$, $N \ge 0$.

# Answer
It doesn't matter whether you allow $N\_0 = 0$ or not (though per your definition, it is not allowed). If $C\_1 g(N) \le T(N) \le C\_2 g(N)$ holds for all $N \ge 0$, then in particular, it holds for all $N \geq 1$, or for all $N \geq 1000$, for that matter.

The condition "$C\_1 g(N) \le T(N) \le C\_2 g(N)$ for all $N \ge N\_0$" only requires that if $N \ge N\_0$ then $C\_1 g(N) \le T(N) \le C\_2 g(N)$. There is not requirement in the other direction. It's not an if-and-only-if.
> 1 votes

---
Tags: time-complexity, asymptotics
---