# Question
Title: Difficulty in understanding a portion in the proof of the $\text{"white path"}$ theorem as with in CLRS text
I was going through the $\text{DFS}$ section of the *Introduction to Algorithms* by *Cormen et. al.* and I faced difficulty in understanding the $\Leftarrow$ direction of the proof of the white path theorem. Now the theorem which is the subject of this question depends on two other theorems so I present the dependence before presenting the actual theorem and the difficulty which I face in the said.

---

**Dependencies:**

> ***Theorem 22.7 (Parenthesis theorem)*** In any depth-first search of a (directed or undirected) graph $G = (V, E)$, for any two vertices $u$ and $v$;, exactly one of the following three conditions holds:
>
> * the intervals $\[d\[u\], f\[u\]\]$ and $\[d\[v\], f\[v\]\]$ are entirely disjoint, and neither $u$ nor $v$ is a descendant of the other in the depth-first forest,
> * the interval $\[d\[u\], f\[u\]\]$ is contained entirely within the interval $\[d\[v\], f\[v\]\]$, and $u$ is a descendant of $v$; in a depth-first tree,
> * the interval $\[d\[v\], f\[v\]\]$ is contained entirely within the interval $\[d\[u\], f\[u\]\]$, and $v$ is a descendant of $u$ in a depth-first tree.

> ***Corollary 22.8 (Nesting of descendants' intervals)*** Vertex $v$ is a proper descendant of vertex $u$ in the depth-first forest for a (directed or undirected) graph $G$ if and only if $d\[u\] \< d\[v\] \< f\[v\] \< f\[u\]$.

---

> ***Theorem 22.9 (White-path theorem)***
>
> In a depth-first forest of a (directed or undirected) graph $G = (V, E)$, vertex $v$ is a descendant of vertex $u$ if and only if at the time $d\[u\]$ that the search discovers $u$, vertex $v$ can be reached from $u$ along a path consisting entirely of white vertices.
>
> Proof
>
> $\Rightarrow$ : Assume that $v$ is a descendant of $u$. Let $w$ be any vertex on the path between $u$ and $v$ in the depth-first tree, so that $w$ is a descendant of $u$. By Corollary 22.8, $d\[u\] \< d\[w\]$, and so $w$ is white at time d\[u\].
>
> $\Leftarrow$:
>
> 1. Suppose that vertex $v$ is reachable from $u$ along a path of white vertices at time $d\[u\]$, but $v$ does not become a descendant of $u$ in the depth-first tree.
> 2. Without loss of generality, assume that every other vertex along the path becomes a descendant of $u$. (Otherwise, let $v$ be the closest vertex to $u$ along the path that doesn't become a descendant of $u$.)
> 3. Let $w$ be the predecessor of $v$ in the path, so that $w$ is a descendant of $u$ ($w$ and $u$ may in fact be the same vertex) and, by Corollary 22.8, $f\[w\] \leq f\[u\]$.
> 4. Note that $v$ must be discovered after $u$ is discovered, ***but before $w$ is finished.***$^\dagger$ Therefore, $d\[u\] \< d\[v\] \< f\[w\] \leq f\[u\]$.
> 5. ***Theorem 22.7 then implies that the interval $\[d\[v\], f\[v\]\]$ is contained entirely within the interval $\[d\[u\], f\[u\]\]$.***$^{\dagger\dagger}$
> 6. ***By Corollary 22.8, $v$ must after all be a descendant of $u$.*** $^\ddagger$

---

$\dagger$ : Now it is clear that since $u$ is the first vertex to be discovered so any other vertex (including $v$) is discovered after it. In point $1$ we assume that $v$ does not become the decendent of $u$, but by the statement that ***but before $w$ is finished*** I feel that this is as a result of exploring the edge $(w,v)$ (this exploration makes $v$ ultimately the descendant of $u$, so the proof should have ended here $^\star$)

$\dagger\dagger$ : Considering the exact statement of theorem 22.7 , I do not get which fact leads to the implication in $5$.

$\ddagger$ : The proof should have ended in the $\star$, but why the stretch to this line $6$.

Definitely I am unable to get the meaning the proof of the $\Leftarrow$. I hope the authors are using proof by contradiction.

(I thought of an alternate inductive prove. Let vertex $v$ is reachable from $u$ along a path of white vertices at time $d\[u\]$. We apply induction on the vertices in the white path. As a base case $u$ is an improper descendant of itself. Inductive hypothesis, let all vertices from $u$ to $w$ be descendants of $u$ , where $w$ is the predecessor of $v$ in the *white path*. We prove the inductive hypothesis by the exploration of the edge $(w,v)$. But I want to understand the proof the text.)

# Answer
> 1 votes
$\dagger\dagger$ Theorem 22.7 concludes that exactly one of the three conditions listed is satisfied. The inequalities listed in (4) show that the intervals $\[d\[u\],f\[u\]\]$ and $\[d\[v\],f\[v\]\]$ intersect. Therefore, the first condition of the theorem is not the one being satisfied. In the other two conditions one of these two intervals is inside the other. Now, because the inequality $d\[u\]\<d\[v\]$ is strict, it can't be that $\[d\[u\],f\[u\]\]$ is inside $\[d\[v\],f\[v\]\]$. So, the third condition in the theorem is the only one that can be satisfied.

$\dagger$ This is also using theorem 22.7 or its corollary. The inequality $d\[u\]\<d\[v\]$ is part of the assumption, that by time $d\[u\]$ the vertex $v$ is still white. The inequality $f\[w\]\leq f\[u\]$ comes from Corollary 22.8, since $w$ is a descendant of $u$. The inequality $d\[v\]\<f\[w\]$ is due to $(w,v)$ being an edge. Because all neighbors of $w$ must be discovered before we consider it finished. Now, the claim that the proof should end here is jumping to the conclusion of the theorem without justification. It hasn't been justified that DFS will actually use $(w,v)$ to discover $v$.

**Example 1:** For example, consider the graph with vertices $1,2,3,4$ and (directed) edges $(1,2),(1,4),(2,3),(4,3)$ and we start at $1$ doing DFS. Assume that we already discovered $1$ and $2$.

At this point the vertex $v=3$ is is a white path from $u=w=2$. Just one edge $(2,3)$. DFS will discover $3$ and make it a descendant of $2$. There is no way to change that, since Theorem 22.9 proves it. But imagine that at this point we stop obeying DFS and go to discover $4$ and from $4$ go and discover $3$. Then $3$ wouldn't be a descendant of $2$. It would only be a descendant of $4$ and $1$. Theorem 22.9 proves that DFS wouldn't do that.

**Example 2:** This is to illustrate the question in the comments. Consider the graph with vertices $1,2,3,4$ and edges $(1,2),(1,4),(2,3),(2,4),(3,4)$. Assume that we have discovered already $1$ and $2$, in that order. The vertex $v=4$ is in a white path from $u=w=2$. However, the edge $(2,4)$ doesn't necessarily need to be used by DFS. If the neighbors of a vertex are considered in the order according to the labels that we gave them in this example, then from $2$ DFS will discover $3$ and from $3$ it will discover $4$. Then $3$ becomes finished, then $2$ becomes finished, and $1$ becomes finished, in that order.

While theorem 22.9 doesn't ensure that either $(2,4)$ or $(3,4)$ will be used, since that depends on the other in which neighbors are explored, note that it does ensure that the edge $(1,4)$ will **not** be used (under the assumptions of the example that $1$ was discovered and $2$ just got discovered). In fact, Theorem 22.9 implies that $4$ will be a descendant of $2$.

---
Tags: algorithms, graphs, proof-techniques, graph-traversal
---


# Question
Title: Algorithm to find slope of line with a modulus
Say I have some data which represents a single line, and I want to determine its approximate slope. This data has a known minimum and maximum on the y-axis. When the line crosses the maximum, it re-emerges at the minimum, or vice versa, so there appear to be many parallel lines in the data. Clearly, the feasibility of this is dependent on the sampling rate and the amount of noise in the data. Also, a slope too steep will put the apparent parallel lines too close to each other such that they'd become impossible to distinguish. So, we'll assume that the sampling rate, noise, and slope are all within reasonable limits. Is there a particularly elegant way to approach this problem?

# Answer
> 0 votes
As I understand it, the best way should just be to take the known maximum - minimum as your change in ***y***, and the period length as the change in ***x*** (assuming the function you've described is periodic, with its domain as ), and their ratio is the slope. Since you're dealing with discrete points, you'd just need enough data to estimate the shape of two periods to solve for the period length, but more is obviously better.

---
Tags: modular-arithmetic
---


# Question
Title: Definition of liveness property in model checking
A property $P$ is simply a set of sequences of states and a certain program is characterized by its set of sequences of states, let's call it $T$. A program is compliant to a specific property P if $T\subseteq P$.

Intuitively, a specific liveness property LP1 is the set of traces (sequences of states ) in each of which "something good" will happen, based on the specific property LP1 (for example "termination"). This means that if a program it's compliant with LP1 in each of its traces the "good thing" will happen, that is the program will terminate.

However, I don't understand how the formal definition of liveness property contains what was said, can you explain me? This definition to me makes no sense (i know all the terminology)...

$\forall t\in S^{\*}\\,(\exists t'\in S^{\omega }:t\leq t^{'}\wedge t^{'}\in LP1)$

# Answer
> 2 votes
I'm not sure where the particular liveness definition you wrote comes from, but the definition given in *Defining Liveness* (Schneider, Alpern, 1985) is as follows.

A property $P$ is a liveness property if and only if: $$ \forall \alpha \in S^\* : (\exists \beta \in S^\omega : \alpha\beta \vDash P) $$

where $S^\*$ is the set of all partial executions and $S^\omega$ is the set of all infinite executions.

This definition captures the intuition that the "good thing" (the "something good" that you mentioned) specified by a liveness property can always occur in the future. That is, no matter the finite prefix $\alpha$ you choose, you can always find an infinite suffix $\beta$ to extend it with that will satisfy a liveness property $P$. I am assuming that the $\leq$ symbol in the definition you gave is used to express a prefix relationship between traces, which makes it analogous to the definition from the paper.

You might make an argument for defining liveness in some alternative way. Indeed, two slightly different characterizations of liveness are given in that same paper (see *uniform liveness* and *absolute liveness*). The definition given above, though, provides a basis for the topological characterization of safety and liveness properties which they use to prove the decomposition theorem i.e. that any property can be expressed as a conjunction of a safety and liveness property. So, it would seem that the definition is relatively "natural".

As they remark in the final paragraph of that paper:

> It seems naive to hope for a proof that a formal definition for liveness (or safety) is correct, because "good things" and "bad things" are not well-defined concepts. However, the simple topological characterization of the definitions suggests that they do indeed capture fundamental distinctions.

---
Tags: software-verification, model-checking
---


title: Range search in a max-heap

text:
# Question
Title: Range search in a max-heap
I am having trouble with coming up for a suitable algorithm for this question. A max-heap is essentially visualized as a binary tree not a binary search tree. Also the runtime of the algorithm must depend only on the number of elements in the output. I was thinking of doing a preorder traversal on the max heap. While doing the preorder traversal, if the value of a node is less than the given value x, we return to the previous recursive call. All child nodes in a max heap are less than the parent node. Otherwise we output current node and recur on the children.

I am not sure however if the runtime of this algorithm depends only on the number of elements in the output.

Anybody have other suggestions/thoughts? Thanks.

# Answer
> 0 votes
The algorithm you're describing is basically correct.

To summarize in one sentence: "If the current value is less than $x$, turn back."

The reason it has the desired time complexity is because the set of the nodes you are visiting is precisely:

* the root node
* all the nodes which are *direct descendants* of the nodes in the output (since every node has no more than two children, there are no more than $2k$ of these)

So the total number of times the body of your function gets executed is no more than $2k+1$.

---
Tags: binary-trees, heaps
---


# Question
Title: Proof that $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states
How can you prove that any DFA accepting the language generated by the regular expression $\\{0|1\\}^\*0\\{0|1\\}^n$ requires at least $2^{n+1}$ states?

I first attempted induction on $n$. But I don't even see how to prove the base-case, like if $n=1$. You need the DFA to take any string and, when it encounters a 0, get set down a track of checking that $n$ characters follow. If it's fewer than $n$ then fine you reject. But if there are more characters, to sort of re-set it so that it looks for the first 0 after the earlier one was found. But DFAs don't have that kind of memory.

And once you've established the base-case, the inductive case doesn't seem clear either. If you know the result is true up to $n$, then if you consider the regex with $n+1$ then you get a DFA which accepts it. You intuitively want to remove the accepting states and "move them back" one vertex in the graph. Now you have a DFA with at least $2^n$ states. But how do you know that you needed $2^n$ accepting states so that the net number of accepting states is then $2^{n+1}$?

# Answer
> 2 votes
This isn't about induction, it's about proving that the correct DFA **must** have enough memory to remember **everything** about the last $n+1$ characters. The very number $2^{n+1}$ should have been a clue to this.

Imagine that the DFA has just now read some prefix that's longer than $n+1$, but it doesn't yet know if there are any more characters left. Ask the question: what must the DFA currently remember?

* Well, clearly, it must remember what it read $n$ characters ago, to decide whether to accept or reject if the string just ends right now
* It also must remember what was $n-1$ characters ago, just in case the string ends 1 character later
* And it must remember what was $n-2$ characters ago, just in case the string ends 2 characters later
* And it must remember what was $n-3$ ...

As you can see, by that kind of logic it must be absolutely sure about each of $2^{n+1}$ bits. To formalize this deduction, try to prove the following:

LEMMA: If $a$ and $b$ are two *different* strings of length $n+1$, then they should lead the DFA in question to two *different* states.

The method for proving this lemma is to append things to $a$ and $b$, such that, for example, string $ac$ must be accepted and string $bc$ must be rejected. If the automaton knows the difference between $ac$ and $bc$, then it must have known the difference between $a$ and $b$. Look up "right invariant equivalence" if you don't already know that concept.

Once you prove the lemma, the rest is obvious. There are $2^{n+1}$ different strings which all lead to different states. Therefore, there are at least $2^{n+1}$ different states.

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


# Question
Title: How does maths consistency impacts on computer science?
Lot of mathematicians have made several efforts to answer the question : are mathematics consistent ? Although we haven't yet had a proof of consistency, and surely we will never (Gödel second theorem), does this question has an impact on computer science ? I mean, does the work of those mathematicians, like Gödel's theorems or formal deduction systems, shows new answers or new problems in computer science ? What would happen in computer science if, for example, we found a paradox in set theory ?

# Answer
> 6 votes
Absolutely nothing will happen. Computers will still work, experts in machine learning will continue perfecting their tools, and even theoretical computer scientists will go on happily proving their theorems. Most mathematicians will also not feel much difference.

While we are trained to think that we are carrying out our proofs in ZFC, in practice proofs in mathematics and computer science are almost always carried out in English. Even if a contradiction is discovered in set theory, it is extremely likely that the axioms can be amended in such a way that the contradiction disappears and no proofs are affected apart from those in very specialized fields of a foundational nature.

More controversially, one can argue that most mathematicians argue in a nebulous system which actually does not rely on ZFC at all. Indeed, the average mathematician and nearly all computer scientists have little recourse to ZFC during their research life. Making this claim less nebulous, one can (and people do) argue that virtually all proofs in non-foundational fields can be carried out in weak subsystems of ZFC that are in less danger of being shown to be inconsistent. A nice reading in this general direction is McLarty's What does it take to prove Fermat's last theorem.

# Answer
> 2 votes
This would have a *huge* impact on computer science. All of CS is either a branch of mathematics, or built on the foundations of mathematics.

Every algorithm correctness proof or complexity bound is proven using mathematics. An inconsistency would shake the field to its core.

Moreover, through the Curry-Howard correspondence, proofs are isomorphic to well-typed programs, so a ton of type theory would go out the window.

That said, there is hope. There are multiple foundations of mathematics: ZF set theory, ZFC set theory, Martin-Lof Type Theory, Homotopy Type Theory, etc. Much of Computer Science has been done in all of these theories (particularly in PL theory), so if one is proven inconsistent, it may not mean that all is lost.

# Answer
> 1 votes
Let's assume that maths is inconsistent, and there is a proof that 1 = 0. Using that proof, you can prove that the runtime of any algorithm is zero.

That proof, however, doesn't change the runtime of the algorithm. So we would be in a slightly problematic situation: That we cannot use or trust proofs that are so complex that they can take advantage of this inconsistency. I think it is only very slightly problematic.

# Answer
> 0 votes
I think that the other Debaters answered the question concerning an impact of the consistency of mathematics on computer science.

But I have some comments to the following sentences:

> Lot of mathematicians have made several efforts to answer the question : are mathematics consistent ? Although we haven't yet had a proof of consistency, and surely we will never (Gödel second theorem), does this question has an impact on computer science ?

Namely, I recommend the paper: T. J. Stepien, L. T. Stepien, "On the Consistency of the Arithmetic System", *J. Math. Syst. Sci.*, vol. 7, No.2, 43-55 (2017); arXiv:1803.11072. There in this paper a full proof of the consistency of the Arithmetic System was published. This proof had been done **within** this Arithmetic System (of course, on the silent assumption that first-order logic is consistent).

---
Tags: logic, mathematical-foundations
---


# Question
Title: Interview q: Small possible length of stick from an array of stick lengths
I was asked this question in a phone interview recently and I bombed it completely. Zero clue how to approach it. I wasn't able to find any similar patterns on google-ing. Thought maybe folks here might be able to help?

---

**Statement**: Given `m` sticks with different lengths. Combine these sticks to form longer sticks with the same length. What’s the smallest possible length of these newly unified sticks?

Conditions:

* Must use all sticks
* `m < 50`
* max length of single stick less than 20

**Example**:

```
Input: 5 2 1 5 2 1 5 2 1
Output: 6
(Process: 1+5, 1+5, 1+5, 2+2+2)

```

---

```
Input: 3 3 3 2 2 5
Output: 9
(Process: 3+3+3, 2+2+5)

```

---

```
Input: 1 2 3 4 5
Output: 5
(Process: 2+3, 1+4, 5)

```

---

```
Input: 1 3 4 5
Output: 13
(Process: 1+3+4+5)

```

# Answer
> 1 votes
Pragmatic approach: If I were given this in an interview, I'd formulate it as an integer linear programming problem and let an off-the-shelf ILP solver look for a solution for me.

Theoretical approach: As Dmitry mentions, this problem is related to bin packing. (It's not identical because you require the bins to be full, whereas normal bin packing doesn't require that.) Wikipedia says that there is a pseudopolynomial time algorithm for bin packing when the bin size is fixed, so you might look up that algorithm and see if it can be modified to apply to your problem. You might also explore this paper:

Michel X. Goemans, Thomas Rothvoß. "Polynomiality for bin packing with a constant number of item types". SODA 2014.

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


# Question
Title: Distributed predicate computation on event stream
My question is actually a request for papers, articles, texts or books on the problem that I'm trying to solve on my work.

I'm working on a program that computes a predicate value (true or false) for a given object in a distributed system in which there is a stream of events that can change the object's attributes and, consequentially, the predicate value. Whenever the predicate value changes, the program must send a notification about this change.

For example, consider that there is an object `A` which has an attribute called `name` and consider that there is a predicate `P` which is true when the object's `name` is equal to `Jhon`. Each event in the stream has a timestamp and a value for the attribute name. So consider the following sequence of events:

```
e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 2 }
e3 = { name: Peter, timestamp: 3 }
e4 = { name: Doug, timestamp: 4 }
e5 = { name: Jhon, timestamp: 5 }

```

In this problem the events have a total order relation: If you have two events you always can say which one is the oldest of them.

Now, the events don't necessarily show up in the stream in the correct order according to its timestamp. Each event is unique to its timestamp, so there are no two or more events with the same timestamp for the same object. Also, the timestamps don't necessarily form a sequence that always increase by one: if we see `e1` with timestamp `1` and `e3` with timestamp `3`, it doesn't imply the existence of `e2` with timestamp `2`. There is no guarantee that all events will be received or when they will be received. It's part of the problem that we only know about the existence of the events that we see in the stream.

The real scenario is even worse: there are multiple computers parallelly processing this stream of events. However, for simplicity, I'll go further in this example considering only one computer.

If the events arrive and are processed in the order described above, then the notifications sent should be:

```
P(A) = true when e1 arrives
P(A) = false when e3 arrives
P(A) = true when e5 arrives.

```

That is the correct sequence of notifications because it respects the timestamp order. Now, imagine that the computer receives the events in the following order:

```
e1, e5, e2, e4, e3

```

A naive algorithm which doesn't consider the event's timestamp would send an incorrect sequence of notifications:

```
P(A) = true when e1 arrives
P(A) = false when e4 arrives

```

The algorithm that I'm working on considers the timestamps and infers when a notification should have been sent but was not. So when `e3` arrives it will notice that the notification `P(A) = true` for `e5` was not sent. This feels a bit like reinventing the wheel, though I'm not aware of any reading about this problem. I would like some references to this problem or to something similar, like some papers dealing with this kind of problem.

The real problem is quite more complex since it involves storing the predicate $\times$ object state in a database that works as a shared state between the computers processing the stream and I'm talking about thousands of events arriving per second so it's not possible to keep all events stored in some database.

Is there any literature about the problem that I have described? if so, could you give me links to it?

I would like to see a paper or a text that explains an algorithm that solves this problem and it would be even better if such paper provides proofs about the algorithm (e.g. correctness).

If such paper doesn't exist (I actually think that is the case), I would accept an answer that describes an algorithm and provides an argument or a proof about its correctness.

For this algorithm to be correct, it should always send the correct sequence of notifications no matter what order that events arrives. And the algorithm shouldn't keep all the received events in memory, because the real problem deals with too many events to save in memory or to store in a DB. It would be reasonable to keep some events in memory, preferably a fixed amount.

# Answer
> 1 votes
# Impossibility result #1: dropped events

The problem cannot be solved in general; there is no way to guarantee that your requirements will be met if some events are dropped (i.e., not received). Consider first this stream:

```
e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 4 }

```

where the algorithm sees both events. Next, consider this stream:

```
e1' = { name: Jhon, timestamp: 1 }
e2' = { name: Pete, timestamp: 2 }
e3' = { name: Jhon, timestamp: 3 }
e4' = { name: Jhon, timestamp: 4 }

```

where the algorithm sees only the events `e1'`,`e4'` (the other events are lost and never received). You might notice that what the algorithm sees in both cases is identical, so its outputs will be identical in both cases. However, the correct answer differs in these two cases, so there is no hope for an algorithm that always produces a correct output. (The correct response in the first case is to produce no notifications; the correct response in the second case is to produce two notifications, one to indicate that the predicate is false after receiving `e2'`, and one to indicate that the predicate is true after receiving `e3'`.)

It is not clear how to adapt the requirements to deal with this situation. The only plausible solution I can see is to say that the notifications that are produced should depend only on the received events, not on the events that are sent. This is equivalent to specifying that events cannot be dropped.

# Impossibility result #2: re-ordered events

You state that you must be able to handle re-ordered events, without storing all events in memory, and with arbitrary re-ordering. However, these requirements are incompatible: that is impossible to achieve. Consider a long sequence of events with timestamps 2,4,6,8,10,12,... At the end of the long sequence of events, if an event with an odd timestamp arrives, the only way to be sure you can handle it correctly is to store the entire history of past events (or past states of the object).

So, you're going to have to relax the requirement about re-ordering as well. Perhaps you're willing to store all events in memory forevermore. (If so, you have a solution.) Perhaps you are willing to impose a bound on re-ordering, e.g., no event will be delayed by more than 10 minutes. (If so, you only have to store history for the past 10 minutes, and everything older can be deleted.) Perhaps something else makes more sense in your particular situation.

But the one thing that is not an option is to impose all of the strong requirements stated in your question, and require an algorithm that is always correct.

---

I'm not aware of any literature on this and I don't particularly see any reason to expect there to be any. It's a very specific set of requirements, and it looks to me like the resulting task is either trivial or impossible to solve. Those usually aren't the kind of problems that tend to be studied in the literature. Perhaps you might be interested in persistent data structures, but that's just a fancy way of storing the entire history of events, which you said you want to do; and you don't need a fancy data structure to do that in your particular situation.

---
Tags: algorithms, reference-request, distributed-systems
---


# Question
Title: Maximum Chromatic number of Cayley Graphs with large degree
It is known that there does not exist a regular graph of order $n$ with clique size greater than $\lceil\frac{n}{2}\rceil$. My question pertains to Cayley graphs with large degree, say $\ge \frac{n}{2}$ and **not complete**. I think the maximum chromatic number is $\lceil\frac{3n}{5}\rceil$. As an example of a graph attaining the attaining the upper bound, we consider the complete graph with order divisible by $5$ and remove a $2$\- factor. The two factor we remove is the disjoint union of $\frac{n}{5}$ $5$-cycles. Then, the chromatic number is $\frac{3n}{5}$.

Are there any Cayley graphs with degree $\ge\frac{n}{2}$, and not complete, such that their chromatic number exceeds $\lceil\frac{3n}{5}\rceil$. And, also, are there other Cayley graphs with chromatic numbers between $\lceil\frac{n}{2}\rceil$ and $\lceil\frac{3n}{5}\rceil$

# Answer
> 2 votes
Erdős and Gallai showed in their paper Solution of a problem of Dirac then the chromatic number of a non-complete regular graph is at most $\frac{3}{5}n$.

Caccetta and Pullman constructed in their paper Regular graphs with prescribed chromatic number connected $k$-chromatic regular graphs on $n$ vertices for all $k \> 1$ and $n \geq \frac{5}{3}k$. You can check their construction to see whether it can be adapted to give Cayley graphs.

---
Tags: graphs, combinatorics, discrete-mathematics, colorings
---


# Question
Title: Context free grammar problem for number of a's is twice the number of b's
Can you to find for me a context free grammar for the following language?

$$\\{w\in\\{a,b\\}^\*: \\#\_a(w)=2\\#\_b(w)\\} $$

Here $\\#\_a(w)$ counts the number of $a$'s in $w$.

# Answer
Let $c(w)=2\\#\_b(w)-\\#\_a(w)$. Your language is exactly $\\{w\mid c(w)=0\\}$.

Now consider a string $w$ with $c(w)=0$ and $|w|\ge 2$. If we can split $w$ into three parts: $w=pms$ such that $c(p)$ and $c(pm)$ have different signs, i.e., $c(p)c(pm)\<0$, then there are two cases:

1. $c(p)\>0$ and $c(pm)\<0$. Note each time we append a character to string $x$, $c(x)$ is either increased by 2 or decreased by 1, so we can always split $m$ into two parts $m\_1m\_2$ such that $c(pm\_1)=0$.
2. $c(p)\<0$ and $c(pm)\>0$. In this case we can always split $m$ into two parts $m\_1m\_2$ such that either $c(pm\_1)=0$, or $c(pm\_1)=-1$ and $m\_2$ begins with $b$.

As a result, either $w=w\_1w\_2$ where $c(w\_1)=c(w\_2)=0$, or $w=w\_1bw\_2$ where $c(w\_1)=c(w\_2)=-1$.

If $w$ cannot be split into such three parts, then $w$ must be either $bw\_1aa$ or $aaw\_1b$ where $c(w\_1)=0$.

So, if we let $S\_-$ generate the language of strings where $2\\#\_b-\\#\_a=-1$, then we have the following grammar \begin{align} S&\rightarrow SS\mid S\_-bS\_-\mid bSaa\mid aaSb\mid\epsilon\\ S\_-&\rightarrow aS\mid SS\_- \end{align}
> 4 votes

# Answer
The following grammar generates the language $L = \\{ w \in \\{a, b\\}^\*\ | \ \\#\_a(w) = 2\\#\_b(w) \\}$.

```
S -> bSaa | baSa |
     aSba | abSa |
     aSab | aaSb |
     SS | ε

```

First, for every `b` introduced, 2 `a`'s are introduced. The location of an `b` could be before, between, or after both `a`'s.

Aside for the rule `S -> SS`, the grammar generates the string from outside in. Thus, there is no left or right recursion. So there are two places in each rule where recursion could happen: inside on the left and inside on the right.

Suppose there is a string $w = bxb \in L$. An example of such a string would be `baaaab`. Since $\\#\_a(w) = 2\\#\_b(w)$, then $\\#\_a(x) = 2(\\#\_b(x) + 2)$. There must exists at least one point in $x$ such that $x = x\_1x\_2$ where $bx\_1 \in L$ and $x\_2b \in L$. Hence the rule `S -> SS`.

**Edit:** The following rules must be added. See the accepted answer for a complete solution. These rules allows us to build string from inside out.

```
S -> QbQ
Q -> aS | SQ

```
> 1 votes

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


# Question
Title: Why selection sort is a stable sort algorithm?
One of the specifications of sort algorithms is stability, which means items with the same value in different indices are not replaced after applying sort algorithm. Why selection sort is unstable and can we make a sort algorithm stable by changing its swap condition?

# Answer
Just run an example. I will use colors to distinguish multiple elements with the same value and a $\mid$ to separate the unsorted part from the sorted part.

With the input

$\mid\color{blue}{2},3,\color{red}{2},1$

the first step will swap $\color{blue}{2}$ with $1$.

$1,\mid3,\color{red}{2},\color{blue}{2}$

The order of the $2$s changed. It continues

$1,\color{red}{2},\mid3,\color{blue}{2}$

$1,\color{red}{2},\color{blue}{2},\mid3$

So, the $2$s ended in a different order as they started.

To avoid this you can insert the smallest element of the unsorted part at the beginning of the unsorted part, instead of swapping it.

So, the first step would be

$1,\mid\color{blue}{2},3,\color{red}{2}$

The next step leaves it as it is.

$1,\color{blue}{2},\mid3,\color{red}{2}$

It continues with

$1,\color{blue}{2},\color{red}{2},\mid3$

To prove that this happens in general, observe that if an element with multiplicity is about to be moved, it must be the first element (from left to right) of that value appearing in the unsorted part. So, when it gets moved to the beginning of the unsorted part it continues appearing before all the elements of the same value appearing in the unsorted part and after all the elements of the same value that could already be in the sorted part.
> 2 votes

---
Tags: algorithms, sorting
---


# Question
Title: Is it decidable if a language described by number of occurences is regular?
It is known that the language of words containing equal number of 0 and 1 is not regular, while the language of words containing equal number of 001 and 100 is regular (see here).

Given two words $w\_1,w\_2$, is it decidable if the language of words containing equal number of $w\_1$ and $w\_2$ is regular?

# Answer
I and several colleagues answered this question here with a necessary and sufficient criterion for when the language $L\_{x=y}$ (all words having an equal number of occurrences of $x,y$) is regular. We also show the same for fewer $x$ than $y$, and more $x$ than $y$.

C.J. Colbourn, R.E. Dougherty, T.F. Lidbetter and J. Shallit. Counting Subwords and Regular Languages. Developments in Language Theory. DLT 2018. LNCS 11088. Springer. doi:10.1007/978-3-319-98654-8\_19
> 5 votes

# Answer
Given two words $w\_1$,$w\_2$, is it decidable if the language $L$ of words containing equal number of $w\_1$ and $w\_2$ is regular?

First some definitions:
*They could be made more concise, and the notations could be improved if they are to be used in proofs. This is only a first draft.*

Given two words $w\_1$ and $w\_2$, we say that:

* $w\_1$ *always occurs* with $w\_2$, noted $w\_1\triangleleft w\_2$, iff

1. for any string $s$ such that $s=xw\_2y$ with $\mid x\mid,\\, \mid y\mid\ \geq \mid w\_1\mid +\mid w\_2\mid$ and $|x|\_0,|x|\_1|,|y|\_0,|y|\_1| \geq 1$ there is another decomposition $s=x'w\_1y'$.
    *Note*: The condition that $x$ and $y$ each contain at least a 0 and a 1 is required by a pathological case (found by @sdcvvc): $w\_1=1^i0$, $w\_2=v1^{i+j}$ and $y\in1^\*$, and its symetrical variants.
    2. there is a string $s=xw\_2y$ with $\mid x\mid,\\, \mid y\mid\ \geq \mid w\_1\mid +\mid w\_2\mid$ such that there is at most one decomposition $s=x'w\_1y'$
* $w\_1$ *always cooccurs* with $w\_2$, noted $w\_1\triangleleft \triangleright\\,w\_2$, iff each always occur with the other,
* $w\_1$ and $w\_2$ *occur independently*, noted $w\_1\triangleright \triangleleft\\,w\_2$, iff neither one always occur with the other,
* $w\_1$ *always occurs $m$ times or more* than $w\_2$, noted $w\_1\triangleleft\_m w\_2$, iff for any string $s$ such that $s=xw\_2y$ with $\mid x\mid,\ \mid y\mid|\ \geq \mid w\_1\mid +\mid w\_2\mid$ there are $m$ other decompositions $s=x\_iw\_1y\_i$ for $i\in\[1,m\]$ such that $i\neq j$ implies $x\_i\neq x\_j$.

These definitions are constructed so that we can ignore what happens at the ends of the string where $w\_1$ and $w\_2$ are supposed to occur. Boundary effects at the end of the string have to be analyzed separately, but they represent a finite number of cases (actually I think I forgot one or two such boundary sub-cases in my first analysis below, but it does not really matter). The definitions are compatible with overlap of occurrences.

There are 4 main cases to consider (ignoring the symetry between $w\_1$ and $w\_2$):

1. $w\_1\triangleleft \triangleright\\,w\_2$
Both words come necessarily together, except possibly at the ends of the string. This concerns only pairs of the form $1^i0$ and $01^i$, or $0^i1$ and $10^i$. This is easily recognized by a finite automaton that only checks for lone occurences at both ends of the string to be recognized, to make sure there is a lone occurrence at both ends or at neither end. There is also the degenerate case when $w\_1=w\_2$: then the language L is obviously regular.
2. $w\_1\triangleleft w\_2$, but not $w\_2\triangleleft w\_1$
One of the 2 words cannot occur without the other, but the converse is not true (except possibly at the ends of the string). This happens when:

* $w\_1$ is a substring of $w\_2$:then a finite automaton can just check that $w\_1$ does not occur outside an instance of $w\_2$.
    * $w\_1=1^i0$ and $w\_2=v1^j$ for some word $v\in\\{0,1\\}^\*$, $v\neq01^i$: then a finite automaton check as in the previous case that $w\_1$ does not occur separated from $w\_2$. However, the automaton allows counting one extra instance of $w\_1$ that will allow acceptance if $w\_2$ is a suffix of the string. There are three other symetrical cases (1-0 symmetry and left-right symetry).
3. $w\_1\triangleleft\_2 w\_2$
One of the 2 words occurs twice in the other. That can be recognized by an a finite automation that checks that the smaller word never occurs in the string. The is also a slightly more complex variant that combines the two variations of case 2. In this case the automaton checks that the smaller string $1^i0$ never occurs, except possibly as part of $v$ in the larger one $v1^j$ coming as a suffix of the string (and 3 other cases by symetry).
4. $w\_1\triangleright \triangleleft\\,w\_2$
The 2 words can occur independently of each other. We build a generalized-sequential-machine (gsm) $G$ that output $a$ when it recognizes an occurrence of $w\_1$ and $b$ when recognizing an occurrence of $w\_2$, and forgets everything else. The language $L$ is regular only if the language $G(L)$ is regular. But $G(L)=\\{w\in\\{a,b\\}^\*\mid\ \mid w\mid\_a=\mid w\mid\_b\\}$ which is clearly context-free and not regular. Hence $L$ is not regular.
Actually we have $L=G^{-1}(G(L))$. Since regular languages and context-free languages are closed under gsm mapping and inverse gsm mapping, we know also that $L$ is context free.

One way to organize a formal proof could be the following. First build a PDA that recognizes the language. Actually it can be done with a 1-counter machine, but it is easier to have two stack symbols to avoid duplicating the finite control. Then, for the cases where it should be a FA, show that the counter can be bounded by a constant that depends only on the two words. For the other cases show that the counter can reach any arbitrary value. Of course, the PDA should be organized so that the proofs are easy enough to carry.

Representing the FA as a 2-stack-symbols PDA is probably the simplest representation for it. In the non-regular case, the finite control part of the PDA is the same as that of the GSM in the proof sketch above. Instead of outputting $a$'s and $b$'s like the GSM, the PDA counts the difference in number with the stack.
> 4 votes

---
Tags: regular-languages, undecidability
---


# Question
Title: is (infinitely often p) ∨ (infinitely often ¬p) valid?
i'm trying to prove every trace over PROP = {p} is a model of the formula. I am very stuck in figuring out a model pi that satisfies this formula, can anyone point me in the right direction?

# Answer
> 2 votes
The LTL formula for the given problem could be: $G(F(p)) \lor G(F(\lnot p))$. Consider a $\omega$-word $w = w\_1w\_2w\_3 \ldots$ over $\\{\\{\\}, \\{p\\}\\}$:

Let $w\_i = w\_iw\_{i+1}\ldots$ \begin{align\*} & \\; \\; \\; \\; \\; \\; \\; \\; \\; w \not\models G(F(p))\\ &\implies \exists i . w\_i \not\models F(p)\\ &\implies \exists i. \forall j \geq i . w\_j \models \lnot p\\ &\implies \exists i. \forall j \geq i . w\_j \models F(\lnot p)\\ &\implies \exists i. w\_i \models G(F(\lnot p))\\ &\implies w \models G(F(p)) \lor G(F(\lnot p)) \end{align\*}

Therefore, $G(F(p)) \lor G(F(\lnot p))$ is valid.

Note that this doesn't mean that $G(F(p)) \land G(F(\lnot p))$ is not satisfiable. For example, consider the word $w=\\{p\\}\\{\\}\\{p\\}\\{\\}\\{p\\}\\{\\}\ldots$

# Answer
> 0 votes
Consider a model $\pi$. Let $T$ be the set of times at which $p$ holds. If $T$ is infinite, then "infinitely often $p$" holds. If $\overline{T}$ is infinite, then "infinitely often $\lnot p$" holds. One of these two must hold, since there are infinitely many times.

# Answer
> 0 votes
You can use logical equivalences to show this is a valid LTL formula over models with the proposition $p \in \mathrm{Prop}$.

$$\begin{aligned} &\mathsf{G}\mathsf{F} p \vee \mathsf{G}\mathsf{F}\neg{}p\\ &= \langle \mathsf{GF}\varphi \vee \mathsf{GF}\psi \equiv \mathsf{G}(\mathsf{F}\varphi \vee \mathsf{F}\psi) \rangle\\ &\mathsf{G}(\mathsf{F} p \vee \mathsf{F}\neg{}p)\\ &= \langle \mathsf{F}\varphi \vee \mathsf{F}\psi \equiv \mathsf{F}(\varphi \vee \psi) \rangle\\ &\mathsf{G}\mathsf{F}( p \vee \neg{}p)\\ &= \langle\text{excluded middle} + p \in \mathrm{Prop} \rangle\\ &\mathsf{G}\mathsf{F}\top\\ &= \langle \mathsf{F}\top \equiv \top \rangle\\ &\mathsf{G}\top\\ &= \langle \mathsf{G}\top \equiv \top \rangle\\ &\top \end{aligned}$$

Most of the above equivalences are fairly easy to show by unfolding the semantics. The only annoying part is showing the $\mathsf{G}(\mathsf{F} \varphi \vee \mathsf{F}\psi) \Rightarrow \mathsf{G}\mathsf{F} \varphi \vee \mathsf{G}\mathsf{F}\psi$ direction of $\mathsf{G}\mathsf{F} \varphi \vee \mathsf{G}\mathsf{F}\psi \equiv \mathsf{G}(\mathsf{F} \varphi \vee \mathsf{F}\psi)$.

(see also A Calculational Deductive System for Linear Temporal Logic for a nice list of LTL theorems)

---
Tags: formal-methods, linear-temporal-logic
---


title: Greedy algorithm for vertex cover

text:
# Question
Title: Greedy algorithm for vertex cover
Given a graph $G(V, E)$, consider the following algorithm:

1. Let $d$ be the minimum vertex degree of the graph (ignore vertices with degree 0, so that $d\geq 1$)
2. Let $v$ be one of the vertices with degree equal to $d$
3. Remove all vertices adjacent to $v$ and add them to the proposed vertex cover
4. Repeat from step 1. until in $G$ there are only vertices with degree $0$ (no edges in the graph)

At the end the removed vertices are a vertex cover of the given $G(V, E)$, but is it a minimum vertex cover? Is there an example where the algorithm does not find a minimum vertex cover?

# Answer
> 6 votes
Start with a clique on the vertices $A,B,C,D$.

Connect $A,B$ to a new vertex $a$.

Connect $B,C$ to a new vertex $c$.

Connect $a,c$ to a new vertex $b$.

The vertex $b$ is the only one of degree 2, so your algorithm will start by adding $a,c$ to the vertex cover. The remaining graph consists of the clique $A,B,C,D$ and the isolated vertex $b$, so the algorithm will add 3 more vertices, ending up with a vertex cover of size 5.

In contrast, the 4 vertices $A,B,C,b$ cover all edges.

# Answer
> 4 votes
Take $k$ copies of $C\_4$, and attach them all to a single vertex. For instance, if $k=2$, you get the graph $X\_{27}$ shown below (courtesy of graphclasses.org):

A vertex cover of size $k+1$ can be obtained by selecting the vertex with maximum degree (let's call it $w$) and all vertices that are *not* adjacent to it.

The algorithm you propose might start with one of the vertices of degree 2 that are not adjacent to $w$ (say, $v$) and will add both neighbours to the cover, and then we repeat the process on the rest of the graph. In the case where $k=2$ above, you will end up with a cover of size $4$, whereas what I described in the previous paragraph yields a cover of size 3.

Side note: as counter-intuitive as this algorithm seems (in the sense that if I had to be greedy with respect to the degree, I'd naturally extract a maximum degree vertex at every iteration), it seems to have been proposed before. See this question on cstheory.

# Answer
> 3 votes
Using the notation $\[v\](n\_1,\ldots,n\_k)$ to mean that because of vertex $v$ we remove its neighbors $n\_1$ through $n\_k$, your algorithm might remove vertices in the following way: $\[2\](1,5,7), \[6\](8), \[3\](9,11), \[10\](12), \[4\](13,15), \[14\](16)$. This yields a vertex cover of size $10$.

However, $(2,6,8,3,10,12,4,14,16)$ is a vertex cover of size 9.

---
Tags: algorithms, complexity-theory, graphs, np-complete, vertex-cover
---


# Question
Title: Is the problem that determines whenever the word member $\in$ L(M) decidable or not?
Given a Turing machine M on alphabet {m,e,b,r} we're asked to determine if member $\in$ L(M). You must realize that M is not one specific machine and can be any turing Machine with the same alphabet. My goal is to determine whenever this problem is decidable or not.

My idea was to use mapping reducibility. The goal was to see if we can translate all problems from $A\_{TM}$ which is known to be undecidable into our current problem. This would make our current problem undecidable by contagion. However I'm struggling in doing so because I'm not sure if it's possible. $A\_{TM}$ is defined as a Turing machine M that accepts the word w.

Any help to get unstuck would be appreciated.

# Answer
> 1 votes
I would try it like this:

Reduction from $A\_{TM}$: Given TM $A$ und word $w$.

Use that to define a new machine $A'$ that works as follows:

1. Run like $A$ on input $w$
2. If $A$ rejects $w$, go into eternal loop.
3. If $A$ accepts, delete the band content and write "member"

---
Tags: formal-languages, turing-machines, undecidability, decision-problem
---


# Question
Title: Dynamic programming: speed of top down vs bottom up approaches
I have just completed a dynamic programming exercise on LeetCode (Coin Change). I tried a top down approach, but it failed for the larger inputs, whereas the bottom up approach worked for all inputs. Is the top down approach significantly slower because of the recursion?

I thought that bottom up approaches needed to compute everything: eg if we have a result array of size n, we run a loop from i=0 to i=n to find result\[i\], whereas the top down approach only computes relevant entries (we start at i=n then go down to 0, but we might skip some of the entries in between). So I thought the top down approach would be faster.

Or maybe there was just a bug in my top down approach.

Update: The problem on LeetCode is: " You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1: coins = \[1, 2, 5\], amount = 11 return 3 (11 = 5 + 5 + 1)

Example 2: coins = \[2\], amount = 3 return -1."

I defined an array result of size amount+1; result\[i\] is the minimum number of coins needed to reach amount i (with result\[0\] = 0).

If we have N coins, and coin j has value V\[j\], the recursion is: result\[i\] = 1 + minimum of result\[i-V\[j\]\] for all j=1...N (only the j for which i-V\[j\]\>=0)

I used a bottom up and top down approach to compute result\[amount\]:

If we don't have a coin of value 1, we won't need to compute result\[i\] for every i with a top down approach.

The time limit was exceeded for top down with this input: Coins: \[186,419,83,408\], Amount: 6249

# Answer
> 4 votes
Top down approach would be faster in cases where the no of entries that you have to compute are significantly less than than the total number of entries. Remember, recursive approach is slow than iterative approach because there is some overhead of function call too.

Top down approach fails in some cases because it works by recursion. In recursion you require space (stack space) for storing each function call. Now, if the depth of your recursion tree is large you may run out of stack space. In that cases iterative approach (like bottom to top approach) works because you can use memory from heap and running out of stack space is not an issue there.

# Answer
> 3 votes
Top-down is usually slower because function calls and cache lookups are relatively expensive. Bottom-up is essentially filling a table, which is also more cache-friendly.

# Answer
> -1 votes
What makes it slow isn't top down vs. bottom up. It will be slow if (a) you calculate the same intermediate result again and again, and (b) if you calculate results that in the end you don't need.

Typically top-down will tend to waste time by evaluating the same intermediate results again and again, unless you do something about it. And typically bottom-up will calculate intermediate results that you never need, unless you do something about it. Which is worse depends on the nature of the problem, and on your cleverness avoiding multiple or unnecessary evaluations.

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


# Question
Title: First-order mutual-recursive functions Turing-complete or incomplete?
Assume we have a C-like programming language with no pointer/heap semantics (i.e. there is no concept of memory; everything is on the stack). The only datatype supported is Integer, but suppose the Integer is infinitely large (i.e. without 32-bit, 64-bit, or any size limit).

Is it true that this language is Turing-*in*complete, but becomes complete if we add pointer/heap semantics (i.e. access to RAM-like memory)?

# Answer
> 2 votes
Roughly speaking, as a heuristic, if your language includes primitives of unbounded size as well as standard control structures (e.g., loops and conditional statements), the language is likely to be Turing complete. (Credits: I'm just expanding on Dmitry's observation.) I'll show a few examples below.

If your language doesn't have loops, you can simulate them with recursion.

# Linked lists

If your language includes linked lists, it will be Turing-complete.

In particular, you can encode a Turing machine with two linked lists. You split the tape into two pieces, the part to the left of the head and the part to the right of the head. Let $L$ be a linked list of the symbols on the tape to the left of the head, and $R$ the symbols to the right. The linked list should start with the symbols closest to the head and go outward.

Now you can simulate each of the individual operations of the Turing machine using a few lines in your programming language. For instance, shifting the tape head to the right can be done by popping an item $x$ from the front of $L$, then pushing $x$ onto the front of $R$. The finite-state control works on finite data and so can be expressed as a finite number of simple operations. Now put an infinite loop around this, with each iteration of the loop simulating one step of the Turing machine, and you have built an interpreter for a Turing machine in your language.

# Bigints

If your language includes bigints (i.e., integers that can be of unbounded size) and basic operations on them (e.g., add, multiply, compare, divide), then it will be Turing-complete.

In particular, you can simulate linked lists of items over a fixed alphabet using bigints. Suppose you want to encode a linked list of bits. Then you can encode this as a bigint by treating the sequence of bits in the linked list as the binary representation of an integer (the least significant bit is the first bit in the linked list, and so on). Basic operations on the linked list can then be translated into operations on the integer. For instance, popping a bit from the head of a linked list can be expressed as $b := L \bmod 2, L := (L-b)/2$; pushing a bit can be expressed as $L := 2L+b$; and so on. More generally, if you have a linked list where each item is in the range $\\{0,1,\dots,k-1\\}$ (e.g., a tape alphabet of size $k$), then this can be viewed as an integer in base $k$. There are some details -- for finite lists, you probably want to have one reserved symbol to indicate the end of the list -- but they don't change the general picture.

Now you can use this to simulate linked lists, and then use the construction above to simulate a Turing machine.

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


title: Context switch in an Text Editor

text:
# Question
Title: Context switch in an Text Editor
I am new to operating systems and have been wondering about this.

Consider a normal text editor, and it's process running in the CPU. Since text editors include IO operations, do the process keep switching it's state from **Wait** -\> **Run** -\> **Wait** etc. While the user is typing and the same is reflected on the screen or some processing such as auto-correct etc. And while the current process is in **Wait**, other process is in **Run** state (Context Switching).

OR

Text - Editor itself creates multiple processes, one for handling IO operation and other for processing the data and it is being established through Inter-Process Communication.

New to OS and stuck with this, thank you for any kind of help .

# Answer
There is no single answer: you could build a text editor in any way you want.

One simple architecture for a text editor is to have a single process, which blocks on I/O when it is waiting for the user to provide input. But it's also possible for a text editor to be built in a multi-threaded way with multiple processes, e.g., spawning one thread to do spellchecking in the background or anything else.
> 1 votes

---
Tags: operating-systems
---


title: Definition of 'Record'

text:
# Question
Title: Definition of 'Record'
Given the definition of 'record': *"a collection of field values for a given entity"*, is this a set of field values for ALL the fields of the entity, or only one particular field \[so that you get a different set for each field\]? Also, is the relationship b/w a field & field value essentially equivalent to a function?

**NOTE: Total beginner learning data struc. & algos.**

# Answer
> 1 votes
All of the fields. For instance, here is an example of a record:

```
{name: D.W., favoritecolor: blue}

```

You can think of a record as a function from field (key) to value. For instance, the above would correspond to a function $f$ defined by $f(\text{name})=\text{D.W.}$, $f(\text{favoritecolor})=\text{blue}$.

---
Tags: data-structures
---


# Question
Title: Algorithm to determine if a top-down non deterministic tree automata accepts some tree?
Given a non-deterministic top-down tree-automata. is there an algorithm, that can determine if there exists any tree that accepted by this automaton? if so, what is the most efficient algorithm known?

Thanks.

# Answer
> 0 votes
Yes, you can do it in linear time. Associate to each pair of a state $q$ a boolean variable $x\_q$; the intended meaning is $x\_{q,s}$ should be true if there exists a tree that is accepted by the automaton if we start with state $q$ at the root. Then, each transition rule of the automaton corresponds to a Horn clause on these boolean variables. For instance, the transition rule $f(q\_1,\dots,q\_n) \to q'(f)$ corresponds to the Horn clause $(x\_{q\_1} \land \cdots \land x\_{q\_n}) \implies x\_{q'}$. Now, solve the associated HornSAT problem using any standard algorithm to find the minimal satisfying assignment to all of these clauses; this can be done in linear time. If you find any final state $q$ of the automaton such that $x\_q$ is set to true by this assignment, then the answer is yes, there exists a tree that's accepted by this automaton; otherwise, the answer is no.

---
Tags: tree-automata
---


# Question
Title: Minimum vertex cover algorithm with linear programming
Consider the following algorithm: given a graph $G$ with $n$ vertices, set up a linear programming problem *LP* where there is a variable $x\_i$ for each vertex $v\_i$ of $G$, each variable can take value $\geq 0$, for each edge $v\_av\_b$ of $G$ set the constraint $x\_a+x\_b\geq 1$. The objective function is $\min\sum\limits\_{1}^{n}{x\_i}$. Find the variable (or one of the variables) $x\_i$, among the variables not set to $0$, that set to $0$ gives the minimum value of the objective function. Add the constraint $x\_i=0$ to *LP*. Repeat until the optimal solution of *LP* is integer (that is each variable takes value in $\left\\{0; 1\right\\}$).

I am looking for a graph where the vertices associated to the variables that take value $1$ in the final optimal solution of *LP* are not a minimum vertex cover of $G$ (if it exists).

# Answer
> 1 votes
Consider the graph

```
  2-4---7
 /  |\ /|
1   | × |
 \  |/ \|
  3-5---6

```

Setting $x\_1,x\_2,x\_3,x\_6$ or $x\_7$ to 0 gives your LP a value of 4, while setting $x\_4$ or $x\_5$ to 0 gives your LP a value of 5. However, if you set $x\_1=0$, you will finally get a vertex cover of size 5, while the optimal vertex cover is of size 4.

---
Tags: algorithms, graphs, optimization, linear-programming, vertex-cover
---


# Question
Title: Are there any known W[3] or W[3]-hard problems?
We are currently working on a variant of domination parameter and we have shown that it is in W\[3\] with regard to parameterized complexity. To show it is W\[3\]-complete, we must show the problem is W\[3\] hard i.e, reduce an already known W\[3\] hard problem to ours. But unlike W\[1\] and W\[2\], where many famous problems are proved those classes, surprisingly we have not come across a single problem that is W\[3\] hard and not even in just W\[3\]. Of course there is the general W\[t\] case which we can go for, but any result for W\[3\] in particular would help a lot.

# Answer
> 6 votes
There are a few examples in the answer to Natural complete problems in higher levels of the W-hierarchy. In particular, the W\[3\]-complete problem **$p$-HYPERGRAPH-(NON)-DOMINATING-SET** may be useful for your proof.

Given that the linked question is now almost 6 years old, you'd perhaps expect some more examples to pop up by now. However, I couldn't find anything concrete in a quick literature search. The closest thing I could find was *Separating sets of strings by finding matching patterns is almost always hard* (2017) by Lancia et al., where they **conjecture** that the problem they call **PATTERN IDENTIFICATION** is W\[3\]-complete for a particular parameter, but this conjecture is probably not very useful for your proof. I do note that I'm not an expert in this field, so there may be some more recent results out there I simply wasn't able to find.

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


title: Is unary machine code a concept?

text:
# Question
Title: Is unary machine code a concept?
Please assume for the sake of this session that humans can fluently read and understand *machine languages* and time isn't a problem in that regard.

I, not a computer scientist, would at least theorize that a unary machine language is possible but might just be much "less comfortable" than binary machine language.

Is unary machine code a concept?

# Answer
> 0 votes
Yes, you could express machine code in unary. How do I know? Well, anything that can be represented in binary, can be represented in unary. Machine code can be represented in binary (as a binary string of bits)... therefore it can be represented in unary (as a unary string).

It wouldn't be useful or practical to do so. It's not just less comfortable; it's much worse than that. Conversion to unary involves an exponential increase in size (a string that takes $n$ bits in binary would take $2^n$ symbols in unary), so it would be totally infeasible in practice. But in theory, you can imagine it; there's no barrier in principle.

---
Tags: communication-complexity
---


# Question
Title: How does each element in the output array of a DFT correspond to a specific frequency?
I have a basic understanding of the Fourier Transform, though I'm trying to use it in a program and I'm confused on the specifics. Based on source code I can find online, the DFT takes a set of samples/numbers, performs a summation for each term, and returns a set of these summations which is the same size as the input set. Suppose I have a periodic function. As I understand it, the output array should contain the amplitudes/weights of each frequency which sum to that function. What I can't figure out is how each frequency is encoded in the array as just an index. In each example I read, we just assign a summation at each iteration of the inner loop to the next consecutive index in the output array. How are these indices indicative of which frequency they correspond to?

I'm attaching the source code I'm referencing to the bottom of this in case the website I linked to ever goes down.

```
import cmath
def compute_dft_complex(input):
    n = len(input)
    output = []
    for k in range(n):  # For each output element
        s = complex(0)
        for t in range(n):  # For each input element
            angle = 2j * cmath.pi * t * k / n
            s += input[t] * cmath.exp(-angle)
        output.append(s)
    return output

```

# Answer
Let us denote the input signal by $x(0),\ldots,x(n-1)$ and the output signal by $y(0),\ldots,y(n-1)$. Your program is using the following formula: $$ y(k) = \sum\_{t=0}^{n-1} e^{-2\pi i tk/n} x(t). $$ We also have $$ x(t) = \frac{1}{n} \sum\_{k=0}^{n-1} e^{2\pi i tk/n} y(k). $$ In other words, any input signal can be represented as a linear combination of the functions $\chi\_k(t) = e^{2\pi i tk/n}$, and the output signal gives the coefficients of this representation (up to a normalization factor).

The parameter $k$ is analogous to frequency. You can see the analogy more clearly if you write $$ \chi\_k(t) = \cos \frac{2\pi k}{n} t + i \sin \frac{2\pi k}{n} t. $$
> 1 votes

---
Tags: algorithms, fourier-transform
---


title: Lambda Calculus Conversion

text:
# Question
Title: Lambda Calculus Conversion
How can I take a Haskell data type or function (eg fold, list, String, zip) and convert or translate it to a lambda calculus abstraction? Example: If sum computes a sum of all elements in a list, and :type sum = Num a =\> \[a\] -\> a.

```
    sum []     = 0
    sum (x:xs) = x + sum xs

```

How do I take this information to translate it to a lambda calculus expression, or rather an abstraction?

I have tried to find guides online but they just give me the answers. I want to know how to actually make the conversion/translation from a Haskell function like add, sum, map, fold, etc. to a lambda calculus abstraction.

# Answer
The thing to notice here is that your function `sum` is defined on lists, which are inductively defined. Theoretically, the inductive definition of a list defines for every type T a term

```
match_list :: T -> (a -> [a] -> T) -> ([a] -> T)

```

satisfying the property

```
match_list s t [] = s
match_list s t (x::xs) = (t x xs)

```

in addition, defining a recursive function requires an untypable fixed-point combinator `fix` satisfying the property

```
fix F = F (fix F)

```

so combining the two, we could write your definition by first defining

```
F :: ([a] -> a) -> ([a] -> a)
F := λ f -> match_list 0 (λ x -> (λ xs -> x + f xs))

```

and then

```
sum := λ x -> (fix F) x
     = λ x -> (fix (λ f -> match_list 0 (λ x -> (λ xs -> x + f xs)))) x

```

To convince oneself that this works, let's try this on the example

```
sum [1,2] = (fix F) [1,2]
          = (F (fix F)) [1,2]
          = (λ f -> match_list 0 (λ x -> (λ xs -> x + f xs))) (fix F) [1,2]
          = match_list 0 (λ x -> (λ xs -> x + ((fix F) xs))) [1,2]
          = 2 + ((fix F) [1])
          = 2 + ((F (fix F)) [1])
          = 2 + ((λ f -> match_list 0 (λ x -> (λ xs -> x + f xs))) (fix F) [1])
          = 2 + (match_list 0 (λ x -> (λ xs -> x + ((fix F) xs))) [1])
          = 2 + (1 + ((fix F) []))
          = 2 + 1 + ((F (fix F)) [])
          = 2 + 1 + ((λ f -> match_list 0 (λ x -> (λ xs -> x + f xs))) (fix F) [])
          = 2 + 1 + (match_list 0 (λ x -> (λ xs -> x + (fix F) xs)) [])
          = 2 + 1 + 0

```

This is theoretically what would go on in a purely functional language (for example the *untyped* lambda calculus), however in languages like haskell, lisp, or ocaml (I am unaware of inductive datatypes in python), the terms `match_list` and `fix` are "internal" constructs and are not explicit terms in the language.
> 2 votes

# Answer
Try this.... It should help build up the intuition step by step

http://pages.cs.wisc.edu/~horwitz/CS704-NOTES/2.LAMBDA-CALCULUS-PART2.html

Alternatively since it's not really clear what you mean, maybe an example of what kind of abstraction you want for something simpler than sum?
> 0 votes

---
Tags: lambda-calculus, functional-programming, python, haskell, lisp
---


# Question
Title: Why decision tree method for lower bound on finding a minimum doesn't work
(Motivated by this question. Also I suspect that my question is a bit too broad)

We know $\Omega(n \log n)$ lower bound for sorting: we can build a decision tree where each inner node is a comparison and each leaf is a permutation. Since there are $n!$ leaves, the minimum tree height is $\Omega(\log (n!)) = \Omega (n \log n)$.

However, it doesn't work for the following problem: find a minimum in the array. For this problem, the results (the leaves) are just indices of the minimum element. There are $n$ of them, and therefore the reasoning above gives $\Omega(\log n)$ lower bound, which is obviously an understatement.

My question: why does this method works for sorting and doesn't work for minimum? Is there some greater intuition or simply "it just happens" and we were "lucky" that sorting has so many possible answers?

I guess the lower bound from decision tree makes perfect sense: we do can ask yes/no questions so that we need $O(\log n)$ answers: namely, we can use binary search for the desired index. My question still remains.

# Answer
> 1 votes
Interesting question!

The way I understand this is that on sorting it happens that one comparison allows you to discard approximately a half of the possible answers. However on the case of the minimum, one comparison allows you to discard only one possible answer in the worst case. Therefore a proper decision tree for the problem of finding the minimum element has linear height.

It happens in general that the case of sorting is kind of the best we can hope for, as a single comparison can never discard more than half of the answers in the worst case. Think about it this way: if an answer to a comparison were to discard more than half of the possible answers, then the opposite answer to the comparison would discard less than half, and thus one could not expect to discard more than half in the worst case.

That way, we know that for any decision tree with $n$ leaves we can't hope for a height of less than $\log n$ (this is actually true for every kind of tree, because of the same reason), however on certain decisions trees each query is not as helpful and thus the trees get way taller.

I don't know if this actually answers your concern though.

# Answer
> 1 votes
In the comments I said that $n$ is the number of different possible outcomes of a minimum algorithm and that this is only a lower bound for the number of leaves of the decision trees of the comparison-based minimum algorithms (in which nodes represent the comparisons and edges the results of those comparisons). This is an application of Lemma 1 here, which then implies the bound that you got on the height of the tree. This is Lemma 2 in the linked document. They call this an *information theoretic argument*.

The reason why it gives such a conservative lower bound for the height of the trees, is that the bound on the number of leaves is too conservative. So, Lemma 1's fault of not being strong enough.

---

I was curious to see if this method could give a better lower bound if one manages to bound better the number of leaves. For this what we need to do is to have some control on the number of times an outcome of the algorithm is repeated across the leaves.

Suppose a comparison-based algorithm for minimum has decision tree with a maximum of $K$ leaves corresponding to the same outcome.

Then the tree has at most $Kn$ leaves and at most height $\log(n)+\log(K)$. If $n\>2(\log(n)+\log(K))$, then none of the paths from root to leaf compares all elements of the array. Since the height of the path is bounded by $\log(n)+\log(K)$, then there are at most that many comparisons in the path. Each comparison looks at $2$ elements, so at most $2(\log(n)+\log(K))$ are inspected. Then we can keep the elements compared in one of the paths fixed and make the other elements smaller than the element that that path chooses as minimum. This input would result on the same output from the algorithm but have a different minimum. So, the algorithm must be incorrect. So, the inequality above must be false. This argument has the flavor of the *adversary argument*, which applied directly gives the best lower bound for this problem.

Hence $n\leq 2(\log(n)+\log(K))$. From this we get that $\log(K)\geq n/2-\log(n)$, or in other words

$$K\geq 2^{n/2-\log(n)}$$

Now, this tells us that the decision trees for these algorithms will always have at least $K+(n-1)\geq 2^{n/2-\log(n)}+(n-1)$ leaves. So, their height is at least $$\log\left(2^{n/2-\log(n)}+(n-1)\right)\geq n/2-\log(n)$$

---
Tags: sorting, lower-bounds, decision-tree
---


title: optimizing for loops

text:
# Question
Title: optimizing for loops
Disclaimer: I'm not a compiler expert. I'm simply curious and come seeking enlightenment.

I've seen people claim that -- for efficiency -- `for` loops should generally use a zero comparison for termination. So rather than:

```
void blink1(int n) {
    for (int i=0; i<n; i++) {
        blink_led();
    }
}

```

you should write:

```
void blink2(int n) {
    for (int i=n; i>0; i--) {
        blink_led();
    }
}

```

I thought that was a little silly: why put the burden on the human if a compiler could interpret both cases as "blink\_led() n times"?

But using Mr. Godbolt's Compiler Explorer, I now think I'm wrong. For all the compilers I tried, the "compare against zero" always produced a shorter loop. For example, x86-64 gcc 10.2 with -O3 optimization produced the following inner loops:

```
blink1:
    ...
.L3:
        xor     eax, eax
        add     ebx, 1
        call    blink_led
        cmp     ebp, ebx
        jne     .L3

```

vs

```
blink2:
    ...
.L12:
        xor     eax, eax
        call    blink_led
        sub     ebx, 1
        jne     .L12

```

### So here's the question

This seems like such a common case.

Why can't (or why doesn't) the compiler notice that the effect of the `for` loop is simply *"do this thing N times"* -- whether counting up or counting down -- and optimize for that?

# Answer
What you read is total nonsense, except for the most primitive of compilers. First, comparison with an integer is as fast, possibly even faster than comparison with a constant. Second, a good optimising compiler will take a loop written using some common pattern and turn it into the best possible code; it may not recognise your obfuscated pattern and produce less good code for it.

And lastly, you shouldn’t replace readable with unreadable code unless there is an actual need for it. If you spend an hour making the change, it needs to produce 20 hours saved CPU time at least. When you are at that level, better algorithms are very likely to give better savings.
> 2 votes

# Answer
I think I agree mostly with @gnasher729, but those people what worry about "efficiency" would criticize using the for loop at all -- the "i" variable doesn't add anything ...

Why not:

```
void blink3(int n) {
    while (n-- > 0) {
       blink_led();
    }
}

```

I've added the "\> 0" for a couple of reasons: 1) just in case somebody asks for a NEGATIVE amount of blinking, don't want to roll backward for 2 billion times. 2) it's a bit more obvious to the unitiated (maybe).

By the way, in contrived example, the "blink\_led()" function is weird and fishy -- gonna probably wait around to be able to see it go on, then off. So "efficiency" is a bit off the table.

But, in general, for most things, efficiency is mostly about how quickly it can be coded and also (more importantly) how quickly it is understood.
> 0 votes

---
Tags: optimization, compilers
---


# Question
Title: Estimating size of state space search problem
Im currently enrolled in an AI course and we are starting with state space search problems. My professor always seems to ask, given a certain problem, what is the estimate size of the state space? It's been 3 years since ive taken a course in discrete math which is the type of question I am asking.

How can I use things like branch factor and depth to estimate state space?

# Answer
> -1 votes
So lets take an 8 queens problem. Intially the **size of state** is **64C8** where 64 is the number of squares in a chess board and 8 is the number of queens that can be placed.

**Now** lets say, you can only put one queen in each column so that's only 8 squares available. This reduces the **branching factor** from 64 to 8. Now the **size of state** is **8C8** only.

Now lets say, you can only use 2 queens instead of 8. This reduced the **depth** from 8 to 2. So in this case instead of being 8 queens , now it's going to be a 2 queens problem. So that changes the **size of state** from **8C8** to **8C2**. Cheers man.

---
Tags: search-algorithms, search-trees, counting
---


# Question
Title: Shortest Path in a Directed Acyclic Graph with two types of costs
I am given a directed acyclic graph $G = (V,E)$, which can be assumed to be topologically ordered (if needed). Each edge $e$ in G has two types of costs - a nominal cost $w(e)$ and a spiked cost $p(e)$. I am also given two nodes in $G$, node $s$ and node $t$.

The goal is to find a path from $s$ to $t$ that minimizes the following cost: $$\sum\_e w(e) + \max\_e \\{p(e)\\},$$ where the sum and maximum are taken over all edges of the path.

Standard dynamic programming methods show that this problem is solvable in $O(E^2)$ time. Is there a more efficient way to solve it? Ideally, an $O(E\cdot \operatorname{polylog}(E,V))$ algorithm would be nice.

---

This is the $O(E^2)$ solution I found using dynamic programming, if it'll help.

First, order all costs $p(e)$ in an ascending order. This takes $O(E\log(E))$ time.

Second, define the state space consisting of states $(x,i)$ where $x$ is a node in the graph and $i\in \\{1,2,...,|E|\\}$. It represents "We are in node $x$, and the highest edge weight $p(e)$ we have seen so far is the $i$-th largest".

Let $V(x,i)$ be the length of the shortest path (in the classical sense) from $s$ to $x$, where the highest $p(e)$ encountered was the $i$-th largest. It's easy to compute $V(x,i)$ given $V(y,j)$ for any predecessor $y$ of $x$ and any $j \in \\{1,...,|E|\\}$ (there are two cases to consider - the edge $y\to x$ is has the $j$-th largest weight, or it does not).

At every state $(x,i)$, this computation finds the minimum of about $\deg(x)$ values. Thus the complexity is $$O(E) \cdot \sum\_{x\in V} \deg(x) = O(E^2),$$ as each node is associated to $|E|$ different states.

# Answer
> 2 votes
This answer is mostly based on my earlier comments.

It is unlikely that there is an algorithm that works in $O(|E|^{2 - \varepsilon})$ time for *all* graphs. It is still possible that there are faster algorithms for dense graphs ($E = \Omega(V^2)$) or somehow dense graphs ($E = \Theta(V^\alpha)$ for some $\alpha \> 1$), but an algorithm that works in $O(|E|^{2 - \varepsilon})$ time for sparse graphs ($E = O(V)$) would contradict so called **$k$-cycle hypothesis** (you can check this paper and this paper for more details on the statement and its applications to lower bounds for dynamic shortest path and other graph problems).

## The reduction

I prefer to state the $k$-cycle hypothesis in the following way, which is equivalent to the way it is usually stated (for more details, see the last section):

> For any $\varepsilon \> 0$, there is a positive integer $k$, such that there is no $O(|E|^{2 - \varepsilon})$ algorithm for checking whether there is a closed walk of length exactly $k$ in the given directed graph.

Let's reduce the problem of finding a closed walk of length $k$ in a given directed graph $G(V,E)$ to the problem in question for a slighty larger graph. Construct a new graph $H$ ($H$ will be a DAG), whose vertex set consists of a *source vertex* $s$, a *sink vertex* $t$ and vertices $(v, \ell)$ for each $v \in V, \ell \in \[1, k + 1\]$ ($k + 1$ *layers*, each being a copy of $V$).

Each edge $u \to v$ of the original graph splits into $k$ edges in $H$: $(u, \ell) \to (v, \ell + 1)$ for each $\ell \in \[1, k\]$, with each of those edges having $w$ and $p$ parameters set to $0$. Also, there will be $|V|$ edges from the source to the first layer ($s \to (v, 1)$ with parameters $w := v$ and $p := 3|V| - 2v$ for each $v \in V$; here I assume that vertices of $G$ are numbered from $0$ to $|V| - 1$). Similarly, there will be $|V|$ edges from the last layer to $t$ ($(v, k + 1) \to t$ with $w := v$, $p := 3|V| - 2v$). Clearly, $H$ has $(k+1)|V| + 2$ vertices and $2|V| + k|E|$ edges.

Now, each $s \to t$ path $s \to (v\_1, 1) \to (v\_2, 2) \to \ldots (v\_{k + 1}, k + 1) \to t$ in $H$ corresponds to a walk of length $k$ in the original graph ($G$). The corresponding walk is closed if and only if $v\_1 = v\_{k + 1}$. The main idea is that we have chosen the parameters $w$ and $p$ to ensure that paths with $v\_1 = v\_{k + 1}$ have the smallest possible cost.

Indeed, the cost of $s \to (v\_1, 1) \to \ldots \to (v\_{k + 1}, k + 1) \to t$ path in $H$ is $v\_1 + v\_{k + 1} + \max(3|V| - 2v\_1, 3|V| - 2v\_{k+1}) = v\_1 + v\_{k + 1} + 3|V| - \min(v\_1, v\_{k + 1}) = 3|V| + |v\_1 - v\_{k + 1}|$. Hence, the shortest $s \to t$ path in $H$ has cost $3|V|$ if and only if the original graph $G$ contained a closed $k$-walk. Therefore, under k-cycle hypothesis, there is no $O(|E|^{2 - \varepsilon})$ algorithm for problem in question.

## Can we do better for dense graphs?

Honestly, I don't know. Proving lower bounds for dense graphs seems to be difficult, because the problem is strictly simpler that dynamic shortest paths. Hence, the only simple "vector of attack" is to try using the same methods that are used for dense graphs and hope that they will work even for the simpler problem. Maybe future answerers will be more succesful here?

As for faster algoritms, an existence of $O(VE)$ algorithm sounds plausible. The only thing that I managed to come up with is the following algorithm, whose complexity is a bit hard to estimate, but I suspect that it still should take $\Omega(E^2)$ time in the worst case:

> Find some shortest ($s \to t$)-path in the original graph with respect to sum of $w$'s, breaking ties by minimizing the maximum of $p$'s (it is possible to do this by dynamic programming in $O(|E|)$ time). Let's say that the largest value of $p$ for edges on the chosen path is $P$. Then, all edges $e$ with $p\_e \geqslant P$ can't appear in a path with a smaller cost (because otherwise the chosen path was not shortest with respect to sum of $w$'s). Therefore, we can delete all such edges and repeat the process.

## Why did I choose an uncommon statement of k-cycle hypothesis?

Usually, it is stated in the terms of finding a *simple cycle* of length $k$, but for fixed $k$ finding a simple cycle can be reduced to finding a closed walk in (larger) graph by known techniques like color coding. All these techniques require blow up the size of the graph exponentially with respect to $k$ (otherwise we could solve Hamiltonian Cycle in subexponential time), but we can handle this, because $k$ is fixed and small.

Intuitively speaking, for small $k$, the "main problem", asymptotically speaking, is not ensuring that all vertices of the cycle are different, but *remembering where the cycle started*.

Because the problems are equivalent, I chose the one which is easier to work with. Moreover, apart from having a *theoretical* reduction, we also have a *practical* reduction now. For example, if we assume that there is no way to check whether a graph with $10^6$ edges has a closed walk of length $k = 6$ in under $10$ minutes on a normal computer (I would say, that this is a huge understatement, considering the large constant factors of graph searches; though I would be very positively surprised to be wrong), then there is no way to solve the problem in question for graphs with $10^6 / (k + 2) = 1.25 \cdot 10^5$ edges in under $10$ minutes, e.t.c. The point is, that the constant factors involved in the reduction are reasonably small.

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


# Question
Title: Remove features with too little variation
I have the following messy chart;

As you can see some features are very stable through the time series (post-2011) like Extraversion. Is there an algorithm to remove features that do not have much variation compared to the other features?

# Answer
Step 1. Identify a measure of variation for a feature.

Step 2. Remove all features for which this measure is below some threshold (or is below that of msot other features).

There are many measures of variability that you could use in step 1: standard deviation, interquartile range, range (max minus min), median absolute deviation, and more. Any of these are probably reasonable.
> 2 votes

---
Tags: algorithms, time-series-analysis
---


# Question
Title: Begin with AWS or Azure ML Course? (or something else?)
I tend to see a lot of ML/AI/DL courses everywhere. Having no background in either of these, I am confused about what to do and where to begin. I was suggested to have a look into the Stanford Andrew Ng ML course. That seems pretty outdated now. I see Python libraries being used always everywhere.

The following two courses came to my notice :

1. ML with Azure
2. AWS ML Program

Apart from that, there are several Andrew Ng/Coursera courses available on the internet. I would be equally happy to check out books instead of/alongside (an) online course(s). Suggestions would be appreciated.

# Answer
I'm currently doing the Andrew Ng course and I'm enjoying it even if it's old. There's a lot of concepts in it that are still used today.

Although he uses Octave/ Matlab instead of Python I would still recommend this course not only because it's basically recommended all over the internet but this guy knows his stuff. There's a free **18 hour** video playlist on Youtube that you can check if you feel like not paying for the **54 hour** one on Coursera. It covers just as many topics.

As for books I would recommend **An Introduction to Statistical Learning** if you're just starting out and **Elements of Statistical Learning** if you're a bit more advanced.

Again this is from personal experience.
> 0 votes

---
Tags: artificial-intelligence
---


# Question
Title: Books for the Mathematical Theory of AI/ML
I am interested in the mathematical foundations of Artificial Intelligence and Machine Learning. Are there any books which will describe and present the mathematical foundations in detail? I am not that interested in coding and would prefer a text which is heavy in mathematics and the theory.

# Answer
My favorite is Understanding Machine Learning: From Theory to Algorithms. It’s presentation is very probability oriented and introduces concepts in a very concise, yet insightful way. It covers the foundations of a lot of Statistical Learning Theory and thanks to the rigorous introduction, I found it is easy to build on certain directions that interest me.
> 4 votes

# Answer
I usually recommend **An Introduction to Statistical Learning** if you're starting out and **Elements of Statistical Learning** if you're a bit more advanced. They are both equally pleasing and completely **free**.
> 1 votes

---
Tags: machine-learning, reference-request, artificial-intelligence
---


# Question
Title: How can I treat a problem like a search problem in AI?
I'm a CS student and I'm trying to understand the **searching algorithms** used in AI.

My problem is that I don't really understand how to **treat a problem like a search problem**. I don't know which would be the **first steps** for solving it and how shall I choose the right algorithm for that.

For example, I have a problem like that:

*n vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of an n×n n grid. The vehicles must be moved to the top row but in reverse order; so the vehicle i that starts in (i, 1) must end up in (n−i+ 1, n). On each time step, every one of the n vehicles can move one square up, down, left, or right, or stay put; but if a vehicle stays put, one other adjacent vehicle (but not more than one) can hop over it. Two vehicles cannot occupy the same square.*

I understood that the start state of each car is the bottom row, each car has at most five possible moves from any position and if each car has a 3x3 grid of empty space around it, then all five moves are possible.

My idea is that I should treat the car route like a tree where each node is a position of the car at a time, but I don't know how correct is it.

Which would be my first steps regarding this problem to solve it like a search problem?

I would be very thankful for any advice!

# Answer
> 2 votes
To treat it as a search problem, you should have a decision tree in mind. In your example, the each node's degree would be the total combination of possible movements for each car (except for the combination in which all cars stay put). Then, each edge of the decision tree would represent a transition from one timestep to the next and each node would represent the positions of all the vehicles at that timestep. One can use the current depth of the tree during the search process to track the current timestep. Using this setup, there are many possible tree search algorithms that may suffice for your problem.

# Answer
> 0 votes
So the way I usually simulate these kind of trees on paper is that I make a node **for every move**. So from **starting**(parent) node I make one **node**(child) for **Up**, one node for Down and you know the rest.

Once it moves to that new space **reevaluate** again and make more nodes using that new space in the grid. Hope this helps!

---
Tags: artificial-intelligence
---


# Question
Title: Find Index In Sorted Array Such That A[i] = C1 * i + C2
I'm already know that there is an algorithm that can solve A\[i\]=i in O(log(n)) in a sorted array. But I want to know if there is any kind of algorithm that also can solve A\[i\] = C1 * i + C2 (witch C1 and C2 are constant values) in O(log(n)) or not

# Answer
> 2 votes
Finding i such that A\[i\] = i, where A is a sorted array, needs to check every single array element in the worst case. Choose an array where A\[i\] = i-1 for every i except that A\[k\] = k for one single k. If you looked at any number of array elements other than A\[k\], every single one of the remaining elements could be the one you are looking for.

Now replace every array element with A\[i\] * C1 + C2, and unless C1 = 0, you have exactly the same problem.

Of course you can be optimistic, and often you will find i a lot quicker. Let's say you have array elements a\[1\] to a\[1000\], and you find that a\[500\] = 770. You now know that 1 \<= i \<= 499 or 770 \<= i \<= 1000. You just significantly reduced the number of choices. Of course my first example would have a\[500\] = 499, which tells you nothing apart from i ≠ 500.

---
Tags: algorithms, binary-search
---


# Question
Title: Minimum number of given operations in order to group letters in a string
> # Description
>
> Suppose we have a string containing letters 'A', 'B', 'C', 'D', and the characters are placed in a stack. We also have an empty stack. Ultimately, we want all of the same letters to be together (continuous order) in the 2nd stack, using only 3 operations:
>
> * **push("p"):** Removes an items from the bottom of the 1st stack and place it to the top of the 2nd
> * **complement("c"):** Replace every all letters of the 1st stack with their "complements". The pairs are **A - B** and **C - D**
> * **reverse("r"):** Reverse the content of the 2nd stack. The top becomes bottom and bottom-\>top.
>
> The characters in the 2nd stack don't have to be in any particular order, we just need to find a way so that in the 2nd set we have letters of the same kind together, without any different letter interrupting the sequence.
>
> **Here are some examples of accepted answers:**
>
> 1. AAABCCCCCCCDDDDD
> 2. DDC
> 3. A
> 4. BBBDDDAAAAA
> 5. CCCCCCCC
> 6. ABCD
> 7. BBBCCCCCCBBB -\> important example, this is also accepted because we consider 1st position neighbor to the last
> 8. AAAADAAAAA -\> accepted for the same reason as 7)
>
> **Examples of not accepted answers:**
>
> 1. AAAABBBBACCCDDDD -\> Not accepted because As are not together
> 2. ABCDB -\> Bs not grouped
>
> # Example of moves
>
> ```
> | Move | First Stack | Second Stack |
> +------+-------------+--------------+
> |      | DBACA       |              |
> +------+-------------+--------------+
> | p    | DBAC        | A            |
> +------+-------------+--------------+
> | p    | DBA         | CA           |
> +------+-------------+--------------+
> | r    | DBA         | AC           |
> +------+-------------+--------------+
> | p    | DB          | AAC          |
> +------+-------------+--------------+
> | c    | CA          | AAC          |
> +------+-------------+--------------+
> | p    | C           | AAAC         |
> +------+-------------+--------------+
> | r    | C           | CAAA         |
> +------+-------------+--------------+
> | p    |             | CCAAA        |
> +------+-------------+--------------+
>
> ```
>
> Note that the example above finds a solution, but **not the minimum solution**. The correct answer would be **"ppr ppp"**
>
> # Correct examples
>
> Spaces in the sequence have no meaning and are added for readability purposes.
>
> ```
> +------------------------+-------------------------------------+
> | First Stack (input)    | Moves (output)                      |
> +------------------------+-------------------------------------+
> | DD                     | pp                                  |
> +------------------------+-------------------------------------+
> | BADA                   | ppr pp                              |
> +------------------------+-------------------------------------+
> | DADA                   | ppc pp                              |
> +------------------------+-------------------------------------+
> | DBACA                  | pprppp                              |
> +------------------------+-------------------------------------+
> | BDA CACA               | ppr prp rppp                        |
> +------------------------+-------------------------------------+
> | CAC DCDC               | pcp cpc pcp cpp                     |
> +------------------------+-------------------------------------+
> | ADA DBD BCB DBCB       | ppr pcr pcr prp rpr prp rpr prp rp  |
> +------------------------+-------------------------------------+
> | DAB BCC DCC BDC ACD CC | ppc pcp cpp rpp rpp cpc ppr ppc prp |
> +------------------------+-------------------------------------+
>
> ```

# Brute force approach

We could just use brute force approach,calculating all possible moves until the first stack is empty. This could be done using BFS or A\* algorithms.

For example, we could initialize an empty queue, start from a parent node and create 3 new nodes for every possible move. Then add these nodes to the queue. Every time remove a node from the queue and apply the operations. Save the sequence of moves while nodes are created. If the last move was a "c", then skip "c" operation for this node. The same is true about "r" operation (no repetitive $c$s or $r$s). Every time we perform an operation we have to check if the 2nd stack satisfies our constraints. If not then delete this node. If `stack1 = empty` for a node, then finish the program and return the sequence of moves.

In the above description I tried to think of an algorithm similar to backtracking, but with BFS instead of DFS and some improvements for this specific problem.

# Questions

Is there a better way to solve this problem?
Can we apply some heuristics as improvement in the brute force approach?

# Answer
> 2 votes
This can be solved in $O(n)$ time using BFS.

Consider any sequence of moves that ends in a valid solution (all letters are in the second stack and are grouped). At every intermediate point in this sequence, the letters on the second stack must be grouped. (If the letters in the second stack ever become ungrouped, then they stay ungrouped from there on -- there's no way to repair things from there on.)

Therefore, we can characterize the state at any intermediate point by the number of letters remaining in the first stack, whether the first stack was complemented or not, and the order of the letters in the second stack. In other words, the state is $\langle k, c, s \rangle$ where $0 \le k \le n$ and $c \in \\{\text{True},\text{False}\\}$ and $s \in \\{A,B,C,D\\}^\*$ is a sequence of letters that describes the order the groups appear in the second stack. In particular, no letter can appear more than once in $s$, except that the first and last letter can be the same. Here I let $n$ denote the number of letters originally on the first stack. (Equivalently, you can let $s$ denote the sequence of letters in the second stack, but we only include states where the second stack is grouped.)

In particular, there are at most $178(n+1)$ states that you can be in at any intermediate point. (There are $n+1$ possible values for $k$, and $1+4+12+24+24+24=89$ possible values for $s$, and 2 values for $c$.)

You can explore the graph of possible states using breadth-first search. At each state, there are only three possible moves, so three edges out of that state; thus we explore a graph with at most $178(n+1)$ vertices and at most $3 \times 178(n+1)$ edges. The breadth-first search terminates when it reaches any state of the form $\langle n,c,s\rangle$. The running time is $O(n)$.

---
Tags: algorithms, dynamic-programming, search-algorithms, strings
---


title: Latin-1 Supplement Unicode Characters

text:
# Question
Title: Latin-1 Supplement Unicode Characters
The unicode characters under the "Basic Latin" unicode block from U+0020 to U+007F are the characters that characters we use in English. However, the "Latin-1 Supplement" block from U+00A0 to U+00FF is an extension of the "Basic Latin" block and includes characters that are used in some languages. For example, the Spanish language use all the characters from U+00A0 to U+00BF as well as the letter "Ñ/ñ" (U+00D1 and U+00F1), which is pronounced like the "ny" in "canyón". So, how did some languages get the characters under the Latin-1 supplement block?

# Answer
The Latin-1 supplement was taken unaltered from the upper half of an existing standard, ISO 8859-1, which in turn was based on a standard published by the European Computer Manufacturers Association (ECMA) in the early 1980s as ECMA-94.

ECMA-94 was based on an actual hardware encoding, developed by Digital Equipment Corporation (DEC) for its popular VT-220 video display terminal, presumably on the basis of what they perceived as customer demand. But the various national standards associations negotiated some adjustments which, as is often the case, were hammered out in interminable meetings attended by well-meaning people with a lot if enthusiasm but without much expertise in designing character sets.

In the end, ISO 8859 was extended to a series of 8-bit encodings, ISO 8859-1 through ISO 8859-15, providing support for national languages which had not been well-served by the original encoding.

By then it was obvious that 256 codes were not enough for all the alphabets in use at the time, but there was still some reluctance to switch to a wider encoding for languages which could be shoe-horned into eight bits. Many manufacturers were quite prepared to sacrifice the possibility of representing multilingual documents (unless, of course, one of the languages was English), and the relatively simple Unicode proposal was countered within the ISO by a byzantine collection of unworkable multibyte shift encodings. Fortunately Unicode did eventually prevail, but the provisions for context-dependent shift encodings continue to complicate multilingual APIs.

For another view of this history and some interesting links, you can check out the Wikipedia entry on ISO 8859-1.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Can application DNS requests bypass a firewall on Windows and Linux
Assuming I have firewall set to block an application from accessing the Internet, would I DNS request go through?

I tried using C (gethostbyname) on Windows and the answer is no. It seems that the application sends the DNS request to the public DNS server, but I wonder if this is the same under Linux.

In particular, could there be that there is a local DNS server (loopback interface) running on the OS such that gethostbyname would instead use the local DNS for the requests. Firewalls may block public packets but for private subnets especially for loopback that may be allowed to applications depending on how one configures the firewall. This way a block app would place a request to an unblocked app (DNS local relay server) that can communicate with a remote system.

# Answer
> 1 votes
It depends on the policy enforced by the firewall. If it blocks outbound DNS requests, then the request wouldn't go through; if it doesn't, the request would go through. A firewall is a mechanism; it has to be configured with a policy that determines which packets or connections are allowed and which are blocked. Just saying you have a firewall does not tell us what policy you have chosen to have it enforce.

The details of how gethostbyname() behaves are beyond the scope of this site.

You certainly could have a situation where the firewall blocks an application from making DNS requests to the outside world but allows them to a local DNS server; and where the local DNS server acts as a resolver or a proxy and itself makes requests to the outside world. That will depend on the firewall and how it is configured as well as the DNS server and how it is configured.

---
Tags: operating-systems, computer-networks
---