# Question
Title: Looking for an algorithm to minimize cost of edge traversals in a bipartite graph subject to constraints
I have a set of urns that can each hold different amounts of sand. Porters can deliver sand to each urn subject to a transport fee per unit of sand. Each porter has a finite amount of sand they are capable of delivering to each urn. The objective is to fill the urns with all the available sand while minimizing total cost. Here's a motivating example:

Black circles show porters. The value in the center of the porter circles show the total amount of sand they can transport. Gray squares show urns. The value in the center of the urns show the amount of sand an urn can hold. Porter\_Urn edges show the cost of transporting 1 unit of sand to a given urn. Using this example, Porter 1, which has 100 units of sand could transport 1 unit of sand for a cost of 50 to Urn 3, which can hold a total of 65 units of sand. That would be very expensive!

Is there an algorithm to solve this optimization problem? It seems like maybe a maximum flow problem or maybe a multi-knapsack problem? Or some other algorithm from Operations Research?

# Answer
> 2 votes
This is straight up a minimum-cost flow problem. All it's missing is a an edge from the source to each porter with zero cost and capacity equal to the porter, and a zero cost edge from each urn to the sink with capacity equal to that urn.

---
Tags: graphs, network-flow
---


# Question
Title: Why we can't have some algorithm to be polynomial if there are generic conditions that make them so?
I explain it better:
There are some algorithms that is clearly in NP, also NP-complete, but that under certain conditions they can be solved in polynomial time.

An example is Bin Packing, the decision version of the problem is an NP-complete problem and it's defined as follows in the book "Computers and Intractability" by Michael R. Garey and David S. Johnson:

> INSTANCE: Finite set $U$ of items, a size $s(u) \in Z$ for each $u \in U$, a positive integer bin capacity $B$, and a positive integer $K$.
> QUESTION: Is there a partition of $U$ into disjoint sets $U\_1, U\_2, ..., U\_k$ such that the sum of sizes of the items in each $U\_i$ is $B$ or less.

And there is a comment that says "Solvable in polynomial time for any fixed $B$ by exhaustive search."
I have asked in math.stackexchange how it is possible and I get a clearly answer about that:
https://math.stackexchange.com/questions/3804912/bin-packing-problem-with-fixed-size-of-bins

Now I ask you why we can't applicate things like this to all instance of the problems? What is the thing that I don't get that makes this impossible?
For example, in the Bin Packing problem I think that I would can always enumerate the solutions and search into them because the $ B $ is always fixed once I get it, ok the number of the solutions could be a huge number, but it still remains a polynomial time algorithm. Or the "enumerate solutions" meanings that they are precomputated and the algorithm just has to check between them? And in this case, why we can't precomputate always?
I'm not saying something like $ P=NP $ because I'm sure not the first person that think about this thing and if the most accredited opinion is that $ P \not= NP $ it must be why this thought of mine is wrong and I want to understand why this isn't a generic solution for the problem, and where I'm wrong.

# Answer
> 1 votes
It's often the case that an NP-complete problem has some parameter $b$ that when fixed to a small constant makes an polynomial algorithm possible, yes.

However in fixing $b$ that problem (at least as of writing when $P =^? NP$) loses its completeness. That means when we want to do a reduction we (for at least some instances) need this parameter to be bigger than $b$.

---
Tags: algorithms, complexity-theory, np-complete, polynomial-time, packing
---


# Question
Title: Efficient way to count number of intersections of line segments
On my computer science course's exam I was given the following task:

*You are given $n$ segments that lies on the same line: $i$-th segment starts at coordinate $from\_i$ and ends at $to\_i$. Your task is for each segment count number of other segments that intersects it.*

EXAMPLE INPUT:
5
7 8
8 9
0 3
2 7
10 15

EXAMPLE OUTPUT:
2 1 1 2 0

I've implemented the naive algorithm:

```
def count_intersections(i):
    counter = 0
    for j in range(len(data)):
        if i != j:
            if data[i][0] <= data[j][0]:
                left = data[i]
                right = data[j]
            else:
                left = data[j]
                right = data[i]

            if right[0] <= left[1] <= right[1]:
                counter += 1
            elif left[0] <= right[0] <= left[1]:
                counter += 1

    return counter

n = int(input())
data = []
for i in range(n):
    data.append(tuple(map(int, input().split())))

for i in range(n):
    print(count_intersections(i), end = ' ')

```

As you can see, I just iterate through eacher other segment and increment counter if it intersect the given one. Time complexity of my solution is $O(n^2)$. And because of this I got Tme Limit Error.

Do you know more efficient solution? Maybe some extraordinal Data Structure?

# Answer
Let's first assume there is no common boundaries between all segments.

Create the list of tuples ($pos$, $ind$) with a value ($pos$) for each boundary of every segment (thus $2n$ values) and $ind$ the index of the segment, sorted by $pos$. Sorting is achieved in $O(n \log(n)).$

Keep two counters, $open$, the number of opened segments and $close$, the number of closed segments. Both are initially at 0.

$E\[i\]$ will be an array of the segment $i$ state, where 0 means not opened yet, 1 otherwise.

$A\[i\]$ will be the $n$-element array to output, which are 0s initially.

Then loop through the list,

```
for tuple (pos, i),
    if E[i] == 0, then A[i] = close, open += 1, E[i] = 1
    else A[i] = open-A[i]-1, close += 1

```

The "-1" stands for a segment not counting himself.

This achieves $O(n)$, then still driven by the sorting $O(n \log(n))$.

Now, how to treat common boundaries ? In your exemple, I understand that segments are closed and for example \[2, 7\] does intersect \[7, 8\]. A simple way to do it (clearly not the most efficient but still $O(n)$), is to loop 3 times on the tuples at the same position:

* first, you only count the opening segments in $open$
* then, you only update $E\[i\]$ and $A\[i\]$ for both opening and closing segments
* finally, you only count the closing segments in $close$ (that now have $E\[i\] = 2$)
> 3 votes

# Answer
**Edit**: By mistake I thought we were working in 2 dimensions, this answer is for the 2d case. (I don't know why plshelp mentioned order statistics tree in his/her deleted answer because I didn't understood it but maybe he/she misunderstood like me.)

We can use a sweep line algorithm. We think of each active segments as a 1d moving point while we are sweeping the plane.

We store the list of active segments in an order statistics tree (as said by plshelp in a now deleted answer) and we use a priority queue of "events". We store in the "events" each start/end of a segment and also the (dynamically added and removed) intersections.

We continuously update for each active segment the time of intersection with the next segment in the list of active segments and store it in the priority queue. When treating an event:

1. If this is a start or an end, we add or remove the corresponding active segments.
2. If this is an intersection, we increment the number of intersections and swap the two corresponding segments in the list.

We also update the new times of intersections (removing or adding at most a low bounded number of items in the priority queue).

Notice that when inserting a new segment, the comparison function must use the current time, but the elements already in the list are necessarily sorted even if the comparison function has changed. This algorithm is in $O((n+k)\log(n))$ where $n$ is the number of segments and $k$ is the number of intersections, since the priority queue cannot store more than $3n$ events.
> 1 votes

---
Tags: algorithms
---


# Question
Title: How to convert a recursive function to a non recursive one using stack while keeping memoization?
Let's say I want to count the number of ways a string can be decoded, once encoding algorithm follows this map: `'a'=>'1', 'b'=>'2', ... 'z'=>'26'`.

I could simply count it using a recursive function as follows:

```
def num_ways(s: str) -> int:
    if len(s) > 0 and s[0] == '0':
        return 0

    if len(s) <= 1:
        return 1

    if len(s) >= 2 and int(s[:2]) > 26:
        return num_ways(s[1:])

    return num_ways(s[1:]) + num_ways(s[2:])

```

However, this function can be easily optimized by using memoization technique. (I'll avoid showing off memoization into that code to keep it tidy, but you can assume I could use such a decorator that would be responsible for this job)

Alright! But what if I want to use a stack to replace that recursion? (I don't want to use a bottom-up dynamic programming approach in this case)

So I could have something like this:

```
def num_ways_stack(s: str) -> int:
    stack = deque()
    stack.append(s)

    ways = 0
    while stack:
        cur_s = stack.pop()

        if len(cur_s) > 0 and cur_s[0] == '0':
            continue

        if len(cur_s) <= 1:
            ways += 1
            continue

        if len(cur_s) >= 2 and int(cur_s[:2]) > 26:
            stack.append(cur_s[1:])
            continue

        stack.append(cur_s[1:])
        stack.append(cur_s[2:])

    return ways

```

It works! But how can I optimize it by memoizing duplicate work as well as I'm able to do in the recursive method? Moreover, is there a better way to convert from a recursive function to a stack-based non-recursive one?

# Answer
You can simply maintain a (hash)table, just like in the recursive case. Basically, you need to treat items on the stack like function arguments in recursion. Every time you pop items off the stack for processing, you check whether the particular entry in the table had been filled first. This gives you an equivalent memoized algorithm.

Additionally, you also need to check whether the table already contains the entry when you add an item to the stack; this avoids blowing up the stack with already memoized entries.

```
maintain a hashtable T of strings.

def num_ways_stack(s: str) -> int:
    stack = deque()
    stack.append(s)

    ways = 0
    while stack:
        cur_s = stack.pop()
        if cur_s is in T, then discard cur_s and continue

        if len(cur_s) > 0 and cur_s[0] == '0':
            continue

        if len(cur_s) <= 1:
            ways += 1
            continue

        if len(cur_s) >= 2 and int(cur_s[:2]) > 26:
            stack.append(cur_s[1:])
            continue

        if cur_s[1:] is not in T:
            stack.append(cur_s[1:])
        if cur_s[2:] is not in T:
        stack.append(cur_s[2:])

    return ways

```

To answer your second question, which is if there are other methods of converting recursion to iteration, there certainly is. For certain functions that are tail-recursive (and if not, you can try rewriting them into tail-recursive ones using continuous-passing style) you can convert them to equivalent iterative algorithms without keeping a stack but a bunch of variables.

For dynamic programming recurrences, the conventional practice for iterative computation is you identify an order which can be used to correctly fill up the memoization table (e.g. row-major, column-major, or diagonal) and use nested loops to iteratively compute the values in the memoization table. This potentially saves space, as it avoids the need to maintain a stack during the recursion.
> 2 votes

---
Tags: algorithms, optimization, recursion, stacks, memoization
---


# Question
Title: How to calcualte the Big-O complexity of the following algorithm?
I have been trying to calculate the Big-O of the following algorithm and it is coming out to be O(n^5) for me. I don't know what the correct answer is but most of my colleagues are getting O(n^3).

```
for(i=1;i<=n;i++)
{
    for(j=1 ; j <= i*i ; j++)
    {
        for(k=1 ; k<= n/2 ; k++)
        {
        x = y + z;
        }
     }
}

```

What I did was start from the innermost loop. So I calculated that the innermost loop will run `n/2` times, then I went to the second nested for loop which will run `i^2` times and from the outermost loop will run `i` times as `i` varies from `1` to `n`. This would mean that the second nested for loop will run a total of `Sigma(i^2) from i=1 to i=n` so a total of `n*(n+1)*(2n+1)/6` times. So the total amount that the code would run came out to be in the order of `n^5` so I concluded that the order must be `O(n^5)`. Is there something wrong with this approach and the answer that I calculated?

I have just started with DSA and this was my first assignment so apologies for any basic mistakes that I might have made.

# Answer
```
for(i=1;i<=n;i++)
{
    for(j=1 ; j <= i*i ; j++)
    {
        for(k=1 ; k<= n/2 ; k++)
        {
        x = y + z;
        }
     }
}

```

The triple-nested loop is equivalent to the summation $$\sum\_{i=1}^{n}\sum\_{j=1}^{i^2} \sum\_{k=1}^{n/2} 1$$ $$=\frac{n}{2}(\sum\_{i=1}^{n}\sum\_{j=1}^{i^2}1)$$ $$=\frac{n}{2}(\sum\_{i=1}^{n}i^2)$$ $$=\frac{n}{2} \cdot (\frac{1}{6}n(n+1)(2n+1))$$ $$=O(n^4)$$

---

In terms of *actual* code efficiency, since `x=y+z` is invariant in the loop, any good optimizing compiler will extract the statement out of the loop (in compiler-speak, hoist the statement to loop preheader), hence making the compiled code run in $O(1)$.
> 3 votes

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


# Question
Title: Algorithmic problem with many different time/space complexity solutions
I am preparing a lesson about algorithmic thinking for beginner programmers. I would like to show them an easy to understand problem which has as many solutions as possible with different time or space complexities. Sorting quickly comes to mind but if you avoid intentionally stupid solutions such as Bogosort, you only really have O(n^2) and O(n\*log n) complexities.

In this respect I love the problem for computing the n-th Fibonacci number with integer arithmetic. You can do it exponentially as a naive approach, linearly if you are a bit clever, and even logarithmically if you are smart as hell. On the other hand, fibonacci numbers would not appear very practical to novice programmers. I would like something that is related to more practical problems as I do not want the students to think that algorithm design is something really abstract and theoretical.

# Answer
I like this one: given a string $S$, find the longest substring that appears two or more times in $S$.

There are plausible algorithms with running time $O(n^3)$, $O(n^2)$, $O(nk \log n)$, $O(nk \log k)$, $O(nk)$, $O(n \log n)$, $O(n \log k)$, and even $O(n)$, where $n$ is the length of $S$ and $k$ is the length of the longest such substring.

However I don't know if it has practical applications.

Computational biology is a good source of practical algorithm problems.
> 1 votes

# Answer
Another example is the famous subset sum problem: There is an exponential-time algorithm that works in $O(2^{n/2} \textsf{poly}(n))$. There are also pseudopolynomial time algorithms working in $O(nt)$ (via dynamic programming) and $O(n+t)$ (the later one being a randomized algorithm). Depending on the input size, one can choose between different algorithms (e.g. if $t$ is too large, then maybe the exponential-time algorithm works better).
> 0 votes

---
Tags: algorithms, time-complexity, space-complexity, introductory-lesson
---


# Question
Title: NP-completeness of a Generalized Version of Subset Sum
I am curious about the NP-completeness (or if not, an efficient algorithm) for the following generalization of the subset sum problem:

In subset sum, we are given a number $t$ and a collection $S$ of integers with $|S|=n$, and ask if we can use a subset $S'\subseteq S$ to sum up to $t$. We can generalize the problem by extending the operation allowed: instead with only addition, we can permit addition together with multiplication and parenthesization.

It seems with the extended case, the usual reduction technique of encoding 3SAT in the problem breaks down, as parenthesization together with multiplication is difficult to handle (on the other hand, it seems like multiplication itself is easier to handle, as it can be expressed as a summation of identical elements).

Intuitively this generalized problem looks much harder; however, I haven't managed to find a way to prove its NP-completeness. I'm wondering if it can be indeed proven to be NP-complete, and what sort of reduction technique could be used in this problem.

# Answer
Without loss of generality consider an instance $\langle S, t \rangle$ of subset sum where $S$ contains only positive integers and $t \ge 1$ (zeros can be dropped from $S$, and the case $t=0$ is trivial).

Now build a new instance $\langle T, t' \rangle$ of your generalized version of subset sum by choosing $T = \\{ (t+1)x : x \in S \\}$ and $t'=t(t+1)$.

If the elements of a subset $S' \subseteq S$ sum to $t$, then the elements of $\\{ (t+1)x : x \in S' \\} \subseteq T$ sum to $\sum\_{x \in S'} (t+1)x = (t+1)\sum\_{x \in S'} x =(t+1)t = t'$.

If there is a subset $T' \subseteq T$ of elements that can be arranged in an expression $E$ (that uses only addition, multiplication, and parentheses) that evaluates to $t'$, then $E$ uses no multiplication. Indeed, if $E$ used at least one multiplication, it would evaluate to at least $(t+1)^2 \> (t+1)t = t'$ since each of the involved factors must be at least $(t+1)$. As a consequence it must be that $t' = t(t+1) = \sum\_{x \in T'} x$. Let $S' = \\{ \frac{x}{t+1} : x \in T' \\} \subseteq S$. We have that $\sum\_{x \in S'} x = \sum\_{x \in T'} \frac{x}{t+1} = \frac{1}{t+1} \sum\_{x \in T'} x = \frac{t'}{t+1} = t.$

This shows that your version of generalized subset sum is NP-complete (membership in NP is trivial).
> 2 votes

# Answer
(Steven's solution works, but since I've already written mine, let it be here)

The standard reduction (e.g. as described here) almost works. All you have to do is to prohibit multiplication.

* For each number, you add a new highest-order digit, which is equal to $1$. Now, if we multiply these numbers, then we will immediately get more than the required sum.
* For each clause, we create $2$ numbers of form $1000...000$: they play the role similar to $x\_i$ and $y\_i$ (numbers for the clauses) in the slides: if we didn't select $x\_i$ or $y\_i$, we can select one of these numbers. This way, we can always make the highest-order digit to be what we want.
* The sum itself also gets a new highest-order digit, which is equal to $n + 2m$.
> 1 votes

---
Tags: np-complete, reductions
---


# Question
Title: What exactly prevents there from being a free OS like IBM's self-maintaining "z" OS?
> IBM designed IBM i as a "turnkey" operating system, requiring little or no on-site attention from IT staff during normal operation.

This is a dream of mine. Unfortunately, it costs a million dollars per nanosecond and I have $0 budget.

The opposite of this dream is the *nightmare* of being forced to manually babysit and update/mess with "some Linux distro". While some apparently have the ability to self-update, I went insane trying to actually enable this and communicate with the community about how to interpret the manual. Eventually, I gave up on it, since it was clearly not meant to be enabled, and if the system patches in FreeBSD are anything to go by, it would quickly brick the machine since those patches kept breaking everything even when manually applying them. I spent countless nights sweating and swearing with a bricked server somewhere across the world in a data center and me only having some fragile connection (if any at all) to try to fix the issues causes by the broken patches with zero support or even useful documentation.

What exactly is it that makes this IBM OS able to maintain itself? Again, I have $0 to spend, so even having two servers where I can apply updates on one while the other is actively serving, and then "switch over" only when the other is done, is entirely unrealistic to me. But even that would be a nightmare to me, something which I have zero interest in ever subjecting myself to. I don't exaggerate when I say that maintaining even a single server caused me to lose my mental health, for real, with all the constant stress and worry this caused.

A "managed" server is even more expensive, and that requires trusting "unknown bunglers" as well, which I don't. I barely trust myself.

What stops a free-of-charge OS, maybe called something like "Turnkey Linux", from maintaining itself by default and without bricking itself or any software installed? The supported software can be very limited, as long as it includes PHP and PostgreSQL.

Why is this not a thing? There must be a good reason.

# Answer
> What exactly is it that makes this IBM OS able to maintain itself?

It's not clear what you mean by that. IBM i certainly does not maintain itself. In the companies I know that use IBM i, an OS update is a big f…ing deal that involves shutting down most operations in the entire company and the entire IT department pulling an all-weekender.

In the company I know best, they had a large machine for production, and two older, smaller machines for development and testing. Usually, one of the development and testing machines would run the same versions as the production machine, and the other one would run the next OS release. When it came time to update the production machine, they would first update one of the development machines to the exact versions that the production machine was currently running and the other one to the exact versions that they wanted to update to.

Then, they would start migrating their applications to the new OS release, which took anywhere from a couple of weeks to a couple of months. Once they had migrated and tested all applications to the new OS release, they set a date for doing the migration, which was always on a weekend, preferably a long weekend with a bank holiday on Friday or Monday.

On Friday afternoon, they would stop all business processes as far as possible (which in itself required weeks of planning and prior warning) and move the processes that couldn't be stopped to the development machine. (Note that the development machine was much smaller and much older, so it could only take the load of the few most essential services.)

Then, they updated the production machine, which typically takes an entire day, installed the updated versions of the applications, and after thorough testing, moved the processes back to the now updated production machine.

In later years, the company had grown so much that it was not possible to do this process anymore within the timeframe of one weekend, so instead they rented an identical clone of their production machine from IBM for a couple of weeks, so they could run the old and new OS in parallel and migrate the applications one-by-one.

> What stops a free-of-charge OS, maybe called something like "Turnkey Linux", from maintaining itself by default and without bricking itself or any software installed?

Nothing stops it from doing so.

Or, to be more precise: the Free Software / Open Source *community* is a *community*. In a community, people pitch in with their help. So, for *every* question of the form "why doesn't the community do X", the answer is *always* "because there are only people asking why the community is not doing X and no people doing X".

Free Software / Open Source projects have the *unique* feature that if there is something you don't like about them, *you have the power to change it*. However, the change will only come about *if* you **do** something about it. Complaining is not doing.

And, by the way, my WiFi router *is* a Linux computer that completely maintains and updates itself, so the thing that you are asking why it doesn't exist, actually *does* exist.
> 1 votes

---
Tags: philosophy
---


# Question
Title: Interactive programming language minimizing reevaluations
I'm looking for any programming language, DSL, library or pattern for **live scripting** but minimizing the expressions reevaluation.

Topological sorting provides non-revaluation of expressions.

Memoization provides a simple way of not re-evaluating but is a waste of memory.

A form of topological ordering can be achieved by maintaining (in each language object) a version number for each dependency but it does not seem to be easily composable/scriptable.

Which available tools would be the most suitable?

Thank you!

(I think the closest I've found might be https://www.shinoe.org/cameleon)

# Answer
The specific *CS* topic resolving the question is:

Incremental computing

A detailed article explaining a related DSL is:

IceDust: Incremental and Eventual Computation of Derived Values in Persistent Object Graphs
> 3 votes

---
Tags: programming-languages
---


# Question
Title: Bottom-up Mergesort vs Natural Merge Sort
I ran into natural mergesort in this Wikipedia page: https://en.wikipedia.org/wiki/Merge\_sort#Natural\_merge\_sort

However, I can't find much information regarding:

1. The algorithm(s) to achieve natural mergesort, and the pros and cons of each method
2. How natural mergesort compares to bottom-up mergesort (pros and cons of each w.r.t the other)

In short, I'm looking for resources that would teach me algorithms to do natural mergesort, and how to weigh it against the usual bottom-up mergesort

# Answer
Natural Mergesort usually refers to Timsort. In terms of comparison to bottom-up mergesort, Timsort has $O(n)$ best-case running time where as bottom-up mergesort is at least $O(n\log n)$ on any input.

However, analysis of the worst-case running time of Timsort proves to be more tricky; an 2018 paper \[1\] establishes that its worst-case time complexity is $O(n\log \rho)$, where $\rho$ is the number of maximal monotonic sequences in the input array.

\[1\]: Nicolas Auger, Vincent Jugé, Cyril Nicaud, Carine Pivoteau, "On the Worst-Case Complexity of TimSort"
> 2 votes

---
Tags: algorithms, sorting, mergesort
---


title: Is this Language decidable?

text:
# Question
Title: Is this Language decidable?
As the title says; is this language decidable and how do you prove it?

$$L =\\{\langle M\rangle \mid M \text{ is a Turing Machine and there is an input that } M \text{ halts on} \\} $$

# Answer
Your language is not decidable. To show that it suffices to notice that the existence of a Turing machine $T$ that decided $L$ implies the existence of a Turing machine that solves the halting problem.

Indeed, given any Turing machine $M$ with input $x$ you can construct a Turing machine $M'$ that ignores its input, writes $x$ on the tape, and then simulates $M$. Clearly $M'$ halts (regardless of its input) if and only if $M$ halts on input $x$. We can decide whether $M'$ halts by checking whether $M' \in L$ using $T$ with input $M'$.
> 0 votes

---
Tags: turing-machines, undecidability
---


title: Circular Queue using Dynamic Array

text:
# Question
Title: Circular Queue using Dynamic Array
I'm learning data structures from "Fundamentals of Data structures in C" by Sahni . In the topic, Circular Queue using Dynamic Array, the author has mentioned below point,

> Let *capacity* be the initial capacity of the circular queue,We must first increase the size of the array using realloc,this will copy maximum of *capacity* elements on to the new array. To get a proper circular queue configuration, we must slide elements in the right segment(i.e, elements A and B) to the right end of the array(refer diagram 3.7.d). The array doubling and the slide to the right together copy at most **2 * *capacity* -2** elements.

I understand array doubling copies at most *capacity* elements. But how does array doubling and slide to right copy at most **2 * *capacity* -2** elements??

# Answer
> 1 votes
I think the author is just saying the circular list has capacity of $n-1$ where $n$ is the total cells. When the array is doubled there is copying of these $n-1$ elements to new array in addition with shifting of these $n-1$ elements in the worst case, thus making it total $2n-2$ doubling and sliding in the worst case.

# Answer
> 0 votes
In above example queue capacity is 8. A circular queue can have capacity - 1 elements. Here it is 7. While array doubling those 7 elements are copied. Then suppose front = 0 and rear = 7, then the elements from 1 to 7 has to be moved to the right. Here it copies 7 elements. Hence the total is 7 + 7 = 14. 2 * 8 - 2 = 14

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


# Question
Title: Why does paging not have external fragmentation?
I have read that paging does not suffer from external fragmentation as the frames and the pages are all of the equal sizes, but when we store a last level page table in a frame at that time it may not fully occupy the frame. Similarly, if n such page tables are stored, that does not occupy the frames entirely, then there can be a case where all the gaps exceed a page size. Then there should be external fragmentation, right? So why is it said that paging does not have external fragmentation?

# Answer
The details depend on the processor architecture, but the principle is the same everywhere. All page tables of a given type at a given level have the same size. When all memory blocks have the same size, there is no fragmentation: a memory block is allocated starts at an offset which is a multiple of the block size, so the size of any hole is a multiple of the block size. If a gap opens in the page table, the operating system can use this gap the next time it needs to allocate a page table.

Furthermore the size of a page table pretty much always divides the size of a page — both are powers of two. So a page contains a whole number of page tables with no leftover space. This means that the operating system can allocate pages for page tables and no table spreads over multiple pages, so there's no need for the page tables to be consecutive and therefore there's no fragmentation of the address space for the page tables themselves.
> 4 votes

# Answer
The collection of internal fragmentation do not contribute to external fragmentation. **External fragmentation is contributed by the empty space which is EXTERNAL to partition(or page)**. So suppose if there are only two frames in main memory ,say of size 16B, each occupied by only 1B data. The internal fragmentation in each frame is 15B. The total unused space is 30B. Now if you want to load one new page of some process, you will see that you do not have any frame available. You are unable to load a new page eventhough you have 30B unused space. Will you call this as external fragmentation? Answer is no. Because these 15B unused space are INTERNAL to the pages. So in paging, internal fragmentation is possible but not external fragmentation.
> 0 votes

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


# Question
Title: Given two identical DOM trees find same node in tree B
So for the question 'Given two identical DOM trees, and an element in one tree, find the same element in the second tree'.

I can solve it in two ways -

1. Start at the given element and traverse up to the root of tree A - save the path and then follow the path down the second tree to the element.
2. Start at the root and traverse both trees at the same time using breadth-first search - once I find node A in tree A return the current node in tree B.

The complexity for the second approach will be O(N) as the worst case I could end up going through every node in the tree to find the element.

For the first approach is the complexity simply O(P) where P is the length of the path from the given node to the root? At most I will go up against P nodes and then down P nodes in tree B and 2P ~= P. I heard someone say it's Log(N) but I'm not sure how that could be.

# Answer
You are right, the complexity of the second algorithm is $O(P)$ where $P$ is the depth of the given vertex in the second tree. Notice that, without additional assumptions, it might very well be $P=\Omega(N)$ (think, e.g., of a path rooted in one endpoint where the given vertex is the other endpoint).

If the second tree is somehow "balanced", for some reasonable definition of balanced\* then its height will be at most $O(\log n)$, hence $P=O(\log n)$.

\*Since your tree is not necessarily binary you'd have to provide a suitable definition of balanced. A sufficient condition for $P=O(N)$ would be for the heights of the two tallest subtrees rooted in two children of each node of the second tree to differ by at most an additive constant.
> 0 votes

---
Tags: time-complexity, trees
---


# Question
Title: How can I solve this constrained assignment problem?
The assignment problem is defined as follows:

> There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one task to each agent in such a way that the total cost of the assignment is minimized.

The number of tasks is larger than the number of agents.

My problem statement though imposes an additional constraint on the above.

> Each task belongs to exactly one 'category'. Each 'category' has an associated maximum number of tasks that can be assigned. Enforce this constraint on the earlier definition.

For a layman's example, consider this -

> A restaurant serves n customers (agents), and has on it's menu m possible dishes (tasks), with m \> n. Each customer gives his preference for each of the m dishes, which is the cost for this particular assignment problem. Find a solution which minimizes cost i.e. which gives each customer a dish that is as high on their preference as possible.
>
> Additionally, each dish belong to a certain cuisine (category). The restaurant can only make a certain number of dishes per cuisine. Enforce this constraint on the problem above.

I understand that this is a very specific problem, but any help would be appreciated.

I am currently solving the first part of the problem using the Hungarian Algorithm for assignment.

# Answer
> 0 votes
Introduce dummy variables with zero cost so that it becomes a balanced assignment, which can be solved with Hungarian Algorithm.

# Answer
> 5 votes
This can be formulated as an instance of minimum-cost flow problem. Have a graph with one vertex per agent, one vertex per task, and one vertex per category. Now add edges:

* Add an edge from the source to each agent, with capacity 1 and cost 0.
* Add an edge from each agent to each task, with capacity 1 and cost according to the cost of that assignment.
* Add an edge from each task to the category it is part of, with capacity 1 and cost 0.
* Add an edge from each category to the sink, with capacity given by the maximum number of tasks assignable in that category and cost 0.

Now find the minimum-cost flow of size $t$, where $t$ is the number of tasks. There are polynomial-time algorithms for that.

# Answer
> 0 votes
I know it is a bit late for an answer to that post. Maybe you should have closed it within a year of no relevant answer. The problem is not that easy, just with one additional constraint, there is a lot of work dealing with the problem. You can use branch and bound algorithm. In the branch and bound, there are different ways to proceed.

---
Tags: algorithms, optimization, combinatorics, assignment-problem
---


# Question
Title: Are there any examples of projects running a program that will take many years to finish its job?
There are algorithms that are said to be unfeasible to be applied in practice due to their time complexity. In textbooks, it's common to see remarks like "it would take hundreds of years" about using them. Unfortunately, it's often the case an inefficient algorithm is the only proven solution for an interesting problem.

Is there an example of a project running one of those algorithms where the participants know they won't be around to see the results hoping to solve a problem for the next generations?

# Answer
There have been several programs running for very long times, like the Great Internet Mersenne Prime Search, which has been going for some 25 years now.
> 1 votes

# Answer
The best answer I can think of is Shigeru Kondo running an algorithm for 371 days to compute the first 10,000,000,000,050 digits of pi.

Link
> 0 votes

# Answer
The computers on board Voyager 1 have been running for almost 43 years at the time of writing. I believe this holds the record for the longest uninterrupted uptime of any piece of software.
> 0 votes

---
Tags: time-complexity
---


title: How to prove ln(n) = Θ(log2 n)?

text:
# Question
Title: How to prove ln(n) = Θ(log2 n)?
This is a homework problem and I'm not sure how to do it correctly. It says "Prove ln(n) = Θ(log2 n) with n = odd number".

Bu using Natural logarithm rules, we can somehow know this is partcially true

However, I'm stuck with this since I don't understand how to do the whole procedure.

# Answer
You correctly pointed out that $\ln n = \frac{\log\_2n}{\log\_2 e}$. You can rewrite this as $\ln n = \frac{1}{\log\_2e}\cdot\log\_2n$. Since $\Theta(\cdot) $ allows you to drop constant factors (and as @Pseudonym pointed out, $\frac{1}{\log\_2e}$ is constant), it follows that $\ln n = \Theta(\log\_2n)$
> 1 votes

---
Tags: algorithm-analysis, asymptotics
---


# Question
Title: Check if a NFA accepts a string of non-prime length
> Given a nondeterministic finite automaton $A$, give an algorithm that checks whether the language $L(A)$ decided by $A$ contains a string whose length is a composite (i.e. not prime) number.

My obvious \[edit: wrong\] answer is that, if $A$ has $n$ states, then I can simply check if it accepts any word of composite length $\le n$. This violently works, since the input alphabet is defined as finite.

Is there a more refined solution? And would that entail some involved graph search?

P.S. To give some context, this comes from an exercise that previously asked to find algorithms that solved the emptiness problem for regular languages, and the problem of equivalence between two NFAs. I solved those in an analogously simple fashion.

# Answer
The basic idea is that if a regular language is infinite, then it contains a word of infinite length. Indeed, the pumping lemma shows that the set of lengths of words in the language contains an arithmetic progression, and every arithmetic progression contains a composite integer.

We can check whether the language accepted by an NFA is infinite as follows:

* Remove all states which are unreachable form an initial state, or from which a final state cannot be reached.
* Check whether the remaining graph contains a cycle.

If the language is infinite, you can immediately answer "Yes". Otherwise, the NFA only accepts words of length at most $n-1$ (where $n$ is the number of states), and you can use the algorithm that you suggest. Your algorithm can be slightly optimized by identifying all letters in the alphabet.
> 1 votes

---
Tags: algorithms, regular-languages, automata, finite-automata
---


# Question
Title: Efficient Algorithm to Find the n-th Odious Number
An odious number is defined as an integer that has odd binary Hamming weight. I need an implementation of algorithm that finds the nth odious number, preferably recursive. Any ideas? A python script is also wanted, but I can write it myself once the algorithm is found.

More description can be found on formula section in OEIS: A000069.

# Answer
> 5 votes
Here is the recursive formula for odious numbers, $$\begin{align} a\_1&=1,\\ a\_{2n} &= 6n-3 -a\_n,\\ a\_{2n+1} &= a\_{n+1} + 2n. \end{align}$$ The formula can be proved easily by observing, as greybeard pointed out, there is exactly one odious number among $2k-1, 2k$ for all positive integer $k$.

Here is a simple algorithm in Python to compute the $n$-th odious number.

```
def odious_number(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return 3 * (n - 1) - odious_number(n // 2)
    else:
        return odious_number((n + 1) // 2) + n - 1

if __name__ == "__main__":
    for i in range(1, 16):
        print(odious_number(i), end=", ")
    # Output: 1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28,

```

---

There is also a "closed" formula. $$a\_n = 2n - 1 - \text{hamming\_weight}(n - 1)\ \\%\ 2$$

So, we have the following one-liner.

```
def odious_number(n):
    return 2 * n - 1 - (n - 1).bit_count() % 2

```

<sub> `int.bit_count()`, which returns the Hamming weight of an integer, is available since Python 3.10. Before that version of Python, we can use, for example, `bin(i).count('1')`. </sub>

# Answer
> 5 votes
Here is an alternative answer, following greybeard's advice. For each $k$, the two integers $2k,2k+1$ contain exactly one odious number. Hence the $i$th odious number is either $2i$ or $2i+1$: it is $2i$ if $i$ itself is odious, and $2i+1$ otherwise.

Stated differently, the $i$th odious number is $2i+1-b$, where $b$ is the parity of the number of ones in $i$.

---
Tags: algorithms, number-theory, counting
---


# Question
Title: Disprove unrealistic speed-up of total Turing machines
Let $T\_1$ be a total Turing machine deciding language $L\_1$, and let $I\_1$ and $I\_2$ be two separate inputs to $T\_1$. Further, let $I\_{c}$ be $I\_2$ concatenated to $I\_1$ with some separation symbol in between, and let $S\_{T}(I)$ be the number of steps total TM $T$ needs to run until it accepts/rejects input $I$. I am wondering about the following two statements:

> For every $T\_1$ there exists another total Turing machine $T\_2$ such that for all valid inputs $I\_1 \neq I\_2$ for $T\_1$, $T\_2$ accepts $I\_c$ if $T\_1$ accepts $I\_1$ **or** if $T\_1$ accepts $I\_2$.

> For every $T\_1$, there exists a $T\_2$ with the above property such that for all valid inputs $I\_1 \neq I\_2$, it holds that $S\_{T\_2}(I\_c) \< S\_{T\_1}(I\_1) + S\_{T\_1}(I\_2)$

To me, it seems as if the second statement would imply an impossible speed-up and should have an obvious counterexample, but I haven't been able to come up with one.

# Answer
> 3 votes
Suppose that the input alphabet is $\\{0,1\\}$, and consider the language $L\_1 = 0^\*$. We can easily construct a Turing machine $T\_1$ such that $S\_{T\_1}(I) = |I|+1$. On the other hand, $S\_{T\_2}(I\_c) \geq |I\_c|+1$. Since $|I\_c|=|I\_1|+1+|I\_2|$, we get $$ S\_{T\_2}(I\_c) \geq |I\_1|+1+|I\_2|+1 = S\_{T\_1}(I\_1) + S\_{T\_1}(I\_2). $$

---
Tags: turing-machines, time-complexity
---


title: Shortest path in modular arithmetic

text:
# Question
Title: Shortest path in modular arithmetic
Suppose we have 7 vertices, each of which corresponds to a different integer modulo seven. The edge exists between two vertices x and y if x + 3 ≡ y mod 7. For example, there is an edge between 0 and 3, and an edge between 5 and 2. What is the length of the shortest path between 0 and 1?

My method to get the answer is to apply the definition of congruence. The edge exits iff $7 | x + 3 - y$. Thus, I got one cyclic graph and then get the answer is 2. Is there any method I can play with modular arithmetic without drawing a graph so that I can get shortest path between node 0 and node 1?

# Answer
Let us consider the more general case in which you have $n$ vertices, and you connect $x,y$ if $x-y \equiv a \pmod{n}$ (in your case, $n = 7$ and $a = 3$).

Your graph is a union of disjoint cycles. When $n$ is prime (as in your case), it is a single cycle. Hence if you want to get from $x$ to $y$, either you keep adding $a$ (modulo $n$), of you keep subtracting $a$ (modulo $n$). If you add $m$ times the value $a$ (where $m$ is possibly negative) then $x+ma \equiv y \pmod{n}$, that is, $ma \equiv y-x \pmod{n}$. Let us now assume that $(a,n) = 1$ (for example, $n$ is prime and $1 \leq a \leq n-1$). Then $m \equiv a^{-1}(y-x) \pmod{n}$.

Solving the equation above (assuming $x \not\equiv y \pmod{n}$), there will be one solution $m\_+$ in the range $1,\ldots,n-1$ and another $m\_-$ in the range $-1,\ldots,-(n-1)$. The distance is $\min(m\_+,-m\_-)$.

In your case, $n = 7$ and $a = 3$. We can compute $a^{-1} = 5$. If $x = 0$ and $y = 1$ then $a^{-1}(y-x) = 5$, and so $m\_+ = 5$ and $-m\_- = 2$. So the shortest path goes backwards for two steps: $0 \to 4 \to 1$.
> 2 votes

# Answer
We can easily generalize this problem: Given a finite group G, two elements g and h in G, and a subset S of G, find the shortest path from g to h in the graph whose vertices are the elements of G and whose edges are the elements of S or the respective inverses of the elements of S, i.e., two vertices x and y are adjacent if and only if y=xr for some r that is either an element of S or is an inverse of some element of S. Note that this graph has |G| vertices and |S||G| edges in an explicit or implicit computer implementation. A simple breadth-first search algorithm on this graph starting at the vertex g and terminating once the vertex h is reached will yield the shortest path between g and h in time O(|G| + |S||G|)=O(|S||G|) time. Moreover, we do not actually have to construct this graph; this is because we already know what all the edges are. We just have to loop through the neighbors of the current group element at every iteration of the breadth-first search algorithm.

In your case, for any positive integer n, we have S={3 mod n} and that the order of the additive group of residue classes mod n is n, so we can find the shortest path between any two specified residue classes mod n in O(n)=O(n) time.
> 1 votes

# Answer
You need to find integers $a$ and $b$ such that

$3a = 7b + 1$

and from all the (infinitely many) values of $a$ you want the one that minimises $|a|$. In this case, we can see by trial and error that the set of solutions is $a=5+7n$ for integer values of $n$, and to minimise $|a|$ we take $n=-1$, so that $a=-2$, and the shortest path is $0 \to 4 \to 1$.

In general, there will be infinitely many solutions to $pa = qb + 1$ as long as $p$ and $q$ are co-prime (do not share any common factors other than $1$), and you can use the Euclidean algorithm to find the smallest positive value of $a$. If the smallest positive value of $a$ is $a\_0$ then the value of $a$ that minimises $|a|$ is either $a\_0$ or $a\_0 - q$.
> 1 votes

---
Tags: number-theory, modular-arithmetic
---


# Question
Title: To what extent is an x86 machine equivalent to a Turing Machine?
**To what extent is the abstract model of computation specified by the x86 language Turing complete?**

The above question is related to this question:
Is C actually Turing-complete?

In theoretical computer science the random-access stored-program (RASP) machine model is an abstract machine used for the purposes of algorithm development and algorithm complexity theory.

> **The RASP is a random-access machine (RAM) model** that, unlike the RAM, has its program in its "registers" together with its input. The registers are unbounded (infinite in capacity); whether the number of registers is finite is model-specific. Thus the RASP is to the RAM as the Universal Turing machine is to the Turing machine. The RASP is an example of the von Neumann architecture whereas the RAM is an example of the Harvard architecture. https://en.wikipedia.org/wiki/Random-access\_stored-program\_machine

# Answer
# RIP relative addressing of the x86 language provides access to unlimited memory

An abstract machine having a tape head that can be advanced in 0 to 0x7FFFFFFF increments an unlimited number of times specifies a model of computation that has access to unlimited memory. The technical name for memory addressing based on displacement from the current memory address is relative addressing.

I am focusing on building a precise bridge between conventional high level concrete programming models (none of which can possibly be Turing Complete) and the closest abstract model that is Turing complete. To do this we must necessarily make at least minimal adaptations to the concrete model.

One concrete model of computation requiring very little change to adapt it to become a Turing complete abstract model of computation is the 32-bit signed RIP relative addressing of the x86-64.

If we take this machine language and get rid of all absolute addressing modes, leave the size of memory and the width of the instruction pointer unspecified then with these minimal changes the abstract model based on the x86-64 becomes Turing complete.
> 0 votes

# Answer
The difference is: since x86 machines are finite, Turing machines can decide languages (decision problems) that cannot be decided by any x86 machine.

---

As I explained before, the idea of 'the set of decidable computations' is a category error. Decidability is a property of formal languages (or equivalently, of decision problems), not of computations. So, no, the statement in the second paragraph of your question is not correct. It's not even wrong -- it is neither true nor false.

I suspect that perhaps you have found a statement of the Church-Turing thesis that is worded in a way that is confusing. I suggest reading a standard reference on the Church-Turing thesis, and don't rely solely on the wording you have bolded.

It is true that every decision problem that can be solved by an x86 machine can be solved by a Turing machine (or, equivalently, every language that can be decided by an x86 machine can be decided by a Turing machine). This is true because you can program a Turing machine to simulate the behavior of an x86 machine. However, the converse is not the case: any real x86 machine has a fixed and finite amount of memory, while a Turing machine can use an unlimited amount of storage on its tape, so there are decision problems that can be solved by a Turing machine, but not by an x86 machine. (Even if we take into account the amount of storage provided by disks, disks use fixed-length addresses, so there is a fixed and finite upper bound on the maximum amount of disk storage that can be addressed from a standard x86 machine.)

If you wanted an x86 machine to be equivalent in power to a Turing machine, you'd have to provide some way to extend its amount of storage without limits. If you had a way to do that, then yes, any decision problem that can be decided by one could be decided by the other: each one could simulate the other.
> 6 votes

# Answer
For a real computer, everything is decidable. There is a (far bigger than astronomically but) finite number of possible states, so any program will eventually halt or enter the exact same state a second time, in which case it will never halt.

Of course that is purely theoretical. It is (based on quantum physics and the total energy in the universe) physically impossible to run a 256 bit counter from zero to $2^{256}-1$.

(Deleted my comments responding to someone who is unwilling to understand).
> 4 votes

# Answer
# Mapping x86 programs to a Turing equivalent abstract model

The following abstract machine maps the x86 language to machines with a fixed pointer size of the largest unlimited integer address that is actually needed by the computation.

```
Instruction
     : INTEGER ":" OpCode
     | INTEGER ":" OpCode Integer
     | INTEGER ":" OpCode Integer "," Integer

HEXDIGIT [a-fA-F0-9]
INTEGER  {HEXDIGIT}+
OPCODE   HEXDIGIT{4}

Address:OpCode
Address:OpCode Param
Address:OpCode Param, Param

```

Computational equivalence means that two machines will always produce equivalent output for equivalent input or fail to halt on equivalent input for a set of computations.

The set of computations not requiring more memory than is available for x86/x64/C computations will always have corresponding output for corresponding input or fail to halt on corresponding input exactly corresponding to the behavior of a Turing machine on equivalent input.
> 0 votes

---
Tags: turing-machines, turing-completeness, church-turing-thesis
---


# Question
Title: Can you insert into sorted list with time O(1)?
Wondering if this was possible. If I have a sorted list, can I find the right spot for an integer and insert it, all in O(1) time? The only way I can think to do this is via having a MASSIVE hashmap with one slot for each possible integer. 2 billion different integers * 4 bytes per integer = 8 gigabytes....but it'd technically work. There has to be a better way to do this though, right?

# Answer
Sounds like you want a solution for bounded integers, 32-bit for example. If so, any sorted dictionary whose complexity depends on the key length only will do what you want. Two examples are binary trie and van Emde Boas tree.
> 1 votes

# Answer
One way to convince yourself it is not possible is to consider what it would enable. Assume there exists an O(1) algorithm for insertion into an unbounded sorted array, CONST\_INSERT. Then we can define a O(n) sorting algorithm as follows:

* Let $L$ be an empty list $()$ and $U = (u\_1, u\_2, \ldots u\_n)$ be an unsorted list.
* Iterate over $i: 1 \rightarrow n$, inserting $u\_i$ into $L$ using CONST\_INSERT

This produces a sorted array, since at the end of every iteration $i$, $L$ will be exactly a sorted list of $(u\_1 \ldots u\_i)$. And it will have a runtime of O(n).

From a practical perspective, if an O(n) sorting algorithm existed it would be very useful, so you'd likely know about it. From a theory perspective, resources like this might help you convince yourself that no such sorting algorithm could exist.
> 1 votes

# Answer
One thing before I explain: `HashMap` doesn't use an array that big, it uses *chaining*, which is another concept you'll have to look up. And if you're talking about creating an array size 2 billion, that still won't work because you still have to scan the 2 billion entries in the array. Ok, technically that's O(1), but only because O(2 billion) is counted as O(1).

I actually wondered about this for a long time. If you think about it, there is no possible way even with the `HashMap`. Before I get into why `HashMap` doesn't work, if you don't use a `HashMap`, you'll have to scan the whole size that you have to insert. Now to the `HashMap` part, after inserting you're number, you'll have to update ***every*** entry after that. And if you don't, you'll get an O(1) insertion *once*, but after that you'll get wrong insertions.
> 0 votes

---
Tags: time-complexity, arrays
---


# Question
Title: Algorithms that must compute a global property?
Could you give me examples of polynomial-time algorithms that must compute a global property over their entire input? A purely illustrative example of this might be a graph algorithm that somehow must count the total number of nodes before computing its final answer.

# Answer
A silly example: Checking if a graph has more than m nodes. :-)

Some more interesting examples:
> 1 votes

---
Tags: algorithms, reference-request
---


title: Google Foobar Level 4 - Graph Problem

text:
# Question
Title: Google Foobar Level 4 - Graph Problem
So, I have been solving problems in Google Foobar for the past two weeks or so ans has reached Level 4. The first problem is as stated below and I have come up with a solution which is able to pass all test cases except one. I have been stuck on it for the past 3 days and hasn't been able to made any progress so far. Can someone help me by pointing me in the right direction.

Here's the problem statement:

# Running with Bunnies

You and your rescued bunny prisoners need to get out of this collapsing death trap of a space station - and fast! Unfortunately, some of the bunnies have been weakened by their long imprisonment and can't run very fast. Their friends are trying to help them, but this escape would go a lot faster if you also pitched in. The defensive bulkhead doors have begun to close, and if you don't make it through in time, you'll be trapped! You need to grab as many bunnies as you can and get through the bulkheads before they close.

The time it takes to move from your starting point to all of the bunnies and to the bulkhead will be given to you in a square matrix of integers. Each row will tell you the time it takes to get to the start, first bunny, second bunny, ..., last bunny, and the bulkhead in that order. The order of the rows follows the same pattern (start, each bunny, bulkhead). The bunnies can jump into your arms, so picking them up is instantaneous, and arriving at the bulkhead at the same time as it seals still allows for a successful, if dramatic, escape. (Don't worry, any bunnies you don't pick up will be able to escape with you since they no longer have to carry the ones you did pick up.) You can revisit different spots if you wish, and moving to the bulkhead doesn't mean you have to immediately leave - you can move to and from the bulkhead to pick up additional bunnies if time permits.

In addition to spending time traveling between bunnies, some paths interact with the space station's security checkpoints and add time back to the clock. Adding time to the clock will delay the closing of the bulkhead doors, and if the time goes back up to 0 or a positive number after the doors have already closed, it triggers the bulkhead to reopen. Therefore, it might be possible to walk in a circle and keep gaining time: that is, each time a path is traversed, the same amount of time is used or added.

Write a function of the form solution(times, time\_limit) to calculate the most bunnies you can pick up and which bunnies they are, while still escaping through the bulkhead before the doors close for good. If there are multiple sets of bunnies of the same size, return the set of bunnies with the lowest prisoner IDs (as indexes) in sorted order. The bunnies are represented as a sorted list by prisoner ID, with the first bunny being 0. There are at most 5 bunnies, and time\_limit is a non-negative integer that is at most 999.

For instance, in the case of
\[
\[0, 2, 2, 2, -1\], # 0 = Start
\[9, 0, 2, 2, -1\], # 1 = Bunny 0
\[9, 3, 0, 2, -1\], # 2 = Bunny 1
\[9, 3, 2, 0, -1\], # 3 = Bunny 2
\[9, 3, 2, 2, 0\], # 4 = Bulkhead
\]
and a time limit of 1, the five inner array rows designate the starting point, bunny 0, bunny 1, bunny 2, and the bulkhead door exit respectively. You could take the path:
Start End Delta Time Status
\- 0 - 1 Bulkhead initially open
0 4 -1 2
4 2 2 0
2 4 -1 1
4 3 2 -1 Bulkhead closes
3 4 -1 0 Bulkhead reopens; you and the bunnies exit

With this solution, you would pick up bunnies 1 and 2. This is the best combination for this space station hallway, so the answer is \[1, 2\].

# Solution

There are two parts of the solution that I have come up with:

1. Negative Cycle - if there is any negative cycle in the graph then we can just loop it as many times as required and pick all the bunnies. I am doing this by Floyd Warshall algorithm as well as getting all the shortest pair paths which can be used in case there is no negative cycle
2. DFS - In case there is no negative cycle, I simply start from the start point and try to get all the permutations of the order in which we can travel the graph and then check if the solution is correct at the end point.

<pre><code>    static int size;
    static List < Integer > ans;
    public static int[] solution(int[][] times, int times_limit) {
        // Your code here
        int n = times.length;
        if (n <= 2 || (n != times[0].length)) {
            return new int[] {};
        }
        boolean negCycle = check(times, n);
        if (negCycle) {
            int[] ans = new int[n - 2];
            for (int i = 0; i < n - 2; i++) {
                ans[i] = i + 1;
            }
            return ans;
        } else {
            size = 0;
            ans = new ArrayList < >();
            boolean[] visited = new boolean[n];
            visited[0] = true;
            for (int i = 1; i < n - 1; i++) {
                dfs(i, times_limit - times[0][i], times, new ArrayList < >(), visited);
            }
            if (ans.size() == 0) {
                return new int[] {};
            }
            int[] ret = new int[ans.size()];
            for (int i = 0; i < ret.length; i++) {
                ret[i] = ans.get(i);
            }
            Arrays.sort(ret);
            return ret;
        }
    }

    public static void dfs(int u, int time, int[][] times, List < Integer > list, boolean[] visited) {

        int n = times.length;
        if (time <= -999 || (u == n - 1 && time < 0) || (size == n - 2)) {
            return;
        }
        if (time >= 0 && u == n - 1) {
            if (list.size() > size) {
                ans = new ArrayList < >(list);
                size = list.size();
            }
            return;
        }
        if (visited[u]) {
            return;
        }
        visited[u] = true;
        list.add(u - 1);
        for (int v = 1; v < n; ++v) {
            if (v == u) {
                continue;
            }
            dfs(v, time - times[u][v], times, list, visited);
        }
        list.remove(list.size() - 1);
        visited[u] = false;
    }

    public static boolean check(int[][] times, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (times[i][k] + times[k][j] < times[i][j]) {
                        times[i][j] = times[i][k] + times[k][j];
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (times[i][i] < 0) {
                return true;
            }
        }
        return false;
    }
} ```

</code></pre>

Please let me know if there's something wrong in my methodology.

# Answer
I found the issue in my code. It was a very stupid mistake from my end. It was not passing the test case where there was a negative cycle in the graph because I was passing the result based on 1 as index starting instead of 0.

The original return value was being made by this:

```
for (int i = 0; i < n - 2; i++) {
      ans[i] = i + 1; // Extra one here
}

While it should be:
for (int i = 0; i < n - 2; i++) {
      ans[i] = i;
}

```
> 1 votes

---
Tags: graphs, shortest-path
---


# Question
Title: Efficiently selecting a random subset of size $m$ from a set of size $n$
This is a cross post of my question here on math.se.

I have a list of $n$ items and would like to randomly select an $m$ set from it efficiently (in terms of time complexity). Also, I want all possible subsets to be selected with equal probability. The obvious solution is to pick a random integer from $1$ to $n$ and choose the corresponding element, then repeat $m$ times, not counting the event in which one chooses and already chosen element. This becomes increasingly inefficient as $m$ approaches $n$ so for $m\>n/2$ it would make sense to instead to pick a $(n-m)$-set and return its compliment.

For values of $m$ close to $n/2$, a better solution I think would be to consider each of the $n$ elements and decide either to pick that element or discard it, each time updating the probability of picking or discarding depending on the number of elements chosen vs discarded prior. Specifically, the algorithm would go as follows (python):

```
def randomSubset(n,m):
  L = []
  for i in range(n):
    if uniform(0,1)<m/(n-i): L,m = L+[i],m-1
  return L

```

However I am concerned that this may not result in each subset being chosen with equal probability.

I have two questions. First, does this algorithm pick subsets with equal probability (if so, I'd like a proof that it does and if not I'd also like a proof that it doesn't). Second, more broadly I would like to know what good solutions exist to this problem. Clearly if $m\<\<n$ then the first method is better than the second however at some point the second method (if it does in fact work) is better than the first. Moreover, an entirely different approach may be best in general.

# Answer
> 3 votes
The probability that the element $1$ belongs to a random $m$-subset of an $n$-element set is $m/n$. Therefore you should include $1$ in your subset with probability $m/n$.

If you put $1$ in your subset, then you are left with choosing an $(m-1)$-subset of an $(n-1)$-element set.

If you didn't put $1$ in your subset, then you are left with choosing an $m$-subset of an $(n-1)$-element set.

This means that you have to slightly update your algorithm, replacing $m$ with $m-|L|$.

The resulting algorithm is somewhat similar to reservoir sampling.

A third approach, with some similarities, is generating a random permutation of $1,\ldots,n$ and selecting the first $m$ entries.

The downside of all of these approaches are that they run in time $\Theta(n)$, whereas for $m \ll \sqrt{n}$, your first algorithm runs in (expected) time $\tilde\Theta(m)$.

We can improve on the $\Theta(n)$ running time as follows. We will generate a random ordered $m$-subset given $m$ indices $i\_1,\ldots,i\_m$, where $i\_j \in \\{1,\ldots,n-(j-1)\\}$. The $j$'th element in the subset will be the $i\_j$'th smallest number in $\\{1,\ldots,n\\}$ out of the numbers not already chosen.

In order to complete the description of the algorithm, we need to solve the following problem: given $S \subseteq \\{1,\ldots,n\\}$ and $i$, find the $i$'th smallest element in $\overline{S}$. We can assume that $S$ is stored in a structure (such as a self-balancing binary tree) which can efficiently answer the following type of query: given $x$, how many elements in $S$ are smaller than $x$. We can then find the $i$'th smallest number in $\overline{S}$ using binary search.

Overall, this algorithm runs in $\tilde\Theta(m)$ for all values of $m$, where the tilde hides factors logarithmic in $n$. (When $m \ll \sqrt{n}$ we can use your first approach, thus getting rid of this dependence on $n$.)

---
Tags: algorithms, probability-theory, randomized-algorithms, statistics
---


title: Decide if this language is context free

text:
# Question
Title: Decide if this language is context free
I got this question for homework:

> Decide if this language is context free or not:
>
> $\qquad \\{x@1^m: x \in \left\\{0,1\right\\}^\*, m \in \mathbb{N}, x\_m = 1\\}$.

Intuitively I think it's not context-free because a $PDA$ can't remember the places of all the $1$'s in $x$.

I tried using the pumping lemma but couldn't find the right example to show the language is not context-free.

I'd be grateful for any lead.

# Answer
Hint: Following up on Hendrik Jan's hint, here is another way to view this language: $$ \\{ x1y@1z : x,y \in \\{0,1\\}^\*, z \in \\{1\\}^\*, |x| = |z| \\}. $$
> 2 votes

# Answer
I think the context free grammar with these productions and starting symbol `S` produces your language (assuming words start at index 0):

**S -\> 0S1
S -\> 1S1
S -\> 1X
X -\> 0X
X -\> 1X
X -\> @
**

Explanation: You can produce any words from `{0,1}*` with index \< `m`and add a `1`to the right part of the word. When you reach index `m`, you switch to `X` and continue the word from `{0,1}*`. You can end the word by producing an `@`.
> 2 votes

# Answer
Let $L = \\{x@1m:x\in\\{0,1\\}^∗,m\in N,x\_m=1\\}$.

A language $L$ is context-free when a context-free grammar $G = \langle\Sigma, N, S, R\rangle$ such that $L(G) = L$ (the language of $G$ is the same as $L$).

\begin{align} G = \langle\\{0, 1\\}, \\{S, X\\}, S, \\{&\\ &\qquad X \rightarrow 0X,\\ &\qquad X \rightarrow 1X,\\ &\qquad X \rightarrow \epsilon,\\ &\qquad S \rightarrow 0S1,\\ &\qquad S \rightarrow 1S1,\\ &\qquad S \rightarrow 1X@1 \\ &\\}\rangle \end{align}
> 0 votes

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


# Question
Title: What complexity does this 'how many ways to climb' algorithm have?
I have a solution to the following problem:

> Given a stairway of $n$ stairs, which you can climb from $1$ to $m$ at the time ($1 \leq m \leq n$), return all the ways you can climb the stairway.
>
> E.g. for $n = 3$, $m = 2$, the possible ways to climb are $\[2,1\], \[1,2\], \[1,1,1\]$

```
// outputs all the ways to react total using steps from 1 to max;
// returns the count of iterations
function permut(total, max, out) {
  // store unfinished tracks; start with an initial track
  let iter = [{ val: [], sum: 0 }];
  let count = 0;

  // take the next track until there are none
  for (let i of iter) {
    for (let s = 1; s <= max; s++) {
      // append step value to the current track
      // assume constant complexity
      let val = [...i.val, s];
      let sum = i.sum + s;

      count++;

      if (sum === total) {
        // we've reached the top;
        // do not expand current track further
        out(val);
        break;
      }

      // add an unfinished track and start over
      iter.push({ val, sum });
    }
  }

  return count;
}

```

Codesandbox: https://codesandbox.io/s/busy-cdn-7idu9

However, I can't figure out the time complexity relatively to $m$ and $n$. For $m = 1$ the number of iterations is $n$, for $m = n$ it's $2^n - 1$.

Also, is there a canonical solution to this problem?

# Answer
The solution is the recursive formula:

$S\[k\] = \sum\_{i=1}^mS\[k-i\]$

For $m=2$ this is the Fibonacci sequence, and the way to program it is with dynamic programming. The complexity of the dynamic programming is $O(m \cdot n)$.

Consider the last step before reaching step $k$, the number of ways to reach $k$ when the last step is $i$, is equal to the number of steps to reach $S\[k-i\]$
> 4 votes

# Answer
What you are looking for is the so-called partition function (with some constraints on the addends). A simple upper bound is the number of solutions (and thus for the runtime since you generate all of them). For the unconstrained case this is $e^{c\sqrt n}$ as per Siegel with c=$\pi\sqrt\frac{2}{3}$.

There are several specialised formulas with tighter bounds depending on certain contraints (see https://en.wikipedia.org/wiki/Partition\_(number\_theory) for lots of them) but generally the dominating term will be in the order of $n!$.

In (de Azevedo Pribitkin, W. Ramanujan J (2009) 18: 113. https://doi.org/10.1007/s11139-007-9022-z) an upper bound of $\frac{e^{c\sqrt n}} {n^{3/4}}$ is given. Without further assumptions about $m$ that is probably the best bound we can give while keeping the formula simple.
> 3 votes

# Answer
I believe the question is about time complexity without DP. I read somewhere that it was mentioned the complexity is $\mathcal O(m^n)$ but there is a much tighter bound that I will derive below.

Based on the recursion relation we get

$$ T(n) = \sum\_{i=1}^m T(n-i) + m $$

where I have included the time for adding the results of the recursive calls.

Now it seems intuitive that the time complexity is exponential so lets take as an ansatz $T(n) \sim x^n$ and then we get

$$ x^n = x^{n}(x^{-1} + x^{-2} + ... +x^{-m}) + m $$

At this point we can drop the term linear in m *assuming* that we will get $x\>1$. If we do not get the same our assumption will be unjustified but we will see below that this is indeed what we get.

On summing the series on the RHS we get

$$ 1= \frac{1-x^{-m-1}}{1-x^{-1}}-1 $$

which can be further simplified to give

$$ \frac{x^m(x-2)+1}{x-1}=0 $$

This solution asymptotes to 2 from below. Thus the tighter bound is $\mathcal O(2^m)$.
> 2 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: Why, intuitively, does the Ackermann function require $\mu$-minimisation?
I have read proofs that the function is not primitive recursive and I (think) I understand them. Most I've seen show that the set of functions dominated by the Ackermann are exactly the primitive recursive functions etc.

But, coming at it from the point of view of the 'ground requirements' which define the collection of recursive functions, I am having a hard time making the link between the (current) definition for the Ackermann function, and why it *requires* unbounded minimisation/search.

I am unfamiliar with a lot of theoretical computer science so I hope my question makes sense!

# Answer
> 1 votes
Roughly speaking, a function is primitive recursive if it can be computed by a program in which all loops are bounded ahead of time. Concretely, we can consider the LOOP programming language, which has the following instructions:

* Set $x$ to zero.
* Increment $x$.
* Run a piece of code $x$ times.

We can use LOOP to compute one-argument functions using some input/output convention, say the input is in $x$ and the output is in $y$.

If the program has no loops, then $y \leq x + C$ for some constant $C$. If the program has no nested loops, then $y = O(x)$. If it has nesting depth 2 (a loop can appear within another loop, but that's it), then $y = O(x^C)$ for some constant $C$. More generally, if the program has nesting depth $d$, then $y$ can be bounded by a function on level $d$ on the Ackermann hierarchy.

The Ackermann function is constructed in such a way that it doesn't belong to the Ackermann hierarchy, and so cannot be computed by a LOOP program. In brief, it grows too fast.

---

Growing too fast isn't the only reason for not being primitive recursive. Indeed, using diagonalization we can construct Boolean recursive functions which are not primitive recursive. Let $f\_i$ be an effective enumeration of all primitive recursive functions, and define $$ f(n) = \begin{cases} 1 & \text{if } f\_n(n) = 0, \\ 0 & \text{otherwise}. \end{cases} $$ The function $f$ is recursive but, by construction, not primitive recursive.

---
Tags: computability, recursion
---


# Question
Title: Maximal subsets of a point set which fit in a unit disk
Suppose that there are a set $P$ of $n$ points on the plane, and let $P\_1, \dots, P\_k$ be distinct subsets of $P$ such that all points in $P\_i$ fits inside one unit disk for all $i$, $1\le i\le k$.

Moreover, each $P\_i$ is maximal, i.e., no unit disk can cover a subset of $P$ that is a strict superset of $P\_i$. Visually speaking, if we move a unit disk that covers $P\_i$ to cover a point not in $P\_i$, then at least one point which was inside that disk will become uncovered.

Here is an example:

In the above figure, there are three maximal subsets.

I don't know whether this problem has a name or was studied before, but here are my questions.

1. Can $k$ be exponential with respect to $n$?
2. If not, then can we find those maximal subsets in polynomial time w.r.t. $n$?

I think that there are exponentially many such subsets because of the following argument:
Suppose that the points are centers of some disks with radius $1/2$. If a subset of such points fit in a unit disk, then they form a clique. Since there are exponentially many cliques in a set of disks, then there should be exponentially many maximal subsets of this particular set of points that fit into a unit disk.

# Answer
Let's define a function $f: \Bbb R \times \Bbb R \rightarrow \left \[0, n \right \] $, returning a number of points from the set $P$, covered by a unit disk with the center at the point $(x, y)$. This is a piecewise constant function, and it's easy to see that its domain can be thought as a planar subdivision, defined by *all intersections* of unit disks, centered at points from the set $P$. This subdivision contains *vertices* (= intersection points), *edges* (= circular arcs) and *faces* (= pieces of the plane, where the function $f$ returns the same value). We'll say that these faces are *labeled* by this value.

We'll assume that the planar graph, defined by this subdivision, is a 4-regular one - it's a common assumption, meaning that all the points in $P$ are in general position (each intersection point belongs to exactly two circles). An example of such subdivision for $n=3$ is below, where the label for each face (including the external one) is shown in red color.

As far as I understand your maximal subsets $P\_i$ can be associated with such faces of this subdivision, which have labels **larger than all labels of their neighboring faces**. It's kind of static interpretation of your "moving disk" semantics, which you used in your definition of the maximal subset.

The subdivision will contain as many faces as possible in the case when all the unit circles pairwise intersect each other. It can be shown, that in this case:

* number of vertices is $n(n-1)$
* number of edges is $2n(n-1)$
* number of faces is $n(n-1)+2$

So, answers to your questions will be:

1. No, the number $k$ of maximal subsets is $O(n^2)$, because it can't be more than the number of all faces.
2. Yes, all the maximal subsets can be found in $O(n^3)$ time by naive scanning algorithm.

As for *name* of this problem - it looks like it may be related to some variations of the Unit Disk Cover problem.
> 4 votes

---
Tags: time-complexity, computational-geometry
---


# Question
Title: How to prove that {<M1, M2> : M1 and M2 are two DFAs and L(M1) $\neq$ L(M2)} is in NL?
My idea is to find a turing machine which recognizes this language in $\log N$ space, could anyone give me some clue on how to find such turing machine?

# Answer
Yuval's answer describes the main component. For the sake of completeness I'll precise a couple of details.

First, $L(M\_1) \neq L(M\_2)$ means that there is a string that is accepted by one of the automaton but not the other. Let's "build" an automaton $M$ that accepts precisely such strings, and we will then want to check whether it accepts a least one string. Then $M$ has states $(q^1\_i, q^2\_j)$ for each state $q\_i$ of $M\_1$ and $q\_j$ of $M\_2$. A state $(q^1\_i, q^2\_j)$ of $M$ is accepting if and only if $q\_i$ is accepting in $M\_1$ and $q\_j$ is not accepting in $M\_2$ or vice versa. Now, in order to tell if $M$ accepts a string, we need to know if there's an accepting node that is reachable from $(q^1\_0, q^2\_0)$. We can first guess such a state $(q^1\_m, q^2\_n)$ as its representation uses only a logarithmic number of bits. Then we can, one step at a time, guess a path of states from $(q^1\_0, q^2\_0)$ leading to $(q^1\_m, q^2\_n)$. Of course after each guess we need to actually verify that there is an edge in $M$ from the previous state to the recently guessed one. In order to do that we can always keep two states in memory, the current one and the state we just guessed as the next one, this uses logarithmic memory still.
> 2 votes

# Answer
Let $M = M\_1 \times M\_2$ be the product automaton for $L(M\_1) \Delta L(M\_2)$. Then $L(M\_1) \neq L(M\_2)$ iff some accepting state of $M$ is reachable from its initial state. Finally, directed reachability is in $\mathsf{NL}$ (in fact, $\mathsf{NL}$-complete).
> 0 votes

---
Tags: turing-machines, space-complexity
---


# Question
Title: Extracting regex submatch boundaries without backtracking
I'm attempting to develop from scratch a simple regex engine. I would like for my engine to have the ability to report, "The regex matched on a substring of this line starting at index and ending at index ."

It makes sense to me how to accomplish this using recursive backtracking. However, I'd like my implementation of the search to use Thompson's multi-state approach. Is this feasible?

# Answer
It occurred to me after I made this post that I could store the states in a linked list format:

```
typedef struct stateRecord {
    struct stateRecord *next;
    size_t state;
    size_t startIdx;
    size_t endIdx;
} stateRecord;

```
> 0 votes

---
Tags: algorithms, finite-automata, regular-expressions
---


# Question
Title: What becomes of context-sensitive grammars if $\epsilon$ productions are allowed?
The original formulation of the 3 restricted grammar types of Chomsky all included the restriction that the right-hand side of a replacement cannot be $\epsilon$ (non-contracting). This, however, can be (and usually is) lifted for regular and context-free grammars (i.e. they are allowed to have productions of the form $X \to \epsilon$) without altering the class of languages generated.

The rule, however, remains for context-sensitive grammars.

My question is, given a grammar with productions $\alpha X \beta \to \alpha \xi \beta$ where $\alpha, \beta, \xi\in (N \cup T)^\*$ (i.e. a context-sensitive grammar with $\epsilon$-rules), what class of languages does that describe? The recursively enumerable ones (same as unrestricted grammars) or something else?

# Answer
It can be shown that the context sensitive grammars you describe are equivalent to just asking for productions $\alpha \to \beta$ with $\lvert \alpha \rvert \le \lvert \beta \rvert$. So allowing productions $A \to \varepsilon$ just removes the restriction on lengths, and you have landed on unrestricted grammars.
> 1 votes

---
Tags: formal-languages, chomsky-hierarchy
---


# Question
Title: What is the difference between a lock convoy and lock/thread contention?
From wikipedia on lock convoy:

> A lock convoy occurs when multiple threads of equal priority contend repeatedly for the same lock. Unlike deadlock and livelock situations, the threads in a lock convoy do progress; however, each time a thread attempts to acquire the lock and fails, it relinquishes the remainder of its scheduling quantum and forces a context switch. The overhead of repeated context switches and underutilization of scheduling quanta degrade overall performance.

From wikipedia on lock/thread contention contention:

> lock contention: this occurs whenever one process or thread attempts to acquire a lock held by another process or thread. The more fine-grained the available locks, the less likely one process/thread will request a lock held by the other. (For example, locking a row rather than the entire table, or locking a cell rather than the entire row.);

Could somebody please elaborate a bit further on both of those things? To me it seems like they are essentially the same, or if they are not, then surely lock contention causes a lock convoy. Is that the case or are they separate and independent concepts? Also, I don't understand the sentence "it relinquishes the remainder of its scheduling quantum and forces a context switch".

# Answer
> 2 votes
There are two blocking approaches used in locking algorithms when **a lock is busy**. spin wait or block (go to sleep, relinquish processor and wait for OS to awake the thread and re-schedule). Lock convoy as mentioned will happen when blocking strategy is used.
OS schedule threads on a core in *time-sliced* manner. Every thread get the processor for some per-determined time-slice, say 2 ms. OS in a *round-robin* fashion schedule all the threads in the ready-queue one by one. If say a thread after it get schedule and start its execution, say after 100 us, ask for a lock. If the lock is busy, the thread unable to get the lock, blocks and relinquishes processor. So remaining 1.9ms (2ms-100us) time slice is not used by the thread. Even after it is awaken by the OS when lock is free, the thread has to wait for its turn in the round-robin queue. The number of active threads could be in 100's.

Lock contention causes convoy effect.

---
Tags: concurrency
---


# Question
Title: What are analog and digital in computer science?
I once thought that any *analog computer* is any computer which "doesn't need electrical current to work".
I once thought that any *digital computer* is any computer which "does indeed need (a correctly distributed) electrical current to work".

I found out both assertions as wrong.

**What are analog and digital in computer science?**

# Answer
I'll try to answer your remaining question: what are analog and digital in computer science?

The trouble is that these terms aren't from computer science. They are from the field called "signal processing". When someone says "analog computer", they simply mean that the computer is designed on principles of analog signal processing and built from analog components. The same goes for digital computers: they are designed with digital signal processing in mind and built from digital components.

So what does "analog" means? The word is taken from Greek word "proportional". To clarify what it means, let's look at the sum operation implemented with graduated cylinders:

Say you want to compute $13 + 38$. First, you take an empty cylinder and fill it up to $13$ ml mark. Then you take another empty one and fill it up to $38$ ml mark. Then you pour one into the other and look how much ml of liquid is there, which you announce as the result of the sum operation.

This is "proportional", because if you want to use $26$ instead of $13$ as an input, you use double amount of liquid. Double amount of liquid means twice as large number. An electrical analog computer could use the voltage of electric current is a similar way.

Now let's take a look on a digital computation implemented with Soldier Crabs. Here's how you make logical OR:

And here's logical AND:

You put a swarm of crabs where you want logical $1$ as an input and you leave empty places where you want logical $0$. Then you look where the swarm ball ends up and interpret it as $0$ or $1$. This is built on principles of (binary) digital processing:

1. No crabs (no electric current, no water flow) means $0$.
2. A swarm of crabs (5V, steady water flow) means $1$.
3. What if you can't decide which is the case? You just say that your digital component is broken.
> 2 votes

# Answer
There is a distinction between continuous phenomena and discrete. It's the former than is called analog in computer science and the latter, digital.

After all, the digits 0 and 1 are discrete.

Whilst \[0,1\], the interval between 0 and 1 is continuous and so analog. (I don't know if you are familiar with the notation \[a,b\]. It simply means all numbers between a and b).
> 1 votes

# Answer
Before we had electric or electronic calculators, there were mechanical calculators. These worked with whole numbers, so they were digital, but they were powered by hand (typically by turning a crank) not by electricity.

On the other hand, in the period 1900 to 1960 there were a variety of analogue computers that were powered by electricity. Even though electronic digital computers were available from the 1950s onwards, an analogue computer was sometimes quicker, cheaper or easier to operate than an early digital computer. This wikipedia article contains pictures and descriptions of several electrical analogue computers.
> 1 votes

---
Tags: turing-machines, quantum-computing, message-passing
---


# Question
Title: Find the length of the longest subarray having sum greater than k
I tried to solve this problem but could not do it better than $O(n^2)$.

My Algorithm:

```
1. Calculate prefix sum

2. for i in 1..n:
     for j in 1..i:
       if presum[i] - presum[j-1] > k:
          ans = max(ans, i - j)

```

**Edit:** I have found a solution which works in $O(n\log n)$. This solution does a binary search on the length of the subarray and chooses the maximum length of the subarray satisfying the property.

The code is as follows:

```
#include<stdio.h>
long long int a[1000005]={0},sum[1000005]={0},n,k;
long long int check(long long int len)
{
long long int i,c=0;
for(i=len;i<=n;i++)
{
 if((sum[i]-sum[i-len])>=k)
   c++;
}
 return c;
 }

int main()
{
 long long int i;
 scanf("%lld",&n);
 scanf("%lld",&k);
 for(i=1;i<=n;i++)
  {
  scanf("%lld",&a[i]);

  sum[i]=a[i]+sum[i-1];
  }
 long long int low=0,high=n,ans=0,count=0;
 while(low<=high)
 {
  long long int mid=(low+high)/2;
  long long int p=check(mid);
  if(p>0)
  {
   ans=mid;
   low=mid+1;
  }
  else
  {
  high=mid-1;
  }
}
if(ans==0)
    printf("-1\n");
else
    printf("%lld\n",ans);
return 0;
 }

```

My doubts: How does this algorithm discards the search space?

More specifically, what I want to know that suppose there does not exist any subarray of length $len$, then how can we show that there won't exist any subarray of length $\>len$. The above code does the same way, whenever there does not exist any subarray of length $mid$ it removes the other half and continues to search for an answer in the lower half by decreasing the $high$ to $mid-1$.

# Answer
We can improve your code and speed it up from $O(n^2)$ to $O(n \cdot \log n)$ with one change.

First precompute all prefix sum. Let $P\_t$ = the sum of the first $t$ elements. Notice that $P\_t$ is defined from $0 \leq t \leq n$ and in particular $P\_0=0$. This step is $O(n)$ so it is ok.

Now you need to find two index $0 \leq j \< i \leq n$ such that $P\_i - P\_j \> k$ and $i - j$ is maximum.

The next step in your solution is fixing the right most index ($i$), so we need to figure out a way to find fast the leftmost $j$ such that $P\_i - P\_j \> k$. For a fixed $i$ the condition can be converted to:

What is the smallest $j$ such that $P\_i - k \> P\_j$?

We might be tempted to do binary search here, but it is not correct since $P\_j$ is not sorted... but wait, we can just get rid of "not sorted elements" easily. Let's say that if there exist two index $a \< b$ such that $P\_a \leq P\_b$, then we are not interested at all in the element at position $b$, since it will never be the leftmost index of an optimal interval, given that we can extend that interval up to position $a$.

With this in mind we can define an index $j$ important, if there is no index $k \< j$ such that $P\_k \leq P\_j$, i.e. $j$ is the smallest element in the prefix ending at $j$. One nice property of important elements, is that they form a strictly decreasing subsequence of array $P$, and for any fixed $i$, the optimal election of $j$ is an important index.

Since the important index array forms a strictly decreasing subsequence we can perform binary search without any issue. To build such array, we inserts elements one by one, if the new element is less than the minimum element in the array then it is important and should be inserted, otherwise, we don't add this element. The minimum element of the important index array will always be the last one.

Pseudocode:

```
def largest_subarray(array, k):
    n := length of array
    P := prefix sum of array
    # Remember that P[0] = 0, P[1] = array[1], ...

    # List of important index in increasing order.
    # Notice the values such indexes are pointing too are decreasing.
    # That is P[J[0]], P[J[1]], ... is strictly decreasing
    # Initially there is only index 0
    J := [0]

    # Answer of this function.
    longest_length := -1

    for i in 1..n:
        # Check if there is at least one solution ending
        # at index i. i.e. If P[i] - min(P[j < i]) > k

        # Index of the smallest element
        last_j := J[-1]
        if P[i] - P[J[-1]] > k:
            # There is at least one solution, so we can run binary search
            # to find the optimal solution. i.e the smallest index j
            # such that P[i] - P[j] > k
            # Since j belongs to J, we are finding the smallest index
            # p such that P[i] - P[J[p]] > k
            p := bin_search()
            longest_length := max(longest_length, i - J[p])

        # Check if i is important
        if P[i] < P[last_j]:
            J.push(i)

    return longest_length

```
> 2 votes

# Answer
Here is an $O(n)$ algorithm.

Compute the array of the prefix sums of the given array. This can be done in $O(n)$ time.

Let $p=(p\_0, p\_1, \cdots, p\_n)$ be the array of the prefix sums, where $p\_0=0$, $p\_1=a\_1$, $p\_2=a\_1+a\_2$, etc. Now the problem is to find the largest $j-i$ such that $j\>i$ and $p\_j-p\_i\>k$.

Suppose $(p\_i,p\_j)$ is a pair such that $j\>i$ and $p\_j-p\_i\>k$. If $j-i$ reaches the maximum with $(p\_i,p\_j)$, then

* $p\_i$ should be the smallest element among $p\_0, p\_1, \cdots, p\_i$; otherwise, we can replace $p\_i$ by that smallest elements and obtain a larger $j-i$.
* $p\_j$ should be the largest element among $p\_j, p\_{j+1}, \cdots, p\_n$; otherwise, we can find replace $p\_j$ by that largest element and obtain a larger $j-i$.

That means, we need only to search for $(p\_i,p\_j)$ where $p\_i$ is the smallest element in some prefix of $p$ and $p\_j$ is the largest element in some suffix of $p$. This search can be done by the handy two-pointer technique.

* First, we retain the smallest element so far as we traverse $p$ from left to right, to form an array of length at most $n$, from which we will choose $p\_i$. Call it array `left`. We will let `left_p` be the index of $p\_i$ in `left`.
* Second, we retain the largest element so far as we traverse $p$ from right to left, to form an array of length at most $n$, from which we will choose $p\_j$. Call it array `right`. We will let `right_p` be the index of $p\_j$ in `right`.
* For each `left_p`, we will find `right_p` furthest to the right such that $p\_j-p\_i\>k$ and keep track of the maximum $j-i$ found so far, after which we will we will increase `left_p`. Although this step may involve a nested loop, it will be done in $O(n)$ time since in each iteration, either `left_p` and `right_p` will be increased.

Here is an implementation in Python.
> 1 votes

---
Tags: algorithms, data-structures, arrays, maximum-subarray
---


# Question
Title: Determining which recursive term is bigger if they share the same definition
We are given a recursive definition:

$a\_1 = x,\\a\_2=y, \\a\_n= c\_1a\_{n-1}+c\_2a\_{n-2} \text{ for }n\ge3 $

where $x,y,c\_1,c\_2,n$ are natural numbers

we are to prove that $a\_n \le c\_3^n$ for all n

The base case is true

Assuming $a\_k \le c\_3^k$ is true

show $a\_{k+1} \le c\_3^{k+1}$ is true

---

We have:

1. $c\_3a\_k \le c\_3^{k+1}$

and

2. $a\_{k+1} = c\_1a\_k + c\_2a\_{k-1}$

where 1 can be written:

3. $c\_1a\_k + ma\_k$

where $m+c\_1 = c\_3$

which can be rewritten:

4. $c\_1a\_k + mc\_1a\_k + mc\_2a\_{k-1}$

Now, 4 and 2 have the first term equal.

How can I determine whether $ mc\_1a\_k + mc\_2a\_{k-1}$ in 4 is bigger or not than $ c\_2a\_{k-1}$ in 2?

# Answer
Let $c\_3 = \max(1,x,y,c\_1+c\_2)$. Then $$ a\_1 = x \stackrel{c\_3 \geq x}\leq c\_3^1 $$ and $$ a\_2 = y \stackrel{c\_3 \geq y}\leq c\_3 \stackrel{c\_3 \geq 1}\leq c\_3^2. $$

Now suppose that $a\_{n-2} \leq c\_3^{n-2}$ and $a\_{n-1} \leq c\_3^{n-1}$. Then $$ a\_n = c\_1 a\_{n-1} + c\_2 a\_{n-2} \stackrel{\text{assumption}}\leq c\_1 c\_3^{n-1} + c\_2 c\_3^{n-2} \stackrel{c\_3 \geq 1}\leq c\_1 c\_3^{n-1} + c\_2 c\_3^{n-1} \stackrel{c\_3 \geq c\_1+c\_2}\leq c\_3^n. $$
> 2 votes

---
Tags: recurrence-relation, recursion, induction
---