# Question
Title: Virtual and physical address spaces in address binding
I just need to check my understanding regrading two points .As was stated in the textbook "Operating systems concept " :

> The compile-time and load-time address-binding methods generate identical logical and physical addresses. However, the execution-time address binding scheme results in differing logical and physical addresses.

This is because at compile time the compiler knows where the program will resides in the main memory , and hence , it can computes the absolute address and therefore the virtual and physical address spaces will be the same . Same can be said for load time binding , except that the absolute address is calculated at the load time , and hence , the virtual and physical address spaces will be the same. However , at run time binding the program may change its address space multiple of times while executing and hence we get a different physical address space each time the program changes its address space and a new absolute address is calculated making the physical address space different from the virtual address space. Is that right ?

The second point is that we use the memory management unit to map between the virtual and physical address in run time address binding. In this hardware solution , we use a relocation register that includes the base address where the process is residing in the main memory . The value in this relocation register always changes when the process changes its address space while executing , resulting in calculating a new absolute address and hence a new base address. Is that right ?

# Answer
> 2 votes
I don't think the author of the book refers to the difference between the logical and physical addresses. The author refers to the difference between static and dynamic binding. In static binding, the addresses (both physical and logical) don't change during execution. In dynamic binding, the addresses can change during program execution (not the position of the program but the address referenced by the instructions). There is really no requirement or logic which says that, for some linking types, the physical addresses must be the same as the logical addresses or that they must be different.

Actually, a user mode program doesn't know anything about physical addresses. The OS really manages the whole thing without any requirement on where a logical address is translated. The memory allocator of the OS is the only one responsible to determine where a logical address is translated. It determines that by some algorithm such as the buddy algorithm. It selects a portion of physical memory and builds the page tables so that logical address translations arrive to that portion.

User mode programs really only care about logical addresses. They don't know anything about where they translate to. I think the author simply uses syntactic turns that make its phrases unclear. I think the author actually wishes to introduce the difference between static and dynamic binding and categorize the 3 binding types as either static or dynamic.

For binding/linking (I'll use linking for the rest of the answer because I think it refers to the same concept), there is mostly data linking and function linking. Your data is either static/global or local. For functions, they are either defined directly in the code or they are defined outside of it in a library which can itself be either dynamic or static. Functions can also be virtual. I'll give some examples of those using Linux and gcc on the x86 architecture so you can see an actual implementation.

Data is either static/global or local. Static/global data is simply placed in the data segment of the executable. This data is accessed using either PC-relative addressing or using absolute addresses. PC-relative doesn't care about the start address and makes the code position independent. GCC defaults to using PC-relative addressing unless you specify a large code model. PC-relative addressing is limited to a 32 bits offset from the code because of machine code limitations (the instruction only has 4 bytes for the offset). If your code is too large (some portion of it may be further away than a signed 4 bytes offset or 2GB), PC-relative doesn't work and you must use a large code model. For example, look at the following code:

```
int global = 0;

int main(){
    global = 3;
}

```

It compiles to (without optimization):

```
main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR global[rip], 3
        mov     eax, 0
        pop     rbp
        ret

```

Here, the compiler leaves an unresolved symbol for the linker. The linker (the one you call yourself when building your program), sees that unresolved symbol in the object of the program and resolves the offset from PC to put in the `mov DWORD PTR global[rip], 3` instruction.

Local data is data found within a function without the static keyword. It is the most common type of data in a program because static/global data is often avoided to provide code modularity and manageability. Local data is accessed with an offset from the stack base pointer register. For example, take the following code:

```
int main(){
    int local = 0;
    local = 3;
}

```

It compiles to (again without optimization):

```
main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], 0
        mov     DWORD PTR [rbp-4], 3
        mov     eax, 0
        pop     rbp
        ret

```

The code normally does 3 things:

1. It pushes RBP;
2. It moves RSP in RBP;
3. It decrements RSP of the space required for the function.

In this case, the third element wasn't needed. The compiler optimized it away due to the simplicity of the program even though optimization is not enabled. Those 3 steps basically build what is called a stack frame. The stack frame is per function and every function has its own. It means that every function will do these 3 steps unless some of them can be optimized away.

Local data will thus be accessed by using a negative offset from RBP as you can see in the `mov DWORD PTR [rbp-4], 0` and `mov DWORD PTR [rbp-4], 3` instructions. Since RBP is found below the stack frame, the data within it is accessed using a negative offset from it. This whole concept of local data and its usage of the stack is often simply called automatic storage. Automatic storage is determined only by the compiler (the offsets from RBP, the amount of bytes to decrement RSP and the optimizations to do or not do).

For function linking, there are several cases. Functions can either be defined within the code you write or in a library (like the standard library) outside your program. They can also be virtual which is also a special case. For functions, dynamic vs static binding is really only determined by the `virtual` keyword and is not found in C (only in C++).

The functions you define yourself within your program are called with a relative `call` instruction. If your function is within the same object file as where it is called, the compiler simply calculates the relative offset right now. If the function is found in another object, the compiler leaves a symbol for the linker. The linker will thus combine all this code together (the different object files) and determine the resulting offsets to place in the `call` instructions.

The functions you call outside your program are often found within a dynamic library (like it is the case for the C/C++ standard library implementations). When you call a function in a dynamic library, the compiler again leaves a symbol for the linker. The compiler passes several libraries (like the standard libraries such as libc or libstdc++) by default to the linker. The linker will thus find those unresolved symbols in those dynamic libraries. The linker will leave them unresolved for the dynamic linker to resolve them at load time of the program. The dynamic linker will thus place the dynamic libraries in the logical address space somewhere and resolve the resulting offsets in the code of your program.

Shared libraries can be positioned anywhere in the logical address space but the x64 `call` instruction can actually contain a 64 bits immediate. It can thus call anywhere the function was resolved to be in the logical address space.

As to runtime linking, it is really only determined by the `virtual` keyword in C++. For example, look at this code:

```
class A {
   void f() {  }
};

class B: public A {
   void f() { }
};

void g(A& arg) {
   arg.f();
}

int main() {
   B x;
   g(x);
}

```

The code will compile to:

```
A::f():
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-8], rdi
        nop
        pop     rbp
        ret
g(A&):
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     QWORD PTR [rbp-8], rdi
        mov     rax, QWORD PTR [rbp-8]
        mov     rdi, rax
        call    A::f()
        nop
        leave
        ret
main:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        lea     rax, [rbp-1]
        mov     rdi, rax
        call    g(A&)
        mov     eax, 0
        leave
        ret

```

Here, we have a class B that inherited the class A. A programmer would like that, when it calls the f() function, the right function is called based on the type of the object referenced. If the programmer calls f() with a reference to an object of type A, it would like that A::f() is called and vice-versa. This is called polymorphism. You have 2 definitions of the same function and would like that the right one is called based on the type of object referenced. To achieve this, you must make A::f() virtual. In the g() function above (looking at the assembly), A::f() is blindly called without looking at the type of the object referenced. The type of the object referenced cannot be determined before runtime because which object calls the g() function is not known yet. The type of the object referenced must be determined at runtime (during program execution). This is called runtime linking (execution-time address binding).

If you change the code to the following (simply adding the virtual keyword on A::f()):

```
class A {
    public:
        virtual void f() {  }
};

class B: public A {
    public:
        void f() { }
};

void g(A& arg) {
   arg.f();
}

int main() {
   B x;
   g(x);
}

```

The compiled g() function changes to:

```
g(A&):
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     QWORD PTR [rbp-8], rdi
        mov     rax, QWORD PTR [rbp-8]
        mov     rax, QWORD PTR [rax]
        mov     rdx, QWORD PTR [rax]
        mov     rax, QWORD PTR [rbp-8]
        mov     rdi, rax
        call    rdx
        nop
        leave
        ret

```

The g() function will determine which f() function to call based on the type of the object referenced instead of only on the type of the reference in the definition of g().

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


# Question
Title: What does it mean unambiguously that a number is value 0 up to numerical precision?
I was reading that a quantity $x$ is $0$ upt to numerical precision. What does this statement formally mean -- especially in the context of numerical methods or real computers.

---

I looked up in google what that means but nothing useful came up. Then I read the precision page in wikipedia but it didn't really help:

> In computer science, the precision of a numerical quantity is a measure of the detail in which the quantity is expressed. This is usually measured in bits, but sometimes in decimal digits. It is related to precision in mathematics, which describes the number of digits that are used to express a value.

If something is exactly zero instead of a number like 1e-7, my guess is that it's so close to zero that the machine couldn't measure it. Is that not right?

What does that a quantity is some value up to numerical precision unambiguously?

---

PS: I was thinking this could go on SO but given that it's not directly about programming but yes about concrete real values reported by computer, I went for CS. If it belongs somewhere else feel free to comment or help me move it.

cross posted: https://www.quora.com/unanswered/What-does-it-mean-unambiguously-that-a-number-is-value-0-up-to-numerical-precision

# Answer
> 2 votes
I would imagine that it means that given your number format (IEEE-754 single/double/quadruple/etc precision) then you could have numbers which are smaller than machine precision (less than machine epsilon) which are represented by 0 but aren't 0 in reality. Numbers are logarithmically spaced by the machine epsilon value (for double precision it's like 1e-16 or $2^{-53}$) and you can't represent things with finer precision using that many bytes so it's just 0.

In most cases when you have some numerical method you have a tolerance for the method to converge and in some cases it's just machine epsilon. So people may say the error or whatever goes to 0 but they really mean it went to a number that we can no longer represent.

---
Tags: computer-architecture, floating-point, numerical-algorithms, numerical-analysis, number-formats
---


# Question
Title: What happens in the event of a collision in a crypto hash function?
I was reading about hash functions in crypto and a website had mentioned that they were collision free, which obviously isn't possible if there are infinite input values that are mapped to outputs of a finite length. So what happens in the event of a hash collision? How do crypto currencies overcome this problem?

Also, this is slightly off topic, but why can't a hash value be decoded? I mean if values are being mapped, to mapped to an output finite list of encoded values why can't you reverse engineer the process? It can't be truly random there has to be a method for which a hash function maps its values right?

Please let me know if I am using any terminology wrong or am completely mistaken in any assumptions I make in my question. I am just trying to learn so please let me know.

# Answer
> 1 votes
> I was reading about hash functions in crypto and a website had mentioned that they were collision free, which obviously isn't possible if there are infinite input values that are mapped to outputs of a finite length.

Just wonder which site is that. If we are talking about cryptographic hash functions that this is obviously false due to the pigeonhole principle. Well, that is the most simple argument in the combinatorics that rules!

One should really read some good books before a random page on the web.

> So what happens in the event of a hash collision?

That really depends on the case; for example, if you are using MD5 or SHA-1 (The collision resistance of MD5 and SHA-1 is broken!) for digital signatures for hashing the message then signature forging is easy.

For example, a secretary can prepare two documents $a$ and $b$ such that $H(a) = H(b)$ and gives their boss $a$ to sign then use $b$ on their advantage - where $a$ says 'Transfer Alice 1M' and $b$ says 'Transfer Bob 1M'.

Hopefully, cryptography comes a long way to produce hood hash functions that has collision resistance which is $2^{128}$ for SHA-256 by the birthday paradox with 50% probability.

Note that, if you trying to forge someone's signature you need the second-preimage attack that has $2^{256}$ expected cost on SHA-256.

> How do crypto currencies overcome this problem?

By using a good cryptographic hash function that has good collision resistance like SHA-256. One needs to produce around $2^{128}$ documents to find a collision with 50% probability. One may argue that the 50% advantage is too high for the adversary they even can live with 0.1% advantage for which they need to produce $1.5×10^{37} \approx 2^{123}$ documents and this is still not possible. In cryptography, for such even we say negligible.

> Also, this is slightly off topic, but why can't a hash value be decoded? I mean if values are being mapped, to mapped to an output finite list of encoded values why can't you reverse engineer the process? It can't be truly random there has to be a method for which a hash function maps its values right?

As D.W. noted they aimed the be one-way and this is similar to the pre-image resistance of hash functions; given a hash value $x$ it must be hard to find one input $m$ such that $H(m)=x$. The expected cost for $n$-bit hash function is $c\cdot 2^n$.

Reversing a hash function has been asked many times around. Even this is not a well-defined question. Hash functions are clearly not 1-1 functions therefore inverse of an element doesn't need to exist uniquely. Assuming that one needs to find any of them, then how wan can turn back where information is lost. Yes, the non-linear operations destroy information this is why one cannot revert hash functions easily. The computation cost of searching or making a big table is not possible ( say Rainbow). Note that although MD5 and SHA-1 has collision resistance is broken, their pre-image resistance are still there. There is no major cryptographic hash function that has lost it pre-image resistance on the literature.

Hash functions are deterministic, however, they are candidates for Random Oracles (RO) in which (analogy) there is a box in which there is a gnome with a notebook, pencil, and dice. When you asked the hash of a message, they check the list, if exists return this value, if not toss the coin n-times, write the value into the book and return the value to you. As you can see this is similar to hash functions if you ask hash of a message $m$ you get it, if you ask again $m$ then you get the same message (deterministic). If you ask a new message $m'$ that never hashed, you cannot predict that before hashing (random tosses). SHA-256 has an extra property that is not expected in RO; length extension attack, on the other hand, SHA-512/256,SHA-3,BLAKE has immunity to such attacks that makes them close to RO.

# Answer
> 1 votes
No, hash functions are normally *not* collision-free. Instead, they are collision-resistant, which is different. Collision-resistant means that it is computationally difficult to find collisions, not that they don't exist.

Normally hash functions are not invertible (can't be "decoded"), often because the input space is larger than the output space, and also because they are one-way.

---
Tags: polynomial-time, hash, cryptography
---


# Question
Title: Finding a context free grammar (CFG) for a non-context free language (CFL) a^n b^n c^n
It is known that the language $\\{a^nb^nc^n|n\geq0\\}$ is not context-free (we can prove it using the pumping lemma, as shown here: Is $a^n b^n c^n$ context-free?). Yet, this answer claims it has found a context-free grammar for this language. My question is, is it possible to find a context free grammar for a not context-free language?

# Answer
> 2 votes
No. Every context-free grammar generates a context-free language. If you can find a context-free grammar for a language, then the language is context-free.

That assumes the claimed grammar is correct. People claim all sorts of things on the Internet. I wouldn't believe it until you have verified or proven it correct. In this particular case, the answer was incorrect and the grammar doesn't work. I left a comment explaining, and indeed, another answer already responded to that erroneous claim.

---
Tags: formal-languages, automata, context-free, formal-grammars, pushdown-automata
---


# Question
Title: How do these Crypto terms relate to each other and what do they all mean?
Alright this is another day of my pursuit to learn about how crypto works. I have several terms that I have found linked together. I was trying to do research on how the Target Hash is determined and how a Nonce is decided. But I think I am getting lost in several terms and need helping making the connections.

I found a post on here that said the hash is "computed by double-SHA256 the block header, including timestamp, nonce, version, Merkle root, nBits which encodes the difficulty, and previous block hash." and "A target computed from the difficulty only".

I am confused what the difference between a block header and a block's hash value is. Confused about the nonce and target value and how they are decided. Merkle root seems like something out of my depth for now. And I am familiar with difficulty as it relates to finding revenue from proof-of-work mining, but I am not familiar with how difficulty is calculate or what nBits is and how it relates to this mess.

I know this is a lot of stuff to walk someone through but honestly a lot of posts are either older and if I wanted any clarity I am not sure if I would get a response and my other options is articles assembled by gurus that oversimplify stuff.

# Answer
> 1 votes
It really depends on the crytocurrency you are looking at. I will take example on Bitcoin here. Also, Bitcoin has gone through lots of changes which makes it difficult to track everything. For example, the target determination algorithm has changed at least 2 times.

Bitcoin uses SHA-256 as its hashing function. SHA-256 is a very simple algorithm but it is harder to find out and calculate the probabilities of possible attacks against it. The agency responsible for its development (SHA-256) is the NIST agency of the US. You can browse it at http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf. The PDF on the link provided really defines the SHA-2 family of hash functions. It is really easy to implement.

In SHA-256, the program splits the message (the bits of it) into fixed sized blocks adding some padding if necessary. The resulting blocks (each split of the message having nothing to do with the blockchain blocks) are passed through several functions. The hash value of the last block is added to the current hash value. The resulting 256 bits hash is thus dependent on the whole message input. This makes the hash unique with a very high probability.

For Bitcoin, things are quite simple. The algorithm was changed but, early on, the target was simply calculated by the network of nodes with the equation: new target = current target × (minutes to mine the last 2016 blocks / 20160 minutes). 20160 minutes is the time expected to mine 2016 blocks. If the current mining time of 2016 blocks is higher than expected, the new target will become smaller by the equation and vice-versa.

The goal of mining is to get blocks from the network of nodes (which include the transactions) and find a hash of that block that is lower than the value of the target. If the target is very high, the probability of finding that hash increases. I don't have actual probabilities but by logic it is easy to conceive that, the higher the target value, the easier it is to find a hash which is smaller.

This mining process must have a way to make the hash of the block vary which introduces the nonce. The nonce is a 32 bits value which is started at 0 and stored in the header of the block. The hash of the block is made and the nonce incremented by one at every unsuccessful attempt. If the nonce reaches its maximum capacity. The coinbase transaction is used.

The coinbase transaction is used to compensate the miner and to further increase the amount of possible different nonces. The coinbase transaction has special requirements and it is verified to make sure it meets some requirements. For example, the nodes will check if the miner doesn't compensate himself too much based on the current miner subsidy (starting at 50 BTC and halved every 210k blocks) and on the amount of transaction fees included in the transactions of the block.

Transactions are quite complex structures. They have inputs and outputs. The coinbase transaction will thus have lots of unused fields and inputs/outputs will be mostly empty. It is only the miner compensating itself. All those fields can thus be used to change the hash value of the block in order to find a hash smaller than the target.

As to transactions themselves. I don't know a lot about them. I know they rely a lot on assymetric cryptography whereas a public key can be shared and its private counterpart is kept private. It is very hard to find the private key from the public key so you can prove you own a certain address by providing its associated public key and signature.

Merkle root is simply a hash of all the transactions. Transactions are simply arrays of bytes with some added meaning. They are hashed in pairs until a "root" is found.

---
Tags: algorithms, hash, cryptography, blockchain
---


# Question
Title: How to partition N numbers into K groups with constraints on the size and sum of each group?
Suppose we are asked to assign $N$ numbers into $K$ mutually exclusive groups. The partition has to satisfy two constraints for each group. The first one is that group $k$ must contain exactly $n\_k$ elements. The second one is that the sum of all numbers in group $k$ must be in the range $(l\_k, u\_k)$. Of course we have $\sum\_{k}^{K}n\_k=N$.

For example, suppose there are 1000 numbers and the sum of the 1000 numbers is 1e5. We need to divide the 1000 numbers into 3 groups, say Group A, B and C. Group A, B and C must contain exactly 600 numbers, 300 numbers and 100 numbers, respectively. Additionaly, the sum of all numbers in Group A must be in the range (1e4, 7e4), the sum of Group B in the range (2e4, 4e4) and the sum of Group C in the range (1e4, 3e4).

Is there an algorithm to solve such a problem?

# Answer
> 2 votes
Of course there are algorithms, for example you can enumerate all possible partitions and check whether one of the partitions satisfies the constraints.

If the question is instead "Is there an efficient algorithm?" for such a problem, then unless P = NP the answer is *no*, since the problem includes 3-PARTITION as a special case (take $n\_k=3$ for all $k$ and $l\_1=u\_1=...=l\_K=u\_K$).

---
Tags: optimization, partitions
---


# Question
Title: Can a nondeterministic Turing machine improve upon a P-time problem?
Linear search is solvable in O(n) time by a deterministic Turing machine. If we apply a nondeterministic Turing machine to the problem, can we solve the decision problem "Is $x$ in the array $A$?" in O(log n) time or even O(1) time? If my understanding of nondeterminism is correct then the answer is yes because it can follow multiple computation paths at once? I.e. the "genie" would just tell the algorithm where the element we are searching for is to be found?

# Answer
No. A Turing machine still needs to move the tape head to each element in the array, by moving one symbol per step, so O(N) movements on average. If the elements each occupy 1 space on the tape, and the 5th element is the one being searched for, the shortest path to an accept state still requires a minimum of 5 steps (to move right 4 times and then check the symbol under the tape head).

If we use some kind of nondeterministic random-access machine instead, where the machine can jump instantly to any element, then it can be done in fewer than O(N) steps, probably O(log N) if not O(1). This would depend on the particular type of machine used.
> 4 votes

---
Tags: turing-machines, nondeterminism
---


# Question
Title: Prove that Turing Machine ever writes a blank symbol over a non blank symbol is undecidable
I have been given the following problem from the book Introduction to the Theory of Computation by Martin Sipser and was wondering if my solution is correct: Determine if a Turing Machine ever writes a blank symbol over a non blank symbol over the course of its computation on whatever string given on input, formulate this problem as a language and prove that it is undecidable.

This is my solution:

The langauge is the following: L ={\<M\> | M is a single tape Turing Machine and M writes a blank symbol over a non blank symbol during the course of its computation on any input string}.

---

This is my solution to part 1.

Let's assume that L is a decidable language and H is its decisor, we can then prove that there exists a decisor for ATM (impossible!).

On input \<M , w\>:

1. Build a new Turing Machine N as follows
2. Execute decisor H on input
3. Return the output

N = On any input:

1. Execute M on input w and if it accepts write a blank symbol on a non blank symbol in the tape then accept otherwise reject

---

# Answer
> 2 votes
The overall structure of your proof is fine, but the construction of N is insufficient. You are making sure that if M halts, then N will overwrite a non-blank with a blank. However, you also need to make sure that if M does not halt, then N never overwrites a non-blank with a blank - but it might, because M might do that.

You'll want to fiddle around with the tape alphabet that N is using a bit to fix this. When M attempts to do overwrite a non-blank with a blank, N needs to do something that keeps the "spirit" of the algorithm but doesn't involve writing a blank...

---
Tags: turing-machines, computability, undecidability, semi-decidability
---


# Question
Title: "partial sorting" algorithms (aka "partitioning")
**Context:**

When trying to tame real-world datasets that contain outliers and noise, the interquartile mean is a handy tool: you sort the data, throw away the top and bottom 25% of the data and take the mean of what's left. (Of course, you can choose other partitioning than top and bottom 25%.)

Which led me to wonder: is there any efficiency to be gained only partially sorting the array? That is, if we describe three groups: A is the low quartile, B is the middle, and C is the high quartile, we don't care if A or C are sorted: we're going to discard them. And we don't care if B is sorted since we're only going to take the mean of its values. It's sufficient that the data is partitioned into those three groups.

**The question:**

* is there a "partial sorting" algorithm that is more efficient than a full sort that will yield those three groups?
* Are there additional savings if the array is always a power of 2 (assume N \>= 4)?
* What if you want to adjust the partition boundaries other than quartiles? Does that make it less efficient?

**Update**

I've added "partitioning" to the title, since (I now know) that's the correct term for what this question is about. Thank you to everyone with good answers!

# Answer
> 26 votes
The algorithm quickselect can return the $k$-th value of an unordered array in average linear time. It can be "improved" (though not so much in practice) using the median of medians to guarantee worst case linear time.

Using that, you can quickselect the $\frac{N}4$-th, $\frac{N}2$-th and $\frac{3N}4$-th values. The algorithm will partition the array into the four desired parts. All this can be done in linear time. It is optimal since you need to check each element at least once.

As long as you use a constant number of them, you could use other values than quartiles (like deciles, for example).

# Answer
> 10 votes
There are a couple of algorithms which are useful for this particular problem. Although they are usually described as selection algorithms, which compute the $k^{th}$ order statistic of an unordered dataset, they can also be used for in-place partitioning of the data-set; a $V\_1, V\_2, ..., V\_n$ is partitioned at $k$ if $\forall i\<k,V\_i\le V\_k$ and $\forall i\>k,V\_i\ge V\_k$.

In other words, $V\_k$ is at the position it would be if $V$ were fully sorted, and no preceding element is greater. This is sometimes called an "unordered partial sort", but I think "partition" describes it better.

Unlike sorting, this operation can be performed in time $O(n)$ and space $O(1)$, although the most common algorithm only promises expected $O(n)$ time. (In theory, worst-case $O(n^2)$ is possible, but superlinear times are rare with random data and the guaranteed $O(n)$ time algorithm has a lot of overhead.) The best-known instance of such an algorithm is C.A.R. Hoare's Quickselect but there are many other possibilities.

For computing a truncated subsequence, such as the interquartile range, you can gain a bit of extra efficiency by doing both partitions at the same time. Of course, this doesn't improve the asymptotic efficiency, but the real-world execution time is less.

Quickselect can be thought of as the beginning of a quicksort (and it's not a coincidence that Hoare also developed the quicksort algorithm.) It avoids the $\log n$ factor by only recursing on one side of the pivot. (Or, equivalently, looping, which demonstrates $O(1)$ space.) Since the only outcome required is that the vector be partitioned at $V\_k$, it's only necessary to process one side of the selected pivot. This should be reasonably intuitive; after partitioning with the pivot, all the elements preceding the pivot point are no greater than the pivot, and all elements following it are at least as great. There must either be at least $k-1$ preceding elements or at least $n-k$ following elements (or both); whichever side of the array satisfies that condition cannot possibly contain the $k^{th}$ order statistic, and thus there is no need to examine it further.

As with quicksort, selecting a good pivot --or at least, not selecting a bad pivot-- is crucial. If you somehow managed to always select a pivot whose value is near the minimum or maximum of the dataset, you'd end up with quadratic time. (But since all recursive calls are tail calls, even in pathological cases, the space requirement continues to be constant.) In practice, you can avoid this problem by selecting a random pivot and using a partitioning algorithm which is tolerant of datasets with large numbers of repeated values.

To compute the interquartile range, you might start by using the selection algorithm to find $V\_{n/4}$ and then call the algorithm again on the upper three-quarters of $V$ to find $V\_{3n/4}$. But it's evident that this involves quite a bit of duplication of work at the beginning. A better solution is to partition the array until a pivot is discovered which is inside the interquartile range. Once the array is partitioned at that point, quickselect can be called independently on the two sides of the pivot, to select the first quartile on the left and the third quartile on the right.

Quickselect is probably the best solution for the interquartile range, but if the desired subsequence endpoints are closer to the ends of the array --for example, if you want to find the first and ninth decile-- then you might consider using a partial heapsort. This algorithm partitions at $V\_k$ in worst-case $O(n \log k)$ (but on average, the time complexity is close to $O(n)$), as follows:

1. Use **heapify** to turn the first $k$ elements of $V$ into a max-heap.
2. For each of the remaining $n-k$ elements:
    * If the element is less than the heap's maximum, swap it and the heap's maximum and repair the heap.
    * Otherwise, continue.

If you build the heap backwards, so that the maximum is at position $k$, then you'll end up with $V$ correctly partitioned. (Otherwise, you'll have to swap $V\_1$ and $V\_k$.)

Repairing the heap at step 2 takes $O(\log k)$, but note that it doesn't always happen. In fact, assuming the dataset is randomly ordered, it happens less and less frequently as you proceed, since the heap's range shrinks each time an element is replaced making it less likely that a new element will need to be inserted.

Again, this algorithm can be adapted to find a range, by building a reversed max-heap at the beginning of the array and a forward min-heap at the end of the array, and then scanning the elements in between. This doesn't help as much as it does with quickselect, but it still helps a bit.

If you're worried about the possibility of a pathologically sorted input --not so much of a worry as it would be for quicksort, since the worst case here is log-linear rather than quadratic-- you can shuffle the input as you go by swapping each element with a randomly selected element from the unprocessed segment, in effect a single step of the Fisher-Yates shuffle algorithm. Although that makes worst-case performance extremely unlikely, it does have a practical cost, because reading a large array in random order is much less cache-friendly than reading the array sequentially.

# Answer
> 4 votes
> is there a "partial sorting" algorithm that is more efficient than a full sort that will yield those three groups?

Since you're talking about "real-life" scenarios rather than theoretical asymptotics, here's something you could do:

* Take a number of uniformly and independently sampled values from the array, and use them to estimate the distribution of values; or at least - estimate the values of your first and third quartiles. The exact number of samples depends on the probability-and-accuracy combination you're interested in, and what you know about the size of the value space; but let's not go into the statistical details here. Suffice it to say that getting a value in a given quarter happens with probability 1/4, independently of other samples, so you can apply large deviation bounds.
* Now that you have a likely-decent-estimate of the quartiles, perform your filtering. With very high probability, you now have a little more or a little less than 50% of the elements, ranging between around the 1st quartile and around the 3rd quartile.
* You can know how far you are from having gotten the actual quartiles, by keeping count of how many elements are in each of the 3 sets you've formed.

This is usually enough for your real-life needs, as the choice of quartiles is typically arbitrary, i.e. you usually want "the stuff that's around the middle", and the above gives you this. The overall time complexity will be linear in the length of the array.

... Now, you might be asking - why did I even bother suggesting this solution? You already got suggestions of linear-time solutions (even if it's estimated-linear-time), right?

Well, the answer is **this is efficient in real life**. Your $O(\cdot)$ constant will be *extremely low* in term of abstract computational operations; and your memory access pattern (after the initial sampling) will be *ideal*: A clean single consecutive pass over your elements. Cache friendly, CPU prefetch friendly, and it can even be parallelized relatively well.

> Are there additional savings if the array is always a power of 2 (assume N \>= 4)?

I doubt it. You're thinking like a theoretician here - they/we always hate it when we have to soil our neat pseudo-code with some "if it's not divisible by two" corner cases.

# Answer
> -1 votes
Basically what you're asking about with partitioning into three groups is a famous Dutch national flag problem posed by Dijkstra himself and analysed throughout (with proofs) in his book "A Discipline of Programming". Highly recommend. :)

# Answer
> -1 votes
You have an array of n items, and you want items number l to r to be where the would be in a fully sorted array, and you don't care where the other elements are.

A very slight modification of quicksort does this easily. Start with the subarray from 1 to n. Using the quicksort partitioning method, you create two portions from 1 to k and from k+1 to n. At this point, quicksort would sort both halves recursively. Instead you only handle partitions containing at least one point from l to r.

```
Normal Quicksort: Call sort (1, n)
sort(l, r):
    if r > l
        partition (l, r) to a..b and c..d
        sort(a, b)
        sort(c, d)

Quicksort to get range x, y: Call sort(1, n, x, y)
sort(l, r, x, y)
    intersect l..r with x..y
    return if intersection is empty
    partition (l, r) to a..b and c..d
    sort(a, b, x, y)
    sort(c, d, x, y)

```

---
Tags: sorting, partitions
---


# Question
Title: Use Hoare axiom for array-componenet assignment to determine the weakest pre-condition
ASSERT( P ) /\* determine what is P \*/

A\[i\] = A\[m\];

A\[k\] = 2;

ASSERT( A\[i\] == x + 5 )

# Answer
> 0 votes
I don't know about the weakest but I can tell you about candidate precondition,a\[m\] is assigned to a\[i\] so the range of m must concide with that of i,the postcondition is a\[i\]==x+5 so a\[m\]==x+5.

I have used the fact that array is a collection of tuples of index and value and thus the above result.

---
Tags: hoare-logic
---


# Question
Title: For any two languages A and B there exists J such that both A and B are Turing reducible to J
Here is the my attempt:

**Proof :** Suppose $J = \\{aa' \mid a \in A\\} \cup \\{bb' \mid b \in B\\}$ such that $a'$ and $b'$ are the symbols that do not belong to any $w \in A \cup B$ and $a,b$ are strings.

We build a Turing Machine(Oracle) $M$ on input $w$ :

* Query oracle if $wa' \cup wb' \in J$.
* If YES, Accept. Reject Otherwise.

Now we can safely deduce $w \in A \iff wa' \in J$ and $w \in B \iff wb' \in J. \\: \square$

---

which is not very much different from THIS ANSWER.

Is there any way we can prove this using hierarchy of languages :

# Answer
> 3 votes
I don't think this proposition can be proved using the hierarchy of languages as illustrated in the question alone. That hierarchy of languages is too coarse to imply directly any implication between decidability of different languages.

Since the structure of the Turing degrees is extremely rich and complicated, it does not make much sense to stick to the general hierarchy of languages if one wants to find more about them, anyway.

---

The construction of $J$ in the question is good.

However, the Turing machine $M$, which accepts the language $A\cup B$, is not used at all. In particular, it has nothing to do with "we can safely deduce $w \in A \iff wa' \in J$ and $w \in B \iff wb' \in J$."

What should have been done is to show that given an oracle $O$ that decides $J$,

* there is an oracle machine with access to $O$ that decides $A$ and
* there is an oracle machine with access to $O$ that decides $B$.

For example, we can build oracle Machine $T\_A$ that on input $w$:

1. Query $O$ if $wa'\in J$.
2. If YES, accept. Reject otherwise.

Since $w\in A\iff wa'\in J$, $T\_A$ decides $A$.

---
Tags: complexity-theory, turing-machines, undecidability, decidability
---


# Question
Title: If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular
Prove/Disprove: If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular.

I think that this one is true, but I am stuck:

Since $R$ is not regular, it is infinite, so $R \cup L$ is also infinite.

Since $R$ is non-regular, it must be that $R \cup L$ is not regular.

It just doesn't feel complete for me...

Any help will be amazing!

Thanks!

# Answer
> 1 votes
(weird choice of letter $R$ for a non-regular language).

Since $L$ is finite, so is $L\setminus R$ (hence regular).

Now, note that $R = (R\cup L) \setminus (L \setminus R)$. Can you find a contradiction if $R\cup L$ is regular?

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


# Question
Title: Store strings which have same start, but different end
I need to store a list of strings in some files. In this moment, there are too many strings in too many files, which is a problem for me.

Here is an example of strings:

```
aaaaaaaa
aaaaaaab
aaaaaaac
aaaaaaad
aaaaaaae
aaaaaaam
aaaaaaan
aaaaaaao
aaaaaaap
aaaaaabc
aaaaaabd
aaaaaabe
aaaaaabf
aaaaaabg
....
aaaraaai
aaaraaaj
aaaraaak
aaaraaal
....
acaraaao
acaraaap
acaraaaq
acaraaar

```

As you can see, there is an order, somehow, but is not an order which permits me to play to much.

Some example of what I need based on above example:

```
aaaaaaaa(till e)
aaaaaaam(till p)
aaaaaabc(till g)

```

and so on. But is not that good.

There must a be better way to do that.

I am looking for an algoritm to store the strings in files and those files to have small sizes. If the files are too big, then it will be hard to include them in my application.

Tell me, what's the best way to do what I want ?

**Edit:**

Ideally, I want to store the strings in a json file(s).

The file(s) will be further included in a web application. That's why I want to have a small size for the files. Else, my users should wait too much to download the files.

Of course, if I will store the strings in a file in a better way, then I should parse the content of the file(s) to get the strings back (to be readable). I do prefer this, yes.

# Answer
> 1 votes
How many strings are there in total, and what is the last string in the set?

Assuming these strings are all in lexicographic order and there are no duplicates, what you have is a bunch of 8-digit numbers expressed in base 26.

I'm going to assume that all strings are possible, which means that the set of all possible strings has size $n=26^8$. But there are only $k$ strings stored. The number of possible subsets is, therefore, $n$ choose $k$. And so, assuming the strings are statistically independent, you *need* this many bits to store the set of strings:

$$\log { n \choose k }$$

(All logarithms are base 2 by default; we will use the natural logarithm function $\ln$ in a little bit.)

Note that word, "need". Under these assumptions (which are just assumptions), any representation which uses this many bits is optimal.

A good approximation when $n$ is large (which it is in this case) is to use the binomial entropy function:

$$H(p) = - p \log p - (1-p) \log (1-p)$$

Then:

$$\log { n \choose k } \approx n\\,H\left(\frac{k}{n}\right)$$

So a very interesting number to know about here is $p = \frac{k}{n}$, which is the probability of a string being in the set.

If $p \approx \frac{1}{2}$, then $H(p) \approx 1$, so $n\\,H(p) \approx n$. An optimal representation is to store a bitmap of $n$ entries.

If $p \ll \frac{1}{2}$, then $n\\,H(p) \approx k \log n$, and so an optimal representation is to store each of the $k$ strings using $\log n$ bits each.

If $p \> \frac{1}{2}$, then it's probably more efficient to store the strings that are *not* in the set.

There is a lot of work on compressing increasing integer sequences; it is a standard workhorse of information retrieval. But what I'm going to suggest for this application is Elias-Fano coding, because it's easy to understand.

We will introduce a parameter $b$. Represent each string as a number (convert from base 26), and split each number into the quotient and the remainder when divided by $b$.

We will actually work out $b$ later. For the moment, I will assume $b=4$. We will represent each base-26 numeral $x$ as an integer, and as a pair $(q,r)$ where $q$ is the quotient $\left\lfloor \frac{x}{b} \right\rfloor$, and $r$ is the remainder $x-qb = x \bmod b$.

```
aaaaaaaa = 0 = (0,0)
aaaaaaab = 1 = (0,1)
aaaaaaac = 2 = (0,2)
aaaaaaad = 3 = (0,3)
aaaaaaae = 4 = (1,0)
aaaaaaam = 12 = (3,0)
aaaaaaan = 13 = (3,1)
aaaaaaao = 14 = (3,2)
aaaaaaap = 15 = (3,3)
aaaaaabc = 28 = (7,0)
aaaaaabd = 29 = (7,1)
aaaaaabe = 30 = (7,2)
aaaaaabf = 31 = (7,3)

```

...and so on. We store the remainders as an array:

```
0 1 2 3 0 0 1 2 3 0 1 2 3

```

We only have to use $\log b$ bits for each entry. In this case, $\log 4 = 2$, so this bit string encodes the remainders:

```
00 01 10 11 00 00 01 10 11 00 01 10 11

```

The compressed size of this array is $k \log b$ bits.

For the quotients, what we will do is count the number of strings that have each quotient. There are 4 strings with quotient 0, 1 string with quotient 1, no strings with quotient 2, 4 strings with quotient 3, and so on. So we can represent this as an array:

```
[4,1,0,4,0,0,0,4]

```

To compress this array, we will use a unary code:

```
11110 10 0 11110 0 0 0 11110

```

This unary representation has an interesting structure. The number of `1`s in the compressed representation is exactly equal to $k$, and the number of `0`s in the representation is exactly equal to $\left\lceil \frac{n}{b}\right\rceil$, the maximum possible quotient.

So, ignoring ceilings and floors, the compressed size is the combined size of these two compressed arrays, in bits:

$$k \log b + k + \frac{n}{b}$$

This is minimised when:

$$b = \frac{\ln 2}{p}$$

It is convenient to round $b$ to the next highest power of 2, so that the array for the remainders are stored using a whole number of bits.

And so using this value of $b$, the total size is in bits is:

$$k \log \left( \log (\ln 2) - \log p + 1 + \frac{1}{\ln 2} \right) \approx 2k + k \log \frac{1}{p}$$

You can verify for yourself that this is close to optimal over a large range of $p$.

# Answer
> 0 votes
The simplest and most effective first step is to use gaps and consecutive-run-lengths to represent the strings.

Assume all strings are 8-lowercase-letter strings.
Let $a=0$, $b=1$, $c=2$, $\cdots$, $z=25$.
Each string also means a number in base 26, which is also the number of strings that is lexicographically smaller than the string.
Imagine aaaaaaaa as the starting reference string.

The strings in the question will be represented as $$0, 5,\ \ 7, 4,\ \ 13, 5,\ ..., 4,\ \ ..., 4,\ \ \dots$$ where
$0,5$ means a run of $5$ numbers starting from $0+0=0$, i.e, from aaaaaaaa to aaaaaaae.
$7,4$ means a run of $4$ numbers starting from from $0 + 5 + 7 = 12$, i.e., strings from aaaaaaam to aaaaaaap.
$12, 5$ means a run of $5$ number starting from $12 + 4 + 12 = 1\cdot26+2$, i.e., strings from aaaaaabc to aaaaaabg.
$\cdot, 4$ means $4$ strings from aaaraaai to aaaraaal.
$\cdot, 4$ means $4$ strings from acaraaao to acaraaar.

---

The sequence of numbers obtained above can be compressed by various compression tools such as xz, bzip2 and brotli.

A rough simulation with $p\approx0.355$ produces compression ratio around something like $5497787/961011\approx5.72$, assuming initially each string is stored with 8 bytes.

# Answer
> 0 votes
In my comment, I have suggested to view (*model*) the sequence of strings as an *initial string* and *consecutive runs of increasing strings alternating with gaps*.
Encoding details aside and taking the successor to `aaz` to be `aba`(*number base 26₁₀*), the suggested representation `aaaaaaaa5,8,4,12,5` (4&12 mixed up above) has length 18 for 14 strings of length 8:
5 strings from `aaaaaaaa` to `aaaaaaae`, a gap of 8,
4 strings from `aaaaaaam` to `aaaaaaap`, a gap of 12,
5 strings from `aaaaaabc` to `aaaaaabg`:

I think

> ```
> aaaaaaaa(till e)
> aaaaaaam(till p)
> aaaaaabc(till g)
>
> ```

quite decent, actually.

Not optimal (I think $n$ choose $k$ is), but simpler to adapt, say to occasional lexicographically smaller strings: `aaaaaaaa5,8,4,12,5,-13,…` or strings from large alphabets.

---
Tags: algorithms
---


# Question
Title: Prove a greedy algorithm that obtains the minimum integer with at most k adjacent swaps is correct
This problem is from LeetCode.

> You're given a string num representing the digits of a very large integer and an integer k. You are allowed to swap any two adjacent digits of the integer at most k times.
>
> Return the minimum integer you can obtain also as a string.

My question is, why does the following greedy algorithm work?

```
minimum_integer(num, k):
    n <- length of num
    i <- 0
    while i < n and k > 0:
        pos <- position of the first smallest element in num[i..min(n-1, i + k)]
        while pos > i:
            swap pos and pos-1 of num
            decrease pos by 1
            decrease k by 1
        increase i by 1
    return num

```

The algorithm makes sense intuitively; we essentially move the minimum digit in a window of size at most k into each possible position, and since we minimize leading digits each time starting from the first leading digit, it makes intuitive sense that the resulting number should be minimized. But I'm not sure how to prove it produces an optimal solution using an exchange argument.

# Answer
Let $A$ be the greedy algorithm you presented and $A'$ be the algorithm that correctly solves the problem.

Let $m=d\_{n-1}d\_{n-2}d\_{n-3}...d\_2d\_1d\_0$ be the solution obtained by $A$ and $m'=d'\_{n-1}d'\_{n-2}d'\_{n-3}...d'\_2d'\_1d'\_0$ be the number obtained by $A'$.

First, some observation about $A$. For each index $0 \le j \le n-1$, $A$ select that smallest digit from indices $\le j$ that can be placed at index $j$ using the remaining number of moves. This implies that once a digit is in-place, it remains in its position until the end. Now, the number of swaps $A$ uses to move a digit initially at index $i$ is $j - i$, which is the minimum possible if swapping adjacent digits is the only allowed move. Therefore, $A$ uses the minimum possible moves to place a digit to its place.

Let $i$ be the last index that $A$ updated before it exhaust all the remaining moves. Because $A$ selects the minimum digit that can be placed at index $j \ge i$ using the minimum number of moves while not exceeding the available moves, it must be that $d\_j = d'\_j$ for $i \le j \le n-1$. Now, since $A$ uses the minimum number of moves possible to move a digit to its final position, the total number of moves $A'$ uses to change all index $j \ge i$ cannot be less than the total number of moves used by $A$. Therefore, both $A$ and $A'$ cannot change any remaining index less than $i$, thus $d\_j = d'\_j$ for $0 \le j \le i-1$. Finally, $m = m'$.
> 2 votes

---
Tags: algorithms, greedy-algorithms, correctness-proof, integers
---


title: What's grammar for a^n b^n c^n d^n

text:
# Question
Title: What's grammar for a^n b^n c^n d^n
What wiil be grammar rules for the language L={a^n b^n c^n d^n; n\>0}

# Answer
> 1 votes
May I propose the following indexed grammar $G= ( \\{S,A,C\\}, \\{a,b,c,d\\}, \\{f\\}, S )$:

* $S\[\sigma\] \to S\[f\sigma\]$
* $S\[\sigma\] \to A\[\sigma\]\\, C\[\sigma\]$
* $A\[f\sigma\] \to a\\, A\[\sigma\]\\, b$, $\quad A\[\\,\] \to \varepsilon$
* $C\[f\sigma\] \to c\\, C\[\sigma\]\\, d$, $\quad C\[\\,\] \to \varepsilon$

---
Tags: turing-machines, formal-grammars, context-sensitive
---


# Question
Title: Efficient data structure for insertion, deletion and smallest-not-in-range query on an array of integers
I'm trying to make a data structure $A$ that has the following features:

* insert($a$) operation : insert given integer $a$ to $A$. It is assured that all integers are unique.
* delete($b$) operation : delete $b$ from $A$.
* smallestNotInRange($p$,$q$) : returns the smallest value $k$ such that $k\in \[p,q\]$ and $k \notin A$.
* Each operation should take $O(\log{n})$ time and should use $O(n)$ space. $n$ is the number of integers in $A$.

Because of the last function the first thing I thought of was using segment trees. However, it was not the right choice because it uses $O(n \log n)$ space.
The next thing I thought of was using a balanced binary search tree. Everything is good for insert and delete operations because insertion and deletion of a balanced binary search tree take worst-case runtime of $O(\log n)$ and the data structure use $O(n)$ space. The problem is with the smallestNotInRange operation. When the number of integers in range $\[p,q\]$ is less than $\log n$ the operation will take $O(\log n)$, however, when the number of integers in range $\[p,q\]$ is greater than $\log n$ the operation will take $O(n)$. How can I resolve this problem and get this to work at worst-case runtime of $O(\log n)$?

# Answer
You can use a balanced BST. For each node $n$, let $n.lsize$ be the size of the left subtree of $n$. Insert and delete is just standard BST add and remove with size updating. To implement `smallestNotInRange` do the following:

1. Find node $n\_p$ containing $p$. If it does not exist, then $k =p$, else let $size\_{p\_{left}} = n\_p.lsize$.
2. Starting from the root, find the shallowest node $n\_m$ such that $p \le m \le q$. To do this, check the value of the current node. If the value is less than $p$ move down to its right subtree. Else, if the value is greater than $q$ move down to its left subtree. Otherwise, the current node is $n\_m$. If at some point, the visited subtree is empty, then $k = p + 1$.
3. If $n\_m.lsize - size\_{p\_{left}} \lt m - p$ and $n\_m$ is the parent of $n\_p$, then $k = p + 1$. Otherwise, let $q = m - 1$ and repeat step 2, but this time starting at the left child of $n\_m$, instead of the root.
4. If $n\_m.lsize - size\_{p\_{left}} = m - p$ and $m = q$ then there is no such $k$. Otherwise, set $size\_{p\_{left}} = -1$, $n\_p = n\_m$, and $p = m$ and repeat step 2, but this time starting at the right child of $n\_m$, instead of the root.

For step 1, it is self-explanatory why $k=p$ when $n\_p$ does not exist. The variable $size\_{p\_{left}}$ is initially set to the number of elements in the left subtree of $n\_p$, which are elements not in $\[p,q\]$.

The idea behind steps 2 to 4 is like doing a binary search to find the subrange in $\[p,q\]$ closest to $p$, that contains an element not in $A$. Step 2 is like the "finding the middle" part of the binary search.

Step 3 checks if there is a missing element in the subrange $\[p,m\]$. If there is, it continues the search in that subrange. There is a missing element when $m-p$, the expected number of elements in the range, is greater than $n\_m.lsize - size\_{p\_{left}}$. The subtraction ensures that when $n\_p$ is in the left subtree of $n\_m$, we do not count the elements in the left subtree of $n\_p$ since they are not in $\[p,m\]$.

If there is no missing element in $\[p,m\]$, step 4 performs the search in the subrange $\[m,q\]$ instead. When going to this subrange, the new $n\_p$ will never appear as subtree of the $n\_m$ hence, the left subtree of $n\_m$ will also not contain elements that are not in $\[p, m\]$. Therefore, we set $size\_{p\_{left}} = -1$. This will effectively add 1 to $n\_m.lsize$ when comparing it to $m - p$, since $m-p$ takes into account $p$ but $n\_m.lsize$ doesn't.

As for the running-time, step one takes $O(\log n)$ in the worst-case if it happens that $n\_p$ is a leaf of a balanced BST. For steps 2-4, this is just modified BST search. Choosing the node to visit is controlled by the result of comparing $n\_m.lsize - size\_{p\_{left}} $ and $m - p$. Each time a node is visited, only constant amount of work is done, thus the running-time for the entire steps 2-4 is also $O(\log n)$ because the tree is balanced. Therefore, the entire procedure is $O(\log n)$.
> 5 votes

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


# Question
Title: 3D gift wrapping algorithm: how to find the first face in the convex hull?
I am implementing the gift wrapping algorithm to find the convex hull of a set of points in the 3D space.

However, all the articles I have read seem to omit the description of the first step of the algorithm; namely, finding a face (that is, a triangle) in the set that will definitely be in the convex hull (and doing so in $O(n^2)$).

Example of such an article: https://www.sciencedirect.com/science/article/pii/S002200000580056X

I do understand how to find a *vertex* that definitely be in the convex hull: just take one with extreme coordinates. However, I don’t know how to approach the problem for edges or faces.

# Answer
Find a point with minimum $x$. $O(n)$.

Find the next vertex by 2D gift wrapping on the 2D projection of the points on a plane. $O(n)$.

The third vertex is obtained by comparing the faces built from the above edge and all remaining points. $O(n)$.
> 1 votes

# Answer
For simplicity, let us assume no four points are in the same plane. Otherwise, adapt the following procedure to deal with the degenerated cases.

Define the usual lexicographic order on points. That is, for any two distinct points $P$ and $Q$, $P\<Q$ if the $x$ coordinate of $P$ is smaller than that of $Q$, or, if their $x$ coordinates are equal, the $y$ coordinate of $P$ is smaller than that of $Q$, or, if both x coordinates and y coordinates are equal, the $z$ coordinate of $P$ is smaller than that of $Q$.

Iterate through all points, keeping tracking of three smallest points. At the end of iteration, those three smallest points are the vertices of a triangle in the convex all.
> 0 votes

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


# Question
Title: Doubt about computing running time / time complexity of a function in Python
I am learning about time complexity now, and I am working with BST (Binary Search Trees).

This question needs some context and this is a follow up post to this post. Basically, I would like to compute the time complexity of the function below. The function below refers to a BinarySearchTree where 'u.l' represents the left child of 'u' and 'u.r' represents the right child of 'u'. Additionaly, 'u.p' represents the parent of 'u' and 'self.r' represents the root of our binary search tree.

```
def remove_node(self,u):
    if u.r == None or u.l == None: self.splice(u)
    else:
        w = u.r
        while w.l != None:
            w = w.l
    u.x = w.x
    self.splice(w)

```

In the post I linked, we showed that `splice(self,u)` is a function with `O(1)` time-complexity and thus every statement that uses this function only will also have `O(1)` time complexity. Being aware of this, the best case scenario will be obviously when we enter the first `if` statement and in this case we will have that `remove_node` function is `O(1)` time-complexity (since `u.x = w.x` and `self.splice(w)` are also `O(1)` procedures).

With this being said, we must now study the worst case scenario, which is when we enter the `else` statement instead of the `if` statement. `w = u.r` is an atributtion and so it is `O(1)` in time complexity.

And now is where my trouble begins. The main question here is: How many times will be `while` cycle run? Well, this one is obvious. It will run as much times as the number of nodes in the left path of `u.r` to the end of the tree. But how would one translate this into time-complexity? Because we might have a BST such that `u.r == None` and thus the `while` cycle will run 0 times, but we might also have a BST such that `u.r != None` and in this case the `while` cycle will run a total of `n`times, where `n` represents the number of nodes to the left of `u.r` and its left descendants.

Below I give two examples of how many times the while cycle would run in this scenarios:

```
          u
            \
             u.r
              /
           u.r.l                   => The while cycle will run 4 times
          /    \
     u.r.l.l   u.r.l.r
     /
u.r.l.l.l

```

But there are other examples. How would one determine the time complexity of this function? Thanks for any help in advance!

# Answer
You could say that this function has a time complexity of $\mathcal{O}(h)$, where $h$ is the height of the BST.

You could be more precise and say that it is a $\Theta(h)$ in the worst case. This means that the complexity will never be more than linear in the height, but adds that this linear case can be reached (even if not every time as you have stated).
> 5 votes

# Answer
While Nathaniel's answer is obviously right, there is something else to consider: Do the operations that you perform change the shape of your tree? I binary tree with 1000 nodes could have a height of 10, or it could be degenerated to a linked list with a height of 1,000. That would happen if you have a naive implementation of "add a node" and add 1,000 nodes in sorted order.

So what is the height of your average tree, based on the algorithms that you are using?
> 4 votes

---
Tags: complexity-theory, time-complexity, runtime-analysis, python
---


# Question
Title: Check if a string can be obtained by a sequences of insertion of "abc"
Let $a$ initially be an empty string. One can transform $a$ into $b$ in the following way: $a$ becomes $a\_{left}+$"$abc$"$+a\_{right}$, where $a=a\_{left}+a\_{right}$ in a prior state. $a\_{left}$ or $a\_{right}$ can be the empty string. Given a string $b$, check if it is valid, i.e. check if it can be obtained from $a=$"" by applying the transformation described above zero or more times.

I have written an algorithm, and I am almost 100% sure it is correct. I draw this conclusion almost exclusively from having run the algorithm on many test cases. I am, however, unable to prove the correctness. In other words, I am unable to understand how it works at a deep level. Can you help me with that? Can you clearly and thoroughly prove the correctness?

Algorithm:

```
    let stck be an empty stack of characters
    for each character c in the string b:
        if c=="c":
            if length of stack is strictly less than 2:
                return False
            if the second to last character is not "a" OR the last character is not "b":
                return False
            stck.pop
            stck.pop
        else:
            stck.push(c)

    return true if and only if stck is empty

```

# Answer
Congratulation, your algorithm works fast and correctly like magic. However, why is it correct?

**Claim: A string $s$ is valid iff either $s$ is empty or the two letters to the left of the leftmost occurrence of $c$ in $s$ is "$ab$" and $s$ with that "$abc$" removed is still valid.**

Proof: "$\impliedby$" is by definition.

"$\implies$". Let $s$ be a valid string. If $s$ is empty, of course. Assume $s$ is not empty. $s$ was obtained by a series of insertion of "$abc$". Instead of $a, b, c$, we can imagine that each $a$ is an apple, each $b$ is a banana, and each $c$ is a cherry. Each fruit is different from another. Now we can identify and track each letter in $s$, without loss of generality.

Consider the insertion $L$ that inserted $c\_L$, the leftmost cherry in $s$.

I claim that all insertions that happened after $L$ must insert "$abc$" to the right of $c\_L$. Otherwise, whichever insertion happening after $L$ that inserted to the left $c\_L$ will leave some cherry, say, $c\_0$ to the left of $c\_L$. Notice that any insertion does not change the left-right order of existing letters/fruits. No matter what happened later, $c\_0$ would have remained to the left of $c\_L$, which contradicts the fact that $c\_L$ is the leftmost $c$ in $s$.

Hence the letters to the left of $c\_L$ would never change after $L$ had been performed. That means, the two letters immediately to the left of $c\_L$ in $s$ must be "$ab$". The substring "$abc\_L$" is the first occurrence of $abc$ in $s$.

Now imagine we repeat the series of insertions that produced $s$, starting from the empty string, with one exception: when it is time to repeat $L$, we will skip it instead. Since all later insertions inserted to the right of $c\_L$, we can see that this new execution series will yield $s$ without the substring "$abc\_L$". $\quad\checkmark$

---

Correctness of your algorithm follows from the claim above.

* Suppose $s$ is valid.
When the algorithm encounters the first $c$, i.e., the leftmost "$c$", "$c\_L$" of $s$, the claims tells us that "$ab$" must be on the top of the stack. The algorithm then "removes" the substring "$abc\_L$". Ignoring this substring, the algorithm had been behaving and will be behaving exactly the same as if the input had been $s$ with "$abc\_L$" removed. So, by induction on the length of $s$ and that $s$ accepts the empty string, we see that $s$ will be accepted by the algorithm.
* On the other hand, if $s$ is accepted by the algorithm, it is easy to see that $s$ is valid.

---

**Exercise**. Show that given a valid string $s$ and any substring "$abc$" in it, $s$ with that substring removed is still valid.
> 3 votes

---
Tags: algorithms, strings, correctness-proof, stacks
---


# Question
Title: Find the flaw in the 3SAT solver algorithm
I consider decision version of 3SAT problem. Main idea is to find congruent clauses and construct such maximum formula, which satisfiability/truth table won't be changed.

In case of unsatisfiable formula, this "maximum core" size equals to `8/6 * (n - 2) (n - 1) n`, where `n` is maximum literal number.

Otherwise for satisfiable maxcore, size equals or less than `7/6 * (n - 2) (n - 1) n`

Input: 3SAT CNF, Output: Satisfiability

Implementation:

```
# Maximum satisfiable formula size of N literals
def upperbound(N):
  n = N - 2
  return ((n * (n + 1) * (n + 2)) // 6) * 7

# Generate non-conflict clauses from pair. Function can return either 1, N + 2 (starting from N = 7) or 0 caluses
def children(p,p1,literals):
  general = set(p | p1)
  exclude = set()

  for a,b in itertools.combinations(general,2):
    if a == b * -1:
       general.remove(a)
       general.remove(b)
       exclude.add(a)
       exclude.add(b)

  if len(exclude) == 2:
   size = len(general)
   if size == 3:
    return { frozenset(general) }
   elif size == 2:
    for e in general:
     exclude.add(e * -1)
    options = set()
    for l in literals - general - exclude:
     general.add(l)
     options.add(frozenset(general))
     general.remove(l)
    return options

  return frozenset()

def isat(formula,N):
   lim = upperbound(N)
   literals = set(range(-1 * N,N + 1)) - {0}
   pairs = doubly_linked_list() # DS to get rid of duplicate combinations

   for clause in formula: # Filling initial formula
     pairs.push(clause)

   while True:
      pair = pairs.pop()
      if pair != None:
       p,p1 = pair
       for child in children(p,p1,literals):
        if child not in formula:
         pairs.push(child)
         formula.add(child)
       if len(formula) > lim:
        return False
      else:
        return True # No more combinations and maximum satisfiable size reached.
   return True

```

Special list to escape clause pairs duplicates:

```
class Node:
   def __init__(self, data):
      self.data = data
      self.next = None
      self.prev = None
      self.pair = None
      self.completed = False

class doubly_linked_list:
   def __init__(self):
      self.head = None
      self.tail = None
      self.cur = None

   def push(self, data):
        newNode = Node(data);
        if self.head == None:
            self.head = self.tail = newNode
            self.head.previous = None
            self.tail.next = None
        else:
            self.tail.next = newNode
            self.tail.pair = newNode
            newNode.previous = self.tail
            self.tail = newNode
            self.tail.next = None
        self.cur = self.head

   def pop(self):
      if self.cur == self.tail:
        return None
      elif self.cur.completed == True:
        self.cur.pair = self.cur.pair.next
        self.cur.completed = False
      p = self.cur.data
      p1 = self.cur.pair.data
      if self.cur.pair != self.tail:
        self.cur.pair = self.cur.pair.next
      else:
        self.cur.completed = True
        self.cur = self.cur.next
      return p, p1

```

Example unsat input:

```
{frozenset({1, 3, 5}), frozenset({1, 4, -3}), frozenset({3, -1, -2}), frozenset({2, 5, -3}), frozenset({-5, -1, -2}), frozenset({3, -4, -5}), frozenset({3, 4, -5}), frozenset({5, -3, -2}), frozenset({4, -3, -2}), frozenset({2, -4, -3}), frozenset({2, 4, -3}), frozenset({1, 3, 4}), frozenset({2, 5, -1}), frozenset({1, -3, -2}), frozenset({2, -5, -3}), frozenset({5, -1, -2}), frozenset({3, 5, -2}), frozenset({-5, 4, -2}), frozenset({-4, -3, -1}), frozenset({-5, -3, -1})}

```

And sat one:

```
{frozenset({2, -4, 5}), frozenset({2, -6, -3}), frozenset({-7, 3, -1}), frozenset({-8, 1, 7}), frozenset({-8, -5, -4}), frozenset({1, -3, -7}), frozenset({2, 4, 6}), frozenset({8, -7, -6}), frozenset({-7, -3, -2}), frozenset({-8, 4, 7}), frozenset({4, -3, -2}), frozenset({8, -7, 2}), frozenset({-7, 5, 6}), frozenset({-8, -4, -2}), frozenset({3, 4, -1}), frozenset({-4, 5, -2}), frozenset({2, -1, 7}), frozenset({-8, 2, -4}), frozenset({-7, 5, -3}), frozenset({3, 6, 7}), frozenset({2, 5, -1}), frozenset({-8, -1, 7}), frozenset({-7, 2, -3}), frozenset({-8, 5, 6}), frozenset({-8, 3, 4}), frozenset({-7, -3, 6}), frozenset({3, 5, -1}), frozenset({2, -4, -1}), frozenset({5, 6, 7}), frozenset({-7, 2, 6})}

```

I have a problem whether with complexity analysis or with valid counter examples. My guess that algorithm is O(n^7), but it should be impossible.

Empirical research of worst cases also shows polynomial growth.

Relationship of f(n) = k, where n is max literal, and k is basic iterations count (1 + size of children function result) or time.

ln(x) vs ln(y) shows straight line.

ln(y) vs x doesn't show straight line.

X (max literal) : `[4,5,6,7,8,9,10,11,12,13,14]`

Y (iterations) : `[594, 3495, 12970, 37450, 91756, 199794, 397740, 737715, 1291950, 2157441, 3461094]`

I need clarification that this is an exponential algorithm or some counter examples which will break it.

# Answer
> 1 votes
From the looks of it, you're taking every pair of 3-clauses and resolving them, keeping the implications. (If the result is a tautology or if there is no literal to resolve upon then nothing is kept.) The problem is that you are also discarding 4-clauses (i.e., `size == 4`), which makes your search implicationally incomplete.

One can demonstrate this with a direct transformation, though there are likely smaller explicit counter examples. Consider a single clause `(x ∨ y ∨ z)`; taking three fresh variables a, b, and c we can replace this with the following set of clauses:

```
(x ∨ ¬a ∨ b)
(y ∨ ¬b ∨ c)
(z ∨ ¬c ∨ ¬a)
(x ∨ a ∨ ¬b)
(y ∨ b ∨ ¬c)
(z ∨ c ∨ a)

```

If `(x ∨ y ∨ z)` is false, then the above becomes unsatisfiable (it becomes two implication chains expressing `a → ¬a` and `¬a → a`). If `(x ∨ y ∨ z)` is true, then the chains are broken and it becomes satisfiable.

Within this set of clauses, every resolvent is a 4-clause (or a tautology), so your algorithm derives no implications from them. Furthermore, since a, b, and c do not appear anywhere else in the formula, any resolvent produced by these clauses upon x, y, or z will also be a 4-clause.

The clause `(x ∨ y ∨ z)` *is* implied by the above, but it requires resolving two 4-clauses to get there (while also deriving two other 4-clauses along the way). Since you do not keep 4-clauses, this implication is missed and your algorithm incorrectly reports sat for unsat formulas.

Modifying your code a bit into:

```
def num_var(formula):
    N = 0
    for c in formula:
        for l in c:
            N = max(N, abs(l))
    return N

def isat(formula):
    N = num_var(formula)
    # [...]

```

We can define a function which performs the above translation on every clause in the formula:

```
def obfuscate(formula):
    next_var = num_var(formula) + 1
    new_formula = set()

    for (x, y, z) in formula:
        a = next_var + 0
        b = next_var + 1
        c = next_var + 2
        next_var += 3

        new_formula |= {
            frozenset({x, -a, b}),
            frozenset({y, -b, c}),
            frozenset({z, -c, -a}),
            frozenset({x, a, -b}),
            frozenset({y, b, -c}),
            frozenset({z, c, a}),
        }

    return new_formula

```

Passing any unsat formula through this will produce another unsat formula, which your algorithm will claim is sat after producing zero new clauses during its search:

```
# 3-SAT form of (1) ∧ (-1):
unit_conflict_on_1 = {
    frozenset({1, 2, 3}),
    frozenset({1, -2, 3}),
    frozenset({1, 2, -3}),
    frozenset({1, -2, -3}),
    frozenset({-1, 4, 5}),
    frozenset({-1, -4, 5}),
    frozenset({-1, 4, -5}),
    frozenset({-1, -4, -5}),
}

print(isat(obfuscate(unit_conflict_on_1)))

```

---

If you correct this issue, you will lose your polynomial bound on the number of clauses you might derive.

In general, resolution (and things with the strength of resolution, like CDCL) have known exponential lower bounds for hard tautologies. Getting below this barrier requires techniques stronger than searching over the space of implications.

---
Tags: time-complexity, asymptotics, satisfiability, 3-sat
---


# Question
Title: Finding overlapping time under distance condition
I have a set of records (2 or more for each person) on multiple peoples locations (latitude and longitude) with timestamps. each record has: person ID, latitude, longitude, timeStamp. for each 2 people I wish to know if they have been under distance d from one another for over time t.

Is there an algorithm that can help me? Thanks!

# Answer
> 1 votes
Sort the records for each person, by increasing timestamp. Given a pair of people, you can merge the sorted list of records for each of those two people, and then do a linear scan over that sorted list of records: basically, once the two are within distance d, you start counting, and you check whether the remain within distance d for the next items until after t time steps have passed. To find this for all pairs of people, you can enumerate over all pairs of people and do a linear scan for each pair. There may be more efficient algorithms, but this is a very simple technique that will be easy to implement.

If you want a more efficient algorithm, here is an alternative. Imagine a metronome that "ticks" once every t/2 time steps. At each "tick" of the metronome, take the current location of all the people, and find all pairs of people who are within distance d of each other at that "tick". For each such pair, apply the method above to see if they have remained within distance d for a time period surrounding that tick. How can you efficiently find all pairs within distance d at a particular "tick"? Well, you have n points in the plane, and you want to find all pairs that are distance d or less apart. A simple approach is to grid the plane up into cells, each of size dxd, map each person's location into one cell, and then for each person, check for all other people in the same cell or in an adjacent cell, and for each pair of people you find in this way, check whether they are distance d apart.

---
Tags: algorithms, euclidean-distance, time-series-analysis
---


# Question
Title: Implementation of Kruskal's algorithm using priority queues
Is there a way to implement Kruskal's algorithm for finding the MST of an undirected graph using priority queues? The standard implementation uses the disjoint set data structure but I was curious if a PQ implementation is possible, and potentially even better in time complexity.

I looked it up online and found a PQ implementation for Prim's algorithm, but not for Kruskal's algorithm. Any help would be much appreciated.

# Answer
A priority queue (PQ) cannot replace the disjoint-set or union-find (UF) data structure for the Kruskal's algorithm for they have different purpose.

Recall that in Kruskal, the edges in $E$ are ignored, as if the graph is fully disconnected. And for each iteration, it selects a minimum edge from $E$ that can be used to linked vertices, while ensuring that no cycle is created.

The UF is used to guarantee that there will be no cycle when adding a new edge. A PQ cannot do this. Maybe you can use a PQ for selecting the next edge to be added but I don't see how it will improve the running-time of the algorithm, compared to the usual approach of sorting the edges.
> 1 votes

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


title: Rank of a graph in matroid theory

text:
# Question
Title: Rank of a graph in matroid theory
I was going through the concept of graphs as matroids and I came upon the rank of a graph. Wikipedia lists it as $n - c$, $n = |V|$, $c =$ \# of connected components.

I do understand rank and nullity of matrices, and graphs when expressed in their incidence matrix form have a one-to-one correspondence with the rank of its incidence matrix. However, I am not understanding how $r(G) = |V| - c$, $c = $ \# of connected components and the definition of rank as the maximum size of a subforest of $G$ are equivalent.

I tried looking it up online but found no satisfactory explanation. Any resources that would be helpful to understand the concept would be great.

# Answer
> 1 votes
The rank of a graphical matroid is the size of a spanning forest, which consists of a spanning tree in each connected component. A spanning tree for a connected component of size $m$ contains $m - 1$ edges. Summing this over all connected components, we see that a spanning forest contains $n - c$ edges.

---
Tags: graphs, matroids, rank
---


# Question
Title: Prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma
I'm currently trying to prove that $L=\\{a^n b^l : n \leq l\\}$ is not regular by pumping lemma

My proof:

If we choose $w$ such that $w=a^P b^P$, then since $|xy| \leq p$, $y$ must be $a^P$, meaning it can be pumped any number of times $i$, such that $a^{iP} b^P \in L$. Since $iP \leq P$ is not true for any $i \> 1$, it cannot exist in $L$, therefore $L$ cannot be regular.

Is this a valid proof? I don't fully comprehend the pumping lemma, so please let me know if/where I may be going wrong.

Thank you

# Answer
There is a bit of a confusion on the notations:

* what is $P$? If it is the pumping length, then say it so;
* what is $p$? Is it a typo and should be a $P$?
* what are $x$ and $y$? Don't hesitate to remind the hypotheses of the pumping lemma;
* why would $y$ be $a^P$? The only conclusion you can make is that $y = a^k$ for $1\leqslant k \leqslant P$.

The ideas of the proof are good but you should improve the details.
> 1 votes

---
Tags: automata, finite-automata, pumping-lemma
---


# Question
Title: Using pre-,post-, and in-order indexes to find information about a Binary Search Tree
Recently I have been studying ways of traversing a BST (in python), and have collided with the terms pre-order, post-order and in-order.

I believe that I understood the three terms pretty well, and have tried several exercises and examples, which I got right. But I have problems when formulating a relation between these ways of traversing a tree with other properties of the tree.

Take this exercise as an example:

I have tried to draw several binary trees and to imagine some kind of relation between the numbers and the size of the subtrees, but always been unable to.

Thanks for any help in advance! -- This exercise is from Open Data Structures (in pseudocode) from Pat Morin

# Answer
> 6 votes
Long story short: it is possible in constant time if the tree is a full binary tree. If not, there are some cases where there is not enough information to find the size of the subtree in constant time.

Note that you have access to the node of the tree and not only the numbers of the node $u$.

That means that you can check in constant time the pre-, in- and post-order numbers of the left and right child of $u$.

Now you can use the pre-order to find the size of the left child and the post-order to find the size of the right child. Can you see how?

## Some vocabulary and details on tree traversal

A bit of vocabulary:

* a *descendant* $v$ of a node $u$ is a node that appears in the subtree rooted in $u$. A **left** (resp. **right**) descendant is a descendant of the left (resp. right) child of $u$;
* an *ancestor* $u$ of a node $v$ is a node such that $v$ is a descendant of $u$; $u$ is a **left** (resp. **right**) of $v$ if $v$ is a right (resp. left) descendant of $u$;
* a *cousin* $w$ of a node $v$ is a node such that $v$ and $w$ have a common ancestor $u$, different of $v$ and $w$. $w$ is a **left** (resp. **right**) cousin of $v$ if $w$ is a left (resp. right) descendant of $u$ and $v$ is a right (resp. left) descendant of $u$.

Now here is an array to know what appears before and after a node $u$ in each order:

| Which node | pre-order | in-order | post-order |
| --- | --- | --- | --- |
| left ancestor | before | before | after |
| right ancestor | before | after | after |
| left descendant | after | before | before |
| right descendant | after | after | before |
| left cousin | before | before | before |
| right cousin | after | after | after |

What does that mean? It means that for a node $u$, $u.pre$ (the pre-order number of $u$) is equal to the number of ancestors of $u$ plus the number of left cousins. Similarly, $u.post$ is the number of descendants plus the number of left cousins.

That also means that $u.post - u.pre$ is the number of descendants minus the number of ancestors.

## If the tree is a full binary tree, there is a constant time solution

Now let's go back to the problem.

Consider a node $u$. If $u$ has no child, then the size of the subtree is obviously $1$. Otherwise, $u$ has a left child $v$ and a right child $w$. Note that all descendants of $v$ are also left cousins of $w$.

* since $v$ and $w$ have the same number of ancestors, $w.pre - v.pre$ is equal to the size of the subtree rooted in $v$!
* that also means that $w.post - v.post$ is equal to the size of the subtree rooted in $w$ (because the number of descendants of $v$ \+ left cousins of $v$ is equal to the number of left cousins of $w$).

That means that the size of the subtree rooted in $u$ is: $$w.pre + w.post - v.pre - v.post + 1$$

## If the tree is not full, some conclusions are possible, but there may be problems

Now, as Hendrik Jan pointed it out in the comments, what if $v$ or $w$ doesn't exist?

* if $u$ has only a left child $v$, it is possible to know the size of the right child of $v$, using the in-order number. Indeed, since $u$ has no right child, $u.in - u.post$ is equal to the number of left ancestors of $u$, which is also the number of left ancestors of $v$. That means that the number of right descendants of $v$ is $u.in - v.in - 1$ (since $u.post = v.post + 1$ because $u$ has no right child). Now three cases are possible:
    + $v$ has no left child. Since we know the size of the right child, we know the size of the subtrees rooted in $v$ and in $u$ (it is $u.in - v.in + 1$ for the latter);
    + $v$ has a left and a right child. Using the previous method, we can find the size of the subtree rooted in $v$ and then the size of the subtree rooted in $u$;
    + $v$ has a left child but no right child. In the case, we are stuck as we cannot find any conclusion using only the informations in $u$ and $v$. As an example, here are two trees where a node $u$ has an only left child $v$ and $u$ and $v$ have the same pre-, in- and post- order numbers, but the subtree rooted in $v$ are not of the same size:

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

  1
 / \_________
2            4
 \          /
  3        5
          /
         6
        /
       7
        \
         8
          \
           9

```

In both trees, the node $5$ has a pre-order of $5$, in-order of $8$ and post-order of $7$, and the node $6$ (only left child of $5$ that has only a left child) has a pre-order of $6$, in-order of $7$ and post-order of $6$. However, the subtree rooted in $5$ is of size $4$ in the first tree and of size $5$ in the second tree. That means that knowing only those informations cannot lead to the conclusion. One could find similar examples with a left path as long as wanted.

* Similar conclusions can be done if $u$ has only a right child.

---
Tags: binary-trees, python, binary-search-trees, subtree
---


# Question
Title: Why is Scale Space Needed to Detect Scale Invariant Features?
I have been doing research on the SIFT (scale invariant feature transform) algorithm, and while I have repeatedly read that in order to detect image features that do not vary with respect to scales of visual perspective, a scale space must be constructed from the source image using repeated Gaussian smoothing and taking differences of those Gaussians. Then local extrema are found in the four dimensional scale space which are designated as scale invariant key points. How this process is performed seems straightforward, but my question is why does this process work at all? What is special about the Gaussain blur that allows us to do this? In the publications that I am reading (listed below), the reason this works is not clear to me.

Lindeberg, Tony. “Detecting Salient Blob-like Image Structures and Their Scales.” Scale-Space Theory in Computer Vision (1994): 249-70. Web. http://www.nada.kth.se/~tony/abstracts/Lin92-IJCV.html

Lindeberg, Tony. “Scale-space.” Encyclopedia of Computer Science and Engineering. Vol. 4. N.p.: n.p., n.d. 2495-504. Web. 16 Oct. 2016. ftp://ftp.nada.kth.se/CVAP/reports/Scale-Space-EncCompSci.pdf

Lowe, David G. “Distinctive Image Features from Scale-Invariant Keypoints.” International Journal of Computer Vision 60.2 (2004): 91-110. Web.

**EDIT**

I have read many high level explanations of this concept, which generally say that as the sigma of the Gaussian increases, fine grained features should be suppressed and that coarse grained features should be generalizations of fine grained features. But I am looking for a more rigorous and possibly mathematical explanation of why this is the case.

# Answer
> 0 votes
This is several years later (thanks, bot, for bumping the question).

*What is special about the Gaussian blur that allows us to do this?*

In theory, you could use any bandpass filter at different scales to implement a SIFT-like algorithm, but difference-of-Gaussians has a couple of features which makes it especially convenient.

First, the convolution of two Gaussians is a Gaussian. So applying a Gaussian blur to an image that has already been Gaussian-blurred is mathematically equivalent to applying a Gaussian (with larger sigma) blur to the original image. This saves a lot of work in practice.

Second, the difference-of-Gaussians is a reasonably good approximation to the Laplacian-of-Gaussian. The Laplacian operator measures the difference between the value of a function at a point, and the average of the function in a region around the point. (This is why solutions to Laplace's equation are often the same thing as "equilibrium" in physical systems.) But it's also an excellent way of capturing what it means to be a "feature" in image processing: a "feature" is a value that's different from the average in its neighbourhood.

# Answer
> 0 votes
If a maximum is found at a given octave X in the original image, then, if we have the scale-invariant property, this maxima will be found on the zoomed down (downscaled) image at octave X-1.

---
Tags: image-processing, computer-vision
---


# Question
Title: How do I get $T(n) \leq 3T(\lfloor n/4 \rfloor) + cn^2$ from $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$?
Section 4.4 of Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein gives the following to verify that $O(n^2)$ is an upper bound for the recurrence $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$:

> \begin{align} T(n) &\leq 3T(\lfloor n/4 \rfloor) + cn^2 \\ & \leq 3d \lfloor n/4 \rfloor^2 + cn^2 \\ &\leq 3d(n/4)^2 + cn^2 \\ &= \frac{3}{16} dn^2 + cn^2 \\ &\leq dn^2. \end{align}

How do I get $T(n) \leq 3T(\lfloor n/4 \rfloor) + cn^2$ from $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$?

# Answer
> 1 votes
The equation $$ T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2) $$ has the following meaning: there exists a function $f(n) = \Theta(n^2)$ such that $$ T(n) = 3T(\lfloor n/4 \rfloor) + f(n). $$ Since $f(n) = \Theta(n^2)$, we can find a constant $c\>0$ such that $f(n) \leq cn^2$, and so $$ T(n) \leq 3T(\lfloor n/4 \rfloor) + cn^2. $$

---
Tags: asymptotics
---


# Question
Title: Longest common subsequence of two permutations
Given two permutations $\pi\_1$ and $\pi\_2$ of numbers $\\{1,2,\dots,n\\}$, can we find $\mathrm{LCS}(\pi\_1,\pi\_2)$ in $O(n\log n)$? I think we can use LIS but I get stuck.

# Answer
> 3 votes
A sequence $i\_1,\ldots,i\_m$ is a common sequence if $\pi\_1^{-1}(i\_1) \< \cdots \< \pi\_1^{-1}(i\_m)$ and $\pi\_2^{-1}(i\_1) \< \cdots \< \pi\_2^{-1}(i\_m)$.

A sequence $j\_1,\ldots,j\_m$ is such that $\pi\_1(j\_1),\ldots,\pi\_1(j\_m)$ is a common sequence if $j\_1 \< \cdots \< j\_m$ and $\pi\_2^{-1}(\pi\_1(j\_1)) \< \cdots \< \pi\_2^{-1}(\pi\_1(j\_m))$.

We conclude that the longest common sequence of $\pi\_1,\pi\_2$ is the longest increasing sequence of $\pi\_2^{-1}\pi\_1$.

---
Tags: algorithms
---