# Question
Title: Definition(s)/characterization(s) of intractability
I've been searching around for definitions of **intractability**, and I realized that despite being widely used, the concept of intractability (when talking about computing problems of course) is **not formally defined**.

I'm currently writing a report in which I characterize some problems as intractable (in my context, they are intractable because their output size can be exponential w.r.t the input size), and I need to feel 'comfortable' about what intractability is in order to write coherent stuff in the report.

The way I understood it is the following: a problem is *intractable* if it cannot be solved reasonably fast, with reasonably big instances.

This leaves a lot of space for human appreciation of what a reasonable execution time is, and what a reasonable input size is. This also allows to describe some problems in **P** as intractable (if it runs in `O(n^150)` for instance) , and even in some cases, to eventually describe some NP-complete problems as tractable (many MILP problems can actually be solved fast with reasonably big instances).

My questions:

* Is there a better/more elegant/more precise way to define intractability ?
* Are there problems/contexts which could be described as being on the border, meaning that they're really not easily fitting in any of the 2 categories (tractable/intractable) ?

# Answer
What is intractable or not inherently depends on what the underlying computational model is as well as what your conventions are. By far, the most widely used notion is based on the Cobham-Edmonds thesis, which states that, for any given machine model for which time (or any equivalent thereof) is a valid resource, the *tractable* problems are those that can be solved in polynomial time. In this sense, tractability quite certainly has a formal definition.

This means that, if you are using run-of-the-mill TMs, then the class of tractable problems is $\mathbf{P}$. If you use probabilistic TMs (with two-sided error), it would then be $\mathbf{BPP}$. If you use quantum circuits, $\mathbf{QBP}$. For ATMs, $\mathbf{PSPACE}$—and so on.

> Are there problems/contexts which could be described as being on the border, meaning that they're really not easily fitting in any of the 2 categories (tractable/intractable) ?

The way tractability is usually understood, this is impossible. There is a well-defined set of tractable problems. Using standard logic, a problem is either in that set or it isn't. You could identify some problems as more difficult than others, but that is a different concept altogether since it would produce a whole spectrum of hardness (and, hence, is not quite captured by the aforementioned notion of tractability). What would rather fit that notion is *time complexity* itself; after all, it allows you to express a problem's hardness based on the time resources (as a function on $\mathbb{R}\_0$) needed to solve it. (And, as we know, most such functions can be compared using, for instance, asymptotic analysis.)

**TL;DR:** Intractability is a *discrete* concept; time complexity is a *continuous* one (or as continuous as it can be in the set of (computable) $\mathbb{N} \to \mathbb{R}\_0$ functions).
> 2 votes

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


# Question
Title: Given N vertices and M edges find if two nodes are in the same connected component?
Given a set of $n$ people and $m$ friendship relations between those people (relation is between two persons) we need to suggest a data structure that supports the division of those people into maximum groups such that if 2 people are connected, they belong to the same group.

Asking $k$ queries, where each query is asking if $(i,j)$ are 2 people are in the same group, what data structure can have a total running time of $O(m+n+k)$?

For example:

$n = \\{1,2,3,4\\}$

$m = \\{(1,2) , (2,3)\\}$ (person 4 has no friends)

So the above relations will form 2 groups: $\\{1,2,3\\} ,\\{4\\}$

I thought about taking an Undirected graph and checking if two vertices are in the same connected component. The problem is that I do $k$ checks. And I need to find a way such that a check will be $O(1)$.

# Answer
> 1 votes
The problem is that you want to do a graph traversal every check : that is way too often.

Do a graph traversal to find the connected component of each vertex (e.g. give them a number). This takes $O(m+n)$ time. Store these numbers in an array indexed by the vertices, let's call it $A$. Then check if two vertices $i$ and $j$ are in the same connected component in $O(1)$ time by checking whether $A\[i\] = A\[j\]$.

---
Tags: graphs, union-find
---


# Question
Title: Given a set of numbers, get the maximum 10 number average below a certain threshold
As an input, my program accepts a big set of numbers (often times more than 30) and a maximum threshold. I'm trying to get the maximum average between 10 of those numbers below that threshold (the numbers used in that average are also returned).

Right now, I'm testing all 10 number combinations, recording them and their average in a list and getting the maximum average from that list.

As you know, though, when the set becomes too big (usually around 30 numbers), the time period the program takes to execute gets much larger, often way too large to be usable.

What would be an algorithm that cuts down on execution time, while achieving the same (or approximate) result?

EDIT: numbers are floats between 0 and 1.

# Answer
Looking for a maximum average $m$ below a threshold $m\_{max}$ is the same than looking for a maximum sum $s$ below a threshold $s\_{max}$. If you have to select $k = 10$ numbers among $N$, you have:

$s\_{max} = k \times m\_{max}$

now the question looks like a Knapsack problem with a forced number of selected items $k$. You can use a DP solution closed to the one solving Knapsack. I also assume $s\_{max} \> 0$ and all available numbers are strictly positives. Note, that you may apply a simple offset on all numbers and $m\_{max}$ if any is negative.

Let's build a $k\times s\_{max}$ array $A$ with $A\[i, j\]$, the index of the last number selected to have $i$ selected values for a total of $j$. $A$ is initially filled with an "null" value.

Then the pseudo algorithm is:

```
for n from 1 to N:
    v = n-th available value
    for i from k-1 to 1:
        for j from smax-v to 1:
            if A[i, j] is not null and A[i+1, j+v] is null then:
                A[i+1, j+v] = n
    if A[1, v] is null:
        A[1, v] = n

```

The best sum you can obtain is the last $A\[k, j\]$ which is not null. Using the index in $A$, you can backtrack the subset. Note that $i$ and $j$ loops go backward, to be sure the same value is not used twice.

Complexity is $O(Nks\_{max})$ in time and $O(ks\_{max})$ in space.

If $s\_{max}$ is large and $N$ quite small, a (key, value) structure (in fact $k$ of these structures) instead of $A$ may be much more efficient as you won't have to loop on all empty values.
> 2 votes

# Answer
"Average \< threshold" is equivalent to "Sum \< 10 times threshold".

Find all subsets of five integers, and sort them in ascending order by their sum. That takes O (N over 5) space and O (N over 5, times log N) time.

Let S be the first, second, third subset and so on, as long as the sum of S is less than 5 x threshold. For each S find a subset T which is the last subset such that S + T have a sum less than 10 times the threshold. Finding all S and T is done in O (N over 5) time.

For each T, you need to find T' at the same or an earlier position such that S and T' have no element in common. Then S and T' are a candidate for the optimal sum. You can stop the search for T' once the sum of S and T' is not greater than the optimum value so far. It's hard to say how much finding T' contributes to the total execution time.

If you have many items, then the execution time may not a problem stopping you, but the O (N over 5) storage may very well be. But you don't have to store them all. To generate all subsets of 5 items in ascending order of sum: Store all sets of two items, and all sets of three items, sorted by their sums. Then you create a priority queue, with N over 2 items: Each item is one fixed subset of two items, combined with the smallest subset of three items, and without a common element. The priority queue gives you immediately the smallest subset of five items; then you replace that entry of (2 + 3) items with the same 2 items and the next largest 3 items. That gives you subsets with smallest sums in ascending order; another priority queue gives you the subsets in descending order of size.

The execution time is the same, but the storage requirement goes down to O (N over 3) instead of O (N over 5).

Find all sums of two elements in ascending order, call them $X\_i$. Find all sums of three elements in ascending order, call them $Y\_i$.

Take $X\_1 + Y\_1$, $X\_2 + Y\_1$, $X\_3 + Y\_1$ etc. and put them into a priority queue. Remove the smallest item which will be $X\_i + Y\_j$ for some i, j and insert $X\_i + Y\_{j\_1}$ if $Y\_{j+1}$ exists, and repeat. Obviously skip i, j where $X\_i$ and $Y\_j$. This gives you all sets of 5 items in ascending order of sum.

Have a second priority queue where you start with the highest $Y\_j$ instead of $Y\_1$, and extract the highest sum.
> 2 votes

# Answer
First, let us notice that if you replace 10 by 2 and the numbers are sorted, then you can solve this in linear time using a two pointer algorithm: one pointer starts at the bottom of the array, and the other one advances as far as possible while keeping the average below the threshold. Then you advance the first pointer by one and move the second one back until the average is below the threshold. And so on. We notice that the same algorithm also works for a weighted average.

Given $N$ numbers, you can divide them into two halves of $N/2$ numbers ("meet-in-the-middle"). Each set of 10 numbers splits into an $a$-set of the first half and a $b$-set of the second half, for some $a,b$ summing to 10. We can run the algorithm above for all such $a,b$ (using the appropriate weights). This will improve the running time from being proportional to $\binom{N}{10}$ to being proportional to $\binom{N/2}{10}$ (for $N \geq 20$).

You could try improving this further by partitioning into halves in a random fashion, and hoping for a balanced split, which will happen with reasonable probability. You then only have to try $a,b$ which are balanced. (The extreme would be to aim for $a=b=5$, but that's not necessarily the best choice.) While this is a randomized algorithm, it can probably be derandomized while taking only a small hit in the running time.
> 1 votes

# Answer
Here is the outline of an algorithm that obtains the accurate result in $O({N\choose 5}N^2\log\_2N)$ time. Its idea comes from *meeting at the middle* and two-pointer technique. In an ordinary setup, it yields the accurate result within a couple of seconds when given 50 numbers.

Assume the input numbers are given in an array. Selecting 10 numbers from the given multi-set of numbers is the same as selecting a subsequence of 10 elements. We first select the fifth element of the subsequence. Then we select 4 elements that sit before that fifth element. Then we select 5 elements that sit behind that fifth element. This selecting process ensures the same 10 numbers will not be selected twice.

$\newcommand{\sum}{\operatorname{sum}}$If $arr$ is an sequence of numbers, $\sum(arr)$ denotes the sum of all numbers in $arr$.

### Algorithm

Input: A number $T$ and an array $arr$ of $N$ numbers

Output: 10 numbers in the array whose average is as large as possible but smaller than $T$, followed by the sum of them.

Procedure:

1. Sort $arr$.
2. For $i$ from 5 to $N-5$ exclusive:

1. Collect all subsequences of the first $i$ elements of $arr$ where each subsequence has 5 elements, the last of which is $arr\[i-1\]$. Sort these subsequences by their sums. Let the sorted subsequences be $front5$.
    2. Collect all subsequences of the last $N-i$ elements of $arr$ where each subsequence has 5 elements, the first of which must be larger than $arr\[i-1\]$. Sort these subsequences by their sums. Let the sorted subsequences be $behind5$
    3. (**two pointer technique**.) Let $f$ be the first element in $front5$. Let $b$ be the largest element in $behind5$ such that $sum(f)+sum(b) \<T$. Let subsequence $answer$ be the combination of $f$ and $b$.
        1. Let $f$ be the element in $front5$ after $f$. Search for the largest element $b$ in $behind5$ such that $sum(f)+sum(b) \<T$. If $sum(f)+sum(b)\>sum(answer)$, update $answer$ to be the combination of $f$ and $b$.
        2. Go back to the step above as long as $f$ is not the last element in $front5$.
3. Output $answer$ and $sum(answer)$.

A few corner cases are not specified in the outline above. For example, if the average of any 10 numbers is no less than the threshold $T$, the algorithm can output something like "null".

### An implementation in Java

Just click the "Run" button to see the result.

A subsequence can be viewed as a list of indices. For example, the subsequence $arr\[0\], arr\[3\], arr\[5\], arr\[6\], arr\[12\]$ can be treated as the list \[0,3,5,6,12\]. If $n\le64$, each index can be encoded in 6 bits. Then a subsequence of 5 elements can be encoded using a single 32-bit integer. A subsequence of 10 elements can be encoded using a single 64-bit integer.
> 1 votes

# Answer
The biggest average of 10 is the average of the biggest 10.

A list of 10 isn't so time-consuming to maintain as a list of 30. Maintain a list of the 10 largest input integers that are less than the threshold. The list starts empty; unless and until it contains 10 integers, *every* input integer that is less than the threshold should be inserted into this list. Once the list contains 10, every time you read an integer $n$ which is less than the threshold, but bigger than the smallest $s$ in your list, replace $s$ by $n$ in the list.
> 0 votes

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


# Question
Title: combinatoric grouping optimization problem based on time interval overlap, weight constraint, and distance minimization
Let each element be an individual. Consider that an individual is defined such that each individual has a time range, weight, and location.

The goal is to group together individuals whose time ranges overlap while ensuring that, within the group, the sum of the weights of the individuals do not exceed a certain threshold. At the same time, it is desirable to minimize the total distance between the individuals in the group. As many individuals as necessary can be placed into a group as long as the weight constraint is met. Let there be N individuals (assume at most 5000 individuals in a practical implementation).

The goal is to have as many individuals grouped (that is at minimum paired) as possible while minimizing the total distance between individuals in groups. This problem appears to be NP-hard so I am not looking for a global minimum but a good solutions.

For example, consider an example in the discrete time case where there are ten time intervals. \[1, 2, 3, 4, 5, 6, 7, 8, 9, 10\]. The weight threshold is 4 and the location of the individuals are points on the 1-D line of integers. Say that we have the following individuals:

```
A: time range: [1, 2, 3] | weight: 1 | location: 1
B: time range: [2, 3, 4] | weight: 2 | location: 2
C: time range: [4, 5, 6] | weight: 2 | location: -3
D: time range: [4, 5, 6] | weight: 3 | location: -3

```

**Note:**

* A and C cannot be grouped because they do not have overlapping time ranges.
* grouping together A and B gives is preferable to grouping together B and C because A and B are closer together.
* C and D cannot be grouped because the sum of their weights exceed 4. Does any one have a recommended algorithm for solving a problem like this?

*I've looked at the examples in (Studies in Computational Intelligence 666) Michael Mutingi, Charles Mbohwa (auth.) - Grouping Genetic Algorithms\_ Advances and Applications-Springer International Publishing (2017). However, none of the grouping algorithms seem very fitting.*

**Different Ways to Understand / Interpret This Problem:**

*Interpretation 1: Bin-Packing Problem*

The goal is to find a partition of the individuals such that, within each partition, time ranges of all members overlap. The total 'weight' sum of each partition is below a certain threshold (note that no single individual will exceed the weight threshold). The total 'distance' sum (computed by summing the distance derived from each partition) is minimized. As few one individual partitions are formed.

*Interpretation 2:*

See Below

**My Impractical Approach For This Problem**

*Step 1: Defining an individual*

```
Individual:
   Time Range: [2, 3, 4]
   Weight: 2
   Location: -3

```

*Step 2: Finding Potentially Time-Compatible Individuals*

Imagine that a 24-hour day is defined as 24 one-hour bins. Each bin represents one hour. For example, the bin at index 6 represents 6 am. Let's call this the timetable.

We place individuals into these bins based on their time range. For example, If John's time range is \[1, 2\] and Wilson's time range is \[2, 3\], then the timetable will be populated as follows:

```
[ [] , [John] , [John, Wilson], [Wilson], [] , ... , [] ]

```

Here, individuals in the same bin could potentially be grouped.

> **OUTDATED**
>
> *Step 3: Generating Viable Groups Based On Weight Constraint*
>
> Let's define the weight limit of a group to be 4.
>
> For each bin in the timetable, we generate groups that meet the weight constraint (the sum of the weights of the individuals is below 4). Note we can skip over the bins with one or fewer individuals. Here, each group has the following characteristics:
>
> ```
> Group:
>    Individuals: [ Person1, Person2, ... ]
>    Weight: INT (computed by summing weight of individuals)
>    Distance: FLOAT (computed by finding distance sum between individuals)
>
> ```
>
> We take all of the groups we generated and store them together in a list called viable\_groups.
>
> *Step 4: Finding the best set of groups*
>
> We optimize the groups / partitioning by finding the set of disjoint groups such that the total distance sum is minimized.
>
> **Problem with this approach**
>
> By step 3, this approach becomes computationally infeasible because we generate all possible groups by enumeration.

**UPDATE:**

*Step 1: New Definition of 'Individual'*

In the beginning, each individual is treated as a singleton group:

```
Group:
   members: [person1]
   time range: [0, 1, 2, 3, 4, 5]
   weight: 2
   location: -3

```

*Step 2: same as before*

*Step 3: sort time bins by population*

Time bins are sorted by the number of singleton groups in that bin in descending order. After the sort, the time bin with the most number of singleton groups is ranked first.

*Step 4: merge groups until no merge is possible*

Starting with the first time bin, construct a graph such that the nodes are the groups and the edges represent the distance between two groups. An edge exists between two groups only if their weight sum does not exceed the maximum capacity. For example, let the weight threshold be 4 and consider the following singleton groups:

```
group1:
   members: [person1]
   time range: [0, 1, 2]
   weight: 1
   location: -3

group2:
   members: [person2]
   time range: [0, 1, 2, 3]
   weight: 2
   location: 0

group3:
   members: [person3]
   time range: [0, 1]
   weight: 3
   location: 1

```

Notes that out of the 3 possible edges, the following edges exist:

```
group1 -- 3 -- group2
group1 -- 4 -- group3

```

This is because group2 - group3 exceeds the weight threshold of 4.

Now we find the edge with the smallest value and merge the two end nodes. After merging the two nodes, we recompute the edges based on the new set of nodes available, and we repeat until no edges exist.

In terms of the above example, we would merge group1 and group2 to obtain:

```
group12:
   members: [person1, person2] (union of members)
   time range: [0, 1, 2] (intersection of time ranges)
   weight: 3 (sum of weights)
   location: 1.5 (center between two locations)

group3:
   members: [person3]
   time range: [0, 1]
   weight: 3
   location: -3

```

Now, if we recompute the edges, we see that no edges exist. Thus, we are done with the first time bin.

Next, we remove all of the singleton groups that have members that overlap with the members in subsequent time bins. For example, in this case, if we find either group1, group2, or group3 in the subsequent, we remove those groups.

we repeat the merging process we performed on the first time bins.

We repeat this until the last time bin.

*This is my approach so far, and I realize it's not the most efficient. Does anyone have recommendations for improvements? Please let me know in the comments if any part of the explanation is unclear!*

# Answer
> 1 votes
Okay, I will attempt to give a new approach. Note that I am not sure to understand all features and issues. Moreover, the most adapted strategy probably depends strongly on data.

## Assumptions

I make the following assumptions, i can eventually adpat my answer if one is wrong.

* there are $N$ persons to group ($N \approx 1000-5000$)
* each person $p$ has a time range (soonest to latest $\[S\[p\], L\[p\]\]$) which may not be discrete but is not interrumpted. So $p$ is available for any $t$ in $\[S\[p\], L\[p\]\]$.
* each person $p$ has a weight strictly positive ($W\[p\] \> 0$).
* each person $p$ has location value $P\[p\]$
* in a group, all persons have to share a time lapse of at least $dt$
* the total weight of a group should not be greater than $w\_{max}$

The number of person alone should be minimized. Then the total distance in group should be minimized $D = \sum\_{grp} max\_{p \in grp}(P\[p\])-min\_{p \in grp}(P\[p\])$.

## Build the meeting graph

So you should indeed first build a graph $G(v, e)$ where each person is a vertex and an edge between two persons means they can be in the same group. This is of course an undirected graph. The weight of the edges $d$ represents the distance between the two persons

So let's sort persons with increasing soonest time $S$. Then you can find simply all the edges of the graph with this algorithm:

```
for p from 1 to N:
    for k from p+1 to N:
        if L[k]-S[p] > dt:
            break
        if W[k]+W[p] < w_max:
            add edge (k, p) of weight d=|P[k]-P[p]|

```

In this graph $G$, a group has to be a clique respecting weight constraint. The distance of the group is the maximum edge of the clique.

## Start grouping

Your structure for groups should be a list $groups$ of list containing element in each group (initially empty) and an array $G\[p\]$ giving for each $p$, -1 if it is not grouped, else the index of the group of $p$ in $groups$.

For better performances, you can also track the distance and the total weight of each group.

Now loop on persons $p$, if $p$ is alone try to group it else continue.

Let's consider all neighbors $k$ of $p$ in $G$ and find the move that minimize the distance increase $\Delta D$:

* If $k$ is alone ($G\[k\] = -1$), you can group up $k$ and $p$, the cost in distance is the edge weight $\Delta D = d$.
* If $k$ is already grouped, check if $p$ can be added to $groups\[G\[k\]\]$, it should have an edge to every element and the total weight should not pass $w\_max$:

+ if it is possible, You can compute the $\Delta D$ of such grouping which can be 0.
    + else if only one element prevent $p$ from coming consider re-assigning it (see below)
    + else just ignore this group.

## Re-assignment

The idea is to do something like in Hungarian algorithm. You can first ignore to make the algorithm run without, but it may increase performances especially to reduce the number of isolated element.

When an element $p$ should be re-assigned, you start building a tree with this element being the root. This tree explores the possibilities of re-assignment. So $p$ cannot join some groups because it does not share any time lapse with one of the elements of the group or because weight would pass threshold.

List all the elements $e\_i$ of the group that would let $p$ join if removed. Add all the $e\_i$ to the tree as children of $p$. In the tree the edges are indexed with the $\Delta D$. Then for each $e\_i$, look for the assignment leading to the lowest $\Delta D$. It may recursively ask for a new re-assignment, making you looking deeper in your tree.

An important point, is that in your recursions, you may encounter again a person which is already in the tree. Keep only the lightest path to it. At the end keep the all the path root to leaf that minimize the total $\Delta D$. All edge of this path is a re-assignment you actually do.

## Annealing

Now, you obtain some grouping which is probably not optimal. You can try to do some annealing to improve the state. For instance, break some of the groups with the largest distance and try to assign their elements again.

## Example

Some illustration of the method.

You want basically to assign $p$ here. The nodes are the person with blue edge between them if they share a time slot. The edge is red if it is selected to make a group. The values in the nodes are the index of the person but also their location value (just to make this example clearer), weights are not a problem in this example. The location of $p$ is 0.

So we build the assignment tree for $p$. $p$ is the root and it can either go with $6$ to form a new group ($\Delta D = 6$), either go in {$1,2,5$} group but $5$ has to be removed from the group ($\Delta D = -2$).

So add 5 in the tree and investigate on what $5$ can join instead. It can go in {$3, 4$} group removing $4$ ($\Delta D = 1$). And $4$ finally may join $6$ ($\Delta D = 2$). You found node $6$ again but with a lightest distance (total $\Delta D = 1$).

---
Tags: algorithms, optimization, combinatorics
---


# Question
Title: Changing a complete undecidable turing machine language
$L = \\{\langle M\rangle\mid \text{M is a TM and }L(M) = \\{101\\}\\}$ meaning M accepts only the string $101$. Which is neither co-recognizable / recognizable. Can be proven easily by $HALT \leq\_m L (\text{ or } \bar{L})$ mapping reduction. Reasoning being its very to prove for all TM that none accepts 101 or none rejects 101. How do I tweak this to make this either recognizable or co-recognizable but not both?

My attempt:

$L = \\{\langle M,w\rangle\mid \text{M is a TM and for some }L(M) = \\{101\\}\\}$

$\bar{L} = \\{\langle M,w\rangle\mid\text{M is a TM and for none }L(M) = \\{101\\}\\}$

I'm trying to change it to it *can* accept 101 instead of it only accepts 101. And the complement is that it *cant* accepts 101. I'm stuck at the complament i don't think its proper and the wording of the language. I don't know if theres a easy way to change this language.

# Answer
How about the following languages?

* $L\_{101}=\\{\langle M\rangle\\, \mid 101 \in L(M)\\}$, which is recognizable but not co-recognizable.
* $\overline{L\_{101}}=\\{\langle M\rangle\\, \mid 101 \not\in L(M)\\}$, which is co-recognizable but not recognizable.

Let $\text{HALT}\_\epsilon:= \\{ \langle M \rangle \mid M \text{ is a TM that halts on empty input.}\\}$. $L\_{101}$ and $HALT\_\epsilon$ can be reduced to each other easily.

Another set of choices can be the following classic languages.

* $\text{ACCEPT}=\\{\langle M, w\rangle\\, \mid w\in\Sigma^\*\text{ and } w\in L(M)\\}$, which is recognizable but not co-recognizable.
* $\overline{\text{ACCEPT}}=\\{\langle M, w\rangle\\, \mid w\in\Sigma^\*\text{ and } w\not\in L(M)\\}$, which is co-recognizable but not recognizable.
> 0 votes

# Answer
Well, lets start with your $L$ first. Claim: $L$ is undecidable.#

Clear: $L$ is not empty (there exist TM that accept that input) and not trvial (there exist a input w on some $M$ where $w \notin L(M)$ by definition of $L$. Thus, $L$ ist not trival and no property of $M$, so by Rice'S Theorem $L$ is not decidable.

For your $L^C$ the argumentation is basically the same, it is also undecidable.

To make a language r.e (recursive enumerable), in your terms co-recognizable we need a aditional property:

1. **Termination properties of your TM** For the recursive languages, we need this also, because REC is a subclass of RE.

A language $L$ is r.e. iff. for each $w \in L$ there exists a TM M, such that M **halts and accepts**. For recursive language you need more, here the TM must even **halt and decline** the input if it is not part of the language.

A recursive language would be:

$L\_{rec} = \\{\<M\> |$ for each input $w$ M halts and accepts, if $w = 101$, otherwise M halts and declines. $\\}$

EDIT: Language is not reursive (but r.e). If $L\_{rec}$ would be recursive, it would be co-recognizable. Given a word $x = \<U\>w$ (coding of U and input word w for U). Chose $U$ as a TM that never halts and $w=101$.

Assume there exists a TM $M$ which could compute that $\<U\>w \notin L\_{rec}$. That is if $U$ does not halt. So, $M$ has to know if $U$ halts and thus never halts (it always waits for U to stop). A contradiction.

I will let this answer stay here to clarify the pitfall between decidability and recognizability. Recognizablity is a weaker property of a language then decidability.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: BigO time complexity of 3 nested for loops
I'm debating with a friend whether a particular function I wrote is $O(N^3)$ or $O(N \times M \times X)$

I believe it is the latter since all 3 variables differ in size. $N = 100, M = 50, X = 10000$

```
for i in range(len(N)):
  for j in range(len(M)):
    for p in range(len(X)):
      if statement:
        count += 1
        list.append(count)

```

The outer loop executes $N$ times, the inner loop executes $M$ times, and the most inner loop executes $X$. Hence giving $N \times M \times X$. His theory is that because $X$ is so much greater than the other two variables it makes it $O(N^3)$

# Answer
> 1 votes
Obviously you can't say it's $O(N^3)$ because X might grow a lot faster than N. But you can't even say it's O (N x M x X), because you don't know how often the "list.append(count)" is executed and what the time complexity of that operation is.

# Answer
> 0 votes
As you have mentioned that $ N, M, X $ are variables, the time complexity would be $ O(N\*M\*X) $.
A possible counter argument for the complexity not equal to $ O(N^3) $ is, what if the rate of increase of $ X $ is greater than rate of increase of $ N $ ?

---
Tags: time-complexity, runtime-analysis, efficiency, big-o-notation
---


# Question
Title: Geometric median of two disjoint sets of points lies on line between their respective medians
I was working on a problem about geometric medians and I had an idea for a divide and conquer solution, but it would only work if a set of points, when split into two disjoint sets, and those sets respective geometric medians calculated and a line passed between, it holds that the geometric median of the overall set of points lies on that line. When graphing it and visualizing it, seems possible, and when I used existing algorithms and experimented, it seems to be **very close** but not quite on the same line. I am not sure if this is due to error in calculation of the geometric median or not.

I have some example Python code demonstrating how close the numbers are here: Geometric Median comparison

Any expertise in this matter would be appreciated.

# Answer
> 1 votes
If $A$ and $B$ are two set of points, the geometric median of $A \cup B$ does **not** necessarily lie on the line passing between the geometric mean of A and the geometric mean of $B$.

In the following example the points of $A$ are red and the one in $B$ is blue. The geometric median of $A$ is the red square. The green line connects the geometric means of $A$ and $B$. The black square is the geometric mean of $A \cup B$, i.e., the Fermat point of the triangle whose vertices are in $A \cup B$.

---
Tags: algorithms, computational-geometry, linear-algebra, divide-and-conquer
---


# Question
Title: Check if two separate ranges have some number in common
We are given two permutations: A of size N and B of size M. We need to process Q queries, each query is given by two ranges, one subarray range in permutation A and one in B. We should check if there is at least one same number in those two ranges.

We don't need to answer the queries online, so we can sort them in different ways.

I tried different things with segment trees, but I don't have working ideas

# Answer
> 1 votes
You can get $\tilde{O}(NM)$ preprocessing time and $O(1)$ time per query.

Assume for simplicity that $N$ and $M$ are powers of $2$. For each index $i = 1, \dots, n$ and $h = 2^0, 2^1, \dots, 2^{\log N}$, let $A\[i, h\]$ be the set of the elements in positions from $i$ to $i + 2^h -1$ in $A$. Define $B\[j, k\]$ similarly.

Let $R\[i, h, j, k\]$ be true if $A\[i,h\] \cap B\[j, k\] \neq \emptyset$ and false otherwise. You can compute each $R\[i, h, j, k\]$ in constant time by exploiting the following relations: $$ R\[i, h, j, k\] = R\[i, h-1, j, k\] \vee R\[i + 2^{h-1}, h-1, j, k\] \quad \mbox{for }h\>0 \\ R\[i, h, j, k\] = R\[i, h, j, k-1\] \vee R\[i, h, j + 2^{k-1}, k-1\] \quad \mbox{for }k\>0$$

where $R\[i, 0, j, 0\]$ is true iff the i-th element of $A$ equals the $j$-th element of B.

There is an intersection between the elements of A in positions $i, i+1, \dots, i+\ell\_A - 1$ and the elements of B in positions $j, j+1, \dots, j+ \ell\_B - 1$ iff the following condition is true: $$ R\[i, h, j, k\] \vee R\[i + h, h, j, k\] \vee R\[i, h, j + k, k\] \vee R\[i + h, h, j + k, k\], $$ where $h = \lfloor \log \ell\_A \rfloor$ and $k = \lfloor \log \ell\_B \rfloor$.

# Answer
> 0 votes
Either I'm misunderstanding something or you're severely overcomplicating the issue.

Memory: N+2M

Runtime: Q\*range\_A

A: plain old array

B: hashmap value =\> position

For slice of A: If B.get(a) within range\_B return true

Else return false

---
Tags: data-structures, arrays, permutations
---


# Question
Title: How to solve this job scheduling programming problem?
I am trying to solve this question. The question is a variation of job scheduling. There are n processes given to you with their execution time `Ti` and individual deadlines `Di`. A process can be executed anytime before its deadline. A process can not be executed after its deadline is over. So, you have to find the maximum number of processes that can be executed. Given that `n <= 1000` and `Ti & Di <= 1,000,000` For example:

```
Ti Di
3  4
4  8
11 23

```

**Answer = 3**

I tried to solve this question using branch & bound mechanism. I first sort the processes on the basis of deadline. Then like `0/1 knapsack`, I recursively took 2 cases. One is to take current process and other one is to discard this process. But the complexity of this approach is **2^n** and it gave me TLE. Please suggest a better approach for this problem.

# Answer
> 1 votes
I assume your question is "how many jobs can you achieve on time ?". The idea to use something like 0/1 knapsack is good. There is actually a DP resolution of 0/1 knapsack much more efficient than "recursively select or discard each item".

Let's call $t\_{max} = max(D\[i\])$, the end horizon of your problem.

Create a vector $A$ of size $t\_{max}$, $A\_i\[t\]$ stands for the number of achieved jobs at time $t$ after considering all jobs until $i^{th}$ one. Initially, $A\_0$ is filled with 0.

Then you loop on jobs, to build $A\_i$ from $A\_{i-1}$:

```
for t from D[i] to T[i] by -1:
    A[t] = max(A[t], A[t-T[i]]+1)

```

Time complexity is $O(Nt\_{max})$.

---
Tags: algorithms, dynamic-programming
---


title: Current value of flow in a network

text:
# Question
Title: Current value of flow in a network
Confused about a question regarding flow networks.

**Question is:** *Given the network below, what is the current value of flow in this network?*

Does the current flow of a network refer to the maximum flow or something else?

# Answer
> 0 votes
The question is asking how many units are flowing from $s$ to $t$ under the current flow.

The *maximum flow* problem asks for the maximal number of units that can flow from $s$ to $t$ under *any* flow.

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


title: Weak NP-completeness

text:
# Question
Title: Weak NP-completeness
I know that the Knapsack problem is weakly NP-complete. I also notice that on Wikipedia:

> "A problem is said to be strongly NP-hard if a strongly NP-complete problem has a polynomial reduction to it \[...\]"

The way I prove the NP-hardness is by a reduction chain: SAT $\leq$ 3SAT $\leq$ Tripartite Matching $\leq$ Exact cover by 3-sets $\leq$ Subset sum $\leq$ Knapsack.

Does it mean all these problems are weakly NP-complete? Because it seems that according to Wikipedia if one of them is strongly NP-complete, Knapsack will be strongly NP-complete.

# Answer
As is often the case, the Wikipedia article is misleading.

A problem involving integers parameters is:

* Strongly NP-complete if the problem is NP-complete when the parameters are encoded in unary (i.e., $n$ is encoded as $0^n$).
* Weakly NP-complete if the problem is NP-complete when the parameters are encoded in binary (which is the usual encoding).

In other words, there is only one notion of NP-completeness, and the confusing terms *strongly* and *weakly* NP-complete simply refer to different encodings of problems.

For a problem like SAT, these terms are simply inapplicable, since SAT has no integer parameters. The terms do apply to the related problem of weighted MAX-SAT, in which the input is a set of weighted clauses and a target, and the problem is to determine whether there is an assignment which satisfies clauses whose total weight exceeds the target.
> 6 votes

---
Tags: complexity-theory, np-complete
---


# Question
Title: is $x^{100000000000}$ a "polynomial time"?
per this post

> $t = x^2$ means the problem is solvable in "Polynomial" time.

per this post

> in the form
>
> $$a\_{n}x^{n}+a\_{n-1}x^{n-1}+\dotsb +a\_{2}x^{2}+a\_{1}x+a\_{0} { \> \boldsymbol{=0}}$$
>
> plug in $n=100000000000$ with $a\_n=1$ and $a\_k=0$ for all $k \neq n$
>
> then we see that $x^{100000000000}$ is a polynomial
>
> it doesn't matter if its 2, 3, or a billion, as long as the n is a finite number

in this context, does $t = x^{100000000000}$ still mean the problem is solvable in "Polynomial" time?

# Answer
> 2 votes
Yes, $x^{100000000000}$ is a polynomial. Your first quote gives an example; your second is the definition.

---
Tags: polynomial-time
---


title: $stCON$ with path of length $≥ n/2$

text:
# Question
Title: $stCON$ with path of length $≥ n/2$
The following problem seems very similar to the $stCON$ decision problem:

{$G, s,t | G = (V, E)$ such as $V$ is a graph, $s,t ∈ V$, there exists in $G$ a simple path from $s$ to $t$ of length $≥ n/2$}

But from what I've read, it cannot be placed in $NL$. The reason is unclear. Why it cannot be placed in $NL$ using an verifier Turing Mechine like in $stCON$ case and another counter for the path length?

# Answer
The NL algorithm for $s$-$t$ connectivity proceeds as follows. Start at $s$. For $n-1$ steps, guess a neighbor of the current node, and accept if that neighbor is $t$. The memory requires is two vertices (the current one and the next one), and a counter that counts the length of the current walk.

If you want to check that there is a simple $s$-$t$ path of length at least $n/2$, you need some way to ensure that in the process, vertices don't repeat. It's not so clear how to do that without storing all vertices visited so far, which cannot be done in logspace.
> 1 votes

---
Tags: complexity-theory, graphs
---


# Question
Title: Proving that a set of operations can't generate one integer from a given one
Given two numbers, $n$ and $m$, are there some mathematical methods of deducing $m$ from $n$ using limited number of elemantary operations?

Example: 335 can be deduced from 2000 using division by 2, addition of 5 and division by 3: $((2000/2)+5)/3) = 335$.

I need to prove that 1889 can't be derived from 2019 using the following 3 operations:

1. $n+7$ ;
2. $n\*2$;
3. $n/3$ (if divisible).

All I come up with is some sort of breadth-first search.

# Answer
> 3 votes
If you have implemented breadth first search correctly, you should have found that 1889 can be reached.

$\quad 2019+7\to 2026$
$\quad 2026+7\to 2033$
$\quad\quad\cdots\quad$ (add 7 repeatedly)
$\quad 4238+7\to 4245$
$\quad 4245 \div 3 \to 1415$
$\quad 1415 * 2 \to 2830$
$\quad 2830 * 2 \to 5660$
$\quad 5660 + 7 \to 5667$
$\quad 5667 \div 3 \to 1889$

It is possible that you had been asked to show that 1883 can't be derived from 2019.

### A number can be derived from 2019 iff it is a positive integer not divisible by 7

**Proof**:
"$\Longrightarrow$": If $n$ is not divisible by 7, neither is any of $n+7$, $n\*2$ and $n/3$ (when $n$ is divisible by 3). If we start with a number that is not divisible by 7, it will remain not divisible by 7 regardless of how many operations we have applied on it. Since 2019 is not divisible by 7, we cannot derive any number that is divisible by 7.

"$\Longleftarrow$":

In fact, we can derive all positive numbers not divisible by 7 without the operation $n\to n * 2$. For all $k\ge0$,

* $\dfrac{2019 + 7 * (((7k+1)\*3^{6k+7}-2019)/7)}{3^{6k+7}}=7k+1$
* $\dfrac{2019 + 7 * (((7k+2)\*3^{6k+11}-2019)/7)}{3^{6k+11}}=7k+2$
* $\dfrac{2019 + 7 * (((7k+3)\*3^{6k+6}-2019)/7)}{3^{6k+6}}=7k+3$
* $\dfrac{2019 + 7 * (((7k+4)\*3^{6k+9}-2019)/7)}{3^{6k+9}}=7k+4$
* $\dfrac{2019 + 7 * (((7k+5)\*3^{6k+8}-2019)/7)}{3^{6k+8}}=7k+5$
* $\dfrac{2019 + 7 * (((7k+6)\*3^{6k+10}-2019)/7)}{3^{6k+10}}=7k+6$

### Exercises

**Exercise 1.** Assume the same three operations. Let $n$ be a positive number not divisible by 7. Then a number can be derived from $n$ iff it is a positive integer not divisible by 7.

**Exercise 2.** Assume the same three operations. Let $n$ be a positive number divisible by 7. Then a number can be derived from $n$ iff it is divisible by 7.

**Exercise 3.** If positive integer $m$ can be derived from positive integer $n$ using the three operations, then $m$ can be derived from $n$ using the first and last operations, namely, $n\to n+7$ and $n\to n/3$ (if divisible).

# Answer
> 0 votes
Define $f(x) = x/3, g(x) = 2x, h(x) = x+7$ and $D = \mathbb{N}$ for the functions $f,g,h$. I presume that the question is the following:
Given $x,y \in \mathbb{N}$ is there a transformation sequence $s\_{(n)}:= (f \circ g \circ h) ^{n}$ such that $(f \circ g \circ h) ^{n}(x) = y)$ with the restriction that always $3 | (g\circ h)(f \circ g \circ h) ^{n-1}(x)$ ?

Now write $s\_{(n)}$ as a direct expression depending only on $x,n$. Lets call this $c(x,n)$. Here $c(x,n) = \frac{2^nx+14(2^n-1)}{3^n}$ For simplicity we write also $c(x,n):=\frac{num(x,n)}{3^n}$

Given $x,y$, then $y$ can be derived from $x$ iff $c(x,n)=y$ has a has at least one natural solution for $n$ and $3^i | num(x,i)$ for all $i \leq n, i \in \mathbb{N}$.

Applied this result to the conrete numbers, we see that the positive $n \approx 0.166$ and hence 1889 can not be derived from 2019.

If there are no restrictions on the composition of the function, this problem is (according to my professor) at least $NP$-complete. A formal proof would be nice, until now I didnt find a suitable Problem for a sharp reduction.

---
Tags: algorithms, number-theory, search-problem
---


# Question
Title: Why isn't the Generalized Super Mario Bros. obviously in NP?
It is shown in the paper: "Classic Nintendo Games are (Computationally) Hard" by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta that the Generalized Super Mario Bros. (SMB, for short) video game is NP-hard.

> **Theorem 3.1.** It is NP-hard to decide whether the goal is reachable from the start of a stage in generalized Super Mario Bros.

(When generalizing the original Super Mario Bros., we assume that the screen size covers the entire level, because the game forbids Mario from going left of the screen.)

---

However, it does not claim that SMB is in NP.

My problem: Why isn't SMB obviously in NP?

---

I came up with two reasons.

* First, the solution/certificate to SMB may be not of polynomial size, due to e.g., timing. Is this valid? If so, how to argue this point more formally?
* Second, the computer can be treated as a second player. Thus, SMB is a two-player game, which may be reasonably harder. However, are the actions of the computer player determined from the beginning of the game so that we can still regard SMB as a single-player game?

---

Related posts:

---

***Added:*** A follow-up paper also by Erik Demaine (et al.) which shows that a generalized level of SMB is PSPACE-complete.

# Answer
> 2 votes
One reason why it is not obvious that reachability of SMB is NP is that we would need a complete formalization of SMB, which the paper does not provide. This makes sense, as the purpose of the paper is to showcase techniques for proving NP- and PSPACE-hardness of reachability problems in generalized video games, and to do that they only have to fully specify the portion of the video game that is nessecary for their reduction framework.

Another aspect is that a priori I would see no reason that e.g. Donkey Country would be PSPACE-hard (which the paper shows), but SMB not. Sure, likely the framework from the paper cannot be used directly to show SMB is PSPACE-hard, but that doesn't mean it isn't possible. So, it doesn't seem obvious to me why SMB is *not* PSPACE-hard, from which it follows that it isn't obvious that it lies in NP. (as long as you don't think it is obvious that PSPACE$\neq$NP, at least)

---

As for your specific reasons why SMB might not be in NP, the fact that other games are PSPACE-hard seems a good argument why a polynomial certificate may not exist. However, proving that there indeed cannot be a polynomial size certificate would be the same as proving PSPACE$\neq$NP, so there are no known techniques to do that.

The second reason is related to the reason why the other games are PSPACE-hard. In general, solving two-player games can be done by reasoning "If P1 makes this move in turn 1, then for all moves P2 can do, pick a move for P2 s.t. $\ldots\ldots$ at the final move, P1 wins". This is the same as determining whether there is a satisfying assignment to a boolean formula with alternating universal and existential quantifiers: the true Quantified Boolean Formula problem (QBF). QBF is a PSPACE-complete problem.

This means that a 2-player game is PSPACE-hard if the above strategy of essentially going over all the moves is the *only* strategy to be guaranteed to win. The strategy of the 'computer' is of course limited in being only a simple function of the current state, but such a limited strategy can apparently be enough, as in the other games that are shown to be PSPACE-hard.

---

One question that may rise is why it *is* obvious that the problems lie in PSPACE. The authors cover this on page 2, but I will rephrase their argument here for the sake of completeness. Their main assumption is that the size required to describe the internal game state is polynomial in the input size. Their (somewhat informal) argument for this is that state changes of the game must controlled by a 'simple' and deterministic function of the player input. From the assumption it follows that we can solve a game reachability problem by making moves nondeterministically while maintaining the current game state. This means that the problem is in NPSPACE, and therefore in PSPACE as PSPACE=NPSPACE.

# Answer
> 0 votes
I remember discussing that with other people, and we came to the conclusion that it might have been because the authors couldn't exhibit a certificate of polynomial size.

For example, a path that solves the level might not be of polynomial size : maybe in some cases, you need to do an exponential number of steps to complete the level.
If you can show that for any level there exists there exists a path of polynomial size (or any other polynomial certificate), then you would prove that $SMB \in \mathcal{NP}$.

Also, the interesting point in a reduction is often the NP-hard part, which changes for every problem, the membership in NP is usually a formality, an looks very similar everytime (eventhough it is necessary). The authors might have chosen to ignore that part for this reason (EDIT : and therefore only done a hardness proof, not a completeness proof).

---
Tags: complexity-theory, np-complete, np, computer-games
---


# Question
Title: How to verify Hamilton-Path in log-space?
Given an undirected graph $G$ and an undirected path $p$, Is it possible to verify $p$ is a Hamilton path in graph $G$ using logarithmic space? How is it possible to verify the path goes through all vertices without somehow save which one had been already checked?

# Answer
> 1 votes
Instead of looking at every vertex in the path to see if you've visited the whole graph, look at every vertex in the whole graph and see if it's in the path. If the graph has $n$ vertices and the cycle doesn't, then reject. Otherwise,

```
for i = 1 to n do
    foundit = false
    for j = 1 to n do
        if path[j] = i then
            foundit = true
    if !foundit then
        return false
return true

```

Storage used is two integer variables, taking $\log n$ bits each, and one Boolean, taking some constant number of bits.

# Answer
> 2 votes
You can check all vertices in order.

Suppose we are given vertices $v\_1, v\_2, \cdots, v\_n$ and a path $p=(p\_1,p\_2, \cdots,p\_m)$.Check if $m==n$. If not, reject. Otherwise, check if $v\_1$ appears in $p$. If not, reject. Otherwise, check if $v\_2$ appears in $p$. If not reject. And so on. Finally check if $v\_m$ appears in $p$. If not, reject. Otherwise, accept.

---
Tags: complexity-theory, graphs
---


# Question
Title: Finding the maximum disjoint weight in a weighted node graph
I have a graph of nodes that reflect resource allocation. Each node has a weight to reflect this. A well formed graph is disjoint, so there will be no edges, and the weight of the graph is just the sum of the nodes. Any graph that contains edges needs to be reduced by removing one of the two nodes on an edge, until all edges are removed and the graph becomes disjoint. After reducing a graph the total weight should be the maximum possible.

I have already tried an algorithm that simply picks the largest node and discards the connected nodes. This has the problem that it may give a total that is too low.

So I need to find a new algorithm that will be accurate more consistently. My current idea is to look at the graph around each node and determine the difference between that node's weight and the total weight of the connected nodes.

1. Select the node with the largest difference
2. A positive difference means select the node and ignore the others
3. A negative difference means ignore this node and select the others
4. For a difference of zero it's not as clear which side to select
5. Repeat

At each stage, at least one node (and it's related edges) will be discarded from the graph. Eventually the graph will be made fully disjoint.

# Are there any other approaches, and what are the differing costs in terms of time and memory?

Below are some simple examples

## Case 1

AA:2, AB:3

No edges, so total weight is 5.

## Case 2

BA:3, BB:2, BC:5, BD:2

BB \<\> BC, BC \<\> BD

Total weight is 8 (BA + BC)

## Case 3

CA:2, CB:3, CC:5, CD:3

CB \<\> CC, CC \<\> CD

Total weight is 8 (CA + CB + CD)

My current approach would report 7 (CA + CC)

## Case 4

DA:4, DB:3, DC:3, DD:3, DE:4

DA \<\> DB, DA \<\> DC, DA \<\> DD, DC \<\> DE, DC \<\> DE

Total weight is 9 (DB + DC + DD)

My current approach would report 8 (DA + DE)

## Case 5:

EA:4, EB:3, EC:3, ED:3, EE:4

EA \<\> EB, EA \<\> EC, EA \<\> ED, EB \<\> EC, EC \<\> EE, EC \<\> EE

Note there is complete sub graph between nodes EA, EB, and EC

Total weight is 8 (EA + EE)

# Answer
The problem that you are trying to solve is called "maximum weight independent set". It is NP-hard so not much hope for exactly solving it efficiently. There exist efficient approximation algorithms though (see e.g. this question).
> 1 votes

---
Tags: algorithms, graphs, algorithm-analysis, weighted-graphs
---


# Question
Title: How to build tree from graph with specific property
We are given connected undirected graph of $n$ nodes and $m$ edges. On each node one integer(value) from $0$ to $n-1$ is written.

We need to build tree such that for each node $i$, all nodes in the subtree of $i$ should be reachable from $i$ by going only through edges with values greater than $i$.

Such tree is always rooted at $0$ since all vertices can be reached from $0$.

For example, for the given graph:

```
(5, 1), (1, 2), (1, 3), (3, 4), (3, 0), (5, 2)
The tree we are looking for is rooted at 0 and its edges are:
(0, 1), (1, 2), (1, 3), (2, 5), (3, 4)

```

I have heard that this is solvable with using disjoint data set structure however I couldn't find a way how to properly find a way to connect the components.

# Answer
> 0 votes
In a connected component, the minimum node can reach any other node without passing by a lower index node. As your initial graph is connected, the node 0 can indeed reach any other and is the perfect root for your tree.

For any connected component, you keep the index of the node it is attached to. Initially, there is none as 0 will be te root.

Once you considered the minimum node of a connected component, you can remove it as no other node in the CC may use it. Let's call this node $k$, you add $k$ to its place in the tree you are building, as child of the node index of the connected component.

Then either the connected component is still connected and its new index is $k$, either it is cut in several connected components, all having $k$ as index.

---
Tags: graphs, trees
---


# Question
Title: How to calculate average waiting time for round robin cpu scheduling?
I have tried to calculate average waiting time for the below details there are two answers I'm getting using two methods I'm not understanding which one is correct?

The time quantum is 2 This is the first method:

```
Process Id         Arrival Time        Burst Time
P0                      0                   5
P1                      1                   3
P2                      2                   1
P3                      3                   2
P4                      4                   3

```

This is the first gantt chart:

```
P0      P1      P2      P0      P2      P4      P1          P0          P4
0-2     2-4     4-5     5-7     7-9     9-11    11-12       12-13       13-14

Process Id         Waiting Time
P0                     8
P1                     8
P2                     2
P3                     4
P4                     7

```

> Average waiting time1: 29/5=5.8

And this is the second method:

This is the second gantt chart:

```
P0      P1      P2      P3      P4      P0      P1          P4          P0
0-2     2-4     4-5     5-7     7-9     9-11    11-12       12-13       13-14

Process Id         Waiting Time
P0                     9
P1                     8
P2                     2
P3                     2
P4                     6

```

> Average waiting time2: 27/5=5.4

# Answer
> 0 votes
The average waiting time would depend on the order in which the processes are scheduled. Your round-robin scheduler does not mention of an optimization scheme to minimize the waiting time. Both schedules listed out are correct and produce the respective waiting times.

---
Tags: operating-systems, scheduling, cpu
---


# Question
Title: Are there FPTASs for the min cost flow problem?
In literature, one can find many approximation algorithms for the multicommodity min cost flow problem or other variants of the standard single-commodity min cost flow problem. But are there FPTASs for the min cost flow problem?

Possibly, there is no need for an FPTAS here since an optimal solution can be computed very fast (using double scaling or the enhanced capacity scaling algorithm, for example). But from a theoretical point of view, this would be interesting to know.

# Answer
> 1 votes
If an optimal solution can be calculated in polynomial time, then the same algorithm gives you an FPTAS.

There might, however, be quasilinear time algorithms which give better and better approximations, running faster than algorithms for computing the min cost flow exactly.

# Answer
> 0 votes
You may want to look at "Adding Multiple Cost Constraints to Combinatorial Optimization Problems, with Applications to Multicommodity Flows" by David Karger and Serge Plotkin (STOC 1995). They find a $(1+\epsilon)$ approximation in ${\tilde O}(\epsilon^{-3}kmn)$ time, where $k$ is the number of commodities, $m$ is the number of edges, and $n$ is the number of vertices in the input problem.

---
Tags: algorithms, approximation, polynomial-time, network-flow
---


# Question
Title: Find axis-aligned rectangle with maximum area in a point set in the Euclidean plane
On the plane $n$ points $(x\_i, y\_i)$ are marked. Select 4 points so that they define a rectangle with the greatest area and sides parallel to the axes.

Time limit for python is 10 seconds, for other programming languages - 2 seconds.

Input data:

* in first string integer $n$, $(4 \leq n \leq 3000)$
* in next $n$ strings pairs of integer coordinates $x\_i\ y\_i$ $(-10\ 000 \leq x\_i,\ y\_i \leq 10\ 000)$

Output data:

* 4 different indices (numbers from $1$ to $n$), specifying the vertices of the rectangle.

I made in python, but even with tests of $n \leq 111$ it have TL.

```
n = int(input())
l = []
for i in range(n):
    a, b = map(int, input().split())
    l.append((a, b))

ans = [1, 2, 3, 4]
mS = 0

for i in range(0, n - 3):
    for j in range(i, n - 2):
        for k in range(j, n - 1):
            for t in range(k, n):
                r = [l[i], l[j], l[k], l[t]]
                w = sorted(r, key=lambda element:(element[0], element[1]))
                if w[0][0] == w[1][0] and w[1][1] == w[3][1] and w[3][0] == w[2][0] and w[2][1] == w[0][1]:
                    s = (w[1][1] - w[0][1]) * (w[3][0] - w[1][0])
                    if s > mS:
                        mS = s
                        ans = [i + 1, j + 1, k + 1, t + 1]

ans = sorted(ans)
print(ans[0], ans[1], ans[2], ans[3])

```

# Answer
**Step 1.** Sort all the points according to their $x$-coordinate - you will get an array of buckets, where each bucket contains a (sorted) list of points with the same $x$-coordinate. You can drop (or ignore in all subsequent steps) all the buckets, containing only single point.

**Step 2.** Define a mapping $M$, where the key will be a **closed integer interval** and the value - **ordered set of integers**. Scan all the buckets, created in the Step 1. For each bucket insert all the possible pairs of its $y$-coordinates into the mapping $M$ \- *their corresponding $x$-coordinates must be inserted into the set*, corresponding to this interval:

```
function Insert(M, x, y0, y1)
  if mapping M contains element ([y0, y1] -> S)
    insert x into set S
  else
    insert element ([y0, y1] -> (x)) into mapping M

```

You can drop (or ignore in all subsequent steps) all the elements of the mapping $M$, for which their value set contains only a single number.

**Step 3.** The mapping M will contain elements like this:

$$(\[y\_0, y\_1\] \rightarrow (x\_0, x\_1, ..., x\_{m-1}))$$

The *biggest* rectangle with "vertical" side $\[y\_0, y\_1\]$ will have "horizontal" side $\[x\_0, x\_{m-1}\]$, so you can ignore all the *middle* elements of the ordered set. Finally, scan all the elements in the $M$ to find the element with largest rectangle area $A$:

$$A = (y\_1 - y\_0) \cdot (x\_{m-1} - x\_0) $$

Number of intervals in $M$ is $O(n^2)$, so time to insert into the mapping will be $O(n^2log(n))$.
> 3 votes

# Answer
Sort the points indexes on increasing $x\_i$ (time complexity $O(N\log N)$). Then, with one loop on this sorted list, you can create the following structure:

* $GX$, list of sublists where points in the same sublist share the same $x$ value.
* $AX$, array of size $n$ giving for any $i$ the index of the sublist that contains $i$ in $GX$.

Once it is done, sort every sublist of $GX$ on increasing $y$

Let's do the same for $y$, to obtain $GY$ and $AY$. So far time complexity is still $O(N\log N)$.

A valid rectangle of four points $a, b, c, d$ starting up left clockwise should have:

* $AX\[a\] = AX\[d\]$
* $AX\[b\] = AX\[c\]$
* $AY\[a\] = AY\[c\]$
* $AY\[b\] = AX\[d\]$

Now, let's do the nested loops using $GX$ and $GY$ to hardly reduce the number of rectangles to check:

* Loop on all possible $a$
* Loop on all $b$ in $GY\[AY\[a\]\]$
* create two pointers $c$ and $d$ in respectively $GX\[AX\[b\]\]$ and $GX\[AX\[a\]\]$
* evaluate in linear time all possible $c, d$ such that $y\[c\] = y\[d\]$ (it is possible as the GX are sorted by $y$)

Complexity should be $O(N^2)$, I am not sure about that.

As all the sublists are sorted, you can also know the maximum array reachable from the upper left corner in $O(1)$. So check the potentially large rectangles first and use a stop criterion.

You finally have a $O(N^2)$ complexity instead of your $O(N^4)$.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Dove tailing questions about accepting language
$L = \\{M | \text { M is a TM and there exist some string w that contains five 1's such that M halts}\\}$

Where $\Sigma =\\{0,1\\}$

let $w\_1, w\_2, \cdots, \in \Sigma^\*$ be an effective enumeration. We give a TM $R$ that recognizes $L$

```
R = "On input <M>
    for s = 1 to infinity:
        for i = 1 to s
            run M on input w_i for s steps
            if M halts on w_i within s steps then
                accept

```

Can I assume $M$ knows to halt only if there are five $1$'s? Or do I need another if statement such as in line 4

```
if M halts on w_i within s steps then
    if w_i.count("1") is 5 then
        accept

```

# Answer
Showing some machine $R$ that recognizes $L$ is enough to prove that $L$ is recognizable, however, you have yet shown $R$ recognizes $L$.

Formally, you must show:

* $M \in L \Rightarrow R $ accepts $M$
* $M \notin L \Rightarrow R $ does not accept $M$, but not necessarily halts.

---

Let $S\_i$ be all strings in $\Sigma ^\*$ of length exactly $i$. It is clear, for any $i$ that is finite, $S\_i$ is also finite.

Let $S\_i^\*$ be a subset of $S\_i$, where every $s \in S\_i ^\*$ contains exactly five $1$'s.

$R$ is a machine that given input $M$:

1. for $i=5...\infty$
2. for $s$ in $S\_5^\* \cup S\_6^\* \cup \dots \cup S\_i^\*$

simulate $s$ on $M$ for $i$ steps. If $M$ halts in $i$ steps or less, finish and accept. Otherwise continue.

Suppose $M \in L $ (and we will show $R$ accepts $M$): There exists $w^\*$ of length $k$ that contains five $1's$ and $M$ halts on $w^\*$ in $r$ steps.

Since $S\_i^\*$ is finite, $S\_5^\* \cup S\_6^\* \cup \dots \cup S\_k^\*$ is also finite (finite union of finite subsets), so $R$ simulates $w^\*$ on $M$. Now if $r \leq k$ then $M$ halts and $R$ accepts $M$.

If $r \> k$ then surely $w^\* \in S\_5^\* \cup S\_6^\* \cup \dots \cup S\_r^\*$, hence at $i=r$ $M$ will halt on $w^\*$ and $R$ will accept.

The second step is very simple; if $M \notin L$ then no such $w$ with five $1's$ exists such that $M$ halts on it, and $R$ will run indefinitely.
> 0 votes

---
Tags: turing-machines
---


title: Recurrence with Minimum

text:
# Question
Title: Recurrence with Minimum
I need to solve the following recurrece:

$T(n,m)=\begin{cases} 1, & m\leq 2(n-1)!\\ \min\limits\_{a,b\geq 1\\a\cdot b\leq (n-1)!}{T(n-1,a)+T(n-1,b)+T(n,m-ab)}, & \text{else} \end{cases}$

Note: in the first line beneath the $\min$ we have $a,b$ and in the next line it's $a\cdot b$.

I find it difficult to solve this recurrence as it contains $\min$, so I tried to calculate the minimum, but I didn't know how to prove it (I believe that the minimum occurs at $a=b=\sqrt{(n-1)!}$, but I don't know how to prove it...). So I am stuck with this.

Any help would be highly appreciated!

**Edit:**

Experiments show that

$T(n,m)=\begin{cases}1 & f(n,m)\leq 0\\ 3+2\Big\lfloor\frac {f(n,m)-1}{(n-1)!}\Big\rfloor & \text{else}\end{cases}$

for $f(n,m)=m-2(n-1)!$, and considering the $\min$ of an empty set to be infinity.

# Answer
> 1 votes
Let us prove that for $m \geq 1$, $$ T(n,m) = \max(1, 2\lfloor \tfrac{m-1}{(n-1)!} \rfloor - 1). $$ (This is the same as your formula.)

If $m \leq 2(n-1)!$ then by definition $T(n,m) = 1$, and indeed $\lfloor \tfrac{m-1}{(n-1)!} \rfloor \leq 1$, showing that our formula also gives the value $1$. If $m \> 2(n-1)!$, then $$ T(n,m) = \min\_{\substack{a,b \geq 1 \\ ab \leq (n-1)!}} T(n-1,a) + T(n-1,b) + T(n-ab). $$ Since $ab \leq (n-1)!$ also $a,b \leq (n-1)!$, and so $T(n-1,a) = T(n-1,b) = 1$. Therefore $$ T(n,m) = 2 + \min\_{\substack{a,b \geq 1 \\ ab \leq (n-1)!}} T(n,m-ab) = 2 + \min\_{1 \leq c \leq (n-1)!} T(n,m-c). $$ We can prove inductively that $T(n,m)$ is monotone nondecreasing, and so $$ T(n,m) = 2 + T(n,m-(n-1)!). $$ From here it's not too hard to prove the formula by induction.

---
Tags: recurrence-relation, factorial
---


# Question
Title: Decision problem - vertex with path to all other vertcies
Consider the following decision problem: Given a directed graph $G$, is there a vertex $v$ that has path to all other vertcies. I am able to place this problem in NL, similarly to the strongly-connected graph problem. But is this problem NL-complete? Thinking about reduction from $stCON$ problem, but can't get it through.

# Answer
Suppose we are given a directed graph $G$ and two vertices $s,t$. Add a new vertex $a$ and an edge from $a$ to $s$. Also, add an edge from $t$ to all vertices in the graph apart from $a$.

Since $a$ has no incoming edges, if there is any vertex from which all other vertices are reachable, it must be $a$. For this to happen, in particular $t$ must be reachable from $a$. Since the only outgoing edge from $a$ points at $s$, this can only happen if $t$ is reachable from $s$. In that case, all other vertices are also reachable from $a$, via $t$, since we added outgoing edges from $t$ to all vertices apart from $a$.
> 1 votes

---
Tags: complexity-theory, graphs
---


# Question
Title: If the Intel Pentium processors, was not made compatible to programs written for its predecessor, it could have been designed to be a faster processor
I find this question while solving some government job question bank. If someone could provide the answer along with a little explanation it would be very helpful.

Ques:- If the Intel Pentium processors, was not made compatible to programs written for its predecessor, it could have been designed to be a faster processor.

1. The statement is true
2. The statement is false
3. The speed cannot be predicted
4. Speed has nothing to do with the compatibility

(I did not find any tag as microprocessor or something so i have to keep it under the tag computer architecture, sorry for that, but i did not have sufficient reputation to create a tag.)

# Answer
> 1 votes
Let me ask you a similar question. If car X, which is automatic, didn't have to support manual gear, then it could have been designed faster:

1. The statement is true
2. The statement is false
3. The speed cannot be predicted
4. Speed has nothing to do with the compatibility

What do you think?

---

Let me mention in passing two relevant points from the world of computers:

* Intel *did* design a Pentium-replacement with a completely new architecture, *Itanium*. It wasn't successful, for various reasons. One of them was lack of compatibility.
* All problematic aspects of Windows are often blamed on backward compatibility.

---
Tags: computer-architecture
---


# Question
Title: Is finding a single digit of a computation is as hard as finding the computation?
Let $f: \mathbb{N} \rightarrow \mathbb{N}$ a computable function such that computing $f(n)$ takes $\Omega(2^{2^{2^{|n|}}})$ time in worst case terms and such that the languages:

$$\begin{align\*} L\_1 &= \\{ n \mid f(|n|) = n \\} \\ L\_2 &= \\{ (n,k) \mid \text{the first digit of $n$ is the $k$'th digit of $f(|n|)$} \\}\end{align\*}$$

Are infinite.

Prove or disprove that $L\_1 \leq\_{P} L\_2$ i.e there is a polynomial time reduction from $L\_1$ to $L\_2$.

Heuristically I am thinking that for any function it is impossible to compute a digit of the computation without generally computing the function so I am thinking it should be correct, though not sure how to prove it formally.

# Answer
> 1 votes
For some functions $f$ you might be correct. For example, we can arrange that $f(|n|) \neq n$ for all $n$ (by controlling the length of $f(x)$) while keeping $f$ arbitrarily difficult, and so $L\_1$ reduces to $L\_2$ trivially.

Here is a function $f$ satisfying your constraint, for which $L\_1$ does not polynomially reduce to $L\_2$. The construction uses diagonalization. (There is some ambiguity in your notation, but the proof can be adapted however you resolve the ambiguities.)

Let $L$ be some computable language which requires time $2^{2^{2^n}}$ (such languages exist due to the time hierarchy theorem). We define the function $f$ as follows: $f(\epsilon) = f(0) = 0$, and $f(0x)$ is the indicator of $x \in L$. We define the rest of the function $f$ by giving an algorithm which eventually defines all remaining values.

Let $\phi\_i$ be an enumeration of all functions computable in polynomial time. We can construct such an enumeration using timed Turing machines. We go over the functions $\phi\_i$ in order. When it's time to process $\phi\_i$, let $n \geq 1$ be the smallest value on which $f$ is undefined. Let $m = \phi\_i(0^n,2)$. We consider several different cases:

* Case 1: $f(|m|)$ is already defined. If the second digit of $f(|m|)$ is $0$, define $f(n) = 1^n$, otherwise define $f(n) = 0^n$.
* Case 2: $f(|m|)$ is not defined, and $|m| \neq n$. Define $f(|m|)$ arbitrarily, and proceed as in case 1.
* Case 3: $|m| = n$. Set $f(n) = 10$.

In all cases, we ensure that $f(n) \neq 0^n$ iff the first digit of $0^n$ equals the second digit of $f(|m|)$, showing that $\phi\_i$ is not a polytime reduction from $L\_1$ to $L\_2$.

# Answer
> 0 votes
If your result is a k digit integer, then finding the result is at most k times harder than finding the digit that is hardest to find.

There are functions where some digits may be easy to find, and some harder. For example, it is a lot easier to find the k-th digit of pi in hexadecimal than to find all of the first k hexadecimal digits, but the same is not known for decimal.

All depends on the function.

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


# Question
Title: Split array into contiguous subarrays of approximately same sums
My question is similar to this splitting question, but my objective function is different.

Looking for an algorithm to split array of $n$ positive (integer) numbers into $N$ contiguous non-empty subarrays ($N\<n$) of approximately same sums:

$$ \min\_{\text{splits}} \\,(\max\_j S\_j - \min\_j S\_j), $$ where $S\_j$ is sum of numbers in $j$-th subarray $(j=1,\ldots,N)$.

E.g., best splitting of $100, 1, 1, 103, 90$ into three subarrays is $100,1,1|103|90$.

Typically $n\approx~10^6-10^8$, $N\approx 10-100$.

I suspect it would be some greedy approach...

# Answer
This is a polynomial time algorithm:

Let $S^\*\_j$ be the sum of the the elements in the $j$-th subarray in an optimal solution and guess $m^\* = \min\_j S^\*\_j$ (there are only polynomially many choices of $m^\*$).

Given a a way to split an array into $k$ contiguous subarrays of sums $S\_1, \dots, S\_k$, define the *cost* of such a subdivision as: $$ \begin{cases} \max\_i S\_i & \mbox{if } \min\_i S\_i \ge m^\* \\ +\infty & \mbox{ otherwise.} \end{cases} $$

Let $OPT\_{m^\*}\[i,k\]$ the cost to split the array consisting of the first $i$ input elements into $k$ contiguous (non-empty) subarrays, and let $x\_i$ be the $i$-th input element. Then, for $i,k \ge 1$, $$ OPT\_{m^\*}\[i\]\[k\] = \min\_{j=0, \ldots, i-1} \begin{cases} \displaystyle\max\\, \left\\{ OPT\_{m^\*}\[j\]\[k-1\], \sum\_{h=j+1}^i x\_i \right\\} & \mbox{if } \displaystyle\sum\_{h=j+1}^i x\_i \ge m^\* \\\\[10pt\] +\infty & \mbox{otherwise} \end{cases}. $$

Where $OPT\_{m^\*}\[0\]\[0\] = 0$ and $OPT\_{m^\*}\[i\]\[0\] = OPT\_{m^\*}\[0\]\[k\] = +\infty$ for all $i,k \> 0$.

The measure of an optimal solution to the original problem will be $OPT\_{m^\*}\[n\]\[N\] - m^\*$ and you can reconstruct where to split the input array using standard techniques (e.g., by inspecting the dynamic programming table in reverse order or by storing the value of $j$ chosen for each entry $OPT\_{m^\*}\[i\]\[k\]$).
> 2 votes

# Answer
For a partition $p$ of some numbers into $N$ parts, let $\delta(p)$ be the largest difference between the sums of numbers in the same part, i.e., $\delta(p)=\max\_j S\_j - \min\_j S\_j$, where $S\_j$ is the sum of numbers in $j$-th part, $1\le j\le N$.

This answer gives an approximate algorithm that is about as fast as possible and as simple as possible. It return a partition $p$ such that $\delta(p)\lt 2u$, where $u$ is the maximum number in the given array of positive numbers.

**An example to illustrate the approximate algorithm**

Suppose we should split array $$\[5, 8, 1, 2, 4, 1, 7, 3, 1, 6, 7, 10, 8, 9, 4, 2, 2, 8, 3, 5, 2, 6, 13, 11, 5, 8, 3, 5, 1, 9, 5\]$$ into $N=6$ parts, subarray $p\_1, p\_2, p\_3, p\_4, p\_5$ and $p\_6$. Let $S\_j$ be the sum of numbers in $p\_j$.

The sum of all numbers in the array is $166$. The average of all $S\_j$ is $avg=164/6=27.\bar3$.

1. $S\_1$ should be no less than $avg$ but as small as possible. Hence $p\_1= \[5, 8, 1,$$\\,2, 4, 1, 7\]$ and $S\_1=28$.
2. The next sum $S\_2$ should be no more than $avg$ but as big as possible. Hecne $p\_2= \[3, 1$$, 6, 7, 10\]$ and $S\_2=27$.
3. Since the average of $S\_1$ and $S\_2$ is greater than $avg$, the next sum $S\_3$ should be no more than $avg$ but as big as possible. Hence $p\_3=\[8, 9,$$\\,4, 2, 2\]$ and $S\_3=25$.
4. Since the average of $S\_1, S\_2$ and $S\_3$ is smaller than $avg$, the next sum $S\_4$ should be no less than $avg$ but as small as possible. Hence $p\_4=\[8, 3,$$\\, 5, 2, 6, 13\]$ and $S\_4=37$.
5. Since the average of $S\_1, S\_2, S\_3$ and $S\_4$ is greater than $avg$, the next sum $S\_5$ should be no more than $avg$ but as big as possible. Hence $p\_5=\[11, 5,$$\\,8,3\]$ and $S\_5=27$.
6. Finally, what remains is the last part, $p\_6=\[5,1,9,5\]$ and $S\_6=20$.

$$\[\underbrace{5, 8, 1, 2, 4, 1, 7}\_{p\_1},\underbrace{3, 1, 6, 7, 10}\_{p\_2},\underbrace{8, 9, 4, 2, 2}\_{p\_3},\underbrace{8, 3, 5, 2, 6, 13}\_{p\_4},\underbrace{11, 5, 8, 3}\_{p\_5},\underbrace{5, 1, 9, 5}\_{p\_6}\]$$

$\delta((p\_1,p\_2,p\_3,p\_4,p\_5,p\_6))=\max\_j S\_j - \min\_j S\_j=37-20=17$.

**Pseudocode**

Input: an array of $n$ positive numbers $a\[0\], a\[1\],\cdots, a\[n-1\]$ and $N$, a positive integer smaller than $n$.

Output: increasing indices $i\_1,i\_2, \cdots, i\_{N-1}$ such that $\delta(p)\<2u$, where the $j$-th part of partition $p$ is the (contiguous) subarray whose indices are between $i\_{j-1}$ inclusive and $i\_{j}$ exclusive, where $1\le j\le N$, $i\_0=0$ and $i\_N=n$. $\ \ u$ is the maximum of all $a\[i\]$.

Procedure:

1. Create the array of partial sums $ps$ by $ps\[0\]\leftarrow 0$ and $ps\[i\]\leftarrow ps\[i-1\]+a\[i-1\]$ for all $1\le i\le n$.
2. $parts\leftarrow1$. $\ \ at\\\_least\leftarrow\text{True}$. $\ \ j\leftarrow0$. $\ \ avg\leftarrow ps\[n\]/N$.
3. While $parts\<N$:
    1. If $at\\\_least$ is $\text{True}$, find the smallest index $k$ such that $k\gt j$ and $ps\[k\] \ge ps\[j\]+avg$. Otherwise, find the largest index $k$ such that $k\gt j$ and $ps\[k\]\le ps\[j\]+avg$.
    2. Output $k-1$.
    3. If $ps\[k\]\le parts\times avg$, $\ at\\\_least\leftarrow\text{True}$; otherwise $at\\\_least\leftarrow\text{False}$. $\ parts\leftarrow part+1$. $\ \ j\leftarrow k$.

We can add a bit of bookkeeping to track $\max\_j S\_j$ and $\min\_j S\_j$ so that the procedure can output $\delta(p)$ as well.

Note that this algorithm does not require $a\[i\]$ be an integer. It works equally well when they are floating-point numbers.

**Complexity**

The algorithm runs in $O(n)$ time-complexity, where $n$ is the number of elements in the given array. When $n$ is as large as $10^8$, a reasonable implementation is likely to return the result well within a second where the time to read the input is excluded.

The algorithm uses $O(n)$ working spaces. In fact, the array of partial sums is introduced only for the sake of easier description and coding. If we replace it with computing of the partial sums on demand, the algorithm will run with $O(1)$ space-complexity and the same $O(n)$ time-complexity.

**Implementation in Java**

Just click the "run" button to see the test result.

**Exercise.**

Show the partition $p$ obtained by the approximate algorithm satisfies $\delta(p)\lt 2u$ by establishing that $|S\_j-avg|\<u$ for all $j$.
> 1 votes

---
Tags: algorithms, dynamic-programming, greedy-algorithms
---


# Question
Title: Exercise 11 of section 3.2.2(The art of computer programming)
I'm asking about its part a.

> a) If $f(z),\space a(z),\space b(z)$ are polynomials with integer coefficients, let us write $a(z)\equiv b(z) (\operatorname{mod} f(z)\space and\space m)$ if $a(z) = b(z) + f(z)u(z) + mv(z)$. Prove that the following statement holds when $p^e\>2$ (p prime) , $f(0)=1$:
>
> *If $z^\lambda \equiv 1 (\operatorname{mod} f(z)\space and\space p^{e})$ and $z^\lambda \not\equiv 1 (\operatorname{mod} f(z)\space and\space p^{e+1})$ then $z^{p\lambda} \equiv 1 (\operatorname{mod} f(z)\space and\space p^{e+1})\space but\space z^{p\lambda} \not\equiv 1 (\operatorname{mod} f(z)\space and\space p^{e+2})$*

Here's my reasoning:
We have $z^\lambda$ has the form of $$f(z)u(z) + p^ev(z) + 1$$ where $p^{e+1}|f(z)u(z),f(z)|p^ev(z)$ and $v(z)\not\equiv 0(\operatorname{mod} p)$ **(\*)**
Or we can just simplify it as: $z^\lambda = Z + 1$, where Z is a multiple of $f(z)$ and $p^e$ but not $p^{e+1}$'s one. So:$$z^{p\lambda} = 1+{p\choose 1}Z+{p\choose 2}Z^2+...$$
$z^{p\lambda}-1$ is certainly divisable by f(z). Also, we can see that ${p\choose k}Z^k(1\leqslant k\leqslant p-1)$ is a multiple of $p^{e+1}$ and $p^{e+2}|Z^p$(due to the fact $p^e\>2$,$p^{pe}|Z^p$ implies $p^{e+2}|Z^p$). We now can conclude: $$z^{p\lambda} \equiv 1 (\operatorname{mod} f(z)\space and\space p^{e+1})$$

Next, it's easy to establish: $p^{e+2}|p^{(e+1)k}$,where $k\geqslant$ 2. And that shows: $$z^{p\lambda} \equiv 1 + p^{e+1}v(z) (\operatorname{mod} p^{e+2}\space and\space f(z))$$ Due to **(\*)**,$1+ p^{e+1}v(z) \not\equiv 1(\operatorname{mod} p^{e+2})$, completing the proof

---

My proof is based on the answer of excercise 11. And the difference between it and mine makes me confused.

> If $p^{e+1}v(z) \equiv 0 (\operatorname{mod} f(z)\space and\space p^{e+2})$, there must exist $a(z)$ and $b(z)$ such that $p^{e+1}(v(z) +pa(z)) = f(z)b(z)$. Since $f(0)=1$, this implies $p^{e+1}|b(z)$(by Guass's lemma 4.6.1G); hence $v(z) \equiv 0 (\operatorname{mod} f(z)\space and\space p)$, a contradiction.

So, my questions are:
*1. Why is the above argument necessary?*
*2. Is the Gauss's lemma 4.6.1G the one in wikipedia?*

# Answer
> 1 votes
> We have $z^\lambda$ has the form of $$f(z)u(z) + p^ev(z) + 1$$ where $p^{e+1}\mid f(z)u(z),f(z)\mid p^ev(z)$ and $v(z)\not\equiv 0\pmod p\ $ **(\*)**

You misunderstood the definition of $a(z)\equiv b(z)\pmod {f(z)\text { and }m}$. If $z^\lambda \equiv 1 \pmod{ f(z)\text{ and }p^{e}}$, then $$z^\lambda=1 + f(z)u(z) + p^ev(z)$$ for some $u(z), v(z)$. There is no further requirement on $u(z)$ and $v(z)$. It is incorrect to deduce $p^{e+1}\mid f(z)u(z)$. It is incorrect to deduce $f(z)\mid p^ev(z)$.

However, if we also have $z^\lambda \not\equiv 1 \pmod{ f(z)\text{ and }p^{e+1}}$, then we must have $v(z) \not\equiv 1 \pmod{ f(z)\text{ and }p}.$

---

> Why is the above argument necessary?

Now that you can understand the notation correctly, you can figure it out by yourself.

---

> Is the Gauss's lemma 4.6.1G the one in Wikipedia?

Yes, lemma 4.6.1G in the book is the same as the Gauss's lemma on Wikipedia.

---
Tags: algorithms, modular-arithmetic
---


# Question
Title: Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?
We say that two languages $L\_1,L\_2$ are decreasing reducible if there exists a **polynomial time** reduction $f:\Sigma^\*\to\Sigma^\* $ and there exists $n\in\mathbb{N}$ such that for every $x\in\Sigma^\*$ satisfying $|x|\ge n \implies |f(x)|\lt |x|$.

Assuming $P\ne NP$

> Prove\Disprove: Every two NP-complete languages $L\_1,L\_2$ are decreasing reducible.

I'd appreciate a hint or direction

# Answer
Let $L$ be any NP-complete language, and consider what happens when $L\_1 = L\_2 = L$. Given an instance $x$, by applying $f$ a linear number of times we would get that $x \in L$ iff $y \in L$, where $|y| \< n$. Since there are only finitely many strings of length smaller than $n$, we can hardcode the correct answer for these strings, thus obtaining a polynomial time algorithm for $L$.
> 4 votes

---
Tags: complexity-theory, turing-machines, computability, np-complete, reductions
---


# Question
Title: Parallelization of priority queue-based algorithms
There's a number of algorithms that operate by maintaining and consuming a priority queue of "events". I'm thinking primarily of geometric algorithms, particularly sweep-line algorithms like Bentley-Ottmann and Fortune's algorithm, but also things like Dijkstra's algorithm and Prim's algorithm.

There's no trivial way to parallelize these algorithms: In non-degenerate cases there's exactly one event which is legal to process. One could speculatively distribute the next `n` events to `n` processors, but (a) handling them in any interleaved order would generally violate the algorithm's invariants, and (b) would often add new events to the priority queue which should have been handled earlier.

Nevertheless, for things like sweep-line algorithms, there's a natural locality to exploit. Handling two events which are close to each other along the sweep axis but far away on the perpendicular axis would *probably* be okay as long as the underlying state structure could be concurrently updated, and one could imagine either speculatively handling those events and rolling back only when interactions were detected, and/or partitioning a prefix of the queue into mutually independent workloads.

Are there any articles which explore this sort of approach, either for specific problems or for paradigms like sweep-line algorithms?

# Answer
Two old, but, I think, still very useful resources:

* M.T.Goodrich, M.R.Ghouse, and J.Bright. **Sweep Methods for Parallel Computational Geometry**. *Algorithmica* (1996), 15:126-153. - closely related to what you are asking about, download for free: link.
* S.G.Akl, K.A.Lyons. **Parallel Computational Geometry**. Prentice-Hall, 1993 - monograph about first ten years of research in parallel computational geometry. In the Chapter Four they say: "The plane sweep technique appears to be inherently sequential", but nevertheless refer to a number of parallel sweeping algorithms. Please see: link.
> 3 votes

---
Tags: reference-request, computational-geometry, parallel-computing, priority-queues
---


title: How to put elements in allowed bags?

text:
# Question
Title: How to put elements in allowed bags?
Let's say I have a list of "Items"

I also have a list of "Bags". Each bag is a set of "Items" which gives what item can be placed in that bag. But only one item can go in each bag.

I want to place all items in a bag. It's okay if there are empty bags left over.

Does this sort of problem have a name and a solution other than a naive depth first search (a link in the direction of such an approach will be fine)?

# Answer
> 1 votes
This problem is call "$X$-satuated bipartite matching" or Hall's marriage problem, which is discussed at here on Wikipedia.

Consider each item as a woman. Each bag is a man. If item $a$ is allowed to be placed in bag $x$, it means woman $a$ and man $x$ can be married happily. Only one item can go in each bag corresponds to the assumption of monogamy, a man with one wife and a woman with one husband. So the problem is asking whether it is possible that all women can be married happily.

Please check the link for details and much more interesting result around. You can find various efficient algorithms to solve the problem and related problems.

Since we are here, we should mention the following celebrated theorem.

> Hall's Marriage Theorem — A family $S$ of finite sets has a transversal if and only if $S$ satisfies the marriage condition.

---
Tags: algorithms, terminology, knapsack-problems, constraint-satisfaction
---


# Question
Title: Does a Minimum-Spanning-Tree always give a lower bound for the weight of any Hamiltonian cycle of the graph?
A minimum-spanning-tree (MST) path is always $V-1$ edges and a Hamiltonian Cycle (HC) is always $V$ edges.

Because the HC has an extra edge we could say that in general, the weight of every Hamiltonian cycle of a connected graph will be more.

If we take an edge of every Hamiltonian cycle we will find an MST and by that, the MST weight will be always lower than HC.

* There is a way to prove this where MST tree not necessary belongs to the HC?
* There is more definitive proof for this?

# Answer
Suppose:

* $G$ is some graph with non-zero, positive weights.
* The minimum spanning tree of $G$ is denoted by $MST$
* $H\_C$ is a hamiltonian *cycle* in $G$.
* $H\_P$ is a hamiltonian *path* in $G$, given by removing any one edge of $H\_C$.

Since all the edges are positive and non-zero, we immediately get that:

$$w(H\_C) \> w(H\_P)$$

Also, $H\_P$ is a subgraph that includes all vertices of $G$ (and connects them), so $H\_P$ in fact spans $G$.

Hence, by definition of minimum spanning tree:

$$w(H\_P) \geq w(MST)$$

It follows that $$w(H\_C) \> w(H\_P) \geq w(MST)$$

---

In case we allow zero weights, the inequality holds, it simply will not be strictly greater (for the same reasons noted in the answer). That is: $$w(H\_C) \geq w(H\_P) \geq w(MST)$$
> 3 votes

---
Tags: complexity-theory, graphs
---


# Question
Title: Can I simplify successive XOR operations?
I'm doing an online programming challenge where successive XOR operations are used (from codewars.com, if you don't want to create an account, here are the instructions).

We have a rectangle of known dimensions where every value of column and row (zero-indexed) are XOR-ed in order to create a value. Then, we must compute the sum of every value of that rectangle. (i.e. for a rectange of 8 columns & 5 rows, the first value would be 0 ^ 0 = 0, then 0 ^ 1 = 1, etc. until 7 ^ 4 = 3, then the sum of every value would give 105, which is the result)

I've tried different approach to this problem, but every one of them end up being too slow and not enough efficient. The naive solution is of time complexity $O(N^2)$, which becomes too slow when we're working with a lot of values.

Here would be the function to compute the value of 1 row. (x is the number of columns & y is the number of the current row) $$ f(x,y) = (0 \oplus y) + (1 \oplus y) + (2 \oplus y) + (3 \oplus y) + .. + ((x - 1) \oplus y) $$ So the whole rectangle would be that function from 0 to y - 1 for the y value.

**So my question is: Is there a way where I can simplify a function like that to gain efficiency ?**

# Answer
> 4 votes
Yes, there are ways to improve the efficiency greatly.

---

Let ${}\_k{i}$ be the $k$-th digit of $i$ in binary representation, i.e., it is 0 if $\lfloor i/2^k\rfloor$ is even and 1 otherwise. For example, since $19=(10011)\_2$, $\_019=1$, $\_119=1$, $\_219=0$, $\_319=0$, $\_419=1$. In most programming languages, ${}\_k{i}$ can be computed as $(i\text{\>\>}k)\\%2$.

Let us apply the power of summand splitting and rearrangement to inspect the contribution to the sum by the $k$-th digits in isolation.

$$\begin{aligned} \text{total sum} &=\sum\_{\text{ row } i\\,}\sum\_{\text{ column }j\\,} i \oplus j\\ &=\sum\_{\text{ row } i\\,}\sum\_{\text{ column }j\\,} \sum\_{0\le k\lt u} ({}\_k{i}\oplus {}\_k{j})\cdot 2^k\\ &=\sum\_{0\le k\lt u} 2^k\sum\_{\text{ row } i\\,}\sum\_{\text{ column }j\\,} {}\_k{i}\oplus {}\_k{j}\\ &=\sum\_{0\le k\lt u} 2^k\left(\\#\\{\text{row }i\mid {}\_k{i}=1\\}\cdot \\#\\{\text{column }j\mid {}\_k{j}=0\\}\right.\ + \\ &\quad\quad\left.\\#\\{\text{row }i\mid {}\_k{i}=0\\}\cdot \\#\\{\text{column }j\mid {}\_k{j}=1\\}\right) \end{aligned}$$

We can set $u=\lceil\log\_2\max(m+1, n+1)\rceil$ or any integer such that $n,m\lt 2^u$, where $n$ is the number of rows and $m$ is the number of columns. If $m$ and $n$ are ints or longs in Java or C#, $u=63$ could be a good choice.

Now the problem is shifted to compute $\\#\\{\text{row }i\mid {}\_k{i}=0\\}$ and the like ones. We have $$\begin{aligned} \\#\\{\text{row }i\mid {}\_k{i}=0\\} &=2^k\left\lfloor\frac {n-1}{2^{k+1}}\right\rfloor + \min\left(n-2^{k+1}\left\lfloor\frac{n-1}{2^{k+1}}\right\rfloor,\ 2^k\right)\\ \\#\\{\text{row }i\mid {}\_k{i}=1\\} &=2^k\left\lfloor\frac{n-1}{2^{k+1}}\right\rfloor + \max\left(0,\ n-2^{k+1}\left\lfloor\frac{n-1}{2^{k+1}}\right\rfloor -2^k\right) \end{aligned}$$ In terms of Java, they are, respectively,

```
((n-1)>>(k+1)<<k) + Math.min(1<<k, n - ((n-1)>>(k+1)<<(k+1))),
((n-1)>>(k+1)<<k) + Math.max(0, n - ((n - 1)>>(k+1)<<(k+1)) - (1<<k))

```

The time-complexity of the algorithm is about $O((\log n)^2)$

---
Tags: algorithms, complexity-theory, time-complexity, bit-manipulation, xor
---


# Question
Title: Why are most mutex implementations unfair?
My understanding is that most popular implementations of a mutex (e.g. std::mutex in C++) do not guarantee *fairness* -- that is, they do not guarantee that in instances of contention, the lock will be acquired by threads in the order that they called lock(). In fact, it is even possible (although hopefully uncommon) that in cases of high contention, some of the threads waiting to acquire the mutex might *never* acquire it.

This seems like an unhelpful behavior to me -- it seems to me that a fair mutex would yield behavior more in line with what a programmer would want/expect.

The reason given for why mutexes are typically not implemented to be fair is "performance", but I'd like to understand better what that means -- in particular, how does relaxing the mutex's fairness requirement improve performance? It seems like a "fair" mutex would be trivial to implement -- just have lock() append the calling thread to the tail of the mutex's linked list before putting the thread to sleep, and then have unlock() pop the next thread from the head of that same list and wake it up.

What mutex-implementation insight am I missing here, that would explain why it was considered worthwhile to sacrifice fairness for better performance?

# Answer
Jim Sawyer's answer points to one answer: When you have threads with differing priorities, "fair" behaviour would be incorrect. When you have multiple threads which could run, the highest priority thread is generally the one that should run.

However, there's a little-discussed secret of operating system implementation which you should be aware of, which is that occasionally operating systems run code as the user by hijacking a user thread. For safety reasons, most operating systems that do this only do it while a thread is blocked. When the operating system is done, the thread is re-suspended, and this typically has the effect of moving the thread to the back of the wait queue.

A typical example is a signal handler in Unix, an asynchronous system trap in VMS, or an asynchronous procedure call in Windows NT. These are all essentially the same thing: The operating system needs to notify the user process that some event happened, and this is is handled by running code in user space.

Many operating system services such as asynchronous I/O are often implemented on top of this facility.

Another example is if the process is under the control of a debugger. In that case, the debugging system may execute code as the user task for various reasons.
> 7 votes

# Answer
'Priority inversion' is one reason that fairness can be undesirable. A low priority process hits the locked mutex and sleeps. Then a higher priority process hits it, and also sleeps. When the mutex unlocks, which process should get the lock next?
> 4 votes

# Answer
A fair mutex will spend more of its lifetime locked than an unfair mutex, all else being equal. Because a thread releasing an unfair mutex can always just unlock it. But a thread releasing a fair mutex can only unlock it when the waiter queue is empty. Otherwise, the releasing thread must leave the mutex locked for the sake of the next thread, aka the first thread on the waiter queue, which is then dequeued and awoken. The mutex remains locked at least until the newly awoken thread is scheduled on a CPU, which could be a long time if there are many currently runnable threads.

And if the releasing thread promptly tries to re-acquire the same mutex, it must put itself in the rear of the waiter queue and go to sleep. This would not have happened if the thread didn't release the mutex to begin with. Therefore this incentivizes longer "more greedy" critical sections.
> 3 votes

---
Tags: concurrency, synchronization, threads
---