# Question
Title: Scheduling algorithm to minimize the number of late jobs
There are $n$ (non-recurring) jobs where each job $i$ has an arrival time $a\_i$ and a duration $t\_i$. All the jobs share a deadline length $d$ (deadline for each job is $a\_i + d$). The problem is to find a (non-preemptive) scheduling time $s\_i$ for each job on a single processor/machine such that the total number of missed deadlines is minimized (or maximize the number of on-time jobs).

So, even in cases where not all deadlines can be met, we want to find out the schedule that meets the maximum number of deadlines. Does this problem even have a polynomial solution? I tried a dynamic programming approach, but I can't really identify the subproblems.

For example, given this set of jobs (where each job is described by $(a\_i, t\_i)$): \[(0, 50), (5, 20), (25, 40)\] where $d = 60$, the best we can do is to meet 2/3 deadlines with a schedule like this: \[(5,20), (25, 40), (65, 50)\].

# Answer
For an optimal selection, one possible sequencing is always the one respecting the order of arrival time $S\_0$. Another may be possible, but you can check that you always can do the switches to obtain $S\_0$. This is due to the fact that all jobs have the same $d$.

Thus, your problem is equivalent to select the subset of jobs which do not overlap if they are executed as soon as possible in arrival time order.

Then you can do an approximative greedy algorithm considering jobs in increasing duration order. Counting the duration sorting, this has a $O(N \log(N))$ time complexity. It would generally give a very good result but might fail for example on $(a\[i\], t\[i\]) = \[(0, 60), (30, 50), (60, 60)\]$ with $d = 60$.

Or you can do a dynamic programming on $T$ array of $t(n)$, the soonest time at which $n$ jobs are achieved.

Initially, $T\_0 = \[0, +\infty, +\infty ..., +\infty\]$, it has size $N+1$, the number of jobs (+ 0 index). The jobs are considered in increasing arrival time order. $T\_k$ is the state of $T$ after considering $k^{th}$ job.

To keep track of the selection, you need an array $previous$ of size $N \times N$ and an array $lastElement$ of size $N$. All are initially filled with -1. $lastElements\[i\]$ tracks the index of the last added job for $T\_{i+1}$. $previous\[i\]\[j\]$ tracks the element added just before j for $T\_{i+1}$.

Then the sub-problem is to compute $T\_{k+1}$ from $T\_{k}$.

This is the pseudo-code:

```
function next_job(T_last, a_k, t_k, d):

    T = T_last

    for i from 0 to N-1 do:
        if T_last[i] == +inf then break

        begin = max(a_k, T_last[i])
        end = begin + t_k

        if (end > a_k + d) then continue

        if (T[i+1] < end) then:

            T[i+1] = min(T[i+1], end)
            lastElement[i] = k
            if(i > 1) previous[i, k] = lastElement[i-1]
        end
    end

    return T

```

The final result is of course the largest $i$ such that $T\[i\]$ is not $+\infty$. It has a $O(N^2)$ overall time complexity.

To obtain the selection, you pick $elem0 = lastElement\[i-1\]$, then $elem1 = previous\[i-1, elem0\]$, then $elem2 = previous\[i-2, elem1\]$ and so on until you have your i elements.

Let's make a small example with $(a\[i\], t\[i\]) = \[(0, 60), (10, 30), (50, 20)\]$, $d=60$ :

* $T\_0 = \[0, +\infty, +\infty, +\infty\]$ =\> initialization
* $T\_1 = \[0, 60, +\infty, +\infty\]$ =\> one job may be achieved at time=60
* $T\_2 = \[0, 40, +\infty, +\infty\]$ =\> up to now only one job may be selected, but job (10, 30) took the place of (0, 60) as it can be achieved sooner.
* $T\_3 = \[0, 40, 70, +\infty\]$ =\> optimal solution selects 2 jobs.

At the end, $lastElements = \[1, 2, -1\]$ (starting job indexing at 0) and $previous = \[\[-1, -1, -1\] \[-1, -1, 1\] \[-1, -1, -1\]\]$. This let you track the optimal selection $\\{1, 2\\}$.
> 1 votes

---
Tags: algorithms, scheduling
---


# Question
Title: If well-founded induction holds, then the relation $\to$ on a reduction system terminates
I am trying to understand a proof from "Term Rewriting and All That" by Baader and Nipkow.

Well-founded induction (WFI) is the following statement:

> $\forall x \in A(\forall y \in A(x \stackrel{+}{\to}y \Rightarrow P(y))\Rightarrow P(x)) \Longrightarrow \forall x\in A (P(x))$

Here is the proof I cannot understand.

> Theorem: If well-founded induction holds, then the relation $\to$ on a reduction system terminates.
>
> Proof: by WFI, where $P(x):=$ "there exist no infinite chain starting from $x$". The induction step is simple: If there exist no infinite chains starting from any successor of $x$, then there exist no infinite chains starting from $x$. Hence, the premise of WFI holds, and we can conclude that $P(x)$ holds for all $x$ i.e., $\to$ terminates.

Why can we define $P(x)$ to be "there exist no infinite chain starting from $x$"?

# Answer
Well-founded induction, like all other forms of induction, holds for *any* predicate $P$. That can mean two different things:

1. Well-founded induction holds for every predicate which you can express in your formal system.
2. Well-founded induction holds for every subset $P \subseteq A$.

Either way, informally speaking you can define $P$ to be whatever you want.

Formally speaking, you might run into set-theoretic issues, those that separate naive (or elementary) set theory from axiomatic set theory. But presumably this is not the focus of the book, so you can just ignore such issues.

(The gap is that in case 1, you need to show how to express $P$, and in case 2, you need to show that the set $\\{x \in A : \text{there exists no infinite chain starting at $x$}\\}$ exists.)
> 1 votes

---
Tags: reductions, term-rewriting
---


# Question
Title: If an array is full of the same integer, like 0s or 1s, are they all the peak of the array?
I am learning the MIT course Introduction to Algorithms.

The professor is saying

> In particular, as an example, position 2 is a peak if, and only if, b greater than or equal to a, and b greater than or equal to c. So it's really a very local property corresponding to a peak.

My question is, if an array if full of the same integer, like 0s, or 1s, are they all the peak of the array?

# Answer
> 4 votes
This is something you will encounter over and over, not just in science but also in engineering, in law, in programming, and generally in jargon. If there is a definition for a term, then that term means exactly what the definition says it means. No more. No less.

In particular, you may have an intuitive notion of what the term means *in English*, but this is *not* English. This is technical jargon. A "peak" doesn't mean what you think it means, it doesn't mean what it means in English, it means *exactly* what its definition says it means.

So, depending on the definition, all elements could be the peak, or there could be no peak, or any element could be the peak, or maybe it could even be the case that the question doesn't even make sense because there is some precondition to the definition of "peak" that doesn't apply in this case.

Look at the definition. Apply it. Ignore any intuition about what you think the answer should be. Trust the result.

---
Tags: data-structures, terminology, arrays
---


# Question
Title: How does casting really work for primitive data types?
I have written the following C code which purpose it is to flip an **unsigned** number in binary representation and give back an **unsigned** number:

```
long flippingBits(long n) {
    return (unsigned)(~n);
}

int main(){
    long a = flippingBits(someNumber);
    ...
}

```

This code does work fine. What about this code?

```
unsigned long flippingBits(long n) {
    return (~n);
}

int main(){
    unsigned long a = flippingBits(someNumber);
    ...
}

```

This code indeed prints out negative numbers. WTF. This is beyond my intuition. So is there an (architectural) way, to explain this phenomenon? How does the casting of primitive data types work?

# Answer
> 2 votes
Casting of primitive datatypes works in a very simple way:

> Under the hood, values don't have types. Casting does absolutely nothing.

As a simple example, let us consider casting 65 to an ASCII character, thus obtaining the symbol `A`. What happens under the hood? Absolutely nothing. The only thing that changes is how the *program* treats the value. When it thinks of it as an integer, it sees 65; when it thinks of it as an ASCII character it sees `A`.

The CPU does accommodate different datatypes when performing various operations. For example, it has separate instructions for signed and unsigned integer arithmetic, and for floating point arithmetic. Moreover, there are different instruction for different lengths (i.e. 16-bit vs. 32-bit vs. 64-bit for integers). But it is up to the programmer to instruct the CPU which instruction to use. The CPU doesn't keep track of datatypes, which are a higher-level concept.

Modern CPUs do keep a distinction between *code* and *data* to some extent, for security purposes. But otherwise the semantics of data is up to the programmer.

Sometimes casting *does* have an actual effect, and this is during *promotion*. When casting an integer to a floating point number, or a 32-bit integer to a 64-bit integer, the program calls some instruction which effects this conversion (in the second case, the exact instruction depends on whether the integer is signed or unsigned).

When casting a signed integer to an unsigned integer of the same length (or vice versa), probably nothing happens. This is exactly your case.

# Answer
> 1 votes
> How does the casting of primitive datatypes works?

The restriction "primitive datatype" is not enough:

Casting from a 16-bit integer to a 32-bit integer works differently than casting between integer types of the same size. And casting between integer and floating-point types is even more complex.

> This Code does work fine. What about this code?

Both code examples will work differently on different CPUs, operating systems and possibly using different compilers.

This is because under some operating systems (e.g. 32-bit Windows) `long` and `unsigned` data types have the same number of bits; under other operating systems (e.g. 64-bit Windows) `long` has twice as many bits as `unsigned`.

And you use the `~` operator `(~n)` on a signed data type which *may* cause different results depending on the compiler you use.

> This code indeed prints out negative numbers.
>
> So is there an (architectural) way, to explain this phenomenon?

There are two effects:

The **first effect** is:

If you pass a value of a wrong data type to some function, C will automatically cast the value.

And if you are casting a value that is outside the range of the data type you are casting to, the result will typically not be what you are intuitively expecting.

In the case of two integer data types, normally the "rightmost" bits of the value are copied to the new value.

Let's take `(signed char)3478` as an example:

The number 3478 is written as `110110010110` in binary. `signed char` is an 8 bit data type. The rightmost 8 bits of `1101 10010110` are `10010110`. And the value (-106) is stored as `10010110` in a `signed char` variable.

Therefore `(signed char)3478` will result in (-106).

The value `a` is stored in an `unsigned long` variable which means that it **cannot** be negative!

However, you say that you "print out" the value of `a`. This means you pass the value to some function that prints it to the screen.

Obviously that function expects some signed data type. C will cast the value stored in `a` to the signed data type and as in the example with the number 3478, the result of casting may be a negative number.

If you use `printf` you may see a **second effect**:

If some function (such as `printf`) has a variable number of parameters, the way the parameters are passed to the function is depending on the data types passed. (The details may also vary from OS to OS.)

You may now pass the wrong data type to the function; for example you use `"%d"` (`signed int`) in the `printf` format string but you pass an `unsigned long`.

If you do this, the compiler will write the value of `a` to some data storage (memory or register) which is suitable for `unsigned long` values before actually calling the function. (For such functions the compiler is not able to find out which data type is really expected by the function, so it has to assume that the function expects the data type you are passing to the function.)

However, `printf` will look for a value in some data storage suitable for `signed int` values which *might* be located somewhere completely different. That data storage does not contain any useful value because the compiler wrote the value of `a` somewhere else!

---
Tags: c
---


# Question
Title: Doubt in vertex connectivity less than edge connectivity
Sir i recently started graph theory. I understood the reason why edge connectivity is less than min degree(remove all vertices incident to min degree vertex). I have doubt in 2nd part of proof when given graph is not complete graph. how to prove here vertex connectivity less than edge connectivity? confused here. Pls clarify my doubt

# Answer
> 1 votes
I'm not sure I understand your question, so this is the specific question I'm answering:

> Why is the vertex connectivity of a graph always less than or equal to its edge connectivity?

If that's wrong, please let me know in the comments or edit the question.

---

The vertex connectivity of a graph is defined as *the smallest number of vertices you can delete to make the graph no longer connected*. The edge connectivity is the same, except substitute "edge" for "vertex".

So, let's take a graph $G$, and say its edge connectivity is $e\_c$. This means, by definition, there's some set of edges $E\_c$, such that deleting all those edges will make $G$ no longer connected, and $|E\_c| = e\_c$ (there are $e\_c$ different edges in the set).

Let's assume that the vertex connectivity is greater than $e\_c$. I'm going to show that this leads to a contradiction.

Let's go through $E\_c$ and take one arbitrary endpoint from each edge. (At random, or always take the tail, etc, doesn't matter.) Call this new set of endpoints $V\_{Ec}$. There's one for each edge, so there are $e\_c$ total.

Deleting a vertex includes deleting every edge that touches it, so deleting every vertex in $V\_{Ec}$ must delete every edge in $E\_c$. Thus, deleting every vertex in $V\_{Ec}$ makes the graph disconnected.

But we only deleted $e\_c$ different vertices! If the vertex connectivity is any larger than $e\_c$, we have a contradiction—since the vertex connectivity is the *smallest* number of vertices you can delete to disconnect the graph. And we just showed you can do it with fewer.

Therefore, the vertex connectivity can never be larger than the edge connectivity.

---
Tags: graphs
---


title: 2-SAT reduction to Easy Puzzle Solving

text:
# Question
Title: 2-SAT reduction to Easy Puzzle Solving
## Introduction

I've been developing interest in complexity classes and thought I was unable to prove my problem is *NP hard*, so I wanted to see if it was *P-hard*. I wanted to see if my puzzle solving is special. *I have linked a previous question of mine to help clarify what is mentioned below.* Explained here

## Random Instance of 2-SAT used for attempt reduction

> I took an instance of my problem X
>
> *Let's say my problem X is determining if a puzzle is valid for my language*
>
> (a∨¬b)∧(¬a∨b)∧(¬a∨¬b)∧(a∨¬c)
>
> *Instance of X*
>
> a = shift(L) puzzle
>
> ¬ a = invalid puzzle
>
> ¬b = invalid puzzle
>
> b = shift(L) puzzle

---

## Reduction into Shorter Instance

> (a∨¬b)∧(¬a∨b)

*This boolean expression is only checking for 2-sat. Being True (valid puzzle) or False (invalid puzzle).*

My idea is that a deterministic machine will consider *n^2 x n^2* puzzles as invalid if the lower right-hand box is not filled. My puzzles are solved in quadratic time when provided a puzzle with this *n x n* box. Any other puzzle will simply fail to be solved if it does not follow my language. *I have used an algorithm that can determine in poly-time that those failed puzzles are invalid puzzles.* Because, the solver will not know it as an invalid puzzle. So it will try to map it out in my language thus giving an invalid puzzle.

## Question

I have the algorithm and proven that it works in poly-time, the problem is that *I only know how to prove it by showing the algorithm*. I just don't know how to write it out mathematically. How would I properly do this?

# Answer
> 4 votes
I'm going to need to question your premise here.

I have no doubt that you can poly-time reduce `2SAT` to your custom problem. But you can poly-time reduce `2SAT` to pretty much *anything*. The idea of "P-hardness" under poly-time reduction isn't really a useful one.

For example, let's take the following problem:

> `IS-IT-ONE`: given a single bit, is that bit a 1?

This problem is "P-hard" under poly-time reduction. For example, I can reduce `2SAT` to it:

> **Reduction from `2SAT` to `IS-IT-ONE`**
>
> * Solve `2SAT` the usual way
> * If the problem is satisfiable, let $B$ be 1
> * If the problem is unsatisfiable, let $B$ be 0
> * Run `IS-IT-ONE` on $B$ and return the result

This reduction runs in poly-time, *because solving `2SAT` can be done in poly-time*.

In other words:

***Every problem in P can be poly-time reduced to any other non-trivial problem.***

(Only two languages are considered "trivial" for this purpose: "return true" and "return false", aka $\Sigma^\*$ and $\varnothing$.)

If you're interested in classes smaller than P, great! There are several of them, such as L: the set of problems that can be solved using a logarithmic amount of memory. It may or may not be the same as P—that's an open problem.

But if you want to talk about P versus L or NL or anything else within P, you can't use poly-time reductions any more. When talking about L, for example, you'll usually want a *log-space reduction*, using a Turing machine with writable tape bounded by the log of the input size. These aren't as famous as poly-time reductions, but they're still quite important in complexity theory.

---
Tags: complexity-theory, sudoku
---


# Question
Title: What is the difference between A-normalization and K-normalization in compilers?
Administrative normal form is a program intermediate representation in which each immediate instruction has a name. It is used in GHC and OCaml.

K-normalized form is an intermediate representation in which each instruction consists of one assignment and operation. It's used in MLKit, Min-Caml, and GoCaml.

Both A-normalization and K-normalization involve generating a let expression with a continuation.

A-normalization and K-normalization seem to be exactly the same transformation. What is the difference between them such that they deserve different names?

# Answer
As far as my search-foo led me; *K-Normal Form* is inspired by *A-Normal Form*, but instrumented for use in *Storage Mode Analysis*, which is a static program analysis used for inferring memory mangement directives for functional programs.

The term seems to originate from the following publication: *L. Birkedal, M. Tofte, and M. Vejlstrup.* **From region inference to von Neumann machines via region representation inference.**

A copy of the publication can at the time of writing be obtained from *L.Birkedal's* faculty webpage under *publications*.
> 3 votes

---
Tags: programming-languages, compilers
---


# Question
Title: MSO (Monadic second-order logic) Logic On Words
Let L be a language over $\Sigma = \\{a,b,c\\}$ that contains all words, where the length $|w|\_b$ (number of all b's) has remainder 1 if divided by 3.

MSO logic over words are definded as follow:

I want to express this language using MSO logic. But my problem is how can I count the b's to calculate the reminder? So it would be easiert if I just look on $|w|$, cause I could use max.

# Answer
Start with the following: There are three disjoint sets $X\_1,X\_2,X\_0$ that together hold the $b$-positions of the string. The last $b$ is in set $X\_1$,
> 0 votes

---
Tags: automata, logic, first-order-logic
---


# Question
Title: Why does everyone say that NFA guesses it's next state?
In the picture above e is an empty string, and a is a symbol from an alphabet. Every book or professor I have heard from, says than when we make transitions in the NFA, the NFA must **guess** which state to go to next. In the example above, the NFA must guess whether it should go left or right.

Why do they use the word **guess**? I have written a simple regular expression engine once and used dfs to go both right then left, if the right path didn't lead to a final state.

# Answer
> 5 votes
There are many equivalent ways to describe the operation of an NFA. One is using guesses. If you don’t like it, I suggest not using it.

Guesses come up very naturally in the *union* construction. Suppose we are given NFAs for two languages $A,B$. We create a new NFA with a new initial state which points to the initial states of the NFAs for $A,B$, with $\epsilon$-transitions. When considering the semantics of the new NFA, it is natural to think of the NFA as first “guessing” which of the two $\epsilon$-transitions to take initially — this amounts to guessing whether the input belongs to $A$ or to $B$.

An NFA accepts a given input word if it can work its way from the initial state to an accepting state, following the input symbols and using $\epsilon$-transitions at will. Tracing the operation of the NFA, at a given point there might be many possible transitions to take, and the NFA has to choose one of them. If the input belongs to the language of the NFA, then there must exist a set of correct choices which leads the NFA to an accepting state. We refer to the process in which the NFA chooses an accepting path by the name *guessing*. This is a metaphor which many people find helpful, but if you don’t, feel free not to use it.

# Answer
> 1 votes
Consider the NFA in your picture, which finds all the strings which are repeats of "a" which are a multiple of two or three long. The left branch is for multiples of three, the right for multiples of two. It should be clear how these $\epsilon$-transitions can be used to "join" together those two smaller automata to build this expression.

Now say you are running the algorithm, and you have received a certain number of a's. You don't know at this point which branch you "should" be in. The two sides cannot be somehow "merged" as we don't allow mixtures of pairs and triples: it needs to recognise either "all pairs" or "all triples" and at the start we don't know: it's undetermined, hence non-deterministic finite automaton.

There are many ways to implement non-determinism and it's not really important in the description of NFAs which you choose, so it's not specified. The NFA description is more abstract than that.

* The most convenient for theoretical construction is the "perfect guesser", the lucky dude. If you can manage to put aside the idea that this is not directly implementable, this carries the least baggage and complexity into the discussion, except discussion about implementation (for example, discussion about construction).
* Another way to look at it is the *possibility* of acceptance. Imagine that the accept state executes some terrible deed (sets off a bomb, or something), and the implementation follows any epsilon transitions just randomly. You've been asked as a safety expert whether it's *possible* that the deed would be performed for a given string. You have to assume the "worst case" to do this. There's no "magic" involved in this analogy, so you might prefer this approach.
* One *slightly* practical means of implementing an NFA is to allow parallel execution. At each branch point *both* are considered by different threads (etc). At the end the threads are collected and the algorithm looks to see if any are successful.
* Another, more practical means is by back-tracking decisions you've made to choice points. This is the same thing as exploring a search-space by depth-first search. This seems to be what you implemented.
* It's also possible to just "put a counter" on every state you might be in at any point in time as you go through a string (when there's an $\epsilon$-transition new counters go on all states at the other end of it). At each step move on all the counters and see if any counter ends up in the accept state at the end.
* It's possible to extend this approach to build a DFA, without all this $\epsilon$ annoyingness. A downside to doing that is that the DFA could be vastly bigger than the NFA; the upside is that it rarely is and sometimes is smaller. (There are other practical downsides to the DFA route, too). This algorithm is called the powerset construction.

Given all this complexity, when you're talking about (say) building an NFA from a regular expression, it's usually best just to ignore these details and just assume luck (good or bad).

In my experience, people who are more anxious and pessimistic (seemingly, an increasing proportion) often have a distracting emotional reaction to the idea of the "lucky guy" interpretation, and I've found that it's often best to go with the "possibility of doom" (safety guy) explanation when first introducing it.

---
Tags: finite-automata, terminology
---


title: High Level Assemblers vs Compilers?

text:
# Question
Title: High Level Assemblers vs Compilers?
I'm reading the *"Art of Assembly"* 2nd Edition by Randall Hyde. In the book the author seems uses his own language called High Level Assembly (HLA). Coming from a C Background, I question how useful this is in learning (real x86/NASM for use on Linux) Assembly. But, looking it up there seems to be a term "High Level Assembler" (wikipedia) that gives some credibility to calling HLA "Assembly".

HLA provides ENUMs; bounds checking; multi-dimensional arrays; constant, static, and readonly variables; operators; a standard library; some error-catching; alignment and a lot of other stuff.

Where is the line drawn between an Assembler and a Compiler. From the book, it seems there is even some addressing modes not supported by HLA,

> Actually, the 80x86 does support addressing modes involving certain 16-bit registers, as mentioned earlier. However, HLA does not support these modes and they are not useful under 32-bit operating systems.

If it is a compiler, then does it "compile" the Assembly, or "assemble" the Assembly? Or is "High Level Assembly" just a procedural programming language that has little to do with Assembly?

# Answer
> 1 votes
The verb *assemble* and the noun *Assembler* is useful when it's important to point out that the program generates machine code with a 1:1 correspondence to the atomic instructions of the (Assembly) language.

But only a few simple directives (e.g. macros) need be added to the Assembler to reach something that gives more readable and compact code that can be, for all intents and purposes, considered high level.

If this was all that was added, you supply the actual macros, e.g. FUNC, CALL, STRUCT, etc. yourself, and can build your own language.

These macros are not the atomic Assembly Language instructions; nor are the directives built into the Assembler that lets you create them. Neither the macros you write, nor the directives are part of the agreed-upon Assembly syntax for the CPU.

For most intents and purposes, *Compiler* can be substituted for *Assembler*, and it's clear that you mean the program that generates an exe from text (or a tool). Perhaps some distinction could be useful when you mean language-specific such programs that can't parse Assembly, but there are ones that can do both.

---
Tags: terminology, compilers
---


# Question
Title: Orthogonal range reporting with fixed upper rectangular corner
Consider the following special case of orthogonal range searching:

Given a set $S$ of $n$ points in $d$ dimensions, and rectangular queries with a fixed "upper-left" rectangle corner $(0,0,...0)$, report the total number of points inside the rectangle.

This is different in that all rectangles queried have a fixed corner. In this case, will we have a dynamic algorithm with a better runtime, or is the problem still as hard as general orthogonal range searching?

# Answer
> 1 votes
The count of any rectangle $C(U, L, D, R)$ can be obtained combining the counts of 4 fixed "upper-left" retangles:

$C(U, L, D, R) = C(0, 0, D, R) - C(0, 0, U, R) - C(U, 0, D, L) + C(0, 0, U, L)$,

noting $C(up, left, down, right)$ the count in the rectangle delimited by $(up, left, down, right)$.

Thus, you cannot expect more than a factor 4 runtime improvement.

---
Tags: algorithms, data-structures, computational-geometry
---


# Question
Title: How to approach analysis of randomized algorithm
Let us suppose we have a sequence of values $C(i)$ that represent some counter for a given $i$ for $i \in \lbrace 1, \cdots, n \rbrace$. Let us assume some uniform distribution $U$ where selecting any integer between $1$ and $n$ has equal probability. A simple process using this information is to loop for some fixed number of iterations $M$ that, for ease, is a multiple of $n$, and do the following:

1. Randomly obtain some constant $k \leq n$ number of integers from $U$ and place them into a set $V$
2. For $i^\* = \arg \min V$, do update $C(i^\*) \leftarrow C(i^\*) + 1$

Ultimately, I want to be able to investigate the quantity $P\left( | C(i) - \frac{1}{n}\sum\_{j=1}^n C(j) | \leq \epsilon \right)$ for any $i$. The question I have is if this simple algorithm allows, in probability, for the values of $C(i)$ to remain close to their average values regardless of how many iterations we do. This probability is obviously of a form where one could take advantage of say Hoeffding's inequality but I am not quite sure how to make use of the algorithm structure to get to that point.

I am not very well versed in randomized algorithms and so any insight into how to approach the analysis of such a simple algorithm would be insightful.

# Answer
Let $P$ be the distribution of $i^\*$, which you can calculate explicitly: $$ \begin{align\*} p\_i := \Pr\[P=i\] &= \left(1-\frac{i-1}{n}\right)^k - \left(1-\frac{i}{n}\right)^k. \end{align\*} $$ This is the probability that all samples are at least $i$ minus the probability that they are all at least $i+1$.

The counter $C(i)$ has binomial distribution $\mathrm{Bin}(M,p\_i)$, which will be concentrated around $Mp\_i$. In contrast, $\frac{1}{n} \sum\_{j=1}^n C(j) = \frac{M}{n}$. Therefore you can only expect $C(i)$ to be close to $\frac{1}{n} \sum\_{j=1}^n C(j)$ if $p\_i \approx \frac{1}{n}$. Even when $p\_i \approx \frac{1}{n}$, the concentration of $C(i)$ is not so good – the standard deviation is $\sqrt{Mp\_i(1-p\_i)} \approx \sqrt{M/n}$, so the probability that $C(i)$ is very close to $M/n$ is probably quite small.
> 3 votes

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


title: Two questions on MSO

text:
# Question
Title: Two questions on MSO
**First question :**

Is the following formula a valid MSO formula?

$\theta(S, r) = \exists (e\_1, t\_1), ... ,(e\_h, t\_h) \bigwedge\limits\_{(e\_i, e\_j) \in \rho(S,r)} \mathcal{R}((e\_i, t\_i), (e\_j, t\_j))$

So my main concern here is the fact one states there exists $e\_1, t\_1$ *etc.* but then goes on to not use these in the actual formula (only using $e\_i$ and $e\_j$). Is this correct?

**Second question :**

While browsing around, I found the following :

(found in this post : MSO (Monadic second-order logic) Logic On Words)

My question here is, in MSO, how come one can still use 2-ary relations, such as $S(x,y)$ (as well as $\mathcal{R}((e\_i, t\_i), (e\_j, t\_j))$ from the first question), since I thought MSO is supposed to use only 1-ary relations, *i.e.* sets?

I think I might have found the answer myself, but I would like to verify : is this allowed because one does not *quantify* over these 2-ary relations?

# Answer
> 3 votes
You are asking two questions. The first question is about logic more generally. You are wondering whether a statement of the form $$ \exists x \\, \mathrm{True} $$ is valid, although $\mathrm{True}$ doesn't mention $x$. There is absolutely no requirement in the syntax of logical formulas that you use all the variables you quantify over. This similar to functions which don't depend on all of their arguments. Do you object to the function $f(x) = 1$?

As for your second question, *monadic* refers to the fact that you are only allowed to quantify over *unary* predicates. The language itself can freely contain $k$-ary predicates for any $k$. Compare this to first-order logic, in which you are not allowed to quantify over *any* predicates. Would that mean that first-order logic only allows for 0-ary predicates?

---
Tags: logic
---


# Question
Title: Suggest a Data Structure To Manage 2 Sets
I was given the following problem which really baffled me, and I would like some guidance in solving it.

I want to make a data-structure which represents two sets $A,B\subseteq \mathbb{R}$, so that I can Insert an element to a set of my choosing in $O(\log n)$ (where $n$ is the number of elements existing in both sets).

However, it is also required to be able to find in $O(1)$ some $x \in A\cup B$ such that the amount of elements in $A$ lesser than $x$, equates to the number of elements in $B$ greater than $x$, if exists:

$$\left | \left \\{ y\in A: y\<x \right \\} \right | = \left | \left \\{ y\in B: y\>x \right \\} \right |$$

Now the obvious direction is to use balanced trees (say AVL). I can use the same tree for both sets or separate to 2 different trees. I also presume I should store more data in the nodes, However I'm not sure which. I thought about storing the number of elements smaller and greater but that would make the Insert method $O(n)$, since I have to update many nodes in the respective tree.

# Answer
> 1 votes
You are on the right approach to attach "more data" to a balanced search tree.

For all $x\in A\cup B$, let $$d(x)=\left | \left \\{ y\in A: y\<x \right \\} \right | - \left | \left \\{ y\in B: y\>x \right \\} \right |,$$ which is an **increasing** function on $x$.

---

For simplicity, let us assume all elements are distinct first. We can use a balanced search tree $T$ to store all elements in $A$ and $B$, keeping track of whether each element comes from $A$ or $B$.

* We will also store $(x\_\ell, \delta\_\ell)$ , where $x\_\ell$ is the largest element $x$ in $T$ such that $d(x)\le0$ and where $\delta\_\ell=d(x\_\ell)$.
* We will also store $(x\_r, \delta\_r)$ , where $x\_r$ is the smallest element $x$ in $T$ such that $d(x)\ge0$ and where $\delta\_r=d(x\_r)$.

Either pair might not exist. However, at least one pair must be available, which is enough to identify the wanted $x\in A\cup B$, i.e., $d(x)=0$, if exists.

---

Suppose $v$ will be inserted into $T$. Here is a sketch of what to do to maintain the data structure. The idea is simply to move $x\_\ell$ or $x\_r$ to its neighbor one or two times. Several obvious boundary cases such as when $d(x)\>0$ for all $x$ in $T$ before or after $v$ is inserted have been skipped.

1. Insert $v$.
2. Update $(x\_\ell, \delta\_\ell)$ as the following.

1. Do the following.
        * find $x\_{-1}$, the predecessor of $x\_\ell$. Compute $d(x\_{-1})$.
        * find $x\_{-2}$, the predecessor of $x\_{-1}$. Compute $d(x\_{-2})$.
        * find $x\_{1}$, the successor of $x\_\ell$. Compute $d(x\_1)$.
        * find $x\_{2}$, the successor of $x\_1$. Compute $d(x\_2)$.
    2. Let $x\_{\text{new}}$ be the largest element $x$ among $x\_{-2}, x\_{-1}, x\_\ell, x\_{1}, x\_{2}$ such that $d(x)\le0$. Update $(x\_\ell, \delta\_\ell)$ to $(x\_{\text{new}}, d(x\_{\text{new}}))$
3. Update $(x\_r, \delta\_r)$ similarly, which should take $O(\log n)$ time as well.

Any kind of balanced search trees can be used as long as the insertion, finding the predecessor and finding the successor can be done in $O(\log n)$. In particular, we can use AVL tree or red-black tree.

* Step 1 takes $O(\log n)$ time.
* Each search for predecessor or successor in Step 2 takes $O(\log n)$ time. Each computation of $d(\*)$ takes $O(1)$ time, as we know $d(x\_\ell)$. For example, $d(x\_{-1})=d(x\_\ell)-\lambda\_A(x\_{-1})-\lambda\_B(x\_\ell)$, where $\lambda\_A(x\_{-1})$ is 1 if $x\_{-1}\in A$ and 0 otherwise. $\lambda\_B(x\_{\ell})$ is 1 if $x\_{\ell}\in B$ and 0 otherwise. Similarly, $d(x\_1)=d(x\_\ell)+\lambda\_A(x\_\ell)+\lambda\_B(x\_1)$. So step 2 takes $O(\log n)$ tims.
* Similarly, step 3 takes $O(\log n)$ time.

---

When there are duplicated elements in $A$ and $B$, the idea is similar but somewhat more complicated. A balanced search tree $T$ will store all distinct elements in $A$ and $B$. Each node will store

* a distinct element $x\in A\cup B$,
* how many time that element appears in $A$,
* and how many time that element appears in $B$.

The order of the node is determined by the order of that element. Attached to the whole $T$ are the two pairs $(x\_\ell, \delta\_\ell)$ and $(x\_r, \delta\_r)$ defined the same as above.

---

**Exercise 1.** Refine the algorithm so that at any point of time, only one of the pairs $(x\_\ell, \delta\_\ell)$ and $(x\_r, \delta\_r)$ is maintained.

**Exercise 2.** Refine the algorithm so that only 1 or 2 cases in step 2.1 are needed by considering $v\<x\_\ell$ or not, $v=x\_{-1}$ or not, $v\in A$ or $v\in B$, etc.

**Exercise 3.** Consider using one balanced search tree for elements in $A$ and another one for elements in $B$ instead of using one for both of them. Will it work?

---
Tags: data-structures, trees, sets
---


title: Construct a grammar for the language

text:
# Question
Title: Construct a grammar for the language
How can I achieve this. Write a grammar for the language consisting of strings built only of the letters a and b. The strings may have any number of these letters, but the letter combinations bab must be in each string somewhere, and each string must start with a bb. For example, the strings bbababbbaa, bbbaaaababaa, and bbbab are in the language, while a, aabb, baaa, and bbba are not.

# Answer
1. The string much start with $ bb $ .
2. There should at least one occurrence of the sub-string $ bab $

Hence, the structure of the regular expression must be something like this: $$ bb\[some \\: string\]bab\[some \\: string\] $$

and, we can define $ \[some \\: string\] $ something like this:

$$ (a + b)^\* $$

which means, there can be any number (including 0) of either a's or b's. Therefore, the final regex for the word is, $$ bb(a+b)^\*bab(a+b)^\* $$
> -1 votes

---
Tags: formal-grammars, programming-languages
---


title: Is there purely recursive functions?

text:
# Question
Title: Is there purely recursive functions?
Is there any problem that can be only solved with recursion, and not with iteration? (haven't been able to find anything online).

If there isn't any, is there a reason why?

Thanks in advance!

# Answer
> 4 votes
The Böhm–Jacopini theorem states that everything can be implemented using just IFs and WHILEs. Indeed, your CPU essentially implements an infinite WHILE loop with conditional execution.

Recursion can be simulated iteratively using a stack; this is how recursion is implemented under the hood. Conversely, the same construction as in the theorem shows that everything can be implemented using only tail recursion (which is essentially a WHILE loop). So iteration and recursion are equivalent.

---
Tags: recursion
---


# Question
Title: In instructions pipelining, why does register read/write take up only half clock cycle?
While studying instruction pipelining in MIPS processor, we make an assumption that registers read/write stages take only a half clock cycle, as this picture shows (half clock cycles are dotted in register operations):

So what is the purpose of this assumption? and why is the fourth instruction in this graph is considered a hazard if we actually wrote the value of $2 in the first half clock cycle and then read it in the latter one?

# Answer
By using different phases of a clock cycle for register write and register read, the number of register file ports can be reduced. (This can reduce area and latency.) A two-read and one-write instruction would otherwise require three register file ports (or introduce a structural hazard); by using different phases of the cycle one port can be used for both read and write. This can also facilitate reading from the register file in the same cycle as the value is written, which reduces the number of results that must be managed through the forwarding network.

The fourth instruction (add $14, $2, $2) does not have a data hazard even without forwarding.
> 1 votes

---
Tags: cpu-pipelines, mips
---


# Question
Title: Functional data structure fast to add and unorded deletion
I am looking for a functional data structure that would work in this role.

Adding items to the struct happens often. Removing items from the struct happens as often as adding them but I have no way of knowing what order the deletion happens in. Over the long term addions will equal removal Rarely I need all items currently in the struct

I thought of using a queue but out of order removal from a queue is expensive.

# Answer
My recommendation is a straightforward hash map. If you have a good hash function for your distribution of keys, the time complexity for adding and removing (with an arbitrary key) is amortized $O(1)$.

EDIT: Hash maps can be purely functional if you want (example), they just become a whole lot less efficient. I don't think it's theoretically possible to get lower than $O(\log n)$, which is what you get from using a red-black tree as the backend. The linked HAMT implementation is also $O(\log n)$, just with a significantly smaller hidden constant.
> 2 votes

---
Tags: data-structures, functional-programming
---


title: Why anyone learn compiler?

text:
# Question
Title: Why anyone learn compiler?
I am learning compiler in my Uni. I have been through all major compiler techniques like top-down parsing, bottom-up parsing, Lexical analyzer, Symbol table, etc. I have a good understanding of them, but I am still confused about the course.

What is the point of learning all these things? What are their applications? Where these applications are used? The main point is, if someone asks me, Why Compiler? What is the benefit of taking this course?

# Answer
> 10 votes
Let me break up several possible interpretations of your question:

**What is the purpose of learning compilation?**

There are several possible answers:

1. So that you know how to build a compiler should you have to. This is not a good answer nowadays.
2. Part of the goal of the computer science curriculum is to explain to you how a computer works, stopping at the hardware. This includes the operating system, file systems, the compiler, the network stack, and more.
3. As a programmer, you will be using compilers. Sometimes it will be useful to know what happens under the hood. For example, understanding garbage collection will help you choose which language to use in embedded applications.
4. Compilation is part of the standard curriculum, so you might get asked about it in interviews.

**Why are they teaching me compilation?**

Apart from the reasons listed above, there is an additional one: universities are very conservative. In the past it used to be more important to understand how compilers work. Nowadays this is less important, but change is slow, so material that made sense 10 years ago is still being taught today.

That said, some universities might *reform* their compilation curriculum, for example by de-emphasizing parsing, concentrating on more exciting aspects such as optimization, memory management, dynamic and static analysis, and the like.

**Why am I studying compilation?**

As an aspiring programmer, your university training contains lots of apparently useless classes, for example calculus. People choose to go to university for various reasons - it's a rite of passage, an opportunity for socialization and finding a partner, and it might help you get a job; or even just family or peer pressure.

Some people do away with university training, preferring other formal training, or even self-training. Some of these people are very successful. For whatever reason, you chose to attend university rather than any of these alternative routes. You should accept that university training is rather theoretical, and try to make the most out of it.

# Answer
> 7 votes
I have stumbled into this question ( and the whole CS site in general ), and I had never actually studied CS officially, but I will try to answer. ( not in order of importance )

**General :**

* I am not sure what country / terminology you are from but ( usually outside the US ) university is not a college and a college is not a university. While colleges aim at precise jobs education, university is a broader education that aims at more general understanding and horizons.
* On the same note, CS is more like Architecture rather than Building Engineering. Architects aim at a broader, "big-picture" education. Building engineering is more about Details in the realization or application of the design.

+ You can learn to pilot an aircraft without knowing the mechanics of how the aircraft works. But never a good pilot, let alone an excellent one. same goes for a F-1 driver ( or any driver / Equipment operator actually).
    + In long terms contributions to society and progress and technology, who will score more : the aircraft pilot / Formula-1 driver or the people who designed the aircraft / car ( engines, aerodynamics, technologies etc ? )
* Designing a compiler means designing / creating the **technology**. Using the language / programming / designing the software means creating the **application** of that technology。

**More Specific**

* How do you think new languages / technologies are designed and born ? with old compilers ?
* similar to above in one (important) word : **research**. this is where programming languages research is done. Not just a language that is the same in a new packaging. but a really new one.
* Compiler teaches you how real world applications are working and how to design them.
* Learning Compilers gives you with both theoretical and practical knowledge that is crucial in order to implement a programming language. It gives you a new level of understanding of a language in order to make better use of the language ( optimization is just one example ).
* Sometimes just using a compiler is not enough. You need to optimize the compiler itself for your application.
* There are certain things you can only do at compile time. see JIT as one example.
* Compilers have a general structure that can be applied in many other applications, from debuggers to simulators to 3D applications to a browser and even a cmd / shell.
* understanding compilers and how they work makes it super simple to understand all the rest. a bit like a deep understanding of math will help you to understand geometry or physics you can not do physics without the math. not on the same level.
* Just using something (read: tool, device, software, programming language) is usually enough when everything goes as expected. But if something goes wrong, only a true understanding of the inner workings and details will help to fix it.

**Even more specific** ( to your concern regarding hiring )

Compilers are super elaborated / sophisticated systems ( architecturally speaking ).If you will say that can or have written a compiler by yourself - there will be no doubt as to your capabilities as a programmer. There is **nothing you can not do** in the SW realm. Interview over.

Pick your answer.

P.s.

try to change the *"we"* in your title to *"anyone"*.

"Why would **anyone** learn compiler" ?

Does this question makes sense in a world that aims at progress ? ( even more - the High-tech world that supposed to lead that progress? )

If your question is aimed at yourself - e.g. why should ***you*** learn this subject - no one can really answer that but you. But you must agree that ***someone*** should..

.. and that ***someone*** will be from the ***cs*** field.

# Answer
> 4 votes
Because you are a **Computer Science** major and you have to deal with all these. A few months ago, I was also having the same question, while studying for the Computer Architecture finals, why am I even dealing with all these root level stuff, assembly code, optimizations while my friends from IT and Software development major learning new programming languages and frameworks which are going to help them in acing the software developer interviews.
Well, Computer Science deals with all that is involved between tiny logical gates to magical modern day software. While Software development is learning how to stay afloat in a vast ocean, Computer Science is advanced scuba diving. As you will go with the courses like, OS, Computer Architecture, Compilers, Theory of computation etc, everything will start making sense to you. I mean, EVERYTHING!

---
Tags: compilers
---


# Question
Title: Relationship between dependent sum type and dependent product type?
Since dependent sum type ($\sum\_{n\in \mathbb{N}} P(n) $) is interpreted as ($\exists n\in \mathbb{N}:P(n) $) and dependent product type ($\prod\_{n\in \mathbb{N}} P(n)$) is interpreted as ($\forall n\in \mathbb{N}:P(n)$), is it correct to say that an element of dependent product type represents a set(in a vague way) of elements of corresponding dependent sum type for every n?

# Answer
> 1 votes
I believe you meaning the following.

A value of type $\prod\_{n : \mathbb{N}} P(n)$ is a function which takes a value $n$ of type $\mathbb{N}$ as input and outputs a value of type $P(n)$. So the domain of such a function is $\mathbb{N}$. What is its codomain? Well, the type of the result depends on the value of the input, which is why it's called a *dependent* product. So it doesn't really have a codomain in the traditional sense.

But we can also view this situation as follows: Yes, such a function $f$ has a codomain, namely the dependent sum $\sum\_{m : \mathbb{N}} P(m)$; but with the condition imposed that $(\mathsf{fst} \circ f)(n) = n$ for all $n : \mathbb{N}$, where $\mathsf{fst} : \sum\_{m : \mathbb{N}} P(m) \to \mathbb{N}$ is the first projection.

More precisely, the following types are indeed equivalent ("equivalent" as in the HoTT book):

1. $\prod\_{n:\mathbb{N}} P(n)$
2. $\prod\_{f : (\mathbb{N} \to (\sum\_{m : \mathbb{N}} P(m)))} \prod\_{n:\mathbb{N}} ((\mathsf{fst} \circ f)(n) = n)$ (the type of functions satisfying the stated condition)

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


# Question
Title: How to find the number of intervals containing a point when given a static set of intervals?
I've seen similar questions around here but I'm trying to address this problem with a slight change and maybe it makes it easier to solve.

I'm given a set of intervals $\\{s\_1,s\_2,...,s\_n\\}$ where each interval has a starting point $b\_i$ and an ending point $r\_i$. Also, the set is not changing meaning no new intervals are inserted or removed, and no end/start points are identical.

I want to be able to return the number of intervals in $O(\log(n))$ time. I am aware of an interval tree however I actually don't have to worry about insertions and deletions so there might be something simpler.

Also, say I use an AVL tree where I use the start points as keys, and in each node I hold:

* start - the start point of the interval
* end - the end point of the interval
* max - the max end point of an interval that is contained in the tree initiated at this node

And I search like so:

Given a point $p$, I start at the root and go down based on the max value compared to the point. If $p$ is greater than the max of the node, I'm currently at I consider it's right sub-tree. If $p$ is smaller than max, I consider the right sub-tree until I hit null or I find an interval that contains the point(based on start and end points).

This algorithm can return an interval that contains $p$ in $O(\log(n))$ time, but what if I wanna return the number of all intervals that contain it?

I understand it can be done in $O(\log(n)+k)$ time, where $k$ is the number of intervals containing the point but can't see really how.

# Answer
It is a very strong assumption that the time it takes to preprocess is not a concern.

Assume each given interval contains both of its endpoints. Otherwise, the solution below can be adapted easily.

Sort all $b\_i$ and $r\_i$ into an increasing sequence $A=(a\_1, \cdots, a\_{2n})$. Let $c\_1=1$. For $i$ from 2 to $2n-1$, let $$c\_{i}=\begin{cases} c\_{i-1}+1&\text{ if } a\_{i}\text{ is a starting point of a given interval,}\\ c\_{i-1}-1&\text{ if } a\_{i}\text{ is an ending point of a given interval.} \end{cases}$$ $c\_i$ is the number of the given intervals that contain the open interval $(a\_i, a\_{i+1})$ for $1\le i\le 2n-1$. Let $C$ be the sequence $(c\_1, \cdots, c\_{2n-1})$. The combination of $A$ and $C$ is what we wanted from preprocessing.

Given any number $p$, if $p \gt a\_1$ and $p\lt a\_{2n}$, we can find the largest index $i$ such that $p\ge a\_{i}$ by binary search in $O(\log n)$ time. Then the number of given intervals that contain $p$ is given by $$\begin{cases} 0&\text{ if } p\<a\_1,\\ 1&\text{ if } p= a\_1,\\ c\_{i}&\text{ if } a\_i\<p\lt a\_{i+1}\text{ or } p=a\_i\text{ and } c\_i\>c\_{i-1},\\ c\_{i}+1&\text{ if } p=a\_i\text{ and } c\_i\<c\_{i-1},\\ 1&\text{ if } p=a\_{2n},\\ 0&\text{ if } p\>a\_{2n},\\ \end{cases}$$ In other words, we can get the answer in $O(\log n)$ time once $A$ and $C$ are known.
> 2 votes

---
Tags: balanced-search-trees, intervals
---


title: Is the IO monad technically incorrect?

text:
# Question
Title: Is the IO monad technically incorrect?
On the haskell wiki there is the following example of conditional usage of the IO monad (see here).

```
when :: Bool -> IO () -> IO ()
when condition action world =
    if condition
      then action world
      else ((), world)

```

Note that in this example, the definition of `IO a` is taken to be `RealWorld -> (a, RealWorld)` to make everything more understandable.

This snippet conditionally executes an action in the IO monad. Now, assuming that `condition` is `False`, the action `action` should never be executed. Using lazy semantics this would indeed be the case. However, it is noted here that Haskell is technically speaking non-strict. This means that the compiler is allowed to, for example, preemptively run `action world` on a different thread, and later throw away that computation when it discovers it doesn't need it. However, by that point the side-effects will already have happened.

Now, one might implement the IO monad in such a way that side-effects are only propagated when the whole program has finished, and we know exactly which side-effects should be executed. This is not the case, however, because it is possible to write infinite programs in Haskell, that clearly have intermediate side-effects.

Does this mean that the IO monad is technically wrong, or is there something else preventing this from happening?

# Answer
> 13 votes
This is a suggested "interpretation" of the `IO` monad. If you want to take this "interpretation" seriously, then you need to take "RealWorld" seriously. It's irrelevant whether `action world` gets speculatively evaluated or not, `action` doesn't have any side-effects, its effects, if any, are handled by returning a new state of the universe where those effects have occurred, e.g. a network packet has been sent. However, the result of the function is `((),world)` and therefore the new state of the universe is `world`. We don't use the new universe that we may have speculatively evaluated on the side. The state of the universe is `world`.

You probably have a hard time taking that seriously. There are many ways this is at best superficially paradoxical and nonsensical. Concurrency is especially either non-obvious or crazy with this perspective.

"Wait, wait," you say. "`RealWorld` is just a 'token'. It's not *actually* the state of the entire universe." Okay, then this "interpretation" explains nothing. Nevertheless, as an *implementation detail*, this is how GHC models `IO`.1 However, this means that we do have magical "functions" that actually do have side-effects and this model provides no guidance to their meaning. And, since these functions actually have side-effects, the concern you raise is completely on point. GHC *does* have to go out of its way to make sure `RealWorld` and these special functions are not optimized in ways that change the intended behavior of the program.

Personally (as is probably evident by now), I think this "world-passing" model of `IO` is just useless and confusing as a pedagogical tool. (Whether it's useful for implementation, I don't know. For GHC, I think it is more of a historical artifact.)

One alternative approach is to view `IO` as a describing requests with response handlers. There are several ways of doing this. Probably the most accessible is to use a free monad construction, specifically we can use:

```
data IO a = Return a | Request OSRequest (OSResponse -> IO a)

```

There are many ways to make this more sophisticated and have somewhat better properties, but this is already an improvement. It doesn't require deep philosophical assumptions about the nature of reality to understand. All it states is that `IO` is either a trivial program `Return` that does nothing but return a value, or it's a request to the operating system with a handler for the response. `OSRequest` can be something like:

```
data OSRequest = OpenFile FilePath | PutStr String | ...

```

Similarly, `OSResponse` might be something like:

```
data OSResponse = Errno Int | OpenSucceeded Handle | ...

```

(One of the improvements that can be made is to make things more type safe so that you know you won't get `OpenSucceeded` from a `PutStr` request.) This models `IO` as describing requests that get interpreted by some system (for the "real" `IO` monad this is the Haskell runtime itself), and then, perhaps, that system will call the handler we've provided with a response. This, of course, also doesn't give any indication of how a request like `PutStr "hello world"` should be handled, but it also doesn't pretend to. It makes explicit that this is being delegated to some other system. This model is also pretty accurate. *All* user programs in modern OSes need to make requests to the OS to do anything.

This model provides the right intuitions. For example, many beginners view things like the `<-` operator as "unwrapping" `IO`, or have (unfortunately reinforced) views that an `IO String`, say, is a "container" that "contains" `String`s (and then `<-` gets them out). This request-response view makes this perspective clearly wrong. There is no file handle inside of `OpenFile "foo" (\r -> ...)`. A common analogy to emphasize this is that there is no cake inside of a recipe for cake (or maybe "invoice" would be better in this case).

This model also works readily with concurrency. We can easily have a constructor for `OSRequest` like `Fork :: (OSResponse -> IO ()) -> OSRequest` and then the runtime can interleave the requests produced by this extra handler with the normal handler however it likes. With some cleverness you can use this (or related techniques) to actually model things like concurrency more directly rather than just saying "we make a request to the OS and things happen." This is how the `IOSpec` library works.

1 Hugs used a continuation-based implementation of `IO` which is roughly similar to what I describe albeit with opaque functions instead of an explicit data type. HBC also used a continuation-based implementation layered over the old request-response stream-based IO. NHC (and thus YHC) used thunks, i.e. roughly `IO a = () -> a` though the `()` was called `World`, but it isn't doing state-passing. JHC and UHC used basically the same approach as GHC.

---
Tags: programming-languages, functional-programming, haskell
---


# Question
Title: Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree?
Let $G$ be an undirected connected weighted graph, and let $T$ be a minimum spanning tree of $G$ with edge weights: $w\_1 \le w\_2 \le ... \le w\_{n-1}$.

Now let $T'$ be some other spanning tree of $G$ (doesn't have to be minimum) with edge weights: $w'\_1 \le w'\_2 \le ... \le w'\_{n-1}$.

I need to prove\disprove the following claim: for every $i$: $w\_i \le w'\_i$.

I've tried to find a counterexample, but I wasn't successful. So I'm quite sure the claim is correct. However, I had trouble to prove it formally.

I assume the contrary, which means there is an $i$ that satisfies $w'\_i \< w\_i$ and I take the first one that does. I tried adding it to the tree $T$ or trying to find a minimum spanning tree with this edge using Kruskal, but no luck.

# Answer
> 2 votes
Here are some hints:

1. Flesh out your counterexample with quantifiers properly: "There exists a graph $G$, and a minimum spanning tree $T$ for $G$ with edge weights $w\_1 \le w\_2 \le \dots \le w\_{n-1}$, and another spanning tree $T'$ of $G$ with edge weights $w'\_1 \le w'\_2 \le \dots \le w'\_{n-1}$, and an integer $i$ obeying $1 \le i \le n-1$, such that $w'\_i \< w\_i$". In a situation like this, from the set of all such counterexamples ($(G, T, T', i)$ tuples), you are free to choose one having minimum possible $i$, and it's nearly always useful (and never harmful) to do so.
2. "I tried adding it to the tree $T$" -- you must first show that it is not already in $T$. Here you can use minimality of $i$ for edges to the left, and the increasing weight order for edges to the right.
3. Let's add it to $T$, to make a graph I'll call $G\_2$. What noticeable feature does $G\_2$ contain?
4. What simple modifications could you make to that feature in $G\_2$ to turn it back into a tree? Hint: With this particular feature, there will always be at least 3 ways to do this, and there could be as many as $n$.
5. Can you choose an option in the previous step that will lead to a tree that is strictly lighter than $T$, and thus a contradiction (since we assumed $T$ to be minimal)?

# Answer
> 0 votes
Let us fix $G$ and $T$, a minimum spanning tree (MST) of $G$ as in the question. Assume weights of all edges are distinct; we will come back to the general case later.

Since all weights are distinct, there is one-to-one correspondence between edges and their weights.

Let $e\_i$ be the edge with weight $w\_i$ and $e\_i'$ be the edge with weight $w\_i'$. Let $T\_i$ be the graph with edges $\\{e\_1, \cdots, e\_i\\}$ for $i\le n-1$. The proof of Kruskal's algorithm in the case of $G$ proves, in fact, $G$ has a unique MST that will be found by Kruskal's algorithm, because all weights are distinct. Specifically, the case "Otherwise, $e$ is not in $T$" cannot happen.

**Minimality Lemma**. If an edge not in $T\_i$ can be added to $T\_i$ without creating a cycle, $e\_{i+1}$ must not weigh more than that edge.

Proof. Kruskal's algorithm tries adding the edge of the least weight among the available edges repeatedly, thus including $e\_1, e\_2, \cdots$ to form $T$ in that order. Let us inspect the moment when Kruskal's algorithm adds $e\_{i+1}$ to $T\_i$. If $e$ is an edge that weigh less than $e\_{i+1}$, it must have been tried to be added to $T\_k$ for some $k\le i$. Either $e$ was added to $T\_k\subseteq T\_i$ or a cycle was created at that time, which means adding it to $T\_i$ will create a cycle, too. Done.

For any graph $S$, let $p(S)=0$ if $e\_1\not\in S$; otherwise let $P(S)$ be the largest index $k$ such that the first $k$ lightest edges in $S$ is the same as the first $k$ lightest edges in $T$. WLOG, let $T'$ be a counterexample such that $p(T')$ is the largest (among all spanning trees of $G$). Let $q=p(T')$.

**Observation**: $w\_{q+1}\lt w'\_{q+1}$.
Proof. $\\{e\_1, e\_2\cdots, e\_q\\}\subseteq T'$. Consider $e\_{q+1}'$, the next heavier edge in $T'$. The Minimality Lemma tells that $e\_{q+1}$ does not weighs more than $e\_{q+1}'$. If it weighs the same as $e\_{q+1}'$, then it is $e\_{q+1}'$, which contradicts to our assumption of $q$ being the largest. So it must weigh less than $e\_{q+1}'$. Done.

Since $T'$ is a spanning tree, if we add $e\_{q+1}\not\in T'$ to $T'$, we must have created a cycle. Since we do not have a cycle in $T\_{q+1}$, there must be an edge $e'\not\in T\_q$ in that cycle. The above observation tells us $e\_{q+1}$ weighs less than $e'$.

Let $T''$ be $T'$ with $e'$ replaced by $e\_{q+1}$. Since $e'$ and $e\_{q+1}$ are on that same cycle, $T''$ is also a spanning tree. Since the only difference between $T'$ and $T''$ is one edge of $T'$ is replaced with an edge of smaller weight, $T''$ is also a counterexample. Since both the first $q+1$ lightest edges of $T''$ and that of $T$ are $\\{w\_1, w\_2\cdots, w\_q, w\_{q+1}\\}$, $p(T'')\ge q+1\>q$. This contradicts the assumption that $q$ is the largest. Done.

---

How about the general cases when all weights are not distinct?

For any $\epsilon\>0$ that is smaller than the minimum positive difference among the original weights, if we subtract $\epsilon/i$ weight from $e\_i$ and subtract $\epsilon/(2dn)$ weight from other edges using different positive integer $d$ for different edges, all new weights will be different and, since edges of $T$ are reduced more, $T$ remains to be an MST.

Letting $\epsilon$ go to 0 to take the limit of the inequalities that we have proved in the cases of distinct weights, we will obtain the same inequalities in the general cases.

---

Interested readers may enjoy the following exercise.

**Exercise**. Generalize MST $T$ to minimum-weighted sub-forest.

**Problem**. Can we prove the above generalization directly?

# Answer
> 0 votes
Here is a very simple proof that is built on top of two results.

**The replace-by-lighter-edge algorithm generates a minimum spanning tree (MST).** Start with any spanning tree $H$ of $G$. Find the cycle in $H$ plus an edge $e$ not in $H$. If an edge $t$ in that cycle is heavier than $e$, remove $t$ from $H$ and add $e$ to $H$. Repeat until we cannot any more. Then $H$ is a MST of $G$.
This is proven in this answer.

**All MSTs of $G$ have the same number of edges with any given weight.**
This is a classic result proven in this answer.

For the sake of contradiction, suppose for some $i$: $w\_i \gt w'\_i$. Then the number of edges in $T'$ with length less than $w\_i$ is at least $i$. Now apply the replace-by-lighter-edge algorithm on $T'$ so that the new $T'$ is an MST. Note that the number of edges in the new $T'$ with length less than $w\_i$ is still at least $i$. However, since all MSTs have the same number of edges with any given weight, $T'$ and $T$ should have the same number of edges with length less than $w\_i$, which is false. QED.

---
Tags: algorithms, graphs, minimum-spanning-tree
---


# Question
Title: Quick sort worst case complexity improvement
Can the worst case time complexity of quick sort be changed from $O(n^2)$ to $O(n\log n)$ by modifying it?

# Answer
The simplest way is to choose the median as pivot. Since the median can be found in linear time, the overall algorithm would satisfy the recurrence $$ T(n) = T(\lfloor \tfrac{n-1}{2} \rfloor) + T(\lceil \tfrac{n-1}{2} \rceil) + O(n), $$ whose solution is $T(n) = O(n\log n)$.
> 2 votes

---
Tags: time-complexity, sorting, quicksort
---


# Question
Title: Subtree with minimum sum of nodes' costs
Let's consider a tree with root $r$ ( not necessary binary) and to each node $i$ we associate a cost $\sigma(i)$ that can be negative, positive or zero. We want to select the set of nodes that minimize $\sum\_i \sigma(i)$. Of course, the problem until now is easy :

1. If there are only non-negative costs the solution is the empty set.
2. If there are some non-positive costs, we select them all.

But, there is an additional constraint that states: "if a node $\sigma(i)$ is selected, its predecessor to the root is also selected. Thus we are looking for the set of nodes that grow upward to the root and that minimize that sum, or equivalently, we are looking at a subtree of root $r$ that minimize that sum.

My question is how to design an algorithm that solves this problem and how to prove its correctness and compute its complexity?

(I have a hint that states that we could do some bottom-up traversal, of the tree but I don't know how to use this information)

Any help will be appreciated. Thanks

# Answer
> 2 votes
For a node $i$ with children $j\_1,\ldots,j\_d$, let us denote the best solution for the subtree rooted at $i$ by $\tau(i)$; you're interested in $\tau(r)$, where $r$ is the root. The function $\tau$ satisfies the recurrence $$ \tau(i) = \min(0, \sigma(i) + \tau(j\_1) + \cdots + \tau(j\_d)). $$ Indeed, there are two cases to consider. Either we take no vertex, in which the answer is 0. Otherwise, we must take $i$ itself (by the constraint), and then we should take the best solutions for the subtrees rooted at all children of $i$.

Like all such recurrences on trees, this one can be evaluated in linear time in many ways.

---
Tags: algorithms, graphs, algorithm-analysis, graph-traversal
---


# Question
Title: Predicting the next number output by a random number generator
Given a start of a sequence of random numbers generated by some random number generator (of which we don't have the implementation), can we predict the next numbers in the sequence?

For example, having a series of random numbers like this

```
40 46 15 37 9 4
32 26 5 33 17 21
12 19 13 36 25 29

```

These are the output numbers from a random number generator and I want to know the pattern that was used to generate them.

# Answer
> 2 votes
It is a well-known fact concerning (cryptographically secure) pseudorandom generators (PRGs) that pseudorandomness is equivalent to next-bit unpredictability. That is, distinguishing the output of a PRG from the uniform distribution is just as hard as predicting its next bit of output (when the PRG works on a uniformly distributed seed). This goes back to a result by Yao.

Further reading:

---

If we are talking about standard (i.e., not necessarily cryptographically secure) random number generators (RNGs), then things are a bit different. If the RNG simply has to fulfill a set of heuristics, then it can be the case that it does so despite being (almost) fully predictable. (As an extreme example, consider the rather naive heuristic $\lim\_{n \to \infty} E(|G(1^n)|\_0) = \lim\_{n \to \infty} E(|G(1^n)|\_1) = \frac{1}{2}$, that is, the string $G(1^n)$ tends to have just as many zeroes as ones and the "generator" $G(1^n) = 0^{\lfloor \frac{n}{2} \rfloor} 1^{\lceil \frac{n}{2} \rceil}$.)

Breaking such an RNG would involve statistical tests and *ad hoc* methods; your chances of success depend on what the heuristics are and how much computational power and RNG data you have available. Without having detailed these things, it cannot really be said whether it is feasible to break it or not.

# Answer
> 1 votes
It depends on the random number generator.

If you use random numbers for physical simulations, or maybe in a computer game, you don’t care whether the random numbers are predictable or not. What you care about is that you can produce different sequences, and often that you can replay a sequence. And you like one that is fast.

In cryptography, or if you run a lottery, you want numbers that are not predictable. Some random number generators have that property, some don’t. Those that cannot be predicted are called “cryptographic”.

Your average linear congruential random number generator is predictable, but it can be hard work. If I use one with 32 bit state, and give you the results of 50 simulated coin throws, and you know how I calculated the outcome, you can write a program easily that identifies the seed and predicts the next coin throws in a few minutes. If you don’t know my exact code, it is a lot harder. If I used a cryptographic RNG it would be impossible.

---
Tags: pseudo-random-generators, random-number-generator
---


# Question
Title: If a problem Q is NP complete, is another problem reducible to Q also NP complete?
Let's say $\mathcal{P}$ is a yes/no prolem with an existing reduction to the problem $\mathcal{Q}$ (with time complexity $\mathcal{O}(n^2)$). $\mathcal{Q}$ is NP complete. Does this mean that $\mathcal{P}$ is also NP complete?

# Answer
**Not necessarily.** *Any* language in $\mathbf{P}$ is poly-time many-one reducible to *any* non-trivial language (i.e., all except $\varnothing$ or $\Sigma^\ast$); see here, for example. The latter language (i.e., the one you are reducing to) is, in this case, the $\mathbf{NP}$-complete $\mathcal{Q}$. For all we know, your language $\mathcal{P}$ could be any language in $\mathbf{P}$ and, therefore, not necessarily $\mathbf{NP}$-complete (even under the assumption $\mathbf{P} = \mathbf{NP}$).
> 1 votes

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


title: Creating a CFG from a specific CFL

text:
# Question
Title: Creating a CFG from a specific CFL
I am pretty desperate finding the correct context free grammar for the following language: $$L=\\{a^lb^mc^n \mid l,m,n \in \mathbb{N}\_0, \\, l\geq 2n+m\\}$$

I would really appreciate if anyone could tell me how to generate the CFG from this language as I am stuck on this one for 2 days now.

I can't find a solution for adding the right amount of $b$'s and $c$'s to a generated string.

At the moment I have: $$ \begin{align\*} S &\rightarrow aS \mid T \mid U \mid \varepsilon \\ T &\rightarrow aTb \mid \varepsilon \\ U &\rightarrow aaUc \mid \varepsilon \end{align\*}$$

# Answer
> 3 votes
It might be easier than you have been thinking.

$$\begin{aligned} S&\rightarrow aS\mid U\\ U&\rightarrow aaUc\mid T\\ T&\rightarrow aTb\mid \epsilon \end{aligned}$$

The idea is to identify the language that could be obtained by a fixed operation that peels off some symbols. Peeling off $a$'s, we shrink words in $S$ to words in $U$. Peeling off some $a$'s and $c$'s, we shrink words in $U$ to words in $T$. $$\begin{aligned} S&=\\{a^ka^{2n}a^mb^mc^n \mid k,m,n \in \mathbb{N}\_0\\}\\ U&=\\{a^{2n}a^mb^mc^n \mid m,n \in \mathbb{N}\_0\\}\\ T&=\\{a^mb^m\mid m \in \mathbb{N}\_0\\} \end{aligned}$$

---
Tags: context-free
---


# Question
Title: Solving using the master theorem: T(n)=T(n/2)+n⋅log n and T(n)=T(n/8)+2.n
Could someone help me with these 2 questions?

I do not understand the case 3

1. $T(n) = T(n/2) + n \log n$
2. $T(n)=T(n/8)+2 n$

# Answer
> 1 votes
Let me show you how to solve these without using the master theorem. For the first item:

$$ T(n) = n\log n + \frac{n}{2} \log \frac{n}{2} + \frac{n}{4} \log \frac{n}{4} + \cdots \leq \left(n + \frac{n}{2} + \frac{n}{4} + \cdots\right) \log n \leq 2n\log n. $$ This shows that $T(n) = O(n\log n)$. Since clearly $T(n) = \Omega(n\log n)$, we can conclude that $T(n) = \Theta(n \log n)$.

The second item can be solved in the same way.

---
Tags: algorithms, master-theorem
---


# Question
Title: What does "bounded above" mean in Family of Bachmann–Landau notations?
Per wiki

> |f| is bounded above by g (up to constant factor) asymptotically

with this concrete example,

$$f(n) = \log n$$

$$g(n) = n^c = n^{0.000001}$$

Does "bounded above (up to constant factor)" means $f(n)$ is above $g(n)$

# Answer
> 3 votes
A quantity $a$ is *bounded above* by a quantity $b$ if $a \leq b$.

A quantity $a$ is *bounded above (up to constant factor)* by a quantity $b$ if there exists a constant $C\>0$ such that $a \leq Cb$. (This makes sense when $a,b$ depend on some other variable).

A quantity $a(n)$ is *bounded above (up to constant factor) asymptotically* by a quantity $b(n)$ if there exist constants $N,C\>0$ such that $a(n) \leq Cb(n)$ for all $n \geq N$. This is usually expressed as $a(n) = O(b(n))$.

# Answer
> 0 votes
"$x$ is bounded above by $y$" just means that $x\leq y$.

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


# Question
Title: Predicate Logics - double negation HELP me understand
Sorry for maybe a silly question but i need to understand how ¬(¬∀x ¬A(x)) equals ∀x ¬A(x)

In my mind, the negation before the parenthesis will be applied to both ¬∀x and ¬A(x). So it would look like this:

¬(¬∀x ¬A(x)) = ¬¬∀x ¬¬A(x)

A double negation would become positive and would then let ¬(¬∀x ¬A(x)) equal to ∀x A(x).

So, why would ¬(¬∀x ¬A(x)) equal ∀x ¬A(x)? Why wouldnt ¬(¬∀x ¬A(x)) equal ∀x A(x)?

# Answer
The semantics of negation are very simple:

> $\lnot \alpha$ is True iff $\alpha$ is false.

In your example, $\lnot (\lnot \forall x \lnot A(x))$ is True iff $\lnot \forall x \lnot A(x)$ is False iff $\forall x \lnot A(x)$ is True iff for all $x$, $\lnot A(x)$ is True iff for all $x$, $A(x)$ is false.

Perhaps the issue would become simpler if we fully parenthesize your expression: $$ \lnot \stackrel 1( \lnot \stackrel2( \forall x \stackrel3( \lnot \stackrel4( A\stackrel5( x \stackrel 5) \stackrel 4) \stackrel 3) \stackrel 2) \stackrel 1). $$ The superscripts count the nesting depth.
> 1 votes

---
Tags: predicate-logic
---


title: The cheapest path in the graph

text:
# Question
Title: The cheapest path in the graph
I am supposed to decide, if the statement is true or false and use arguments for my answer.

In every weighted n-vertices graphs:

1. with no negative weighted edges,
2. with n\>10,
3. in which every weighted edge appears constant number of times(e.g. 1,2,3.., but not n number of times), but graphs, in which every edge has the same value, does not satisfy this condition,

there exists between every two vertices at most 4\*n^3.

I tried to draw some graphs and I conclude that all of them satisfy my conditions. But I do not have general explanation.

So is that true? If not, can you say me some counter example?

Thanks.

# Answer
> 1 votes
Hint: consider cases where every weight is very large.

---
Tags: graphs, weighted-graphs
---


# Question
Title: Tarjan's Algorithm failure case, what am I missing?
I'm having a little trouble with Tarjan's Algorthm.

So here's my problem: I have a graph such that these nodes are directionally-connected as shown:

```
A: B C D E
B: D E
C: B D E F
D: C E
E: B
F: A B D E

```

My problem is Tarjan's Algorithm never revisits nodes, apparently. If the node isn't on the stack, it's not checked.

So here's what's happening:

My algorithm is going A, D, E, B. B checks D.

```
A(id=0, link=0), D=1, E=2, B=3
-> D is visited, D is on stack, D's id is 1, B(id=3, link=1)

```

Cute. B checks against E (cycle—it's a tie), which has an ID of 2, and is on the stack, no change.

B is out of neighbors, doesn't have a neighbor, returns out of the recursion so E can continue.

E, upon return from DFS of B, checks B's low-link value. It's lower, so E's low-link value becomes 1.

```
A(id=0, link=0)
B(id=3, link=1)
C(undefined)
D(id=1, link=1)
E(id=2, link=1)
F(undefined)

```

Now return to D. D's id and low-link value are 1, so no change.

Now here's the fun part.

D proceeds to check C. C checks F. F checks A, which has been visited and is on the stack. A has an ID of 0, so D updates.

```
F(id=5, link=0)
C(id=4, link=0)
B(id=3, link=1)
E(id=2, link=1)
D(id=1, link=0)
A(id=0, link=0)

```

A proceeds to check the rest of its neighbors. B and D have higher link values and IDs and are on the stack, so A doesn't update.

Every node has been visited.

There's a path from D to E to B to D, meaning those are part of the same SCC (in fact, all of these are in the same SCC—it's one SCC).

The stack is {A, D, E, B, C, F} with F at the top.

The two SCCs are {B,E} and {A,C,D,F}.

…you can reach A from B, and you can reach B from A.

What am I missing here?

# Answer
> 1 votes
Answer: the low-link value is not the identifier. I eventually found this while researching during the writing of this question. Question posted because I wrote it and hey, maybe this will help someone else.

Everything up to the current node is popped off the stack when identifying an SCC. My misunderstanding was trying to pop only what has the same low-link value.

---
Tags: algorithms, graphs
---


# Question
Title: Is the number of shortest paths between every two vertices at most 4*n^3?
In every weighted graph with $n$-vertices

* with negative weights,
* with $n \> 10$,
* a weight can't appear $n$-times in graph,

there are between every two vertices at most $4n^3$ shortest paths.

I'm trying to prove whether the statement above is true or false, however I am clueless. So far I failed to find a graph where there would be more than $4n^3$ shortest paths so I'm guessing it's true?

# Answer
> 1 votes
Consider the following graph, where we have $3\times 4+1=13$ nodes, $a1, b1, c1, a2, b2, c2, a3, b3, c3, a4, b4, c4, a5$ and $4\times4=16$ edges $a1b1, a1c1, b1a2, c1a2, \cdots, a4b4, a4c4, b4a5, c4a5$ with weights $1,1,1,1,\cdots, 4,4,4,4$ respectively.

Every path from $a1$ to $a5$ is a shortest path between them since all of them have the same weight (length). There are $2^4=16$ of them.

Consider extending this graph to a much larger graph, following the same pattern. For example, suppose we will have $100\times3+1=301$ nodes and $100\times4+1=400$ edges. Now compute how many shortest paths there are between $a1$ and $a301$.

---

**Exercise 1.** Construct a graph with the same constraint such that there are more than $4n^3$ paths of the same weight between every two vertices.

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


# Question
Title: How To Show That B is Semi-Decidable Given A
I am preparing for my Computational Theory final and ran into this exact problem :

*B={ x | there exists a prefix of x that is in A}.*

Show that ***B*** is semi-decidable. In other words, you need to describe an algorithm ***M*** that on input a string ***x*** semi-decides if some prefix of ***x*** is in ***A*** (“semi-decides” means that it is OK if the algorithm loops for strings with no prefix in ***A***). You will assume that you have an algorithm ***MA*** that semi-decides ***A***.

Any help would be greatly appreciated!

# Answer
A language is semi-decidable if there is a Turing machine that halts for all strings in the language, and doesn't halt for strings not in the language.

You are given that $A$ is semi-decidable. Therefore there is a Turing machine $M$ that halts on an input $x$ iff $x \in A$. Your goal is to construct another Turing machine $M'$ that halts on an input $x$ iff one of the prefixes of $x$ is in $A$. In other words, $M'$ should halt on $x$ iff $M$ halts on one of the prefixes of $x$.

You take it from here.
> 1 votes

---
Tags: turing-machines, decision-problem, semi-decidability
---


# Question
Title: If an algorithm solves an NP problem, for what f(n) can we claim that R belongs to TIME(f(n))?
Let $R$ be some problem in NP.

Suppose algorithm of solution check M(x,y) runs in time $O(n^3)$ and uses $y$ additional information, s.t $y \leq 5 \log n$ bits.

For what $f(n)$ can we claim that $R$ belongs to $\textbf{TIME}$$(f(n))$?

I have no idea how to solve this.

# Answer
> 2 votes
Suppose, for clarity:

* $X$ is the input, and $|X|$ = $n$
* $Y^\*$ is a "yes" certificate, $|Y^\*| \leq 5\log n$ bits
* $M$ is an algorithm that verifies the instance $X$ given certificate $Y^\*$ in $O(n^3)$ time.

There are $2^{|Y^\*|}$ possible binary certificates of length $|Y^\*|$, so algorithm $A$ that checks all possible certificates $Y\_i$ of length $5\log n$ will have exactly $ 2^{5\log n} = n^5$ certificates to check.

Since each certificate takes $O(n^3)$ time to verify (with $M$), $A$ will run in $O(n^8)$. If $X \in R$, a certificate $Y^\*$ that verifies it exists and $A$ will find it (because it checks them all).

It follows that $A$ accepts $R$ and runs in $O(n^8)$ time, so $R \in \textbf{TIME}(n^8)$

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


# Question
Title: Running time for Breadth-First-Search vs Depth-First-Search
Can someone explain why BFS is $O(V + E)$ whereas DFS is $\Theta(V + E)$. I understand the definitions of both notations, but I just don't see why the bound for DFS should be tighter than that of BFS.

Is it because DFS is guarenteed to visit all vertices and hence has the lower bound $\Omega(V+E)$?

Note: I am studying the CLRS book, which is where the running times is coming from

# Answer
The running time of both BFS and DFS are $\Theta(V+E)$ since both of them are guaranteed to visit every vertex and every edge at least once. Note that we are talking about the situation when the input graph is a connected graph whose edges are given by adjacency-list, the most common situation (in the course of your study).

It is not surprising that the CLRS book presents the running time of BFS as $O(V+E)$ even though $\Theta(V+E)$ is the optimal asymptotic bound for its running time. It is actually a general practice that the running time of an algorithm is described in term of big $O$ even though it might be possible to describe in term of big $\Theta$. The reason is that how tight we can bound the running time of an algorithm from above is the major concern for many situations.
> 3 votes

---
Tags: algorithms, time-complexity, runtime-analysis
---


# Question
Title: How to prove the emptiness of intersection of two context free languages is undecidable?
Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful.

Do you maybe have a book or paper I should investigate?

# Answer
> 8 votes
A popular reference is the article *Undecidable Problems for Context-free Grammars* by Hendrik Jan Hoogeboom.

The following is a proof taken from this note by Rob van Glabbeek.

---

**Theorem**: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection.

**Proof**: By a reduction of post correspondence problem (which is known to be undecidable) to the empty intersection problem. Given a set $d\_1,\cdots,d\_n$ of dominos where, for $i=1,\cdots,n$, the top string of $d\_i$ is $w\_i$ and the bottom string of $d\_i = x\_i$. Consider the context-free grammars

$$W\to w\_1Wd\_1\mid w\_2Wd\_2\mid\cdots\mid w\_nWd\_n\mid w\_1d\_1\mid w\_2d\_2\mid\cdots\mid w\_nd\_n$$ and $$X\to x\_1Xd\_1\mid x\_2Xd\_2\mid\cdots\mid x\_nXd\_n\mid x\_1d\_1\mid x\_2d\_2\mid\cdots\mid x\_nd\_n.$$

Now notice that the given instance of PCS has a match exactly when the intersection of the languages generated by the resulting grammars above is nonempty.

---
Tags: formal-languages, context-free, reference-request, undecidability
---


# Question
Title: How to prove that a language is not context-free using pumping lemma
I'm trying to prove that that language isn't a context free:

$ L = \\{ w11w \mid w\in \Sigma^\* = \\{0,1\\}\\}$

I succeed to prove that $L = ww$ isn't context free, but not the language above. What am I doing wrong?

# Answer
> 1 votes
Here is the simplest way. Suppose that your language were context-free, and consider its intersection with $0^\*(10)^\*110^\*(10)^\*$. Applying further simple manipulations, you reach the language $\\{a^nb^mc^nb^m : n,m \geq 0\\}$, which is known not to be context-free.

If you insist on using the pumping lemma, perhaps you can get inspiration from this argument.

---
Tags: context-free
---


# Question
Title: Bellman-Ford - is number of interations greater than diameter?
> Diameter of a connected, undirected graph is the smallest natural number *d*, so that between any two vertices of the graph exist path of length at most *d*.
>
> Prove or disprove: in Bellman-Ford is the number of iterations always equal or lower than *d*.

I'm trying to solve this issue. What I tried was sketching a lot of graphs, however I have failed to find a single graph where the number of iterations would be higher than the diameter.

The only graph where the number of iterations wouldn't be \<= than diameter would be a graph with negative edges, however I found out that in undirected graph there can't be any negative edges, otherwhere there would be a negative cycle.

So, AFAIK the statement is correct. However, how would I prove such a statement? I don't even know how to start. Thanks for any help

# Answer
> 1 votes
In the Bellman–Ford algorithm, after $t$ iterations the array contains, for any two nodes, the minimal walk of length at most $t$ connecting them. Assuming your graph doesn't have negative weights, the shortest walk between any two vertices will be a path, and so its length would be at most the diameter. Therefore there is no need to run the algorithm beyond $d$ iterations.

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


title: Fast hash function for set equality

text:
# Question
Title: Fast hash function for set equality
I'm searching an hash function for integer set equality that must be fast. It must support update (adding an element already in the set must not change the hash) and union. MinHash has these 2 properties but it is too expensive and I do not need all the feature of MinHash, in fact I don't need set similarity but only equality. Do you know something that can satisfy my needs? Thanks :)

P.S. I have to implement it in C for an high performance software

# Answer
> 3 votes
MinHash already *is* super-fast. I suggest you check whether you understand correctly how MinHash works.

Take any standard hash function $H$; then all you have to do is compute $H$ once on each element of the set. You can implement $H$ with as fast a hash algorithm as you want. The update operation requires one call to $H$ (namely, if your set's hash is currently $y$, and you add element $x$, the new hash is $\min(y, H(x))$), and the union operation is super fast (namely, the union of two sets with hashes $y\_1,y\_2$ is $\min(y\_1,y\_2)$). Notice that these operation have the property you want (adding an element already in the set does not change the hash).

I have a hard time imagining how you could get much faster than that.

If you want this to be faster, a reasonable way is to choose a $H$ that is faster.

I've described a variant where the hash of a set is the smallest of the element-hashes. The only downside is that the number of hash collisions might higher than you like. Measure and see if that is actually a problem in practice. If it is, you can consider variants that keep the $k$ distinct smallest element hashes. If $k$ is large, you can store those $k$ hashes in a heap of size $k$ to make the update and union operations faster.

---
Tags: data-structures, sets, hash
---


# Question
Title: Partitioning a boolean circuit for automatic parallelization
tl;dr: I have a problem where I have a Boolean circuit and need to implement it with very specific single-thread primitives, such that SIMD computation is significantly cheaper after a threshold. I'm trying to optimize the implementation.

Going into detail, the input is a combinatorial Boolean circuit (so no loops, state, etc.). I'm implementing it in software with a rather unusual set of primitives, such that:

* logic gates must be computed one at a time, as the "engine" is single-threaded
* NOT gates are free
* AND, OR, XOR have a cost of 1 (eg. 1 second)
* N identical gates can be evaluated at the same time for a cost of 10 plus some tiny proportional term (eg. a batch of 20 distinct AND gates can be evaluated in 10 seconds, 50 distinct XOR gates in ~10 seconds, etc.)

The objective is to implement the circuit with the given primitives while minimizing the cost.

---

### What I tried

This problem looks vaguely related to the bin packing problem, but the differences - constraints on the order of the items and different cost for each "bin" depending on the number of items - make me think it's not particularly applicable.

I was suggested to use integer linear programming, which sounds like the best fit so far, but I'm not sure how to represent the problem. Specifically, I'd use binary variables to represent whether the *implementation* gate/batch M is used in place of the *circuit* gate N, but then I don't know how to express the objectives to be maximized/minimized.

# Answer
> 1 votes
One approach for formulating this as an ILP problem could be to have zero-or-one variables $x\_{i,t},y\_{i,t},z\_t$, with the intended meaning that $x\_{i,t}=1$ if the $i$th gate is evaluated in the $t$th instruction (not as part of a batch), or $x\_{i,t}=0$ otherwise; and $y\_{i,t}=1$ if the $i$th gate is evaluated in a batch in the $t$th instruction, or $y\_{i,t}=0$ otherwise; and $z\_t=1$ if the $t$th instruction is a batch instruction, or $z\_t=0$ otherwise.

Your problem can then be represented as an integer linear program, with some constraints to enforce consistency of these boolean variables:

* Each gate is assigned to a single instruction: $\sum\_t x\_{i,t} + y\_{i,t}=1$.
* Non-batch instructions are assigned a single gate: $\sum\_i x\_{i,t} = 1-z\_t$.
* Non-batch instructions don't set any $y$ values: $\sum\_i y\_{i,t} \le C z\_t$, where $C$ is a large constant equal to the maximum batch size (or the number of gates, if there is no limit).
* Gates can only be batched together if they compute the same logic function: $y\_{i,t} + y\_{j,t} \le 1$ for each pair of gates $i,j$ that have a different logic function.
* A gate can only be evaluated once all of its inputs are ready: $x\_{i,t} + y\_{i,t} \ge x\_{j,u} + y\_{j,u}$ for each pair of gates $i,j$ such that the output of $i$ is an input to $j$, and for each pair $t,u$ with $t\<u$.

(I'll assume you treat NOT gates as free and don't try to assign them to any instruction; they just happen automatically.)

Now any consistent assignment to the $x$'s and $y$'s will correspond to a valid way to implement the circuit. The cost of this assignment will be $9 \sum\_t z\_t + c \sum\_{i,t} y\_{i,t} + k$, where $c$ is the tiny proportional term and $k$ is the total number of instructions in the schedule (both $c$ and $k$ are constants). If you pick a value for $k$, the maximum number of instructions allowed, you can use an ILP solver to minimize $9 \sum\_t z\_t + c \sum\_{i,t} y\_{i,t} + k$ subject to the inequalities above, and this will give you the best way to schedule your boolean circuit using $k$ instructions. Then, I suggest you search over different values of $k$, solving an ILP for each one, to find the best boolean circuit.

Be prepared: ILP is NP-hard, so finding the optimal solution might take a very long time if the circuit is large and you're aren't very lucky. Some ILP solvers have the ability to terminate their search after a fixed time limit and return the best solution they've found so far, which might be useful if that happens.

---
Tags: graphs, linear-programming, partitions
---


# Question
Title: Linear programming IFF with equality constrain
Is it possible to write the following logical constrain in linear programming?

Let $v$ be an integer variable and $k$ an integer constant. Let $y$ be a binary variable. The logical constraint is

$y=1 \Longleftrightarrow v=k$.

I need this kind of constraint in linear programming to use it in AMPL, but I really can't find a way to write it down as a linear constraint.

# Answer
Yes, this is possible. The main idea is that a binary variable can be used to enable/disable a inequality constraint as follows: given an inequality $a\cdot x\leq b$ and a binary variable $v$, pick a constant $L$ such that $a\cdot x - b\leq L$ is true for all variable assignments. Then the inequality $a\cdot x \leq b+ (1-v)L$ will be equal to $a\cdot x\leq b$ if $v=1$ and will always be true if $v=0$.

So, the constraint $y=1\Rightarrow v=k$ part can be modeled by the two inequalities $v\leq k+(1-y)L$ and $v\geq k - (1-y)L$. For the other part, $v=k\Rightarrow y=1$, we first transform this into $y\neq 1\Rightarrow v\neq k$. We can model the $v\neq k$ condition as $v \< k \vee v \> k$ and to model the 'or' we introduce a new binary variable $q$. In particular, we want $v\<k$ if $q=1$ and $y=0$ and $v\>k$ if $q=0$ and $y=0$, so we get $v \< k + (1-q+y)L$ and $v \> k-(q+y)L$.

In summary, the inequalities $$\begin{align} v&\leq k+(1-y)L\\ v&\geq k - (1-y)L\\ v &\< k + (1-q+y)L\\ v &\> k-(q+y)L\end{align}$$ model the constraint $y=1 \Leftrightarrow v=k$.
> 0 votes

---
Tags: optimization, linear-programming, integer-programming, mathematical-programming
---


# Question
Title: Find plane within margin of error of >50% of points
> There are $N \< 3\times10^4$ 3D points. At least 50% of them lie approximately in the same plane, i.e. the distance between the plane and each point is at most $p$. Find such a plane.

**Attempt**: since the number of points in the plane is at least 50%, we can randomly sample 3 points from the set. They will all be in the plane with probability 12.5%. We build a plane through these 3 points and check that at least 50% of points lie approximately in it. Within 10-20 samples we'll find the plane.

Problem: because of the margin of error there's not just one plane going through 3 points, but many possible planes. How do we examine all of them?

How would you tackle this problem?

# Answer
> 2 votes
One reasonable approach is to use RANSAC.

Pick three points. Find the plane that goes through them. Iterate through all the points and keep the points that are near that plane (the inliers) and discard the rest (the outliers). If fewer than 50% of the points are inliers, discard this plane. Otherwise, discard the plane you have so far and use linear regression to find the best plane that fits the inliers as well as possible. That's a candidate plane.

Repeat this 1000 times, to get 1000 candidate planes. Take the best one. You can measure how good a candidate plane is by taking the average distance from the plane to each point, averaged over all the points that are close to that plane (ignore the ones that are far away; if 50% or more are far away, discard the plane).

---
Tags: computational-geometry, data-mining
---