# Question
Title: Determine smallest possible parameter set for FPT
I am reading a book about complexity analysis and cannot find a way to solve a problem in that book. The problem is, that I do not understand how to determine the smallest possible parameters, given the runtime of an algorithm. Do I just need to insert some numbers and see if the parameters exceed n at some point? Perhaps someone can explain that to me.

Consider the following exercise:

> The following O(.) expressions represent worst-case runtimes of different algorithms, where n is a measure of the input size and p, q and r are parameters (where p, q, r \<= n). Which of the following running times are FPT running times? Give the smallest possible parameter set for which the running times are FPT (if one exists) and explain.
>
> a) $O(p^q * n^2)$

Now I know that by the definition of FPT, this runtime is FPT (because we have a function of the parameters times n^constant). However, what are the smallest $p$ and $q$ in that case?

There are some more, but I just want to understand how to solve it and then I'll try the rest myself again.

Taken from:

> Rooij, I. V., Blokpoel, M., Kwisthout, J., & Wareham, T. (2019). Fixed-Parameter Tractable Time. In Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis (p. 125). Cambridge, England: Cambridge University Press.

# Answer
Recall that the runtime must be of the form $f(k) \cdot n^c$ for some constant $c$. So I believe that the exercise is asking, given that all three are at most $n$, which do you have to take as formal parameters in your analysis to achieve an FPT runtime.

So if only $p$ is a parameter, is that FPT? What if only $q$? Clearly, if both are fixed, you have FPT runtime.
> 0 votes

---
Tags: complexity-theory, parameterized-complexity
---


# Question
Title: Confused in calculating the shortest-path using Dijkstra's Algorithm
I am required to find the shortest path using Dijkstra's Algorithm. After performing the calculations, am I getting the following values correct?:

```
A=0
B=13
C=8
D=20
E=14
F=25
G=31
H=38
I=46
J=52

```

# Answer
Assuming that you only want to know the distance from A to a certain point, your first calculations are right. However A to H should be 37. Check that again. Also, there are shorter paths from A to I and A to J. Just have a look again - the other values are correct.
> 0 votes

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


# Question
Title: Sequence to explore the complexity of the NP problem
Let $X$ be some problem known to be in $NP$. What is the natural next step in exploring the complexity of the problem? Is it trying to prove whether it is in $P$ or try to prove it is $NP$-Hard? Taking the example of the Graph-isomorphism problem it seems to me that after discovering that problem is in $NP$. It is not easy to decide what to do next. Some people suggest me to prove it into $NP \cap CoNP$.

**Question** : What is worth to try if it is only known that problem is in $NP$? Is there any sequence (like first $NP$, $NP$-Hard, ....) to explore the complexity of the problem?

# Answer
So you have found out $X \in \mathbf{NP}$. Unfortunately, as Juho hints at in their answer, there is no "list" you can systematically go over to try and investigate $X$ further. This is mainly because separation results in complexity theory are (yet) few and far between, so most of the things you may try will not explicitly fail; you'll only be unsuccessful. For example, if you try to show $X \in \mathbf{P}$ you might succeed, but if it turns out to be incorrect it is very unlikely you will be able to prove it (since then $\mathbf{P} \neq \mathbf{NP}$).

This lack of "feedback" means you should tackle $X$ from different perspectives, and it is only experience (and a good deal of luck!) which will give you a "hunch" as to where the most promising one is. The following are a few options you might consider, as well as their implications if you manage to prove or disprove them (if any). Note I am only considering structural complexity theory here (which seems to be what you are interested in), but by all means this is what the entirety of complexity theory is about. Depending on the structure of $X$, it is also possible to consider $X$ from a parameterized complexity point of view, or try to find subexponential algorithms for it (see also number 4 below), and so forth and so on.

1. *$X$ is $\mathbf{NP}$-complete*

**Prove:** This is basically the end of the line for investigating $X$. It is also not a very surprising result since the list of $\mathbf{NP}$-complete problems is *huge* (and it already was when Richard Karp started to compile this list).

**Disprove:** Congratulations! You have proved $\mathbf{P} \neq \mathbf{NP}$.
2. $X \in \mathbf{P}$

**Prove:** This is the second most likely outcome and even more unsurprising than the former.

**Disprove:** Congratulations! You have proved $\mathbf{P} \neq \mathbf{NP}$.
3. $X \in \mathbf{coNP}$

**Prove:** Then $X$ is in $\mathbf{NP} \cap \mathbf{coNP}$ (which, for instance, includes factoring). Reconsider $X \in \mathbf{P}$.

**Disprove:** Congratulations! You have proved $\mathbf{NP} \neq \mathbf{coNP}$.
4. *$X \in \mathbf{GI}$ (the graph isomorphism class)*

**Prove:** Then $X$ admits a quasipolynomial-time algorithm (and is unlikely to be $\mathbf{NP}$-complete). Reconsider $X \in \mathbf{P}$.

**Disprove:** Congratulations! You have proved $\mathbf{P} \subseteq \mathbf{GI} \neq \mathbf{NP}$
5. $X \in \mathbf{BPP}$

**Prove:** Since it is widely suspected that $\mathbf{BPP} = \mathbf{P}$, this is only interesting if $X \in \mathbf{P}$ is not obvious. Consider also $X \in \mathbf{RP}$ or even $X \in \mathbf{ZPP}$.

**Disprove:** Congratulations! You have proved $\mathbf{NP} \neq \mathbf{BPP}$ (and quite likely also $\mathbf{P} \neq \mathbf{NP}$).

And the list goes on and on. As you can see, disproving any of these options leads to separation results, all of which would be major breakthroughs and, thus, unlikely to be proven simply by considering a random problem $X \in \mathbf{NP}$. This means you cannot expect to go through this list from head to tail making ticks and crosses as you go; you have to "guess" which of the options (if any!) is more likely and (with some luck) you'll be able to prove it.
> 5 votes

# Answer
It depends, you should try to do whatever the problem smells like. You will need experience to get a good hunch.

It's also not uncommon to try to do both. You might start by trying to come up with a polynomial time algorithm. Getting stuck? Why is that? Could you simulate that in an NP-hardness proof? Or you might start by building an NP-hardness proof from a "nearby problem" that has similar characteristics. While playing around with suitable gadgets you might realize things like "oh, any algorithm will always have to do this when encountering this type of subgraph..."

This earlier answer talks more about the art of finding reductions.
> 3 votes

---
Tags: np-hard, np
---


# Question
Title: Number of Function Calls In Recursive Code
I am new to recursion. I am doing some practice questions and I was wondering what the technique is for going from some recursive code to identifying the number of function calls it makes.

```
function win(n)
   if n ≤ 3 let memo(n) = 'yes'
   if memo(n-2) = 'no' or memo(n-3) = 'no' let memo(n) = 'yes'
   else let memo(n) = 'no'
   let win(n) = memo(n)

```

> Roughly, what is the number of steps that this program uses to compute $\mathit{win}(n)$? Is $\mathrm{step}(n)$ linear in $n$, polynomial in $n$ or exponential in $n$? Is it feasible to use this code to calculate $\mathit{win}(1000)$ on a fast supercomputer? Justify your answer.

# Answer
> 3 votes
First, let me correct the program:

```
1 function win(n)
2     if memo(n) exists:
3         return memo(n)
4     if n ≤ 3:
5         memo(n) = true
6     else:
7         memo(n) = not win(n-2) or not win(n-3)
8     return memo(n)

```

Compared to your code, there are two main differences:

1. If the value of the function is already known, that it is immediately returned (lines 2–3).
2. Otherwise, we compute the value of the function recursively by invoking *win* rather than *memo* (line 7).

The running time of *win* depends on which values have already been calculated. For example, if you already computed the value of *win* on $n-2$ and $n-3$, then computing it on $n$ takes time $O(1)$. We can also bound the running time of *win* on input $n$ by $O(n)$, since lines 4–8 run at most once for every value of the input.

We could also implement *win* without any memoization:

```
1 function win(n)
2     if n ≤ 3:
3          return true
4     else:
5          return not win(n-2) or not win(n-3)

```

The running time of this implementation satisfies the recurrence $$ T(n) = T(n-2) + T(n-3) + O(1), $$ with base case $T(n) = O(1)$ for $n \leq 3$. Using standard techniques, we determine that the running time is $\Theta(c^n)$, where $c \approx 1.3247$ is the unique real root of $c^3=c+1$.

Finally, let us take a look at some values of *win*: $$ \begin{array}{c|cccccccccccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\\hline \mathit{win}(n) & T & T & T & T & F & F & T & T & T & F & F & T & T & T & F & F \end{array} $$ Notice the period of 5. We can easily prove the following formula by induction: for $n \neq 1$, $\mathit{win}(n)$ holds iff $n \bmod 5 \in \\{0,1\\}$. This gives an $O(1)$ algorithm for computing *win*.

---
Tags: algorithms, complexity-theory, computability, recursion
---


# Question
Title: Describe a Turing machine that accepts a word iff there are twice as many 0's as 1's
Can anyone help me describe a Turing machine the language of which is the set of the words that have twice as many 0's as 1's? Assume the alphabet is $\\{0,1\\}$.

# Answer
Roughly speaking, the machine could act as follows:

1. Scan the input, looking for a 1 entry.
2. If no 1 entry is found, check that there are no 0 entries left, and halt at an accepting or rejecting state accordingly.
3. If a 1 entry is found, erase it.
4. Look for a 0 entry. if none is found, halt at a rejecting state. Otherwise, erase it.
5. Repeat step 4 one more time.
6. Go back to step 1.

When erasing an entry, you should change it to a symbol different from the blank symbol, so that you will be able in the future to scan through the entire breadth of the work.

If you have multiple tapes, you could try the following algorithm instead:

1. Scan the input. Whenever you see a 0, copy it to auxiliary tape 0. Whenever you see a 1, copy it to auxiliary tape 1.
2. As long as there are 1s in auxiliary tape 1: erase a 1, and erase two 0s from auxiliary tape 0; if there are not enough 0s, reject.
3. Accept iff there are no 0s in auxiliary tape 0.

This is a more efficient variant of the first algorithm.
> 4 votes

---
Tags: turing-machines
---


# Question
Title: Minimum depth of a leaf in a tree that corresponds to a comparison-based sorting algorithm
The lower bound of comparisons in a comparison-based sorting algorithm is $\log\_2 n!=Θ(n\log n)$. Yet there can be less comparisons needed in an algorithm. If you take a sorted array, it will take $n-1 = O(n)$ comparisons (with insertion sort) to sort the array — comparing every adjacent pair of numbers. I don't understand then how is $\log\_2 n!=Θ(n\log n)$ the lower bound.

I also don't understand the corresponding trees to the sorting-based algorithms: each leaf in the tree corresponds to one of the permutations of the $n$ numbers. If the minimum number of comparisons needed is $\log\_2 n!$ then the depth of every leaf should be at least $\log\_2 n!$, yet I saw that it's possible for a leaf to be with depth of $O(n)$.

Can there be leaves with depth even smaller than $n-1$?

# Answer
> 2 votes
The lower bound is for the *worst-case* number of comparisons. Every comparison-based sorting algorithm performs $\Omega(n\log n)$ comparisons *in the worst case*. This means that the tree has depth $\Omega(n\log n)$.

If you don't like the tree argument, here is an adversary argument which is basically a reformulation of the tree argument. We will maintain the set $\Pi$ of all permutations consistent with the answers so far. When the algorithm compares $i$ to $j$, we answer the result which reduces $\Pi$ by at most a half (one of the two answers must have this property). After $\log\_2 (n!/2)$ steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least $\log\_2 n! = \Omega(n\log n)$ comparisons on this branch.

In fact, we can strengthen this result (going back to the tree argument): every comparison-based sorting algorithm makes $\Omega(n\log n)$ comparisons *on average* (when the input is a random permutation of $1,\ldots,n$). For the proof, note that there can be at most $2^k$ leaves at depth $k$. In particular, the number of leaves at depth $(\log n!)/2$ is at most $\sqrt{n!}$. Therefore for at least $n! - \sqrt{n!}$ permutations, all leaves are at depth more than $(\log n!)/2$, and for this $1-o(1)$ fraction of permutations, the algorithm will make at least $(\log n!)/2 = \Omega(n\log n)$ comparisons.

Finally, let us show that you cannot possibly know the correct permutation if you perform less than $n-1$ comparisons. Construct a graph whose vertices are the elements of the array, and $(i,j)$ are connected if you compared the elements at these positions. If you make less than $n-1$ comparisons, then the graph won't be connected. In particular, you can partition the vertex set into two non-empty parts $A,B$ such that no element of $A$ was compared to any element of $B$. In particular, there is a permutation consistent with the performed comparisons in which all elements of $A$ are smaller than all elements of $B$, and another one in which all elements of $A$ are larger than all elements of $B$.

# Answer
> 2 votes
The worst-case time complexity of an algorithm is the time complexity for the worst-case input. Insertion sort takes $\Theta(n^2)$ in the worst-case, not $O(n)$. However, mergesort and heapsort each take $\Theta(n \log n)$ in the worst-case, and so achieve the $\Omega(n \log n)$ lower bound.

Suppose $n!$ is roughly $1000$, so that $\log n!$ is about $10$ (I know $1000$ is not the factorial of any integer, but just suppose you have a $1000$ permutations that need to be put as leaves). A nearly complete binary tree with $1000$ leaves will have a height of about $10$ (plus or minus 1). If the binary tree is not complete, then the height (or depth) will be larger. So, if some leaves in the binary tree are at small depth, then there exist other leaves in the tree which have a large depth, and in fact these leaves would have a larger depth than would have been the case if all leaves had the same depth. But even in the best case situation - where the tree is the shortest - there will exist leaves of height at least $10$, and so the height of the tree is always at least $10$. Similarly, if there are $n!$ leaves in a binary tree, there will exist some leaves having height at least $\log n!$. Therefore, the height of a binary tree having $n!$ leaves is at least $\log n!$. This part of your question is about the maximum number of nodes (or just leaves) that can be accommodated in a tree having some fixed height, and isn't related to sorting.

Now to show that there can't be any permutation at depth $n-2$. We need at least $5-1=4$ comparisons to sort five elements. To understand this intuitively, observe that if $a\_i$ is the $i$th element and we know $a\_1 \< a\_2$ and $a\_2 \< a\_3$, then there is no need to compare $a\_1$ with $a\_3$ and we can sort the three elements as $(a\_1,a\_2,a\_3)$. We can *deduce* how $a\_1$ and $a\_3$ fare (relative to each other) without making another comparison because the first and third elements are being compared indirectly (via the second element). But if there were 5 elements in the array, two comparisons are not enough to make all five elements directly or indirectly related to each other. This is because a connected graph on 5 vertices must have at least $5-1=4$ edges.

If positions 1 and 2 are compared, 2 and 3 are compared, and 4 and 5 are compared, and no further comparisons are made, then the algorithm cannot correctly sort the five elements because there is no way to determine whether the elements in $\\{a\_1,a\_2,a\_3\\}$ are smaller than or larger than the elements in $\\{a\_4,a\_5\\}$ \- we would only know how the elements within each subset fare relative to each other. A correct algorithm should be able to produce one of at least two different outputs, depending on whether the first subset contains large values, or whether the first subset contains all small values. Similarly, for all $n$ elements of the array to be directly or at least indirectly compared to each other, at least $n-1$ comparisons must be made.

---
Tags: sorting
---


# Question
Title: Give an NL-algorithm for complement of 2-SAT
**Question1:** What is the difference between 2SAT and the complement of 2SAT?

**Question2:** It is known that NL is contained in P, but what we know about P over NL? can be said that an algorithm that runs in P, uses NL space?

Information That I gather

I follow the Papadimitriou algorithm to solve 2-SAT with Let give 2-SAT a graph of connected nodes according to the specifications contained literal and clauses where the information of the nodes and connections is a container in a CNF of 2 literals per clause, because of the problem need to be contained in NL we assume that we are only working to solve this in 1 writing tape and 1 only input tape to run the algorithm

```
    for i=0 repeat log2(n times)
      Choose Random initial assignment for every literal
         Repeat 2n^2
           -If
             The assignment satisfies all the paths in the sequence
             of clauses, Halt and report
           -else
             Pick arbitrary unsatisfied clauses and flip the value of its literals
     Report unsatisfiable

```

According to 2-SAT reachability one condition for the possibility of no reach, if one path of the graph where there are connected nodes with the same literal and one of them is a negation, then the graph doesn't have a satisfiable result, and that would be the case in the algorithm. This is the same case for a complement of 2SAT.

In the non-deterministic solution, the algorithm could give only a correct answer or a false negative depending on the condition of the arrangement of the clauses, but never retrieve a false positive because of the condition establish in the conditional operator.

With the else clause the algorithms cover different possible clauses fliping the literal where the condition was unsatisfied and trying new options.

The algorithm uses only memory to keep the counter running because the counter corresponds to the size of the input in Log2(n)\*2n^2 space on the writing tape.

Also is prove that 2SAT correspond to NL and NL-complete and we know that NL=coNL

# Answer
> Question1: What is the difference between 2SAT and the complement of 2SAT?

The set of all strings that do not describe satisfiable 2CNF formulas.

> Question2: It is known that NL is contained in P, but what we know about P over NL? can be said that an algorithm that runs in P, uses NL space?

We don't know anything significant beyond that $\mathrm{NL}\subseteq\mathrm{P}$.

It doesn't really make sense to ask if "an algorithm... uses NL space". You can ask if an algorithm uses logarithmic space and if it's nondeterministic, but there's no such thing as "nondeterministic space" *per se*. By that, I mean that the storage space itself isn't nondeterministic: nondeterminism is a property of the algorithm that uses the space.

It's certainly not true that an algorithm that runs in polynomial time necessarily uses logarithmic space: it could use polynomial space. It's possible that every deterministic algorithm that runs in polynomial time could be rewritten as a nondeterministic algorithm that uses only logarithmic space but we don't know if that's true or not. If it were true, we would have $\mathrm{P}=\mathrm{NL}$.

Note that, formally speaking, $\mathrm{NL}$ and $\mathrm{P}$ are classes of problems, not algorithms.
> 4 votes

# Answer
Assuming that P≠NL, we know that P-complete problems are not in NL. The prototypical example is the Circuit Evaluation Problem, in which you are given a circuit (with constants as inputs), and the goal is to determine whether it evaluates to true. Wikipedia describes many other P-complete problems.

Some problems are not (known to be) P-complete, yet we still believe they shouldn't belong to NL. For example, the complexity class CC sits between NL and P: NL⊆CC⊆P. It is believed that both inclusions are strict, and this implies that CC-complete propblems are not in NL. Examples include decision versions of the stable matching problem and the lexicographically first maximal matching problem.

Another example is the complexity class ⊕L, sitting between L and P, for which a complete problem is satisfiability of linear equations mod 2. There is not much information on this class, but it features in the refined Schaefer's theorem, and seems to be incomparable with NL (i.e., it is conjectured that none of the two classes contains the other).

Let me close with an important comment: NL=coNL. Therefore to show that a language is in NL, it suffices to show that its complement is in NL. The language 2SAT is known to be NL-complete, and in particular both 2SAT and its complement are in NL.
> 2 votes

---
Tags: complexity-theory, 2-sat
---


# Question
Title: Is there any use case for the bottom type as a function parameter type?
If a function has return type of ⊥ (bottom type), that means it never returns. It can for example exit or throw, both fairly ordinary situations.

Presumably if a function had a parameter of type ⊥ it could never (safely) be called. Are there ever any reasons for defining such a function?

# Answer
One of the defining properties of the $\bot$ or empty type is that there exists a function $\bot \to A$ for every type $A$. In fact, there exists a *unique* such function. It is therefore, fairly reasonable for this function to be provided as part of the standard library. Often it is called something like `absurd`. (In systems with subtyping, this might be handled simply by having $\bot$ be a subtype of every type. Then the implicit conversion is `absurd`. Another related approach is to *define* $\bot$ as $\forall \alpha.\alpha$ which can simply be *instantiated* to any type.)

You definitely want to have such a function or an equivalent because it is what allows you to make use of functions that produce $\bot$. For example, let's say I'm given a sum type $E+A$. I do a case analysis on it and in the $E$ case I'm going to throw an exception using $\mathtt{throw}:E\to\bot$. In the $A$ case, I'll use $f:A\to B$. Overall, I want a value of type $B$ so I need to do something to turn a $\bot$ into a $B$. That's what `absurd` would let me do.

That said, there's not a whole lot of reason to define your own functions of $\bot\to A$. By definition, they would necessarily be instances of `absurd`. Still, you might do it if `absurd` isn't provided by the standard library, or you wanted a type specialized version to assist type checking/inference. You can, however, easily produce functions that will end up *instantiated* to a type like $\bot\to A$.

Even though there isn't much a reason to write such a function, it should generally still be *allowed*. One reason is that it simplifies code generation tools/macros.
> 17 votes

# Answer
To add to what has been said about the function `absurd: ⊥ -> a` I have a concrete example of where this function is actually useful.

Consider the Haskell data-type `Free f a` which represents a general tree structure with `f`-shaped nodes and leaves containing `a`s:

`data Free f a = Op (f (Free f a)) | Var a`

These trees can be folded with the following function:

```
fold :: Functor f => (a -> b) -> (f b -> b) -> Free f a -> b
fold gen alg (Var x) = gen x
fold gen alg (Op x) = alg (fmap (fold gen alg) x)

```

Briefly, this operation places `alg` at the nodes and `gen` at the leaves.

Now to the point: all recursive datastructures can be represented using a Fixed-point datatype. In Haskell this is `Fix f` and it can defined as `type Fix f = Free f ⊥` (i.e. Trees with `f`-shaped nodes and no leaves outside of the functor `f`). Traditionally this structure has a fold as well, called `cata`:

```
cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg x = fold absurd alg x

```

Which gives a quite neat use of absurd: since the tree cannot have any leaves (since ⊥ has no inhabitants other than `undefined`), it is never possible to use the `gen` for this fold and `absurd` illustrates that!
> 6 votes

# Answer
The bottom type is a subtype of every other type, which can be extremely useful in practice. For example, the type of `NULL` in a theoretical type-safe version of C must be a subtype of every other pointer type, otherwise you couldn't e.g. return `NULL` where a `char*` was expected; similarly, the type of `undefined` in theoretical type-safe JavaScript must be a subtype of every other type in the language.

As a function return type, it's also very useful to have certain functions that never return. In a strongly-typed language with exceptions, for instance, what type should `exit()` or `throw()` return? They never return control flow to their caller. And since the bottom type is a subtype of every other type, it's perfectly valid for a function returning `Int` to instead return $\bot$—that is, a function returning `Int` can also choose not to return at all. (Maybe it calls `exit()`, or maybe it goes into an infinite loop.) This is good to have, because whether a function ever returns or not is famously undecidable.

Finally, it's very useful for writing constraints. Suppose you want to constrain all parameters on "both sides", providing a type that must be a supertype of the parameter, and another type that must be a subtype. Since bottom is a subtype of every type, you can express "any subtype of S" as $\bot \prec T \prec S$. Or, you can express "any type at all" as $\bot \prec T \prec \top$.
> 2 votes

# Answer
There is one use I can think of, and it's something that has been considered as an improvement to the Swift programming language.

Swift has a `maybe` Monad, spelled `Optional<T>` or `T?`. There are many ways to interact with it.

* You can use conditional unwrapping like

```
if let nonOptional = someOptional {
    print(nonOptional)
}
else {
    print("someOptional was nil")
}

```
* You can use `map`, `flatMap` to transform the values
* The force unwrap operator (`!`, of type `(T?) -> T`) to forcefully unwrap the contents, otherwise triggering a crash
* The nil-coalescing operator (`??`, of type `(T?, T) -> T`) to take its value or otherwise use a default value:

```
let someI = Optional(100)
print(someI ?? 123) => 100 // "left operand is non-nil, unwrap it.

let noneI: Int? = nil
print(noneI ?? 123) // => 123 // left operand is nil, take right operand, acts like a "default" value

```

Unfortunately, there was no concise way of saying "unwrap or throw an error" or "unwrap or crash with a custom error message". Something like

```
let someI: Int? = Optional(123)
let nonOptionalI: Int = someI ?? fatalError("Expected a non-nil value")

```

doesn't compile, because `fatalError` has type `() -> Never` (`()` is `Void`, Swift' unit type, `Never` is Swift's bottom type). Calling it produces `Never`, which isn't compatible with the `T` expected as a right operand of `??`.

In an attempt to remedy this, Swift Evolution propsoal `SE-0217` \- The “Unwrap or Die” operator was put forth. It was ultimately rejected, but it raised interest in making `Never` be a subtype of all types.

If `Never` was made to be a subtype of all types, then the previous example will be compilable:

```
let someI: Int? = Optional(123)
let nonOptionalI: Int = someI ?? fatalError("Expected a non-nil value")

```

because the call site of `??` has type `(T?, Never) -> T`, which would be compatible with the `(T?, T) -> T` signature of `??`.
> 2 votes

# Answer
Swift has a type "Never" which seems to be quite like the bottom type: A function declared to return Never can never return, a function with a parameter of type Never can never be called.

This is useful in connection with protocols, where there may be a restriction due to the type system of the language that a class must have a certain function, but with no requirement that this function should ever be called, and no requirement what the argument types would be.

For details you should have a look at the newer posts on the swift-evolution mailing list.
> 0 votes

---
Tags: type-theory, type-checking
---


# Question
Title: Predicate Logic - negating the conclusion to prove logical consequence?
In Predicate Logic, if you want to prove the logical consequence using the method of resolution, do you ALWAYS start off by negating the conclusion?

# Answer
> 1 votes
The method works in the same way as proofs by contradiction. Suppose you have a set of assumptions $A$ and you want to prove that formula $\phi$ is a logical consequence of the formulas in $A$. One of the ways to do this is as follows.

1. Put the negation of $\phi$ in your assumptions. So, now $A' = A\cup\\{\neg\phi\\}$
2. Show that $A'$ is inconsistent. Here, this means to consecutively apply the resolution step on (appropriately chosen) formulas of $A'$, until a contradiction $(T\to F)$ is reached.

Classical logic tells you that, if (a) the initial set of assumptions $A$ is consistent and (b) $A\cup\\{\neg\phi\\}$ is inconsistent, then $A\cup\\{\phi\\}$ is consistent and you can say that $\phi$ is a logical consequence of $A$. So, if steps (1) and (2) succeed, then $\phi$ is a logical consequence of $A$.

If you don't negate the goal when you put it in the set of assumptions and if you manage to show that $A\cup\\{\phi\\}$ is inconsistent, then $A\cup\\{\neg\phi\\}$ is consistent and therefore $\neg\phi$ is a logical consequence of $A$.

---
Tags: predicate-logic
---


title: Properties of reciprocal Quines

text:
# Question
Title: Properties of reciprocal Quines
I was reading about the concept of quine and in particolar of "reciprocal Quines" for example a Program $A$ that output the code of a program $B$ and vice versa, with the two being written in the same programming language.

Thinking of this particular case I have come to the conclusion that these two program must necessarily submit to certain properties. The first thing that came to my mind is the fact that they cannot have different cardinalities, the reason is easily understood: lets take the case that one of the two (lets say $A$) has a $\gt$ cardinality, so $\mid A \mid\gt\mid B \mid$.

Now we codify this example in a trivial way: $A = 1111$ (|A|=4) and $B = 111$ (|B|=3).
It is evident that $A$ can produce the $B$ code but the reverse cannot happen as $B$ has fewer bits than $A$. The only way for the game to work is that the programs have the exact same length and all the practical examples I have seen online (through high-level programming languages) seem to respect this "supposition" of mine.
A second thing I noticed is the fact that these two codes differ only by a short number of characters.

Am I making any mistakes in these considerations?
Is there a way to calculate the maximum number of difference characters that can exist between the two codes?

I would also appreciate if someone could indicate me some sources for the theoretical study of this particular case of quines, searching online I found only practical examples accompanied by brief explanations on the syntax of programming languages.

# Answer
> 4 votes
I don't see why they should have the same length, given that one can succinctly output large amounts of whitespace using something like

```
for i=1 to 1000 do
    print " "

```

So, given any mutual Quines $A$ and $B$, one could surely add 1000 spaces to $A$ and 2000 spaces to $B$ and adjust the programs to use `for` loops like the above.

---
Tags: programming-languages, strings
---


title: Floating point arithmetic

text:
# Question
Title: Floating point arithmetic
I need to change x1 = 0.3 and x2 = -0.29 to a FP(floating point) number with one sign bit, a 4 bit mantissa, a 3 bit exponent. The results I got are:

x1: 0 001 0011

x2: 1 001 0010

I am also trying to calculate the number of significant digits of x1 and x2 and I have found 2 for each, but I am unsure of this result.

The question also requires me to find z = (FP)x1 + (FP)x2 and the number of significant digits of z. But I am not sure how to proceed with this part of the question. Therefore, any guidance on how I could proceed would be greatly appreciated.

Thank you very much!

# Answer
> 7 votes
Firstly, you need to decide if the floating point numbers you are working with are "***normalized***" or not.

Think about how binary numbers are represented in scientific notation.

Consider the number `100101.010101`
The expression given above is ***not*** given in scientific notation, but what if we change that?
To re-write `100101.010101` in scientific notation, we move the binary point to the left until we have $1.\[\text{something}\] * 2^{\text{some power}} $
For the specific example I gave, we have $(1.00101010101)\_2\*(2^5)\_{10}$
Note that binary numbers written in scientific notation almost always begin as `<one><dot><something>`

As such, most computers today do not store the leading $1$. Normally, this leading $1$ would be the most significant bit of the mantissa. However, its existence is implied in normalized numbers. There is only one number whose binary scientific notation representation does not begin as "one-dot-something." That number, is zero. As such `1.0000[...] * 2 ^ [some large magnitude negative number]` represents the number zero in many computer systems today.

---

You say that you want to represent $0.3$ as a floating point number.

First, I think it will help to represent $(1/2), (1/4), (1/8), (1/16),$ etc... in decimal form.

$(1/2) = 0.5$
$(1/4) = 0.25$
$(1/8) = 0.125$
$(1/16) = 0.0625$ $(1/32) = 0.03125$ $(1/64) = 0.015625$

Okay; $0.3 = 0.25 + 0.05$
$0.25 = (1/4)$. $0.05$ is the leftover remainder.

$0.05 = 0.03125 + 0.01875$
$0.03125 = (1/32)$.
$0.01875$ is the leftover remainder.

Okay; $0.3 = 0.25 + 0.03125 + 0.015625 + 0.00029296875$

We have $0.3 = (1/4) + (1/32) + (1/64) + 0.00029296875$
$(0.3)\_{10} = (0.010011)\_{2} + $ a remainder of $(0.00029296875)\_{10}$

You said that you only wanted a 4 bit mantissa. I think our leftovers/remainder are small enough at this point.

Let's write the number in scientific notation.

$(0.3)\_{10} = (1.0011)\_{2} \*(2^{2})\_{10} + $ a remainder of $(0.00029296875)\_{10}$

I suppose we want the exponent in binary-format instead of decimal. We can do this:

$(0.3)\_{10} \approx (1.0011)\_{2} \*(2)\_{10}^{(100)\_{2}}$

```
SIGN: POSITIVE
MANTISSA: 10011
EXPONENT: 100

```

You wanted a 4 bit mantissa, but I went out to 5 bits. We round the number to obtain that $0.3$ is represent-able as:

```
SIGN: POSITIVE
MANTISSA: 1001
EXPONENT: 100

```

A normalized float would omit the leading $1$ of the mantissa. However, simply explain in your homework, that it was not specified whether the float be normalized or non-normalized. Therefore, you chose to use non-normalized floating point numbers.

---

You asked about ***significant figures***. There are many different definitions of "***significant figure***." All of these different definitions are about how many of the leftmost digits of the approximation are correct.

Imagine writing two numbers lined up on a sheet of paper

```
APROX: 0.00070384
EXACT: 0.00070392

```

Now, cover-up the rightmost digits with a blank sheet of paper

```
APROX: 0.0007
EXACT: 0.0007

```

They are both correct for the number `7`. That's good. slide the topmost sheet of paper to the right

```
APROX: 0.00070
EXACT: 0.00070

```

They're still the same. That's 2 significant figures so far.

```
APROX: 0.000703
EXACT: 0.000703

```

Still the same up to 3 figures.

```
APROX: 0.0007038
EXACT: 0.0007039

```

Uh oh; `8` and `9` are different. So the exact value, and the approximation are the same up to 3 significant figures, but ***not*** 4 significant figures.

The above method does not work very well.

Note that `0.499999999999999999999999999999` is a ***very good*** approximation of `0.5` However, if you use the sliding paper method, then not a single digit matches, and so, the approximation is not correct to even 1 significant figure!

My procedure for calculating significant figures will be different from the sliding paper method. The procedure is as follows:

1. Put the exact value in scientific notation.
2. Put the approximate value almost in scientific notation. However, make sure the approximate number has same exponential term as the exact value. Maybe the approximation is not of the form X.XXX Maybe the approximate number looks like 0.0XXXX or XXX.X
3. Subtract the approximate from the exact, or vis versa.
    4. The number of significant digits is the number of zeros on the left. For example, `0.000XXX` means 4 significant figures. `0.XXXXX` means 1 significant figure.

To calculate teh number of significant figures, convert your floating-point number back into decimal:

```
SIGN: POSITIVE
MANTISSA: 1001
EXPONENT: 100

```

$(1.0011^{100})\_{2} = (0.28125)\_{10}$

Notice that the floating point approximation is not the same as the exact value of $0.3$
Just how different are they?

$3.0 \*\text{some exponent} - 2.8125 \*\text{the same exponent} = 0.1875$

The floating point approximation of `0.3` is correct to 1 significant figure.

Repeat the process for `-0.29`:
1. Calculate the floating point approximation.
2. Take the difference between the approximation and the exact value. 3. Count the number of leftward zeros in the difference.

$-0.29 = -(1/4 + 1/32 + 0.00875)$

Note that the remainder $0.00875$ is less than $(2^-6)$. Your mantissa is only 4 bits long, so we needn't worry about the remainder.

$-0.29 \approx -(1/4 + 1/32)$
$-0.29 \approx -0.28125$
$2.9 - 2.8125 = 0.0875$
The floating point approximation of 0.29 is correct to 2 significant figures.

---

The exact value of `0.3 + -0.29` is `0.01`.

Compute the following:

```
(float approx of 0.3) + (float approx of -0.29) =
(2.8125) + -0.28125) =
0

```

Then compare the approximate value (`0`) to the exact value (`0.1`) for the number of significant figures of $z = float(x\_1) + float(x\_2)$

1.0 - 0.0 = 1.0

The result has zero significant figures of accuracy.

Note that your textbook's definition of significant figures is probably different than mine. In your homework, explain to your teacher what definition you used. The concept of significant figures is more important that the details. Knowing roughly how many digits of the approximation are correct is more important than knowing exactly how to compute the number of significant figures.

---
Tags: floating-point
---


# Question
Title: NL - iterating all edges of a graph in log space
Given a turing machine which has logrtmic space, and consists of an input tape and a working tape, Is it possible to iterate all egdes of an input graph? I know the answer is probably NO, because clique and other similer NP problems belongs to NP and not to NL. Unfortunately, I can't find a satisfying and clear explanation to that fact. Can some one make it more clear for me?

# Answer
There's absolutely no problem to iterate over all edges in a graph in logspace (even deterministic logspace!). The details depend on how the graph is encoded. For example, if the graph is encoded as an adjacency matrix, then you can simply go over all pairs of vertices.

However, this doesn't give an NL algorithm for clique. The problem is that you need to iterate on $k$-tuples of vertices, for non-constant $k$. This is something you cannot do in logspace.

NP is sometimes described in terms of witnesses. However, the "official" definitions is using nondeterministic Turing machines, which are allowed to have more than one correct move at any given point in time. The class of languages accepted by nondeterministic polytime Turing machines coincides with the class of languages which are given a polynomial size witness and can verify it in polynomial time. Unfortunately, there is no such alternative description for nondeterministic logspace Turing machines.
> 6 votes

# Answer
You can iterate over the edges of a graph in logarithmic space, since all that is required in order to do so is a counter up to the number of edges. Note that the hardness of clique and other hard problems in NP does not lie in simple iteration, but in detecting different structures in your input which are not apparent (e.g. a clique of a large enough size).

Additionally, languages decidable by Turing machines which are not able to read the entire input are decidable in constant time, so not being able to iterate over the entire input is not interesting in the standard Turing machine model (as opposed to random access).
> 3 votes

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


# Question
Title: How to find highest normal form of a relation, given its functional dependencies
Let's say that I have a relational model, defined as:

$$X(A,B,C,D,E,F,G)$$ with the functional dependencies: $$f\_1: \\{A,B,C\\} \to \\{D,E,F,G\\}$$ $$f\_2: \\{A,B\\} \to \\{C\\}$$

Using this information I need to determine the highest normal form (for us it's BCNF) that this relation will go to. It's clear that the relation is already in it's atomic form, therefore it's already in it's first normal form. The to proceed to the second normal form, I found that the candidate key is $\\{A,B\\}$ and since all non prime attributes are fully dependent on the candidate keys, it's in the second normal form. But from this point I'm not sure where to go because all the non prime attributes (excluding $C$), $D,E,F,G$ are dependent on $C$ which is also a non prime attribute.

How can I separate this relation and proceed to the third normal form?

PS - I'm not sure if this is the right place to ask a database question but since the stack exchange for database is for professionals, I thought I should post it here. If someone knows a better stack exchange for this sort of a question, I'll transfer it over to that one.

# Answer
> 1 votes
In your example $C$ is derived attribute from $A, B$, but none of: $D, E, F, G$ is more dependent on $C$ than $A, B$, or solely functionaly dependent on $C$, so there is no transitive dependency. Since you have 2NF it is in 3NF.

For BCNF it is sufficient to be in 3NF and do not have overlapping candidate keys, which you do not have, hence it is in BCNF.

---
Tags: data-structures, database-theory, databases
---


# Question
Title: The Ising Model and Computational Complexity
I've been told recently that one can use the Ising model can find solutions to certain NP-hard problems, such as Clique, although it doesn't do so in polynomial time.

Googling gets a few Arxiv results but where might I find an introduction to this interesting relationship?

# Answer
Finding the minimal energy configuration in the Ising model is NP-hard, and many problems can be directly reduced to it. For a list, including Karp's original 21 NP-hard problem see e.g. Ising formulations of many NP problems. The Ising model is also equivalent to unconstrained quadratic binary optimization which also can be used to model a large number of other NP-complete problems, see e.g. A unified modeling and solution framework for combinatorial optimization problems.
> 3 votes

---
Tags: complexity-theory, reference-request, np-hard, physics
---


# Question
Title: cheap multi agent path planning algorithms
I am trying to make a tower defence game where some critters are trying to make their ways through a 2D grid-like obstacle course. The idea is these critters cannot walk into the obstacles or into each other during their path, and they would like to get to the other side as soon as possible.

I just need a cheap, not-optimal solution that can path all the agents from one side of the map to another, moving in the grid (up-down-left-right) directions while not walking into each other nor into the obstacles.

I am not wanting an optimal solution, just one that looks reasonably greedily optimal would be nice (i.e. not like not moving the 2nd agent without completing the path on the first agent, etc).

I'm thinking about something with potential fields with a little bit of A\* is as much as I am willing to compute. If there's anything simple to implement I'd be happy to know ! !

# Answer
> 1 votes
I would do a unique breadth exploration from the exit to get the shortest **distance to exit** of any position. Only obstacles (like walls) should be considered, not critters. This exploration should be done again each time an obstacle is added or removed. With some optimization, you may not have to recompute all the positions.

Then each time a critter should move, check if any accessible position has a better (lower) **distance to exit**. If not, the critter stay in position, else it moves to the one with the lowest **distance to exit**.

By "any accessible position", you can consider either up-down-left-right or something more complicated (moving more than one space, jumping obstacles and so on...).

# Answer
> 0 votes
A possible approach can be to use similar techniques to the ones used to solve some variants of sokoban.
First, you need to solve a one-to-all shortest path, in order to obtain the distance between any vertex and the destination on your original graph `G`, taking in account the obstacles, but not the critters.
Once you have that, you can consider the graph of configurations. A vertex of this graph is a configuration, meaning a representation of `G` along with the position of your critters.
You can define a heuristic `h`, which to a configuration associates a distance estimation, in this case the sum of the distances between the critters and the arrival.
All you have to do then is to run an A\* algorithm on the graph of configurations. When you are in a configuration, the reachable configurations are the configuration where one of your critters has moved of one step on the grid.
The origin configuration is `G` with the critters in their original positions, and the destination configuration is `G` with the critter all on the destination vertex. The heuristic for A\* is the one defined above.

---
Tags: a-star-search
---


title: Number of nil-links in a binary tree

text:
# Question
Title: Number of nil-links in a binary tree
In its section Properties of binary trees Wikipedia states:

> The maximum possible number of null links (i.e., absent children of the nodes) in a **complete** binary tree of n nodes is (n+1), where only 1 node exists in bottom-most level to the far left.

I wonder about the precise statement used here. In my opinion *every* binary tree with $n$ nodes has *exactly* $n+1$ nil links (or missing children). A proof by induction is easy. (In fact that is equivalent to the statement some lines above: "a perfect binary tree with $\ell$ leaves has $n=2\ell-1$ nodes".)

Question: what am I missing here? Has Wikipedia different assumptions on binary trees?

As an illustration, a non-complete binary tree with 12 nodes and 13 nil-pointers, marked as square nodes. It can also been seen as a perfect binary tree with 25 nodes, the squares indicating leafs.

# Answer
> 2 votes
The Wikipedia article defines a *null links* as "absent children of the nodes", presumably "absent" in the sense of what nodes are missing to obtain a perfect binary tree (i.e., "a binary tree in which all interior nodes have two children and all leaves have the same depth or same level"). Under this definition, leaves (i.e., the nodes in the last level of the tree) do not have links. Hence, because all other levels are filled, to determine the number of null links you need only look at the previous to last level of the tree. This also explains the maximum case (i.e., "where only 1 node exists in bottom-most level")

---
Tags: binary-trees
---


# Question
Title: Existence of path under weight and value budgets
Consider the following problem:

> Input: An undirected graph $G = (V, E)$, each edge has a non-negative weight $w\_i$ and a non-negative value $v\_i$. There are two vertices to represent start point $s$ and end point $t$. We are also given two values $W,V$.
>
> Decide whether there is a simple path from $s$ to $t$ with total weight at most $W$ and total value at most $V$.

How do I show that the problem is NP-hard by reduction from PARTITION?

# Answer
Here is the idea of the reduction; I'll let you fill in the details.

We are given an instance of the partition problem, consisting of numbers $x\_1,\ldots,x\_n$ summing to $S$. We construct a (non-simple) graph on the vertex set $s = v\_0,\ldots,v\_n = t$. For $i=1,\ldots,n$, there are two edges from $v\_{i-1}$ to $v\_i$: one with weight $x\_i$ and value $0$, and one with weight $0$ and value $x\_i$. Our target weight and value are both $S/2$.

I'll let you figure out why this works, and convert it to a simple graph.
> 1 votes

---
Tags: graphs, np-hard
---


# Question
Title: Non-existence of approximation algorithm for the knapsack problem
I am working on the following exercise: Prove that if $P \neq NP$, there cannot exist an approximation algorithm $A$ for the knapsack problem (KP) such that $\exists k \in \mathbb{N}, \forall I \in S: OPT(I) - P\_A(I) \leq k$ where $OPT(I)$ is the optimal profit on instance $I$ and $P\_A(I)$ is the profit calculated by $A$.

I know that there is a FPTAS $A'$ for the KP which guarantees a solution with profit $P\_{A'}(I) \geq (1 - \varepsilon)OPT(I)$ on any instance $I$ and $\varepsilon \> 0$.

My approach is to create a contradiction. For this I consider $A = A'$ and aim to show that $P\_A(I) \geq (1 - \varepsilon)OPT(I) \geq ... \geq OPT(I) - c$ where $c \in (0,1)$ is a constant. This way, for an adequate choice of $\varepsilon$ I would show that we obtain an optimal solution within polynomial time. However, I struggle how to choose $\varepsilon$.

I need some advice on how to proceed. Many thanks in advance!

# Answer
> 3 votes
Given an instance of knapsack, multiply all values by $k+1$. Any solution satisfyign $OPT(I) - P\_A(I) \leq k$ is in fact optimal, so you could use such an algorithm to solve knapsack.

---
Tags: approximation, randomized-algorithms, knapsack-problems
---


title: What is a constructor in java?

text:
# Question
Title: What is a constructor in java?
I have checked many websites but did not get the right answer. what is the meaning of constructor in java?

# Answer
> 0 votes
Constructors are used to initialize the object’s state. Like methods of, a constructor also contains collection of statements(i.e. instructions) that are executed at time of Object creation.A constructor is invoked at the time of object or instance creation.

---
Tags: java
---


# Question
Title: Find candidate keys given functional dependencies
In my database class we practiced how to find the candidate keys, given the functional dependencies. However they were easy examples, based on a single attribute being functionally dependent on a single attribute but in our book it gives the following example of more complex functional dependencies. Let's say that I have the following relationship:

$$R(A,B,C,D,E,F)$$

with the following functional dependencies:

$$f\_1: \\{A,B,C\\} \to \\{D,F\\}$$ $$f\_2: \\{D,E,F\\} \to \\{A,C,E\\}$$ $$f\_3: \\{D\\} \to \\{B\\}$$

and I need to find all the candidate keys. Because we need at least $3$ of the attributes to make candidate keys. Through writing out each of the tuples made up of $3$ or more attributes, I found that $\\{A, D,E,F\\}$, $\\{A,B,C,E\\}$, $\\{D,E,F\\}$ and $\\{A,C,D,E\\}$ are all candidate keys. However the catch is that either $\\{A, D,E,F\\}$, $\\{A,B,C,E\\}$ or $\\{D,E,F\\}$,$\\{A,C,D,E\\}$, $\\{A,B,C,E\\}$ are the candidate keys.

I think that because the definition of a candidate key is that there can't be a subset of it that's also a candidate key. Using this logic, $\\{A, D,E,F\\}$ would also not be candidate key as $\\{D,E,F\\}$ is already a candidate key. Therefore, the final candidate keys would be:

$$\\{D,E,F\\},\\{A,C,D,E\\}, \\{A,B,C,E\\}$$

Is my understanding of the topic correct or have I gone of the rails?

# Answer
> 4 votes
Assuming that the three dependencies are a cover of the dependencies of the relation schema R, to find all the candidate keys we could start from a canonical cover of the FDs, for instance the following one:

```
{ A B C → D
  A B C → F
  D E F → A
  D E F → C
  D → B }

```

From these dependencies we can see that `E` must belong to all the candidate keys, since it does not appear in any right part.

We can start now from the left hand parts of the dependencies to see if their closure contains all the attributes:

```
ABC+ = ABCDF

```

by adding `E` (that must be present in every candidate key) we discover the first candidate key, since `ABCE+ = ABCDEF`.

Then from `DEF`:

```
DEF+ = ACBDEF

```

so this is already a candidate key.

Finally, starting from `D` we found that:

```
D+ = DB

```

trying again to add `E`, we find:

```
DE+ = BDE

```

we can now try to add `A`:

```
ADE+ = ABDE

```

which is still not a candidate key, and finally adding `C` we find the last candidate key:

```
ACDE+ = ABCDEF

```

---
Tags: data-structures, database-theory, databases
---


# Question
Title: in function declarations, what advantages are there to having the type of the parameter specified after the parameter name?
For typed languages, what advantages/disadvantages are there to specifying the parameter type after the parameter name?

For languages like ~~C~~ and Java, the type comes first:

```
void myfunc(TypeA param1, TypeB param2);

```

For other languages like Scala, Rust, etc, the type comes after the parameter name:

```
fn myfunc(param1: TypeA, param2: TypeB) {}

```

What advantages are there to this approach? I could see in languages where specifying a type is optional (or inferred) and can be left off, but at least for Rust types have to be specified in a function's parameter list.

# Answer
It's completely arbitrary.

In a given programming language, one would hope that the same convention is used throughout, so either `int f(int x)` or `f(x: int): int` but not `int f(x: int)` or `f(int x): int`; but even that is arbitrary.
> 4 votes

# Answer
No, in C it’s not type followed by parameter name. It is a declaration, where the parameter name can be found in many positions.

```
int f (int (*p)());

```
> 3 votes

# Answer
This is largely an arbitrary choice. One language did it some way, a long time ago, and then many but not all other languages copied a familiar syntax. That being said, the choice is not *completely* arbitrary. Putting the type before or after the variable name is largely cosmetic, but there are more differences than this between the C-style syntax and the Pascal-style syntax used in languages like Rust and Scala.

In early languages where variable declarations had a type, the syntax of a declaration was of the form `*Type* *Name*` where `*Type*` is a reserved word and `*Name*` is a name chosen by the programmer. Here the order is not arbitrary: first you say what kind of thing you're declaring, then you give it a name. Compilers at the time were very primitive and needed to know early on what they were parsing; writing `INTEGER X` let the compiler know immediately that it had to work on an integer declaration, whereas `X INTEGER` would have required the compiler to first remember that it had seen `X` and only after that it would have known that it was supposed to declare an integer variable. Languages of the 1950s and 1960s such as ALGOL and FORTRAN tended to use this syntax. Interestingly, at the time, in programming language descriptions, “type” had a more general meaning that it has today: today it has a specific technical meaning that's more or less synonym with “datatype”, but at the time it had its ordinary English meaning, which could cover things like integer and real, but also things like label and statement.

extended this syntax in a way that allowed defining **compound types**. In C, the syntax of a variable declaration mimics the syntax of its use. For example, `int x` declares an integer called `x`, and `int *p` declares a pointer-to-integer called `p`, and the expression `*p` has the type `int`. This syntax is not purely prefix because accessors can be suffixes: for example `a[1]` is an `int` if `a` is an array of `int` values, so the syntax to declare an array of integers is `int a[]`.

C became a very popular language, so many languages after it retained a similar syntax for several things including variable declarations and types.

The colon syntax goes back to at least Pascal in 1971. This is the syntax used by computer scientists at least since the early 1970s. I suspect that it started in theory papers and was adopted by Pascal and later by other languages, but for all I know it may have originated with Pascal. Why colon to denote that a value belongs to a type? discusses the origin of $x : T$ in computer science. Modern languages that draw from modern (or not-so-modern-anymore) theory tend to use the syntax that's familiar to computer scientists, including ML, Scala, Swift, Rust, and many others. Haskell is somewhat unusual in using a double colon `::` where others use a colon `:`.

The order $x : T$ vs $T : x$ is arbitrary: these days, compilers don't mind, and for humans, it's just a matter of habit. However, having a punctuation sign between the variable name and the type is not arbitrary. Most languages that use this syntax also allow the left-hand side to be an expression, to form a type annotation. More importantly, the right-hand side is a **type expression**, not just a type name. Recall that C supports declarations of variables with compound types, but the syntax is somewhat awkward, with the variable name ending up somewhere in the middle. C's syntax does not work with compound types that are made of more than one type part. For example, in ML, `x : bool * int * string` means that `x` is a triple consisting of a boolean, an integer and a string. Haskell writes this `x :: (Bool, Integer, String)`. Both the ML and the Haskell way allow building complex types. The C approach fails: where do you put the variable name?

Languages such as Java and C# deviate from the C syntax by putting the whole type information before the variable name: `int[] a`, `(bool, int, string) x`, `List<int> v`. With no separator, it's impractical to allow both sides to have an arbitrary length, but these languages do support type expressions, which can be used to declare a variable.
> 3 votes

---
Tags: programming-languages
---


# Question
Title: Intuition behind eigenvalues of an adjacency matrix
I am currently working to understand the use of the Cheeger bound and of Cheeger's inequality, and their use for spectral partitioning, conductance, expansion, etc, but I still struggle to have a start of an intuition regarding the second eigenvalue of the adjacency matrix.
Usually, in graph theory, most of the concepts we come across of are quite simple to intuit, but in this case, I can't even come up with what kind of graphs would have a second eigenvalue being very low, or very high.
I've been reading similar questions asked here and there on the SE network, but they usually refer to eigenvalues in different fields (multivariate analysis, Euclidian distance matrices, correlation matrices ...).
But nothing about spectral partitioning and graph theory.

Can someone try and share his intuition/experience of this second eigenvalue in the case of graphs and adjacency matrices?

# Answer
> 6 votes
The second (in magnitude) eigenvalue controls the rate of convergence of the random walk on the graph. This is explained in many lecture notes, for example lecture notes of Luca Trevisan. Roughly speaking, the L2 distance to uniformity after $t$ steps can be bounded by $\lambda\_2^t$.

Another place where the second eigenvalue shows up is the planted clique problem. The starting point is the observation that a random $G(n,1/2)$ graph contains a clique of size $2\log\_2 n$, but the greedy algorithm only finds a clique of size $\log\_2 n$, and no better efficient algorithm is known. (The greedy algorithm just picks a random node, throws away all non-neighbors, and repeats.)

This suggests *planting* a large clique on top of $G(n,1/2)$. The question is: how big should the clique be, so that we can find it efficiently. If we plant a clique of size $C\sqrt{n\log n}$, then we could identify the vertices of the clique just by their degree; but this method only works for cliques of size $\Omega(\sqrt{n\log n})$. We can improve this using spectral techniques: if we plant a clique of size $C\sqrt{n}$, then the *second eigenvector* encodes the clique, as Alon, Krivelevich and Sudakov showed in a classic paper, *Finding a Large Hidden Clique in a Random Graph*.

More generally, the first few eigenvectors are useful for partitioning the graph into a small number of clusters. See for example Chapter 3 of lecture notes of Luca Trevisan, which describes higher-order Cheeger inequalities.

# Answer
> 7 votes
(Disclaimer: This answer is about eigenvalues of graphs in general, not the second eigenvalue in particular. I hope it is helpful nevertheless.)

An interesting way of thinking about the eigenvalues of a graph $G = (V, E)$ is by taking the vector space $\mathbb{R}^n$ where $n = |V|$ and identifying each vector with a function $f\colon V \to \mathbb{R}$ (i.e., a vertex labeling). An eigenvector of the adjacency matrix, then, is an element of $f \in \mathbb{R}^n$ such that there is $\lambda \in \mathbb{R}$ (i.e., an eigenvalue) with $A f = \lambda f$, $A$ being the adjacency matrix of $G$. Note that $A f$ is the vector associated with the map which sends every vertex $v \in V$ to $\sum\_{u \in N(v)} f(u)$, $N(v)$ being the set of neighbors (i.e., vertices adjacent to) $u$. Hence, in this setting, the eigenvector property of $f$ corresponds to the property that *summing over the function values* (under $f$) *of the neighbors of a vertex yields the same result as multiplying the function value of the vertex with the constant $\lambda$*.

# Answer
> 6 votes
I think for most things it's more productive to look at the Laplacian of the graph $G$, which is closely related to the adjacency matrix. Here you can use it to relate the second eigenvalue to a "local vs global" property of the graph.

For simplicity, let's suppose that $G$ is $d$-regular. Then the normalized Laplacian of $G$ is $L= I - \frac1d A$, where $I$ is the $n\times n$ identity, and $A$ is the adjacency matrix. The nice thing about the Laplacian is that, writing vectors as functions $f: V\to \mathbb{R}$ like @dkaeae, and using $\langle \cdot, \cdot \rangle$ for the usual inner product, we have this very nice expression for the quadratic form given by $L$: $$ \langle f, Lf\rangle = \frac{1}{d} \sum\_{(u,v) \in E}{(f(u) - f(v))^2}. $$

The largest eigenvalue of $A$ is $d$, and corresponds to the smallest eigenvalue of $L$, which is $0$; the second largest eigenvalue $\lambda\_2$ of $A$ corresponds to the second smallest eigenvalue of $L$, which is $1 - \frac{\lambda\_2}{d}$. By the min-max principle, we have

$$ 1 - \frac{\lambda\_2}{d}=\min\left\\{\frac{\langle f, Lf\rangle}{\langle f, f\rangle}:\sum\_{v \in V}{f(v)} = 0, f \neq 0\right\\}. $$

Notice that $\langle f, Lf\rangle$ does not change when we shift $f$ by the same constant for every vertex. So, equivalently, you can define, for any $f:V \to \mathbb{R}$, the "centered" function $f\_0$ by $f\_0(u) = f(u) - \frac{1}{n}\sum\_{v \in V}{f(v)}$, and write

$$ 1 - \frac{\lambda\_2}{d}=\min\left\\{\frac{\langle f, Lf\rangle}{\langle f\_0, f\_0\rangle}: f \text{ not constant}\right\\}. $$

Now a bit of calculation shows that $\langle f\_0, f\_0\rangle = \frac{1}{n}\sum\_{\\{u,v\\}\in {V\choose 2}}{(f(u) - f(v))^2}$, and substituting above and dividing numerator and denominator by $\frac{n}{2}$, we have

$$ 1 - \frac{\lambda\_2}{d}=\min\left\\{\frac{\frac{2}{nd} \sum\_{(u,v) \in E}{(f(u) - f(v))^2}}{\frac{2}{n^2}\sum\_{\\{u,v\\}\in {V\choose 2}}{(f(u) - f(v))^2}}: f \text{ not constant}\right\\}. $$

What this means is that, if we place every vertex $u$ of $G$ on the real line at the point $f(u)$, then the average distance between two independent random vertices in the graph (the denominator) is at most $\frac{d}{d - \lambda\_2}$ times the average distance between the endpoints of a random edge in the graph (the numerator). So in this sense, a large spectral gap means that what happens across a random edge of $G$ (local behavior) is a good predictor for what happens across a random uncorrelated pair of vertices (global behavior).

---
Tags: graphs, adjacency-matrix
---


# Question
Title: Confused between bandwidth and frequency
I am new to Computer Science and started learning about computer networking very recently. I know that *bandwidth* means how many bits can be sent through the channel in 1 second. However, recently I came across another definition of bandwidth which says it is the range of frequency where the signal is received.

How to think intuitively of this? *Frequency* is the number of cycles per second. **What is the relation between frequency and bandwidth?**

Please note that I am a lay man. Kindly elaborate.

# Answer
"Bandwidth" has several different meanings. Among others, it can refer to either a frequency range or to data rate in bits/second. You have to use the context to figure out which is meant.

These two notions of bandwidth are not directly related, but a signal with a wider frequency range (i.e., higher signal bandwidth) can usually transmit data at a higher rate (i.e., has higher data bandwidth). However, the relation also depends on how much noise is present.
> 0 votes

---
Tags: computer-networks
---


# Question
Title: How to solve the optimization of bin packing using the decision version
Let us say the optimization version of the bin packing problem asks you to give a packing using the fewest bins possible and the decision version asks if it is possible to pack the bins into $k$ bins.

> How can you reduce the optimization version to the decision version?

If you only have to answer what the fewest bins possible is then it is clear you can use binary search. But if you actually have to give the packing, I can't see how to do it.

# Answer
If you could solve the decision problem (do these items fit in k bins) you can obviously solve the optimisation problem (what is the minimum number of bins) using binary search. But you actually want to know what to put into each box. That’s easily done doing the decision problem at most n^2 times.

Let’s say you know k boxes are required and sufficient. Sort the item by descending size. Replace the biggest and second biggest item with one item of their combined size and check if the new items fit into k bins. If not, try the largest and third largest item, and so on. After n attempts, you either know two items that are in the same bin in an optimal solution, or you know the largest item is on its own. And you repeat that, each time you find that you can put two items in the same bin by solving at most n decision problems.
> 2 votes

# Answer
This answer will probably be quite annoying...

To be explicit, your bin packing problem is: find a way of assigning items of size $s\_1, \dots, s\_k$, to the minimum number of bins such that no bin contains items of total size more than $t$.

Consider the following problem, Non-Uniform Bin Packing: the input is a list of bin sizes and item sizes and we want to know if we can put all the items in the bins so no bin is overflowing. This problem is clearly in **NP**: an assignment of items to bins is of polynomial size with respect to the input, and we can check in polynomial time if none of the bins are overflowing. Since this problem is in **NP**, it can be reduced to Bin Packing, which is **NP**-complete. (This is the annoying part: I've not said how to perform this reduction, because I've not managed to figure it out.)

We can use Non-Uniform Bin Packing to solve your problem in the usual way. We build up the solution by asking, for each item in turn, whether that item can go in each bin. First, as you describe, use binary search to find out how many bins we need; call this $d$. Then, suppose we have a partial solution, in which we have placed items $1, \dots, i$ into bins, and the remaining capacities of the bins are $c\_1, \dots, c\_d$ (our initial partial solution is that $i=0$, i.e., we've placed no items, and the remaining capacities are $t, \dots, t$). Then, just try placing the $(i+1)$st item in each bin in turn until the Non-Uniform Bin Packing algorithm says that there is a solution for items $i+2, \dots, k$ in the remaining bin capacities. That is, we ask in turn if items $i+2, \dots, k$ can be placed in bins with capacities $c\_1-s\_{i+1}, c\_2, \dots, c\_d$, then $c\_1, c\_2-s\_{i+1}, c\_3, \dots, c\_d$, then ... and finally $c\_1, \dots, c\_{d-1}, c\_d-s\_{i+1}$. Do this until you've placed each item and you have your assignment.
> 1 votes

# Answer
There is some inconsistency about whether, in the context of complexity analysis, an optimization problem is defined as asking for the optimal *solution* or the optimal *objective function value*. For example, Wikipedia's entry on decision problems says:

> There are standard techniques for transforming function and optimization problems into decision problems. For example, in the traveling salesman problem, the optimization problem is to produce a tour with minimal weight. The associated decision problem is: for each $N$, to decide whether the graph has any tour with weight less than $N$. By repeatedly answering the decision problem, it is possible to find the minimal weight of a tour.

The second sentence defines the optimization problem as *producing the optimal tour*, whereas the last sentence implicitly defines it as *producing the weight of the optimal tour*.

Similarly, the entry on optimization problems says:

> For example, if there is a graph $G$ which contains vertices $u$ and $v$, an optimization problem might be "find a path from $u$ to $v$ that uses the fewest edges". This problem might have an answer of, say, 4.

But 4 is not an "answer" to the problem of "find\[ing\] a path". So, this quote, too, is inconsistent about whether the optimization problem means finding the optimal solution or finding the optimal objective function value.

I am not trying to wade into a debate here about the quality of Wikipedia entries; I'm just trying to make the point that in common usage, there is an inconsistency about the way "optimization problem" is used, and that inconsistency can lead to confusion about the relationship between decision and optimization problems.

Now, back to your original question. If what you are asking is:

> How can you reduce the "find the optimal solution" version of the optimization problem to the decision problem?

then I don't know of a way to do this, though @David Richerby gives one in his answer.

If what you are asking is:

> How can you reduce the "find the optimal objective function" version of the optimization problem to the decision problem?

then the answer is, using binary search, as you have pointed out.

And if what you are really asking is:

> Why does everyone say you can reduce the optimization problem to the decision problem, when it seems impossible?

then my answer is, when people say you can reduce the optimization problem to the decision problem, they mean the "find the optimal objective function" version of the optimization problem, but they are not always sufficiently clear in articulating that.

Now, from a *practical perspective*, if you are actually going to solve the decision problem, you usually run some algorithm that determines whether the items can be packed into $k$ bins. That algorithm is most likely going to do the packing, so in the course of your binary search, you will find the actual packings.
> -2 votes

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


# Question
Title: Linked list: advantages of preventing movement of nodes and invalidating iterators on add/remove
C++ and Java include native classes for linked lists, C++ std::list and Java LinkedList

For C++ std::list, nodes can be "moved" within a list, or from list to list (if the lists are compatible), via std::list::splice(), which in turn is used by std::list::merge() and std::list::sort().

With Java's native LinkedList, there is no method like splice() to move nodes. Attempting to emulate splice() by using `listiterator add(element)` and `listiterator remove()` methods doesn't work because `add` or `remove` will invalidate all iterators for a list other than the iterator used to do the `add` or `remove`. The indexed based `get(index)`, `add(index, element)` and `remove(index)` functions could be used, but have time complexity O(n).

As for C++ std::list versions of add and remove, note that std::list::insert() doesn't invalidate any iterators, and std::list::erase only invalidates iterators that point to deleted nodes, and depending on the compiler, iterator invalidation may only occur with a debug build, while a release build (meant for speed) will not invalidate any iterators.

I ran into this issue with an SE question about implementing a merge sort with Java's native `LinkedList`. With C++, merge sort can be implemented using iterators using either top down (uses stack to store iterators) or bottom up (uses small (26 to 32) array of iterators), both of which sort a list by moving nodes within the original list via splice(), using the iterators as pointers to sorted run boundaries.

Why does Java's native LinkedList not include a splice method?

---

Some background on C++ and Java linked lists:

C++ std::list is usually implemented as a doubly linked list. I'm not aware of any exceptions to this, but it's possible since the standard doesn't require specific implementations. std::list is a standalone class. Visual Studio implements std::list as a circular doubly linked list with a dummy node. std::list::end is an iterator to the dummy node.

Java LinkedList is always implemented as a doubly linked list, and part of the ArrayList family of classes.

# Answer
> 4 votes
I think this is due to the differences in the philosophy underlying the design of both programming languages. The C++ philosophy allows data structures to cause *undefined behavior* as soon as the user violates an invariant, while Java wants to avoid that in all cases. Java aims to raise exceptions when invariants are broken, or, when that can not be detected, to allow *unspecified results* when the invariant is broken.

This is not just a "C++ vs Java" difference, but a general difference in programming languages between the philosophies "undefined behavior can happen if you're not careful" and "undefined behavior can't happen, ever, and I'll try hard to report errors at runtime".

> Existing iterators, being pointers to nodes, are not invalidated by moving, adding, or removing nodes, as long as the iterators don't point to nodes that are later deleted.

The last part is crucial. C++ can say "iterators are invalidated", while Java wants to detect if those are used after they are invalidated (and raise an exception).

Detection can be expensive, and require each list to be aware of the iterators that are currently scanning the list, so that they can be checked and possibly flagged as invalid. Each list object should have a list of (weak references to) all the active iterators, and check whether they refer to deleted list cells.

Since this would impact performance, a simpler approach is to invalidate all the iterators every time the list is modified. This can be done by storing a single number in both list and its iterators. When the iterator is created, the number is copied from the list. When the list is modified, the number is incremented. When the iterator is used, we quickly compare the two numbers, and throw if they differ.

This is reasonably cheap, even if it's suboptimal because it invalidates *all* iterators, when that is not really necessary.

There is some middle ground between these two approaches. A Java library could avoid undefined behavior, and allow the list to be in an invalid state when the invariant is broken, but allow iterators to remain valid in more cases (without trying to check this). This means that all list methods can potentially throw, or produce invalid results, including failing to terminate. Debugging can be quite hard in such conditions, but that's the price to pay when invariants are not checked early at runtime.

---
Tags: java, linked-lists, c++
---


# Question
Title: Log-space reduction - How to calculate overall space needed?
Assume A, B are two decision problems. Given a reduction from A to B that uses log^c1(n) space and an algorithm that solves B in log^c2(n) space, Can we determine some lower bound to the space needed by an algorithm which solves A using this reduction?

# Answer
> 1 votes
The answer depends on how large the output of the reduction $f$ is. Usually, in the context of log-space reductions, there are two main variants of composing reductions (or, in this case, composing a reduction with an algorithm solving the reduced problem directly). Goldreich ("Computational Complexity: A Conceptual Perspective") names these *naive* and *emulative* compositions, though I don't believe there is a widely agreed terminology for them. (Please correct me if I'm wrong.)

Let $x$ denote a problem instance of $A$.

**Naive composition.** If $|f(x)|$ is small, then we can compute the entirety of $f(x)$ and then apply the algorithm solving $B$, *reusing the space* used to compute $f$. This means the space complexity is on the order of $$\max(\log(|x|)^{c\_1}, \log(|f(x)|)^{c\_2}) + |f(x)|$$ plus some minor factors to organize things (e.g., keep track of whether we are performing the reduction or running the algorithm solving $B$).

**Emulative composition.** If $|f(x)|$ is large, then it makes sense not to generate the entirety of it in a single batch but, rather, to generate it bit-by-bit *on the fly* (i.e., as the algorithm solving $B$ needs it). Hence, whenever the algorithm solving $B$ needs bit number $i$ of $f(x)$, we run the reduction from scratch up to the point where bit number $i$ is produced and then pass this over to $B$. This means $f(x)$ is a virtual value which we provide to the algorithm for $B$ only on a bit-by-bit basis. Reusing space like this gives a space complexity on the order of $$\log(|x|)^{c\_1} + \log(|f(x)|)^{c\_2} + O(\log(|f(x)|))$$ plus some minor factors, as before (e.g., to keep track of what bit of $f(x)$ we have last provided). Note how this is a big improvement whenever $|f(x)|$ is large.

---
Tags: complexity-theory
---


title: Showing Cycle is NL-complete?

text:
# Question
Title: Showing Cycle is NL-complete?
Consider the following decision problem :

> Cycle: Given a directed graph G, does G contains a directed cycle?

It is very clear why Cycle belongs to NL. My question is - how to show Cycle is also NL-hard? it seems almost obvious to show logarithmic reduction from stCON. I thought about the following reduction:

> Given a tuple (G, s, t), return G with a new edge (t,s).

# Answer
> 6 votes
Let us reduce direct connectivity to CYCLE.

We are given a directed graph $G$ and two vertices $s,t$. Suppose that $G$ contains $n$ vertices.

* We create $n$ copies of the vertices of $G$.
* For each edge $x \to y$ in $G$, we add an edge from the $i$th copy of $x$ to the $(i+1)$th copy of $y$.
* We also add an edge from each copy $i$ of $t$ to the first copy of $s$ (i.e. the edges $(t\_i,s\_1), i=1,...,n$).

The new graph contains a cycle iff $t$ is reachable from $s$ in $G$.

We can construct the new graph from the original graph in logspace. Hence this is a logspace reduction, which shows that CYCLE is NL-hard.

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


# Question
Title: Shortest path between any origin to any destination through some way stations
How can one find the shortest path between any one of the origins to any one of the destinations through a number of way stations on the way using Dijkstra algorithm?

You can visit those way stations in any order. There will be multiple origins and multiple destinations, but a path from **any** origin to **any** destination will suffice as long as it's the shortest.

# Answer
Unless I'm misunderstanding the problem, you can't solve this with any simple modification to Dijkstra's because it's NP-complete.

Given an arbitrary graph, call every node a "waystation", then add start/finish nodes that are fully connected. Now running the solver for your problem will solve TSP on the original graph.
> 1 votes

# Answer
You're most of the way there in the comment with the handling of multiple sources and destinations. The simple way to do it is to insert two new vertices: the new source, with a 0-weight edge to each of the multi-sources, and the new destination, with a 0-weight edge from each of the multi-destinations.

---

For the waypoints, I will quote myself:

> This is one of a class of similar problems which can all be handled by deriving a graph $G' = (V', E')$ from the original graph $G = (V, E)$ and then using the standard algorithm on $G'$.
>
> Consider that at any point in your search in $G'$ you need the path information you would have at a corresponding point in the search in $G$ plus the knowledge of ...

here, the knowledge of which waypoints you've already visited. So $G'$ is potentially considerably larger than $G$.

Hint:

> If there are $k$ waypoints, $G'$ will contain $2^k$ copies of $G$, plus some edges connecting them.
> 1 votes

# Answer
You should build a distance matrix with:

* one row respresenting **any origin** and $k$ rows for the $k$ waypoints
* one column representing **any destination** and $k$ columns for the $k$ waypoints.

To fill this matrix, you can run $k+1$ Dijkstra algorithms for each row (time complexity $O(k(|V| + |N|\log |N|))$). For the row any origin, you just start with all origins at distance 0 in your heap.

Then you come to the NP-complete part, you indeed have to solve Travelling salesman problem on your distance matrix, starting on the **any origin** row and finishing on the **any destination** column. There are many ways to process it but for small $k$, you can simply use brute force (time complexity $O(!k)$).

So you obtain the shortest distance of the path answering to your problem and the ordered sequence of the waypoints visits. To obtain the path you can run again $k+1$ Dijkstra algorithms to build the path waypoint by waypoint. You can either have stored the path of any value of the distance matrix building it (space complexity $O(|N|k^2)$).
> 0 votes

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


# Question
Title: Why don't most websites I visit seem to use TLS with Ephemeral Diffie-Hellman?
When I click "view certificate," under Public Key Algorithm it usually says "RSA Encryption" or "Elliptic Curve Public Key." I assume this is the algorithm used to agree on a premaster secret (symmetric keys) between the client and server, or steps 4-6 in the image below. Why not use Diffie-Hellman then? Doesn't ephemeral Diffie-Hellman provide forward secrecy?

TLS handshake

# Answer
> 3 votes
The typical process to establish a secure channel uses asymmetric cryptography for two purposes: to allow the parties to authenticate each other, and to establish a shared symmetric key (in TLS, that's the premaster secret). At least one of the sides needs to authenticate the other, otherwise the two sides could each establish a secure channel with a man-in-the-middle. The shared symmetric key must be established in such a way that a man-in-the-middle cannot find it out. There are many different ways to do this, and I'll focus on ways that are actually used in TLS.

Most TLS connections do authentication and shared key establishment independently. This is the only way in TLS 1.3 (except with pre-shared symmetric keys), and it's the most common way in previous TLS versions.

To establish a shared key, each side creates an ephemeral Diffie-Hellman key (usually elliptic-curve DH, but it can also be finite-field DH) and sends the public key to the other side. Each sides receives the other side's public key, calculates the shared secret, and discards the ephemeral DH key. Thanks to the security properties of Diffie-Hellman, it's impossible to reconstruct the shared secret by observing wire traffic: an adversary would also need to have one of the private DH keys. Hence this method guarantees perfect forward secrecy.

For authentication, the client authenticates the server. (The server can optionally authenticate the client, but having one side do authentication is enough to prevent active man-in-the-middle attacks.) The way this works is that the server sends a digital signature (RSA, DSA or ECDSA) of the handshake, i.e. of the packets that both sides have either read or written so far, and the client verifies this signature. The client either already knows the server's public key (public key pinning or raw public keys, both rare settings), or far more commonly verifies a certificate chain from a root certificate authority trusted by the client to the server's public key.

The authentication process has no impact on the shared key establishment. That's why you don't find anything about Diffie-Hellman in the certificate information: it isn't involved in that part of the protocol. The algorithms mentioned in the server certificate are the one used to sign the handshake (subject public key algorithm) and the one used by the CA to sign the certificate (certificate signature algorithm).

By the way, “PKCS#1 v1.5 RSA Encryption” in X.509 certificates is called this for historical reasons, but it's actually a PKCS#1 v1.5 RSA signature.

TLS ≤1.2 also has cipher suites that use static Diffie-Hellman (also called non-ephemeral Diffie-Hellman). With these cipher suites, DH also provides the authentication part of the process. The server always uses the same DH key. The client verifies that the DH public key that it receives from the server is the one that it expects. If an adversary tries to impersonate the server and sends the legitimate server's public key, they won't be able to calculate the shared secret because they don't have the private key. If an adversary tries to impersonate the server and sends their own public key, the client will abort the connection because it sees a public key that is not the expected one. Static Diffie-Hellman does not provide forward secrecy, since obtaining the server's static private key is enough to decrypt all past recorded traffic.

Just like with signature-based cipher suites, the client doesn't actually need to know the server's public key in advance. The client can use a public key infrastructure to validate the server's public key: it checks that the server's public key comes in a certificate that has been signed by a (chain of) CA that the client trusts. An X.509 certificate can contain a signature of an (EC)DH public key. It's rarely done in practice, because it only has a marginal performance benefit, it's less secure (no forward secrecy), and there's a self-reinforcing loop that almost nobody does it (because there's no reason to) so almost nobody implements support for it (because there's no demand) so almost nobody does it (because there's no software support).

# Answer
> 0 votes
Diffie-Hellman does not directly provide signing and so cannot be used in Certificates. El Gamal (which is related to Diffie-Hellman) can, but it not used because this would require an extra verification step.

RSA could be used to sign the Diffie-Hellman key, and that key actually used to set up the session key, but it doesn't work that way. See Diffie-Hellman and its TLS/SSL usage on https://security.stackexchange.com for practical details.

---
Tags: cryptography, security, encryption
---


# Question
Title: Cannibals missionaries problem - solving usings graphs
I am trying to solve the cannibals - missionaries problem; we have the number of cannibals, the number of missionaries and the position of the boat. We are trying to transfer all of them to the other side, however there can't be more cannibals than missionaries on either side. The capacity of the boat is limited by 2.

There are multiple ways to solve this problem, I'm trying to do it using graphs. My questions is, how to I transform these "states" (M,K,B) into vertices in a graph? Each state represent the number of missionaries, the number of cannibals and the position of the boat.

I'm having troubles with visualization of these practical problems into graphs. Could you give me any help on how to add those vertices to the graph? Once I have the graph completed, it should be easy to solve using BFS.

# Answer
> 3 votes
You did most of the job. Each vertex is a state $(M, K, B)$ and edges represent the possibility to pass from a state to another with one ship transport. Let say $B$ can take the values $L$ or $R$ for left and right edges respectively. $K$ is the number of cannibals on left edge and $B$, the number of monks on left edge. Initially all monks and cannibals are on left edge with the boat: state is $(M\_0, K\_0, L)$. Note that for any state there are $M\_0-M$ monks and $K\_0-K$ cannibals on right edge.

You can notice that any ship transport would change $B$ value from $L$ to $R$ or vice-versa. Thus your state graph is a bipartite graph. It changes nothing to the problem, but it is interesting to notice it.

Concerning $K$ and $M$, to respect the "cannibal constraint", a valid node must have:

* $K \le M$ for left edge (or $M = 0$),
* $K\_0-K \le M\_0-M$ for right edge (or $M=M\_0$)

A valid left-\>right transport (edge) should be:

$(M\_i, K\_i, L)$ -\> $(M\_i-m, K\_i-k, R)$, such that $(m, k)$ in $\\{(1, 0), (2, 0), (1, 1), (0, 1), (0, 2)\\}$.

and a valid right-\>left transport (edge) should be:

$(M\_i, K\_i, R)$ -\> $(M\_i+m, K\_i+k, L)$, such that $(m, k)$ in $\\{(1, 0), (2, 0), (1, 1), (0, 1), (0, 2)\\}$.

Of course you must keep $0 \le M \le M\_0$ and $0 \le K \le K\_0$.

## BFS in the graph

So now, how to proceed ? You can create all possible vertices that is to say all $(M, K, B)$ with $M \le M\_0, K\le K\_0, B \in {L, R})$ that does respect the cannibals constraint. Then build all the possible edges (up to 5 from any vertex). Finally you can run the BFS in this graph to find an eventual solution. The graph would have up to $2 M\_0 K\_0$ vertices and $10 M\_0 K\_0$ edges.

A stronger solution is to build your graph as you explore it. You can express formally all states reachable from any state and check if the vertex of this state is already explored or not.

Also note that BFS is generally a good exploration method to find the shortest distance, but here you can expect left-\>right transports should move 2 persons and right-\>left transports should move only one person to decrease the left edge population.

This is indeed a good exercise for graph state representation and exploration, but after it you should try to answer these questions:

* What property between $M\_0$, $K\_0$ is necessary and sufficient to have a solution ? (exception of $M\_0 = 0$)
* What is the straight forward method to find such solution ?

Here is a small example for $M\_0 = 3, K\_0=2$. In blue the edges enconutered and in red the followed one.

---
Tags: graphs, graph-traversal
---


# Question
Title: Does this lock have a name (related to reader-writer lock)
The object can be locked two different ways, where if the lock is entered the same way a second time, the lock is recursive, but if it's entered the other way, it blocks. Like a reader-writer lock, but symmetric.

In case the text isn't clear, this code should be clear. Beware of bugs. I've only proved it correct, I haven't actually used it yet.

```
struct mylock {
    pthread_mutex_t entry;
    pthread_mutex_t manager;
    pthread_mutex_t core;
    int counter;
    int state;
}

void mylock_acquire(struct mylock *lock, int state)
{
    assert(state != 0);
    pthread_mutex_lock(&lock->entry);
    if (lock->state != state) {
        pthread_mutex_lock(&lock->core);
        lock->state = state;
    }
    pthread_mutex_lock(&lock->manager);
    ++lock->counter;
    pthread_mutex_unlock(&lock->manager);
    pthread_mutex_unlock(&lock->entry);
}

void mylock_release(struct mylock *lock)
{
    pthread_mutex_lock(&lock->manager);
    if (--lock->counter == 0) {
        lock->state = 0;
        pthread_mutex_unlock(&lock->core);
    }
    pthread_mutex_unlock(&lock->manager);
}

```

This is exactly the same as reader-writer, right down to there being exactly two classes of lock holder, except that the "writer" side is also multi-entry. So I took the core reader-writer code I learned two decades ago and converted it from P-V notation to mutexes and made both sides use the reader-type logic. ratchet freak did catch that it's no longer allowed to unlock a mutex from another thread anymore.

The actual code is different due to using atomic operations, but that complicates the question too much. The sample code is designed to illustrate the lock structure as simply as possible.

If I call up the Debian man page for pthread\_mutex\_unlock it actually says you can unlock from another thread ("If the mutex is of the "fast" kind, `pthread_mutex_unlock` always returns it to the unlocked state."), but ratchet freak has pointed out this isn't portable.

What is the name of this kind of lock? If it has a name, it would be helpful for documenting the thing.

# Answer
> 1 votes
The code is far from optimal, if you instead use a condition variable it is much clearer:

```
struct mylock {
    pthread_cond_t entry;
    pthread_mutex_t manager;
    int counter;
    int state;
}

void mylock_acquire(struct mylock *lock, int state)
{
    assert(state != 0);
    pthread_mutex_lock(&lock->manager);
    while (lock->state != 0 && lock->state != state) {
        pthread_cond_wait(&lock->entry, &lock->manager);
    }
    lock->state = state;
    ++lock->counter;
    pthread_mutex_unlock(&lock->manager);
}

void mylock_release(struct mylock *lock)
{
    pthread_mutex_lock(&lock->manager);
    if (--lock->counter == 0) {
        lock->state = 0;
        pthread_cond_broadcast(&lock->entry);//may have multiple waiters on same state
    }
    pthread_mutex_unlock(&lock->manager);
}

```

It is also fairly useless, I cannot think of any scenario where such a pattern of exclusion would be useful. Which would be the reason why it doesn't have a name.

---
Tags: threads
---


# Question
Title: Difference between greedy and work conserving scheduler for DAG
For both schedulers I have found the definition, that no processor stays idle, if there is more work it can do.

However, I found two different upper bounds on the computation time of $T$. For the following equations $T\_{\infty}$ is the computation time on infinite processors and $T\_1$ is the duration on one processor.

\[1\] Greedy Schduler (Theorem 1): $T = T\_1/m + T\_\infty$

\[2\] Work-Conserving Scheduler (Theorem 1): $T = (T\_1-T\_\infty)/m + T\_\infty$

Both consider the scheduling of directed acyclic graphs where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v\_i$ has to execute before task $v\_j$ if there exists an edge $(v\_i,v\_j)$ between those two tasks. I have x threads that can execute those tasks. However, I am not 100% sure if \[2\] considers preemptive scheduling for their upper bound, but it does seem to be the case for their theorem 1.

In this presentation (page 41) I have found both equations for an upper bounds of the greedy scheduler.

Is there by definition any difference between the two schedulers?

# Answer
> 2 votes
If I understand well, it is the same scheduling method with different names. I think Work-conserving Scheduler is the more "official" one. "greedy" can indeed qualify many aspects of the problem and one should always precise which. greedy algorithm is a paradigm not a specific method for a specific problem.

Anyway about the upper-bound, the presentation of your last link says that it is:

$T \< (T\_1-T\_\infty) / m + T\_\infty$

but that a simpler one is generally used:

$T \< T\_1 / m + T\_\infty$

Of course the latter is greater than the former but both are true. Also note that they are both equivalent to $T\_\infty$ when $m$ tends to $+\infty$.

---
Tags: graphs, parallel-computing, greedy-algorithms, scheduling
---