# Question
Title: $O(\log n)$ search algorithm for a sorted natural number array with block of 0s on right
Assume A is an m sized array containing n ($m \ge n$) natural numbers (excluding $0$), sorted on the left of it. All remaining cells on right are filled with zeros.

For example, $m=10, n=4$:

$$A = \\{5,7,11,24,0,0,0,0,0,0\\}$$

How can I find the index of a natural number x in A with $O(\log \boldsymbol{n})$ complexity?

**Edit:** $n$ is not known.

# Answer
A two-stage binary search works. First, for the purposes of this search define $0$ to be greater than any positive integer.

Then, let $l = 1$ and $h = 2$ and:

1. While $A\_h \leq x$ let $l \leftarrow h$ and $h \leftarrow 2h$. Since for all $h \> n$ we have $A\_h = 0$, which we defined to be greater than any positive number, this loop must exit within $O(\log n)$ iterations.
2. Now $A\_l \leq x \< A\_h$, and $A$ is sorted, so we can do a binary search in range $\[l, h\]$. This also takes $O(\log n)$ steps since $l,h \leq 2n$.
> 2 votes

# Answer
Take a modified "compare" operation which considers 0 to be larger than any other number. Then use ordinary binary search. That's all.

Missed the "O(log m)" requirement... Easy. You check the elements at index 2^20, 2^400,2^8,000, 2^160,000 etc. first. Except for m = 1, log n is at most 20 times larger than log m. As long as you realise that the "block of zeroes" at the right side is a red herring.
> 0 votes

---
Tags: algorithms, search
---


title: How to count occurences in a Skiplist

text:
# Question
Title: How to count occurences in a Skiplist
If we have an sorted skiplist how can we count the occurences if it is sorted on a effective way? Occurence of the same element in the skiplist?

# Answer
Suppose the skip list is constructed with probability parameter $p$. Suppose you want to find the number of occurrences of an element $e$ in the skip list.

Algorithm: Perform a standard search of $e$ in the skip list. Suppose, the element is found at level $i$. Then, the element must also appear in each of the levels from $1$ to $i$ since a level $j$ is a subset of level $i$ if $j \< i$.

To count the number of occurrences of the element at any such level, the algorithm makes a linear scan to left and right from the current position. Since each level is sorted, the algorithm stops once it finds an element different from $e$. This takes time $O(p\_j)$, where $p\_j$ is the number of occurrences of element $e$ at $j^{th}$ level.

Overall time is: search time + $\sum\_{j = 1}^{i} O(p\_j)$ = search time + $p\_{e}$, where $p\_e$ is the total number of occurrences of element $e$ in the skip list.

If the element $e$ has $t$ copies in the input set, then the expected number of times it appears in the skip list is $t /p$. That is $\mathbb{E}\[p\_e\] = t/p$. Also, the expected search time in a skip list is $O(\frac{1}{p} \cdot \log\_{1/p} n)$. Therefore, the overall search time becomes $O(\frac{1}{p} \cdot \log\_{1/p} n) + O(t/p)$.
> 1 votes

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


# Question
Title: Topological sort with minimum maximal distance in array
I have a DAG that admits many possible topological sorts. I want to construct one that has the minimum maximum distance between a node and its neighbours in an array storing the nodes in sorted order.

Does this problem have a name that I can search (minimum maximum distance topological sort didn't turn up anything)?

(If the problem is NP-hard, a good heuristic will do too.)

# Answer
The measure you are trying to minimize is called (directed) bandwidth. Finding a minimum directed bandwidth ordering is NP-hard.
> 6 votes

---
Tags: graphs, terminology, np-hard, topological-ordering
---


title: A one-pass heavy hitter algorithm

text:
# Question
Title: A one-pass heavy hitter algorithm
I was shown this problem from a class last year and I am still not sure what the right answer is.

Items that occur with high frequency in a dataset are sometimes called heavy hitters. Accordingly, let us define the HEAVY-HITTERS problem, with real parameter $\varepsilon\>0$, as follows. The input is a stream $\sigma$. Let $m, n, f$ have their usual meanings. Let $$ \mathrm{HH}\_{\varepsilon}(\sigma)=\left\\{j \in\[n\]: f\_{j} \geq \varepsilon m\right\\} $$ be the set of $\varepsilon$-heavy hitters in $\sigma$. Modify Misra-Gries to obtain a one-pass streaming algorithm that outputs this set "approximately" in the following sense: the set $H$ it outputs should satisfy $$ \mathrm{HH}\_{\varepsilon}(\sigma) \subseteq H \subseteq \mathrm{HH}\_{\varepsilon / 2}(\sigma) $$ Your algorithm should use $O\left(\varepsilon^{-1}(\log m+\log n)\right)$ bits of space.

How can you do this?

I found a paper by Manku and Motwani but it isn't a modification of Misra-Gries as far as I can see. From the stated complexity it looks like you should set $k=\frac{1}{\epsilon}$ and run a constant number of copies of Misra-Gries but I can't get that to work.

# Answer
Choose $k = 2/\epsilon$, and output all items satisfying $\hat{f}\_j \geq \frac{\epsilon}{2}m$.

The final estimates satisfy $$ f\_j - \frac{\epsilon}{2} m \leq \hat{f}\_j \leq f\_j. $$ If $j \in \mathrm{HH}\_\epsilon(\sigma)$ then $\hat{f}\_j \geq \epsilon m - \frac{\epsilon}{2} m = \frac{\epsilon}{2} m$, and so we output $j$. Conversely, if we output $j$ then $f\_j \geq \hat{f}\_j \geq \frac{\epsilon}{2} m$, and so $j \in \mathrm{HH}\_{\epsilon/2}(\sigma)$.
> 2 votes

---
Tags: streaming-algorithm
---


# Question
Title: Binary Tree as 2D array with variable length raws
Usually we use the tree data structure when we care about time complexity for ins/del/...

-In this special case problem, space saving is mandatory too that is 2 pointers for each node is unaffordable; actual data are in leaves so infact even the internal nodes are considered overhead

-So, I thought of storing it as a 2D array with variable row size, we can assume the tree is almost always full complete power of 2, something like

R\[0\]= N leaf nodes

R\[1\]= N/2 level-1 nodes

R\[2\]= N/4 nodes

.. ..

R\[logN\]= root

-I can derive the formulas for del/ins/... as the tree is easily mind-vewable from this presentation, without any pointers at all.

-Now, did I miss something???

-Is there any flaw in this?

-I'm checking for brainstorming or some opinions.

# Answer
Whether or not this is an efficient representation depends on what the binary tree means. A heap (in the priority queue sense) uses precisely this idea to represent a binary tree with an array.

The situation would be a little more difficult if you needed to implement, say, a dynamic binary search tree this way. A full binary search tree represented as an array is essentially the same thing as a sorted array.
> 1 votes

# Answer
I think I found a confirmation to my method from this MIT lecture about heaps (although it is not heaps the solution, but it is mentioned in the lecture) From PDF lecture 8 in here https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2020/lecture-notes/index.htm

You can find he specifically says when we want to save the pointers space of a full binary tree, we can store it as an array & access it using the following equations

Only, I made it variable size 2D array to make it more easy to visualize the tree view, besides it's more easier to fetch proofs this way; a detail specific to our problem

(and reversed their order, in my presentation R\[0\] contain the leaves, in his representation R\[0\] is the root), and thus my equations are just a little different, but the idea is still the same
> 0 votes

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


# Question
Title: Oldest publication of the lower bound on comparison sort
We all know that the worst case complexity for comparison sort is in $\Omega(n\log(n))$, but who was the first to publish this?

Everywhere I look, people have their own proofs but no reference to the original. A lot of them talk about Shannon Entropy which was published in 1948.

# Answer
Check this paper: A Tournament Problem published in 1959. The authors show $\Omega(n \log n)$ lower bound for ranking of objects by means of pairwise comparisons.

CLRS cites this in Chapter Notes of Chapter 8.
> 0 votes

---
Tags: history
---


# Question
Title: Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T
Given a set of numbers, S {s1, s2, ... sn} and a value T, I am looking to determine if any three elements in the set add up to value T. It is valid to have repeats like 2+2+2 would be fine for achieving a goal value of T=6. This is ultimately a decision problem of whether such a trio of values exists within the set that add up (with allowing repeats) to the target value.

The goal is to use FFT as a blackbox for solving the problem. I am at a complete loss here. How can FFT be used as a black box to solve subset sum?

# Answer
For a set $S = \\{s\_1,\dotsc,s\_n\\}$. Construct a polynomial $P(x): x^{s\_1} + x^{s\_2} + \dotsc + x^{s\_n}$.

Multiply the polynomial by itself three times, i.e., $P(x) \cdot P(x) \cdot P(x)$. Let this polynomial be $Q(x)$

**Claim:** The coefficient of $x^T$ in $Q(x)$ is non-zero if and only if there exist three values in $S$ that sum to $T$.

**Proof:** \[You may want to try it by yourself\]
> 3 votes

---
Tags: algorithms, divide-and-conquer, subset-sum, polynomial-time-reductions, fast-fourier-transform
---


# Question
Title: How is a histogram implemented as a data structure?
I'm reading a paper about O(1) median filtering. I'm confused how histograms, denoted H, have the properties described. How can histograms be implemented such that: summing histograms, H(A ∪ B) = H(A) + H(B), is a O(1) operation with respect to the number of accumulated \[points\]?

# Answer
As the paper says:

> "Notice that summing histograms is a O(1) operation with respect to the number of accumulated pixels. It depends only on the size of the histogram, which is itself a function of the bit depth of the image".

For example, for a 8-bit image, there are only 256 possible values for the pixel intensity, so the histogram is of size at most 256, regardless of the width or height of the image. So, you can sum two such histograms with only 256 operations, regardless of the width or height of the image.
> 0 votes

---
Tags: data-structures
---


title: simplified into asymptotic notation

text:
# Question
Title: simplified into asymptotic notation
I have a function that needs to be represented in theta form. The below is my answer.
But the correct answer is **(n.2^n)**

Can someone please explain me how??

# Answer
> 1 votes
Assuming $\log=\log\_2$, we have $$2^{n+\log\_2 n}=2^n \cdot 2^{\log\_2 n}=n \cdot 2^n$$ where we used main property(or definition) of $\log$: $a^{\log\_a b}=b$, for appropriate $a,b$.

---
Tags: algorithms, algorithm-analysis, big-o-notation
---


# Question
Title: How to traverse a graph in reverse dfs order
For kosaraju's algorithm to traverse the graph in reverse order the naive solution is to reconstruct the original input graph in reverse order and dfs on it. Is there any way I can avoid creating copy of the graph in reverse order? how can I dfs on the same original graph going back across the edges?

# Answer
The only solution I came up with is at the expense of the algorithm's neat linear complexity.

This could still be useful if you need to save up on resources at the expense of running time.

The idea is:

* At every time you land on a new node A, you go through all of the "not-visited" nodes.
* For each node you check if there is an edge that goes from that node B to the current node A.
* If there is such edge B -\> A, then DFS(B) using this same approach.
> 1 votes

---
Tags: algorithms, graphs, search-algorithms, graph-traversal
---


# Question
Title: The interpretation of expected time bound for searches in a hash table
As CLRS book,page 260 stated,

> Thus, the total time required for a successful search is $\Theta{\left(2+\alpha/2-\alpha/2n\right)}=\Theta{(1+\alpha)}$

I wouldn't have any problem if the author says the bound is eventually $\Theta{(2+\alpha/2-\alpha/2n)}$ or even $\Theta{(1+\alpha(1-\frac{1}{n}))}$. What kind of logics shall we apply to simplify the original result, i.e, cancelling the factor $1/n$ of $\alpha$. What i've missed? is anyone got the same confusion?

# Answer
> 0 votes
It is easy to see that $\Theta(2 +\alpha/2 - \alpha/2n) \subseteq O(2+\alpha/2) \subseteq O(1+\alpha)$

For the other direction, note that $\alpha = \frac{n}{m}$, where $m$ is the size of the table and $m \geq 1$. Therefore, $\alpha/2n \< 1/2$. It gives $\Theta(2 +\alpha/2 - \alpha/2n) \subseteq \Omega(3/2+\alpha/2) \subseteq \Omega(1+\alpha)$.

Therefore, $\Theta(2 +\alpha/2 - \alpha/2n) = \Theta(1+\alpha)$

---
Tags: algorithms, time-complexity, efficiency, hash-tables, big-o-notation
---


# Question
Title: Algorithm to find approximate position of element from a noisy sorted list
Let's have a static function f(n) which for a given n returns only these answers "lower" or "higher" comparing against an imaginary number x

In a sorted list `l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]` It is obvious that using binary search we can find the position of the element in O'log(n) time.

Now let's have a sorted list but with some noise (somewhat sorted) `l = [1, 2, 4, 3, 5, 6, 9, 7, 8, 11, 10, 12, 13, 16, 15, 14, 17, 20, 19, 18]`

I'm looking for an algorithm that converges quickly to the approximate position of the imaginary x. I do have an algorithm (a modified binary search, relaxing the boundaries each side, performing at logn), Just wanted to hear from fresh perspective from other people.

Expectation: It is not allowed to sort the list, because the dataset is not sortable in a practical way.

The motivation to this question is, I'm writing a guessing game, containing list of publicly soured words sorted by popularity, the objective of the computer is to guess the number of words the player knows by asking as little questions as possible, where the player would respond "know" or "don't know", hence it's important for the algorithm to converge quickly

# Answer
> 1 votes
This is simply a heuristic.

Instead of comparing the element $e$ to the middle element at position $m$, compare it with each of the elements in range $m-c$ to $m+c$, for some constant $c$ say $5$ or $10$.

1. If $e$ is smaller than the majority (approximately) of the elements in this range, move recursively to the left.
2. If $e$ is larger than the majority (approximately) of the elements in this range, move recursively to the right.
3. If the majority does not happen, the algorithm is already at an approximate position.

---
Tags: algorithms, binary-search, searching
---


title: Step size choice with l-bfgs

text:
# Question
Title: Step size choice with l-bfgs
I'm trying to implement L-BFGS but I can't quite figure out how to do step sizes. I tried small fixed step sizes, but for some reason the iterates always explode whenever memory \< variable size (which is kind of the whole point). So I thought I'd try some back tracking line search.

My issue is, I don't want to re-evaluate the function or gradient, because those are the most expensive steps. I have all the current iterates $g$ gradient, $s=x-x\_{prev}$, $y=g-g\_{pref}$, $H^{-1} y$, $H^{-1} g$ etc available, and I can do operations of order of the variable size.

Are there any line search methods that can be used especially for this purpose, that basically don't require recomputing any function, gradient, or hessian for the intermediate points?

Thanks!

# Answer
Suppose in one step of BFGS: compute $p\_k$ such that $B\_{k}p\_{k} = -grad(f)$ $x\_{k+1} = x\_{k}+\alpha\_{k}\*p\_{k}$ where $\alpha\_k$ is determined by Wolfie Condtion. Maybe you can check it here:https://en.wikipedia.org/wiki/Wolfe\_conditions
> 0 votes

---
Tags: algorithms, optimization
---


# Question
Title: What is the sequence that is computed by a Turing machine?
so I was wondering how to know the sequence a Turing machine T computes?

We are reading The Annotated Turing by Charles Petzold at the moment which includes Turing's original paper "On Computable Numbers, with an Application to the Entscheidungsproblem" and adds explanations.

As far as I understand we are looking at circle-free machines, i.e. they will print down more than a finite numbers of symbols of the first kind (which means 0 and 1s).

So there is no end when we can say: "The sequence that is now on the band is the sequence the Turing machine computes". But when are we taking this "snapshot" then? When do we know e.g. that the first digit is "permanent" and that it is the first digit of the sequence that the machine is computing? Maybe the TM writes a million digits and then changes the first digit.

What is about a Turing machine that forever first prints a 0 and then without moving the head prints a 1 and so on? What sequence does this TM compute?

I am sure this question has already been asked but cannot find it so I would also be very thankful for links.

# Answer
> How to know the sequence a Turing machine T computes?

Sometimes it's impossible to directly and instantaneously "know" a number, even if it is computable. To say that a machine T *computes* a number means that it will keep on writing an increasingly large sequence of its digits, properly, when put to work. For many numbers the ability to produce such a machine (or something comparable) is the best thing we have in terms of "knowing", or representing them. You will see that this puts a limit on what can be done with numbers, operationally.

> What is about a Turing machine that forever first prints a 0 and then without moving the head prints a 1 and so on? What sequence does this TM compute?

A Turing machine doesn't have to do anything meaningful. Arguably, most of them don't. In fact, there isn't a way of classifying them, or studying them systematically, that doesn't have significant holes. Any "science of Turing machines" will be incomplete - in a nutshell, this is what the paper contends.
> 0 votes

---
Tags: turing-machines, computability
---


# Question
Title: A problem about the midpoint ellipse algorithm
I have read the book "Computer Graphics with Open GL" (Hearn, Fourth Edition) recently. However, when I read the midpoint ellipse algorithm, the following example in the book is confusing me:

> For region 2, the initial point is $(x\_0,y\_0) = (7,3)$ and the initial decision parameter is $$p2\_0 = f\_{\text{ellipse}}\Big(7 + \frac{1}{2}, 2 \Big) = -151$$

in which $f\_{\text{ellipse}}(x,y) = r^2\_y x^2 + r^2\_x y^2 - r^2\_x r^2\_y$.

When I fed the value into the formula mentioned above, eventually, I get -23. Therefore, is the result given in this example wrong?

# Answer
> -1 votes
I've got a test tomorrow and just happened to come across this question today. I think the answer given might be incorrect and -23 is the correct value the equation returns. Just to cross-check, are the consecutive decision parameter values 361 and 297? Irrespective, the values are such that the coordinates generated would be identical.

---
Tags: graphics
---


title: K-Path-Problem is in $P$ or $NPC$

text:
# Question
Title: K-Path-Problem is in $P$ or $NPC$
> Given an undirected graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of at least length $k$ exists between these two vertices?

How can we solve this problem? I think maybe that it's in $NPC$ with a reduction of HamiltonPath but I'm not sure.

# Answer
> 1 votes
This problem is $\textsf{NP}$-complete. This is more or less the longest path problem.

---
Tags: graphs, np-complete, np
---


title: interactivity between RAM and CPU

text:
# Question
Title: interactivity between RAM and CPU
I have a very silly question, when data is transferred from the RAM to the CPU is this data transferred "copies" of the original data stored inside the RAM?

# Answer
> 1 votes
Yes, I think it's reasonable to consider that as a copy of the data in the RAM. It's a copy in the sense that if you modify the data in the CPU, the data in RAM remains unchanged.

(But at the end of the day it doesn't really matter what you call it: the computer is going to do what it does, regardless of what words you use to describe it.)

# Answer
> 0 votes
Yes, I guess you could say that as if you change data in CPU, even then, the data in RAM will be same.(IF it has not been erased due to some reason)

---
Tags: cpu
---


# Question
Title: Algorithms question: Largest contiguous subset selection
Q. Given two arrays, $A$ and $B$, of equal length, find the largest possible contiguous subset of indices $\[i,j\]$ such that $\max(A\[i: j\]) \< \min(B\[i: j\])$.

Example: $A = \[10, 21, 5, 1, 3\], B = \[3, 1, 4, 23, 56\]$.

Explanation: $A\[4\] = 1, A\[5\] = 3$, $B\[4\] = 23, B\[5\] = 56$, $\max(A\[4\], A\[5\]) \< \min(B\[4\], B\[5\])$.

The indices are $\[4,5\]$ (inclusive), and the largest contiguous subset has size 2.

I can do this in $O(n^2)$ brute force method but cannot seem to reduce the time complexity. Any ideas?

# Answer
O(n) solution:

Move index `j` from left to right and drag `i` behind so that the window from `i` to `j` is valid. So always increase `j` by 1, and then increase `i` as much as needed for the window to be valid.

To do that, keep a queue `Aq` of indexes of non-increasing A-values. Then `A[Aq[0]]` tells you the max A-value in the window. Similarly, keep a queue for non-decreasing B-values.

For each new `j`, first update `Aq` and `Bq` according to the new A-value and new B-value. Then, while the window is invalid, increase `i` and drop `Aq[0]` and `Bq[0]` if they're `i`. When both `j` and `i` are updated, update the result with the window size `j - i - 1`.

Python implementation:

```
def solution(A, B):
    Aq = deque()
    Bq = deque()
    i = 0
    maxlen = 0
    for j in range(len(A)):
        while Aq and A[Aq[-1]] < A[j]:
            Aq.pop()
        Aq.append(j)
        while Bq and B[Bq[-1]] > B[j]:
            Bq.pop()
        Bq.append(j)
        while Aq and A[Aq[0]] >= B[Bq[0]]:
            if Aq[0] == i:
                Aq.popleft()
            if Bq[0] == i:
                Bq.popleft()
            i += 1
        maxlen = max(maxlen, j - i + 1)
    return maxlen

```

Test results from comparing against a naive brute force reference solution:

```
expect:  83   result:  83   same: True
expect: 147   result: 147   same: True
expect: 105   result: 105   same: True
expect:  71   result:  71   same: True
expect: 110   result: 110   same: True
expect:  56   result:  56   same: True
expect: 140   result: 140   same: True
expect: 109   result: 109   same: True
expect:  86   result:  86   same: True
expect: 166   result: 166   same: True

```

Testing code (Try it online!)

```
from timeit import timeit
from random import choices
from collections import deque
from itertools import combinations

def solution(A, B):
    Aq = deque()
    Bq = deque()
    i = 0
    maxlen = 0
    for j in range(len(A)):
        while Aq and A[Aq[-1]] < A[j]:
            Aq.pop()
        Aq.append(j)
        while Bq and B[Bq[-1]] > B[j]:
            Bq.pop()
        Bq.append(j)
        while Aq and A[Aq[0]] >= B[Bq[0]]:
            if Aq[0] == i:
                Aq.popleft()
            if Bq[0] == i:
                Bq.popleft()
            i += 1
        maxlen = max(maxlen, j - i + 1)
    return maxlen

def naive(A, B):
    return max((j - i + 1
                for i, j in combinations(range(len(A)), 2)
                if max(A[i:j+1]) < min(B[i:j+1])),
               default=0)

for _ in range(10):
    n = 500
    A = choices(range(42), k=n)
    B = choices(range(1234), k=n)
    expect = naive(A, B)
    result = solution(A, B)
    print(f'expect: {expect:3}   result: {result:3}   same: {result == expect}')

```
> 3 votes

# Answer
You can solve the problem in $O(n \log n)$ time. Construct a data structure $D\_A$ that can answer queries of the following form in constant time: given two indices $i \in \\{1,\dots,n\\}$ and $j \in \\{i,\dots,n\\}$, report $\max\_{h=i,\dots,j} A\[h\]$. This can be done in time $O(n)$. Similarly, construct a data structure $D\_B$ that can report $\min\_{h=i,\dots,j} B\[h\]$. Have a look at this paper for details.

For each index $i=1,\dots, n$ such that $A\[i\]\<B\[i\]$, find the largest index $j \ge i$ such that $M\_i(j)=\max\_{h=i,\dots,j} A\[h\] $ is smaller than $m\_i(j) = \min\_{h=i,\dots,j} B\[h\] $. You can do so by noticing that $M\_i(\cdot)$ is monotonically non-decreasing while $m\_i(\cdot)$ is monotonically non-increasing. This implies that $\forall j' \le j, M\_i(j')\<m\_i(j')$ and that $\forall j'\>j, M\_i(j') \ge m\_i(j')$. As a consequence you can use binary search to find $j$ with only $O(\log n)$ queries to $D\_A$ and $D\_B$. Consider $(i,j)$ as a candidate solution.

Finally, among all the candidate pairs $(i,j)$, return one of those that maximize $j-i$ (if any).
> 0 votes

# Answer
The idea is once you have parsed a part of the 2 arrays and got a subsequence *i,j* then no go through it again as we already know the result

*A\[i-j\]≤B\[i-j\]* (that what kept the loop going)

and *A\[j+1\]\>B\[j+1\]* (that what stopped it)

Then we keep the length of this interval in a variable, say *max* and start checking for a longer sequence starting from *j+2*

A Pseudocode could be

i=j=0;

N= array\_size;

While(i\<N)

{

While (A\[j\]≤B\[j)AND(j\<N) j++;

*//now A\[j\]\>B\[j\]*

If ((j-i) \> max) { Res.str=i; Res.end=j-1;}

i=j+1;

}
> 0 votes

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


# Question
Title: Greedy approach behind SPOJ Aggressive Cows problem
My doubt is related to the given SPOJ problem:

> Farmer John has built a new long barn, with N (2 \<= N \<= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 \<= xi \<= 1,000,000,000).
>
> His C (2 \<= C \<= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ wants to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

I was able to come up with idea of using Binary Search but struggled with the positioning of the cows. After watching some solutions like this one , almost all of them were placing the first cow at the first stall stating its a greedy approach which works.

I am unable to understand what exactly are we being greedy about as what matters to us is the distance between the cows and not where the cows are placed(i.e we can place 3 cows in the two valid given orders where both give a minimum distance of 2 `[1,4,6]`and `[4,6,10]`)so what is the necessity of placing the first cow at first position.

Also even if there is some reason behind this approach ,how does it guarantee that for a chosen distance `dist` if we can't place the given number of cows (the fist cow being placed at first stall)with `dist` as the minimum distance then there is no other way of placing the cows(the order in which placing starts from any stall) which would satisfy the conditions.

# Answer
Suppose the choosen distance is `dist`. That is, the separation between every cow should be at least `dist`.

Suppose the stalls are at located at positions: $s\_1, \dotsc,s\_n$, in sorted order. And suppose there is a feasible solution that places the cows at stalls: $s\_{l\_{1}}, s\_{l\_{2}}, \dotsc, s\_{l\_{C}}$ (in sorted order) such that distance between cows is at least `dist`

**Observation:** In the above solution, if $s\_{l\_{1}} \neq s\_1$, then we can always place the cow at location $s\_1$; the distance between the cows will only increase. In other words, the solution stays feasible.

Therefore, there always exists **a** solution where a cow is placed at $s\_1$ given `dist` is feasible.

---

Now, for the cow at $s\_{l\_{2}}$ you can shift it to the left till the distance between it and $s\_{1}$ does not become less than `dist`. Use the above observation inductively, to see why this correct. The same logic holds for the subsequent cows. I leave the details to you.
> 1 votes

---
Tags: greedy-algorithms, binary-search
---


title: inversions in array

text:
# Question
Title: inversions in array
If the worst case arrays {5 4 3 2 1} have number of inversions as Θ(n^2) =\> n(n-1)/2 swaps
The best case arrays {1 2 3 4 5} have number of inversions 0(no swap)

What kind of arrays have number of inversions Θ(n)?

{2 1 3 4 5} can this be an array with number of inversions Θ(n) as there will be only 1 swap.

# Answer
> 1 votes
For example, if to place the minimal element into the maximal position, you'll get $n-1$ inversions:

$${2,3,4,5,1}$$

For more information please see here.

# Answer
> 1 votes
Number of permutations of length $n$ with $k$ inversions refers to so called Mahonian numbers $T(n,k)$ who are generated by coefficients from expansion $$\prod\limits\_{i=0}^{n-1} (1 + x + ... + x^i)$$

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: If P!=NP, does there exist infinite hierarchy of languages between P & NP?
This looks to me as some tweaking or generalization of Ladner's result on NP-I languages, can some help me in the right direction? or redirect me to some sources where this generalization is explicitly proven?

# Answer
> 3 votes
$\def\P{\mathbf P}\def\NP{\mathbf{NP}}$This already follows from Ladner’s original paper

> Richard E. Ladner: *On the Structure of Polynomial Time Reducibility*, Journal of the ACM 22 (1975), no. 1, pp. 155–171, doi 10.1145/321864.321877.

Theorem 1 in Ladner’s paper states:

> If $B$ is computable and not in $\P$ then there exists a computable $A$ such that $A\notin\P$, $A\le^\P\_mB$, and $B\nleq^\P\_TA$.

Assuming $\P\ne\NP$, you can apply it to $B=L\_0=\mathrm{SAT}$ to obtain $L\_1=A\notin\P$ such that $L\_1\lneq^\P\_mL\_0$, i.e., $L\_1\in\NP$ and $L\_1$ is not $\NP$-complete. But you can now iterate this process: taking $L\_1$ as the new $B$, you obtain $L\_2\notin\P$ such that $L\_2\lneq^\P\_mL\_1$, etc., obtaining an infinite sequence of $\NP$-languages strictly decreasing w.r.t. poly-time reducibility: $$\mathrm{SAT}=L\_0\gneq^\P\_mL\_1\gneq^\P\_mL\_2\gneq^\P\_mL\_3\gneq^\P\_mL\_4\gneq^\P\_m\dots$$

---
Tags: complexity-theory
---


# Question
Title: Calculating minimal discriminator of a set of columns in a matrix with unique rows
Having a matrix $M$, with unique rows, how to calculate a minimal subset of colums $D$ such that every row is unique? Also, how to maximize the amount of unique rows, if the number of chosen columns is limited?

For example:

$M$ =

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

```

$D$ (columns {4, 6} from $M$) =

```
0 1
0 2
1 0
2 0

```

It seemed like a Bounded Knapsack Problem at first, but the weights of each item in knapsack depends on other items, so it's not a classical knapsack problem.

Is there a known solution for this problem?

# Answer
The problem is NP-hard by a straightforward reduction from the problem of finding a discriminating code in a bipartite graph.

Let if $G=(I \cup A, E)$ is the bipartite graph with $I = \\{i\_1, \dots, i\_n\\}$ and $A=\\{a\_1, \dots, a\_m\\}$, you can create a matrix $M$ with $n$ rows and $n$ columns. The entry on the $j$-th row and $k$-th column is $1$ if $(i\_j, a\_k) \in E$ and $0$ otherwise.

A minimum discriminator of $M$ induces discriminating code of $G$ having the same size, and vice-versa.
> 1 votes

---
Tags: time-complexity, knapsack-problems
---


# Question
Title: What is the meaning of the pipe symbol here?
I am reading Distributed Algorithms by Nancy Lynch. In chapter 16, I came across the pipe symbol. Does this mean the same as "or" in some programming languages or could someone explain that line please?

# Answer
> 3 votes
Its a standard notation in mathematics, called the set-builder notation.

Basically, it means: "the set of all $(m,i)$ such that $(m,j)\in T$".

---
Tags: algorithms, automata, discrete-mathematics, distributed-systems
---


# Question
Title: If $A\leq_P B$ and $B\in \text{NP}$, is $A\in \text{NP}$?
Let $A\leq\_P B$ mean that the language $A$ is polynomial time reducible to $B$. It is a theorem that $A\leq\_P B$ and $B\in \text{P}$ then $A\in \text{P}$.

My question is, if $A\leq\_P B$ and $B\in \text{NP}$, is $A\in \text{NP}$? What if $B$ is $\text{NP}$-complete?

# Answer
If $A \le\_p B$ and $B \in \mathsf{NP}$ then $A \in \mathsf{NP}$.

A non-deterministic polynomial-time Turing machine that decides $A$ works as follows:

* Reduce the input instance $I\_A$ of $A$ to an instance $I\_B$ of $B$ using the polynomial-time reduction from $A$ to $B$.
* Simulate a nondeterministic polynomial-time Turing machine that decides $B$ on input $I\_B$ (such a Turing machine exists since $B \in \mathsf{NP}$).

If $B$ is $\mathsf{NP}$-complete then it is still true that $A \in \mathsf{NP}$ since all $\mathsf{NP}$-complete are in $\mathsf{NP}$. It is not necessarily true that $A$ is $\mathsf{NP}$-complete. As a counterexample choose $A = \emptyset$ and $B$ as the language of satisfiable SAT instances. Notice that this does not require the assumption $\mathsf{P} \neq \mathsf{NP}$.
> 1 votes

---
Tags: complexity-theory, np, polynomial-time
---


# Question
Title: How can an instruction be fetched every cycle?
From what I understand, in a pipelined CPU, every stage takes 1 cycle. But instructions are fetched from memory which takes up to ~150 cycles. The CPU fetches most instructions from the L1-cache, but I've read that it takes around 4 cycles. From that logic, a new instruction should only start every 4th cycle, which obviously makes no sense?  This diagram shows a new instruction starts every cycle.

So, how does the CPU fetch a new instruction every cycle, if it takes more than one cycle to even fetch an instruction?

# Answer
> 3 votes
> So, how does the CPU fetch a new instruction every cycle, if it takes more than one cycle to even fetch an instruction?

It could be done by starting the next fetch before the previous one completed.

An L1 hit may "take around 4 cycles", but the number that is thrown around a lot is the load-use latency of hitting the L1D cache and then using the result in an ALU operation (which isn't representative nor predictive of what goes on in the front-end of a processor), and it normally refers to architectures that have a significantly longer pipeline the one that the diagram in your question is for. If the diagram shows a single cycle FI stage, I'm inclined to believe it: that architecture probably fetches an instruction in a single cycle (which was, and still is, a normal thing for architectures that aren't "super-pipelined"), otherwise the diagram should show more fetch stages.

The kind of architecture which that "4 cycles" figure is about, look more like this (actually the load-use latency is only 3 cycles here, but you get the idea):

How long the I-cache access takes is not so clear from this diagram, but I argue that it should be at most 3 cycles and possibly less, because after 3 cycles there is an arrow going down to the decoders and by that time the instruction data should be available, otherwise there would be nothing to decode. But how long the cache access takes is not that important (well it is important, but it's not as bad as limiting fetches to on in k cycles where k is the cache latency), whether it takes 1 or 2 or 3 cycles, one access can happen every cycle, so when all goes well the pipeline can stay full.

---
Tags: cpu, cpu-cache, cpu-pipelines, instruction-set
---


# Question
Title: Inversions of Insertion Sort and Bubble Sort
An array with bubblesort time $\Theta(n)$ is nothing but a sorted array like: A = 1 2 3 4 5
No swaps are done so only $n - 1$ comparisons.
An array with insertionsort run time $\Theta(n^2)$ is a reverse sorted array: A = 5 4 3 2 1
Each element is swapped in every iteration.
There cannot be any array that can have IS time as $\Theta(n^2)$ and BS time as $\Theta(n)$.
But how can i prove this in terms of their inversions?

# Answer
> 1 votes
Let's consider the swaps performed by insertion sort. In the $i$-th iteration, insertion sort repeatedly swaps the element $x$ originally in $A\[i\]$ with some element $y$ originally in $A\[1:i-1\]$ until the subarray $A\[1:i\]$ is sorted. Then, since we must have $x\<y$ for the swap to occur, we have that each swap induces an inversion in the original array. Notice that the $i$-th iteration takes time proportional to $1+s\_i$ where $s\_i$ is the number of swaps in the iteration.

If follows that insertion sort takes time $O(n+\sum\_{i=1}^n s\_i) = O(n + s)$, where $s$ is the number of inversions of $A$. Thus, when insertion sort takes time $\Omega(n^2)$ we must have $s=\Omega(n^2)$.

Finally, notice that at most one inversion can be removed by each swap performed by bubble sort, implying that bubble sort takes time $\Omega(s)=\Omega(n^2)$.

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: What is the name of a sequence structure where writes in the same area are faster?
I recall reading about a data structure for sequences where writes in the same area are faster due to some kind of caching or structure manipulation. What are some structures that do this? I know a gap buffer is one of them (kind of), but are there any others?

# Answer
At the data structure level, this is called a "finger". You might be looking for "finger search trees":

https://cs.au.dk/~gerth/papers/finger05.pdf
> 0 votes

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


# Question
Title: I made bubble_sort() function following the algorithm. But it is not working. where is my error?
This was the algorithm for bubble sort in textbook.

I tried the with WHILE loop, then I tried the same with the for loop. My answer is not sorted. Why? I follow the above algorithm in Python 3.0.

**My attempt**

Step1: I created a swap() function. it was working perfectly. Step2: I made bubble\_sort() function following the algorithm. But it is not working. May I get help?

# Answer
> 1 votes
This one seems to be working well for me. Try out without the swap function.

---
Tags: sorting, python
---


# Question
Title: Figuring out the equivalence between two definitions of "transitive functional dependencies" and intuition behind the intended meaning of definition
The definition given below is present in the exercise of the text *Database System Concepts* by *Korth et. al.*

> **Let $\alpha$ and $\beta$ be sets of attributes such that $\alpha \rightarrow \beta$ holds, but $\beta \rightarrow \alpha$ does not hold. Let $A$ be an attribute that is not in $\alpha$, is not in $\beta$, and for which $\beta → A$ holds. We say that $A$ is transitively dependent on $\alpha$ .**

The definition given below is from the text *Fundamentals of Database Systems* by *Navathe et. al.*

> **A functional dependency $X → Y$ in a relation schema $R$ is a transitive dependency if there exists a set of attributes $Z$ in $R$ that is neither a candidate key nor a subset of any key of $R^\dagger$ and both $X → Z$ and $Z → Y$ hold.**
>
> $\dagger:$ This is the general definition of transitive dependency. Because we are concerned only with primary keys in this section, we allow transitive dependencies where $X$ is the primary key but $Z$ may be (a subset of) a candidate key.

The above two definitions are not exactly the same apparently. Now with the analogy of mathematical relations, I get the rough idea that if $X\rightarrow Z$ and $Z\rightarrow Y$ are functional dependencies then $X\rightarrow Y$ is a transitive functional dependency. \[Just as we have in mathematics $(a,b)\in R$ and $(b,c)\in R$ and if a relation is transitive then we have $(a,c)\in R$.\] But the thing is that, here these $X$, $Y$ and $Z$ have some added conditions to them. But in the definitions given in *Navathe text* and *Korth text* these conditions seem different.

The first definition says that if $\alpha \rightarrow \beta$ holds then $\beta \rightarrow \alpha$ should not hold. Also, $A$ should not be a part of either $\alpha$ or $\beta$. While the second definition talks about $Z$ being neither a candidate key nor a subset of a candidate key. Neither can I figure out the equivalence between them, \[except that if $Z$ is not candidate key, then if $X\rightarrow Z$ then $Z \rightarrow X$ should not hold\] nor the intuition behind these conditions.

# Answer
Let first introduce a third definition of transitive dependency.

The fundamental idea of a transitive dependency is that you have a “cascade” of two “proper” functional dependencies `X -> Z` and `Z -> Y` in the same relation scheme. Let’s define exactly what I mean for “cascade of proper FDs”.

First, we want to exclude the case in which `X` and `Z` are “equivalent”, that is in which `X -> Z` and `Z -> X`. This is because if they are equivalent, it is safe to consider that `Z -> Y` is perfectly equivalent to `X -> Y`, so we can say that this is not really a transitive dependency (a “cascade of proper dependencies”). Note that this means also that `Z` cannot contain a candidate key, otherwise we will have that `Z -> X`.

Then, we want to exclude also the dependencies which are trivial, or in which `Y` contains at least an attribute which belongs to `X` or `Z`. Such dependencies in a certain sense are not “proper”, because the information contained in the dependency `AB -> AC` is perfectly equivalent to that contained in the dependency `AB -> C` (since `A` is obviously equal).

This is the basic definition of transitive dependency.

The main differences between the two definitions are so the following:

1. The first one considers dependencies with a single attribute in the right part, while in the second `Y` can be a set of attributes. As we have seen, this is not really an important difference, but can produce slightly different definitions.
2. The first definition takes into account trivial dependencies, while the second one ignore them (maybe this is said before the definition).
3. The first definition includes implicitly the fact that  (in my definition `Z`) is not a candidate key, otherwise we will have  `->` , while it do not say anything about the possibility that it contains only a subset of a candidate key. This is a real difference between the two definitions. I think that this constraint in the second definition is tied to the fact that the definition of transitive dependency is used in the definition of normal forms. Note that in one of the first paper on the subject, Bernstein, Philip A. “Synthesizing Third Normal Form Relations from Functional Dependencies.” ACM Transactions on Database Systems 1, no. 4 (1976): 277–98, the definition of transitive dependency is equivalent to that of the first book.
> 1 votes

---
Tags: database-theory, databases
---


# Question
Title: Are there infinitely many distinct implementations of any algorithm using any Turing-complete computational model?
Subject pretty much says it all. My strong impression is that for any algorithm and any choice of programming language or computational model, if it's Turing-complete, then there must be infinitely many ways to implement the algorithm such that a fixed interpreter for the language will necessarily return the same output, even if this is essentially just a matter of adding NOOP equivalents to the code.

Is this provably true, false, or unknown? And if applicable, can someone point me towards relevant keywords, in particular if this is an established theorem or conjecture?

# Answer
No sooner did I click okay on my question than a plausible answer occurred to me. Posting to make sure this makes sense.

Since any TC language must be able to simulate any other TC languages, it requires only translating any given program through a simulation in another language and back again to get a much less efficient but equivalent program. Since you could do this arbitrarily many times, or with arbitrarily many languages in whatever order, that should work as a proof sketch.
> 0 votes

# Answer
Just add nonsense operations that don't affect the result at will.
> 0 votes

---
Tags: computation-models, turing-completeness, church-turing-thesis
---


title: Array Doubling Size Strategies

text:
# Question
Title: Array Doubling Size Strategies
I would like to discuss resizing strategies for arrays please. If you have an array of $k$ initial size and it gets full, so you would like to choose from one of the following approaches:

**Approach 1**: if array get full, then we resize the array by $k$ constant.
**Approach 2**: if array get full, then we resize the array by doubling the previous size.
**Approach 3**: if array get full, then we follow $3k, 5k, 7k, 9k, \cdots$ etc resizing.

Now to compare approaches:

1. **Approach 1** is time consuming as we do resizing more frequently.
2. **Approach 2** is memory consuming.
3. **Approach 3** is most intuitive one because it adopts to higher frequency of PUSH calls.

**Problem**: How approach 3 is more intuitive compared to approach 2 please? Both are similar as I see them.

# Answer
> 4 votes
Check amortized analysis. Note that usually array resizing requires (1) get memory for new version, (2) copy old contents over, (3) delete old version. The point of your approach 2 (double the size of the array each time, more generally extend by a fixed factor) is that it gives amortized constant cost for each push on the stack. The others get costlier when the stack grows.

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


# Question
Title: Simplifying the boolean expression xy + (!x)z + yz with boolean algebra?
So using K-maps I was able to simplify xy + (!x)z + yz to xy + (!x)z, and I double-checked that the truth tables are the same.

I'm having trouble understanding how I would have used boolean algebra to get this result. I tried my usual tricks of adding zero, letting addition distribute over multiplication, etc., without avail.

Any thoughts appreciated.

Thanks.

# Answer
> 1 votes
$$ xy + \bar{x} z + yz = xy + \bar{x} z + (x+\bar{x})yz = xy + \bar{x} z + xyz + \bar{x}yz = xy(1 + z) + \bar{x} z(1 + y) = xy + \bar{x}z. $$

# Answer
> 0 votes
The Problem can be solved by **Properties of Boolean Algebra** or we also can use **Consensus Theorem** (also known as **Redundancy Theorem** in many literature)

Using **Properties of Boolean Algebra**
$xy+x'z+yz$
$xy+x'z+1.yz$
$xy+x'z+(x+x')yz$
$xy+x'z+xyz+xyz'$
$xy+xyz'+x'z+xyz$
$xy(1+z')+x'z+xyz$
$xy.1+x'z+xyz$
$xy+xyz+x'z$
$xy(1+z)+x'z$
$xy.1+x'z$
$xy+x'z$

Now, **Consensus Theorem** provides a *neat and quick* solution just by observing few things :

**If,** following requirements are fulfilled.

1. Three variables are there in Expression.
2. Each variable is repeated twice. (Either in Normal Form or in Complement Form)
3. One variable is repeated in complemented form (say X)

**Then,**
Reject the term which doesn't contain X.

In given problem, $xy+x′z+yz$

* A. Three Variables are there ($x, y$ and $z$)
* $x$ is repeated Twice ($x$ and $x'$), $y$ is repeated twice ($y$ and $y$) and $z$ is repeated twice ($z$ and $z$)
* $x$ is repeated in complemented form.

Therefore, reject term which doesn't contain $x$. Thus $yz$ is rejected.

Using same theorem $A'B'+AC'+B'C$ will be reduced to $A'B'+AC'$

---
Tags: boolean-algebra
---


# Question
Title: Proving that the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + 1$ with $T(2) = 1$ is asymptotically $O(n)$
I've already solved the recurrence exactly and found that $T(n) = n - 1$. Therefore, I know that $T(n) = O(n)$.

However, I'm having trouble showing that $T(n) = O(n)$ without solving the recurrence exactly.

My strategy so far has been to prove that $T(n) \leq cn$ ($c$ is a constant) $\forall n \geq 2$ via induction on $n$.

Clearly, the base case holds $T(2) = 1 \leq 2c$ as long as $c \geq \frac{1}{2}$.

For the inductive hypothesis (IH), I assume $\forall k \< n$, $T(k) \leq ck$.

Finally, for the inductive step, I have

$$ \begin{alignat\*}{2} T(n) &= 2T\left(\frac{n}{2}\right) + 1 &&\text{ (by definition)}\\ &\leq 2c\left(\frac{n}{2}\right) + 1 &&\text{ (by IH)}\\ &= cn + 1 \end{alignat\*} $$

However, I can't conclude that $T(n) \leq cn$ from this. Where am I going wrong?

# Answer
If you can solve a recurrence exactly, then there isn't much motivation to solve it approximately, unless the solution is much easier.

Nevertheless, here is a trick that could actually be useful. Define $$ S(n) = T(n)+1. $$ Then $$ S(n) = T(n) + 1 = 2T(n/2) + 2 = 2S(n/2), $$ and so $S(2^k) \leq 2^k S(1)$ by induction.

Let's see what this trick gives you more generally.

**Application 1**

Consider the recurrence $A(n) = 2A(\lfloor n/2 \rfloor) + (-1)^n$, with base case $A(1)$.

Define a new recurrence $T(n) = 2T(\lfloor n/2 \rfloor) + 1$, with base case $T(1) = A(1)$. Prove by induction that $A(n) \leq T(n)$. The technique above shows that $T(n) = O(n)$, hence $A(n) = O(n)$.

**Application 2**

Consider the recurrence $B(n) = 2B(\lfloor n/2 \rfloor) + \log n$, with base case $B(1)$.

Define $R(n) = B(n) + \log n$. Then $$ R(n) = B(n) + \log n = 2B(\lfloor n/2 \rfloor) + 2\log n = 2R(\lfloor n/2 \rfloor) - 2\log \lfloor n/2 \rfloor + 2\log n. $$ You can check that $2\log n - 2\log \lfloor n/2 \rfloor = O(1)$, and so the previous technique shows that $R(n) = O(n)$. It follows that $B(n) = O(n)$.

**Application 3**

Consider the recurrence $C(n) = 2C(\lceil n/2 \rceil) + 1$, with base case $C(1)$.

Defining $D(n) = C(n) + 1$ with base case $D(1) = C(1)$, we see that $$ D(n) = 2D(\lceil n/2 \rceil). $$ Let us try to prove by induction that $D(n) \leq Kn - L$. Since $\lceil n/2 \rceil \leq n/2 + 1/2$, if the induction hypothesis holds for $\lceil n/2 \rceil$ then $$ D(n) \leq 2K(n/2 + 1/2) - 2L = Kn + K - 2L. $$ Choosing $L = K$, we get $D(n) \leq Kn - L$. Choosing $K = D(2)$, the induction hypothesis holds in the base case $n=2$. Altogether, we have proved $D(n) \leq K(n-1)$ (for $n \geq 2$), and so $D(n) = O(n)$, implying $C(n) = O(n)$.
> 2 votes

# Answer
**If someone is not aware of method to solve this recurrence**, then We can solve this by **Substitution**

Given,

**$$T(n)=2T(\frac{n}{2})+1$$**

Now, going by relation,

$$T(\frac{n}{2})=2T(\frac{n}{4})+1$$

We will **Substitute** this in **Original Recurrence Relation**

Therefore,

**$$T(n)=2T(\frac{n}{2})+1$$**
**$$T(n)=2 \Biggl(2T(\frac{n}{4})+1\Biggr) + 1$$**
**$$T(n)=2 \Biggl(2T(\frac{n}{2^2})+1\Biggr) + 1$$**
**$$T(n)=2 \Biggl(2 \Biggl( 2T(\frac{n}{8})+1\Biggr) +1 \Biggr) + 1$$**
**$$T(n)=2 \Biggl(2 \Biggl( 2T(\frac{n}{2^3})+1\Biggr) +1 \Biggr) + 1$$**

> Opening Brackets Carefully and Rearranging for Observing Pattern

**$$T(n)=2^3T(\frac{n}{2^3})+ 2^2 + 2^1 + 1 $$**
**$$T(n)=2^3T(\frac{n}{2^3})+ 2^2 + 2^1 + 2^0 $$**

> Using **Summation formula for Geometric Progression**

**$$T(n)=2^3T(\frac{n}{2^3})+ 2^0(\frac{2^3-1}{2-1})$$**
**$$T(n)=2^3T(\frac{n}{2^3})+ {2^3-1}$$**

> Let us assume that the algorithm takes **k** iterations.
>
> Therefore, after **k** iterations.

**$$T(n)=2^kT(\frac{n}{2^k})+ {2^k-1}$$**

> Since, we know **T(2)**. Therefore Put,
> $$\frac{n}{2^k}=2$$

**$$T(n)=\frac{n}{2} T(2)+ \frac{n}{2}-1$$**
**$$T(n)=\frac{n}{2} .1+ \frac{n}{2}-1$$**
**$$T(n)=n-1$$**

Therefore, $T(n)$ is asymptotically $O(n)$

Another quick method of solving this is Master Theorem
> 1 votes

---
Tags: algorithm-analysis, recurrence-relation, discrete-mathematics
---


title: Make the forward counter go down

text:
# Question
Title: Make the forward counter go down
Suppose, I have a 4-bit binary Incrementor that uses XOR gates to increment the inputted number by the value of 1 (b0001, to be precise).

Suppose, we connect it to 4 D-Flip-Flops (DFF) to create a counter that goes up every time we send the clock pulse. This is straightforward: Just connect the outputs of DFFs to the corresponding inputs of the Incrementor, and the outputs of the incrementor—to the corresponding inputs of the DFFs.

What I would like to figure out is how to alter the set up in order to make the counter go down instead of up at the flip of the up/down switch (e.g., goes down every time we send the clock pulse and the up/down switch is activated). I would prefer a walk through the entire process instead of just a ready answer.

# Answer
> 0 votes
Hint: what happens when you add $2^4$ each clock tick? What about $2^4-1$? How can you implement this (efficiently)?

You can also solve this in general: what happens when you add $2^n-1$ for an $n$-bit number? What would be the general way to implement this?

---
Tags: circuits, digital-circuits
---


title: Compress set of mostly known bitstrings

text:
# Question
Title: Compress set of mostly known bitstrings
Let's say there is a *sender* sending *messages* with *commands* to a *recipient*.

1. The *sender* knows a set of *commands* but doesn't know anything about the recipient. A command is simply an opaque uniform random 128-bit string. E.g., the sender might know these commands and what they do:

```
(1)  0x'BC04672BCEB7AEE08E555599F051F1CF'
(2)  0x'E3D0AC4094435D3093B99CFA31746B93'
(3)  0x'91014098C485DA109A39D52CDB611AD2'
(4)  0x'00156B495D2C9F81AB783A277DF30044'
(5)  0x'CADBBE207ABF184C95B33D707FB45552'

```
2. The sender then selects a subset of these commands and sends them in a *message* to the recipient. E.g.:

```
(1)  0x'BC04672BCEB7AEE08E555599F051F1CF'
(2)  0x'CADBBE207ABF184C95B33D707FB45552'
(3)  0x'00156B495D2C9F81AB783A277DF30044'

```
3. The recipient also knows a set of commands and doesn't know anything about the sender. There is typically a large overlap of the set known by the sender and the set known by the recipient, but the recipient may know some commands that the sender doesn't know and vice versa. E.g., the recipient might know these commands:

```
(1)  0x'D96F0AF780545565AD7721B1F9CD78C1'
(2)  0x'00156B495D2C9F81AB783A277DF30044'
(3)  0x'BC04672BCEB7AEE08E555599F051F1CF'
(4)  0x'69E71BBB6393F1E1A5FAD6B50A960D6E'

```
4. For each command in the message that the recipient does know, it performs some action. The other commands it just ignores. E.g.:

```
(1)  0x'BC04672BCEB7AEE08E555599F051F1CF' -> action
(2)  0x'CADBBE207ABF184C95B33D707FB45552' -> ignore
(3)  0x'00156B495D2C9F81AB783A277DF30044' -> action

```

I'd like to **compress the messages**. The main challenge is that each message must stand by itself and cannot (e.g.) build on any message exchanged in either direction before. There's little to no redundancy in a message that could be eliminated. However, since **most commands are known to both the sender and the recipient**, I'm wondering if there may be some way to exploit that fact to make the messages shorter.

# Answer
One simple approach is to use what is known as a "priming text", which is a text that is representative of the text that you wish to compress (e.g. by containing a bunch of strings that you expect to find).

There are lots of ways to realise this, but we will take LZ77 as an example. LZ77 works by searching for common strings within a sliding window. You fix a window size (say, 64kb, which is small today, but this is for illustration purposes). At any point in the text, the compressor either encodes literal characters, or a reference to some string within the previous 64kb.

Normally, you start with an empty window, because there is no already-transmitted text to refer to. But there's no reason why this has to be the case. If, instead, you fill it with a text that is known to both the sender and receiver, then the compressor already has some strings that it can refer to.

The same idea works with many other compression schemes: With LZ78, you could prefill a dictionary with priming text, with a PPM-like method, you could prime the model, and so on. It's not obvious to me how you would incorporate a priming text with the Burrows-Wheeler transform, but someone may have done it.
> 2 votes

---
Tags: data-compression
---


# Question
Title: Nandgame--I am not sure I understand the Data Flip-Flop specifications
Nandgame (nandgame.com) has you solve puzzles of increasing complexity which culminate in constructing a simple CPU. You start at the level of nand gates, and build everything else up out of those.

I'm having trouble understanding the specifications for the Data Flip-Flop puzzle. If I'm reading it correctly, when the "clock" bit *changes* from zero to one, the storage device should send its value to output, but while the "clock" bit *remains* either one or zero, nothing should change the output value.

What I'm stuck on is this idea of having output change *when and only when the clock changes from zero to one* I can't see a way to do that which doesn't allow the output to change any time the clock bit is equal to one (or trivially, equal to zero if I thrown an inverter on it fsr). But that results in a failure when I submit such solutions.

Could I just be reading the specifications incorrectly somehow?

Here is a transcription of the specification:

A DFF (Data Flip-Flop) component stores and outputs a bit, but only change the output when the clock signal change from 0 to 1.

When st (store) is 1 and cl (clock signal) is 0 the value on d is stored. But the previous value is still emitted.

When the clock signal changes to 1, the flip-flop starts emitting the new value.

When st is 0, the value of d does not have any effect.

When cl is 1, the value of st and d does not have any effect.

# Answer
OK, Just so that other people googling this god-forsaken problem can find the optimal solution, I got it in 9 nand gates. First, you don't need St to set your output latch, you can just hook up the output latch st(or its nand equivalent) to cl. That saves you an and gate. Second, if you deconstruct your latches to just nands and invs you can pull a duplicate inv out of one of the latches and turn it into a nand. Also you can reuse the inv from your !cl for your second latch's !st
> 2 votes

# Answer
I have worked 20 years as FPGA logic designer but I stop at task Data Flip-Flop! It is possible to build Data Flip-Flop. Two latches is required (sequential connection). First latch stores input data when st&!cl, second latch stores result of first latch to output when st&cl. Unbeliveable! Thanks to google...
> 0 votes

# Answer
Compact answer (AHDL language): latch1.st=st & !cl; latch1.d=d; latch2.st=st & cl; latch2.d=latch1.q; q=latch2.q;

.q - output port of the latch d,st,cl - inputs q - output latch1, latch2 - latch elements
> 0 votes

---
Tags: circuits
---


title: $f(O(x))$ vs. $O(f(x))$

text:
# Question
Title: $f(O(x))$ vs. $O(f(x))$
I understand what $O(f(x))$ means... $O(f(x))=\\{g(x): g(x) ≤ cf(x), c,x\_0\>0 \\}$. But I can't find a clear explanation on the meaning of: $f(O(x)).$ Can you explain the exact definition of this? When does $f(O(x))=O(f(x))$? Can you provide examples of when this holds and say why?

# Answer
> 3 votes
As $O(x)$ is set of functions, then $f(O(x))=\\{f\circ g \colon g \in O(x) \\}$, when it have sense.

Simply example of $f$, without any requirement, to hold $f(O(x))=O(f(x))$ can be identity function i.e. $f(x)=\text{id}(x)=x$.

Let me mention, that one of the well known formulas of mathematical analysis is $$O(O(f(x))) = O(f(x))$$

Where assumed $f(x)\>0$.

---
Tags: asymptotics
---


# Question
Title: Detecting odd cycle using mod operator and breadth first search algorithm
If we want to detect and **odd cycle** if an undirected graph $G=\<V,E\>$. Suppose we run BFS algorithm from CLRS book as follows,

**Q**: Now my question is suppose we have the following graphs:

The figure to the left above:

* $d\[v\] \bmod{2} == d\[u\] \bmod{2}$ equal and gives odd cycle.
* $d\[v\] \bmod{2} == d\[a\] \bmod{2}$ not equal remainder, so won't give odd cycle.

The figure to the right above:

* $d\[x\] \bmod{2} == d\[u\] \bmod{2}$ not equal remainder, so won't give odd cycle.
* $d\[x\] \bmod{2} == d\[v\] \bmod{2}$ not equal remainder, so won't give odd cycle.

**Problem**: so the only case to discover odd cycle is when we have the left right graph and when exactly we compare vertex $v$ distance with $u$ distance. What do you think please? If the mod operator works, can you give your interpretation as why this should work in general please if possible?

# Answer
The idea, in a nutshell, is that a graph does not contain an odd cycle iff it is 2-colorable (also known as bipartite).

Your algorithm attempts to find a 2-coloring of the graph. In each connected component, the coloring is unique once we fix the color of one of the vertices, since all neighbors of a white vertex are black and vice versa. The algorithm uses this coloring strategy, and verifies that it results in no monochromatic edges.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Finding $Aeven(x)$ and $Aodd(x)$ for a Fast Fourier Transform (FFT) problem?
In this article about FFT the author used FFT on this polynomial.

$A(x) = 3+2x+3x^2+4x^3$

Using $ A(x)= Aeven(x^2) + xAodd(x^2)$ the author determined the following for $Aeven(x)$ and $Aodd(x)$

$ Aeven(x) = 3+3x$

$ Aodd(x) = 2+4x $

How were $Aeven(x)$ and $Aodd(x)$ determined? Shouldn't $Aeven(x) = 3+3x^2$ and $Aodd(x) = 2x+4x^3$ ?

# Answer
You have $Aeven(x^2) = 3 + 3x^2$, so that means that $Aeven(x) = 3 + 3x$.

For $Aodd$, you have $xAodd(x^2) = 2x + 4x^3$, so $Aodd(x^2) = 2 + 4x^2$, hence $Aodd(x) = 2 + 4x$.
> 2 votes

---
Tags: polynomials, fast-fourier-transform
---


# Question
Title: trouble solving the recurrence 4T(n/2) + n
I am having trouble figuring out how to solve this recurrence problem...

$$ \begin{aligned} &4T(n/2) + n \\ = &4(4T(n/4) + n/4) + n \\ = &16T(n/4) + 2n \\ = &4^kT(n/2^k) + kn \end{aligned} $$

I lose the trail here and I cannot figure out how to finish it and actually find the complexity. Can anyone help? How can this be done?

# Answer
We can use **Master Theorem** to solve this :

If a **Recurrence Relation** is of the Form

## $$T(n)=aT\bigg(\frac{n}{b}\bigg)+{n^k}({\log(n)})^p$$

Then, as per **Master Theorem**, we have **Six Conditions** depending on value of $a,b,k$ and $p$

* If $\log\_ba\>k$
Answer is $\theta(n^{\log\_ba})$
* If $\log\_ba=k$ and $p\>-1$
Answer is $\theta({n^k}({\log n})^{p+1})$
* If $\log\_ba=k$ and $p=-1$
Answer is $\theta({n^k}\log\log n)$
* If $\log\_ba=k$ and $p\<-1$
Answer is $\theta(n^k)$
* If $\log\_ba\<k$ and $p\geqslant0$
Answer is $\theta({n^k}({\log n})^p)$
* If $\log\_ba\<k$ and $p\<0$
Answer is $\theta({n^k})$

In any problem, our main motive is to find $a,b,k$ and $p$.

**In Given Problem**
$a=4$
$b=2$
$k=1$
$p=0$

Now, $\log\_24 = 2$ which is greater than $k$ $(1)$ Therefore, Answer is $\theta(n^{\log\_ba})$

**Putting Value(s)**

## $$\theta(n^2)$$
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, recurrence-relation, recursion
---


# Question
Title: Maximum interval scheduling - Circular Variation
Consider a variant of interval scheduling except now the intervals are arcs on a circle. The goal is to find the maximum number of arcs that do not overlap. Let $C$ be the circle on the plane centered at the origin with unit radius. Let $A\_1, ..., A\_n$ be a collection of arcs on the circle where an arc $A\_i$ is specified by two angles $\alpha\_i\in \[0,2\pi\]$ and $\beta\_i\in \[0,2\pi\]$: the arc starts at the point on the circle with angle $\alpha\_i$ and goes counter-clockwise till the point on $C$ at angle $\beta\_i$. Two arcs overlap if they share a point on the circle.

I want the maximum number of non-overlapping arcs in the given set of arcs.

One way to do it is to first sort the intervals by start angle in $O(n\log n)$ time. Then, for each arc $A\_i$, assume it is taken, and mark all arcs that intersect it as "invalid". Then, run the *normal interval scheduling* algorithm on the remaining "valid" arcs which won't overlap $A\_i$ and the maximum end time will not intersect the first start time. This takes $O(n)$ per arc, leading to an $O(n^2)$ time algorithm when taking the maximum across all possible arc selections.

My question is, can we do better? Is $O(n\log n)$ also achievable on the circular case?

# Answer
> 3 votes
Yes.

What we need to do is, basically, running the $O(n^2)$ algorithm provided in the question, but without unnecessary intervals and redundant steps.

---

Here is the gist of an $O(n\log n)$ algorithm.

Assume each interval is expressed as $\[\alpha, \beta\]$, where $0\le\alpha\lt 2\pi$ and $\alpha\le \beta\lt \alpha+2\pi$. It means all the points on the circle whose angles are between $\alpha$ and $\beta$.

If an interval is contained in another interval, remove the containing interval. This operation will not decrease the maximum number of non-overlapping arcs. Repeat this operation as long as possible. The whole removing process can be done in $O(n\log n)$ time by sorting the intervals by ascending start angle primarily and descending end angle secondarily, and then processing each interval in order.

Now no interval contains another interval and the remaining intervals are sorted both by start angle and by end angle (both orders are strictly ascending). Pick an arbitrary interval (that has not been removed). For example, let us pick the first one remaining. Denote it by $B\_{00} = \[\alpha\_{00}, \beta\_{00}\]$.

Let $k$ be the number of intervals after $B\_{00}$ that contains $\beta\_{00}$ but not $\alpha\_{00}$, $0\le k$. Let them be $B\_{10}, B\_{20}, \cdots, B\_{k0}$ in order. In other words, assuming $B\_{i0}= \[\alpha\_{i0}, \beta\_{i0}\]$ for all $i$, $1\le i\le k$, we have $\beta\_{i0}\le\alpha\_{(i+1)0}\lt \beta\_{(i+1)0}$ for all $i$, $0\le i\lt k$.

For each $i$, $0\le i\le k$, let us run the usual greedy interval scheduling algorithm starting with $B\_{i0}$. (For intervals sorted by ascending end angle used in that greedy algorithm, we can reuse the sorted intervals produced by the first step.) However, instead of running them one by one separately, we will run them in turn. When we find two runs can include the same interval in their respective sets of non-overlapping intervals, stop the run that includes less number of intervals so far, or, in the case when both include the same number of intervals so far, the one that starts earlier. This pruning operation ensures that each interval will be accessed at most a constant number of times. This step of running all scheduling, with a proper implementation, takes $O(n)$ time.

Finally, pick the run that include the most number of non-overlapping intervals. That number is the wanted maximum number.

---

Here is an implementation in Python, with brief comments. Instead of $2\pi$, parameter `perimeter` is used to denote the perimeter (by some unit of angle or time). The interval `schedules[i][0]` in method `max_non_overlapping` corresponds to $B\_{i0}$ above while `more_schedules` is true.

```
from collections import deque
from functools import cmp_to_key

def sort_and_reduce(intervals):
    """ Return sorted intervals without any interval contains another """

    # Sort by increasing start. Break ties by decreasing end.
    intervals = sorted(intervals, key=cmp_to_key(lambda x, y: x[0] - y[0] if x[0] != y[0] else y[1] - x[1]))

    result = []
    for cur_interval in intervals:
        # remove intervals that contain `current`
        while result and result[-1][1] >= cur_interval[1]:
            result.pop()
        result.append(cur_interval)
    return result

def max_non_overlapping(perimeter, intervals):
    """ return the maximum number of non-overlapping circular intervals

    Each (circular) interval in `intervals` is a pair `[start, end]`,
    where `0 <= start < perimeter` and `start <= end < start + perimeter`.
    Interval `[start, end]` stands for the set of numbers (angles)
    `0 <= num < perimeter` such that either `start <= num <= end`
    or `start <= num + perimeter <= end`. Two intervals are
    non-overlapping iff their corresponding sets of numbers are disjoint.
    """

    intervals = sort_and_reduce(intervals)

    ans = 0

    # `schedules` is a queue of schedules. Each schedule is a list of
    # non-overlapping intervals in natural order, i.e, ordered by increasing
    # starts as well as by increasing ends since so are `intervals` as they
    # have been sorted and reduced.
    schedules = deque()

    # Are we still building the first intervals of the parallel greedy runs?
    more_schedules = True

    # Invariants for the schedules in `schedules` at the end of each iteration:
    #   1. Every interval appears in most one of the schedules in the queue.
    #   2. The last `end`s of schedules are increasing.
    #   3. Any two adjacent schedules contain the same number of intervals and
    #      the first `start`s in them are increasing, except when the second
    #      schedule contains the the very first interval, at which time the
    #      second schedule contains one more interval than the first schedule.
    for cur_interval in intervals:
        if more_schedules:
            # if `schedules` is empty or the start of `cur_interval` is smaller
            # than or equal to the end of the very first interval.
            if not schedules or cur_interval[0] <= intervals[0][1]:
                schedules.append([cur_interval])
                continue
            else:
                more_schedules = False
        if cur_interval[0] > schedules[0][-1][1]:
            if cur_interval[1] < perimeter:
                while len(schedules) > 1 and cur_interval[0] > schedules[1][-1][1]:
                    # pop schedules[0] since schedules[1] cannot be worse than it.
                    schedules.popleft()
                schedules[0].append(cur_interval)
                # keep schedules sorted by earliest-end first
                schedules.append(schedules.popleft())
            else:
                # a schedule can contain at most one such interval, i.e., an
                # interval whose `end` is at least `perimeter`
                while schedules and cur_interval[0] > schedules[0][-1][1] and \
                        cur_interval[1] < perimeter + schedules[0][0][0]:
                    ans = max(ans, 1 + len(schedules.popleft()))
                while schedules and cur_interval[1] >= perimeter + schedules[0][0][0]:
                    ans = max(ans, len(schedules.popleft()))
                while schedules and cur_interval[0] > schedules[0][-1][1] and \
                        cur_interval[1] < perimeter + schedules[0][0][0]:
                    ans = max(ans, 1 + len(schedules.popleft()))
                if not schedules:
                    break
        # else `cur_interval` cannot be included.

    return max(ans, len(schedules[-1]) if schedules else 0)

if __name__ == "__main__":
    perimeter = 16
    intervals = [[5, 13], [4, 8], [3, 16], [1, 14], [10, 19], [2, 9], [7, 18], [11, 12], [15, 17], [6, 20]]
    res = max_non_overlapping(perimeter, intervals)
    print(res)
    # output: 3,  which is the number of intervals in schedule [[4,8], [11,12], [15,17]]

```

---
Tags: algorithms, scheduling, intervals
---


# Question
Title: Can more compression be achieved when data is sorted (in ascending or descending order)?
Let's say I have a file which is exactly 1 MB in size.
Contents of file are :
0001001000... upto 128 bytes (128 bytes per line in file).
If I sort it in ascending or descending order (using notepad++):
Line 1: 0000000....
Line 2: 0000001.... and more.
Now if I compress it I get a 110 to 120 KB file.
I want to know if I can achieve more compression (to get a file 10 - 50 KB in size).
Is there any special compression algorithm or program for this (for sorted data) OR
I have reached the maximum compression ?
Compression program I used:
7z 19.00
Archive format: 7z
Compression level: Ultra
Compression method: LZMA2
Dictionary size: 64 KB
Word size: 64
Solid Block size: 64 MB
Number of CPU threads: 4
\# Note : Whole file contains 0s and 1s only, there are no other ASCII characters.
I know that reducing the bytes per line and then compressing it will reduce the file size significantly but I don't want to do that for some reason, so reducing the bytes per line is not an option.

# Answer
Compressibility of a file depends on the nature of the file, and what methods are applied to it. It is common for some prepressing to improve the compression.

For example, if a list of words is sorted, you will see that many words in a row with have the same prefix, and can be taken advantage to reduce the overall file size with some extra encoding. Sequential increasing integers (i.e., sorted) and taking the differences often allow one to reduce the data a lot.

Sorting is an option. If the data can be sorted without needing to be unsorted, then by all means, sort the data. Try the existing compression methods available. If you see some pattern that can be taken advantage of, and you can create a PRE/POST process that can perform the reduction, and undo the reduction to return the file back to what it was before. Great, do so.

When it comes to data compression, the more that is understood about the nature of the specific data, the more likely that some parts of it can be compressed. For example a RGB color image has the colors interleaved values, but compress poorly with generic compression, as they do not understand or attempt to do interleaving.
> 2 votes

# Answer
When I tried to delete my answer a pop up window asked if I'm voting to delete the question. I'm not voting to delete a question addressed to the whole internet world, I'm just deleting my answer
> 0 votes

---
Tags: data-compression, binary
---


title: Recurrence and Time complexity

text:
# Question
Title: Recurrence and Time complexity
I am having problem solving this recurrence. Can anyone help me with this please:

$$ T(n) = 2(T(\sqrt n))^2 , T(1) = 4. $$

# Answer
> 2 votes
Let $S(m) = \log\_2 (2T(2^m))$. Then $S(m)$ satisfies the recurrence $$ S(m) = 2S(m-1), \quad S(0) = 3. $$ You can work it out from here.

# Answer
> 1 votes
Solving by **Substitution**

Given,
$T(n)=2(T(\sqrt n))^2$

$T(n)=2(T(n^{1/2}))^2$

$T(n)=2(2(T(n^{1/4}))^2)^2$

$T(n)=2(2(2(T(n^{1/8}))^2)^2)^2$

$T(n)=2.2^2.2^4(T(n^{1/8}))^8$

$T(n)=2^{1+2+2^{2}}(T(n^{1/2^3}))^{2^3}$

Using Summation Formula for Geometric Progression
$T(n)=2^{(2^3-1)}(T(n^{1/2^3}))^{2^3}$

Therefore, for **k iterations**

## $T(n)=2^{(2^k-1)}(T(n^{1/2^k}))^{2^k}$

Now, **Assuming** that instead of $T(1)=4$, it is given that $T(2)=4$
(Since, $n^{1/2^k}=1$ will be possible when $n=1$ or $\frac{1}{2^k}=0$, which seems invalid as per algorithm)

Therefore, put $n^{1/2^k}=2$

$\frac{1}{2^k}{log\_2n}=1$

${2^k}={log\_2n}$

Thus,

## $T(n)=2^{({log\_2n}-1)}(T(2))^{log\_2n}$

$T(n)=2^{({log\_2n}-1)}(4)^{log\_2n}$
$T(n)=2^{({log\_2n}-1)}(2)^{2log\_2n}$
$T(n)=2^{({log\_2n}-1)}2^{log\_2{n^2}}$

## $T(n)=\frac{2^{({log\_2n})}2^{log\_2{n^2}}}{2}$

$T(n)=\frac{n^3}{2}$

## Thus, $T(n)$ is $O(n^3)$

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


# Question
Title: How to prove that insert complexity in binary search tree is minimum O(log n)?
Is it connected to BST search O(log n) or height log n?

How to prove that insert will give give you correct BST in minimum O(log n) time?

# Answer
> 2 votes
Insert complexity in a binary search tree is *not* minimum $\Omega(\log n)$. For instance, if the element to be inserted is larger than the largest element of the tree, then you can make the whole tree the left child of a new root node containing the element to be inserted.

In a *balanced* binary search tree, with only a pointer to the root and not any other nodes, I'd guess insert complexity is $\Omega(\log n)$. In order to prove this, you'd probabaly want to specify which type of balanced BST we're talking about: AVL, red-black, weight balanced, etc.

# Answer
> 0 votes
The minimal height of a BST is always log n, you can easily prove it by induction. Then if you want to insert a new node you need to find the corresponding leaf where to insert it, which takes at least log n operations (comparisons) in the worst case, more if the tree is not balanced (larger height). Hence you obtain an insert cost of O(log n). We always focus on the worst case scenario to compute the O-complexity.

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


# Question
Title: Hierarchy of parser grammars vs Chomsky hierarchy of grammars and the comparsion of the language acceptance power of each parser grammar
While reading the text *Modern Compiler Implementation in C* by *Andrew Appel* I came across the hierarchy of grammar given below.

The above diagram is very helpful in understanding the correlation among the various parser grammars. All the grammar above are context free grammars. From theory of computation texts, I have the following Chomsky hierarchy of grammars in my mind.

Now I wonder, how to correlate these two diagrams - a possible superposition, which shall show where exactly in the Chomsky hierarchy the parser grammars lie, and their extent with respect to the boundaries already defined by Chomsky hierarchy.

---

If possible, could you please as well suggest the resource from which I can develop more knowledge regarding this.

---

PS: After the comments and discussion in the answer by Yuval Filmus, I made an attempt to draw the situation:

---

*If we consider on the basis of the power of language corresponding to a grammar type*

---

*If we consider just on the basis of grammar type*

Reference : Theory of Computation Lectures by Prof. Harry Porter

*Are the above diagrams which I have constructed as per my understanding correct?* If they are not then could anyone please rectify it...

# Answer
All of the grammars in your first figure are context-free grammars. That text seems to identify *grammar* with *context-free grammar*.
> 3 votes

---
Tags: formal-grammars, compilers, parsers, check-my-answer, chomsky-hierarchy
---


# Question
Title: Rigorously show that this program outputs $2n-$ #number of ones in binary representation of $n$ stars
Given following program:

```
while n > 0 do
    for i = 1 to n do
       print '*'
    n = n / 2

```

where $/$ is integer division as usual. We want to calculate exactly how many * are printed. By summing up $n+n/2+n/4+...+n/2^{\lfloor\log\_2n\rfloor}$ we get $2n-1$ but only if $n$ is a perfect power of $2$. In this case we can do simple algebra by manipulating the sum and using sum of geometric sequence formula. The problem is the integer division if $n$ is not a power of two. If we denote $s$ to be number of $1$'s in the binary representation of $n$, the result should be $2n-s$, but how to show this rigorously? My idea was to somehow show that for each $1$ in the binary representation, when we divide, we somehow lose the precision so $1$ less * is printed (because dividing by 2 is basically right bit shift).

# Answer
Given a non-negative integer $x$, let $|x|$ denote the number of ones in the binary representation of $x$.

You can prove the claim by induction on $n$. The base case $n=0$ is trivially true. Consider then $n\>0$. During the first iteration, the algorithm prints $n$ stars. The number $x$ of stars printed by the other iterations is exactly the number of stars printed when the input of the algorithm is $\lfloor n/2 \rfloor$. Hence, by induction hypothesis, $x=2\lfloor n/2\rfloor - |\lfloor n/2 \rfloor|$.

If $n$ is even the total number of printed stars is: $$ n+x = n+2\lfloor n/2 \rfloor - |\lfloor n/2 \rfloor| =n+2(n/2)-|n/2| =2n-|n/2|=2n-|n|, $$ where we used the fact $|n/2|=|n|$ since the least significant bit of the binary representation of $n$ is a $0$.

If $n$ is odd the total number of printed stars is:

$$ \begin{align\*} n+x &= n+2\lfloor n/2 \rfloor - |\lfloor n/2 \rfloor| =n+2((n-1)/2)-|(n-1)/2| \\ &=2n-1-|(n-1)/2| =2n-1-(|n|-1) =2n-|n|, \end{align\*} $$ where we used $|n|=1+|n-1|=1+|(n-1)/2|$ since the last bit of the binary representation of $n$ is a $1$.
> 2 votes

---
Tags: loops
---


title: Palindrome operations on a string

text:
# Question
Title: Palindrome operations on a string
You are given a string S initially and some Q queries. For each query you will have 2 integers L and R. For each query, you have to perform the following operations:

Arrange the letters from L to R inclusive to make a Palindrome. If you can form many such palindromes, then take the one that is lexicographically minimum. Ignore the query if no palindrome is possible on rearranging the letters.

You have to find the final string after all the queries.

**Constraints:**

1 \<= length(S) \<= 10^5

1 \<= Q \<= 10^5

1\<= L \<= R \<= length(S)

**Sample Input :**

4

mmcs 1

1 3

**Sample Output:**

mcms

**Explanation:** The initial string is mmcs, there is 1 query which asks to make a palindrome from 1 3, so the palindrome will be mcm. Therefore the string will mcms.

If each query takes O(N) time, the overall time complexity would be O(NQ) which will give TLE. So each query should take around O(logn) time. But I am not able to think of anything which will solve this question. I think since we only need to find the final string rather than what every query result into, I guess there must be some other way to approach this question. Can anybody help me?

I found this question in a sample test of a coding competition.

# Answer
> 1 votes
The key idea is that there are only $26$ alphabets in the string. Let $\Sigma$ denote the set of alphabets, i.e., $|\Sigma| = 26$. Assume that you have a data structure that for every pair of $L$ and $R$, computes the number of occurrences of any alphabet in $\[L,R\]$ efficiently. Using those numbers, you can easily check in $O(|\Sigma|)$ time if the substring from $L$ to $R$ forms a palindrome or not; this part is easy I leave the details to you. After finding the palindrome, you need to update the data structure without changing the original string; this part is complex, which I will explain in more detail.

**Data Structure:** Maintain an Interval tree (or segment tree) for each alphabet. A leaf in the tree corresponds to an interval $\[s,t\]$, such that the alphabet appears contiguously in the string $S$ from positions $s$ to $t$. For example: Suppose the string $S$ is $baaaedaabbbzz$ and the alphabet is $a$. Then the leaves of the segment tree of alphabet $a$ will be: $\[2,4\], \[7,8\]$ since $a$ appears in the string from positions $2$ to $4$, and it also appears in the string from positions $7$ to $8$. Similarly, for $b$, the leaves of its segment tree would be $\[1,1\], \[9,11\]$.

The segment trees for all the alphabets can be constructed in $O(|S| \log |S|)$ time. If you are not familiar with segment trees, you will need to study it by yourself.

**Query:** For a given query $\[L,R\]$, you can find the number of occurrences of any alphabet between positions $L$ and $R$ using the corresponding segment tree of the alphabet. This takes $O(\log |S|)$ time for each alphabet. Now, you can easily check if the sub-string makes a palindrome or not.

**Updating the Data Structure:** Now, you do not need to output/print the palindrome; you just need to find the interval in which an alphabet occurs in the palindrome (the lexicographically smallest one). This can be done in $O(|\Sigma|)$ time; it is easy, I leave the details to you. There will be at most two intervals for each alphabet in the palindrome. Update the segment trees of each alphabet by adding these new intervals. Adding these two intervals takes $O(\log |S|)$ time. However, you also need to remove some old intervals that overlap with these new intervals. It also takes $O(\log |S|)$ time: Why? Think in terms of amortized analysis.

Lastly, after performing all the queries, you can reconstruct the final string using the segment trees.

Overall running time is $O((|S|+|\Sigma|) \cdot \log |S|) \approx 10^7$.

---
Tags: substrings
---


# Question
Title: Must a partial halt decider be a pure function of its inputs?
**Must a partial halt decider be a pure function of its inputs?**

A partial halt decider correctly decides the halt status of some of its inputs.

I am trying to write C code that would be acceptable to computer scientists in the field of the theory of computation.

In computer programming, a pure function is a function that has the following properties:

(1) The function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams).

(2) The function application has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or input/output streams).

https://en.wikipedia.org/wiki/Pure\_function#Compiler\_optimizations

I created a partial halt decider that is able to tell when it is called in infinitely nested simulation. It can only do this if it has a static memory variable to keep track of the simulation of its input across recursive invocations.

**Does this still meet the Halting Problem requirement that the function must be a pure function of its inputs?**

# Answer
A decision algorithm is required to behave as an "observationally pure" function. In other words, its externally observable behavior (for someone who can run it on inputs of their choosing and observe what it outputs) must be consistent with it being a pure function.

Presumably, unless you specify otherwise, any normal reader of your definition of "partial halt decider" would assume that such an algorithm is also required to be observationally pure.

Why? Because the algorithm is supposed to compute a mathematical function, and a mathematical function is pure, so any algorithm that correctly computes it also must be observationally pure.

There is no requirement that the particular implementation of the algorithm be pure in the sense you have listed. It is OK to have code that, for instance, defines a local variable and then overwrites its value. For instance, a Turing machine can overwrite what is written on the tape. Nonetheless, from the perspective of any external observer who only sees the input-output behavior of the Turing machine, it remains observationally pure.
> 3 votes

---
Tags: computability, c, theory
---


# Question
Title: Name for type of actions that only care for outcome
There is a definition for kind of actions that only care for outcome.
Classic example for such an action is `remove` from `collection`:
When you try to remove an item that doesn't exist in collection, there are two possible outcomes: **failure** with `item doesn't exist` or **success** (because the outcome is that the item doesn't exist).
I'm interested in the second one. How do you call `remove` that succeeds when the item it is trying to remove is not present?

# Answer
This doesn't actually answer the question but it fits to be an answer.
What I looked for is *idempotent* (when I asked this question I was actually looking for this word, but failed to express myself properly). The definition is quite different from the question asked here:

> In computing, an idempotent operation is one that has no additional effect if it is called more than once with the same input parameters. For example, removing an item from a set can be considered an idempotent operation on the set.

But indeed, any operation that is idempotent will meet the question criteria.
> 1 votes

# Answer
This is usually called a "blind" operation. This is common in log-structured merge trees, where a blind delete is often written as a "tombstone" that will take precedence over any previous insert or update of the given value.
> 1 votes

# Answer
With reference to your answer, the first form is also idempotent, except that it gives a diferent answer. Both versions remove the element from the set if it was there and don't change the set if the element wasn't there.

This is about the specification of the function: do you want returned the information that the element *was* in the set or not? The first (you want the information) means the function must return this information; the second (you don't care) means the function does not need to return the information (but could and you could choose to ignore the information).

In C this would be:

```
void remove(tElement *element);  // remove element, if there

int  remove(tElement *element);  // remove element, if there, and tell me

```
> 0 votes

---
Tags: data-structures
---


# Question
Title: If the probability of frame being lost is $P.$ Then, calculate the mean no. of transmission for the frame to make it success$.$
Here the probability of frame being lost is $P.$ So the probability of frame reaching safely would be $(1-P).$

Now lets consider that the frame will reach safely in $k$-th transmission. That means that the frame being lost $k-1$ times and reached in $k$-th time with probability $(1-P).$ Now a frame requires $k$-transmissions exactly when the first $k-1$ attempts fail .... this happens with probability $P^{ \text{k-1} }$ and the $k$-th transmission succeeds , this happens with probability $1-P.$

For $k=1,$ the probability $= (1-P)$

For $k=2,$ the probability $= P(1-P)$

For $k=3,$ the probability $=$ $P^2$$(1-P)$ $.............. ............. {\infty}$

So the mean number of transmission will be $= (1-P) + P(1-P) +$ $P^2$$(1-P)$$.......... $Which gives me $1.$

But solution saying,

$\sum\_{k=1}^{\infty} kP\_k$

$=$ $\sum\_{k=1}^{\infty} k(1-P)P^{k-1}$

$=$$(1-P)$$\sum\_{k=1}^{\infty}kP^{k-1}$

$= (1-P).$$\frac1{{(1-P)}^2}$ $=$$\frac1{{(1-P)}}$

I don't understand how they multiply $P^{ \text{k-1} }$$(P-1)$ by $k.$

# Answer
You have to compute the "average of the number of transmissions" and not the "average of probabilities". Think of it as you are rolling a dice and a number $k$ comes with probability $P^{k-1} \cdot (1-P)$. So, the average value that you get on dice is $\sum\_{k = 1}^{\infty} k \cdot (\textrm{Probabaility of $k$}) = \sum\_{k = 1}^{\infty} k \cdot P^{k-1} \cdot (1-P)$

In other words, you have to compute the expected value of "the number of transmissions". Therefore, we multiply by $k$.

Read more about geometric distribution and its expected analysis here.
> 0 votes

---
Tags: probability-theory, computer-networks
---


# Question
Title: What could be the most efficient algorithm to find index in an array that matches given conditions?
I have an array A with n elements. I am trying to write an efficient algorithm to find the index of elements that matches condition A\[j-1\]\>=A\[j\]\<=A\[j+1\].

Example:

```
A = [12,11,9,7,5,54,67,87,23,54,20,22]

```

Should return `4` because subarray `[7,5,54]` matches the condition where `A[4] = 5.`

Below is the solution I tried. It has run time `O(n)`. I am looking if there is any other better solution?

```
 def sol_1():
      for j in range(1,n):
        if A[j-1]>=A[j] and A[j]<=A[j+1]:
          return j
      return False

```

# Answer
You can not do better than $n-2$ in the worst case. You can show this using an adversarial argument.

Suppose the array is $A = \[1,2,3,\dotsc,n\]$. There is no index in the array that satisfies that $A\[i-1\] \geq A\[i\] \leq A\[i+1\]$. Therefore, the answer is trivially no. For the sake of contradiction assume that there is an algorithm that solves the problem in less than $n-2$ operations. It means there is an index of the array that is not accessed by the algorithm. Suppose this index is $t$ and $1\<t\<n$. Since the algorithm has not seen this index yet, the adversary can decrease $A\[t\]$ value by $1$, i.e., $A\[t\] = t-1$. Now, index $t$ satisfies that $A\[t-1\] \geq A\[t\] \leq A\[t+1\]$; thus proving the algorithm wrong.

Therefore, any correct algorithm must access at least $n-2$ entries of the array. Therefore, the lower bound on the running time is $\Omega(n)$.
> 2 votes

---
Tags: algorithms, algorithm-analysis, arrays
---


title: Relationship between NP and CoNP

text:
# Question
Title: Relationship between NP and CoNP
I have a question from a test that I could not pass, I could not answer the question and I am looking for help with this question

This is the question

Will be $A\in \mathbf{NP}$

Suppose that $A\notin \mathbf{coNP}$. determine which of the claims is correct:

1. $\mathbf{P}=\mathbf{coNP}$
2. $\mathbf{P}=\mathbf{NP}$
3. $\mathbf{P}\neq \mathbf{NP}$
4. $\mathbf{NP} \cap \mathbf{coNP} = \varnothing $

According to the data in the question, you need to choose the correct answer from the 4 possible answers.

I do not understand if there is any connection at all between the language A, and the answers themselves.

What I think is that A must only be in $\mathbf{NP}$ and it cannot be in $\mathbf{P}$, because it is not in $\mathbf{coNP}$, and $\mathbf{coNP}$ itself is in $\mathbf{P}$.

But I do not find an answer that can fit it, maybe 3 is correct, but it has nothing to do with the question at all, it is always true.

# Answer
$P$ is closed under complement. The rest is up to you.
> 1 votes

# Answer
The correct answer is no. 3.

Suppose $A \in \text{NP}$ and $A \notin \text{co-NP}$. Clearly this shows $\text{NP} \neq \text{coNP}$, but that's not a possible choice for this question.

Observe that complement of the machine output can be trivially implemented in a deterministic polynomial machine. That is to say, $\text{P} = \text{co-P}$. Thus, if $\text{P} = \text{NP}$, then $P = \text{co-NP}$, which together imply $\text{NP} = \text{co-NP}$. This cannot be the case by assumption, so $\text{P} \neq \text{NP}$.
> 1 votes

# Answer
1+2 are not proven true and false, considered to be extremely hard to be proven either way, and most people assume they are false. That obviously answers 3.

4: P is a subset of both NP and co-NP, and since P is not empty, 4 is false.

Language A is indeed irrelevant. If the question had said "assume A in co-NP" that would have shown much more trivially that 4 is false, but it's false anyway.
> -2 votes

---
Tags: complexity-theory, computability, reductions, np
---