# Question
Title: Hardness of the k-center problem with relaxed triangle inequality
Consider the $k$-center problem where we are given an undirected, complete graph $G=(V, E)$, with a distance $d(u, v) \geq 0$ for each pair $u, v \in V$. Furthermore, we assume that the triangle inequality holds: for each triple $u, v, w \in V$ it is the case that $d(u, w) \leq d(u, v)+d(v+w)$. The goal is to find $k$ clusters, grouping together the vertices that are most similar into clusters together. The goal is to choose a set $S \subseteq V$ of $k$ cluster centers such that we minimize the maximum distance of a vertex to its cluster center.

It is not difficult to show that there is no $\rho$-approximation algorithm for the $k$-center problem for $\rho \< 2$ unless $\mathbf{P}=\mathbf{NP}$: Consider the dominating set problem, which is NP-complete. In the dominating set problem, we are given a graph $G = (V, E)$ and an integer $k$, and we must decide if there exists a set $S ⊆ V$ of size $k$ such that each vertex is either in $S$, or adjacent to a vertex in $S$. Given the instance $G=(V, E)$ of the dominating set problem, we can then construct an instance $G'=(V, E')$ of the $k$-center problem by setting the distance between adjacent vertices in $G$ to 1 in $G'$, and the distances between nonadjacent vertices in $G$ to 2 in $G'$. Then, there is a dominating set of size $k$ if and only if the optimal distance ($OPT$) for $k$-cluster instance $G'$ is $1$. Thus, if we assume we have an approximation algorithm $A$ for the $k$-center problem with approximation factor $\rho \< 2$, we can run it on $G'$. Then, if $OPT=1$, $A$ will return a solution with distance $\<2$, i.e. 1. Else, if $OPT =2$, $A$ will return a solution with distance at least $2$. Thus, we can solve the dominating set decision problem, which implies that $\mathbf{P}=\mathbf{NP}$.

My question is then concerned with the $c$-relaxed $k$-center problem, where we do not have a metric but only the following approximate triangle inequality: For each triple $u, v, w \in V$, it is the case that $d(u, w)/c \leq d(u, v)+d(v, w)$. Is it possible to show that unless $\mathbf{P}=\mathbf{NP}$, there is no solution to the $c$-relaxed $k$-center problem with approximation factor $\rho \< c+1$

# Answer
You can show hardness of approximation of any $\rho \< 2c$.

Simply take the distance between non-adjacent vertices to be $2c$ and distance between the adjacent vertices to be $1$. Note that the graph should satisfy relaxed triangle-inequality, and it indeed does, given that $c \geq 1$.
> 1 votes

---
Tags: algorithms, complexity-theory, np, approximation, clustering
---


# Question
Title: Creative solving of searching redundant connection in graph
I am trying to solve problem in leetcode: https://leetcode.com/problems/redundant-connection/description/ \*finding redundant connection in undirected graph

And now I am writing a solution, inpired by Kruskal's algorithm: https://en.wikipedia.org/wiki/Disjoint-set\_data\_structure#/media/File:UnionFindKruskalDemo.gif

In short: I just add vertices in sets if I find a pair, when both vertices exist in set then it is an additional edge...

```
var findRedundantConnection = function(edges) {
  let additionals = [];
  let sets = [];
  for (let i = 0; i < edges.length; i++) {
    //find connections of each vertices in edge
    let check_0_indexes = [];
    let check_1_indexes = [];
    for (let j = 0; j < sets.length; j++) {
      if (sets[j]&&sets[j].includes(edges[i][0])) { //if vertices exist in sets
        check_0_indexes.push(j);
      } else if (sets[j]&&sets[j].includes(edges[i][1])) {
        check_1_indexes.push(j);
      }
    }
    //add to sets (but if not an additional, if additional then add to additionals)
    check_0_indexes.map(el=>{
        if(sets[el].includes(edges[i][1])){ //check first vertice: if pair exist in set
            additionals.push(edges[i]);
        } else {
            sets[el].push(edges[i][1]);
      }
    });
    check_1_indexes.map(el=>{
        if(sets[el].includes(edges[i][0])){
            additionals.push(edges[i]);    //check second vertice: if pair exist in set
        } else {
            sets[el].push(edges[i][0]);
        }
    });
    if(!check_0_indexes.length&&!check_1_indexes.length){
        //if both vertices not in sets
        sets.push([]); //create new set and add vertices
        sets[sets.length-1].push(edges[i][0]);
        sets[sets.length-1].push(edges[i][1]);
    }
  }
  return additionals.pop();
};

```

\*JavaScript

But in this case: `edges = [[3,7],[1,4],[2,8],[1,6],[7,9],[6,10],[1,7],[2,3],[8,9],[5,9]]`
I do not know how to catch loop ( (8,9) and (7,9) ) Any ideas about it?

# Answer
This step is incomplete:

> sets\[el\].push(edges\[i\]\[1\]);

For edge $(2,3)$, only $3$ is getting added to the existing set $\\{2,8\\}$. And, only $2$ is getting added to existing set $\\{3,7,9, \dotsc\\}$.

You should also add all the elements of the set $\\{2,8\\}$ to $\\{3,7,9, \dotsc\\}$ and vice-versa. Note that you have to merge the two sets $\\{2,8\\}$ to $\\{3,7,9,\dotsc\\}$ into one.
> 2 votes

---
Tags: algorithms, graphs, data-structures
---


# Question
Title: Justification for the properties of algorithmic recurrences in 'Introduction to Algorithms' (CLRS, 4e)
The fourth edition of 'Introduction to Algorithms' defines algorithmic recurrences on page 77 as follows:

> \**Algorithmic recurrences
>
> \[...\] A recurrence is ***algorithmic***, if for every sufficiently large ***threshold*** constant $n\_0 \> 0$, the following two properties hold:
>
> 1. For all $n \< n\_0$, we have $T(n) = \Theta(1)$
> 2. For all $n \geq n\_0$, every path of recursion terminates in a defined base case within a finite number of recursive invocations.

The following justification is then provided for the first property:

> \[...\] The first property says that there exists constants $c\_1$, $c\_2$ such that $0 \< c\_1 \leq T(n) \leq c\_2$ for $n \< n\_0$. For every legal input, the algorithm must output the solution to the problem it's solving in finite time (see Section 1.1). Thus, we can let $c\_1$ by the minimum amount of time to call and return from a procedure, which must be positive since, because machine instructions need to be executed to invoke a procedure. The running time of an algorithm may not be defined for some values of $n$ if there are no legal inputs of that size, but it must be defined for at least one, or else the "algorithm" doesn't solve any problem. Thus, we can let $c\_2$ be the algorithm's maximum running time on any input of size $n \< n\_0$, where $n\_0$ is sufficiently large that the algorithm solves at least one problem of size less than $n\_0$.

I'm not sure I follow the reasoning for $c\_1$ and $c\_2$ being the minimum and maximum base case running times, respectively.

For $c\_1$, the authors say, *"For every legal input, the algorithm must output the solution to the problem it's solving in finite time (see Section 1.1). Thus, we can let $c\_1$ by the minimum amount of time to call and return from a procedure."*

* I don't see the connection between the alogrithm completing in finite time and $c\_1$ being the minimum running time. **Doesn't this reasoning makes more sense for $c\_2$ being the maximum running time?** Since if an algorithm by definition finishes in a finite amount of time, then there must be some ceiling to the running time.

For $c\_2$, the authors say, *"The running time of an algorithm may not be defined for some values of $n$ if there are no legal inputs of that size, but it must be defined for at least one, or else the "algorithm" doesn't solve any problem. Thus, we can let $c\_2$ be the algorithm's maximum running time on any input of size $n \< n\_0$, where $n\_0$ is sufficiently large that the algorithm solves at least one problem of size less than $n\_0$."*

* I don't understand why there being at least one input of size $\< n\_0$ implies that $c\_2$ is the maximum running time. This argument seems to make more sense for $c\_1$ being the minimum running time, since if there is at least one problem of size $\< n\_0$, then it must take some non-zero amount of between $c\_1$ and $c\_2$.

I would be grateful for any help on this, as I cannot find anything on algorithmic recurrences outside of the book.

# Answer
The 1st property is referring to the time needed by the recursive algorithm to solve a problem instance with size $n\<n\_0$. Under this case the algorithm can directly solve the problem, i.e. no recursion needed. They are then trying to show that the time needed for this must be constant, because the size of the instance is bounded from above by a constant $n\_0$. And that's where the two constants comes into play.

The reason for having two constants $c\_1$ and $c\_2$ is to prove that the time needed is $\Theta(1)$. Please review the definition of $\Theta$ for this.

The algorithm must terminate after some time otherwise it will not solve the problem. Now as mentioned above we are only considering constant size instances. Since the running-time is based on the size of the input, the running-time must be constant (*no matter how long it takes, the algorithm is only processing constant number of things*) . Among all the possible instances with constant size, one of them will need the least amount of time. This gives you $c\_1$.

Now for the other case, it's almost the same idea except you just select the instance that will give the largest running-time and you'll get $c\_2$. As noted in their explanation, there must be at least one instance that gives the max time, which again must take constant time. This instance exist since the algorithm needs to be able to solve the problem.

As a final note, just in case only one instace fits the size restriction, then it's still acceptable that $c\_1 =c\_2$.
> 2 votes

# Answer
If there is at least one $n\<n\_0$ such that there is a legal input, then obviously the running time can be bracketed as

$$c\_{\min}\le T(n)\le c\_{\max}$$ where the minimum and maximum are taken over all legal inputs (for all $n\<n\_0$).

Obviously, the lower bound is itself bounded by the time for an empty function, let $c\_1$, and

$$c\_1\le c\_{min}.$$ The author also denotes $c\_{\max}$ as $c\_2$. Note that $c\_1$ can be known *a priori*, while $c\_2$ depends on the studied algorithm.
> 2 votes

---
Tags: algorithms, algorithm-analysis, recurrence-relation, recursion, divide-and-conquer
---


# Question
Title: Reformulating the Given Conditions in Decidability Problems
I came across the following question:

> Given two context-free languages $L\_1$ and $L\_2$ is it decidable whether $L\_1 - L\_2 = \emptyset$ ?

The problem $ALL\_{\text{CFG}}$ that states:

Given a CFG $G$ then $L(G) = Σ^\*$ is known to be undecidable.

So I thought to fix $L\_2$ to be $Σ^\*$ and allow $L\_1$ to be any context-free language to prove that the problem stated is undecidable.

What concerns me the most is that the $ALL\_{\text{CFG}}$ refers to a context-free **grammar** and not a context-free **language**.

One of the definitions of a context-language is the following:

$L$ is a context-free language $\leftrightarrow$ There exists a context-free grammar $G$ s.t $L(G) = L$ which translates to 2 things:

1. $L$ is a context-free language $\rightarrow$ There exists a context-free grammar $G$ s.t $L(G) = L$
2. Given a context-free grammar $G$ s.t $L(G) = L$ $\rightarrow$ $L$ is a context-free language

The only way I see to address my concern regarding $ALL\_{\text{CFG}}$ is to add bullet $(1)$ to the proof and state that if the problem in question is decidable then $L(G\_1) = Σ^\*$ is decidable (which is not) where $G\_1$ is the context-free grammar that generates $L\_1$. Would this approach work?

I am seeing this kind of question for other kinds of languages as well.

Say that the problem in question was the following:

Given two **recursive** languages $L\_1$ and $L\_2$ is the $X$ problem decidable?

Will the same approach work if I manage to take the problem from the domain of recursive languages to the domain of Turing Machines with $M\_1$ and $M\_2$ where $L(M\_1) = L\_1$ and $L(M\_2) = L\_2$?

# Answer
> 1 votes
Your approach is correct.

---

> Given two context-free languages $L\_1$ and $L\_2$ is it decidable whether $L\_1 - L\_2 = \emptyset$ ?

It is understood the $L\_1$ is given as $L(G\_1)$ where $G\_1$ is a given context-free grammar. $L\_2$ is given as $L(G\_2)$ where $G\_2$ is a context-free grammar.

This convention is used for similar propositions/exercises unless specified otherwise.

For example, if we are asked "given two **recursive** languages $L\_1$ and $L\_2$ is the $X$ problem decidable?", then we can assume $L\_1$ is given by $L(M\_1)$ where $M\_1$ is a decider and $L\_2$ is given by $L(M\_2)$ where $M\_2$ is a decider.

Technically, "a context-free language $L\_1$" can be for example given as $L(S)$ where $S$ is a context-sensitive grammar such that $L(S)$ is context-free or given as $L(T)$ where $T$ is a Turing machine such that $L(T)$ is context-free. However, these kinds of interpretations are not used anywhere during introductory study.

---

Here is an exercise.

> Prove the following *promise problem* is undecidable.
> Given a Turing machine $T$ that accepts a decidable language and a string $w$, determine whether $T$ accepts $w$.

Here we should understand that it is possible the given $T$ is not a decider., although $T$ accepts a decidable language.

This undecidability says there is no decider that given an arbitrary string $w$ and an arbitrary semi-decider $S$ that accepts a decidable language, can output whether $S$ accepts $w$. In other words, the halting problem is still undecidable even the Turing machine in the input is guaranteed (by an oracle) to accepts a decidable language each time (however, it is possible that the given Turing machine itself is not a decider).

---
Tags: context-free, undecidability, correctness-proof
---


# Question
Title: Let the vertices of the graph G be the numbers 1, 2, ..., 100, a. Determine χ(G), the chromatic number of the graph G
Let the vertices of the graph G be the numbers 1, 2, ..., 100, and two (different) vertices be adjacent if and only if at least one of **2, 3, or 5 is a common divisor** of the respective numbers. Determine *χ(G)*, the chromatic number of the graph G.

I tried to solve and got that all even numbers i.e 2,4,6,...,100 form a clique of size 50. And that all prime numbers are isolated so they do not matter in coloring. But I cannot show chromatic number is 50. Any suggestions?

# Answer
> 5 votes
Hint 1:

> Show that the graph is $50$-partite.

Hint 2:

> Each partite set contains exactly two elements.

Full Solution:

> For colors $c\_1,\dotsc,c\_{50}$, assign color $c\_i$ to numbers $2i-1$ and $2i$. Note that no two consecutive numbers can have a common divisor other than $1$.

---
Tags: graphs, discrete-mathematics
---


# Question
Title: What does it take to support a programming language on an OS?
From my understanding, something like Linux is very geared towards C programs, with things like `libc`. What I'm wondering is, even in Java, you have arguments to your "main" program. The same thing occurs in C. From my understanding, this is just some data the kernel puts on an anonymous page for the stack of the process. How does this actually really work across languages, and how can the kernel/operating system support it? More detail is very appreciated, I'm very interested to hear about this.

# Answer
> 0 votes
I'm glossing over a few (lots of) details, but the following is essentially what happens when you run a program:

1. The operating system breaks off a chunk of memory for the program to run in. The binary code is copied into part of that memory (possibly a segment marked as read-only by non-OS processes). Another part is reserved for global variables, and another for local variables.
2. There exists a **program counter** that points to the part of that memory containing the instruction that will run next. This is a dedicated register that is read by the CPU directly when it executes the next cycle.
3. There exists a **stack pointer** that points to the beginning of the part of memory reserved for local variables. When we add a new local variable (including function arguments), we put it at the current stack pointer, and then increment the stack pointer, thus creating a stack. (If we add too many locals, e.g. via a recursive call that never terminates, we run off the end of the stack: that's what a stack overflow is.)
4. When we call a function, we:
    1. push the current value of the program counter onto the stack. This lets us know where to return to.
    2. push each of the function arguments onto the stack
    3. increment the stack pointer to reserve space for the function's local variables. (The part of the stack corresponding to a particular function call is called its **stack frame**).
    4. Set the program counter to the location of the function we want to call.
    5. The return statement compiles to code that undoes all that and sets the program counter to the value we stored on the stack.
5. So all the operating system has to do to pass the command line arguments is:
    1. The shell (command prompt) is just a regular program. You type a command; it reads it, tokenizes the arguments, and puts them in an array.
    2. The shell calls a couple of **system calls** (functions that talk to the operating system) in the `fork` and `exec` family (for Unix. Other OSes have different names for them). Those tell the operating system to start a new process with the supplied arguments. (The path to the program to be run is put at the front of the argument array)
    3. The operating system reserves space for the program (as described in (1)), puts that array on the stack just like any other function call would do, and sets the program counter to the location of `main`. (The return address will be the location of some cleanup code that frees all the memory and such). `main` now has access to the array just like any other function would have access to its own arguments.

There will also be some extra steps involved in linking shared libraries, setting up multiprocessing, and doing memory protection. I didn't explain how these work because I don't know they're out of scope.

---
Tags: programming-languages, operating-systems, compilers
---


title: Halting problem in C++

text:
# Question
Title: Halting problem in C++
The halting problem relies on the fluidity of Turing machines. That is, a string can represent a machine.

Can you do the same for C++ on a modern computer?

Let's see my first attempt. Let `bool h(string x, string y)` be the purported function that decides haltingness and always halts. You can easily turn it into a full program.

Now define a self-contradictory function `f`:

```
bool f(string x) {
    if (h(x, x))
        for (;;);
    return true;
}

int main() {
    cout << h(f, f) << endl;
}

```

The problem is that I can't feed the code of `f` into `h` in `main()`.

My second attempt: Prepare 4 files: `h.cpp`, `h.exe`, `f.cpp`, `f.exe`. And suppose the call formats are

```
h.exe filename1 filename2
f.exe filename

```

My problem is that in `f.cpp` I need to call `h.exe`, which in turn has to be part of `f.cpp`.

What's your working scheme?

# Answer
> 5 votes
If you want to prove that the halting problem for C++ programs can't be decided by a C++ program, just copy the proof of the Halting problem but replace every use of a universal Turing machine with a C++ interpreter/compiler that's written in C++.

# Answer
> 2 votes
The halting problem states that there is no $h$ function that works on every input. You are missing that you need to supply a concrete implementation of a function $h$ (which is as hard as writing a compiler), and prove that it works on any input function. The latter is an impossible task, as you should feed $h$ with all valid programs.

The proof of the halting problem is not constructive, it just shows the impossibility.

# Answer
> -1 votes
> The problem is that I can't feed the code of f into h in main().

This problem is solved by invoking h with the machine address of f.

**Translated to C for the x86utm operating system**

```
00 typedef int (*ptr)();
01 int h(ptr x, ptr y)
02
03 int f(ptr x) {
04   if (h(x, x))
05     for (;;);
06   return 1;
07 }
08
09 int main()
10 {
11  Output("Input_Halts = ", h(f, f));
12 }

```

When h is a simulating termination analyzer based on an x86 emulator within the x86utm operating system this is the execution trace of the above code:

**Line 11:** main() calls h(f,f) that simulates f(f)

**keeps repeating:**
**Line 04:** simulated f(f) calls simulated h(f,f) that simulates f(f) ...

**Simulation invariant:**
f correctly simulated by h never reaches its own Line 06.

This enables h to correctly report that (its input) f correctly simulated by h never halts. The above is fully operational code within the x86utm operating system

---
Tags: halting-problem, c++
---


# Question
Title: Prove simple theorems in Haskell in automated way
I would like to prove in Haskell, whether in vanilla Haskell or using some libraries / tools, some simple theorems such as:

```
and [n*(n+1)/2 == sum [0..n] | n <- [0..]]

```

Is there a simple enough (ie. fully automated) way to prove such theorems involving integers in Haskell? I am not really interested in the proof itself, or a counterexample, but merely a yes/no answer.

There's this publication which doesn't seem practically usable; other than that most of everything else seems to be rather complex, ie. involving a completely separate language and not concerning Haskell.

# Answer
> 3 votes
SMT (satisfiablity-modulo-theories) solvers can provide an (almost-) push-button solution for at least a subset of such problems, especially for those that use machine-arithmetic, IEEE-floats, etc., where efficient decision procedures do exist. There's also good support for arrays and data-types, along with reasoning about arithmetic with mixed types.

There are several Haskell libraries built on-top-of SMT solvers to access these features. So, the answer to your question is a qualified "yes." If you squint the right way, then you can code and prove properties of many Haskell functions using SMT-solvers.

I say "squint" because you'll have to modify your functions to work with symbolic values. This translation depends on the exact problem you're working on and what library you use. I'm most familiar with SBV, so my answer below uses that system.

For non-recursive functions that work on numbers (i.e., machine integers, reals, floats, unbounded integers etc.), the translation is relatively easy. Things get hairy when you have algebraic types, but support is there for most common data structures. You can see many examples at SBV's hackage documentation.

Where things get tricky is recursion: Both recursive functions and recursive data-types are problematic for SMT solving. While the underlying solvers do support such definitions, proof-support is (at least for the time being) rather weak. The main reason is that any interesting property of a recursive definition will need to use induction, and SMT solvers do not perform induction out-of-the-box.

However, for a certain subset of problems, you can make quite a bit of progress. SBV supports several programming idioms and proof tricks that let you do inductive proofs over naturals. Since you mentioned `sum` in your question, here's an example based on that.1

First some preliminaries:

```
module Example where

import Data.SBV
import Data.SBV.Tools.NaturalInduction

```

This simply brings SBV in scope, and the induction tactic. Let's recursively define summing numbers up to an arbitrary natural `n`:

```
sumToN :: SInteger -> SInteger
sumToN = smtFunction "sumToN" $ \n -> ite (n .== 0) 0 (n + sumToN (n-1))

```

Of course, in regular Haskell you'd write this simply as `sum [1..n]`. Alas, that definition won't do when we want to prove it for all `n`. This is the "symbolic transformation" you need to do. Since Haskell's `if-then-else` takes a boolean as an argument, we use `ite` instead, which does the same thing but over symbolic test values.2 Also note how we tell the solver to *not* expand this definition by explicitly marking it as an `smtFunction`. Unless you mark functions this way, SBV will unroll them at each call site, and that won't work here since `n` is symbolic and thus the recursive call will never terminate.

Now we can write a little helper:

```
check :: (SInteger -> SInteger) -> IO ThmResult
check f = inductNat $ \n -> (sumToN_spec n, f n)
  where sumToN_spec :: SInteger -> SInteger
        sumToN_spec n = (n * (n+1)) `sEDiv` 2

```

This simply calls SBV's `inductNat` function, which itself takes a split-predicate: That is, a function that takes a natural number and evaluates the "left-hand-side" (which you can think of as the specification), and the "right-hand-side" (which you can think of as the implementation). The spec is defined right there as the usual formula. (The function `sEDiv` is symbolic euclidian division, which is equivalent to regular division when the divisor is positive.3)

We can now check if our definition is good:

```
*Example> check sumToN
Q.E.D.

```

And voila, we have our proof.

It's instructive to see what happens if we make a mistake. Let's write a buggy version of our function:

```
sumToN_bad :: SInteger -> SInteger
sumToN_bad n = ite (n .== 123) 0 (sumToN n)

```

We introduced a point-failure: A corner case bug if you will: The function will work for all values except `123`. Note that the above looks exactly what you'd write in Haskell, aside for the use of `ite`: Since it's not recursive we can let SBV unroll it in all call-sites. (Notice we didn't call `smtFunction`. We could've; but we didn't need to.) We now have:

```
*Example> check sumToN_bad
Falsifiable. Counter-example:
  P(0)   =       (0,0) :: (Integer, Integer)
  P(k)   = (7503,7503) :: (Integer, Integer)
  P(k+1) =    (7626,0) :: (Integer, Integer)
  k      =         122 :: Integer

```

We get a full-account of the induction proof. The base case (i.e., `0`) passes. The proof is also true all the way up to `122`, but spec and the implementation diverge at `k+1 = 123`. Note how difficult it would be for a test based approach to catch this bug: It'd have to use `123` as its test value. But an SMT solver can easily identify such corner cases.

Of course, this doesn't mean the SMT solver will be able to complete all such proofs. SMT solving is not a panacea, it's merely another tool to use in verification. It's entirely possible that it will loop-forever, since decision procedures for recursive definitions is necessarily incomplete. My experience, however, is that they work well in most practical cases, and hopefully SMT-solvers will continue to improve to make such problems even more amenable to these sorts of techniques. At the cost of more user-involvement, a better approach is to use a proper theorem prover (such as Isabelle, Coq, ACL2 etc.), and use SMT-solvers as engines in proof discovery, allowing you to discharge many proof-obligations (especially those involving arithmetic) automatically.

---

1 SBV will call to Microsoft's z3 SMT solver by default. See https://github.com/Z3Prover/z3. SBV can also use other SMT solvers as well (such as cvc5, yices, etc.), though support for z3 is the most robust. Make sure you installed z3 and its executable is in your path before you use SBV.

2 One can use rebindable syntax in GHC to allow `if` to be used, but I find that approach more confusing than helpful.

3 We use euclidian division instead of the regular Haskell division, since SMT solvers deal with it much better. SBV supports both variants.

# Answer
> 3 votes
Look at Agda \[1\]\[2\]

I think that it's exactly what you are looking for.

I recommend using its emacs mode for autocompletion and hole/interactive programming. \[2\]/quick-guide.html

A very good introduction is plfa \[3\], also \[2\]/tutorial-list.html

\[1\] https://en.wikipedia.org/wiki/Agda\_(programming\_language)

\[2\] https://agda.readthedocs.io/en/v2.6.0.1/getting-started/what-is-agda.html

\[3\] https://plfa.github.io/

# Answer
> 1 votes
On top of everyone else, don't forget that the Curry-Howard correspondence also gives you a way to prove theorems.

Say you want to prove that $B \wedge (A \vee (B \rightarrow A)) \rightarrow A$. Here's the proof:

```
-- The statement of the theorem...
proof :: (b, Either a (b -> a)) -> a
-- ...and the proof.
proof (b, Left a) = a
proof (b, Right f) = f b

```

---
Tags: proof-assistants, automated-theorem-proving, haskell
---


# Question
Title: Select at least one from each category to minimize union, NP-hard problem?
I have this problem that is very similar to the minimum k-union problem:

Given a collection $C$ of subsets of a finite set $S$ and each set $c\in C$ has a label that is its category. The problem is to select at least one $c$ from each category such that the size of their union is minimized.

Is this problem NP-hard?

# Answer
Nice question! Let us call this problem the **minimum label-covering problem**.

We will reduce the hitting set problem, a well-known $\mathsf{NP}$-hard problem to the minimum label-covering problem, thus proving it is also $\mathsf{NP}$-hard. Our strategy is simply translating "intersecting the $i$-th set" in the hitting set problem to "labelled with the $i$-th label" in the minimum label-covering problem.

Given $V=\\{V\_1, V\_2,\cdots, V\_m\\}$, which is a collection of subsets of a finite set $U$ and a number $k$, the hitting set problem is to find the smallest subset of $U$ which intersects (hits) every set in $V$. Let $S$ be the disjoint union of $U$ and $\\{l\_1,l\_2,\cdots, l\_m\\}$, a set of $m$ labels. Let $C$ be the set of all subsets of $S$ of the form $\\{u, l\_i\\}$ where $u\in V\_i$. Let the label for $\\{u, l\_i\\}$ be $l\_i$. Suppose we have solved the minimum label-covering problem for $C$, $S$ and the specified labelling, that is, we have selected at least one set from each category such that their union is minimized. Let $U'$ be the set of all elements of $U$ that are members of the selected sets. It is easy to verify that $U'$ is the smallest subset of $U$ that hits every set in $V$. Our proof is done.

### An exercise

Given a collection $C$ of subsets of a finite set $S$ and each set $c\in C$ has a label that is its category, the **maximum label-covering problem** is to select at most one $c$ from each category such that the size of their union is maximized. Show the maximum label-covering problem is $\mathsf{NP}$-hard.
> 2 votes

# Answer
I'm not sure I fully understood the above reduction. here is an example: $U$ = {$v\_1, v\_2, v\_3, v\_4$} $V$ = {{$v\_1$}, {$v\_2$}, {$v\_3$}, {$v\_4$}} $L$ = {$l\_1, l\_2$} suppose the first two subsets has the label $l\_1$ and the last two the label $l\_2$. A solution for min label cover would be for instance {$v\_1, v\_3$} - we have covered both labels. but it does not hit every set in V.
> 0 votes

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


title: Telescope Scheduling Predecessors

text:
# Question
Title: Telescope Scheduling Predecessors
In Algorithm Design and Applications by Michael T. Goodrich and Roberto Tamassia Chapter 12.3 there is a presentation of a problem called the Telescope Scheduling problem.

Given n requests each with benefit, start time and end time, find the best combination of non conflicting requests that maximises the total benefit.

I understand the dynamic programming solution but for it the predecessor of each request is needed. That is *"the largest index, j \< i, such that requests i and j don’t conflict. If there is no such index, then define the predecessor of i to be 0."* (I suppose i and j refer to the index of the request when sorted by end time)

It states that one can sort the requests by start time in one list L' and by end time in another list L and then *"the predecessor of request i is literally the index of the predecessor in L of the value, si, in L'."*

I cant see what that means.

# Answer
Did you missed the following step?

> Given a listing of $L$ ordered by finish times and another listing, $L'$, ordered by start times, then **a merging of these two lists**, as in the merge-sort algorithm (Section 8.1), gives us what we want.

Let us use the example in *Figure 12.6: The telescope scheduling problem*.

Listing $L$ is represented as $f\_1,f\_2,f\_3,f\_4,f\_5,f\_6,f\_7$.
Listing $L'$ is represented as $s\_1,s\_2,s\_4,s\_3,s\_7,s\_5,s\_6$.
A merging of these two lists gives us the following diagram.

$$\begin{aligned} L&:\quad f\_0, \quad\phantom{\overbrace{s\_1, s\_2, s\_4}^{\text inserted}} f\_1, \phantom{\overbrace{s\_3,}^{\text inserted}} f\_2, \phantom{\overbrace{s\_7,}^{\text inserted}} f\_3, \phantom{\overbrace{s\_5,}^{\text inserted}} f\_4, f\_5, \phantom{\overbrace{s\_6,}^{\text inserted}} f\_6,f\_7\\ L'&:\quad \phantom{f\_0,}\quad\overbrace{s\_1, s\_2, s\_4}^{\text inserted} \phantom{f\_1,} \overbrace{s\_3,}^{\text inserted} \phantom{f\_2,} \overbrace{s\_7,}^{\text inserted} \phantom{f\_3,} \overbrace{s\_5,}^{\text inserted} \phantom{f\_4, f\_5,} \overbrace{s\_6,}^{\text inserted} \phantom{f\_6,f\_7}\\ \end{aligned}$$ where $f\_0$ is a virtual request with index $0$ that happens before all real requests.
The meaning of "the predecessor of request $i$ is literally the index of $\ $ the predecessor in $L$ $\ $of $\ $the value, $s\_i$, in $L'$" should be clear now. For example,

* since the predecessor in $L$ of $s\_1$ is $f\_{\boldsymbol{0}}$, the predecessor of request $1$ is $0$.
* since the predecessor in $L$ of $s\_2$ is $f\_{\boldsymbol{0}}$, the predecessor of request $2$ is $0$.
* since the predecessor in $L$ of $s\_7$ is $f\_{\boldsymbol{2}}$, the predecessor of request $7$ is $2$.
> 4 votes

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


# Question
Title: Substitution method for the upper bound of a recurrence without an explicit base case
**Pages 90-91** of *'Introduction to Algorithms'* (4th ed.) show how the substitution method can be used for determining the upper bound on the recurrence:

$$T(n) = 2T(\lfloor n/2 \rfloor) + \Theta(n) \tag{4.11}$$

We guess that $T(n) = O(n \lg n)$ and try to prove $T(n) \leq cn \lg n$ by induction.

I can follow the proof for the inductive case, but need some help understanding the proof for the base cases of the induction (I've highlighted the part I'm unsure about in bold):

> We’ve shown that the inductive hypothesis holds for the inductive case, but we also need to prove that the inductive hypothesis holds for the base cases of the induction, that is, that $T(n) \leq cn \lg n$ when $n0 ≤ n \< 2n\_0$. As long as $n0 \> 1$ (a new constraint on $n\_0$), we have $\lg n \> 0$, which implies that $n \lg n \> 0$. So let’s pick $n\_0 = 2$. **Since the base case of recurrence (4.11) is not stated explicitly, by our convention, $T(n)$ is algorithmic, which means that $T(2)$ and $T(3)$ are constant (as they should be if they describe the worst-case running time of any real program on inputs of size 2 or 3).** Picking $c = \max\[T(2), T(3)\]$ yields $T(2) ≤ c \< (2 \lg 2)c$ and $T(3) ≤ c \< (3 \lg 3)c$, establishing the inductive hypothesis for the base cases. Thus, we have $T(n) ≤ cn \lg n$ for all $n ≥ 2$, which implies that the solution to recurrence (4.11) is $T(n) = O(n \lg n)$.

**Questions:**

1. I don't understand the part of the proof in bold: *"Since the base case of recurrence (4.11) is not stated explicitly, by our convention, $T(n)$ is algorithmic, which means that $T(2)$ and $T(3)$ are constant".* The convention that the authors are referring to is stated on **page 78**:

> We adopt the following convention:
>
> *Whenever a recurrence is stated without an explicit base case, we assume that the recurrence is algorithmic.*
>
> That means you’re free to pick any sufficiently large threshold constant $n\_0$ for the range of base cases where $T(n) = Θ(1)$.

So by assuming that $T(2)$ and $T(3)$ are constant, we are treating them as base cases of the *recurrence*, is this correct? If so, how can we simultaneously consider them to be base cases of the *induction*? The base cases of the induction are input sizes in the range $n\_0 ≤ n \< 2n\_0$, but the base cases of the recurrence are input sizes $n \< n\_0$ (not sure of this). So, how can $T(2)$ and $T(3)$ be in both sets?
2. The authors conclude the proof by saying that *"Thus, we have $T(n) ≤ cn \lg n$ for all $n ≥ 2$..."*. They mention the constraint on $n$, but not the constraint on $c$, why is this? Shouldn't they say something like *"Thus, we have $T(n) ≤ cn \lg n$ for all $n ≥ 2$ **and** $c \geq \max\[T(2), T(3)\]$..."* instead?

# Answer
> 0 votes
1. The confusion comes from the fact that the $n\_0$ doesn't need to have the same value in both definitions. In the inductive proof, it's mentioned that $n\_0$ is taken to be $2$, while the base cases of the recurrence are using $n\_0 = 4$ so that $T(2)$ and $T(3)$ are constants.
2. The definition of $f(n) = O(g(n))$ is "There exist constants $0 \< c, n\_0$ such that for every $n \> n\_0$, $f(n) \< cg(n)$". To prove that $f(n) = O(g(n))$, it's enough to find specific values for this. In the proof, they take $n\_0 = 1$ and $c = \max\[T(2),T(3)\]$, so their conclusion shows that $T(n) = O(n\lg n)$.

---
Tags: algorithms, algorithm-analysis, recurrence-relation, divide-and-conquer
---


# Question
Title: Can an optimization algorithm be "universal"?
I am wondering if a Bayesian Optimization framework (e.g. Google's Vizier) can be used in lieu of a traditional solver like Gurobi or CPLEX.

In trying to answer this question, I realized that I don't know enough about optimization theory to answer a more general question: Just how interchangeable are heuristic approaches for solving computationally hard optimization problems?

Coming from an ML background, I'm reasoning by analogy with supervised learning problems: In ML, some methods like Neural Networks (with a sufficient number of layers) or Support Vector Machines are universal, in that they can approximate any shape decision boundary or regression function up to an arbitrary level of precision.

Are there equivalent algorithms in optimization theory that can be used to solve any optimization problem (linear, non-linear, continuous, discrete, etc...), e.g. can Genetic Algorithms or Particle Swarm Optimization be thrown at *any* optimization problem and give us a reasonable solution? SGD is used to solve NP-Complete problems (i.e. training a neural network) - does that mean that it can be used for any optimization problem?

I assume that the reverse is true: Not all optimization are universal, for example methods that work for LP or QP don't necessarily work for harder problems.

If it is indeed the case that some optimization algorithms are universal, is Bayesian Optimization one of these universal algorithms? Can be used to approach LP, QP, MIP, TSP, and NP-Hard problems in general?

# Answer
Even if there were, remember that there is no free lunch in search and optimization. An optimization algorithm *necessarily* trades proficiency in one class of problems for inefficiency in another class of problems. This is related to why the fact that neural networks, SVMs, and even the humble step function are "universal" is of little practical import.

Even within a specific class of optimization problem— say, linear programming— it is well known that a general, off-the-shelf optimizer e.g. Gurobi isn't likely going to do as well as some specialized optimizer tailored to your use case, should one be available (of course, frequently, there isn't one, which is why general purpose optimizers exist).
> 2 votes

# Answer
There is no heuristic that is "universal" in practice. Which heuristic works best in practice often depends on the specific problem you're dealing with. There's no one "silver bullet" heuristic that works great on every optimization problem.
> 1 votes

---
Tags: optimization, linear-programming, constraint-satisfaction, sat-solvers, quadratic-programming
---


# Question
Title: Definition of "deterministic" semantics in While language
I came across this definition in my book but I'm not sure that I understand it correctly.

Isn't this the same as saying: $\langle S, s\rangle \rightarrow s = \langle S, s\rangle \rightarrow s$ implies that $s=s$? Why do they use a different prime symbol here even though they are the same statement $S$ being executed on the same state $s$.

2nd Question: How does this statement by the author above allow us to "uniquely determine a final state s' if (and only if) the execution of S terminates"

I think I'm missing the point here because this definition came after **Induction on the Shape of Derivation Trees**.

3rd Question: How will this proof help us perform induction on the shape of derivation trees?

# Answer
> 0 votes
I've come back to this as I solved it but forgot to post my reasoning. The statement above simply states that if we execute a statement S on a state s twice, the resulting state should be the same. Hence, we can "determine" the final result unambiguously.

---
Tags: semantics
---


# Question
Title: Can we efficiently find the most common pair in a set of sets?
Given a collection of sets $C=\\{S\_1, S\_2, \ldots, S\_n\\}$ with each $S\in C$ holding some integers, I would like to find a pair $\\{x,y\\}, x\ne y$ such that $\\{x,y\\}\subset S$ for the highest number of $S\in C$ among all such pairs.

Is there an efficient algorithm to find such a pair?

# Answer
> 2 votes
Not an optimal answer, just a possible solution, close to brute-force.

* list all integers from all $S\_k$ and store them in a map; to each integer, associate the list of sets that contain it; sort these lists by set index. For $m$ distinct integers and an average list length $l$, this process will take like $O(m \\,l\log(l))$ time and $O(m\\,l)$ space.
* try all integers in turn; for every integer, try all *larger* integers (to form all possible pairs) and take the intersection of the two lists of sets by a merge-like process; keep the longest intersection. This takes $O(m^2\\,l)$ operations.

As a heuristic optimization, you can skip trying the elements with a list of sets smaller than the current best length.

**Update**: trying the elements by decreasing list length might reinforce the above heuristic.

# Answer
> 1 votes
Here is a plausible heuristic. It has no guarantees of approximation factor, but might be useful in practice given the problem sizes you mentioned. Pick a threshold $\tau$, say $\tau=100$, chosen to balance running time vs quality of approximation. Execute the following algorithm:

* Initialize $h$ to an empty hashmap (with a default that if you look up a nonexistent key, the lookup returns 0).
* For each set $S \in C$ such that $|S| \le \tau$:

+ For each pair $x,y \in S$ with $x\<y$:

    - Set $h\[x,y\] := h\[x,y\] + 1$.
* Optionally, delete all entries $x,y$ such that $h\[x,y\] \le \kappa$, for some constant $\kappa$ chosen to balance between running time vs approximately quality.
* For each $S \in C$ such that $|S| \> \tau$: (a)

+ For each $x \in S$:

    - Find all $y$ such that $y \in S$ and $h\[x,y\]\>0$. (b)
        - For each such $y$, such that $y\>x$:

        * Set $h\[x,y\] := h\[x,y\] + 1$.
* Output the pair $x,y$ such that $h\[x,y\]$ is maximized.

To improve the running time at the cost of reduced quality of approximation, you might be able to skip the loop marked (a).

There are many ways to implement the line marked (b):

1. You can iterate through all elements of $S$, and look them up in $h$. The running time will be linear in the size of $S$.
2. If you use an appropriate datastructure, you can implement the line (b) to run in time linear in the size of $S$ or $\\{y \mid h\[x,y\]\>0\\}$, whichever is smaller. In particular, for each $x$, you can keep track of $\\{y \mid h\[x,y\]\>0\\}$, sorted in order of increasing $y$. Then, you can merge those two sets using a standard merge-join, advancing the pointer where needed using binary search. This might be faster, especially if you delete entries of $h$ based on $\kappa$.

---
Tags: algorithms, sets
---


title: How to prove O(1) /= POLY(n)?

text:
# Question
Title: How to prove O(1) /= POLY(n)?
I know that there is no way to prove that P = NP, but how would one go about proving constant time /= P (i.e. O(1) /= POLY(n))?

(Or perhaps that any two other complexity classes do not equal each other).

If anyone has any papers on this, that would be really helpful :).

# Answer
Take the problem of determining whether the input, a natural represented as a binary string, is an even natural.

This can easily be solved by a TM in $O(N)$: just go to the end of the input and check the last bit. (Note that $N$ here is the length of the input string.)

This problem can not be solved in $O(1)$. By contradiction, assume that a TM does solve it in $k$ steps for any given constant $k$. Then, take any input that's longer than $k$. The TM starts on the first bit and in $k$ moves can not reach the last bit, so it have to give the same result for an even and an odd input number. Hence it does not solve the problem.

This reasoning can be generalized to prove that the problems solvable in $O(1)$ are strictly included in those solvable in $O(f(N))$ with unbounded $f$.
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: Parallel Algorithm Pseudocode: Helman-JaJa Listrank
What would Helman-JaJa listrank pseudocode be like? I tried looking around but all I found were "prosecode" descriptions (eg pp. 18-19 here) which I find kinda hard to follow.

# Answer
> 2 votes
# Helman-JáJá

Helman-JáJá's is a beautiful parallel algorithm, but the original paper (if I may say so) does not do a particularly great job of communicating some of that beauty to non-experts (this, incidentally, is also my only criticism of JáJá's wonderful text on parallel algorithms). Technically, it is a prefix computation (a.k.a. running totals) algorithm, and list ranking happens to be just one such prefix computation where it might be useful.

I'll quote the original paper (pp. 43-44) and give rough, very high-level pseudocode with comments, and a super brief summary in my own words of what the step aims to do. The paper assumes that it is operating on two types, viz. `List` and `Sublist`. If you're planning to implement this (a great concurrent programming exercise), these could be structs or classes, depending on the language you use (I recommend Cilk, but feel free to use what you like).

## Compute Processor Sums

> (1) Processor $P\_i (0\leq i\leq p - 1)$ visits the list elements with array indices $\frac{in}{p}$ through $\frac{(i + 1)n}{p} - 1$ in order of increasing index and computes the sum of the successor indices. \[...\] \[The\] negative successor index \[that\] denotes the terminal list element \[...\] is replaced by the value ($-s$) for future convenience. Additionally, as each element of `List` is read, the value in the successor field is preserved by copying it to an identically indexed location in the array `Succ`. The resulting sum of processor indices is stored in location $i$ of the array $Z$.

**Summary**: Partition the list evenly among the processors and let each processor compute the sum of successors. The summation is basically a reduction; tons of scope for exploiting parallelism if you know the right algorithms. The following part (ignoring the negative successor index and replacing it with $-s$, the array $Z$) is something you may find useful as implementation detail.

**Pseudocode**:

```
parforeach processor i operating on its partition of elements j:
  Z[i] <- Σj
  copy the successor of j into Succ, aligned with List by index

```

## Find the Head

> (2) Processor $P\_0$ computes the sum $T$ of the $p$ values in the array $Z$. The index of the head of the list is then $h = (\frac{1}{2}n(n - 1)) - T$

**Summary**: Reduce the processor-sums array to a single sum. The HJ paper treats this as a serial step executed only by the master thread/processor 0, but this needn't be. The formula finds the head, given the (+)reduction of the entire array (the paper covers why on p. 42, but the short version is that the head of the entire list is no one's successor, so it will be the only element 'missing' from the sum of all successors from $0$ to $n - 1$, which is given by $\frac{1}{2}n(n - 1)$).

**Pseudocode**:

```
processor 0:
  T <- ΣZ[i]
  h <- n(n - 1)/2 - T

```

## Partition the List

> (3) For $j=\frac{is}{p}$ up to $\frac{(i + 1)s}{p} - 1$, processor $P\_i$ randomly chooses a location $x$ from the block of list elements with indices $(j - 1)\frac{n}{(s - 1)}$ through $j\frac{n}{(s - 1)} - 1$ as a splitter which defines the head of a sublist in `List` (processor $P\_0$ chooses the head of the list as its first splitter). This is recorded by setting `Sublists[j].head` to $x$. Additionally, the value of `List[x].successor` is copied to `Sublists[j].scratch`, after which `List[x].successor` is replaced with the value ($-j$) to denote both the beginning of a new sublist and the index of the record in `Sublists` which corresponds to its sublist.

**Summary**: Pick random indices to split the list into $s$ sublists. Everything else in the paragraph is either mathematical formulations for the indices in each partition, or how you could encode the information you would need for the subsequent steps.

**Pseudocode**:

```
parforeach processor i:
  if (i = 0):
    x <- head -- x is the splitter
  else:
    x <- random index in the processor's partition
  Record the head of the sublist and its immediate successor

```

## Compute Local Prefixes

> (4) For $j=\frac{is}{p}$ up to $\frac{(i + 1)s}{p} - 1$, processor $P\_i$ traverses the elements in the sublist which begins with `Sublists[j].head` and ends at the next element which has been chosen as a splitter (as evidenced by a negative value in the successor field). For each element traversed with index $x$ and predecessor $pre$ (excluding the first element in the sublist), we set `List[x].successor = -j` to record the index of the record in `Sublists` which corresponds to that sublist. Additionally, we record the prefix value of that element within its sublist by setting `List[x].prefix_data = List[x]prefix_data ⊗ List[pre].prefix_data`. Finally, if $x$ is also the last element in the sublist (but not the last element in the list) and $k$ is the index of the record in `Sublists` which corresponds to the successor of $x$, then we also set `Sublists[j].successor = k` and `Sublists[k].prefix_data = List[x].prefix_data`. Finally, the prefix\_data field of `Sublists[0]`, which corresponds to the sublist at the head of the list is set to the prefix operator identity.

**Summary**: Compute the local running totals within each sublist. The rest of this long paragraph is bookkeeping to record the sublist prefix sums and track how the sublists are arranged (we're going to use it momentarily).

**Pseudocode**:

```
parforeach processor i:
  Compute the local prefix sum within i's partition of the list
  Store the local prefix at the next head
  Mark the next sublist as the ith partition's successor

```

## Order the Heads

> (5) Beginning at the head, processor $P\_0$ traverses the records in the array `Sublists` by following the successor pointers from the head at `Sublists[0]`. For each record traversed with index $j$ and predecessor $pre$, we compute the prefix value by setting `Sublists[j].prefix_data = Sublists[j].prefix_data ⊗ Sublists[pre].prefix_data`.

**Summary**: Traverse from head to head, computing the prefix sums of the stored prefix sums. In effect, this gives a relative prefix of the heads. The bookkeeping we'd done before helps us identify 'successor-heads' for this step.

**Pseudocode**:

```
processor 0:
  j <- the head of the second sublist
  pre <- head -- Sublists[0] is the head of the overall list
  while(sublists remain):
    Sublists[j].prefix_data <- Sublists[pre].prefix_data ⊗ Sublists[j].prefix_data
    pre <- j
    j <- next head after j

```

## Compute All Prefix Sums

> (6) Processor $P\_i$ visits the list elements with array indices $\frac{in}{p}$ through $\frac{(i + 1)n}{p} - 1$ in order of increasing index and completes the prefix computation for each list element $x$ by setting `List[x].prefix_data = List[x].prefix_data ⊗ Sublists[-(List[x].successor)].prefix_data`. Additionally, as each element of `List` is read, the value in the `successor` field is replaced with the identically indexed element in the array `Succ`.

**Summary**: Revisit all the sublists, adding the relative prefix of the head to each element. To use the list ranking example, if something was ranked 2 in its sublist, and its head (0 locally) got a relative rank of 5, add 5 to every element of this sublist to get their 'global' ranks (in the big list). Any of our bookkeeping that didn't help us in step (5) become useful in step (6), with `-(List[x].successor)` serving as an indicator of sublist membership. The last line is about restoring the 'true' successors, since we mutated `List[i].successor`.

**Pseudocode**:

```
parforeach processor i:
  foreach element x in its partition:
    List[x].prefix_data <- List[x].prefix_data ⊗ Sublists[-(List[x].successor)].prefix_data -- Add the head's relative rank
    List[x].successor <- Succ[x] -- restore the true successors

```

---

*If you're reading this carefully, and especially if you've done concurrent programming before, you might have spotted an excellent opportunity to execute the last step as a massively-parallel operation.*

---
Tags: algorithms, randomized-algorithms, parallel-computing, linked-lists, pseudocode
---


title: Page allocation for a program

text:
# Question
Title: Page allocation for a program
When my professor explained how the OS handles memory, he described demand paging, and how when a process starts up, the code page with the first instruction is loaded into memory, and everything else is loaded on-demand.

I haven't been able to find more information on this, but I'm curious if the stack would be allocated at this point and the memory filled with the argument vector for the program. Is this determined by the ABI? Would this be allocated at program start or only done by the OS at first reference to the stack?

Additionally, does the OS zero pages (my professor described these as anonymous pages) when giving them to the program if they do not have a reference on disk? It seems to me it would be best to do so (for security) if the memory was previously mapped by another process, and perhaps unnecessary if it were mapped by the same process.

# Answer
It depends on the operating system, in general. Some don't load the first code page, but let the load-on-demand system handle that!

The ABI does determine the state of the user program at the point where its entry is invoked. There may or may not be a user stack set up.

In the SysV ABI for x86-64 follow, the user state is, roughly, this:

* There is a user stack set up.
* `*argv` and `*envp` have been pushed on that stack.
* Four specific registers contain `argc`, `argv`, `envc`, and `envp`.

It is then up to the runtime for the programming language to set everything else up. We'll use C as our example. The relevant part of the runtime is called crt0 or c0 (short for C runtime, and the 0 means "very first"). The typical jobs that it has to do are:

* Set up the heap, signal handlers, the handler for `atexit`, etc.
* Set up exception handling and run global constructors if this is C++.
* Invoke `main`.
* On return from `main`, call `exit`.

One important difference in Windows is that the command-line is a single string; you can see this by looking at `WinMain`. So if you are writing a program that uses `main` as its entry point, the C runtime parses the command line for you.

As for zeroing pages, that is generally correct. The program file in a modern operating system is built from a number of segments. They are, typically:

* `text`, which is a part of the file that is mapped as read-only and executable. This corresponds to executable code.
* `rodata`, a part of the file mapped as read-only. This corresponds to read-only data (e.g. static string data, virtual dispatch tables, etc).
* `data`, a part of the file mapped as read-write and copy-on-write. This corresponds to statically initialised read-write data.
* `bss`, which is a region of memory mapped as zero-fill. This corresponds to uninitialised read-write data; because it is uninitialised, there does not need to be an image of this data stored in the program file.

The term "bss" was originally a pseudo-assembly instruction for the IBM 704, which meant "block started by symbol". The connection between this and the modern usage is tenuous and not relevant; Peter van der Linden suggested that you can think of it as "better save space".

Stack and allocated heap memory is also zero-fill. This is literally the case in some operating systems, where heap is allocated by memory mapping the special file `/dev/zero`, but in POSIX-like operating systems you can almost always map anonymous memory directly, or there is a special system call (e.g. `VirtualAlloc` in Windows, `vm_allocate` in Mach/macOS). The semantics are always that new regions are zero-filled.

(EDIT: Thanks to Peter Cordes for correcting one mistake in the last paragraph.)
> 1 votes

---
Tags: operating-systems, memory-management, virtual-memory, process-scheduling, paging
---


title: Disk addressing

text:
# Question
Title: Disk addressing
I am wondering how disk addresses are accessed from a program. From my understanding, the two main facilities are programmed I/O (instructions) and memory-mapped I/O (simply loads and stores). The second is usually just loads and stores into a specific part of memory that maps into the device.

* Is it common for memory-mapped I/O to encompass the whole disk address space or just specific device registers? Can the locations of these memory addresses overlap with valid RAM addresses?
* How does the disk expose the "block interface" to the kernel and at what level of memory management is this handled?
* How do you address these blocks and how does this all work?

# Answer
User programs generally do not "address" disk directly. Nor is the data from disk mapped into address space.

The general way that data is transferred between disk and memory is via DMA. Many disk host controllers also provide a slower way to do it as well using memory-mapped I/O registers or I/O ports, to make things simpler for firmware to boot an operating system.

See my previous answer for more on the how and why of DMA.

How a driver exposes disk transfers to the rest of the kernel is highly specific to the operating system. Typically, a modern operating system dedicates as much non-allocated memory as it can to be used by buffer cache; essentially, a cached copy of disk blocks. So the "operation" that a driver exposes essentially initialises a DMA request to a page frame of buffer cache, and then notifies the operating system when the request has completed.
> 0 votes

---
Tags: data-structures, operating-systems, memory-management, memory-hardware
---


# Question
Title: Can negative edge weights in a graph be positive numbers?
I'm a little confused by the concept of a "negative" edge weight. All of the examples I have seen represent negative edge weights as negative numbers. Is it possible for an edge weight to carry a negative weight, and be represented as a positive number?

As an example, suppose we had a graph of a network where the edges represent the time elapsed for data to travel between server A and server B. Suppose that we had a weight on each edge representing the lag time between certain servers (so perhaps the time for the data to travel between A and B has a lag of time t, which means the total time can be shown as the time to get to B from A, plus the lag). Is "lag" a negative edge weight in this case, even though it is a positive number?

# Answer
**Short answer:**

A positive weight is a positive number. A negative weight is a negative number.
> 2 votes

# Answer
The negative and positive refers to the sign of the number, i.e., a negative weight = negative number.

The reason why negative weights are important is because many algorithms only work when the edge weights are a non-negative.

A simple example of an algorithm is Dijkstra's Algorithm to find shortest paths in a graph. It doesn't work on graphs with negative weight. An example of such a graph is the following (if Dijkstra is run starting at node $a$):

In the example you gave above, intuitively it seems that lag time should be a positive number (since you'd want to minimise it), but it depends on the application, and I suppose both representations should work.
> 0 votes

---
Tags: graphs, graph-traversal, weighted-graphs, theory
---


# Question
Title: Minimum pumping length of a context-free language
I was studying about the minimum pumping length of the language $L$ containing all palindromes over $\\{a,b\\}$ from this material about the pumping Lemma for CFLs.

The productions are as follows:

$$S\to aSa \mid bSb \mid a \mid b \mid \lambda$$

We have two cases to deal with,

* when the string $w\in L$ is of sufficient length and |$w$| is even,

the string is either of the form $w=uaau^R$ or $ubbu^R$.

I understood the explanation and why the minimum pumping length is 3.

* when the string $w\in L$ is of sufficient length and |$w$| is odd, there may be four possibilities,

$$uaaau^R$$ $$uabau^R$$ $$ubbbu^R$$ $$ubabu^R$$

**I didn't understand the explanation given which goes like:**

>

**I didn't get why they left out $v$ or if $v$ is considered to be $\lambda$.**

However, I tried to proceed like this:

If we decompose $uaaau^R$ as $w=uvxyz$ as required by the pumping lemma for CFLs, we get $u=u,\ v=a,\ x=a,\ y=a, z=u^R$, the first 3 conditions of the lemma are satisfied.

For the last condition, we see that $uv^ixy^iz=ua^iaa^iu^R\in L$ for any $i\geq0$

---

Similarly, we can decompose $uabau^R$ as $u=u,\ v=a,\ x=b,\ y=a, z=u^R$.

So, $uv^ixy^iz=ua^iba^iu^R\in L$ for any $i\geq0$

---

**Could you please tell me whether my procedure is wrong and how to improve it?**

**I'm also very confused as to why they didn't mention $v$ in their explanation since the pumping lemma requires the string to be divided into 5 sub-strings $u,v,x,y,z$.**

# Answer
> 1 votes
Please ignore the second example in that material you are studying since it contains some errors. Please see the following corrected version of that example.

---

Let $L$ be the language consisting of all palindromes over $\\{a, b\\}$. The following is an unambiguous grammar for $L$. $$S \to aSa\mid bSb\mid a\mid b\mid\lambda$$ What is the minimum pumping length of $L$?

The answer is $1$.

If a palindrome $w$ has even length, the substring $aa$ or $bb$ is in the middle of the string. That is, $w = uaau^R$ or $w = ubbu^R$. Suppose $w = uaau^R$. We let $u = u$, $v = a$, $x = \lambda$, $y = \lambda$, and $z = au^R$. The first three conditions are obviously satisfied. For any $i\ge0$, $uv^ixy^i = ua^{i+1}u^R\in L$. The case that $w = ubbu^R$ is similar.

If $w$ has odd length, then there are two possibilities:

* $w = uau^R$.
We let $u = u$, $v = a$, $x=\lambda$, $y = \lambda$, and $z = u^R$. The four conditions are satisfied.
* $w = ubu^R$.
This case is similar to the case above.

The minimum pumping length cannot be $0$ since $1\le|v|+|y|\le|vxy|\le p$.

---
Tags: context-free, pumping-lemma, strings, substrings
---


title: P NP R RE closures

text:
# Question
Title: P NP R RE closures
I wrote the following table for all the closures in those classes.

is anything there incorrect?

also, would appreciate help with coNP and coRE closures. couldn't find much information about it online.

# Answer
updated table:

"?" means it's an open question (unkonwn)
> 1 votes

---
Tags: complexity-theory, computability, np, closure-properties, recursively-enumerable
---


title: Is T V F a tautology?

text:
# Question
Title: Is T V F a tautology?
(Consider $T=true$, $F=false$) I apologize for the simple question but I'm confused as to what is a tautology and what isn't and I haven't found a clear definition. I think that a tautology is a propositional well-defined formula which is true in all states. Does this allow $T$ v $F$ to be a tautology because it is true in all states and $T$ and $F$ are propositions themselves? Or does a tautology imply that there exists variables say $E\_{0}$ to $E\_{i}$ because it is a well-defined formula and not a closed formula?

# Answer
> 0 votes
Probably the best way to think of $T$ and $F$ is that they are "constants".

If you think of arithmetic-type algebra, $x$ and $y$ are pronumerals or variables, but $0$ and $1$ are constants. $T$ and $F$ are not unlike $1$ and $0$ (respectively). They are propositions in the same way that $x$ and $y$ are numbers.

A "tautology" is a statement that is true under all possible valuations of its variables. That means that a *closed* formula is always a tautology, a contradiction (which is the opposite of a tautology), or formally undecidable in the system.

$T \vee F$ is closed formula; it has no free variables. Therefore, yes, it is a tautology. Any possible boolean valuation of its variables (all zero of them) is true.

# Answer
> 0 votes
A tautology is something that is always true. $T\lor F$ is an almost-trivial example of one (the trivial example would be $T$ by itself).

As a bonus, a contradiction is something that is always false. The trivial example is $F$ and an almost-trivial example like the one you asked about would be $T\land F$.

---
Tags: propositional-logic
---


# Question
Title: How does merge sort decide how to merge an array?
So, the way I understand merge sort: We split an array into two halves, then we split those halves into halves, etc. until we get arrays that can be split no further. We kind of build up a tree in the process. Then we do what I call "compare, sort, merge." Starting with the unit-length arrays, we compare the first element of each sibling array. If the first element of array A is greater than (or less than, depending on which order is wanted) the first element of array B, then the values are swapped out. The arrays are then merged as follows:

\[element 0, array A, element 0 array B, element 1 array A, element 1 array B\]

For example, given the array \[14,34,9,20\], the arrays are split 2 times: first into \[14,34\], then into \[14\],\[34\],\[\[9\],\[20\]. Since 14\<34, nothing happens. Since 9\<20, nothing happens there. So we end up with \[14,34\],\[9,20\]. Since 14 \> 9, we end up with \[9,34\],\[14,20\]. 34\>20, so we end up with \[9,20\],\[14,34\]. Then we merge the arrays without comparing values - the first elements of each array go first, followed by the second elements of each array, like so: \[9,14,20,34\].

Am I understanding correctly?

# Answer
I am not sure what you want to be confirmed in your explanation. The structure of MergeSort is a typical Divide & Conquer pattern as follows:

```
MergeSort(S):
  if |S| == 1
    Skip; // Nothing to do, S is already sorted
  else
    S0, S1:= Split(S); // S0 and S1 are two halves of S
    MergeSort(S0); MergeSort(S1); // Now, S0 and S1 are sorted (by recursion)
    S:= Merge(S0, S1); // Now S is sorted

```

The `Split` operation is trivial. The `Merge` is the interesting operation. It relies on the fact that you can obtain a single sorted sequence from two independent sorted sequences in a single pass, by intertwining the elements in increasing order.

```
MergeSort(14, 34, 20, 9)
  MergeSort(14, 34)
    MergeSort(14) -> 14
    MergeSort(34) -> 34
    Merge(14; 34) -> 14, 34
  MergeSort(20, 9)
    MergeSort(20) -> 20
    MergeSort(9) -> 9
    Merge(20; 9) -> 9, 20
  Merge(14, 34; 9, 20) -> 9, 14, 20, 34

```

---

MergeSort has many good properties. Unfortunately, the Merge step cannot be performed in-place, so extra space is required on every recursion level.
> 0 votes

---
Tags: sorting
---


title: Memory (physical addressing)

text:
# Question
Title: Memory (physical addressing)
From my understanding, physical memory (main memory -- DRAM) is addressed differently than disk. This is all a bit of an abstraction to me, and I am hoping to make my understanding more concrete.

* Page tables store physical addresses in RAM. They may be marked invalid in the hardware to generate a trap to the OS (page fault) which then recognizes that the page actually resides in swap space or is an anonymous page that is unallocated (heap)

When you address physical memory, how does that work? Is it just like virtual addresses where it's a large linear address space of the size of your RAM? Do you just use simple C pointers but your CPU is in real (and not virtual) mode so its interpreted correctly? Any concrete examples would be appreciated, specifically how is it done in a way so that the hardware can interpret it correctly when performing transformations? From my understanding, it is simply a simple concatenation of bits "Physical Page Number" and the Offset, which forms a Physical Address.

# Answer
> 2 votes
The whole point of using the abstraction of virtual addresses (which is to say, giving every process the illusion that it has all the memory reserved for itself) is to free the application software from the concerns of managing the physical memory and isolate processes from each other.

The specifics involve a number of engineering tradeoffs, but this is facilitated through some kind of mapping that is maintained by the system software. This mapping is updated as processes start executing and terminate, and as the application code executes. For instance, `malloc` establishes a page file as a backing store. Something like `mmap` allows processes to explicitly map file bytes (loaded one page at a time). The applications use memory addresses in the virtual address space, which are translated by the operating system into physical addresses.

This diagram illustrates the address translation process that the system software would execute. The mapping of a virtual address to a physical address is first checked in the TLB (translation lookaside buffer), which is an associative cache of recently-used mappings. TLB misses, in turn, look for the mapping in the page table. If a mapping is found, it is stored in the TLB. A page table miss - either because there is no translation available, or because the existing one is invalid (a segmentation fault), or simply because the page is not in physical memory and has been swapped out to make room for other pages - triggers a page fault. In the latter case (swapping out), the page is read from the swap file/swap partition and written to both the page table and the TLB (a write through).

When the physical memory is full, the page replacement policy kicks in and decides which page to evict to make room for the incoming page. Most of the page replacement algorithms that you're likely to encounter (unless you go super deep into this stuff) are approximations of LRU (least recently used), which, as the name suggests, evicts the least recently used page.

The theoretical optimal replacement policy would be to evict the page that will be accessed farthest in the future, which, evidently from the phrasing, requires (for lack of better wording) a bit of auguring. As it happens, though, we're in luck - LRU happens to be a good approximation - asymptotically close, in fact, but I digress.

What do physical addresses look like? They're not really different from logical addresses.

Whether or not you have a valid translation only changes whether the physical page number is read from the TLB, the page table, or the swap partition/file. The addresses themselves are structured similarly - a (virtual page number + offset) maps to a (physical page number + offset), where the offset isn't translated but simply read from the virtual address.

---
Tags: data-structures, operating-systems, memory-management, virtual-memory, paging
---


# Question
Title: Is a machine Turing-complete when it can decide a context-sensitive language?
If a machine can decide a context-sensitive language (like the language of palindromes with a non-linear center) is that fact a proof that the machine is Turing-complete?

Can this be used to prove Turing completeness of a programming language when a program that can decide a string of a context-sensitive language can be written in that programming language?

Or else, can the proof be achieved by using a recursively enumerable language such as the language of prime numbers?

# Answer
> 17 votes
No. Context-sensitive languages can be recognized by linear-time nondeterministic Turing machines, which are not Turing complete.

The ability to recognize a recursively enumerable set also does not prove that the programming language is Turing-complete. For instance, the set $\\{0,1\\}^\*$ is recursively enumerable, but is recognizable by a DFA, which is not Turing complete.

Or, consider a programming language with only two constructs: if-then-else statements, and "isprime?()", a primitive function that can be applied to any integer to test whether it is prime. Such a programming language can recognize the language of prime numbers, but is not Turing-complete.

---
Tags: formal-languages, turing-machines, formal-grammars, turing-completeness
---


# Question
Title: Regular expression for the language containing neither aa nor bb
I want to create a regular expression for the language

$L=\\{ w \in \\{a,b\\} |$ w has neither aa nor bb as a subword$\\}$.

I've tried various things, but I can't seem to get the correct regular expression.

# Answer
$((ab)^∗∪(ab)^∗a)∪((ba)^∗∪(ba)^∗b)$ will work.

The possibilities are: $a,ab,aba,ababa,...$ or $b,ba,bab,baba,...$ or empty string
> 0 votes

# Answer
Empty or a singleton will work. Among the strings of at least two characters, $a$ and $b$ must alternate.

Hence $$b^+(ab)^\*a^+$$
> 0 votes

# Answer
(ab)*(a+ε)+(ba)*(b+ε) will work.
> -2 votes

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Single Source Shortest Path Problem with Multiple Weights Each Edge
I am trying to solve the single source shortest path problem, but with the added constraint that there is an additional weight on each edge (so we have two weights in total for each edge, call them p and q) and for this additional weight, we want the shortest path to be strictly monotonically increasing along the whole path (otherwise, for the purposes of this problem, it's not a valid shortest path). So our problem is that we want the shortest path for the value of p and that for every q on each edge in this path, q is increasing.

I am thinking that a solution could build from Bellman-Ford (examining each edge weights) but so far I am stuck, because it seems to me that I need to store information about the paths somehow.

# Answer
You can use the following variant of the Floyd-Warshall algorithm:

Let $u$ and $v$ be any vertices in the graph. Let $E\_u$ and $E\_v$ be the set of edges incident on $u$ and $v$, respectively.

Then, define $S\[u,v,e\_u,e\_v,k\]$ be the shortest path of at most $k$ edges between $u$ and $v$ that starts at an edge $e\_u \in E\_u$ and ends at an edge $e\_v \in E\_v$.

*Base Case*: $S\[u,v,e\_u,e\_v,1\] = w\_p(u,v)$ if there exists an edge between $(u,v) = e\_u = e\_v$; otherwise $S\[u,v,e\_u,e\_v,1\] = \infty$.

*Dynamic Programming Step*: $S\[u,v,e\_u,e\_v,2k\] = \min\_{w \in V } \Big\\{ \min\_{e\_w, e\_w' \in E\_w \text{ and } w\_q(e\_w) \< w\_q(e\_w')} \Big\\{ S\[u,w,e\_u,e\_w,k\] + S\[w,v,e\_w',e\_v,k\] \Big\\} \Big\\}$.

*Final Solution*: The value of the shortest path from $s$ to $v$ that satisfies the monotonic constraint is: $\min\_{e\_s \in E\_s, e\_v \in E\_v} \Big\\{ S\[s,v,e\_s,e\_v,|V|\] \Big\\}$

The running time is polynomial in $|V|$ and $|E|$. It might be an overdo; but it can be a starting point to discover some better algorithm.
> 2 votes

# Answer
Let $G=(V,E)$ be the original graph. Define a new graph, $G'=(V',E')$, that represents the set of all valid paths in $G$, where a path is considered valid if its $q$-values are strictly monotonically increasing.

In particular, $V'=V \times Q$, where $Q=\\{q(u,v) \mid u,v \in V\\} \cup \\{-\infty\\}$ is the set of $q$-values that occur on the edges of $G$ along with $-\infty$. Thus, a vertex in the new graph is a pair $\langle v,x \rangle$. Now we have an edge $\langle v,x \rangle \to \langle w,y \rangle$ in the new graph whenever $v \to w$ is an edge in $G$ and $y = q(v,w) \> x$, and the $p$-weight on this edge is $p(v,w)$. If $s$ is the source vertex in $G$, then the source vertex in $G'$ is $\langle s,-\infty\rangle$.

Now use any shortest-paths algorithm to find the shortest paths in $G'$ starting from the source $\langle s,-\infty\rangle$. If all $p$-weights are non-negative, you can use Dijkstra's algorithm. If $p$-weights can be negative, use Bellman-Ford.

---

This is a product construction, where you're taking a product between $G$ and a secondary graph which requires that $q$-values be strictly monotonically increasing. See especially How hard is finding the shortest path in a graph matching a given regular language? for the general case, and Shortest path given correct order of colours? and Retrieving the cheapest path of a graph with time-dependent edge weights for a few other analogous examples.
> 2 votes

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


# Question
Title: Clarifications about tree-width definition
I have read the definition of treewidth/tree-decomposition both in Wikipedia and in here: https://medium.com/@karlrombauts/treewidth-how-all-graphs-are-trees-in-disguise-ec699b69e2fb

I'm finding something hard to understand why the treewidth of a tree is $1$. By the definition of tree-decomposition, I may select to have a single $X\_1$ to contain all vertices. All requirements hold.

If we are referring to the $|X\_1|$ it will be $n$ and then the tree width is $n-1$. If we are referring to the quantity of such sets, so we have only $X\_1$, therefore the treewidth is $1-1=0$.

Likewise, this can be for any graph, not only trees. We can always decide $X\_1$ will contain all vertices...

So I am not sure why it is claimed that the treewidth of a tree is exactly $1$? I think I'm missing out something in the understanding, and I'm looking for an explanation to this, and maybe one more example for a non-tree graph when the treewidth isn't trivially $1$.

Also, I read that $k$-treewidth do not contain $K\_{k+2}$ as a minor. I'm not looking for a proof,but merely an intuition.

**Edit:** I understand now the width is the minimal maximal bag size. However, I still fail to see why any tree has width $1$. If the idea is $1$ bag for $1$ edge, wouldn't this be the case for any graph too? Why will it only work for a tree?

# Answer
Yes, for a tree, the decomposition corresponds to one bag per edge. However, if you consider the graph $C\_6$, the cycle on 6 vertices, you don't get a *tree* decomposition if you follow the same scheme.

What you would do for a cycle is essentially to pick an arbitrary vertex, $v\_1$, remove it from the graph. Perform your trick with one bag per edge for the remaining graph (a $P\_5$), and then put $v\_1$ into every bag.

This naive trick works for every graph, i.e., find a smallest set $X$ such that $G-X$ is a forest, and then add $X$ to every bag. *Warning*: does not guarantee that the width is optimum, but does actually give you a valid tree decomposition, and perhaps some intuition. That also explains how adding one vertex can only increase the width of a graph with at most one.

(Ps, this set $X$ is called a *feedback vertex set*).
> 2 votes

---
Tags: graphs, terminology, trees, treewidth
---


# Question
Title: Minimum coins to make change when real numbers are allowed
There is the classical version of the minimum coins to make change problem where the change and the set of coins available are all integers. Given an infinite amount of each type of coin, we're asked the smallest number of coins required to make change for a given amount. This can be solved with dynamic programming, Python code below. The code will return $\infty$ when the amount can't be made.

```
def coinsChg(coins, amount):
   dp_array = [np.inf for i in range(amount+1)]
   dp_array[0] = 0
   for coin in coins:
      for j in range(coin, amount+1):
         dp_array[j] = min(dp_array[j], dp_array[j-coin]+1)
   return dp_array[-1]

```

This got me thinking about the case where the coins and the amount to be constructed can be any real numbers and not just integers. One complication is that we can't express real numbers exactly on a computer, complicating the question of whether or not the amount can be made exactly. So let's say we restrict ourselves to rational numbers. For the coins and the amount, we are given the numerators and the denominators. Now, given the integer arrays of coin numerators, coin denominators, the amount numerator and amount denominator, we need to return the smallest number of coins to make the amount exactly. If this isn't possible, the algorithm should return $\infty$ like before. Dynamic programming seems to be out of the question now. So what is a good algorithm for solving this? Is it NP-hard?

# Answer
> 1 votes
Unfortunately, it is NP-hard, by reduction from the subset sum problem.

The reduction is trivial: let $S$ be a set of integers, and $T$ a target sum (i.e., an instance of the subset-sum problem). Consider the following change-making problem: let $S$ be the set of coin denominations, and $T$ be the desired change. Then there exists a way to make change for $T$ using these coins, iff there is a subset of $S$ that sums to $T$.

---
Tags: dynamic-programming, coin-change
---


# Question
Title: Semi-decidability of Fullness problem for Turing Machines
**Input:** code $u$ of a Turing Machine working on a binary alphabet.

**Question:** Does $M\_u$ accept all words $w \in \\{0,1\\}^\*$.

This is of course an undecidable problem. I wonder if the problem is semi-decidable or the complement of the problem is semi-decidable.

Initiatively it can't be semi-decidable that would require testing an infinite amount of words, and its complement can't be semi decidable either - that would require detecting if the machine halts for some word, however I can't think of a reduction that would prove it.

# Answer
> 0 votes
That's because the set of total Turing machine((Let's say TTM)) is not recursively enumerable. If you prove that the set of Total Turing machines is not recursively enumerable, you actually prove that this set is not decidable. Because for every set S, If S is decidable, Then S is recursively enumerable. For proving that TTM is not recursively enumerable, Let's say there is a Turing machine which enumerates TTM. Then There would be a computable function f which can assign a natural numbers to every Total Turing machine.

f(k)\[l\] refers to output of Turing Machine f(k) with l as input.

Now, define Turing machine TD to give f(i)\[i\]+1 for each natural number i. Since f is computable and all of f's range's programs are total. TD exists. But TD is not in f's range. Because for every natural number i, the program f(i) can not be TD because for input i, f(i) and TD have different outputs.

So the set of Total Turing machines is not r.e((recursively enumerable)) which means it is not decidable.

---
Tags: formal-languages, turing-machines, automata
---


# Question
Title: Finding the first vertex in a recursively growing graph
I have an undirected graph which grew according to a **recursive algorithm**, i.e., it started with a single vertex and then, one after another, new vertices arrived and connected to existing ones.

Now, I'm given the graph with, say, $n$ vertices. **I would like to estimate (efficiently) which vertex was the first one.** How can I do so? Note that this is, in most cases, a probabilistic question. This means that you cannot determine the first vertex but you can give an answer which is the most probable vertex.

---

I am already aware of an algorithm by Shah & Zaman (2011) from this paper. However in this paper, they assume that the graph of interest (in their case the rumor graph) is actually a tree. In my case however, this is *not* the case.

---

**Requirements to the graph growing algorithm:**

* In each step, only one vertex is added.
* Vertices from previous steps are *not* regarded differently. This means that when a new vertex arrives, it does not have any information on the timing the previous vertices were added.

# Answer
If I understand correctly, the first node is the one and only one in the graph having only outgoing edges. (If no such node exists, there is no solution.)

If all you have is the graph topology (which representation ?), all you can do is an exhaustive search node by node until you find one with only outgoing edges.

If the graph is a DAG, you can trace a backward path from an arbitrary node. But in the worst case this is not faster than exhaustive.
> 0 votes

---
Tags: graphs, probability-theory
---


title: False proofs that look correct

text:
# Question
Title: False proofs that look correct
I remember seeing a list of False Proofs when I was taking Discrete Maths and I found it to be very interesting and also helpful.

So, if anyone knows some common proof mistakes students make or some cool sneaky way to trick people in a proof send them my way! Bonus points if they're cs/algorithms related.

Thank you so much!

# Answer
One of my favourites is the "brothers paradox": https://en.wikipedia.org/wiki/Boy\_or\_Girl\_paradox

I tell it as I learned it\*, as follows: in a village, each family has two children, elder and younger. The children are born with probability $\frac12$ for either boy or girl.

I knock on a door, and a boy opens it and says "I'm the elder". What is the probability he has a sister? (clearly $\frac12$).

I knock on another door, and a boy opens it and says "I'm the younger". What is the probability he has a sister? (clearly $\frac12$).

I knock on a third door, and a boy opens it and says nothing. What is the probability he has a sister?

Now the lies start: if I use the law of total probability, I might say something like: $$Pr\[sister\]=Pr\[sister|elder\]\cdot Pr\[elder\]+Pr\[sister|younger\]\cdot Pr\[younger\]=\frac{1}{2}Pr\[elder\]+\frac{1}{2}Pr\[younger\]=\frac12$$ But on the other hand, I could say that the only case where he does not have a sister is the (boy,boy) setting, and we already know this house is not (girl,girl), so the probability is $\frac23$.

Both are very convincing, if told correctly.

The fallacy is that the sample space is undefined, or put more whimsically "How does the family decide who answers the door?"

\*I learned it this way from the legendary Prof. Raz Kupferman.
> 18 votes

# Answer
Merge-sort can be done in linear time!

Indeed, the time complexity to sort a list or array of length $n$ verifies$^{(1)}$: $$T(n) = T\left(\left\lfloor\frac{n}2\right\rfloor\right) + T\left(\left\lceil\frac{n}2\right\rceil\right)+ \Theta(n)$$

Let us prove by induction that $T(n) = \Theta(n)$:

* the base case is $n = 1$, and this is the base case of the merge-sort algorithm, which is indeed done in constant time, so $T(1) = \Theta(1)$.
* assume $T(k) = \Theta(k)$ for all $k\< n$, for some $n\> 1$. Then using the previous formula and induction hypotheses: $$T(n) = T\left(\left\lfloor\frac{n}2\right\rfloor\right) + T\left(\left\lceil\frac{n}2\right\rceil\right)+ \Theta(n) = \Theta\left(\left\lfloor\frac{n}2\right\rfloor\right) + \Theta\left(\left\lceil\frac{n}2\right\rceil\right)+ \Theta(n) = \Theta(n)$$

By induction, we indeed got that $T(n) = \Theta(n)$ and we got a comparison sort in linear time.$^{(2)}$

$\phantom{a}$

$^{(1)}$ I will not prove that fact, this is a well-known (correct) formula.

$^{(2)}$ Actually, using the same kind of proof, one could prove that the merge operation is done in $\Theta(1)$, and so, merge-sort can be done in $\Theta(1)$ too.
> 16 votes

# Answer
I have often seen among undergraduates that they believe that the heaps are constructed in $\Theta(n \log n)$ time.

The standard algorithm for that is to insert an element to a heap one after another. Each insertion takes $O(\log n)$ time. Atleast $n/2$ elements have heapify cost $\Theta(\log n)$. This gives overall running time of the algorithm: $\Theta(n \log n)$.

However, interestingly, the heaps can be constructed in $\Theta(n)$ time. The algorithm places all the numbers contiguously in an array. Then the algorithm calls heapify operation starting from the last element and iteretively do the same till the first element. In each heapify call, we are bubbling the elements down. Note that the first element has heapify cost of $\Theta(\log n)$ and atleast $n/2$ elements at the end of the array have heapify cost of $\Theta(1)$. Using simple inequlities, one can show that the total heapify cost adds to only $\Theta(n)$.

I find it a sneaky proof indeed!
> 9 votes

# Answer
This one is regarding $\mathsf{FPT}$ time algorithm.

Suppose an algorithm has time complexity of: $O((\log n)^k \cdot n^{O(1)})$.

Is it an $\mathsf{FPT}$ time algorithm in parameter $k$?

Well obviously no since the time complexity is not of the form $O(f(k) \cdot n^{O(1)})$. This is what most of people think, and even many researchers in the field as well.

However, that is incorrect!

Interestingly, $(\log n)^k$ $= O(2^{k^2/2} \cdot n)$ (See Hint 3.18, Page 74, from the book: Parameterized Algorithms).

Thus, the running time of the algorithm is $O(2^{k^2/2} \cdot n^{O(1)})$ which is indeed $\mathsf{FPT}$ in parameter $k$.

So, the answer is actually yes!
> 9 votes

# Answer
This one is classic.

$0$-$1$ Knapsack problem is polynomial time problem since there is dynamic programming solution with running time $O(n W)$ time.

However, it is incorrect.

Note that the input size is $poly(n + \log W)$. Therefore, the running time of $O(n W)$ is exponential in the input size. Infact, the $0$-$1$ Knapsack problem is $\mathsf{NP}$-hard and the running time of $O(n W)$ is pseudo-polynomial.

---

Similarly, a naive algorithm for testing if a number is a prime number has running time $O(\sqrt{n})$. It is not polynomial running time algorithm.
> 8 votes

# Answer
An simple example that I can think of, which is commonly use as introductory topic in amortized analysis, is the analysis of dynamic table. The usual scenario is to analyze the total time needed to insert $n$ elements in a dynamic table with some initial capacity, say 1. Now each time the table is full, it will be resized, say twice the size, by creating a larger table and transferring all current elements to the new table and then proceed with the insertion. Clearly, an insert takes $O(n)$ time in the worst-case. So if there are $n$ elements to be inserted, the total time to insert them all is at most $n \times O(n) = O(n^2) $. This of course is not tight and with some careful analysis, e.g. summing-up the *actual* time of each insert instead of relying on the worst-case, it can be shown that many of these inserts actually takes $O(1)$ time, hence the time needed to perform the sequence is at most $O(n) $.
> 6 votes

# Answer
Induction often yields great wrong proofs because there are many things which can fail:

* The induction base $P(0)$ can be false, or it may be missing at all and hence the rest of the induction is based on a false assumption. If the induction base is false, everything else is an *ex falso quodlibet*.
* The induction step $P(k) \Rightarrow P(k+1)$ can have an antecedens which is not true for all $k$. Also in this case, we have an *ex falso quodlibet*.

So, with an *ex falso quodlibet*, every nonsense can be "proven".

There are many cases where it is not quite obvious that either $P(0)$ or $P(k)$ is actually false. One of my favourites (involving $P(k)$ not being generally true): Every non-negative integer number is twice as large as itself:

$\forall n\in \mathbb{N}, n \geq 0: n = 2n$

https://math.stackexchange.com/questions/2439032/given-a-wrong-proof
> 5 votes

# Answer
Maybe not exactly what you're looking for, but the Monty Hall problem is famously counterintuitive.

There are three doors. One conceals a car, and the other two goats. You select one door. The host opens another door, and it has a goat. By changing your choice to the other closed door, you double your odds of choosing the car, compared to keeping your original choice.

> Many readers of Savant's column refused to believe switching is beneficial and rejected her explanation. After the problem appeared in Parade, approximately 10,000 readers, including nearly 1,000 with PhDs, wrote to the magazine, most of them calling Savant wrong...Paul Erdős, one of the most prolific mathematicians in history, remained unconvinced until he was shown a computer simulation demonstrating Savant's predicted result.
>
> https://en.wikipedia.org/wiki/Monty\_Hall\_problem
> 3 votes

# Answer
Spaghetti sort can sort numbers in linear time.

Assume without loss of generality that the numbers to be sorted are all in the interval $(0,1)$. A whole spaghetti has length $1$.

1. For each number cut one spaghetti to the corresponding length. This clearly takes $O(n)$.
2. Grab all the spaghetti and hit the whole bundle on the table upright. Takes $O(1)$.
3. Lower your hand slowly on the bundle of spaghetti. The first spaghetti you hit corresponds to the biggest number. Remove it from the bundle. Doing this once takes $O(1)$. Repeat this step $n$ times.

Total time to sort the entire stack is $O(n)$.

**Edit:** I encountered this 'algorithm' first in my student days and we knew there had to be a problem because sorting numbers should always take at least $O(n\log(n))$. I thought the key problem lies in step 2. This step is not actually constant effort, it takes longer with a bigger number of spaghetti. From discussions in the comments I learned that step 1 is not actually linear either. You need to cut to a certain accuracy and this takes more effort if you need higher accuracy.
> 3 votes

# Answer
Along the lines of rexkogitans's remark that proofs by induction are fertile ground for false proofs: one of my favorites is that every natural number can be uniquely described in fifteen English words or less.

Let the set of counterexamples be $S$ and assume, for contradiction, that $S$ is nonempty. Every nonempty set of natural numbers must have a least element; call it $x$.

But then $x$ is "the smallest natural number that cannot be uniquely described in fifteen English words or less", and therefore $x$ is not in $S$, a contradiction. So $S$ must be empty and the theorem holds.
> 3 votes

# Answer
As a general idea, maybe a 'proof' of a greedy algorithm as applied to a problem where the failure case is not immediately obvious?

A classic example (used for introducing Ford-Fulkerson) would be always taking the s-t path with max flow (without creating the residual graph), with some hand waving on how another "optimal" solution replacing paths $P\_0, \cdots, P\_n$ with paths $Q\_0, \cdots, Q\_n$ must have the cumulative flow of the first set larger or equal to the second set.

For example (an argument I just came up with): all of the Q flows cannot be added to the current optimal solution, and thus each of them shares a bottleneck with one of the P flows (it cannot bottleneck another flow that is unchanged otherwise the solution we are considering is not feasible). Thus, replacing a P flow with the associated Q flows that it bottlenecks will at most maintain the flow because the bottleneck is still there. This could probably seem believable if the final statement is disguised well and given some supporting "evidence".

A greedy algorithm for set cover also seems very intuitive (because of how similar it seems to other greedy problems) and it takes a bit of thinking to find a counter example.
> 2 votes

# Answer
(Too long and formatting-heavy for a comment.)

For each of the false proofs you linked (https://imgur.com/a/SUT0cRX), here is my brief analysis of each. I've spoilered them in case you want to look at each one individually yourself before checking what I said. Please let me know in the comments if I made any mistakes or you have any questions.

Theorem 0.1:

> This is true given the condition that for all x there exists some y such that x ~ y. P.S. #1: This condition is necessary because being reflexive implies this. P.S. #2: https://en.wikipedia.org/wiki/Equivalence\_relation#Connections\_to\_other\_relations confirms both parts of this: "A partial equivalence relation is transitive and symmetric. Such a relation is reflexive if and only if it is total, that is, if for all a, there exists some b such that a ∼ b. \[ proof 1: If: Given a, let a ∼ b hold using totality, then b ∼ a by symmetry, hence a ∼ a by transitivity. — Only if: Given a, choose b = a, then a ∼ b by reflexivity. \] Therefore, an equivalence relation may be alternatively defined as a symmetric, transitive, and total relation."

Theorem 0.6:

> This works for propositions which only have 2 possible values, true or false. It does not work for predicates that are sometimes true and sometimes false.

Theorem 0.2:

> "x times" depends on x, but you treated it as a constant. (Also, you divided by x without stating that it must be non-zero.)

Theorem 0.3:

> Splitting the square root only works when the terms are positive.

Theorem 0.4:

> The inductive step is invalid when n=1, because there is no overlap between the sets.

Theorem 0.5:

> The inductive step is invalid when n=0, because 1 is not less than or equal to 0.
> 1 votes

# Answer
Here's a wrong proof, though it only takes a moment's thought to dispel:

"**Theorem**": $\mathrm{P} \not= \mathrm{NP}$

"**proof**": There is some oracle $O$ such that $\mathrm{P}^O \not= \mathrm{NP}^O$. But if $\mathrm{P} = \mathrm{NP}$ then $\mathrm{P}^O = \mathrm{NP}^O$ for *any* oracle $O$! QED.
> 0 votes

---
Tags: algorithms, np, proof-techniques, education
---


# Question
Title: Proving that $Prefix(L)$ is recursively enumerable
Given a language $L$ that is recursive prove that $Prefix(L) = \\{ x \ | \ xv \in L\\}$ is recursively enumerable.

My first attempt at this was to try and formulate an algorithm in pseudocode.

```
Prefix-Recogniser(x)
    for v in Σ*:
     w = xv
     if L-Decider(w) -> YES:
      return YES

```

Since $L$ is recursive a decider for it say $M$ exists and if $x$ is a prefix of $L$ at some point Prefix-Recogniser will respond with YES.

A Turing Machine can be easily implemented for the pseudocode above but is my thought process correct?

# Answer
Yes your way is true. Because when L is recursive, your language should have a decidable alphabet. Because if it doesn't, then the set of your language's words can't contain a recursive subset. So your way to enumerate all possible words is true.
> 0 votes

---
Tags: formal-languages, turing-machines, turing-recognizable
---