# Question
Title: Why is the time complexity of insertion sort not brought down even if we use binary search for the comparisons?
There are two factors that decide the running time of the insertion sort algorithm:
the number of comparisons, and the number of movements.
In the case of number of comparisons, the sorted part (left side of $j$) of the array is searched linearly for the right place of the $j^{th}$ element. If instead, we use a binary search, then the time complexity of finding a place for the $j^{th}$ element comes down from $\operatorname{O}(n)$ to $\operatorname{O}(\log n)$. So, for all the $n$ elements, the time complexity for comparisons becomes $\operatorname{O}(n \log n)$. Even so, the number of movements is still going to take $\operatorname{O}(n)$ time, and the total time complexity isn't brought down and remains $\operatorname{O}(n^2)$. Why is that?

Are any of my statements wrong assumptions?

Can a possible explanation be: the total time complexity isn't brought down and remains $\operatorname{O}(n^2)$. This is because to search an element (using binary search) it takes $\operatorname{O}(\log n)$ time, and to move the elements it takes $\operatorname{O}(n)$ time. Total cost is $\operatorname{O}(\log n)+\operatorname{O}(n)=\operatorname{O}(n)$ time. To do this for $n-1$ elements, it takes $n(n-1)=\operatorname{O}(n^2)$ time?

# Answer
> 10 votes
For the $j^{th}$ element, you would do ~ $\log j$ comparisons and (in the worst case) ~$j$ shifts.

Summing over $j$, you get

$$ \sum\_{j = 1}^{n} (j + \log j) = \frac{n(n+1)}{2} + \log (n!) = O(n^2 + n \log n) = O(n^2) $$

The idea is that the linear work of shifting trumps the logarithmic work of comparing. You end up doing less comparisons, but still a linear amount of work per iteration. So the complexity does not change.

# Answer
> 2 votes
The "possible explanation" after the edit in the question is exactly correct. That's why the time complexity is not improved.

On the other hand, unless the array is already mostly sorted, or if the array is very small, using binary search to find where to insert an array element is very likely to make the sorting almost twice as fast.

On the other hand, for large n where sorting an array using insertion sort is unacceptably slow, making it twice as fast still leaves it unacceptably slow.

# Answer
> 0 votes
I don't think the complexity is remain the same. Time complexity of binary insertion sort, if optimized the code

Sample Link: https://cboard.cprogramming.com/cplusplus-programming/139831-analysis-binary-insertion-sort-algorithm.html. My code to work with in Python: implement numpy for closer view at C/C++:

It is True that when you perform shifting element, it is always in linear way. However, even in the worse case, you re-defined the data at the remaining array without making any shifting but rather losing your time. Note that I want to clarify REAL-TIME Complexity; not Time Complexity in general to be more specific

Denote index at the outer is 'i'. Denote index from searching is 'j'

* If performing Linear Search for index && Full-scale Shifting (to the end): O(2N), which resulting O(2N^2) time complexity
* If performing Binary Search for index && Full-scale Shifting (Re-writing the array: O(N + log2(N)), which resulting O(N^2 + N\*logN) time complexity
* If performing Binary Search for index && One-sided Shifting (to the end): O(N + log2(N)), which resulting O(N^2/2 + N\*logN) time complexity
* If performing Binary Search for Index && Mid-bounded Shifting (to the "i" instead array.length). Time complexity in the worst case can be defined as follow:

* Binary Search: log2(N) : easy to determine
* However, in case of partially-shifting: Time complexity is O(k). Since you only shifting "i-j-1" variables by one move and re-adding the key-point "1". For relatively large array, in average case the number of shifting when k towards the left-half of the sorted one is equal to the right-helf of the sorted one. Thus causing O(i-j) = O(i//2) of time complexity. It can be viewed as using pivot in selection sort or quicksort or timsort.

Thus the overall time complexity for one epoch is log2(N) + i-j ~ log2(N) + i/2 Since this time, it can only be run up to N/2.

=\> Time complexity for the whole array, in best case, O(N), near-asymtomtic case / small array is O(NlogN) and in average case, would be O(NlogN + N^2/4). If lucky enough, it could be O(NlogN + N^2/16) For best case and average case, it would be O(N) and O(2Nlog(N))

Take:

```
import numpy as np
import pandas as pd
from time import time
from typing import List

class Sorting:
    def __init__(self, data_size: int, lower_bound: int = 0, higher_bound: int = 1000):
        if lower_bound > higher_bound:
            lower_bound, higher_bound = higher_bound, lower_bound

        if data_size <= 0:
            self.__data__: np.ndarray = None
        else:
            using = max(abs(lower_bound), abs(higher_bound))
            if lower_bound == 0 and higher_bound > 0:
                x = [2 ** 8 - 1, 2 ** 16 - 1, 2 ** 32 - 1, 2 ** 64 - 1]
                dtype = [np.uint8, np.uint16, np.uint32, np.uint64]
            else:
                x = [2 ** 7 - 1, 2 ** 15 - 1, 2 ** 31 - 1, 2 ** 63 - 1]
                dtype = [np.int8, np.int16, np.int32, np.int64]

            for i in range(len(x)):
                if using <= x[i]:
                    self.__data__ = np.random.randint(low=lower_bound, high=higher_bound,
                                                      dtype=dtype[i], size=data_size)
                    break

        self.data_size: int = data_size
        self.lower_bound: int = lower_bound
        self.higher_bound: int = higher_bound

        self.columns: List[str] = ["Bubble Sort", "Selection Sort", "Insertion Sort (Min-Max)",
                                   "Insertion Sort (Max-Min)", "Binary Insertion Sort"]
        self.recording_time: List[float] = [[0] * len(self.columns)]
        self.array_size = [data_size]

    def reset_data(self, data_size: int, lower_bound: int = 0, higher_bound: int = 1000):
        # Avoid Memory Leakage
        del self.__data__
        if lower_bound > higher_bound:
            lower_bound, higher_bound = higher_bound, lower_bound

        using = max(abs(lower_bound), abs(higher_bound))
        if lower_bound == 0 and higher_bound > 0:
            x = [2 ** 8 - 1, 2 ** 16 - 1, 2 ** 32 - 1, 2 ** 64 - 1]
            dtype = [np.uint8, np.uint16, np.uint32, np.uint64]
        else:
            x = [2 ** 7 - 1, 2 ** 15 - 1, 2 ** 31 - 1, 2 ** 63 - 1]
            dtype = [np.int8, np.int16, np.int32, np.int64]
        for i in range(len(x)):
            if using <= x[i]:
                self.__data__ = np.random.randint(low=lower_bound, high=higher_bound,
                                                  dtype=dtype[i], size=data_size)
                break

        self.data_size: int = data_size
        self.lower_bound: int = lower_bound
        self.higher_bound: int = higher_bound

        self.array_size.append(data_size)
        self.recording_time.append([0] * len(self.columns))

    def get_array(self):
        return self.__data__

    def sort_array(self):
        self.__data__.sort()

    def reverse_array(self):
        self.__data__ = np.flip(self.__data__)

    def BubbleSort(self, reverse: bool = False, copy: bool = True):
        """
        This method do bubble sort. Time complexity: O(N^2) since there are two loops over loops
        Real Time complexity: N*(N-1)/2
        :param copy: bool
        :param reverse: bool
        :return:
        """
        start = time()
        if copy is True:
            copied_version = np.copy(self.__data__)
        else:
            copied_version = self.__data__

        if reverse is False:
            for i in range(0, copied_version.size):
                swapped = False
                for j in range(len(copied_version) - 1, i, -1):
                    if copied_version[j - 1] > copied_version[j]:
                        copied_version[j - 1], copied_version[j], swapped = copied_version[j], copied_version[j - 1], True
                if swapped is False:
                    break

        else:
            for i in range(0, copied_version.size):
                swapped = False
                for j in range(len(copied_version) - 1, i, -1):
                    if copied_version[j - 1] < copied_version[j]:
                        copied_version[j - 1], copied_version[j], swapped = \
                            copied_version[j], copied_version[j - 1], True
                if swapped is False:
                    break

        end = time()

        self.recording_time[self.array_size.index(self.data_size)][0] = end - start
        print("Bubble Sort: Executing Time: {:.6f}s".format(end - start))
        return copied_version, end - start

    def SelectionSort(self, reverse: bool = False, copy: bool = True):
        """
        This method do selection sort. Time complexity: O(N^2) since the first loop to iterate over the array.
        The second loop at "argmin" method which only return the first index that is smallest
        :param copy: bool
        :param reverse: bool
        :return:
        """

        start = time()
        if copy is True:
            copied_version = np.copy(self.__data__)
        else:
            copied_version = self.__data__

        if reverse is False:
            for index in range(0, copied_version.size):
                if index + 1 == copied_version.size:
                    break
                minimum_index = index + 1 + copied_version[index + 1:].argmin(axis=-1)
                copied_version[index], copied_version[minimum_index] = \
                    copied_version[minimum_index], copied_version[index]
        else:
            for index in range(0, copied_version.size):
                if index + 1 == copied_version.size:
                    break
                minimum_index = index + 1 + copied_version[index + 1:].argmin(axis=-1)
                copied_version[index], copied_version[minimum_index] = \
                    copied_version[minimum_index], copied_version[index]
        end = time()

        self.recording_time[self.array_size.index(self.data_size)][1] = end - start
        print("Selection Sort: Executing Time: {:.6f}s".format(end - start))
        return copied_version, end - start

    def __BinarySearch__(self, array, number, start, end, reverse: bool = False):
        """
        This method will determine the accurate position to help sorting the array.
        Embedding with InsertionSort
        """
        if reverse is False:
            if start == end:
                if array[start] > number:
                    return start
                else:
                    return start + 1
        else:
            if start == end:
                if array[start] < number:
                    return start
                else:
                    return start + 1

        if start > end: # Ensuring position can be found
            return start

        mid = (start + end) // 2
        if reverse is False:
            if array[mid] < number:
                return self.__BinarySearch__(array=array, number=number, start=mid + 1, end=end, reverse=reverse)
            elif array[mid] > number:
                return self.__BinarySearch__(array=array, number=number, start=start, end=mid - 1, reverse=reverse)
            else:
                return mid
        else:
            if array[mid] > number:
                return self.__BinarySearch__(array=array, number=number, start=mid + 1, end=end, reverse=reverse)
            elif array[mid] < number:
                return self.__BinarySearch__(array=array, number=number, start=start, end=mid - 1, reverse=reverse)
            else:
                return mid

    def InsertionSort(self, reverse: bool = False, copy: bool = True, perform_type: str = "binary"):
        """
        This method do insertion sort. Time complexity: O(N^2) since the first loop to iterate over the array.
        The second will have to pass the array to have the right order which thus getting O(k) complexity.
        Since k is iterate along with N, Real-time complexity is O(N^2)
        The second loop at "argmin" method which only return the first index that is smallest got O(N) complexity

        You can try binary insertion sort: it can help faster in sorting and lower down a little bit of time
        but general time complexity is remained. Time complexity in average case equal to O(N^2)
        """

        start = time()
        if copy is True:
            copied_version = np.copy(self.__data__)
        else:
            copied_version = self.__data__
        if perform_type.lower() == "left-right":
            left_to_right, right_to_left, binary = True, False, False

        elif perform_type.lower() == "right-left":
            left_to_right, right_to_left, binary = False, True, False

        elif perform_type.lower() == "binary":
            left_to_right, right_to_left, binary = False, False, True

        else:
            raise ValueError("Unable to found valid number")

        if reverse is False and left_to_right is True:
            for index in range(1, copied_version.size):
                key_point = np.copy(copied_version[index])
                if copied_version[index - 1] < key_point:
                    continue
                for i in range(0, index):
                    if i == 0:
                        if key_point < copied_version[i]:
                            copied_version[i + 1:index + 1] = copied_version[i:index]
                            copied_version[i] = key_point
                            break
                    else:
                        if copied_version[i - 1] <= key_point <= copied_version[i]:
                            copied_version[i + 1:index + 1] = copied_version[i:index]
                            copied_version[i] = key_point
                            break

        elif reverse is False and right_to_left is True:
            for index in range(1, copied_version.size):
                key_point = np.copy(copied_version[index])
                if copied_version[index - 1] < key_point:
                    continue
                i = index - 1
                while i >= 0 and key_point < copied_version[i]:
                    copied_version[i + 1] = copied_version[i]
                    i -= 1
                copied_version[i + 1] = key_point

        elif reverse is True and left_to_right is True:
            for index in range(1, copied_version.size):
                key_point = np.copy(copied_version[index])
                if copied_version[index - 1] > key_point:
                    continue
                for i in range(0, index):
                    if i == 0:
                        if key_point > copied_version[i]:
                            copied_version[i + 1:index + 1] = copied_version[i:index]
                            copied_version[i] = key_point
                            break
                    else:
                        if copied_version[i - 1] >= key_point >= copied_version[i]:
                            copied_version[i + 1:index + 1] = copied_version[i:index]
                            copied_version[i] = key_point
                            break

        elif reverse is True and right_to_left is True:
            for index in range(1, copied_version.size):
                key_point = np.copy(copied_version[index])
                if copied_version[index - 1] > key_point:
                    continue
                i = index - 1
                while i >= 0 and key_point > copied_version[i]:
                    copied_version[i + 1] = copied_version[i]
                    i -= 1
                copied_version[i + 1] = key_point
        else:
            for index in range(1, copied_version.size):
                key_point = np.copy(copied_version[index])
                if reverse is True and copied_version[index - 1] > key_point:
                    continue
                elif reverse is False and copied_version[index - 1] < key_point:
                    continue
                i = self.__BinarySearch__(array=copied_version, number=key_point, start=0, end=index - 1,
                                          reverse=reverse)
                copied_version[i + 1:index + 1] = copied_version[i:index]
                copied_version[i] = key_point
        end = time()
        if left_to_right is True:
            self.recording_time[self.array_size.index(self.data_size)][2] = end - start
        if right_to_left is True:
            self.recording_time[self.array_size.index(self.data_size)][3] = end - start
        if binary is True:
            self.recording_time[self.array_size.index(self.data_size)][4] = end - start
        print("Insertion Sort: Executing Time: {:.6f}s".format(end - start))
        return copied_version, end - start

    def get_time(self, output: str = None):
        file = pd.DataFrame(data=self.recording_time, index=self.array_size, columns=self.columns)
        if output is not None:
            file.to_csv(path_or_buf=output)
        return file

    def automate(self, size: List[int], lower_bound: int = 0, higher_bound: int = 1000, reverse: bool = False,
                 insert_type: str = 'binary', bubble_sort: bool = True, selection_sort: bool = True,
                 insertion_sort: bool = True, output: str = None):
        for index, value in enumerate(size):
            print("Matrix Size:", value)
            self.reset_data(data_size=value, lower_bound=lower_bound, higher_bound=higher_bound)
            # print(self.get_array())
            if bubble_sort is True:
                self.BubbleSort(reverse=reverse)
            if selection_sort is True:
                self.SelectionSort(reverse=reverse)
            if insertion_sort is True:
                self.InsertionSort(reverse=reverse, perform_type=insert_type)
        self.get_time(output=output)

```

My final word is optimize your code to lower down your REAL-TIME complexity rather make full attention on time complexity to think of.

**\[EDIT\]**: Real-Time complexity I will try to clarify this according to time-complexity in descending order:

* Linear Search + Array Rewriting:

Worst Case = Average Case: O(N) * O(N + N) = O(2N^2) (contained some "if" to get best case O(N))

* Linear Search + Element-Swapping:

Average Case: O(N) * O(N + N) = O(2N^2) (contained some "if" to get best case O(N))

Worst Case: could be O(N^3+N^2)

* Linear Search + Half-Right Swapping:

Worst Case: O(N) * O(N + N/2) = O(3/2 * N^2) (inversely-linear order, obtained by averaging left to right)

* Linear Search + Pivot ("j"-index) \<--\> Key ("i"-index) Swapping:

Worst Case: O(N) * O(N + N/4) = O(5/4 * N^2) (inversely-linear order:, obtained by averaging left to right)

Average Case: O(N) * O(N + N/16) = O(16/15 * N^2) (inversely-linear order, obtained by averaging left to right)

* Binary Search + Array Rewriting:

Worst Case = Average Case: O(N) * O(log2(N) + N) = O(N^2 + Nlog2(N)) (contained some "if" to get best case O(N))

* Binary Search + Element Swapping:

Average Case: O(N) * O(log2(N) + N) = O(N^2 + Nlog2(N)) (contained some "if" to get best case O(N))

Worst Case: O(N^3 + Nlog2(N))

* Binary Search + Half-Right Swapping:

Worst Case = Average Case: O(N) * O(log2N + N/2) = O(1/2 * N^2 + Nlog2(N)) (inversely-linear order, obtained by averaging left to right)

* Binary Search + Pivot ("j"-index) \<--\> Key ("i"-index) Swapping:

Worst Case: O(N) * O(log2(N) + N/4) = O(1/4 * N^2 + Nlog2(N)) (inversely-linear order:, obtained by averaging left to right)

Average Case: O(N) * O(log2(N) + N/16) = O(1/16 * N^2 + Nlog2(N)) (inversely-linear order:, obtained by averaging left to right)

Lucky Case: O(2Nlog2(N))

---
Tags: algorithms, time-complexity, sorting, binary-search
---


title: Reduction from $VC$ to $CD$

text:
# Question
Title: Reduction from $VC$ to $CD$
We define the vertex cover as the problem of finding for a graph $G$, a cover of size $k$. A cover is a set of vertices such that every vertex has an edge to this set. We define CD (cycles destructor), as the set of vertices with the size $k$, whose removal will lead to a cycle-free graph. Show a reduction from VC to CD. In other words, prove that CD is $\mathsf{NP}$-hard.

# Answer
> 0 votes
The identity reduction: for any graph G, if there is a VC V, then for any cycle a $\exists .v \in V$. therefore, for any cycle, removal of one vertex will break the cycle. Now you look for a set of size k that will fit to this definition. Therefore V is a cycle destructor. Side note, there can be a subset of V which will be also a vertex destructor, or even a set that has a vertex that it is not in any vertex cover.

---
Tags: graphs, np-complete, reductions, np, vertex-cover
---


# Question
Title: Job Shop Problem: How do you get an ordered sequence of operations from the disjunctive acyclic graph?
### Intro

The job shop problem is a classic scheduling theory problem. Given $N$ jobs and $M$ machines, a typical goal of the JSP is to minimise the *makespan* (starting time of the last operation + its processing time) over the set of jobs. Jobs must be processed on a sequence of machines in a particular order. An operation refers to a particular job being processed on a particular machine.

---

### Representation

A disjunctive graph is typically used to represent the problem of minimising makespan. Each **node** in the graph is labelled $(i,j)$ where $i$ refers to the job, and $j$ to the machine on which the job is to be run. *Conjunctive* arrows between nodes indicate precedence constraints for a particular job. Each conjunctive edge is given a weight, corresponding to the processing time $P\_{i}$ for the particular operation $O\_{i}$ at the *base* of the edge. *Disjunctive* edges are placed between operations that take place *on the same machine*. An example of two simple jobs is given below:

Note that $J\_{1}$ is comprised of the upper row of nodes, and $J\_{2}$ the lower row.

---

### Problem

My problem is with the terminology used to describe how to solve the JSP. The book "Scheduling Theory, Algorithms, and Systems" (Pinedo, 2008) states on page 181 that:

> A feasible schedule corresponds to a *selection* of one disjunctive arc from each pair such that the resulting directed graph is acyclic

However, if I do just that, I can derive a graph that looks something like this:

Now, it is said that:

> The makespan of a feasible schedule is determined by the longest path in G(D) from the source U to the sink V

And if I sum the longest *weighted* path, I can indeed derive a "makespan" value. However, I still don't get why this is a "feasible schedule". Because I don't really have a schedule at all. The path doesn't give me an ordering for how to execute the callbacks. That is because the path necessarily does not visit every operation. Meaning that it does not give a feasible schedule at all.

### Verdict

In light of what I have described above, my question is: **How can I derive the full sequence of operations to perform from the disjunctive graph model of the job shop problem?**

**Edit**: There's a mistake in my graph, the last edges going to $V$ should be labelled with a weight.

# Answer
> 1 votes
The graph consisting of all vertices corresponding to a particular machine and the induced chosen edges form a directed path. This path tells you exactly which jobs to run on that machine and in what order.

The length of the longest weighted path from u to a job tells you exactly when you can start processing that job.

---
Tags: graphs, weighted-graphs, scheduling
---


# Question
Title: Prove a statement about searching in binary search tree
Suppose search $n$ times in a given binary search tree $T$ with $n$ nodes. each searching have cost $C\_i$, and $\sum\_{i=1}^{n}C\_i=O(n\log n)$. Now the problem is to find height of $T$. I think it be $O(\sqrt{n\log n})$, but after reading this post, what is correct proof to get that result?

# Answer
Let $h$ be longest path from root $T$ to leaves. We must read $h+1$ nodes. So searching for root of $T$ we have cost $1$, for child of root we have cost $2$ , and etc. it's sufficient to sum over cost at each nodes on $h$. As a result we have

\begin{gather\*} 1+2+3...+h=O(h^2). \end{gather\*}

Now as mentioned in question, $O(h^2)$ must be $O(n\log n)$. More formally, $O(h^2)=O(n\log n)$ that we can conclude that $h=O(\sqrt{n\log n})$.

For example consider a binary search tree with $n$ nodes such that root have sub tree with height $\sqrt{n\log n}$, and right sub tree of root have height $\log (n-\sqrt{n\log n}).$
> 1 votes

---
Tags: binary-search-trees
---


title: Addressing mode in 8086

text:
# Question
Title: Addressing mode in 8086
I'm a beginner learning about Assembly language and I was doing questions where I have to identify different addressing mode in 8086 processor.

One such instruction is: **mov ah,09h**

Here the source operand has immediate address mode and destination operand has Register address mode. In many tutorials online they have just mentioned that the instruction has only Immediate addressing mode, I don't understand why these tutorials do not mentioned about the destination addressing mode. Shouldn't the answer be both immediate and register addressing mode for the given instruction.

I know it is a very simple question but every other explanation on the internet is making me more confused. I would really like to know if my reasoning is correct.

# Answer
Well, x86 hasn't the simplest instruction format... And similar addressing modes can be named differently for different CPUs.

In most CPUs (particularly RISCs and simple 8bits CPUs), there is only zero or one memory operation for data, so each instruction can be binned in one addressing mode or another.

For CISC CPUs it can be a bit more complex, for example x86 supports writing an immediate value to memory without going through a register.

Intel manuals don't really name the addressing mode for each instruction, because it's too complex, there are instead acronyms to describe operands such as imm8,imm16,r/m8,r/m16...

So your "MOV AH,0x09h" is probably "immediate" addressing, Intel describes it as "MOV r8,imm8" : 8bit register as destination to 8bit immediate.
> 2 votes

---
Tags: assembly
---


# Question
Title: Prove that in a tree where each node has 0 or 2 children, number of nodes with 0 child is one more than the number of nodes with 2 children
How to prove

In a tree where every node has either $0$ or $2$ children, the number of nodes with $0$ child is $1$ more than the number of nodes with $2$ children.

# Answer
This can be proven by induction. What you describe is a Full binary tree, and it has a convenient induction definition:

* a single node (or leaf) is a full binary tree;
* a tree with two children that are full binary trees is a full binary tree.

This permits a structural induction proof of the property you want:

* prove that it is true for a single node tree;
* suppose that it is true for two full binary trees $a$, $b$, then prove that it is true for the node $N(a, b)$ with $a$ and $b$ as children.
> 3 votes

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


title: Find successor element in heap

text:
# Question
Title: Find successor element in heap
Does finding the successor of an element in a heap take $O(\log n)$?

An heap is not a binary search tree, so couldn't an element's successor be found in $O(n)$ time?

# Answer
Suppose you have a min heap $H$, and you want to find successor one of the leaf node that its successor is maximum value, so you need to scan all leaves in tree, in addition we know that number of leaves in $H$ is $O(n)$. So you need read $O(n)$ nodes.
> 0 votes

---
Tags: trees
---


# Question
Title: Understanding lemma found in proof of quotient construction for DFAs
> Lemma 13.6 $p \in F \Longleftrightarrow \[p\] \in F'$
>
> *Proof.* The direction $\Rightarrow$ is immediate from the definition of $F'$. For the direction $\Leftarrow$, we need to show that if $p \approx q$ and $p \in F$, then $q \in F$. In other words, every $\approx$-equivalence class is either a subset of $F$ or disjoint from $F$. This follows immediately by taking $x = \epsilon$ in the definition of $p \approx q$. $\quad\square$

The excerpt above found in Dexter C. Kozen's Automata and Computability. This lemma is found in a proof of the Quotient Construction for DFA.

I do not understand how the author concludes that if one wants to show $\[p\] \in F' \implies p \in F$ (1), then it is equivalent to showing that $p≈q$ and $p \in F \implies q \in F$ (2). Can someone please provide as detailed as possible an explanation of why if we want to show (1) it is equivalent to show (2)? Any idea on why the author does not feel the need to justify this?

# Answer
Let us start with explaining the notation:

* $F$ is the set of accepting states of some DFA.
* We define an equivalence relation $\approx$ on the states of the DFA as follows: $p \approx q$ if for all words $x$, $\hat\delta(p,x) \in F$ iff $\hat\delta(q,x)$, where $\hat\delta$ is the transition function of the DFA (extended from symbols to words).
* We denote the equivalence class of a state $p$ by $\[p\]$.
* $F' = \\{ \[p\] : p \in F \\}$.

Now suppose that $\[p\] \in F'$. According to the definition of $F'$, $\[p\] = \[q\]$ for some $q \in F$. Standard properties of equivalence relations imply that $\[p\] = \[q\]$ iff $p \approx q$. By definition of $\approx$, $\hat\delta(p,x) \in F$ iff $\hat\delta(q,x) \in F$ for all words $x$. Taking $x = \epsilon$, we see that $p = \hat\delta(p,\epsilon) \in F$ iff $q = \hat\delta(q,\epsilon) \in F$. Since $q \in F$, this shows that indeed $p \in F$.
> 1 votes

---
Tags: finite-automata
---


# Question
Title: Words which, cyclically shifted twice, equal their reverse
> Let the alphabet be $Σ = \\{0, 1\\}$. For any string $w ∈ Σ^\*$ of length at least 2, define the operation $C\_2(w)$ to be a cyclic shift of size 2 on $w$. That is, if $w = w\_1w\_2 \cdots w\_n$ with $n ≥ 2$ and each $w\_i ∈ Σ$, then $C\_2(w) = w\_3 \cdots w\_nw\_1w\_2$ if n ≥ 3, and $C\_2(w) = w$ if $n = 2$. Recall that $w^R$ means $w$ written backwards.

> Give a context-free grammar that generates the following language: $$ \\{w \mid w \text{ has length at least 2 and } C\_2(w) = w^R\\}. $$

I'm having trouble constructing the context free grammar, so any tips would be much appreciated!

# Answer
> 2 votes
Let us see which words satisfy $C\_2(w) = w^R$. Write $w = \sigma \tau x$, where $\sigma,\tau \in \Sigma$ and $x \in \Sigma^\*$. Then $C\_2(w) = x \sigma \tau$ and $w^R = x^R \tau \sigma$, and so $C\_2(w) = w^R$ iff $x = x^R$ and $\sigma = \tau$.

You should be able to use this information in order to construct a grammar for your language.

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


title: Special case of subset sum in $O(n)$

text:
# Question
Title: Special case of subset sum in $O(n)$
A sorted array $A\[1..n\]$ is given. Each element of $A\[i\]\in \mathbb{N}$, and for each $A\[i\],A\[j\]$ we have $A\[i\]+A\[j\]\leq n$. Find two elements $A\[i\], A\[j\]$ such that $(A\[i\]-i)+(A\[j\]-j)=0$. Give a deterministic $O(n)$ time algorithm for this problem.

I tackle with this problem as follow :

Calculate each $A\[i\]-i$ , and insert it into hash table $T$ that take $O(n)$ , then one time traverse $A$ such that to find and element that $A\[i\]-i=T\[i\]$. Each search take $O(1)$ in expected, but we must give a deterministic in $O(n)$.

# Answer
The assumptions $A\[i\] \in \mathbb N$ and $A\[i\] + A\[j\] \leq n$ together imply that $0 \leq A\[i\] \leq n$, and so $-n \leq A\[i\]-i \leq n$. This suggests maintaining an array $B\[-n\],\ldots,B\[n\]$, initialized with zeroes. We go over the elements of $A$ one by one. We put $B\[A\[i\]-i\] = i$, and then check whether $B\[i-A\[i\]\]$ is non-zero, say equal to $j$. If so, then $i-A\[i\] = A\[j\] - j$, and so $A\[i\] - i + A\[j\] - j = 0$. (This allows $i = j$; if you want to disallow it, reverse the order of these two steps.)
> 2 votes

# Answer
You can do it in $O(n)$ time and $O(1)$ auxiliary space assuming a model where the integers are stored as $w$-bit integers where $w \> 2$, and we can modify the input array (non-destructively).

---

First, we're going to steal two bits of storage space per element from our array.

In one linear scan find the index $l$ such that the most significant bit of $A\[l-1\]$ is 0 and the MSB of $A\[l\]$ is 1. This position is unique because the array is sorted. Save $l$ and clear all the top bits. Note that you can still retrieve the original values, by computing $A\[i\] + 2^{(w-1)\[i \geq l\]}$.

Now apply the same process for both subarrays $A\[1..l-1\]$ and $A\[l..n\]$, but this time stealing the *second* most significant bit. The end result is that the top two most significant bits of each element are zero, but we store three indices (where the top two bits transition from $00$ to $01$, $01$ to $10$, and $10$ to $11$) that allows us to recover the original data, when ignoring the top two bits.

---

From this point on I assume that $A\[i\]$ refers to the original values, but also that we have 2 bits of storage for each element, using the above technique, which I'll call $P\[i\]$ and $N\[i\]$. We initialized $P\[i\] = N\[i\] = 0$.

As Yuval Filmus notes because we have $A\[i\] \in \mathbb{N}$ and $A\[i\] + A\[j\] \leq n$ we can assume $0 \leq A\[i\] \leq n$ and thus $-n \leq A\[i\] - i \leq n$.

Initialize $z = 0$. Loop over $1 \leq i \leq n$ and compute $x = A\[i\] - i$:

1. If $x = 0$, if $z \> 0$ return $(z, i)$. Otherwise store the index $z = i$.
2. If $x \> 0$, check if $N\[x\] = 1$, if yes do a linear scan to find the earlier value $A\[j\] = -x$ (it must exist) and return $(j, i)$, otherwise set $P\[x\] = 1$.
3. If $x \< 0$, check if $P\[-x\] = 1$, if yes do a linear scan to find the earlier value $A\[j\] = -x$ (it must exist) and return $(j, i)$, otherwise set $N\[-x\] = 1$.

If we reach $i = n$ and we didn't return a value, no solution exists.

---

If necessary we can restore the input array to the original state after finding the value above.
> 2 votes

---
Tags: algorithms, data-structures
---


title: Constructing 2-Universal Families

text:
# Question
Title: Constructing 2-Universal Families
Let H be a class of all functions, mapping M possible keys to N integers. Is it true that H is a 2-universal family? Is it a good idea to use H in applications?

I don't even know where and how to start. Can you give me a hint on how to prove this? Is it even possible to prove this?

# Answer
> Can you give me a hint on how to prove this?

Let $H$ be a class of all functions which map universe $Z\_n$ to $Z\_m$. We will assume that, any particular mapping is done by exactly one of the functions in the class.

Total functions in $H$ = number of all possible mappings = $m^n$

Given any distinct keys $x$ and $y$, we need to find number of all possible functions (mappings) in which they collide. The remaining $n-2$ keys have total mappings: $m^{n-2}$. The $(x,y)$ pair can collide by mapping to any of the $m$ slots. So,

Total functions in $H$ where $(x,y)$ collide = $m^{n-2}\cdot m = m^{n-1}$

Thus probability of collision = $m^{n-1} / m^n = 1/m$.
> 1 votes

---
Tags: algorithms, hash
---


# Question
Title: Solving number of distinct elements in $O(\frac{n\ell}{p})$ space complexity with $2p$ passes over data
Suppose there is an n-element stream with elements from $\\{0,1\\}^\ell$ which means each element is in set $\\{0, \dots , 2^\ell-1\\}$. Also may assume $2^\ell \>n^2$. How can I with $2p$ passes over the data (for $p \in \\{1, \dots , 2^\ell\\} $) solve the *number of distinct elements* problem using only $O(\frac{n}{p}\ell)$ bits of memory? Not looking for probabilistic algorithms.

# Answer
> 1 votes
Try something along the following lines. Preform $p$ iterations where each iteration consists of two passes over the stream. The $i$'th iteration first pass remembers all elements whose index $\bmod p$ equals $i$ , denote this collection by $S\_i$. The second pass, for each element of the stream whose index $\bmod p$ is greater than $i$, checks if it appears in $S\_i$, and if so deletes it. Denote by $S\_i'$ the remaining subset after the second pass, then your algorithm returns $\sum\limits\_{i=1}^p |S\_i'|$.

---
Tags: space-complexity, streaming-algorithm, big-data
---


title: $coNP$ and $\oplus P$?

text:
# Question
Title: $coNP$ and $\oplus P$?
Let a non-deterministic machine have at most $2^{t+1}-1$ accepting paths (highest significant bit position is $t$ and lowest significant bit position is $1$).

I want to decide if the number of accepting paths $N\_{accept}$ is $0$ or $\>0$.

I can ask a $\oplus P$ oracle to decide if $2^t|N\_{accept}$ and $2^{t+1}|N\_{accept}$ as $MOD\_{2^m}P=MOD\_2P$ by https://complexityzoo.net/Complexity\_Zoo:M#modkp.

There are three different scenarios

1. $2^t|N\_{accept}$ and $2^{t+1}|N\_{accept}$ in which case $N\_{accept}=0$.
2. $2^t|N\_{accept}$ and $2^{t+1}\nmid N\_{accept}$ in which case $N\_{accept}=2^t$.
3. $2^t\nmid N\_{accept}$ and $2^{t+1}\nmid N\_{accept}$ in which case $1\leq N\_{accept}\leq2^t-1$.

So $N\_{accept}=0\iff\oplus P$ oracle accepts twice.

Why would the above not place $coNP$ in $\oplus P$ or at least $NP^{\oplus P}$?

# Answer
> 0 votes
The result that $\mathrm{MOD}\_{2^m}\mathrm P=\mathrm{MOD}\_2\mathrm P$ only applies when $m$ is *constant*. Thus, your strategy only works if $t$ is constant, which is a trivial case. You would need it to apply to $t\approx n^c$. (Actually, the argument works for $m=O(\log n)$, but this is still not enough.)

Specifically, the reduction of $\mathrm{MOD}\_{2^m}\mathrm P$ to $\mathrm{MOD}\_2\mathrm P$ relies on the simple number-theoretic fact that $$2^m\mid s\iff2\mid s\land2\mid\binom s2\land2\mid\binom s{2^2}\land\dots\land2\mid\binom s{2^{m-1}}.$$ If $s$ counts the number of objects satisfying some property, then $\binom s{2^r}$ counts the number of $2^r$-element *sets* of objects with that property.

That is, given a language $L\in\mathrm{MOD}\_{2^m}\mathrm P$ of the form $$w\in L\iff2^m\mid\\#\\{x\<2^{n^c}:R(w,x)\\},$$ where $n$ denotes $|w|$ and $R\in\mathrm P$, we can express $L$ as $$w\in L\iff\forall r\<m\ 2\mid\\#\\{(x\_0,\dots,x\_{2^r-1})\in\[0,2^{n^c})^{2^r}:R\_r(w,x\_0,\dots,x\_{2^r-1})\\},$$ where $$R\_r(w,x\_0,\dots,x\_{2^r-1})\iff x\_0\<\dots\<x\_{2^r-1}\land\forall i\<2^r\\:R(w,x\_i).$$ (These $m$ instances of $\oplus\mathrm P$ can be then combined to a single $\oplus\mathrm P$ predicate as $\oplus\mathrm P$ is closed under poly-time Turing reductions; in fact, even $\mathrm{\oplus P^{\oplus P}=\oplus P}$.)

As long as $m=O(\log n)$, the sequences $(x\_0,\dots,x\_{2^r-1})$ can be represented with $n^{O(1)}$ bits, and the predicates $R\_r$ are computable polynomial time, but neither is true for larger $m$.

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Checking validity of formulas in first-order logic
*Given four formulas in first order logic. Which of the following formulas are* not *valid? (In logic a proposition is valid if it never evaluates to $\bot$.)*

1. $(\exists x P(x)\to Q)\to (\forall x (P(x)\to Q))$
2. $((\neg P\to Q)\wedge(P\to R))\to (\neg P\to R)$
3. $(\exists x(P(x)\to Q(x)))\leftrightarrow (\forall x P(x)\to\exists x P(x))$
4. $(\forall xP(x)\to Q)\to (\forall x (P(x)\to Q))$

According to proof by negation, for example if we negate formula in $1$ then we get $\bot$, as a result this shows that $1$ is valid. Instructor said only $4$ is not valid, but I think both $2$ and $4$ are not valid according to proof by negation.

# Answer
> 0 votes
First of all, the following heuristic comes from this post

> Heuristic: To try to determine whether $\phi$ is valid: If the answer's not obvious, look for an interpretation where $\phi$ is false.

So try to proof by negation. Consider $1:$

Let \begin{gather\*} \phi\equiv(\exists xP(x)\to Q )\to(\forall x(P(x)\to Q)). \end{gather\*}

Now negate $\phi$ then we have: \begin{gather\*} \neg\phi\equiv \neg(\neg(\exists xP(x)\to Q )\vee(\forall x(P(x)\to Q)))\equiv (\exists xP(x)\to Q )\wedge \neg(\forall x(P(x)\to Q))\equiv (\forall x\neg P(x)\vee Q )\wedge (\exists x(P(x) \wedge \neg Q)) \end{gather\*}

so after elimination of quantifiers:

\begin{gather\*} \neg P(x)\vee Q \end{gather\*} \begin{gather\*} P(C\_1) \end{gather\*} \begin{gather\*} \neg Q \end{gather\*}

oblivious that if we use resolution, and resolve each clause we achieve $\bot$.

As a result we can say $1$ is valid.

$2$ is not valid, you can use above method or if we set

\begin{gather\*} Q\equiv \top \end{gather\*} \begin{gather\*} P\equiv R\equiv \bot \end{gather\*}

as a result $2$ is $\bot$.

Repeat idea that used in $1$ for $3$:(as you know from logic, $A\leftrightarrow B\equiv (A\to B) \wedge (B\to A)$) so we have:

\begin{gather\*} \neg(((\exists x(P(x)\to Q(x)) \to (\forall xP(x)\to \exists xP(x))) \end{gather\*} \begin{gather\*} \wedge \end{gather\*} \begin{gather\*} (\forall xP(x)\to \exists xP(x)) \to ((\exists x(P(x)\to Q(x)) )) \end{gather\*}

After applying negation: \begin{gather\*} \equiv \end{gather\*}

\begin{gather\*} (((\exists x(\neg P(x)\vee Q(x)) \wedge (\forall xP(x)\wedge \forall x\neg P(x))) \end{gather\*} \begin{gather\*} \vee \end{gather\*} \begin{gather\*} (\exists x\neg P(x)\vee \exists xP(x)) \wedge ((\forall x(P(x)\wedge \neg Q(x)) )) \end{gather\*} Eliminate quantifiers:

\begin{gather\*} (\neg P(C\_1)\vee Q(C\_1)) \wedge (P(x)\wedge\neg P(x)) \end{gather\*} \begin{gather\*} \vee \end{gather\*} \begin{gather\*} (\neg P(C\_2)\vee P(C\_3)) \wedge (P(x)\wedge \neg Q(x) )) \end{gather\*} As you know

\begin{gather\*} (\neg P(C\_1)\vee Q(C\_1)) \wedge (P(x)\wedge\neg P(x))\equiv \bot \end{gather\*}

So we have:

\begin{gather\*} \bot \end{gather\*} \begin{gather\*} \vee \end{gather\*} \begin{gather\*} (\neg P(C\_2)\vee P(C\_3)) \wedge (P(x)\wedge \neg Q(x) )) \end{gather\*}

\begin{gather\*} \equiv \end{gather\*} \begin{gather\*} (\neg P(C\_2)\vee P(C\_3)) \wedge (P(x)\wedge \neg Q(x) )) \end{gather\*} As a result above formula can't equal to $\top$ because we can't resolve some clauses to get $\bot$. So $3$ isn't valid.

$4$ remain as exercise, if you follow described approach for other options, you can see $4$ is not valid.

---
Tags: logic
---


title: Is a zero matrix nilpotent matrix?

text:
# Question
Title: Is a zero matrix nilpotent matrix?
Let a matrix $A=0$. Can I say $A$ is nilpotent? I am asking if the zero matrix is nilpotent or not. Nilpotent means that $A^k = 0$ for some $k$ that is a non-negative integer. When $k = 1$, $A^k = A = 0$. Does this idea support that a zero matrix is nilpotent?

# Answer
> 1 votes
Sure, the zero matrix $0$ is nilpotent since any of its powers is again the zero matrix. Just a side note: This question would be more suitable at the math stackexchange.

---
Tags: mathematical-foundations
---


# Question
Title: Clique is NP hard to approximate up to $n^{a}$ for some $a \in (0,1)$
Given that $\mathsf{NP}=\mathsf{PCP}\_{\[\frac{1}{n},1\]}\left(O\left(\log n\right),\left(O(\log n\right)\right)$, show that it is NP-hard to approximate clique up to factor of $n^a$ for some $a \in (0,1)$.

# Answer
The $\delta$-GAP-CLIQUE is the following promise problem:

1. yes instances are pairs $(G,m)$ such that $G$ is a graph the contains an $m$-clique
2. No instances are pairs $(G,m)$ such that all cliques in $G$ are of size $\<\delta m$

Start by observing that the NP hardness of $n^{-\alpha}$-GAP-CLIQUE implies that max clique is $n^{-\alpha}$ hard to approximate. Now suppose that $SAT\in PCP\left(c\_1\log n,c\_2\log n, \delta\right)$. Try finding a reduction from SAT to $n^{-\alpha}$-GAP-CLIQUE, i.e. you want to be able to map satisfiable formulas to graphs with a large clique and non satisfiable formulas to graphs where all cliques are small enough. Let $V$ be a non-adaptive PCP verifier with the above parameters for SAT.

The idea is to assign a vertex to every pair $(s,r)\in\\{0,1\\}^{c\_1\log n}\times\\{0,1\\}^{c\_2\log n}$ such that $V$ accepts $\varphi$ given randomness $r$ and answers $s$ to the queries from the proof. We say $(s,r),(s',r')$ are consistent if there exists no $i\le c\_1\log n$ such that on randomness $r$ and $r'$ the $i'th$ bit from the proof queried by $V$ is the same, and $s\_i\neq s\_i'$. Let $G$ be the graph whose vertices are accepting pairs $(s,r)$ for $\varphi$ and two pairs are connected by an edge if they are consistent. The key observation is that a $k$-clique in $G$ is equivalent to the existence of a proof $\pi$ with at least $k$ different random strings $r$ causing $V$ to accept $(\varphi,\pi)$. I leave it to you to fill in the details, namely to show that $\varphi \mapsto (G,n^{c\_2})$ is a reduction from SAT to $\delta-GAP-CLIQUE$.
> 1 votes

---
Tags: np-hard, approximation, clique
---


# Question
Title: Does any graph based optimization problem, which have a greedy algorithm, has guarantee that there exist an order which give the optimum
There exist greedy algorithms for vertex coloring like optimization problems. We know that for graph coloring, there is an order of vertices for which greedy coloring produces the optimum results. Is it true for any problem on graph which has such a greedy algorithm.

# Answer
> 1 votes
Yes, for every simple graph problem I can think of it's pretty simple to come up with some greedy strategy that gives the optimum if you order your vertices correctly.

Take for example Independent Set. The simplest strategy imaginable for finding an independent set is to fix some ordering $(v\_1,\ldots,v\_n)$ on the vertices of your graph $G$, putting vertex $v\_i$ into your independent set $I$ if it has no neighbors among the vertices that have been put into $I$ so far. This always leads to a maximal independent set, and it's easy to see that every maximal independent set (including those of maximum size) can be generated this way, by just taking an ordering where evey vertex in the set comes before every vertex not in the set.

This strategy also works for other vertex subset problems like Feedback Vertex Set or Dominating Set. Unfortunately, it is pretty uninteresting and unlikely to give much insight into these problems. It's potentially more interesting when such strategies can be devised for more complex problems like Treewidth.

---
Tags: greedy-algorithms
---


# Question
Title: Accurate height of recursion tree for given recursion
We are trying to find height of following recursion formula in terms of $n,k$:

\begin{gather\*} T(n,k)=T(\frac{n}{2},k)+T(n,\frac{k}{4})+nk \end{gather\*}
\begin{gather\*} T(n,1)=T(1,k)=O(1) \end{gather\*}

I read this link , and this post, but i think neither of answers are true.

# Answer
> 0 votes
Look at recursion tree, as you see we go down until we are be in $T(2,k)$ that is equal to decease $n$ $\log n-1$ times to become $n=2$. So that branch have height $\log n-1$ Because we are not in base case then we can continue, but on $k$ we recurse. Because of value $n$ not be changed we can go down until $k=1$ that this branch have height $\log\_4 k$. Now we can say height of $T(n,k)$ is is summation of two branches: \begin{gather\*} O(\log\_2n+\log\_4n) \end{gather\*}

# Answer
> 0 votes
Yes, you are right. Now, this recurrence formula is not all well-formed, but assuming that it really means

> $T(n,k) = T(\lfloor\frac{n}{2}\rfloor,k)+T(n,\lfloor\frac{k}{2}\rfloor) +nk$

, the height of the recursion tree becomes $\lfloor\log\_2(n)\rfloor + \lfloor\log\_2(k)\rfloor - 1$ . The deepest leaves in the tree will then always have one of $n$ and $k$ being 1, and the other being 2 or 3.

---
Tags: recurrence-relation
---


# Question
Title: Time complexity of insertion in binary search tree
Given a binary search tree $T$, we insert $n$ elements, but when the size of tree become doubled then we balance the tree. for example if we insert $2^{k-1}$ element then when the size become to $2^k$ then we balance $T$. what is time complexity insert $n$ items in such tree?

I think be $O(n)$, but when i want draw a such tree i get stuck.

# Answer
It can't be $O(n)$.

Suppose $n=2^k$,and for given $n$ elements, we inserted $\frac{n}{8}$ and $T$ is balanced. Now suppose you insert next $\frac{n}{8}$, But suppose when you inserted $\frac{1}{2}\frac{n}{8}$ elements that those make a chain with length $O(n)$. So for next $\frac{1}{2}\frac{n}{8}$ elements you maybe have cost $O(n)$ for each insertion. As a result the time complexity of $n$ insertion is $O(n^2)$.
> 0 votes

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


title: Randomized Version of NP

text:
# Question
Title: Randomized Version of NP
I came across interactive proofs and randomized computation, in particular, i read about the complexity classes $\text{IP}, \text{BPP}, \text{RP}$, etc.

Since the above classes are well-known, I will give a hand-wavy definition of $\text{IP}$. Then, I will state my question. Roughly speaking, a language $L \in \text{IP}$ iff there exist a pair of interactive algorithms *Prover* $P$ and *Verifier* $V$, with $V$ running in probabilistic polynomial time (in the length of the input $x$: $x$ is common to both $P$ and $V$), such that:

* If $x\in L$, and the Prover $P$ follows the protocol, then the probability that the Verifier $V$ accepts is 1, and
* if $x\notin L$, then for any Prover $P$ (even a cheating one), the probability that the Verifier $V$ accepts is at most $\frac{1}{2}$.

I note that $P$ is allowed to be computationally unbounded.

Now to understand the power of interaction, I started to see what happens when restrict or give up the interaction between the prover and the verifier. I read the following in this lecture here, given by *Jonathan Katz*:

1- Assume that the verifier has input $x$. If the protocol is such that the prover $P$ sends a proof $\pi$ (to the fact that $x\in L$) to the verifier $V$, and then the interaction ends. The verifier has then to verify that $x \in L$, given $\pi$. If the verifier is deterministic and runs in polynomial time in $|x|$. Then, it is not hard to see that such interactive protocol is equivalent to the complexity class $\text{NP}$.

2- Now if we consider the interaction protocol in item 1, and additionally allow the verifier to be probabilistic, then we get more than $\text{NP}$. Specifically, it is known that in this case, any language in $L \in \text{BPP}$ can be handled by the protocol. Note that this actually suggest that we can eliminate the error when $x\in L$.

The protocol in item 2, can be thought of as a randomized version of $\text{NP}$.

**Here comes my question:** can the protocol given in item 2, handle any language in $\text{IP}$? That is, given a language $L\in \text{IP}$, can we give up the interaction entirely and still be able to verify that $x \in L$ in probabilistic polynomial time with completeness $1$, and soundness at most $\frac{1}{2}$? Intuitively, I think the answer is unknown because randomized complexity classes are conjectured to be contained in $\text{P}$ and we don't even know whether $\text{P}$ is a strict subset of $\text{PSPACE} = \text{IP}$.

# Answer
The class you described is MA (interactive proofs consisting of one round where the prover, Merlin, sends one meassage to the verifier, Arthur, which then has to decide in probabilistic polynomial time whether to accept or reject).

Since $BPP\subseteq \Sigma\_2\cap \Pi\_2$ it immediately follows that $MA\subseteq \Sigma\_2\cap \Pi\_2$, which is believed to be a strict subset of PSPACE which contains the entire polynomial hierarchy.
> 3 votes

---
Tags: complexity-theory, complexity-classes, space-complexity, randomness, interactive-proof-systems
---


title: Why aren't Grobner bases more common?

text:
# Question
Title: Why aren't Grobner bases more common?
I have only heard of / seen Grobner bases in passing, but my understanding is that they are much like vector bases but for polynomials instead of linear systems. I know polynomials are used in CAD and graphics at the very least. Is there any particular reason why I haven't seen Grobner bases in application? I'm trying to determine whether they are worth the time to learn for my own work.

Edit: I should probably have specified that my use for them would be in solving algebraic systems. I'm mainly wondering how they compare to numerical solution techniques such as Newton's method, and other more linearization/derivative based methods. I'm an interested in any use case, but especially in this one.

# Answer
Well, I don't know what you expect to get as an answer, but in the comments you already got that if you haven't seen them used is due to two reasons.

1. The main one is probably that maybe you haven't had the need to solve problems in which they are needed, yet, and
2. that the problems, like finding **a** solution of a system of polynomial equations. are more efficiently done by algorithms that target exactly that problem, like Newton's method. Groebner bases can end up with large degrees for systems with relatively few variables and degrees larger than one.

---

The usefulness of Groebner bases becomes clear once you study what they are. They are a form in which to put a system of equations. The form is canonical once you fix a way to order monomials in several variables. If you have seen some commutative algebra, Groebner bases are a canonical set of generators of ideals in a polynomial ring $I\subset R=K\[x\_1,x\_2,\ldots,x\_n\]$.

When you choose a convenient monomial order it happens that the form has the same property as the row echelon form for linear system of equations, that the equations have less and less variables until eventually (for a system that has finitely many solutions) the last equation is a polynomial in one variables. So, incidentally you get out of it a method to find **all** solutions by backward substitution. You find all solutions of this polynomial in one variable, by either Newton's method, or perhaps some method that finds them all roots at once. This gives you the possible values of one of the variables. Then you substitute these values in the previous equations and repeat the process with them. See here for one way to do these steps.

**Example:** For the system $$\begin{align}x^2+y^2-1&=0\\xy-4&=0\end{align}$$ you get $$\begin{align}4x+y^3-y&=0\\y^4-y^2+16&=0\end{align}$$ Try it with Singular, by inputting

```
// Define the ring R[x,y] of polynomials in variables x,y;
// and lexicographical ordering to order monomials.;
ring r = 0,(x,y),lp;
// The ideal generated by those two polynomials. ;
ideal I =(x^2+y^2-1,x*y-4);
// The same ideal, but now generated by its Groebner basis.;
ideal GI=groebner(I);
// Print it.;
GI;

```

As you see, Groebner basis is not an algorithm, but a form for a system, and its goal is not to find one solution, but to put the system in a form that helps compute properties of the set of solutions as a whole. Modulo technicalities, the set of solutions is called an algebraic variety. Problems that you might need to solve could be, for example,

1. What is the **intersection** of algebraic varieties? More explicitly, suppose you have a mechanical arm with both ends attached to two fixed points and having two or three elbows (joints). What are the positions that these elbows can be? It is an algebraic variety that can be described first as the intersection of the equations that you get by imposing the length of each segment of the arm and the condition on the fixed points at each end.
2. **Parametrization** of algebraic varieties. If the mechanical arm above had only one elbow, its positions would be a circle. Perhaps you know that $t\mapsto (\cos(t),\sin(t))$ parametrizes a circle, when $t\in\[0,2\pi)$, but it could be better to get a rational parametrization, like $t\mapsto(\frac{1-t^2}{1+t^2},\frac{2t}{1+t^2})$, for $t\in\[-\infty,\infty\]$. Such parametrizations always exist. You compute them by an algorithm that uses Groebner bases among other things.
3. Maybe you need the inverse problem of (2), **implicitization**. You want a robot arm that can cut this shape that the design team chose for the silhouette of a car. They sure like their Bezier curves. They happen to be algebraic.
4. You want your computer to discover the proofs of all synthetic geometry problems that you did in high school. After sufficient squaring, the hypotheses and the thesis are polynomial equations. So, you only need to check that the first can reduce the latter to $0=0$. This a particular case of problem (1).
> 1 votes

---
Tags: numerical-analysis, computer-algebra
---


# Question
Title: k-center problem: proof for Gon algorithm gives a 2-approximation
The $k$-center problem is where we a given a graph $G(V,E)$, an integer $k$, a distance metric $d$ and we want to find a subset $C\subseteq V$ (such that $|C|\leq k$) which minimizes the following function: $\max\_{v\in V}\min\_{c\in C}d(v,c)$.

I am trying to understand the proof that the $Gon$ algorithm is a 2-approximation. The algorithm arbitrarily selects the initial center and loops for $k-1$ iterations, where at each iteration it adds the vertex which is furthest away from its nearest center as a new center.

The full proof that this algorithm gives a 2-approximation is described in Gonzalez, Clustering to minimize the maximum intercluster distance. The cost of the optimal solution is $OPT(V)$ and they describe the term "$(k+1)$-clique of weight $h$ for $V$":

> Set $T$ is said to form a $(k+1)$-clique of weight $h$ if the cardinality of set $T$ is $k + 1$ and every pair of distinct elements in $T$ are at least $h$ units apart.

The part that I don't understand is the following lemma:

> **Lemma 2.1:** If there is a $(k+1)$-clique of weight $h$ for $S$, then $OPT(V)\geq h$.

My question is, what is the proof for this lemma?

# Answer
If $k+1$ vertices are at least $h$ units apart, then no ball of diameter $\< h$ can cover two of these vertices, hence you would need at least $k+1$ balls.

Since you want to have at most $k$ balls, $h$ must be *at least* the minimum distance of the $k+1$ vertices (pairwise).

**Another way of phrasing it** would be:

> If you have a set $T$ of $k+1$ points, and at most $k$ balls of diameter $h$, then *at least one ball must contain two points*. Let $d$ be the shortest distance between two vertices in $T$ (the two closest vertices). Then $h \geq d$.

---

Taking the contra-positive of the lemma: If $\text{OPT} \< h$, then you cannot have $k+1$ points that have pairwise distance $\geq h$, or in other words, if $\text{OPT} \< h$ then

1. Any set with pairwise distance at least $h$ has at most $k$ vertices
2. Any set with at least $k+1$ vertices has a pair with distance less than $h$.
> 2 votes

---
Tags: algorithms, approximation, greedy-algorithms
---


title: Is O(1) considered polynomial time?

text:
# Question
Title: Is O(1) considered polynomial time?
I am reading about P and NP and looking at the reduction of a Rudrata/Hamiltonian path to a Rudrata cycle. I think adding an extra node and 2 edges connecting the start, `s` and the target, `t` is `O(1)` time as this doesn't depend on the size of the graph. *Algorithms* by Dasgupta et al. says that the pre and post processing steps take polynomial time.

> One last detail, crucial but typically easy to check, is that the pre- and postprocessing functions take time polynomial in the size of the instance *(G, s, t)*.

This makes me think that `O(1)` is polynomial time. Is this incorrect?

# Answer
> 2 votes
Yes, any constant is a polynomial of degree zero.

---
Tags: np-complete, asymptotics, big-o-notation, hamiltonian-path
---


# Question
Title: Linear Discriminant Method as Pre-processing for inputs going into a Neural Network?
As the title suggests, I am curious whether Linear Discriminant Method can be performed on a dataset as pre-processing before putting the reduced-dimensional data as input for a neural network for creating the mapping function/ surrogate model.

Thanks!

# Answer
> 0 votes
This is not a useful method. LDA is basically a two-class classifier, which works under certain assumptions on the distribution of the data. If those assumptions hold, LDA is optimal and there is no reason to use a neural network. If those assumptions don't hold, LDA might not be a useful tool. Even if you do use LDA, LDA maps each data point to one of two classes, so there is no information left for the neural network to do any further processing.

In short: LDA is not useful as a preprocessing step before a classifier; you either use LDA as the classifier itself, or you don't use LDA at all.

---
Tags: algorithms, machine-learning, neural-networks
---


# Question
Title: A data structure that supports efficient insertion of arbitrary integers, value lookup, and removal of all integers smaller than a given threshold?
I'm looking for a data structure that supports efficient:

1. Insertion of arbitrary integers.
2. Value lookup (given a particular value `needle`, return true if it's currently in the structure).
3. Removal of all values below a given `threshold` integer.

I suspect this can be with a self-balancing BST, with insertion and lookup both costing `log(n)` time. I *think* the removal operation can be done by pruning an entire subtree out, but I'm not sure this can be done in `log(n)` time while keeping the tree balanced. If we remove a very large subtree (say the left child of the root node), it seems like it would take basically rebuilding the entire tree, which is `O(m log m)` with `m` being the number of remaining nodes, and at any rate no less than `O(m)`.

A cheaper approach would be to use a naturally-ordered self-balancing BST. For removal, we can just start at the smallest node, and keep removing (and rebalancing) until we run out of nodes or hit the `threshold`. This will cost `O(m log n)` where `m` is the number of nodes to be removed.

Bonus question: what if instead of removing below a `threshold`, we need to support removal of all nodes in a range between `upper_bound` and `lower_bound`?

# Answer
> 1 votes
If you accept randomized algorithms you could use TREAP. This data structure is BST where each node is augmented with *priority*, a random number. The only one invariant over normal normal BST is that parent's priority must be greater than children's. This results in a very simple implementation of *Insert* and *Delete* functions (recursive variant is 10-15 lines of clean C code). The complexity of basic operations is $O(\log N)$ on average.

It is possible to cut-off all nodes below *threshold* in $O(\log n)$ time assuming that nodes below the *threshold* are not disposed.

```
Node cut(Node node, int threshold) {
   if (node->key < threshold) {
      // optionally dispose node, and subtree at node->left
      return cut(node->right, threshold);
   }
   node->left = cut(node->left, threshold);
   return node;
}

root = cut(root, threshold);

```

Note, that there is no rebalancing because the node is replaced by one of its children (or subchildren). As result the priority invariant in satisfied.

Disposal of nodes with a key below the threshold will increase complexity to $O(k + \log n)$, where $k$ is a number of disposed nodes. Cost of disposal will be amortized to $O(1)$ over multiple operations because each node is created and disposed only once.

Removal of nodes *above* a given threshold will require symmetrical functions.

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


# Question
Title: solving Recurrence relation f T(n)=T(n/2)+log log(n)
```
T(n)=T(n/2)+log log(n)--------1
T(n)=T(n/4)+log log(n/2)+log log(n)-------------2
T(n)=T(n/8)+log log(n/4)+log log(n/2)+log log(n)-----------3
T(n)=T(n/2k)+log log(n/k)+....+log log(n/2)+log log(n)
T(n)=1+log log(n/k)+....+log log(n/2)+log log(n)
 n/2k=1 => n=2k
 T(n)=1+log log(2K/k)+....+log log(n/2)+log log(n)
 T(n)=1+log log(2)+....+log log(n/2)+log log(n)
 T(n)=1+log (log(2)*....*log(n/2)*log(n))

```

I ARRIVED AT THIS POINT BUT I DIDN'T KNOW HOW TO CONTENU ANY HELP PLEASE

# Answer
Let's consider $n=2^k$: $$\begin{array}{l}T(n)=T\left(\frac{n}{2}\right)+\log\log n = T\left(\frac{n}{2^2}\right)+\log\log \frac{n}{2}+\log\log n = \\ =T\left(\frac{n}{2^3}\right)+\log\log \frac{n}{2^2}+\log\log \frac{n}{2}+\log\log n=\\ =\cdots=\\ =T\left(\frac{n}{2^k}\right)+\log\log\frac{n}{2^{k-1}}+ \log\log\frac{n}{2^{k-2}}+\cdots+\log\log n=\quad(3)\\ =T(1)+\log\log 2 + \log\log 2^2 + \cdots + \log\log 2^k=\\ =T(1)+\log\left\[ \log2\cdot \log2^2 \cdots \log2^k \right\] =\\ = T(1)+\log\left\[ k!\log^k2 \right\]=\\ =T(1) + \log k! +k \log\log 2 \in \Theta(k \log k)\end{array}$$ where $k=\log\_2 n$.
> 1 votes

# Answer
Define $S(n) = T(2^n)$, and assume that "log" is the base-2 logarithm. Then

S(n) = $T(2^n) = T(2^{n-1}) + \log \log 2^n$ = $S(n-1) + \log n$.

That means we find S(n) by adding S(0), plus the sum of $\log k$ for 1 ≤ k ≤ n. That sum is equal to the logarithm of n!, so $S(n) = S(0) + \log n!$. A good approximation to n! is the Stirling formula $n! ≈ n^n e^{-n} (2 \pi n)^{1/2}$.

The base-2 logarithm is $\log n! ≈ n \log (n/e) + \log (2 \pi n) / 2$, and S(n) ≈ S(0) + $n \log (n/e) + \log (2 \pi n) / 2$.

Since $S(n) = T(2^n)$, we have $T(n) = S(\log n)$, so $T(n)$ is about T(1) + $\log n \cdot (\log \log n - \log e) + \log (2 \pi \log n) / 2$.
> 0 votes

---
Tags: time-complexity, recurrence-relation, recursion
---


# Question
Title: Why are regular tree languages closed under intersection, but deterministic context free languages are not closed under intersection?
I am looking for intuition here. Essentially, I understand that the set of parse trees from a context free grammar forms a regular tree language. I also understand that regular tree languages are closed under union, intersection and complement. Now, why are deterministic context free languages not closed under intersection? (the intersection of DCFL need not even be in CFL) but intersection of regular tree languages are closed under intersection? (I get why DCFL union is not in DCFL -- because there is ambiguity).

# Answer
> 4 votes
The intuition is that the strings of a context-free language are formed by the "frontier" (the leaves) of the derivation trees. The trees themselves are no longer directly visible.

Thus, the intersection of two tree languages consists of the trees the structure of which belongs to two tree grammars. We must be able to map productions of both grammars onto the *same tree*. Moreover, the tree is visible, we do not have to guess it.

For the intersection of two context-free languages we need *two trees*, one for each grammar and we only need the two frontiers to be the same. Hence we can find languages like $\\{a^nb^nc^n \mid n\ge 1\\}$ which is the intersection of two context-free grammars. The first one has a tree structure that verifies that the $a$'s and $b$'s are equal, while the second grammar checks the $b$'s and $c$'s with another tree structure. Also we need to 'guess' the two trees as we only 'see' their frontiers.

I do not think that determinism is essential in this discussion.

---
Tags: formal-languages, automata
---


title: Unification with a list of terms

text:
# Question
Title: Unification with a list of terms
The problem: we have a list of terms $\[t\_1, ..., t\_n\]$ , and a term $t$, and we want to find which of the terms in the list can be unified with $t$. Obviously we can iterate through the list and check one-by-one whether $t\_i$ unifies with $t$, but what better (i.e. faster) approaches exist? Assume we can store the list however we want.

I'm particularly interested in approaches that extend well to unification modulo a theory, but assume the empty theory to start.

This must be a basic question but I can't find good references, so any references are much appreciated.

# Answer
Prolog compilers already do this. Imagine if you had the program:

```
p(t1) :- body_1.
p(t2) :- body_2.
% ...
p(tn) :- body_n.

```

and you issued the query `p(t)`.

There is a lot of literature on this topic, and I don't know if there is a recent review which covers it all. You could start with:

Colomb, J. *Enhancing Unification in Prolog through Clause Indexing*, J. Logic Programming, 1991:10:23-44.
> 2 votes

---
Tags: algorithms, data-structures, unification
---


# Question
Title: Scott Aaronson's Proof of $\textbf{BPP} \subset \textbf{P/poly}$
The proof is in the image below, taken from "Quantum Computing Since Democritus":

Here's what I don't totally get: my understanding of random algorithms is that randomization is not done over the input space; the inputs are still worst case. So that when a random algorithm has some error, what I interpret that to mean is that given *any* input string to the algorithm, there is at most such-and-such probability of outputting a wrong answer.

If I take the same string $s$ and run it through the random algorithm with error rate $e\<1$ an $n$ amount of times, I should expect $ne$ wrong answers.

I haven't been able to reconcile the above with the technique used in the linked proof; in particular, the jump from $2^{-n^2}$ being the error rate of the BPP algorithm to saying that a $2^{-n^2}$ fraction of random strings cause us to err. If someone could explain this proof a little more verbosely I think I'd find that very helpful.

# Answer
> 3 votes
What he here means by a "random string" is not an element of the input space, but rather a string *of random choices*, i.e. a series of coin flips that have been taken while executing the randomized algorithm. If you enumerated every possible such series of coin flips, you would see that at most a $2^{-n^2}$ fraction of them would lead the algorithm to conclude with the wrong answer.

---
Tags: complexity-theory, randomized-algorithms
---


# Question
Title: Finding closest line segment intersecting rays
Assuming we have a fixed set of line segments $S$ such that any two segments are either disjoint or have a common endpoint.

A query would look like this; given a query point $q$ shoot 4 rays from $q$ (both sides horizontally and both sides vertically) and report the line segment in $S$ closest to $q$ intersecting any on these rays.

Is there a way to do this faster than $O(n)$ by preprocessing the data and storing it in some data structure? Or do we have to check for intersections with all segments for each ray and then compute the distances from the intersected line segments to $q$?

# Answer
> 2 votes
You'll need two data structures - for vertical rays and for horizontal rays. I'll describe a data structure for vertical rays. Draw a vertical line through each segment end - you'll get a set of vertical *slabs*. Each of these slabs will be divided by pieces of original segments into *trapezoids* (possibly infinite ones).

Number of these slabs will not exceed $2n$, and number of trapezoids in each slab will not exceed $n$. In order to find a segment, closest to the query point along a vertical ray (going up or down), you need to use binary search to find a slab at first, and then - another binary search to find a trapezoid inside the found slab. Upper and lower boundary of this trapezoid will give you the answer. These two binary searches will take $O(log(n))$ time.

The data structure for horizontal rays is similar - the only difference is that slabs should be horizontal.

---
Tags: algorithms, data-structures, computational-geometry
---


# Question
Title: If $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ is $L_1=L_2$
If the *same* $f$ reduces $L\_1$ to $L$ and also $L\_2$ to $L$ does it imply that $L\_1=L\_2$?

My intuition says no, but I couldn't find a counterexample.

# Answer
Using the definition of reduction,

$x\in L\_1\iff f(x)\in L \iff x\in L\_2$

And thus $L\_1=L\_2$.
> 1 votes

# Answer
When a reduction takes place that means that the problem $L\_i$ is just a different "point of view" of problem $L$. Given that you have two problems $L\_1$ and $L\_2$ reducible to the same $L$ then you could say that by solving $L$ you would be able to solve both. This in turn implies that they could be treated as the same problem.
> -2 votes

---
Tags: computability, reductions
---


# Question
Title: Is the language of binary strings that contain a substring of the form $ww$, where $w \in (0+1)(0+1)^*$ regular?
Consider the language:

$L=$binary strings that contain a substring of the form $ww$, where $w \in (0+1)(0+1)^\*$.

I am convinced this language is not regular, as $w$ can have arbitrary length due to the $(0+1)^\*$ term, and whatever is generated by this term must be remembered for the next occurrence of $w$ immediately thereafter. So, a DFA cannot accept this language. Is this correct? Perhaps, I could show this more formally with the pumping lemma, but I just want to make sure the intuition is correct.

Now, do you agree that the way I have defined the language above implies that the first occurrence of $w$ must be the same as the second occurrence of $w$? For example, $w$ cannot equal $01$ in its first instance, but $011$ in its second instance.

Now, consider the language:

$T=$binary strings that contain a substring of the form $wy$, where $w,y \in (0+1)(0+1)^\*$.

T is regular. Because $(0+1)^\*(0+1)=(0+1)(0+1)^\*$, the regex representing $T$ can be written as $(0+1)^\*(00+01+10+11)(0+1)^\*$. Is this correct?

Now, back to language $L$. This was defined in some exercises I was doing exactly as it is above. The solution said that $L$ is regular and can be represented by regular expression: $(0+1)^\*(00+11+0101+1010)(0+1)^\*$.

Lastly, If my thinking about $L$ is incorrect for some reason, does the regular expression $(0+1)^\*(0+1)(0+1)^\*(0+1)(0+1)^\*(0+1)^\*$ equal $L$?

I hope I have communicated my thoughts clearly on this matter. Please help me understand.

# Answer
Your language is regular.

Let's see which words *do not* belong to $L$. If a word contains $00$ or $11$ as a substring that it does belong to $L$, hence any word not in $L$ must have alternating $0$s and $1$s. If such a word has length at least $4$ then it must start with $0101$ or $1010$, and so again it is in $L$. We are left with the following words, which comprise $\overline{L}$: $$ \epsilon, 0, 1, 01, 10, 010, 101. $$ Since $\overline{L}$ is finite, it is regular, hence so is its complement $L$.

What this argument shows is that any word in $L$ contains one of $00,11,0101,1010$ as a substring. This explains the given regular expression.
> 1 votes

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


# Question
Title: Asymptotic order of a recursive function
\begin{gather\*} T(n)=T(\frac{n}{\log n})+O(1) \end{gather\*} \begin{gather\*} T(1)=O(1) \end{gather\*} I try to use substitution method to solve $T(n)$, but because of $\log n$ get stuck. Can we use substitution method for solving $T(n)$?

My attempt: One step of my extending of $T(n)$: \begin{gather\*} T(n)=T(\frac{n}{\log n})+O(1)=T(\frac{\frac{n}{\log n}}{\log \frac{n}{\log n}})+O(1)+O(1) \end{gather\*}

# Answer
> 0 votes
Initially, we prove lower bound as follow:

Suppose in each iteration we divide $n$ to $\log k$ so we define new fuction $a\_k(n)$ as follow:

\begin{gather\*} a\_k(n) =a\_k\left(\frac{n}{\log k}\right) \end{gather\*}

If $k\<\<n$ then after using substitution method we have : \begin{gather\*} a\_k(n) =a\_k\left(\frac{n}{\log^t k}\right) + \overbrace{O(1)+O(1)+...+O(1)}^\text{t times} \end{gather\*}

So for find value of $t$:

\begin{gather\*} \left(\frac{n}{\log^t k}=1\right) \end{gather\*} \begin{gather\*} n=\log^t k \end{gather\*} \begin{gather\*} t=\log\_{\log k}n. \end{gather\*}

As a result, \begin{gather\*} T(n)=\Omega\left(\frac{\log n}{\log\log n}\right). \end{gather\*} For upper bound we do trickly: As mentioned in this post

Now we define $a\_k(n)$ as follow: $$ a\_k(n) = \begin{cases} a\_k\left(\frac{n}{\log k}\right) + O(1) & \text{if } n \ge k, \\ T(n) & \text{otherwise.}\\ \end{cases} $$

As you see $T(n)\leq a\_k(n)$ for $k\leq n$ so we set $k=\sqrt{n}$ and we have $$ a\_k(n)\leq T(\sqrt{n})+O\left(\frac{\log \frac{n}{k}}{\log\log k}\right)$$ $$ T(n)\leq T(\sqrt{n})+O\left(\frac{\log n}{\log\log n}\right)$$

Multiply side of inequality by $\log\log n$:

$$ T(n)\log\log n\leq T(\sqrt{n})\log\log n+O\left(\log n\right)$$

$$ T(n)\log\log n\leq T(\sqrt{n})\log(\log (\sqrt{n}\times\sqrt{n})) +O\left(\log n\right)$$

$$= T(n)\log\log n\leq T(\sqrt{n})\log(\log \sqrt{n}+\log\sqrt{n}) +O\left(\log n\right)$$

$$= T(n)\log\log n\leq T(\sqrt{n})\log(\log \sqrt{n}(2)) +O\left(\log n\right)$$

$$= T(n)\log\log n\leq T(\sqrt{n})(\log\log \sqrt{n}+\log 2) +O\left(\log n\right)$$ $$= T(n)\log\log n\leq T(\sqrt{n})(\log\log \sqrt{n}+1) +O\left(\log n\right)$$

So we define $$H(n)=T(n)\log\log n$$ As a result we have:

$$= H(n)\leq T(\sqrt{n})+H(\sqrt{n}) +O\left(\log n\right)$$

We show that $T(n)\leq O(\log n)$:

$$T(n)=T\left(\frac{n}{\log n}\right)+O(1)\leq T\left(\frac{n}{2}\right)+O(1)$$

So

$$= H(n)\leq H(\sqrt{n}) +O\left(\log n\right)$$

Finally with substitution method:

$$= H(n)\leq H\left(n^{\frac{1}{2^k}}\right) +O\left(\log n\right)\left(1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots + \frac{1}{2^{k-1}}\right)$$

We know that $k=\log\log n$, and becuase of : $$\left(1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots + \frac{1}{2^{k-1}}\right)\leq 2$$ then $$ H(n)\leq O\left(\log n\right)$$

As the result $$T(n)\leq O\left(\frac{\log n}{\log \log n}\right)$$ We prove upper bound and lower bound of $T(n)$ so $$T(n)\leq \theta\left(\frac{\log n}{\log \log n}\right).$$

# Answer
> 1 votes
What you are asking is really, how many times do you need to apply the transformation $m \mapsto \frac{m}{\log m}$ in order for a value to drop from $n$ below some constant $C$; if the answer is $f(n)$, then $T(n) = \Theta(f(n))$.

Given $n$, define a sequence by $n\_0 = n$ and $n\_{i+1} = n\_i/ \log n\_i$. We would like to know the minimal value of $t$ which satisfies $n\_t \< C$.

Taking logarithm, we see that $\log n\_{i+1} = \log n\_i - \log\log n\_i \geq \log n\_i - \log\log n$. Since $\log n\_0 = \log n$, this shows that $t \gtrsim \frac{\log n}{\log\log n}$.

In the other direction, as long as $n\_i \geq \sqrt{n}$, we have $\log n\_{i+1} \leq \log n\_i - \log \log \sqrt{n} \leq \log n\_i - \log \log n + \log(1/2)$. Hence we get from $n$ down to $\sqrt{n}$ in roughly $\frac{\log n}{\log\log n}$ steps. We then get down to $\sqrt\[4\]{n}$ in roughly $\frac{\log \sqrt{n}}{\log\log \sqrt{n}} \approx \frac{\frac{1}{2} \log n}{\log\log n}$ steps. Continuing in this way, we see that $t \lesssim \frac{2\log n}{\log\log n}$ (summing the series $1+\frac{1}{2}+\frac{1}{4} + \cdots = 2$).

---
Tags: recurrence-relation
---


title: Prove that $1^\text{nan} = 1.00$

text:
# Question
Title: Prove that $1^\text{nan} = 1.00$
I know that for most computation involve nan (not a number) the result is a nan itself except for some cases. For example, $1^{\text{nan}} = 1.00$ which proven by mathematicians to be true.

I tried to find a proof but failed so my question is how to prove that $1^{\text{nan}} = 1.00$?

# Answer
The fact that $1^{\text{nan}}= 1.0$ is *by definition*, and not by proof, more specifically, it is by definition of the standard IEEE 754, **IEEE Standard for Floating-Point Arithmetic**.

From the definition of floating-point arithmetic, as specified in IEEE 754 revision 2008, *9.2.1 Special values*:

> `pow(+1, y)` is `1` for any `y` (even a quiet NaN).

Here is the full list of special values for `pow`:

> For the pow function (integral exponents get special treatment):
>
> * `pow(x, ±0)` is `1` for any x (even a zero, quiet NaN, or infinity)
> * `pow(±0, y)` is `±∞`s and signals the divideByZero exception for `y` an odd integer `< 0`
> * `pow(±0, −∞)` is `+∞` with no exception
> * `pow(±0, +∞)` is `+0` with no exception
> * `pow(±0, y)` is `+∞` and signals the divideByZero exception for finite `y < 0` and not an odd integer
> * `pow(±0, y)` is `±0` for finite `y > 0` an odd integer
> * `pow(±0, y)` is `+0` for finite `y > 0` and not an odd integer
> * `pow(−1, ±∞)` is `1` with no exception
> * **`pow(+1, y)` is `1` for any `y` (even a quiet NaN)**
> * `pow(x, y)` signals the invalid operation exception for finite `x < 0` and finite non-integer `y`.
> 4 votes

# Answer
While @Pal GD is correct that it is a definition, it is not an arbitrary definition.

There is a basic rule behind:

> if a function f(x, y) has the property for some value X that f(X, y) is independent of y , be it finite or infinite, then that f(X, NaN) must be the same as f(X, y) .

This is from W. Kahan the designer behind the IEEE 754 standard (see reference)

For a discussion why this rule makes sense, please see this answer

If one sticks to this rule one can indeed proof that `1.0^NaN == 1.0`
> 4 votes

---
Tags: floating-point
---


# Question
Title: Building a tree with the heap property from an array and preserving its order
How efficiently can I build a binary tree satisfying the heap property from an array and such that the **inorder traversal of the tree is the original array**?

For example, if I have:

> 2 1 5 6 2 3

I want to build:

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

```

Because it has the heap property and its inorder is the original array `2 1 5 6 2 3`.

# Answer
I think I have found a linear solution. We can build the tree keeping a pointer to its rightmost element. Every time we want to insert a new value, we compare it to the rightmost element:

* if it is smaller, we proceed to compare it to the parent of the current node, ascending through the rightmost branch.
* if it is greater, we append it as its right child, and append the previous right child as the left child of the new node.

As every comparison adds a new element or removes an element from the rightmost branch, we know this is done in ${\cal O}(n)$.

In my example:

```
1st step

 2 <--

2nd step

   1 <--
  /
 2

3rd and 4th steps

  1
 / \
2   5
     \
      6 <--

5th step

  1
 / \
2   2 <--
   /
  5
   \
    6

6th step

  1
 / \
2   2
   / \
  5   3
   \
    6

```

The second and fifth steps are using the second case of the algorithm, the rest are using the first case.
> 1 votes

# Answer
An O(n)-time algorithm for the problem has been published by Gabow et al. (1984) in the context of "Cartesian trees": https://dl.acm.org/doi/10.1145/800057.808675

As pointed out above by Raphael, there is a close relationship to treaps. You may also want to visit the corresponding Wikipedia entry: https://en.wikipedia.org/wiki/Cartesian\_tree
> 2 votes

# Answer
I have found a solution in ${\cal O}(n \log n)$. We could sort the array tracking the original index of every element in ${\cal O}(n\log n)$. In the original `2 1 5 6 2 3` example:

```
Sorted array:     1 2 2 3 5 6
Original indexes: 1 0 4 5 2 3

```

And now, we could insert the sorted elements on a binary tree in order. We insert the first element on the root, and then, we compare every element's index with the root's one to decide if we insert it on the left or the right subtree. The building process would be something like this:

```
First and second steps:

     1(1)
    /
2(0)

Third and fourth steps:

     1(1)
    /    \
2(0)      2(4)
             \
              3(5)

Final two steps:

     1(1)
    /    \
2(0)      2(4)
         /   \
       5(2)  3(5)
         \
          6(3)

```

It preserves the heap property, as we are inserting the nodes in order as children of previously inserted nodes. It preserves the *inorder property*, as we are using the indexes to position the elements on the tree.

Is there any better solution I am missing? I would like to find a linear one or prove that it cannot exist.
> 1 votes

# Answer
here is my solution when I met this question during interview:

```
public TreeNode buildTree(int[] inArray){
  if (inArray == null || inArray.length == 0) return null;

  int n = inArray.length;
  return dfs(inArray, 0, n - 1);
}

private TreeNode dfs(int[] inArray, int start, int end){

  if (start == end){
    return new TreeNode(inArray[start]);
  }

  if (start > end){
    return null;
  }

  int minIndex = findMin(inArray, start, end);
  TreeNode curNode = new TreeNode(inArray[minIndex]);

  TreeNode leftNode = dfs(inArray, start, minIndex - 1);
  TreeNode rightNode = dfs(inArray, minIndex + 1, right);

  curNode.left = leftNode;

  curNode.right = rightNode;

  return curNode;
}

private int findMin(int[] inArray, int start, int end){
  int minIndex = -1;
  int min = Integer.MAX_VALUE;
  for (int i = start; i <= end; i++){
      if (inArray[i] < min){
        minIndex = i;
        min = inArray[i];
      }
  }

  return minIndex;
}

```
> -1 votes

# Answer
Just refere wiki: https://en.wikipedia.org/wiki/Binary\_heap it a trivial algoritm using **sift down** operation. But advise you to do in on your own. Should be simple. Why do you need unbalances tree by the way? Should work for unbalances, I think.
> -2 votes

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


# Question
Title: Are EAX , EBX registers 64 bit in length in modern processors
The EAX, EBX and ECX registers on a cpu are they 64 bits for a 64-bit cpu ?

# Answer
No, they still refer to a 32bit register. But they are part of 64bit registries RAX, RBX and RCX.

The main reason for this is backward compatibility.
> 1 votes

---
Tags: cpu, assembly
---


# Question
Title: AdaBoost - why using such alpha function?
I'm reading the paper where AdaBoost was invented (link), and I couldn't understand why they have chosen the formula `α_t = 1/2 * ln((1-ε_t) / ε_t)`.

snippet: AdaBoost algorithm from the paper

What is the motivation behind that specific formula? Why not using something that feels more natural like `ε_t`?

# Answer
Recall that the final hypothesis after $T$ rounds is $h\_T(x)=sign\left(\sum\limits\_{i=1}^T \alpha\_t h\_t(x)\right)$, i.e. $\alpha\_t$ is the weight of $h\_t$ in $h\_T$. If $\epsilon\_t$ is high (near one) you want to answer the opposite of $h\_t$, so you want $\alpha\_t$ to be negative and very large in absolute value. If on the other hand $\epsilon\_t$ is very low then you want $\alpha\_t$ to be very large. The worst case is $\epsilon\_t=\frac{1}{2}$, in which case $h\_t$ is of no use to you.

The function $\log\frac{1-\epsilon\_t}{\epsilon\_t}$ satisfies those properties. This magnitude is known as log odds (where the probability considered is $p=1-\epsilon\_t$, the success probability). Intuitively, the odds ratio tells you how often an event with probability $p$ occurs, in our case if e.g. $\epsilon\_t=1/3$ then $\frac{1-\epsilon\_t}{\epsilon\_t}=2$, i.e. $h\_t$ is expected to succeed with ratio $2:1$.
> 4 votes

---
Tags: machine-learning, learning-theory
---


# Question
Title: Find minimum number of points which intersect overlapping arcs
Say I have a circle of a fixed radius, with overlapping arc intervals along its edge. I want to return a minimum set of Points which intersects all arcs in $n^2$ time.

I'm having some trouble proving that my algorithm works. I'm getting caught up with arc intervals that span $0,2\pi$.

For example I have the intervals (in degrees): `[45,90],[315,50],[300,25],[310,350]` \- when I do a sweep I find that the first degree with the least intersects (2) - is 25 - committing to this yields needing 3 points `{25,45,310}`, whereas the optimal solution is 2 points `{~45,~350}`. I'm thinking I can maybe just exclude that angle of the least intersects - but I'm not sure how to prove I won't run into a similar problem with a different set of arcs?

So far I have:

```
# place Intervals in a minHeap based on "starting" radian/degree O(n)
# i = sweep intervals to find first radian/degree with least intersects O(n)
p = float(+inf)
P = {}
while minHeap is not None:
  I = minHeap.deleteMin()
  if I.start>I.end:
    I.end += 360   # trying to normalize
  end if

  if I.start < i:
    minHeap.insert(new interval with I.start + 360 and I.end +360) #too early to evaluate
  else:
    if I.last <= p:
      p = I.last #looking for the counterclockwise radian/degree which covers most arcs
    end if

    if I.first > p:
      #found an interval out of reach - updating trackers
      p = p % 360 #normalizing
      P[p] = true #will eventually return P
      p = I.last  #updating to the new most counterclockwise rad/degree
    end if
  end if
end while
return P

```

# Answer
> 1 votes
A little abstraction would help both reasoning about and solving the problem efficiently, I think.

For every point $x$ on the circle, there is some set $S\_x$ of pairwise overlapping arcs that intersect this point. Now, if there is some other point $y$ such that $S\_x \subseteq S\_y$, you can always use $y$ instead of $x$ in a solution to your problem. We can therefore focus on a set of representative points $x\_1,\ldots,x\_m$ such that each set $S\_{x\_1},\ldots,S\_{x\_m}$ is maximal. There are at most $n$ such points (the proof of which I will leave as an excercise) and you should be well able to find this set in $O(n^2)$ time.

Now, if the arcs don't wrap all around the circle, i.e. there is some point on the circle that doesn't touch any arcs, then you can look at the arcs as intervals on a straight line. Given the right infrastructure (you should sort the arcs *both* by starting and ending angle, again easily doable in $O(n^2)$ time) you can solve this problem greedily in $O(n)$ time (cf. this post).

Finally, to solve the problem, you do as follows: For each $1\leq i\leq m$, you ask the following question: "If i use $x\_i$, how many other points must I use in order to cover the arcs that are not in $S\_{x\_i}$?" These arcs naturally do not wrap around the circle. You can therefore calculate this in linear time, and return the minimum set of points over all tries. Since $m\leq n$, this will only take $n^2$ time in total.

---
Tags: algorithm-analysis, sorting, greedy-algorithms, intervals, selection-problem
---


# Question
Title: Calculating worklist with live variable analysis
I am struggling with the calculation of the worklist algorithm, I do not want to implement the iterative algorithm as so many redundant steps it takes.

The algorithm I am following to calculate the worklist for live variables is as below

Can anybody explain to me for my example given below, what would be my initial worklist and how the worklist algorithm would be applied to this?

```
x = 1   /*block 1*/
y = 23  /*block 2*/
x = 100 /*block 3*/
print x+y /*block 4*/

```

for simple understanding I have taken this code, I have calculated below equations for In\[n\] block only as I am not able to understand how this algorithm works for out\[n\].

```
in[4] = use[4] U (out[4] - def[4])
       = {x, y} U { }
in[3] = use[3] U (out[3] - def[3])
       = { } U { y }
in[2] = use[2] U (out[2] - def[2])
       = { } U { y } - { y }
in[1] = use[1] U (out[1] - def[1])
       = { } U {  }

```

Now, even though I calculated these equations I am not sure how to use it in worklist? And at end how to does the worklist gets empty?(Algorithms - Nielson book slide 15)

# Answer
> 1 votes
first of all, this will be my first post in here, so if I can't express myself clearly, I am open to all questions and suggestions. So let's start with your first question, about the initial worklist and how should it look like? In your example, there are four blocks if we show it on control flow graph, we get :

Here we have 4 blocks or as the algorithm calls, "nodes". We create our initial worklist as a FIFO construct. So initially we have something like this :

Now, we will initialize the algorithm. In initialization part, we assign all in and out functions to empty set. So in\[1\], in\[2\].... out\[3\], out\[4\] will be empty. Also we have created our list in FIFO construct such as W = 4,3,2,1. Now we start the loop.

We start with w.pop = 4. As the algorithm suggests, out\[4\] = union of successor nodes' in functions. But for node 4, there is no successor so it will be again empty, {} . For in\[4\] = use \[4\] U (out\[n\] - def\[n\]) = {x,y} U ({} -{}) = {x,y}. Then we check if in\[4\] has changed or not. The answer is yes, it changed because it was an empty set initially but it updated and become {x,y}. So we should add our work list its predecessors where it is node 3. Now the equations have become in\[1\], in\[2\], in\[3\] = {} , in\[4\] = {x,y} and out \[1\], ...out\[4\] = {}.

Now we continue with our new worklist w = 3,3,2,1. So now we have 3 as the head. out\[3\] = in\[4\] = {x,y} and in\[3\] = use\[3\] U (out\[3\] - def\[3\]) = {}U ({x,y} -{x}) = {y}. Is our new in\[3\] is different? Again the answer is yes. Then, we add its predecessor 2 to our list. Our list becomes w = 2,3,2,1.

We continue to do it out\[2\] becomes in\[3\] = {y} and in\[2\] = {} U ({y} - {y} ) = {}. In this situation there is no update for in\[2\]. Because it was {} and still it is. Then we do not add its predecessor to work list, w =3,2,1.

We do the same things for 3 and 2, nothing changes. Then finally we came to the node 1. out\[1\] = in\[2\] = {} and in\[1\] = {}. So it does not change. And finally we finish our list, it became empty. And the algorithm terminates with the equations:

in\[1\] = {} in\[2\] = {} in\[3\] = {y} in\[4\] = {x,y}

out\[1\] = {} out\[2\] = {y} out\[3\] = {x,y} out\[4\] = {}

I hope it helps. If you have any questions remaining you can post here or ask me via private message (I don't know if this platform has a functionality for this). If you think that I made some mistakes, that could happen, please let me know.

---
Tags: compilers
---


# Question
Title: Divide and conquer algorithm for a gas station problem
I never heard about this variation of the gas station problem. The statement is as follows:

> There is just one road connecting the n+1 cities c0, …, cn consecutively. You want to go from c0 to cn stopping at most s times to fill the tank of the car. There are gas stations at the cities, but none on the roads. The length of each road is ℓ0, …, ℓn−1. Which is the minimum range for your car? Suppose that you start with a full tank.

This has to be done in something like `nlogn`, because I already tried the `n^2` approach and is not good. I don't know how to decide if I should refill at some point or not. For this inp:

```
5 0
100 300 500 200 400
5 1
100 300 500 200 400
5 2
100 300 500 200 400
5 3
100 300 500 200 400
5 4
100 300 500 200 400

```

The output should be: 1500 900 600 500 500

(Consider that the input is a sequence of `n` and `s`, followed by `n` naturals that represents `l_i`.

Source

# Answer
You can use binary search on the range of the car. Refill only if needed.

---

Here is the algorithm in more detail.

1. Let `low = 0` and `high = distance from c0 to cn`. During the whole algorithm, range `high` is always big enough for a car to reach cn from c0, while range `low` is always not.
2. Repeat the following as long as `low + 1 < high`
    1. `mid = (low + high) /2`
    2. If range `mid` is big enough, set `high = mid`. Otherwise, set `low = mid`.
3. Return `high`, which must be the minimum range of the car.

---

How can we check if a given range is big enough?

Simple.

We will try driving a car with that range from c0 to cn. At each city, if the remaining range of the car is not enough for the car to reach the next city, refill the car to its full range. If we have refilled s+1 times before we have reached cn, that given range is not enough. Otherwise, it is enough.

---

It takes $O(n)$ time to check whether a given range is big enough.
The bisecting loop will run at most $\lceil\log\_2 m\rceil$ iterations, where $m$ is the distance from c0 to cn.
So, the algorithm runs in $O(n\log\_2 m)$-time.
> 1 votes

---
Tags: algorithms, divide-and-conquer
---


# Question
Title: Could AI be used to detect when a human is picking survey response options randomly?
Context: I am a clinical psych researcher dabbling in machine learning.

Humans cannot be truly random. Therefore, could machine learning be used to analyze a string of numbers and determine the probability that said string was generated by a human or by a computer? Taking it a step further, could machine learning be used to look at survey responses and determine the likelihood as to whether the participant was answering questions honestly, or whether they "Christmas-tree'd" either part of or all of the survey? If so, would this be dependent on the specific questions that each survey item asked, or simply on the type of survey question (e.g., Likert-type, sliding scale, ruler, yes/no or true/false questions, free response, etc.)?

# Answer
> 2 votes
AI is probably not the best tool for this job. Several classical techniques in survey design include:

* Consistency check: ask the same question in several ways, spread out across the survey, and check if they've answered consistently.
* Open-ended questions: ask an open-ended question, see if they write nonsense or the bare minimum.
* Attention check questions: e.g., "What is your favorite color? Regardless of your favorite color, please pick the second option." Beware that these are controversial and have pros and cons.
* Recruitment: recruit subjects who are less likely to try to cheat you. Pay them a reasonable wage for their time.

My experience is that it is easy to be overly worried about respondents answering dishonestly; if you follow basic good practices, the overwhelming majority of respondents will try to be helpful and won't try to cheat you.

---
Tags: machine-learning, artificial-intelligence, randomness
---