# Question
Title: Algorithm to find all acyclic orientations of a graph
I am working on acyclic orientations of undirected graphs and have the following questions:

1. Given connected undirected simple graph $G$, how to find all possible acyclic orientations of $G$ ?
2. What is the number of acyclic orientations? It is known (from here) to be $(-1)^p\ \chi(G,-\lambda)$ for a graph $G$ with $p$ vertices where $\chi$ is the chromatic polynomial evaluated at $-\lambda$; but I wasn't successful in understanding how to evaluate $\chi$ at a negative value ($-\lambda$).

# Answer
As Yuval noted, you can count the number of acyclic orientations by evaluating the chromatic polynomial of a graph at negative unity. For computing chromatic polynomials, there are efficient algorithms known for some graph classes.

There is also a recursive algorithm for generating *all* acyclic orientations of a graph given by Squire \[1\]. The algorithm requires $O(n)$ time per acyclic orientation generated. Roughly 20 years ago this was the fastest algorithm known; it's possible a faster one is known now, or that you can improve Squire's algorithm by known techniques.

---

\[1\] Squire, M. B. (1998). Generating the acyclic orientations of a graph. Journal of Algorithms, 26(2), 275-290.
> 5 votes

---
Tags: algorithms, graphs, counting
---


# Question
Title: Inclusion of complexity classes (Deterministic Turing Machine)
I can't understand what my professor wrote about these inclusions concerning deterministic classes:

$$ DTIME(f) \subseteq DSPACE(f) \subseteq \sum\_{c\in\Bbb N}DTIME(2^{c(log+f)}) $$

I understood the first inclusion:

> The Turing Machine needs to do at least one step in order to check the next cell on tape

I didn't get the second one:

> The number of configurations of the Turing Machine with fixed space is finite, and the computation must stop within a maximum number of steps equal to these settings, otherwise wewould have a cycle.

I don't understand the argument of the summation: why that $2$ and that $c(log+f)$? Why is it written like that?

# Answer
Expanding on the comments, the idea is that if a Turing machine has $M$ possible configurations then if it halts, it must do so within $M$ steps. The reason is that once the machine has stepped through $M+1$ different configurations, it must have stepped on the same configuration $C$ twice. Since the machine is deterministic, each time it reaches configuration $C$, it will work its way in the same manner and reach $C$ again, and again, and again, indefinitely.

How many different configurations are there? Suppose the tape alphabet is $\Sigma$ (include the blank symbol), the space is $S$ (assume for simplicity that the tape is one-way infinite so there is a unique chunk of space $S$), and there are $N$ states. Then the number of configurations is $NS|\Sigma|^S$, since a configuration is given by the state, the position of the head, and the contents of the tape. We can write this bound as $$ NS|\Sigma|^S = 2^{\log N + \log S + (\log |\Sigma|) S} \leq 2^{c(1+\log S + S)} $$ for $c = \max(\log N, \log |\Sigma|)$. Assuming $S \geq 2$, we can further simplify this to $2^{c(1+\log S+S)} \leq 2^{c'(\log S+S)}$ for $c' = 2c$.
> 5 votes

---
Tags: turing-machines, time-complexity, space-complexity, complexity-classes
---


title: Reducing from 3-COLOR to 3-CNF SAT?

text:
# Question
Title: Reducing from 3-COLOR to 3-CNF SAT?
I get how to reduce 3-SAT to 3-COLOR, but I'm not sure how to do it the other way around. Does anyone have any hints or insight?

# Answer
Hint: For each vertex $v$ and color $c$, have a variable $x\_{v,c}$ which means "vertex $v$ gets color $c$". Now construct a 3SAT instance that states:

1. Each vertex gets some color.
2. Neighboring vertices get different colors.
> 1 votes

---
Tags: graphs
---


title: Operator overloading: Java vs. Python

text:
# Question
Title: Operator overloading: Java vs. Python
Why operator overloading was included in Python and not in Java? How does one decide to include or exclude operator overloading in a programming language?

It is said here that operator overloading is excluded from Java to make the language simpler (for programmers, language and VM developers, etc.).

I don't understand why the same explanation doesn't work for excluding it in Python?

# Answer
Operator overloading is an example of *syntactic sugar* — a notation that doesn't give any extra power but makes programming easier. I don't know the rationale for the decisions in Java and in Python, but see below. See also this answer on stackoverflow.

First, I would like to critique the page you were linking. Let's consider the points raised there one by one.

1. Simplicity and cleanliness: It is claimed that operator overloading slows down the compiler and the JVM (!). This is non-sense. It's plain wrong for the JVM, since this is just syntactic sugar so it wouldn't affect the generated code *at all*. As for the compiler, the compiler is already equipped to parse infix operators and to resolve virtual methods, so supporting operator overloading won't make it more complex. On the flip side, operator overloading makes the *Java code* simpler and cleaner: compare `a.add(b)` to `a+b`.
2. Avoid programming errors: It is claimed that non-standard semantics for operators might confuse programmers. Compare this to C++'s use of `>>` and `<<` in streams. I think this point is valid but overstated. The same point could be made with regard to other conventions. It's up to the programmers to not abuse the capabilities of the language.
3. JVM complexity: It is claimed that operator overloading complicates the JVM. As stated above, at the JVM level there would be absolutely no difference.
4. Easy development of tools: It is claimed that operator overloading complicated the design of IDEs. The answer here is very similar to the answer to the first point. The only complication with operator overloading is that you have to figure out the type of the operands, but presumably if it makes any difference you would need to do it anyway since there are also several different *number* types, say integer and floating point.

A point which is not raised is that operator overloading might complicate optimization since certain algebraic identities hold for numbers but not in general. This criticism is wrong for the following reason: algebraic identities cannot in general be used even for *floating-point* computations, since order of operations makes a difference. So the compiler needs to determine the type of the operands anyway, and could easily abstain from optimizing user defined operators.

The Python philosophy is to supply the coders with the rope to hang themselves. If you're a good coder, you will use the rope for good, say for tying your bicycle in the train, rather than to hang yourself or anybody else. Python trusts programmers more than Java, *by design*. See the second point above.

Let me end this answer by quoting an excellent answer to the stackoverflow question mentioned above:

> I left out operator overloading as a fairly personal choice because I had seen too many people abuse it in C++.

James Gosling. Source: http://www.gotw.ca/publications/c\_family\_interview.htm

> Many C++ design decisions have their roots in my dislike for forcing people to do things in some particular way \[...\] Often, I was tempted to outlaw a feature I personally disliked, I refrained from doing so because I did not think I had the right to force my views on others.

Bjarne Stroustrup. Source: The Desing and Evolution of C++ (1.3 General Background)
> 10 votes

---
Tags: programming-languages, api-design
---


# Question
Title: Just another Divide-And-Conquer question - but somehow different
Please consider the following Divide-And-Conquer Problem:

> You’re consulting for a small computation-intensive investment company, and they have the following type of problem that they want to solve over and over. A typical instance of the problem is the following. They’re doing a simulation in which they look at n consecutive days of a given stock, at some point in the past. Let’s number the days i=1,2,...,n; for each day i, they have a price p(i) per share for the stock on that day. (We’ll assume for simplicity that the price was fixed during each day.) Suppose during this time period, they wanted to buy 1,000 shares on some day and sell all these shares on some (later) day. They want to know: When should they have bought and when should they have sold in order to have made as much money as possible? (If there was no way to make money during the n days, you should report this instead.)

There already is a discussion about the same problem, but I don't understand why they try to make it that complicated. I think the following Algorithm will yield the result they ask for:

```
DivideAndConquer(1,..,n)
(i1,j1) := DivideAndConquer(1,..,n/2)
(i2,j2) := DivideAndConquer(n/2 + 1,..,n)
return (min(p(i1),pi2),max(p(j1),p(j2)))

```

Even if they ask for the range, we can get it from `(i,j) := DivideAndConquer(1,..,n)` by `j-i`. So, what am I missing?

PS: I don't see the point of using a DivideAndConquer approch at all. Why not sorting the input twice. Once in ascending and once in descending order induced by `p(i)`.

EDIT: According to the explanation of Yuval Filmus, the algorithm should look like the following:

```
DivideAndConquer(1,..,n)
(i1,j1) := DivideAndConquer(1,..,n/2)
(i2,j2) := DivideAndConquer(n/2 + 1,..,n)
Let p(i) be minimal in 1,..,n/2
Let p(j) be maximal in n/2 + 1,..,n
return (i,j)

```

# Answer
Your solution doesn't work since it could output $i\_2,j\_1$ which isn't legal since $i\_2 \> j\_1$. Your code also has a few bugs — are you returning indices or stock prices?

The idea behind the divide and conquer solution is that the optimal solution is of one of three forms:

1. Buy and sell within the first half.
2. Buy and sell within the second half.
3. Buy within the first half and sell within the second half.

The first two are taken care of by the recursion, and for the third you just need to compute the minimum of the first half and the maximum of the second half.

There is also a simple (and faster) solution not involving any kind of recursion or sorting. The idea is to scan the array from left to right, keeping at any given point the smallest value seen so far. At any given point in time, you can consider the gain from buying at the smallest price seen so far and selling at the current price. The maximum over all these possibilities is the optimal strategy. This algorithm takes linear time, and can even be implemented online.
> 4 votes

---
Tags: algorithms, algorithm-analysis, divide-and-conquer
---


# Question
Title: How to iterate over vectors in order of probability
Consider a random $n$ dimensional vector $v$ where $v\_i \in \\{0,1\\}$. For each $i$ we know $p\_i = P(v\_i = 1)$ and let us assume the $v\_i$ are independent. Using these probabilities, is there an efficient way to iterate over all possible binary $n$ dimensional vectors in order from most likely to least likely (with arbitrary choices for ties)?

Take for example $p = \\{0.8, 0.3, 0.6\\}$. The most likely vector is $(1,0,1)$ and the least likely is $\\{0,1,0\\}$.

For small $n$ we could label each vector with its probability and sort although this isn't very efficient. However, consider $n=100$ for example. This is no longer an option.

# Answer
You can solve this with a priority queue.

Let $L(x)$ be the log-probability of the vector $x$, i.e.,

$$L(x) = \log \prod\_i p\_i^{x\_i} (1-p\_i)^{1-x\_i} = \sum\_i \ell\_i(x\_i)$$

where

$$\ell\_i(b) = \log (p\_i^b (1-p\_i)^{1-b}).$$

Since the log is monotone, your problem is equivalent to looking for a way to enumerate the vectors $x \in \\{0,1\\}^n$ in order of decreasing $L(\cdot)$ value.

Of course, it is easy to identify the vector which has highest probability, i.e., highest $L(\cdot)$-value. We simply put a $1$ in the $i$-th position if $p\_i\ge 1/2$ and a $0$ otherwise; call the result $x\_{\text{best}}$. So create a priority queue that will hold a set of $n$-vectors. Initialize it to a single element, $x\_{\text{best}}$. Assign it the priority $L(x\_{\text{best}})$. In general, if $x$ is in the priority queue, its priority will be $L(x)$. Also, create a set $S$ of nodes that have been previously output; initially we will have $S = \emptyset$.

Now repeat the following loop:

* Find the value of maximum priority and remove it from the priority queue. Call it $x$.
* Output $x$. Add $x$ to $S$.
* For each $i=1,2,\dots,n$: Let $y$ denote the vector obtained by flipping the $i$th bit of $x$; if $y \notin S$, add $y$ to the priority queue, with priority $L(y)$.

This loop will output the elements of $\\{0,1\\}^n$ in order of decreasing $L(\cdot)$-value.

Why does this work? Basically, if $x$ has the highest $L(\cdot)$-value, then the next-highest must be obtained by flipping a single bit; flipping two bits will give you something strictly worse. The same kind of justification can be applied inductively. Or, to think about it another way, this is basically Dijkstra's algorithm applied to the $n$-dimensional cube (vertices are $\\{0,1\\}^n$), and Dijkstra's algorithm is an efficient way to enumerate the nodes of a graph in order of decreasing distance. Since $L(\cdot)$ is additive, it can be understood as a distance from $x\_{\text{best}}$.
> 6 votes

# Answer
To address the issue of asymptotic behavior a bit (in an answer, since this is too long for a comment): in $n$ dimensions, the priority-queue algorithm that's been mentioned essentially marches an '$(n-1)$-plane' through the $n$-cube, so the worst-case behavior is exponential in the dimension — but then, so is the number of vectors being iterated over. Finer-grained analysis requires understanding of the number of edges of a hypercube that can be 'cut' by such an $n-1$-plane (and more to the point, the number of vertices they can connect to on the other side); I'm pretty certain this is maximized when the plane is orthogonal to the long diagonal of the hypercube, but proving that is a little tricky. The asymptotic worst-case should be roughly ${n\choose\lceil n/2\rceil}\approx\frac1{\sqrt{\pi n/2}}2^n$ (for instance, when all the weights are equal then this is the number of elements of weight $\lceil n/2\rceil$), so that the priority queue will have to be of size roughly $\frac1{\sqrt{\pi n/2}}$ times the total number of elements iterated over — for instance, when $n=20$ it'll grow to roughly $18\\%$ of the $2^{20}$ total elements. In particular, note that since the maximum heap size is asymptotically very close to the total size of the data being worked on, the total running time of the priority-queue algorithm is essentially the same, asymptotically, as just sorting all the weights upfront: for $n$-dimensional data, it's of time $2^n\cdot\lg(Cn^{-1/2}2^n)$ $\approx 2^n\cdot(n-\frac12\lg n+\lg C)$ $\in\Theta(2^n\cdot n)$, which is the asymptotic complexity of the sort-based approach. (In practice, of course, the queue is noticably better than sorting.)

My strong suspicion is that you're going to need time $\Theta(v\log v)$ (or maybe even $\Theta(nv)$) to iterate over the first $v$ values; the real question (to my mind at least) is whether you can do it in space $\ll\Theta(v)$. To that end, you might look at variants of the *Bresenham* line-drawing-algorithm; it solves a similar problem (finding the next pixel in a line) by keeping track of $n$ 'discrepancies', one for each of the $n$ axes, and updates those on each step of the line. I don't know of any It's possible you could find a way to hold only a small discrepancy vector, use that to determine the next point(s), and then update it suitably; digging into the details of the Bresenham algorithm (and again, variants and extensions of it) is the best place I can think of to find more information on that potentially-fruitful approach. (But again, since in the worst case you can have $\Theta(2^n/\sqrt{n})$ points with the *same* weight, any general algorithm that uses less space is going to have to be smart enough to figure out a good way of iterating over those without having to store all of them.)
> 1 votes

---
Tags: algorithms, enumeration
---


title: Hardness of approximating hitting set

text:
# Question
Title: Hardness of approximating hitting set
Consider the hitting set problem with $n$ elements and $m$ sets. I gather from the linked page as well as this that

1) it is NP-hard to approximate the cost of the optimal solution to a multiplicative factor of $c \log n$ for some $c\>0$.

2) it is NP-hard to approximate the cost of the optimal solution to a multiplicative factor of $c \log m$ for some $c\>0$.

3) it is NP-hard to approximate the cost of the optimal solution to a multiplicative factor of $c \log \max(n,m)$ for some $c\>0$.

Is my understanding correct? This seems to be a straightforward consequence of what is on the internet, but some of the notation in these sources is mysterious to me and I want to make sure I'm not misunderstanding.

# Answer
> 2 votes
For every choice of $\alpha \> 0$, Moshkovitz shows that approximating set cover on instances with $n^{C\_\alpha}$, where $C\_\alpha$ is some constant depending only on $\alpha$, better than $(1-\alpha) \log n$ is NP-hard. Since $\log m \leq C\_\alpha \log n$, it is NP-hard to approximate set cover better than $\frac{1-\alpha}{C\_\alpha} \log m$. I'm not sure what is $\sup\_{\alpha\to 1} \frac{1-\alpha}{C\_\alpha}$, but it can probably be gleaned from the paper. At any rate, all three results you mention are correct, and the first can be strengthened by replacing $c$ with $1-\alpha$ for any $\alpha \> 0$.

---
Tags: np-hard, approximation
---


# Question
Title: How does mathematical software evaluate symbolic sums?
Wolfram alpha is able to compute this sum: $$ \sum\_{j=1}^n \binom{j}{2} = \frac{1}{6}(n-1)n(n+1). $$

How can Wolfram alpha do it? What kind of algorithm does it use?

# Answer
It uses algorithms discussed in the book A=B by Petkovšek, Wilf and Zeilberger. These algorithms can compute a closed-form expression for a summation of rational functions (in your case, the rational function is $j(j-1)/2$), or determine that no such closed-form expression exists.
> 2 votes

---
Tags: computer-algebra
---


title: Inserting a sentence into search trees

text:
# Question
Title: Inserting a sentence into search trees
Let's say you have the following sentence: "This is my first cs question posted here". How would I go about inserting the sentence into a search tree. Do I assign each word a number value and perform the insertions based on those?

# Answer
Search trees of various sorts can work with an *arbitrary* ordered domain, as all they rely on is a comparison function which is assumed to satisfies the axioms of a complete order:

1. If $a \< b$ and $b \< c$ then $a \< c$.
2. Exactly one of $a \< b$, $a = b$, $a \> b$ (shorthand for $b \< a$) holds.

In your case, you're probably meant to use the *lexicographic* order on strings. In this order, $x \< y$ if:

1. Either $x$ and $y$ first differ in the $i$th symbol, and $x\_i \< y\_i$;
2. Or $x$ is a prefix of $y$.

Symbols are probably compared in ASCII order in your case.
> 1 votes

---
Tags: data-structures, strings, search-trees
---


title: Turing machine with repeated strings

text:
# Question
Title: Turing machine with repeated strings
How would I go about making a Turing machine to accept the following language L?

$$L = \\{ www \mid w = \\{0,1\\}^\* \text{ and } w \> 0\\}$$

I was thinking counting the number of symbols in the input string and then dividing by three to find the beginning of each instance of *w* and then testing if each instance is the same, but this seems a bit roundabout.

I feel like there is a way by marking the first three symbols and then moving the 2nd and 3rd markers until the strings in between them are the same but I'm having a hard time articulating this into an algorithm.

Can anyone point me in the right direction?

# Answer
From the comment: a quick way is to think that you are working on a two-tapes TM (initially the second tape is empty). You start placing $abc$ on it; then continue scanning it expanding the $a$, $b$ and $c$ substrings ($aabbcc,aaabbbccc,aaaabbbbcccc,...$) until the length of the second string matches the length of the input (or reject if you "overflow" it). During a scan simply replace the first $b$ with 1 $a$, the first 2 $c$s with 2 $b$s and append 3 $c$s at the end.

```
   Input: 011010110101101
2nd tape: <empty>
  Scan 1: abc
  Scan 2: aabbcc
  Scan 3: aaabbbccc
  Scan 4: aaaabbbbcccc
  Scan 5: aaaaabbbbbccccc

```

At this point it should be easy to check if the three subwords are equal ... finally think how to "merge" the second tape into a single one (just add extra symbols to the tape alphabet ...).
> 1 votes

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


title: Amdahl law and parallelism

text:
# Question
Title: Amdahl law and parallelism
I know after some reading Amdahl law is a embarrassingly parallel programming model. Embarrassingly parallel means there is no communication and tasks work independently. Am I to assume a parallel and a non parallel aspect of the program is embarrassingly parallel? If not, what makes it embarrassingly parallel?

# Answer
Your terminology is incorrect. Amdahl's law is a way of estimating performance of a parallel program. It is not a "programming model". Amdahl's law says that if there is a computation, part of which is $M$ sequential (not parallelizable) instructions and part of which is $N$ instructions which could be parallelized, and you have $P$ processors, then the shortest computation time you can hope for is: $$ M + \frac{N}{P}. $$

So the speedup with $P$ processors is: $$ \frac{M+N}{M+\frac{N}{P}}. $$

Which, in the limit as $P \gg N$ goes to $$ \frac{M+N}{M} = 1 + \frac{N}{M}. $$

The takeaway message is simply that you shouldn't fool yourself. $N/M$ is much more important than $N/P$.
> 4 votes

---
Tags: terminology, parallel-computing
---


# Question
Title: regular expression: sum of positive fixed point decimal numbers
I need help with this exercise.

Indicate the regular expression for the following Languages. Explain your expression in one sentence and indicate the basis form of the alphabet. Indicate also every assumption you make.

i) Sums of positive fixed-point decimal numbers. The following Strings should exist in the Language:

e.g: 3.14 or also 3 + 4.2 + 7 + 1

I have a couple more exersices that are pretty similar but I guess if I get to understand this exercise I could try to do the others faster.

I appreciate the help in advance.

# Answer
The idea is to identify the different kind of subexpression you have, and the regular expression should write itself.

Here you have a non-empty sum of decimal numbers, so the "outside shape" is $E=N(+N)^\*$, where N is an expression for decimal numbers, and "+" is the symbol for addition. Now we just have to detail N: it is a non-empty sequence of digits, with possibly one dot, which does not start with $0$ and does not end with $0$ if there is a dot. For short let write D=0+1+2+...+9 the expression for 1 digit. here the "+" is the one from regular expression, meaning Union, not the addition symbol. Also, the first digit should not be 0, and if there is a point, the last one should not be 0. So let's P=1+2+...+9 the expression for nonzero digits

We are now ready to write N: N=PD\*+PD\*.D\*P+0.D\*P It means that either we don't have a dot, and then we can end with 0, or we have a dot, and then we cannot ened with 0. There is also a special case for numbers like $0.345$.

By substituting the letters with their explicit expressions, you get the full explicit one for E.
> 1 votes

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


title: Bloom filter variant

text:
# Question
Title: Bloom filter variant
I've been playing around with a simple probabilistic data structure which is very similar to a Bloom filter. Where a Bloom filter would use $k$ independent hash functions to choose $k$ of the $m$ bits to set, this structure uses $m$ hash functions, and sets each bit with probability $p$.

This structure doesn't produce as low a false-positive rate as Bloom filters, but it seems to be extremely fast to compute, particularly if $m$ is some multiple of the machine word size and $p = 2^{-b}$ for some integer $b$: The hash functions can be computed in parallel by AND-ing $b$ independent $m$-bit hashes, and no dependent indexing or variable bitshifts are required.

I'm certain someone's come up with this idea before me, and done a lot more advanced analysis and comparison of it than I'm qualified to do. Is there a particular name for this type of structure?

# Answer
> 3 votes
Let's analyze how many hash bits you need in your new scheme versus a Bloom filter.

First of all, we need to agree about terminology. I will use $q$ to represent the probability of a false positive.

For a Bloom filter the design problem of choosing $m$ and $k$ given that you want to hold $n$ elements with false positive rate $q$ is solved by $k = -\lg\_2 q$ as the number of hashes, and $m=\frac{n k}{\ln 2}$ bits for the table. (See the wikipedia page or several of the previous cs.se questions about Bloom filters.) (This works out to a table with maximum entropy: your table is about half 1s and half 0s after $n$ insertions.) The number of hash bits you need to produce per insertion is $k \lg\_2 m$

Now your structure: Let's assume that the desired $n$ and $q$ are the same. $k$ and $m$ are going to be about the same, but now $k$ is going to be the average number of bits that remain set after `AND`ing your $b$ independent $m$-bit hashes. How big does $b$ need to be? Well you want the probability of any particular bit in your final hash to be about $k/m = p = 2^{-b}$. So $b = -\lg\_2 k/m = \lg\_2 m - \lg\_2 k$. But that means that you have to generate $b m = m(\lg\_2m-\lg\_2k)$ hash bits, which is way more than $k \lg\_2 m$. For example, if $n = 709$ and $q = 1/16$ then $k = 4$ and $m = 4096$. So a bloom filter would require $4 \times 12 = 48$ bits of hash, while your scheme requires $b = 10$ and a total of $40960$ bits of hashing.

Worse, there are some elements whose hash works out to 0 (i.e., whenever you look them up the probability of getting a false positive is 100%). Suppose I `AND` together 10 different bit vectors of length $m$. The probability that each bit will be set to 1 is 1/1024. The probability that *all* the bits will be set to 0 is $(\frac{1023}{1024})^{4096}\approx e^{-k} \approx 0.0183$.

---
Tags: reference-request, data-structures, probabilistic-algorithms, bloom-filters, dictionaries
---


# Question
Title: Given a complete, weighted and undirected graph $G$, complexity of finding a path with a specific cost
Given a fully connected graph $G$, suppose that we are searching for a simple path $P$ with a specific cost $c$.

Is answering to that problem *yes* or *no* equivalent to subset-sum problem? What would be the complexity of finding such path?

I have made a reduction from subset-sum problem:

If each number in a set $S$ is a vertex of $G$ and weight of $\<i,j\>$ is $|i-j|$, then answering the question above *yes* or *no* is the same as solving the sumbet-sum problem.

P.S. The initial vertex I have visited is added to the cost.

**Edit: Edge weights**

# Answer
Given an instance $\langle \\{s\_1,\ldots,s\_n\\}, T \rangle$ of subset sum, construct the following weighted graph. The vertices are $$ v\_0,v\_1,\ldots,v\_n,u\_1,\ldots,u\_n. $$ Connect $v\_{i-1}$ and $v\_i$ with an edge of weight $s\_i$. Connect $v\_{i-1}$ to $v\_i$ via $u\_i$ (i.e., add the edges $\\{v\_{i-1},u\_i\\},\\{u\_i,v\_i\\}$) with zero weight edges. There is a simple path of total cost $T$ iff there is a subset of $\\{s\_1,\ldots,s\_n\\}$ summing to $T$. This shows that your problem is NP-hard, and in fact NP-complete, since it's clearly in NP.
> 5 votes

---
Tags: algorithms, graphs, decision-problem
---


# Question
Title: Minimum weighted arithmetic mean partion?
Assume I have some positive numbers $a\_1,\ldots,a\_n$ and a number $k \in \mathbb{N}$.

I want to partition these numbers into exactly $k$ sets $A\_1,\ldots,A\_k$ such that the weighted arithmetic mean

$$\text{cost}(A\_i,\ldots,A\_k)=\sum\_{i=1}^{k}\frac{|A\_i|}{n}c(A\_i)$$

is minimal, where $c(A\_i)=\sum\_{a \in A\_i}a$ is simply the sum of all numbers in $A\_i$.

Is there actually a (polynomial) algorithm to do this or is this a (**NP**) hard problem?

I tried to reduce it to some NP-hard problems but didn't get anywhere, especially because the numbers are nonnegative and thus in an optimal partition big sets need to have smaller weight which seems to be some kind of balancing problem instead of a packing problem (which I am more familiar with).

# Answer
Suppose first that we fix the sizes of the sets $|A\_i| = n\_i$ in non-decreasing order $n\_1 \leq \cdots \leq n\_k$. In that case, if we arrange the numbers $a\_i$ in non-decreasing order, then an optimal choice is $$ A\_1 = \\{a\_n,\ldots,a\_{n-n\_1+1}\\}, A\_2 = \\{a\_{n-n\_1},\ldots,a\_{n-n\_1-n\_2+1}\\}, \ldots, A\_k = \\{a\_{n\_k},\ldots,a\_1\\}. $$ The reason is that given any solution where $a\_i \in A\_I$ and $a\_j \in A\_J$, switching $a\_i$ and $a\_j$ will result in a total change of $$ -n\_Ia\_i-n\_Ja\_j + n\_Ja\_i+n\_Ia\_j = (n\_I-n\_J) (a\_j-a\_i),$$ so the switch is beneficial (or harmless) as long as $n\_I \leq n\_J$ and $a\_j \geq a\_i$.

In view of this, there is always an optimal solution in which $A\_1,\ldots,A\_k$ is a partition of $a\_1,\ldots,a\_n$ into intervals. This suggests a dynamic programming algorithm. For each $\ell \leq k$ and $t \leq m \leq n$, we compute $$ \min\_{A\_1,\dots,A\_{\ell-1} \vdash a\_1,\ldots,a\_t} \sum\_{i=1}^\ell |A\_i| c(A\_i), \quad \text{where $A\_\ell = \\{a\_{t+1},\ldots,a\_m\\}$}. $$ Here $A\_1,\dots,A\_{\ell-1} \vdash a\_1,\ldots,a\_t$ means that the left-hand side is a partition of the right-hand side into intervals. I am assuming that sets could be empty; the algorithm can be modified to ensure that sets are not empty (just make sure $\ell \leq t \< m$).
> 4 votes

---
Tags: optimization, np-hard, np, partitions
---


# Question
Title: Robot follows a path near an obstacle without colliding
I have a problem that I would like to solve it. A robot have to move near an obstacle (e.g a wall) without colliding. He should also try to be always near the obstacle. The following picture can help you to understand what I need to do:

1. In red is the wall
2. Black dots is the robot moving
3. The dashed line is the path of the robot

The robot doesn’t have any information about the wall. He has only a sensor that can tell him approximately what the distance to the wall is. A perfect robot is a robot who can move within a distance of 1m to the wall. The robot some times doesn’t respect that distance:

1. The distance can be sometimes \> 1m
2. The distance can be less often \< 1m
3. The robot can collide but it should be very rare and it is better to avoid it all the time.

Do you have a solution for this problem? I am new to AI and there is a lot of material to read. So on which topic of AI should I concentrate to find a solution for this problem?

# Answer
> 1 votes
Robot Motion Planning is an important topic in Computational Geometry. There have been a lot of research in this field.

Here are some pointers that might help you:

Slide: http://www.mpi-inf.mpg.de/departments/d1/teaching/ss10/Seminar\_CGGC/Slides/06\_Bazhenova\_RMP.pdf

Slide: http://www.cs.cmu.edu/afs/cs/academic/class/15381-s07/www/slides/020807motion.pdf

Book: http://books.google.com/books?hl=en&lr=&id=\_VRM\_sczrKgC&oi=fnd&pg=PR11&dq=robot+motion+planning&ots=zFkR07oxBJ&sig=efsVfaDPAlhKgxZwClKS136moCI#v=onepage&q=robot%20motion%20planning&f=false

Website: http://correll.cs.colorado.edu/?p=965

---
Tags: artificial-intelligence
---


title: Tree data structure for fast merges

text:
# Question
Title: Tree data structure for fast merges
I need trees that have the following properties:

1. Each node in the tree has two values associated with it - a key and an associated opaque data element.
2. An internal node in the tree has unbounded number of children. The tree reflects a real world hierarchy that is in flux over time - hence the maximum number of children of a given node are not known ahead of time.
3. There is an ordering defined on sibling nodes that is a function of the keys stored in the nodes.

Allow the following operations to be $O(\lg n)$.

## Update operations

* `merge(tree_1, tree_2)` \- Destructively consumes `tree_1` and `tree_2` to create a new tree which contains keys from both input trees. I realize now that this operation is underdefined, I will put more thought into the semantics of the merge.
* `insert(tree, parent_key, child_key, value)` \- inserts the given key-value pair into the given subtree rooted at the node pointed to by the parent key.
* `delete(tree, key)` \- Delete subtree rooted at node with given key.
* `update(tree, key, value)` \- Destructively updates the existing data associated with the given key-value pair.

## Query operations

* `find(tree, key)` \- returns the value associated with the given key in the given tree.
* `get_tree(tree, key)` \- Return a subtree that is rooted at node with given key. The returned tree must a reference and share identity with corresponding nodes in the incoming tree. Modifying any nodes via the returned tree will hence result in changes to the initial tree.
* `children(tree, key)` \- Returns sequence of (key, data) of child nodes of node corresponding to key.

Things I looked at before I asked this question - Binary trees, AVL trees, Red Black trees, 2-3 trees and they were not suitable because of fixed degree of internal nodes.

# Answer
> 3 votes
If you have a guarantee that any given key will be present in at most one tree, you can implement these operations using the Union-Find data structure for disjoint sets. Basically, you use the disjoint sets data structure to keep track of which keys are present in the same "tree". Then, you have a separate hash table on the side to map keys to values. With these two data structures, each of your operations can be implemented in $O(\alpha(n))$ time, where $\alpha(n)$ is the inverse Ackerman function. In fact, you can treat each operation as running in essentially constant time.

Some examples of how to implement your algorithms:

* merge(tree\_1, tree\_2): Invoke Union(tree\_1, tree\_2).
* insert(tree, key, value): Check that key is not already present, by looking it up in the hashtable. If it is already present, bail out (abort). Otherwise, create a new singleton disjoint set containing just the value key. Merge that new set with tree\_1, using a Union() operation. Insert (key, value) into the hashtable.
* update(tree, key, value): Check that key is in this tree, by calling Find(key); if it's not, bail. Then, update the mapping for key in the hashtable.
* find(tree, key): Check that key is in this tree, by calling Find(key); if it's not, bail. Then, get the mapping for key from the hashtable.
* get\_tree(tree, key): Check that key is in this tree, by calling Find(key); if it's not, bail. Then, return key.
* children(tree, key): Return the single-entry list \[(key, value)\] (pretend key is a leaf).

With this implementation, the merge operation has the side effect of destroying the old trees (so you are not allowed to retain handles to the old trees). If you wanted a persistent data structure, you can look at persistent disjoint-set data structures.

However, this answer has two serious limitations: first, it does not allow you to specify or control the parent-child relationship; second, it requires that the key sets of the trees be disjoint (no key appear in more than one tree). It sounds like these limitations make this answer unusable in your context, but I'm not certain yet (perhaps a future revision of the question will make this clearer).

# Answer
> 2 votes
Refer to literature of AVL tree, which is a balanced binary tree. Using AVL tree all of the operations you mentioned can be performed in O(log n) time, where n is the sum of the number of nodes in tree\_1 and tree\_2 for (a), and number of nodes of the tree for (b) and (c), and as far as I know this time bound is the tightest one among the tree data-structures.

---
Tags: data-structures, trees, dictionaries
---


# Question
Title: Constructing an unrestricted grammar for a^n b^m c^n d^m
I've been trying to construct an unrestricted grammar which has the language:

`L = {a^n b^m c^n d^m | n>0, m>0}`

But I can't seem to figure it out without making the derivations run an unreasonably long amount of time. Can anyone help me devise an elegant way to create this grammar?

Edit: In order to clarify, I was trying to find an Unrestricted Grammar that would run in `O(n^2)` time or better. As it stood, all of my solutions were exponential, which made parsing very long strings prohibitively costly.

# Answer
> 3 votes
How about the following: $$ \begin{align\*} &S \to XY \\ &X \to aXC | aC \\ &Y \to BYd | Bd \\ &CB \to BC \\ &aB \to ab \\ &bB \to bb \\ &Cd \to cd \\ &Cc \to cc \\ \end{align\*} $$ In this grammar you need to apply $O(nm)$ rules to get $a^nb^mc^nd^m$.

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


# Question
Title: Where/when did Stephen Kleene first define the Kleene closure/star?
I'm working on a paper and would like to review the origins of Kleene's closure. I am unable to find any article of Kleene's that has the original definition of the Kleene closure.

Is there a paper by Kleene in which he first defines the Kleene closure?

# Answer
Kleene's classic paper on finite automata and regular expressions is

> Kleene, Stephen C.: "Representation of Events in Nerve Nets and Finite Automata". In Shannon, Claude E.; McCarthy, John. *Automata Studies*, Princeton University Press. pp. 3–42., 1956.

There seems to be a scan or recreation of that version of the paper at: http://www.dlsi.ua.es/~mlf/nnafmc/papers/kleene56representation.pdf.

But, as pointed out by @HendrickJan, the work seems to have been done about 5 years earlier. The article starts with a note that says that "the material ... is drawn from Project RAND Research Memorandum RM-704 (15 Dec 1951, 101 pages) ... used by permission of the RAND Corporation ... supported by the RAND Corporation during the summer of 1951." A scan of the RAND research memorandum is available for free from the RAND website: http://www.rand.org/pubs/research\_memoranda/RM704.html.

"Regular events" are defined in Section 7 of both papers. (page 46 of the 1951 memorandum and page 23 of the 1956 paper). Interestingly, Kleene defines $\*$, the closure operator, as a *binary* operator, rather than a unary operator as we do today. This enables Kleene to avoid dealing with empty strings. $E\*F$ means the same thing it does today: "0 or more instances of E followed by F" but there is no way to say $E^\*$ and have it include the empty string.
> 8 votes

---
Tags: formal-languages, reference-request, automata
---


# Question
Title: Subspace clustering with random transformation
One approach for clustering a high dimensional dataset is to use linear transformation, and the most common approaches are PCA and random projection (where random projection arises from the Johnson-Lindenstrauss Lemma). I was wondering why we can't use other random transformation s like when our transformation matrix $R$ was drawn from a uniform distribution?

# Answer
It is possible that choosing $R$ according to a uniform distribution *with zero mean* constitutes a Johnson–Lindenstrauss random projection (i.e., it approximately preserves distances). See for example a paper by Achlioptas which suggests three distributions that definitely work: a zero-mean Gaussian, a random $\pm 1$, and a specific distribution on $\\{0,\pm 1\\}$. It is probable that using the methods in the paper, the case of the uniform distribution can also be analyzed.
> 1 votes

---
Tags: data-mining, linear-algebra, classification, cluster
---


# Question
Title: How does one figure out where a class of languages falls under some complexity class?
I was wondering how can someone prove that one class of languages is of a certain complexity? For example, how could I show the Turing-recognizable languages are in P?

Would I have to come up with an algorithm that runs in deterministic polynomial time?

# Answer
Turing recognizable languages are not (generally) in P, as the time hierarchy theorem implies. To show that a class $L\_1$ is contained in a class $L\_2$, you need to show that every language in $L\_1$ belongs to $L\_2$. For example, to show that $L$ (logspace) is contained in $P$ (polytime), you argue as follows: every language in $L$ is decided by some machine running in logarithmic space; this machine must run in polynomial time; so the language is in $P$. In this example, the same machine was used, but this is not necessary. For example, Savitch's theorem shows that $\mathrm{NSPACE}(s(n)) \subseteq \mathrm{DSPACE}(s(n)^2)$, and here the same machine cannot be used (since a non-deterministic Turing machine is not necessarily deterministic).
> 0 votes

---
Tags: complexity-theory, formal-languages, proof-techniques
---


# Question
Title: Set that keeps unique categories of objects
I would like to know if this type of special set operator exists, and if yes what is it called and if it has any other special properties.

Lets say I have this set $S$ of items. Like all sets, if the same item is added twice in the set, the set will not add it again. However, when adding an item, using this special operator, it also checks if it is 'better' than another item already in the set, and if yes it replaces it with the new item rather than letting both.

For a more concrete example:

$S\_1 = \\{apple, orange, pear\\}$

$S\_2 = \\{betterApple, orange, banana\\}$

$S = S\_1 \cup\_\succ S\_2 = \\{betterApple, orange, pear, banana\\} $

So in this case $\cup\_\succ$ checked some relationship, lets say $\succ$ where $betterApple \succ apple$, and if such a relationship existed it dropped $apple$ rather than allowing both in the set, keeping the *stronger* one in the set.

# Answer
> 1 votes
There is no official operation that accomplishes what you want, but you can always define an operation $\cup\_{\succ}$ which does so. Just define the operation in words.

---

If for some reason you want a "physical" implementation, then here is one way. Each set is a collection of pairs, i.e. $$ \begin{align\*} S\_1 &= \\{ (apple,apple), (orange,orange), (pear,pear) \\}, \\ S\_2 &= \\{ (apple,betterApple), (orange,orange), (banana,banana) \\}. \end{align\*} $$ Furthermore, there is some partial order $\prec$ such that $(x,y),(z,w)$ are comparable iff $x = z$. When you take the union $S\_1 \cup S\_2$, you get $$ S\_1 \cup S\_2 = \\{ (apple,apple), (apple,betterApple), (orange,orange), (pear,pear), (banana,banana) \\}. $$ Then you can define a function $$ \phi(S) = \\{ x \in S : \text{ no $y \in S$ satisfies $y \succ x$ } \\}. $$ What you want is $\phi(S\_1 \cup S\_2)$.

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


# Question
Title: An $O(n)$ algorithm to FFT-evaluate an FFT evaluation
This question is from a practice exam in my algorithms class. I'm posting the question and the answer listed in that practice exam:

> Let $W$ be an $n\times n$ matrix whose $(i,j)$-th entry is $\omega\_n^{ij}$, where $\omega\_n$ is a principal $n$th root of unity. Let $X=(X\_0,\dots,X\_{n-1})$ be an $n$-vector. The product $W \times X$ can be computed in $O(n\log n)$ time. Let $FFT(X)$ denote the vector that results by applying the FFT evaluation algorithm to the vector $X$.
>
> Describe an $O(n)$ algorithm to compute $FFT(FFT(x))$.
>
> Answer: $FFT(FFT(x))$ is $W^2\times X$
> $(W^2)\_{jk} = 0$ if $j+k$ is not a multiple of $n$, and $n$ otherwise.

I'm confused about everything:
1. How does this run in $O(n)$? To compute $(W^2)\_{jk}$ I'm already iterating through $n^2$ elements....
2. Why is $FFT(FFT(x)) = W^2\times X$?
3. Why is $(W^2)\_{jk} = 0$ if $j+k$ is not a multiple of $n$, $n$ otherwise?

I would appreciate an answer that isn't too advanced as my math skills are limited to basic undergrad math classes of an engineering major.

# Answer
Let's answer your questions one by one.

1. You don't compute $W^2$ by squaring $W$ *algorithmically*. Rather, you compute $W^2$ "on paper", and you find out a formula for $W^2$. Given this formula, you can check that $$ (W^2 X)\_j = \sum\_{k=0}^{n-1} (W^2)\_{jk} X\_k = nX\_{-j}, $$ where $-j$ is the unique $k$ such that $j+k$ is a multiple of $n$. For example, if $n = 5$ then the correspondence between $j$ and $k$ is $$ \begin{array}{c|c} j & k \\\hline 0 & 0 \\ 1 & 4 \\ 2 & 3 \\ 3 & 2 \\ 4 & 1 \end{array} $$ Let $Y = W^2X$. Then $Y\_j = nX\_{-j}$, and so we can compute $Y$ from $X$ in linear time $O(n)$.
2. Since $FFT(X) = W\times X$, $FFT(FFT(X)) = W\times FFT(X) = W \times (W \times X) = (W \times W) \times X = W^2 \times X$.
3. This is a calculation: $$ \begin{align\*} W^2\_{jk} &= \sum\_{i=0}^{n-1} W\_{ji} W\_{ik} \\ &= \sum\_{i=0}^{n-1} \omega\_n^{ji} \omega\_n^{ik} \\ &= \sum\_{i=0}^{n-1} \omega\_n^{i(j+k)} \\ &= \sum\_{i=0}^{n-1} (\omega\_n^{j+k})^i. \end{align\*} $$ If $j+k$ is a multiple of $n$ then $\omega\_n^{j+k} = 1$ and so $$ W^2\_{jk} = \sum\_{i=0}^{n-1} 1^{j+k} = \sum\_{i=0}^{n-1} 1 = n. $$ Otherwise, $\omega\_n^{j+k} \neq 1$ and so we can use the formula for the sum of a geometric series to conclude $$ W^2\_{jk} = \sum\_{i=0}^{n-1} (\omega\_n^{j+k})^i = \frac{(\omega\_n^{j+k})^n - 1}{\omega\_n^{j+k} - 1} = 0 $$ since $\omega\_n^{(j+k)n} = (\omega\_n^n)^{j+k} = 1^{j+k} = 1$.
> 4 votes

---
Tags: algorithms, algorithm-analysis, fourier-transform
---


# Question
Title: Are NP-Complete languages closed under any regular operations?
I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NPC languages would produce a language not necessarily in NPC. Is it also true that NPC languages are not closed under the complement, concatenation, and kleene star operations?

# Answer
For all of the examples in this answer, I'm taking the alphabet to be $\\{0,1\\}$. Note that the languages $\emptyset$ and $\\{0,1\\}^\*$ are definitely not **NP**-complete.

* The class of **NP**-complete languages is not closed under intersection. For any **NP**-complete language $L$, let $L\_0 = \\{0w\mid w\in L\\}$ and $L\_1 = \\{1w\mid w\in L\\}$. $L\_0$ and $L\_1$ are both **NP**-complete but $L\_0\cap L\_1 = \emptyset$.
* The class of **NP**-complete languages is not closed under union. Given the **NP**-complete languages $L\_0$ and $L\_1$ from the previous part, let $L'\_0 = L\_0 \cup \\{1w\mid w\in \\{0,1\\}^\*\\}\cup\\{\varepsilon\\}$ and $L'\_1 = L\_1\cup \\{0w\mid w\in \\{0,1\\}^\*\\}\cup\\{\varepsilon\\}$. $L'\_0$ and $L'\_1$ are both **NP**-complete but $L'\_0\cup L'\_1 = \\{0,1\\}^\*\\!$.
* The class of **NP**-complete languages is not closed under concatenation. Consider the **NP**-complete languages $L'\_0$ and $L'\_1$ from the previous part. Since both languages contain $\varepsilon$, we have $L'\_0L'\_1 \supseteq L'\_0\cup L'\_1 = \\{0,1\\}^\*\\!$.
* The class of **NP**-complete languages is not closed under Kleene star. For any **NP**-complete language $L$, $L\cup \\{0,1\\}$ is **NP**-complete but $\big(L\cup \\{0,1\\}\big)^\* = \\{0,1\\}^\*\\!$.
* If the class of **NP**-complete problems is closed under complementation, then **NP** = **coNP**. Whether this is true or not is one of the major open problems in complexity theory.
> 19 votes

# Answer
Take a look at the proofs for union, intersection, concatenation, and kleene star of NP languages, here. Its seems like a similar argument could be made for NP-Complete languages.

For notation let

* $A$ be a oracle that decides a known NP-Complete problem like 3-SAT. See the definition of turing reducible
* $L\_1$ and $L\_2$ are NP-Complete languages
* $M\_1$ and $M\_2$ are Turing machines that decide $L\_1$ and $L\_2$ using $A$.
* $L\_3$ is $L\_1 \cup L\_2$
* $M\_3$ is a turing machine that decides $L\_3$

In the case of union from , we can create a new machine $M\_3$ that decides $L\_3$ by calling $M\_1$ and $M\_2$ as sub routines. In turn, each time $M\_1$ or $M\_2$ is called, $A$ is also called. So $M\_3$ decides $L\_3$ using $A$. By the argument from , the running time of $M\_3$ is in P and since it uses $A$ as a subroutine, $L\_3$ is NP-Complete. In other words, $L\_3$ is NP-Complete for the same reason that $L\_1$ and $L\_2$ are NP-Complete.

The same argument can be made intersection and it looks like similar arguments could be made for concatenation, and kleene star.

In the case of compliment, it seems likely to be difficult to prove for the same reasons is difficult to prove compliment in NP.
> -2 votes

---
Tags: complexity-theory, np-complete, closure-properties
---


# Question
Title: What's a good algorithm for deleting multiple elements in a heap?
I have a binary min-heap, size n, and I want to delete a number of elements, identified by some predicate.

Any algorithm needs at least n tests of the predicate (preferably, *exactly* n), so the interesting performance metrics are the number of moves of elements, and the number of additional tests of the predicate.

One possible way is to first delete elements from the corresponding array, using a single pass to delete elements and compact the array. And then rebuild the heap from the array. Both steps are O(n). But as far as I understand, the rebuild step can need n moves of elements even if only one or two elements are deleted, if they are at unlucky positions in the array.

I wonder if there's some good algorithm which

* needs O(n) element moves in the worst case
* needs few extra tests of the predicate, say total n + O(log n) tests in the worst case
* needs a lot fewer then n element moves in the special cases that only a few elements are deleted, or only a few elements are kept.

# Answer
I think you're optimizing for the wrong metrics. The total running time will be $\Theta(n)$ no matter what you do. Scanning the entire array to identify which elements to remove will take $\Theta(n)$ time, so your total running time can't be any better than $\Theta(n)$. Conversely, there is a simple algorithm that achieves $\Theta(n)$ time. MakeHeap can be done in $\Theta(n)$ time, so it gives you a simple $\Theta(n)$ running time algorithm: scan the entire array, delete whatever you want to delete, then run MakeHeap.

However, if you're trying to optimize the amount of work per deletion and for some reason the time taken to scan the array "doesn't count" (I don't understand why it wouldn't count, but let's just run with it):

In this case there is an alternative algorithm. Deleting a single element from a heap can be done in $O(\lg n)$ time. So, if you want to delete $k$ items, delete each one-by-one. Total running time: $\Theta(n)$ to scan the array, $\Theta(k \lg n)$ to delete them.
> 2 votes

---
Tags: heaps
---


# Question
Title: How to find partition set of a Partition Problem using its decision problem
I understand Partition Problem is NP-complete.

Given we have a magic black box that can answer Yes or No for the partition problem. I was wondering how to come up with a polynomial time algorithm to find the actual set using this black box.

Thank you.

# Answer
> 0 votes
Here is what you would do if instead of PARTITION you had SUBSET-SUM. Given a set $S$ and a target $T$, repeat the following process:

1. Pick some $x \in S$.
2. If $S \setminus \\{x\\}$ has a subset summing to $T$, remove $x$ from $S$ and go back to 1.
3. Otherwise, remove $x$ from $S$ and replace $T$ with $T - x$. Mark $x$ and go back to 1.

The set of all marked elements at the end of the algorithm is an answer.

This approach doesn't work for PARTITION (why?), but perhaps it helps figuring out how reductions of this sort work. One idea to try for PARTITION is merging elements (replacing $x,y$ with $x+y$). I'll let you work out the details.

---
Tags: complexity-theory, np-complete, partition-problem
---


# Question
Title: What does "finding an optimal action" for a bandit mean?
In Sutton and Barto's reinforcement learning book, in multi-armed bandit problem a phrase has been used. "finding an optimal action" using greedy/$\epsilon$-greedy algorithm. When it is said that an algorithm "finds the optimal action " ?

# Answer
In the bandit setting, to each arm is associated an unknown reward distribution. The optimization goal is to find a policy (a series of level pulls) which yields the maximum sum of rewards.

"Finding an optimal action" thus refers to the process of discovering the arm which gives you the most reward.
> 2 votes

---
Tags: algorithms, terminology, machine-learning, optimization, artificial-intelligence
---


# Question
Title: Prove that there is a path of lenght k+1 in a graph with minimum degree k
I am faced with this question.

> Let $G$ be a graph in which each vertex has degree at least $k$. Show that there is a path of length $k$ in $G$ - that is, a sequence of $k+1$ distinct vertices $v\_0, v\_1, ..., v\_k$ such that for $0 ≤ i \< k$, $v\_i$ is connected to $v\_{i+1}$ in $G$.

I started attacking it this way:

If $G$ has a vertex of degree atleast $k$, it has atleast $k+1$ vertices. That is, $G$ can have $|v| \geq k+1$

In the case where $|v| = k+1$, the graph is a fully connected graph of $k+1$ vertices, which trivially has a path of length $k+1$.

I am not able to prove the cases where $|v| \geq k+2$

# Answer
**Hint.** Build up the path, using the minimum degree condition to show that you can extend it as much as you need to.
> 3 votes

# Answer
Here are some tips on how to approach this kind of question. First, try some example graphs, to see what happens. Pick a few small graphs, and try by hand to find such a path. What strategy do you find yourself using? Can you generalize it?

Next suggestion: Have you considered what happens if you run depth-first search in such a graph?
> 2 votes

---
Tags: graphs
---


title: regular expression in license plates

text:
# Question
Title: regular expression in license plates
I'm trying to write a regular expression for some particular license plates. They consist of one up to three capital letters, a hyphen, one up to two capitol letters and one up to four numbers. The license plate should not exceed the 8 symbols.

Example: AA-AA123

What I have until now is the following:

because there has to be at least one letter before the hyphen, I have this expression for the first letter: $$ P = (A\cup B \cup...\cup Z) $$

For the second letter: $$ D = (A\cup B \cup...\cup Z\cup empty) $$ empty indicates the possibility that there could not be a letter.

For the numbers is basically almost the same procedure: $$ E = (1\cup 2 \cup...\cup 9) $$ $$ F = (1\cup 2 \cup...\cup 9 \cup empty) $$

now for my explicit expression I think the answer would be: $$ K= PDD^\* - PDEF^\*F^\* $$

but I'm not quite sure. I think this means I have 8 symbols, at least one letter before the hyphen but I could have up to three, the hyphen (that is a must), at least one letter after the hyphen but up to two and at least one number but I could have up to 4.

Something tells me I have something wrong here, I'm still new in the regular expressions world and I appreciate any help I could get in advance.

# Answer
> 2 votes
As David Richerby pointed out $D^\*$ will accept an arbitrary number of letters (including none). If I'm not mistaken you need to take all possible options to achieve not having more than 8 characters. $$ K = ( PDD-PDEF ) \cup (PDD-PEFF) \cup (PD-PDEFF) \cup (PD-PEFFF) \cup (P-PDEFFF) $$ This assumes the hyphen is one of the 8 letters and thus does not allow more than 8 letters. Less letters are allowed because of your definitions of $F$ and $D$ including the empty word $\varepsilon$.

EDIT: added missing cases from commenter.

# Answer
> 0 votes
A straightforward answer is that it must match the regexp $P\\{1,3\\}-P\\{1,2\\}E\\{1,4\\}$ and must be exactly 8 characters long. If I was implementing this in code, that's what I would do: I would check that it matches the former regexp, and check that its length is 8.

Note on notation: $P\\{1,3\\}$ means one to three repetitions of $P$. Of course, you can remove this standard notation using standard methods: e.g., $P\\{1,3\\}$ is equivalent to $(P|PP|PPP)$, and so on. Thus, the regexp I gave earlier is equivalent to $(P|PP|PPP)-(P|PP)(E|EE|EEE|EEEE)$.

If you insist on a single regexp that checks everything, without a separate check that the license plate is 8 characters long, you could re-express the requirement that this must be exactly 8 characters long as the regexp $(P|E)\\{8\\}$, so we want something that matches both $P\\{1,3\\}-P\\{1,2\\}E\\{1,4\\}$ and $(P|E)\\{8\\}$. Since regular languages are closed under intersection, you can derive a single regular expression for their intersection using standard techniques.

Yet another way to approach this is to build up a finite-state automaton to recognize such license plates, then convert it to a regexp. Your individual constraints can be expressed in a straightforward way as a non-deterministic finite-state automaton (NFA), and then there are standard ways to convert a NFA to a regexp.

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


# Question
Title: Create a shallow logic circuit that increments a binary number
This circuit should be reasonably efficient in size and depth, but with priority on depth.

If depth was not a concern, then I guess I could make a specialized adder for the least significant bit and then modelled the rest of the circuit as a ripple adder with only that initial, possible carry. The carry has to ripple through the first sequence of consecutive bits set to 1. For example:

$inc(0111) = 1000$
$inc(0001) = 0010$
$inc(0100) = 0101$ (no ripple)

But this takes linear time, in the worst case (binary string is $1...1$). How do you optimize for depth? Does the optimal circuit have a $log\_2(n)$ depth?

Is perhaps the best strategy to use a parallel prefix circuit? If so, I guess one would make a specialized adder for the least significant bit. Then you have the result of the least significant bit, which is 0 if a carry was generated, 1 otherwise. If a carry was generated, then you need to efficiently ripple it through all the adjacent, consecutive 1-bits. If one is to use a prefix sum, then you need an associative binary operator. It also needs to preserve the value of the bits that are not part of the initial, consecutive 1-bits (from right to left). This might mean that you pass in the carry bit that was (possibly) generated after the increment on the least significant bit, while the rest of the operators gets fed predefined bits which preserve the values of the relevant bits of the number (bit vector).

At this point, I'm stuck.

# Answer
You are on the right track with a parallel-prefix circuit. You already have the key when you said

> The carry has to ripple through the first sequence of consecutive bits set to 1.

Now suppose you are figuring out the output for, say, the 5th bit. What function of the first 4 bits tells you whether the 5th bit should ripple? That's the function you need to make a parallel-prefix circuit for.
> 2 votes

---
Tags: logic, circuits
---


# Question
Title: How to evaluate all derivatives of a polynomial at a point with FFT?
I found this problem:

> Evaluating all derivatives of a polynomial at a point
>
> Given a polynomial A(x) of degree-bound n, its tth derivative is defined by
>
> From the coefficient representation $(a\_0, a\_1, . . . , a\_{n-1})$ of A(x) and a given point $x\_0$, we wish to determine A(t) ($x\_0$) for t = 0, 1, . . . , n - 1.

I know the vector of the coefficients has to be used and I also know that the derivative of a term $ax^n$ is $a\*n\*x^{n-1}$, but where do I go from there?

I can only think of the naïve scheme to evaluate this: Find the first derivative ($O(n)$), evaluate it using Horner's method ($O(n)$). Repeat this for all deterivaties, giving $(O(n^2)$).

# Answer
> 1 votes
Hint: Taking the derivative has a certain, simple diagonal effect on the Fourier transform, that hopefully was covered in class. Hence if you compute the Fourier transform of the original function, you "know" the Fourier transform of all its derivatives as well. Given the Fourier transform, there is a formula for the value of the actual function. In your case, in order to compute the value of all derivatives of the function at a point, you multiply some matrix by the vector of Fourier coefficients. This matrix looks suspiciously similar to the DFT matrix, so hopefully you can compute the matrix-vector product in time $O(n\log n)$.

---
Tags: fourier-transform
---


# Question
Title: Complexity of factoring products of distinct prime numbers
Problem: Input is an integer number $x$ that we know factors as $p\_{i\_1}\cdot p\_{i\_2}\ldots p\_{i\_n}$, where the $p\_{i\_j}$'s are distinct prime numbers. Output is the above factorization of $x$.

Do you know any results/references for the time complexity of this factoring problem?

Note: If the $p\_{i\_j}$'s are not assumed distinct, then the problem is just integer factorization. This is a very special case.

# Answer
As far as I know, there are no non-trivial lower bounds on factoring, and in particular, no variant is conjectured to be NP-hard. (While factoring is not a decision problem per se, you can make up a corresponding decision problem that gives the $k$bit of the $\ell$th smallest factor.)

As far as algorithms go, there are a great many of them, including the following subexponential ones:

1. Quadratic sieve: this factors an integer $n$ in time $2^{O(\sqrt{\log n\log\log n})}$. There are many variants of this algorithm resulting in different constants for the big O, and one of them (due to Dixon) provably has the stated running time.
2. Elliptic curve method: this factors an integer $n$ with smallest prime factor $p$ in time $2^{O(\sqrt{\log p \log\log p})}$ (in general, this is the time it takes to find the factor $p$ rather than the complete factorization). No variant of this algorithm has a provable running time guarantee. The algorithm relies on the fact that random elliptic curves modulo $p$ have a certain order (number of points) distribution, and this empirically verifiable property isn't proven. (What you really need to know is the probability that the order is $\alpha$-smooth, whose conjectured behavior is satisfied for any reasonably smooth probability distribution.)
3. Number-field sieve: this factors an integer $n$ in time $2^{O(\sqrt\[3\]{\log n (\log \log n)^2})}$. No variant of this algorithm has a provable running time guarantee. The algorithm relies on the probability that a random element of a number field is smooth (in terms of its norm), a property which can be empirically verified but is unproven.

In practice, one first runs simpler algorithm which are able to find small prime factors more quickly. Some of the algorithms might run into problem if all prime factors are repeated, which is ruled out by your constraints, but I can't think of any concrete example.

There is no consensus on the conjectured complexity of the problem. Recent advances in the related discrete logarithm problem suggest that factoring might be in quasipolynomial time, and some people (Charles Rackoff, for example) wouldn't even rule out a polynomial algorithm for factoring. Others would concede that the number-field sieve algorithm might not be optimal, but that factoring should require time $2^{\Omega((\log n)^c)}$ for some $c \> 0$.
> 5 votes

---
Tags: complexity-theory, reference-request, time-complexity, factoring
---


title: Coq --- non-terminating programs

text:
# Question
Title: Coq --- non-terminating programs
People usually say Coq does not allow writing non-terminating functions. I have a question regarding that.

Does Coq allow writing exactly **all** terminating functions? In other words, what are the completeness and soundness properties of Coq's procedure for checking well-foundness of fixpoint definitions?

# Answer
Coq cannot always know whether a program will terminate, because that would be a solution to the halting problem.

Coq is able to notice that a certain class of programs will terminate. The main heuristic it uses is that if one of the arguments to the function must get smaller on each recursive call, the program must terminate.

If you have a function that terminates, but Coq cannot tell that it terminates, you can add an extra argument that always get smaller on recursive calls. Doing this amounts to providing a proof that the function terminates.

So basically, Coq accepts any program that the user can prove the termination of.
> 5 votes

# Answer
There is no effective enumeration of all decidable languages. For suppose that $P\_i$ was an effective sequence of programs (meaning that the mapping $i \mapsto P\_i$ is computable) such that each $P\_i$ always halts, and every decidable language is $L(P\_i)$ for some $i$. Consider the program $P$ which, on input $i$, runs $P\_i$ on input $i$ and accepts if $P\_i$ rejects. The program $P$ always halts and so $L(P)$ is decidable, hence $L(P) = L(P\_i)$ for some $i$. But by construction, $i \in L(P)$ iff $i \notin L(P\_i)$. This contradiction shows that no such effective enumeration is possible.
> 3 votes

---
Tags: machine-models, coq
---


# Question
Title: Is the complexity class NP computably enumerable?
The definition of the complexity class $\mathsf{NP}$ seems to ensure (as good as possible) that it is computably enumerable. It looks as if the class could be enumerated by enumerating all Turing machines, and for each Turing machine report for each $k\in\mathbb{N}$ the language generated by stopping each computation after $n^k$ steps, and reject if the input hasn't been accepted before reaching this step limit.

This only gives a computable enumeration of Turing machines. However, it seems that the corresponding languages will be decidable, because the enumeration includes an explicit time bound for each of its Turing machines. Hence this should give an computable enumeration of $\mathsf{NP}$.

> Question: Is the conclusion from this reasoning correct, i.e. is $\mathsf{NP}$ computably enumerable? One issue that I have is that even for decidable languages, we can only (computably) decide whether two given languages are different, but not whether they are equal. Hence it seems that we can't avoid to report the same language more than once. The deeper issue here is that being computably enumerable is a property of subsets of the natural numbers, but the complexity class $\mathsf{NP}$ doesn't seem to correspond to a subset of the natural numbers in any canonical way.

# Answer
Your trick is actually used in structural complexity theory, say in these proofs of Ladner's theorem. In order to enumerate all languages in NP, you instead enumerate all timed Turing machines $\langle M, k \rangle$, which automatically stop and (say) reject after $kn^k$ steps. Another variant is that a time polytime machine is a pair $\langle M,k \rangle$, where $M$ is guaranteed to stop within $kn^k$ steps. You can't enumerate timed polytime machines under this definition, for the same reason as in Raphael's answer.
> 1 votes

# Answer
I can't make heads nor tails from what you attempt to do, but I know that the answer to your question is: no, NP is not enumerable.

First, let's fix what that means. I assume you are asking if

$\qquad\displaystyle \mathrm{TM}\_{\mathsf{NP}} = \\{ \langle M \rangle \mid L(M) \in \mathsf{NP} \\}$

is recursively enumerable. It's not by the extended Rice theorem since the Turing machine $M$ that never halts is an NP-acceptor for the empty language, so $M \in \mathrm{TM}\_{\mathsf{NP}}$, but there certainly are $M'$ with $M \subsetneq M'$ and $M' \notin \mathrm{TM}\_{\mathsf{NP}}$.

Intuitively, no algorithm can separate $M$ (which has infinitely many equivalent brethren, by the way) from any other Turing machine in finite time, and thus can never enumerate them.
> 5 votes

---
Tags: computability, complexity-classes, np, enumeration
---


# Question
Title: Are there any PSPACE problems that don't exist in NP-Hard?
The question is in the title, I suppose. I am studying complexity classes, and I understand that NP-Hard is the set of problems that are at least as hard as the hardest problems in NP. Therefore, it will naturally contain PSPACE problems.

However, I was specifically wondering if there were any PSPACE problems that were not in NP-Hard? (from my understanding, implying that they are *easier* than the hardest problems in NP).

# Answer
Assuming we use polytime reductions in both, all PSPACE-hard problems are NP-hard, which follows directly from the definition and from the easy fact NP$\subseteq$PSPACE: a languages $L$ is PSPACE-hard if all languages in PSPACE polytime-reduce to $L$. If $L$ is PSPACE-hard then in particular, all languages in NP polytime-reduce to $L$, and so $L$ is also NP-hard.

On the other hand, there are problems in PSPACE which are not NP-hard, for example $\emptyset$ and $\Sigma^\*$. If P=NP then all other problems in PSPACE are NP-hard, since every non-trivial language (a language different from $\emptyset,\Sigma^\*$) is NP-hard in this case. If P$\neq$NP then every problem in P also belongs to PSPACE and is not NP-hard.
> 5 votes

---
Tags: complexity-theory, np-hard, complexity-classes
---


# Question
Title: Is traversing an unconnected graph possible?
I have been assigned a fun project: design and implement a program that maintains the data of a simple social network. Each person in the network should have a profile that contains his name, current status, and a friends list.

I think it is clear that the project calls for the use of the ADT graph. Each vertex represents a person in the network and an edge between vertices a friendship. Now, the graph may not be connected because some members do not have any friends in the network. With that in mind, consider this feature that must be implemented:

**•The network must have a feature that computes the “emergency phone chain," make sure that each member in the network is contacted, and only by one person. Any of the people in the network may initiate the first call. Utilize a depth-first graph traversal algorithm.**

Now, what I think my professor is suggesting is merely a full traversal of the graph. How is that possible for an unconnected graph? Any suggestions?

(btw, the wording above is somewhat unclear - does the professor mean that everyone in the network is contact by the same one person? Thoughts? I would ask her, but she is unavailable until next week.)

# Answer
> 1 votes
That's a question only your professor can answer. There are at least two possible solutions:

1. Each "chain" involves a single connected component.
2. Some links will be among non-friends.

In the latter case, you would like to minimize the number of unfriendly links. If there are $c$ connected components, then you only need $c-1$ of these.

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


# Question
Title: What does it mean that a value can only be incremented after it's been loaded into a register?
Consider the following program:

```
const int n = 50;
int tally;

void total() {
  int count;
  for (count = 1; count <= n; count++){
    tally++;
  }
}

void main() {
  tally = 0;
  parbegin (total (), total ());
  write (tally);
}

```

> 1. Determine the proper lower bound and upper bound on the final value of the shared variable tally output by this concurrent program.Assume processes can execute at any relative speed and that a value can only be incremented after it has been loaded into a register by a separate machine instruction.
> 2. Suppose that an arbitrary number of these processes are permitted to execute in parallel under the assumptions of part (a).What effect will this modification have on the range of final values of tally?

My problem is that I don't understand the question what does this mean ?

> ... and that a value can only be incremented after it has been loaded into a register by a separate machine instruction.

I feel that when two processes execute simultaneously due to this assumption some value of tally will be lost but I don't know how it can happen because I don't know what this assumption means so I can't find lower bound!it is obvious that if 2 or n process execute one after the other tally will be 100 hence 100 = (number of process \*50) is upper bound!

# Answer
> 0 votes
if we suppose the processes P1 and P2,at first P1 executes. it increments tally to 1 but before it loads it to memory,it lose the processor,then P2 is processing and after 49 iteration it makes tally to 49 and stores it then it lose processor and again P1 is processing and store 1 to tally then lose processor and P2 load 1 to register and lose processor, P1 increment tally to 1+49 = 50(within 49 iteration) and tally = 50 ,then lose processor ,P2 increment the register which was 1 and loads 2 to tally and now it is complete and tally = 2 ; so answer is :

```
1.  2 <= tally <= 100
2.  2 <= tally <= 2*numbers of process

```

.

# Answer
> 2 votes
Here are some more concepts to help with this.

CPUs use load and store instructions to execute the high level language concept of `tally++;`. This is not atomic, unlike atomic CPU operations such as read-modify-write.

This question is alluding to the fact that there is no atomicity and that the common set of instructions can be executed in any interleaving by the $n$ processes.

The "lost update" concept is the enemy here. Wikipedia's "Concurrency control" article talks about this but mostly in a database transaction sense. Nevertheless it is absolutely the same high level concept of:

* Thread1 reads `tally` into register (likely the ALU) (observes 6)
* Thread2 reads `tally` (observes 6)
* Thread1 increments ALU (now is 7)
* Thread2 increments ALU (now is 7)
* Thread1 writes ALU to `tally` memory (value stored is 7)
* Thread2 writes ALU to `tally` memory (value stored is 7)

So BOTH threads/processes/whatever have "incremented" tally but the shared memory value of tally is ONLY 1 larger than when it started. Thread2's write to memory caused a lost update; Thread1's write was "lost".

By setting the question to say that there are at least three instructions required to increment (i.e. `tally++;`) the asker is saying that it is entirely possible that lost updates can occur due to interleaving of the instructions by multiple processes and causing lost updates.

I'd say the lower bound of tally is 50 (maximum destructive interleavings occur). Upper bound is 50 * numProcesses (where no unscrupulous interleavings of the increment code occur).

Concepts to look up are:

* Shared memory concurrency/parallel
* Atomic and non-atomic instructions like load store and read modify write
* Interleaving of instructions
* Lost update

# Answer
> 1 votes
All operations are done in the CPU, the value is read from memory, incremented, and written back. This is so even in machines with "increment memory" instructions.

---
Tags: terminology, concurrency, semantics
---


# Question
Title: Automata with no transition for some character
Given an automaton and an alphabet $\\{a, b\\} $, and the language accepted by the automaton is $ab^\*$.

Such an automata can be found here:

My question is: this automaton cannot process the word $ba$ for example. In general, do automata have to be able to process any word?

# Answer
> 3 votes
In a deterministic automaton, every state must have *exactly one* transition for each symbol in the alphabet. In a nondeterministic automaton, this requirement is dropped and there could be multiple transitions or no transition for some symbol. If there is no transition for the next character in the string, the automaton rejects its input. This is what happens with the automaton on the left: it rejects the string $ba$ (and every other string beginning with $b$) because it has nowhere to go when it reads that first $b$.

# Answer
> -2 votes
An Automaton is supposed to accept only (all) strings that are in some language for which it is defined, and reject any string not in the language.

The automaton on the left, accepts all strings of from $\mathcal{L} = ab^\* \equiv {a, ab, abb, abbb, abbbb, ... }$

strings are not commutative, i.e $ab \neq ba$

As you pointed out, it won't accept $ba$ since that's not in $\mathcal{L}$

and in general, automata accept any string in the language.

\[by process i assume you mean accept/reject\]

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


title: Satisfiabilty 2-sat

text:
# Question
Title: Satisfiabilty 2-sat
Im trying to work out whether the following clause is satisfiable:

```
{x, y},{x,¬y},{¬x, y},{¬x,¬y},{x, z},{x,¬z},{y, z},{y,¬z}

```

My basic understanding is to work this out, you must give each literal a true or false assignment to work out if each clause is satisfiable so:

x=1, y=1, z=1,

```
{1,1}, {x,0}, {0,1}, {0,0}, {1,1}, {1,0}, {1,1}, {1,0}

```

Therefore the clause `{x,y}` and `{x,z}` are satisfiable?

I also heard you can switch the statement so:

x=1, y=0, z=1,

This means `{x,y}` is not satisfiable.

If we changed z to 0 as well `{x,z}` would not be satisfiable. What really confuses me here is when the truth assignments are changed, neither clauses are satisfiable.

Where am I going wrong?

# Answer
> 4 votes
You seem to assume that both literals in a clause must be true in order to satisfy the clause. However, it is sufficient that one of them is true. So with your first assignment all clauses but `{¬x,¬y}` are satisfied.

You also mix up some terminology:

* A clause is a single group of literals like `{x,y}`. What you are trying to satisfy overall is a group of clauses or a formula.
* When you are considering a specific assignment of values, you talk about clauses that are "satisfied", not "satisfiable". Satisfiability is a property of the formula as a whole. (A single clause is always satisfiable.)

PS: Since your formula only uses 3 variables it is feasible to try out each possible assignment of values in order to see if the formula is satisfiable.

---
Tags: logic, satisfiability, propositional-logic
---


title: Best (Fastest) Arithmetic Algorithms

text:
# Question
Title: Best (Fastest) Arithmetic Algorithms
What are the best arithmetic algorithms out there (addition, subtraction, multiplication, division, power, root)?

I am looking for algorithms that could be easily extended to multiprecision and arbitrary precision settings.

# Answer
The concept of a "best" algorithm is not as simple as you'd expect. It depends on at least two more parameters: the machine model and the numbers involved (i.e., how large are the numbers being operated on). For a thorough discussion of this as regards integer multiplication, see Fürer's paper How Fast Can We Multiply Large Integers on an Actual Computer?

There is a wikipedia page devoted to the computational complexity of mathematical operations, including everything you mention. However, from a practical point of view, I would rather look at the source code of a strong library for multiprecision arithmetic like GMP. Such a library is optimized for fastest performance on actual computers. The source code of GMP is readily available, and you can peek under the hood.
> 1 votes

---
Tags: binary-arithmetic, arithmetic
---


# Question
Title: Can we create binomial heaps in linear time?
I'm studying binomial heaps in anticipation for my finals and the CLRS book tells me that insertion in a binomial heap takes $\Theta(\log n)$ time. So given an array of numbers it would take $\Theta(n\log n)$ time to convert it a a binomial heap. To me that seems a bit pessimistic and like a naive implementation. Does anyone know of a method/implementation that can convert an array of numbers to a binary heap in $\Theta(n)$ time?

# Answer
Wikipedia claims that insertion takes $O(1)$ amortized time, and so converting an array of numbers into a binomial heap should indeed take time $O(n)$. This is also supported by these lecture notes, and probably mentioned in CLRS.
> 4 votes

---
Tags: data-structures, efficiency, heaps, priority-queues
---


# Question
Title: Does "serializable" also mean that it's lockable
Here's an final exam question for a Database Fundamentals class. I've read the book, stuff online.. I can't figure out if "*serializable*" also means that the schedule is `lockable` or not. What I mean is.. I understand that for the schedule to be isolated, you have to have non-conflicting *reads* & *writes*, but then it also says "if the transactions are not isolated(i.e., serializable).."

By determining if the schedule is isolated, does this include determining if locks(lock-W(x), lock-R(x)) and unlocks can be placed inside the schedule, is `"serializable"` both *isolated* and *lockable*?

`lockable` \- can locks and unlocks be placed inside the schedule at appropriate R/W-intervals.

Here's the question:

> a). Two transactions are shown below. The statements of the transaction are executed from top to bottom. Specify whether the current schedule meets the Isolated property of ACID and why or why not. If the transactions are not isolated (i.e., serializable) specify what concurrency problem may occur with this schedule. Be specific about what statement(s) in what transaction(s) causes the issue.

$$ \begin{array}{}Time&Transaction \\, 1&Transaction \\, 2 \\1&Read(B)&Read(B) \\2&\\\_&Update(C = C + B) \\3&Read(C)&\\\_ \\4&\\\_&COMMIT \\, or \\, ROLLBACK \\5&Update(A=B+C)&\\\_ \\6&COMMIT\\, or \\, ROLLBACK&\\\_\end{array} $$

# Answer
The definition of *serializable schedule* is pretty clear. Intuitively, it is a schedule which is equivalent to a *serial schedule*.

More formally, according to \[1\] :

> A serializable schedule over a set S of transactions is a schedule whose effect on any consistent database instance is guaranteed to be identical to that of some complete serial schedule over the set of committed transactions in S.

In your example the schedule is definitely serializable, since it is equivalent to running Transaction 2 and then Transaction 1.

I don't know what do you mean by "lockable" and not sure that this term can be applied to a schedule.

\[1\] R.Ramakrishnan and J.Gehrke, Database Management Systems, 3rd edition
> 1 votes

---
Tags: concurrency, databases
---


title: Definition of “c-competitive” algorithm

text:
# Question
Title: Definition of “c-competitive” algorithm
What is the definition of a "c-competitive" algorithm? For example what does it mean, if we say that there is a 2-competitive algorithm for packet routing?

# Answer
> 3 votes
You are given algorithm $ALG$ for optimization problem $\mathcal{P}$ and and cost function $\mathcal C$.

You can define cost of **optimal algorithm** $OPT$ as:

$C(OPT(I))=\min\_{O\in F(I)}\mathcal C(I,O)$, where $I$ is valid input, $F$ is a feasible solution on input $I$ and $O$ is the output associated with that feasible solution. Then you can define cost of c-competitive algorithm as:

$\mathcal C(ALG(I))\le c\cdot \mathcal C(OPT(I)) + \alpha$,

Where $\alpha$ arbitrary is constant, if $\alpha = 0$ then we are talking about **strictly c-competitive** algorithm

---
Tags: algorithms, terminology, performance
---


# Question
Title: shortest time based on traffic congestion data
I want to develop one algorithm which can predict shortest time to be taken to go to a destination from a source in a road network based on traffic congestion data. Consider that I have a server which gives me real time traffic congestion data for all the path segments in a road network. Now I want to develop such an algorithm which can predict time to be taken based on these data. So in short:

time\_to\_be\_taken\_from\_source\_to\_destination = function ( traffic\_congestion\_data ). And 'time\_to\_be\_taken\_from\_source\_to\_destination' is proportional to 'traffic\_congestion\_data' as time increases when traffic\_congestion increases.

Are there any such algorithm alraedy developed? Any idea? reference to any algorithm or theory will be appreciated.

# Answer
There is no special "algorithm theory" behind this.

You decomposed this data into a graph, right? You have intersection nodes, and you have edges with path difficulty (distance/average speed), yes? The congestion data simply modifies the average speed of the edge, so it's just A\* business as usual. Regular shortest path heuristics will probably still be relevant for conservation purposes if you're lazy.

Obviously a prominent example of an implementation of this would be https://maps.google.com/.
> 1 votes

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


# Question
Title: Are self-stabilizing algorithms guaranteed to work in parallel?
Self-stabilizing algorithms are extremely useful in distributed systems, but can the algorithm be applied concurrently to each computational node?

My instinct is to say yes, but I can't help but imagine a 'Game Of Life' scenario where the state of the graph toggles between two states. What keeps the question alive in my mind is the possibility that both such states would be considered 'correct', but then if the state were correct, wouldn't the graph stabilize?

If they are not guaranteed to work in parallel, can you provide an example where absolute convergence doesn't exist?

---

A self-stabilizing algorithm is an algorithm (in all my experience, applied to arbitrary graphs and graph structures exclusively) that, upon repeated applications, guarantees *convergence* onto a correct state—one that meets a set of requirements. Consider a simple example:

> You maintain a network of hospitals and data centers. Each hospital must be connected to exactly one data center, and each data center must be connected to exactly two other data centers. (You can imagine also attempting to minimize latency.) When you set up the network, it is in a correct state—all requirements are met.
>
> Weeks pass, and a giant storm takes out one of your data centers. Being the forth-dimensional thinker you are, you planned for situations like this by putting into place a self-stabilizing algorithm that will automatically reconfigure the network to get back to a correct state. You set up a daemon to oversee the operation. It picks arbitrary nodes in your network and asks them if they are in a correct state. If not, the daemon corrects that part of the network.
>
> All is well and you can stay asleep in bed (because everything catastrophic happens at 3am).

The trick is, the daemon isn't a necessary part of this system—it's just easier to think about it like this. In reality, each node is its own computational unit—constantly evaluating its own state and taking steps to correct itself if necessary.

The introductory paragraphs of the Wikipedia article on the subject give a very good technical overview:

> Self-stabilization is a concept of fault-tolerance in distributed computing. A distributed system that is self-stabilizing will end up in a correct state no matter what state it is initialized with. That correct state is reached after a finite number of execution steps.

Just as a piece of requested information that doesn't fit in well above:

> When the graph is stable, no node has any faults with it. Since no predicates apply to it, no actions are taken, and the graph remains stable.

# Answer
I suggest you look for a textbook that provides an introduction to self-stabilizing algorithms (with some definitions, examples, etc.), and work through that textbook. I think that will provide you a much better understanding, and you'll be able to answer this kind of question yourself. Trying to learn a subject by reading Wikipedia and asking questions on StackExchange sites is not the way to go.

For instance, I think you'll find that, yes, of course each distributed node is working concurrently (in parallel); that's what it means for a system to be a *distributed* system. And yes, for a self-stabilizing algorithm to be correct, one must show that it will never enter an infinite loop of the sort you describe; this is the *convergence* property.

Designing an algorithm with these properties is non-trivial, but in general, designing self-stabilizing systems is not easy. No one ever promised this stuff would be easy.
> 4 votes

# Answer
I think self-stabilizing algorithms guaranteed to work in parallel environment also. but you should go through book also, here i am mentioning some good books for self stabilization from my experience:

**References:** **1:** Self-Stabilization by Shlomi Dolev

**2:** Distributed Systems: An Algorithmic Approach bye Sukumar Ghosh Chapter 17.
> 0 votes

---
Tags: algorithms, parallel-computing
---


# Question
Title: MIS algorithm for Tree in O(log* n) time
I know Distributed Graph Coloring algorithm in O(log\* n) which is given at P11: Vertex Coloring

Same for Maximal Independent Set \[MIS\] they gave remark like algorithms exist in O(log\* n) time at P70: Maximal Independetn Set

How we can reduce Graph coloring problem to MIS in O(log\* n) time?

# Answer
> 1 votes
A tree is always a bipartite graph, which means it will have only two colors.

Look at what the algorithm described on the paper you have linked:

```
We first choose all nodes of the first color. Then, for each additional color
we add "in parallel" (without conflict) as many nodes as possible.

```

Being bicolored means that if you choose any of the two colors, no nodes from the other color can be added. So, for a Tree, finding the MIS has time complexity equal to the coloring algorithm (just color it, then the color with most nodes is the MIS, that can be chosen in constant time).

If you can color in $O(\log^\* n)$, then that's $O(\log^\* n)$ for a tree (that, however, is only for graphs that can be bicolored).

---

Regarding your specific confusion:

Any graph that is $N$-colorable is also $M$-colorable with $M \> N$ and $M \leq V$ (number of vertices). This doesn't change the fact that a tree is bipartite (meaning it is 2-colorable). To see this, just take a bicolored graph. To create a third color, you can just color any node with a third color (or as many as you want, as long as they had the same previous color).

Now, I don't have much knowledge about distributed algorithms, but the paper you linked on the comment says that 3-coloring the tree is actually less expensive than 2-coloring it (regarding the amount of messages sent). This doesn't change the fact that, for a tree, you can be sure that it is $N$-colorable (with $N \geq 2$ and $N \leq V$).

Now, from Theorem 1.17, you have an algorithm that colors a tree with 3 colors in $O(\log^\* n)$. From Corollary 7.3 you have that MIS can be done in time $C + T$.

From what I understand, for a general graph you don't know how many colors it needs, but for a tree, since you know it is $N$-colorable with $N \geq 2$ and can be 3-colored in $O(\log^\* n)$, this would give you time $O(3 + \log^\* n) = O(\log^\* n)$. The difference to a general graph is that the number of colors become constant.

---
Tags: graphs, reductions, distributed-systems
---


# Question
Title: What is the difference between expected cost and average cost of an algorithm?
While going through probabilistic/average analysis of an algorithm, I found written somewhere that average cost and expected cost are same. Can anyone please tell me what does exactly expected cost stands for.I think we take care of likelihood of an event while finding expected cost unlike average cost.

# Answer
In short, the average is the expected value of the uniform distribution.

If $T(x)$ denotes the runtime of some algorithm on input $x \in \mathcal{X}$, then the *expected* runtime for input size $n$ is

$\qquad\displaystyle \mathbb{E}\[T(X) \mid |X| = n\] = \sum\_{x\in\mathcal{X}\_n} \operatorname{Pr}\[X=x \mid |X| = n\] \cdot T(x)$

given some random distribution for random variable $X$.

*Average* runtime is more specific and corresponds to

$\qquad\displaystyle \overline{T}(n) = \frac{1}{|\mathcal{X}\_n|} \cdot \sum\_{x\in\mathcal{X}\_n} T(x)$

or, in other words, the expected runtime given a uniform distribution over inputs of the same size.

Since we *usually* use the uniform distribution the terms are often used interchangeably in algorithm analysis.

One famous exception is the analysis of binary search trees. As opposed to averaging height over all rooted binary trees, we calculate the expected height w.r.t. the uniform distribution of different insert sequences ("random permutation model"), which assigns some (shapes of) trees a higher probability than others. That is not a technical detail: the average height of rooted binary trees is in $\Theta(\sqrt{n})$ whereas the expected height of BSTs in the random permutation model is in $\Theta(\log n)$.
> 4 votes

# Answer
In statistics, the average is often used as an *estimator* for the expected value of a random variables. It is a reasonable choice because this way of estimating the expectation of a random variable whose distribution is unknown, is unbiased and converges to the true value of the expectation. Perhaps that's the motivation to treat both as being the same.

Note: The expectation (or expected value) of a random variable $x$ is usually defined as follows: Let $X$ be the set of all possible values for $x$ and $p(x)$ be its density function. Then $$ E\[x\] := \sum\_X x\cdot p(x) $$

is the expectation of $x$. Change the sum to an integral if $X$ is uncountable, (e.g. if $X = \mathbb{R}$) If you don't know $p(x)$ you can apply Laplace's Principle of Insufficient Reason and assume each value of $x$ to be equally likely, i.e. $p(x) = \frac{1}{n}$ where $n=|X|$. Substitute into the above formula for the expectation and you have the formula for (arithmetic) average.
> 1 votes

# Answer
If you are studying a Randomized algorithm, then expected cost or expected time complexity is a natural metric to analyze the cost or complexity of the algorithm. To understand this concept you need a brief background of Probability theory (concepts like Random variable, Expectation etc.).

By **expected cost** it means that what is the value of the cost in expectation. Generally the cost is represented as a **random variable** and then its **expectation** is computed to find the expected cost. And, surprisingly for any input of the algorithm the expected cost is same.

On the other hand, the average cost is computed for a deterministic algorithm by taking the average of the costs over all the inputs.

P.S: These concepts could be described in a clearer way in the context of specific algorithms. Thus it's better to provide more information like which algorithm you are studying.
> 0 votes

# Answer
Strictly speaking, *expectation* is a property of a probability distribution whereas an average is a simple function computed from a set of numbers (typically, their mean).

However, in typical CS language, these terms are often confused. The "average running time" can either refer to the expected runtime when considering a random input, or in the case of randomized algorithms, it could mean the expected runtime given a specific input. In the latter case, the expectation is computed over all possible coin flips that the algorithm tosses.
> -2 votes

---
Tags: terminology, algorithm-analysis, average-case
---


# Question
Title: Is there C++ code that takes infinite time to compile?
Is C++ as a formal language recursively enumerable? If yes, is there any invalid C++ code that takes "infinite" time to compile?

# Answer
In theory this code should compile infinitely

```
template<long long K>
struct t {
  enum { value = (K&1) ? t<K+1>::value : t<K-1>::value};
};
int main() {
  int i = t<1>::value;
}

```

But in real life compilers are limiting template instantiation depth. Another thing is that long long is limited so you cannot represent all integers.
> 4 votes

---
Tags: computability, compilers, semi-decidability
---


title: How to cluster a large movie dataset ??

text:
# Question
Title: How to cluster a large movie dataset ??
I have to cluster a movie dataset of 10000 movies. A movie has attributes like Genres, Actors, Directors, Year. Earlier I thought that we can use a simple clustering algorithm like k-medoids and the distance can be pre-computed between two movies by subtracting genres & actors.

```
Initialise
d(movie1, movie2) = 0

d(movie1, movie2) -= number of common genres
d(movie1, movie2) -= number of common actors
d(movie1, movie2) -= 1 (if they have a common director)
d(movie1, movie2) -= 1 (if they belong to same decade)

```

Is this approach correct ? Is k-medoids fast enough to cluster this dataset (I doubt it isn't) ? If it isn't fast enough any better clustering algorithm and strategy to cluster this dataset ?

# Answer
> 1 votes
Distances have to be non-negative. Your distance metric leads to a negative distance value, which is not allowed. A better distance metric would be "the number of genres where they don't agree, plus the number of actors where they don't agree".

As far as how well this will work, the only way to find out is to try it and see.

---
Tags: machine-learning, cluster
---