# Question
Title: How do I find a regular expression for a particular language?
I have a language, and I want to find a regular expression for the language. How do I do that? Is there a step-by-step, systematic procedure for that? Pretend I am just learning this topic; what approach can I use?

If it helps, you can assume the language is given in English (e.g., something like "$L$ is the set of words that contain at least one $a$, an even number of $b$'s, and does not contain the substring $ab$") or algebraically (e.g., $L=\\{a^i b^j (abb)^k : i+2j+k=3\ell, i,j,k,\ell \in \mathbb{N}\\}$).

This is intended as a reference we can point others to. Please explain your method in a form that someone new can understand it.

# Answer
Occasionally you can just stare at the language, get insight, and write down a regular expression just like that. However, more typically, we need a systematic procedure. Fortunately, the field of formal languages provides a more systematic approach that will help you structure your approach to this problem. Often, one effective approach is as follows:

*Step 1.* Find a non-deterministic finite-state automaton (NFA) for the language.

*Step 2.* Convert the NFA to a regular expression.

*Step 3.* Double-check whether your regular expression is correct.

In more detail, here is how you do each of those two steps:

*Step 1.* To find a NFA for your language, you can think of this as a programming problem, where you have to write a program that works in a very limited programming language where you are only allowed to have a fixed, finite amount of state. Try to write a program that reads in a string one letter at a time and decides whether the input string belongs to the language or not, *using only a fixed amount of memory* (say, $c$ memory cells, where $c$ is some constant that does not depend on the input string, not even on the length of the input string). This program then corresponds naturally to a NFA, where the NFA has one state per possible value of the program's memory.

Sometimes, it can also be helpful to use the closure properties of NFA. For instance, if the language $L$ is specifies as $L = L\_1 \cup L\_2$, then it suffices to build a NFA for $L\_1$ and a NFA for $L\_2$; then the closure properties for regular languages allow you to derive a NFA for $L$. For more techniques to build a NFA, take a look at our reference question How to prove a language is regular? for more approaches.

*Step 2.* To convert the NFA to a regular expression, apply the algorithm described in How to convert finite automata to regular expressions?.

*Step 3.* To check whether your regular expression seems to be correct, you can try testing it on a few example strings to see if it seems to give the correct answer. Try both several examples that *are* in the language and several that are not.

---

This is just one approach. There are other approaches, including writing down a regular grammar and converting it to a regular expression, or writing a system of linear expressions in regular languages and converting to a regular expression using Arden's Lemma, or others. For an overview of those methods, take a look at How to prove a language is regular?, How to convert finite automata to regular expressions?, and Known algorithms to go from a DFA to a regular expression.

You can also look at other examples of this kind of problem on this site, e.g., by looking at questions tagged .
> 4 votes

# Answer
What @D.W. has not mentioned is how exactly to construct an automaton based on a language. This can be achieved in polynomial time using Angluin's Theorem.
> -1 votes

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


# Question
Title: Why is a set of attributes X not a key if X → Y holds but there exists a strict subset V of X where V → Y?
Apologies if I butchered the question, I wasn't quite sure how to word it.

In the Ramakrishnan text (2nd edition) on page 423 (in the section on functional dependencies) this statement is made:

> If $X \rightarrow Y$ holds, where \[$X$ is the set of key attributes and\] $Y$ is the set of all attributes, and there is some subset $V$ of $X$ such that $V \rightarrow Y$ holds, then $X$ is a superkey; if $V$ is a strict subset of $X$, then $X$ is not a key.

I got the basic idea here (that if $X$ contains some $V$ where $V \rightarrow Y$ then $X$ is a key that contains a smaller key), but I must be misunderstanding something on the second case. Why isn't $X$ a key in the second case? It would seem that a strict subset would be a stronger case for being a "key within a key" which is how I understand a superkey to be structured.

# Answer
Generally, you want to define a key as a superkey that is minimal with respect to inclusion; if $X$ is a superkey, $V$ is a superkey and $V \subset X$, then $X$ can't be minimal.

The intuitive idea behind the definition is that we don't want keys to contain "useless" attributes. For instance, imagine a table that contains a list of people, each of which has a unique number $K$, a name $N$ and a surname $S$. $K$ would be a key to that table, because it functionally determines all other attributes in the relation. The pair of attributes $\\{K, S\\}$ also functionally determines the entire relation, but attribute $S$ is "useless" in that respect, because it is itself determined by $K$.
> 1 votes

---
Tags: database-theory
---


title: Balanced Binary Tree

text:
# Question
Title: Balanced Binary Tree
Can someone please explain to me how the Wikipedia example on the left for a balanced binary tree is correct?

> One common balanced tree structure is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1

For node `ABCDE`, isn't the height of left subtree 2 and the height of the right subtree 0, making the difference of height 2?

**EDIT** As David rightly pointed out:

> That page defined "balanced" immediately above the example you're asking about, and it defines balanced in a different way to you.

I thought that the example was using the definition that comes immediately **after** the example, which I have quoted above. Apologies for the confusion.

# Answer
> 3 votes
That Wikipedia article is using a different definition of "balanced":

> A balanced binary tree has the minimum possible height.

Therefore, since a perfect binary tree of height $d$ has $2^{d}-1$ nodes, if a tree has $n$ nodes, the minimum possible height for that tree is $\left \lceil \log\_2n \right \rceil$, and the tree you mention does indeed satisfy that condition.

Observe that the usual definition of "balanced tree" is in an asymptotic setting, i.e. depth is $\mathcal{O}(\log n)$.

---
Tags: binary-trees
---


# Question
Title: composite number Pumping Lemma for L = {$0^p$∣$p$ is a composite number}
Consider the language $L = \\{0^p \mid p \text{ is a composite number}\\}$.

I know that this is not a regular language. I have thought that to prove this language is not regular take the complement (prime numbers) which must be regular, but its complement has prime numbers and 0 and 1 occurrences of 0's.

Could anybody give me a hint to prove without taking complement?

# Answer
The Pumping Lemma will give you a way to generate strings in the language whose lengths are in an arithmetic progression. If you pick the initial string right, you should be able to apply Dirichlet's (?) Theorem that arithmetic progressions having certain properties necessarily include infinitely many primes.
> 1 votes

# Answer
It can also be proved by taking the complement. This doesn't answer your question as per the last sentence, but shows how you could extend your arguments in the second paragraph.

Let $$L\_1=\\{0^p| p\text{ is a prime}\\}$$ Then, we have the complement of $L$ to be, $$\bar{L}=L\_1\cup\\{\epsilon,0\\}$$ where $\epsilon$ denotes the empty string.

$L\cup\bar{L}=\Sigma^\*$, where $\Sigma=\\{0\\}$, the alphabet of the language. Also, $L$,$L\_1$, and $\\{\epsilon,0\\}$ are all pairwise disjoint.

Thus,

$$\begin{align}L\_1&=\Sigma^\* -(L\cup\\{\epsilon,0\\})\\ &=\Sigma^\*\cap \overline{L\cup\\{\epsilon,0\\}} \end{align}\tag1$$

Suppose $L$ was regular. We know that $\\{\epsilon,0\\}$ is regular as the number of strings in the language is finite. By the closure under union, we must have $L\cup\\{\epsilon,0\\}$ to be regular. Again, by closure under complement, we must have $\overline{L\cup\\{\epsilon,0\\}}$ to be regular. As $\Sigma^\*$, the set of all strings is regular, by closure under intersection, $\Sigma^\*\cap \overline{L\cup\\{\epsilon,0\\}}$ must be regular. From $(1)$, this means that $L\_1$ must be regular.

Using the pumping lemma, as suggested by you, it can be shown that $L\_1$ is not regular, leading to a contradiction. Thus, the assumption that $L$ is regular is incorrect, $L$ is not a regular language.
> 1 votes

---
Tags: automata, regular-languages, pumping-lemma
---


# Question
Title: What does distinct mean in terms of an array?
I've tried searching this up, but from my what I think it is. It means there are no duplicate elements (ie. all elements are unique elements)?

# Answer
> 0 votes
This is just the ordinary English-language use of the word "distinct". The objects in some collection are described as "distinct" if each is different from the others. So an array with distinct elements is one where no two elements are the same.

> **distinct**, adjective
>
> 1. Recognizably different in nature from something else of a similar type:
>
> * ‘the patterns of spoken language are distinct from those of writing’
>     * ‘there are two distinct types of sickle cell disease’
>
> OxfordDictionaries.com

# Answer
> 0 votes
Yes you are right.. An array is distinct if it contains unique elements i.e. no duplicates

---
Tags: terminology, arrays
---


# Question
Title: Why is string concatenation not distributive over intersection?
Background: This is to be seen in the context of formal languages, very beginner-level.

My professor claims that concatenation is not distributive over intersection, meaning that $L \circ (L\_1 \cap L\_2) \neq (L \circ L\_1) \cap (L \circ L\_2)$ and $(L\_1 \cap L\_2) \circ L \neq (L\_1 \circ L) \cap (L\_2 \circ L)$.

While it seems silly of me to doubt what he says, I personally have trouble explaining this to myself and am looking for a counter example.

If I concatenate only with the intersection of $L\_1, L\_2$ it ought to be the same as concatenating first and then finding the duplicates, so to speak.

# Answer
> 5 votes
When we say that concatenation doesn't distribute over intersection, we don't mean that $L(L\_1\cap L\_2) \neq LL\_1 \cap LL\_2$ for all languages $L,L\_1,L\_2$, but rather that this inequality holds for *some* $L,L\_1,L\_2$. Here is one example: $$ L = \\{a,aa\\}, L\_1 = \\{a\\}, L\_2 = \\{aa\\}. $$ In this case $L(L\_1 \cap L\_2) = \emptyset$ but $LL\_1 \cap LL\_2 = \\{aaa\\}$.

---
Tags: formal-languages
---


title: Why graph planarity is important

text:
# Question
Title: Why graph planarity is important
What is the reason to study planar graphs and algorithms on such graphs (as well as algorithms allowing to check a graph's planarity)? Where in industry this knowlege is needed? I know that planarity arises in microchip design ("wires" intersection). I also found the following excerpt from a lecture notes:

> The study of two-dimensional images often results in problems related to planar graphs, as does the solution of many problems on the two-dimensional surface of our earth. Many natural three-dimensional graphs arise in scientific and engineering problems. These often come from well-shaped meshes, which share many properties with planar graphs.

Where I can read about it in more detail? Or may be you can explain in a few words what exactly these applications are?

# Answer
For some graph classes $C$, the question "is there a fast algorithm for deciding whether a graph $G$ belongs to class $C$?" is perhaps only of theoretical curiosity. But it can also be argued otherwise: suppose a problem you care about is hard in general, but efficiently solvable for graphs of class $C$. Wouldn't it be nice if you could quickly test if you can use a fast algorithm, instead of always using a slow brute-force, for example?

In general, it is not hard to imagine some graphs arising from applications are naturally planar, like road networks, printed electric circuits, railways, or chemical molecules. For more concreteness, it seems like a good set of keywords is "planar graph applications". One of my first hits was \[1\] from the domain of computer vision.

---

\[1\] Schmidt, Frank R., Eno Toppe, and Daniel Cremers. "Efficient planar graph cuts with applications in computer vision." Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. IEEE, 2009.
> 9 votes

---
Tags: graphs, planar-graphs
---


title: Why are some games np-complete?

text:
# Question
Title: Why are some games np-complete?
I read the Wikipedia entry about "List of NP-complete problems" and found that games like super mario, pokemon, tetris or candy crush saga are np-complete. How can I imagine np-completeness of a game? Answers don't need to be too precise. I just want to get an overview what it means that games can be np-complete.

# Answer
> 73 votes
It just means that you can create levels or puzzles within these games that encode NP-Hard problems. You can take a graph coloring problem, create an associated Super Mario Bros. level, and that level is beatable if and only if the graph is 3-colorable.

If you want to see the *specific* way the NP-Complete problems are translated into the games, I recommend the paper "Classic Nintendo Games are (Computationally) Hard". It's well written and easy to follow.

An important caveat to keep in mind is that the NP-hardness requires generalizing the games in "obvious" ways. For example, Tetris normally has a fixed size board but the hardness proof requires the game to allow arbitrarily large boards. Another example is off-screen enemies in Super Mario Bros: the proof is for a variant of the game where off-screen enemies continue moving as if they were onscreen, instead of ceasing to exist and being reset to their starting position when Mario comes back.

# Answer
> 21 votes
I honestly don't know exactly what kind of model is used by the people making those claims; however, what seems reasonable to me would be talking about the $\mathcal{NP}$-completeness of deciding something about a game situation.

Let's take as an example Tetris, since it's the only one from those you quote that I understand enough to talk about. Tetris has a rule called "perfect clear", that gives the player a large bonus if a piece drop clears the board entirely. One might wonder if, given an ordered sequence of pieces $\\{P\_i\\}$ and an integer $k$, there exists a legal sequence of moves for the pieces $P$ that achieves at least $k$ perfect clears. Problem statements such as those are sufficiently abstract that can be modeled with the tools of complexity theory.

Long story short, "$\mathcal{NP}$-complete" means one thing and one thing only, fancy claims such as "Super Mario is $\mathcal{NP}$-complete" have to be translated into a formal statement before they make any actual sense.

# Answer
> 3 votes
For single player games, you can always ask the question "is there a winning strategy for the player", and that question often has a "YES" answer that can be verified in polynomial time, and may very well be NP complete.

For two-player games, the answer can very often not be verified in polynomial time, because to verify that a move for A is a winning move, you must demonstrate that for every response of B there would be again a winning move for A and so on.

# Answer
> 2 votes
Here's a simplistic hand-waving explanation:

Such games are *in NP* because "running" a player's behavior over the course of a game and checking whether s/he wins or loses can be done efficiently (we need it to be in polynomial time in the length of the game, but it's probably linear or $O(n \log(n))$-ish).

Such games are *NP-hard* because the player's behavior is very expressive. While at any given point a player may only have a limited, even a fixed, number of possible actions, that's enough to create a space of behaviors or strategies exponential in the length of the game; and while you may be able to provide a simple condition or logical formula on the validity/benefit/correctness of a player's actions locally, globally you get a similar effect as with a large combinatorial circuit, or a k-CNF formula.

Hopefully this makes some intuitive sense and also rings enough CS theory bells.

PS - Some games are much more (computationally) complex than that. For example, the boardgames Hex, Go and and Reversi are PSPACE-complete. That's essentially because the formula you need to satisfy for a winning strategy is a repeatedly-alternating-quantifier formula: The exists a move by player 1, such that for every move by player 2, there exists a move by player 1 etc. etc. such that with all those moves having been played, either some of player 2's moves are invalid or we have a valid sequence player 1 has won. With NP games, it's typically just one player's behavior/strategy/choice of moves.

# Answer
> 0 votes
Well, it's certainly in NP, because a possible solution is just a finite number of inputs (in each input frame you can select any of the k buttons, we represent each selection of the buttons for each frame with a letter) that brings you to the win-screen. We know that this game has been beaten before, so we know, that there exists a solution. An NTM goes over it's tape and guesses magically a correct certificate of length n. Then it simulates Super Mario with the input and verifies it. The verification can be done in polynomial time (linear time actually, if the solution is correct, it will take exactly n frames to win).

To show NP-completeness, we could reduce 3-SAT to it by building a 3-Sat checker with the level generator (which is built through arbitrary code execution https://www.youtube.com/watch?v=IOsvuEA2h4w).

So we have a 3-SAT CNF input, that we check for correct formatting first. If it's badly formatted, we just translate it into one 'jump'-input (it's not possible to to beat Super Mario within one frame by doing a jump).

We call the length of the 3-CNF input n.

If it's correctly formatted, we translate it into a number of inputs, that builds the 3-CNF checker for us (always the same code of length k), translates the 3-CNF into a String of inputs, that builds the specific 3-CNF in the checker (in O(n)),and checks all possible solutions by brute-force. It idles and does nothing, if after going thru all solutions, none is found. It restarts the game and uses a known solution for Super Mario to beat the game (the code to do that is has the length j). Our transformation is thus in O(n), so it is within polynomial time.

If the CNF is badly formatted, we don't win (by definition our input is not winning, if we haven't won one frame after the execution of it). If the CNF is not satisfiable, we don't win (you can't win by idling for one frame in the level generator, we ensured that in our code). If the CNF is satisfiable, the checker finds a solution restarts and wins the game. Thus the polynomial reduction of 3-Sat to Super Mario is complete and we have proven, that Super Mario is NP-complete.

(Hope I haven't messed this up somewhere. We do run into a storage problem, if the 3-CNF is too long, but limited storage is usually ignored in these contexts, I believe)

# Answer
> 0 votes
*I rewrote this answer to try to address some comments on a previous version.*

I assume that you've read the Wikipedia definition for NP-completeness which really doesn't focus on games. I'll water down the exact meaning of NP-completeness and game theory just a bit and explain the essence of a NP-Complete game.

Let's consider a 2-player game with alternate moves, more restrictively this is essentially about Combinatorial games. Basically a game which the you have some number of moves that can be made and you must chose one of them. You would like to play "perfectly" which means that you'd never make a "bad" move. So of the allowable moves you'd like to select the best one. (Of course your opponent has the same goal...)

> Note that perfect play doesn't mean that you'll always win. The rules of the game can be such that the first or the second player should win. Also some games like Tic-Tac-Toe should end in a draw. Thus what "perfect play" means in this discussion is:
> (1) That you'll never be in a winning position and then lose the game because you made a "bad" move
> (2) You'll never miss an opportunity to get into the winning position if such an opportunity arises.

Given the current state of the game what you'd like is to be able to use an "efficient algorithm" to calculate the best move. On the other hand let's note that an algorithm that has to search through the whole game tree is an "inefficient algorithm."

Now lets define "efficiency" a bit more formally. I'm going to simplify this a bit but the essence is correct. Consider the number of calculations, $C$, that must be done to chose the next move, that one the average each move has $B$ possibilities (the branching factor) and that there are $n$ moves left in the game. The notion is also that each calculation takes the same time so that the effort can be translated into time complexity, $T$, instead of raw calculations.

* An "efficient algorithm" will have:
$T \varpropto aB^a + bB^{\alpha-1} + cB^{\alpha-2} + ... + hB^0$
where $\alpha$ is a "small integer," and a-h are some real numbers. Thus the efficient algorithm executes in *polynomial time* since this is a polynomial expression.
* An "inefficient algorithm" will have:
$T \varpropto aB^n$
and this algorithm executes in *exponential time* (i.e. nonpolynominal time). The point here is that as $n$ gets larger a combinatorial explosion results.

Now the important point is that it is *impossible* to have an efficient algorithm, polynomial time, which plays perfectly for a game which NP-complete. To play perfectly a NP-complete problem must, by definition, be solved by an inefficient algorithm that runs in nonpolynomial time.

> Note that the running time is about the intrinsic number of calculations, not the response time perceived by a human. For a small game like Tic-Tac-Toe the computer could play all possible future moves and still respond quickly as perceived by a human.

For Nim it is possible to create an polynomial time algorithm. At any point in the game the algorithm can calculate which player has a winning move and what that move should be.

On the other hand let's take the game of Qubic. (You're trying to make a line of 4 in a 3D grid. So it is essentially tic-tac-toe on a 4x4x4 grid.) Qubic is NP-complete thus there is no polynomial time algorithm to calculate the next perfect move. The only way to know if you currently have a winning move is to try all the possible moves of both players to verify that a particular move is a winner, or at least not a loser.

> Truthfully the whole game tree for Qubic is small enough so that it can be encoded into a computer program which can play perfectly. What encoding means is that the whole game tree has been explored and all the moves worked out in advance. So the program can essentially do a quick database call using the current board state and get back the best move for that board state without having to do the tree search each time a move is to be made. This is really a "cheat" for our purposes here.

Now let's discuss chess to discuss the *evaluation function* ignoring some of the other features of chess playing programs. Chess is still an unsolved game. It is unknown if the first or second player should win. It is not possible to be given any board position and predict with certainty who will win. In fact chess has such a large game tree that it is just impossible to search the whole game tree. You'd need computers which are not just 10 or 100 times faster but billions of billions of time faster than any current computer. (There is the hope that quantum computing could cut through this Gordian knot.)

Think of the chess evaluation function as giving each possible next move a probability of being the best move. What a chess program does is to combine look aheads with the evaluation function. Thus the program looks at all possible future moves until it gets to a point where a "good" score can be given to the board position. The computer evaluates all possible paths through the tree this way and then chooses the path with the best score. Since the search never got to the end of the game for all the paths being evaluated, all chess programs ultimately use an imperfect evaluation function. (If you're near the end of the game then the computer might be able to look at all possible future moves.) That means that might be possible to beat the program even if the program had a winning position at some point.

---
Tags: complexity-theory, np-complete, computer-games
---


# Question
Title: Do two strongly connected nodes constitute a cycle in directed graph?
I'm seeing seemingly contradictory information about this around. On the one hand, it seems that for undirected graphs, you need at least 3 nodes to make a cycle. On the other other, I've also seen people differentiate between trivial and non-trivial cycles.

Let's say in your directed graph you have two nodes A and B with an edge from A to B and an edge from B to A. Do you have a cycle (A, B)? And does it always count as a cycle, or would some people consider it a cycle and others not?

Also, let's say you traverse that directed graph and hit A before you hit B. Is the edge (B, A) a back edge?

# Answer
Like most things, you should only care about definition if it makes sense and useful in your context.

And in the context of strongly connected component, a nice property we would like to say is that:

> Node $a$ and $b$ belongs to the same cycle if and only if $a$ and $b$ are strongly connected.

This nice statement only holds if you count $f\rightarrow g\rightarrow f$ as a cycle. So, we would like to count this as a cycle when talking about strongly connected components.
> 3 votes

---
Tags: graphs, graph-traversal
---


# Question
Title: Solving for the minimum cost, colored, set cover
## Formulation

This problem has four entities:

* A universe: $U = \\{1, 2, ..., n\\} $ of $n$ elements, indexed with $u$
* A set of available colors: $C \in \\{1, 2, ..., m\\} $ with $m$ colors, indexed with $c$
* A collection of sets: $S = \\{s\_1, s\_2, ..., s\_k\\}$ where there are $k$ sets, indexed with $i$. These sets contain elements of the Universe. $\bigcup S = U$.
* A cost function: $cost(u, c)$ where $u$ is the element, $1 \le u \le n$, and $c$ is the color of that element $1 \le c \le m$

We must assign a single color to each element such that the overall cost of the color assignment is minimized AND such that a valid set cover exists such that all elements in each set of the set cover have the same color. That is:

$$min \sum\limits\_u cost(u, c) x\_{u,c}$$

subject to

* $0 \le x \le 1$. That is, $x\_{u,c}$ is a binary decision variable which indicates that a particular element ($u$) is a particular color ($c$).
* $\sum \limits\_c x\_{u,c} = 1 \quad \forall u \in U$. That is, an element may only have one color.
* $\sum \limits\_{s:u\in S} y\_s \ge 1 \quad \forall u \in U$. That is, every element must be in the set cover.
* $0 \le y \le 1$. That is, $y\_{s}$ is a binary decision variable which indicates that a particular set ($s$) is included in the set cover.
* $ x\_{s\_{i\_1},c} = x\_{s\_{i\_2}, c} = ... = x\_{s\_{i\_l},c} \quad \forall s\_i \in S \bigm| y\_s = 1$. That is, given that a set is included in the set cover, everything in that set must be the same color.

## Example

$U = \\{1, 2, 3, 4, 5, 6, 7, 8\\}$

$C = \\{r, g\\}$

$S = \\{\\{1, 2\\}, \\{1, 2, 3\\}, \\{2, 3, 4\\}, \\{3, 4, 5\\}, \\{4, 5, 6\\}, \\{5, 6, 7\\}, \\{6, 7, 8\\}, \\{7, 8\\}\\}$

$cost\_{r} = \\{0, 0, 2, 1, 2, 1, 1, 0\\}$

$cost\_{g} = \\{1, 0, 1, 2, 0, 0, 0, 3\\}$

Optimal solution: $= \\{r, r, g, g, g, g, r, r\\}, \quad cost=4$

That is, the set cover is $\\{\\{1, 2\\}, \\{3, 4, 5\\}, \\{4, 5, 6\\}, \\{7, 8\\}\\}$.

**Typically**, $U$ consists of 100-2000 elements, $C$ consists of 3 - 10 colors, $S$ consists of 200-4000 sets of 5-25 elements.

## Context

Perhaps one way to think about this, is that you have a paint brush of a certain size that is larger than an element - that is it can only paint a collection of elements in one stroke. The allowed places to 'stroke' are overlapping - they are the sets in S. When you paint a particular set a particular color there is a cost associated with it that you would like to minimize. When you paint an area, you can paint the overlapping areas the same color only paying for the 'difference' in cost (kinda).

## Questions

* Is the formulation above well formed, and understandable? Is there a better formulation more related to an already existing problem?
* Can this be expressed as an integer linear programming problem?
* How would you solve this problem?

I have constructed an algorithm to solve this problem that first tries to use branch and bound to construct the optimal solution - it does quite well, but as the problem gets larger it slows down. If it starts to take too long I stop the branch and bound and use a random search to improve a solution. I think that having a better mathematical understanding of the problem will help me solve it better - I would also like to prove that this is NP-Hard.

One idea I have toyed with is to construct a new collection of sets $S'$ which consists not only of all the original sets but all of their combinations / unions (I understand this will be a lot, $2^k - 1$ right, but for at least proving the complexity of the problem it should be ok..) and then duplicating those sets once for each color, and then solving for the weighted exact set cover. Does that 'reduction' prove that this is NP-Hard? Is that even a reduction?

I've also thought about thinking about the problem the other way around, that is thinking about it in terms of the sets being assigned a certain color - but then I don't know exactly how to account for the overlapping of the sets in the minimization, also there will be some sets that do not have a single color so long as the sets that do have a single cover form a covering of the universe.

Thanks in advance.

# Answer
> 2 votes
Unfortunately this is NP-hard (even if we use only the costs 0 and 1), so it's very unlikely that there exists a polynomial-time algorithm that will solve every instance. I'll show this by reducing the NP-hard problem Exact Cover to your problem. I'll work with the decision variant of your problem, in which we are given a number $q$ in addition to $U$, $C$, $S$ and $cost()$, and the task is to report whether or not there is a solution with cost at most $q$. (With an algorithm that answers the decision problem, minimisation/maximisation can then be accomplished efficiently with binary search, and an actual solution realising that optimal solution size can also be recovered without too much extra difficulty.)

Recall that in the Exact Cover problem, we are given a collection $A = \\{a\_1, \dots, a\_r\\}$ of sets, each of which is a subset of some ground set $B$, and our task is to report whether or not it is possible to choose a subset $X \subseteq A$ of sets in $A$ such that every element in $B$ belongs to exactly one set in $X$. To encode an instance of the Exact Cover problem as an instance of your problem:

* For each set $a\_i$ in $A$:
    + Add the set $a\_i$ to $S$, as $s\_i$.
    + Add a new colour $c\_i$ to $C$.
    + Set $cost(b\_j, c\_i) = 0$ for every $b\_j \in a\_i$.
    + Set $cost(b\_j, c\_i) = 1$ for every $b\_j \notin a\_i$.
* Set $U = \cup\_{s\_i \in S}s\_i$ as usual.
* Set $q = 0$.

Basically, we create a colour $c\_i$ for each set $a\_i$ in $A$, and set the costs of that colour so that ground elements from the corresponding set ($a\_i$) get no cost, while every other ground element gets a positive cost. This means that whenever there does exist an exact cover for $A$, it is possible to create a zero-cost solution to the corresponding constructed instance of your problem: just assign every ground-set element the colour corresponding to the unique set that contains it. Thus, a "YES" answer to the Exact Cover problem implies a "YES" answer to the constructed instance of your problem.

In the other direction, we would like to show that a "YES" answer to the constructed instance of your problem implies a "YES" instance to the original Exact Cover problem instance. So, we start by assuming a "YES" answer to the constructed instance of your problem. This means that there exists a zero-cost assignment of colours to ground-set elements that could be produced by choosing a set cover from $S$, then choosing a colour for each set in the cover, and assigning that colour to all ground-set elements belonging to that set. We can represent such a solution as a pair $(X, f)$, where $X \subseteq S$ is the set of ground-element sets chosen for the cover, and $f : X \to C$ is a function that maps a set in $X$ to a colour in $C$. (Even though it is individual ground-set elements that we colour and not sets of them, $f$ is still well-defined for a feasible solution, since we require of every set $x \in X$ that every $e \in x$ is assigned the same colour.)

In order to easily build a solution to the original Exact Cover instance from $(X, f)$, we want the ground-set elements having some particular colour to be exactly the ground-set elements in some set in $A$: then we can simply go through each colour present in the solution to the your problem (i.e., in the range of $f$) and include the corresponding set from $A$ in the Exact Cover solution. So in other words, we would like to have a solution $(X, f)$ that has $f(x\_i) = c\_i$ for each $x\_i \in X$. But this is complicated by the fact that $X$ could contain sets that overlap, which is of course forbidden in an Exact Cover solution. Between any pair $x \in X, x' \in X$ there are two kinds of potential overlap: containment (either $x \subset x'$ or vice versa), and "proper overlapping", where $x \cap x' \neq \emptyset$ but neither set contains the other.

To address the problem of containment, it is easy to see that, whenever there exists a solution $(X, f)$ that contains a pair of sets $x \in X$ and $x' \in X$, one of which contains the other, then there also exists another solution $(X', f')$ with the same cost and in which the smaller of the two sets has been removed. (If $x = x'$, then just remove either one arbitrarily.) Iterating this process until we cannot apply it any more ensures that there must exist a solution $(X'', f'')$ in which no set in $X''$ contains any other set in $X''$. (Note that all we care about is the fact that such a solution *must exist*; for the purposes of answering the YES/NO question about the original Exact Cover instance, we don't need to know a specific solution.)

This leaves the problem of "properly overlapping" sets. I'll now show that these cannot occur in any zero-cost solution to your problem.

Suppose towards contradiction that there is some chosen set $x\_i \in X''$ such that $f(x\_i) \neq c\_i$. Then $f(x\_i) = c\_j$ for some $j \neq i$, with $x\_j \in X''$ also. But because there is no other set in $X''$ that contains $x\_i$ as a subset, there must be at least one ground-set element $b \in x\_i$ that is not also in $x\_j$. Thus assigning $b$ the colour $x\_j$ incurs a cost of 1, which cannot be recouped via any other means. Since we know that $(X'', f'')$ has a cost of 0, this is a contradiction. Thus it follows that if there exists a zero-cost solution $(X, f)$ to the constructed instance of your problem, then there must also exist a zero-cost solution $(X'', f'')$ to it in which no chosen set contains any other chosen set *and* in which no set properly overlaps any other set. $X''$ is, thus, an exact cover -- so the answer to the Exact Cover instance must also be "YES".

We have established that a "YES" answer to the constructed instance of your problem implies a "YES" answer to the original Exact Cover instance, and vice versa. This implies that a "NO" answer to either instance implies a "NO" answer to the other, which in turn implies that the two problems are equivalent. Since the construction of instance of your problem took only polynomial time and space, an algorithm that solves your problem in polynomial time could also be used to solve Exact Cover in polynomial time. Since Exact Cover is NP-hard, it follows that your problem must be NP-hard too.

---
Tags: complexity-theory, graphs, optimization, integer-programming
---


title: Well-Characterized vs NP-Complete

text:
# Question
Title: Well-Characterized vs NP-Complete
Definition: `Well-Characterized` also known as `Good-Characterized` is defined as follows:

> Problem that have Yes and No certificates i.e., are in NP $\cap$ co-NP, are said to be Well-Characterized. (**Reference**: *V.Vazirani, Approximation Algorithm*)

Does exist any `Well-Chracterized` problem that is also being `NP-Complete`? I don't looking for any proof, I just want a real-world example of such problem.

# Answer
We don't know. If any **NP**-complete problem were in **co-NP**, then we'd have **NP$\\,=\\,$co-NP** and we don't know whether that's true or not.
> 2 votes

---
Tags: np-complete, np
---


# Question
Title: Algorithm with $O(n)$ time and $O(n)$ space to compare two arrays
$A$ and $B$ are two arrays with $n$ elements each in the range $1$ to $n^2$.

1.How to check if the elements of $A$ are distinct in $O(n)$ time and $O(n)$ space

2.How to check if $A$ and $B$ have a common element in $O(n)$ time and $O(n)$ space.

Both the algorithms shouldn't use Hash sets or any other advanced data structure. A and B are just simple Arrays.

# Answer
A HashSet can store $n$ elements in $\mathcal{O}(n)$ space and add/query elements in amortized $\mathcal{O}(1)$ time. Therefore we can use the following approaches:

**1. Are A's values distinct?**

```
HashSet setA;
for i in {1, ..., n}
    if setA.contains(A[i])
        return "No, A[i] is a duplicate.";
    endif
    setA.add(A[i])
endfor
return "Yes, values are distinct.";

```

**2. Do A and B intersect?**

```
HashSet setA, setB;
for i in {1, ..., n}
    if setB.contains(A[i]) or setA.contains(B[i])
        return "Yes, A and B intersect.";
    endif
    setA.add(A[i]);
    setB.add(B[i]);
endfor
return "No, A and B are disjoint.";

```

**Edit:** Thanks to D'Nabre for pointing out a problem. The assumed $\mathcal{O}(1)$ for querying the HashSets may not work out in this case. D'Nabre also pointed at the element distinctness problem, which is worth a look. From Wikipedia:

> it may also be solved in linear expected time by a randomized algorithm that inserts each item into a hash table and compares only those elements that are placed in the same hash table cell.
> 2 votes

# Answer
The principle is similar to radix sort; then check uniqueness in each bucket.

* Prepare n lists of elements (buckets), initially empty
* For each element x:
    + Separate x into its two digits msd (most significant digit) and lsd in base n.
    + Append lsd to the end of the msd'th list
* Iterate through all buckets, check that each lsd in each list is unique. If not, some number x was added twice.

--

```
n = ...

def unique1(xs, seen):
  """Are the values of xs (0 to n-1) unique? O(len(xs))"""
  unique = True
  for x in xs:
    if seen[x]:
      unique = False
      break
    seen[x] = True
  # Clear seen[] for next run.
  for x in xs:
    seen[x] = False
  return unique

def unique2(xs):
  """Are the values of xs (0 to n^2-1) unique? O(n)"""

  # Sort xs into buckets by most significant digit. n buckets containing
  # len(xs) (= n) elements in total, so O(n) space.
  buckets = [[] for _ in range(n)]
  for x in xs:
    msd, lsd = divmod(x, n)
    buckets[msd].append(lsd)

  # Check uniqueness in each bucket. In total len(xs) values are passed to
  # unique1, so total O(n) time.
  temp = [False] * n
  for b in buckets:
    if not unique1(b, temp):
      return False

  return True

```

Edit: trivial to extend to second question by also storing the source of the element (set A or B) in the buckets.
> 2 votes

# Answer
It would be quite simple if your values were all in the range 0 ≤ k \< n: Create an array b of n boolean values initialised to all "false", then for each array element k check whether b \[k\] is true or false. If b \[k\] is true then there are duplicates, and if not then set b \[k\] = true.

Unfortunately, the values are from 0 to n^2 - 1.

For every j, 0 ≤ j \< n, build a linked list of all array values k where k = j (modulo n). That can be done in O (n) time and space for all array elements, since all you need to do is initialise n empty lists, and add each array element to one of the lists.

Then for each linked list, use the method above to check whether the values floor (k / n), which are all in the range from 0 to n-1, are unique. The array b is initialised *once*. Then we check one linked list, and when we are done with that list, we set all elements of b corresponding to list elements back to false. That way the total time is again O (n), since the total number of items in all linked lists is exactly n.

The essential "trick" to not use more than O (n) time is to not initialise the array b each time (O (n), needs to be done n times), but set it to "all false" only once, and then just set those elements back to false that were set to true before.
> 1 votes

---
Tags: algorithms, arrays
---


# Question
Title: Predict language from given expression $(b^* (aaa)^* b^*)^*$
I want to predict language from the given regular expression.

Regular Expression: $$(b^\* (aaa)^\* b^\*)^\*$$

As per my assumption language may be like:

Let the string contain alphabet $\\{a,b\\}$ where every string contain number of $'a'$ divided/multiply by $3$.

Let me know whether my assumption is correct or not.

Thanks

# Answer
A simple counter example can be found for your answer. Take the string $$ababa$$ Here, the alphabet is $\\{a,b\\}$ and the number of $a$s is a multiple of $3$, yet it doesn't fit into the regular expression.

In the regular expression, $b^\*(aaa)^\*b^\*$ denotes strings that contain an arbitrary (possibly zero length) sequence of $b$s, a sequence of $a$s that is a multiple of $3$ (possibly zero again), followed by an arbitrary length sequence of $b$s.

So, $(b^\*(aaa)^\*b^\*)^\*$ is such a sequence repeated over any number of times, including the empty string.

You could call the language as $$L=\\{x|x\text{ contains sequences of consecutive }\\a\text{s and }b\text{s, where the length of each sequence of }a\text{s is a multiple of }3\\}$$

over the alphabet $\Sigma=\\{a,b\\}$.

In general, a language is just some subset of the set of all strings over a given alphabet. Given a language, there need not be any straightforward way of describing it in English. A regular expression, given the alphabet, completely specifies and describes the language.
> 1 votes

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


title: Ask about a non-RE language

text:
# Question
Title: Ask about a non-RE language
I have a question about undecidability. And I hope you could point out where I am wrong.

The question is: to decide the following question as (A) recursive, (B) RE but not recursive, (C) not RE.

$L = \\{\langle M\rangle|M \text{ is a TM and } |L(M)| \geq 3\\}$

If we use $HP$ as halting problem and $\overline{HP}$ as the complement of halting problem. Then the solution could be (B) RE but not recursive (Taken from the Internet):

I understand this proof. But I have another proof as follows, and I can't figure it out why it is wrong.

---

We prove this by a reduction from $\overline{HP}$. Simulate $M'$ on input $w$ works as follows: it runs $M$ on $x$ and *rejects* if $M$ halts on $x$.

(1) $\langle M, x\rangle \in \overline{HP}$ $\rightarrow$ $M$ doesn't halt on $x$ $\rightarrow$ $M'$ accepts all inputs $\rightarrow$ $|L(M')| \geq 3 $ $\rightarrow$ $M' \in L$

(2) $\langle M, x\rangle \notin \overline{HP}$ $\rightarrow$ $M$ halts on $x$ $\rightarrow$ $M'$ doesn't accept any input $\rightarrow$ $|L(M')| \< 3$$\rightarrow$ $M' \notin L$

Thus $\overline{HP} \leq\_m L$. As $\overline{HP}$ is not RE, $L$ is not RE, which is wrong.

---

So where is wrong?

Thanks!

# Answer
> 0 votes
Recall that if a TM $M$ doesn't halt on input $x$, then $x \notin L(M)$

Your mistake is in (1), if $M$ doesn't halt on $x$, then $M'$ doesn't halt too (since the simulation of $M$ on $x$ doesn't halt). so $M'$ doesn't accept any input, that is $L(M')=\phi$.

---
Tags: computability, undecidability
---


# Question
Title: How to show that $\log (n!) = \Omega(n\log n)$ using Stirling's approximation?
Using Stirling's approximation, we have $\log\_{2} (n!) = n\log\_{2} n - (log\_{2} e)n + O(log\_{2}n)$. Most lecture notes I have come across say that $ n\log\_{2} n - (log\_{2} e)n + O(log\_{2}n) = \Omega (n\log\_{2} n)$. Can someone give a rigorous proof of the last line using the basic definitions of big-O and big-Omega?

Thank you in advance.

P.S. There are similar posts on this and I know some other proofs of $\log (n!) = \Omega(n\log n)$ with or without using Stirling's approximation. I don't have any problem with $\log (n!) = \Omega(n\log n)$. It's just that I can't see why $ n\log\_{2} n - (log\_{2} e)n + O(log\_{2}n) $ is $ \Omega (n\log\_{2} n)$.

# Answer
> 0 votes
A function $f(n)$ is said be $\Omega(g(n))$ if there exist $c,n\_0\gt 0$ such that $f(n)\ge cg(n)\ge 0$ for all $n\ge n\_0$.

A function $f(n)$ is said be $\mathcal O(g(n))$ if there exist $c,n\_0\gt 0$ such that $0\le f(n)\le cg(n)$ for all $n\ge n\_0$.

Here, $$\log\_2(n!)=n\log\_2 n-(\log\_2 e)n+\mathcal O(\log\_2 n)$$

Let $f(n)=\mathcal O(\log\_2 n)$ such that $$\log\_2(n!)=n\log\_2 n-(\log\_2 e)n+f(n)$$

By definition, $f(n)\ge 0$.

Thus, $$\begin{align}\log\_2(n!)&\ge n\log\_2 n-(\log\_2 e)n\end{align}$$

We want to find some constants $c,n\_0\gt0$ such that $$n\log\_2n-(\log\_2e)n\ge cn\log\_2 n$$ for all $n\ge n\_0$, that is, it must satisfy, $$(1-c)n\log\_2n\ge (\log\_2e)n$$ As $n\gt 0$, it must satisfy $$(1-c)\log\_2n\ge (\log\_2e)$$ Note that $$(1-c)\log\_2n\ge(1-c)\log\_2n\_0$$ for all $n\ge n\_0$. So, we need a positive $c$ and a $n\_0$ to satisfy $$(1-c)\log\_2n\_0\ge (\log\_2e)$$ This is easily possible, as the RHS is a constant and the LHS can be made large by choosing $n\_0$ and $c$ appropriately. For instance, choosing $c=0.1$ and $n\_0=4$ works.

Thus, by definition, $$\log(n!)=\Omega(n\log n)$$

# Answer
> 0 votes
You really don't need Stirling's approximation.

Upper limit for log (n!): n! is the product of n numbers, all with a logarithm ≤ log n.

Lower limit for log (n!): n! is the product of n numbers, half of which are ≥ $n^{1/2}$ if n ≥ 4, which makes the logarithm ≥ log n / 2.

So for n ≥ 4, (n log n) / 4 ≤ log (n!) ≤ n log n.

# Answer
> 0 votes
I'll write $\log$ for $\log\_2$, since that's the only kind of log we care about, here.

We have $\log n! = n\log n + c\log n + O(\log n)$, where $c=\log \mathrm{e}$ is positive. So, there's a constant $d$ such that, for all sufficiently large $n$, we have

$$n\log n + \log n - d\log n \leq \log n! \leq n\log n + c\log n + d\log n\\,.$$

For all $n\geq c$, $0\leq c\log n\leq n\log n$. For all $n\geq 2d$, $\tfrac12n\log n\geq d\log n$. This gives $$n\log n + 0 - \tfrac12n\log n \leq \log n!\leq n\log n + n\log n + \tfrac12n\log n\\,,$$ which is to say, $$\tfrac12n\log n \leq \log n!\leq \tfrac52n\log n\\,,$$ and we're done.

---
Tags: asymptotics
---


# Question
Title: What's the fastest way to find the Kth smallest value in an unsorted list without sorting?
My initial algorithm:

1. Compare element 0 with every other element, keeping track of how many elements are less than it.
2. Repeat for each element until an element that is greater than exactly (k-1) elements is found.

I assume this would take $O(n^2)$ in the worst case. Can a faster runtime be achieved without sorting the list?

# Answer
> 10 votes
Use selection algorithm for linear time https://en.m.wikipedia.org/wiki/Selection\_algorithm

# Answer
> 5 votes
Unfortunately I can't just comment but I have to post it as an answer.

Anyway, you could try to use a min-heap on your unsorted array, you should be able to get a time complexity of O(n+k\*logn).

# Answer
> 3 votes
The Quickselect algorithm can do that in O(n) average complexity, it is one of the most often used selection algorithm according to Wikipedia.

It is derived from QuickSort and as such suffers from a O(n²) worst case complexity if you use a bad pivot (a problem that can be avoided in practice).

The algorithm in a nutshell: After the pivoting like in QuickSort, only descend into either the lower or the higher side of the array - depending on which of them has the element you're after.

# Answer
> 2 votes
Create a max-heap of size $k$. The invariant is that the heap always contains the $k$ smallest elements observed so far.

1. Insert the first $k$ elements of the list into the heap
2. For each remaining element $i$ in the list:
    * let $M$ be the maximum element in the heap
    * If $i \< M$, then delete $M$ and insert $i$ into the heap

At the end, the heap will contain the $k$ smallest elements in the list.

Looking up the maximum element has constant cost. The cost of insertion and deletion is $O(k)$. The time complexity of this method is $O(n . \log k)$

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


# Question
Title: integer = c lg n (inputs of size n, Cormen 3rd, page 23)?
I just started with my "Algorithms" course. But my CS-background is lower than that of an average CS-student (I'm a data science student). Only had intro-2-prog course (Python/Java), that's it.

Cormen states on page 23: "...when working with inputs of size n, we typically assume that integers are represented by c lg n bits..."

* How is " c lg n " derived? It's relation to the input size?
* What calculation/proof is made here?
* Which assumptions should one have to come to this assumption?
* Which CS-field/subject (or academic/uni course?) works/operates with this notation, that should be learned prior to the "Algorithms" couse?

# Answer
`lg n` is the base-`2` logarithm of `n`, satisfying `2^lg n = n`, so about `lg n` bits (`ceil lg n` to be exact) are needed for integers that can represent `0..n-1`, which suffices for pointers into the input. The authors of CLRS are saying that the word size should be about this much (`c lg n`). This is arguably reasonable because `c lg n`-bit words index storage of `n^c` (so any polynomial in `n`), and `c lg n`-bit operations can be synthesized from `lg n`-bit operations in constant time. If we make the word size much bigger, then the implied data-parallelism starts to distort running times.

The mathematical preliminaries here should be covered in an intro discrete mathematics class.
> 2 votes

---
Tags: algorithms, encoding-scheme
---


title: Exist algorithms without input data?

text:
# Question
Title: Exist algorithms without input data?
I would like to know cases that an algorithm runs without any data entry.

# Answer
Yes, of course they exist, and they're useful both practically and theoretically.

Any time you write a computer program to solve some specific task that's hard-coded into the program (for example, to compute some value or find solutions to a specific set of equations you're interested in), that's an algorithm with no input.

If you want to prove undecidability of, e.g., the problem of determining whether a Turing machine halts for every input, the first step is to translate a program that uses its input to a program that doesn't use its input and always computes as if it received some specific input. That's another example of an algorithm without an input.
> 3 votes

# Answer
In addition to David Richerby's answer which I find very complete I wanted to add a few specific cases (which actually follow his explanations):

1. The computation of some irrationals such as $\pi$ or $e$.
2. The list of prime numbers and other lists (i.e., lists of logarithms and such) which do not require a seed.
3. Equations in general (but clearly not all as many might require boundary conditions), either algebraic or non-linear. This would also include solving some set of mathematical expressions such as differential equations or integrals.

Hope this helps,
> 1 votes

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


# Question
Title: What is the name of this positive integer set data structure?
Google is failing me, so here goes:

* The data structure is used to describe a set of positive integers.
* It works conceptually, by keeping track of disjoint ranges \[a,b) on the number line.
* These ranges are stored, in a sorted manner. For two consecutive ranges `[a, b), [c, d)` the invariant is that `a < b < c < d`.
* The ranges are stored flat in an internal array, meaning that for the ranges `[a, b), [c, d)` the internal representation is `[a, b, c, d]`.
* To look up if an integer `x` belongs to the set, we perform a binary search. If `x` is found in the array at an even position, `x` is a member; if `x` is not found in the array, but can be inserted at an odd index while preserving order, it is also a member. Otherwise `x` is not a member.
* The internal array does not necessarily contain an even number of elements; if there is an odd number of elements, the last range is open-ended above. `[a, b, c]` is the set `[a,b) ∪ [c,∞)`
* Conceptually you start excluding numbers up from zero until you reach the first number in the array, then you include numbers up until the second number of the array, then you exclude until the third, include until the fourth, etc.
* Union of a collection of sets is made by iteratively taking the least element from the set with the smallest least element. If that element used to occupy an even index, we increment a counter, if it used to occupy an odd index, we decrement. Whenever the counter moves away from zero, or falls to zero, we include the just-removed element in the new array, otherwise we discard it.
* Complement of a set is computed by inspecting the first element of the array. If it is zero, remove it, it it is not zero, prepend zero.
* This data structure is often used to store information about Unicode properties, as it very compactly describes consecutive ranges of Unicode code points.

What is the name of this beast?

# Answer
> 3 votes
The name of the data structure, as @Evil correctly pointed out, is an Inversion List.

And boy is that Wikipedia article a stub.

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


# Question
Title: How do you solve a recurrence relation with multiple subproblems of different sizes?
For instance, consider the following recurrence relation.

> T(n) = T(n/2) + T(n/3) + T(n/4) + n

Would you use the substitution method for this?

# Answer
> 0 votes
You can find an upper bound like this: $T(n)\leq 3T(n/2)+n$.

Solving using master theorem, $T(n)=O(n^{log\_23})$

---
Tags: recurrence-relation
---


title: Interesting problem on tree

text:
# Question
Title: Interesting problem on tree
You are given a tree of $N$ nodes with colors assigned to each node. You need to find for each node $X$, a value $AR\[X\]$.

$AR\[X\]$ = The sum of values of $CALC(X , i)$ for each $i$ from $1$ to $N$.

$CALC(A,B)$ = Count the number of non-repeating colors in the path from $A$ to $B$.

Can somebody suggest an efficient solution to this problem?

# Answer
For a fixed root, there are two kinds of path: the ones which pass the root and the ones which don't. The first kind is special since we can seperate a path $(a,b)$ into $(a,r)$ and $(r,b)$, which might be easier to deal with via proper preprocessing. Consider following divide and conquer procedure:

```
Solve(T):
  Fix a root r
  for each a
    for each b s.t. (a,b) pass r
      AR[a]+=calc(a,b)
  for each branch T_i of r (which is also a tree)
    Solve(T_i)

```

Note that we neither miss a pair nor count a pair twice since $(a,b)$ don't pass $r$ if and only if they are in the same branch. In addition, it's not hard to prove that trees in depth-$d$ recursive call don't overlap. Therefore, if we can do the non-recursive part in $O(\text{size of tree})$, the complexity would be $O(\text{recursive depth}\times n)$. If we always choose $r$ as the centroid, recursive depth is bounded by $O(\log n)$ and hence the complexity would be $O(n \log n)$. Now let's see how to solve the non-recursive part.

For a pair of node $(a,b)$, let $\text{path}(a,b)$ denote the set of distinct values on the path from $a$ to $b$, and $I\_{ab}(v)$ denote the indicator function which is $1$ when $v\in \text{path}(a,b)$ and $0$ otherwise. It's not hard to see $\text{calc}(a,b)=|\text{path}(a,b)|=\sum\_vI\_v$.

Recall that in each phase, we choose the centroid $r$ as the root and consider only the paths passing the root. Let $B\_a=\\{b\in T:(a,b)\text{ pass }r\\}$. Using the indicator function above, we have $\sum\_{b\in B\_a}\text{calc}(a,b)=\sum\_{b\in B\_a}\sum\_v I\_{ab}(v)=\sum\_v\sum\_{b\in B\_a} I\_{ab}(v)$. Therefore, computing $\sum\_{b\in B\_a} I\_{ab}(v)$ for each $a$ and $v$ also gives us the answer. (You can interpret this as the number of $b$ such that $v\in \text{path}(a,b)$.) To do this, consider the set $S$ for each value $v$ such that $S\_T(v)=\\{u\in T: v\in\text{path}(r,u)\\}$. We need to maintain $|S(v)|$ for the whole tree and similarly $|S\_i(v)|$ for the $i$-th branch of $r$. We will see how to implement this later.

Since $B\_r=T$, $\sum\_{b\in B\_r}\text{calc}(r,b)$ is exactly $\sum\_v|S(v)|$. Next, consider node $a$ in the $i$-th branch. Let $r\_i$ denote the $i$-th child of $r$. For each node $b$ which is **not** in the $i$-th branch, we can split path $(a,b)$ into $(r,b)$ and $(r\_i,a)$. Therefore, $$\sum\_{b\in B\_a}\text{calc}(a,b)=\sum\_{b\in B\_a}\text{calc}(r,b)+\sum\_{b\in B\_a}|\text{path}(r\_i,a)\backslash\text{path}(r,b)|$$ It's not hard to see that the first term equals to $\sum\_v(|S\_T(v)|-|S\_i(v)|)$, so let's focus on the second term. Now consider each node $u$ on the path from $r\_i$ to $a$ and count $\text{value}\[u\]$ one by one. There are two possible cases:

1. $\text{value}\[u\]=\text{value}\[u'\]$ for some $u'\neq u$ on the path from $r\_i$ to $u$. In this case, we have already counted $\text{value}\[u\]$ before so just ignore it.
2. If not, we should count the number of $b$ such that $\text{value}\[u\]$ doesn't appear in $\text{path}(r,b)$ and add it to $AR\[a\]$. This is exactly $(n-n\_i)-(|S(\text{value}\[u\])|-|S\_i(\text{value}\[u\])|)$ where $n\_i$ is the number of nodes in the $i$-th branch.

Note that the number we count for each $u$ is independent from $a$. Therefore we can do this for every $a$ in a single DFS which takes $O(n)$. (Tell me if you need more details.)

Now the only remaining part is the preprocessing which computes $|S(v)|$, and it's actually similar to previous steps:

Consider each node $u$.

1. If $\text{value}\[u\]=\text{value}\[u'\]$ for some $u'\neq u$ on the path from $r$ to $u$, we have already counted $\text{value}\[u\]$ before so just ignore it.
2. If not, add $n\_u$ to $|S(\text{value}\[u\])|$. Here $n\_u$ means the size of subtree rooted at $u$.

$|S\_i(v)|$ can be computed similarly. The preprocessing also takes $O(n)$.

The complete flow seems like

```
Solve(T):
  Choose a centroid r as the root
  Preprocess() //Compute |S(v)| and |S_i(v)| via a tree traversal

  AR[r]+=Sum{|S(v)|}
  for each node u
    AR[u]+=Sum{|S(v)|-|S_i(v)|}

  Update AR with the second term via another tree traversal

  for each branch T_i of r (which is also a tree)
    Solve(T_i)

```
> 1 votes

# Answer
Let's call a number of unique values over path $(a, b)$ its *cost*. You need at first to calculate a matrix of costs for all possible pairs in the tree. This matrix will be symmetric with ones on the main diagonal. After you have this matrix, you can find your $AR(n)$ values by summarizing costs on its rows (or columns).

Let's at first build a matrix $M$ of **sets** \- each element of this matrix, corresponding to a path $(a, b)$ will contain a set $S(a, b)$ of (unique) values on this path. The cost of the path $(a, b)$ will be a number of elements in the set $S(a, b)$.

The following recursive process will produce this matrix of sets:

**Subdivbision step.** Find an edge $(b\_1, b\_2)$ in the tree $T$ in such way that its removal will give you two trees $T\_1$ and $T\_2$ with approximately the same number of nodes. Calculate matrices of sets for both $T\_1$ and $T\_2$.

**Merging step.** The matrix of sets for the tree $T$ will consist of four parts - the matrix of sets for $T\_1$, the matrix of sets for $T\_2$, and two "cross-over" matrices for paths from $T\_1$ to $T\_2$ and for paths from $T\_2$ to $T\_1$ (you can calculate just one of the cross-over matrices because of symmetry). The following formula can be used to calculate a set $S(n\_1, n\_2)$:

$$S(n\_1, n\_2) = S(n\_1, b\_1) \cup S(b\_1, b\_2) \cup S(b\_2, n\_2)$$

where $n\_1 \in T\_1$ and $n\_2 \in T\_2$.

You can use Tree Centroid Decomposition during the subdivision step - and I'll leave that to you.
> 0 votes

---
Tags: algorithms, trees
---


# Question
Title: Decidability of bitstring languages with no ones' complements
For any string $s \in \\{0,1\\}^\*$, let the ones' complement of $s$, denoted $1\_c(s)$, be the string obtained by flipping all bits in $s$. For example, $1\_c(001100) = 110011$. Now call a language $L \subset \\{0,1\\}^\*$ *ones' complement asymmetric* or OCA for short, if for every string $s \in \\{0,1\\}^+$, precisely one of $s$ and $1\_c(s)$ is in $L$.

I want to come up with a mapping reduction from a language $L \subset \\{0,1\\}^\*$ to an OCA language (and vice-versa) so as to prove the existence of decidable/recognizable and undecidable/co-recognizable and undecidable, etc., OCA languages. My problem is especially that we require *every* string in $\\{0,1\\}^+$ to be such that either it or its ones' complement appears in any OCA language. This seems particularly problematic if $L$ lacks strings of a particular length, meaning it isn't obvious how we'd go about constructing an OCA language from $L$.

# Answer
> 3 votes
I don't think there exist recognizable-but-undecidable OCA languages, because if we have a Turing machine *M* that recognizes a given OCA language, then we can create a derived Turing machine that incrementally simulates *M* on both its input and its one's-complement (flipping back and forth, trying a finite number of steps in each simulation) until one input or the other has been recognized.

(Note: the derived Turing machine will also need to be given specific logic to decide the empty string; but that's obviously possible to do for any given language.)

Therefore, you can't construct any reduction mapping that would let you prove the existence of recognizable-but-undecidable OCA languages.

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


# Question
Title: If all frames are naturally broadcast in a LAN, what is the need for a broadcast address?
The Ethernet MAC address FF:FF:FF:FF:FF:FF is reserved for broadcasts. If all frames are naturally broadcast in a LAN, what is the need for a broadcast address?

# Answer
> 3 votes
So that receiving devices can blindly throw away packets that aren't addressed to them or the broadcast address. Doing this test is much simpler than having to verify the CRC and tossing it up to the next layer that may toss it out itself.

A switch will also make use of the target address to only propagate packets to where it knows the destination address resides, reducing congestion.

The broadcast destination is used for stuff like DCHP where the sender doesn't know the target's MAC but still needs to send out the message.

# Answer
> 1 votes
The purpose is to inform the recipients that they should receive rather than ignore the message.

While Ethernet messages are "naturally broadcast", this is an implementation detail. Most messages are intended only for one recipient, and just happen to be receivable by the other addresses connected to the LAN.

---
Tags: computer-networks
---


# Question
Title: what's analogy learning algorithm ? differences from induction learning algorithm?
I am a computer engineering student and trying to get the idea behind all these Artificial Intelligence Concepts and applications. I know little theoretically about machine learning and some high level brief introduction of artificial intelligence as a whole and neural network. What i am interested in is knowing the similarities or difference between the concepts: Deep Learning, Genetic Algorithm/Programming, Artificial Neural Networks and Machine Learning. How do they relate or how they help each other? What are their particular applications?

# Answer
In a nutshell, (statistical) machine learning is a certain approach to artificial intelligence. Traditional artificial intelligence incorporates hard-coded rules which are written by humans. Statistical machine learning, in contrast, has the computer learning the rules by itself using statistical means.

There are several paradigms used for statistical machine learning, such as support vector machines, artificial neural networks, and genetic algorithms. Recently a certain type of artificial neural networks, *deep* neural networks, has come to the fore due to unprecedented performance. Machine learning using deep neural networks is known as *deep learning*.
> 0 votes

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


# Question
Title: Checking if a given flow is a maximum flow
I'm curious as to if there's any way to check (without having to run a 'whole' maximum-flow-algorithm) whether a given flow $f\_e$ is the maximum flow of the flow graph $G$ in $O(|E|)$ time complexity.

I've thought about running one iteration of Ford-Fulkerson to see if there is an augmenting path from the source $s$ to the sink $t$, but couldn't such a solution get a time complexity worse than $O(|E|)$ in the worst case?

# Answer
A flow is maximum if there is no $s$-$t$ path in the residual network. You can check this in time $O(|E|)$.
> 4 votes

---
Tags: graphs, graph-traversal, network-flow, ford-fulkerson
---


title: How hard are PSPACE-complete problems?

text:
# Question
Title: How hard are PSPACE-complete problems?
There are already good answers from several perspectives regarding the "hardness" of $PSPACE$-complete problems, such as this: What is practical difference between NP and PSPACE-complete?

But what are the practical implications when we actually try to solve (decide) a $PSPACE$-complete problem on a deterministic Turing machine? If $PSPACE \neq NP$ (or $PSPACE \neq P$, should it make a difference) then obviously it will take super-polynomial (exponential?) time. But what about space? Is there some $k\>1$ that we know of such that it will definitely take $\Omega(n^k)$ space? And do we know for sure that it won't take more than $O(n^l)$ space for some $l$?

(Or is the question itself stated badly for some reason?)

# Answer
> 7 votes
By *definition*, PSPACE consists of all languages decided by some Turing machine using polynomial space. So every language in PSPACE can be decided by some Turing machine using space $O(n^\ell)$ for some $\ell$. The space hierarchy theorem ensures moreover that for any $\ell$ there is a language in PSPACE which requires space $\Omega(n^\ell)$.

Any PSPACE-hard language requires space $\Omega(n^k)$ for some $k$, since otherwise any language in PSPACE would be decided by a Turing machine using subpolynomial space, and this contradicts the space hierarchy theorem.

For any $k \> 0$ there is a PSPACE-hard language which can be decided in space $O(n^k)$. Indeed, take any PSPACE-complete language $L$. It can be decided using space $O(n^\ell)$ for some $\ell$. Consider now the language $L' = \\{(x,0^{|x|^{\ell/k}}) : x \in L\\}$, which is PSPACE-hard by reduction from $L$. An algorithm for $L$ can be converted to one for $L'$ which uses $\log n$ space to verify the input structure and $O(|x|^\ell)$ for the rest. Since $n \geq |x|^{\ell/k}$, $O(|x|^\ell) = O(n^{(k/\ell)\ell}) = O(n^k)$.

---
Tags: space-complexity
---


# Question
Title: Convert a digraph to the corresponding undirected graph in linear time using adjacency lists
Suppose we have a directed graph $G = (V,E$) represented with adjacency lists. Is it possible to convert $G$ into its undirected equivalent\* $G'$, also represented with adjacency lists, in $O(|V|+|E|)$ time?

The obvious algorithm walks the adjacency list of each vertex $v$, and for each adjacent vertex $u$, inserts edges $(v,u)$ and $(u,v)$ into $G'$. The issue is duplicates. If $(u,v)$ happens to be in $G$ already, $(u,v)$ will be inserted into $G'$ twice: once when processing $v$'s adjacency list, and once when processing $u$'s. Assuming that a well-formed graph doesn't contain any duplicate edges, we would need to check $u$'s adjacency list to see whether it contains $v$ before performing the second insertion. But this check takes linear time in $|V|$, and we would need to perform this check for $O(|E|)$ edges, resulting in $O(|V|\*|E|)$ time complexity.

\*Terminology: by "undirected equivalent" of a digraph $G=(V,E)$, I mean the directed graph $G'=(V,E')$ such that

if $(v,u) \in E$ then $(v,u) \in E'$ and $(u,v) \in E'$ and
if $(v,u) \in E'$ then either $(v,u) \in E$ or $(u,v) \in E$.

# Answer
If you perform the check at the end rather than throughout, it will be much faster.

Start by going over all edges, and for each edge $(i,j)$ add the edge $(j,i)$ to the adjacency list of $j$.

Now given the adjacency list of $i$, we want to remove duplicates. For that we use an array indexed by $V$, which is initialized to zero (we only need to initialize it once). Go over the list and count how many times you see each edge. Now go over the list a second time and only add the first occurrence of every edge. Finally, go over the list a third time to reset the array back to zero. In all, we do $O(1)$ work per edge.

One drawback of this algorithm is that the resulting adjacency lists aren't sorted, even if you started out with sorted ones. Here is a different algorithm which works in $O(|V|+|E|)$ time and maintains this invariant (assuming it holds originally). For each vertex $i$, compute the sorted lists $\\{ j : (i,j) \in G \\}$ and $\\{ j : (j,i) \in G \\}$. Then merge them and remove duplicates.
> 5 votes

# Answer
Yuval's idea is probably better, but I'm posting mine anyway since it's a different approach.

First of all, observe that the only duplicates are those involving two nodes $u, v$ such that there is an edge "in both directions", in other words cycles of length two.

In the DFS forest of $G$, the only such edges are back-edges going from a node to its parent. This suggests an algorithm to solve your problem. Perform a DFS of $G$, adding each edge you find to $G'$, except for the edges $(u, v)$ such that $v = \pi(u)$.
> 2 votes

---
Tags: graphs
---


# Question
Title: Approximating the dominating set on a certain kind of DAG
A *dominating set* on a *directed graph* $G=(V,E)$ is a subset $D$ of $V$ such that for all $v\in V$ it holds that $v\in D$ or there is an $u\in D$ such that $(u,v)\in E.$

For a concrete problem (size reduction of endgame tablebases), I want to approximate the dominating set of a directed acyclic graph with the following properties:

* Each vertex $v\in V$ has a nonnegative integer $\mathop{\mathrm{DTM}}(v)$ assigned to it (with DTM standing for *distance to mate*)
* For each pair of vertices $(u,v)$, if $(u,v)\in E$, then $1+\mathop{\mathrm{DTM}}(u)=\mathop{\mathrm{DTM}}(v)$ (if a move leads from $v$ to $u$, then the distance to mate from $v$ is one larger than that from $u$)
* For each vertex $v\in V,$ there exists a vertex $z\in V$ with $\mathop{\mathrm{DTM}}(z)=0$ such that a path from $z$ to $v$ exists (each position can be brought to mate)

Given these boundary conditions, is there an efficient way to approximate $D$ for large graphs (more than 100'000'000 nodes?)

# Answer
That problem is hard to approximate by reduction from set cover:
max(DTM) = 2    and    exactly one vertex has  DTM = 0
and    the vertices with  DTM = 1  are exactly the sets    and
the vertices with  DTM = 2  are exactly the set-elements

To push a solution forward, just add in the  DTM = 0  vertex.
To pull a solution back, remove that vertex if it's present, and for each
DTM = 2  vertex, replace that vertex with any one of the sets that element is in.
However, you presumably have another property:  low maximum degree .
That is useful because:

Your problem is a special case of set cover:  The elements are the vertices and the
sets are those formed as \[v in V such that u=v or (u,v) in E\] for elements u of V.
The size of those sets is bounded above by one plus your graph's maximum out-degree.
Theorem 3.1.6 says the greedy algorithm does significantly better on such instances.
> 2 votes

---
Tags: graphs, dag
---


title: Sum collision from two lists of numbers

text:
# Question
Title: Sum collision from two lists of numbers
Suppose you have two large lists of integers of length $N$, and you want to find two pairs $(a\_1, b\_1)$, $(a\_2, b\_2)$ from the lists such that $a\_1 + b\_1 = a\_2 + b\_2$ (modulo the integer width). Say for example, that $N = 2^{32}+1$ and the integers are 64 bits.

Is there any efficient way to do this? I know that if you are given a particular value, you can easily find the pairs that sum to that value in linear time, so the hard part is finding the colliding sum value in the first place. The obvious approach is $O(N^2)$, but I can't think of anything better.

One other idea I had was to try FFT to do a convolution on the lists, but I don't think that helps because the lists of integers are sparse, while my understanding is that the fourier transform would involve computing $2^{64}$ elements.

This answer says that there is an $O(N^{4/3})$ algorithm if the integers are randomly distributed, but doesn't provide any details.

# Answer
> 1 votes
You can find a solution with an algorithm that requires about $2^{24}$ operations and $2^{22}$ space, and requires only $N=2^{22}$ entries in each list. (If you have more than that in each list, ignore the rest and use only the first $2^{22}$ entries.) Here's how.

*Step 1.* Build a list $L$ of all of the pairs $(a,b)$ such that $a+b \equiv 0 \bmod 2^{22}$.

By the birthday paradox, we expect there will be about $N^2/2^{22} \approx 2^{22}$ such pairs $(a,b)$, since there are $N^2$ possible pairs and each pair has a $1/2^{22}$ chance of satisfying the condition. To find them, build a sorted list of the values $a \bmod 2^{22}$, a sorted list of the values $-b \bmod 2^{22}$, and merge the sorted lists. Or, use a hash table.

*Step 2.* Look for two pairs $(a\_1,b\_1)$ and $(a\_2,b\_2)$ in $L$ that have the same sum modulo $2^{64}$.

By the birthday paradox, we expect such a solution should exist with high probability, since we have about $2^{22}$ entries in $L$ (and thus about $2^{43}$ candidate solutions) and the condition holds with probability $1/2^{42}$. (Why $1/2^{42}$? Well, their sum is guaranteed to match in the low 22 bits, by the way we constructed $L$. So, we just need their high 42 bits to match too.)

---
Tags: algorithms, combinatorics
---


# Question
Title: Deterministic construction for trapezoidal decomposition
There is a nice decomposition called trapezoidal to process point location queries given a set of disjoint generally curvilinear segments. I found the randomized algorithm for building this type of decomposition in Berg's book on computational geometry. Can someone point me out papers which report deterministic algorithms with only a little polynomial overhead which provides the same capabilities of trapezoidal decomposition for point location ?

# Answer
I finally found recent paper titled "Optimal randomized incremental construction for guaranteed logarithmic planar point location" by several authors, where deterministic times are given for query and the seach structure, but expected time for preprocessing.
> 0 votes

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


# Question
Title: Optimizing estimator of composed functions when function is known
I have a problem which I'm looking to see if there is literature on:

Consider three types of actors, a Director, Aggregator, and Follower. The Director talks to multiple Aggregators, the Aggregator talks to multiple Followers. The director gives simple commands to the Aggregator, who then can portion out the commands to each Follower as she sees fit.

The question then is, how can the Director know whether or not an Aggregator can complete a given request at time step T? T+1? If T is now, then this is relatively easy as the Aggregator can simply sum up the capabilities of each of the Followers and return it, saying "this is what I can do in total." The problem then is, if the Director is doing her own optimization problem in deciding how to direct two different Aggregators, given each command she must be able to predict how the Aggregator will react. I.e., what are the Aggregator's capabilities in time step T+1 given a direction D in time step T?

Due to the complexity of the Aggregator, I think it's likely best to create an estimator across the current state of the Aggregator (or all of their followers). Further, the Aggregator can give whatever knowledge it wants to the Director, though ideally this would be of constant size no matter the size of the set of Followers. This is therefor an optimization problem on the Aggregator's side for creating an optimal estimator, which is well studied.

What I want to know: Is there any literature about creating an estimator when you *know* the exact function you are estimating? So if I am the aggregator, how can I tell the Director, in a constant space for the amount of information I give no matter the number of followers, the information require to best predict I would react to a given direction?

Put another way: How can I create an optimal estimator in which I have full knowledge of the shape and composition of the functions I am estimating?

I can think of a number of places where this might occur, potentially in networking, data compression, etc., though I think I don't have the necessary vocabulary. I've tried searching through aggregation, optimization, estimation, forecasting, prediction, which a number of different combinations of keywords relating to these. There is a ton of generalized work on making estimators and predictors, though none which target the assumption that they already have perfect knowledge of that which they're estimating.

# Answer
> Is there any literature about creating an estimator when you know the exact function you are estimating?

I think *streaming algorithms* may be of interest to you. A streaming algorithm is an algorithm that operates on some model of a massive 'stream' of data that is simply impossible to completely store, but it is possible to traverse it and do some computations with bounded memory. Often, it is impossible to solve even simple computations with bounded memory, but answers that are correct with high probability can be found efficiently, with techniques as random sampling, aggregating medians or probabilistic data structures.
> -1 votes

---
Tags: optimization, reference-request, machine-learning
---


# Question
Title: Map overlay, any algorithm for face updating step?
In chapter 2 of this book the map overlay algorithm, which takes as inputs two doubly connected edge lists, is explained. "Basically" a line intersection algorithm allows to update both the half edges records and the vertices records. After such step the detection of boundary cycles is applied, and later a graph is built, where each connected component represents a new face record. It is explained how to detect whether a boundary cycle is clockwise or not, but I'm not sure how an overall module that implements this part should work. Say I have a DCEL where the face records are not valid, but both the half-edges and the vertices are, do you know any detailed algorithm the actually build the graph? Even a pseudocode is fine.

I can understand how to implement the boundary cycles detection, I would iterate through the half-edges list, navigate through the "next" record, remove such record from the list and when I reach the initial half-edge I would go to the next half-edge of the list and repeat. I would put such sub list of half edges into another list so I would have a list of boundary cycles. I would also label each element of the boundary cycles list as "clock wise" or "anti-clockwise" based on the trick the book explains. Once I have such a list how do I figure out what boundary cycles are incident to the same face? In practice what's the test applied?

# Answer
Before we 'fill in' the value for the new faces at the halfedges, we wait until the rest of the algorithm is finished, so we know which faces are still present in the end and only have to traverse every edge once. We do this by getting the halfedge that we have considered as a 'representative' and traverse the proper cycle until we return at our edge. So, our complexity is bounded by the sum of the faces and the edges, instead of their product, giving $O(n)$ instead of $O(n^2)$.

That book tends to ignore the subtleties that arise in dealing with DCELs. At first, it seems strange that updating faces would take only $O(n)$ time, since the face of the edge would get updated multiple times. Here, $n$ is 'the complexity of the subdivision', i.e. the sum of the edges and faces of the DECL.

However, since we only want to store the final face value at the end, we wait with the updating the face values of the half-edges until we have filled in everything else. We can store the new value at only one half-edge, which will be the 'representative' of that face and maintain a list of those half-edges.

Then, at the final step, we fill in the face values for the cycles of the stored representative edges, by traversing the cycle associated with the half-edge until we return to the edge where we started and remove a (different) representative if we encounter it, since this means that the face it belonged to no longer exists. By doing so for every representative in the correct order (i.e. from the last created face to the first), we avoid traversing cycles for faces that do not occur in the final DECL. So, we are able to check every face and visit all edges after that, which means we get the required complexity of $O(n)$.
> 1 votes

---
Tags: graphs, computational-geometry
---


# Question
Title: "Learning occupancy grid maps with forward sensor models, S.Thurn,2008" a formula that is difficult to overcome
I am reviewing the document" Learning occupancy grid maps with forward sensor models, S.Thrun, 2008" (http://faculty.iiit.ac.in/~mkrishna/ThrunOccGrid.pdf)

i am really confused about formula (26), which is merged by formula (22), (24), (25) in an "intersection of probabilities" computed in (22),(24),(25). So, it should be a product of factors in (22),(24),(25). If it is correct, the first factor of (26), 1/sqrt(2\*π\*σ), should be powered.

any one can tell me why 1/sqrt(2\*π\*σ) isn't powered?

# Answer
> 0 votes
The vector $c\_t$ has exactly one coordinate which is 1, and the rest are 0s. You can check that if, for example, $c\_{t,k}=1$, when you substitute $c\_{t,k}=1$ and $c\_{t,\ell}=0$ for all $\ell \neq k$ in (26) you get (22). The same happens for (24) and (25).

---
Tags: artificial-intelligence, probability-theory, probabilistic-algorithms
---


title: Leibniz formula for π

text:
# Question
Title: Leibniz formula for π
So in my APCS class today we played around with generating pi, and approximating to a user defined number of places. We used the Leibniz formula for π. As we began playing around with it we tried throwing in 2147483647, the largest value for an int, but noticed it wasn't going to finish anytime soon. I googled runtime analysis a bit and am wondering how I would graph the complexity of the program. The function appears to be logarithmic, but I figure that as the complexity increases with each calculation, so would the complexity, but when i graphed it as a Riemann sum, it was a negative value with a slope of 0. Why would that be? I attached my code.

```
public class pi_calculator
{

public static void main(String [] args) {
Scanner scan = new Scanner (System.in);
int numberOfTerms = 0; {
numberOfTerms += scan.nextInt();
double startTime = System.nanoTime();
double piSum = 0;

if ( numberOfTerms > 0 && numberOfTerms <= 2147483647 ) {
   for( int i = 0; i <= numberOfTerms; i++ ){
        piSum += 4.0 * (Math.pow(-1, i)/(2*i+1));
   }
   double endTime = System.nanoTime();
   double duration = (endTime - startTime)/1000000;
   System.out.print( "Your pi estimate: " + piSum +"\n in: " + duration + "ms" );
}
else {

 System.out.print("ERROR");
}

}
}}

```

# Answer
This should really go in codereview.stackexchange.

In many languages, increasing the maximum possible int value either invokes undefined behaviour or produces the minimum possible value or both. If numberOfTerms == 2147483647 your code is most likely to *never* finish.

The execution time will be awful because you call a very expensive function Math.pow just to get a sequence that alternates between +1 and -1. Don't translate formulas literally, use your brain first. If numberOfTerms == 2147483646 then your code is quite likely not to finish before you give up.

The Leibniz formula is just awful to calculate π. To find n significant digits, you need to add $O (10^n)$ terms. Your function will *never* be as precise as the 3.141592653589 that I can quote from memory.

You have significant numerical problems because you will have rounding errors that are adding up badly, so I doubt you will get more than 8 digits correct ever.
> 2 votes

---
Tags: complexity-theory, runtime-analysis
---


# Question
Title: Infix vs postfix vs prefix - which has the smallest processing time
Infix, prefix (polish notation) and postfix (reverse polish notation) are all forms of arithmetic operations. As I understand it, infix is what we use in maths where the rules of BODMAS (Bracket, Order, Division and Multiplication, Addition and Subtraction) are used to decide what order the operations are used in. I can understand this being more computationally expensive to calculate than pre/post fix as the processor would have to reorder the equation so that it follows BODMAS. However, I do not understand why there is both prefix and postfix as they just change the order of tree traversal, so logically would take the same amount of processing time as each other. Is there any reason for choosing one over the other, and is my belief of infix being slower than post/prefix correct?

# Answer
> 1 votes
You can express the same in prefix and postfix without brackets.

For example, **a + b * c** can be ambiguous so it can give 2 different results so you need some precedence to solve the expression(as you have mentioned BODMAS) but both the trees if traveled in prefix or postfix leads to a unique results like **(a + b) * c** will have postfix **ab+c\*** and **a + (b * c)** will have **abc\*+**.

---
Tags: trees, arithmetic
---


# Question
Title: Can an instruction with a dependency read the register in same cycle as it's being written?
I'm learning about superscalar processors and struggling with it a bit. I wrote an assembly program and now must move it through in-order in-issue completion and I have a question about instructions as they move through the latter stages of the pipeline.

I have two instructions I1 and I2. I1 performs an operation on R1 and R2 and then loads the result in to R1. I2 needs read the new result of R1 and then overwrite R1, but obviously cannot do so until R1 is finished, otherwise I1 will be incorrect. At what point will I2 be able to correctly read the new result of R1? While I1 is in the WB stage or once I1 has finished the WB stage?

Thanks! I also realize this may not be an ideal design, but it's what I have to work with. Also, if this is not CS related and belongs in a different stack exchange, please move.

# Answer
With modern processors, arithmetic units tend to be able to deliver results simultaneously to a register, and to another arithmetic unit that requires that result.

There is a limit to this, so if you have three add instructions "x = a + b, y = x + x, z = x + x", then the a+b operation is unlikely to be able to send the result to a register, and to four inputs of two more additions. Even reading from a register is likely limited, so in this extreme example you could have (assuming an adder can forward to one input and a register, and registers can be read by two inputs):

```
Cycle 0: Adds a+b, sends result to x and first input of y = x + x.
Cycle 1: y = x + x reads second input from x; z = x + x reads first input from x
Cycle 2: Adds x + x, sends result to y. z = x + x reads second input
Cycle 3: Adds x + x, sends result to z.

```

On the other hand, take x = a + b, y = x + a, z = x + b:

```
Cycle 0: Adds a + b, sends result to x and first input of y = x + a
         y = x + a reads a, z = x + b reads b.
Cycle 1: Adds x + a, sends result to y. z = x + b reads x.
Cycle 2: Adds x + b, sends to z.

```

So an instruction cannot read a register at the time it is written to, but often results can be forwarded to an instruction at the same time they are written to a register.
> 2 votes

---
Tags: cpu-pipelines
---


# Question
Title: Hash table where items can fall into multiple buckets. What's the name of the data scrtucture?
I have a task to search through an array of items. I want to narrow the search down to some partitions. I thought of hash tables, but the difference in my case is that the "hash-function" is not unique; in my case, it rather should be called "partition-function".

Here's a fizz-buzz example:

* \[-1\]:1,2,4,7,8,11,13,14,16
* \[3\]:3,6,9,12,15
* \[5\]:5,10,15

You see, 15 fell into two buckets. It's ok with me. Since I'm going to look up "all who's divisible by 3" I'll get 15. Same for "all who's divisible by 5".

I see the following problems for the datastructure:

* Data is duplicated (more space, it's ok with me)
* Inserts/Updates/Deletions are more expensive

The question is:

* Is this approach to partitioning a good one?

# Answer
Whether it is a good approach or not entirely depends on the time/space requirements of your particular application. All data structures have trade-offs. Your primary alternatives for storing partitions of a multiset are:

* **Collection of containers/dictionaries**: you can store each subset in a different container or dictionary (such as an array or a hash table). This will allow fast unions and intersections between specific subsets, but slow membership queries. This is probably the data structure that you are trying to implement.
* **Generalized bit vector**: assuming that your universal set $U$ is not too big, you can define a two-dimensinal array. The $i$th element of this array will store the identifers of the subsets that contain $i$. Membership queries will be fast; however, unions/intersections take time proportional to $U$.
* **Dictionary with a subset attribute**: you can store each distinct element of the multiset in a dictionary (e.g., a hash table); then, associate an attribute to each element. This attribute will record the identifiers of the subsets that contain the element. Membership queries can be performed in the time it takes to search in the dictionary; however, union/intersection operations are again slow.
* **Union-find**: in this data structure, each subset is represented as a rooted tree that is made up of parent pointers. This idea is extremely useful since it enables membership queries and union of subsets in (nearly) constant time. It does not support, however, to split previously unioned subsets.

For more information about all of these choices, you can have a look at Section 12.5 of The Algorithm Design Manual \[1\].

\[1\] Steven S Skiena: The Algorithm Design Manual, Springer-Verlag London (2008).
> 2 votes

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


# Question
Title: Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (proofs, etc.)?
I'm a student, so I apologise if this is an idiotic question: Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (posing conjectures, proofs, etc.)? Why or why not?

I have heard arguments that computers will never be able to do mathematics close to the ability of humans, and these arguments are sometimes justified with reference to P vs NP (assuming that $P \not = NP$). It is said that, since these problems are NP rather than P (?), the solutions (proofs) could either be so lengthy as to not be understandable and/or verifiable by humans, or the solutions (proofs) would take so much time that the task practically becomes impossible. Are these statements true? Why or why not?

# Answer
> 5 votes
The fundamental restriction is human computer programmers' inability so far to create computers equipped with real intelligence. "Never" is a very long time, so it's hard to accept that something will "never" happen unless there is a very good argument.

Human brains and computers are not fundamentally different. The practical difference is that some human brains are programmed in a significantly better way for finding mathematical proofs, while computers have other advantages. With equally good programming, computers would probably have the advantage.

And remember that the majority of humans are also unable to do any mathematics better than current computers can.

PS: P vs. NP is a red herring. Computers are not able to generally solve NP complete problems above modest size because it is too computational intensive (but often many instances can be solved, just not all). But nor can humans. No mathematical proof that humans have found ever involved solving a hard instance of an NP-complete problem. On the other hand, there are many problems in P that are just as unsolvable.

PS. In general the problem "given a mathematical hypothesis, is there a proof for it" will be NP-hard (take any instance of an NP-complete problem, and declare that "answer is YES" is a mathematical hypothesis). The question "is there a proof for Fermat's Last Theorem" is obviously an easy instance of that problem :-) Since it took humans 357 years to prove, we can take bets if computers will manage quicker.

# Answer
> 4 votes
It depends what you mean by "doing mathematics". If you mean large scale computation, computers can easily do this, as can be seen from programs like Wolfram Alpha. Engines like these are obviously not perfect, but given the rate of development in machine intelligence, I don't think we have reason to believe this is a cause for limitation.

If by "doing mathematics" you mean applying deductive reasoning to given axioms, or formulating proofs, there are in fact computer generated proofs. It is even a big controversy whether the mathematical community should accept such proofs as valid, because they are often far to large for any human to check. Of course this is very new, and there is also much room for improvement. But again, no inherent limitations here.

One of the only limitations unrelated to human ability I can think of would be limitations inherent to mathematics, particularly Gödel's incompleteness theorems. Every set of axioms containing basic arithmetic is either inconsistent or incomplete. The Halting Problem is another great example that shows computers cannot do everything.

---
Tags: complexity-theory, time-complexity, p-vs-np, mathematical-programming, proof-assistants
---