# Question
Title: What are some real world applications of graphs?
Can you give some real world examples of what graphs algorithms people are actually using in applications?

Given a complicated graphs, say social networks, what properties/quantity people want to know about them?

—-

It would be great if you can give some references. Thanks.

# Answer
> 44 votes
Graphs are definitely one of the most important data structures, and are used very broadly

---

**Optimization problems**

Algorithms like Dijkstra's enable your navigation system / GPS to decide which roads you should drive on to reach a destination.

The Hungarian Algorithm can assign each Uber car to people looking for a ride (an assignment problem)

Chess, Checkers, Go and Tic-Tac-Toe are formulated as a game tree (a degenerate graph) and can be "solved" using brute-force depth or breadth first search, or using heuristics with minimax or A\*

Flow networks and algorithms like maximum flow can be used in modelling utilities networks (water, gas, electricity), roads, flight scheduling, supply chains.

---

**Network Topology**

The minimum spanning tree ensures that your internet traffic gets delivered even when cables break.

Topological sort is used in project planning to decide which tasks should be executed first.

Disjoint sets help you efficiently calculate currency conversions between NxN currencies in linear time

Graph coloring can in theory be used to decide which seats in a cinema should remain free during a infectious disease outbreak.

Detecting strongly connected components helps uncover bot networks spreading misinformation on Facebook and Twitter.

DAGs are used to perform very large computations distributed over thousands of machines in software like Apache Spark and Tensorflow

---

**Specialized types of graphs**

Bayesian networks were used by NASA to select an operating system for the space shuttle

Neural networks are used in language translation, image synthesis (such as fake face generation), color recovery of black-and-white images, speech synthesis

# Answer
> 25 votes
Pathfinding is arguably one of the most practical subareas of algorithms and graphs. I am sure you can find plenty of use cases from navigation, routing, logistics and computer games, all growing multimillion businesses.

If you want to think about social networks, you might think about recommender systems some of which are graph-based for discovering similar likes.

# Answer
> 14 votes
Chances are high you found your way to the Stack Exchange network via Google or another search engine. Google uses the PageRank algorithm, which models webpages and links in them as a directed graph. The algorithm itself is perhaps more linear algebra than graph theory (it looks for an eigenvector for the graph's adjacency matrix), but given that the majority of the Earth population uses it on a daily/weekly basis, it should definitely count as an important real world application of graphs.

# Answer
> 7 votes
Cargo routing for e.g. railways, shipping liners, cargo planes are extremely difficult optimization and useful problems that are fundamentally some sort of network flow problem on a large graph. Similarly, rerouting cargo once delays happen is an important multi-item path finding problem that is very important to e.g. Maersk. What about designing routes for the garbage trucks in a city?

There are also network design problems, e.g. for choosing which links to build in the electricity network to make it robust. E.g. are there any edges that would disconnect the graph if removed? What about a pair of edges? What about five? Note that since this is a network flow problem, the graph might still be a single component; there could just be insufficient capacity between two clusters after removing the edge.

What about detecting bottlenecks in graphs? That is important when designing computer communication networks. For example, there's something called the Cheeger constant that can measure the "bottleneckedness" of a graph.

Stack exchange has an entire separate community dedicated to solving optimization problems like these at or.stackexchange.com.

# Answer
> 7 votes
In compilers, instruction scheduling algorithms are graph algorithms. They operate on the Data Dependence Graph, finding a topological sort which can most efficiently execute the instructions.

---

Certain computations can be expressed as a graph. Microsoft Excel formulas form a graph, as they refer to other cells and perform a computation which further formulas may depend on. There are also "blueprint" programming languages which are graphs, with nodes representing operations and edges representing the flow of data.

Machine Learning uses graphs. The model is expressed as a graph, piecing together different operations which combine to perform the overall behavior you want.

# Answer
> 7 votes
I think we should mention the Kevin Bacon Number and the Erdős Number and similar applications. They are nice and interesting.

# Answer
> 6 votes
**Markov chains** are commonly represented by directed graphs, and have tons of applications across probably most, if not all, scientific fields. The Wikipedia page on Markov chains discusses in more detail many of the following places where you might see Markov chains:

* Thermodynamics and statistical mechanics
* Chemical reaction networks
* Phylogenetics
* Population dynamics
* Neurobiology (neurons as nodes, synapses as edges)
* Automatic speech recognition
* Google's PageRank system
* Markov Chain Monte Carlo (statistics), which itself has tons of applications across fields
* Games
* etc

Some of these examples show up in the broader applications section for the Graph Theory Wikipedia page as well, along with various others

# Answer
> 6 votes
One example that you may overlook when thinking of graphs are *meshes*.

Almost every algorithm that works on 3D meshes is a graph algorithm. In fact you often use algorithms that are usually defined on general graphs like Dijkstra's algorithm in many mesh processing tasks.

The simplest mesh representation is a undirected graphs equipped with a metric on edges. A more sophisticated data structure is a half-edge mesh, that is a directed graph that has two edges with opposite direction between connected points and a metric on the edges that gives the same length for both half-edges that form an edge.

# Answer
> 6 votes
It's not been mentioned yet, but one big area where they're used every day by developers is in software version control.

Almost all modern distributed version control tools utilize a directed acyclic graph structure to track changes, with each node representing a set of changes and each edge connecting pairs of changes that are derived from each other. `git` even explicitly calls this out in their technical documentation.

Because of merging changes, a regular tree structure cannot accurately represent the standard working model used in most DVCS systems, so you actually *need* a graph here to get an accurate idea of what has happened in terms of changes to a pisece of software.

# Answer
> 5 votes
Regarding social networks and your second question,

> What properties/quantity people want to know about them

You can try it yourself, so anything you might want to know about the social network is a valid answer to your own question.

Ref How to use Facebook's Graph Search (and why you would even want to)

Some examples given in the article are

> I searched for photos of my friends who visited Hawaii, because I just returned from a trip to Oahu and wanted to see their photos of the islands.
>
> Friends who listen to Daft Punk and live in San Francisco
>
> Friends of my friends who work at TechHive

You can also find some other real world applications from the websites of Palantir and Neo4j

I remember some years ago seeing a presentation from Palantir where they helped the police use graphs to model criminal networks. So they would add connections between people based on friendship, family relationships, financial transactions, phone calls, etc, as well as businesses used for money laundering, where they kept their bank accounts, etc. I think the police has done similar work on paper for many years, but with graphs and computers it can be made more efficient, scalable, and easily be queried.

# Answer
> 5 votes
They're commonly used in molecular biology and genomics to model and analyse datasets with complex relationships.

For example, graph-based methods are often used to 'cluster' cells together into cell-types in single-cell transcriptome analysis.

Another use is to model genes or proteins in a 'pathway' and study the relationships between them. This is common in analysis of metabolic pathways and gene regulatory networks. See here for examples of how graphs are used in genomics.

Evolutionary trees, ecological networks, and hierarchical clustering are also represented as graph structures.

Applications of graph theory range far beyond social and toy examples. These will only become far more widespread as technology develops to leverage this kind of data. At this point, graph-based methods are so pervasive that researchers in some fields (such as biology) may not even be aware that they're using them.

# Answer
> 5 votes
One example not mentioned here is Gaussian elimination to solve linear equation systems. In order to minimize runtime and memory requirements, it is important to do the elimination in the right order so as to avoid too many non-zero entries in the resulting equations.

It turns out you can model this problem as a graph problem.

# Answer
> 2 votes
Graphs appear all over the place in physics, most often as a visual representation of an underlying tensor calculus in a monoidal category (in the sense of string diagrams or Penrose notation). Feynman diagrams or Feynman graphs give the most important and striking example of this. Feynman graphs are a visual way of doing calculations in perturbative quantum field theory, the physical framework underlying the Standard Model of Particle physics, and also used to describe complex, many-body quantum systems.

Each graph encodes a complex number called an amplitude, and by summing over graphs/amplitudes, one can calculate, for example, the probability for a particular collisional process between elementary particles taking place. These graphs are sometimes interpreted as providing a picture of particle collisions in spacetime, although this intuition is often misued. In perturbative string theory, sums over one-dimensional Feynman graphs are replaced by sums over two-dimensional surfaces.

Other, related appearances of graphs are as angular momentum diagrams or in tensor networks, and each of these (including Feynman graphs!) arise from some categorical tensor caculus.

# Answer
> 2 votes
Using GPS/Google Maps/Yahoo Maps, to find a route based on shortest route. Google, to search for webpages, where pages on the internet are linked to each other by hyperlinks; each page is a vertex and the link between two pages is an edge.

On ecommerce websites relationship graphs are used to show recommendations.

And more

---
Tags: graphs
---


title: Check if language is decidable

text:
# Question
Title: Check if language is decidable
I would like to determine if the following language is decidable or not. L = { w $\in$ $\Sigma^\*$ | $T(M\_w)$ is recognized by a Turing machine with at most 42 states}.

I know that every finite language is decidable, but I am not sure if this has anything to do with this particular problem.

Every help is appreciated, I am a little lost.

Thank you

# Answer
Define C = { $L | L$ is decidable by a turing machine with at most 42 states }

Notice that there is a finite amount of such languages, as there are a finite amount of turing machines with 42 states. for that reason, we have $C\ne\emptyset, \sum^\*$

By Rice's theorem, the language $S=$ { $w | L(M\_w) \in C$ } is undecidable. This language is precisely the language in question
> -1 votes

---
Tags: formal-languages, turing-machines, undecidability, semi-decidability
---


# Question
Title: I'm trying to understand DFAs is my DFA correct in this question if not why?
I have the following alphat {0,1}.

I'm told to draw a DFA which fulfills the following: {w|w starts with 1 and ends in 0}

This is the DFA I came up with.

# Answer
> 3 votes
This dfa is **incorrect**. To start, a dfa MUST define a transition for every node, including accepting nodes.

Anyhow, the current dfa would have accepted the language L = { w | w is a series of 1's and a single 0 at the end }

To correct this, you need to add another transition from B to A when it recieves 1 and a transition from B to itself when recieving 0. This is required to allow strings with 0 in the middle to also be accepted

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


# Question
Title: Automata that respect the condition {w|w contains at least two 0s and at most one 1}
we have the alphabet {0,1}.

{w|w contains at least two 0s and at most one 1}

It tried this: (However I'm not sure if it's correct. If it's incorrect why?)

# Answer
> 2 votes
This is obviously not correct, as every state is an accepting state - meaning this will accept literally *every word* (not to mention you forgot to define what B does when it sees a '1').

Although, even if we would have changed state A to be non-accepting, then this dfa would have accepted words with exactly one 1's (and any amount of 0's)

To fix this, we must do the following changes:

1. make A a non-accepting state.
2. add a state C that A will point to when it gets a '0' and D will go to B when it sees a '0'
3. create three more states D, E, F that will act like copies of A, D, B - **BUT** will will send to C on a 1, and we will have A,D send to E,F respectively on 1.
4. add state C that is non-accepting, where F will send you to it when it sees '1'. C will have a connection to itself for both 0 and 1. this state is usually referred as a *terminating state*, as there is no way out and it is not accepting.

The new DFA looks like this:

I have tried to make it look such that every 'row' counts the number of 1's and columns count the number of 0's

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


# Question
Title: Binary to ASCII using logical operations
I am learning Computer Architecture from Introduction to Computing Systems (2nd Edition) and am stuck on this question.

What operations can be used to convert the binary representation of 3 into ASCII representation for 3? What about binary 4 to ASCII or any other digit?

The concepts I have learnt until now are Basic Logic gates and Bit Masking so I have to use them for conversion. Can someone help me understand what my approach should be?

# Answer
By looking at a ASCII table you can see that the $4$ least significant bits of all characters between $0$ and $9$ correspond to the respective integer representations of the numbers between $0$ and $9$, while the 4 most significant bits are always $0011$ (leading zeroes are not shown in the table, so keep in mind you need to pad binary numbers to 8 bits).

If $x$ is the binary representation of a number between $0$ and $9$, you can then obtain the ASCII representation of the corresponding character as $$ x \\;| \\;00110000, $$

where $|$ denotes a bitwise logical or and the second operand is in binary.
> 3 votes

---
Tags: computer-architecture, binary
---


# Question
Title: State complexity of converting epsilon-NFAs to NFAs without epsilon transitions
I am well-aware of the result showing that one can convert an epsilon-NFA (that is, an NFA with epsilon transitions) $A$ to an NFA without epsilon transitions $A'$, where $L(A) = L(A')$.

Is there a similar result comparing the state complexities of $A$ and $A'$? That is, if one has an epsilon-NFA $A$ with $n$ states, is it true that there exists an equivalent NFA without epsilon transitions $A'$ that also has $n$ states?

# Answer
> 2 votes
Yes, we can transform an epsilon NFA into a NFA by keeping the same state set, basically adding new edges. If there is an $\varepsilon$ path from state $p$ to state $q$, and an edge from state $q$ to state $r$, then add an $a$ edge from $p$ to $r$. Also, if from state $p$ we can reach a final state then state $p$ can be made accepting. After these two steps we can remove the original $\varepsilon$ edges without changing the language.

---
Tags: complexity-theory, finite-automata, nondeterminism
---


# Question
Title: Expressing functions using the arithmetic dictionary
i have seen in the "logic to cs" class i take - a theorem that states: "every recursive (computable) function $f$ can be expressed using the arithmetic dictionary {$C\_0, C\_1, f\_+(,), f\_x(,), R\_\le(,)$} with the structure {$D=\mathbb{N} ,C\_0=0,C\_1=1, f\_+(a,b) =a+b, f\_x(a,b)=ab, R\_\le(a,b) = a\le b $}"

But we didnt prove this theorem because a part of the students didnt take the "computational models" course (i did take it though)

Where can i find a proof for this theorem? Thanks in advance!

# Answer
> 3 votes
I'm not sure this is exactly what you are looking for, but you might find what you want in Theorem 3.2.1 of *Computability Theory* by S. Barry Cooper:

> All recursive functions are representable in PA.

that is for any recursive function $f$, there exists a binary predicate $F$ in the language of arithmetic such that for any natural numbers $x$ and $y$ we have $$ f(x) = y ~\Rightarrow~ \vdash\_{PA} F(x,y) $$ and $$ f(x) \neq y ~\Rightarrow~ \vdash\_{PA} \lnot F(x,y) $$ where $\vdash\_{PA}$ means 'PA proves'.

This theorem is central to Gödel's famous *incompleteness theorem*, so you might also want to take a look at ch. 8 of the mentioned book where it is discussed, and this notion of 'representability' is extended to 'semi-representability', to include the c.e. sets as well.

---
Tags: turing-machines, computation-models, first-order-logic
---


# Question
Title: What are the differences between symbolic execution and SAT solvers?
My understanding is that symbolic execution only deals with specific paths and bad patterns, while SAT solvers, or satisfiability modulo theories in general, provide a much more robust analysis of the program.

Could someone validate the statement above and (briefly) explain the differences between these two formal verification methodologies?

# Answer
> 6 votes
**TL;DR:** They differ in their basic input and output. SAT and SMT solvers don't know what programs are; they are tools that answer yes or no questions about mathematical formulas. Symbolic execution, on the other hand, is a method of analyzing programs. Symbolic execution usually relies on SAT and SMT solvers, but not the other way around.

---

**SAT and SMT solvers** don't directly have anything to do with programs. Instead, a SAT or SMT solver takes as input a mathematically described "formula", and answers, roughly, whether it is true or false. (Often a third option is allowed, *unknown*, for cases where the solver is unable to figure out an answer.)

For example, a possible input to a SAT solver is `(a and not b) or (not a and c)`. That is, it is a mathematical formula, where `a`, `b`, and `c` here are Boolean (0 or 1) constants. The SAT solver is supposed to decide if it is possible for the formula to be true, by choosing values of `a`, `b`, and `c`. SMT solvers are similar, but `a`, `b`, and `c` would be replaced by more complex formulas using integers, strings, functions, etc., for example `x + 3 = y^2`.

---

**Symbolic execution** is a fancy way of running a program, but not how the program was intended to be run. Instead, the program is run using so-called "symbolic" values, which are kind of like placeholders. For an example of what that means, suppose I have a function like `f(x) = if x > 0 then 1 else 0`. Now, normally, I would run the program by inputting, say, `3`, and get `f(3) = 1`, since `3` is greater than `0`. With symbolic execution, I run the program by inputting a placeholder variable, `input`, and I evaluate the program to get two cases: either `input > 0 and answer = 1` or `input <= 0 and answer = 0`. This may seem useless, but it ends up being a powerful way of analyzing programs.

---

**The connection between the two** is that symbolic execution often relies on SMT solvers during execution, to figure out if a certain path is actually possible, or if it should be discarded. For example, an SMT solver could be used to determine if `input <= 0 and answer = 0` is possible (the answer is yes, for example if `input = 0`). In this way, SMT is kind of the "driving force" behind what makes symbolic execution feasible.

---
Tags: satisfiability, sat-solvers, smt-solvers, symbolic-execution
---


# Question
Title: Complexity of recursion T(n) = 2T(n-1) + C?
I am trying to calculate the Time Complexity of the Recursive Function, suppose this,

```
function T(int n){
 if(n == 1) return 1;
 return T(n-1) + T(n-1);
}

```

the time complexity equation is: `T(n) = 2T(n-1) + C`, taking `C = 1 and T(1) = 1`. Now, since I am working on this, I am confused whether I am doing the right process using `Back Substitution`. This is how I approached the calculation. I have followed the below question, but did not find it very satisfactory, so raising the question again.

This is how I approached the problem:

```
1. T(n) = 2T(n-1) + 1
2. T(n-1) = 2T(n-2) + 1 //since we have T(n-1) in Eq(1)
3. T(n-2) = 2T(n-3) + 1 //since we have T(n-2) in Eq(2)

```

**Back Substitution to Solve for final complexity**

```
1. T(n-1) = 2(2T(n-3) + 1) + 1
2. T(n) = 2(2(2T(n-3) + 1) + 1) + 1
        = 2(4T(n-3) + 1 + 2) + 1
        = 8T(n-3) + 1 + 6
        = 8T(n-3) + 7
        = 8T(n-3) // Ignoring 7, since it is a constant
        = 2^3T(n-3)
        = 2^kT(n-k)

```

**Substituting the value of K, since base case is n = 1**

```
1. n-k = 1
2. k = n-1

//Substituting the value of k in the above T(n) Equation
T(n) = 2^{n-1}T(n-n+1)
     = 2^{n-1}T(1)
     = 2^{n-1} * 1
     = 2^{n-1}

```

So from above I got 2n-1, is the above process correct, or needs improvement. I am starting off with time complexity, and this recursion is kind of tricky for me. Please help!

# Answer
> 4 votes
The exact equation is (if $T(1) = 1$):

$$ T(n) = 2T(n-1) + 1 = 2(2T(n-2) + 1) + 1 = $$ $$ 2^2 T(n-2) + 2 + 1 = $$ $$ 2^2(2T(n-3) + 1) + 2 + 1 = 2^3 T(n-3) + 2^2 + 2 + 1$$

Hence, $T(n) = 2^{n-1} + 2^{n-2} + \cdots + 1 = 2^n - 1$ (by mathematical induction).

# Answer
> 1 votes
For a shortcut to the exact expression, add `C` on both sides of the recurrence and write it as:

```
    T(n) + C = 2 (T(n-1) + C)

```

Define `U(n) = T(n) + C` then the above gives `U(n) = 2 U(n-1)`.

Therefore `U(n)` is a geometric progression with common ratio `2`, so `U(n) = 2^n U(0)`, then:

```
    T(n) = U(n) - C
         = 2^n U(0) - C
         = 2^n (T(0) + C) - C

```

For `C = 1` and `T(0) = 0` this reduces to `T(n) = 2^n - 1`.

---
Tags: time-complexity, complexity-theory
---


title: What is a loop variable?

text:
# Question
Title: What is a loop variable?
In the context of compilers, what exactly is a loop variable (if there is a standard definition)?

Every read/write make up for the loop variable, or only writes make them up? Or is it writes in the body and reads in the condition?

# Answer
> 1 votes
The term that I was taught (thanks, Dragon Book!) is "induction variable". It refers to any variable which is a linear function of the number of iterations in a loop.

I don't know the term "loop variable", but if I had to guess, it would refer to a variable whose value changes inside the loop, and which is tested to decide the loop termination condition.

But to be honest, it would depend what you were trying to use it for. Pick whatever definition helps your analysis.

# Answer
> 0 votes
Usually a variable which is used for the control of a loop. Basically a counter (as in a for/next-style loop), but can play a more general role.

---
Tags: loops
---


# Question
Title: On the complexity analysis of quick-union in Algorithms by Sedgewick and Wayne
I am currently studying Algorithms, Fourth Edition by Sedgewick et al. On page 226, there is an analysis of the quick-union algorithm's find() method's worst case.

This is the algorithm:

```
  private int find(int p)
  { // Find component name.
      while (p != id[p]) p = id[p];
      return p;
  }

```

Suppose we have originally an array from 0 to N-1. Now I count N comparisons in total (inside the while) plus N-1 accesses (last comparison is false) to rewrite the value of p. This would give me 2N - 1 accesses to the array. The textbook however says there are 2N+1 accesses. What am I doing wrong? Thanks for your time.

Computational complexity is being measured by the number of accesses to the array that we use to model which site belongs to which component. Suppose we want to connect the site labeled 3 with the site labeled 1. In order to do that we just make sure id\[3\]=1. The find() method exists to give us the component to which an element belongs. If we now connect 1 to 4, then we just make id\[1\] = 4. Now find(3) will be 4, because 3 points to 1 which in turn points to 4.

# Answer
Yes, you are correct!

You have identified a typo in that book, *Algorithms*, the fourth edition by Robert Sedgewick and Kevin Wayne. Please check the errata for the first printing (March 2011) of the fourth edition.

> p. 226
>
> Printed: in the worst case, it needs 2 N + 1 array accesses
> Fixed: in the worst case, it needs 2 N - 1 array accesses
> Reported by Victoria Solomon, 15-Sep-11.
> 1 votes

---
Tags: algorithms, union-find, connected-components
---


# Question
Title: "problematic" non-halting inputs for Turing machines
Let us start this question out, by defining for a Turing machine, the set of words it **doesn't** halt on. Define: $P(M)=\\{w\in\Sigma^\*|M$ doesn't halt on $w \\}$

We know that the $HALT$ problem is $RE\setminus R$ \- thus every TM $M$ that computes $HALT$ has a word it doesn't halt on, i.e $P(M)\ne\emptyset$.

From this, arises the (simple) question:

$Q(1):$ "is a problem undecidable if and only if every TM that computes it has a non empty 'problematic' set $P(M)$?" $ ^{Q\space(1)}$

Moreover, let's note that for the $HALT$ problem we know that given $M$ that computes it, there are infinitely many inputs it will never halt on (I encourage to think why this is so, before proceeding in the post)

So, similarly we might want to ask ourselves the (slightly) harder version of the first question.

$Q(2):$ "is a problem undecidable iff every TM $M$ that computes it has $|P(M)|=\aleph\_0$?" $ ^{Q\space(2)}$

Moreover - let's ask an even stronger question:

$Q(3):$ "if $L$ is undecidable, will we still be able to find a **finite** set of Turing machines $M\_1,...,M\_n$ that compute $L$ and have $\bigcap\_{k\space=\space0}^nP(M\_k)$ finite? what about an **infinite** set of Turing machines that satisfy that?" $ ^{Q\space(3)}$

And our final (and half-open) question will be:

$Q(4):$ "What else can we understand about Turing machines and their problematic sets?"

# Answer
So, let's start tackling those problems. As a side note, I have arranged the questions such that each question uses the answer of the one before it (and this way, they almost seem too trivial to begin with $:$P).

$A(1):$ is pretty trivial from definition. If $L$ is undecidable then there is no Turing machine that computes it and always halts, thus all Turing machines that compute $L$ have $P(M)\ne\emptyset$. The other direction is also as simple as this one.

$A(2):$ let's assume $L$ is undecidable. If there was a Turing machine $M$ that computes $L$ and has a finite $P(M)$, then let us build a new machine $\hat M$ such that it will have $P(\hat M)=\emptyset$ as following (on input $w$):

* reject if $w \in P(M)$ (this is possible since $P(M)$ is finite)
* otherwise, return $M(w)$

this new machine, will halt for every $w\in P(M)$, but since for every $w\notin P(M)$ it will run $M$, and it's guaranteed that it will halt on it (since otherwise it would have been in $P(M)$), we have that the new $\hat M$ always halts, and accepts $L$ \- thus contradicting the assumption. The other direction is simply derived from $A(1)$.

$A(3)$: for **finite** sets of Turing machines, $M\_1,...M\_n$ we will show that its impossible to have finite $\bigcap\_{k\space=\space0}^nP(M\_k)$ but undecidable $L$. lets assume towards contradiction this doesn't hold. Just at $A(2)$, we will build $\hat M$ \- but now its enough to build it such that $P(\hat M)=\bigcap\_{k\space=\space0}^nP(M\_k):$

* Run $M\_1(w), M\_2(w), ...,M\_n(w)$ in parallel
* Accept if any one of them accepted.

Now, it's obvious why $\hat M$ accepts $L$. Let $w\notin P(\hat M)$, then there is some $1\le k\le n$ such that $M\_k(w)$ halted, thus $w\notin\bigcap\_{k\space=\space0}^nP(M\_k)$. let $w\in P(\hat M)$, then it didn't halt on any $M\_k$, thus $w\in P(M\_k)$ for all $k$. Concluding that $P(\hat M)=\bigcap\_{k\space=\space0}^nP(M\_k)$ is finite and therefore from $A(2)$ cannot exist.

Regarding **infinite** sets of Turing machines, this is definitely possible. Just define for each $w\in \Sigma^\*$ the machine $M\_w$ that accepts $L$ but also halts on $w$ (similarly to the build in $A(2)$). then $w\notin P(M\_w)$ therefore $w\notin \bigcap\_{\hat w} P(M\_\hat w)$ and thus not only that $\bigcap\_{\hat w} P(M\_\hat w)$ is finite, its also empty.

$A(4):$ let $L$ is undecidable and $M\_1,M\_2...$ are Turing machines who accept $L$ and their intersection of the "problematic set" is finite. If we look at the function $f:\mathbb{N}\rightarrow\Sigma^\*$ defined by $f(k)=\langle M\_k\rangle$ , then it is **not** computable. This follows from $A(2)$ since if that function was computable, we would have been able to create a Turing machine $\hat M$ with $P(\hat M)=\bigcap\_k P(M\_k)$

Another idea i have started to think about is what happens when we talk about **two** languages or more, instead of one at a time. Let $M\_1$ be a machine for $L\_1$ and $M\_2$ for $L\_2$. then, we can define a machine $M$ for $L\_1\bigcap L\_2$ or $L\_1\bigcup L\_2$ with:

$P(M) = P(M\_1)\bigcup P(M\_2)$ (note this also can prove closure properties in $\mathcal R$)

or if $L\_1\Delta L\_2$ is finite, then we the problematic sets of machines for the languages are pretty much the same(for every machine $M$ in any one of them we can find machines $M'\_1,M'\_2$ for the other two languages with the same problematic set)

Although I have yet to write a formal proof of the above. (honestly, I don't have energy to write more proofs like that in this one big post) I still encourage you to try proving that at home!

Finally! I think (but still unsure) we can get similar results (but with more constraints) for time complexity analysis if we define $P(M, t)$ for time-constructible $t(n)\ge log(n)$ as the group of words $M$ doesn't halt on within $t(n)$ steps. In this definition there is the tricky problem of constants, so its harder to show theorems by defining new machines (as they might do just a little bit more constant work that will make some word enter the problematic set, and big-O notation here is somewhat meaningless for different constants)

***If you think that something is incorrect, or just want to add more - I will be glad to make changes.***
> 0 votes

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


# Question
Title: Analysis of the long division algorithm in the Knuth book (Seminumerical algorithms) 1
I've been reading through the long division algorithm exposed in the Knuth book for a week and I still miss some details. There's an implementation of such algorithm in "Hacker's Delight" by Warren, however basically the author explains that it's a translation of the classic pencil and paper method and the Knuth book is the one that provides all the details. I really want to understand the analysis but for some reason that I can't quite understand it is a bit strange in the exposition.

It firstly starts by saying that

> "a moment's reflection about the ordinary process of long division shows that the general problem breaks down into simpler steps, each of which is the division of an $n+1$-place dividend $u$ by an $n$ place integers $v$.

I of course agree with such intuition, but it's because I've been taught in that way, not because there's a proof. It shouldn't be hard to work out the why however since

$$ \begin{array}{l} u = \sum\_{j=0}^{m+n-1} u\_j b^j \\ v = \sum\_{j=0}^{n-1} v\_j b^j \end{array} \Rightarrow \frac{u}{v} = \frac{\sum\_{j=0}^{m+n-1} u\_j b^j}{v} = \frac{\sum\_{j=m-1}^{m+n-1} u\_j b^j}{v} + \frac{\sum\_{j=0}^{m-2} u\_j b^j}{v} = \frac{\sum\_{j=0}^{n} u\_{j+m-1} b^{j+m-1}}{v} + \frac{\sum\_{j=0}^{m-2} u\_j b^j}{v} = \frac{\sum\_{j=0}^{n} u\_{j+m-1} b^j}{v}b^{m-1} + \frac{\sum\_{j=0}^{m-2} u\_j b^j}{v} = \left(q\_{m-1} + \frac{r\_{m-1}}{v} \right)b^{m-1} + \frac{\sum\_{j=0}^{m-2} u\_j b^j}{v} = q\_{m-1}b^{m-1} + \frac{r\_{m-1}b^{m-1} + \sum\_{j=0}^{m-2} u\_j b^j}{v} $$ where $0 \leq r\_{m-1} \leq v - 1$, using an induction argument I can show that I have always to do this (i.e. that the problem is to perform several iteration of dividing an $n+1$ digit number by an $n$ digit number. One key observation is that of course if $$ 0 \leq q\_{m-1} \leq b - 1 $$ then $q\_{m-1}$ represent the most significant digit of the division

Later the problem is stated as

> Let $u = (u\_nu\_{n-1} \ldots u\_1 u\_0)\_b$ and $v = (v\_{n-1} \ldots v\_1 v\_0)\_b$ be nonnegative integers in radix-$b$ notation, where $u/v \< b$. Find an algorithm to determine $q = \left\lfloor u/v \right\rfloor$.

From this point I have a problem (which is the object of my question). After the observation made that the condition $u/v \< b$ is equivalent $(u\_n \ldots u\_1) \< (v\_{n-1} \ldots v\_0)$ I would also observe that $v\_{n-1}$ is not necessaraly 0. It is later defined the quantity $$ \hat{q} = \min \left( \left\lfloor \frac{u\_n b + u\_{n-1}}{v\_{n-1}} \right\rfloor,b-1\right) $$ Where is not actually stated any condition on $v\_{n-1}$, which at least shouldn't be $0$. Then the author proves both theorems $A$ and $B$ which they make perfectly sense to me if $v\_{n-1} \neq 0$.

One could argue that before the theorems it is said

> ...as long as $v\_{n-1}$ is reasonably large...

However I think that this statement should be interpreted more like "we now show how much large $v\_{n-1}$ has to be in order to..." So there's actually no assumption here, he wants to show that.

The question is... Shouldn't basically the condition $v\_{n-1} \neq 0$ be clearly stated? I'm sure there's something subtle about the condition $u/v \< b$ that I'm missing...

(I have other questions but I'll go through that later)

# Answer
> 1 votes
Theorem B on page no. 272 of the book states that,

> if $v\_{n-1}$ $\geqslant$ $\lfloor b/2 \rfloor$, then q ∈ \[ q̂ - 2 , q̂ \].

Therefore, the algorithm is valid only when $v\_{n-1}$ $\geqslant$ $\lfloor b/2 \rfloor$, which makes $v\_{n-1} \neq 0$ obvious. To ensure this we need to multiply both u and v by a factor ${(= (base-1) / v\_{n-1})}$.

---
Tags: algorithms, proof-techniques, arithmetic, mathematical-analysis
---


# Question
Title: Finding the minimum cut of an undirected graph
Here's a question from a past exam I'm trying to solve:

For an undirected graph $G$ with positive weights $w(e) \geq 0$, I'm trying to find the minimum cut. I don't know other ways of doing that besides using the max-flow min-cut theorem. But the graph is undirected, so how should I direct it? I thought of directing edges on both ends, but then which vertex would be the source and which vertex would be the sink? Or is there another way to find the minimum cut?

# Answer
> 14 votes
There are plenty of algorithms for finding the min-cut of an undirected graph. Karger's algorithm is a simple yet effective randomized algorithm.

In short, the algorithm works by selecting edges uniformly at random and contracting them with self-loops removed. The process halts when there are two nodes remaining, and the two nodes represent a cut. To increase the probability of success, the randomized algorithm is ran several times. While doing the runs, one keeps track of the smallest cut found so far.

See the Wikipedia entry for more details. For perhaps a better introduction, check out the first chapter of Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal.

# Answer
> 8 votes
For every undirected edge $(u,v, weight)$ create two directed edges $(u,v, weight)$ and $(v,u,weight)$.

> ...but then which vertex would be the source and which vertex would be the sink?

Doesn't matter.

# Answer
> 1 votes
Ford-Fulkerson algorithm should work for you. You can create two fake vertices viz. the source and sink.

Also have a look at Edmonds-Karp algorithm. There are two variations of it:

1. One version picks the shortest path
2. Other picks a path with the maximum capacity

, as opposed to Ford-Fulkerson which picks an arbitrary path.

This is a good resource.

# Answer
> 0 votes
Check out Stoer-Wagner Algorithm: https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner\_algorithm

---
Tags: algorithms, graphs
---


# Question
Title: I'm asked to draw DFA for this {$\epsilon$, 0} however I do not understand what {$\epsilon$, 0} mean
I'm asked to draw a DFA of this {$\epsilon$, 0} but have no clue what it means. Can someone help me understand what the automata is supposed to do?

I know that $\epsilon$ is the symbol for empty word.

As an example having to make an automata for this {w| w contains at least two 0s and at most one 1} is pretty understandable but {$\epsilon$, 0} not so much.

To put it simply I do not understand the problem question I'm asked.

\**Edit: I forget to specify that we have the alphabet {0,1}

# Answer
> 2 votes
The problem is to find a DFA, such that **the only two words it accepts are '$\epsilon$' - the empty word, and '0'**

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


# Question
Title: what is the time complexity of this code
what is the time complexity of the following code. please help me.

// a is mxn matrix

```
for i = 1 to m:
    l = {}

    for j = 1 to n:
        if(a[i,j] != 0):
            add j to l

    if(len(l) > 1):
        for k=1 to len(l)
            for j=k+1 to len(l):
                some other code

```

# Answer
> 1 votes
I will assume that the time complexity of "some other code" is constant. You can bound the total time required by noticing that the outer loop performs $m$ iterations.

The first inner loop performs $n$ iterations and, in the worst case, inserts $n$ elements into $l$.

The last two inner nested loops perform a number of iterations that is monotonically increasing with the length of $l$ and is therefore maximized when the length of$l$ is $n$. In this case the number of iterations is: $$ \sum\_{k=1}^n \sum\_{j=k+1}^n 1 = \sum\_{k=1}^n (n-k) = \sum\_{k=0}^{n-1}k = \frac{n(n-1)}{2} = O(n^2). $$

The overall time complexity is therefore $O(m \cdot (n +n^2)) = O(mn^2)$.

---
Tags: time-complexity
---


# Question
Title: Responsive input sliders - is there a better way?
I am building an app where a user controls inputs via multiple sliders each with discrete steps. The app then uses the combination of slider values to run some calculations and returns back an output value.

The sliders are meant to be highly responsive, so the user can immediately see the impact of their input combination on the output value -so I have resorted to eagerly calculating ALL possible combinations of sliders and letting the client query the results in the browser itself for faster response times.

The problem is that the number of possible combinations can seriously explode. If I have 6 inputs each with 10 steps, that is 10^6 = a million possible combinations! That's way too expensive to calculate eagerly.

Is there a better way to do this? I could try to restrict the number of sliders that can be moved at any point, to lower the solution space...but wondering if there's a better solution out there.

# Answer
> 2 votes
I like John L's suggestion. Have the app compute the view for the current position of all sliders. Also, for each of the 6 other sliders, for each other 9 positions of that slider, precompute the view obtained from that. In other words, you precompute all views that can be obtained by changing the position of a single slider. That involves precomputing 6\*9 = 54 other views. Now, when the user clicks on a slider and changes its position, you'll be able to immediately display that view, and you can start precomputing 54 more views (for all combinations of changing one other slider to a different position). As long as you can compute 54 views in the it takes for a user to move their mouse from one slider to another, you'll be able to keep up in a responsive way.

---
Tags: algorithms, optimization, optimal-strategy
---


# Question
Title: Can Stoer-Wagner find min s-t cut for given s and t?
Stoer-Wagner algorithm can be used to find global minimum cut in a graph. I'm wondering if it could be adapted to find a minimum s-t cut, given s and t. We can start a single phase with {s} but there's no guarantee that vertex t will end up in the other subset. Is there any way to do it?

# Answer
> 2 votes
Finding a minimum s-t cut is easier than finding a minimum cut, so there is no reason to use or adapt Stoer-Wagner; instead, using a standard algorithm for finding a minimum s-t cut, such as using a network flow algorithm.

---
Tags: graphs, minimum-cuts
---


# Question
Title: Joining points of polygon in correct order
I have a point's array of some 2d shape(polygon). The polygon could be either crossed or convex, I don't know it. And I want to join those points in the correct order.

My first thought was to take some point as an origin and start looking for the closest one and so on. But this approach doesn't work for some crossed polygons, for example: on **Image1**, it would go from `x3` to `x5` because it is closer than to `x4`, but what I really want is to join `x1-x2-x3-x4-x5-x6`.

After some thinking, I've realized that my requirement `correct order` is very unclear because on **Image2** red lines are in the correct order too. So let's add the requirement that polygon lines shouldn't at least cross.

I really confused, can someone point me in what direction I should move? Maybe it's some famous algorithm but I just don't know how to google it properly. Thanks.

**Image1**:

**Image2**:

# Answer
> 1 votes
Start from the leftmost point $x\_0$ (the one with minimum $x$-coordinate). If there are ties break them in favor of the point with minimum $y$ coordinate.

Suppose for simplicity that there are no two points that are collinear with $x\_0$ (this case can be handled by suitably breaking ties).

Shoot a ray vertically at an angle of $-\frac{\pi}{2}$ radians. Sweep the plane by rotating the ray anticlockwise up to an angle of $\frac{\pi}{2}$ radians. Whenever the ray intersects a vertex, let this vertex be $x\_{i+1}$ where $i$ is the number of intersected vertices so far. Connect $x\_{i}$ to $x\_{i+1}$. Finally, connect the last encountered vertex back to $x\_0$.

In practice this boils down to writing all points in polar coordinates from $x\_0$, then sorting them by their angle, and connecting them in order.

---
Tags: algorithms, polygons
---


title: Reduction of 3-SAT to Vertex Cover?

text:
# Question
Title: Reduction of 3-SAT to Vertex Cover?
Can someone explain to me in the simplest possible way, how to reduce $3SAT$ to $Vertex\\:Cover$?

I am following the explanation here (scroll to the bottom of page 4). I understand the basic setup of having two "gadgets": the 2-node variable gadgets and 3-node clause gadgets.

I also understand the formula $k = variables + 2\\:clauses$ as the minimum number of nodes required to cover all the edges. What I don't understand is how this setup proves that if there exists a $k\text-covering$, then the boolean expression in CNF is satisfiable.

Examples with expressions that are satisfiable and not satisfiable would be helpful. Also, once the $3SAT$ problem is converted to a $k\text-covering$, does it provide a means to identify which value (true or false) should be assigned to each variable so as to satisfy the boolean expression?

# Answer
To show that Vertex Cover and 3SAT is "equivalent", you have to show that there is a 3SAT satisfaction if and only if there is a k vertex cover in the graph constructed in the reduction step.

Assuming you are familiar with how the reduction is done, (if not ,refer to the document).

Since you only asked about `how this setup proves that if there exists a k-covering, then the boolean expression in CNF is satisfiable.`

This is effectively the "only if" part to the proof that the two are "equivalent". So all you need to do is to show that as long as there is a k Vertex Cover for the graph constructed in the reduction, you have a satisfying solution to 3SAT.

The proof:

Since there is a k Vertex Cover, then one and only one node of each of the variable gadgets must be in the Vertex Cover. (This is because k = variables+2clauses,if you don't choose one of the variable in the variable gadget then the middle connection in the gadget is not incident, and if you choose in one gadget, you will end up with variables + 1 + 2 clauses, we'll show that you must choose 2 nodes in each clause gadget in the next sentence.)

We must have 2 nodes in each clause gadget because if we don't, then one of the connection in the clause gadget is not incident.

So set the variable corresponding to the one node that is selected in each of the variable gadgets to TRUE.

Now we have two scenarios for each of the clause gadgets:

One: A gadget can have a connection with a variable Node that is set to TRUE. In this case the gadget has a variable which is TRUE, the gadget is therefore satisfied.

Two: A gadget does not have a connection with a variable Node set to True. Then it must select all 3 of its Nodes to make the edges all incident. And that is not possible when we have a k Vertex Cover.

Hope this answers your question :))
> 2 votes

---
Tags: complexity-theory, np-complete, reductions, satisfiability, 3-sat
---


# Question
Title: Why is this language a regular language?
Came across this in a book, and I'm wondering why the following language is regular?

$$ L = \\{a^nww^R: n \geqslant 0, w \in \\{a,b\\}^3\\}$$

Is it correct to say that $$ \\{a^n : n \geqslant 0\\} $$ is a regular language because it can be expressed by a regular expression $$a\*$$, and $$ \\{ww^R: w \in \\{a,b\\}^3\\} $$ is a regular language because it is finite; therefore the union of the two regular languages makes a regular language?

# Answer
> 6 votes
This is **not** an union of two regular languages! It's a *concatenation*. Note the difference,

1. Union: $L\_1 \cup L\_2$
2. Concatenation: $\\{ab : a \in L\_1 \wedge b \in L\_2\\}$.

That said, your other observations are correct, and indeed the concatenation of two regular languages is also regular itself. You can prove this by constructing two NFAs for the regular languages and connecting the accepting states of $L\_1$ to the starting states of $L\_2$ by an $\epsilon$-transition.

---
Tags: regular-languages, finite-automata, formal-grammars, regular-expressions
---


# Question
Title: Show that recurrence is $O(\phi^{\log n})
I have a function whose time complexity is given by the following recurrence:

\begin{equation\*} T(n) = \begin{cases} \mathcal{O}(1) & \text{for } n=0\\ T(k)+T(k-1)+\mathcal{O}(1) & \text{for } n=2k\\ T(k)+\mathcal{O}(1) & \text{for } n=2k+1\\ \end{cases} \end{equation\*}

and I have to prove that $$T(n)\in \mathcal{O}(\phi^{\log\_2 n}),$$

where $\phi$ is the golden ratio, $(1 + \sqrt5)\over2$.

I think I could prove it by induction but, how would I go on about it if I didn't know that $T(n)\in \mathcal{O}(\phi^{\log\_2 n})$ in the first place?

# Answer
> 1 votes
Your sequence (shifted by 1) is known as Stern's diatomic sequence, or the Stern–Brocot sequences. The usual recurrence is: \begin{align} &a(0)=0 \\ &a(1)=1 \\ &a(2n) = a(n) \\ &a(2n+1) = a(n) + a(n+1) \end{align} The recurrence suggests that the answer has something to do with binary representation, so one might be prompted to look at the maximal value of $a(n)$ among numbers of length $m$ in binary: $$ 1,2,3,5,8,13,\ldots $$ This is the Fibonacci sequence. (One can check that the first maxima are attained at $(2^n-(-1)^n)/3$.)

From here, one immediately sees that the rate of growth is $O(\phi^{\log\_2 n})$.

More can be said. For example, Coons and Tyler determined the best possible constant in front of $\phi^{\log\_2 n}$ in their paper The maximal order of Stern's diatomic sequence.

You can find many more links in the OEIS entry A002487.

---
Tags: asymptotics
---


# Question
Title: can more than two arrows point towards the same state from other states in a DFA?
Is something like this possible:

You have state A,B,C all pointing towards accepting state D. Is this allowed? Where online can I find a list of rules that define how an automata must be drawn or conceived?

# Answer
Yes, this is allowed (and in fact, you lose a lot of computational power without it)

here is a definition of DFA (both formal and as drawings) + an example
> 1 votes

# Answer
A deterministic finite automaton is a tuple $\langle Q,\Sigma,q\_0,\delta,F \rangle$, where $Q$ is a finite set ("states"), $\Sigma$ is a finite non-empty set ("alphabet"), $q\_0$ is an element of $Q$ ("initial state"), $\delta$ is a function from $Q,\Sigma$ to $Q$ ("transition function"), and $F$ is a subset of $Q$ ("accepting states").

(Your definition might allow $\delta$ to be a partial function.)

As you can see, there are absolutely no constraints on the transition function, other than it being a function (or a partial function, if that is the definition you use).

In mathematics, definitions are precise. There is nothing which is left "implies" or "winked". If it's not in the definition, we don't require it. Whatever conforms to the definition, is allowed.
> 0 votes

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


# Question
Title: NFA that ends with 0 and doesn't have 11 after the first 0
So as the title says i m trying to find this NFA. So far i thought to make an NFA that "guesses" what comes after the first 0 and i got this:

After some time trying to get rid of all the extra (7 !) states i put in i got to this beauty:

But now i cant figure out how to get rid of the one extra state. Also if you have any tips on how to go to simpler NFA's instead of what i did (like a thought process for this problem) i would appreciate it a lot. Thank you

# Answer
> 1 votes
Simply remove state 2, and make a transition from 1 to 5 directly. This will get rid both of a state (state 2) and a connection (the epsilon connection)

# Answer
> 1 votes
From the theoretical perspective: there is a completely algorithmic procedure that given a DFA returns an equivalent DFA with the minimum number of states.

In your specific case: remove the $\epsilon$ transition and merge state $2$ with state $5$.

---
Tags: finite-automata
---


# Question
Title: Regular expression for a palindrome of finite length?
I have a language $$ L = \\{ww^R, w \in \\{ab\\}^5\\}$$

I know this is a regular language because it is finite (since w can only be of length 5). I want to prove it's a regular language, so I'd create a regular expression for it.

Theoretically, my regular expression could be the union of all strings in the language, but is there a concise way to express this rather than writing all possible strings out?

# Answer
Sticking $w$ with its reverse together usually is not a regular language and therefore there is no natural concise way to represent that using regular expressions (at least to my knowledge)

Im not really sure why you would like to find a regular expression for this language, since - as you have stated - this language is finite, and therefore regular (if you want a proof for this claim, it is here)
> 1 votes

# Answer
There seems to be nothing better than enumerating all 32 strings, because of the connection between first and last, 2nd and 9th character etc.
> 0 votes

---
Tags: regular-languages, finite-automata, formal-grammars, regular-expressions
---


# Question
Title: computationally efficient linear index to index pair mapping
Consider two index sets $S = \\{0, 1, 2, 3, 4, ..., N - 1\\}$ and $Q = \\{0, 1, 2, ..., \frac{N(N + 1)}{2} - 1\\}$. Let $R = \\{(a, b)\space |\space a, b \in S, a \ge b\\} = \\{(0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2), \dots\\}$. There will be $\frac{N(N + 1)}{2}$ elements in $R$. Is there a one-to-one function $f : Q \to R$ that is computationally efficient?

One application is to map the linear memory index to row and column of a triangular matrix. Another application is to map thread numbers to work items in parallel programs where the work deals with pairs of items (triangular domain problems).

# Answer
For a given $m \in Q$, we need to find the biggest $n \in R$, such that $\frac{n(n+1)}{2} \leq m$. Hence, the first element will be $n$ and the second elemnet is $\lfloor m - \frac{n(n+1)}{2} \rfloor$. Now, the question is how can we compute $n$ efficiently? Fortunately, it can be computed by testing some constant numbers and the specified pair will be $(n, \lfloor m - \frac{n(n+1)}{2} \rfloor)$ for a given number $m \in Q$.
> 1 votes

---
Tags: discrete-mathematics
---


# Question
Title: Time complexity of code running at most summation(N) times in a loop
Let’s say I have a JavaScript loop iterating over input of size N. Let’s say all elements in N are unique, so the includes method traverses the entire output array on each loop iteration:

```
let out = []
for (x in N) }
  if (!out.includes(x)) {
    out.push(x)
  }
}

```

The worst case runtime of the code inside the loop seems to be not O(N), but the summation of N, which is substantially faster.

Is this properly expressed as O(N^2) overall or is there a standard way to convey the faster asymptotic behavior given the fact that the output array is only of size N at the end of the loop?

# Answer
If i understand you correctly, then the following holds: $\sum\_{k=1}^nk= \frac{n(n+1)}{2} \ge \frac{n^2}{2} = \Theta (n^2)$

Thus there is no asymptotic gain.
> 2 votes

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


# Question
Title: $a^*b^*c^* \setminus \{a^n b^n c^n | n ≥ 0\}$ is not regular using pumping lemma?
$L=a^\*b^\*c^\* \setminus \\{a^n b^n c^n \mid n \geq 0\\}$ can be proved as context-free by partitioning it as $L = \\{a^nb^mc^\* \mid n \neq m\\} \cup \\{a^\*b^nc^m \mid n \neq m\\}$ and further dividing each $\neq$ into smaller and larger. You will have four sets. You can give CFG's for each. Then since CFGs are closed under union, you have your proof.

Now how can I go around proving that $L$ is not regular? If you prove that the each of these four sets are not regular, you still can not prove that the union is not regular, can you?

# Answer
Lets assume towards contradiction that L is regular. Then, by closure properties, we have $\bar L$ is regular, and thus also $\bar L \bigcap (a^\*b^\*c^\*)$ is regular. But calculating it, we find out $\bar L \bigcap (a^\*b^\*c^\*)=\\{a^nb^nc^n\\}$ is **not** regular.
> 3 votes

# Answer
Suppose that $L$ is regular. Take the complement of $L$ and intersect it with $a^\*b^\*c^\*$. You are left with $M = \\{a^n b^n c^n \mid n \ge 0\\}$. Due to the closure properties of regular languages, $M$ is also regular.

Let $n\_0$ be the pumping length of $M$. By the pumping lemma there is some $x \in \\{1, \dots, n\_0\\}$ such that all words $a^{(n\_0-x)+ix} b^{n\_0} c^{n\_0}$ for $i \ge 0$ belong to $M$.

Pick $i=0$ to obtain $a^{n\_0 - x} b^{n\_0} c^{n\_0} \in M$, a contradiction.
> 2 votes

# Answer
Suppose that $L$ is regular, and let $p$ be the pumping lemma constant. Let $w = a^p b^{p+p!} c^{p+p!} \in L$. By the pumping lemma, we can write $w = xyz$ so that $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. Since $|xy| \leq p$, the subword $y$ is composed entirely of $a$'s, say $y = a^t$, where $t \neq 0$. Then $xy^{1+n!/t}z = a^{p+p!} b^{p+p!} c^{p+p!} \notin L$, contradicting the pumping lemma.
> 2 votes

---
Tags: regular-languages, context-free, pumping-lemma
---


# Question
Title: Does an algorithm exist that transforms any connected graph, cyclic or not, into tree form?
I developed an algorithm that transforms any simple connected graph, cyclic or not, into a tree. The resulting tree is syntax-preserving, in a sense that it allows to reconstruct the original input graph and only the original input graph. In other words, the constructed tree preserves adjacency information, while resolving cycles. Moreover, I assume that with the constructed tree allowing to reconstruct only the original input graph, no other graph that is structurally different can exist that would result in an identical tree form.

I did some research on algorithms that transform graphs into tree form, but I was unable to find another algorithm that would work for any simple connected graph like described above. However, I am pretty such there must exist something.

So maybe one more experienced in graph theory can help me out. It would be highly appreciated.

Alex

# Answer
In a general graph, the number of edges can go up to $\mathcal{O}(n^2)$ (where n is the number of verticies). But in a tree, that number is always $n-1$.

Then, we understand that its impossible to convert a graph to a tree preserving syntax without increasing the memory for each node by a linear factor, or increasing the number of nodes significantly.

Let us define a unique number for every node (in any way you like).

The algorithm now will be:

1. Let $\mathcal{T}$ be the tree from the BFS algorithm on the graph (starting from node 1, for uniqueness)
2. For every edge $e=(i,j)$ in the graph, that is not in $\mathcal{T}$ already, w.l.o.g assume $i\le j$, and add a new node with value $j$ to $\mathcal{T}$, and a connection between it and the (original) node $i$ in the tree.

Note that in the new tree, there will be a lot of nodes that have the same number.

To reconstruct the original graph, we will do the following:

1. Create a node for every unique number in $\mathcal{T}$.
2. Add an edge $(i,j)$ if there is a node with number $i$ that has an edge to some node with value $j$
> 0 votes

---
Tags: graphs, trees
---


# Question
Title: Lambda calculus without free variables is as strong as lambda calculus?
First question: How would one prove that by removing free (unbound) variables from lambda calculus, and allowing only bound variables, its power is not reduced (it is still Turing-complete) ?

Second question: Is the proposition given above really true? Is lambda calculus sans free variables really Turing-complete?

# Answer
I'm assuming you are referring to the untyped lambda calculus.

If so, write $\newcommand{\num}\[1\]{\ulcorner #1 \urcorner}\num{n}$ for the Church numeral of the natural unmber $n$.

It is known that there exists a closed term (i.e., without free variables) $TM$ such that $$ TM\ \num{i}\ \num{n}\ =\_{\beta\eta}\ \num{m} $$ if, and only if, the $i$-th Turing machine (in some standard enumeration) run with input $n\in\mathbb N$ (encoded as usual) halts returning $m$ as output.

Indeed, writing $TM$ is a standard "programming" exercise in the lambda calculus. For that, one can represent the tape as a pair-or-pairs-of-pairs-of... (AKA a cons list) of symbols. Then a "stepping" subroutine to advance the tape and the TM state can be written. Finally, the stepping subroutine is invoked until a halting state is reached. This last step can be achieved using a fixed point combinator such as $Y$.

Since we can simulate any Turing machine, we get Turing completeness.

---

Alternative proof, which is (in my opinion) easier to actually perform in full detail: prove that any general recursive function can be $\lambda$-defined using a closed lambda term. For that, proceed by induction on the definition of general recursive function.

Indeed, even if you do not aim for closed terms, in this programming exercise you will obtain a closed one in a natural way. After all, when programming one never needs a variable which was not declared beforehand.

Since the general recursive functions are exactly those which can be computed by a Turing machine, we get Turing completeness for the closed lambda calculus.
> 2 votes

---
Tags: proof-techniques, lambda-calculus, turing-completeness
---


title: Can a DTM simulate an enumerator E?

text:
# Question
Title: Can a DTM simulate an enumerator E?
An enumerator is defined as a 7-tuple: https://en.wikipedia.org/wiki/Enumerator\_(computer\_science)

A Deterministic Turing machine is defined as a 7-tuple: https://en.wikipedia.org/wiki/Turing\_machine

How are these definitions different? Can a DTM M simulate an enumerator E, for part of its computation can it call an enumerator E as a subroutine and run it to some point then do something with its output etc?

I assume the answer is yes, you can do things like enum in normal programming with universal language / universal machine. Since DTM is usual definition of universal machine it can perform an enumeration-- just want to be sure, maybe I'm wrong and its a fundamentally different kind of machine?

# Answer
Yes. A deterministic Turing machine can simulate another deterministic Turing machine (possibly only up to some point), and an Enumerator is a particular kind of deterministic Turing machine.
> 1 votes

---
Tags: turing-machines, enumeration
---


# Question
Title: Can we specify the pumping length while applying pumping lemma
In all the examples I have seen, the pumping length $p$ is not specified. The string is a pattern that somehow has the $p$. E.g. when proving $L=\\{a^n b^n c^n | n \geq 0\\}$ is not context free, we assume the string $s \in L$ has the form $a^pb^pc^p$, and continue.

Do we have to select such a general pattern?

E.g. Can I just say, $s=aaabbbccc$, where $p=3$, and reason continuing this?

# Answer
The pumping lemma states that if $L$ is regular, then $\exists p.\forall w.\exists x,y,z. w=xyz \wedge$ they can be "pumped"

Thus to show that $L$ is **not** regular, we must show $\neg(\exists p.\forall w.\exists x,y,z. w=xyz \wedge$ they can be "pumped"$)$ which is equivalent to $\forall p. \exists w. \forall x,y,z.w=xyx\wedge($ all other requirements given in the lemma$)\rightarrow\exists.n$ they cannot be "pumped" n times

This shows us its **nessecary to never assume what p is.**

Furthermore, it explains why we need to find only one word (which depends on p).
> 1 votes

---
Tags: pumping-lemma
---


# Question
Title: How do you represent an r.e. complexity class with a list of TMs?
In this book ‘Theory of computation’ By Dexter Kozen on page 313,exercise 127 he says "A set of total recursive functions is recursively enumerable (r.e.) if there exists an r.e. set of indices representing all and only functions in the set. For example, the complexity class P is r.e., because we can represent it by an r.e. list of TMs with polynomial-time clocks." How do you do what he is talking about for any collection of languages that is r.e.? How do you represent an r.e. complexity class with a list of TMs? What is an example of an enumerator that does this for any r.e. class C?

# Answer
> 0 votes
Its easy to iterate through all turing machines - simply iterate through all strings, and pick the ones that actually represent a TM.

I think its possible to iterate through all $P$ by iterating through all turing machines, and for each one to add a "clock" that counts the number of steps and halts after some polynomial time.

---
Tags: complexity-theory, turing-machines, enumeration
---


# Question
Title: Is X+Y sorting problem still an open problem?
I have found that `X + Y sorting` is an open computer science problem but that book was too old and then I have google it but didn't find any strong evidence that it is still open or there is an algorithm that can solve it in O(n2) comparison without using `Fast Fourier Transform`.

Is there any algorithm proposed that can solve it in O(n2) comparison or `is it still unsolved`?

# Answer
> 3 votes
Here the problem status is "open". The page was revised in 2006 and it seems updated to September 2017, so we can safely suppose that the problem is still open. Anyway, an algorithm that solves the problem using $O(n^2)$ comparison (and total complexity $O(n^2\cdot \log(n))$) is known from 1992: J.-L. Lambert, *Sorting the sums $x\_i+y\_j$ in $O(n^2)$ comparisons*, Theoretical Computer Science, (1992):103, 137–141 doi 10.1016/0304-3975(92)90089-X.

---
Tags: algorithms
---


title: PDA with more than one initial state

text:
# Question
Title: PDA with more than one initial state
I'm wondering if PDAs with more than one initial states are also accepting context free languages.

If found that question on this site about NFAs and would like to know if this answer is also valid for PDAs if one defines a new single initial state and connects this with the former initial states using $\epsilon : \epsilon \to \epsilon$ transitions?

# Answer
PDAs that are allowed to have more than one initial state (let's call them PDAIs) are computationally equivalent to conventional PDAs:

* Trivially, every conventional PDA can be considered as a PDAI that happens to have one initial state.
* Every PDAI can be converted to an equivalent PDA with the process you describe.

So yes, PDAIs accept exactly the context free languages.
> 2 votes

# Answer
Yes this is possible. In fact, if we take out the non-determinism from the PDAs, then we end up with something that is computationally significantly weaker!
> 0 votes

---
Tags: formal-languages, automata, context-free, pushdown-automata
---


# Question
Title: Proof for palindrome grammar by induction
I can't seem to find a solution to the following question.

> Given the following grammar for palindromes:
> $$G\_{pal}=\\{\\{a,\dots,z\\},\\{P\\},P,R\\},$$ with $R$ consisting of the rules
> $$P \to \epsilon \mid a \mid aPa\text{ for every }a \in \Sigma.$$
>
> Prove that every palindrome $w$ is in $L(G\_{pal})$:
>
> $$w = w^r \longrightarrow w \in L(G\_{pal}).$$

# Answer
To show $w\in L(G\_{Pal})$, Show with induction on **word length** the lemma: "If $w=w^R$ then $P\rightarrow...\rightarrow w$"

* basis is simple. Do it yourself.
* assume $|w|=n+1$ and we know that every $\hat w$ with $\hat w = \hat w^R, |\hat w|\le n$ satisfies, $P\rightarrow...\rightarrow \hat w.$ Then: define $\hat w:=w\_{2,...,n}$. since $w=w^R$ then also $\hat w = \hat w^R$. But $|\hat w|\le n$, thus $P\rightarrow...\rightarrow \hat w$. Now we can derive $w$ since we know we can derive $w'$: $P\rightarrow w\_1Pw\_1\rightarrow w\_1Pw\_{n+1}\rightarrow...\rightarrow w\_1\hat ww\_{n+1}=w$

We have shown that $w$ can be constructed from $P$ in the grammer. So $w=w^R\rightarrow w\in L(G\_{Pal})$

Note that in order to show that this grammer is correct, **this is not enough.** you will need to also show that $w\in L(G\_{Pal})\rightarrow w=w^R$
> 0 votes

---
Tags: formal-languages, finite-automata
---


# Question
Title: NFA-$\epsilon$ extended transition function for inverted strings
It is well known that in $NFA-\epsilon$ the extended transition function is defined as it follows: \begin{align\*} \hat\delta: Q &\times \Sigma^\* \rightarrow \mathbb{P}(Q) \\ \hat\delta(q,\epsilon) &= ECLOSURE(q) \\ \hat\delta(q,\alpha x) &= \bigcup\_{p\_i \in \hat\delta(q,\alpha)}ECLOSURE(\delta(p\_i,x)) \text{ for } \alpha \in \Sigma^\* \text{ and } x \in \Sigma \end{align\*}

I would like to give an equivalent definition for the function but now considering an string $w \in \Sigma^\* $ such that $w = x\alpha$ with the same definitions for $x$ and $\alpha$ given above. But what I've only got is the base case (i.e. $w = \epsilon$) which is pretty the same. Any hints to define the function like that?

# Answer
> 2 votes
First, there's a typo at your definition of $\hat\delta$. Case $\hat\delta(q,\alpha x)$ should be $\bigcup\_{p\_i \in \hat\delta(q,\alpha)}ECLOSURE(\delta(\color{green}{p\_i},x))$ (green for highlighting the difference).

The equivalent definition in terms of a string given as $(x\alpha)$, where $x\in\Sigma$ and $\alpha\in\Sigma^\*$, is $$ \hat\delta(q,x\alpha) = \bigcup\_{p\_i \in ECLOSURE(\delta(q,x))} \hat\delta(p\_i,\alpha) $$

---
Tags: formal-languages, automata, finite-automata
---


# Question
Title: Default scan order in SCAN and LOOK disk scheduling algorithms
I've been learning various disk scheduling algorithms in Operating systems. I wanted to know if there was any default scan order in SCAN, C-SCAN, LOOK and C-LOOK algorithms, like towards higher cylinders or lower cylinders ? Or are they OS-specific ?

# Answer
There is no specific order. In SCAN, C-SCAN, LOOK and C-LOOK we have to start moving towards the closest cylinders as in SSTF or you can start moving towards a direction in which there are less number of requests and then move towards the other
> 0 votes

---
Tags: operating-systems, scheduling
---


# Question
Title: SCAN and CSCAN algorithms of disk scheduling
I am having hard time understanding the working of SCAN and CSCAN algorithm of disk scheduling.I understood FCFS,Closest Cylinder Next but heard that SCAN resembles elevator mechanism and got confused. My book says that for the incoming order :\[10 22 20 2 40 6 38\] (while the disk currently at 20) the SCAN moving at the start serves \[(20) 20 22 38 40 10 6 2\]; this requires moves of \[0 2 16 2 30 4 4\] cylinders, a total of 58 cylinders. How does the pattern \[(20) 20 22 38 40 10 6 2\] came?

# Answer
> 1 votes
In the SCAN algorithm (also called Elevator algorithm) the disk head, when servicing requests, will move in one direction until it reaches the edge of the disk.

For example consider a disk with 5000 sectors. If we assume the head begins at sector 0 it will move the head over every sector from 0 to 4999, servicing any requests on sectors as it moves. When the head reaches sector 4999 it will reverse the movement direction and repeat the process, servicing any requests as it progresses back to sector 0.

The C-SCAN modification is very similar. If we, again, assume the disk head is at sector 0 it will begin moving from 0 to 4999. Upon reaching sector 4999 the disk head immediately returns to sector 0, no requests are serviced during this movement.

For the example you've given \[10 22 20 2 40 6 38\], and the head at sector 20. The arm begins moving, I will assume that it is moving in the positive direction as that is what the answer seems to indicate.

REQUESTS: \[10 22 20 2 40 6 38\]; READ: \[ 20 \]

REQUESTS: \[10 22 20 2 40 6 38\]; READ: \[ 20, 22 \]

REQUESTS: \[10 22 20 2 40 6 38\]; READ: \[ 20, 22, 38 \]

REQUESTS: \[10 22 20 2 40 6 38\]; READ: \[ 20, 22, 38, 40 \]

REQUESTS: \[10 22 20 2 40 6 38\]; READ: \[ 20, 22, 38, 40 \]

As 40 is the largest sector in the queue we would now expect the arm to seek to the edge of the disk. Since it's not given I assumed 40 was the last block. Thus the arm reverses seek direction.

REQUESTS: \[10 22 20 2 40 6 38\]; READ: \[ 20 22 38 40 10 \]

REQUESTS: \[10 22 20 2 40 6 38\]; READ: \[ 20 22 38 40 10 6 \]

REQUESTS: \[10 22 20 2 40 6 38\]; READ: \[ 20 22 38 40 10 6 2 \]

In the case of C-SCAN the order of the last three requests is reversed. The arm would seek to 0 and then begin producing \[ ... 2 6 10 \]

# Answer
> 0 votes
SCAN works like an elevator does. It scans down towards the nearest end and then when it hits the bottom it scans up servicing the requests that it didn't get going down. If a request comes in after it has been scanned it will not be serviced until the process comes back down or moves back up. So in your case from 20,22 is the closest so it starts moving in that direction. Continuing `20,22,38,40,end` now reversing head and moving in the opposite direction i.e. from end to `10,6,2.` So the order should be `20,22,38,40,end,10,6,2 for SCAN` and `20,22,38,40,10,6,2 for LOOK`.

---
Tags: computer-architecture, operating-systems, scheduling
---


# Question
Title: Construct a PDA that recognizes the following language: L={uawb: u,w ∈ {a,b}*, |u|=|w|}
I am having trouble finding the PDA with 1 state for this one. So far my solution is this but i cant figure out how to get to 1 state.

Alphabet: {a, b}, Stack alphabet (the first symbol is the initial one): $ S (this can be changed,i just wrote these 2), Acceptance condition: empty stack, Deterministic (DPDA): false

Thank you

# Answer
You can create a CFG for the language and then use this explanation on how to transform a CFG into a (1 state) PDA
> 2 votes

---
Tags: pushdown-automata
---


# Question
Title: Why high and lower bit of generator must be 1?
Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 213:

> When the polynomial code method is employed, the sender and receiver must agree upon a **generator polynomial**, $G(x)$, in advance. Both the high- and low-order bits of the generator must be 1. To compute the CRC for some frame with $m$ bits corresponding to the polynomial $M(x)$, the frame must be longer than the generator polynomial. The idea is to append a CRC to the end of the frame in such a way that the polynomial represented by the checksummed frame is divisible by $G(x)$. When the receiver gets the checksummed frame, it tries dividing it by $G(x)$. If there is a remainder, there has been a transmission error.

My question is how do you determine high order bit? And why high order bit and lower order bit, both must be one? From my understanding, it is used to detect burst error but is my understanding true?

# Answer
The low order bit, also known as the least significant bit (LSB), is the "ones" bit of the number. For example, in 001101, the LSB is the rightmost bit 00110**1**.

The high order bit, also known as the most significant bit (MSB), is the "topmost" bit of the number. In our example 001101, it is the leftmost bit **0**01101.

The two terms are also used figuratively (in general discourse): a high order bit is something important, and a low order bit is something not important.

Now to your question. We represent a message $m\_0,\ldots,m\_n$ by a polynomial $M(x) = \sum\_i m\_i x^i$. Given a generator polynomial $G(x)$, the idea is to extend the message to a new message $M'(x)$ that satisfies $G(x) \mid M'(x)$.

If the low order bit of $G(x)$ is zero, then such an extension isn't always possible. Indeed, the low order bit of $G(x)$ is zero iff $x \mid G(x)$. If this is the case, then $G(x) \mid M'(x)$ implies $x \mid M'(x)$, i.e. $m\_0 = 0$. So if the lower order bit of $G(x)$ is zero, we will only be able to extend $M$ to $M'$ if $m\_0 = 0$ (and even this is not necessarily a sufficient condition).

If the high order bit of $G(x)$ is zero, then the problem is a different. The probability that $G(x) \mid M'(x)$ for a random $M'$ is $2^{-\deg G(x)}$ (assuming $G$ is irreducible, that is, cannot be factored nontrivially). Therefore CRC offers us $\deg G(x)$ bits of protection. We therefore want $G(x)$ to have the maximum degree possible. This corresponds to having a high order bit of one.

In practice, $G(x)$ is stored without its high order bit: an 8-bit CRC polynomial really corresponds to 9 bits 1xxxxxxxx, but there is no need to store the 1.
> 1 votes

---
Tags: error-correcting-codes
---


# Question
Title: Efficient algorithm to map two differently-sized sets of numbers as closely as possible?
## The problem

I have two sets of numbers and need to find a mapping between those two sets, so that the total distance between two mapped numbers is as small as possible. Two numbers must not be mapped if they are farther apart then `0.18`. As many numbers should get mapped as possible.

Also, the sets are not necessarily the same size. So, consequently, some numbers of the larger set won't get any mapping.

Example:

Is there a reasonably efficient algorithm that finds a mapping like this? Or, is there a term for this specific problem so that I can research algorithms on my own?

## My research

Through googling I encountered this question, which led me to the term "Euclidean Bipartite Matching Problem" which seems to be the term for a problem very similar to mine. However, my problem is slightly different than the Euclidean Bipartite Matching Problem.

So basically, I'm looking for an efficient algorithm for the 1-dimensional Euclidean Bipartite Matching Problem *except* that the two sets of numbers can be of differing size, and the distance between two numbers must not exceed `0.18`.

## My attempt

I've already coded my own implementation, however... it doesn't work properly and is pretty complicated too so that I'm not even sure *why* it doesn't work.

As for the basic idea behind my implementation: let's call the first set the *red numbers* and the second set the *blue numbers* (apparently that's the terminology used in the Euclidean Bipartite Matching Problem). Now;

1. go through all red numbers, and for each:
    1. find the closest blue number within a ±0.18 range
    2. if the blue number is already assigned to a different red number:
        * if the existing assigned red number is nearer than our red number, skip this blue number
    3. assign our red number to the blue number
    4. if we overwrote a previously-assigned red number in the process, make the red number find itself a new blue number (i.e. make the red number go through steps 1-4 again)

(I'm doubtful that this implementation is even correct) but yeah, this is what I tried so far.

---

Are there well-known algorithms to do this task, so that I don't have to create a wonky, non-functioning, slow implementation myself? Or in general, is there a term for this specific problem? Then I could google for that term and find what I need.

I'll be happy about any answer or pointers :)

# Answer
This can be solved by reduction to the unbalanced assignment problem.

Build a bipartite graph where the vertices are the two sets of numbers, and there is an edge from a vertex in one set to a vertex in the other set if and only if the distance between the numbers is less than or equal to 0.18. Set the weight of each edge to the distance between the two numbers.

The goal is to find a **minimum-weight maximum bipartite matching** in this graph. Some minimum-weight bipartite matching implementations will do this directly.

If you only have access to an implementation that requires a fixed output matching size, you can still solve this by adding extra edges with arbitrarily huge weights (any value larger than 0.18 times the size of the smaller vertex set) to make a complete bipartite graph. Then throw out any mappings in the output that have the arbitrarily huge weights. This works because the minimum weight guarantee ensures that as few as possible of the edges with arbitrarily huge weights will be chosen in the output assignment.
> 1 votes

---
Tags: algorithms, bipartite-matching
---


title: Solving Exact2IS using IS

text:
# Question
Title: Solving Exact2IS using IS
i encountered the following problem:

Exact2IS ={G has exactly 2 independent sets}

Assuming that given a graph G i can find an independent set how can i check if G has exactly 2 independent sets.

(i can check if a graph contains independent set in O(1) and also find some independent set in O(1))

I was thinking on find some independent set(if there is any) of size k and then remove one vertex from the set and check if the graph still has independent set of size k -after i check i return the vertex to the graph exactly as it was.

The problem my idea check only if a graph G contains at least 2 independent sets and not exactly.

Anyone have an idea how can i check if a graph has exactly 2 independent sets(in polynomial time and given the fact that find and check if there is independent set is O(1))?

Any clues or ideas will be appreciated :) Thanks

# Answer
> 3 votes
First of all, if you can determine whether a graph $G$ contains an independent set of size $k$, then you can also find such a set efficiently. This is known as "search-to-decision reduction". Here is the basic idea. Choose an arbitrary vertex $v$, and remove it. If the graph still has an independent set of size $k$, then keep going. Otherwise, all independent sets of size $k$ contain $v$. Accordingly, remove $v$ and all its neighbors, and find an independent set of size $k-1$ in the remaining graph. In this way, you can recover an independent set of size $k$.

Second, how to check whether a graph contains *at least* two independent sets of size $k$, assuming $k \geq 2$. First, you determine whether in contains at least one. Suppose that it does, say $I$. If $J$ is any other independent set, then $I \setminus J$ and $J \setminus I$ are both nonempty (since $|I| = |J|$). In particular, if $x \in I \setminus J$ and $y$ is any other vertex in $I$, then even after adding the edge $(x,y)$, the set $J$ will constitute an independent set.

This leads to the following algorithm: for each pair of vertices $x,y \in I$, check whether $G + (x,y)$ contains an independent set of size $k$. If so, this independent set is necessarily different from $I$. Conversely, if an independent set of size $k$ different than $I$ exists, then necessarily it will be an independent set in $G + (x,y)$ for some $x,y \in I$.

Third, how to check whether a graph contains *exactly* two independent sets of size $k$. This is the same as checking whether a graph contains at least *three* independent sets. I think that at this point, it's better if you try to generalize the above argument from two to three independent sets. You might get stuck, but you won't know until you try.

# Answer
> 0 votes
If you are allowed to **find** an IS of size $k$ in $\mathcal O(1)$, then what you have written is *almost* the solution. just twice find an IS of size $k$, and after that check to see if there still is another one.

But usually, for oracle machines, you are not allowed to find an (in this example) IS within $\mathcal O(1)$ time, and you are only allowed to **check if one exists** within $\mathcal O(1)$.

I hope this helps!

---
Tags: algorithms, complexity-theory, computability, polynomial-time-reductions
---


# Question
Title: O(m+n) Algorithm for Linear Interpolation
# Problem

Given data consisting of $n$ coordinates $\left((x\_1, y\_1), (x\_2, y\_2), \ldots, (x\_n, y\_n)\right)$ sorted by their $x$-values, and $m$ sorted query points $(q\_1, q\_2, \ldots, q\_m)$, find the linearly interpolated values of the query points according to the data. We assume $q\_i \in (\min\_j x\_j, \max\_j x\_j)$

I heard off-hand that this problem could be solved in $O(m+n)$ time but can only think of an $O(m \log n)$ algorithm. I can't seem to find this particular problem in any of the algorithm textbooks.

# Linearithmic Algorithm

```
interpolated = []
for q in qs:
    find x[i] such that x[i] <= q <= x[i+1] with binary search
    t = (q - x[i]) / (x[i+1] - x[i])
    interpolated.append(y[i] * (1-t) + y[i+1] * t)

```

This gives us a runtime of $O(m \log n)$, it's unclear to me how to get this down to $O(m + n)$ as the search for $x\_i$ must be done for every query point.

# Answer
> 0 votes
You only need to perform binary search for the first element and then iterate simultaneously through the data points and query points.

# Pseudocode

```
interpolated = []
find x[i] such that x[i] <= q[0] <= x[i+1] with binary search

for q in qs:
    while not x[i] <= q <= x[i+1]:
        i++
    t = (q - x[i]) / (x[i+1] - x[i])
    interpolated.append(y[i] * (1-t) + y[i+1] * t)

```

---
Tags: algorithms, machine-learning, search-algorithms, numerical-algorithms
---


# Question
Title: How to define an automata for zig zag concatenation?
I have two DFAs one for language A and one for language B. I'm asked to make an FDA that is the zig-zag concatenation of letters of A and letters of B. This is described by the following: {w: w = $a\_1 b\_1$...$a\_k b\_k$ and $a\_1...a\_k \in A$ and $b\_1 ... b\_k \in B$}. With $1 \leq i \leq k$ and $a\_i \in \Sigma$ and $b\_i \in \Sigma$

This automata should be described as a 5-tuple {Q, $\Sigma$,$\delta$,$q\_0$,$F$}.

I simply do not know how I would go about defining the total function $\delta$.

This is what I tried:

$Q = Q\_A \cap Q\_B$ // We only want the words that contains both a and b

$F = F\_A \cap F\_B$ // The accepted states should contain both letter from a and from b.

$q\_0 = q\_A$ //because the word starts with a letter from a.

$\Sigma$ // in this problem we aren't interested in defining the alphabet we just leave the symbol as is in the 5-tuple.

# Answer
let $Q=Q\_A\times Q\_B\times \\{1,2\\}$ (1 means A, 2 means B)

also define $F=F\_A\times F\_B\times \\{2\\}$ (we end with B)

and $q\_0=(q\_A,q\_B,1)$ (we start with A)

with the delta function: $\delta ((q\_1,q\_2, i),\sigma)= \begin{cases} (\delta(q\_1,\sigma),q\_2,2) &i=1 \\ (q\_1, \delta(q\_2,\sigma),1) &i=2 \end{cases}$

The idea is to encode both A and B together, with some "index" telling us if we need to check A or B
> 2 votes

---
Tags: regular-languages, finite-automata, closure-properties
---


title: Regular languages, automata

text:
# Question
Title: Regular languages, automata
I want to ask about the definition of regular languages. My book says there has to exist a deterministic finite automaton that recognizes it. Does this mean the finite automaton recognizes exactly this language and nothing else or it can recognize possibly some other words not in the language?

# Answer
> 0 votes
It means the automaton recognizes **exactly** it. in fact, you can even build an automaton that accepts every word (try to do it yourself), so there would be no meaning in the other definition

# Answer
> 0 votes
You can think of it as of a correct implementation of an algorithm in different programming languages. No matter which implementation you choose they all do exactly the same thing described by the algorithm.

Regular expressions or deterministic finite automata are just two different "programming languages" for implementing a regular language. If an automaton imlements the language correctly, it will recognize **exactly the same set** of words that are in the language.

---
Tags: finite-automata
---


title: Computing average access time

text:
# Question
Title: Computing average access time
```
A computer has a cache memory and a main memory with the following features:

```

\- Memory cache access time: 4 ns \- Main memory access time: 80 ns \- The time needed to load a line in cache is 120 ns. \- Write-through policy. If the hit ratio in this computer is 95 % and the 90% of the memory accesses are read operations, what is the average access time?

It seems a bit weird to me since I have read through this site calculate the effective (average) access time (E AT) of this system but I still do not know how to do it. I would appreciate any help. Thanks!

# Answer
This is just a single-level cache, then? That means just two possibilities when accessing: a hit or a miss, with hit rate + miss rate = 100%. It follows that the average is simply the time spent with hits and the time spent with misses, which comes out to:

hit rate * hit time + miss rate * miss time
> 1 votes

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


title: Zigzag concatenation of two languages

text:
# Question
Title: Zigzag concatenation of two languages
Given two regular languages $A,B$ on the same alphabet $\Sigma$, I want to show that the following language is regular: $$ \\{a\_1b\_1 \ldots a\_kb\_k \in \Sigma^\* \mid a\_1,\ldots,a\_k,b\_1,\ldots,b\_k \in \Sigma,a\_1\ldots a\_k \in A, b\_1\ldots b\_k \in B\\}. $$

However I simply do not understand how I'm supposed to do this. Simply put, my confusion is what $w = a\_i b\_i$ means. Is it concatenation? Does it mean that the word $w$ is the concatenation of $a=a\_1\ldots a\_k$ with $b=b\_1 \ldots b\_k$?

# Answer
Since languages $A$ and $B$ are regular, we can assume there are DFAs $$ M\_A = \\{Q\_A, \Sigma, \delta\_A, s\_A, F\_A\\} ~~\text{and}~~ M\_B = \\{Q\_B, \Sigma, \delta\_B, s\_B, F\_B\\} $$ that recognize them, respectively. Let's call the zig-zag lanuage $Z$. It is easy to see that the alphabet of $Z$ is $\Sigma$.

We will construct a DFA, $M\_Z = \\{Q\_Z, \Sigma, \delta\_Z, s\_Z, F\_Z\\}$, for $Z$.

**Set of states**

$M\_Z$ must be such that it will alternately apply $\delta\_A$ and $\delta\_B$ each time it reads a character from the input string. For that, it must be able to track all possible combinations between states of $M\_A$ and $M\_B$, as well as which of the two transition functions it should apply on the next transition. We will use 0 to represent that the next transition should be a $\delta\_A$-move and $1$ for a $\delta\_B$-move. Altogether, we have $Q\_Z = Q\_A \times Q\_B \times \\{0,1\\}$.

**Initial state**

Clearly, the initial state of $M\_Z$ is $s\_Z = (s\_A, s\_B, 0)$.

**Accepting states**

For a state $q\_f = (q\_A, q\_B, i)$ of $M\_Z$ to be accepting, both $q\_A$ and $q\_B$ must be accepting states of $M\_A$ and $M\_B$, respectively. This is to satisfy the conditions $a\_1\ldots a\_k\in A$ and $b\_1\ldots b\_k\in B$ in the definition of $Z$. In addition, the last transition before reaching $q\_f$ should be a $\delta\_B$-move, therefore the next transition (if there is one) is expected to be a $\delta\_A$-move, represented with $i = 0$. So, the set of accepting states is $F\_Z = F\_A\times F\_B\times\\{0\\}$.

**Transition function**: Here is where the alternating behavior of $M\_Z$ is constructed.

If the DFA is in a 0-state, then it should perform a $\delta\_A$-move, leading to a 1-state. The DFA still needs to remember the (non-active, for now) state of $M\_B$. A similar behavior, but with 0 and 1 switched, is adopted for transitions from 1-states. \begin{align\*} \delta\_Z((q\_A, q\_B, 0), x) &= (\delta\_A(q\_A, x), q\_B, 1)\\ \delta\_Z((q\_A, q\_B, 1), x) &= (q\_A, \delta\_B(q\_B, x), 0) \end{align\*}
> 2 votes

---
Tags: regular-languages, finite-automata, closure-properties
---


# Question
Title: Finding largest farthest increasing pairs in array?
Is there a simple linear algorithm for finding in an array A two such elements that $A\[i\] \> A\[j\]$ and $i - j$ is as large as possible? If one wants to actually return the indices, then linear memory usage seems impossible to avoid. If the only result needed is the value $i - j$, i.e. the distance, can we get away with less than linear memory?

Obviously, one can use constant memory if one is willing to loop over all pairs (i, j).

# Answer
> 2 votes
I'm going to assume that in your question, $i \> j$ holds as well (if there is no such pair of values, then you have a nonincreasing array and the problem is trivial).

The two alternatives you've pointed out in your post are

* $O(n)$ additional memory and $O(n)$ time
* $O(1)$ additional memory and $O(n^2)$ time

An "intermediate" solution, for example, is to pick $O(\frac{n}{B} + B)$ additional memory and $O(n \cdot \left(\frac{n}{B} + B)\right)$ time. To do this, divide the array into continguous blocks of size $O(B)$, and so the number of blocks is $O(\frac{n}{B})$. For each block, store only the minimum value of the block in an array `block_minimum`.

Say you're at the $i$-th index. The goal is to find the first index in the array where the value of the corresponding element is greater than `A[i]`.

First, for all preceding blocks, find the first block $j$ for which `block_minimum[j] < A[i]`. If such a block exists, scan that block and find the first index $k$ belonging to the block for which `A[k] < A[i]`. The index $k$ is the first index of the array for which `A`. There are $O(\frac{n}{B})$ preceding blocks.

However, if such a block doesn't exist, then second, iterate on preceding elements in the current block (there are $O(B)$ of them).

The combination of the two steps consumes $O(\frac{n}{B} + B)$ time for an index $i$. So the overall time usage is $O\left(n \cdot \left(\frac{n}{B} + B\right)\right)$ and the extra memory usage is $O\left(\frac{n}{B}\right)$ (the number of blocks).

If we choose $B = O(\sqrt n)$, we obtain a solution that uses $O(\sqrt n)$ memory and $O(n \sqrt n)$ time. This technique is commonly known as *square-root decomposition*.

# Answer
> 0 votes
First of all, it seems that there is no comparison-based linear time algorithm for this problem. Though I have no formal proof yet.

If we assume that array $A$ consists of only positive integer values and each value is bounded by $O(n)$ (here and after $n$ is a length of an array $A$), then we can use an idea of counting sort to get a linear time algorithm. That is, let's create an array $B$ such that $B\[i\]$ stores a pair of numbers: minimum and maximum index of elements (let's denote them $B\[i\].min$ and $B\[i\].max$) in array $A$ with value $i$. Obviously, we can compute $B$ in $O(n)$ time using a single run through $A$. Then let's iterate through $B$. On $i$-th iteration let's maintain a value $ M\_i = \min\_{1\leq j\< i} B\[j\].min$. And let's compute $S\_i = B\[i\].max - M\_i$. The maximum over all $S\_i$ is an answer to your problem. Time and memory complexities of this algorithm (under specified assumptions) are both $O(n)$.

---
Tags: arrays
---


# Question
Title: Chromatic number of a graph with $10$ vertices each of degree $8$?
I have simple graph G on 10 vertices the degree of each vertex is 8. I need to determine the chromatic number of G. I tried drawing and all but it seems there is a trick needs to be used.

# Answer
Let $G = (V, E)$ be a simple graph like you described (which is unique up to isomorphism and known as the Turán graph $T(10, 5)$, by the way). Note that the maximal degree possible in a graph with $10$ vertices is $9$ and thus, for every vertex $v$ in $G$ there exists a unique vertex $w \ne v$ which is not connected to $v$ and the two vertices share a neighborhood, i.e. $N(v) = N(w)$. Therefore, $v$ and $w$ may be colored using the same color. This however implies that the chromatic number of $G$, denoted by $\chi(G)$, satisfies $\chi(G) \leq 5$ since we can take all such pairs $\\{v, w\\}$ as described above and assign every such pair a unique color (using 5 colors in total).

To see that $\chi(G)$ cannot be less than $5$ consider the (induced) subgraph $G'$ of $G$ that we get by removing one vertex of every such pair $\\{v, w\\}$ as described above (that means $vw \notin E$). We find that $G'$ consists of 5 vertices and is complete, therefore implying that $G$ contains a clique of size $5$ and giving us $\chi(G) \geq 5$.

Hence we have shown $\chi(G) = 5$.
> 6 votes

# Answer
Let $v$ be some node. then it had 8 neighbors, and there is exactly one node $u$ which is not connected to $v$. Notice that also $u$ has 8 neighbors, and thus $v$ is the only node not neighboring it.

We can partition the graph into 5 groups of 2 nodes $V\_1=\\{v\_1,u\_1\\},...,V\_5=\\{v\_5,u\_5\\}$, where every group's node's **are not connected to each other** (there is no edge $(v\_i,u\_i)$) but they **are connected to everything else**.

This is a 5-partition of the graph, and we can give a different color for each pair. Thus the chromatic number satisfies $\chi (G) \le 5$. But if we use less than 5 colors, say, 4 colors, then there must be two groups with a node that has the same color in both, but since that they are connected we get a contradicton to the coloring. Thus $\chi (G) \ge 5$ and finally $\chi (G) =5$

---

***From here, it is a solution to the clique number, and not the chromatic number:***

Since we have 5 groups, Then choosing one node from each group guarantees to give us a clique of size 5. So if we define $\omega (G)$ to be its chromatic number, then in this case we have proven that $\omega (G) \ge 5$.

**Lets assume toward contradiction** that $\omega (G) \> 5$. Then there exists a clique of size at least 6. Let that clique be $\\{w\_1,..,w\_6\\}$. From the pigeonhole principle, we have that there are two $w\_i, w\_j$ in the same $V\_k$. But then **there is no edge between them**, in contradiction that this is a **clique**.

Thus $\omega (G) \le 5$ and finally combining those two together we have $\omega (G)=5$
> 2 votes

---
Tags: graphs
---


# Question
Title: Asymptotic of divide-and-conquer type recurrence with non-constant weight repartition between subproblems and lower order fudge terms
While trying to analyse the runtime of an algorithm, I arrive to a recurrence of the following type :

$$\begin{cases} T(n) = \Theta(1), & \text{for small enough $n$;}\\ T(n) \leq T(a\_n n + h(n)) + T((1-a\_n)n+h(n)) + f(n), & \text{for larger $n$.} \end{cases}$$ Where:

* $a\_n$ is unknown and can depend on $n$ but is bounded by two constants $0\<c\_1\leq a\_n \leq c\_2 \< 1$.
* $h(n)$ is some "fudge term" which is negligeable compared to $n$ (say $O(n^\epsilon)$ for $0\leq \epsilon \< 1$).

If $a\_n$ was a constant, then I could use the Akra-Bazzi method to get a result. On the other hand, if the fudge term didn't exist, then some type of recursion-tree analysis would be straight-forward.

To make things a bit more concrete, here is the recurrence I want to get the asymptotic growth of:

$$\begin{cases} T(n) = 1, & \text{for n = 1;}\\ T(n) \leq T(a\_n n + \sqrt n) + T((1-a\_n)n+\sqrt n) + n, & \text{for $n \geq 2$} \end{cases}$$ Where $\frac{1}{4} \leq a\_n \leq \frac{3}{4}$ for all $n\geq 1$.

I tried various guesses on upper bounds or transformations. Everything tells me this should work out to $O(n\log(n))$ and I can argue informaly that it does (although I might be wrong). But I can only prove $O(n^{1+\epsilon})$ (for any $\epsilon\>0$), and this feels like something that some generalization of the Master theorem à la Akra-Bazzi should be able to take care of.

Any suggestions on how to tackle this type of recurrence?

# Answer
> 1 votes
According to the OP, to complete the proof we need to prove that for large enough $n$, $$ (a\_n n + \sqrt{n})^{a\_n + 1/\sqrt{n}}((1-a\_n)n + \sqrt{n})^{1-a\_n + 1/\sqrt{n}} \leq n. $$ Taking out a factor of $n^{1+2/\sqrt{n}}$, we get $$ (a\_n + 1/\sqrt{n})^{a\_n + 1/\sqrt{n}} (1-a\_n + 1/\sqrt{n})^{1-a\_n + 1/\sqrt{n}} \leq n^{-2/\sqrt{n}}. $$ Dividing by $(1+2/\sqrt{n})^{1+2/\sqrt{n}}$, we get $$ \left( \frac{a\_n + 1/\sqrt{n}}{1 + 2/\sqrt{n}} \right)^{a\_n + 1/\sqrt{n}} \left( \frac{1-a\_n + 1/\sqrt{n}}{1 + 2/\sqrt{n}} \right)^{1-a\_n + 1/\sqrt{n}} \leq \frac{1}{n^{2/\sqrt{n}} (1+2/\sqrt{n})^{1+2/\sqrt{n}}}. $$ Raising to the power $1/(1+2/\sqrt{n})$, and defining $p = (a\_n + 1/\sqrt{n})/(1 + 2/\sqrt{n})$, we get $$ p^p (1-p)^{1-p} \leq \frac{1}{n^{(2/\sqrt{n})/(1+2/\sqrt{n})}(1+2/\sqrt{n})}. $$

The left-hand side is $1/\exp h(p)$, where $h(p)$ is the entropy function. Hence it is maximized when $a\_n = 1/4$, at which point $p \approx 1/4$. Since $(1/4)^{1/4} (3/4)^{3/4} \< 1$, for large enough $n$ we can bound the left-hand side by some $\theta \< 1$. As for the right-hand side, as $n\to\infty$ it tends to $1$. Indeed, taking logarithm, we get $$ \frac{2\log n}{\sqrt{n} + 2} + O\left(\frac1{\sqrt{n}}\right) \longrightarrow 0. $$ In particular, for large enough $n$ it will be larger than $\theta$.

---
Tags: asymptotics, recurrence-relation
---