# Question
Title: Problem with understanding Multi-party security circuit for secure stable matching
I am reading the following paper: MPCircuits: Optimized Circuit Generation for Secure Multi-Party Computation

Paper Link

I have following question:

We have two groups shown in the circuit. Why we call it a multi-party circuit?

Paper provides a comparison of its multi-part technique with the old 2 part based technique:

> In secure stable matching, the match list is computed while keeping the preference lists private to their respective owners. This problem has been studied in the recent literature \[21\], \[22\] where the secure stable matching problem is reduced to a **two-party secure computation** scenario. Each individual XOR shares her preference list and sends it to two non-colluding servers who perform the secure computation. However, stable matching is inherently **a multi-party problem** and the assumption of two non-colluding servers may not be feasible in practice. To the best of our knowledge, we provide the first solution for multi-party secure stable matching.

The attached figure shows only how to input the preference list of group#1 and group#2. How can we perform n\*n computation using the figure? Somebody please guide me. Zulfi.

# Answer
Stable matching involves finding a matching between two groups of people (group 1, say males, and group 2, say females). Those are the groups that is referring to.
> 0 votes

---
Tags: reference-request, circuits, bipartite-matching, security
---


# Question
Title: Languages such that DFA requires $\Omega(c^k)$ states but NFA needs only $O(k)$ states?
Given an alphabet $\Sigma$, let $c=|\Sigma|$. Can a set of languages $\\{L\_k\\}$ be created, such that any DFA for $L\_k$ has $\Omega(c^k)$ states and a NFA for $L\_k$ exists with $O(k)$ states?

I'm having trouble creating an $L\_k$ such that any DFA for it has $\Omega(c^k)$ states. There are constructions that require $\Theta(2^k)$ states, but here $c$ is an arbitrary constant, so if $c\>2$ those constructions do not suffice.

---

Is the language of strings with a suffix of $s\_k, |s\_k|=k$ such a language? Following is a draft proof of that.

Proof by contradiction: let a DFA $\langle Q, \Sigma, \delta, q\_0, F\rangle$ have $|Q|\<c^{k-1}$. Let $a, b$ be strings of length $k$ and $a\_k=(s\_k)\_1\not=b\_k$

Let $q\_a$ and $q\_b$ denote $\delta(q\_0, a)$ and $\delta(q\_0, b)$, respectively.

There are two cases:

I. there are no $a,b$ such that $q\_a=q\_b$. Then each string corresponds to a different state, but there are $c^{k-1}$ such strings, therefore $|Q|\geq c^{k-1}$, which is not possilbe.

II. There are $a,b$ such that $q\_a=q\_b$. Then $\delta(q\_a, s\_2s\_3\ldots s\_k)=\delta(q\_b, s\_2s\_3\ldots s\_k)=q\_c$. $as\_2s\_3\ldots s\_k$ should be accepted and $bs\_2s\_3\ldots s\_k$ shouldn't, therefore $q\_c$ is both an accepting state and not an accepting state, which is not possible.

This seems to prove that any DFA for $L\_k$ has at least $c^{k-1}$ nodes, which is sufficient for $\Omega(c^k)$. If my proof is correct, the only task left is to prove that a NFA containing $O(k)$ nodes exists for $L\_k$.

The simplest way to do this is to create such a NFA, however I'm not sure how to do that. $O(k)$ suggests that $i$-th node should correspond to the state of "prefix of $s$ of length $i$ matches the suffix of the input string", however I do not follow how such a NFA can be created.

# Answer
The language $L\_k$ that you list doesn't work.

There is a straightforward NFA for the language $L\_k$ you list, with $k+1$ states. It guesses where the suffix starts, then checks that the suffix is equal to $s\_k$.

In particular, the NFA has states $0,1,\dots,k$, with transitions $0 \to 0$ on each symbol, transitions $i-1 \to i$ on the symbol that matches the $i$th character of $s\_k$, and $k$ being an accepting state.

It follows, using the subset construction, that there exists a DFA with $2^{k+1}$ states.

Consequently, that language does not meet your requirements, if $c\>2$.
> 1 votes

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


# Question
Title: How to find the shortest even length cycle in a bipartite graph?
If you have n vertices and m edges, how would you find the shortest cycle of a bipartite graph in O(n^2) time? To do it in O(nm) time, it is simply a BFS on every single vertex. I do not understand how you can do it just by going over every single vertex. I know you would have to stop at non-tree edges to do so, but how would you use this type of technique to guarantee this runtime and find the shortest cycle? Could anyone give me some sort of advice or help?

# Answer
> 0 votes
Run a BFS visit from each vertex of the graph. Stop each visit as soon as you encounter a cycle. To be more precise, the BFS visit classifies vertices as "visited", "discovered" (but not already visited), and "unknown". We stop the visit whenever we are visiting a vertex $v$ that has an edge towards a vertex that was already in the "discovered" state. In this way the BFS visit will examine only $O(n)$ vertices/edges. Return the shortest discovered cycle.

To see that this algorithm must work, let $2k$ be the length of the shortest cycle $C$, let $s$ be an arbitrary vertex in $C$, call $u$ and $v$ the two vertices at distance $k-1$ from $s$ in $C$, and let $w$ be the unique vertex at distance $k$ from $s$ in $C$.

Consider the BFS visit from $s$ and notice that if a cycle is encountered while visiting a vertex at level $\ell$ of the BFS tree, then its length is $2\ell+2$.

No cycle can be encountered while visiting levels $0$ though $k-2$ (as otherwise the shortest cycle would have length at most $2k-2$). Moreover, a cycle must be encountered at level $k-1$. This is obvious if the visit was halted before visiting both $u$ and $v$, therefore suppose that both $u$ and $v$ are visited, in this order (w.l.o.g.). When $u$ was visited, the state of $w$ changed from "unknown" to "discovered" (since $(u,w)$ is an edge of the graph). When $v$ was visited, the edge $(v,w)$ was encountered, and the visit was stopped since $w$ was already in the "discovered" state.

---
Tags: algorithms, graphs
---


# Question
Title: Loop-local variable in Cytron's SSA algorithm
I am trying to write a compiler that converts a simple imperative language to SSA form, but I am having trouble with loops. As an example, I have some code that looks like:

```
fun count() {
    i = 0;
    while(i < 10) {
        x = i + 1
        i = x;
    }
    return i;
}

```

I then convert it to a control flow graph that looks like this:

```
0 ->
    predecessors                = []
    successors                  = [1,2]
    dominators                  = [0]
    strict dominators           = []
    dominatees                  = [0,1,2]
    dominance frontier          = []
    inverse dominance frontier  = []
    immediate dominator         = none
    immediate dominatees        = [1,2]
    instructions                =
        r := 0
        i := 0
        if i >= 10 goto 2 else goto 1

1 ->
    predecessors                = [0,1]
    successors                  = [1,2]
    dominators                  = [0,1]
    strict dominators           = [0]
    dominatees                  = [1]
    dominance frontier          = [1,2]
    inverse dominance frontier  = [1]
    immediate dominator         = 0
    immediate dominatees        = []
    instructions                =
        x := i + 1
        i := x
        if i < 10 goto 1 else goto 2

2 ->
    predecessors                = [0,1]
    successors                  = []
    dominators                  = [0,2]
    strict dominators           = [0]
    dominatees                  = [2]
    dominance frontier          = []
    inverse dominance frontier  = [1]
    immediate dominator         = 0
    immediate dominatees        = []
    instructions                =
        r := i
        ret

```

The issue I'm running into is that when I use the algorithm for placing phi nodes described in section 5.1 of *Efficiently Computing Static Single Assignment Form and the Control Dependence Graph*, I get something like this:

```
0 ->
    predecessors                = []
    successors                  = [1,2]
    ...
    instructions                =
        r := 0
        i := 0
        if i >= 10 goto 2 else goto 1

1 ->
    predecessors                = [0,1]
    successors                  = [1,2]
    ...
    instructions                =
        x := phi(x, x)
        i := phi(i, i)
        x := i + 1
        i := x
        if i < 10 goto 1 else goto 2

2 ->
    predecessors                = [0,1]
    successors                  = []
    ...
    instructions                =
        x := phi(x, x)
        i := phi(i, i)
        r := i
        ret

```

I understand why a phi is necessary for `i` in basic block #1 and #2, but I don't understand why phis are necessary for `x`, and in fact they seem to break the renaming algorithm that follows (specifically, at one point where the renaming algorithm tries to pop off the `S("x")` stack, that stack is empty, because `x` was not assigned to in basic block #0). Did I somehow incorrectly implement this algorithm, or is there some subtlety I'm not understanding?

# Answer
Congratulations for implementing Cytron's algorithm! You are one of a select few who have attempted it.

Most compilers these days tend to use a much simplified algorithm which inserts and then removes redundant phi nodes. We will go through that later. Be aware that although it produces minimal SSA form on reducible flow graphs, it sometimes doesn't on irreducible flow graphs. But all in good time.

I'm going to go through a couple of related points, some of which you've probably already noticed, but I'm going to mention anyway to make this answer a bit more self-contained.

First off, the definition of $\mathit{HasAlready}$ in the paper is doesn't make a lot of sense. It is defined as follows:

> $\mathit{HasAlready}(\*)$ is an array of flags, one for each node, where $\mathit{HasAlready}(X)$ indicates whether a $\phi$-function for $V$ has already been inserted at $X$.

Already, we see a problem: Where's $V$ in this query? But then, in figure 11, we see this code:

> $\texttt{if}\\,\mathit{HasAlready}(X) \< \mathit{IterCount}$
>
> ...
>
> $\\,\\,\\,\\,\\,\\,\\,\\,\mathit{HasAlready}(X) \leftarrow \mathit{IterCount}$

So $\mathit{HasAlready}(X)$ should clearly be an integer, not a flag. Its value represents the highest-numbered variable that has had a $\phi$-function introduced for each basic block.

Secondly, if you are constructing SSA form using basic blocks, then Cytron's algorithm as published doesn't deal with multiple assignments to the same variable within a basic block, because the they don't need $\phi$-functions. The set of assignments to a variable $V$ (denoted $\mathcal{A}(V)$ in the paper) only refers to the *last* assignment in a basic block.

Now what you've identified is the dual of this: the only "uses" which matter are any that occur *before the first* assignment in a basic block. That also means that no potential reaching definition of a variable is "used" in a basic block if there are no uses before that first assignment in the block.

Now I've forgotten a lot of the details here, but that might explain the pop issue in the renaming algorithm: there isn't an assignment to `x` in basic block 1 as far as Cytron's algorithm is concerned.

OK, now that's out of the way, here's what most compilers tend to do: insert $\phi$-functions everywhere for everything (using variable scopes so we don't go completely crazy), and then remove the redundant ones.

In your case, let's suppose that `x` is declared outside the loop and initialised with 0. We rename every assignment, then insert a $\phi$ at the start of every block (except the start block) with the incoming values from the last assignment in all predecessors:

```
0 ->
    r_0 := 0
    i_0 := 0
    x_0 := 0
    if i_0 >= 10 goto 2 else goto 1

1 ->
    i_1 := Phi(i_0, i_2)
    x_1 := Phi(x_0, x_2)
    r_1 := Phi(r_0, r_1)
    x_2 := i_1 + 1
    i_2 := x_2
    if i_2 < 10 goto 1 else goto 2

2 ->
    i_3 := Phi(i_0, i_2)
    x_3 := Phi(x_0, x_2)
    r_3 := Phi(r_0, r_1)
    r := i_3
    ret

```

This is already valid SSA form, it is just not *minimal* SSA form.

Now we iteratively apply two transformations:

1. If there is a Phi assignmment whose value is unused, remove it.
2. If there is a Phi assignment whose arguments are the returned value of the assignment and one other value, remove it and rename the assigned variable to that other value.

An example of the first rule is in block 2, with `r_3`. That is unused, so we remove it.

An example of the second rule is in block 1, with `r_1`. Here, `r_1` can be replaced with `r_0` everywhere. In general, you might find something like this:

```
v_1 := Phi(v_1, v_2, v_2, v_1, v_2)

```

In that case, remove the Phi and replace `v_1` with `v_2` everywhere.

It should be clear why these two simplifications are valid transformations. What's interesting is that if you apply these two rules until none apply any more, you get minimal SSA form if the flow graph is reducible.

In your case, you get this:

```
0 ->
    r_0 := 0
    i_0 := 0
    x_0 := 0
    if i_0 >= 10 goto 2 else goto 1

1 ->
    i_1 := Phi(i_0, i_2)
    x_2 := i_1 + 1
    i_2 := x_2
    if i_2 < 10 goto 1 else goto 2

2 ->
    i_3 := Phi(i_0, i_2)
    r := i_3
    ret

```

Now you can see that all of the Phi nodes for `x` have been eliminated, as we would hope. Also, `x_0` and `r_0` are dead definitions, but they can be removed later.

Just as a last comment, the very notion of a "basic block" isn't necessarily that important in modern compilers any more, after you have resolved scopes and before you generate assembly language.

The "sea of nodes" representation is a case in point. Many modern IRs tend to think in terms of sequencing constraints instead of linear blocks of code. That way, you don't have to deal with basic blocks specially as in this example.

If you think of each instruction as its own "basic block", then Cytron's algorithm should work perfectly!
> 4 votes

---
Tags: compilers, static-analysis
---


# Question
Title: Finding The Inverse of The Modulo Operation
I created an algorithm to convert a hexadecimal digit into an alphanumeric string, but now I want to create the inverse of this algorithm. The algorithm, in short, is as follows:

> hexadecimal digit % length of alphanumeric character array = index in alphanumeric character array

For example, the algorithm takes hex digit `4e` (`78` in decimal), mods it with the size of an alphanumeric character array (size: `62`), and returns decimal number `16`, which is a `G`. The alphanumeric character array in this example is structured like the following: (0-9, A-Z, a-z).

> In short this example is written as: `(4e)78 % 62 = 16(G)`

The inverse of this algorithm is what I hope to achieve and from various tests, it seems multiple results can occur, but my ultimate goal is to end up with a reversible algorithm, where, for example, hexadecimal digit `4e` gets converted to letter `G` then back again to `4e` when put through the inverse algorithm. From the example, I developed a possible description of the inverse algorithm:

> Suppose we have a modular equation. Let `x` be the dividend, `y` be the divisor, and `r` be the remainder. `r` and `y` are given where `r=16` and `y=62`. Find an `x` such that `x % y = r` or `x % 62 = 16`.

The solution that I tried: Bruteforce the dividend

The dividend will never be out of the closed interval `[0, 255]` since a pair of hexadecimal numbers can have a maximum value of `ff`, which is `255` in decimal. Thus, if we test x's against the modular equation until we get an equal remainder, we can derive the dividend.

However, this solution will result in multiple possible `x` values due to the modulo operation causing a wrap-around effect in the alphanumeric array, which means multiple values can cause the equation to hold true. In the case of the provided example, the proposed solution results in the following dividends: `16`, `78`, `140`, and `202`. The second dividend is the correct one and the one that results in the algorithms being reversible. However, the issue is finding it, since the correct one isn't directly known at the time of running the inverse algorithm.

Any help in devising either a solution to my proposed method or a different one would be greatly appreciated. Thanks.

# Answer
I ended up solving my issue, but not in the way I expected. The solution involves the inherent halving of the output string. Using this, one can simply calculate the quotient of dividing `x` by `y` and using that as the second alphanumeric character, forming a pair. In the given example, the resulting `G` would become `G1` because the modular arithmetic involved looping over the alphanumeric character array once.

The algorithm is now as follows: `x % y = r + (x / y)`, which is easily reversible by bruteforcing the possible dividends and simply selecting the correct one using the second character in the alphanumeric pair. Thus, this modified algorithm is now reversible and has been proven to work with the example given in the original question.
> 0 votes

---
Tags: modular-arithmetic
---


# Question
Title: Algorithms (optimization problem): find collection of objects whose permutation satisfies criteria
I'm putting together a personal list of recipes that I enjoy, and would like to construct an algorithm that parses this recipe database and automatically builds me a meal plan for the week.

For N number of meals per day, find permutation of recipes that comes the closest to satisfying these conditions:

* Sum of meal calories ~= my defined daily calorie limit
* Average recipe macros\* (weighted by recipe calories) ~= my desired macros (i.e. (30/40/30))

(\*: Macros are the ratio of carbs/protein/fats in a meal, and are usually found in a tuple form: (CC/PP/FF))

Each recipe can be assumed to be in the form:

```
'name': {
   'calories': a,
   'protein': b,
   'carbs': c,
   'fats': d
}

```

In other words:

```
Inputs: n_meals, max_cals, (cc,pp,ff) # <- macros
Output: [recipe_1, recipe_2, ..., recipe_n]

```

I have no formal training in algorithms, so I'm not really sure where to start. The naive approach would be to take every permutation of recipes in the list and use the permutation which satisfies the criterion the closest.

This is definitely a multi-dimensional optimization problem but that's the depth of my knowledge. Perhaps something like a breadth-first search algorithm would be most appropriate?

Thanks all.

# Answer
> 1 votes
You could formulate this as an instance of integer linear programming. You use zero-or-one variables $x\_{ij}$, with the intended meaning that $x\_{ij}=1$ if you assign recipe $i$ on day $j$. Then your restrictions can be expressed as linear inequalities (e.g., $\sum\_i x\_{ij}=3$ means you eat 3 meals per day, $\sum\_j x\_{ij}=1$ means that you eat each recipe once). You introduce a variable $y$ that expresses how far off from the goals you're allowed to be; then the restrictions on calories and macronutrients are also linear. Finally, you feed this to an off-the-shelf ILP solver to minimize $y$.

Or, assuming you have three meals per day, you could generate all possible ways to pick a single day's menu that meets the calory requirement for that day, then exhaustively explore all possible ways to combine those daily menus into a week's worth of menus.

---
Tags: algorithms, optimization, search-algorithms, shortest-path
---


# Question
Title: Why does a software video encoder create higher quality output than a hardware video encoder
It is said commonly that a software video encoder has creates higher quality output than hardware encoder. Higher quality here means higher picture quality at a given bit rate.

Hardware encoders are commonly for realtime usage and some are for mobile applications, then there are trade offs in hardware encoders to get realtime performance and have lower power.

Commonly what exactly is the trade off (e.g. which encoding algorithm parameter) in hardware encoder that makes it have lower quality than a software encoder?

Will simply changing some encoding parameter (and as a result more chip area and power consumption) make a hardware encoder have the same quality as a software encoder?

H.264/H.265 are considered.

# Answer
> 4 votes
There is no reason in principle why hardware would have to produce worse results than software. But there are two problems:

1. Better quality requires better algorithms, and better algorithms in hardware usually take more circuits and cost more money, while higher quality in software can be almost free.
2. Real-time encoding must finish in given time. If you run a video conference you have one second to encode one second of video. Even if you knew how to produce better quality in more time, you are not allowed to. But if you use an offline encoder, that can give you an option to encode an hour of video in six hours with low quality, in twelve hours with medium quality, or in 36 hours with highest quality.

And of course you can have the latest and best quality software encoder at any time. If your hardware is three years old and not very good, replacing it with much better new hardware is inconvenient and costly.

# Answer
> 1 votes
The premise is false. Any encoder can be implemented in either hardware or software. There is no fundamental reason that hardware encoders need to be lower quality than software encoders.

---
Tags: video
---


title: Is this an example of Tail Recursion

text:
# Question
Title: Is this an example of Tail Recursion
As I have read in this answer: What is tail recursion? tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call.

Here after the recursive call we just assign the result to another variable. Can we consider this code as tail recursion?

```
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:

        if not head or not head.next:
            return head

        head_ = head
        head_next = head.next
        head_next_next = head.next.next

        head_next.next = head_

        head_.next = self.swapPairs(head_next_next)

        return head_next

```

# Answer
It is considered tail recursion if there is no computation between the recursive call and the return.

In your example there is no computation, only an assignment.

It would depend on the actual compiler if code for an optimised tail recursive call was made at this point, but yes some compilers could treat this as a tail recursive call.
> 2 votes

---
Tags: recursion
---


# Question
Title: A query regarding the hierarchy of monotone Complexity Classes
I have recently started studying the monotone complexity classes. There doesn't seem to be a single/clear containment hierarchy or single source regarding the same. Can we create one?

The classes are namely: $mTC^0, mNC^0, mNC, mAL, mcoNL, mL, mNL, mP, mNP, mP/Poly$. (I think that covers most)

The relationships I am aware of:

1. $mTC^0 \subset mNC^0 \subset mL$
2. $mL \subset mNL$
3. $(mP = mAL) \subset mNP$
4. $mNC \neq mP$

My queries about containment relationship b/w:

1. $mNC$ vs. $mP$
2. $mP/Poly$ vs. $mP$

Please feel free to add Open Questions and other known relationships b/w these classes as you see fit.

# Answer
> 2 votes
Raz and McKenzie, Separation of the monotone NC hierarchy, showed that the monotone NC hierarchy is strict, and separated it from monotone P. In all of these separations, the upper bound holds for the uniform class while the lower bound holds even for the non-uniform class (so by monotone P, they really mean monotone P/poly).

Monotone P is easy to separate from monotone P/poly since the latter contains uncomputable functions. For example, the language $\\{w : |w| \in K\\}$ is in monotone P/poly for any $K \subseteq \mathbb N$, but isn't in monotone P if $K$ is uncomputable.

(By the way, there are several reasonable ways to define monotone P, and I'm not sure they are all equivalent. However, all of them should satisfy what I wrote in the preceding paragraph.)

---
Tags: complexity-theory
---


# Question
Title: Definition and example of search problem
I searched the pages a lot about the search problem but didn't understand much, so please make it clearer for me.

WIKIPEDIA:

> In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation. If R is a binary relation such that field(R) ⊆ Γ+ and T is a Turing machine, then T calculates R if:
>
> If x is such that there is some y such that R(x, y) then T accepts x with output z such that R(x, z) (there may be multiple y, and T need only find one of them) If x is such that there is no y such that R(x, y) then T rejects x

If anyone can explain it to me easily and give a few examples, it will help me a lot.

# Answer
Here is an example of a search problem:

> Given a CNF $\varphi$, find a satisfying assignment $x$.

Every satisfying assignment would do. A machine solves this problem if on input $\varphi$:

* If $\varphi$ is satisfiable, then the machine outputs a satisfying assignment.
* If $\varphi$ is unsatisfiable, then the machine outputs "unsatisfiable".

An important class of search problems are those that always have solutions. Here is a canonical example:

> Given an unsatisfiable CNF $\varphi$ and an assignment $x$, find a clause not satisfied by $x$.

Note that since $\varphi$ is unsatisfiable, for every assignment there is a clause which $x$ doesn't satisfy. A machine solves this problem if given $\varphi$ and $x$, it outputs a clause of $\varphi$ unsatisfied by $x$.
> 1 votes

---
Tags: search-algorithms, search-problem
---


# Question
Title: Turing machines moving left at least once
> Is the following language decidable? $$ L = \\{ \langle M,w \rangle \mid \text{$M$ moves its head left at least once when run on $w$}\\}. $$

I feel like this is a decidable language. But I don't know the algorithm to prove that it is decidable. Any help would be appreciated.

# Answer
Let's assume for simplicity that at each step, the head moves either left or right (but doesn't stay in place).

Suppose that $M$ never moves its head left when run on $w$. After the machine traverses the length of $w$, it reaches a blank cell, and from this point on, will always fall on a blank cell. Therefore the only information that changes from step to step is the current state of the machine. After at most $|Q|$ steps (where $Q$ is the set of states), the machine will either halt or repeat a state, in which case it enters an infinite loop.

This gives a simple algorithm for deciding your language, that I'll let you spell out.

If the head is also allowed to stay put, the argument becomes a bit more complicated, but the conclusion is identical.
> 1 votes

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


# Question
Title: Is the language of palindromes context-free?
Is the language $\\{ w=w^R \mid w \in \\{0,1\\}^\* \\}$ a context-free language?

I am confused in deciding whether the language is context-free or not, that is one of my problems, I do a pumping lemma proof and what I get is that it is not a context-free language, but I want to make sure again.

# Answer
> 2 votes
The language of palindromes is one of the standard examples of a non-regular context-free language. It is generated by the context-free grammar $$ S \to 0S0 \mid 1S1 \mid 0 \mid 1 \mid \epsilon $$

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


# Question
Title: Maximum coverage 1/2-approximation algorithm: why does the central lemma hold?
I am looking for an approximation algorithm for the Maximum Coverage problem and a proof of its approximation ratio. As approximation algorithm I use the greedy algorithm which chooses the set that maximizes the number of new elements at each turn (same as the one proposed in the Wikipedia article). However it is not as trivial to reach a result about the approximation ratio of this greedy approach.

So I did some research and found these lecture notes that describe some useful concepts for this problem and also proves a lemma. Now let me iterate what is said in these lecture notes before we get to the lemma.

---

**Maximum Coverage problem** Given a set of sets $U=\\{S\_{1},\dots,S\_{m}\\}$ and a number $k$, choose (at most) $k$ sets such that the union of the sets is maximized, or $\max\_{I\subseteq U}\vert \cup\_{j\in I}S\_{j}\vert$ for some index set $I$. The sets may have elements in common. Let $\mathbf{OPT}$ denote the optimal solution, i.e. numbers at most covered by $k$ sets, let $a\_{i}$ denote the number of newly covered elements in the $i$:th iteration by the greedy algorithm, let $b\_{i}$ be the total number of covered elements in the $i$:th iteration, i.e. $b\_{i}=\sum\_{j=1}^{i}a\_{i}$, and let $c\_{i}$ be the number of uncovered elements at the $i$:th iteration, i.e. $c\_{i}=\mathbf{OPT}-b\_{i}$. Moreover, $a\_{0}=0$, $b\_{0}=0$ and $c\_{0}=\mathbf{OPT}$.

**Lemma**: The number of newly covered elements at the $(i+1)$:th iteration (i.e. $a\_{i+1}$) is always greater than or equal to $(1/k)\cdot$*number of uncovered elements at the $i$:th iteration*, or $a\_{i+1}\geq c\_{i}/k$.

**Proof**: Optimal solution covers $\mathbf{OPT}$ elements at $k$ iterations. That means, at each iteration there should be some sets in $U$ whose size is greater than or equal to the $(1/k)$ of the remaining uncovered elements, i.e., $c\_{i}/k$. Otherwise, it was impossible to cover $\mathbf{OPT}$ many elements at $k$ steps by the optimal solution. Since the approximation algorithm is greedy, i.e., choosing always the set covering maximum number of uncovered elements,the chosen set at each iteration should be at least the $(1/k)$ of the remaining uncovered elements. That is, $a\_{i+1}\geq c\_{i}/k$.

---

I do not understand this proof, why does it have to be the case there exist such sets? And why is the size of the set important, is it not the number of new elements the set contributes that is important? It all seems arbitrary to me to choose that there is a lower bound of $(1/k)\cdot c\_{i}$ for $a\_{i+1}$. I am also confused about how the optimal solution is related to the greedy solution, what is the rationale behind the statement that if this is not true then it would have been *impossible* for the optimal solution to be $\mathbf{OPT}$ in $k$ iterations? Since I have trouble understanding at all, is there any *other* way to explain this lemma?

# Answer
> 2 votes
Let $S\_{O\_1},\ldots,S\_{O\_k}$ be an optimal solution, and let $O = S\_{O\_1} \cup \cdots \cup S\_{O\_k}$.

At the $i$'th iteration, suppose that the elements covered by the sets chosen the algorithm form the set $T$. Let $S'\_{O\_i} = S\_{O\_i} \setminus T$ and $O' = O \setminus T$, that is, we have removed from the optimal solution all elements already covered. Since $$ |O'| = |S'\_{O\_1} \cup \cdots \cup S'\_{O\_k}| \leq |S'\_{O\_1}| + \cdots + |S'\_{O\_k}| \leq k \max\_{i=1}^k |S'\_{O\_i}|, $$ we see that among the sets $S\_{O\_1},\ldots,S\_{O\_k}$, at least one (the one maximizing $\max\_i |S'\_{O\_i}|$ covers at least $|O'|/k$ uncovered elements.

The greedy algorithm chooses a set covering at least as many uncovered elements. This allows us to obtain a lower bound on its approximation ratio, as follows. Let $T\_i$ be the union of the sets chosen in the first $i$ steps of the greedy algorithm. The starting point is $T\_0 = \emptyset$. At step $i$, the argument above shows that we cover at least $|O'|/k$ new elements. Since $|O'| = |O \setminus T\_{i-1}| \geq |O| - |T\_{i-1}|$, this shows that $$ |T\_i| \geq |T\_{i-1}| + (|O| - |T\_{i-1}|)/k = \left(1 - \frac{1}{k}\right) |T\_{i-1}| + \frac{|O|}{k}. $$ In particular, $$ \begin{align} &|T\_1| \geq \frac{|O|}{k} \\ &|T\_2| \geq \frac{|O|}{k} + \left(1 - \frac{1}{k}\right) \frac{|O|}{k} \\ &|T\_3| \geq \frac{|O|}{k} + \left(1 - \frac{1}{k}\right) \frac{|O|}{k} + \left(1 - \frac{1}{k}\right)^2 \frac{|O|}{k} \end{align} $$ and so on. At the end of the algorithm we get a set $T\_k$ satisfying $$ \begin{align} |T\_k| &\geq \frac{|O|}{k} \left\[1 + \left(1 - \frac{1}{k}\right) + \cdots + \left(1 - \frac{1}{k}\right)^{k-1}\right\] \\ &= \frac{|O|}{k} \frac{1 - \left(1 - \frac{1}{k}\right)^k}{1 - \left(1 - \frac{1}{k}\right)} \\ &= \left(1 - \left(1 - \frac{1}{k}\right)^k\right) |O|. \end{align} $$ Now it's time for some calculus: $$ \ln \left(1 - \frac{1}{k}\right) = - \frac{1}{k} - \frac{1}{2k^2} - \cdots \leq -\frac{1}{k}, $$ and so $$ \left(1 - \frac{1}{k}\right)^k = \exp\left\[k\ln \left(1 - \frac{1}{k}\right)\right\] \leq \exp (-1) = 1/e, $$ implying that $$ |T\_k| \geq \left(1 - \frac{1}{e}\right) |O|. $$ In other words, the greedy algorithm gives a $(1-1/e)$-approximation (this is better than your claimed $1/2$). It turns out that $1-1/e$ is tight for the greedy algorithm, and moreover, then $1-1/e$ cannot be improved by a polynomial time algorithm unless $\mathsf{P} = \mathsf{NP}$ (and unconditionally in the value oracle model).

---
Tags: np-complete, approximation, set-cover
---


# Question
Title: Solving $UCYCLE$ in logspace - two possible approaches ? Why can't we one of them use to solve connectivity?
$$UCYLE = \mathcal \\{ \<G\> ~:~ G \text{ is an undirected graph that contains a simple cycle}\\}.$$
There are two possible approaches to this exercise: Solving cycle in undirected graph in log space?

https://stackoverflow.com/questions/29640543/solving-cycle-in-undirected-graph-in-log-space

These two solutions are different. The instresting solution is second one (on stackoverflow). In this case we generally implement DFS in logspace. I can see that it does work (using DFS). However the question is:
**Why we can't use this DFS algorithm to solve USTCON problem ?**

However, I can see that we can't easily use this DFS to solve bipartity problem. It is not easy to count number of nodes in cycle.

**Edit**
Modified algorithm from stackoverflow (mentioned link) which should solve ustcon problem:

```
    for v_j in neighbours(s)
        current, prev = v_j, s
        repeat
            idx = neighbours(current).index(v_j)
            idx = (idx + 1) % len(neighbours(current))
            current, prev = neighbours(current)[idx], current
            if current = t then return connection between s and t
        until current adjacent to s
return no_connection between s and t

```

# Answer
> 1 votes
Your algorithm is from the paper Problems complete for deterministic logspace by Cook and McKenzie, where it is used to perform DFS on trees, as well as for related problems such as cycle detection. Presumably it doesn't work on graphs with cycles.

# Answer
> 1 votes
This algorithm is not DFS. One of the problems it can solve is checking if a graph is cyclic, but it doesn't mean it is possible to traverse every cycle or path in graph (unless it's a tree), imagine graph made of triangle with squares on the sides - the algorithm will not detect the three-vertex cycle whatever (v,e) we start with. It will not detect the path between two vertices, that we can add in the middles of two sides of the triangle. Therefore UCYCLE problem can be solved in logspace, but BIPARTITE and especially USTCON require a different approach.

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


title: Job Scheduling decision problem

text:
# Question
Title: Job Scheduling decision problem
I would like to know how to prove that the Job Scheduling decision problem is strongly NP-complete using 3-partition.

Input: A set of $n$ tasks of length $t\_1, t\_2, \ldots t\_n \in \mathbb N$ and $k$ processors.

A feasible solution is a function $\alpha: \\{1, \ldots ,n\\} \rightarrow \\{1, \ldots k\\}$ which assigns each task to a processor.

The usage time $u\_j$ of a processor $j$ is the sum of the lengths of all the tasks assigned to it, that is to say that $u\_j = \sum\_{i: \alpha(i)=j}t\_i$.

We try to minimize $\max\_j u\_j$, that is to say the time of use of the most used processor.

In the JS$\_{dec}$ decision problem corresponding to JS, the instance is accompanied by a target value $T$ and we are trying to find out if there is a solution where all the processors have a usage time limited by $T$.

# Answer
Let $X = \\{x\_1, \dots, x\_n\\}$ be an instance of $3$ partition where $n$ is a multiple of $3$ and each $x\_i$ is strictly between $\frac{3}{4n}\sum\_{i=1}^n x\_i$ and $\frac{3}{2n}\sum\_{i=1}^n x\_i$. The problem remains NP-hard even with this restriction.

The instance of the job scheduling decision problem has $n$ jobs, $t\_i = x\_i$, $k=\frac{n}{3}$, and $T=\frac{3}{n}\sum\_{i=1}^n x\_i$.

If the 3-partition instance is a "yes" instance, then there is a partition of $X$ into $\frac{n}{3}$ sets $X\_1, X\_2, \dots, X\_{\frac{n}{3}}$ such that, for each $j=1, \dots, \frac{n}{3}$, $\sum\_{x \in X\_j} x = \frac{3}{n}\sum\_{i=1}^n x\_i$. Let $\alpha(i)$ be the index $j$ of the unique set $X\_j$ containing $x\_i$. Then $\alpha$ is an assignment for the job scheduling instance in which, for each $j=1,\dots,\frac{n}{3}$, $u\_j = \sum\_{i : \alpha(i)=j} = \sum\_{x \in X\_j} x = \frac{3}{n}\sum\_{i=1}^n x\_i = T$. This shows that the job assignment instance is a "yes" instance.

If the job scheduling instance is a "yes" instance, then let $\alpha$ be a corresponding assignment. For each $j=1,\dots,\frac{n}{3}$:

* $|\\{i : \alpha(i)=j\\}| \le 3$, as otherwise $u\_i \> 4 \cdot \frac{3}{4n}\sum\_{i=1}^n x\_i = T$.
* $|\\{i : \alpha(i)=j\\}| \ge 3$, as otherwise $u\_i \< 2 \cdot \frac{3}{2n}\sum\_{i=1}^n x\_i = T$, implying that $\max\_{j' \neq j} u\_j \ge \frac{\sum\_{i=1}^n x\_i - u\_i}{\frac{n}{3}-1} \> \frac{\sum\_{i=1}^n x\_i - T}{\frac{n}{3}-1} = \frac{\frac{n-3}{n}\sum\_{i=1}^n x\_i}{\frac{n-3}{3}} = \frac{3}{n}\sum\_{i=1}^n x\_i = T$.

As a consequence, the sets $X\_1, \dots, X\_{\frac{n}{3}}$, where $X\_ j = \\{x\_i : \alpha(i)=j\\}$, contain $3$ elements each and form a partition of $X$. Moreover, $\sum\_{x \in X\_j} x = u\_j \le T = \frac{3}{n}\sum\_{i=1}^n x\_i$ and an argument similar to the one above shows that $\sum\_{x \in X\_j} x \ge \frac{3}{n}\sum\_{i=1}^n x\_i$. This proves that $\sum\_{x \in X\_j} x = \frac{3}{n}\sum\_{i=1}^n x\_i$ and hence that the $3$ partition instance is a "yes" instance.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Derivation of product type eliminator in type theory
In HoTT book, section 1.5 (Product Types) in order to define the eliminators for the product type it assumes a function of type $g:A \rightarrow B \rightarrow C$ and then goes on to define the eliminator rule ,saying that we can define a function $f:A \times B \rightarrow C $ for any such g by:

$f((a, b)) :\equiv g (a) (b)$.

Then it states that

> Note that in set theory, we would justify the above definition of $f$ by the fact that every element of $A \times B$ is an ordered pair, so that it suffices to define $f$ on such pairs. By contrast, type theory reverses the situation: we assume that a function on $A \times B$ is well-defined as soon as we specify its values on pairs, and from this we will be able to ***prove*** that every element of $A \times B$ is a pair.

Would you please explain in further detail what the above paragraph is trying to state?

# Answer
> 0 votes
What is meant here, is that you can construct an identification $x=(\mathsf{pr}\_1(x),\mathsf{pr}\_2(x))$ for any $x:A\times B$. In other words, you can show $$\Pi\_{(x:A\times B)}x=(\mathsf{pr}\_1(x),\mathsf{pr}\_2(x)).$$ In order to do this, we use the *induction principle* of $A\times B$. By the induction principle it suffices to show that $$\Pi\_{(a:A)}\Pi\_{(b:B)}(a,b)=(\mathsf{pr}\_1(a,b),\mathsf{pr}\_2(a,b)).$$ Now you simply observe that by the definition of the projection maps, there are judgmental equalities $\mathsf{pr}\_1(a,b)\equiv a$ and $\mathsf{pr}\_2(a,b)\equiv b$. Therefore, the above type reduces to $$\Pi\_{(a:A)}\Pi\_{(b:B)}(a,b)=(a,b),$$ which can be proved by reflexivity.

We conclude that every element of $A\times B$ can be *identified with* a pair, namely the pair of its own projections. The same is true for $\Sigma\_{(x:A)}B(x)$.

---
Tags: type-theory, homotopy-type-theory
---


# Question
Title: Algorithm: turining a fraction into a decimal expansion string
I already asked this question over on Mathematics and got the suggestion to ask it here.

So I'm basically implementing a number type that can represent all fractions and was working on an algorithm to compute the decimal expansion for said fractions.

Let's say we have the reduced fraction $\frac{n}{m}$. For converting it into its decimal expansion I now have two algorithms.

The first algorithm is simply long division to calculate the decimal expansion up to a given number of decimal places.

The second is:

Let $a \in \\{1,2,\ldots\\}$ be a specifier for accuracy.

Calculate: $$ \begin{align} p &= \lceil \log\_{10}(m) \rceil + a \\\\ f &= \lfloor \frac{10^p}{m} \rfloor \\\\ v &= n \cdot f \end{align} $$ Then in $v$ insert the decimal comma at the correct place or add `0.` with leading zeros.

Which works well but it is hard to control the accuracy with $a$. For example if I have the fraction $\dfrac{884279719003555}{281474976710656} \approx \pi$ then I get:

```
 a | dec. exp.
---|--------------------------------
     v acc 0
 1 | 3.0949790165124425
       v acc 1
 2 | 3.13919300246262025
        v acc 1
 3 | 3.14096156190062736
             v acc 7
 8 | 3.14159264580768862709685
              v acc 8
 9 | 3.14159265288192637912529
                  v acc 12
10 | 3.141592653589350154328134
                  v acc 12
11 | 3.141592653589350154328134
                  v acc 12
12 | 3.141592653589350154328134
                     v acc 15
f  = 3.1415926535897931159979634...

pi = 3.1415926535897932384626433...

```

So its seems I can control with $a$ that at least $a-1$ decimal places are correct.

But I'm not sure if this will always be the case.

Also, I benchmarked both algorithms, and the second is more than 5 times faster. So I really want it to be controllable.

| Method | Mean | Error | StdDev |
| --- | --- | --- | --- |
| first | 4,929.2 ns | 24.34 ns | 20.33 ns |
| second | 848.8 ns | 4.00 ns | 3.54 ns |

So my question basically is: does anybody have suggestions on improving the algorithm or maybe another algorithm that does the job even better (a.i. fast)?

# Answer
> 4 votes
All we need is a function $f$ that gives the whole part of a fraction. One can define this one using integer division:

$$f(a, b) = \lfloor a / b\rfloor$$

Finally let's assume we have routine $g(a, b)$ that reduces a fraction to its simplest form. This can be done with the Euclidean algorithm.

Let's first take the integer part of a fraction out using $f$, and reduce our fraction using $g$, giving us $\frac{a}{b} \< 1$. Then we can repeatedly ask for the next decimal $d$ and continue with $10\cdot \frac{a}{b} - d$:

1. $d := f(10a, b)$
2. $a, b := g(10a - b\cdot d, b)$

This algorithm will perfectly give you all digits ad infinitum, and $g$ makes sure the numbers stay small and manageable.

---
Tags: algorithms
---


# Question
Title: How do you calculate the training error and validation error of a linear regression model?
I have a linear regression model that I've implemented using Gradient Descent and my cost function is a Sum of Squares Error function. I've split my full dataset into three datasets, a training set, a validation set, and a testing set. I am not sure how to calculate the training error and validation error (and the difference between the two).

Is the training error the Residual Sum of Squares error calculated using the training dataset? Is the validation error the Residual Sum of Squares error calculated using the validation dataset? What is the test set for exactly (I've learned the model using the training set, from the textbooks I've read I think this is the set to use to learn the model)?

Any help in clearing up these points is much appreciated.

# Answer
> 0 votes
Yes. Yes. The test set is used to get an unbiased measure of the performance of your model. This is explained in many sources, better than I can explain here; I won't try to repeat them. See, e.g., https://en.wikipedia.org/wiki/Training,\_validation,\_and\_test\_sets, https://stats.stackexchange.com/a/104750/2921, or standard textbooks.

---
Tags: machine-learning
---


title: Polynomially related encodings

text:
# Question
Title: Polynomially related encodings
CLRS states that:

> For some set $I$ of problem instances, we say that two encodings $e\_1$ and $e\_2$ are polynomially related if there exist two polynomial-time computable functions $f\_{12}$ and $f\_{21}$ such that for any $i \in I$, we have $f\_{12}(e\_1(i)) = e\_2(i)$ and $f\_{21}(e\_2(i)) = e\_1(i)$.

My understanding of the above statement says that, for example, if we have *base 2* encoding of a problem, we can convert it to *base 3* encoding of the problem in polynomial time and vice versa.

I wanted to confirm from the respected community if my understanding is correct, or am I having a flaw in my understanding?

Also, If I am correct, CLRS states one more thing: "unary encodings are expensive". I want to know, what do the authors mean by that? Do they mean to say that representing 8 by 11111111 is costlier than representing 8 by 1000?

# Answer
> 3 votes
Yes, it's correct that you can convert between base-2 and base-3 representation (in either direction) in polynomial time. Thus, that would be a good example of two encodings that are polynomially related.

You can't convert from binary (base-2) to unary representation in polynomial time; it causes an exponential increase in the size of the instance. That's probably what is meant by "expensive".

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


title: Is P contained in NP-hard?

text:
# Question
Title: Is P contained in NP-hard?
I'm studying complexity classes and the diagram in NP-Hardness article is confusing to me.

NP-hard has all problems that can be reduced in polynomial time from a problem in NP to them. P is contained in NP. Then it is possible to reduce a problem X in P to a problem Y in NP-hard? This does not add up to me in the scenario P!=NP.

What am I missing here? Is P contained in NP-hard?

# Answer
> NP-hard has all problems that can be reduced in polynomial time from an NP to them.

Not quite: NP-hard consists of all problems to which **every** NP problem reduces.

Suppose $X\in \mathsf{P}$. If $\mathsf{P}\not=\mathsf{NP}$, then $SAT$ (for example) is **not** reducible to $X$. So $X$ is not $\mathsf{NP}$-hard: there are some problems in $\mathsf{NP}$ which do not reduce to $X$.

Note that the class of problems to which *some* problem in $\mathsf{NP}$ reduces is ... the class of all problems whatsoever! This is because (as you observe) once we discard the "edge cases" $\emptyset$ and $\mathbb{N}$, every problem in $\mathsf{P}$ is also in $\mathsf{NP}$, and problems in $\mathsf{P}$ are trivially reducible$^1$ to everything.

---

$^1$With respect to *polynomial-time many-one reducibility*. Change the reducibility, and you potentially change the situation. E.g. $\mathsf{P}$ **is** $\mathsf{NP}$-hard *with respect to exponential-time many-one reducibility*, since with respect to this reducibility all problems in $\mathsf{NP}$ are trivial.

* The "many-one" bit is why $\emptyset$ and $\mathbb{N}$ are problematic: no nonempty set is many-one reducible to $\emptyset$, and dually no no set other than $\mathbb{N}$ is many-one reducible to $\mathbb{N}$. This annoyance goes away with more intricate reducibilities, like (variations of) Turing reducibility: literally every problem in $\mathsf{P}$ is reducible to everything with respect to polynomial-time *Turing* reducibility.

In complexity theory, the default reducibility notion is polynomial-time many-one reducibility. So if we just say "$\mathsf{NP}$-hard" we mean with respect to that reducibility - in which case "there is an $\mathsf{NP}$-hard problem in $\mathsf{P}$" is equivalent to $\mathsf{P=NP}$.
> 2 votes

# Answer
Let $H$ be the set of $\textsf{NP}$-Hard problems, that is, the set of problems $A$ such that *every* problem $B \in \textsf{NP}$ can be reduced to $A$ via a Karp reduction.

Then $\textsf{P} \nsubseteq H$. Consider the problem $A$ associated with the language $\emptyset$ and let $B$ be the problem associated with the language $\\{0,1\\}^\*$. Clearly $A \in \textsf{P}$ and $B \in \textsf{P} \subseteq \textsf{NP}$, but $B$ cannot be reduced to $A$ via Karp reduction. This shows that $A \not\in H$, therefore $\textsf{P} \setminus H \neq \emptyset$.

Notice that this is true regardless of whether $\textsf{P} = \textsf{NP}$.
> 1 votes

---
Tags: complexity-theory, np-hard, np
---


# Question
Title: What strings does this language accept/reject?
```
F = {ww | w ∈ {0,1}^*}

```

Which strings are accepted and why?

1. 0011
2. 1010
3. 1111

# Answer
Though the hint has been provided in the comment section, Here is the answer too:

F accepts strings of form ww.

1. No, there is no way you can write it in the form of ww.
2. Yes. w=10
3. Yes. w=11
> 1 votes

---
Tags: turing-machines, finite-automata
---


title: Maximum cut optimisation

text:
# Question
Title: Maximum cut optimisation
Consider the algorithm below which calculates a V cut

* Initialize $V\_1 = V$ et $V\_2 = \emptyset$
* Attempt to improve the value of the cut in any of the following ways

Check if there is a $v \in V\_1$ such as $c(V\_1-\\{v\\}, V\_2 \cup \\{v\\}) \> c(V\_1,V\_2)$

If yes continue with $V\_1 = V\_1 -\\{v\\}$ et $V\_2 = V\_2 \cup \\{v\\}$.

Check if there is a $v \in V\_2$ such as $c(V\_1 \cup \\{v\\}, V\_2 - \\{v\\}) \> c(V\_1,V\_2)$ If yes continue with $V\_1 = V\_1 \cup \\{v\\}$ et $V\_2 = V\_2 - \\{v\\}$.
* When improvement is no longer possible, return the cut $V\_1, V\_2$

1 . How can I prove that the algorithm is executed in polynomial time by displaying done at most $|E|$ iterations.

Let $(V\_1,V\_2)$ be a cut. For a $v \in V\_1$ we call $\alpha(v)$ the neighbors of $v$ which are in $V\_1$ and $\beta(v)$ the neighbors of $v$ which are in $V\_2$.If $v \in V\_2$, we set $\alpha(v)$ and $\beta(v)$ the neighbors of $v$ which are in $V\_2$ and $V\_1$ respectively.

2. How to prove that if the algorithm can no longer advance then for everything $v \in V$ we have $|\alpha(v)| \leq |\beta(v)|$

# Answer
1) is easy. As you say the algorithm can perform at most $O(|E|)$ iterations. Initially $c(V\_1, V\_2)=0$. Each iteration, except the last, increases $c(V\_1, V\_2)$ by at least $1$. The claim follows since $c(V\_1, V\_2) \le |E|$.

2) Suppose that, for some $v \in V\_1$, $|\alpha(v)| \> |\beta(v)|$ Then moving $v$ from $V\_1$ to $V\_2$ increases the value of $c(V\_1, V\_2)$ by $|\alpha(v)|$ and decreases it by $|\beta(v)|$, therefore $c(V\_1 \setminus \\{v\\}, V\_2 \cup \\{v \\}) = c(V\_1, V\_2) + |\alpha(v)| - |\beta(v)| \> c(V\_1, V\_2)$. This shows that the algorithm could not have terminated. The case $v \in V\_2$ is symmetric.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Is there an efficient algorithm for determining the probability a large randomly chosen integer is not divisible by any integer of some set?
Given a set of 10 integers $A = a\_1, a\_2, \cdots a\_{10}$, is there an efficient algorithm which can tell me what's the probability a randomly chosen integer between $1$ and $10^{10}$ is *NOT* divisible by any member of this set.

I understand the Inclusion-Exclusion principle can be used to solve this problem but I can't figure out how to implement it so that it works efficiently.

**Note**: When I say "efficient", I mean polynomial time, yet I am not entirely sure what qualifies as polynomial time is this case as both variables are fixed.

# Answer
Let $\mathbf x$ be a random number in the range $1,\ldots,N$, and let $E\_i$ denote the event that $\mathbf x$ is divisible by $a\_i$. You are interested in the probability that none of the events $E\_1,\ldots,E\_m$ happen (in your case, $m = 10$). Using the inclusion-exclusion principle, this reduces to computing the probability of the events of the form $E\_{i\_1} \land \cdots \land E\_{i\_k}$, that is, $\mathbf x$ is divisible by all of $a\_{i\_1},\ldots,a\_{i\_k}$. Since a $\mathbf x$ is divisible by a bunch of numbers iff it is divisible by their LCM, it suffices to determine the probability that $\mathbf x$ is divisible by $a$.

Among $1,\ldots,N$, the numbers divisible by $a$ are $$ a,2a,3a,\ldots,\lfloor N/a \rfloor a, $$ in total $\lfloor N/a \rfloor$ numbers. Hence the probability that $\mathbf x$ is divisible by $a$ is exactly $$ \frac{\lfloor N/a \rfloor}{N}. $$
> 2 votes

---
Tags: probability-theory, randomized-algorithms, polynomial-time
---


# Question
Title: Given an input and a program when can you derive the output faster than just running the program?
Given an input string W, a description of a turning machine M, and a target output string O (W,M,O) as input, when can a machine M' decide, in fewer steps than simply running M on W, if running M on W, in fact, produces O or not?

What are the circumstances under which this faster M' exists and when is this impossible, i.e. when does this problem reduce to the halting problem (seems like it does)?

Thanks!

# Answer
Here's an example:

```
for i from 1 to 10000000000
  do nothing
end for
output 1

```

In general, however, you can't save much. Indeed, the time hierarchy theorem states, roughly speaking, that you cannot simulate a $T(n)$-time Turing machine running in time $o(T(n)/\log T(n))$.
> 2 votes

# Answer
In general, what you ask is impossible (regardless of the number of steps that $M'$ takes). If such a machine $M'$ existed then you could solve the halting problem.

Let $T$ and $x$ be a Turing machine and an input string, respectively. Consider a Turing Machine $T'$ that first simulates $T$ on $x$ and, when (if) $T$ terminates, clears the tape and halts.

Now running $M'$ with input $(T', \epsilon, \epsilon)$ decides whether $T'$ outputs the empty string. But this happens if and only if $T'$ terminates.
> 1 votes

---
Tags: halting-problem
---


title: Asymmetric encryption puzzle

text:
# Question
Title: Asymmetric encryption puzzle
I came across this riddle link question:

> Your name's Graham.
>
> Bob wanted to send Alice a secret msg m. However, he was concerned about the security. He encrypted his message with a keyword that both of them knew. Several weeks before this, you overheard them exchanging the keyword k = 'EZRA'. Now, Bob has asked you to deliver the letter to Alice. You want to find out what's the letter about. Decrpyt the secret message m using the ciphertext c='MEDMTBJBMAE'.

The answer to this question was `HELLO GRAHAM`. How could one deduce that without knowing the answer of course.

What can we deduce from the keyword EZRA?

# Answer
> 1 votes
Convert A = 1, B = 2, ..., Z = 26. Take the difference of (cipher text - key) modulo 26. Extend "EZRA" with itself. The third row is the difference between the first and second rows. There might be an error on 'B' and 'G'.

```
 M  E  D  M  T  B  J  B  M  A  E
13  5  4 13 20  2 10  2 13  1  5

 H  E  L  L  O  G  R  A  H  A  M
 8  5 12 12 15  7 18  1  8  1 13

 5 26 18  1  5 21 18  1  5 26 18

 E  Z  R  A  E  Z  R  A  E  Z  R
 5 26 18  1  5 26 18  1  5 26 18

```

---
Tags: encryption
---


# Question
Title: the problems that could exist if halting problem is solved
What problems might exist if halting problem is solved. If there exist an oracle that can compute whether a given machine halts or not then what would be problems that could exists if such oracle is there

# Answer
"Exists" is a weird word to use here; I assume you're asking about what problems would be *solvable* if we were suddenly able to solve the halting problem.

Phrasing things in terms of sets of natural numbers for simplicity (as is the general approach here) you're asking for a characterization of the sets which are Turing reducible to $0'$. It turns out that this is a very robust notion. For example, the following three properties of a set $X$ are equivalent:

* $X\le\_T0'$.
* $X$ is limit computable: there is a computable total function $f(x,s)$ such that for each $n\in\mathbb{N}$ we have $\lim\_{s\rightarrow\infty}f(n,s)$ exists and is $1$ iff $n\in X$ and is $0$ otherwise.
* $X$ is $\Delta^0\_2$-definable: there are formulas $\varphi\_1(z)\equiv\forall x\exists y\theta\_1(x,y,z)$ and $\varphi\_2(z)\equiv\forall x\exists y\theta\_2(x,y,z)$ where $\theta\_1,\theta\_2$ use only bounded quantifiers such that $$X=\\{n:\varphi\_1(n)\\}=\\{n:\neg\varphi\_2(n)\\}.$$

Meanwhile, some problems which are **not** Turing reducible to the halting problem include:

* Does a given Turing machine halt on all inputs?
* Do two Turing machines accept the same language?
* Is a given c.e. set actually computable?

The first two have Turing degree $0''$, while the third has degree $0'''$. It's worth noting that while there are sets which are not "iterations of the halting problem," and in particular there are always lots of degrees between ${\bf d}$ and ${\bf d'}$, there is strong evidence that no "natural" examples of such sets. (There's also a lot of stuff "off to the side" - for example, the set of problems which are Turing-*incomparable* with $0'$ has full measure and is comeager.)
> 1 votes

---
Tags: complexity-theory, halting-problem
---


# Question
Title: Find the k-th member of the recursive sequence
I have a recursive sequence: $a\_n = 5a\_{n - 1} + 2a\_{n-2} + 3$, for $n \> 1$. And I could return $k-th$ member in $O(\log{k})$ of sequence i.e. $a\_k$.
I know how to get the formula of the $k-th$ member using the generating function method, but I need to find a more algorithmic solution.
For example, like this one.

# Answer
> 1 votes
Something like this?

$$ \begin{bmatrix} 5 & 2 & 3 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \cdot \begin{bmatrix} a\_n & a\_{n-1} & 0 \\ a\_{n-1} & a\_{n-2} & 0 \\ 1 & 1 & 0 \end{bmatrix} = \begin{bmatrix} a\_{n+1} & a\_n & 0 \\ a\_n & a\_{n-1} & 0 \\ 1 & 1 & 0 \end{bmatrix} $$

Therefore $a\_k$ is the first element of the matrix: $$ \begin{bmatrix} 5 & 2 & 3 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}^{k-2} \cdot \begin{bmatrix} a\_2 & a\_1 & 0 \\ a\_1 & a\_0 & 0 \\ 1 & 1 & 0 \end{bmatrix}. $$

This only requires $O(\log k)$ matrix multiplications, each of which can be done using a constant amount of arithmetic operations on scalars.

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


# Question
Title: Analyzing a randomized algorithm for finding an approximate median of an array
I'm given an array $A$ = ($a\_1, a\_2, \cdots a\_n$), where n is uneven. For an element $a\_i$ we denote its position in the array with $p(a\_i)$. This element would be an $ε$-approximate median of the array, if after we sort it, the following inequality holds:

$$\frac12 ((1 - ε) × n) \< p(a\_i) \leqslant \frac12 ((1 + ε) × n)$$ For example, the array $1,2,\cdots,9$ would have $4,5,6$ as $\dfrac13$-approximate medians.

My task is to analyze the following randomized algorithm, which finds an $ε$-approximate median of the array in constant time:

> Choose $2k + 1$ elements of the array $A$: $b\_1, b\_2, \cdots, b\_{2k+1}$, where each element is chosen uniformly randomly and independently of all the others (it is possible for an element to repeat). Using the algorithm for finding a median of an array in linear time (QuickSelect) output the median of the array the elements $b\_1, b\_2, \cdots, b\_{2k+1}$ form.

I'm also given the following two random variables:

$K$: number of elements in $b\_1, b\_2, \cdots, b\_{2k+1}$, which are smaller or equal to the $\dfrac12 ((1-ε)×n)$-biggest element in the original array $A$.

$G$: number of elements in $b\_1, b\_2, \cdots, b\_{2k+1}$, which are bigger than the $\dfrac12 ((1+ε)×n)$-biggest element in the original array $A$.

What I have to do is find the best possible upper bounds for $$P(K \geqslant (1 + ε) E(K))$$ and $$P(G \geqslant (1 + ε) E(G)),$$ where $E(K)$ and $E(G)$ are the expected values for the random variables. I also have to find a bound for the probability the algorithm will be successful, which depends only on $k$, not on $n$, $E(K)$ or $E(G)$.

What I have done so far: I computed the expected values for the two random variables. I believe they are binomially distributed, so for example for $K$ I have $2k + 1$ events each with probability $\dfrac12(1-ε)$ to happen, so $$E(K) = (2k + 1) × \dfrac12 (1 - ε).$$ $E(G)$ turns out to be the same. Then I tried computing the two upper bounds, mentioned above with the Markov, Chebyshev and Chernoff inequalities:

Markov: $$P(K \geqslant (1 + ε) E(K)) \leqslant \frac1{1 + ε},$$ Chebyshev (might be false): $$P(|K - E(K)| \geqslant εE(K)) \leqslant \frac{\operatorname{Var}(K)}{ε^2 × (E(K))^2} = \frac{1}{ε(2k + 1)},$$ Chernoff: $$P(K \geqslant (1 + ε) E(K)) \leqslant \exp\left( -\frac13 ε^2 E(K) \right).$$ Are these correct? If they are, am I correct that Chebyshev is the best one? How do I continue with finding the probability of success of the algorithm?

Thank you :)

# Answer
> 0 votes
As suggested in the comments, the Chernoff bound is the best one because it gives better bounds as the input grows. We can again use this same Chernoff bound to determine a lower bound for the probability of success for the algorithm. This turns out to be $1 - 2 * \exp\left( -\frac13 ε^2 E(K) \right)$ as we have to subtract from $1$ the probabilities $P(G \geqslant (1 + ε) E(G))$ and $P(K \geqslant (1 + ε) E(K))$ because those are exactly the cases, where the algorithm fails to output the desired $ε$-approximate median.

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


# Question
Title: What does $(\log n) \cdot (\log n)$ simplify to in Big O notation?
Does it simplify to $O(\log n)$ or $O(\log^2 n)$ or something else entirely? I am a bit stuck on this one.

# Answer
As $\log(n) \times \log(n) = \log^2(n)$, you can say $\log(n) \times \log(n) = O(\log^2(n))$.Moreover, as $\lim\_{n\to\infty}\frac{\log(n)}{\log^2(n)} = 0$, you can't write $\log(n) \times \log(n) = O(\log(n))$, but you can write $\log(n) \times \log(n) = \omega(\log(n))$.
> 2 votes

# Answer
One more way of approaching these type of questions if you have slightest idea of possible answers is as follows:

The questions is: What does $(log $ n).($log $ n) simplify to in Big O notation(By Big O I assume you mean the tightest upper bound)

The possible answers provided are: $(log $ n) and $O(log^2$ n)

Solution: Let us take log of all the above three terms

1. $log ((log $ n).($log $ n)) = $loglog$ n + $loglog$ n = 2$(loglog$ n)
2. $log (log$ n) = $loglog$ n
3. $log (log^2$ n) = 2($loglog$ n)

Don't ignore the constants after taking the log.

You can now clearly see that:

($log $ n).($log $ n) = $O$($log^2$ n)

and

($log $ n).($log $ n) = ($log$ n)
> 0 votes

---
Tags: big-o-notation
---


# Question
Title: When can the coinduction hypothesis be used?
We can use the induction hypothesis when we are proving a property for a structure that is well-ordered. I am aware that there is a proof for this.

When it comes to coinduction, I'm confused.

One of the answers to another question "What is coinduction?" mentions that there is a notion of a corecursive definition to be well-formed.

A lot of things I (try to) read related to coinduction mostly talk about bisimulation and equivalence. But to the best of my knowledge, those are trying to prove some relationship for two coinductive data structures. For example, they prove that two streams are equivalent. And the coinductive hypothesis is somehow derived from one of the bisimulation's hypothesis. Even so, I think I'm still lost on the requirements of what constitutes well-formedness in the coinductive world.

I can somehow see that the coinduction hypothesis works when proving those kinds of propositions, but I'm still unclear when they can be used to prove more general propositions such as the one mentioned in What is coinduction?. In that link, the proposition states that "something is infinite". This seems like a more generic form of statement one would be interested in proving.

A possibly related question is whether any proposition can be converted and re-stated as a proposition of equivalence or not.

Is there some simple informal reasoning that talks why co-induction works for some well-formedness requirement?

I'm hoping for an explanation like if possible: https://math.stackexchange.com/questions/432293/well-ordering-and-mathematical-induction/432302#432302.

# Answer
> 3 votes
First, let me recall least and greatest fixed points for $\subseteq$. We are working relative to some set $U$, the universe. In the case of (co)inductive definitions, $U$ is the set of all terms. A function $f:2^U\to2^U$ (from subsets of $U$ to subsets of $U$) is *monotone*, if $A\subseteq B$ always implies $f(A)\subseteq f(B)$. A *fixed point* of $f$ is a set $A$ such that $f(A)=A$.

For monotone $f$ there always is a least fixed point $\mu f$, namely the intersection of all $A\subseteq U$ such that $f(A)\subseteq A$. *Least* means that for arbitrary fixed points $F$ we always have $\mu f\subseteq F$.

For an example, let $f\_{\tt nat}$ be defined by $f\_{\tt nat}(A)=\\{0\\}\cup\\{n+1\mid n\in A\\}$. The function $f\_{\tt nat}$ is the one-step closure function under the constructors $0$ and $+1$. The condition $f\_{\tt nat}(A)\subseteq A$ means that $A$ is closed under the constructors $0$ and $+1$. The intersection means that the $\mu f\_{\tt nat}$ contains only those elements which are in every set closed under the constructors. These happen to be the natural numbers. The example shows how the inductive definition of natural numbers is the least fixed point of closure under the natural numbers' constructors. Generally, inductively defined sets are least fixed points of closure under constructors.

Dually, for monotone $f$ there also is a greatest fixed point $\nu f$, namely the union of all $A\subseteq U$, such that $f(A)\supseteq A$. *Greatest* means that for arbitrary fixed points $F$ we always have $\nu f\supseteq F$. To make the duality complete, let us note that intersection is the $\subseteq$-infimum and union the $\subseteq$-supremum and thus the $\supseteq$-infimum. So, in fact, greatest fixed points for $\subseteq$ are just least fixed points for $\supseteq$ and vice versa. (Also, observe that the requirement of monotonicity is the same for $\subseteq$ as for $\supseteq$.)

Now, for proof techniques. Let us begin with the example of induction on natural numbers. To show that some property $P$ holds for all natural numbers, we show that $P(0)$ and that $P(n)$ implies $P(n+1)$. Viewing $P$ as a subset of $U$ (the set of all elements where the property holds), the proof obligation for natural induction is that $P$ is closed under $f\_{\tt nat}$. Correctness of the proof technique of natural induction then follows from the definition of least fixed point: If $f\_{\tt nat}(P)\subseteq P$, then $P$ is part of the intersection that forms $\mu f\_{\tt nat}$, so the property holds throughout $\mu f\_{\tt nat}$, that is $\mu f\_{\tt nat}\subseteq P$.

Induction is just the generalization of the previous paragraph to arbitrary monotone $f$ instead of $f\_{\tt nat}$. Coinduction is the dual of induction: The proof obligation is $f(P)\supseteq P$. This means that if $P$ holds on some element $x$, then $x$ is constructed using only base elements on which $P$ also holds. So, instead of showing that the property survives application of constructors, we have to show that it survives deconstruction. Once the proof obiligation is satisfied, we obtain $\nu f\supseteq P$.

What good is the conclusion $\nu f\supseteq P$? Let us reconsider $P$ not as a property but as a subset of $U$. The conclusion of coinduction establishes that all elements of $P$ are well-formed members of the coinductivly defined set $\nu f$. This is what happens in the example in What is coinduction? showing `forall n, Infinite (from n)`. Here, $f$ is closure under the constructors of `Infinite` (not of `colist`!) and $P$ is the set of all terms of the form `from n` for some `n`.

---
Tags: logic, induction, coq, coinduction, isabelle
---


# Question
Title: Solving recurrence relation for asymptotic analysis
How to solve the recursion:

$ T(n) = \begin{cases} T(n/2) + O(1), & \text{if $n$ is even} \\ 2T(\lceil n/2 \rceil) + O(1), & \text{if $n$ is odd} \end{cases} $

I know that it can be written as O(n). But I want to find a tighter bound. For example, when dealing with powers of two, T(n) is O(logn), which will most probably allow for a tighter bound overall.

So, how to solve this recursion?

# Answer
> 2 votes
Suppose $n = 2^m + 1$. Then $$ T(n) \geq 2T(2^{m-1}+1) \geq 4T(2^{m-2}+1) \geq \cdots, $$ and so $T(n) = \Omega(n)$ for $n$ of this form. Therefore you cannot get a better worst-case bound than $O(n)$.

In more detail, this example shows that if $T(n) = O(f(n))$ for a monotone function $f(n)$ then $f(n) = \Omega(n)$. You might be able to get an upper bound using more information on $n$.

---

Let's analyze a similar but slightly simpler recursion, $$ S(n) = \begin{cases} S(n/2) + 1 & \text{if $n\>0$ is even}, \\ 2S(\lfloor n/2 \rfloor) + 1 & \text{if $n$ is odd},\\ 0 & \text{if $n = 0$}. \end{cases} $$ Let us denote $$ S(a\_1,\ldots,a\_k) = S(2^{a\_1} + \cdots + 2^{a\_k}), $$ where we implicitly assume that $a\_1 \> \cdots \> a\_k$. We have $$ \begin{align\*} S(a\_1,\ldots,a\_k) &= 1 + S(a\_1-1,\ldots,a\_k-1) \\ &= 2 + S(a\_1-2,\ldots,a\_k-2) \\ &= \cdots \\ &= a\_k + S(a\_1-a\_k,a\_2-a\_k,\ldots,a\_{k-1}-a\_k,0) \\ &= a\_k + 1 + 2S(a\_1-a\_k-1,a\_2-a\_k-1,\ldots,a\_{k-1}-a\_k-1) \\ &= (a\_k + 1) + 2(a\_{k-1}-a\_k) + 4S(a\_1-a\_{k-1}-1,\ldots,a\_{k-2}-a\_{k-1}-1) \\ &= (a\_k+1) + 2(a\_{k-1}-a\_k) + 4(a\_{k-2}-a\_{k-1}) + \cdots + 2^{k-1}(a\_1-a\_2) \\ &= 2^{k-1} a\_1 - 2^{k-2} a\_2 - \cdots - a\_k + 1. \end{align\*} $$ Notice now that $$ 2^{k-1} a\_1 - 2^{k-2} a\_2 - \cdots - a\_k + 1 \geq \\ 2^{k-1} a\_1 - 2^{k-2} (a\_1 - 1) - \cdots - (a\_k - (k-1)) + 1 = \\ a\_1 + 2^k - k, $$ and on the other hand, $$ 2^{k-1} a\_1 - 2^{k-2} a\_2 - \cdots - a\_k + 1 \leq \\ 2^{k-1} a\_1 - 2^{k-2} (k-2) - 2^{k-3} (k-3) - \cdots - 0 + 1 = \\ 2^{k-1} (a\_1 - k + 3) - 1. $$ This gives us a lower bound of $\Omega(\log n + 2^{|n|})$ and an upper bound of $O(n)$, where $|n|$ is the Hamming weight; note that if $n = 2^m-1$ then the lower bound is linear in $n$. Indeed, $$ S(2^m-1) = 1 + 2S(2^{m-1}-1) = 1 + 2 + 4S(2^{m-2}-1) = \cdots = \\ 1 + 2 + 4 + \cdots + 2^{m-1} S(1) = 2^m-1. $$

---

It is likely that you can find a similar formula for $T$.

---
Tags: asymptotics
---


title: Greedy algorithm for job scheduling

text:
# Question
Title: Greedy algorithm for job scheduling
Consider the following greedy algorithm for Job Scheduling. For each new task, assign the task to processor with the shortest uptime.

> How to prove that this algorithm has an approximation ratio of 2?

Suppose that once the algorithm is completed, processor $1$ is the busiest and assume task $l$ is the last task assigned to it. Let $s$ be the time that was used on processor $1 $ before adding task $i$. The algorithm has therefore found a valuable solution $u\_1 = s + t\_\ell$.

I'm stuck on how to show that:

* for every $1 \leq j \leq k$ we have $s \leq \sum\_{i: \alpha(i)=j}t\_i$.
* $s \leq 1/k \\; \sum\_i t\_i \leq u^\*$ and $t\_\ell \leq u^\*$ and use these results to limit $u\_1$ ($u^\*$ is the optimal value).

Here is the definition of the Job Scheduling problem

Input: A set of $n$ tasks of length $t\_1, t\_2, \ldots, t\_n \in \mathbb N$ and $k$ processors.

A feasible solution is a function $\alpha\colon \\{1, \ldots ,n\\} \rightarrow \\{1, \ldots k\\}$ which assigns each task to a processor.

The usage time $u\_j$ of a processor $j$ is the sum of the lengths of all the tasks assigned to it, that is to say that $u\_j = \sum\_{i: \alpha(i)=j}t\_i$.

We try to minimize $\max\_j u\_j$, that is to say the time of use of the most used processor.

# Answer
> 1 votes
You can find this algorithm analyzed at the very beginning of these lecture notes, or in these lecture notes (which consider a better variant of the algorithm but only analyze your variant), as well as in many other resources.

These are the first two hits when searching for `makespan approximation`.

---
Tags: approximation, scheduling
---


title: What threads share in general?

text:
# Question
Title: What threads share in general?
Well this is general question. And if anyone want to make it implementation specific then I will prefer Unix related stuff. But first need to know following problems in generality:

I read single process can have multiple threads. Multiple threads of same process does share things among them. I want to know what they share and what not. Considering process is comprised of address space, stack, heap, global variables, code, data, OS resources, what among them is shared by threads? I have following guessings:

1. **Global variables -** I have read thread shares global variable. Also while programming in Java and C#, I have made threads to share class level variables. So I am believing that the threads share global variables (though not sure whether the concepts in high level programming languages translates as is to low operating system level facts).
2. **Heap -** Since global variable is stored in the heap, heap is shared among threads.
3. **Stack -** Since each thread can have its own execution sequence/code, it must have its own stack on which it might push/pop its program counter contents (when say function calls and returns happen). So threads of same process do not share stack.

Now I am unsure about the sharing of following things

4. **Address space -** Not sure what exactly counts under address space. But I guess address space is generally used in the context of processes, not threads. And since all threads of same process reside in the same address space as the parent process, it is said that threads share address space. (But then they maintain different stack inside same address space?)
5. **OS resources -** I guess this can be very implementation specific. For example, parent process can selective give handle of same file to some of its threads and not to all. Or I am mistaking and OS resources means something other than files?
6. **Code -** Threads can have different code, so sharing code is not always the case.
7. **Data -** Unsure about what to consider under data. But sure that global variables are shared among threads. And sure that local variables are not similarly shared.

Overall I am considerably confused due to vague terms, super-generalizations done in the Operating Systems books and extra-implementation specific details provided online. So I am trying to find some answer that can satisfy me.

# Answer
In general each *thread* has its own registers (including its own program counter), its own stack pointer, and its own stack. Everything else is shared between the threads sharing a process.

In particular a *process* is generally considered to consist of a set of threads sharing an address space, heap, static data, and code segments, and file descriptors*.

An *address space* is simply the mapping of logical addresses to specific pieces of physical memory. So when we say that all the threads in a process share the same address space we mean that when accessing a variable `foo` in global scope all the threads will see the same variable. Similarly, the threads may all be running a different point in the code at any particular time, but they are all permitted to call the global function `bar()`, which will correspond to the same function for every thread in the process.

Most modern operating systems have added a notion of *thread local storage*, which are variables of global scope that are not shared. The usual example of the use of this is for the variable `errno`. That's a single variable of global scope, but in most modern operating systems each thread is given its own local copy, so that an error in a library call on one thread won't impact the behavior of other threads.

* There is some additional process state shared by all the threads in a process, things like the process id, the signal handling, and file locks. For a complete list of process state shared by threads you need to look at the documentation for the specific threading implementation. For example, the pthreads man page.
> 20 votes

# Answer
Threads come up in two perspectives: operating systems, and programming languages. In both case, there is some variation in what attributes a thread has.

A minimal definition of a thread is that it's stuff that happens in sequence, one thing after another.

In a typical machine execution model, each thread has its own set of general-purpose registers and its own program counter. If the machine sets out a specific register as a stack pointer, there's one copy per thread.

From an operating system perspective, the minimum an operating system needs to do to support threads is provide a way to switch between them. This can happen either automatically (premptive multitasking or only when the thread makes an explicit request (cooperative multitasking; in that case threads are sometimes called fibers). There are also hybrid models with both preemption and cooperative yields, e.g. preemption between threads of different groups or tasks but explicit yields between threads of the same group/task. Switching between threads involves at a minimum saving the register values of the old thread and restoring the register values of the new thread.

In a multitasking operating system that provides isolation between tasks (or processes, you can treat these terms as synonyms in an OS context), each task has its own resources, in particular address space, but also open files, privileges, etc. Isolation has to be provided by the operating system kernel, an entity that's above processes. Each task normally has at least one thread — a task that doesn't execute code isn't of much use. The operating system may or may not support multiple threads in the same task; for example the original Unix didn't. A task can still run multiple threads by arranging to switch between them — this doesn't require any special privileges. This is called “user threads”, especially in a Unix context. Nowadays most Unix systems do provide kernel threads, in particular because it's the only way to have multiple threads of the same process running on different processors.

Most operating system resources apart from computation time are attached to tasks, not threads. Some operating systems (for example, Linux) explicitly delimit stacks, in which case each thread has its own; but there are OSes where the kernel doesn't know anything about stacks, they're just part of the heap as far as it's concerned. The kernel also typically manages a kernel context for each thread, which is a data structure containing information about what the thread is currently doing; this lets the kernel handle multiple threads blocked in a system call at the same time.

As far as the operating system is concerned, the threads of a task run the same code, but are at different positions in that code (different program counter values). It may or may not happen that certain parts of the code of a program are always executed in a specific threads, but there's usually common code (e.g. utility functions) that can be called from any thread. All the threads see the same data, otherwise they'd be considered different tasks; if some data can only be accessed by a particular thread, that's usually solely the purview of the programming language, not of the operating system.

In most programming languages, storage is shared between threads of the same program. This is a shared memory model of concurrent programming; it's very popular, but also very error-prone, because the programmer needs to be careful when the same data can be accessed by multiple threads as race conditions can occur. Note that even local variables can be shared between threads: “local variable” (usually) means a variable whose name is only valid during one execution of a function, but another thread can obtain a pointer to that variable and access it.

There are also programming languages where each thread has its own storage, and communication between them happens by sending messages over communication channels. This is the message passing model of concurrent programming. Erlang is the main programming language that focuses on message passing; its execution environment has a very lightweight handling of threads, and it encourages programs written with many short-lived threads, in contrast with most other programming languages where creating a thread is a relatively expensive operation and the runtime environment can't support a very large number of threads at the same time. Erlang's sequential subset (the part of the language that happens within a thread, in particular data manipulation) is (mostly) purely functional; thus a thread can send a message to another thread containing some data and neither thread needs to worry about the data being modified by the other thread while it's using it.

Some languages blend the two models by offering thread-local storage, with or without a type system to distinguish thread-local storage location from global ones. Thread-local storage is usually a convenience feature that allows a variable name to designate different storage locations in different threads.

Some (difficult) follow-ups that may be of interest to understand what threads are:

* What is the minimum that a kernel needs to do to support multiple threads?
* In a multiprocessor environment, what does it take to migrate a thread from one processor to another?
* What would it take to implement cooperative multithreading (coroutines) in your favorite programming language with no support from the operating system and without using its built-in support if any? (Beware that most programming languages lack the necessary primitives to implement coroutines inside a single thread.)
* What could a programming language look like if it had concurrency but no (explicit) concept of threads? (Prime example: the pi-calculus.)
> 9 votes

# Answer
That depends. If you consider threads as defined e.g by POSIX (and offered by Unix systems) or by Windows (not familiar with the later, you'd have to ask specifically), then that gives your answer (essentially as @WanderingLogic answer explains). Linux has its very own idea of threads, using the non-standard `clone(2)` system call. It offers rather fine-grained control of what parent and child share. It goes as far as having `fork(2)` and `vfork(2)` essentially wrappers around the internal `clone(2)`, calling it with specific flags, i.e., you can create "threads" that share next to nothing with the parent. Look up its manual page for details, they are available on-line e.g. here. Yes, Linux does offer POSIX style threads, but much more besides.
> 3 votes

# Answer
Threads share:

* Address space
* Heap
* Static data
* Code segments
* File descriptors
* Global variables
* Child processes
* Pending alarms
* Signals and signal handlers
* Accounting information

Threads have their own:

* Program counter
* Registers
* Stack
* State
> 2 votes

# Answer
I will just quickly answer the questions posted.

1. Address space: YES (shared between threads). The process address space consists of the linear address range presented to each process and, more importantly, the addresses within this space that the process is allowed to use. This is a virtual address so 2 processes can have different data at the same address in their respective address spaces
2. OS resources: YES. As explained in the above answer, file descriptors and other OS resources are assigned and managed at the process level.
3. Code: YES. A memory map of the executable file's code, is stored in a section called the text section. This is shared between the threads.
4. Data: YES. A memory map of the executable file's initialized global variables, called the data section is shared.

Reference: http://books.gigatux.nl/mirror/kerneldevelopment/0672327201/ch14.html
> 0 votes

---
Tags: operating-systems, threads
---


title: Solving recurrence

text:
# Question
Title: Solving recurrence
How to solve the recursion:

$ T(n) = \begin{cases} T(n/2) + O(1), & \text{if $n$ is even} \\ T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + O(1), & \text{if $n$ is odd} \end{cases} $

I think $T(n)$ is $O(\log n)$. Can somebody show a proof?

# Answer
> 1 votes
Your function appears in Sung-Hyuk Cha, On Parity based Divide and Conquer Recursive Functions.

Let us consider the following version: $$ T(n) = \begin{cases} 0 & \text{if } n = 0,1, \\ 2 & \text{if } n = 2, \\ T(n/2) + 1 & \text{if } n \geq 4 \text{ is even}, \\ T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + 1 & \text{if } n \geq 3 \text{ is odd}. \end{cases} $$ You can calculate that $$ T\left(\frac{7 \cdot 2^n - (-1)^n}{3}\right) = 2F\_{n+4} - 2F\_{n+1} - 2. $$ For example, $T(2) = 2$, $T(5) = 6$, $T(9) = 10$ (these correspond to $n=0,1,2$).

This gives an infinite sequence of $n$'s such that $$ T(n) = \Theta(n^{\log\_2 \phi}), $$ where $\phi$ is the golden ratio. Empirically, this sequence maximizes the exponent.

The limiting exponent is roughly $0.694241913630617$.

See the related sequences A215673 and A215675, which correspond to slightly different initial conditions.

The sequence of worst-case inputs is A062092, and that of worst-case outputs is A001595.

---

Let us prove the claimed formula. Let $a\_n = \[7 \cdot 2^n - (-1)^n\]/3$. Then $a\_0 = 2$, and $a\_n = 2a\_{n-1} - (-1)^n$ for $n \> 0$. If $n \> 0$ is even then $$ \begin{align\*} T(a\_n) &= 1 + T(a\_{n-1}) + T(a\_{n-1} - 1) \\ &= 1 + T(a\_{n-1}) + T(2a\_{n-2}) \\ &= 2 + T(a\_{n-1}) + T(a\_{n-2}). \end{align\*} $$ Similarly, if $n\>1$ is odd then $$ \begin{align\*} T(a\_n) &= 1 + T(a\_{n-1}) + T(a\_{n-1}+1) \\ &= 1 + T(a\_{n-1}) + T(2a\_{n-2}) \\ &= 2 + T(a\_{n-1}) + T(a\_{n-2}). \end{align\*} $$ Denoting $b\_n = T(a\_n)/2$, we get $b\_0 = 1$, $b\_1 = 3$, and $b\_n = b\_{n-1} + b\_{n-2} + 1$ for $n \geq 2$. The sequence $b'\_n = b\_n + 1$ satisfies the recurrence $b'\_n = b'\_{n-1} + b'\_{n-2}$, from which it is easy to find an explicit formula.

---

In the other direction, let us notice that when $n$ is odd, exactly one of $\lfloor n/2 \rfloor,\lceil n/2 \rceil$ is odd, and the other is even. This shows that for all $n$, we have $$ T(n) \leq T(n/2 + O(1)) + T(n/4 + O(1)) + O(1). $$ According to the Akra–Bazzi theorem, the solution to this recurrence is $T(n) = O(n^p)$, where $p$ is the solution to $$ \frac{1}{2^p} + \frac{1}{4^p} = 1. $$ (To deduce that from the theorem requires a bit of work; briefly, you compare $T$ to another recurrence $T'$ which is defined like $T$ on odd inputs but in a different way for even inputs; $T'$ satisfies the recurrence above exactly, and induction shows that $T \leq T'$.)

Let $x = 2^p$. Then $1/x + 1/x^2 = 1$, and so $x^2 = x + 1$. This is the familiar Fibonacci recurrence, with solutions $x = (1 \pm \sqrt{5})/2$. Only one of them is positive, and we conclude that $p = \log\_2 \phi$. Therefore $$ T(n) = O(n^{\log\_2 \phi}). $$ As we have seen above, the exponent is tight for infinitely many $n$. Since these $n$ are dense enough, we can conclude that $$ \max (T(0),\ldots,T(n)) = \Theta(n^{\log\_2 \phi}). $$

---
Tags: asymptotics
---


# Question
Title: Proving non-regular language using the pumping lemma
I would like to verify that the following language is not regular.

I know that if the pumping lemma is not valid then the language is not regular. (but its not enough to prove that the language is in fact regular if the pumping lemma is valid)

So, given the following language,

$\Sigma =\\{a,b\\}$, $L=\\{v\cdot u\cdot u: v,u\in\Sigma^\*,u\neq \varepsilon\\}$

Can I show that the pumping lemma is not valid here?

*Side note:*

I think I can prove that this language is regular by using regular expressions like so:

denote $r= (a\cup b)^\*$ now, $L=(a\cup b)^\*\cdot (aa\cup bb)\cdot r\cdot r$

Is this true?

# Answer
> 0 votes
Given the word $w = ab^p ab^p$, clearly $w\in L \land |w|=2\cdot(p+1)\geq p$.

Now, consider the division $w=xyz$ where $|xy|\leq p \land |y|\>0$ then

* **Case 1**: $x=\varepsilon$, $\forall s\geq0\ ,y=ab^s$ then if $i=0$ we get that $xy^0z$ is actually $b^{p-s}ab^p$ and that's clearly not in L, because of the '$a$' in the middle of the new word.
* **Case 2**: $x\not=\varepsilon$ then $\forall s\>0:\ y=b^s$ then again if $i=0$ we get that $xy^0z = ab^{p-s}ab^p$ and because $s\>0$ then there is not a repeatable word (because $u=ab^p$ or $u=ab^{p-s}$) so we can conclude that $w\notin L$.

Thus $L\notin REG$.

# Answer
> 1 votes
Your language is not regular. Indeed, let $n$ be the pumping lemma constant, and consider the word $ab^nab^na = a(b^na)^2 \in L$. Suppose that your language were regular. Then you could write $ab^nab^na = xyz$, where $|xy| \leq n$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. We consider two cases:

* Case 1: $x = \epsilon$, and so $y = ab^t$ for some $t \geq 0$. Then $xy^0z = b^{n-t}ab^na$. Suppose this were of the form $vu^2$. Considering the second copy of $u$, we see that $u$ ends in $a$. Since there are two copies of $a$, necessarily $u = b^na$. This is only possible if $t = 0$ (which is OK) and $v \neq \epsilon$ (which is not OK).
* Case 2: $x = ab^t$, and so $y = b^s$ for some $t \geq 0$ and $s \geq 1$. Then $xy^0z = ab^{n-s}ab^na$. Suppose this were of the form $vu^2$. Since $v \neq \epsilon$, the word $u^2$ is a suffix of $b^{n-s}ab^na$, and so as before, necessarily $u = b^na$ and we reach a contradiction since $s \neq 0$.

Now, why does your regular expression $(a+b)^\* (aa+bb) (a+b)^\* (a+b)^\*$ not work? You are implicitly assuming that if you write "$r \cdot r$" then the semantics are that the same word must be chosen twice. However, this need not be the case. For example, the word $aab$ matches your regular expression, but is not in $L$.

---
Tags: regular-languages, finite-automata, regular-expressions, pumping-lemma
---


# Question
Title: Why $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ doesn't refute the lower bound $O(n^{3-\delta})$?
I have a simple quesiton:

> It is conjectured that All Pairs Shortest Path (APSP) has no $O(n^{3-\delta)}$-time algorithm for any $\delta \>0$ by SETH.

also

> there is a result that says APSP can be solved in time $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ by Ryan Williams.

But, this improvement doesn't refute the conjectures.

So, what I did is as following: I compare between $\lim\_{n -\> \infty} \frac{( \frac{n^3}{2^{\sqrt{\log n}}})}{n^{3-\delta} } = 0 $ So, $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ is better than the other one, so why it doesn't mean that we refute the conjecture.

When I have this function: $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$, I didn't know how to compare it with other since Big Omega is only on part of it, how to compare in general with other function when you have this one?

Thanks in advance!

# Answer
The statement "no $O(n^{3-\delta})$ algorithm exists" (for any constant $\delta\>0$) means that there is no algorithm that is a **polynomial factor** faster than $\Theta(n^3)$. It doesn't exclude algorithms that are faster by some **less than polynomial** factor. For example it doesn't exclude algorithms with a running time of $\Theta(\frac{n^3}{\log n})$.

In your case, the set $2^{\Omega(\sqrt{\log n})}$ includes functions that grow slower than any polynomial. For example $2^{\sqrt{\log n}}$. To see this, pick any constant $\epsilon\>0$ and notice that:

$$ \lim\_{n \to \infty} \frac{2^{\sqrt{\log n}}}{n^\epsilon} = \lim\_{n \to \infty} \frac{2^{\sqrt{\log n}}}{2^{\epsilon \log n}} = \lim\_{n \to \infty} 2^{\sqrt{\log n} - \epsilon \log n} = 0. $$
> 4 votes

# Answer
It looks like the comparison in the question is wrong.

$$\begin{aligned} \lim\_{n -\> \infty} \frac{\frac{n^3}{2^{\sqrt{\log n}}}}{\ \ n^{3-\delta}\ \ } &= \lim\_{n -\> \infty} \frac{n^{\delta} }{2^{\sqrt{\log n}}}=\lim\_{n -\> \infty} \frac{2^{\delta\log n} }{2^{\sqrt{\log n}}}\\ &=\lim\_{n -\> \infty} 2^{\delta\log n-\sqrt{\log n}}=\lim\_{m -\> \infty}2^{\delta m-\sqrt{m}}\\ &=\lim\_{m -\> \infty}2^{\sqrt m(\delta\sqrt{m} -1)}\\ &=2^{+\infty}=+\infty.\\ \end{aligned}$$

Here $\log n$ is understood as $\log\_2n$. Since $\log\_a n=\log\_a2\cdot\log\_2n$, the limit above will still be infinity if the base of $\log$ is switched to any number greater than 1.

In fact, for any constant $c\>0$, however smaller it is and any constant $\delta\>0$, however small it is, we still have, by similar argument,

$$\lim\_{n \to \infty}\frac{\frac{n^3}{2^{c\sqrt{\log n}}}}{\ \ \ {n^{3-\delta}\ \ \ }} =+\infty.$$

---

> I compare between $\lim\_{n -\> \infty} \frac{ \frac{n^3}{2^{\sqrt{\log n}}}}{\ \ \ n^{3-\delta}\ \ } = 0 $ So, $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ is better than the other one, so why it doesn't mean that we refute the conjecture.

To be more careful, there is another mistake in the above reasoning. Even if $\lim\_{n -\> \infty} \dfrac{\frac{n^3}{2^{\sqrt{\log n}}}}{\ \ n^{3-\delta}\ \ } = 0 $, it does not imply it will refute the conjecture. The point is, "APSP can be solved in time $\dfrac{n^3}{2^{\Omega(\sqrt{\log n\ })}}$" might be true because it can be solved in time $\frac{n^3}{2^{0.01\sqrt{\log n\ \ }}}$, not because it can be solved in time $\frac{n^3}{2^{\sqrt{\log n\ \ }}}$". If you want to use the fact that "APSP can be solved in time $\dfrac{n^3}{2^{\Omega(\sqrt{\log n\ })}}$" to refute the conjecture, you have to show that

$$O(n^{3-\delta}) \cap \frac{n^3}{2^{\Omega(\sqrt{\log n})}} = \emptyset,$$ or, in plain words, there is no function $f\in \Omega(\sqrt{\log n})$ such that $\dfrac{n^3}f\in O(n^{3-\delta})$.

Well, in fact, the other extreme is true. $\dfrac{n^3}f\in O(n^{3-\delta})$ for all $f\in \Omega(\sqrt{\log n})$.
> 4 votes

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Minimum bottleneck path between two vertices in an undirected graph
I have an undirected graph, where the value of the path is the maximum weight among all weights edges included in it. And I want find the path of minimum value between two given vertices in time $O(n + m)$, where $n$ \- number of vertices, $m$ \- number of edges.

# Answer
> 1 votes
I will use the fact that you can check for the connectivity between two vertices $s$ and $t$ in a graph with $m\>0$ edges in time $O(m)$.

Call $G$ be the input graph, and let $s$ and $t$ be endpoints of the paths you are interested in. I will denote by $G\_w$ (resp. $G^\<\_w$) the graph induced by all the edges of weight at most (resp. less than) $w$ in $G$. You can solve the problem using the following recursive algorithm:

If $G$ has no edges, report that $s$ and $t$ are disconnected in $G$.

If $G$ has at least one edge, find the median $w$ among the edge weights of $G$, and proceed as follows:

* If $s$ and $t$ are connected in $G\_w$ and disconnected in $G^\<\_w$, return $w$.
* If $s$ and $t$ are connected in both $G\_w$ and $G^\<\_w$, apply the algorithm recursively on $G^\<\_w$ (notice that $G^\<\_w$ has at most $\frac{m}{2}$ edges).
* If $s$ and $t$ are disconnected in $G\_w$, build the graph $G'$ obtained from $G$ by identifying all vertices that belong to the same connected component of $G\_w$, and apply the algorithm recursively on $G'$ (notice that $G'$ has at most $\frac{m}{2}$ edges, since it can't contain any edge with weight less than or equal to $w$).

The time complexity of the above algorithm is described by the recurrence equation: $T(m) = T(m/2) + O(m)$, which has solution $T(m)=O(m)$.

This problem is the same as its maximization version once all edge weights are multiplied by $-1$.

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


# Question
Title: Number partitioning targeting ratio of subset sums and equal size
I've seen a number of questions and answers related to the partitioning problem of dividing a set into 2 subsets of equal size and sum that use greedy or dynamic programming solutions to get approximate answers. However, I am looking to split a set into 2 subsets of minimum difference in size but with a target ratio of sums.

I have tried variations of greedy algorithms that will work to minimize the largest difference of the two metrics at any point in the calculation, but this just results in a result that splits the difference between the two. I'm happy with an approximate solution since it needs to run in a reasonable amount of time.

# Answer
> 2 votes
The problem is NP-hard (assuming the numbers are represented in binary). If you could solve your problem efficiently, you could solve the Partition problem: Partition is the special case where the minimum difference is zero (and the target ratio is 1:1). Therefore, you should not expect any simple algorithm to be both efficient and always correct.

If you want a heuristic that gives an approximation, greedy algorithms are reasonable. I suggest you try adapting the standard algorithms for the Partition problem. Another approach is to use an integer linear programming solver.

# Answer
> 0 votes
As D.W.'s answer mentions, this is NP-hard to solve exactly as a known NP-hard problem is a special case of it.

To adapt any algorithm (exact or heuristic) for solving the Partition Problem to your problem, just add a single new "dummy" number calculated to make the ratio what you want. Suppose you want one of the sides to have sum $r$ times the other side's sum, and the total of all numbers is $t$. Since PP finds equal-sum partitions, we want to find a number $d$ to add such that $x+d=rx$, so that removing $d$ leaves us with a sum $x$ on one side, and $rx$ on the other side. Additionally we have that $x+d=rx=(t+d)/2$. We want to eliminate the unknown $x$ and rearrange to obtain $d$ in terms of the other, known, parameters:

$$ x+d=rx\\ x-rx=-d\\ x(1-r)=-d\\ x=d/(r-1) $$

Substituting this into $rx=(t+d)/2$ gives

$$ rd/(r-1)=(t+d/(r-1))/2\\ 2rd=t(r-1)+d\\ d(2r-1)=t(r-1)\\ d=t(r-1)/(2r-1) $$

The PP algorithm will assign this number to one of the two sides; afterwards, just discard it.

---
Tags: algorithms, partitions
---