# Question
Title: What kind of problems in the world can be classified into PSPACE categories?
For instance can we categorize the following problems into NP-Hard ?

1. Is the Universe finite ?
2. Is there life after death ?
3. What came first, the chicken or the egg ?

My question is more around what can be modelled into the PSPACE category of problems ?

# Answer
I'm not sure if this question is meant seriously, but it actually relates to a common misunderstanding in computability.

Recall that a problem is formally captured as a formal language, i.e. a set of strings that are, intuitively, the "yes" instances of the problem. For example, $$SAT=\\{\langle \phi\rangle: \phi \text{ is a satisfiable Boolean formula}\\}$$ Then, a "solution" for the problem is a Turing machine that receives an encoding of the input $\phi$, and answers either "yes" or "no".

Now, often in "real life" you encounter problems that are just a "single" question, and therefore their language doesn't depend on the input, and is either universal or empty. For example all the questions you asked:

*"Is there life after death?"* -- This is not a well-defined question, since you need to formally define what is life and what is death, but assume for the sake of argument that you did define it somehow, then if the answer is "yes", then a TM that always says "yes" is correct. Otherwise, a TM that always says "no" is correct.

In this sense, the problem is trivial. It's certainly in P, but it's also way below P. It's regular. It's even "less" than regular.

The same goes for your two other questions.

The moral of this is the following important observation: complexity theory is relevant only as long as you don't fix the input. Once the input is fixed, then the answer is fixed, and the definition of complexity theory become redundant.

So in order to make these problems interesting, you need to formalize what the computationally-interesting parts are, and study them.
> 5 votes

---
Tags: np-hard, np, decision-problem
---


# Question
Title: Find a path with given weight and the minimum number of edges on a tree
Suppose given a positively-weighted tree $T=(V,E,w)$ and $k\in \mathbb{N}$, where $|V|=n$, the weight function $w:E\to\mathbb{N}$, and each node has degree at most $3$. How we can find a path on $T$ that has weight $k$ and the minimum number of edges in $O(n\log^2n)$?

I think we can use BFS because BFS give us the shortest path in term of number of edges.

# Answer
> 2 votes
This answer explains an algorithm that finds the minimum number of edges in $O(n\log n)$ time. With more bookkeeping, the path of weight $k$ with that minimum number of edges can also be found in $O(n\log n)$ time.

#### A Basic Idea: Numbers with Offset

If $S$ is a set of numbers and $d$ is a number, let $\mathcal N(S,d):=\\{s+d\mid s\in S\\}$. This notation/data structure is handy.

1. If the numbers in $S$ can be accessed directly, so are numbers in $N(S, d)$.
2. To denote $\\{s + d' | s\in \mathcal N(S,d)\\}$, we can use $\mathcal N(S, d+d')$.
3. It takes $O(\min(\\#(S\_1), \\#(S\_2))$ time to compute $S$ and $d$ such that $\mathcal N(S, d)= \mathcal N(S\_1, d\_1) \cup \mathcal N(S\_2, d\_2)$.

The data structure in the next section is an extension of this notation.

#### Map with Offsets (MO)

A MO $\mathcal M$ is a map from weights to lengths together with a weight offset $\mathcal M\_{\text w}$ and a length offset $\mathcal M\_{\text l}$. An entry in $\mathcal M$ (as a map), i.e., a key-value pair $(w,l)$ represent the knowledge that the minimum number of edges in a path of weight $w + \mathcal M\_{\text w}$ is $l+\mathcal M\_\text{l}$.

A MO with $s$ entries and another MO with $t$ entries can be merged into a MO with no more than $s+t$ entries, which shall represent the combined knowledge represented by the two former MOs, in $O(\min(s,t))$ time.

### A Depth-First Search Method $\text{compute\_min\_edges}$

Input: a binary tree rooted at $r$ with weight function $w$ and a global variable $min\\\_len$.
Output: a MO that describes the paths starting from $r$.
Side effect: $min\\\_len$ updated.
Procedure:

* If $r$ has no children, return $(0, 0, \\{0\to0\\})$.
* Otherwise, a path that passes $r$ either starts from $r$, connecting to a node in one of two subtrees, or has one endpoint in each of two subtrees, or consists of $r$ only.

1. for each child $c$ of $r$,
        1. **call this method** with the subtree rooted at $c$, which returns MO $M\_c$.
        2. Add $w(r,c)$ to ${(M\_c)}\_\text{w}$. Add 1 to ${(M\_c)}\_\text l$.
        3. If $\mathcal M$ maps weight $k-{(M\_c)}\_\text w$ to some length smaller than $min\\\_len-{(M\_c)}\_\text l$, reduce $min\\\_len$ to that length plus ${(M\_c)}\_\text l$.
    2. If there is only one child, let $M\_r$ be the only $M\_c$ obtained. Otherwise, there are two children $c1$ and $c2$:
        1. Find all pairs $((u\_{\text{w}}, u\_{\text{l}}), (v\_{\text{w}}, v\_{\text{l}}))$ such that $(u\_{\text{w}}, u\_{\text{l}})$ is an entry in $M\_{c1}$, $(v\_{\text{w}}, v\_{\text{l}})$ is an entry $M\_{c2}$, and $$u\_{\text{w}} + {(M\_{c1})}\_\text w+v\_{\text{w}} + {(M\_{c2})}\_\text w=k.$$ For each pair, if $u\_{\text{l}} + {(M\_{c1})}\_\text l+v\_{\text{l}} + {(M\_{c2})}\_\text l\<min\\\_len$, reduce $min\\\_len$ to the former.
        This step can be done in $O(\min(\\#M\_{c1},\\#M\_{c1}))$ time, where $\\#\mathcal M$ is the number of entries in MO $\mathcal M$.
        2. Merge $M\_{c1}$ and $M\_{c2}$ into $M\_r$.

Let $M\_r$ map ${-}(M\_r)\_{\text w}$ to ${-}(M\_r)\_{\text l}$.
Return $M\_r$.

### The Algorithm in $O(n\log n)$ Time

1. Initialize a global variable $min\\\_len=\infty$.
2. Call $\text{compute\_min\_edges}$ with the given weighted tree, after picking an arbitrary node as the root.
3. Return $min\\\_len$, which is the minimum number of edges in a path that has weight $k$.

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


# Question
Title: Tweaking Floyd-Warshall Algorithm to detect cycles
Cheers, I am trying to solve the problem of minimum length cycle in a graph, and I came across a solution that suggested that I should tweak the Floyd-Warshall algorithm to solve that. It stated that instead of setting `path[i][i] = 0` I should instead set `path[i][i] = INFINITY`, but I don't exactly understand why that is the case! I find that the main diagonal of the array used by Floyd-Warshall does not change, so how can it help me to see the path of the cycle? I understand that the generated array of the algorithm helps me find the shortest path of a pair. e.g. `path[i][j]` gives me the shortest path from *i* to *j* but, although the intuition stays the same, I see that nothing changes, and I can't take the desired result.

I even tried visualing the process, as seen here. I generated the graph below:

but as you can see, although the diagonal is initialized with infinity, it does not get changed, even though the graph clearly has cycles. Can anyone explain what am I missing?

# Answer
> 2 votes
If you let it, running the algorithm will produce, in `path[i][i]`, the length of the shortest path from node `i` to `i`. The length of the shortest cycle will be the smallest value on the diagonal. This requires

* updating `path[i][i]`, instead of skipping it, like that visualization does;
* initializing `path[i][i]` with the actual cost of going from that node to itself in one step: the cost of a self-loop, or if there is no self-loop, infinity.

Initializing the diagonal with 0s will leave it at all 0s, even when you don't skip updating it.

---
Tags: algorithms, graphs, greedy-algorithms, weighted-graphs
---


# Question
Title: Help with model answer for time complexity
Hi I cannot understand why the best case for line 3 is `n-1` and why it isnt just always `n`?

I tried to write this in python to understand when it would be `n-1` and the answer is always `n`. I am assuming that the loop counter in pseudo-code is evaluated one more time than the body is executed as is said in the Cormen book.

My thinking is that if the length of `n` is 1, the loop evaluation is still tested so regardless the answer would still be `n`, even if the loop body itself did not run.

```
Max(A)

1 MaxInt = A[1]
2 index = 2
3 while index ≤ n // Why is the best n-1 here?
4   if MaxInt < A[index]
5     MaxInt = A[index]
6   index = index+1
7 return MaxInt

```

I know it has to be something very simple but I cant seem to work it out as testing with 1 or 1000 the answer I get back for a count is always `n-1` (0, 999) and if I assume that the loops asserts a final time that is + 1, so `0 + 1 = 1`, which is `n` and `999 + 1 = 1000` which is `n`.

# Answer
The loop body will be executed $n - 1$ times because your `index` variable is initially set to $2$ rather than $1$. Hence, at the start of the loop body, the values for `index` are from the range $\\{2, 3, ..., n\\}$, which has $n - 1$ elements.
> 0 votes

# Answer
The number of iterations of the body of the loop is $\max(0,n-1)$.

The number of comparisons performed at line $3$ is $\max(1,n)$.

For both, best case and worst case are identical. If the answer sheet says otherwise, it is wrong.
> 0 votes

# Answer
Observe that after index is incremented from n to n+1 by line 6, the condition in line 3 is tested one last time (this condition evaluates to False because index=n+1, which is not \<=n) before the while loop exists.

Line 3 is executed for the first time when index = 2, and executed for the last time when index = n + 1. Hence, the total number of times line 3 is executed is n. Lines 4-6 are executed when index takes values 2 to n, and hence are executed n-1 times.
> 0 votes

---
Tags: time-complexity, big-o-notation
---


# Question
Title: DFA for the language of non-empty words that are no longer than $2^6$
I was given a question in Automata that I need to prove or disprove, and I thought about this language:

$$L = \\{w\in \\{0, 1\\}^\*\mid 1\le |w| \le 2^6\\}$$ Can you please help me to figure out if its minimal DFA contains only 6 states?

How can I get intuition about DFA sizes?

# Answer
Suppose the minimal DFA $(Q, \delta, q\_0, F)$ contains strictly less than $2^6$ states. Then there exists a state $q$ and two words $u$, $v$ such that $|u| \< |v| \leqslant 2^6$ and $\delta(q\_0, u) = \delta(q\_0, v) = q$.

Now, can you find a contradiction?
> 4 votes

---
Tags: computability, automata, finite-automata
---


# Question
Title: Similarities and differences between Unit and Bottom types?
I came across this recent Reddit thread, *Thoughts on Botton vs Unit Types*, but I don't understand what the similarities and differences are in regards to when you are creating a programming language.

If you are creating a programming language, why do you need both a Bottom *and* a Unit type (as defined in the thread).

> For the sake of this discussion, let's call the bottom type a type that has no members. NIL in Common Lisp, Nothing in Scala, never in TypeScript, Never in Swift. This type can be used to indicate the return type of a function that never returns (a function that only throws an exception, for example).
>
> Let's call the unit type a type that has a single member. NULL and NIL in Common Lisp (the symbol NIL not to be confused with the type NIL), () and () in Haskel, Unit and () in Scala, Void and () in Swift.

What exactly are the differences between the two as well?

In my PL, I currently just have a `void` type, which is meant to mean "nothing" or "empty" or "null" I would think, but this throws into question what I am doing. It seems I need to add another type, but not sure how it fits in. Because then in Rust you have the `None` type, I don't see why I couldn't just make that the `void` type as well. That sort of stuff. What are the similarities and differences, and why do you need both?

# Answer
> 7 votes
Jörg W Mittag gives an excellent answer. But I think it does miss the heart of the question. The quote says "For the sake of this discussion, let's call the bottom type a type that has no members." So while Jorg is right that the "the defining feature of a bottom type is not that it has no members" and that "it is perfectly possible for a bottom type to have members", we should also consider that it is perfectly possible for a bottom type to have no members.

Why would a type with no members be useful and why can't we just use the unit type for the same thing?

## Unit and None

So let's consider a language that has a type `Unit` with one member `unit` and a type `None` with no members. I'll assume that unit is not a member of "ordinary" types like `Int`. While we are at it, let's assume that the only members of `Int` are integers.

### A case for `Unit`

If we declare a function

```
fun foo() : T is .... end

```

where T is a type, that usually means that if a call returns, it returns a value that is a member of type T. Or to put it another way

> Any call to foo either returns a member of T or doesn't return

If T is Unit, that means that any call to foo will return (if it returns) a member of Unit, i.e. unit. Since the value returned is entirely predictable, there is no point writing say

```
val x : Unit = foo()

```

since the value of x is a forgone conclusion. We might as well just write

```
foo()

```

`Unit` is playing the role that void plays in C or Java. The only difference is that we are treating Unit as a type, whereas in C and Java void is not really a type.

So what about None, why not use that instead of Unit for our analog of void?

Consider

```
fun bar() : None is ... end

```

From our understanding of what this means, we see that

> Any call to bar either returns a member of None or doesn't return

But since None has no members, this is equivalent to

> No call to bar returns.

That doesn't sound like void. `None` is not a suitable analog for void, but `Unit` is.

### Three cases for `None`

Is there any point to having `None`?

Here are three arguments for having a `None` type. But note that these arguments don't really rest on `None` having no members, but rather that it is a subtype of all other types in the language, i.e. that it is a bottom type.

#### `None` as a return type

A function that returns `None` sounds pretty useless. But it isn't completely useless. Suppose I have a function that always throws an exception, then I can write

```
fun unreachable() : None is
    throw new AssertionError("Unreacble code reached")
end

```

This can be useful for defensive programming. E.g.

```
fun partial(a : Int) : Int is
    if a > 0
        return 1
    else if a < 0
        return -1
    else
        return unreachable()
    end
end

```

This should type-check since None is a subtype of Int.

What if we had used used Unit for the return type of `unreachable`? The subroutine above would not type check. Since Unit is not a subtype of Int). So we'd have to rewrite the else part as, for example

```
 unreachable()
 return 42

```

which looks rather arbitrary.

Here is a more compelling example. Here we have a generic function

```
fun assertWithResult<T>( b : Bool, v : T, m : String := "Assertion failed" ) : T is
    if b
        return v
    else
        return (throw new AssertionError( m ) )
    end
 end

```

For this to typecheck, we need for `throw new AssertionError( m )` to have the bottom type. If we rewrite the code as

```
else
    throw new AssertionError( m )
end

```

The language implementation will (I'd hope) complain about the missing `return`. We can't rewrite it as

```
else
    throw new AssertionError( m )
    return ...
end

```

since there is nothing we can write in the place of .... `null` is not the answer because I'm supposing `null` is not a member of `Int`, for example. unit has the same problem. I'll consider the case where there is a null value that's in every type later.

#### `None` as the type of something that isn't there.

Suppose our language has lists. (These are lists of values, as in Haskell -- not lists of locations as in Python.)

A reasonable rule for list catenation is that the type of `xs ++ ys` is `List[T|U]` where the type of `xs` is List\[T\], the type of `ys` is `List[U]` and `T|U` is the smallest type that contains the union of the members of `T` and `U`.

What is the type of the empty list constant `[]`. If it is `List[Unit]`, then `[1,2,3] ++ []` will have type `List[Int|Unit]`, which is probably not what you want. But if the type of the empty list constant is `List[None]` we have `List[Int|None]` which is `List[Int]`.

#### Intersection types

Let's introduce multiple inheritance into our language. Given two interfaces `I` and `J` we can write `I&J` for the combination of both. I.e. the members or `I&J` are exactly the members of `I` intersected with the members of `J`. Why not allow intersection types for any two types? Now what is `Int&Unit`? Again `None` comes to the rescue.

## Error without Unit or None

In Haskell, there is bottom type that has one member, which represents an error value. This error value is also a member of all other types.

The arguments above don't require that the bottom type have no members, just that it is a bottom type. (This is the point Jörg made.)

Imagine a language where we have a bottom type `Error` that contains one value, call it `err` that represents an error; and where `err` is a member of all types. `err` is the value of expressions that have errors, e.g., the value of `1/0` might be `err` and the value of `1/0 = 1/0` would also be `err`. (In the literature `err` is often written $\bot$ and called "bottom", but I'm going to avoid that terminology so that the term bottom isn't used with two technical meanings.) It follows that `None` is not a type in this language. (Int and Unit are also ruled out, but let's define a new type `Int?` that contains only integers and `err`.) We'll say that a function that does not return a value implicitly returns `err`. For example

```
fun incr( x : in out Int?) : Error is x := x+1 end

```

is a reasonable function. (The implementation won't complain about a missing return, because `return err` is implicit.) It always returns `err` but, if we don't use the value, this is not an issue.

Now consider

```
fun baz() : Int?
    var y : Int? := 0
    if <<Something>>
        return 1
    else
        return incr(z)
end fun

```

This will type-check since `Error` is a subtype of `Int?`. Personally, I'd rather that it not type-check. I'd rather find out about the error before run time. So even if my bottom type contains an error value, I'd still like to have a unit type (`Unit?`) that additionally contains a non-error value. My personal feelings aside, this is a possible language design.

We can do without None by making the value of `throw` be `err`.

In short, whether or not you have an error value that is a member of every type or not, is largely orthogonal to the other issues such as whether you want `unit` and `Unit`. But it makes a difference to whether your bottom type is empty or not.

## Is `Error` better than `None`?

One argument for all types having an error value holds for languages with lazyness. Suppose we have a type Int\*Int that consist of pairs of Integers. In a lazy language `(i, a[i])` (where `i` is an integer variable and `a` is a list of integers) must have a value, even if `i` is an out of bounds index. That's because `first( (i, a[i] )` would have no error at compile or run time. But no pair of integers makes sense if `i` is out of bounds. The solution is to have `Int?` instead of `Int`. (You could have both, but the type of `a[i]` or any integer expression that might contain an error should be `Int?`, not `Int`.

A very pragmatic reason to have an error value is for uninitialized locations in an imperative language. Again you could have both `Int?` and `Int`, but locations of type `Int` would have to be initialized to integer. This is sort of the approach Java takes. Locations of type `int` are initialized to 0 by default. But location of type `Integer` are initialized to `null` by default. Granted, `null` is not the same as `err` since `null` is a first class value.

There are theoretical reasons for all type having to be inhibited by an error value. For example in Dana Scott's domain theory all types have a bottom value and this is important for showing that all well-typed functions have a meaning.

## `Null` without `Unit` or `None`

Finally, we might consider a design where every type (except `None` and `Error`) has some particular non-error value, call it "null". Think of Java with the primitive types int, bool, double, etc. expunged. Now we can have a type `Null` that contains only `null`. (Or, if all inhabited types should have an err value, we can have a type Null? that contains only `null` and err.) I don't think there is much of a case for a `Unit` (or `Unit?` type containing both `unit` and `null`. Do we still need `None`? I think none of my arguments above for `None` are strong in this case. We can ditch the `None` type and then `Null` (or `Error` if you have `err` as value and `Error` as type) will be the bottom type and also the stand in for void.

## Appendix

Summary of types mentioned above

* `None` no members, subtype of everything
* `Error` contains only `err`.
* `Null` contains only `null`.
* `Null?` contains only null and err.
* `Unit` contains only `unit`.
* `Unit?` contains only `unit` and `err`.
* `Int` contains only integers.
* `Int?` contains only integers and `err`.
* `List[None]` contains only the empty list.
* `List[Int]` contains only lists all of whose members are integers. Supertype of `List[None]`.
* `T | U` the smallest type that contains all members of `T` and all members of `U`.
* `T & U` a type containing only values that are members of both `T` and `U`.

# Answer
> 3 votes
I think you are conflating several different issues, in addition to conflating concepts from mathematical type theory with concepts from practical, "real-world" programming language design.

In practical programming language design, the defining feature of a bottom type is not that it has no members. The defining feature of a bottom type is that it is a subtype of every (other) type, i.e. that it sits at the "bottom" of the type hierarchy. (The opposite is a *top type*.)

A *unit type* is a type which has only a single member.

It is perfectly possible for a bottom type to have members. For example, in Scala, `Null` is the bottom type for all reference types (i.e. it is the bottom type for the half of the type hierarchy which branches off of `AnyRef`) but it has a single member, `null`. (Which, technically, also makes it a *unit type*.)

In mathematical type theory, because of the fact that a unit type has only a single member, the unit type and the unit value convey no information. As a result, also, all unit types and unit values are isomorphic, so there is only *the* unit type and *the* unit value.

But this is not necessarily true for practical programming language design. There may be legitimate reasons to want to distinguish between different unit types or to have multiple bottom types for different parts of the type hierarchy, or to have bottom types have a member.

From a programming language perspective, there are good reasons to want to distinguish between a subroutine which does not return a useful value and a subroutine which does not return at all. I.e. a subroutine which prints something and a subroutine which runs into an infinite loop are very much *not* the same thing, and thus it makes sense for them to have different types.

Some programming languages don't care about one or both of those. E.g. Pascal does not concern itself with subroutines that do not return. It *does*, however, distinguish between subroutines which return a useful value and subroutines that don't. In Pascal, this is not handled via different return types but rather by having two different kinds of subroutines: `FUNCTION`s return a value, `PROCEDURE`s don't.

Some programming languages have a special type annotation which is not actually a type itself which designates a subroutine as not returning a useful value. E.g. in Java, `void` is not a type, but a special keyword denoting the absence of a useful return type.

Many of these programming languages also have the distinction between *expressions* and *statements* where expressions evaluate to a value and have a type, and statements only have side-effects and don't have a type.

Some programming languages, like Scala, only have expressions, and only have subroutines which evaluate to a value. However, Scala is still an impure, partial programming language, so you can have expressions and subroutines which don't evaluate to a useful value and ones that don't terminate.

In Scala, all of these need to have a type, and *IFF* they return, they also need to return *something*. They can't just return nothing like in C or Java.

For something which returns no useful value, it makes sense that this value is the unit value and the type is the unit type. *In general*, there is no need to have multiple "no useful values" and there is no need to have multiple "no useful types". So, the unit type and the unit value are a sensible choice *for that reason alone*, regardless of the connection between programming and logic. But of course, there are good reasons based on the Curry-Howard-Isomorphism, Girard-Reynolds-Isomorphism, etc. as well why that should be the case.

Likewise, for something which never returns, it makes sense to use a type that has no members. This makes it clear that the method never returns, since if it were to return, it would need to return a value, which it can't, because there is no value of that type.

It also makes sense for this type to be the subtype of every other type: if the subroutine never returns, then I obviously use its return value everywhere where a value of any type is expected, because I know this value will never *actually* be consumed since the computation will never progress any further. Since I can pass this value that can never exist anywhere for any type, this means that the value must be a member of every type, and one of the ways to achieve this is to make its type the subtype of every type.

As to your question

> why do you need both?

Clearly, the answer is "You don't", since there are successful programming languages like C, C++, Java, C#, which don't have both unit types and bottom types, and even successful programming languages like ECMAScript, PHP, Python, Perl, Ruby, Lua, and many others which don't even have types at all.

*IFF* you even care at all about subroutines which don't return and/or subroutines which return no useful value, *AND IFF* you want to distinguish between the two, *AND IFF* you want to use the type system for that distinction (as opposed to, say, two different kinds of subroutines like Pascal does), *THEN* you will typically end up with something which looks like a bottom type, something which looks like a unit type, and something which looks like a unit value.

But if you don't care about any of that, then you don't need both or even either.

---
Tags: programming-languages, type-theory
---


# Question
Title: NP-completeness of some problems on assigning candidates to departments
Suppose we have $n$ candidates from a candidate pool $\\{1,2, .., n\\}$ and we have $m$ departments. A candidate can be assigned to at most one department (so not being assigned is possible). Each department $d$ is considering candidates in $C\_d \subseteq \\{1, 2, ... n\\}$ (with possible overlap between departments), and that each department $d$ *must* hire exactly $r\_d$ of the $|C\_d|$ candidates it is considering. The problem is to find an assignment of candidates to departments.

The question: Is this a NP-complete problem?

My *instinct* is yes- it is clearly NP at least.

I am trying to look for a suitable NP-reduction; the NP-complete problems I am familiar with and expected to use are 3-SAT, Independence Set (finding a maximal independent subset of vertices of a graph), Vertex Cover (finding a minimal vertex cover of a graph), Partition (partitioning a multiset into two subsets with equal sum) and 3-Coloring.

The most promising is 3-SAT I think, where I can make each literal a candidate and each clause a department.

So for instance if I have $(x\_1 \lor \neg x\_2 \lor x\_3) \land (\neg x\_4 \lor x\_5)$

Then I will have $5$ candidates, $2$ departments each requiring one candidate and the first department, for instance looking from the candidate pool $\\{x\_1, x\_3\\}$ (not $x\_2$ since the first clause has $\neg x\_2$). This has two big problems in that I'm not sure what to do with the $\neg$ literals, and these may have overlap between clauses (which would cause a candidate being assigned to more than one apartment).

But then I'm not sure how I would use the other problems.

# Answer
> 2 votes
Your problem is not $NP$-complete because it is not a decision problem and hence it is not even in $NP$. Moreover your problem is not $NP$-hard, unless $P=NP$. In fact, your problem can be solved in polynomial time.

To do so, create a bipartite graph $G=(U+V, E)$ where $U=\\{1,\dots,n\\}$ represents candidates and $V$ contains $r\_d$ pairs $(d, 1), \dots, (d, r\_d)$ for each department $d=1,\dots, m$. Intuitively $(d, j)$ represents the $j$-th position to be filled by department $d$. Finally, $E$ contains the edge $(i, (d,j))$ if and only if $i \in C\_d$. (Notice that the size of $G$ is polynomial in the size of the instance since we can assume w.l.o.g. that $r\_d \le |C\_d| \le n$).

Your problem is now equivalent to finding a $V$-perfect matching of $G$. This problem can be solved in polynomial-time (for example by adding a "source" vertex $s$ adjacent to all vertices in $U$, a "target" vertex $t$ adjacent to all vertex in $V$, setting all edges capacities to $1$, and trying to push $\sum\_{d=1}^m r\_d$ units of flow from $s$ to $t$).

---
Tags: algorithms, complexity-theory, np-complete, np-hard, decision-problem
---


# Question
Title: Why DFA's configuration space is finite and PDA configuration space is infinite?
I read from this post the term configuration space. I don't know the meaning of *configuration space*.

What is the exactly meaning of *configuration space?*

And why DFA's configuration space is finite and PDA's configuration space is infinite? Give one example for both the cases then it could be better for me.

# Answer
> 1 votes
### A Configuration just Means "State"

A configuration of a machine $M$ is a snapshot of the machine at a particular moment during a computational process by the machine. It includes all setting/details of the machine. It means, basically, the "state" of a machine, where "state" is in the usual sense of plain English as in "the state of a game", "the state of a kitchen" or "the state of an electrical motor". (In fact, had we not used "state" in the definition of a DFA or a PDA, we would have preferred to use "state" instead of "configuration"!)

A configuration of a machine at a particular moment determines its future behavior completely when further input are fed to that machine.

The configuration space of a machine $M$ means all possible configurations of $M$, i.e., configurations of $M$ at all possible moments.

More formally,

* given a DFA $D=(Q, \Sigma, \delta, q\_0, F)$, a configuration of $D$ is an element in $Q$, that could be associated to a particular moment of $D$. There are $|Q|$ possible configurations of $D$.
* given a PDA $P=(Q, \Sigma, \Gamma, \delta, q\_{0}, Z, F)$, a configuration of $P$ is an ordered pair of an element in $Q$ and its stack (with finitely many stack symbols in it), that could be associated to a particular moment of a computation by $P$. Although the content of the stack of $P$ is finite, there are infinitely many possibilities for the content, just as there are infinitely many natural numbers. So there are $|Q|\times\infty=\infty$ possible configurations of $P$.

* given a Turing machine $T=(Q,\Gamma,b,\Sigma,\delta,q\_{0},F)$, a configuration of $T$ is an ordered triple of an element in $Q$ and the tape with the symbols on it and the head position, that could be a snapshot of $T$ at a particular moment while $T$ is running. There are infinitely many configurations for $T$.

Note that we could have included $\delta$, $q\_0$, etc. in the definition of a configuration of a machine. However, since these elements do not change while a machine runs, there is little benefit to include them.

Also note that the (remaining) input is NOT part of a configuration of a machine, although the (remaining) input is a part of a snapshot (instantaneous description) of a computation made by the machine.

### What is a Machine?

What does it mean by a DFA, a PDA or a Turing machine as a machine?

Take PDA as an example. The PDA machine refers to "Finite control unit" and "Stack" illustrated in the image below, excluding the "Input tape".

A simple mental model for a PDA is a finite state automaton plus a stack with unbounded capacity. A configuration for a PDA is the current state of its finite-state-automaton part and the current stack together with all its content. Readers are encouraged to visualize a running PDA by clicking button "Next Step" on this page, where the configuration of a PDA can be seen as the stack on the left-hand side together with the current state indicated by the red circle on the right-hand side.

Readers can also visualize a running DFA machine by various tools, such as this page. You can enter a regular expression such as `(a+b)*aaa(a+b)*`, which is for words with triple `a`s. Select "DFA". Click "Creat automaton". Then you can see a DFA created at its section "Transition graph". You can use section "Simulate automaton" to run that DFA. A configuration of that DFA is indicated by the state in red.

---
Tags: finite-automata, pushdown-automata
---


# Question
Title: A recursive relation for the number of well formed nested parentheses of length $n$ and depth $\leq d$
Consider a function $C(n, d)$ which counts the number of well formed, i.e, balanced, parenthetical 'words' of length $n$ and maximal nested depth $\leq d$.

That is, $(())$ has $n = 4, d = 2$. $()((())())$ has $n = 10, d = 3$ and so on.

$C(n, d)$ counts all well formed strings above (i.e, $($ and $)$ are balanced), of length *exactly* $n$ and depth *at most* $d$ (that is, smaller depths are allowed).

There should be a recursive expression for $C(n, d)$.

The base cases are easy enough:

$C(n, d) = 0$ if $n$ is odd regardless.

$C(n, d) = 0$ if $d = 0$ but $n\> 0$

$C(n, d) = 1$ if $d = n= 0$ (the empty string)

Now for the recursive step.

I've been thinking about this but there are a lot of overlap which makes things difficult.

For instance, I first guessed $\sum\_{i}\sum\_j C(n- i, d-j)C(i, j)$ That is, you mixing all strings of length $i$ with strings of length $n-i$ should give you strings of length $n$. I think the depth in general will remain $\leq d$ without problems. But the problem with this approach is that I'm pretty sure there will be plenty of double/extra counting of the same strings more than once.

I have a few other candidates but again I think they largely double count in general.

I was also thinking if I could express it solely in terms of $C(n-2, d-1)$ as ${n-2 \choose 2}C(n-2, d-2)$ (placing $(, )$ at any positions in an $n-2$ string) but then this misses out on potential $d$ depth strings. But doing ${n-2 \choose 2}C(n-2, d)$ might inculcate depth of $d$.

# Answer
> 2 votes
Suppose that $w$ is a well-formed parenthetical word of depth at most $d$. Then either $w = \epsilon$, or $d \> 0$ and $w = (x)y$, where $x$ is a parenthetical word of depth at most $d-1$, and $y$ is a parenthetical word of depth at most $d$; furthermore, the decomposition is unique.

---
Tags: algorithms, recurrence-relation, recursion
---


# Question
Title: Prove that DIFFERENTDFA, PDA {<M1, M2> | Where M1 is a DFA and M2 is a PDA where L(M1)≠L(M2)} is undecidable
I am absolutely stumped on this one. I am unsure of how to start with this one. I have thought to reducing the problem to Atm. Another thought I have had is to convert M1 to a PDA and use the complement of EQPDA to solve this but I am honestly really unsure. Any tips that could point me in the right direction or solutions to this or similar problems?

Here is one attempt to solve this problem:
DifferentPDADFA = {\<M1, M2\> | M1 is a PDA and M2 is a PDA, L(M1) != L(M2)}
Write a turing machine, C, to decide the language of M1
Write a turing machine, D, to decide the language of M2
ALLCFG = {\<G, w\> | G is a CFG, L(G)=Σ\*}
ALLCFG' = {\<G, w\> | G is a CFG, L(G) != Σ\*}
Since ALLCFG is known to be undecidable, its complement ALLCFG' is also undeciable.
Use turing machine A, which simulates ALLCFG'.
AllCFG' \<ₘ L
F -\> Input \<D, P, w\>:
1. Construct Turing Machine Y to simulate PDA P
Y\<P, w\>:
On Input X:
1. Ignore Input X
2. Convert our PDA P to a CFG G (page 147)
3. Simulate A with \<G, w\> and return what A returns.
2. Construct Turing Machine Z to simulate DFA D
Z\<D, w\>:
On Input X:
1. Ignore Input X, accept.

Output \<Z, Y\>

Since Z ignores all inputs the language accepted by L(Z) is always Σ\*.
If A accepts \<G, w\> then L(Y) != Σ\*, therefore L(Y) != L(Z).
If A rejects \<G, w\> then L(Y) must be Σ\*, therefore L(Y) = L(Z).
Therefore A accepting \<G, w\> \<=\> L(Y) != L(Z)
Since we know that ALLCFG' is undeciable, L is also undeciable.

# Answer
> 0 votes
Let $Different\_{DFA,PDA} = \\{\<M\_1,M\_2\> \vert \ M\_1 \text{ is a DFA and } M\_2 \text{ is a PDA where } L(M\_1) \neq L(M\_2)\\}$, we want to show that this language is undecidable

Let $ALL\_\text{CFG} = \\{\<G\> | \text{ G is a CFG and } L(G) = Σ^\*\\}$, as we know this language is undecidable, hence its complement, ${\overline{ALL}}\_\text{CFG} = \\{\<G\> | \text{ G is a CFG and } L(G) \neq Σ^\*\\}$, is also undecidable

We will reduce ${\overline{ALL}}\_\text{CFG}$ to $Different\_{DFA,PDA}$, hence showing that the latter is undecidable

The following machine $F$ computes the reduction $f$

$F$ = “On input :

1. Convert $G$ into an equivalent $PDA$ $P$
2. Let $D$ be the $DFA$ recognising the language $\Sigma^\*$
3. output $\<D,P\>$

If $L(G) \neq \Sigma^\*$, then $L(P) \neq L(D)$, and so $\<D,P\> \in Different\_{DFA,PDA}$

If $L(G) = \Sigma^\*$, then $L(P) = L(D)$, and so $\<D,P\> \notin Different\_{DFA,PDA}$

---
Tags: reductions, undecidability, theory, mapreduce
---


# Question
Title: Converting Deterministic Finite Automata to Regular Expression
I am reading Michael Sipser's "Theory of Computation". In one of the proofs he talks about converting "DFA to Regular Expression" and he talks about "GNFAs". I understand one method of converting DFA to Regular Expression that is using Arden's Theorem. I assume GNFA is a medium between DFA and Regular Expression. Can someone explain the GNFA method? and also would i be okay not knowing it and only knowing the Arden Theorem method?

# Answer
> 2 votes
Jacques Sakarovitch studies the outcome of the various algorithms. See his paper *The Language, the Expression, and the (Small) Automaton* (CIAA 2005. LNCS 3845), where some results are summarized that are obtained in his book on automata theory. https://doi.org/10.1007/11605157\_2

First one should note that the expression (and its size) highly depends on the *order* of handling the nodes, and not on the method.

When following strict methods (no additional tricks and shortcuts) the results seem syntactically equal. As far as I understand this result (from the paper) compares state elimination and Arden's solving equations.

> Proposition 1. The state elimination method and the solution (by Gaussian elimination) of a system of linear equations taken from an automaton give the same regular expression (assuming that the same order in elimination is used in both cases).

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


# Question
Title: Performant way to find all leaf nodes in a undirected graph
I am trying to find a better way to find all leaf nodes in my undirected waypoint graph.

This is how I define a leaf node:

A leaf node is a node that is never part of a cycle and so has to meet one of these two criteria:

1. It has only one connection

Or

2. The node's total connections minus the total leaves connected to said node is less than 2

Here is a visual example:

My current approach doesn't feel too efficient, I loop through all nodes and mark those nodes that meet criteria 1.

I loop again and again and mark every node that meets criteria 2. I do this until no further nodes are marked - then I exit the function.

Here is the logic:

```
int count;
do
{
    count = 0;
    foreach (node in allNodes)
    {
        //leaves is a hashset of marked nodes
        if (leaves.Contains(node)) // already marked as leaf
            continue;

        if (IsLeaf(node))
        {
            leaves.Add(nodes);
            count = 1;
        }
    }
} while (count > 0);

```

My `IsLeaf` function has:

```
bool IsLeaf(node)
{
    total = node.Connections;

    // only has 1 or less connections, so it must be a leaf
    if (total < 2)
        return true;

    //count all leaves connected to the node
    totalLeaves = 0;
    foreach (segment in node)
    {
        node2 = segment.GetOtherNode();

        if (_leaves.Contains(node2))
            totalLeaves ++;
    }

    //A node is a leaf when it has less than 2 connections to non-leaf nodes
    return (total - totalLeaves ) < 2;
}

```

I am wondering if there is a more performant way to go about this other than looping all the nodes over and over until all leaves have been found?

# Answer
You can compute the set of "leaves" in linear time. I will color the vertices of $G$ as either white or black. Initially all vertices are white. At the end of the algorithm the leaves will be exactly the vertices colored black. I will additionally associate, to each vertex $v$, a quantity $w(v)$ representing its "white degree", i.e., the current number of white neighbors of $v$. Initially each $w(v)$ is initialized to the degree of $v$. Finally, we keep a "bucket" (e.g., a list) $B$ containing all white vertices $v$ such that $w(v) \le 1$ (this is initialized to contain all vertices with degree $0$ or $1$).

The algorithm repeats the following until $B$ is empty. It extracts one arbitrary vertex $v$ from $B$, and colors $v$ black. Then, it examines each edge $(v,u)$ incident to $v$ and decreases $w(u)$ by $1$. If $u$ is white and $w(u)$ is now exactly $1$ (i.e., the value of $w(v)$ just went from $2$ to $1$), it also adds $u$ to $B$.

To upper bound the time complexity notice that, except for constant multiplicative and additive factors, it is upper bounded by the number of vertices of $G$ (to initialize $w(\cdot)$ and $B$, and to account for the time spent extracting and inserting each vertex into $B$, if needed) plus the overall number of times the edges $(v,u)$ are examined. This latter quantity can be at most twice the number of edges of $G$.

Edit: (the complement of) what you want has a name. You are interested in the vertices not in the $2$-core of $G$. Wikipedia even has a similar algorithm to the one above.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Largest number of disjoint paths of length $k$ and maximum reward in a tree
Consider exercise 23(c) of chapter "Greedy Algorithms", *Algorithms* by Jeff Erickson.

> Given a tree $T=(V,E)$ in which each node has a reward, and $k\in\mathbb{N}$, our goal is to find a set $S$ of paths, each having length exactly $k$, such that the paths in $S$ are pairwise vertex-disjoint and and the overall reward (defined as the sum of the rewards of all the nodes that belong to some path in $S$) is maximized. (note that a path cannot contains two children of the same node)

According to this link, if the weights were unit then the problem above could be solved by a greedy approach. However, a greedy algorithm does not always return the optimal reward for the current situation.

How can we solve the problem above using dynamic programing?

# Answer
Given a vertex $v$, let $r(v)$ denote $v$'s rewards, let $C\_v$ be the set of $v$'s children, and let $T\_v$ denote the subtree of $T$ rooted in $v$. Given a vertex $x$ at depth $d\_T(x) \ge k$ in $T$, we denote by $x\_i$ the $i$-th ancestor of $x$ in $T$ (in particular $x\_0=x$). Define $C\_T(x) =\left( \bigcup\_{i=0,\dots,d\_T(x)} C(x\_i) \right) \setminus \\{ x\_0, \dots, x\_{d\_T(x)} \\}$.

Define $OPT\[v\]$ as the maximum revenue that can be obtained when the instance consists of $T\_v$. Let $r$ be the root of $T$. We observe the following: if there is an optimal set of paths $S$ that is not empty, and $x$ is the lower endpoint of a path in $S$ that has minimum depth in $T$, then: $$ OPT\[r\] = \sum\_{i=0}^k r(x\_i) + \sum\_{u \in C\_T(x)} OPT\[u\]. $$

This immediately yields a dynamic programming algorithm. Indeed, given a generic vertex $v$ you can consider the set $X(v)$ of all vertices $x$ at distance at least $k$ from $v$ in $T\_v$. You have:

$$ OPT\[v\] = \max \left\\{0, \max\_{x \in X(v)} \left\\{ \sum\_{i=0}^k r(x\_i) + \sum\_{u \in C\_{T\_v}(x)} OPT\[u\] \right\\} \right\\}. $$ Where a $\max$ over an empty set is $0$, and the outer $\max$ accounts for empty optimal solutions. (The outer max can be dropped if the rewards are always non-negative, which seems natural).

Since there are $n$ subproblems and the solution to each subproblem $OPT\[v\]$ can be found in time $O(n)$ (once the values $OPT\[u\]$ are known), the overall running time is $O(n^2)$.
> 2 votes

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


# Question
Title: Converting Regular Expression to Finite Automata
I am studying "Theory of Computation" by Michael Sipser. I am studying the section where he teaches how to convert "RE to FA". He uses empty transitions for union, concat and star, but that is very getting very confusing for me

But i found this another method here: https://www.codingninjas.com/codestudio/library/conversion-of-regular-expressions-to-finite-automata

This method does not use empty transitions for union, concat and star.

I am more biased towards the second method, without the empty transitions for regular opoerations.

Do both of the methods yield the same result? that is accept the language described by the RE?

# Answer
> 2 votes
The construction that you show from the book of Sipser is known as Thompson’s construction, building a nondeterministic automaton with $\varepsilon$-transitions. Those empty transitions can be removed by a simple algorithm, and then the automaton can be determinized, if needed. (But that can lead to an explosion in the number of states.)

Sometimes determinization is not needed at al. One can for instance use the general automaton for pattern matching.

There is a slightly more invoved algorithm that avoids $\varepsilon$-transitions. It is called Glushkov Construction, and it carefully considers incoming and outgoing transitions from initial and final states. Hence it is more involved than Thompson's.

The website algorithm you cite is nice for intuition, but quite useless for actual implementation. I cannot see what we should do with the expression $a^\*b^\*$. It cannot be two letters $a$ and $b$ on the same state, can it?

---
Tags: regular-languages, automata, finite-automata, regular-expressions, theory
---


title: Determine the language of the NPDA

text:
# Question
Title: Determine the language of the NPDA
I have to write the language of the below $NPDA$(Non-Deterministic Push Down Automata).

I think that from $q\_0$ to $q\_1$ and then $q\_2$, we are actually building the below all the strings of $0$'s and $1$'s of the form $a^nb^n$ with the lenght at least 2.

But there is also a transition from $q\_2$ to $q\_0$, which makes a cycle, and it just read a $1$ from input string. For example these strings are accepted by this machine, and the point is that in all of them the last character is $0$.

1100 1 10 1 1100

111000 1 1100 1 10

1100

But, unfortunatly I don't know how to write its language accuratly. My idea was to write something like the below language:

$L = \\{ w(1^n) z (0^n) | w ∈ L \\}$ and $z ∊ \\{1,ɛ \\}$

But it is not correct. I will be grateful for any help.

# Answer
Consider $L = \\{1^n0^n\mid n\>0\\}$. It seems that the language of your PDA is $L(1L)^\*$.

It is not exactly the way you wanted, but I think it is an accurate and short way to write it.

You could be a bit more verbose and write it as:

$$\\{1^{n\_1}0^{n\_1}11^{n\_2}0^{n\_2}1…11^{n\_k}0^{n\_k}\mid k \geqslant 1 \wedge \forall i\in \\{1, …, k\\}, n\_i \> 0\\}$$
> 2 votes

---
Tags: pushdown-automata
---


# Question
Title: Dual of a graph where the faces are unclear
To get the dual of a planar graph, each of the faces becomes a vertex. And then, two vertices in the dual graph are connected if they share a common face. My question is about planar graphs that have disconnected components. It's unclear to me how to define a face for these. As a simple example, consider the graph below.

What is the dual graph of this one and how many "faces" does it have?

# Answer
> 1 votes
First of all, the dual of a planar graph is only defined with respect to a planar embedding; for some planar graphs, every embedding gives the same dual graph (as a graph), but this is not always the case.

Given a planar embedding of a planar graph, a *face* is a connected component of the plane with the edges of the graph removed. In your case, after removing the edges, the plane remains connected, and so there is a single face. The dual of your graph thus consists of a single vertex with three self-loops.

The same dual graph would be obtained if instead of your graph we take a matching, a star with three edges, or a path of three edges. This seems to contradict the well-known result that the dual of the dual is the original graph. However, this result only holds for connected graphs (although both the star and the path are connected, the corresponding planar embeddings are different). For more on this issue, see this question.

---
Tags: graphs, duality
---


# Question
Title: Are there invariants in text processing problems?
I have read that when programming it is good to identify relations -- invariants -- that should hold true throughout the program, and it is good to insert assertions throughout the code to check that the invariants are maintained.

I can see how programs that involve mathematics can have invariants, i.e., some mathematical relation must be true throughout the code's manipulations.

Are there invariants in non-mathematical problems?

Are there invariants in text processing programs?

Suppose the processing problem is to transform one terminology to another. Are there invariants in this problem?

Let's take a specific example. The first vocabulary has an item TYPE whose value is A, B, C, or D. The second vocabulary has an item airIndicator whose value is Civil, Joint, Military, or Private. After reading the documentation it is determined that the mapping is as follows:

```
A maps to Civil.
B maps to Joint.
C maps to Military.
D has a different meaning than Private so whenever D is encountered an error should be generated.

```

Here is pseudocode to do the mapping:

```
if TYPE = 'A' then "Civil"
else if TYPE = 'B' then "Joint"
else if TYPE = 'C' then "Military"
else if TYPE = 'D' then error("No mapping for D")
else error("Invalid TYPE value")

```

Is there an invariant in that mapping?

When you write text processing programs do you identify invariants and then insert assertions throughout your code to check that the invariants are maintained?

# Answer
> 3 votes
Yes. One can find invariants in any program. The notion is well-defined and meaningful in any program (whether it is useful in practice is a different question).

Normally identifying invariants is most useful whenever there are loops (or recursion). Straight-line code is usually easy to reason about, so there is usually no need to identify invariants, but when we have loops (or recursion), that's more challenging to reason about and so it can sometimes be more useful to identify invariants.

To learn more, see https://en.wikipedia.org/wiki/Loop\_invariant, , and https://en.wikipedia.org/wiki/Hoare\_logic.

---
Tags: algorithms, formal-methods, software-verification, loop-invariants, software-testing
---


# Question
Title: Distribution maximizing ratio of expected maximum over the mean
I’m looking for a distribution that is non-negative, or has good tail bounds (so non-negative with high probability) and maximizes the ratio between the expected maximum of $n$ iid samples and the mean.

That is, if $X\_1,\ldots,X\_n$ are iid samples from the distribution, $Y = \max(X\_1,\ldots,X\_n)$, and $X$ is another sample, then I want to maximize $$\frac{E\[Y\]}{E\[X\]}.$$

For instance, for a normal distribution $N(\mu,\sigma^2)$, $E\[Y\]$ is $\Theta(\sigma\sqrt{\log n})$, however for the samples to be non-negative with high probability, because of the tail bound on normal distribution, $\mu$ should grow faster than $\sigma$, so $\frac{E\[Y\]}{ E\[X\]}$ will be bounded by $O(\sqrt{\log n})$.

On the other hand, if I’m not mistaken, we can have $\frac{E\[Y\]}{ E\[X\]} = \Theta(\frac{\log n}{\log\log n})$ through binomials, a balls and bins problem setting. However I’m not sure if this is the largest that $\frac{E\[Y\]}{ E\[X\]}$ can be.

# Answer
For non-negative random variables, the answer is $\Theta(n)$.

Notice that $Y \leq X\_1 + \cdots + X\_n$, and so $E\[Y\] \leq n E\[X\]$.

In the other direction, consider the following random variable: $X = 1$ w.p. $1 - 1/n$, and $X = n$ otherwise. On the one hand, $E\[X\] = 1 - 1/n + n/n \approx 2$. On the other hand, $\Pr\[Y = 1\] = (1-1/n)^n \approx 1/e$, and so $E\[Y\] \approx 1/e + (1-1/e) n \approx (1-1/e) n$. In total, $E\[Y\]/E\[X\] \approx \frac{e-1}{2e} n$.
> 1 votes

---
Tags: probability-theory, statistics, balls-and-bins
---


# Question
Title: $\mathrm{MON} = \{\langle M\rangle : \text{$M$ is monotone}\}$ is undecidable
That's a question from a home assignment by T. Zur:

> Say that a Turing machine $M$ is *monotone* if it halts on every input, and if the length of $w$ is greater than the length of $w'$ then $M$ performs more steps on $w$ than on $w'$.
>
> Prove that MON is undecidable.

My idea is to define a reduction from HALT to MON. We define $f(\langle M,w \rangle) = \langle M' \rangle$ so that $M'$ will erase its input, write $w$, and simulate $M$ on it. If $M$ halts then $M'$ accepts.

I feel like I'm missing just a bit but I can't get my head around it.

# Answer
> 3 votes
Your answer is correct

What might seem missing is that $M'$ erases any input, writes $w$ and simulates $M$ on $w$, so it might seem that for any input (say $x$ which we erase), $M'$ takes the same number of steps (simulating $w$), but $M'$ needs to take more steps on larger inputs!

The thing is when you erase the input, the larger the input the more steps you need to take, and so that's not a problem, if the machine can simply ignore the input without making steps, then we simply modify $M'$ to first make some arbitrary steps, the number of these would be the length of the input, then it can proceed by writing $w$ and simulating $M$.

If $\langle M,w \rangle \in \mathrm{HALT}$, $\langle M' \rangle \in \mathrm{MON}$ since whatever the input, $M'$ is simulated only on $w$ and so it halts on every input, also for any inputs $x\_1,x\_2$, where $\vert x\_1 \vert \> \vert x\_2 \vert $, $M'$ takes more steps on $x\_1$ than $x\_2$ since deleting $x\_1$ takes more steps (or $M'$ simply made $\vert x\_1 \vert$ arbitrary steps on $x\_1$) then $M'$ simulates $w$ in both cases.

If $\langle M,w \rangle \notin \mathrm{HALT}$, $\langle M' \rangle \notin \mathrm{MON}$, since $M'$, whatever the input, is simulated only on $w'$ (hence it won't halt at any input).

---
Tags: reductions, halting-problem
---


# Question
Title: Maximum difference between maximum and minimum frequency in a subarray
Can anyone please help me with a better solution than O(n^3) for this problem?

So the problem is given a string, we want to output the substring's length where freqency\[c1\] - frequency\[c2\] is MAX. c1 = Most frequent character c2 = Least frequent character

e.g

'aaabbbbbabcbbbaaaa' =\> 8 ( corresponding to the substring 'bbbbbabcbbb' )

Also please help if there's similar set of problem.

# Answer
Your problem can be solved in linear time in the length of the input string.

Let $s=s\_1s\_2s\_3\ldots$ be your input string. For $0\<i\le j \le |s|$, let $n(i,j,c)$ be the number of occurrences of $c$ in $s\_i s\_{i+1} \dots s\_j$.

Let $m^\*$ be the measure of an optimal solution. Now guess the values of $c\_1$ and $c\_2$ achieving $m^\*$ (there are only $26^2$ choices) and consider the auxiliary problem of computing two indices $i(c\_1, c\_2)$, $j(c\_1, c\_2)$ that maximize $n(i(c\_1, c\_2),j(c\_1, c\_2),c\_1) - n(i(c\_1, c\_2),j(c\_1, c\_2),c\_2)$. Let $m(c\_1,c\_2)$ be the value of this maximum.

The auxiliary problem can be solved by noticing that each occurrence of $c\_1$ in $s\_i s\_{i+1} \dots s\_j$ contributes $1$ to the above quantity while each occurrence of $c\_2$ contributes $-1$ (other characters contribute $0$). Then, this auxiliary problem is equivalent to the maximum subarray problem, which can be easily solved in time $O(|s|)$.

Among all guesses, pick the one maximizing $m(c\_1, c\_2)$ and return $j(c\_1, c\_2) - i(c\_1, c\_2) + 1$.

To see that this algorithm is correct, consider any guess $c\_1, c\_2$ and let $i=i(c\_1, c\_2)$ and $j=j(c\_1, c\_2)$. Notice that if we choose $c^\*\_1$ and $c^\*\_2$ as (one of) the most and least frequent characters in $s\_i, \dots, s\_j$, we must have $m^\* \ge n(i, j, c\_1^\*) - n(i, j, c\_2^\*) \ge n(i, j, c\_1) - n(i, j, c\_2) = m(c\_1,c\_2)$. In other words, $m(c\_1,c\_2)$ is always a lower bound to $m^\*$.

Consider now the case in which your guess of $c\_1$ and $c\_2$ was correct (i.e., $c\_1$ and $c\_2$ are the most and less frequent occurring characters in an optimal solution, respectively). Since the optimal substring induces a feasible contiguous subarray for the auxiliary problem with measure $m^\*$, we must have $m(c\_1, c\_2) \ge m^\*$, thus implying $m(c\_1, c\_2)=m^\*$.
> 4 votes

# Answer
We can provide an $O(n)$ algorithm for such a problem

For every pair of characters $(c\_1,c\_2)$, we take the input string, ignore all other characters, replace $c\_1$ by $1$, replace $c\_2$ by $-1$ and then compute the largest sum of a contiguous subarray, which will be the deviation ($f\_{max} - f{min}$) for this pair

There are only $26 \times 26$ such pairs (which is a constant), an each pair uses only $O(n)$ time, so we end up with $O(n)$ time algorithm

Lets take an example so this becomes clear

Let the input string be $aaabbbbbabcbbbaaaa$

Now for example, let $c\_1 = b, c\_2 = a$

Ignore every other character (or simply replace it by $0$), then replace $b$ by $1$ and $a$ by $-1$, then we get the array $-1 \ -1 \ -1 \ 1 \ 1 \ 1 \ 1 \ 1 \ -1 \ 1 \ 1 \ 1 \ 1 \ -1 \ -1 \ -1 \ -1$, now compute the maximum sum of a contiguous subarray = $8$

And so $c\_1 = b, c\_2 = a$ we have $f\_{max} - f\_{min} = 8$ ($c\_1$ is max and $c\_2$ is min)

Now repeat this for every pair $c\_1,c\_2$, and the output would be the pair with the greatest deviation ($f\_{max} - f\_{min}$)

Again, there are only $26 \times 26$ such pairs (constant), and for every pair we need only $O(n)$ steps, and getting the max over a constant number of pairs takes constant time, so we end up with an $O(n)$ algorithm
> 2 votes

---
Tags: arrays, substrings
---


# Question
Title: How to cross verify the resultant E-NFA in "Regular Expression to E-NFA" is correct?
Let's say that we want to convert the regular expression: (ab + a)\* to Finite Automata, where '+' is union and '\*' is kleene star. Using the Thompson method, Thompson Method

I end up with this:

My question is, is there a way to cross verify that my E-NFA accepts the language of Regular expression mentioned at the start in this post? I tried converting the Resultant E-NFA back to Regular Expression using Arden's Theorem. But I end up with a inifite substitution for the final state q9

Also, is my constructed E-NFA correct?

EDIT: Adding Converting "resultant E-NFA to RE"

epsilon transition = e

q1 = e

q2 = q1e + q8e

q3 = q2e

q4 = q3a

q5 = q4b

q6 = q2e

q7 = q6a

q8 = q7e

q9 = q8e + q1e

Since we have to final states, q1 and q9 we need to substitue other values in q1 and q9. We will start with q9

q9 = q8e + q1e

q9 = q7ee + e

q9 = q6aee + e

q9 = q2eaee + e

q9 = (q1e + q8e)eaee + e

q9 = q1eeaee + q8eeaee + e

q9 = q1a + q8a + e

We again got q8, so this chain will always repeat. So what do i do from here?

# Answer
> 0 votes
You should try the substitutions in order so that you don't get a loop, here is the solution

$q1 = \varepsilon$

$q\_2 = q\_1 \varepsilon + q\_8 \varepsilon$

$q\_3 = q\_2 \varepsilon$

$q\_4 = q\_3a$

$q\_5 = q\_4b$

$q\_6 = q\_2 \varepsilon$

$q\_7 = q\_6a$

$q\_8 = q5 \varepsilon + q\_6 \varepsilon$

$q\_9 = q\_8 \varepsilon + q1 \varepsilon$

---

Substitute for $q\_1 = \varepsilon$ in every other rule

$q\_2 = \varepsilon \varepsilon + q\_8 \varepsilon = \varepsilon + q\_8 \varepsilon$

$q\_3 = q\_2 \varepsilon$

$q\_4 = q\_3a$

$q\_5 = q\_4b$

$q\_6 = q\_2 \varepsilon$

$q\_7 = q\_6a$

$q\_8 = q5 \varepsilon + q\_6 \varepsilon$

$q\_9 = q\_8 \varepsilon + \varepsilon \varepsilon = q\_8 \varepsilon + \varepsilon $

---

Substitute for $q\_2 = \varepsilon + q\_8 \varepsilon$ in every other rule

$q\_3 = (\varepsilon + q\_8 \varepsilon) \varepsilon = \varepsilon + q\_8 \varepsilon$

$q\_4 = q\_3a$

$q\_5 = q\_4b$

$q\_6 = (\varepsilon + q\_8 \varepsilon) \varepsilon = \varepsilon + q\_8 \varepsilon$

$q\_7 = q\_6a$

$q\_8 = q5 \varepsilon + q\_6 \varepsilon$

$q\_9 = q\_8 \varepsilon + \varepsilon$

---

Substitute for $q\_3 = \varepsilon + q\_8 \varepsilon$ in every other rule

$q\_4 = (\varepsilon + q\_8 \varepsilon)a = a + q\_8a$

$q\_5 = q\_4b$

$q\_6 = \varepsilon + q\_8 \varepsilon$

$q\_7 = q\_6a$

$q\_8 = q5 \varepsilon + q\_6 \varepsilon$

$q\_9 = q\_8 \varepsilon + \varepsilon$

---

Substitute for $q\_4 = a + q\_8a$ in every other rule

$q\_5 = (a + q\_8a)b = ab + q\_8ab$

$q\_6 = \varepsilon + q\_8 \varepsilon$

$q\_7 = q\_6a$

$q\_8 = q5 \varepsilon + q\_6 \varepsilon$

$q\_9 = q\_8 \varepsilon + \varepsilon$

---

Substitute for $q\_5 = ab + q\_8ab$ in every other rule

$q\_6 = \varepsilon + q\_8 \varepsilon$

$q\_7 = q\_6a$

$q\_8 = (ab + q\_8ab) \varepsilon + q\_7 \varepsilon = ab + q\_8ab + q\_7 \varepsilon$

$q\_9 = q\_8 \varepsilon + \varepsilon$

---

Substitute for $q\_6 = \varepsilon + q\_8 \varepsilon$ in every other rule

$q\_7 = (\varepsilon + q\_8 \varepsilon)a = a + q\_8 a$

$q\_8 = ab + q\_8ab + q\_7 \varepsilon $

$q\_9 = q\_8 \varepsilon + \varepsilon$

---

Substitute for $q\_7 = a + q\_8 a$ in every other rule

$q\_8 = ab + q\_8ab + (a + q\_8 a) \varepsilon = ab + q\_8 ab + a + q\_8 a = a + ab + q\_8(a+ab)$

Now we can apply Arden's Theroem

$q\_8 = a + ab + (a+ab)^\* = (a+ab)^\*$

$q\_9 = q\_8 \varepsilon + \varepsilon$

---

Substitute for $q\_8 = a + (ab)^\*$

$q\_9 = (a+ab)^\* \varepsilon + \varepsilon = (a+ab)^\*$

And here is our solution :)

---
Tags: regular-languages, finite-automata, regular-expressions, nondeterminism, theory
---


# Question
Title: How does the 'proof' of the Cook-Levin theorem, actually prove the Cook-Levin theorem?
I was wondering if someone could help resolve some issues I have understanding the proof given for the Cook-Levin theorem provided in the Sipser text (3rd edition) – as this proof has truly stumped me.

Having read through this proof numerous times, the only issue I have is that I simply do not understand how it actually proves the statement in question; namely that the resultant Boolean expression is satisfiable if and only if the nondeterministic Turing machine NM running on ‘w’ accepts on at least one of its computation branches. This is because as far as I can tell, you just produce a big Boolean expression that is always satisfiable, even when NM never accepts the input w. For instance, focusing on the ϕ\_accept compound proposition as an example, clearly this is always satisfiable (just set one of the xi,j,q-accept Boolean variables to true – even if this never occurs in any of the computation histories of NM) – consequently what is the point of even including ϕ\_accept? The same can be said for the other compound propositions.

As far as I can tell, the resultant Boolean expression produced evaluates to true if and only if NM accepts on one of its computation branches – but this is not what the statement in question actually says. To be clear, what I mean here is that after producing the Boolean expression, if you were to examine the computation history table for every single branch of NM’s computation tree and go about binding each of the variables depending on whether they are actually true or false for that specific computation history table, then ϕ would evaluate to false for every single table if NM rejects, but ϕ would evaluate to true for at least one of the computation history tables if NM accepts. But clearly this is not what the proof is saying, since they never talk about variable binding or the procedure just mentioned. Consequently, I am utterly stumped by this proof – any help would be greatly appreciated.

# Answer
With careful analysis we can ascertain that this reduction works, meaning that the $NM$ accepts $w$ if and only if $\phi$ is satisfiable (falsifying your claim that $\phi$ is satisfiable anyways)

Lets first have a high level overview of the reduction, $NM$ runs in $O(n^k)$ on input $w$, where $\vert w \vert = n$

We have tableau, an $n^k \times n^k$ table of configurations

We wish to produce $\phi$ such that $\phi$ is satisfiable iff $NM$ has an accepting computation on $w$

Now each cell of the tableau indexed bi $i,j$, $Cell\[i,j\]$, can have only one symbol out of $C = Q \cup \Gamma \cup \\{\\#\\}$, where $Q$ is set of states of $NM$ and $\Gamma$ is the tape alphabet of $NM$

So for position $(i,j)$ and every symbol $s \in C$, we have a variable $x\_{i,j,s}$, where $x\_{i,j,s} = 1$ means that $Cell\[i,j\] = s$

Now lets consider $\phi$ which is composed of four parts

$$\large \phi = \phi\_{cell} \land \phi\_\text{start} \land \phi\_\text{move} \land \phi\_{accept}$$

$\phi\_\text{cell}$ : ensures only one symbol is on for each $(i,j)$ position, so each cell can have only one symbol

$\phi\_\text{start}$ : ensures that the first row of the table is the starting configuration of $NM$ on w

$\phi\_\text{move}$ : ensures that all windows in tableau are legal

$\phi\_\text{accept}$: ensures that an accepting configuration occurs in the tableau

If we think carefully, the only way to satisfy all of these is to have an accepting computation of $NM$ on $w$

You proposed "cheating", by simply letting some variable $x\_{i,j,q\_{accepts}}$ be true hence $\phi\_{accept}$ would be true, but think again, $\phi\_\text{cell}$ would require $Cell\[i,j\]$ to be $q\_\text{accept}$, and if this can not be yielded in an accepting computation, then $\phi\_\text{move}$ would be false since you have made an illegal move

You may fool one of the sub-$\phi$s, but you would get caught by another, the only way to satisfy all $\phi\_{cell},\phi\_\text{start},\phi\_\text{move},\phi\_{accept}$ and hence satisfy $\phi$ is through the existence of an accepting computation

Hopefully by now, you can see that if $NM$ accepts $w$, there there is some accepting computation, and by turning the corresponding variables on we have a satisfying assignment for $\phi$, also if we have a satisfying assignment we can produce a polynomial size accepting tableau for $NM$
> 6 votes

---
Tags: complexity-theory
---


# Question
Title: How to show that language is Turing-recognizable and Turing-decidable?
How do I being to show that if $L\_{1}$ is Turing-recognizable language over $\Sigma=\\{0,1\\}$, then $L\_{2} = \\{ww^R | w ∈ L\_{1} \\}$ is a Turing recognizable language too.

There is another similar problem, but instead of the language being recognizable, it's decidable. If anyone has any ideas on how to approach both of these problems, I'd be very thankful.

I'm very new to this topic and didn't find any similar problems online, so I'm looking for any kind of tips to solve these problems :)

# Answer
> 0 votes
The following is a description of an acceptor/decider for $L\_2$. If the length $|x|$ of the input $x$ is odd, then reject. Otherwise consider the subword $x\_1$ (resp $x\_2$) consisting of the first (resp. last) $|x|/2$ symbols of $x$. Check whether $x\_1 = x\_2^R$. If that is not the case, then reject. Otherwise, simulate an acceptor/decider for $L\_1$ on input $x\_1$.

# Answer
> 0 votes
Here is what a $TM$ for $L\_2$ would do

We first check that input $x$ is not of odd length, if so we reject

Next we cut $x$ into two halves and check that the second half is the reversal of the first, hence the string is of the form $ww^R$

Next, we run the recogniser/decider of $L\_1$ on $w$ (the first half of the input $x$), and output whatever it outputs

So we basically do whatever the recogniser/decider for $L\_1$ does on $w$, but only after checking that the string $x$ is in the form $ww^R$ (which can be done in few steps)

Hopefully its clear that we would yield a recogniser/decider for $L\_2$ form a recogniser/decider for $L\_1$

---
Tags: turing-machines, turing-recognizable
---


# Question
Title: Does cache hit time include both time to read a cache and time to write a cache?
For example, if it takes 1 cycle to read the cache and 3 cycles to write the cache, is the hit time equal to 4 cycles? Also, does this vary based on whether the cache is an instruction cache or a data cache?

# Answer
> 0 votes
I would say, it depends.

Overall there are several strategies how a cache could be incorporated into a process. Few of these options are:

* read through: a client reads from cache, and if the cache does not have a value, then the cache itself reads the data from the store. And the cache saves the value before being returned to a customer. In this case the cost will be vary, depending if the value is already in cache.
* cache aside is another option - the client checks the cache - the cache either gives back the value or returns nothing. If the value was not found, it's the client who goes to datastore to read and also write to the cache.

There are few more strategies, and all of them will have a different cost.

Also, it is important to understand what "cache hit" and "cache miss" is. These are term unrelated to the way how cache is integrated. By definition, a cache hit happens when a client requests a key, and the key is already in the cache, regardless how that key got there. "Cache miss" is opposite - a client asks for the key, and the key is not there.

---
Tags: computer-architecture, cache
---


# Question
Title: Problem size and how it's different than the input for an algorithm
I am trying to understand how the input size, problem size and the asymptotic behavior of an arbitrary algorithm given in pseudo code format differ from each other. While I fully understand the input and the asymptotic behavior, I have problems understanding the problem size. To me it looks as if problem size = space complexity for a given problem. But I am not sure. I'd like to illustrate my confusion with the following example:

We have the following pseudo code:

```
ALGONE(x,y)
    if x=0 or x=y then
      return 1
   end
  return ALGONE(x-1,y-1) + ALGONE(x,y-1)

```

So let's say we give two inputs in $x$ and $y$ and $n$ represents the number of digits.

Since we are having addition as our main operation, and addition is an elementary operation, and for two numbers of $n$ digits, we need $n$ operations, then the asymptotic behavior is of the form $O(n)$.

But what about the problem size in this case. I don't understand what am I supposed to say. The term problem-size is so vague. It depends on the algorithm but even then, even if one is able to understand the algorithm what do you give as an answer?

I'd assume that in this particular case the problem size, might be the number of bits we need to represent the input. But this is a guess of mine, grounded in nothing.

# Answer
I'm not sure what you mean by *problem size*, so let me give a few examples:

* We often analyze graph algorithms in terms of $|V|$ and $|E|$.
* We often analyze algorithms on arrays (sorting, binary search) in terms of $n$, the size of the array.
* We often analyze algorithms on square matrices in terms of $n$, the number of rows (or columns). Sometimes we often take the sparsity (number of non-zero entries) into account.

In this interpretation of *problem size* (which might differ from what you have in mind), we associate with each instance several parameters (often one, sometimes more) with respect to which we analyze the algorithm. It's up to us to define the problem size.

*Input size* is also not as clear cut as it might seem, for two main reasons:

* Sometimes we measures the input size in *bits*, but more often we measure it (implicitly) in terms of machine words (a machine word has length $O(\log N)$, where $N$ is the input size *in bits*). In specific areas such as computational geometry, we allow the words to have unbounded size.
* We don't usually have a specific encoding in mind. Usually all encodings have roughly the same size, but this is not always the case (for example, compare the adjacency matrix and adjacency list representations of graphs).

The concepts of input size and problem size are there to help us understand the complexity of algorithmic tasks. Use the definitions most appropriate for your application.
> 2 votes

# Answer
The asymptotic behavior can refer to any "measurand", such as the processor time taken, but also the space consumption, the number of comparisons, the number of SQL queries of whatever you want.

The input size indeed denotes the space taken by the input data (quite often written $n$, which can be itself an asymptotic representation). But $n$ can also be something different, such as the maximum value of an input parameter.

Problem size might refer to $n$, by language abuse.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Show a reduction of max flow to min cost
Show a reduction of max flow to min cost (not min cost max flow!!)

# Answer
Consider a graph $G$ and let $s$ (resp. $t$) be the source (resp. target) vertex for your max-flow problem. Let $U$ be an upper bound to the max flow (for example the sum of the capacities of the edges leaving $s$, or the sum of the capacities of the edges entering $t$).

Construct an instance of min-cost flow where you want to send $U$ units of flow from $s$ to $t$ and the graph $G$ is modified as follows:

* All edges of $G$ have cost $0$
* Add a new edge $(s,t)$ with cost $1$ and capacity $U$.

If $x$ is the cost of a min-cost flow on this graph, then the max flow in $G$ is $U-x$.
> 0 votes

---
Tags: network-flow
---


# Question
Title: Calculate Physical Address Corresponding to Logical Addresses
Consider a logical address space of 4096, page size = 1024 physical memory = 8192

$\begin{array} {|c|c|} \hline \text{Page No} & \text{Frame No} \\ \hline 0 &7 \\ \hline 1 &4 \\ \hline 2 &2 \\ \hline 3 &3 \\ \hline \end{array}$
What is the physical address corresponding to logical address 500, 1000, 2000, 3000, and 4000?

Can I know how to solve this step by step?
Only one example would be enough.

# Answer
Since you have not mentioned word size, I am going to assume they are same across all three terms. Your problem boils down to calculating which page number(address range) the logical address lies in, finding offset of that address within the page and adding the offset to the physical address where that page is mapped.

Let's do some base calculation

**No. of pages per process** = $floor$($logical$ $address$ $space$/$page$ $size$)$ = 4$

**No. of frames in physical(main) memory** = $floor$($physical$ $memory$ $size$/$page$ $size$)$ = 8$

Consider the logical address $2000$

**Page no. which contains 1000** = $floor(2000/1024) = 1$ i.e. address 2000 lies in page no 1.

**Offset of 2000 in page no. 1** = $2000mod1024=976$

This offset remains same when a page is mapped to a frame. Now we just need to find out the base address of the frame where page no. 1 lies and add the offset to it.

From your page table, it says page no. 1 is held by frame no. 4. The base address of frame no. 4 = $4\*1024=4096$ and goes upto $5119$.

So finally, logical address $2000$ corresponds to physical address $4096+976=5072$

Hope this helps. You can similarly find it for others.
> 1 votes

# Answer
Use this correspondence table:

```
Logical addresses / Physical addresses
     0-1023           7168-8191
  1024-2047           4096-5119
  2048-3071           2048-3071
  3072-4095           3072-4095

```
> 0 votes

---
Tags: paging
---


# Question
Title: Language generated by $S \to aAb|Sb$, $A \to aAb|ab$
> Let $G = (\\{A,S\\}, \\{a,b\\}, S, P\\}$ be the grammar with the following productions: \begin{align} & S \to aAb | Sb \\ & A \to aAb | ab \end{align}
>
> 1. What is the language $L(G)$ generated by the grammar?
> 2. Prove your answer to 1. by induction.

Here is my attempt. I think that the language generated by $G$ is $$L= \\{a^nb^{n+k} \mid n\geq2,k\geq0. \\} $$ I need to prove that $L = L(G)$ by induction on length, but I don't know how to do it properly because I have two parameters ($n,k$). There also need to be two directions to the proof.

I found this post, but it is of no help to me.

What is the base case? I tried looking about distinguishing whether the length is even or odd, and I think I got the pattern between $(n,k)$ correctly, but I really don't have a clue how to start the proof.

# Answer
Start by showing that $L(A)$ (the language generated by the grammar if the starting symbol is $A$) is $L\_A = \\{ a^n b^n \mid n \geq 1 \\}$. You prove this by double inclusion:

* In order to prove that $L\_A \subseteq L(A)$, prove by induction on $n$ that $A \Rightarrow^\* a^nb^n$.
* In order to prove that $L(A) \subseteq L\_A$, prove by induction *on the length of the derivation* that if $A \Rightarrow^\* \alpha$ then either $\alpha = a^n b^n$ for some $n \ge 1$, or $\alpha = a^n A b^n$ for some $n \geq 0$. (In fact we won't need this direction, but it's good practice.)

Now we can show that $L = L(G)$, again by double inclusion:

* In order to prove that $L \subseteq L(A)$, prove by induction on $k$ that $S \Rightarrow^\* aAb^{k+1}$.
* In order to prove that $L(A) \subseteq L$, prove by induction on the length of the derivation that if $S \Rightarrow^\* \alpha$ then either $\alpha = S b^k$ for some $k \geq 0$, or $\alpha = a^{n+1}Ab^{n+k+1}$ for some $n,k \geq 0$, or $\alpha = a^{n+2} b^{n+k+2}$ for some $n,k \geq 0$.
> 1 votes

---
Tags: automata, formal-grammars, induction
---


# Question
Title: Difficulty understanding the CANYIELD function in the Sipser text's proof of Savitch’s theorem
I was wondering whether someone could help me resolve an issue I have understanding the proof given for Savitch’s theorem in the Sipser text (3rd edition). The question I have is more or less identical to the first question given in a previous post (The crux of Savitch's Theorem); which has remained unanswered – hence I’ll re-state the question and elaborate on the details more in this post.

On page 335, the function ‘CANYIELD’ is described:

CANYIELD = “On input c1, c2, and t:

1. If t = 1, then test directly whether c1 = c2 or whether c1 yields c2 in one step according to the rules of N. Accept if either test succeeds; reject if both fail.
2. If t \> 1, then for each configuration cm of N using space f(n):
3. ```
      Run CANYIELD(c1, cm, t/2 ).

```
4. ```
      Run CANYIELD(cm, c2, t/2 ).

```
5. ```
      If steps 3 and 4 both accept, then accept.

```
6. If haven’t yet accepted, reject.”

My question concerns step 2 of this procedure: namely how exactly does it select cm of N? It says ‘for each configuration of N’ – but as far as I can tell no specific method is described for how M can implement this \[which is important, since we need to be able to verify that this selection can be done in O(f2(n))\]. It is not obvious to me how you would be able to know what all of N’s legal configurations are for a given input without running it and storing the computation tree in memory – which obviously we cannot do because it could be exponential in the size of the input. Any help on this would be greatly appreciated.

# Answer
> 3 votes
You can enumerate every possible configuration $c\_m$ of $N$, this process takes only $O(f(n))$ space

First, lets consider the number of configuration of $N$ that runs in $f(n)$ space

If $N$ runs in $f(n)$ space, has $c$ states, $c = \vert Q \vert $, and $g$ tape symbols, $g = \vert \Gamma \vert$, then the total number of strings that can appear on tape are $g^{f(n)}$, we can be in any of the $c$ states, and the head can be in any of the $f(n)$ positions, hence the total number of configurations is $c \cdot f(n) \cdot g^{f(n)} = O(f(n)2^{f(n)})$

We can encode these configurations, hence the space needed would be $O(log(f(n) \cdot 2^{f(n)})) = O(log(f(n)) + log(2^{f(n)})) = O(f(n))$

Hence we only need $O(f(n))$ space

For completion, lets dive into more details of how we can do this in an easy way

A configuration $c\_m$ as we have shown occupies $O(f(n))$ space, meaning it takes $O(f(n))$ cells

Each cell is filled with a symbol $s \in C = Q \cup \Gamma$, where $Q$ is the set of $N$ states and $\Gamma$ is the tape alphabet

Note that $\vert C \vert$ is a constant, and hence each symbol $s \in C$ can have a binary encoding of length $d = \log(\vert C \vert)$, again $d$ is a constant

So, we can replace each symbol $s \in C$ by its $d$-long binary encoding, and we get a binary configuration of length $O(d \cdot f(n)) = O(f(n))$, storing the entire map from symbols to binary code should take only constant space

Now its easy to enumerate every configuration from $000 \ldots 000$ to $111 \ldots 111$, we can use the stored map to change the configuration from binary string to symbols $s \in C$ or vice versa in $f(n)$ space

---
Tags: space-complexity
---


# Question
Title: Does FPT allow for doubling the parameter?
I have recently come across a result that showed that a given problem is in FPT when parameterized by the treewidth of a graph. However, they did this by showing that the problem is in FPT when parameterized by the treewidth of an augmented version of the graph that had treewidth of at most 2k+1 when the treewidth of the original graph is k.

Why is it possible do this?

# Answer
> 3 votes
Let $k$ be the parameter. Is an algorithm has a running time of the form $O(f(2k+1) \cdot \text{poly}(n))$ for a suitable function $f$, then it also has a running time of $O(g(k) \cdot \text{poly}(n) )$ for $g(k) = f(2k+1)$.

---
Tags: algorithms, complexity-theory, parameterized-complexity, treewidth
---


# Question
Title: What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?
I know that retrieving an item in a collection can be done in $O(1)$ time(on average) using hash tables. I would like to know if there is an algorithm that could be as performance without using arrays.

My main motivation for this question is to know if it is possible to build a retrieve element algorithm in $O(1)$ time using just functional programming. It seems that the lower bound is $\Omega(\log(n))$ using trees $T = (a, (T, T)) \text{ | ( )}$.

# Answer
> 5 votes
Without arrays, $\Omega(\log n)$ time is needed. Without arrays, the memory address you access is entirely determined by the control-flow path, i.e., the sequence of control-flow decisions (if construed appropriately) made during the execution. At each step, you can only choose between one of two (or a fixed finite number) of choices for control-flow. So, after $t$ steps of execution, there can be at most $O(2^t)$ different control-flow paths, and at most $O(2^t)$ different memory positions that could potentially be accessed. For the data structure operation to be correct, it needs to be possible to access every one of the $n$ memory positions, so you basically need $2^t \ge n$, which means you need $t \ge \log n$.

# Answer
> 1 votes
@D.W. what if at each step, there is not a fixed finite number of choices, rather some $k$ choices. In that case, there would be $O(k^t)$ different control-flow paths. By properly tuning, $k$ and $t$ , we can get $t^t \geq n$ or $t \geq W(n)$. Here $k$ is Lambert's W-function. @D.W. I think a little more explanation is needed why this cannot happen.

In my opinion, the logic is lying inside the register level. A processor should be able to map the entire range of $n$ different memory units (not necessary RAM units). Considering binary representation there is no way out to hold information of $n$ different locations lesser than $\log\_2(n)$ bits. While we are talking in terms of an array, or considering hash-table can access data in $O(1)$ average time, we assume hash operation is performed in $O(1)$ time. In reality, for hash operation, it takes at least $O(\log\_2(n))$ time (considering the processing of a bit or a constant number of bits at a time). This book is focusing a bit on these aspects.

---
Tags: time-complexity, data-structures, lambda-calculus, functional-programming, lower-bounds
---


title: What is this task type?

text:
# Question
Title: What is this task type?
There are people and the food they prefer:
John -20\> Apple
John -10\> Pear
Ethan -20\> Apple
Ethan -5\> Orange
Michael -10\> Pear
Michael -10\> Limon

The numbers indicate how strongly they prefer the respective food.
i.e. *John likes Apple more than Pear* (20 \> 10). And so for everyone.

The task is to distribute food to absolutely all people, trying to give the most preferred food as much as possible.

Expected result:
John -10\> Pear
Ethan -20\> Apple
Michael -10\> Limon
S = 10 + 20 + 10 = 40

But if so:
John -20\> Apple
Ethan -5\> Orange
Michael -10\> Pear
S = 20 + 5 + 10 = 35 (\<40 — not expected result)

With different initial data, there may be several solutions with the same maximum S.
These solutions must be kept without discarding.

**(1) What kind of task is this and (2) What algorithm should be applied?**

# Answer
**1. Assignment problem.**
**2. Hungarian algorithm.**

Python code:

```
# pip install munkres

from typing import Dict, Union

from munkres import Munkres

G = {
    'John': {'Apple': 20, 'Pear': 10},
    'Ethan': {'Apple': 20, 'Orange': 5},
    'Michael': {'Pear': 10, 'Limon': 10},
}

def find_matching(graph: Dict[str, Dict[str, Union[int, float]]],
                  matching_type=Union['max', 'min'],
                  return_type=Union['list', 'int', 'float', 'number'],
                  big_number: int = 1_000_000):
    negate = -1 if matching_type == 'min' else +1
    items_d, rows_d, cols_d = dict(), dict(), dict()
    n, m = 0, 0
    for row_name, cols in graph.items():
        if row_name not in rows_d:
            rows_d[n] = row_name
            rows_d[row_name] = n
            n += 1
        for item_name, cost in cols.items():
            if item_name not in cols_d:
                cols_d[m] = item_name
                cols_d[item_name] = m
                m += 1
            items_d[(rows_d[row_name], cols_d[item_name])] = cost * negate
    matrix = [[items_d[(i, j)] if (i, j) in items_d else big_number for j in range(m)] for i in range(n)]
    indexes = Munkres().compute(matrix)
    r_list = []
    r_number = 0
    for i, j in indexes:
        cost = matrix[i][j] * negate
        r_list.append(((rows_d[i], cols_d[j]), cost))
        r_number += cost
    if return_type == 'int':
        return int(r_number)
    if return_type == 'float':
        return float(r_number)
    if return_type == 'number':
        return r_number
    return r_list

print(find_matching(graph=G, matching_type='max', return_type='number'))
print(find_matching(graph=G, matching_type='max', return_type='list'))

```
> 1 votes

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


title: Question about stack permutations

text:
# Question
Title: Question about stack permutations
I encountered an exercise in which I am struggling to understand the solution provided even though I spent a lot of time trying to figure it out.

The exercise is the following and was taken from the book "The art of computer programming - Volume 1 by Donald Knuth"

> Imagine four railroad cars positioned on the input side of the track in Fig. 1, numbered 1, 2, 3, and 4, from left to right. Suppose we perform the following sequence of operations (which is compatible with the direction of the arrows in the diagram and does not require cards to "jump over" other cars):
>
> (a) move car 1 into the stack;
>
> (b) move car 2 into the stack;
>
> (c) move car 2 into the output;
>
> (d) move car 3 into the stack;
>
> (e) move car 4 into the stack;
>
> (f) move car 4 into the output;
>
> (g) move car 3 into the output;
>
> (h) move car 1 into the output.
>
> As a result of these operations the original order of the cars, 1234, has been changed into 2431.
>
> Show that it is possible to obtain a permutation $p\_1,p\_2 ... p\_n$ from $1,2 ... n$ using a stack if and only if there are no indices $i \< j \< k$ such that $p\_j \<p\_k \<p\_i$

The answer is : If $j \< k$ and $p\_j \< p\_k$, we must have taken $p\_j$ off the stack before $p\_k$ was put on;
if $p\_j \> p\_k$, we must have left $p\_k$ on the stack until after $p\_j$ was put on. Combining these two rules, the condition $i \< j \< k$ and $p\_j \< p\_k \< p\_i$ is impossible, since it means that $p\_j$ must go off before $p\_k$ and after $p\_i$, yet $p\_i$ appears after $p\_k$·

I tried to apply this reasoning to the permutation \<3,1,2\> which obviously can't be obtained using the constraints of the question, we can see that the indices $1 \< 2 \< 3$ satisfies:
$p\_i = p\_1 = 3$
$p\_j = p\_2 = 1$
$p\_k = p\_3 = 2$
Therefore this permutation is not obtainable, I tried to follow what was said in the answer but I still don't get it, I will appreciate any hints\clarifications.
Thanks.

# Answer
First, lets try to understand this scenario

We have three elements $i,j,k$

Their order of arriving at the stack is $j,k,i$ ($p\_j\<p\_k\<p\_i$)

Their order of getting out of the stack is $i,j,k$ ($i\<j\<k$)

The answer argues that this scenario is impossible to happen, lets try to see why

---

consider elements $j$ and $k$

We know that $j$ enters the stack before $k$, and that $j$ gets out of the stack before $k$

The only way for this to happen is, $j$ enters the stack, $j$ gets out of stack before $k$ enters, $k$ enters the stack $(1)$

---

consider elements $k$ and $i$

We know that $k$ enters the stack before $i$, but $i$ gets out of the stack before $k$

The only way for this to happen is, $k$ enters the stack, $k$ waits till $i$ enters the stack, $i$ enters the stack, $i$ gets out of the stack $(2)$

---

consider elements $i$ and $j$

We know that $i$ gets out of stack before $j$ (this suffices to arrive at our contradiction) $(3)$

---

Now lets recap

Order of arrival $j,k,i$

Order of departure $i,j,k$

In order for this to happen we need

$(1)$ : $j$ enters the stack, gets out of stack before $k$ enters, $k$ enters stack

$(2)$ : After $k$ enters the stack it needs to wait till $i$ enters, $i$ enters the stack then gets out

We can see that for $(1)$ and $(2)$ to happen, we need $j$ to get out of stack before $i$ even enters the stack

But this contradicts $(3)$ : $i$ gets out of stack before $j$
> 3 votes

---
Tags: combinatorics, permutations, stacks
---


# Question
Title: Subdivide a graph into non-crossing triangles with maximum edge weight
Let $G=(V,E)$ be a complete finite graph with the vertices arranged in a circle. Each edge has a nonnegative weight, and we would like to find an efficient algorithm to find a subgraph of maximum total weight, which is a triangulation of the graph. A triangulation of the graph is a subgraph such that no edges cross and no edge can be added to the graph without adding a crossing edge.

Of course as you go around the circle every edge will be added since the weight is nonnegative and these edges can never cause a crossing.

I initially thought of a greedy algorithm, selecting the highest weight edges and eliminating all crossing edges, but of course that won't work. I also thought about eliminating least weight edges but it seems to me that would probably also not work for the same reason.

I also tried to think of a divide-and-conquer algorithm, perhaps sped up by dynamic programming or something. My only thought was to first pick a random vertex and then iterate through all edges, finding the maximum graph weight if the edge were included (by first finding the maximum weight triangulation on one side of the edge and then on the other). But the runtime then seems like it has the equation

$$ T(n)=\[T(n-1)\]+\[T(4)+T(n-2)\] + ... + \[T(n-2)+T(4)\]+\[T(n-1)\] $$

and that doesn't seem like it would be efficient.

# Answer
With proper classification and memoization, an approach by dynamic programming runs in $O(n^3)$ time, where $n=|V|$. That seems efficient enough considering there are $n(n-1)/2$ edges.

---

Assume $n\ge 3 $; otherwise it is easy to solve the problem.

Label the vertices be $v\_0, v\_1, \cdots, v\_{n-1}$ clockwise. Let $v\_n=v\_0$.

For $0\le i\<j \le n$ and $v\_i\neq v\_j$, define $OPT\[i\]\[j\]$ as the maximum weight of a triangulation of the subgraph induced by vertices $v\_i, v\_{i+1}, \cdots, v\_j$ that contains the edge between $v\_i$ and $v\_j$. We have

$$OPT\[i\]\[i+1\]=\text{weight}(v\_i, v\_{i+1}).$$

$$OPT\[i\]\[j\]=\text{weight}(v\_i, v\_j) + \max\_{i\lt k\lt j} \left\\{ OPT\[i\]\[k\] + OPT\[k\]\[j\] \right\\},\quad\text{if } j\ge i+2.$$

A triangulation of $G$ must contain an edge between $v\_0$ and $v\_i$ for some $0\lt i\lt n$. Hence the maximum weight of a triangulation is $$\max\_{0\<i\lt n} \left\\{ OPT\[0\]\[i\] + OPT\[i\]\[n\] - \text{weight}(v\_0, v\_i)\right\\}.$$

It takes $O(n)$ time to compute an entry of $OPT$. There are $O(n^2)$ entries to compute. The overall complexity is thus $O(n^3)$.

With more bookkeeping, the triangulation of the maximum weight can be found without increasing the time-complexity.
> 2 votes

---
Tags: algorithms, time-complexity, dynamic-programming, weighted-graphs
---


# Question
Title: What does the following recurrence formula represent
I know that :

$T(n,k)=T(n−1,k−1)+T(n−1,k)$ is the Pascal triangle.

But what is this then:

$T(n,k)=T(n−1,k−1)+T(n,k-1)$

Is there any name for it? I am trying to learn about it's time complexity etc, but I can't find anything online.

# Answer
The second recurrence is ALSO Pascal's Triangle (interchange n and k).
> 3 votes

---
Tags: algorithms
---


# Question
Title: Subpath optimality lemma in weighted undirected graphs
In an introductory course on Dijkstra's algorithm, I enunciated the following lemma :

> Let x →\* z be a shortest path in a weighted graph and let y be any vertex along that path. It follows that x →\* y and y →\* z are shortest paths too.

To which one of my students pointed out that it does not seem to hold in the undirected graph that I used to explain that Dijkstra's algorithm needs weights to be nonnegative :

```
        B
 (-7) /   \ (8)
     /     \
    A       C
     \     /
 (3)  \   / (2)
        D

```

Indeed, a shortest path from C to A is C -\> B -\> A with total weight 1, but path C -\> B with weight 8 is not a shortest path : C -\> D -\> A -\> B with weight -2 is better.

In the short term I could continue by restricting my lemma to nonnegative weights. Cormen et al. give that lemma for arbitrary weights but for directed graphs only, and this holds.

I feel my counter-example is an… edge(!) case about the notion, wrt undirected graphs, of paths, cycles and the prohibition of negatively weighted cycles for shortest-path problems. The example does not have a negative-weight cycle for any reasonable notion of a cycle, but to create the same contradiction to the lemma in a directed graph, we would need an edge A -\> B and an edge B -\> A both with weight -7, which would give a cycle of weight -14.

**Does anybody have a satisfactory version of the lemma that would work in both directed and undirected graphs, for arbitrary weights ? ie., are there versions of the notions of path, shortest path and so on, were a version of the lemma would hold ?**

Especially in relation to proving eg. the validity of Floyd-Warshall's or Bellman-Ford's algorithms, which iirc also work with undirected graphs, provided they do not have a negative-weight cycle.

# Answer
> 2 votes
You actually have the idea here:

> ... but to create the same contradiction to the lemma in a directed graph, we would need an edge A -\> B and an edge B -\> A both with weight -7, which would give a cycle of weight -14.

If you apply the implementation of Dijkstra's algorithm to an undirected graph, it will treat the graph as if it is directed such that undirected edges are treated as two directed edges - one going in and another going out, and both edges having the same weight. The reason is simple, for every vertex $u$, if $u$ is selected in an iteration of the algorithm such that $v$ is one of its neighbor, vertex $u$ will again be considered when $v$ is selected in a later time. Hence, you can say that the algorithms treat each undirected edge as if they are edges in a cycle.

With that, you can claim that your graph essentially has a negative weight cycle, hence the problem.

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