# Question
Title: Is the function $f: \mathbb{N} \rightarrow \mathbb{N}$ where $f(n) = 2^n$ computable in polynomial time using TM?
Assuming that the input $n$ is given as a decimal number.
I was asked to **prove** whether the function $f: \mathbb{N} \rightarrow \mathbb{N}$ where $f(n) = 2^n$ is computable in polynomial time using TM or not.

My guess is that the function cannot be computed in polynomial time but I can't figure out how I can **prove** it.
Showing that the function can be computed in polynomial time is easy because we just have to exhibit an algorithm and show it runs in polynomial time.

I was trying to think about the problem a little bit but I feel like I don't have the right knowledge and tools when it comes to understanding the relationship between a function that can\cannot be computed in polynomial time and a language that can be decided in polynomial time ? and how it's related to the problem of $P = NP$ ?

My TA said that I should use a certain property that the function above has in order to show that it can't be computed in polynomial time, but he didn't answer the question about the relationship between computable\non-computable functions to decidable\non-decidable languages.

# Answer
Look at the size of the required output. How much time would it take you just to *write* the result?

And this has nothing to do whatsoever with P vs NP, or computable or decidable languages.
> 4 votes

---
Tags: turing-machines, computability, polynomial-time
---


title: longest symmetric sequence

text:
# Question
Title: longest symmetric sequence
Suppose we are given a $n$-vector $A$ of real numbers. We need to find the longest sequence of symmetrical numbers. The numbers $a\_i$ and $a\_j$ are symmetrical if they are located at the same distance from element $a\_k$ and $|a\_i-a\_j|\< \epsilon$, $\forall i \< j$.

**Question**

Can it be done in less than $O(n^2)$ comparisons in the worst case?

A $O(n^2)$ algorithm is to check the condition $|a\_i-a\_j|\< \epsilon$ for element $a\_k$.

Example:

**Input:** 0.006, 0.0061, 0.0069, 0.0135, 0.0065, 0.0193, 0.0086, 0.005, 0.01, 0.035, 0.065, 0.085, 0.1236, 0.086, 0.066, 0.037, 0.0024, 0.0712, 0.0032, 0.0174, 0.1504

There are two possible candidates of length 3 or more in this input (green and red).

**1 (green).** $a\_k$ is 0.0065, and we have four pairs whose maximum absolute difference is 0.0058.

**2 (red).** $a\_k$ is 0.1236, and we have three pairs whose maximum absolute difference is 0.002.

**Ouput**

If $\epsilon \> 0.0058$ then 0.035, 0.065, 0.085, 0.1236, 0.086, 0.066, 0.037

If $\epsilon \<0.0058$ then 0.006, 0.0061, 0.0069, 0.0135, 0.0065, 0.0193, 0.0086, 0.005, 0.01

**Edit.** After the comment by @D.W. It shound be noted that can be situation either $a\_i = a\_k$ or $a\_j=a\_k$, i.e. there is no the element $a\_k$.

# Answer
> 1 votes
The way your condition is written, it could be that almost all elements are considered equal. That will be hard to handle efficiently.

By comparing $x\_i$ and $x\_{i+128}$ for example you can find all k that could be in the middle of a sequence with 129 or more elements. With your typical data that might very much restrict the values k, or there might be none at all and you compare $x\_i$ and $x\_{i+64}$ and so on. (Adjust depending on the number of items).

In your example you would find that $x\_i$ and $x\_{i+8}$ are close enough only for i = 0 and then compare 1 vs 7, 2 vs 6 and 3 vs 5.

---
Tags: algorithms, subsequences, algorithm-design
---


# Question
Title: How does signed floating point adder implement?
The following picture is a block diagram of an arithmetic unit dedicated to IEEE 754 floating-point addition from Computer Organization and Design RISC-V Edition: The Hardware Software Interface 2nd Edition book.

My questions are:

1. Why are in the sketch, the sign of the numbers ignored, while the final result has a sign bit?
2. In the IEEE 754 standard, there is a hidden '1' bit for normalized numbers. How does this bit take part in addition?

# Answer
> 1 votes
Hidden leading bit: You add a 1 when you extract the mantissa except for denormalised numbers where you add zero.

You use both sign bits to determine whether you add the mantissas (same sign) or subtract (different signs). And the result of the sign comes from the sign of the bigger number.

---
Tags: computer-architecture, arithmetic, floating-point
---


# Question
Title: Memory-efficient representation of keys over a huge domain
I don't know if the title of the question is accurated or not, but I was thinking of the following problem:

* I have a set of numbers, let's call them identifiers. Each identifier is stored on a 64-bit long integer; but in practice I only have, let's say, never more than 4 million different identifiers at any time.
* I want to store some information for each existing identifier, for example in a dictionary. If I have exactly 4M different numbers of 8B width each (worst case), to store the dictionary I would need around 32MiB of space only for the keys.
* However, let's consider that I only need 22-bits to have up to 4M different identifiers. If I'd have a way to map each unique 64-bit key to a unique 22-bit key, for this worst case of 4M keys, these 32MiB worth of keys would be reduced to 11MiB; a 65% reduction.

What is the most space-efficient way to implement that 64-bit to 22-bit number mapping?

I was thinking that, assuming the existing keys are evenly distributed over the 64-bit range, between each pair of keys there would be a $2^{42}$-width gap, which is $2^{22}$ times bigger than the maximum number of keys... a lot. In that extreme case (evenly distributed), that would mean that to jump from one id to the next one, I've to add $2^{42}$, in other words, the last 42 bits of all ids would be the same, which means that my mapping would consist of just triming the last 42 bits of each input id.

If the keys are anything but evenly distributed, they must form clusters instead, and so you could identify those clusters, idenfity their centers, assign an 0-based index to each cluster, and then translate each input identifier to the cluster-idx to which the id belongs and the offset within the cluster. If the sum of bits for the cluster-idx and the bits to store the offset is $\leq$ 22-bits, you achieved the goal.

For example, you can sort the clusters by size and assign 22-bits as offset for cluster 0, 21-bits as offset for cluster 1, 20-bits as offset for clusters 2 and 3 (10 and 11), 19-bits for clusters 4, 5, 6, and 7 (100, 101, 110, 111), etc. That means that you would need to store extra storage to maintain the cluster centers and be able to know to which cluster does each potential input id belongs to.

But I don't know how to combine all of those ideas together to implement a mapping-strategy, and how to generalize it for the general problem of mapping up to 2^k identifiers of n-bits using the lowest number of bits possible.

# Answer
Short answer: It's most likely not worth worrying about. The maximum possible amount of space saving is small enough that it's not worth the additional code complexity.

One can prove that any data structure to store the mapping needs at least $\lg {n \choose k}$ bits, where here $n=2^{64}$ and $k=2^{22}$. This evaluates to about 22.8MB. So the most you can hope to reduce space usage is from 32MB to 22.8MB. Probably not worth the bother, from any engineering perspective, as it won't fit in L2 cache either way, and it will easily fit in RAM on any reasonable machine. I suspect that the engineering cost of dealing with complex data structures, and the increased time to compute the mapping, will probably outweigh any space savings in most cases.

---

The long answer: Your question states you care only about the space efficiency of the data structure to store the set of 4M identifiers, and there are no requirements on how long it takes to compute the mapping.

If that's all that matters, the most space efficient way to store the set of 4M identifiers is by using a ranking/unranking scheme for all 4M-element subsets of $\\{0,1\\}^{64}$, also known as a ranking scheme for combinations. See, e.g., https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-unranking-of-combinations-and-permutations/ for one such scheme. This scheme is optimal in space usage: it represents a $k$-subset of a space of size $n$ using $\lg {n \choose k}$ bits. Here $k=2^{22}$ and $n=2^{64}$. So that is a complete solution to your problem.

In practice, such schemes are normally unusable, because while space usage is optimal, the time to compute the mapping is too large. So in a practical setting, we probably care more about a good tradeoff between the space required to store the data structure, and the time to compute the mapping.

From a theoretical perspective, you might be interested in succinct data structures. See, e.g., https://en.wikipedia.org/wiki/Succinct\_data\_structure, https://cstheory.stackexchange.com/q/5010/5038, and these papers:
> 1 votes

# Answer
If you have these keys, they require `8x4=32` bits of storage

```
11110001
11110010
11010001
11010010

```

But you can separate them in buckets

```
bucket: 1111
bucket: 1101

```

now you only need to store the numbers 0001 and 0010 in each bucket, and reduced your storage to half.

You can do it recursively, and reduce the storage space logarithmically.

The data structure is a type of Trie, you probably need a Radix Tree. Surely there is already a trie algorithm optimized for your problem.
> 0 votes

---
Tags: algorithms, data-structures, data-compression, encoding-scheme
---


title: Maximum circular area sum

text:
# Question
Title: Maximum circular area sum
Given an $n \times n$ grid of integers, I would like to compute the circular area which gives the maximum sum of integers within the area. For example:

In this picture, the integers 1, 0, 1, 2, 3, 1, 2, 1, -3, -2, 2, -3, 1, 3, -2, 0, 2, -1 etc are all within the circular area.

If we restrict the circular area to be centered at one of the grid points, is there an efficient algorithm for this problem?

The input is just the grid of integers. The task is to find the center and radius. If the circular area includes part outside the grid that part contributes zero to the sum.

# Answer
There are $n^4$ possible $(x, y, r^2)$ tuple, each describing a circle centered at $(x, y)$ with radius $r$. Since each circle is its smaller version added with $O(1)$ additional points, this yields a time complexity of $O(n^4)$. We may find the additional points by sorting every $r^2 = a^2 + b^2$ pair.
> 2 votes

# Answer
The possible radiuses squared are given by OEIS sequence A001481.

For square with nodes $0,...,n$, there are $1+(n+1)(n+2)/2$ different possible radius. (but only $1+n(n+1)/2$ are inside the rectangle).
You better work with the radius squared, since is integer arithmetic, which is faster than float.

This quadratic equation is the number of nodes inside half a quadrant of a circle. (It double counts a small number of nodes, but is roughly correct).

If you displace this circle to the center, the base of the triangle is reduced th 1/2, which reduces the node count to 1/4 (think of the large triangle as made out of 4 small triangles).

for $0$ to $9$, you get $67$ different radius to try. The radius squared are

```
0, 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29, 32, 34, 36, 37, 40, 41, 45, 49, 50, 52, 53, 58, 61, 64, 65, 68, 72, 73, 74, 80, 81, 82, 85, 89, 90, 97, 98, 100, 101, 104, 106, 109, 113, 116, 117, 121, 122, 125, 128, 130, 136, 137, 144, 145, 146, 148, 149, 153, 157, 160, 162

```

Note that you only need to calculate those radius in 1/8 of the 360º, because the rest of the circle is symmetrical, and do not add more unique radius.

Adding the nodes, for each radius, is a 2D convolution.

First you make a circular mask, for each radius, and then use the mask to calculate the convolution on all nodes (most algorithms use the fast fourier transform).
The mask has $1$ for all the nodes where $\Delta x^2+\Delta y^2 \leq r^2$, and has $0$ on the nodes outside the circle.
Any graphic library has already coded optimized functions to calculate 2D convolutions,and maybe even to create a circular mask.

```
for each unique radius -> O(n^2)
    create mask -> O(n) since you only need to add periferic nodes to the smaller mask.
    calculate convolution -> O(n^2)log(n) size
    find max value in the convolution -> O(n^2)

```

It is a brute force $O(n^4\log(n))$ algorithm, but the convolution is relatively cheap, and probably may be reused with larger masks.
> 2 votes

# Answer
I'm not sure if the algorithm qualifies as "efficient", but at least it works in polynomial time. The idea is that for a given pair pair $(x,y)$ of coordinates, there is at most $n^2$ many radiuses to consider (indeed, two discs that contain exactly the same points will have the same sum).

To enumerate these discs, start with radius $r=0$. Then following procedures takes a radius $r \geq 0$ (not necessarily a natural number!), and returns the smallest radius $r' \geq 0$ such that the disc centered at $(x,y)$ of radius $r'$ contains strictly more points than the disc of radius $r$: it suffices to compute all points $(x',y')$ that do not belong to the disc of radius $r$, and pick any point with minimal distance to $(x,y)$. Return the distance from $(x',y')$ to $(x,y)$.

Overall this gives you a polynomial time procedure to enumerate all sets of points contained is a disc centered at $(x,y)$. Then it suffices to iterate this over all coordinates $(x,y)$.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Unordered data structure with fast insertion, deletion, and iteration
So, I need a data structure that would support the following operations:

* Add an element to the structure and get some "handle" for that element
* Retrieve an element by a handle
* Remove an element by a handle
* Iterate over all elements

Note that the elements are not expected to have any particular order in iteration. Preferably it should also be cache-friendly and don't use too many memory allocations. The language I have in mind is C++, if that matters.

A doubly-linked list satisfies the requirements (with a "handle" being just a pointer/iterator to a list node). However,

* It uses a memory allocation per each new element, which is a bit too much
* Iteration over a list is extremely cache-unfriendly (as compared to e.g. iteration over contiguous array)

Another possible implementation is to use a hand-written slab allocator over a contiguous chunk of memory, with each cell being either free of occupied. Occupied cells store the actual elements, while free cells maintain a singly-linked list of free cells by storing the index of the next cell in the list (or some predefined null value to mark the end of the list). A "handle" in this case would be an index of a cell. Coupled with some extra per-cell data to decide whether a cell is free or occupied, and an index of the head of the list of free cells, this structure allows

* Fast amortized insertion: put the new element to the head of the list of free cells, updating the head index (and reallocating the cells array if no free cell is available)
* Fast element access (just an index into array)
* Fast removal: add the element's cell to the list of free cells
* Fast iteration: iterate over an array, checking if the current cell is occupied

However, I am not entirely happy with this solution, since

* It has to explicitly maintain the cells state (free/occupied) - this is mostly a technical inconvenience and not a serious issue
* Iteration is still not branch-predictor-friendly (due to checking whether the cell is free or occupied) and might waste a lot of time skipping free cells (thanks to Andrej Bauer for pointing this explicitly), so it is an improvement only if the number of free cells is sufficiently low.

Yet another solution is to implement any kind of binary key-value tree stored inside a contiguous array (auto-expanding, like `std::vector`), with array indices used instead of tree node pointers, and keys serving as handles for element access/removal (their only purpose being implementing handles). This way we have

* Amortized $O(\log n)$ insertion - append a tree node to the end of the array, altering the tree structure accordingly (or even $O(1)$ if the tree supports $O(1)$ insertion to the end, like a splay tree, - the data structure generates keys itself, so it can guarantee that they only increase for new elements)
* Amortized $O(\log n)$ removal - remove the node from the tree structure, then swap it with the last node in the array (fixing the indices stored in the last node's children and parent), and decrement the array size
* $O(\log n)$ element access via the tree structure on keys
* Ideal iteration: simply iterate over the whole array (even better if we keep values in a separate array, synchronized with the array for the tree structure, since the latter is not needed for iteration)

This solution trades iteration speed for $O(\log n)$ other operations.

I am mostly interested in increasing the iteration performance, while still retaining fast amortized insertion/deletion. I'm ok with spending some extra $O(n)$ memory, shall the need arise.

**So, here's my question**: are there better options for a data structure with these requirements?

# Answer
> 0 votes
This is my implementation of a list structure.

It is not dynamically allocated, and all allocations are done when it is constructed.

* Iteration is at worst case O(n), n being the max size of the list
* Insert is O(1)
* Remove is O(1), except if using sort optimization(tradeoff: slows remove but potentially helps iteration)

If sorting optimization is used, any new elements that are added will be given an index towards the beginning of the list to fill in gaps better, making better use of the cache and reducing free cells in between. However this is called in the erase function, so removal will be O(log n).

Sorting could be called at a certain threshold (like once every 100 erase calls OR every second or so). This way it will not have as large of an impact on removal time complexity.

Also sorting refers to sorting the element indices that were erased and added back to the array of available indices.

```
template <typename T> struct zList{

#define _setBit(__byteArray, __bitPosition)   (__byteArray[(__bitPosition)/8] |=  (0x01<<((__bitPosition)%8)))
#define _clearBit(__byteArray, __bitPosition) (__byteArray[(__bitPosition)/8] &= ~(0x01<<((__bitPosition)%8)))
#define _getBit(__byteArray, __bitPosition) (__byteArray[(__bitPosition)/8] & (0x01<<((__bitPosition)%8)))
#define divideAndRoundUp(a, b) ((((a)+(b))-1)/(b))

/*
    notes:

    -cache friendly iteration
    -no allocations for insert or erase (unless in the deconstructor of the type)

    -out of range access returns a valid reference (extra element at the end to the max size)
        might be better to just return an exception/assert ?
        can also check if it exists before accessing "list.exists(HANDLE);"

    -sort_descending() this function is used to sort the array indices that were removed
        this may or may not be an optimization depending on the use case.

        sorting helps fill in gaps after erasing elements then adding new elements (the index will be the min index(closest to 0) and not a random one))
            this helps the iteration by looping through less empty elements

        if you don't sort then erase() will be O(1), but iteration *might* suffer
            also sort can be called every x elements erased, or on a timer (maybe once per second, either manually call it or the next time erase it called it can check the time and decide if it needs to sort)

    -Insertion is O(1)
    -Removal is O(1) unless sorting is used O(log n)

    -Iteration: worst case O(n 'n being the maxSize of the array'),    it will iterate the max size of the list and iterate by 1 each time if the unused elements are every other
                    best case O(>=list.size()), an internal minimum index is stored so it knows where the first element is located and how many elements there are
                        so it knows when to start and stop

    HOW TO USE-------------------------------------------------------------------

        //can use Custom class/struct, or a base type
            struct SomeType{
                private:
                int allocated;

                public:
                std::string someString;
                int someValue;
                unsigned char* someAllocation;

                //default constructors will be called if not provided
                SomeType(){ //all constructors are called upon list initialization
                    allocated = 0;
                }
                ~SomeType(){ //all deconstructors are called when an element is erased
                    if(allocated){
                        free(someAllocation);
                    }
                }

                void alloc(){ //if you need to allocate memory, make sure to free it in the deconstructor so it will be cleaned up when erased or zList goes out of scope
                    if(!allocated){
                        allocated = 1;
                        someAllocation = (unsigned char*)malloc(100000000);
                    }
                }

            };

        //Initialize the list
            zList<SomeType> list(10);

        //Clear and or resire the list
            list.clear(); //clear
            list.clear(15); //clear and make new size 15

        //Insert - a little awkward syntax but whatever
            int handleIndex = -1;
            if(!list.isFull()){
                handleIndex = list.newIndex(); //Get an availible index(or handle) in the list
                if(handleIndex==-1){} //You can skip list.isFull() and check if the handle is -1 instead (means it is full)

                //Setting up the element, [] operator returns a refrence to the element
                list[handleIndex].alloc(); //Allocate memory
                list[handleIndex].someString = "test";
                list[handleIndex].someValue = 128;
            }

        //Remove/erase
            list.erase(handleIndex); //erase the element (this calls the deconstructor and then the constructor to reset the memory)

        //Itteration - syntax like standard containers
            //you can pass in a starting handle/index to begin()
            for(auto it = list.begin(); it!=list.end(); ++it){
                SomeType& st_0 = (*it); //dereferencing returns reference to the element
                SomeType& st_1 = list[it.currentIndex]; //or get reference by using the index
            }

            //If you need to erase an element during iteration
            for(auto it = list.begin(); it!=list.end();){ //remove ++it from the statement
                SomeType& st_0 = (*it); //dereferencing returns reference to the element
                SomeType& st_1 = list[it.currentIndex]; //or get reference by using the index

                int needToErase;
                if(needToErase){
                    list.erase(it); //Must erase using iterator and not index here so it can move the iterator to the next element
                }else ++it; //iterate to the next element if we didn't erase
            }

*/

private:
    unsigned long long lastSortTime;
    int minimumLoopIndex; //keeps track of the min index that is being occuied
    int sortIndex; //Helps to lower the amount of indices we need to sort
    int* availIndex; //available indices that we can use
    unsigned char* usedIndicies; //a bitfield representing the array indices that are currently occupied
    T* data; //Array of the elements, this array is allocated with an additional refrence element. This is returned if the array is indexed out of range
    int availIndexCnt; //number of elements we can add to the list
    int maxSize; //max number of elements we can add to the list

public:
    struct Iterator {
        private:
            T* dataPtr;
            int _maxSize;
            unsigned char* _usedIndicies;
            int elementsFound;
            int currentIndicieCount;
        public:
            int currentIndex;

            Iterator(int startIndex, T* _dataPtr, int __maxSize, int _currentIndicieCount, unsigned char* __usedIndicies) : currentIndex(startIndex), dataPtr(_dataPtr), _maxSize(__maxSize), _usedIndicies(__usedIndicies), elementsFound(1), currentIndicieCount(_currentIndicieCount) {}
            Iterator& operator++(){

                //If we have found all the elements then we can stop checking the rest just return end() now
                if(elementsFound>=currentIndicieCount){
                    currentIndex = _maxSize;
                    return *this;
                }

                currentIndex++;

                //Find the next element that is being used
                do{
                    //std::cout << currentIndex << " bb\n";
                    if(_getBit(_usedIndicies, currentIndex)){
                        ++elementsFound;
                        break;
                    }else{
                        unsigned long long testBits = *(unsigned long long*)&_usedIndicies[currentIndex/8]; //Get the next 8 bytes (that includes the current index)

                        //See notes in begin()
                        if(!(testBits              )){ currentIndex += 64-(currentIndex&0x3F); continue; } //advance upto 64 empty elements
                        if(!(testBits&0xFFFFFFFFull)){ currentIndex += 32-(currentIndex&0x1F); continue; } //advance upto 32 empty elements
                        if(!(testBits&0xFFFFull    )){ currentIndex += 16-(currentIndex&0x0F); continue; } //advance upto 16 empty elements
                        if(!(testBits&0xFFull      )){ currentIndex +=  8-(currentIndex&0x07); continue; } //advance upto  8 empty elements
                        if(!(testBits&0xFull       )){ currentIndex +=  4-(currentIndex&0x03); continue; } //advance upto  4 empty elements
                        if(!(testBits&0x3ull       )){ currentIndex +=  2-(currentIndex&0x01); continue; } //advance upto  2 empty elements

                        currentIndex++; //move just 1 element
                    }
                }while(currentIndex < _maxSize);
                if(currentIndex>_maxSize) currentIndex = _maxSize; //make == to end()

                return *this;
            }
            Iterator& operator+=(int steps){
                int newIndex = currentIndex + steps;
                currentIndex = (newIndex < _maxSize) ? newIndex : _maxSize;
                return *this;
            }
            bool operator==(const Iterator& other) const {
                return currentIndex == other.currentIndex;
            }
            bool operator!=(const Iterator& other) const {
                return currentIndex != other.currentIndex;
            }
            T& operator*() {
                return *(&dataPtr[currentIndex]);
            }
    };

    zList(int _maxSize){
        if(_maxSize < 0) _maxSize = 1; //don't allow negative sizes
        maxSize = _maxSize;
        //data = tnew<T>(_maxSize+1, TMC::ZLIST_CONTAINER);
        data = (T*)malloc((_maxSize+1)*sizeof(T)); //make sure to construct all of them initialy
        int i=-1; while(++i < (_maxSize+1)) new(&data[i]) T();

        availIndex = (int*)malloc(_maxSize*sizeof(int));
        int g=-1; while(++g < _maxSize) availIndex[(_maxSize-1)-g] = g;
        availIndexCnt = _maxSize;
        usedIndicies = (unsigned char*)malloc((divideAndRoundUp(_maxSize,8)+16)*sizeof(unsigned char)); //added 16 to be able to access out of range bits
        memset(usedIndicies, 0, (divideAndRoundUp(_maxSize,8)+16)); //zero memory
        sortIndex = maxSize;
        lastSortTime = 0;
        minimumLoopIndex = maxSize; //this will just make the iterator start at the end()
    };
    ~zList(){
        int i=-1; while(++i<(maxSize+1)) data[i].~T(); //call the deconstuctor, all of them will be constructed to be able to safely do this
        free(availIndex);
        free(usedIndicies);
        free(data);
    }

    bool isFull(){ return !availIndexCnt; } //if count is 0 then it flips to 1 and returns as true
    bool isEmpty(){ return availIndexCnt == maxSize; }
    unsigned int size(){ return maxSize-availIndexCnt; }
    void exists(unsigned int arrayIndex){ return ( (arrayIndex<maxSize) && (!_getBit(usedIndicies, arrayIndex)) );} //check if the index if being used

    //Erases all the elements, if a newSize is provided, then it will clear and then resize the list
    void clear(int newSize = 0){ //if newSize is not 0 then delete the old list and create a new one
        for (auto it = begin(); it != end();) erase(it); //erase all the elements

        int g=-1; while(++g < maxSize) availIndex[(maxSize-1)-g] = g;
        memset(usedIndicies, 0, tsize(usedIndicies));
        availIndexCnt = maxSize;
        sortIndex = maxSize;
        lastSortTime = 0;
        minimumLoopIndex = maxSize;

        if(newSize>0){
            if(newSize!=maxSize){
                this->~zList(); // Call the destructor for the current object
                new (this) zList(newSize);
            }
        }
    }

    //Sorts the availIndex array starting from the sort index to the last index of the total count available
    void sort_descending(){
        int n = availIndexCnt - sortIndex; //number of ints to sort from the sort index to the current count
        if(!n) return;
        int* tmp = &availIndex[sortIndex]; //point to the sort index

        std::sort(tmp, tmp+n, std::greater()); //sort the array in descending order

        //-i is the number of sequential numbers from the sort index
        //-k is the index that is expected next, sub 1 each after each check itteration
        int i=-1, k=(maxSize-sortIndex)-1 ; while(++i<n){
            if((k--)!=tmp[i]) break;
        }
        sortIndex += i; //move the sort index by the num of sequential indicies
    }

    //Get an availible index we can use
    int newIndex(){
        if(!availIndexCnt) return -1; //-1 means it is full
        int arrayIndex = availIndex[--availIndexCnt];
        _setBit(usedIndicies, arrayIndex);
        sortIndex--;

        if(arrayIndex<minimumLoopIndex) minimumLoopIndex = arrayIndex; //if our index we got is less than then set the minindex so the loop knows to begin their
        return arrayIndex;
    }

    //erase by using the index we want to remove
    void erase(unsigned int arrayIndex){
        if(arrayIndex>=maxSize || (!_getBit(usedIndicies, arrayIndex))) return;

        //if we are adding back to the array next to the sort index, increment the sort index if the array index is 1 less
        if((sortIndex==availIndexCnt) && (((maxSize-sortIndex)-1)==arrayIndex)) sortIndex++;

        //if the array index matches the min index we can safely move it up 1
        if(arrayIndex==minimumLoopIndex) minimumLoopIndex++;

        availIndex[availIndexCnt++] = arrayIndex; //add index back to be reused
        _clearBit(usedIndicies, arrayIndex);
        data[arrayIndex].~T(); //call the deconstuctor
        new(&data[arrayIndex]) T(); //then the constructor again

        //Optional - see notes
            //sort_descending();

        /*
        TODO:
        set a timer, or call sort every x times
        if(lastSortTime){ //if a timer was set, sort if time passed
            if(getNetTime()>lastSortTime){
                lastSortTime = 0; //all sorted so don't check again till we remove another one
            }
        }else{
            lastSortTime = getNetTime()+1000; //sort in 1 second from now
        }
        */
    }

    //erase by using the itterator, then increment the it to the next one
    void erase(Iterator& it){
        int arrayIndex = it.currentIndex;
        ++it; //move itterator to the next one BEFORE we remove the current node
        erase(arrayIndex); //erase by index
    }

    //Return a refrence to the element in the list
    FORCEINLINE T& operator[](unsigned int arrayIndex){
        //Takes the array index as an unsigned to avoid negative checks, and return the maxSize index if we try to access outside the range (0 to (maxSize-1))
        return *(&data[min(arrayIndex, maxSize)]);
    }

    // Begin function returns an iterator to the head
    Iterator begin(int startIndex = 0){
        int useCustomStart = startIndex!=0;
        if(!useCustomStart) startIndex = minimumLoopIndex; //if automatic start, begin at the minIndex

        //Start at a valid starting index, make sure that start bit is actually set
        do{
            //std::cout << startIndex << " aa\n";
            if(_getBit(usedIndicies, startIndex)){
                break;
            }else{
                unsigned long long testBits = *(unsigned long long*)&usedIndicies[startIndex/8]; //type casting to 64bit int wont cause segfault because usedIndicies is padded with 16 additional bytes

                /*
                    these checks allow us to skip empty cells in the array

                    depending on the sparsity of the empty cells/ application use cases, some checks may not be necessary
                    for example if the empty cells are very sparse (5 or 6) per occupied element, just test the first 4 and 2 bits

                    TODO:
                        automatically determine this with a rough guess

                */

                if(!(testBits              )){ startIndex += 64-(startIndex&0x3F); continue; } //advance upto 64 empty elements
                if(!(testBits&0xFFFFFFFFull)){ startIndex += 32-(startIndex&0x1F); continue; } //advance upto 32 empty elements
                if(!(testBits&0xFFFFull    )){ startIndex += 16-(startIndex&0x0F); continue; } //advance upto 16 empty elements
                if(!(testBits&0xFFull      )){ startIndex +=  8-(startIndex&0x07); continue; } //advance upto  8 empty elements
                if(!(testBits&0xFull       )){ startIndex +=  4-(startIndex&0x03); continue; } //advance upto  4 empty elements
                if(!(testBits&0x3ull       )){ startIndex +=  2-(startIndex&0x01); continue; } //advance upto  2 empty elements

                startIndex++; //move just 1 element (This is required if the checks above fail)
            }

        }while(startIndex < maxSize);
        if(startIndex>maxSize) startIndex = maxSize; //make == to end()
        if(!useCustomStart) minimumLoopIndex = startIndex;

        return Iterator(startIndex, data, maxSize, size(), usedIndicies);
    }

    // End function returns an iterator to a null pointer (end of the list)
    Iterator end() {
        return Iterator(maxSize, data, maxSize, size(), usedIndicies);
    }
};

```

# Answer
> 0 votes
A simple method is a resizable array with a bitmap of which entries are used, and an index where to look for the next unused entry. Resize the array when it’s 90% full. Since you can typically check 64 bits for the next unset bit, finding an empty entry is very fast.

---
Tags: data-structures, c++
---


title: Find median in a sorted matrix

text:
# Question
Title: Find median in a sorted matrix
Suppose we are given a $n\times n$ matrix that is sorted row-wise and column-wise. We want to find the median in $\mathcal{O}(n\log{n})$.

This is my approach:
We know median is such element that is greater than exactly $\lfloor\frac{n^2-1}{2}\rfloor$ elements.
In such matrix, we always know that minimum value is the first element and the maximum value is the last element. So we declare and initialize two variables $\texttt{min}$ and $\texttt{max}$. Then we put $\texttt{mid} = \frac{\texttt{min}+\texttt{max}}{2}$. Afterwards, we're going to count the number of elements that are lower than $\texttt{mid}$ using binary search. For each row, the binary search can be done in $\mathcal{O}(\log{n})$ and we're doing it on $\mathcal{O}(n)$ rows. So this part takes $\mathcal{O}(n\log{n})$ time. If number of smaller elements than $\texttt{mid}$ is lower than $\lfloor\frac{n^2-1}{2}\rfloor$, then we put $\texttt{min}=\texttt{mid}+1$. Otherwise we put $\texttt{max}=\texttt{mid}$. Then recurse with new $\texttt{min}$ and $\texttt{max}$ values. The condiction to stop is when $\texttt{min}\geq\texttt{max}$. Then we return $\texttt{min}$.

Time complexity analysis:
According to the algorithm I explained, the recurrence relation should be: $$T(n)=T(\frac{n}{2})+\mathcal{O}(n\log{n}).$$ Using Master's Theorem, we can conclude $T(n)=\mathcal{O}(n\log{n})$. So we're done.

I want to know:

* Is my algorithm correct?
* Is the time complexity analysis correct?
* I know the algorithm is not explained accurate enough. For example I don't know I should count elements that are strictly smaller than $\texttt{mid}$, or I should also count elements that are equal to $\texttt{mid}$. Also when checking if the smaller elements are $\<$ or $\leq $ than $\lfloor\frac{n^2-1}{2}\rfloor$.

Any helps are immensley valuable to me.

## **EDIT.**

I found a problem in the algorithm. What if $\texttt{min}$ is not an element existing in the array? How can I solve the problem?

# Answer
> 2 votes
Is the time complexity analysis correct? no. you changed what `n` means when you included the master theorem. The runtime of this algorithm is `O(n^2*log(n))`

This algorithm does technically work, but it's a really dumb way of doing it (since at the very least the median of an unsorted list (of `n^2` numbers) can be found in `O(n^2)` time). With the structure you have, I'm pretty sure there exists an algorithm that computes the median in `O(n)` time but doing so will be a little tricky.

# Answer
> 2 votes
Probably main problem I see is recursion being made on *values*

> we put $mid=\frac{min+max}{2}$

> If number of smaller elements than mid is lower than $\frac{n^2−1}{2}$, then we put min=mid+1. Otherwise we put max=mid. Then recurse with new min and max values. The condition to stop is when min≥max. Then we return min.

every step halves $max - min$ \- and we have no information on size of that

example of worst case would be correctly placed distinct powers of 2 - halving $max-min$ would prune only 1 element at a time

# Answer
> 1 votes
The algorithm proposed by Mirzaian and Arjomandi (A. Mirzaian, E. Arjomandi, Selection in X + Y and matrices with sorted rows and columns, Information Processing Letters, Volume 20, Issue 1, 1985, Pages 13-17, ISSN 0020-0190, https://doi.org/10.1016/0020-0190(85)90123-1) can compute any order statistics, including the median, in $O(n)$.

Let $A$ be a matrix of real numbers, whose order is $n$ and in which the rows are sorted in descending order and the columns are sorted in ascending order. Moreover, let $\overline{n} = \lceil \frac{1}{2} (n+1) \rceil$. Then $\overline{A}$ is a submatrix of $A$ of order $\overline{n}$, consisting of the odd indexed rows and columns (plus the last row and columns of $A$ if $n$ is even). Letting $L$ be a list of reals and $a$ a real number, the $rank^+$ and $rank^-$ of $a$ in the list $L$ are defined as follows:

$rank^+(L,a) = |\\{x \in L:x\>a\\}|$;

$rank^-(L,a) = |\\{x \in L:x\<a\\}|$.

For $1 \leq k \leq |L|$, $a$ is the $k$th smallest item of $L$ if and only if $rank^-(L,a) \leq k-1$ and $rank^+(L,a) \leq |L|-k$. The selection algorithm is based on Theorem 3.1 in the paper, which states that, given the matrices $A$ and $\overline{A}$, for any real number $a$ it holds that (i) ${rank^-(A,a) \leq 4 \ rank^-(\overline{A},a)}$ and (ii) ${rank^+(A,a) \leq 4 \ rank^+(\overline{A},a)}$.

Determining $rank^-(A,a)$ can be done in $O(n)$ taking advantage of the fact that the rows and columns of $A$ are sorted respectively in descending and ascending order. Algorithm 1 shows how to compute $rank^-(A,a)$. Similarly, $rank^+(A,a)$ can be determined in $O(n)$ as well.

To select the $k$th item, the algorithm determines two items $a$ and $b$ with $a \geq b$ from $\overline{A}$. Letting $z$ denote the $k$th order statistic of $A$, the algorithm ensures that (i) $b \leq z \leq a$ and (ii) the number of items of $A$ whose value is less than $a$ and greater than $b$ is $O(n)$. The function MAselect (Mirzaian and Arjomandi Select), shown in pseudocode as Algorithm 2, determines the $k$th item of $A$ in $O(n)$.

MAselect simply calls the biselect function (Algorithm 3) with parameters $s$, $A$, $k\_1$ and $k\_2$, with $k\_1 \geq k\_2$. The pair $(x, y)$ is returned, so that $x$ is the $k\_1$th item of $A$ whilst $y$ is the $k\_2$th item.

Defining

$\overline{k\_1} = \begin{cases} n + 1 + \lceil \frac{1}{4} k\_1 \rceil & \quad \text{if } n \text{ is even}\\ \lceil \frac{1}{4} k\_1 + 2 n + 1 \rceil & \quad \text{if } n \text{ is odd} \end{cases}$

and

$\overline{k\_2}=\left\lfloor\frac{1}{4}\left(\mathrm{k}\_{2}+3\right)\right\rfloor$

$\overline{k\_1}$ is the smallest integer such that the $\overline{k\_1}$th item of $\overline{A}$ is at least as large as the $k\_1$th item of $A$, and $\overline{k\_2}$ is the largest integer such that the $\overline{k\_2}$th item of $\overline{A}$ is no larger than the $k\_2$th item of $A$.

The QuickSelect algorithm is Hoare's selection algorithm, which works in expected $O(n)$ time.

# Answer
> 0 votes
As non-unique values complicate things, let's keep to unique ones here.

`[determine] the number of elements that are lower than [split:] For each row, a binary search can be done in O(logn)[, doing it on n rows] takes O(nlogn) time.`
True, and about the best I expect when values are (guaranteed to be) ordered in each row, only.
With values ordered in each column, too, an *amortised analysis* should apply.
Assuming *ordered ascendantly*:
Let's start at the(some) middle element with a value used for the first split. The element to the right is known to be greater (all elements except split neither left nor up, actually, placing split well in the "middle half" of values), so continue with the diagonal neighbour right-up, continuing up until hitting a lower value or the top row, n/2 steps up, at most. From a value lower than split, go right until hitting a value no less than split or the rightmost column for at most another n/2 steps, a subtotal of n steps. Symmetrically for down&left for a total of 2n steps. (Speed up using exponential/binary search as seen fit.)

---

The hard part is continuing from this first boundary between *less than split* and *no less*.
"Shifting the index by one" in individual rows(columns) would seem to imply "$n^2$", with a possible factor of $O(\log n)$ for picking from a priority queue.
Finding a sequence of split values guaranteed to be dominated in length by $O(n)$ looks challenging - think of an adversary picking element values.

---
Tags: algorithms, search-algorithms, recursion, software-verification
---


# Question
Title: How to prove the time complexity of a function without calculating the precise number of steps taken? (Example: cost of optimal binary search tree)
This is my dynamic programming solution in Python to the problem of finding the cost of the optimal binary search tree:

```
def optBST(freqs):
    """C(i,j) = min(C(i,k) + C(k+1, j)) + sum(freqs[i:j])"""
    # i references the rows in the 2D array, representing the starting element.
    # j references the columns in the 2D array, representing the concluding element (exclusive).
    # L represents the length considered, with values ∈ [0, len(freqs)].
    # L = 0 (i.e., i = j) is already considered when the 2D array is initialized.
    # For each length, consider each i that defines a unique set of [i;j) ∈ [0; len(freqs))

    n = len(freqs)
    arr = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for L in range(1, n + 1):
        for i in range(n):
            j = i + L
            if j > n:
                break
            else:
                arr[i][j] = min(arr[i][k] + arr[k + 1][j] for k in range(i, j)) + sum(freqs[i:j])
    return arr[0][n]

keys = [10, 12, 20]
freqs = [34, 8, 50]
print(optBST(freqs))

```

For each $L$, there is a specific range of valid $i$ (the starting point), and $k$ will iterate $L$ times between $i$ and $j$.

So the number of steps taken for each L is:

$$(number\\;of\\;possible\\;i) * L = \[n - (L - 1)\] * L$$

There is $n$ such $L$, so when I summed all that up and worked out the expression, I got the following total steps for the worst case: $$\frac{n(n+1)(n+2)}{6}$$, which is $O(n^3)$.

However, this seems to be a fairly slow process to figure out the time complexity of this function. I imagine there must be a faster (yet still rigorous) way.

$L$ iterates about $n$ times. $i$ also iterates about $n$ times. But $k$ only iterates $m$ times, with $m$ tending toward $n$ but not strictly $n$ all the times.

How to argue that this is still $O(n^3)$?

Thank you!

# Answer
> 0 votes
As you write, $L$ iterates over $O(n)$ many values, $i$ over $O(n)$ many values, and the minimum and sum in the inner loop also iterate over $O(n)$ many values. In total, we get $O(n) \cdot O(n) \cdot O(n) = O(n^3)$ many operations.

This calculation doesn't show that $O(n^3)$ is tight. For this, we notice that if $L$ and $i$ are in the range $(n/4,n/3)$ then we don't break out of the innermost loop, and furthermore $j - i = L = \Omega(n)$. Hence we have $\Omega(n)$ values of $L$ and $I$ for which the minimum and sum take time $\Omega(n)$, for a total of $\Omega(n) \cdot \Omega(n) \cdot \Omega(n) = \Omega(n^3)$ many operations.

This kind of matching lower bound becomes "obvious" with practice, and need not be spelled out explicitly.

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


# Question
Title: Trying to give a proof about graphs. Having a hard time giving proof for Kruskals algorithm. Can you check my answer?
Question: Let G(V, E) be an undirected connected finite graph with the weight function w : E → R+. Let T be a minimum spanning tree of G. Prove that there exists a run of Kruskal’s algorithm that finds T (for suitable ordering of edges).

Answer: We show that the following proposition P is true by induction: If F is the set of edges chosen at any stage of the algorithm, then there is some minimum spanning tree that contains F and none of the edges rejected by the algorithm.

* Clearly P is true at the beginning, when F is empty: any minimum spanning tree will do, and there exists one because a weighted connected graph always has a minimum spanning tree.
* Now assume P is true for some non-final edge set F and let T be a minimum spanning tree that contains F. If the next chosen edge e is also in T, then P is true for F + e.

Otherwise, if e is not in T then T + e has a cycle C. This cycle contains edges which do not belong to F, since e does not form a cycle when added to F but does in T. Let f be an edge which is in C but not in F + e. Note that f also belongs to T, and by P, it has not been considered by the algorithm. f must therefore have a weight at least as large as e. Then T − f + e is a tree, and it has the same or less weight as T. However since T is a minimum spanning tree then this new graph has the same weight as T, otherwise we get a contradiction and T would not be a minimum spanning tree .So T − f + e is a minimum spanning tree containing F + e and again P holds.
* Therefore, by the principle of induction, P holds when F has become a spanning tree, which is only possible if F is a minimum spanning tree itself.

# Answer
To prove correctness of Kruskal's algorithm (and Prim's), you can use *the cut property*.

**Lemma** (The cut property). Let $\emptyset \subset S \subset V$ be a set of vertices and $e$ a cheapest edge with exactly one endpoint in $S$. Then there is a minimum spanning tree $T$ that contains $e$.

**Proof** (sketch). Let $S$ be as above and $e = uv$ a cheapest edge with $u \in S$ and $v \notin S$. Let $T'$ be an MST. If $e$ is in the tree, we are done. So assume $e$ is not in $T'$. Since $T$ is a spanning tree, there is a path from $u$ to $v$ in $T'$, and this path must leave $S$ at some point. So let $e' = u'v'$ be an edge in $T$ with $u' \in S$ and $v' \notin S$. Observe that $w(e') \geq w(e)$. Create $T = (T' \setminus e') \cup e$, the tree where we replace $e'$ with $e$.

1. $w(T) \leq w(T')$.
2. $T$ is spanning
3. $T$ is a tree.

To see why the last is true, observe that we replaced one edge with another, so the number of edges is the same as in $T'$, so we only need to show that it is connected. But this holds since $u'$ is connected to $v'$ via the (already existing) $u$-$u'$-path and $v$-$v'$-path, plus the edge $e$. It follows that $T$ is acyclic and therefore a tree.
> 1 votes

# Answer
The proof in question is based on a Wikipedia page at the time of posting. However, the conclusion that the cycle contains edges that do not belong to $F$ is inaccurate, instead the cycle contains edges that do not belong to $F + e$. The conclusion that $f$ also belongs to $T$ is also left unexplained, which is because $f$ belongs to $T + e$ but not $F + e$. Also note that it lacks a reference. Here is an improved version of the second part, which is in the current page:

> Now assume $P$ is true for some non-final edge set $F$ and let $T$ be a minimum spanning tree that contains $F$.
>
> If the next chosen edge $e$ is also in $T$, then $P$ is true for $F + e$.
>
> Otherwise, if $e$ is not in $T$ then $T + e$ has a cycle $C$. The cycle $C$ contains edges which do not belong to $F + e$, since $e$ does not form a cycle when added to $F$ but does in $T$. Let $f$ be an edge which is in $C$ but not in $F + e$. Note that $f$ also belongs to $T$, since $f$ belongs to $T + e$ but not $F + e$. By $P$, $f$ has not been considered by the algorithm. $f$ must therefore have a weight at least as large as $e$. Then $T − f + e$ is a tree, and it has the same or less weight as $T$. However since $T$ is a minimum spanning tree then $T − f + e$ has the same weight as $T$, otherwise we get a contradiction and $T$ would not be a minimum spanning tree. So $T − f + e$ is a minimum spanning tree containing $F + e$ and again $P$ holds.

Here is what it looks like in the more concise original 2009 page, it contains the same mistake in saying that $f$ is not in $F$ while it should say $f$ is not in $F + e$, my annotations are inside square brackets:

> Now assume $P$ is true for some non-final edge set $F$ and let $T$ be a minimum spanning tree that contains $F$.
>
> If the next chosen edge $e$ is also in $T$, then $P$ is true for $F + e$.
>
> Otherwise, $T + e$ has a cycle $C$ \[$T$ is connected\] and there is another edge $f$ that is in $C$ but not $F$ \[$F + e$ is acyclic\]. Then $T - f + e$ is a tree \[$f$ is not $e$ as $f$ belongs to $T + e$ but not $F + e$\], and its weight is not more than the weight of $T$ since otherwise the algorithm would choose $f$ in preference to $e$ \[$f$ is not less than $e$\]. So $T - f + e$ is a minimum spanning tree \[no more and no less than $T$\] containing $F + e$ and again $P$ holds.
> 0 votes

---
Tags: algorithms, graphs, proof-techniques, check-my-answer
---


# Question
Title: Are permutations of context-free languages context-free?
Given a context-free language $L$, define the language $p(L)$ as containing all permutations of strings in $L$ (i.e. all strings in $L$ such that the order of symbols is not important). Is $p(L)$ context-free?

I found two papers dealing with similar, but not identical, questions:

# Answer
> 5 votes
Start with simple context-free (or even regular) languages, and see what happens. For instance determine $p(L)$ for $L = (ab)^\*$ and $L=(abc)^\*$.

# Answer
> 1 votes
No, in general not. For example the MIX language, consisting of equal numbers of $\\{a,b,c\\}$ in any order is not context-free but is the permutation of the regular language $(abc)^\*$.

---
Tags: formal-languages, context-free, closure-properties, permutations
---


# Question
Title: How to build a deterministic or non deterministic finite automat for a language
$L\_1$ and $L\_2$ are two languages that have a finite deterministic automaton. $Σ = \\{0,1\\}$ for the two languages.

Let $L=\\{x∈L\_1\mid \text{there exists } y∈L\_2,\text{such that } \\#\_0(x)=\\#\_0(y)\\}$, here $\\#\_0(x)$ means the number of times $0$ appears in $x$.

This means we keep every word in $L\_1$ if there is a word in $L\_2$ where the number of $0$ in both words is equal. I need to prove that $L$ has a deterministic finite automaton. I need to build this automaton . I don't even know where to start. Would anyone be able to help me with this problem?

# Answer
A possible approach is to change the language $L\_2$. We only need to check the number of $0$'s in its strings, not the number of $1$'s nor the positions of the $1$'s.

Thus replace all $1$'s in the automaton for $L\_2$ by $\lambda$-transitions, and make the resulting automaton over $\\{0\\}$ deterministic again. Then, add loops with $1$ at every state of the automaton, to allow arbitrary letters $1$, at arbitrary places.

Finally we can apply the product construction for intersection on original automaton for $L\_1$ and the new automaton for $L'\_2$.
> 6 votes

---
Tags: finite-automata
---


# Question
Title: Does adding all of these sequences actually get us the set of all infinite sequences?
Section **1.9 Binary Strings** of the textbook *Introduction to Lattices and Order*, second edition, by Davey and Priestley, says the following:

> Let $\Sigma^\ast$ be the set of all finite binary strings, that is, all finite sequences of zeros and ones; the empty string is included. Adding the infinite sequences, we get the set of all finite or infinite sequences, which we denote $\Sigma^{\ast \ast}$.

I'm confident that, as alluded to, the set of all finite binary strings is a set of infinite sequences (in terms of the amount of finite sequences in the set). But does adding all of these sequences, which, as stated, would be an infinite amount of sequences, actually get us the set of all infinite sequences, as it claims? It intuitively seems like it would be true, but intuition is often wrong when reasoning about infinity in such ways, so I'm not totally sure.

# Answer
> 0 votes
You can prove this to yourself formally as follows: Say that $F$ is the set of finite binary strings, and $I$ is the set of infinite binary strings. Both of these sets are infinite. Now, the question is whether $I\cup F$ is the set of all binary strings. This is equivalent to saying that for any binary string $b$, $b\in I\cup F$. Take some such binary string $b$. $b$ must be either infinite or finite. If $b$ is infinite, $b\in I$, so $b\in I\cup F$. If $b$ is finite, $b\in F$, so $b\in I\cup F$. Therefore, for every $b$, we know that $b\in I\cup F$. Therefore, we know that $I\cup F$ (or $\Sigma^{\**}$ as the book calls it) is the set of all binary strings.

---
Tags: sets
---


# Question
Title: How do you tell whether a binary number is positive or negative?
Consider the figure in Exercise 2. If the current machine code that executes is 0x214bfffd and the values of the registers in the processor are as shown below, what is then the value of the input WD3 ? Answer as a 32-bit hexadecimal value. at = 0x00011021 v0 = 0x5234f1a0 v1 = 0x1114f111 a0 = 0xff001231 a1 = 0xffffffff a2 = 0x32252341 a3 = 0xff1245ee t0 = 0xffff12ff t1 = 0xffffffff t2 = 0xfffffff5 t3 = 0xfffff67f t4 = 0x0121ffff t5 = 0x55f7fff5 Assume that all other registers in the register file have value 0.

> The tex dollar sign is interfering with the dollar signs for the reigsters so I am writing it without dollar signs.

I understand everyhting except the fact that how we can tell directly that t2 = 0xfffffff5 is a negative number? Because that is what they are saying without any explanantion in the answer sheet. I know that a number where the most significant bit is 1 is negative and vice versa positive. But most of the questions I answered tell us to that it is a 4 bit number represented by 8 bit etc which you can then obviously tell. But in this case how do we know that they t2 = 0xfffffff5= -11 and not $t2 = 4294967285?

# Answer
> how do we know that they t2 = 0xfffffff5= -11 and not $t2 = 4294967285?

We don't. They're the same number (in mod 232 arithmetic, which is what your computer uses.)

Essentially, signed or unsigned is not a property of the number. It's a property of each individual assembly instruction. Some instructions don't care about signedness, like `add` or `sub`, because treating them as signed or unsigned doesn't change the result. Other instructions do care, like `mul`, and these instructions usually come in two variants. Let's write two C functions that differ only in signedness of the arguments.

```
int64_t foo(int32_t a, int32_t b) { return (int64_t)a * b; }
uint64_t bar(uint32_t a, uint32_t b) { return (uint64_t)a * b; }

```

If we compile them for MIPS, we get almost the same code but with `mult` versus `multu` instructions.

```
foo(int, int):
    mult    $4,$5
    mflo    $3
    mfhi    $2
    jr      $31
    nop
bar(unsigned int, unsigned int):
    multu   $4,$5
    mflo    $3
    mfhi    $2
    jr      $31
    nop

```

If you call `bar` with a signed argument like `bar(-11, 4)`, it will actually be treated as `bar(4294967285, 4)` because the unsignedness is baked into the `bar` function itself. The argument is always the binary pattern 0xfffffff5, which is just a binary pattern with no inherent meaning. If you pass this binary pattern to a function that expects an unsigned 32 bit integer, that's where the binary pattern suddenly becomes more meaningful.
> 2 votes

---
Tags: computer-architecture, computer-networks, c, assembly, mips
---


# Question
Title: Can I reduce a non semi decidable and undecidable language to a semi decidable and undecidable langauge? many-one reduction
Let's say a Language ***L*** is **NON-semi decidable** and **undecidable**. Let's also take the Halting problem ***H***, which is a **semi decidable** and **undecidable** language.

Is it possible to reduce ***L*** to ***H*** in a **many-one reduction**? I know that both are undecidable languages, and we can reduce an **undecidable** language to another **undecidable** language, but ***L*** being **NON-semi-decidable** and ***H*** being **semi decidable** kinda gives me the idea that these languages are not compatible, and a reduction is not possible. (Why? Well, I think, we are reducing a "harder" language to an "easier" one. It should be the other way around).

If a reduction was possible, are we reducing to just show the undecidability part of both languages but ignoring the (non) semi-decidable part?

Extra question: Would the other way around be possible? **H** reduced to **L**?

I think **yes**. Well both undecidable, compatible, this part is clear to me. But now we are reducing a semi-decidable language to a non semi-decidable language,which should be "harder". In theory in the lecture when A\<B, what we learned is that on the left side of the reduction (A) is max as "hard" as the right side of the reduction (B).

--Edit--

Specified in the title **many-one Reduction**. As Nathaniel pointed out, there are 2 types of reduction (which I wasn´t aware of) and what I needed in this question was the **many-one Reduction**.

# Answer
> 5 votes
It depends on the reduction.

Using a Turing reduction, it is possible. For example, any problem $A$ is Turing-reducible to its complement $\overline{A}$, by puting a negation on an answer given by an algorithm solving $\overline{A}$. If $\overline{A}$ is semi-decidable but undecidable, then $A$ is not semi-decidable (otherwise it would be decidable). If you consider $\overline{A}$ to be the halting problem, then you have your answer.

Note that it is not always possible that such a reduction exists.

Using a many-one reduction, it is not possible, because if $A\leqslant\_m B$ and $A$ is not semi-decidable, then $B$ is not semi-decidable, otherwise, you could, for an instance $x$ of $A$, compute $y = f(x)$ using the reduction, and then $x\in A$ if and only if $y \in B$, and you could use the algorithm that solves $B$ partially to solve $A$ partially.

---
Tags: computability, reductions, undecidability, halting-problem, semi-decidability
---


title: Repeated Substring Pattern

text:
# Question
Title: Repeated Substring Pattern
I've been working on the following challenge on LeetCode:

---

**Problem:** Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

---

During my exploration, I stumbled upon an interesting solution:

```
def repeatedSubstringPattern(s: str) -> bool:
    return s in (s + s)[1:-1]

```

I'm working to comprehend why this solution works.

Firstly, let's consider a string $x$ that can be constructed with a repeated substring pattern. In this case, $x$ takes the form:

$$x=SS\dots S$$

where $S$ is not an empty string, and there are more than two occurrences of $S$.

Now, if we concatenate two instances of $x$ and remove the first and last elements, we get:

$$y=ASS\dots SB$$

This string $y$ includes the original string $x$, and the function returns true.

However, I need to know how to demonstrate why the function returns false when the string does not have the specified form.

# Answer
> 2 votes
Instead of proving that the function returns false when the string is not of the specified form, let us use the contraposition.

Let $s = a\_1…a\_n$ be the string and assume that the function returns true. That means that $s$ is a substring of $a\_2a\_3…a\_na\_1a\_2…a\_{n-1}$. Since $s$ is of length $n$, that means that there exists $k\in\\{2, …, n\\}$ such that: $$s = a\_ka\_{k+1}…a\_na\_1…a\_{k-1}$$

Let $u = a\_k…a\_n$ and $v = a\_1…a\_{k-1}$. Then neither $u$ nor $v$ is empty and $s = uv = vu$.

Suppose (without loss of generality) that $|u| \leqslant |v|$ and let us prove by induction on $|u| + |v|$ that there exists $w$ and $m\_1$, $m\_2$ such that $u=w^{m\_1}$ and $v = w^{m\_2}$:

* if $|u| + |v| = 2$, then $u$ and $v$ are one-letter words and the result is direct with $w = u$ and $m\_1 = m\_2 = 1$;
* otherwise, since $uv = vu$ and $|u| \leqslant |v|$, that means that $u$ is a prefix of $v$, and there exists $v'$ such that $v = uv'$.

+ If $v' = \varepsilon$, then $w = u$ and $m\_1 = m\_2 = 1$ are suitable.
    + Otherwise $uuv' = uv'u$, so $uv' = v'u$. Using induction hypothesis, there exists $w$ and $m\_1$ and $m\_2'$ such that $u = w^{m\_1}$ and $v' = w^{m\_2'}$. Then $v = uv' = w^{m\_1+m\_2'}$.

Since $s = uv$, then $s = w^{m\_1+m\_2}$, and $w$ is a proper substring of $s$, because $m\_1 +m\_2 \> 1$.

---
Tags: algorithms, strings, python, substrings
---


# Question
Title: Understanding the last algebra step of this proof
Could someone help me understand why in the below proof, if $k \> log\_{2}n$, then $P(N\_i=1)\< \frac{1}{n}$?

# Answer
I didn't read the whole proof, but you don't seem to be having any problem with the previous statement that $\Pr(N\_i = 1) = \frac{1}{2^k}$. Then, using the fact that $2^x$ is an increasing function, the identity $2^{\log\_2 x} = x$, and $k \> \log\_2 n$: $$ \Pr(N\_i = 1) = \frac{1}{2^k} \< \frac{1}{2^{\log\_2 n}} = \frac{1}{n}. $$
> 2 votes

---
Tags: graphs, probabilistic-algorithms
---


title: Why does Elbrus use VLIW architecture?

text:
# Question
Title: Why does Elbrus use VLIW architecture?
I find the Russian Elbrus CPU fascinating.

It seems that it is fairly decent at performing calculations, and security. This is likely as it is heavily specific for military and financial industries, within Russia. Less focus was put on end user desktop computers.

However, I am confused about the decision to use the VLIW (Very Long Instruction Word) architecture? Even Linus Torvald did not speak favourably of VLIW in the past...

I assume, since Russia is heavily limited by sanctions and time constraints, they created the fastest CPU possible (which is slow in comparison to rivals such as Intel and AMD), but intend to rely heavily on the VLIW aspect to gain as much performance as possible out of their slow CPU?

Otherwise, what logical reason is there to pick VLIW (along with all of the SDKs, custom built software, Astra Linux etc... that need to support it) over x86?

# Answer
At some point in time people thought that VLIW computers were a very reasonable approach. And as long as you cannot handle out-of-order execution it is quite useful. You may be able to execute say four instructions in some cycles without doing anything complicated. I’ve actually seen a 6MHz maths-coprocessor (a very long time ago) that could theoretically do 60 million operations per second. Had you asked LT 10 years earlier the answer might very well have been different.

Elbrus is based on old designs. Right from the time when VLIW seemed a good idea. Its problem is that it is not flexible enough.
> 3 votes

# Answer
> However, I am confused about the decision to use the VLIW (Very Long Instruction Word) architecture?

A lot of advances in Computer Science that were made in the USSR and/or Russia are not well known in "The West". This is caused by the fact that until the 1990s, there was not much correspondence between Soviet and Western Scientists, and even after the fall of the Iron Curtain, there is still the language barrier, since Soviet and Russian Computer Scientists typically publish in Russian.

The theoretical foundations of what we now call *VLIW* were developed in the 1970s by Михаил Александрович Карцев. He wrote a textbook which was published in 1981, which is two years *before* Josh Fisher developed VLIW without knowing about Карцев's work.

So, by the time Эльбрус switched to VLIW with the Эльбрус 3 in 1990, Russians had more than 10 years of experience with VLIW.

> Even Linus Torvald did not speak favourably of VLIW in the past...

Not to take anything away from the great achievement that Linux is, but why would the Эльбрус design team in the late 1980s have cared what a completely unknown student from Finland thinks?

> I assume, since Russia is heavily limited by sanctions and time constraints, they created the fastest CPU possible (which is slow in comparison to rivals such as Intel and AMD), but intend to rely heavily on the VLIW aspect to gain as much performance as possible out of their slow CPU?

The Эльбрус 1 (1979) and Эльбрус 2 (1984) were out-of-order superscalar RISC designs. The Эльбрус 3 (1990) switched to a completely new VLIW design. So, clearly, the designers saw an advantage in VLIW over OoO superscalar RISC. Otherwise, why throw away an already designed and developed architecture and start from scratch?

Note that the USSR had quite sophisticated compiler technology. For example, *supercompilation* was invented and implemented in production compilers as earls as the 1960s, but practically unknown in The West until the 1990s.

VLIW allows to shift complexity from hardware (which is hard to change and slow to evolve) to the compiler, i.e., software (which is easy to change and quick to evolve).

These are different tradeoffs to make, but considering the long line of hardware-based security vulnerabilities in the last 10 years, it doesn't sound too stupid to put the complex stuff into the compiler, where it can easily be fixed by an update.

Just as an example, Intel added a new feature to their next-gen CPUs that is supposed to increase security. Except, four weeks ago, researchers found that it actually is a massive security hole. These CPUs aren't even on the market yet, but there is nothing Intel can do: the CPUs have been designed, the masks have been created, the production has started – they will have to go to market with a new security feature that actually makes the latest-get CPUs less secure. If this was a software feature, they'd just delay the launch by a couple of days and update the download links.

> Otherwise, what logical reason is there to pick VLIW (along with all of the SDKs, custom built software, Astra Linux etc... that need to support it) over x86?

The Эльбрус 2000 architecture is a dual-ISA architecture which supports both the *e2k* ISA and the x86/AMD64 ISA. Using the AMD64 ISA, it can run Linux, Windows, QNX, and others without the need to port anything, although Linux also has been ported to e2k natively.

Эльбрус uses dynamic translation to implement the x86/AMD64 ISA, very similar to the Transmeta Crusoe CPU that Linus Torvalds worked on.
> 1 votes

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


# Question
Title: Need help with adding elements to hashtable with linear probing
Here is an example problem which I have having trouble figuring out. The red text is the answer.

I get how the values are added before the hashtable is resized... that is common sense. (Insert 0 at index 3, 5 at index 1, etc.)

But when the table is resized, each element has a new position. HOW is 1's new index 0? HOW is 5's new index 7? How did each element of the array get assigned their new index upon table resize?

Any help would be appreciated.

Thanks

# Answer
It is the hash function h(k) that determines the position. They don't specify the hash function, but instead they give the value to which h(k) evaluates for both tables.

The hash function is usually a 32bit or 64bit integer **that gets trimmed to the size of the hash table**. Say they were using crc32 as hash algorithm then h(k) for the old table will be h(k)=(crc32(k) **mod 7**) and for the new table h(k)=(crc32(k) **mod 14**).

So it is very unlikely that the same k will have the same position in each table.

When the hash table resize, you have to move the values from the old table to the new table while re-hashing their positions.
> 1 votes

# Answer
It's not explicitly defined - rather there's an implicit subindex (based off the table's size) to the hash-function. At the start we had e.g., $h(0) = h\_7(0) = 3$. They are then informing you that $h\_14(0) = 8$. There is no explained reason for this. They then re-insert the data to the larger hash table going over the old data in the order it appears in the hash table.
> 0 votes

# Answer
It says in red letter in the given answer: **re-hash the values in the order they appear in the old table**. It is analogous to the operation of a self-resizing array which has to copy over the old elements from the old array into the new (larger size) array.

When a hastable is resized (i.e. enlarged once it reaches its load factor limit) all the keys that exist in the hashtable are re-hashed. The positions of the values need to be placed in their rightful position in the new hashtable, so they have to be inserted with the new hash function so that they can be found accordingly.

The key values are hashed in the order they appear (from left to right) in the hashtable because this is essentially the only way to iterate through all the values of a hashtable (unless you are using an augmented hash table structure like the LinkedHashTable or something).

The upside to rehashing everything is that if the old hashtable had a large number of collisions, when the hashtable resizes to a larger size, many of the elements that collided would spread out now.
> 0 votes

---
Tags: algorithms, data-structures, search-algorithms, hash-tables, search
---


# Question
Title: Help understanding Petersons Algorithm for N Processes
I read the wikipedia article:

https://en.m.wikipedia.org/wiki/Peterson%27s\_algorithm

What I don't understand is how the algorithm is guaranteed to work when the processor or processors are switching between threads. What stops simultaneous advancement?

# Answer
> 6 votes
The rough intuition is that at least one contending process becomes stuck at each step of the stairway to heaven (AKA the critical section) when there are enough contenders present. Consequently there's at most one of them left at the top rung of the ladder.

Having said that, I do remember many students struggling with grasping the finer details. It is a subtle algorithm. What could help is to model and simulate it, say, in Promela, where you could also check exhaustively whether certain properties (expressed as runtime assertions or LTL formulas) hold for the model. See below for such a model. The spin homepage should get you started with that tool.

The properties of $n$-process Peterson's mutual exclusion algorithm as it is presented e.g. in M. Ben-Ari's textbook *Principles of Concurrent and Distributed Programming (Second edition)* depend on a few assumptions about the execution model. These relate to (a) what actions are atomic and (b) what progress is expected of enabled actions. Textbook assumptions aren't necessarily guaranteed in real-life implementations. The wikipedia page you mention has some warnings about that.

Here's an old Promela model I once made for Ben-Ari's version of the algorithm.

```
/* Peterson's solution to the mutual exclusion problem - 1981 */
/* Modeling insprired by Ben-Ari */
#define N 3
#define i _pid+1

inline critical_section() {
     printf("%d in CS\n", _pid);
}
inline non_critical_section() {
  printf("%d in non-CS\n", _pid);
  do                            /* non-deterministically choose how
                                   long to stay, even forever */
    :: true ->
         skip
    :: true ->
         break
  od
}

byte en[N] = 0, last[N] = 0;

active[N] proctype p()
{
  byte j,k;
  do
    :: non_critical_section();
       for (j : 1 .. N) {
         en[i-1] = j;
wap:     last[j-1] = i;
         for (k : 1 .. N) {
           if
             :: k == i
             :: k != i ->
                (en[k-1] < j || last[j-1] != i)
           fi
         }
       };
csp:   critical_section();
       en[i-1] = 0;
  od
}

ltl mutex { !<>(p[0]@csp && p[1]@csp) }
ltl dlf2   { [](p[0]@wap && p[1]@wap -> <>(p[0]@csp || p[1]@csp)) }
ltl dlf3   { [](p[0]@wap && p[1]@wap && p[2]@wap -> <>(p[0]@csp || p[1]@csp || p[2]@csp)) }
/* ltl dlf4   { [](p[0]@wap && p[1]@wap && p[2]@wap && p[3]@wap -> <>(p[0]@csp || p[1]@csp || p[2]@csp || p[3]@csp)) } */
ltl aud   { [](p[0]@wap && ([]!(p[1]@wap || p[2]@wap /*|| p[3]@wap */)) -> <>p[0]@csp) }
ltl ee1    { [](p[0]@wap -> <>p[0]@csp) }
ltl ee3    { [](p[2]@wap -> <>p[2]@csp) }

```

What I have **not** checked is whether the wikipedia page and Ben-Ari agree on what constitutes an $n$-process version of Peterson's mutual exclusion algorithm for 2 processes.

---
Tags: multi-tasking, shared-memory, multithreaded
---


# Question
Title: Algorithm for display nodes of a particular node based on in-degree and out-degree
Suppose we have the following directed graph. When I click on - say - node $e$, it should make the in-pointing neighbors and out-pointing neighbors of node $e$ red, as shown in the below Expected Result. My purpose is that when I click on any node of a directed graph it should tell me what nodes it is influencing (out-degree) and what are nodes which influenced it (in-degree).
**I want to make an algorithm for it. I don't know how to make it**.

* Definition: For a directed graph $G=(V(G), E(G))$ and a vertex $x\_1 \in V(G)$, the
*Out-Degree* of $x\_1$ refers to the number of arcs incident from $x\_1$. That is, the number of arcs directed away from the vertex $x\_1$. The
*In-Degree* of $x\_1$ refers to the number of arcs incident to $x\_1$. That is, the number of arcs directed towards the vertex $x\_1$.

From mathonline.wikidot.com:

Expected Result:

**I want to make mathematical modeling for following pseudo code:**

1. Click on node i (e in example).
2. look for in-degree relationship r and get nodes(node d in below example).
3. look for out-degree relationship r and get nodes (node b and f in example).
4. display the nodes visited through relationship r including e (expected result graph).

# Answer
If you want to highlight the neighbors:

Use adjacency list representation, where each node has a list of all out-edges out of it, and a list of all in-edges into it. Then given a node you can rapidly identify what to highlight.

If you want to highlight everything connected to that node (at any distance):

Use DFS to find the set of nodes that are reachable from it.
> 0 votes

# Answer
Your solution will highly depend on how you represent your graph. If your graph representation is stored both in-neighbours and out-neighbours, then this is a trivial task. So I assume you have a standard adjacency list representation of each node $v$ followed by a list of each of the out-neighbours which $v$ points to. For example, your graph above would be represented as:

* $a: b, c, f$
* $b: c$
* $c: d$
* $d: e$
* $e: b, f$
* $f: $

This sort of graph data structure supports a function like

```
G.getNbrs(a)
```
which would return the out-neighbours of $a$.

For you to find the neighbours which point inward to a node, you will essentially have to check each other node:

```
event clickOnNode(v) {
    turnRed(G.getNbrs(v));
    for each node n of G:
        if (G.getNbrs(n).contains(v)) // that is: if v is in the nbrhd of n
             turnRed(n);
    turnRed(v);   // if you also want the clicked-on node to appear red(?)
}

```

Of course, if your graph is represented differently (like an adjacency matrix) then the algorithm would have to be adjusted accordingly.
> 0 votes

---
Tags: algorithms, graphs, directed-graphs
---


# Question
Title: Finding the pair of nodes with maximum distance in an arbitrary rooted tree
Suppose we are given an arbitrary rooted tree. We want to find two nodes that have the maximum distance among all pairs of nodes. I am looking for an algorithm with time complexity $\mathcal{O}(n)$, where $n$ is the number of nodes in the tree. Note that there may be more than one pair of nodes that satisfy this condition, but finding any one pair is enough.

Also, I am writing code in Java, and the input format is as follows: the first line gives the number of nodes, and the next $n-1$ lines give two numbers $u\_i$ and $v\_i$ each, indicating that there is an edge between nodes $u\_i$ and $v\_i$. What would be a good data structure to store and represent the rooted tree for this problem and implement the algorithm?

Any help is greatly appreciated!

# Answer
> 1 votes
I don't know much about java, but there could be several ways to represent the tree:

* an array of $n$ adjacency lists, like an undirected graph;
* an array of $n$ integers, that contains the parent of each node (and so that the root is its own parent);
* an inductive structure, with a node and the list of its children.

The idea of the algorithm is simple:

* find a leaf $x$ of maximum depth;
* find the farthest node $y$ of $x$ (either by using BFS, or by finding a leaf of maximum depth in the tree rooted in $x$).

Let $V$ be the set of nodes of the tree.

To prove that $d(x, y) = \max\limits\_{u,v \in V^2}d(u, v)$, consider $u$ and $v$ two nodes that maximize $d(u, v)$, and $w$ be their lowest common ancestor and consider two cases:

* if $w$ is an ancestor of $x$, then let $z$ be the lowest common ancestor between $u$ and $x$ (without loss of generality). Since $x$ has greater depth than $u$, then: $$d(u, v) = d(u, w) + d(w, v) \leqslant d(x, w) + d(w, v) = d(x, v)$$
* if $w$ is not an ancestor of $x$, then let $z$ be the lowest common ancestor between $w$ and $x$. Since $x$ has greater depth than $w$, then: $$d(u, v) = d(u, w) + d(w, v) \leqslant d(u, z) + d(w, v) \leqslant d(x, w) + d(w, v) = d(x, v)$$

In both case, the maximum distance can be reach with $x$ as one of the two nodes, which proves the correction of the algorithm.

---
Tags: algorithms, graphs, data-structures, trees, graph-traversal
---


# Question
Title: Cumulative sum algorithm that worked on parallel computing
Compared to "vectors addition" which can naturally work independently for the summation of each of its corresponding elements, it allows parallel work by processors. Example:

```
[1 2 3] + [4 5 6] = [5 7 9]

```

Which only requires 1 iteration.

How to make the "cumulative sum" operation algorithm work in parallel on a vector? Consider the following sequential cumulative sum problem: Give vector

```
a_vector := [1 2 3]
empty_vector := []
Step 1 -> [1]
Step 2 -> [1 3]
Step 3 -> [1 3 6]

```

Those steps filling up the empty vector. So it takes 3 iterations longer.

Though both produce the same number of elements as the number of elements in its operand, so it can be said that both are elementwise operations.

# Answer
Use a parallel prefix sum algorithm. See Wikipedia for some examples.
> 1 votes

---
Tags: parallel-computing
---


# Question
Title: Resolution and what it means to derive the empty set
When using resolution, if the empty set {Ø} is derived from a formula like {¬x,¬y} {x,y}, does that mean the formula is unsatisfiable?

If this is the case, why **is** `{x,y},{¬x,¬y},{x,¬y}` satisfiable, and

`{x},{¬x},{x,y,z,w}` **is not** satisfiable?

# Answer
To complete the Kyle's answer:

A CNF (in Conjunctive normal form) formula, $F$, can be considered as a set of clauses, eg : $F=\\{C\_1,C\_2 \ldots C\_m\\}$ and each clause can be regarded as a set of literals, eg : $C\_1=\\{x,y\\}, C\_2=\\{\lnot x, \lnot y\\}$.

If $F=\varnothing$ i.e. $F$ is the empty set and does not contain any clause then $F$ is satisfiable (=tautology).

If $F=\\{\varnothing, C\_1 \ldots\\}$ i.e. $F$ contains the empty clause then $F$ is not satisfiable. The empty clause can be obtained by the resolution rule eg : the resolvent of $C\_3=\\{x\\}$ and $C\_4=\\{\lnot x\\}$ is the empty clause $\varnothing=\\{\\}$.
> 3 votes

# Answer
You seem to be trying to describe and use the resolution proof system. Two points:

1. The resolution rule is only applied to two clauses at a time. The resulting clause, the resolvent, can be added to the list of propositional clauses and used in future inferences. But a single resolution inference only ever involves two clauses.
2. You can only remove one pair of complementary literals per invocation of the resolution rule. So while (x,y) (-x, -y) -\> (y -y) is a valid inference, albeit tautological, (x,y) (-x, -y) -\> Ø is not a valid inference.
> 2 votes

# Answer
To address **why** the first example is satisfiable but the second is not, it may be helpful to informally think about what's going on geometrically.

The set of all truth-assignments may be represented as the n-cube, or Boolean poset $B\_n$. Every literal corresponds to a distinct (n-1)-face; each positive literal corresponds to the filter of a distinct rank 1 element and each negative literal corresponds to the ideal of a distinct rank n-1 element.

If a k-clause encodes the set of all truth-assignments that satisfy it, its dual encodes the (n-k)-face of all truth-assignments that do *not* satisfy it. (Equivalently, if an input in CNF represents the intersection of unions of maximal ideals and filters of $B\_n$, its dual represents the union of closed intervals.) Resolution on the dual input essentially glues unsatisfiable faces together.

Thus, if you can produce the empty clause via resolution, you have shown that the set of unsatisfying faces can be glued together to produce the n-cube itself. Why? Because a 0-clause must be unsatisfied by an (n-0)-face of assignments, which is all of them.

In the dual formulation of your first example, you have three 0-faces of the 2-cube. Obviously three 0-faces cannot cover all four 0-faces of the 2-cube, so the collection must be satisfiable.

In the dual formulation of your second example, you have two 3-faces and one 0-face of the 4-cube. Since we can glue the two 3-faces together to form the 4-cube, the collection must be unsatisfiable; the 4-face will absorb all other subfaces since it entails them, rendering them redundant.
> 1 votes

# Answer
This is very old post, but I got same question by myself and luckily I've found valid answer so I just write. As I'm not professional pure academic person with respsect to logic, this might be too informal.

I understand the resolution rule by followings.

$$ \frac{a \vee p \quad \neg p \vee b}{a \vee b} $$ $$ \equiv (a \vee p) \wedge (b \vee \neg p) \rightarrow a \vee b \text{ is tautology} $$

## Not all tautology is empty clause

Note that not every tautology returned by resolution are empty clause. Let's see some examples.

$$ \frac{p \vee q \quad \neg p \vee \neg q}{p \vee \neg p} $$

Although resolution rule generated tautology, but $p \vee \neg p$ is not an **empty** clause. It's just one of tautologies.

## Empty clause is only occured with the contradictive literals

The moment that resolution rule returns empty is only for opposite clauses with a single literal(ex: $p$ and $\neg p$). There is a way to comprehend 'empty clause' situation.

$$ \frac{false \vee p \quad false \vee \neg p}{false \vee false} $$

It looks silly, but is still valid since $false \vee p \equiv p$ and $false \vee \neg p \equiv \neg p$. My notation for understanding resolves this vagueness. Just replace the literals in resolution rule with proper symbols:

$$ (false \vee p) \wedge (false \vee \neg p) \rightarrow false \text{ is tautology} $$

It still looks weird, but at least it's defintely true, because the proposition $false \rightarrow false$ is tautology. Therefore the result of the resolution rule itself doesn't say anything about prior inputs directly.

But we all know that we start from CNF, and we all know $p \wedge \neg p$ is $false$ which isn't satisfiable. Since the only case when it gives empty clause is such contradictive situation, we know empty clause implies unsatisfiability.

## Your examples

### Example 1

1. Resolve 1st clause $x \vee y$ with 2nd one $\neg x \vee \neg y$, get $x \vee \neg x$ by removing $y$ from them.
2. Resolve 1st clause $x \vee y$ with 3rd one $x \vee \neg y$, get $x$ by removing $y$ from them.
3. Resolve 2nd clause $\neg x \vee \neg y$ with 3rd one $x \vee \neg y$, get $\neg y$.
4. Resolve $x \vee \neg x$ with $x$ which just repetively returns $x$.
5. Resolve $x \vee y$ with $\neg y$ which again returns $x$.
6. Remains are also same- just generate the clause that already exists.
7. No empty clause, and satisfiable.

### Example 2.

1. Resolve 1st clause $x$ with 2nd one $\neg x$ and tada empty clause, which tells that given CNF is unsatisfiable.
> 0 votes

---
Tags: algorithms, logic, satisfiability, propositional-logic
---


# Question
Title: How to convert NFA with multiple start states to NFA with single start state without epsilon transition?
I can easily convert NFA with multiple start states to NFA with single start state with epsilon transition.

But I want to know how can I do so without epsilon transition

Here's my idea

1. Suppose s1 and s2 are the start states. Let s0 be the new start state.
2. If s1 or s2 are final states, make s0 final state.
3. Duplicate all outgoing-edges (transitions) from s1 and s2 to s0 without changing edge labels.
4. s1 and s2 are no longer start states.

I feel my idea should work, but I just wanted a confirmation.

# Answer
> 1 votes
You got the right intuition. Here is how to do it formally:

Removing $\epsilon$-transitions is standard and easy to do. Lets say that the resulted NFA $A = \langle \Sigma, Q, Q\_0, \delta, F\rangle$ that you get has more than one initial state, that is $|Q\_0| \> 1$. In this case, you can modify $A$ to get an equivalent automaton with a single initial state, simply by adding one more state, and without using $\epsilon$-transitions:

Define the NFA $B = \langle \Sigma, Q\cup \\{q\_{new}\\}, \\{q\_{new}\\}, \eta, F\cup \\{ q\_{new}: Q\_0\cap F\neq \emptyset\\}\rangle$, where $q\_{new}\notin Q$ , and for every letter $a\in \Sigma$ and state $q\in Q$, it holds that:

1- $\eta(q\_{new}, \sigma) = \bigcup\limits\_{q\in Q\_0} \delta(q, \sigma)$.

2 - $\eta(q, \sigma) = \delta(q, \sigma)$.

So essentially $B$ is obtained from A by adding a new state $q\_{new}$, which is the only initial state of $B$. Upon reading $\sigma$ from $q\_{new}$ we move nondeterministically to any state that we can reach in $A$ from $Q\_0$ upon reading $\sigma$, and finally $q\_{new}$ is considered accepting only when there is an initial state in $A$ that is accepting (this part handles the empty-word $\epsilon$).

Correctness follows easily. I leave the empty-word case for you, and simply note that once $B$ leaves the state ${q\_{new}}$, it cannot go back to it, and has to proceed by following transitions of $A$. Now every accepting run of $A$ can be replaced by an accepting run of $B$ -- you only have to replace the initial state of the run with $q\_{new}$, and then verify that the resulted run is legal in B and accepting. Conversely, every accepting run $r$ of $B$ on a non-empty word has a corresponding accepting run of A on the same word: if $q\_{new} \xrightarrow{a} q$ is the first transition that $r$ traverses, then by definition, there is some $q\_0\in Q\_0$ such that $q\in \delta(q\_0, a)$ and thus we can replace the transition $q\_{new} \xrightarrow{a} q$ with $q\_0 \xrightarrow{a} q$ to get an accepting run of $A$.

So what you should do first is define formally the automaton that you think works, and then try to prove that it is indeed equivalent. I leave the details to you.

Note that what I actually did is removal of $\epsilon$-transitions -- it can be done in several ways, but if you care about a single initial state, that can also be done, as we showed.

---
Tags: automata, finite-automata, nondeterminism
---


title: $xx$ application in lambda calculus

text:
# Question
Title: $xx$ application in lambda calculus
I'm just getting started with lambda calculus and I see that the fixed-point $Y$ combinator is defined as:

$Y = \lambda f . (\lambda x . f(x x))(\lambda x . f(x x))$ (\*)

I read here that something like $t s$ (where $t, s$ are both terms) represents an application of a function $t$ to the input $s$, so in (\*) I suppose that $x x$ represents the application of $x$ to the input $x$.

The problem I have with that interpretation is that it supposes that $x$ is itself a function (or an *abstraction*, as defined in the article).

However, in general $x$ seems to just denote a *variable* so how should I understand $x x$?

# Answer
> 2 votes
You're right: $xx$ is the application of $x$ to $x$. But this is not a problem as long as you remember that you're only dealing with *syntax* here: $x$ is a term, $x$ is another term, so $xx$ is a term. In particular, to form an application term $MN$, you do *not* suppose that $M$ is an abstraction.

Another way to put this is that in λ-calculus, *everything is a function*, not only the abstractions. $x$, in particular, is a function that you can apply to any argument.

Of course, in a typed setting terms like $Y$ raise typing issues. But you're doing untyped λ-calculus here, so you don't need to find a well-formed type for $x$.

By the way, having this kind of weird (at first sight...) behaviour is precisely what makes λ-calculus interesting as a computation model.

# Answer
> 1 votes
in $\lambda x . f(xx)$, you are correct to say that $x$ is the variable of a lambda abstraction. However, a variable is simply a placeholder for the substitution that happens when the lambda abstraction is applied to some argument. Consider the following application: $$ (\lambda x . f(x\\,x))\\,y \\;\to\_\beta\\; f(y\\, y) $$ The way you evaluate any application $(\lambda x.t)s$ is by substituting every instance of $x$ in $t$ with $s$.

In the example above $t$ is $f(x\\,x)$, and $s$ is $y$, therefore you substitute all the $x$'s in $f(x\\,x)$ with $y$'s, obtaining $f(y\\,y)$. In this case $y$ is a free variable, but in the case of he $Y$ combinator it's bounded, therefore $y$ could be substituted with any possible $\lambda$-term.

Now that the semantics is clearer, you may ask what would it mean to "feed a function to itself" as its own input. Consider the following combinator (*combinator* is just a name for a $\lambda$-term with no free variables): $$ \Omega = \lambda x. x x $$ What would it mean to apply this term to itself? $$ \begin{aligned} \Omega\\,\Omega &= (\lambda x. x x)(\lambda x. x x)\\ &\to\_\beta (\lambda x. x x)(\lambda x. x x) \\ &\to\_\beta \\;... \end{aligned} $$ Since every time we substitute the two $x$'s in the expression $x\\,x$ with the term $(\lambda x . xx)$ we obtain a new term: $(\lambda x . xx)(\lambda x . xx)$. This happens to be precisely what we started with, and therefore if we keep applying the beta-reduction rule we will always end up where we started; the evaluation never terminates.

If we now come to the $Y$ combinator, we can show that it has a similar property. Notice what happens when we apply $Y$ to a lambda-term $F$.

$$ \begin{aligned} Y F &= (\lambda f . (\lambda x . f(x x)) (\lambda x . f(x x)))F \\ &\to\_\beta (\lambda x . F (x x)) (\lambda x . F (x x)) & (1) \\ &\to\_\beta F (\lambda x . F (x x)) (\lambda x . F (x x)) & (2) \\ &= F(YF) & (3) \end{aligned} $$ In (1) we simply substitute the $f$ variable for the term $F$. In (2) we substitute the $x$'s in $F(x x)$ with $(\lambda x . F (x x))$, and (3) follows from the fact that we are obtaining line (1) with an $F$ applied to it.

The fact that $YF = F(YF)$ (i.e. $YF$ is a *fixed point* of $F$) implies that: $$YF = F(YF) = F(F(YF)) = F(F(...F(YF)))$$ And therefore applying the $Y$ combinator to any term $F$ basically applies the term to itself forever. This can be used to write "recursive functions" in the lambda calculus.

Sorry if that was a bit long, I just thought that taking it step by step would help you better understand what is meant by $x\\,x$.

---
Tags: lambda-calculus
---


# Question
Title: Conflicting definitions surrounding asymptotic notations. Please advise!
I spent the last couple of days trying to understand the different asymptotic notations but it seems I'm hitting some conflicting information.

For context, I believe I've understood the formal definition of different notations, as they are fairly similar to the definition of limit I've learned before. It also seems to me that, in practice when people talk about $Big\\;O$, they're most likely referring to $Big\\;\Theta$ for the worse case (e.g., the discussion of $Big\\; O$ in this CMU handout).

Here is what confuses me:

In this Reddit post, some commenters claimed that **any function** is $Big\\;O$ / $Big\\;\Theta$ / $Big\\;\Omega$ of **itself**. I'm okay with this because it reflects the definition. However, this phrasing seems to imply that when we say $f(n) = O(g(n))$, $g(n)$ isn't necessarily of the 'clean' forms $n$, $log(n)$, or $n^2$. For example, using the above phrasing, it seems correct to say that $n^2 - 3n + 4 = O(n^2 - 3n + 4)$, which leads me to this explanation of little o on Wikipedia.

To summarize, it says:

$f(x) = o(g(x)$ as $x \to \infty$

if for every positive constant $ε$ there exists a constant $x\_{0}$ such that

${\displaystyle |f(x)|\leq \varepsilon g(x)\quad {\text{ for all }}x\geq x\_{0}.}$

Per this definition, it seems correct to say $f(n) = o(g(n))$ for $f(n) = n^2 - 3n + 4$ and $g(n) = 2n^2$ because $g(n) ≥ f(n)$ for $n ≥ 1$ for all positive values of $ε$.

However, the CMU handout linked above also has a section at the end that explains little o, where it says $f(n) = o(g(n))$ when $\lim\limits\_{n \to \infty} \frac{f(n)}{g(n)} = 0$.

This seems incompatible with the example I gave above for Wikipedia's definition, because $\lim\limits\_{n \to \infty} \frac{n^2 - 3n + 4}{2n^2} = \frac12$

How should I reconcile these two definitions?

Thank you very much!

# Answer
> 1 votes
The two definitions are equivalent and it is not true that $n^2 - 3n + 4 = o(2 \cdot n^2)$.

The arbitrary positive $\varepsilon$ in the definition is a real number, not just positive integer. For example for $\varepsilon = \frac14$ we do not have $n^2 - 3n + 4 \leq \varepsilon \cdot 2n^2$ for large enough $n$.

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


title: Question about ALL-NFA in PSPACE

text:
# Question
Title: Question about ALL-NFA in PSPACE
Here is the explanation in Sipser's. For step 3, why should we accept only when none of the markers lie on an accept state? If the alphabet of the language is $\Sigma = \\{a,b,c\\}$, and after the first iteration, let's say $a$ and $b$ lie on the accept state while $c$ doesn't (meaning that c is not in the language). Thus, this language will not be in ALL-NFA because $M$ does not accept $c$. However, according to the procedure described below, the language will be rejected, because at this point there are 2 markers lying on an accept state:

Consider the language $ALL\_{NFA} = \\{\langle A \rangle: \text{$A$ is an NFA and $L(A) = \Sigma^\*$}\\}$.

The following nondeterministic linear space algorithm decides $ALL\_{NFA}$.

Nondeterministically guess an input string rejected by the NFA and use linear space to guess which states the NFA could be at a given time. On input $\langle M\rangle$ where $M$ is an NFA:

1. Place a marker on the start state of the NFA $M$.
2. Repeat $2^q$ times, where $q$ is the number of states of $M$. 2.1 Nondeterministically select an input symbol and change the position of the markers on $M$’s states, to simulate reading that symbol.
3. Accept if stages 2 reveals some string that $M$ rejects, i.e., if at some point none of the markers lie on accept states of $M$. Otherwise, reject.

# Answer
> 3 votes
Note that the procedure decides the complement of $ALL\_{NFA}$, which is sufficient as $PSPACE = NPSPACE$.

The procedure checks whether the NFA $M$ rejects some input. The idea is simple, we actually simulate the run of the DFA $D$ that is obtained by applying the subset-construction on $M$ (a construction that keeps track of the set of states that $M$ can be in at any point in time, that is, the state-space of $D$ is $2^Q$, where $Q$ is the state-space of $M$). Clearly $|D|\leq 2^{|Q|}$. Hence, if $D$ rejects a word, then it rejects a word of length at most $2^{|Q|}$ as we can omit cycles from long rejecting runs of $D$.

Since we want to check whether $D$ rejects some word $w$ of length at most $2^{|Q|}$ using only linear space, we can guess the word $w$, letter after letter, while keeping track (1) only of the current letter of $w$, (2) only of the subset of states that $D$ reaches after reading the prefix of the $w$ that we've guessed so far (meaning, we do not write the whole description of $D$, but only the current subset of states that $D$ is in after reading the guessed prefix of $w$), and finally (3) we hold some counter to keep track at which iteration we're in (we can encode the iteration number in binary, which takes at most polynomial space in $|Q|$).

So the markers in a sense remember the subset of states that we described in item (2) above. If we marked at some iteration only rejecting states, it means that we've succeeded to guess so far a word that is rejected by $D$ (and thus rejected by $M$).

In your example, if the alphabet is $\Sigma = \\{a, b, c\\}$ where $c\notin L(M)$, then it suffices to guess on letter which is $c$ to see that all the states that are reachable from the initial state of $M$ upon reading $c$ are rejecting, and then we accept. So we mark only states that correspond to the current guessed letter, and not those that correspond to all possible guesses.

---
Tags: complexity-theory, automata, space-complexity
---