Complexity classes pertaining to listing all solutions? I was reading a question over at Stack Overflow asking whether it was NP-hard to list all simple cycles in a graph containing a particular node and it occurred to me that I couldn't think of any existing complexity class that was well-suited for talking about problems of the form "list all solutions to this problem." The class NP in some sense consists of problems that ask whether at least one solution exists, the class FNP asks to produce a single solution, and the class #P asks to count how many solutions there are, yet none of these deal with the complexity of exhaustively enumerating all possible solutions.

Is there a complexity class for describing problems that are of the form "given a polynomial-time computable predicate $P(x, y)$ and a string $x$, enumerate all $y$ for which $P(x, y)$ is true subject to [insert some appropriate complexity restrictions]?" I understand that it might be tricky to pin down the restrictions given that the number of solutions might be exponentially larger than the size of the input $x$, though that doesn't seem insurmountable.

The concept you are looking for is called enumeration complexity, which is the study of the computational complexity of enumerating (listing) all the solutions to a problem (or the members of a language/set). Enumeration algorithms can be modeled as a two step process:a precomputation step and an enumeration phase with delay. Both of these steps have their own time and space complexities (perhaps entropy, too). In the general spirit of complexity, there are often trade offs between these to consider.

The precomputation step performs some work that is necessary before the first solution is enumerated. This might involve finding the solution itself or initializing some large data structure that will reduce the overall delay between each solution.

The delay is the resource cost associated with the computation necessary in between arbitrary enumerated solutions. In other words, the delay is a measure of the space and time needed to produce the $i+1^{th}$ solution after the $i^{th}$ one. Problems whose solutions that take $O(1)$ time for each enumeration are said to have constant delay. A requirement of $O(poly(n))$ time is said to have polynomial delay.

For the enumeration problem you specifically mentioned in your question, you should look into the class $ENUM_{NP}$ and its related siblings in section 2.1 of "Enumeration: Algorithms and Complexity" by Johannes Schmidt (Linked at the bottom).

Why do we care about precomputation time and delay?

Delay is very key to understanding the true intricacies of enumeration problems. Enumerating the elements of $\Sigma^*$ (up to size $n$) and $\{ \vec{x} : \phi(\vec{x}) \}$ where $\phi(\vec{x})$ is a Boolean formula (i.e. SAT) both take exponential time. However, enumerating through $\Sigma*$ only requires constant delay since you can just go through the elements in some order. For all we know, the delay for enumerating solutions to a 3SAT instance could be exponential. Our job as complexity theorists is to capture why the latter problem is fundamentally harder (more complex) than the former one. Delay does a pretty good job at showcasing this difference.

Likewise, we also need to know how much precomputation is done. We can reduce the delay for any enumeration problem to constant time and space by precomputing all solutions and storing them in a list to be enumerated at a later time. The challenge is to find the best balance between the two resources.

The order in which you enumerate the elements can also influence the complexity. Requiring results to be returned in a specified sorted order might require us to perform additional computation in both steps. Though situations where any order suffices (as long as each enumerated element is unique) are certainly studied, too.

As far as I know, these classes do not typically have concise labels (akin to $P$ and $NP$). We cannot feasibly expect to be able to do this since enumeration complexity classes are juggling around 3 or more resources (precomputation/total time, space, delay, and entropy). There are simply too many combinations of resource bounds to hand out special names. This does not make these classes any less interesting and also does not stop researchers from trying anyways.

Resources

This survey (really an attempt at formalization) should help you get started. It also proves some basic hierarchy theorems.

Enumeration: Algorithms and Complexity
(Johannes Schmidt, 2009)

https://www.thi.uni-hannover.de/fileadmin/forschung/arbeiten/schmidt-da.pdf

For an enumeration of results in enumeration complexity, check out this compilation curated by Kunihiro Wasa. Since it is categorized by problem type, you can easily find a number of papers dedicated to enumerating graph cycles. It should be simple to modify the algorithms involved to only consider cycles with a given node.

http://www-ikn.ist.hokudai.ac.jp/~wasa/enumeration_complexity.html


Is there a way to combine linear equation and inequalities into same equation in order to optimise software calculations? I’m programming web application which has some tricky calculations and I would need some help with mathematical calculations.
What I'm trying to calculate:
I have number of items. Lets call items a1, a2, ..., an. Each item consists of three components (let's call them x, y and z). Components have a ratio which is percentage. Sum of that ratio is always 1 (or 100%).
There is individual amount of each item and each item has unique tolerance/range +- % (min - max).
Then I have target ratio (x, y and z). I need to figure out what amount of each item must be to find combination which forms target ratio. Items amount must be between their minimum and maximum values. Combined items forms overall x, y and z values with should match target x, y and z
Here is an example how I started to solve the problem:
Item 1:
Amount: 100
Tolerance: +-30%
x = 0.25, y = 0.50 and z = 0.25
Minimum amount: 100% - 30% = 70% -> 100 x 0.7 = 70
Maximum amount: 100% + 30% = 130% -> 100 x 1.3 = 130
(Here 70% and 130% are coming from tolerances and after that min and max amounts can be calculated
Item 2:
Amount: 250
Tolerance: +-25%
x = 0.15, y = 0.30 and z = 0.55
Minimum amount: 100% - 25% = 75% -> 250 x 0.75 = 187.5
Maximum amount: 100% + 25% = 125% -> 250 x 1.25 = 390.6
Item 3:
Amount: 180
Tolerance: +-40%
x = 0.40, y = 0.40 and z = 0.20
Minimum amount: 100% - 40% = 60% -> 180 x 0.6 = 108
Maximum amount: 100% + 40% = 140% -> 180 x 1.4= 252
I have a target ratio.
In this example let the target ratio be:
x = 0.25, y = 0.40 and z = 0.35
I need to find what the amount of each items should be in order to form the target ratio and the items must be in their tolerance ranges (between min and max).
Because of each items has 3 components, without min/max amount the combination can be easily calculated (multiplier for each item) with 3 equations below by using linear equation.
Item 1 = a1, item 2 = a2 and item 3 = a3:
0.25 a1 + 0.50 a2 + 0.25 a3 = 0.25      <- target x = 0.25
0.15 a1 + 0.30 a2 + 0.55 a3 = 0.40      <- target y = 0.40
0.40 a1 + 0.40 a2 + 0.20 a3 = 0.35      <- target z = 0.35
After calculating linear equation I get ratio of items:
a1 = 0.375, a2 = 0.375 and a3 = 0.25 meaning that a1 = 37.5%, a2 = 37.5% and a3 = 25.0% of overall amount of items. Now x, y and z match with target ratio. At this point I haven't used the minimum or maximum values.
Below is the link to online calculator which I now used to calculate factors using linear equation for test purposes:
(Also note that I used a, b and c for item/variable names instead of a1, a2 and a3 in online calculator).
Link to online calculator
In this example there are 3 variables/items and 3 equations. Two problems: min/max is not included and there can be for example 10 items/variables in equation. Then the linear equation doesn't work anymore because there are much more items/variables than equations.
I'm not sure how but these min and max amount's must be added to the same equation (and is it possible to form a matrix):
a1 >= 70       <- item 1 minimum amount
a1 <= 130      <- item 1 maximum amount
a2 >= 187.5    <- item 2 minimum amount
a2 <= 390.6    <- item 2 maximum amount
a3 >= 108      <- item 3 minimum amount
a3 <= 252      <- item 3 maximum amount
And this is my problem. I have no idea how to combine these together (inequalities and linear equations or am I going totally wrong direction?). I need to be able to get values for a1, a2, a3, …, an. And I need at least one suitable solution (combination) if there is any solution also when there are multiple or infinite amount of solutions.
If someone can help I would be very grateful! Thanks for your time!

I find it hard to tell from your question, but your problem sounds like it might be an instance of linear programming, in which case there existing solvers you can use.


Minimize the maximum component of a sum of vectors I'd like to learn something about this optimization problem: For given non-negative whole numbers $a_{i,j,k}$,
find a function $f$ minimizing the expression

$$\max_k \sum_i a_{i,f(i),k}$$

An example using a different formulation might make it clearer:
You're given a set of sets of vectors like

{
    {(3, 0, 0, 0, 0), (1, 0, 2, 0, 0)},
    {(0, 1, 0, 0, 0), (0, 0, 0, 1, 0)},
    {(0, 0, 0, 2, 0), (0, 1, 0, 1, 0)}
}

Choose one vector from each set, so that the maximum component of their sum is minimal.
For example, you may choose

(1, 0, 2, 0, 0) + (0, 1, 0, 0, 0) + (0, 1, 0, 1, 0) = (1, 1, 2, 1, 0)

with the maximum component equal to 2, which is clearly optimal here.

I'm curious if this is a well-known problem and what problem-specific approximate solution methods are available. It should be fast and easy to program (no ILP solver, etc.). No exact solution is needed as it's only an approximation of the real problem.

I see that I should have added some details about the problem instances I'm interested in:

$i \in \{0, 1, \ldots, 63\}$, i.e., there're always 64 rows (when written as in the above example).
$j \in \{0, 1\}$, i.e., there're only 2 vectors per row.
$k \in \{0, 1, \ldots, N-1\}$ where $N$ (the vector length) is between 10 and 1000.

Moreover, on each row the sum of the elements of all vectors is the same, i.e.,

$$\forall i, j, j':\quad \sum_k a_{i,j,k} = \sum_k a_{i,j',k}$$

and the sum of the elements of the sum vector is less than its length, i.e.,

$$\sum_k \sum_i a_{i,f(i),k} < N$$

We cannot discuss the complexity of a problem when the problem size is fixed to a constant, because (most part of) the complexity theory deals with the asymptotic behavior of the complexity of the problem as the problem size tends to infinity.  Here, I consider both the number of rows and the dimention of the vectors as variables.

Then the problem is NP-complete even if the numbers in the input are given in unary.  This is not an answer to your question because you are asking about approximation, but it is something.

Define the problem rigorously:

Instance: n pairs of vectors ai, bi ∈ ℕm (i ∈ {1, …, n}), and K ∈ ℕ, all in unary.
Question: Can we choose either ai or bi for each i so that the sum of these n vectors has at most K in each coordinate?

The following is a known NP-complete problem called 3-partition:

3-partition
Instance: B ∈ ℕ, and 3k integers c1, …, c3k between B/4 and B/2, exclusive, such that ∑i=13k ci = kB, all in unary.
Question: Can the multiset {c1, …, c3k} be partitioned into k multisets S1, …, Sk such that the sum of each Sj is equal to B?

Given an instance (B; c1, …, c3k) of the 3-partition problem, construct an instance of the above problem as follows.  For each i = 1, …, 3k and j = 1, …, k, we will construct a pair of 4k-dimensional vectors, representing the choice on whether ci belongs to Sj or not:

The vector representing the choice “ci ∈ Sj” has only one nonzero entry, which is (k−1)ci at the jth coordinate.
The vector representing the choice “ci ∉ Sj” also has only one nonzero entry, which is B at the (k+i)-th coordinate.

It is not hard to see that the instance (B; c1, …, c3k) of the 3-partition problem has a solution if and only if there is a way to choose a vector from each of the 3k2 constructed pairs so that all the coordinates of the sum of these vectors are at most (k−1)B.  (In fact, when this happens, all the coordinates of the sum are equal to (k−1)B.)  So this is a reduction from the 3-partition problem to the above problem.

So far, I ignored the two additional constraints stated at the end of the question, but both are easy to enforce by modifying this reduction slightly.  The condition that the sum of the elements of each vector is equal can be enforced by appending dummy coordinates which contain only 0 or 1.  The condition that this sum is less than the dimension can be enforced by appending dummy coordinates which contain only 0.


What's the difference between subtyping and inheritance? In object-oriented programming, I have learned the concept of subtyping and inheritance.
I thought they're the same thing, in the beginning. But I was told that they're totally different.

So what's there difference? What's there relationship?

See the following discussions in other stack exchange groups.

See discussion in https://stackoverflow.com/questions/23592131/what-is-the-difference-between-subtyping-and-inheritance-in-oo-programming

Also see https://cstheory.stackexchange.com/questions/10620/how-does-inheritance-differ-from-subtyping

However there is some differences of opinion. See Inheritance Is Subtyping as well as Inheritance Is Not Subtyping


Is there any relationship between time complexity and space complexity of an algorithm? For example:

If algorithm A takes an input of size n, and has a time complexity of O(a^n) and a space complexity of O(1)

Is there a way to increase the space complexity to something like O(n^2) that would guarantee that the time complexity would decrease?

If algorithm A takes an input of size n, and has a time complexity of O(a^n) and a space complexity of O(1)

First of all we do not know any exponential or sub-exponential time algorithm that requires only $O(1)$ space, having said this, it is difficult to reason about a hypothetical algorithm "A" because the spatial and temporal complexity are closely linked to the functioning of the algorithms and are (generally) proportional to each other, however, the answer to your question is no.

Let's try to reason starting from a $3SAT$ instance. Now we know that $3SAT$ is NP-Complete (best known time complexity for $3SAT$ is currently $O(k^n)$ with $ K=1.439$ for a deterministic algorithm)  and $3SAT$ $∈$ PSPACE , in fact space complexity of $3SAT$ is $O(n)$. Now it is difficult to imagine how increasing the space to a constant $k$ (in your question $k = 2$) may lead to a decrease in the execution time of the algorithm that solves $3SAT$ ... in fact always keep in mind that an increase in space also corresponds to a proportional increase over time.
Let me conclude by recalling the relationships between temporal and spatial complexity classes for which we believe all inclusions to be strict:

$L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆EXPSPACE$


Algorithm for storing polygon edges into grid Is there any algorithm which takes edges (given by its two end points), and determines in which cell (or cells) of grid it is?

Grid has fixed dimensions and number of cells. Grid is represented by its cells with matrix. And every cell has list of edges that intersect that cell.

Input is set of pair points, but I can also transform it in just set of points, or any other needed representation.
Output should be the mentioned grid with cells who contain list of edges that intersect that cell.

Algorithm should be fast and robust, and by that I mean it covers special (degenerated) cases and that its time complexity is good.

What I want to be able is to use that grid later for search, for example to answer me question like "Which cells does given edge AB(with end points A and B) intersect?" or "Give me all edges that intersect cell 12"(First row, second column).

Bresenham's method is one possibility, however do be aware that as originally presented, it produces the best discrete approximation to the line, which isn't exactly what you want. You want the grid cells which include the polygon, which means that (say) left-edges should be rounded down and right-edges should be rounded up. Wu's algorithm effectively enumerates all of the cells which a line passes through, so it would probably be easier to modify that.

Do bear in mind that on a lot of modern CPUs, floating point arithmetic is extremely efficient compared with integer arithmetic, especially now that we have SIMD execution units. It can actually be more efficient in some cases since the register file and execution units for floating point are typically independent of those used for integer computations. Bresenham is still important, of course, but it's probably worth considering other methods.

Another algorithm that may be worth considering is Pineda's method, which is used by many (if not most) GPUs to scan-convert triangles into fragments. The question asked about polygon edges specifically, not the interior of polygons, but you might find some useful ideas there.

If raw speed is important, one advantage of Pineda's method is that you can enumerate which 4x4 cells the polygon touches, and then calculate individual grid entries in parallel using SIMD arithmetic. This should be very fast on modern hardware.


Equivalence of two lambda expressions for NOT I've seen two different lambda expressions for the logical NOT function.
One of them just applies its parameter to constants true and false internally in a reverse order:

$NOT \;\;=\;\; \lambda x.\; x \; \mbox{false}\; \mbox{true} \;\;=\;\; \lambda x. \; x \; (\lambda t.\lambda f.f) \; (\lambda t. \lambda f. t ) $

and the other one which captures two more parameters instead of passing them to the returned function externally, and applies $x$ to them in reverse order too:

$NOT \;\;=\;\; \lambda x. \; \lambda t.\lambda f.xft$

of which the other one seems a bit simpler (and it is also simpler when encoded in binary).

So my question is this:
Is there any transformation which could get me from one of these representations to the other?

I see they are equivalent "extensionally", that is, both produce the same results. But I'd like to "prove" it somehow by algebraic transformations, such as those for alpha, beta and eta conversions. Unfortunately, none of these can help me in this case: Alpha is just for renaming. Beta works only for function calls, but we don't have any function call here which could be reduced, since $x$ is free in the function body (not the whole expression, though) in all these expressions until we actually call NOT on something. The most close one seems to be the eta, which is related to extensional equivalence and forwarding parameters, but when the parameters are being reversed, it's not a simple forwarding anymore and eta doesn't seem to apply here.

Is there any more conversion rule I'm missing?
(Well, I guess they won't just skip two Greek letters from no particular reason, wouldn't they?)

P.S.: This question is actually a model one, since there are many other definitions for other functions which have several different forms which seem to be extensionally equivalent, but completely different with regard to the known reduction rules. I've chosen the simplest example of this problem.

Edit:
To better clarify what I'd like to know, here's a diagram showing the reduction steps for both versions of the not function:
http://sasq.comyr.com/Stuff/Lambda/Not.png

As you can see, they really both reduce to the same results (contrary to what @Jonathan Gallagher was saying below). This is what I already know: that they are confluent, and so they're Church-Rosser equivalent. What I don't know however is if there is any conversion rule (similar to alpha, beta & eta) which could allow me to transform one form of not to the other. This would allow me to at least make sure if some other functions (more complicated than these two here), are also equivalent, which could be hard when they can reduce to more than just two possible answers. I'd like to know if there's some conversion rule which could allow me to convert one intensional definition into another when two functions are already extensionally equivalent (i.e. they give the same results for the same parameters). Or (which would be better) if some function can be converted somehow to the other even if I don't know whether they're extensionally equivalent.

In order to prove the two NOT forms are not generally equivalent, all you have to do is find a term that when each is applied, returns a different result such as:

$NOT1 \; \lambda x.\; x \; \;\;=\;\; (\lambda x. \; x \; (\lambda t.\lambda f.f) \; (\lambda t. \lambda f. t )) \; \lambda x.\; x \;\; =\;\; \lambda x. \; x \; $

$NOT2  \; \lambda x.\; x \; \;\;=\;\; (\lambda x.\lambda t.\lambda f.xft)  \; \lambda x.\; x\;\; =\;\; \lambda t.\lambda f. ft \; $


Dijkstra Counter Example I an brushing up on Dijkstra (specifically Wikipedia's pseudocode) and can't resolve this counter example. I want the shortest path between A and E. I would move from A to C to D, where D would have a cost of 105. Once I mark D as visited I no longer have an opportunity to find the correct path A to B to D to E. What am I missing?

initially you have:
Q={A, B, C, D, E}
dist(A)=0, dist(B)=dist(C)=dist(D)=dist(E)=inf
previous(A)=previous(B)=previous(C)=previous(D)=previous(E)=undefined

from Q the vertex with min distance is A. Therefore you choose A and you do
(dist(A)+length(A,B)

your remove A from Q, now you have
Q={B, C, D, E}
In Q the vertex with the min dist is C with dist(C)=5, so you pick C
the only vertex adjacent to C is D so you have
(dist(C)+length(C,D)

you remove C from Q, now you have
Q={B, D, E}
the vertex with the min dist in Q is B so you pick B
(dist(B)+length(B,D)

you remove B from Q, now you have
Q={D, E}
the vertex with the min dist in Q is D so you pick D
(dist(D)+length(D, E)

you remove D from Q, now you have
Q={E}
the vertex with the min dist in Q is E so you pick E
No neighboors
remove E from Q
Q is empty and the algorithm terminates
previous(E)=D
previous(D)=B
previous(B)=A
so this is your shortest path from A to E

I skipped the distance checking for the previous vertex for simplicity (it is always equal), the algorithm performs this check. I think you confuse picking a vertex from the set Q and changing the distance of a vertex. They are two different things. The fact that you are assigning a distance at some point to a vertex does not mean that it will be final. It will be final only when this vertex have the minimum distance in the set Q and it will be the one to be picked next and removed. I hope I am clear.


How to pass comma separated values from yacc to cpp file node I am writing a compiler in CPP using Flex and Bison and having trouble understanding passing values up the syntax tree in bison.
I have grammar like this below,  'exp' would evaluate to any number.
args_list: exp | args_list comma exp;
array_list: datatype identifier '[' number']' equal '{' args_list'}'{$$ = new array_node($1, $2, $4, $8);}

I wanted to pass args_list to the array_node but not getting how to pass? As you can see user can initialize array with any length but how to pass this list to CPP node?
for example - int a[4] = {1,2,3,4} ; I want to pass something like
new array_node(datatype, a, number, args_list)

in which I am not getting how to pass args_list so that I can have array type.
Or please suggest me another way to pass the array list to the cpp file. or how to pass whole array to cpp file from yacc?

args_list’s type can be vector.
Then, instead of calling to new array_node you can have a factory method (array_node::factory) which parses the type, casts the args and returns the array_node object


Algorithm for solving system of congruences I'm trying to understand an algorithm shown in my textbook for solving a system of congruences. The problem states:

Let $r$ and $m$ be arrays of size $n$, such that every two numbers (modulos) from $m$ are coprime. Find $x$ such that

$$x \bmod m_0=r_0\\x \bmod m_1=r_1\\...\\x \bmod m_{n-1}=r_{n-1}$$

So yeah, the classic congruence system problem. The naiive approach is shown first and then comes this:

  Let $M = m_0 \cdot m_1 \cdot ... \cdot m_{n-1}$. Let's assume we can
  find the numbers $w_0, w_1, ...w_{n-1}$ such that $w_i \bmod m_i = 1$
  and $w_i \bmod m_j = 0$ for $i \neq j$. So we're finding numbers $w_j$
  such that it is divisible by every number except for $m_j$ where the
  remainder is $1$. Then the solution x can be constructed as: $$x =
 r_0\cdot w_0  + r_1\cdot w_1 + ...+r_{n-1}\cdot w_{n-1} (\bmod M)$$

Well I guess my question is simply - why? I can't seem to reason this out.
It seems to me that $x$ is always going to be zero. If we take the sum given above and break it up into sums
$$(r_0\cdot w_0)\bmod M + (r_1\cdot w_1)\bmod M + ...$$

it seems like everything should be zero? Let's take the first expression $(r_0 \cdot w_0) \bmod M$. We've got $r_0$ times something that's a multiple of every $m$ except for $m_0$ (because of the way the numbers $w$ were defined), meaning that whole thing will be a multiple of every $m$ except for $m_0$. And then we're taking a modulo $M$ which is also a multiple of every $m$.

How does this give us a solution? The textbook is pretty vague about this and doesn't explain why it works this way. So, any ideas?

Thanks.

It is often less confusing to refrain from using congruences and simply write what it means in extension. I.e. when the textbook says to take an $x$ which is equal modulo $M$ to $r_0\cdot w_0 + \dots + r_{n-1}\cdot w_{n-1}$, it means that any $x$ of the form $x=r_0\cdot w_0 + \dots + r_{n-1}\cdot w_{n-1} + k\dot M$, with $k\in \mathbb{Z}$, is a solution. Under this form it should be clearer that $x$ is indeed a solution since $\forall i\in \mathbb{N}_n,x\equiv_{(m_i)}r_i\cdot w_i + \sum_{j\neq i}r_j\cdot w_j+ k\cdot M\equiv_{(m_i)}r_i$ (as $m_i|M$, $w_i\equiv_{(m_i)}1$, and for $j\neq i$ $m_i|w_j$).


What type of algorithms are faster with a quantum computer? I am a beginning CS student and I am learning algorithms. I heard that even with quantum computers, that general sorting algorithms can never have better than $n\log n$ time. However, I also know that factoring algorithms would be a lot faster. In general terms what kind of algorithms would become substantially faster with quantum computers?

Shor's algorithm which puts FACTORING in BQP (bounded error quantum polynomial-time, effectively the quantum equivalent of P) also can be used to solve the DISCRETE LOGARITHM problem, where we want to find an integer $k$ such that $a^{k} = b$ where $a$ and $b$ are given, in (quantum) polynomial time. The DISCRETE LOGARITHM problem has the same status as the FACTORING problem in that we don't know whether they are polynomial-time solvable, so this might not be a speed up.
Grover's algorithm gives a quadratic speed up in searching unsorted lists (which can be used as a speed up for a lot of algorithms).
Simulating quantum systems is also in BQP, but exponentially slower on a classical TM.
Solving Pell's equation (not really one equation) is in BQP, another exponentially speed-up.
There's also a number of other, more obscure, problems that are in BQP, but appear not to be in P. Wocjan and Zhang give a good starting point to dig them up.


If the integer representation used is "0 through 4,294,967,295 (2^32 − 1)", so does this mean the register cannot handle negative numbers? From Wikipedia:

A 32-bit register can store 2^32 different values. The range of integer values that can be stored in 32 bits depends on the integer representation used. With the two most common representations, the range is 0 through 4,294,967,295 (2^32 − 1) for representation as an (unsigned) binary number, and −2,147,483,648 (−2^31) through 2,147,483,647 (2^31 − 1) for representation as two's complement.

So if the integer representation used is "0 through 4,294,967,295 (2^32 − 1)", so does this mean the register cannot handle negative numbers?

From a similar standpoint, if the integer representation used is "−2,147,483,648 (−2^31) through 2,147,483,647 (2^31 − 1)", so does this mean that the register cannot handle numbers greater than 2,147,483,647?

The contents of a register don't have any inherent semantics.
Some instructions might assume certain semantics. For example, the x86 ADD instruction assumes that the registers represent integers, either unsigned or signed using two's complement. There are signed and unsigned versions in the x86 architecture for the multiplication instructions. Another unlikely place in which sign makes a difference is promotion instruction, in which a smaller register is assigned to a larger register – you want either zero extension (in the unsigned case) or sign extension (in the signed case, assuming two's complement).
What this all means is that certain the instruct set favors some interpretations by having instructions that assume them, but beyond that, the interpretation of the data stored in a register is completely up to the user. Moreover, in x86 at least, the same register can be used for both signed and unsigned operations. The register doesn't "know" which type of data it stores – it is completely up to the programmer. (One could imagine different architectures with different conventions.)


What is one method used to prove each palindrome is in its own Myhill-Nerode equivalence class? I understand how you can use a contradiction in regard to a DPDA to show a language has finitely many Myhill-Nerode equivalence classes, but what is the method used to show each string of a language accepting palindromes is in its own Myhill-Nerode class?

Thanks

There is no "method". You need to use an ad hoc proof, that for each pair of words $a,b$ comes up with a word $w$ such that either $aw \in L$ and $bw \notin L$ or vice versa. We can assume that $|a| \geq |b|$.

If $b$ is not a prefix of $a$ then $aa^R \in L$ but $ba^R \notin L$, since otherwise $ba^R = (ba^R)^R = ab^R$, implying that $b$ is a prefix of $a$.

If $b$ is a prefix of $a$ then $|b| < |a|$, since otherwise $b = a$.
Let $\tau$ be a letter such that $b\tau$ is not a prefix of $a$ (i.e., if $a = bx$, where $x \neq \epsilon$, let $\tau$ be some letter different from the initial letter of $x$). Then $a\tau a^R \in L$ but $b\tau a^R \notin L$, since otherwise $b\tau a^R = (b\tau a^R)^R = a \tau b^R$, implying that $b\tau$ is a prefix of $a$.


Converting recursive algorithm to DP As a follow-up to this question
, I've found a recursive algorithm that solves the given problem, but it runs too slow to pass all given tests.

int solve(int i, int crane1_pos, int crane2_pos, int dist)
{

    if(i == n)
    {
        return dist;
    }

    int dist1 = dist + get_dist(crane1_pos, t[i].first);
    int dist2 = dist + get_dist(crane2_pos, t[i].first);

    return min(solve(i + 1, t[i].second, crane2_pos, dist1), solve(i + 1, crane1_pos, t[i].second, dist2));

}

Where, get_dist is a function that looks like this:

int get_dist(int crn_pos, int fin_pos)
{
    if(crn_pos == -1)
        return 0;

    return abs(crn_pos - fin_pos);
}

$t$ in this particular situation is a vector of pair<int, int>, $n$ is the size of this vector and the initial call of the function is solve(0, -1, -1, 0).

I'm pretty sure this could be further improved by using DP, but upon doing some research on this issue, I found that I'm unable to transform this recurrence into some form of dynamic programming. I've derived the recurrence trees for several examples and I can't find the overlapping subproblems and a way to use memoization.

So I guess my question is, how do you turn this recurrence into DP?

Didn't look at your code, but in general there are two important points that distinguish recursion from dynamic programming.

First recursion is top-down (starting with the big instances, by decomposing them into smaller instances and combining the answers) while DP is bottom-up (first solving the small cases, and combining them into larger ones).

The second important point is the table that contains the solutions to instances with certain parameters. This is to avoid computing certain cases more than once (as recursion tends to do).

So DP is upside down recursion in general. But one can also start with recursion and a lookup table that tests whether a certain subproblem was already solved.


Pseudo-random role assignment I have a number of players, ranging from [0..N].  Each round every player is assigned a specific role, either 1, 2 or 3.  floor(N / 8) role 3's are assigned, floor(N / 4) role 2's are assigned and the rest are assigned role 1's.

At the moment, I pick people completely at random for roles 3 and 2, however, this has the issue that some people can go many, many rounds without getting a specific round.  Although the algorithm is "random", people may still get annoyed at how it seemingly isn't.

I was wondering if anyone knew of a better algorithm which still assigns roles semi-randomly but tries to reduce the chance of someone not getting a role for too long (or, the converse, where it tries to ensure a role is not chosen too often)?

I suspect the biggest problem is going to be the gap between role 3's.  So, one possible approach would be to schedule 8 rounds at a time, and for each block of 8 rounds, make sure that every player gets assigned role 3 exactly once.

This can be done as follows.  For the first round, randomly pick N/8 people to be role 3 in the first round.  Then, randomly pick N/8 people who haven't been picked yet to be role 3 in the second round.  Continue until you have scheduled all of the role 3's for all 8 rounds.   This will ensure that each player is role 3 exactly once in those 8 rounds; and that in each round, exactly N/8 people have role 3.

You could then complete the schedule by randomly scheduling role 2's and role  1's among the remaining people (with the right probabilities).  This would be pretty simple to implement and might be good enough.

What if people start complaining about the role 2's?  Well, you could schedule them nearly-equally, too, with a modest modification.  As before, schedule 8 rounds at a time.  We'll try to ensure each player is assigned role 3 exactly once in those 8 rounds; and that most players are assigned role 2 twice, once in the first 4 rounds and once in the last 4 rounds (but we won't be completely perfect about that).  We'll start by assigning the role 3's as described above and fix their assignment.

Next, we'll assign  role 2's to the first 4 rounds.  In the first round, randomly pick a subset of N/4 people who don't have any assignment in that round, and assign them role 2.  In the second round, out of the people who  don't have any assignment in that round and who haven't been assigned role 2 yet, randomly pick a subset of N/8 of them and assign them role 2.  Continue.  In each round, we find the set of people who don't have a role assigned to them in that round yet and who haven't been assigned role 2 yet, and randomly pick a subset of size N/4  from that set; everyone in that subset is assigned role 2.  In rounds 1-3, it is nearly guaranteed that this set is larger than N/4, so we can pick a subset  of the appropriate size.  In round 4,  this set might be smaller than N/4; if so, assign everyone in that set role 2, and then randomly pick other people who don't have an assignment in that round to be role 2 until you have N/4 role 2a's in that round.  In this way, most people are assigned role 2 exactly once in the 4 rounds, with a few people who get assigned role 2 zero or two times (due to round 4 being imperfect).

Then, do the same for role 2 in rounds 5-8.


Building vertex-edge visibility graph among polygonal obstacles on 2d plane I want to implement algorithm for computing vertex-edge visibility graph among polygonal obstacles, but I can't find any description or scientific paper describing such algorithm. Currently I understand how to extend Lee's algorithm for vertex-vertex visibility graph to compute vertex-edge graph, but I want to achieve better than $O(n^2 log(n))$ complexity. I read paper of Mount and Ghosh about their $O(nlog(n))$ algorithm based on triangulation of free space, and seems it allows extension to produce vertex-edge graph. But that algo has too complicated implementation :)

I wonder if there is a way to extend Overmars and Welzl algorithm $O(n^2)$ or algorithm with similar complexity to produce vertex-edge visibility graph? It's implementation seems to be quite simple. Point me on some papers, links, or describe it here if you can.

I'm not sure if this is what you're after, but here's an $O(n + k)$ approach from J. O'Rourke and I. Streinu, Computational Geometry 10 (1998), pp. 105-120:

  $G_{VE}$ may be constructed in $O(n + k)$ time for a polygon with $n$ vertices and $k$ visibility edges, by a slight modification of Hershberger's algorithm that constructs $G_v$ in this time bound [8] from a polygon triangulation. Supplementing with Chazelle's linear-time triangulation algorithm achieves the claimed bound.


Minimum Length Hamiltonian Path Pair in O(n^2) or better A friend and I have been discussing turning a $O(n^2)$ graph problem's algorithm into $O(n\log n)$, or at least less than $O(n^2)$. And no - this is not a homework question. We've narrowed it down to the following subproblem:

Let $A,B,P,$ and $Q$ be a group of 4 nodes, with coordinates $(x_A,y_A),(x_B,y_B)$,etc... such that:

$x_A$ and $x_P$ are less than both $x_B$ and $x_Q$
$y_A$ and $y_B$ are greater than $y_P$ and $y_Q$.

Let there be an arbitrary cluster of nodes contained within the quadrilateral formed by $A,B,P,$ and $Q$. Find a pair of paths $A\rightarrow B$ and $P\rightarrow Q$ such that:

Every node in the cluster is hit by exactly one of the two paths
The two paths have the minimum possible total (Euclidean) length
The two paths do not intersect
The paths always increase in $x$. That is, if we enumerate path $A\rightarrow B$ as $\{A,(x_1,y_1),(x_2,y_2), ...(x_n,y_n),B\}$, then   $x_i<x_j$ for $0<i<j\leq n$. Also, $x_A<x_1$ and $x_n<x_B$. This property must hold for the $P\rightarrow Q$ path as well.

It is also worth mentioning that no two nodes in the entire problem will have the same $x$ coordinate.

I'm positive some geometric trick will play a huge role in finding the solution. Keep in mind this is just a subproblem and a solution to this in $O(n^2)$ will still be helpful - though I'm hoping for $O(n\log n)$.

Here's an example problem for clarity:

Any solutions or even helpful ideas are always appreciated. Diagrams are also very much appreciated.

Finally, for added clarity, here is what a sample solution might look like:

Since you said a $O(n^2)$ time algorithm would still be useful, there is a straightforward dynamic programming algorithm that runs in time $O(n^2)$.

In particular, a subproblem is specified by a pair of points $(A',P')$; the problem is to find the best pair of paths from $A' \to B$ and $P' \to Q$, using only points that are to the right of both $A'$ and $P'$.  To solve each subproblem, you only have to look at the solution to two subproblems: in particular, to $(Z,P')$ and $(A',Z)$, where $Z$ is the point immediately to the left of the rightmost of $A',P'$.  Therefore, each subproblem can be solved in $O(1)$ time.  As there are $O(n^2)$ subproblems, the $O(n^2)$ running time follows immediately.


Calculating complexity for recursive algorithm with codependent relations I wrote a program recently which was based on a recursive algorithm, solving for the number of ways to tile a 3xn board with 2x1 dominoes:

  F(n) = F(n-2) + 2*G(n-1)

  G(n) = G(n-2) + F(n-1)

  F(0) = 1, F(1) = 0, G(0) = 0, G(1) = 1

I tried to calculate the complexity using methods I know such as recursion tree and expansion, but none resulted in any answer. Actually I had never come across such a recursion, where the relations are codependent.

Am I using the wrong methods, or maybe using the methods in a wrong way? And if so, can anyone offer a solution?

Let us note that $F(n) = G(n+1) - G(n-1)$. Therefore
$$
G(n+1)-G(n-1) = G(n-1) - G(n-3) + 2G(n-1),
$$
implying that
$$
G(n+1) = 4G(n-1) - G(n-3).
$$

Similarly, $G(n) = (F(n+1)-F(n-1))/2$, and so
$$
(F(n+1)-F(n-1))/2 = (F(n-1)-F(n-3))/2 + F(n-1),
$$
implying that
$$
F(n+1) = 4F(n-1) - F(n-3).
$$
These are exactly the same recurrences, though with different initial values.

A simple induction shows that $F(n) = 0$ for odd $n$ while $G(n) = 0$ for even $n$ (this also follows from their semantic meaning).

Using the recurrence, we easily get that for even $n$,
$$
F(n) = (1/2 + 1/2\sqrt{3})(2 + \sqrt{3})^{n/2} + (1/2 - 1/2\sqrt{3})(2 - \sqrt{3})^{n/2}.
$$
Let us comment that this sequence is A001835.

Similarly, for odd $n$,
$$
G(n) = (1/2 + 1/\sqrt{3})(2 + \sqrt{3})^{(n-1)/2} + (1/2 - 1/\sqrt{3})(2 - \sqrt{3})^{(n-1)/2}.
$$
This sequence is A001353.

Alternatively, we can notice that
$$
\begin{pmatrix}
F(n) \\
G(n+1)
\end{pmatrix} =
\begin{pmatrix}
1 & 2 \\
1 & 3
\end{pmatrix}
\begin{pmatrix}
F(n-2) \\
G(n-1)
\end{pmatrix}
$$
It follows that
$$
\begin{pmatrix}
F(2m) \\
G(2m+1)
\end{pmatrix} =
\begin{pmatrix}
1 & 2 \\
1 & 3
\end{pmatrix}^m
\begin{pmatrix}
1 \\
1
\end{pmatrix}
$$
The eigenvalues of the matrix are $2 \pm \sqrt{3}$, and so we are led to formulas as stated above.


Deadlock Solutions: Lock Ordering This is from a textbook on operating systems. This is not homework, just part of the chapter on deadlocks.

transaction(Account from, Account to, Number amount):
    mutex lock1 = getlock(from)
    mutex lock2 = getlock(to)

    acquire(lock1)
    acquire(lock2)
        withdraw(from, amount)
        deposit(to, amount)
    release(lock2)
    release(lock1)

Deadlock is possible if two threads simultaneously invoke thetransaction() function, transposing different accounts. That is, one thread might invoke

transaction(checkingaccount, savingsaccount, 25)

and another might invoke

transaction(savingsaccount, checkingaccount, 50)

What is a good solution to this problem? One I can think of is to use a witness program that will alert the user that a deadlock has occurred, but there must be a better solution implementable by modifying the code. Any ideas?

You simply need to place a total order on the accounts and always lock the accounts in that order.

You define a < operator on Accounts and then change the beginning like this:

mutex lock1 = getlock(from)
mutex lock2 = getlock(to)
if (from < to)
    mutex lockSwap = lock1
    lock1 = lock2
    lock2 = lockSwap

It doesn't matter what order you choose, it just has to stay the same through the whole program.  In C, and other low level languages it is particularly easy to make this kind of < operator because you can just convert the addresses of the objects to integers and do the < on the integers.


Does intersecting the output of 2 programs give the output of another program? Let $S$ be the set of all programs that take integers as input and return integers as output and halt on all inputs. Does there exist a pair of program in $S$, call them $P_1$ and $P_2$, such that there exists no program $P_3$ in $S$ for which the following hold for every integer $y$:

$P_3(x)=y$ for some $x$ iff $P_1(x_1)=y=P_2(x_2)$ for some $x_1$ and $x_2
$.

Let $f$ be a computable bijection from $\mathbb{N}^*$ to $\mathbb{Z}$. For example, $f(1)=0,f(2)=1,f(3)=-1,f(4)=2,\ldots$

Note a non-empty subset of $\mathbb{Z}$ is the range of a program if and only if it is recursively enumerable. On the one hand, the range of a program $P$ can be enumerated by running $P(f(1)),P(f(2)),P(f(3)),\ldots$ On the other hand, for a non-empty recursively enumerable subset $X$ of $\mathbb{Z}$, there exists an enumerator $E$ that enumerates $X$. Suppose $E$ requires $n$ steps to output the first number, we can define a program $P$ that $P(i)$ returns the last number outputted by $E$ within at most $\max\{n,f^{-1}(i)\}$ steps.

Since the intersection of two recursively enumerable sets is still recursively enumerable, your $P_3$ exists if and only if the intersection is not empty.


Why do modern processors need a runtime stack? Professor said that modern processor needs runtime stack.

But he didn't explain the reason.

Why is the runtime stack required in the modern processors?

I would say that "required" is a bit of strong word. Processors provide hardware support for stacks to help implement the call stack abstraction. Having special instructions to do so can improve performance. Note however that some processors like ARM (except in Thumb mode) do not really have special instruction to do so, the ldm/stm instructions with pre/post inc/dec are flexible enough to do so.


Are there any CS-trees named after flora-trees? This is meant to be a fun question, and I hope it's not too off topic. Is there a defined mathematical object or data structure that has a name collision with a type of physical tree in the real world?

In computer science we have red-black trees, B-trees, quadtrees, and so on. In the biological sense of the word tree, we have palm trees, pine trees, redwood trees, etc.

My question: is there a word $w$ such that a $w$ tree could refer to a physical tree in the real world, or a mathematical object?

Robert Tarjan defines the palm tree in "Depth-first search and linear graph algorithms" (1972):

  Let $P$ be a directed graph of two disjoint edge sets, denoted
  $v \rightarrow w$ and $v \overset{-}{\rightarrow} w$ respectively. If $P$
  satisfies the following properties:

  The subgraph $T$ containing the edges $v \rightarrow w$ is a
   spanning tree of $P$;
  Each edge not in $T$ connects a vertex with one of its ancestors in
   $T$.  The edges $v \overset{-}{\rightarrow} w$ are called the fronds of $P$.

e.g.,

He goes on to prove that the directed graph generated by a depth-first search of a connected graph is a palm tree.

In Collective Tree Spanners and Routing in AT-free Related Graphs, Dragan, Yan, and Corneil  construct a specific spanning tree that they call a willow-tree.


Concept of M-augmenting path to find a larger matching than $M$ I'm reading section 16.1 of the book, Combinatorial optimization, Polyhedra and efficiency by Schrijver. Here, he starts with a matching $M$ and describes a path $P$ that is $M$-augmenting if:

The path has odd length (in terms of edges).
Its ends are not covered by $M$.
Its edges are alternately out of and in $M$.

Theorem 16.1 then states that we either have a matching of maximal size or an augmenting path exists.
I don't understand this statement. See the graph below for example. For now, we have the edge between vertices 2 and 5 in a matching $M$. I can't find any path that satisfies the three conditions above. Yet, this is obviously not a maximal matching since the edge between vertices 1 and 4 can be added to increase its size. What am I missing and why is my understanding so way off?
Further, if I'd used 1-4 as my initial matching, it would have been impossible to find a path that satisfies condition 2.

Conversely, I take the graph the the author himself provides as an example of an augmenting path. In the simple linear graph below (which is also a linked list), an augmenting path satisfying the three conditions above exists. However, where is the edge that can be added to this graph to increase the size of $M$?

Actually, I realized what I was missing shortly after posting the question and squinting at the pictures again. Instead of deleting, figured I'd simply post the answer for future reference. The thing I was missing was that the new matching won't have the same edges as the original matching. In the first figure, 3->5->2->4 is such a path and 2->4 $\cup$ 3->5 becomes a larger matching.


What is the difference between Boolean Algebra and Boolean Lattice? What is the difference between Boolean Algebra and Boolean Lattice? I have already searched on Google but could not find a reasonable answer?

According to Wikipedia, these are two names for the same concept. You can differentiate them by stating that Boolean algebra is an algebraic structure having operations $\land,\lor,\lnot$ satisfying certain axioms, and in contrast a Boolean lattice is a lattice having certain properties; but the two definitions are equivalent. Sometimes Boolean algebra and Boolean lattice refer to specific constructions (subsets of a set), but according to Stone's representation theorem these two definitions are also equivalent.


An example of a code that is neither p-code or s-code but is uniquely decodable? As the title says, code can't be a prefix-code and can't be a suffix-code, but it must be uniquely decodable. One possible code is this: {1, 101, 1001, ... }. Number of zeroes corresponds to the index of the letter in a given alphabet (starting from 0). Clearly it's not p-code and not a s-code and it's uniquely decodable. But I need to find another example of such code. And no, I wont accept {0, 010, 0110, ...}. By the way, code words must consist of 0 and 1, i.e. be binary.

An easy way to get new codes of any size is to compose a prefix non-suffix code and a suffix non-prefix code. For instance, start with the prefix non-suffix code $X_5 = \{0, 10, 110, 1110, 1111\}$ and compose it with the suffix non-prefix code $\{0,01\}$, which consists to replace $1$ by $01$ in $X_5$ to get
$$
S_5=  \{0, 010, 01010, 0101010, 01010101\}.
$$
The resulting set is a code that is neither prefix nor suffix.

N.B. The advantage of this method is that you always get codes, no verification needed.


Does CPU without register exist? Is existence of registers in CPU an obligation, Or we just do it for performance?

Can we theoretically and practically have computer architectures that don't use registers?
If yes, please name computer architecture and computer models that doesn't have register.

Update: Do stack machines use register? If yes, is it possible to have stack machines without registers?

Every CPU has, at the very least, some internal registers: a program counter, a register storing flags, and in some architectures, an accumulator (though the latter isn't strictly required).

As you mention, registers are important for speed reasons. CPUs are designed with efficiency in mind. There are no drawbacks to having (external) registers, so I conjecture that all CPUs have them.


Does the Paxos algorithm use failure detectors? Does the Paxos algorithm use failure detectors? If not, how can it solve consensus, given the impossibility result?

In short, the "plain" Paxos algorithm does not use failure detectors, but it can be augmented with failure detectors. Furthermore, the "plain" Paxos algorithm does not fully solve the problem of consensus.

To answer this question more in detail, we first define "the consensus problem". An algorithm "solves" the problem of consensus if it guarantees that the following properties are satisfied:

Termination (or liveness, or progress): all non-faulty processes eventually decide on a value
Agreement (or consistency, or safety): all processes that decide do so on the same value
Validity (or non-triviality): the value that has been decided must have proposed by some process

The "plain" Paxos guarantees that agreement and validity are always satisfied, that is, if you use Paxos to solve consensus, then you will never get as a result processes that decide on different values or that decide on values that have never been proposed.

However, "plain" Paxos does not guarantee termination, that is, if you use "plain" Paxos, then it is possible that processes will never decide on a value. This problem can be (partially) circumvented by using using "leader election", that is, you elect a leader (which must be a proposer in the "plain" Paxos algorithm) which coordinates the proposals. However, the leader can also fail. This failure of the leader can e.g. be detected using failure detectors (which, in practice, may be implemented as "timeouts"). Therefore, Paxos can use failure detectors. But I won't dwell more on this topic.

In conclusion, "plain" Paxos does not fully solve the problem of consensus, because it does not guarantee "progress".


How to remove objects from an array most efficiently? I am wondering if I can rearrange an array faster when I would like to delete more than one object.

You are given a List:

1
2
2
3
4
5
7

And now you want to delete every "2" in the list. So what I would do, is:

int size = 7;
int array[size] = {1,2,2,3,4,5,7};
for(int i = size-1; i >= 0; i--){
   if(array[i] == 2){
      memcpy(&array[i],&array[i+1], size-i);
      size--;
   }
}

But this is not a efficent way doing so, is it?
So I wonder if I could do this on a smarter way without allocating extra memory.

You can maintain a pointer that, in the $i$th iteration, points to the $i$th element that is not 2, i.e., the $i$th element in the final array. In each iteration, we only move the element to which the pointer points to the $i$th position.

int size = 7;
int array[7] = {1,2,2,3,4,5,7};
int i = -1;
int p = -1;
while (1)
{
    ++i;
    do ++p; while (p < size && array[p] == 2);
    if (p >= size) break;
    array[i] = array[p];
}
size = i;

In your example, it works as follows.

Initial: 1 2 2 3 4 5 7
After the 1st iteration: 1 2 2 3 4 5 7
                         i
                         p

After the 2nd iteration: 1 3 2 3 4 5 7
                           i   p

After the 3rd iteration: 1 3 4 3 4 5 7
                             i   p

After the 4th iteration: 1 3 4 5 4 5 7
                               i   p

After the 5th iteration: 1 3 4 5 7 5 7
                                 i   p

After the 6th iteration: 1 3 4 5 7 5 7
                                   i   p


Finding a particular path in weighted tree I have undirected weighted linear tree (path tree) with $n$ nodes ,and
a weight function on edges $\omega: \mathbb{N}\to  \mathbb{N}$,
additionally given $k\in \mathbb{N}$, How we can find a path with
lenght $k$ that have minimum number of edges in $O(n)$?<img src="https://i.stack.imgur.com/HGEwH.png" alt="enter image
description here" />

I think as follow:
Run Bellman Ford for each node and then select a path with length $k$ and minimum number of edges. Unfortunately runtime $\omega(n)$.

The idea is to find, for each vertex $i$, the first vertex $j_i > i$ such that the distance $d(i, j_i)$ between $i$ and $i_i$ is at least $k$.
Then, you can return the pair $(i, j_i)$ such that $d(i,j_i)=k$ and $j_i-i$ is minimized.
This takes $O(n)$ time once you notice that, for $i_1 < i_2$, $j_{i_1} \le j_{i_2}$.
In pseudocode, where $w(\ell, \ell+1)$ denotes the weight of edge $(\ell, \ell+1)$:
i = j = 1
best_i = 0
best_j = n
d = 0

while i != n:
  if d<k and j!=n:
    d = d + w(j, j+1)
    j=j+1
  else:
    d = d - w(i, i+1)
    i=i+1

  if d == k and j - i < best_j - best_i:
    best_i=i
    best_j=j

return best_i, best_j


Which method for ODE instead of Euler's? I need a super-fast method for ordinary differential equations. Should I use the midpoint method? I need this for a reaction-diffusion system (Gray-Scott).

There are lots of methods. I have usually found a 4th order adaptive step size Runge Kutta method to work fairly well. A Leapfrog method might better preserve invariants over the long term. I'm afraid I don't know enough about reaction-diffusion systems to know how that might change my answer. You might look into our sister sites in scientific computing, computational sciences, etc. for more information. If you're not already familiar with the "numerical recipes" series, that could prove very useful, although it may not have anything exactly suited to your needs.


What is "potential speedup" in parallel computing? There is an example problem from p506 of Computer Organization and Design, Fifth Edition: The Hardware/Software interface by David A. Patterson, John L. Hennessy

I wonder how "potential speedup" is defined? The book doesn't give its definition.

In the example, since speedup with $10$ processors is $55\%$ of the potential speedup, the potential speedup should be $ 5.5 / 55\% = 10$. it is equal to the number of processors.

Since the execution time before improvement has a part $(10t)$ unaffectable by parallel computing on multiple processors, according to Amdahl's law (outlined in blue box), the potential speedup must be smaller than the number of processors.

So I am puzzled.

Google books has an earlier (4th) edition which has a similar example too.

Potential speedup $\equiv$ number of processors.  I agree that it is poorly chosen wording.  A better term would be efficiency (the average amount of time that the processors are doing useful work.)


How to model references in an ontology I am interested in creating an ontology which will model arguments (among other things). For example, a triple in the ontology might be

Vaccination -> can lead to -> Autism

(not that I necessarily believe this, just a good example of an argument).
I would like to attach sources to any disputed statement. So ideally, the above example would be stored as

Vaccination -> can lead to -> Autism -> according to -> Article X

This cannot easily be represented as a triple in a standard ontology. What are the accepted ways of modeling this type of data?

I see that on WikiData, all relations can have sources attached to them (e.g. see https://www.wikidata.org/wiki/Q23 for sources on when George Washington was born). It could be that WikiData doesn't store their data as triples.

If you want to say something about an RDF triple (i.e., an rdf:Statement), you can use reification:

@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix voc: <https://example.com/vocabulary#> .
@prefix :    <https://example.com/instances#> .

:Triple42   rdf:type        rdf:Statement .
:Triple42   rdf:subject     :Vaccination .
:Triple42   rdf:predicate   voc:canLeadTo .
:Triple42   rdf:object      :Autism .
:Triple42   voc:publishedIn <https://example.com/articles/vaccination-and-autism> .

But you would probably want to say something about the argument, not about the RDF statement expressing the argument. You can use n-ary relations for this, e.g., by introducing an instance that represents the argument:

@prefix voc: <https://example.com/vocabulary#> .
@prefix :    <https://example.com/instances#> .

:Argument1 a voc:Argument .
:Argument1 voc:publishedIn <https://example.com/articles/vaccination-and-autism> .
:Argument1 voc:textualRepresentation "Vaccination can lead to autism!" .

(and then use properties that dissect the argument to represent it in a machine-readable way)

Relevant vocabularies: PROV, schema:ClaimReview


Why is the class NP-Complete important compared to NP-hard? I'm studying computational complexity and I was wondering why the NP-Complete (NPC) problems is an important class at all. I find it obvious why we're interested in showing a given NP problem is NP-hard.

I also understand the definition of NPC, and that showing a given decision problem is NP-hard, knowing it is in NP, is exactly was NPC means.

However, what I don't understand is: why this concept is so important? Surely, if we find any NP-hard algorithm which runs in time P (whether or not that is in NP), we have shown that $NP = P$.

Why is this concept so important?

There are at least a few reasons that NPC is interesting:

The class NP contains many problems that are interesting (both practically and theoretically), moreover many of these problems turn out to be NP-hard (and hence NP-complete), but many problems outside of NP are almost certainly too hard to be of more than theoretical interest, so NPC provides a (rough) group of problems that are apparently hard, but not so hard that we can't try to do something with them.
In other words, NPC is probably the limit of what we can hope might be polynomial-time solvable, it would seem a stretch to try for PSPACE = P (for example).
The class is NP is structurally interesting. It's the basic example of "do we get any more computational 'speed' from nondeterminism". So we're interested whether P=NP or not, and NPC is (probably) an important component of working that out.
NP-hard (as a class) is really too big and varied to deal with as a single thing, it's everything that can be reduced to from an NP-complete problem, including a huge swathe of stuff outside NP, so from the point of view of trying to develop general results and techniques, there's nothing to grab on to.


Using master theorem to solve recurrence with log I'm not sure how to solve apply the master theorem in order to solve this recurrence:

  $$  T(n) = 4T(n/3) +O(n\log n),\text{ where } T(1) = 1.$$

The master theorem I have been shown is normally used to solve recurrences of the slightly different form
$$  T(n) = aT(n/b) +O(n^d),\text{ where }T(1) = 1.$$

Clearly $c := \log_3 4 > 1$. Choose $1 < d < c$ arbitrarily, say $d = \frac{1+c}{2}$. Then $O(n\log n) = O(n^d)$ and $d < \log_3 4$, and so we can apply the first case of the master theorem.


How partitioning in map-reduce work? Assume a map-reduce program has $m$ mappers and $n$ reducers ($m > n$). The output of each mapper is partitioned according to the key value and all records having the same key value go into the same partition (within each mapper), and then each partition is sent to a reducer. Thus there might be a case in which there are two partitions with the same key from two different mappers going to 2 different reducers. How to prevent this from occurring? That is, how to send all partitions (from different mappers) with the same key to the same reducer?

Let's take a simple example, Counting word into a distributed set of documents:

each mapper takes in input a list of document, and returns a list of pairs word and how many times this word occurs. There is an intermediate layer that takes the outputs of all the mapper and groups values by key. After that the reducer will sum each of this value.
This is a practical example:

Output of 3 mappers

Mapper1
(house,4)
(dog,2)
(cat,1)
Mapper2
(dog,3)
Mapper3
(cat,5)
(house,6)

before give these data to the reducer the intermediate layer will group them by key.
obtaining :

(house, (6,4))
(dog,(3,2))
(cat,(5,1))

After that reducers take in input these pairs and sum values:

Reducer 1
(house ,(6,4))-> (house,10)
Reducer 2
(dog,(3,2)) -> (dog,5)
(cat,(5,1)) -> (cat,6)

The MapReduce idea comes from a paper by google that you can find here:
http://research.google.com/archive/mapreduce.html

reading this article you will notice that the mapper gives in output a list of pairs, but the reducer takes in input a pair of (key , list(value)) this implies that there is something in between that "lists" all values with the same keys. This task is done on the output of ALL the mappers, this task is optimized , sorting values ecc.. but as i say is in practice done on all the mapper.

If you know a little of java i suggest you to try something using the Hadoop framework by Apache

as you can see in the linked example the CombinerFunction(the intermediate layer that i've mentioned) works on the same input of the reducers.


Prove 100,000,000 is a member of the set of functions defined by Big Theta of g(n), where g(n) = 1 So I am trying to work on a problem and honestly... I am so lost with this one. I will try to ask it the best I can.

Exact text of the problem: "Prove the following directly from the definition of Big Theta; 100,000,000 is a member of the set of functions defined by Big Theta of g(n), where g(n) = 1"

Additionally, the definition in question is [Click here to see definition]

Basically, I don't understand the definition and I don't understand the question. I understand that this chapter is talking about asymptotic behavior, and how given 2 different functions these 1 number could "grow" faster than the other up to a certain point and then it would switch. Example, Using 1 and 100,000,000 as n. In the following 2 functions 1 is larger number using 1... and then the other one is larger when you 100,000,000.

1,000,000n and n^2

Perhaps someone can help put the definition and question into words I can understand a little better.

You haven't provided a definition, but here is a standard one:

  Let $f,g$ be functions from $\mathbb{N}$ to $\mathbb{R}$. We say that $f(n) \in \Theta(g(n))$ (usually written $f(n) = \Theta(g(n))$) if there exist a natural number $N$ and positive real numbers $0 < a < b$ such that for all natural $n \geq N$ it holds that $$ ag(n) \leq f(n) \leq bg(n). $$

Roughly speaking, this says that the two functions $f,g$ have the same order of growth – they differ by a constant multiple. The definition is reflexive ($f(n) = \Theta(f(n))$), symmetric ($f(n) = \Theta(g(n))$ implies $g(n) = \Theta(f(n))$) and transitive ($f(n) = \Theta(g(n))$ and $g(n) = \Theta(h(n))$ imply $f(n) = \Theta(h(n))$), and so forms an equivalence relation. Each equivalence class is an "order of growth".

In your question, $f(n) = 10^8$ and $g(n) = 1$. So you have to find natural $N$ and positive reals $0 < a < b$ such that the following holds for all $n \geq N$:
$$ ag(n) \leq f(n) \leq bg(n) \Longleftrightarrow a \leq 10^8 \leq b.$$
I'm sure you can find such $N,a,b$.


Why do we not combine random number generators? There are many applications where a pseudo random number generator is used.  So people implement one that they think is great only to find later that it's flawed.  Something like this happened with the Javascript random number generator recently.  RandU much earlier too.  There are also issues of inappropriate initial seeding for something like the Twister.

I cannot find examples of anyone combining two or more families of generators with the usual xor operator. If there is sufficient computer power to run things like java.SecureRandom or Twister implementations, why do people not combine them?  ISAAC xor XORShift xor RandU should be a fairly good example, and where you can see the weakness of a single generator being mitigated by the others.  It should also help with the distribution of numbers into higher dimensions as the intrinsic algorithms are totally different.  Is there some fundamental principle that they shouldn't be combined?

If you were to build a true random number generator, people would probably advise that you combine two or more sources of entropy.  Is my example different?

I'm excluding the common example of several linear feedback shift registers working together as they're from the same family.

Sure, you can combine PRNGs like this, if you want, assuming they are seeded independently.  However, it will be slower and it probably won't solve the most pressing problems that people have.

In practice, if you have a requirement for a very high-quality PRNG, you use a well-vetted cryptographic-strength PRNG and you seed it with true entropy.  If you do this, your most likely failure mode is not a problem with the PRNG algorithm itself; the most likely failure mode is lack of adequate entropy (or maybe implementation errors).  Xor-ing multiple PRNGs doesn't help with this failure mode.  So, if you want a very high-quality PRNG, there's probably little point in xor-ing them.

Alternatively, if you want a statistical PRNG that's good enough for simulation purposes, typically the #1 concern is either speed (generate pseudorandom numbers really fast) or simplicity (don't want to spend much development time on researching or implementing it).  Xor-ing slows down the PRNG and makes it more complex, so it doesn't address the primary needs in that context, either.

As long as you exhibit reasonable care and competence, standard PRNGs are more than good enough, so there's really no reason why we need anything fancier (no need for xor-ing).  If you don't have even minimal levels of care or competence, you're probably not going to choose something complex like xor-ing, and the best way to improve things is to focus on more care and competence in the selection of the PRNG rather than on xor-ing.

Bottom line: Basically, the xor trick doesn't solve the problems people usually actually have when using PRNGs.


Right moving turing machine I am interested in simulating any turing machine with a turing machine that is allowed only to move right. I guess that it should be pretty standard material and likely it is trivial (or known to be false). Does anyone have a pointer to a reference?

A Turing Machine that can only move right can only read its input once, hence I don't see how it could be more powerful than a DFA.

It does have the ability to write to the tape, but it can't go back to read what it wrote, so this can't be used as memory. I seems that it's essentially equivalent to a Finite State Transducer, which are DFAs that have an output tape as well as input, but are no more powerful. In this case, the TM just happens to overwrite the input as it goes, rather than having a second tape.


Intuition behind this specific algorithm for time series Going through the EPI book and I need some help understanding this part.

There's a problem, 5.7, that deals with buying and selling twice over a single time-series in order to maximise profit. The input is given as a list of ints. The example they give is:

[12, 11, 13, 9, 12, 8, 14, 13, 15]

So here the maximum profit from a single buy-sell event is 7; buy at 8 and sell at 15. From two buy-sell events it is 10; buy at 9, sell at 12 and buy at 8, sell at 15.

The intuition for a single buy-sell is simple where we just keep track of the minimum element in the list and the difference between the minimum and the current element is the profit.

What I don't understand is how the double buy-sell formula works. The book proposes a solution where two passes are made through the data, a forward and a backward pass. The forward pass uses the same formula as above (single buy-sell), but the backward pass starts at the back of the list and keeps track of the maximum instead. The profits of the backward pass are stored in an array and added to the profits of the forward pass with $M[i] = F[i - 1] + B[i]$, and where $F[-1] = 0$.

Why does the backward pass keep track of the maximum, and how does the formula ensure that we won't buy before the second sale?

Here is the solution code given:

def buy_and_sell_stock_twice(prices: List[float]) -> float:
    max_total_profit, min_price_so_far = 0.0, float('inf')
    first_buy_sell_profits = [0.0] * len(prices)
    for i, price in enumerate(prices):
        min_price_so_far = min(min_price_so_far, price)
        max_total_profit = max(max_total_profit, price - min_price_so_far)
        first_buy_sell_profits[i] = max_total_profit
    # Now for the backwards pass.
    max_price_so_far = float('-inf')
    for i, price in reversed(list(enumerate(prices[1:], 1))):
        max_price_so_far = max(max_price_so_far, price)
        max_total_profit = max(
            max_total_profit,
            max_price_so_far - price + first_buy_sell_profits[i - 1])
    return max_total_profit

I broke down the iterator in the reverse pass and it creates:

[(8, 15), (7, 13), (6, 14), (5, 8), (4, 12), (3, 9), (2, 13), (1, 11)]

The expected backwards pass result is also provided for the sample data:

B = [7, 7, 7, 7, 7, 7, 2, 2, 0]

Looking through the code I can see how the algorithm can be used to populate B. What doesn't make sense is why this backwards pass guarantees the max profit, how it guarantees sane buys and sells, and what the intuition is for doing it this way.

I looked at similar questions but they provide different solutions which work great but don't provide any insight on the book's solution. The book is also not readily available online so there is less content on the material.

During the forward pass, you compute F such that F[i] represents the maximum possible profit when restricting yourself to the elements with indices 0,1..,i.

During the backward pass, you compute B such that B[i] represents the maximum possible profit when restricting yourself to the elements with indices i,i+1,..,n-1 (where n is the size of your list). The reason you track the max is that because you are going backwards in time when populating B, you want to sell before you buy.

Now M[i] = F[i-1] + B[i] represents the maximum profit when doing a first buy/sell among indices 0,1..,i-1 and a second buy/sell among indices i,i+1..,n-1, so you are sure that the first sell will happen before the second buy (because the first sell happens at index i-1 at the latest and the second buy at index i at the earliest).

Reciprocally, suppose the optimal solution has two buy/sell's happening at indices b1, s1, b2, s2 (in increasing order). Then you know that M[b2] will be at least as big as the profit achieved by this solution (equal in fact, because it can't be bigger) as b1,s1 happens before index b2, and b2,s2 happens after (or at) b2.

Thus, by taking the maximum over all M[i] you will necessarily hit M[b2] at some point and get the maximum profit. And if the optimal solution has only one buy/sell it will be at M[0] = F[n-1] = B[0] = M[n-1] which you also consider.


Job scheduling approximation In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf

Lemma 5 is given as:

  The approximation factor of the modified greedy [scheduling] algorithm is 4/3.

And gives the example:

  Note that 4/3 is essentially tight. Consider an instance with $m$ machines, $n = 2m+ 1$ jobs, $2m$ jobs of length
  $m + 1, m + 2, · · · , 2m − 1$ and one job of length $m$.

does the above example have an error as a proof of lemma 5?

I have been thinking about it over a day.

The instance in the example is "almost" the right one, however you are right that, as given, it does not prove tightness. The instance is missing two more jobs of size $m$.

After we include these two jobs, we have 2 jobs of each size from $2m-1$ to $m+1$ and 3 jobs of size $m$ (for $n=2m+1$ jobs in total, as stated).

Under the modified greedy algorithm, the maximum load will be $4m-1$. However, one can instead schedule a job of size $2m-i$ with a job of size $m+i$ for each $i=1,2,..., \lfloor  m/2 \rfloor$, and the remaining 3 jobs of size $m$ separately on the same machine. The maximum load will then be $3m$.


Proving number of calls made in cut-rod algorithm I was reading dynamic programming chapter from famous book Introduction To Algorithm

In rod cutting problem it gives simple algorithm as follows:

    cutRod(p,n)
    {
       if (n == 0)
       {
          return 0
       }
       q = -∞
       for (i=1 to n)
       {
          q = max(q,p[i]+cutRod(p,n-i))
       }
       return q
    }

It then says:

  T(n) be the total number of calls made to cutRod() when called with its second parameter equal to n. T(n) equals the number of nodes in a subtree whose root is labeled n in the recursion tree. The count includes the initial call at its root. Thus,

T(0) = 1          and

T(n) = ${\sum\limits_{j=0}^{n-1} T(j)}$

Exercise at the end of this chapters asks to prove from above two that in fact

T(n) = 2$^n$

How can we go about proving this?

You can easily prove this by induction.

Base Case T(0) = 2^0 = 1.

Say T(k) = 2^k. is true for some k.

Hence T(k+1) = T(k) + sum(Ti) {i = 0 to k-1}
             = T(k) + T(k)
             = 2*2^k = 2^(k+1)

Note: By looking at the code, it seems that if you use dynamic programming and memo-ize the T(i)'s from bottom-up, you can make this algorithm into a O(n^2) algorithm.


Computational Complexity of Not All Equal SAT variant Not All Equal SAT is an NP Complete problem. Let us now consider another variant of the problem.

Given a Not All Equal SAT (NAESAT) problem (arbitrary number of literals allowed per clause) with an additional constraint that each pair of clauses share at least 1 literal (not variables but literals).

Is this problem still NP-hard? It seems so, but I am unsure about the reduction.

Your problem is NP-hard, as can be seen by a (known, I believe) reduction from CNF-SAT: Reduce from (for example) $3$-SAT as follows. Given a formula $F$, create a formula for your special NAE-SAT by introducing exactly one additional variable, say $y$. Add $y$ to every clause in $F$ to obtain $F'$.

Example: $F = (x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_2 \vee x_3 \vee \neg x_4)$ becomes  $F' := (x_1 \vee x_2 \vee \neg x_3 \vee y) \wedge (\neg x_2 \vee x_3 \vee \neg x_4 \vee y)$

After doing this, every clause contains $y$ and thus shares (at least) one literal.

Proof sketch:
If $F$ is satisfiable, use the same satisfying assignment to satisfy $F'$, together with $y = false$.

If $F'$ is satisfiable, there are two options

$y = false $, in this case the same assignment satisfies $F$ ($F'$ has at least one true literal per clause, and it is never $y$, thus $F$ has at least one true literal per clause as well)
$y = true$, negate the satifying assignment for $F'$ to satisfy $F$ (at least one false literal per clause in $F'$, after negating the assignment we have at least one true literal per clause)


Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free? $L = \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $

Is this language a context free language?
If yes give a PDA. If no, give a proof.

The pumping lemma for context free languages doesn't seem to work here.

Let $p>1$ be the pumping length. Let the string be divided into five parts according to pumping lemma as $w = uvxyz$.

For any string of the form $a^ib^j \ s.t.$:

$ j\lt i-1$ choose $v=a, \ x=\epsilon, \ y=\epsilon$
$ j\gt 2i+1$ choose $v=\epsilon, \ x=\epsilon, \ y=b$
$ j = i-1$ choose $v=a, \ x=\epsilon, \ y=b$
$ j =  2i+1$ choose $v=a, \ x=\epsilon, \ y=b$
$ j\gt i,\ j\lt 2i $ choose $v=a, \ x=\epsilon, \ y=b$

It is context Free.

You can see it as a union of two languages:
$L_1$ where $j>2i$ and $L_2$ which is very similar to the one of this question.

More information you can find in this question.


Express product in ILP Suppose I have a mixed integer-linear program (MILP) with variables $x,y,z$, where $y$ is a 0-or-1 variable, and I want to impose the constraint $z=xy$.  This is not expressible in a MILP directly.  Is there a way to express this using linear inequalities, by adding some new variables (possibly variables restricted to integers)?

To put it another way: I want to express the constraint $(z=0 \land y=0) \lor (z=x \land y=1)$, in a situation where I already know $y$ is constrained to be either 0 or 1.

It depends on $x$ being bounded or not.

Suppose that $x$ is bounded as $x\in[0,x_{\mathrm{max}}]$. Then, the constraint $z=xy$ can be written as:
$$
\begin{cases}
z\leq x_{\mathrm{max}} y,\\
z\leq x,\\
z\geq x-(1-y)x_{\mathrm{max}},\\
z\geq 0.
\end{cases}
$$

You easily see that:

if $y=0$, then $z=0$; and
if $y=1$, then $z=x$.


Is There a Programming Language That Embraces Globals? All programming languages have globally defined symbols.  While best practices invariably abjure their use as mutable entities the philosophy of what is mutable and what is not mutable is highly context dependent.  Technologies like JIT compilation and type inference generate code on the fly based on the context in which symbols are dynamically referenced.

This makes me wonder exactly how far can this be taken.  Have languages been researched that are oriented around embracing global references?

For an example of what I'm thinking of, in Perl there is a "local" command that allows you to save the value of a symbol that is global to the current dynamic scope, modify the symbol as though global within that scope, and automatically restore its prior global value upon return.  This differs from ordinary concepts of local variables in that the nested dynamic scopes inherit the binding.  It also means that all code references, as well as data references, would be potentially dynamic.

I'm sure features other than a Perl-like "local" would be necessary to make it more wieldy (or less unwieldy for programming in the large, as the case may be).  An example of a more powerful dynamic scoping feature would be Javascript's "with" statement which allows unqualified references (without the object reference itself being repeatedly specified) to the properties of an object within the "with"'s dynamic scope.

The point here is that there are different ways of attacking the problem of programming in the large and some may be more conceptually clean than others in the sense of Ockham's Razor in that there is no escaping global symbols so we may as well make the best of them.

In more abstract terms, Quine suggested a similarly radical approach, at least in spirit, to applying Ockham's Razor in formal logic's use of the "name":

  “Chief among the omitted frills is the name. This again is a mere
  convenience and is strictly redundant, for the following reasons.
  Think of ‘a’ as a name, and think of ‘F(a)’ as any sentence containing
  it. But clearly ‘F(a)’ is equivalent to ‘(∃x)( a = x & F(x))’. We see
  from this that ‘a’ need never occur except in the context ‘a =’. But
  we can as well render ‘a =’ always as a simple predicate ‘A’, thus
  abandoning the name ‘a’. ‘F(a)’ gives way thus to ‘(∃x)(A(x) & F(x))’,
  where the predicate ‘A’ is true solely of the object ‘a’.

  “It may be objected that this paraphrase deprives us of an assurance
  of uniqueness that the name has afforded. It is understood that the
  name applies to only one object, whereas the predicate ‘A’ supposes no
  such condition. However, we lose nothing by this, since we can always
  stipulate by further sentences, when we wish, that ‘A’ is true of one
  and only one thing:

  (∃x)A(x) & ~ (∃x,y)(A(x) & A(y) & ~(x=y) )”

  “(This identity sign “=” here would either count as one of the simple
  predicates of the language or be paraphrased in terms of them.)”

PS:  Part of the reason I ask this question is that I did a multitasking/multiuser OS on the 8088 back in the mid '80s that had a "push and set" macro that I used extensively to create very compact code that, it seemed to me, ran quite fast.  This was a small system -- under 25,000 lines of code -- but it did work well in it specialized function as a 24 user instant messaging/bbs system.

This seems to me (as to some commenters) to be simply dynamic
scoping. It was used often in Lisp to change the behavior of system
functions to get some extra features, or perform hidden actions such
as monitoring of programs.  The cost is indeed that large programs may
be difficult to manage and maintain. Since then, there was a long
battle between static and dynamic scoping, I would guess that static
scoping supporters provided techniques to do what was formerly done by
dynamic scoping. The book I would look for such techniques is Abelson and Sussman:
Structure and Interpretation of Computer Programs.

It is available on the web in different formats, including html and pdf


Are divide and conquer searches applicable to unimodal decision problems? Given a sorted list of booleans with consecutive 0s followed by consecutive 1s such as [0,0,0,0,1,1,1], binary search is able to find the first 1 after all the 0s in log(n) time.

Is this technique generalizable to find the index to the maximum of a unimodal boolean list with a single 1 sandwiched between 0s such as [0,0,0,0,0,1,0,0]?

It seems like any search algorithm would have trouble narrowing down the search range with all the duplicate 0s surrounding a single 1, however binary search copes well with duplicates, so I'm having trouble explaining why this is impossible.

In addition, the unimodal property required by ternary / Fibonacci search is met, where an array A with indices i < j satisfies A[i] <= A[i+1] until maximum at A[j] then A[j] >= A[j+1].

From what I've read this is possible with a list of integers, so it can't be impossible due to just discrete versus continuous functions.

What am I missing here?

No.  Any algorithm for this problem requires at least $n-2$ time in the worst case.  Thus, the problem requires $\Omega(n)$ time.  You can't use binary search.

There's a simple adversary argument: each time the algorithm reads some index in the array, the adversary just answers 0.  After the algorithm has read $n-2$ different positions in the array, there are still two possibilities for where the 1 could be, so whatever the algorithm outputs at that point is wrong for at least one input (there exists an input array that makes the algorithm wrong).


Count points in 2-d range You are given an array $A$ of size N $(N\leq 1\,000\,000)$ containing all integers $1..N$ exactly once. You are required to answer query in $O(\log^2 N )$ and to preprocess in $O(N\log^2N)$:

  How many elements are there between indexes S and E, that are less than X? $( |L| : \forall l \in L \leftrightarrow A[l] < X  \bigwedge S\leq l \leq E )$

$X, S, E$ will vary from query to query, and there will be at most $1\,000\,000$ queries.

I found a lot of algorithms based on kd-trees, but they have complexity linear in the size of the output. Are there any other options, maybe using the property that X and Y coordinates are unique?

First, notice that it is enough to compute how many elements in $a_1,\ldots,a_E$ are less than $X$. (Why?)

Second, assume for simplicity that $N$ is a power of 2. We partition $\{1,\ldots,N\}$ into intervals in $\log N$ ways: as a single interval of length $N$, two intervals of length $N/2$, four intervals of length $N/4$, and so on. We sort each of these. This takes time $O(N\log^2 N)$. (Why?)

Third, given $E$ and $X$, write $a_1,\ldots,a_E$ as a sum of $O(\log N)$ intervals  of the kind we sorted above (use the binary expansion of $E-1$). Find the correct count for each of them in time $O(\log N)$ by searching for $X$ in the sorted interval, and compute the sum.


Trace dependents & precedents of a program in an imperative language We have some programs in a very basic imperative language, the programs contain some basic features: assignment, condition, loop, scalar variables, 1-dimensional arrays and 2-dimensional arrays... Note that a variable or an array may not be initialized (or already hold a value before the execution of a program).

My question is... is there some existing work to identify all the dependents and precedents of a program by static analysis of the syntax, without executing the program? Or, is it very trivial to do that?

Without giving a formal definition of dependent and precedent, I illustrate these 2 notions by the following program:

a[2,2] = 0;
i = 1;
While i <= 10 do {
  a[2,2] = a[2,2] + a[i,1];
  i = i + 1
}

Just from the syntax of the program, we can say, the script precedes a[2,2], because the value of a[2,2] is totally determined by the execution of the program. Also, we can say, the script depends on a[1,1] to a[10, 1], because the values of a[1,1] to a[10, 1] determine the running of the program.

I guess roughly we can say, if a variable is on the right side of the first assignment containing it, the script depends on it; if a variable ever appears on the left side of an assignment, the script precedes it. A variable can be both precedent and dependent for a script at same time.

So, is it really that trivial? Which elements may complicate the issue? Is there some existing research?

The analysis you want is called reaching definitions in the compiler community.

For your case you would put a "fake" definition of each variable you are interested in at the beginning of the program (representing definitions that are entering your script from outside) and then determine whether that definition reaches any of the uses.  If no fake definition reaches any use then the variable is defined inside the script, otherwise its value may be coming in from outside. The interesting cases involve conditionals and loops (some variables may be defined on one side of a conditional and not the other.)

I can highly recommend the following text books if you want to learn more:

Aho, Alfred V.; Sethi, Ravi;  Ullman, Jeffrey D.: Compilers: Principles, Techniques, and Tools, 1986.
Cooper, Keith D.; Torczon, Linda: Engineering a Compiler, 2005.

Reaching definitions analyzes scalars (so you would analyze each a[i,j] independently, as you did in your example.)

You could try to analyze entire arrays simultaneously, but this is a research topic (because parts of the array can be defined and other parts not).  The classic papers on trying to analyze entire arrays are

Zhiyuan Li: Array privatization for parallel execution of loops. Int'l Conf on Supercomputing, 1992.
Dror E. Maydan, Saman P. Amarasinghe, and Monica S. Lam: Array data-ﬂow analysis and its use in array privatization. Symp Principles of Programming Languages, (POPL-20):2-15, 1993.
Peng Tu and David Padua. Automatic array privatization. Int'l Workshop
on Languages and Compilers for Parallel Computing, (LCPC-6):500–521, 1993.


Is it decidable whether a pushdown automaton recognizes a given regular language? The problem whether two pushdown automaton recognize the same language is undecidable. The problem whether a pushdown automaton recognizes the empty language is decidable, hence it is also decidable whether it recognizes a given finite language. It is undecidable whether the language accepted by a pushdown automaton is regular. But ...

  ... is it decidable whether a pushdown automaton recognizes a given regular language?

In case the answer is no, does the problem becomes decidable if the given regular language has star height $1$?

It is undecidable whether a PDA recognizes $\Sigma^*$, the set of all strings over the input alphabet.

Added. It is undecidable to check that $L(G)=\Sigma^*$ as a consequence of the fact that "non-valid" computations of a TM can be coded as strings of a CFG. This is Lemma 8.7 of Introduction to Automata Theory by Hopcroft and Ullman. The authors refer for this result to Hartmanis (1967), Context-free languages and Turing machine computations.

A convenient coding of the computations of a Turing machine $M$ is as follows. A configuration of TM $M$ is a string of the form $xpy$ where $uv$ is the contents of the tape, and the state $p$ is indicated at the postion where the head resides. It is important to note that computational steps of a TM are local changes: $ucpav \vdash uqcbv$ for the instruction $(p,a,q,b,L)$ where the head moves left, and $ucpav \vdash ucbqv$ for the instruction $(p,a,q,b,R)$ where the head moves right.

A valid computation can be coded as a string $w_0\#w_1^R\#w_2\#w_3^R\# \dots$ where $w_0 = q_0x$ codes the initial configuration on string $x$, and we have proper steps $w_i \vdash w_{i+1}$. The last configuration in the string should be final, i.e., have a halting/final state.

It is now an exercise to verify that the strings that are not valid computations can be generated by a CFG $G_M$ (or accepted by a PDA). The strings that do not consist of configuration sequences are even regular. Otherwise one non-deterministically guesses a position where not $w_i \vdash w_{i+1}$. This part of the string is generated by a grammar that is similar to one for $\{ x\#y^R \mid x,y\in \{a,b\}^* , x\neq y\}$.

If the TM $M$ has no accepted strings, it will have no valid computations, and all strings are generated by the grammar $G_M$.


What would happen if we added this rule to red-black trees? So, I know that a normal r-b tree has a height of O(logn). What would happen is we let a red node have a red child if its parent is black?

Would the height still be O(logn)? Would you have to have a totally different insertion scheme to maintain the height?

Yes it stays $O(\log n)$. Compared to the proof of the original one, we have no three red consecutive on a path from the root to a leaf. The bound on the blacks stays the same in a path. The length of the path is now at most three times the number of blacks which is at most $3O(\log n)=O(\log n)$.

The insertion changes indeed. Now we have strictly more cases, since we are supposed to regard two levels up in the tree after inserting and rotating. However, I think a case distinction suffices as well similar to the one in the original r-b trees.


Parsing CFLs (simulating PDA vs CYK algorithm) We can simulate the PDA and parse the language with the following operations (vaguely):

  Read the input symbol and top of stack - $O(1)$
  Check all the transition rules (must check all for non-determinism) - $O(|Transition rules|)$
  Update the stack and the set of states - $O(1)$

Due to non-determinism, the problem size increases and so does the complexity.

However, for deterministic context free languages, the complexity of this algorithm seems to be $O(n|Transition rules|)$ which is linear.

The complexity of CYK algorithm is $O(n^3|G|)$. From various sources it seems that the complexity of CYK algorithm is polynomial for deterministic languages.
http://people.csail.mit.edu/madry/docs/linear.pdf

$|Transition rules|$ has a maximum value of around $|G|$ I think.

So, is this method really better than the CYK algorithm for deterministic CFLs or am I making a mistake in my analysis? If so, then where?

I'm assuming that $|G|$ = Number of production rules in grammar.

Wikipedia mentions that the class of deterministic context-free languages can be parsed in linear time, using an LR parser. In contrast, the fastest algorithm for parsing general context-free languages, Valiant's modification of the CYK algorithm, runs in time $O(n^\omega)$ (where $\omega$ is the matrix multiplication constant), and there is evidence due to Lee that any practical implementation of Valiant's algorithm will run in time proportional to $n^{2.43}$ at best (substitute $\epsilon = 3-2.81$ in Lee's paper; here $2.81$ is the exponent of Strassen's algorithm), and in time proportional to $n^3$ for most values of $n$ occurring in practice.

Context-free grammars used in practice tend to be deterministic, precisely because DCFLs can be parsed faster than CFLs. Indeed, even more restricted variants are commonly used (LALR languages) for reasons of efficiency.


Relation of P vs. BPP and P vs. NP What are the consequences of proving some relation ($\subseteq$, $\subset$, $=$, or $\neq$) on one of the following, to the other?

$P$ vs. $BPP$
$P$ vs. $NP$

It is trivial that $P$ is contained in $BPP$ and that $P$ is contained in BPP. There are of course, many consequences of resolving both of these questions (they wouldn't be major open problems if that weren't the case).  There is an important relationship between resolving 1 and resolving 2: From the Sipser-Lautemann theorem https://en.wikipedia.org/wiki/Sipser%E2%80%93Lautemann_theorem it follows that if $P = NP$, then $P=BPP$.  Of course, we strongly believe that $P \neq NP$, and that $P = BPP$, so this isn't a direction of reasoning that is likely to be actually useful by itself.


Double exponentials vs single exponentials Here are four tenets I cannot reconcile:

Double exponential time algorithms run in $O(2^{2^{n^k}})$ time with $k \in \mathbb{N}$ constant
Exponential time algorithms run in $O(2^{n^k})$ with $k \in \mathbb{N}$ constant
The former bound grows stricly faster than the latter; i.e., there exist algorithms that run in double exponential time but not in exponential time
Applying $a^{b^c} = a^{bc}$ to the double exponential bound we have $O(2^{2^{n^k}}) = O(2^{2^{nk}}) = O(2^{2nk})$, which falls within the previously stated exponential bound

I feel I am missing some subtlety relating to the definition of an exponential-time algorithm as running in $O(2^{\mathrm{poly}(n)})$ rather than $O(2^{n})$, but I am not sure precisely where the subtlety lies.

The issue comes down to ambiguous terminology.

$(a^b)^c = a^{bc}$, but $a^{(b^c)} \neq a^{bc}$. In other words, exponents aren't associative.

Conventionally, nested exponentials without parentheses are grouped in this second way, because it's more useful. So $2^{2^n} = 2^{(2^n)} \neq 2^{2n}$. If we wanted to talk about $(2^2)^n$, we could just write $2^{2n}$ instead, so we reserve the double exponential notation for the other case.


Existence of Hamming code We are given a  number $n \geq 3$ and we know that the Hamming bound is satisfied. Does this imply that there is a Hamming code with length $\frac{q^r-1}{q-1}$, dimension $\frac{q^r-1}{q-1}-r$ and Hamming-distance $3$ or do we have to construct such a code, given that the bound is satisfied?

The Hamming bound is an upper bound on the size of codes. It's not a tight bound in general, though in some specific cases it is achievable. Codes achieving the Hamming bound are called perfect codes.

When the alphabet size is a prime power, all perfect codes are known: apart from some trivial cases (repetition codes, codes with one codeword, and codes containing all possible codewords), they share the same parameters as a Hamming code or a Golay code.

What this means is that if your alphabet size is a prime power and you have parameters satisfying the Hamming bound, then a code with these parameters actually exists only in the cases listed above. In any other case, the bound isn't tight.