# Question
Title: complexity of determining whether a language given by context free grammar is empty
I know that it is decidable problem to check whether given context free grammar represents empty language -- for instance, AFAIR one could convert it to Chomsky normal form, and then check if any word of length $\leq 2^n$ (or maybe $\leq 2^{n+1}$, I'm not sure) belongs to the language, where $n$ is IIRC the number of nonterminals in CNF. If not, then no longer words belong either and the grammar is empty.

The above algorithm has the unpleasant property of having exponential complexity. The questions that interest me are:

* Is there a polynomial algorithm to check whether given CFG represents empty language?
* What's the (asymptotically) best known algorithm for that?
* What's the simplest polynomial algorithm for that (not necessarily having best known complexity)?

# Answer
First, omit all terminal symbols. Then the language is empty iff the grammar does not generate the empty string.

An algorithm to check acceptance of the empty string is straightforward. A non-terminal $A$ is nullable, i.e., $A\Rightarrow^\* \lambda$ iff $A \to w$ where each symbol in $w$ is nullable.

Determine the symbols nullable with a derivation tree of depth $k$, $k=0,1,\dots$. First find all $A$ such that $A\to \lambda$. Remove these $A$ from the right-hand side of productions and repeat. Axiom $S$ is nullable iff the language is non-empty.
This can be implemented in linear time, making lists of all productions that contain a certain letter at their right-hand side.

Seems to be equivalent to HORN-SAT.
> 9 votes

# Answer
Let $G=(V,\Sigma, P,S)$ be your context-free grammar, and define $$ W = \\{ A \in V |\\, \exists w \in \Sigma^\* : A \Rightarrow\_G^\* w \\} $$ It's clear that $L\_G \neq \emptyset \Leftrightarrow S \in W$.

You could use this algorithm to determine whether $W$ is empty:

while( $W' \neq W$) do
$ \quad W' = W$
$ \quad W = W \cup \\{ A \in V \\,|\\, \exists w \in (\Sigma \cup W)^\*: (A \to w) \in P \\} $
endwhile

Since a nonterminal doesn't need to be added more than once it should be able to do this in linear time (linear in the number of nonterminals).
> 6 votes

# Answer
Simplest way is to compute the generating symbols (symbols $A$ such that $A \Rightarrow^\* \alpha$ for $\alpha \in \Sigma^\*$), and check if the start symbol is generating. A symbol $A$ is generating if there is a production $A \to \sigma$ with all symbols in $\sigma$ generating. To compute that, start with the terminals (by definition, generating), check all non-terminals if they have productions with right hand sides only generating symbols, and repeat until no more changes.
> 1 votes

---
Tags: complexity-theory, formal-languages, context-free
---


# Question
Title: Given a regular grammar $G$, $L(G) = \Sigma^*$ is decidable?
*This question was made during a class of Computer Theory in Rome, Italy.*

Let $G$ be a regular grammar, $\Sigma$ its alphabet and $L(G)$ the language generated by $G$

> Given a regular grammar $G$, is $L(G) = \Sigma^\*$ a decidable property?

**My approach**

I can design a Finite State Automaton that recognize the strings in the language $G$. Because regular languages are closed under the iteration operation, the FSA recognize also string in $\Sigma^\*$ alphabet

# Answer
By the "iteration operation" you probably mean the Kleene closure of the language. In the case of the language is $\Sigma^\*$ its Kleene closure is clearly equal itself. But you do not provide detailed explanation about how to use this fact to decide whether $L(G) = \Sigma^\*$. However, you could solve the problem as following:

Solution 1: Convert the regular grammar into the corresponding DFA and take the complement of the DFA. The complement of a DFA accepting all strings has not accept state. So you can decide by checking whether or not it has an accept state.

Solution 2: Convert the regular grammar into the corresponding DFA and minimize it. If this DFA accepts $\Sigma^\*$ then the minimal DFA has only one state which is the accept-state. So you can decide by checking if the minimal DFA has only one state which is accept-state .
> 3 votes

# Answer
Build the minimal DFA for the language. If the language is $\Sigma^\*$, it has only one state (start and accepting, looping back on each symbol). The constructions type 3 grammar to NFA to DFA to minimal DFA are all effective.
> 0 votes

---
Tags: regular-languages, decision-problem
---


title: Multi-Path Length Minimization

text:
# Question
Title: Multi-Path Length Minimization
I've been thinking about path planning and am trying to make good heuristics for cases with multiple agents.

Suppose there are sets $S\_i$ of coordinates in $\mathbb R^2$ or $\mathbb R^3$, each of the same size n, for each possible value of $i$ where $i \in \[0, ... k\]$.

A path is defined as k line segments connecting a sequence of k+1 coordinates, made up of one coordinate from each set $S\_i$ in consecutive order. I want to find n paths such that (a) no two paths have the same point for a given index i in the sequence, and b) the combined path length of all the paths is minimized. In other words, assign coordinates from each set without replacement to construct paths with the goal of making the total path length as small as possible.

Right now i can do the minimization from some $i$ to $i+1$, but I am not sure if locally minimizing each step will yield a global minimum. I know I could brute force it, but that explodes really quickly.

# Answer
> 2 votes
You can solve this optimally in $O(kn^3)$ time by solving a sequence of $k$ Assignment problems.

Let $f(i)$ be the lowest sum of costs of any set of $n$ paths beginning at step $i$ and continuing to step $k$ (i.e., the end). We would therefore like to compute $f(0)$, as well as a set of paths realising it.

Assume we have already computed $f(i+1)$. (Clearly $f(k) = 0$, so we have a starting point.) Let $A\_{i,i+1}$ be the solution to the Assignment problem (minimum-weight bipartite matching) in which one set of vertices are the points in $S\_i$ and the other is the points in $S\_{i+1}$. I claim that we can compute $f(i)$ as $A\_{i,i+1} + f(i+1)$.

Suppose this claim is not correct: then for some $i$, there is a better solution with cost $B\_i \< f(i)$, which can likewise be decomposed as $B\_i = B\_{i,i+1} + B\_{i+1,k}$. In particular, let $i$ be the maximum possible $i$ for which $B\_i \< f(i)$. Then at least one of $B\_{i,i+1} \< A\_{i,i+1}$ or $B\_{i+1,k} \< f(i+1)$ must be true for our assumption $B\_i \< f(i)$ to be true.

It cannot be that $B\_{i,i+1} \< A\_{i,i+1}$, since $A\_{i,i+1}$ is the minimum possible cost by definition of the Assignment problem. So it must be that $B\_{i+1,k} \< f(i+1)$. But this cannot be true either, since if it were then it would violate our assumption that $i$ is maximum possible. Thus supposing the existence of a solution with a better cost $B\_i$ leads to a contradiction, so it cannot be true, meaning that $f(i)$ gives the optimal cost after all.

$f(0)$ gives you the *cost of* the optimal solution. To extract such a solution, just record the matchings produced by the Assignments problems you solved along the way.

---
Tags: algorithms, optimization, constraint-satisfaction, algorithm-design, routing
---


# Question
Title: Mcculloch and Pitts Neurons: Is there errata in this article?
The paper A LOGICAL CALCULUS OF THE IDEAS IMMANENT IN NERVOUS ACTIVITY has the following description of neurons, which I question if there is errata or perhaps I need more information to understand this.

Looking at the picture below (b) is described as an OR gate. I'm confused because with either threshold being met on the $N\_1$ or $N\_2$ neuron, with thresholds 1 and 2, there are not enough inputs to reach the threshold of 3 for $N\_3$. So how is this an OR gate?

(c) makes sense because the sum of the input to $N\_3$ is 3 when both $N\_1$ and $N\_2$ are at their thresholds.

Any guidance appreciated.

# Answer
> 0 votes
In the article mentioned, the figures each have a threshold of 2 for each neuron. Therefore there is no errata.

---
Tags: neural-networks, perceptron, theory
---


title: Recursive set for a string

text:
# Question
Title: Recursive set for a string
Given the definition:

```
Let Σ be the alphabet defined as follows:  Σ = {e, l, v}
We now define the set of strings P according to the following:
BASIS STEP: If x ∈ Σ then x ∈ P
RECURSIVE STEP: If w ∈ P and x ∈ Σ, then xwx ∈ P

```

> How to show that the string *level* is in P.

I do understand what is being asked and that I must use the recursive step to produce the target string. But I just don't know exactly how to go about it in a way that is efficient and accurate. Any help with an explanation is greatly appreciated.

# Answer
How about

$$ v \in \Sigma \Longrightarrow v \in P $$ and $$v \in P \land e \in \Sigma \Longrightarrow eve \in P $$ so $$ eve \in P \land l \in \Sigma \Longrightarrow \boxed{level \in P}$$
> 1 votes

---
Tags: recursion
---


title: Schedule X Classes In N Classrooms

text:
# Question
Title: Schedule X Classes In N Classrooms
I would really appreciate any thought on this, or under which category does this problem fall (Interval scheduling, Interval partitioning,...) I am really out of thoughts

I have X number of classes each with starting, and finishing time, and N number of free classrooms. And I want to find the maximum number of non-conflicting classes that can be scheduled in those N classrooms.

What I've tries so far :

# \- First algorithm:

* Sort Classes in ascending order according to the finishing time of each class.
* Starting with the minimal finishing time, pick all the intervals that don't conflict with it and save it in a subset.
* Repeat the first two steps on the very next interval that conflicts with the one we were working on before.

## Why wrong?

Ex: we have 4 classes (1,4) (2,6) (6,7) (4,8) and we want to find the maximum number of non-conflicting ones that can be fit in 2 classes.

* Starting the algorithm on (1,4) will give me subset {(1,4)(6,7)} that can be fit in the first classroom, and in the second classroom i need to put either (2,6) or (4,8) but not both since they conflict, so in total 3 of those classes can be fit in 2 classrooms using this approach.
* However in real life you can put {(1,4),(4,8)} in a room and {(2,6),(6,7)} in the other, so all of the classes can be held in the 2 rooms.

# \- Second algorithm

* Sort Classes in ascending order according to the starting time of each class.
* Starting with the minimal starting time, pick all the intervals that don't conflict with it and save it in a subset.
* Repeat the first two steps on the very next interval that conflicts with the one we were working on before.

## Why wrong?

Ex: we have 4 classes (1,2) (2,1000) (6,7) (7,8) and we want to find the maximum number of non-conflicting ones that can be fit in **1** class.

* Starting the algorithm on (1,2) will give me subset {(1,2)(2,1000)} that can be fit in the first classroom, and that's it, so in total 2 of those classes can be fit in a classroom using this approach.
* However in real life you can put {(1,2),(6,7),(7,8)} in a room and, so 3 of the classes can be held in a room.

# Answer
> 0 votes
The minimal number of rooms needed can be computed by considering the classes in order of finish times, and if a class can't be fit into any one of the rooms in use, create a new room for it. See e.g. Erickson, "Algorithms", section 4.2.

This is the problem of asking if an interval graph can be colored with $N$ colors (the rooms). Perhaps digging into scheduling nets some algorithm(s). It isn't a problem for which I've seen a simple algorithm. Determining if a general graph is $N$ colorable is NP-complete (i.e., no much better solution expected than just trying all possibilities) if $N \ge 3$, perhaps being an interval graph is enough of a restriction to make it tractable...

---
Tags: scheduling, partitions, colorings, intervals
---


# Question
Title: resource on translating imperative programs to functional programs
I'm not asking this question for the purpose of any particular project. Rather, I'm trying to understand how to translate non-trivial programs in imperative style to functional style. By functional program/style I mean one in which all objects are immutable and functions are pure, and so forth.

**The only example I've seen so far of translating imperative code to functional code is for *highly specific and simple code***. In particular, the example that seems to be used a lot is the factorial function, and *translating iteration into recursion*:

```
//imperative -- iteration
int factorial (n)
   for i=1;i<n;i++
      x=x*i;
   end for
   return x;

//functional -- recursion
int factorial (n)
    if (n==1) return 1; else return factorial (n-1) * n

```

However, this is such a specific example of a function (the factorial), that it doesn't make it clear to me how in general to translate core constructs in imperative style to functional style. e.g. can we *always* translate a for loop into recursion?

**I'm looking for a comprehensive textbook or other resource that in generality shows how to translate imperative code to functional code**

* How do we translate the basic building blocks of imperative code to functional code? Can we even do this in general?
* How do we translate some examples of not-completely-trivial (e.g. not the factorial function) programs?
* Especially interesting, are there fully general automated algorithms for doing these translations? Are they actually used? I can imagine that some compilers do something like this.
* (perhaps also interesting, the opposite, translating functional code to imperative code.)

# Answer
> 2 votes
There probably are automated ways of doing it, but the result will be a unreadable mess. You have to *understand* what the imperative program is doing and *rethink* it as a functional program. Not easy.

The point is that many imperative algorithms have a recursive idea behind them (think binary search, mergesort, quicksort, any tree walking), there it is recognizing that starting point and write it functionally.

First rule I try to impress on my students: Programs aren't for the *computer's* consumption, they are principally for *ḧuman understanding*. Humans will have to write it, and modify it if it turns out wrong (be it a bug or a change in requirements). Today the human's time is much more valuable than the computer's (How much does a computer cost? How much does it's time cost, assuming a life of two years? Take any random program, how often will it have to be run to make up for your salary of a week, if that is what it takes to make it twice as fast?).

# Answer
> 1 votes
The lambda calculus is Turing-complete. The proof of this fact gives an automated way to convert imperative code to functional code. The resulting functional code will be a mess and not understandable to humans, but it exists, and the translation is purely automatic.

In general, the strategy is to implement an interpreter for a Turing machine (or any other Turing-complete computing platform, such as a small CPU) in the lambda calculus. This is a straightforward matter of programming. See e.g. https://stackoverflow.com/q/9619139/781723, Why are functional languages Turing complete?.

---
Tags: reference-request, programming-languages, functional-programming, education
---


title: Are all calculations graphs?

text:
# Question
Title: Are all calculations graphs?
I've come to understand that programs are graphs on several layers. Call-graphs are an example that come to mind without a textbook handy, another is mutation flow.

So I do understand that code is a graph, and that compilers and interpreters usually end up traversing the graph according to the rules of the language. It's magic, really, but here is my question:

Are all calculations graphs? Are there calculations that cannot be expressed as a state machine?

# Answer
> 2 votes
I wouldn't say that code is a graph. I would say that graphs are a convenient way to represent some aspects of graphs.

There is a sense in which every computation on your computer can be expressed as a state machine: if your computer has 8 billion bits of memory, then there are at most $2^{8,000,000}$ possible states, so it can be considered as a state machine on that state space. However, that probably isn't a very useful point of view. Instead, we usually model computers as Turing machines (or in another way), and those cannot be expressed as a finite state machine.

The question of whether all computations are graphs doesn't seem well-defined to me. Presumably graphs can be used to represent some aspects of computations, but that doesn't mean the calculation *is* a graph (or that it is nothing more than a graph).

# Answer
> 1 votes
Graphs are very versatile tools, useful for modelling lots of discrete situations (areas in a map and their frontiers, streets in a city, flight connections between cities, geneologies, friendship among people, ...). No wonder programs, computations, ... can be analyzed in their terms (structure, in which function calls which others, in what order instructions are executed, what values influence which others, ...). They also appear as common data structures.

---
Tags: graphs
---


# Question
Title: Solving a modified Travelling Salesman Problem(TSP)
I am trying to solve a modified version of the TSP. In my version, multiple visits to a city are allowed, as long as the path is the shortest, and also, only subset of the cities are compulsory to visit, as in, you can go through other cities to visit all the subset cities if path is shorter, but if not, the other cities can be ignored. For simplicity, starting city is fixed. Also, all cities are not connected to others directly. I know approx. solutions for the traditional TSP, but, I have trouble solving this one. A naive approach can be to find all possible combinations of the subset cities and check which has the shortest total path length, but that solution will have a n^2 complexity for trying each combination, plus the complexity for finding shortest path for each two cities. So, what should I use to solve this problem?

# Answer
As mentioned in the comments, you can compute APSP (All-Pairs Shortest Paths) at first and build the matrix $$D:=\left(d\_{ij}\right)\_{i,j\in\[n\]}$$, where $d\_{ij}$ is the length of a shortest path from the vertex $i$ to the vertex $j$. By solving the usual travelling sales man on the graph $G'$ where $D$ is the adjacency matrix, you get a solution for your version of the problem. Try to see why this works as an exercise.

Your case is actually mentioned in the Wikipedia page under metrics.

Note that $D$ defines a metric and metric TSP admits a polynomial time 1.5-approximation. The same Wikipedia article contains more information about this algorithm under the section "Constructive heuristics".
> 2 votes

---
Tags: algorithms, graphs, traveling-salesman
---


# Question
Title: Termination of Z combinator with call-by-value
I am trying to build my own λ-calculus interpreter. So far it supports both call-by-value and normal order.

I now want to try recursion via fixed points. The $Y$ combinator works with normal order, tested with the faculty function $$\text{fac} = \lambda f.\lambda n.\text{iszero}\\,n\\,1 (\text{mul}\\,n\\, (f(\text{pred}\\,n)))\text{,}$$ and for example my interpreter yields $Y\\,\text{fac}\\,3 \stackrel{\text{NO}}{\rightarrow} 6$. (I'll write behaviourally equivalent Church numerals as decimal numbers)

As far as I know for call-by-value I will need the $Z$ combinator instead:

$$Z = \lambda f. (\lambda x. f (\lambda y. x x y)) (\lambda x. f (\lambda y. x x y))\text{,}$$

as $Y$ would cause an immediate infinite regression.

My problem is, I fail to understand how $Z\\,\text{fac}\\,0$ is supposed to terminate. It also does not terminate in my interpreter, but I want to understand it manually first.

After some steps call-by-value should arrive at: $$Z\\,\text{fac}\\,0 \\\=\lambda f. (\lambda x. f (\lambda y. x x y)) (\lambda x. f (\lambda y. x x y))\\,\text{fac}\\,0 \\\stackrel{\text{CBV}}{\rightarrow}(\lambda x. \text{fac} (\lambda y. x x y)) (\lambda x. \text{fac} (\lambda y. x x y))\\, 0 \\\stackrel{\text{CBV}}{\rightarrow}\text{fac} (\lambda y. (\lambda x. \text{fac} (\lambda y'. x x y')) (\lambda x. \text{fac} (\lambda y. x x y')) y) \\, 0 \\\stackrel{\text{CBV}} {\rightarrow}\text{fac}\\,F\\,0\stackrel{\text{CBV}}{\rightarrow}\text{iszero}\\,0\\,1\\,a\text{,}$$

where the omitted term

$$a=\text{mul}\\,0\\, (F\\,(\text{pred}\\,0))$$ contains

$$F=\lambda y.(\lambda x.\text{fac}(\lambda y'.xxy'))(\lambda x.\text{fac}(\lambda y'.xxy'))\\,y$$ again.

Now, $\text{iszero}\\,0\stackrel{\text{CBV}}{\rightarrow}\lambda t.\lambda f.t$, s.t.

$$\text{iszero}\\,0\\,1\\,a\stackrel{\text{CBV}}{\rightarrow}(\lambda t.\lambda f.t)\\,1\\,a\stackrel{\text{CBV}}{\rightarrow} (\lambda f. 1)\\,a\text{.}$$

If our language had a branching construct that would ignore the $a$ branch we'd be done, but with call-by-value we have to evaluate $a$ to a value, i.e. an abstraction.

$a=\text{mul}\\,0\\, (F\\,(\text{pred}\\,0))$ and $\text{mul}\\,0$ will be another abstraction so next I have to reduce $F\\,(\text{pred}\\,0)$.

$\text{pred}\\,0\stackrel{\text{CBV}}{\rightarrow}0$, so we reduce $F\\,0$.

$$F\\,0 = (\lambda y.(\lambda x.\text{fac}(\lambda y'.xxy'))(\lambda x.\text{fac}(\lambda y'.xxy'))\\,y)\\,0 \stackrel{\text{CBV}}{\rightarrow} (\lambda x.\text{fac}(\lambda y'.xxy'))(\lambda x.\text{fac}(\lambda y'.xxy'))\\,0\stackrel{\text{CBV}}{\rightarrow}\text{fac}\\,F\\,0$$

And now we're back at square one. Am I doing something wrong?

# Answer
I don't think you're doing the reduction wrong, but the problem isn't the Z combinator. The problem is $\text{iszero}$. Branching constructs in call-by-value cannot just take the direct terms for each branch as arguments like they can in call-by-name (or similar), because both branches will be evaluated regardless of the test. This clearly interacts poorly with recursion, but it's also undesirable in general.

Instead, branching constructs in call-by-value should take explicitly delayed arguments. So something like: $$\text{iszero}\ n\ (λ\\\_. 1) (λ\\\_. \text{mul}\ n\ (f\ (\text{pred}\ n))$$ this way the recursive evaluation can be avoided unless it is actually necessary. You could, of course, leave $\text{iszero}$ as is, always use it this way, and provide an extra argument yourself, but I think normally it would be defined to expect delayed arguments.
> 0 votes

---
Tags: lambda-calculus, evaluation-strategies, fixed-point
---


# Question
Title: What are the real world applications of set cover problem?
I am studying about set cover problem and wondering that which problems in real world can be solved by set cover. I found that IBM used this problem for their anti-virus problem, so there should be many more others that can be solved by set cover.

# Answer
> 11 votes
Set-cover heuristics are used in random testing ("fuzz testing") of programs. Suppose we have a million test cases, and we're going to test a program by picking a test case, randomly modifying ("mutating") it by flipping a few bits, and running the program on the modified test case to see if it crashes. We'd like to do this over and over again. If we do this naively, it will be less effective than it could be: typically many test cases cover basically the same code paths, but a small minority of test cases cover unusual code paths that would be interesting to test more intensively.

So, here's one solution that is used in industry. We use a coverage measurement tool to instrument the program and record which lines of code are covered by each of the million test cases. Then, we choose a small subset $S$ of those million test cases that has maximal coverage: every line of code covered by one of the million test cases will be covered by some test case in $S$. $S$ is called a reduced test suite. We then apply random mutation & testing to the reduced test suite $S$. Empirically, this seems to make random testing more effective. The smaller $S$ is, the more effective and efficient testing becomes.

So, how do we choose a reduced test suite $S$ that is as small as possible, while still achieving maximal coverage? Answer: that's a set cover problem, so we use standard heuristics/approximation algorithms for the set cover problem. The standard greedy approximation algorithm is typically used for this purpose.

# Answer
> 5 votes
Not sure if this is a real-world problem – solving sudokus can be reduced to an exact cover problem (note that exact cover is related to set cover, but not the same). You can find similar explanations here. Some fast solvers directly use Knuth's dancing links to solve sudokus, which is usually much faster than naive backtracking. However, the fastest solvers to date actually don't reduce sudoku solving to exact cover. They apply plain backtracking combined with advanced searching heuristics and careful code optimization.

# Answer
> 4 votes
By far the most relevant, large size, important application of set covering is in personnel shift planning (mainly in large airline companies). There, elements to be covered are the single shifts (or single flights), and sets are legal combinations of work/no work schedules. These easily go to millions or even billions of variables, as the number of combination is huge.

# Answer
> 0 votes
Standard examples are the different variants of **tiling problems**. Given a grid of size $n\cdot m$ (possibly with some restrictions/forbidden squares) along with a set of objects (typically dominos pieces, L-shaped pieces or a a collection of pieces), is it possible to cover the grid (avoiding the restricted tiles) with objects without having to objects overlap.

Most variants can be easily reduced to exact cover (as mentioned in other answers a slightly modified version that requires all sets in the answer to be pairwise disjoint). Note that some of the variants are easier and can even be solved in O(1) as the case of a grid without restrictions and dominoes pieces.

---

Aside from that, minimum set cover occurs quite often in industry or as a daily life problem. Say you have a set of potential employees each with a set of skills and you need to select smallest poasible subset that covers all skills. Similarly, given a list of different kinds of fruits, each having its set of vitamins, what is the smallest set of different kinds of fruits covering all the vitamines you need, and so on.

---

Since you tagged graphs in your question, here are two applications of vertex-cover that might be interesting for you. Note that even though both problems are NP-complete, vertex cover is easier in the common sense, since it is a restricted case where each element in the universe appears in at most two subsets (each edge can be covered only by its endpoints).

In different areas of theoretical computer science, solving (bipartite) vertex-cover through bipartite matching algorithms is used as a subroutine. Here are two examples of which:

## Kernalization techniques

Some kernalization techniques require computing a bipartite vertex-cover as a subroutine. For example **Crown decomposition** and **the expansion lemma**. Another standard example is the linear programming kernalization of vertex-cover itself.

As a reference see \[Parameterized algorithms, Marek Cygan et al., 2015\] or \[Kernalization, Fedor V. Fomin et al., 2019\].

---

## Hardness proofs

Vertex-cover is one of the most studied problems. It is one of the easier NP-complete problems (Admitting approximation-algorithms, single exponential exact algorithms, etc..). These two facts make it one of the easiest problems to reduce when proving that a problem is NP-hard or that a problem does not admit certain running times unless ETH/SETH fail.

For NP-hard proofs I would refer to \[Computers and intractability, Michael R. Garey and David S. Johnson, 1979\] and to \[Karp's 21 NP-Complete Problems\]

For ETH and SETH you can refer to the same book of Cygan et al. refered above.

---
Tags: graphs, set-cover
---


# Question
Title: Determining asymptotic notation of a complex function
$$ 5n^4\log{n} - \frac{100n^2}{\log\_4(n^2)} + 40 $$

I am currently studying algorithm analysis and i need to express this function in terms of big O, theta and omega, so I should find C, and N0 for each case I solved big Oh with c=40 and n0 = 1 but I am stuck here any help ?

# Answer
> 2 votes
If you check the definitions, big-O means "bounded from above" (with a fudging constant $c$ multiplying it all, starting at a high enough $n$), you can disregard "constants multiplying" and "slower growing terms"; so you can say:

$\begin{equation\*} 5 n^2 \log n - \dfrac{100 n^2}{\log\_4 n^2} + 40 = O(n^2 \log n) \end{equation\*}$

(could also say $O(n^3)$, or $O(n^4 \log^{10} n)$ for that matter, *bound from above*).

For a lower bound, the same works fine:

$\begin{equation\*} 5 n^2 \log n - \dfrac{100 n^2}{\log\_4 n^2} + 40 = \Omega(n^2 \log n) \end{equation\*}$

For a lower bound, $\Omega(1)$ or $\Omega(n \log n)$ work fine too.

As you have the same upper/lower bound:

$\begin{equation\*} 5 n^2 \log n - \dfrac{100 n^2}{\log\_4 n^2} + 40 = \Theta(n^2 \log n) \end{equation\*}$

Finding values of $c$ and $N\_0$ I leave to you. They *can* be different for $O$ and $\Omega$!

---
Tags: algorithms, algorithm-analysis, time-complexity, notation, big-o-notation
---


# Question
Title: Where to find practical exercises for algorithm analysis?
What is a good book or resource to find practical exercises of analysis of the complexity of concrete algorithm implementations (that is, which asymptotic complexity does a particular code have)?

I'm interested not in solving algorithms but in practising finding out their complexity. I have seen a couple of these kind of exercises in my Discrete Mathematics textbook (Rossen), but I haven't been able to find a good resource to find others.

# Answer
> 0 votes
Textbooks in algorithms are chock full with examples of algorithms, often with analysis. For example, take a look at Erickson's "Algorithms", Dasgupta et al "Algorithms". Looking around for lecture notes will get you a lot of others. Analysis of algorithms requires some specialized techniques, a modern overview is Sedgewick and Flajolet's "Introduction to the analysis of algorithms".

---
Tags: algorithm-analysis
---


# Question
Title: "Subpaths" of Dijkstra's shortest path also shortest?
I have trouble putting this into formal mathematical terms, so let's suppose that I found the shortest path from A to E as A \> C \> D \> B \> F \> E with Dijkstra's algorithm. Am I correct in assuming that the shortest path from C to B would be C \> D \> B, and that the shortest path from D to F would be D \> B \> F?

# Answer
> 3 votes
Of course, it is true. However, it is not a property of Dijkstra's algorithm but is property of the shortest paths themselves. Suppose that is not true, and you have a shorter path from $C$ to $B$, we denote it as $p\_{CB}$. Then we would have a path $A \rightarrow p\_{CB} \rightarrow F \rightarrow E$ from $A$ to $E$ which is shorter than $A \rightarrow C \rightarrow D \rightarrow B \rightarrow F \rightarrow E$.

# Answer
> 1 votes
If you check what Dijkstra's algorithm does, it computes the shortest paths to *all* nodes from a given start node.

---
Tags: algorithms, algorithm-analysis, dijkstras-algorithm
---


# Question
Title: Relation between size of address bus and memory size; memory Segmentation in 8086
My question is related to memory segmentation in 8086. I learnt that,

> 8086 has a 20 bit address bus. And so it can address 2^20 different addresses. Which means it has an memory size of 2^20, i.e, 1MB.

I have a few doubts:

1. What I understand from the fact that 8086 has a 20 bit address bus is that it could have 2^20 different combinations of 0s and 1s, each of which represents one physical address. What I don't understand is that how does 2^20 different address locations mean 1 MB of addressable memory? How is total number of different addresses locations related to memory size (in Megabytes)?
2. Also, correct me if I'm wrong, the 16 bit segment registers in 8086 hold the starting address of the different segments in the memory (Code, Stack, Data, Extra).My question is, aren't the addresses in memory of 20 bits? Then how can the 16 bit register hold 20 bit addresses? If it contains the upper 16 bit of the 20 bit address, how does the processor make out to which exact address location it has to point?

*P.S: I am a beginner is micro-processors and total reliant on self study, so kindly excuse if my questions seem a bit silly.*

Thanks in advance.

# Answer
As for your first question, the memory size and the address space are the same thing. The memory is composed of addresses, where each address contains a value. In the 8086, each address contains 8bit of data. Then, $2^{20}$ addresses means $2^{20}$ records of size 8bit each. As you known, $2^{20}=1$Mega and 8bit=1Byte so 20bits of address means 1Mega addresses x 8bit = 1MegaByte memory.

As for your second question, you are right - the address needs 20bits, and each register is only 16bits. So the solution is to use **two** registers to address each address in the memory. With 2 registers we *potentially* have 32bits, but the address space needs only 20, so the 8086 actually manipulates the two registers to get only 20 bits. Basically, it concatenates 4bits (all zeros) to the first register (so now it is 20bits), and adds the result to the other register. It is easy to verify that every combination of 20bits is accessible via two registers (actually, multiple combinations lead to the same address).
> 1 votes

# Answer
I wish to add an adjustment to the fine response by @Ran G. His explanation of what the address space is, is entirely correct. However, this matches the memory size *only if each and every address is backed by memory hardware*. And this is NOT necessarily the case!

Why could there be less memory hardware than can cover the address space? One trivial answer is cost: Memory hardware can be expensive, so someone wishing to sell a cheaper computer could build one with less than the maximum amount of memory hardware, and this can work because there are people out there who don't need 'that much' memory. For example, no current computer which has 64-bit addressing is ever sold with $2^{64}$ bytes worth of addressable memory (that's over a billion *billion* bytes!).

A more interesting reason is *memory-mapped I/O*. Strictly speaking, one can attach to a processor's address lines *any hardware which behaves like memory hardware* (with respect to the sent address and data read/write action). Normally this is of course memory hardware, but other kinds of devices can use the same protocols. For example: If one has a robot arm with motors in its several joints, plus pressure sensors on its gripper, then one can control the arm with a computer via a card which maps the signals sent to the motors and received from the sensors to specific addresses, and install that card on the computer's address lines. The advantage being that one can use ordinary instructions to control the device (i.e control becomes a pure software problem). This technique is in fact quite ubiquitous.
> 2 votes

# Answer
That's the beauty of cisc machines. For starters as you can see address bus is 20bit wide but resisters are 16bit wide, so microprocessor will process 16bit at a time.

Now let's answer your questions :

1) Address size has nothing to do with architecture size. You can have instructions that can map 64bit or 128 bit address space in instructions. For example mov can be hard coded in hardware itself to fetch next addressing scheme as required which eliminates requirements of same size bus and resistors. The same mov command with proper bit masking can use address of special resistors instead of memory spaces. It drills down to the choice of system architecture. Thus the name complex instruction set. It goes beyond this simple explanation, but to give an idea, instructions are flexible enough to understand addressing schemes.

So answer is no when you are storing resistor data into memory, it refers to 16bit wide data bus. It is still storing data as usual way. But micro processor can operate on 8bit, 16bit or divide 32bit operation in sub operations as well depending on instruction.

It uses segments to divide memory into usable chunks which is mapped by combing 16bit address scheme but by shifting it to 4bit and adding offset bits to get actual physical address. Modern cpu uses dedicated hardware called memory management unit having multiple operating mode of direct memory access and IO access as well.

Here's the quote :

> Rather than concatenating the segment register with the address register, as in most processors whose address space exceeds their register size, the 8086 shifts the 16-bit segment only four bits left before adding it to the 16-bit offset (16×segment + offset), therefore producing a 20-bit external (or effective or physical) address from the 32-bit segment:offset pair. As a result, each external address can be referred to by 212 = 4096 different segment:offset pairs.

2) Answer to this question is linked on how 8086 translates address to segments. As you can see it doesn't add offsets immediately but directly uses address schemes to map physical address without adding extra hardware. It's a clever way of addressing and doesn't require offset as it's already mapped to stored address space which is kind of 32bit wide when you add address+offset, enough to store 4GB space which you can see in 80386 models. Making it backward compatible as well.
> 1 votes

---
Tags: memory-management, cpu
---


# Question
Title: Minimum circles to cover a set of points and avoid another set of points
Points are in 2d euclidean space. Given a set of n points, A, and a set of m points, B, what is the minimally sized set of circles such that this set of circles covers all points in A and no point in B is covered by a circle?

circles can have arbitrary radius

any thoughts about the difficulty of this problem? any thoughts on non trivial exact algorithms?

# Answer
> 3 votes
The following algorithm will find *some* set of circles, containing all the points in the set $A$ except all the points in the set $B$. This solution might be not optimal (please see the @j\_random\_hacker counterexample in comments), and it's unclear how close this solution will be to the optimal one. The time complexity of this algorithm is exponential, cause it needs the Set Cover Problem solution as one of its steps.

**Step 1.** Build Voronoi Diagram of the set $B$. This diagram will consist of *cells*, *nodes*, *line segments* and *rays*. Each node will correspond to (at least) three points from the set $B$, and each ray will correspond to exactly two points from the set $B$.

**Step 2.** For each Voronoi node construct a **maximal empty open disk** with center in this node. These disks will have (at least) three points from the set $B$ on their boundary, and they won't contain any points from the set $B$. The number of such disks will be $\Theta(|B|)$.

**Step 3.** For each Voronoi ray construct a **maximal empty open disk** with center at this ray and infinitely large radius - it'll be actually a *halfplane*, corresponding to two points from the *convex hull* of the set $B$. These "disks" will have exactly two points from the set $B$ on their boundary, and they won't contain any points from the set $B$. The number of such "disks" will be $\Theta(|B|)$.

**Step 4.** For each point from the set $A$ find all disks, constructed above, containing this point. Each such point may belong to more than one disk, and each disk may contain any number of points from zero to $|A|$. Find a **minimal subset** of the set of all disks, which contains all the points from the set $A$. This is the classic Set Cover Problem, which is NP-complete (it's tempting to try to use geometric nature of this sub-problem to accelerate the search, however it won't be possible - please see the Geometric Set Cover Problem page for more details).

---

I'm thankful to @DiscreteLizard for pointing my error out in the previous version of this answer, and for suggesting the term "disk", which looks more adequate than the "circle".

---

I'd call this problem a "Bomber Problem" - we try to use a minimal number of bombs to strike all needed locations except some friendly ones. Sorry for militaristic jargon!

# Answer
> 3 votes
If $B$ is empty, just pick a single circle. Otherwise, here's a way to turn this continuous problem into a discrete (but still probably hard) problem:

**Lemma:** There exists an optimal solution in which every circle falls into one of the following cases:

1. It has diameter zero and is centred on an $A$-point.
2. It has at least 2 $A$-points on its boundary, and some $B$-point a very small distance $\epsilon \> 0$ from its boundary.
3. It has at least 3 $A$-points on its boundary.

**Proof sketch:** Suppose we have an optimal solution. For any circle with no $A$-points on its boundary, shrink it (keeping the centre in the same position) until it does: Notice that shrinking never causes a point that was outside the circle to move inside it, so this never causes a $B$-point to become covered. Do this for all circles, until all circles have at least one $A$-point on their boundary. If that is the only $A$-point in the circle, shrink that circle all the way down to diameter 0 and centre it at that point.

Second, for any circle that has only one $A$-point on its boundary but at least one other $A$-point inside it, "pull-shrink" it towards the boundary point until at least one more $A$-point lies on its boundary. By "pull-shrink" I mean: Keep that boundary $A$-point on the boundary, and move the circle centre some distance $x$ along the straight line towards it, thereby also reducing the circle's radius by $x$. Pull-shrinking also never causes a point that was outside the circle to move inside it. Think of lying a cylinder on the ground so that it could roll, and putting a smaller-diameter cylinder inside it: the smaller cylinder lies completely inside the larger one, touching it only at the very bottom point.

Finally, "puff out" each circle until either an $A$-point inside it almost escapes (lies on the boundary), or a $B$-point outside it almost touches the boundary, whichever happens first. By "puff out" I mean: Keep the 2 boundary $A$-points on the boundary, and move the circle centre away from them along their perpendicular bisector, causing it to enlarge. Unlike shrinking and pull-shrinking, puffing out can cause points that were inside the circle to move outside, and vice versa. That's why we need a more flexible stopping condition. (For this process to terminate, it may actually be necessary to move the circle centre in the opposite direction, which initially shrinks it: This is necessary if there are no $B$-points in the half-plane defined by the line connecting the two boundary $A$-points and containing the circle centre. Since we have assumed $|B| \ge 1$, at least one of the two half-planes contains a $B$-point, so at least one of the two movement directions will cause the circle to eventually get within $\epsilon$ of a $B$-point, which is all that matters for this proof.)

Starting from an arbitrary optimal solution, after performing these steps, we have constructed a same-size (i.e., optimal) solution that still covers all $A$-points, avoids all $B$-points, and in which each circle either has diameter zero, or has at least 2 $A$-points on its boundary, in addition to either a third boundary $A$-point or a $B$-point just outside its boundary. What this means is that it suffices to consider *only* solutions in which each circle has this property.

---

Since **any 3 non-collinear points lie on the boundary of exactly 1 circle**, we need only consider a finite-size set of circles to choose from:

1. The $|A|$ diameter-0 circles centred on $A$-points.
2. The at most $|B|{|A| \choose 2}$ circles formed by choosing any 2 $A$-points and any $B$-point, which are not collinear, to lie on its boundary, excluding those that contain a $B$-point.
3. The at most $|A| \choose 3$ circles formed by choosing any 3 non-collinear $A$-points to lie on its boundary, excluding those that contain a $B$-point.

Of course, you can also get rid of any circle whose $A$-points are completely contained by some other valid circle, and doing so should speed things up.

To solve the problem, generate these $O(n^3)$ circles and solve a Set Cover problem in which the set of items to be covered is $A$, and each circle contributes a set, namely the set of $A$-points that it covers.

It may be that the Euclidean structure in the problem means that some asymptotically faster algorithm can be used than a general Set Cover solver.

# Answer
> 2 votes
The following randomized incremental algorithm finds a set of disks, containing all the points from the set $A$ except all the points from the set $B$, in polynomial time. It's unclear, how close this set of disks will be to the optimal solution.

The algorithm maintains a disk set, containing a subset of the set $A$ and not containing any points from the set $B$. Points from the set $A$ are inserted into the disk set one by one. The disk set can change at each step. The algorithm ends after all the points from the set $A$ are inserted into the disk set.

**Step 1.** Randomly choose a point $p\_1 \in A$ and create a disk $D\_1$ with center in the point $p\_1$ and zero radius. Create a disk set $S=\\{D\_1\\}$.

**Step $i$ for $i \gt 1$.** The previously constructed disk set $S=\\{D\_1,\dots,D\_k\\}$ contains points $\\{p\_1,\dots,p\_{i-1}\\} \subset A$ and doesn't contain any points from the set $B$. Randomly choose a point $p\_i \in A \setminus \\{p\_1,\dots,p\_{i-1}\\}$ and perform following operations.

* If the point $p\_i$ is contained in some disk from the set $S$, then this set isn't changed - step $i$ is done.
* Otherwise randomly scan disks from the set $S$ trying to find an *expandable disk* \- a disk $D$, which can be expanded to contain all the points it contained previously *plus* the new point $p\_i$. This expanded disk can be constructed easily, however to be *expandable* it must meet additional condition - **this disk must not contain any points from the set $B$**.
* If such expandable disk $D^\*$ is found, replace the disk $D$ by the disk $D^\*$ in the set $S$ \- step $i$ is done. If an expandable disk is not found, create a new disk with center in the point $p\_i$ and zero radius. Add this disk to the set $S$.

Each step of this algorithm will need to scan at most $n$ disks, and for each expanded disk - verify its intersection with all the $m$ points from the set $B$. So, the running time of this algorithm is obviously $O(n^2m)$. This estimate can be improved using more sophisticated data structures for sets $S$ and $B$.

The algorithm can be generalized to work with any types of obstacles instead of isolated points - segments, polygons etc.

---
Tags: algorithms, optimization, computational-geometry
---


title: Is my grammar correct and context free?

text:
# Question
Title: Is my grammar correct and context free?
I have this language

$L = \\{a^{n}b^{3n}c^{2m} : m,n \ge 1\\}$.

I have to determine a free context grammar that generates L. Looks easy BUT i have a question about the grammar I found. First things first, this is my grammar:

$S \Rightarrow BC$

$ B \Rightarrow aBbbb\ \backslash \ abbb $

$ C \Rightarrow Ccc \ \backslash \ cc$

Looks easy and clean to me. I already tested it with strings of different lengths and seems working just fine. Also it does indeed create only strings contained in L and no other strings.

My question is:

This is the first time I generate a grammar without any production containing $S$ itself (An example would be adding $S \Rightarrow B$ and I would solve my problem, because B generates only $a$'s and $b$'s and the number of this chars is dipendent between one another but indipendent with the number of $c$'s inside the string).

Recursively speaking, this works just fine but using $S$ would induce me to create a noncontracting language (because I'd be forced to invert some Non Terminals in order to produce both $a$'s and $b$'s correctly if something is wrong in my grammar). Is this way of creating grammars correct? Can I describe what I wrote as an actual "grammar"? Is it context free?

Also, can I actually derivate $a$ through $B$ without a nonterminal $A$ and without generating it with the $S$ production?

# Answer
Your context-free grammar is just fine. It is not actually necessary for the grammar to have a production with **$S$** in its right-hand side. In fact, a context-free grammar need not have *any* recursive productions or mutually-recursive productions, though the generated language in that case may be quite limited. It is also not necessary to use any particular names for your nonterminals (e.g there is no need for **$A$** to appear anywhere).
> 1 votes

# Answer
Check your definitions. Mine says there is an alphabet of *nonterminals* $N$, an alphabet of *terminals* $\Sigma$ (where $N \cap \Sigma = \varnothing$, essentially "you can tell what is what"), a finite set of *productions* of the form $A \to \alpha$, where the left hand side $A \in N$ (a single non-terminal) and the right hand side $\alpha \in (N \cup \Sigma)^+$ (terminals and non-terminals in any order, at least one; you can allow empty right hand sides as an extension), one of the nonterminals is designated as starting symbol.

That's it. Note that this allows "nonsense" like no productions at all, no productions for the start symbol, symbols that are never used, unconnected pieces. No restriction on how/where a symbol is used. The reason is simple: less restrictions make the definition easier to check and to use. So you can construct something (like it is done for example when building a grammar from a PDA) and it is easy to check it is a CFG, even if it contains lots of useless junk (that wold be messy to eliminate in general). Any "nonsense" is either filtered out because it leads nowhere, or can be eliminated if you are really so inclined. You will see the same in much of mathematics, and this is a branch of mathematics. Take a look at other definitions (like the ones of the different automata), you'll see similar allowance for "nonsense" if you look closely.
> 0 votes

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


# Question
Title: Do exponential functions grow faster than logarithmic?
For example:

$f(n) = n(log\_2 n)^4$ vs $g(n) = n^{1/3}$

Does f(n) grow slower than g(n) as a general rule, even for decimal exponents? I tried doing a limit test but symbolab limit calculator is saying that Steps are currently not supported for this problem.

I graphed them over a large range and it does appear that g(n) grows asymptotically faster.

# Answer
> 1 votes
I think you may be confused about the definition of Big O - graphing `f(n)` and `g(n)` shows `f(n)` surpassing `g(n)` at nearly every scale.

`O(f(n)) > O(g(n)` because `g(n)` is a fractional power polynomial, which is by definition sublinear (if you linearly plug numbers into a square root, cube root, etc., the rate at which the output increases decreases with each successive computation). `g(n)` is a "n log star n" polynomial meaning it follows the form of a log to a power multiplied by n. The rate of growth of these types of functions far exceeds fractional polynomials and its not hard to see why - n is a term of the function, so we know its *at least* linear.

Here's a helpful resource: https://en.wikipedia.org/wiki/Time\_complexity#Table\_of\_common\_time\_complexities

---
Tags: time-complexity
---


# Question
Title: Do closure properties for languages go the other way?
For example I know the union of 2 either decidable or recognizable languages is decidable or recognizable. But say the union of two languages is decidable, does this tell us anything about themselves?

# Answer
No, it doesn't tell us much. Intuitively, union erases information; it's not normally a reversible operation.

So, for example, the union of a language with its complement is clearly decidable and recognizable, regardless of any category in which the language might or might not belong.
> 1 votes

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


# Question
Title: What makes a pseudorandom generator, a high quality one?
Reading this answer to this SO question: Why do we not combine random number generators?, it talks about

> very high-quality PRNG (Pseudo Random Number Generator)

so it makes me wonder what constitutes a high-quality PRNG, I assume you can sum it up as it being "more random", but

* Question1: Which qualities of a PRNG are used to describe how 'random' or 'good' it is?
* Question2: If you have a 'bad quality' PRNG, is there a way to make it better quality?

# Answer
There are several criteria for the quality of a PRNG:

* How fast it is. This includes how fast it is to setup it, and how fast it is to produce a single bit (amortized).
* How difficult it is to guess the next bit given all previous bits.
* How difficult it is to distinguish between output of the PRNG and truly random bits.

The last two criteria are strongly related.

If you have a bad quality PRNG, you can often make it better by *hardness amplification*. Take several copies of the PRNG (using different random keys) and XOR them together. In many (though not all) cases this will significantly improve its quality.
> 8 votes

# Answer
There are practical considerations: How easy to use? How fast? How easy is it to produce a different sequence of random numbers? How easy is it to replay the random numbers (for example, if you generated 10 billion random numbers, can you generate the exact same 10 billion random numbers again?)

The big question: Do the numbers generated behave like a sequence of random numbers? The first PRNG that I ever used had the bizarre property that of two consecutive values, the second was larger with probability about 0.6. Not very random. So you can run all kinds of statistical tests and check if your random number generator behaves in a random way. The more it behaves like random, the better.

And then comes cryptographical randomness. If I give you the last n random numbers, and complete knowledge how the random number generator behaves, can you predict the next random number? If yes, that makes it unsuitable in situations where you have adversaries.
> 1 votes

# Answer
I would add a **uniform distribution** to the list of desired qualities.
> 0 votes

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


title: Asymptotics of a logarithmic series

text:
# Question
Title: Asymptotics of a logarithmic series
Given that,

$T(n) = \sum\_{i=2}^{n} \log\_i n$

I need to find the asymptotic boundary of $T(n)$.

Answer given is $\theta(n)$. Please provide explanation.

# Answer
First, the change-of-base formula may be helpful here: $$ \log\_b(x) = \frac{\ln x}{\ln b} $$ Also, with sums I always find it helps to write out the sum explicitly, so let's do that: $$ T(n) = \sum\_{i=2}^{n} \log\_i n = \log\_2(n) + \log\_3(n) + \log\_4(n) + \cdots + \log\_n(n) $$

Now if you want to show this is $\theta(n)$, there are two things: you should show it is lower bounded by $cn$, and it is upper bounded by $Cn$, for some constants $c$ and $C$.

* For the lower bound, use the fact that each term is greater than or equal to $1$.
* For the upper bound, I suggest dividing the sum into two parts: from $i = 2$ to $i = \sqrt{n}$, and $i = \sqrt{n}$ to $n$. So the first part is $$ \left(\log\_2(n) + \log\_3(n) + \log\_4(n) + \cdots + \log\_{\lfloor\sqrt{n}\rfloor}(n)\right). $$ Here we have $\sqrt{n}$ terms, each which is at most $\log\_2(n)$. The second part is $$ \left( \log\_{\lceil \sqrt{n} \rceil}(n) + \cdots + \log\_n(n) \right). $$ Here we have at most $n$ terms, but you can show (using the change of base formula above) that each term is at most $2$.

Now adding up the two parts, you should get an upper bound of $$ \sqrt{n} \log\_2(n) + 2n, $$ so the final step is to show this is $O(n)$.
> 2 votes

# Answer
First off, $\log\_i n = \ln n / \ln i$, so your sum is:

$\begin{equation\*} \sum\_{2 \le i \le n} \dfrac{\ln n}{\ln i} = \ln n \sum\_{2 \le i \le n} \dfrac{1}{\ln i} \end{equation\*}$

The last sum has no simple form. We can approximate it as an integral:

$\begin{equation\*} \sum\_{2 \le i \le n} \frac{1}{\ln i} \approx \int\_2^n \frac{d t}{\ln t} \end{equation\*}$

This is known as the Eulerian logarithmic integral $\operatorname{Li}(n)$ (see here), it can be shown that $\operatorname{Li}(n) \sim n / \ln n$ if $n \to \infty$. Thus you get:

$\begin{equation\*} \sum\_{2 \le i \le n} \dfrac{\ln n}{\ln i} \sim n \end{equation\*}$

Would need a bit of polish (use integrals to bound the sum from below/above, and use bounds on $\operatorname{Li}(n)$) to make if airtight.

(Here we write $f(n) \sim g(n)$ if $\lim\_{n \to \infty} f(n) / g(n) = 1$)
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Dynamic selection of cache replacement policy
There are some different cache replacement policies could be implemented in CPU. As far as I know, ones have better hit ratio on specific type of code than others, but if that type changes (for example, loops and scan of long file), other replacement policy may become more effective. Did somebody try to investigate how to choose a specific replacement policy at runtime using some statistic information from previous CPU usage? What is this information? Do you know some articles or books about that?

# Answer
> 0 votes
"Adaptive Insertion Policies for High Performance Caching" (PDF) uses set dueling (where a portion of sets are assigned to different policies for tracking) to select insertion as LRU (next victim). Intel Ivy Bridge appears to use such.

For streaming accesses, one could exploit the stride-based prefetchers to detect such and choose cache bypassing (where data is not allocated to particular levels of cache), the use of specialized buffers, or the use of LRU insertion. Stride-based prefetchers retain the addresses of recent cache misses — or accesses — and check for constant offset patterns. By itself the ability to prefetch data can justify cache bypassing (the latency cost is avoided and the bandwidth-to-outer-cache cost may be acceptable), but one would typically also want to predict reuse distance (see, e.g., "Instruction-based reuse-distance prediction for effective cache management" PDF) to avoid excess refetching (when reused "soon") or cache contamination (for relatively large reuse distances).

# Answer
> 0 votes
Various processors have had instructions that affect cache operations. Some examples:

1. Clear cache line. This takes a memory address, allocates a cache line for it, and sets all data in the memory area contained in that cache line to values with no information content (usually all zeroes). This allows then storing data without reading the cache line.
2. Uncached read. This takes a memory address, reads the data, but doesn’t write it to the cache.
3. Prefetch: This takes a memory address and loads the data into cache without giving the results to the CPU. So when the data is needed later it’s already in the cache, no wait needed.
4. Streaming: Whenever data is read, the processor starts filling either the next or the previous cache line.

---
Tags: cpu-cache, caching
---


# Question
Title: Finding pairs $a \in A$, $b \in B$ where $a \ge 3b$ in linear time
There are two sorted arrays A and B containing distinct values. How to find all the pairs $(a,b)$ such that $a \ge 3b$ and a is in A and b is in B. This needs to be done in linear time.

I have tried solving it but it is taking me $n \log n$ time, not $n$. I simply use binary search to look for the value of $b$ corresponding to $a$. But in worst case it will come up as $n \log n$ only.

I have tried to read about it online but found nothing and kind of stuck for the past 2 days. I just want some hints to move in the right direction because I feel that maybe I am missing something very fundamental.

# Answer
If you need to list all output pairs, as you say, then the problem can't be solved in any less than quadratic time, for the reason that the output may be of quadratic size. Imagine that $A$ and $B$ are both half the input (say, both length $n$), and \begin{align\*} A &= \[3n + 1, 3n+2, 3n+3, \ldots, 4n-1, 4n\] \\ B &= \[1, 2, 3, \ldots, n\] \end{align\*}

Then the output to your problem is all pairs of an element in $A$ and an element in $B$, and there are $n^2$ such pairs.

Probably there is an additional fact you haven't mentioned, that you don't have to produce *all* pairs, but you just have to produce a more compact representation of the output (e.g. for each $a \in A$, you only need to produce the *maximal* $b \in B$ such that $a \ge 3b$).

### A hint for this altered version, where you only need the maximal $(a,b)$ pairs:

Imagine you are iterating through both $A$ and $B$ at once, instead of just iterating through $A$ or $B$ separately. So, you are keeping two pointers, one into $A$ and one into $B$. Suppose you have found the maximal pair for $a$, so you know $(a, b)$, and the next element in $A$ after $a$ is $a'$. What should you do?
> 3 votes

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


# Question
Title: Constructing Noneterministic Finite Automata (NFA) with a "not" condition
I have a question about some theoretical CS. Particularly, designing an NFA diagram (nondeterministic finite automata) from some conditions.

I think I understand how to construct NFA's under most simple circumstances, however, the types that I am struggling with are *not* conditions.

Here is one that has me really stumped:

Σ = { a, b, c }

Consider the language L:

L = { ω | ω ϵ Σ\*, ω does not contain "cbac" }

I'd like to use the lambda-transition (λ-transition) to simplify this a bit. I am struggling with. How do I consider this condition?

Any help would be greatly appreciated!

# Answer
> 1 votes
First construct the DFA which accepts any string that DOES contain "abaa". Then interchange final vs non-final! *(note: this only works with a DFA, not an NFA)* The rest you have already figured out.

---
Tags: finite-automata
---


title: Does Turing machine have no shift?

text:
# Question
Title: Does Turing machine have no shift?
In a Turing machine I read that it can go only right or to left. But in my book \[elements of theory of computation, Book by Christos Papadimitriou and Harry R. Lewis \] it says that Turing machine operates in two discrete steps 1) put the control unit in new state. 2)Either: replace the symbol already there by the symbol currently scanned. Or Move read/write head one tape square left or right

In many online tutorials they say you must move read/write head right/left but you may not change state

Can someone please clear the doubt

# Answer
There are a lot of slightly different definitions of Turing machines out there! They usually differ in small but subtle ways. For example, some authors say that a Turing machine's head moves left or right, and writes the symbol; some authors say that it can also stay still. You have seen that Papadimitriou and Lewis allow *either* replacing the character on the tape, *or* moving left or right, which is slightly different than *both* replacing the character on the tape *and* moving left or right.

That sounds like bad news, but the good news is that you can prove that all of these different definitions are equivalent. Your textbook will have some exercises related to that. For example, we can prove:

* That Turing Machines that can move left, right, or stay still are equivalent to ones that just move left or right.

**Proof Idea:** The Turing Machine that can only move left or right can "mimic" staying still by first moving one step to the right, then moving one step to the left. It takes $2$ steps instead of $1$, but it does the same thing.
* That Turing Machines that move the head **OR** write a symbol are equivalent to those that move the head **AND** write a symbol at each step.

**Proof Idea:** the one that moves-or-writes can simulate the behavior of the one that moves-and-writes by first writing, then moving. So it takes $2$ steps instead of $1$, but it does the same thing. On the other hand, the one that moves-and-writes can simulate the behavior of the moves-or-writes one as follows: in order to move without writing, it should write the same symbol that is already on the tape (so that the write has no effect). And in order to write without moving, it should move left and then right, so that there is no net effect.
> 4 votes

---
Tags: turing-machines, computation-models
---


# Question
Title: What is the differences and similarities between refinement type and liquid types?
Looking at the examples here and here both refinement type and liquid types look very similar. What are the differences and similarities?

# Answer
> 3 votes
They are, to a first approximation, the same thing. "Liquid types" come from LiquidHaskell (, ), which is a programming language and verification framework based on refinement types. The Scala repository that you link to is an implementation of refinement types for Scala.

In terms of programming language theory, *refinement types* is the technically correct and more general term. LiquidHaskell and the Scala repository are examples of implementations of refinement types.

# Answer
> 2 votes
Your second link gives an answer, in 'The Liquid Story (Further Reading)':

* a dependant type depends on an arbitrary expression
* a refinement type depends on a logical predicate of a specification language
* a liquid type depends on a logical predicate of a decidable specification language

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


# Question
Title: What happens when the words transfered on the bus are smaller than its width?
So what happens if we're transfering lots of 8 bit words in a 32 bit bus? Does each bus cycle only transfers 8 bit at the time, wasting the other 24 lines of the bus? Or does it transfer 4 words in each bus cycle?

# Answer
> 4 votes
I would say "it depends":

* most likely you ask for 8 bits to be retrieved and you get 8 bits and ignore the other 24 lines;
* if you know you're dealing with sequential data, that you want to consider bytewise, you could retrieve 4 bytes at a time, but you'll have to split or handle the retrieved 4 bytes in code.

On specific architectures you have alignment considerations.

Specifically addressing your question, no, it is very unlikely a system would retrieve 4 words in each cycle only to then "split" them into single words to process, without a program catering for that itself.

# Answer
> 1 votes
It transfers 4 8-bit words on each bus cycle. I would not say the other 24 lines are wasted; the data on them is unused and may have no valid values. Writing code and trying to put 3 8-bit words on those lines would waste time; each cycle (either reading or writing the bus) has 32 bits of data or instruction on it. Therefore, it is more efficient (and easier) to just send the 8 bits as part of the 32 and ignore the (useless) data on the other 24 lines.

This is really a conceptual question and not a question about the workings of the bus. The processor's job is to faithfully transfer 32 bits on each cycle. It does not know which of those bits are important to you, the programmer. It does not know or care whether it contains 2 BCD digits, 8-bit ASCII, 8-bit unsigned integer, 16-bit signed integer, 32-bit floating point, or a 32-bit instruction. The processor's state machine guided by your program must work together to use only those parts of the data which are important to the task at hand. If you only want to transfer 8-bit words, the receiving process (your program) must make sure it only uses the proper 8 bits of the 32 bits sent to it.

# Answer
> 1 votes
There are 4 common hardware approaches (that I know of) for reading and writing octets (8-bit bytes).

The bus controller inside the CPU can be divided into 2 types, which I will here call "simple" or "caching". Both of these types can be combined with either one of 2 major types of hardware bus.

The vast majority of hardware buses are either:

* Some hardware buses are only support full-width reads and writes -- they are word-oriented. For example, the program memory of the Microchip PIC16 series only supports full-width 14-bit reads; the PDP-8 only supports full-width 12-bit reads and writes; many DSPs with 32-bit or 24-bit data buses; many internal buses in floating-point units only support reading or writing complete 64-bit floating point numbers; etc.
* Some hardware buses have individual octet-select lines -- they are byte-oriented. For example, the conventional PCI bus; the 68000 series; the ZipCPU; etc.

## byte-oriented hardware buses and simple bus controller

In this one specific case, then when transferring lots of octets (8-bit bytes), each memory cycle transfers only 8 bits, wasting the remaining lines of the data bus.

With a simple bus controller, then with either kind of hardware bus, when the CPU executes a "LOAD BYTE" instruction, that instruction takes a full memory cycle for each LOAD instruction, and all the data lines except for the 8 bits of interest are ignored.

With a simple bus controller, and a bus with byte-select lines, when the CPU executes a "STORE BYTE" instruction, that instruction takes a full memory cycle, the bus interface activates only a single byte-select line, and all the data lines except for the 8 bits corresponding to that byte-select line are ignored -- only the selected byte of memory changes.

## word-oriented hardware buses and simple bus controller STORE

In this specific case, when transferring lots of octets (8-bit bytes), 2 full memory cycles transfer only 8 bits, wasting the remaining lines of the data bus.

With a word-oriented bus, there's no way to simply change one byte of memory with a single memory cycle. So when the CPU executes a "STORE BYTE" instruction, a simple bus controller -- in order to ensure only one byte of memory is changed -- reads the entire word, modifies the appropriate byte, and then writes out the entire (modified) word.

## caching bus controller

When transferring lots of 8-bit words, a caching bus controller can often (but not always) transfer a full word in each memory cycle (with 32-bit data bus, a full 4 octets each memory cycle).

When the CPU executes a "LOAD BYTE" instruction, often that octet is already in the cache, and so it doesn't use up any DRAM memory cycles.

However, when CPU executes a "LOAD BYTE" instruction, sometimes that octet is not already in cache. So the CPU reads the entire cache line into cache. (Many popular processors have a cache line size of 64 bytes = 512 bits; with a 32-bit data bus, reading a cache line requires 16 memory cycles).

Similarly when the CPU executes a "STORE BYTE" instruction, often that octet is already in the cache, so it doesn't use up any DRAM memory cycles -- it just updates that octet in cache. Later, that entire cache line will be written out.

However, when the CPU executes a "STORE BYTE", sometimes that octet is not already in cache. Some systems use the byte-select lines in combination with a write-around cache policy to immediately write that byte to DRAM, transferring only 8 bits, wasting the remaining lines of the data bus. Other systems use a fetch-on-write cache policy to read the entire cache line into cache, then update just that one byte in the cache. Later, that entire cache line is written out.

A lot of software deals with long UTF-8 strings or long ASCII strings that are always read or written from beginning to end. Starting to read such a string with a caching bus controller causes it to start to pre-load the rest of the string in the cache, so (except at the very beginning and very end of the string) each 32-bit memory cycle reads a full 4 octets of the string. After writing such a string from beginning to end with a caching bus controller, when that string is later flushed from the cache (except at the very beginning and very end of the string) each 32-bit memory cycle writes a full 4 octets of the string.

One popular desktop processor has a cache line size of 64 octets = 512 bits; with a 32-bit data bus, writing out that cache line requires 16 memory cycles. If we are lucky, a lot of "write combining" has occurred and 64 (or more !) of our octet writes have hit this cache line, so each 32-bit write memory cycle is in response to a full 4 octets (or more!) of updated data. In the worst case of random byte writes (which fortunately doesn't happen with typical software), this can theoretically cause "write amplification" where each byte written expands to 16 read memory cycles and 16 write memory cycles.

related: "Transferring \< 4 byte data on a 32-bit system"

---
Tags: computer-architecture
---


title: Algorithm Running Time

text:
# Question
Title: Algorithm Running Time
I'll do my best to explain my question but what I'm wondering is how to calculate a theoretical running time of an algorithm. In my textbook I have questions written as such:

> If a $\Theta(\log\_2{n})$ algorithm requires 20 seconds to execute on an input of one million elements, approximately how long should it take on an input of two million elements?

The answer it gives is 21 seconds and I'm stuck on how they come up with that number.

# Answer
Basically, the complexity of an algorithm gives the relation of the change in the running time with respect to the change in the input size. You can think it as,

$log\_2(1M)$ -\> 20 sec

$log\_2(2M)$ -\> ? sec

$log\_2(2M) = log\_2(2 \*1M) = log\_2(2) + log\_2(1M) = 1 + 20 = 21 sec$
> 1 votes

# Answer
If an algorithm has time complexity $T(n) \in \Theta (\log\_2 n)$, then it means that $T(n)$ is bounded above and below by constant factors of $\log\_2 n$ for sufficiently large $n$. This definition actually leaves a lot of room for possible $T(n)$, and the question in your textbook makes some additional assumptions (or uses a very loose definition of "approximate").

If $T(n) = \log\_2 n + c$, then $T(2n) = T(n) + 1$, so $T(10^6) = 20$ implies $T(2 \cdot 10^6) = 21$.

However, it could also be that $T(n) = k \log\_2 n + c$, in which case $T(2n) = T(n) + k$. Note that the complexities $\Theta(\log\_2 n)$ and $\Theta(\log n)$ are equivalent, and you would typically choose the simplest possible function to express the growth rate. By writing $\Theta(\log\_2 n)$, the textbook is abusing notation to let you know that $k = 1$.

Even then, more complicated expressions are possible e.g. $T(n) = \log\_2 n + A \log\_2 (\log\_2 n) + B \cos n$. Only for sufficiently large $n$ do those additional terms become irrelevant. For any fixed $n$, the answer to your question could be arbitrarily skewed. Therefore, I would say the question is formally meaningless, and whatever intuition it helps build is outweighed by the confusion it creates.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Efficiently finding the min-cost path of an AVL tree
It seems that in a *full* AVL tree, the left edge is always the minimum-cost path. For example, take the following full AVL tree:

The min-cost path would be `8-6-5`. However this is not the case with other AVL trees. Take the previous tree with an additional `4` inserted:

Here the min-cost path would be `8-6-7` rather than `8-6-5-4`.

What is the most efficient algorithm to find the min-cost path in any AVL tree? Given the characteristics of AVL trees, is this algorithm faster than it would be for a standard BST?

# Answer
Searching in an AVL tree is anyways only at most O(log n) (see on @Wikipedia: https://en.wikipedia.org/wiki/AVL\_tree?wprov=sfta1). If you do not care about the higher cost of rebalancing AVL tree instead of BSTree, this tree will have even the advantage of always maintaining the AVL-min-cost path on the left edge. Search the left edge has also O(log n) so no cheaper than other trees. Balancing a tree is only nesessary if building a tree can cause massive imbalance, only than AVL has a marginal advantage above BST.

To your counter example on AVL tree with a not-left-edge min-cost: This is to my quick grasp the furthest imbalance one can find before need of rebalancing of AVL is needed. Hence no need to worry about finding the minimum cost path in AVL tree may be more difficult due to tree depth. So searching the minimum path within the left and not totally left path is O(log n +1) equaling O(log n). So it is basically not harder to find the actual minimum path than finding the obvious left edge.
> 1 votes

---
Tags: algorithms, trees, binary-trees, search-trees, avl-trees
---


# Question
Title: In a Binary Tree, can two nodes have the same value?
In a Binary Tree, can two nodes have the same value? For example:

```
     3
    / \
   4   4
  / \
 1   2

```

They are two different nodes, but they have the same value. Here is code:

```
function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

```

```
const r = new TreeNode(3);
r.left = new TreeNode(4);
r.right = new TreeNode(4);
r.left.left = new TreeNode(1);

```

# Answer
If you say "binary tree", my answer is " yes", since binary tree to me only says: A tree of nodes that only have at most 3 edges, of which two (binary) are pointing in the same direction (to tree leafs).

If you mean a "binary search tree", my answer is "no", since a search tree does not have any advantage in allowing duplicates, since SEARCHING for ONE value in a BST can only result in ONE value, not in two or more. Since BST search is a deterministic algorithm, one of the two mentioned duplicates will never be found and hence is totally useless. Inserting a duplicate in a BST must be skipped since its position in tree is already occupied.
> 3 votes

# Answer
In Binary search trees, the order of nodes are as: $leftnode\<parentnode\<rightnode$. So, your code will always run into error if both left and right of a parent node is same.

Please go through the following links, for more: http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap13.htm https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture8.pdf
> 1 votes

---
Tags: binary-trees
---


# Question
Title: Can the solution to a POMDP be found using linear programming?
It is known that *Markov decision processes* (MDPs) can be solved using linear programming (see page 24 of Carlos Guestrin's PhD dissertation). The linear program is:

$$min\_{V(x)} \sum\_x \alpha(x)V(x)\\ \text{subject to: } V(x) \ge R(x,a) + \gamma\sum\_{x'}P(x'|x,a)V(x')\text{ for all }x\in X, a\in A$$

where $V(x)$ is the value of starting at state $x$ (note that $V(x)$ is the decision variable), parameters $\alpha(x)\>0$ for all $x$ which are termed *state relevance weights* and are typically normalized, that is $\sum\_x\alpha(x)=1$ (the solution of the above LP is actually, surprisingly, independent of the exact choice of $\alpha$), $R(x,a)$ is the reward obtained in state $x$ when action $a$ is taken, and $P(x'|x,a)$ is the probability that transition to state $x'$ when we take action $a$ in state $x$.

**Question**: does anyone know of a similar linear programming formulation for solving *partially observable Markov decision processes* (POMDPs)?

# Answer
What is known about the complexity of finding optimal policies for POMDPs indicates that solution by Linear Programming is not possible in the general case. When the decision horizon is bounded (finite), finding optimal POMDP policies is PSPACE-hard (Papadimitriou and Tsitsiklis, 1987). When the decision horizon is infinite and we are using e.g. the geometrically discounted rewards, finding optimal POMDP policies is unsolvable (Madani, Hanks, Condon 1999). Linear Programming is solvable in polynomial time, and (efficient) reductions from the above PSPACE-hard and unsolvable problems to Linear Programming therefore are not believed to exist and do not exist, respectively. Solution of POMDPs in sufficiently simple special cases is possible with LP, of course (like MDPs, which are fully observable POMDPs).
> 3 votes

---
Tags: dynamic-programming, linear-programming, markov-chains
---


# Question
Title: Prove that the language $\{a^ib^i | i\geq 0\}$ is not regular? (Do we just consider $a^nb^n$, where $n$ is the pumping length?
I think to prove that $\\{a^ib^i | i\geq 0\\}$ is not regular, we just have to consider the string $a^nb^n$ (which is in the language) and apply the pumping lemma. But I'm not sure how to proceed using the pumping lemma (even though I know it applies with our choice of string, since the string is at least $n$ long).

# Answer
To apply the pumping lemma for regular languages:

1. You assume some pumping length $p \> 0$: Suppose a pumping length $p$.
2. You pick a string $s$ such that $|s| \geq n$: Indeed, $a^pb^p$ is a good one since $|a^pb^p| = 2p \geq p$.
3. Now, you have to consider **all** the partitions of $s$ as $xyz$, such that
    1. $|y|\>0$ and
    2. $|xy| \leq p$.

In this case, the 2nd inequality restricts $y$ to contain only $a$'s. Therefore, all the possible partitions are of the form $y = a^k$, $x = a^{p-k-r}$ and $z = a^rb^p$ for $k$ and $r$ such that $k \> 0$ and $p \geq k + r$.

4. For **every** possible partition of the previous step, you have to show that there is some $i\in\mathbb{N}$ such that $xy^iz$ is not in the language.

Here, consider $i = 0$. Then $xy^0z = xz = a^{p-k-r}a^rb^p = a^{p-k}b^p$. It is now a matter of showing that $p-k\neq p$, or, equivalently, that $k \> 0$ which is already true.
> 2 votes

# Answer
In this particular case, you can use the pumping lemma with *any* word of length at least $p$ (the pumping length). Indeed, consider any word $w = a^nb^n$, and suppose that we are given some decomposition $w = xyz$ where $y$ is non-empty and $xy^tz \in \\{ a^ib^i \mid i \geq 0 \\}$ for all $t$ (we don't even need the bound on $|xy|$). If $y$ consists only of $a$'s, then $xy^2z$ will have more $a$'s than $b$'s; if it consists only of $b$'s, then $xy^2z$ will have more $b$'s than $a$'s; and if it consists of both, then $xy^2z \notin a^\*b^\*$.

If instead of your language we consider the language of all words with equally many $a$'s and $b$'s (but not necessarily in the format $a^\*b^\*$) then the above argument would fail, and you would have tobe more careful when choosing your word; however, $a^pb^p$ would still work.
> 0 votes

---
Tags: formal-languages, regular-languages, regular-expressions, pumping-lemma
---


title: Minimize function on permutations

text:
# Question
Title: Minimize function on permutations
**Problem:**

Consider $\[k\] = \\{ 1, 2, \dots, k \\}$ and function (of two arguments) $f: \[k\]^{2} \rightarrow \mathbb{N}$ that is defined for all $(n, m) \in \[k\]^{2}$ (all ordered pairs of numbers from $\[k\]$). Also, we know that for all $n, m \in \[k\]$ $$f(n, m) = f(m, n) .$$

Also, consider the set $S\_{k}$ of all permutations on $\[k\]$ and function $g: S\_{k} \rightarrow \mathbb{N}$ defined as follows $$ \sigma = \sigma\_{1} \sigma\_{2} \dots \sigma\_{k} \quad \Rightarrow \quad g(\sigma) = \sum\_{i = 1}^{k - 1} f(\sigma\_{i}, \sigma\_{i + 1}) .$$

The problem is to find at least one permutation $\sigma \in S\_{k}$ such that $g(\sigma)$ is minimal.

**Question:**

How can we find the desired permutation faster than brute force?

# Answer
> 2 votes
Hamiltonian path is a special case of your problem. Given a graph $G$, let $f(n,m) = 1$ if the edge $(n,m)$ exists, and $f(n,m) = 2$ otherwise. The minimum value of $g(\sigma)$ equals 1 iff $G$ contains a Hamiltonian path.

---
Tags: algorithms, graphs, optimization, permutations
---


# Question
Title: Making groups out of a list of things based on some similarity
Let's say I have a list of n items - i1, i2, ..., in.

These items are similar to one another based on some similarity function, say similar\_func(item\_x,item\_y) where item\_x,item\_y belong to list i1, i2, ... in. This function returns a number that ranges from 0 to 1, where 0 means not similar at all and 1 means exactly similar.

Now I would like a create a number of groups, each of which may contain items from the above list. Each group having items that are similar to each other items of the group by let's say 0.5.

I could run a double loop on the list, comparing each item to one another and creating a group whenever I find two items with similarity more than 0.5. Of course I would need to check if the item already exists in a group already created and with all the other items in that group.

This brute force method is possible and will give the right answer.

But I would like to do this more efficiently. Is there a efficient method for solving this problem?

Edit: There can be any number of groups and an item can be in multiple groups.

If similarity(x,y) = 0.6 and similarity(x,z) = 0.6, but similarity(y,z) = 0.4, then there will be two groups -\> \[x,y\] and \[x,z\]

Also if x is similar to y AND x is similar to z, then it doesnt mean that y is similar to z. The similarity between two items solely depends on the the return value of similarity function when those items are passed as arguments to it.

# Answer
> 2 votes
Suppose you represent your items as vertices in a graph and two vertices are connected by an edge if they have a similarity greater than $0.5$. Then, a possible group corresponds to a clique in this graph (i.e all vertices in the group are connected). You probably only care about the "largest" groups (for example, if $\\{x,y,z\\}$ is a group then you don't care about the group $\\{x,y\\}$), which correspond to maximal cliques in the graph.

Thus, your problem amounts to listing all maximal cliques in this graph. Unfortunately, there can be exponentially many such maximal cliques so you won't be able to do this in polynomial time. The Wikipedia article I link to mentions a few sources and ways to do this either in asymptotically optimal time for the worst case or in time polynomial *per maximal clique*, which might be of interest if the graph happens to have relatively few maximal cliques.

---
Tags: algorithms
---


# Question
Title: Find bipartial subgraph such that mean square deviation of edge lengths is minimum
Let there be graph $G = (V, \\, E)$. $G$ has neither loops nor parallel arcs.

$V = A \cup B, \\, A \neq \emptyset, \\, B \neq \emptyset, A \cap B = \emptyset$

For simplicity's sake, let's consider $G$ is directed.

$\forall \ e \in E \ \\, e.tail \in A, \\, e.head \in B, \\, e.length \in (\mathbb{Z} \cap \[1, 100\]) \cup -\infty \\ \forall \ a \in A, \\, b \in B \ \ \exists! \ e \in E: e = (a, b)$

**The goal is** to develop an algorithm that finds a bipartite subgraph $G' = (V', \\, E')$ such that:

1) $|\\,E'\\;|$ **is maximum**;
2) Under restriction 1), $\sum \limits\_{e' \in E'} (e'.length - (\sum \limits\_{e' \in E'} e'.length \\; / \\; |\\, E' \\; |))^2 $ **is minimum possible**, where $| \\, E' \\; |$ is cardinality of $E'$.

For example, let graph $G$ be defined as following:

In this case, the correct solution is:

The algorithm should run in polynomial time.

# Answer
The way to make $|E'|$ be maximum is to take all the edges, i.e., set $E'=E$. Since your graph is already bipartite, this subgraph will be as well. Then criterion 2 is irrelevant, as there is only one way to achieve the maximum for criterion 1.
> 0 votes

---
Tags: algorithms, graphs, bipartite-graph
---


# Question
Title: Find bipartial subgraph such that sum of edge lengths is maximum
Let there be graph $G = (V, E)$. $G$ has neither loops nor parallel arcs.

$V = A \cup B, \\, A \neq \emptyset, \\, B \neq \emptyset, A \cap B = \emptyset$

For simplicity's sake, let's consider $G$ is directed.

$\forall \ e \in E \ \\, e.tail \in A, \\, e.head \in B, \\, e.length \in (\mathbb{Z} \cap \[1, 100\]) \cup -\infty \\ \forall \ a \in A, \\, b \in B \ \ \exists! \ e \in E: e = (a, b)$

**The goal is** to develop an algorithm that finds a bipartite subgraph such that $\sum \limits\_{e \in E} e.length$ **is maximum possible**.

For example, let graph $G$ be defined as following:

In this case, the correct solution is:

Is there an other approach besides greedy algorithm (take $a$, pick the best $b$ \[such that $b = b\_0, b\_0: (a, b\_0).length = \max\_{b \in B} \ (a, b).length$\] for this $a$, remove $b$ from $B$, take the next $a$)? The algorithm should run in polynomial time.

# Answer
The way to make $\sum\_{e \in E} e.\text{length}$ be maximum is to take all the edges with positive length, i.e., set $E'=\\{e \in E \mid e.\text{length} \> 0\\}$. Since your graph is already bipartite, this subgraph will be as well.
> 0 votes

---
Tags: algorithms, graphs, greedy-algorithms, bipartite-graph
---


# Question
Title: Find bipartial subgraph such that number of edges is maximum and sum of edge lengths is maximum
Let there be graph $G = (V, E)$. $G$ has neither loops nor parallel arcs.

$V = A \cup B, \\, A \neq \emptyset, \\, B \neq \emptyset, A \cap B = \emptyset$

For simplicity's sake, let's consider $G$ is directed.

$\forall \ e \in E \ \\, e.tail \in A, \\, e.head \in B, \\, e.length \in (\mathbb{Z} \cap \[1, 100\]) \cup -\infty \\ \forall \ a \in A, \\, b \in B \ \ \exists! \ e \in E: e = (a, b)$

**The goal is** to develop an algorithm that finds a bipartite subgraph $G' = (V', \\, E')$ such that:

1) $|\\,E'\\;|$ **is maximum**;
2) Under restriction 1), $\sum \limits\_{e' \in E'} e'.length$ **is maximum possible**.

For example, let graph $G$ be defined as following:

There are two subgraphs that satisfy 1):

and

However, sum of the edge lengths of the second subgraph is greater than sum of the edge lengths of the first subgraph so the second subgraph is the correct answer.

The algorithm should run in polynomial time.

# Answer
> 0 votes
The way to make $|E'|$ be maximum is to take all the edges, i.e., set $E'=E$. Since your graph is already bipartite, this subgraph will be as well. Then criterion 2 is irrelevant, as there is only one way to achieve the maximum for criterion 1.

---
Tags: algorithms, graphs, bipartite-graph
---


# Question
Title: Find max flow in a network with all capcities of $\sqrt 2$ and one with 2
Given a graph $G(V, E)$ with capacities on the edges such that all edges have a capacity of $\sqrt2$ apart from one edge with a capacity of 2. need to find max flow efficiently.

I can run Dinic on this graph or FordFulkerson but I know it can be more time-efficient.

What I have tried -

transform all edges capacity to be 1, then find max flow using Dinic algorithm on 0-1 network that is more efficient than a general network. then If the edge that had a capacity of 2 isn't saturated it won't be saturated on the original graph so we can just find the min-cut and multiply the number of edges that cross the min-cut by $\sqrt 2$ and that's the max flow. but if it's saturated I'm stuck.

# Answer
> 1 votes
First, you can divide all capacities by $\sqrt{2}$ so that all capacities are now $1$ except for a single edge $e'$ which has capacity $\sqrt{2}$.

Call this instance $G$. Create $G\_1$ which is a copy of $G$ where the capacity of $e'$ has been replaced with $1$, and find the max flow of this graph, with a value $F\_1$.

Now, consider $G\_2$ which is also a copy of $G$ where the capacity of $e'$ has been replaced with $2$ and has a max flow of $F\_2$.

If $F\_2 \> F\_1$, this means that starting from the flow assignment of maximum flow in $G\_1$ there is an augmenting path in $G\_2$ along which you can push $1$ additional unit of flow. This augmenting path necessarily corresponds to an augmenting path in $G$ where you can push $\sqrt{2}-1$ additional units of flow. Thus, the max flow for $G$ is $F=F\_1 + \sqrt{2}-1$.

If $F\_2 = F\_1$, this means that starting from the flow assignment of maximum flow in $G\_1$ there is no augmenting path in $G\_2$ along which you can push any amount of flow. This also means that this holds for $F$, as the capacity increase of $e'$ between $F\_1$ and $F$ is lower than between $F\_1$ and $F\_2$. Thus, the max flow for $G$ is $F=F\_1$.

(You just need a single search of augmenting path to determine if $F\_2 \> F\_1$ or $F\_2 = F\_1$ once you have computed the flow for $F\_1$)

Then, to get the answer to your original problem, just scale the flow back by multiplying $F$ by $\sqrt{2}$.

# Answer
> 1 votes
Hint:

> In the optimal solution, either the edge of weight 2 is saturated or it isn't. Handle those two cases separately.

Hint #2:

> If I told you the edge of weight 2 it is saturated in the optimal solution, could you find that solution? What if I told you it isn't saturated?

---
Tags: network-flow, ford-fulkerson
---


# Question
Title: How to check equality between any two 2-dimensional arrays (dense matrices) with time complexity less than O(n*m)?
Here, n = no. of rows and m = no. of columns

Suppose, there are three matrices - **A\[3\]\[2\]** : {{1,2},{3,4},{5,6}} ; **B\[3\]\[2\]** : {{1,2},{3,4},{5,6}} ; **C\[3\]\[2\]** : {{2,1},{3,4},{5,6}} . Here A=B , A!=C and B!=C .

**So, task is to check equality between all possible combinations of 2-dimensional matrices from a given set of matrices with time complexity less than O(n^m) .Here the possible combinations are (A,B) , (A,C) and (B,C).**

( **As part of the solution :**

Matrix to matrix comparison is costly .So these matrices have to be converted into 'something' which results less comparison time . I think if I can convert/represent the matrix as a value/string/1-dimensional array , then equality comparison will be less costlier . My question is how to convert/represent ? If it can be solved by hashing how to solve this exactly ? )

***NOTE :*** No. of 2-dimensional matrices and their sizes are not fixed. In my problem scenario no. of 2-dimensional matrices are been generated gradually which can be of any size. Cant predict how many matrices of which size will be generated . ***Here my main task is to identify all possible equal matrices among the set of all generated matrices . Main idea is - whenever a new 2D matrix generates, check if it has been already generated or not. If yes , we can say 'identical matrices found'; If no , continue checking for other matrices .***

# Answer
> Here my main task is to identify all possible equal matrices among the set of all generated matrices . Main idea is - whenever a new 2D matrix generates, check if it has been already generated or not. If yes , we can say 'identical matrices found'; If no , continue checking for other matrices .

It seems it would be easiest to store the previously seen matrices in a Trie. You can then test whether the given input matrix is equal to any of the previous matrices in $O(nm)$, regardless of how many previous matrices there are. This is the best you can do, since you must examine each element of the matrix at least once. You can't get an *individual* comparison to run faster than $O(mn)$, but you can test for equality among the entire set faster.
> 2 votes

# Answer
Can't be done. If you compare $A$ and $B$ (both $m \times n$), if you compare less than $m \cdot n$ elements, the matrices can differ in the elements not compared. If you want to compare $A$ to a set of $r$ $B$ matrices, you'll have to compare against all of them, i.r. $m \cdot n \cdot r$ comparisons. Maybe some smart preprocessing of the $B$ matrices can cut down the factor $r$ for the comparison of $A$ to the set of $B$s, but doing that won't be cheap. If you suspect most of the time they aren't equal, a fingerprint (i.e., a hash like SHA265) of the elements of the $B$ will tell you cheaply which ones can't be equal to $A$, but you'll have to check for equality.
> 0 votes

---
Tags: algorithms, complexity-theory, data-structures
---


# Question
Title: What are the underlying mechanisms allowing us to unsend an email?
I am currently studying Computer Networking, and I was reading about the different types of Application Layer Protocols. In the book I am reading (Computer Networking: A Top-down Approach) it is mentioned that: "*Once the client sends a message into its socket interface, the message is out of the client’s hands and is “in the hands” of TCP.*"

For the sake of example, I thought of the option we have of cancelling the emission of an email? Is this functionality simply implemented via a time-window of seconds before emission or is their an actual procedure I do not know of ?

Do please correct my assumptions as I am afraid I might be off topic on several points

Thank you in advance.

# Answer
> 5 votes
The e-mail system has no way of manipulating already sent e-mails, no.

The only services I've seen which allow you to "unsend" an e-mail simply delay the e-mail being sent for a user-determined amount of time and then allow you to cancel the send before it happens.

Alternatively, I've seen some services allow you to "unsend" e-mails if the recipient is using the same e-mail client as the sender, as both sides are controlled by the same service. Although, once again, this is handled by the service provider, not by the e-mail system itself.

# Answer
> 1 votes
Either you catch the mail before it goes out (locally, or wherever your mail relay is), or you convince the recipient's mail spool to delete the already arrived message. If the recipient got the mail before the "delete" message arrives, though luck.

Personally, I've never seen anything offering this functionality. *If* the mail is handled purely locally (or origin/destination use the sane software offering this), it could be done. No standard way, that's for sure.

---
Tags: computer-networks, communication-protocols
---