criterion for two line segments intersecting I have two line segments $[(x_1, y_1),(x_2, y_2)] $ and $[(x_3, y_3),(x_4, y_4)] $ and I want to know if they intersect.

My current algorithm tries the following:

the line $[(x_1, y_1),(x_2, y_2)] $ is determined by
$\boxed{f(x,y) = \frac{y - y_1}{x - x_1} - \frac{y_2 - y_1}{x_2 - x_1}  = 0}$.
I reasoned that if $y = mx+b$ is my line, I want a point such that $y > mx+b$ and one such that $y < mx+b$.
I want to check if that $f(x,y)$ has opposite signs if I set it on $(x_3,y_3)$ and $(x_4, y_4)$.  So the criterion I check right now is:
$$ \frac{f(x_3,y_3)}{|f(x_3,y_3)|}\;
\frac{f(x_4,y_4)}{|f(x_4,y_4)|} = -1
$$
Unfortunately in my visualization, I still see line segments intersecting.

Is there something wrong with my algorithm?  What is a correct way to check that two line segments intersect?

You need to know about the orientation test.

For any three points, compute the determinant

$$\Delta_{123}=\left| \begin{array}{ccc}
x_1 & y_1 & 1 \\
x_2 & y_2 & 1 \\
x_3 & y_3 & 1 \end{array} \right|.$$

This is twice the signed area of the triangle $123$. When it is $0$, it tells you that the three points are aligned. Otherwise, it tells you on what side of the line joining two points the third lies.

In your case, there is an intersection if $1$ and $2$ are on either sides of $34$, while $3$ and $4$ are on either sides of $12$:
$$(\Delta_{134}>0)\ne(\Delta_{234}>0)\land(\Delta_{123}>0)\ne(\Delta_{124}>0).$$

It is up to you to decide what to do in cases of perfect alignments.

As an extra goodie, the $\Delta$'s can be used to compute the coordinates of the intersection. (Let $P$ be the intersection point, interpolated along the segment $P_1P_2$: $P=(1-t).P_1+t.P_2$; it is easy to show that $(1-t)\Delta_{134}+t\Delta_{234}=0$ and to find the value of $t$.)


Pairwise hash functions that are independent from each other Is there there a way to build a collection of universal hash functions $H=\{h| h:U\to D \}$ where the values of two hash functions are independent one from another? i.e., $\Pr_{h_1,h_2\in H}(h_1(x)=y  \land h_2(z)=w )=|D|^{-2}$ for each $x,y,z,w\in U$.

Also, is there a term for such collection?

If you select $h_1,h_2$ independently at random, then by definition

$$\Pr_{h_1,h_2}[h_1(x)=y \land h_2(z)=w] = \Pr_{h_1}[h_1(x)=y] \times \Pr_{h_2}[h_2(z)=w].$$

If your hash family is universal, then both probabilities on the right-hand side will be $1/|D|$.

In other words, if $H$ is universal, then it automatically follows that

$$\Pr_{h_1,h_2}[h_1(x)=y \land h_2(z)=w] = 1/|D|^2.$$

Every universal collection works -- no extra conditions or requirements are needed.


Is $a^n b^n$ an artificial language or does it occur in the real world? The classic example of a context-free grammar is $a^nb^n$. That is, $n$ occurrences of $a$ followed by an equal number of occurrences of $b$.

Do such forms occur in the real world? Can you provide an example of a real-world case where there must be $n$ occurrences of something followed an equal number of occurrences of something else?

Let me give an example: if I run an on-line store, then for each purchase made to my store, there must be a corresponding delivery of the purchased item. That might be modeled as $n$ purchases followed by $n$ deliveries:

  purchase purchase purchase delivery delivery delivery

However, that is not a good data model since each delivery should legitimately be paired to a purchase:

  purchase delivery purchase delivery purchase delivery

So I am left wondering if there are any real-world examples where data would be (legitimately) modeled as a sequence of $n$ items of one type followed by $n$ items of another type. Can you provide a real-world example please?

Hendrik Jan provided this good example (see it in the comments below): This weekend I visited my mother. Three flights up, and three flights down when I left.

Neat example! Can you think of others?

A colleague just informed me of another example. In the KML specification it says that a <Track> element must contain N <when> elements followed by N <gx:Coord> elements:

https://developers.google.com/kml/documentation/kmlreference#gxtrack

Another excellent example. What are other examples?

Another colleague sent me an article about columnar databases. It is often more efficient to store data in columns rather than rows. For example, we may have a column of person's ages followed by a column of person's heights. Or, a list of N integers (ages) followed by a list of N decimals (heights). This enables efficient calculation of sums or averages. Here's the article:

http://www.postgresql.org/message-id/52C59858.9090500@garret.ru

More examples please! I would like for us to create a nice collection of compelling examples.

The classic consequence of $a^nb^n$ being context-free rather than regular is on opening and closing brackets. $a^nb^n$ represents the simplest possible case of this: no interleaving of opens and closes and no intervening characters. Regular expressions can't even deal with this most basic case.


Counting the number of tree when the set of the subtrees is given There are a set $A$ of trees. There is another set $B$ of trees that is the collection of all possible subtrees of the trees in $A$. I don't have $A$ but only have $B$, and I need to figure out the size of $A$. A brute-force way is making a graph of the trees. For each root node in $B$, find a tree that contains the node, if there exists such a tree, then make a link from the root node's tree to the containing tree. Finally I can obtain the number of trees in $A$ by counting the number of connected components in the graph. However, this may not be so efficient. How can I do it efficiently?

You can't do it at all, let alone do it efficiently. Consider a tree $T$ and let its set of subtrees be $S$. If you're told $B=S$, the cardinality could be anything between $1$ and $|S|$, inclusive, because $A$ could be any subset of $S$ that contains $T$.


How does the problem of "Scheduling to Minimize Lateness" exhibit optimal substructure? The problem of "Scheduling to Minimize Lateness" is as follows (Section 4.2 of the book "Algorithm Design" by Jon Kleinberg and Eva Tardos):

Input: A finite set $J = {J_1, J_2, \ldots, J_n}$ of $n$ jobs, their processing time $t_1, t_2, \ldots, t_n$ and deadlines $d_1, d_2, \ldots, d_n$. We assume that all jobs were available to start at the common start time $0$.
Output: A schedule of these jobs to minimize their maximum lateness.
Suppose a job $J_i$ is scheduled at time $s_i$, then its lateness is defined to be $l_i = s_i + t_i - d_i$ (it is $0$ if $s_i + t_i \le d_i$.)

It is known that this problem can be solved by a greedy algorithm which schedules the jobs in the non-decreasing order of their deadlines.

I am confused about its optimal substructure property (not explicitly described in the book).
Let $L(s, S)$ be the optimal lateness obtainable from scheduling the jobs in $S$ which are available to start at the common start time $s$.
On the one hand, by enumerating over the possible first jobs to schedule, we get the following recurrence:
$$L(s, S) = \min_{1 \le i \le n} \Big(\max\big(L(0, \{J_i\}), L(t_i, J \setminus \{J_i\})\big)\Big).$$
Intuitively, this problem exhibits optimal substructure.
On the other hand, it seems that the problem does not exhibit optimal substructure with respect to the form of subproblems defined above.
To illustrate this, consider three jobs $J = \{J_1, J_2, J_3\}$ with processing time $t_1 = 6, t_2 = 2, t_3 = 2$ and deadlines $d_1 = 2, d_2 = 7, d_3 = 8$. An optimal solution is to schedule $J_1, J_3, J_2$ in that order, producing a maximum lateness of $4$. However, this optimal solution does not contain the optimal solution to the subproblem of scheduling $\{J_2, J_3\}$ given the common start time $t_1 = 6$, which is $L(6, \{J_2, J_3\}) = 2$ by scheduling $J_2, J_3$ in that order.
This contradicts the "definition" of the optimal substructure property given in CLRS (Sections $15.3$ and $16.2$; 3rd edition):

A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.

Problem: How does the problem exhibit optimal substructure?

Let us refine the "definition" of the optimal substructure property given in CLRS into two definitions.

A problem exhibits strongly optimal substructure if every optimal solution to the problem contains optimal solutions to subproblems.
A problem exhibits weakly optimal substructure if there is at least one optimal solution to the problem contains optimal solutions to subproblems.

What you see in the problem of "Interval Scheduling to Minimize Lateness" is the weakly optimal substructure. Take your example of three jobs $J=\{J_1, J_2, J_3\}\,$ with processing time $t_1=6,t_2=2,t_3=2\ $ and deadlines $d_1 = 2, d_2 = 7, d_3 = 8.\,$ One optimal solution is to schedule $J1,J2,J3\,$ in that order, which contains optimal solutions to all subproblems.
Weakly optimal substructure happens often when the goal of an optimization problem is not restricting enough to guarantee every optimal solution must contain optimal solutions to subproblems.
Here is a version of the interval scheduling problem that exhibits strongly optimal substructure. There are two changes in the problem statement compared to the previous one. What is to be minimized is their total lateness instead of their maximum latess. Also the lateness of a job is allowed to be negative. While this version of the problem is rather trivial to solve, it does serve to illustrate the concept of strongly optimal substructure.

Input: A finite set $J= \{J_1, J_2, \ldots, J_n\}\,$ of $n$ jobs, their processing time $t_1, t_2, \ldots, t_n$ and deadlines $d_1, d_2, \ldots, d_n$. We assume that all jobs were available to start at the common start time $0$.
Output: A schedule of these jobs to minimize their total lateness. Each job must continue processing once started. At any time, there can be at most one job that is being processed. Suppose a job $J_i$ is scheduled at time $s_i$, then its lateness is defined to be $l_i = s_i + t_i - d_i\,$. The total lateness is the sum of all $l_i$.


Is the Weighted Maximum Coverage Problem with frequency weights NP-hard? I want to prove the following case of Weighted Maximum Coverage problem with special weights is NP-hard. But I have no idea. So I am here seeking for help.

The Weighted Maximum Coverage problem is formulated as follows (known to be NP-hard):

Given a set I of m elements with each element ej has a weight w(ej), a collection of subsets S=S1,S2,...Sn with each set covers some elements, and an integer k, the object is to find k subsets to maximize the sum weights of covered elements.

Now, my concern is as follows:

When the weight for each element is the number of subsets that cover this element, is the problem still NP-hard? How to prove it?

For example, given I={a,b,c,d}, S=S1,S2,S3, and S1={a,b,c} S2={b,c} S3={c,d}, then the weight of element b is 2, since there are two subset, S1 and S2, covers b.

If you allow sets to repeat, then you can show that this is still NP-hard by making all the weights equal. The idea is to reduce from unweighted maximum coverage to your version of maximum coverage. Given an instance of unweighted maximum coverage, where element $e_i$ appears $w_i$ times, let $W = \max_i w_i$, and for each element $e_i$ of non-zero weight, add $W-w_i$ sets of the form $\{e_i\}$. In the new instance, each element appears the same number of times, so all have the same weight; and one checks that the added sets cannot improve the optimal solution.

If you insist that the sets are disjoint, you repeat the same construction, but to each set in the construction (old and new) you add a unique dummy element. This increases the value of each feasible solution by exactly $k$.


Reducing k Vertex Cover to SAT (last clause problem) I am working on a transformation from k Vertex Cover to SAT and I have some issues regarding the last clause in the boolean formula.

Here is my approach:
    $$\forall \text{ nodes } n_i \in V, \text{ invent variables } v_i$$
    $$\forall \text{ edges } (n_i, n_j) \in E, \text{ invent the terms } (v_i \lor v_j) \Rightarrow C_{edges}$$

Is this approach correct or am I missing something?

First of all, the problem of vertex cover asks whether there is a vertex cover with at most $k$ vertices. Fortunately, there is a vertex cover with at most $k$ vertices iff there is one with exactly $k$ vertices, so your choice of looking for a vertex cover of size exactly $k$ is fine.

Second, you need to describe everything as a CNF, that is, a collection of clauses. You can't just include
$$
y_{i,j} \equiv (y_{i-1,j} \land \lnot v_i) \lor (y_{i-1,j-1} \land v_i).
$$
Fortunately, every formula on $t$ variables can be written as a CNF having at most $2^t$ clauses (exercise), so you can turn this formula into a CNF of constant size.

Finally, you say that you "should write $y_{nk}$ in terms of $v_1 \cdots v_k$", but there is no such requirement. An instance of SAT is just a bunch of clauses. You can use whatever variables and clauses you want; the distinction between original variables $v_i$ and extension variables $y_{i,j}$ is all in your head. If you want to force $y_{n,k}$ to be true, you can just add a singleton clause $y_{n,k}$.


Complexity of a recursive bignum multiplication algorithm We have started learning about analysis of recursive algorithms and I got the gist of it. However there are some questions, like the one I'm going to post, that confuse me a little.
The exercise

Consider the problem of multiplying two big integers, i.e. integers represented by a large number of bits that cannot be handled directly by the ALU of a single CPU. This type of multiplication has applications in data security where big integers are used in encryption schemes. The elementary-school algorithm for multiplying two n-bit integers has a complexity of . To improve this complexity, let x and y be the two n-bit integers, and use the following algorithm
Recursive-Multiply(x,y)
  Write  x = x1 * 2^(n/2)+x0  //x1 and x0 are high order and low order n/2 bits
       y = y1 * 2^(n/2)+y0//y1 and y0  are high order and low order n/2 bits
  Compute x1+x0  and y1+y0
  p = Recursive-Multiply (x1+x0,y1+y0)
  x1y1 = Recursive-Multiply (x1,y1)
  x0y0 = Recursive-Multiply (x0,y0)
  Return  x1y1*2^n + (p-x1y1-x0y0)*2^(n/2)+x0y0

(a) Explain how the above algorithm works and provides the correct answer.
(b) Write a recurrence relation for the number of basic operations for the above algorithm.
(c) Solve the recurrence relation and show that its complexity is $O(n^{\lg 3})$

My conjecture

Since the method is being called three times, the complexity is going to be $3C(n/2) + n/2$.

My questions

What do they mean by hi-lo order bits?

How can I use a recurrence relation on this if I don't know how each recursion works?

The idea is to divide each $n$-bit integer into two halves of $n/2$ bits. For example, $10100010$ would be divided into $1010$ and $0010$. Naively, we would need to multiply four such halves, but in fact there is a way to do with only three. (This is similar to matrix multiplication algorithms such as Strassen's.) The algorithm described by the exercise is known as Karatsuba multiplication.

Regarding your other question, once you have reduced the computation of running time to a recurrence relation, you no longer need to understand anything more about the recursion in order to compute the running time - this is the main point of this abstraction.


Deterministic Communication Complexity of Equality if inputs differ by at most 1 The set equality problem in 2 party communication complexity is known to require $n$ bits of communication between Alice and Bob, for $n$-bit inputs $X$ and $Y$.

Suppose that we promise that the symmetric difference of $X$ and $Y$ is $\le 1$. Is the required communication for a deterministic protocol still $\Omega(n)$?

My thoughts: I believe that the complexity becomes $O(\log n)$ because of the following: When Alice gets its input $X$ of size $k$, she knows that Bob's input differs at $\le 1$ index. Thus, there are only $\le {n \choose 1}n + 1 = O(n^2)$ possibilities for $Y$, given $X$; the "+1" is the case where $X=Y$. So there should be a way to convey this information from Bob to Alice using only $O(\log n)$ bits.
Is my reasoning correct?

Hint: Compare the parities of the inputs. (Can you generalize this idea to at most $k$ differences?)


TSP decision problem vs TSP optimization problem Let's check together whether the TSP-decision problem is NP-complete. Maybe it will help me to understand things better.

Question for TSP-decision problem: Given n cities and a tour from length $k$. The traveller starts at an arbitrary city, visits every other city just once and returns to the starting point. Does a tour from length $\leq{} k$ exist?

Let's first check whether the TSP is in NP:

A proof is given. Proof in this case is a tour. For it to be in NP, we must be able to verify this proof with a deterministic algorithm in polynomial time.
So first we have to check, whether every city is only visited once. This can be done at most in $O(n^2)$. Next we need to calculate the distances and sum them up. This can be done as well at most in $O(n^2)$. The last step is to check whether the calculated length is $\leq{} k$. The hole process would require a polynomial time $\rightarrow 2 n^2 = O(n^2)$.

So the TSP-decision problem is in NP. What about the NP-hardness? We don't need to prove that, because Richard M. Karp proved that the Hamiltonian Circuit is NP-complete. The TSP is a special case of the Hamiltonian Circuit, therefore we know TSP must be NP-complete as well. NP-complete means = NP-hard and NP.

Is this possible with TSP-optimization problem?

Question for TSP-optimization: Given n cities and a tour from length $k$. A traveller starts at an arbitrary city and visits every other city just once and returns to the starting point. Is tour from length k the shortest tour?
We can check in polynomial time, that every city is visited once.
However we can't check whether $k$ is really the shortest tour, because we would have to check every other possible tour as well. That would mean $(n-1)!$ possible tours. And this would make the hole process above exponential.

So TSP-optimization problem is not in NP? Therefore it is not NP-complete, but NP-hard?

Anything wrong about my thoughts?

Only decision problems can be NP-hard or NP-complete; these are problems for which the answer is either Yes or No.

Optimization problems have an optimal solution as an answer. The associated decision problem is, given an instance and a value, whether the the value of an optimal solution is as good or better than the given value.

When we say that an optimization problem is NP-hard, we mean that its associated decision problem is NP-hard; it is an abuse of terms. We could also say that an optimization problem is NP-complete if its associated decision problem is NP-complete.

The TSP optimization problem is, given a graph, find a TSP tour of shortest length. The associated decision problem is, given a graph and a value $k$, decide whether the shortest TSP tour has length at most $k$. These are different than the problems that you describe.

Sometimes we are interested in a weaker version of the optimization problem, namely, given an instance, find the value of an optimal solution. This is the perspective usually considered in the field of hardness of approximation, in which the goal is to show that it is NP-hard to even approximate the optimal value.


Two versions of Subset Sum Problem I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is:

  Given an integer bound $W$ and a collection of $n$ items, each with a positive integer weight $w_i$, find the subset $S$ of the items that maximizes $\sum_{i \in S} w_i$ while keeping this sum at most $W$. Or the decision version: Is there a subset obeying the at-most-$W$ rule with weight at least some number $k$.

So just Knapsack except the values are the weights themselves.

The second and seemingly more common is:

  Given a set of $n$ integers, is there a non-empty subset whose sum is 0 (or equivalently, some number $k$)?

E.g., my textbook (Kleinberg and Tardos) as well as this
have the first one. Wikipedia and other websites have the second.

I believe both are NP-complete. That said, I haven't found an "obvious reduction" from one to the other that suggests why the two problems are given the same name. So my questions are:

Do quick reductions exists between the two?
Why are these given the same name in the first place?

Given an instance of the second problem, we can easily reduce it to an instance of the (decision version of) the first problem: simply take $W = k$. There is a subset of sum at least $k$ and at most $W$ iff there is a subset of sum exactly $k$.

In the other direction, the idea is to add to the collection a small set of items satisfying the following two properties:

The total weight of the new items is $W-k$.
Every weight between $0$ and $W-k$ can be represented as a sum of a subset of the new items.

Having added this collection, we ask whether there is a subset summing to exactly $W$. It is not hard to check that there is a subset of the original collection whose sum is between $k$ and $W-k$ if there is a subset of the enlarged collection summing to $W$ exactly.

How do we add these items? The simplest case is when $W - k = 2^t$, in which case we can simply add $1,2,4,\ldots,2^{t-1}$. More generally, suppose $2^t \leq W-k < 2^{t+1}$, and let $W-k = 2^t + C$. We then add $1,2,4,\ldots,2^{t-1},C$.


is this an example of nominal unification? I am thinking that is the following a problem solved by nominal unification.

$\lambda a.X = \lambda b.\lambda c.c $

where we find $X$. The answer is obvious.

The reason is that it seems in nominal unification $X$ always will be an atom, not a function such as $\lambda c.c$.
The theory seems works fine with this input, just did not saw any example similar to this one.

Sure, these unify under nominal unification.  You get a unifier like $X = (b\ a)\bullet\lambda c.c$ which simplifies to $X = \lambda c.c$.  Figures 1 and 3 of Nominal Unification describe the relevant details of the algorithm.  In particular the transitions will be $\approx?$-abstraction-2 and $\approx?$-variable followed by $\#?$-abstraction-2 and $\#?$-atom.


Removing a character from a string I am asked the following:
def myRemove( str, ch ):
 # Return a new string with the first occurrence of ch removed.  If there is none, return str.

Sample run
>>> myRemove( "abcdabcd", "a")
'bcdabcd'
>>> myRemove( "abcdabcd", "x")
'abcdabcd'
>>> myRemove( "abcdabcd", "d")
'abcabcd'

I have tried a few different methods but have not been able to figure the problem out. Here is my attempt:
def myRemove( str, ch ):
    for num in range (0, len(str)):
        if (str[num] == ch):
            return str[0:num] + str[num + 1:]
        else:
            return str

There is also an extension to this problem which asks : Return a new string with all occurrences of ch removed. If there are none, return str. However, since I have not been able to solve the first part, naturally I was not sure how to solve the second. Would appreciate any guidance.

Notice that the loop will only occur once! In the beginning num will be 0. At this point, we enter the if statement:

if we got that str[0] == ch (notice that num==0 and thus str[0]==str[num]), then we return some string
otherwise we return another string

The important thing here, is that no matter what - we will quit in the first iteration of the for loop.
To fix this, consider placing the return str outside the for loop (without else as well)


When two siblings in a heap are equal, how do you bubble down? I have a heap where both child nodes of the root are 10, and I'd like to perform an operation to remove the min value 9.

I proceed to replacing the root with its next of kin, 18. However when I bubble down, I am unsure of which direction to take.

Picking either should work. The heap property (assuming you have changed it to mean parent $\le$ children) will not be violated.


Why Bloom filter needs $\frac{m}{n}\ln{2}$ hash functions? I show from Wikipedia that the optimal number of hash functions is:

  $k =\frac{m}{n}\ln{2}$.

However it's not obvious for me why, even after reading the Wikipedia article (such as the one on false positives). Anyone interested in explaining with simple words? :)

This is explained in Wikipedia. Given $n,m$, the false positive probability is
$$
\left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k.
$$
This is the quantity we want to minimize. While the exact expression is hard to minimize exactly, we can use the approximation
$$
\left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k \approx (1-e^{-kn/m})^k,
$$
which is good if $m$ is large. We can optimize the latter expression using calculus, and the result is some expression which is very close to $(m/n) \ln 2$. This is a calculation that I leave to you.


Identity in the category of types and functions In the model of (functional) programming languages as a category where the objects are types and the arrows are functions, I'm trying to really understand what's really the identity arrow.

Barr-Wells "Category Theory for CS" says you need the id function, but I wonder: it really has to be the "do nothing" function? For any type A, doesn't any function f:A->A work? If looking at type level, I can't distinguish the functions, shouldn't be ok?

I'm trying to find a counter-example but couldn't.

EDIT:
I was thinking on the Hask category but I guess my question in Category Theory terms is:
Does every endomorphism in an object A is isomorphic to the identity arrow in A?

It has to satisfy the properties of the identity arrow - i.e. its left and right composition with any other arrow is that arrow.

Of course, you can have multiple different categories where the objects are types (for some definition of "types" - it's actually really complicated, if not impossible, once you start looking at polymorphic or dependent types) and arrows are something somehow related to functions between them. What exactly you choose to call "arrow" is up to you, as long as it satisfies the required properties (composition and identity).

A trivial example, you can say that "let us define that the (sole) arrow between type $A$ and type $B$ represents the family of all functions between $A$ and $B$" - in this category the sole arrow $A \to A$ will happen to also be the identity arrow. I suppose this is what you mean under "looking at type level".

Or you can say: For a given family of equivalence relations $Eq_T$ on every type $T$, let us define that there is one arrow between type $A$ and type $B$ for every function $A \to B$, modulo the function equivalence relation "maps $Eq_A$ to $Eq_B$". Then if you take the usual equality relation on integers and consider the arrows $int \to int$, in this category you'll only have one identity arrow - the function that maps a number to itself. The function $x \to x+1$ will not work.


Interview Question: Insert switch to maximize time lightbulb spends on Problem statement:

  You have a lightbulb for an interval of $N$ seconds, where $N$ is given.
  At time 0, the lightbulb switches on, and at time $N$, it switches off,
  regardless of any switches. From time 1 to time $N-1$ you have a maximum
  of $N-2$ switches in the form of an array called switches, which turn
  the lightbulb to the opposite of what it currently is i.e. if it's on
  it'll turn off and vice versa. For example, suppose $N = 8$ and switches
  $[1,2]$. The lightbulb will switch on at time 0, a switch at time 1 will turn it off, a switch at time 2 will turn it on, and it'll remain
  on until time 8, when it turns off. Hence, the time it remains on is
  equal to $1-0 + 8-2 = 7$.

  Now suppose you have to insert a switch in this interval, where there
  is not already a switch present. What is the maximum time the
  lightbulb remains on once you insert the switch. For example, in the
  above case, the solution would be 6 since inserting a switch at time 7
  keeps the time the lightbulb spends on maximum. Since $1-0 + 7-2 = 6$,
  the answer is 6.

I solved this using a brute force solution, using the reasoning that  if you insert a switch at time $k$, the states of the lightbulb before this wouldn't be affected, and the states of the lightbulb from time $k$ to time $N$ will be reversed, and hence you can find the time it spends on after time $k$ by $(N - k) - t$, where $t$ is the time it would spend on from time $k$ to $N$ without the inserted switch. Hence, I can calculate the time the lightbulb would spend on for each time position of the inserted switch and maximize it. However, since calculating the time the lightbulb spends on is $O(n)$ operations and I go through all possible positions, my solution is $O(n^2)$ and this caused my code to time out for some test cases.

Can someone propose a better solution?

Let's call the array of switches $a$ and let's add two elements to the array at the beginning we add 0 and at the end we add 100.
We now want to insert an element between two consecutive elements to maximise the length the bulb is turned on.
Let's make the following observations:

Note1 If a[i+1] = a[i] + 1, two consecutive elements have consecutive values. In this case we can't add anything between them.

Note2 The optimal value we add between $a[i]$ and $a[i + 1]$  for some $i$ is either equal to $a[i] + 1$ or to $a[i+1] - 1$.
Proof. Assuming the claim is not true, there is an optimal value strictly between $a[i]+1$ and $a[i+1]-1$. However, if the bulb is turned off in this interval we can push it back to $a[i]+1$ increasing the length of the turned on pulp in this interval without effecting the others. On the other hand if the bulb is turned on, we push it right to $a[i+1]-1$ increasing the length of turned on pulp in this interval.

So now we can loop over the array, and for each $i$, if $a[i] \neq a[i+1]-1$, we try to add the value $a[i]+1$ and the value $a[i+1]-1$, these are 2*(n-1) tries in total where n is the number of elements in the array (including 0 and n), which is linear in the number of the switches. We only have to show that we can do each step in constant time.
So let's say we already have the array, and we want to check the total value after adding a switch at position $k$. Let's pre-process the array and calculate and building the following 2 arrays in linear time:
 1. The length of light-on since the begin.
 2. The length of light-off from now till the end.
We can do that in two loops over the array using prefix-/suffix-sums.
Now when adding a switch between $a[i]$ and $a[i+1]$ with time stamp $k \in (a[i], a[i+1])$, the total value of on-light will be total value of on light from the begin to $i$ + the total off-light from $a[i+1]$ till the end + the total on-light in the interval between $a[i]$ and a[i+1] after adding $k$ (Which is either $k - a[i]$ or $a[i+1] - k$ depending on the original status of the interval).
Summary, In total we preprocess the array in $O(n)$, we do linear number of checks $O(n)$ and each in constant time in total we have $O(n) + O(n) * O(1) = O(n)$


Vehicle Routing Problem Using Simulated Annealing Suppose I have some locations where goods are to be delivered in multiple time slots(like 7-10 am , 10 am-1 pm, time slots are continuous). All the locations are connected with each other(completely connected graph).

1.) Firstly orders of first slot are to be delivered and then only orders of other slots can be delivered.So, the last point of most optimal first slot sub-tour might not be the most optimal for the overall distance minimization. We might need to go from that last point to some other point of first slot and then from there on go to locations of slot2.

2.) Minimize distance

3.) Trip starts from a depot and ends at the depot( So sequence is something like depot -> Slot 1 orders -> Slot 2 orders -> .......... -> depot , where slot1 is 7-10 am , slot2 is 10 am - 1 pm, slot3 is 1 pm - 4 pm......).

My question is how can this problem be tackled with simulated annealing. like how to fix the starting and end points(as depot) and how to set annealing schedule for such problem.

To solve a combinatorial optimisation problem such as this by a method such as Simulated Annealing, you need 3 basic ingredients:

A representation for a 'Candidate Solution'. For vehicle routing, this is typically a permutation of the depots, i.e. a list of depots in the order to be visited.
A measure of the quality of a candidate solution. Various methods exist for penalising solutions with deliveries outside their time windows or fail to meet other constraints.
One or more 'perturbation operators' for transforming a candidate solution into another (hopefully better) one. For example, swapping two randomly-chosen depots in the permutation is one of the simplest approaches, but of course more informed operators as possible.

Given these three, it's then possible to plug your problem into a range of metaheuristics, such as iterated local search, Tabu search, various Evolutionary Algorithms or Tabu search.

As regards annealing schedule, there's a range of literate on choosing parameters, but one simple option is to obtain initial and final temperatures from the statistics of a sequence of random perturbations, then experiment with the choice of cooling rate in a geometric annealing schedule.

The excellent (and freely-available) book "Essentials of Metaheuristics" offers a more detailed background on the above and some guidelines for what techniques to apply in what circumstances.


Summation of asymptotic notation How can we solve summation of asymptotic notations like given below:
$$
\sum_{k=1}^{n-1} O(n).
$$

You should be very careful when summing up a variable number of terms in asymptotic notation, as the result actually depends on the hidden constants.

Consider the following example: $f_i(n) = i\cdot n$ for all integers $i$ and $n$. Then, for any integer $i$, $f_i(n) \in O(n)$.

If you are not careful, you could end up writing something like:
$$\sum_{i=1}^n f_i(n) = \sum_{i=1}^n O(n) = O(\sum_{i=1}^n n) = O(n^2).$$
And get $O(n^2)$. But this is totally wrong!

If you do the computation without the asymptotic notation, you get:
$$\sum_{i=1}^n f_i(n) = \sum_{i=1}^n i\cdot n = n\sum_{i=1}^n i = n\frac{n(n+1)}{2} = \frac{n^2(n+1)}{2}.$$
And this is not in $O(n^2)$, as it is in $\Theta(n^3)$.

Now some authors define $\sum_{i=1}^n O(n)$ as meaning that the hidden constants are the same for every $O$ and in this case you can sum things together. But this is not always the case so I recommend not using $O$ notation with variable-length sums (as well as when doing induction, where similar problems appear).


Reduction from 3-SAT to a graph problem I have a question, i was trying to reduce 3-SAT to a particular graph problem and i'm not quite sure about a thing i used in the reduction.
In fact the reduction build a bipartite graph, the edge $(x_1,c_1)$ exist if the variable $x_1$ is in the clause number 1, the costs on that edge are dependent on the truthfulness of the variable $x_1$, cost 1 if $x_1$ is true and 0 elsewhere. My question :is it permitted in a reduction or should i have the entire graph instance independent from values taken by the variables ?

Thank you all!

If I understand your question correctly, you're asking whether you can construct a reduction where the truth assignment changes the construction.

In short, no. The whole point of a reduction from problem $A$ to problem $B$ is to show that we can solve $A$ using an algorithm for $B$ - if we already know the solution to $A$, then we could trivially reduce it to virtually any other problem.

In your particular case, if you already know the truth assignment to the variables, then you've already answered whether the input formula to the 3-SAT instance is satisfiable or not, what you want is a reduction that takes the formula, turns it into an instance of your graph problem, where solving the graph problem would tell you what to set the variables in the 3-SAT instance to.


Proof of $P^{\text{#}P} = P^{PP}$ I was reading this article on the complexity class $PP$.

In the fourth paragraph there is a claim that $P^{\text{#}P} = P^{PP}$ and that it can be proved using binary search. Can anyone please explain this in better detail?
The author himself gives the following explanation: If $f$ is a $\text{#P}$ function then the language $L= {(x,k) | f(x) \geq k}$ is in $PP$. Then do binary search on $k$.

This is still not clear to me. The other direction, $P^{PP} \subseteq P^{\text{#}P}$ is clear.

It all boils down to simulating a $\mathsf{\# P}$ oracle using a $\mathsf{PP}$ oracle. Consider a $\mathsf{\# P}$ oracle call: a polytime non-deterministic Turing machine $T$ and an input $x$. We want to know how many runs of $T$ result in the output $1$. Denote this number by $T_1(x)$, and denote the total number of runs of $T$ on $x$ by $T(x)$.

First, let's show that using a $\mathsf{PP}$ oracle we can decide whether $T(x) \geq y$ for any polysize $y$. We construct a Turing machine $T'$ that acts as follows:

Guess a non-deterministic bit $b$.
If $b = 0$, then simulate $T$ on $x$ in such a way that there are $2T(x)+1$ different paths, and in all of them return $1$.
If $b = 1$, then have $2y$ different paths, all of them returning $0$.

The $\mathsf{PP}$ oracle returns Yes iff $T(x) \geq y$. I'll let you show how to implement steps 2 and 3.

Second, we can use binary search to determine $T(x)$ exactly. We start by determining some upper bound on $T(x)$: ask whether $T(x) \geq 2^k$ for $k=0,1,\ldots$, until you find a value of $k$ such that $T(x) < 2^k$. Since $T$ runs in polytime, $k$ is polynomial, and so this step takes polytime. Next, you do classical binary search (starting from $0 \leq T(x) < 2^k$), and determine $T(x)$ exactly. Again, this takes polytime since $k$ is polynomial.

Third, using our knowledge of $T(x)$, we can decide whether $T_1(x) \geq y$ in a similar way. For example, we could construct a new machine $T'$ with $T'(x) = T(x) + T_1(x)$, and then decide whether $T'(x) \geq T(x) + y$. You fill in the details.

Finally, we calculate $T_1(x)$ using binary search. This time we can skip the first half-step since we already know that $T_1(x) \leq T(x)$.


NP-complete reductions I've read that "Every problem in NP can be reduced to every NP-complete problem".

My question is on the choice of the word "reduce". If I were to "reduce" a polynomial problem in NP to an exponential problem in NP, I just plain feel weird about using the word "reduce" because I feel like I've increased the problem, not reduced it. So, why do we use the word reduce?

Also, why do we write "reduce A to B" as $A\le_{p} B$. It seems backwards.

A reduction from A to B shows that A is "no harder" than B in some sense. We call it a reduction because it reduces the problem of solving A to the problem of solving B. This is a usage of the word "reduce" that is more mathematical and less about "size"; you can think of it as meaning that we've reduced the amount of work the world has to do, because even though we haven't solved A or B with the reduction we've made it so that a solution to B will automatically also be a solution to A.

Where A was a problem we didn't have any efficient solutions for, and where we already have an efficient solution for B, this does result in A getting "smaller" in a sense. For example, say we'd already come up with an exponential solution to A, and B is an NP-complete problem. Previously, the best we knew was that A was an exponential problem. After someone comes up with the A -> B reduction, now we know it's actually an NP problem.

Yes, you can use a reduction argument to show that an already-known-to-be-easy problem is "no harder" than a hard problem. You can in fact use a polynomial-time reduction from ANY problem in P to ANY other problem whatsoever (that has at least one "yes" instance and at least one "no" instance),  because you can "solve" the P problem in the reduction but simply encode the answer as an instance of another problem. Yes, this is pointless. But it's not "wrong" or inconsistent.

The problem you're having is purely in the analogy you're using, namely that a reduction is a "way of making a problem smaller". That is a reasonable metaphor for one of the usual aims of reduction proofs, which is to show that a problem is "easier" than previously suspected by finding a way to reduce it to another problem already known to be "easier".

But that doesn't help you with the other extremely common use of reduction arguments, which is to show that a problem C is impossible to solve, by finding a reduction from another problem D which is already known to be impossible. Here the reduction argument isn't "making D smaller", it's showing that C is "big".

Try to think of a reduction argument from A -> B as a way of showing that A is "no harder" than B.  When you think of it that way, it's not at all surprising that you can often reduce easy problems to hard ones; we already knew that they were easier! This account also easily explains the incomputability proofs by reduction; if the Halting Problem is no harder than X, then X can't be solvable.


Does "output" always imply halting in computability? $L = \{P : P(n)$ outputs $n^2$ for all $n \in N  \}$

In questions of this nature, are we supposed to assume that "outputs" means "halts and outputs"? In modern programming languages, I can certainly "output" using a print statement and then have the program go into a loop after that.

The output of Turing machine is the content of the tape when it halts.

This is the standard definition. If a machine has written some string $s$ to its tape but hasn't halted yet, a straightforward reduction from the undecidability of the halting problem means that you have no way of knowing if it will ever write more characters to its tape, so you can't know if $s$ will be the "final" output. That means, for example, that you can't say that, if a non-halting computation never changes the string on the tape after the $t$th step, then the output is that unchanging tape string.

However, see Andrej's answer for a way of getting a well-defined output from a non-halting machine. The key point there is that the output tape is read-only so once a bit of the output has been written, you know that bit will never change.


Is integer sorting possible in O(n) in the transdichotomous model? To my knowledge there doesn't exist a $O(n)$ worst-case algorithm that solves the following problem:

  Given a sequence of length $n$ consisting of finite integers, find the permutation where every element is less than or equal to its successor.

But is there a proof that it doesn't exist, in the transdichotomous model of computation?

Note that I'm not limiting the range of the integers. I'm not limiting solutions to comparison sorts either.

Integers can be stably sorted in $O(n)$ time with $O(1)$ additional space. More precisely, if you have $n$ integers in the range $[1, n^c]$, the can be sorted in O(n) time.

This was only shown a couple of years ago by a team including the late Mihai Pătrașcu (which should surprise nobody who is familiar with his work). It's a remarkable result which I'm surprised more people don't know about, because it means that the problem of sorting integers is (theoretically) solved.

There is a practical algorithm (given in the paper above) if you're allowed to modify keys. Basically, you can compress sorted integers more than you can compress unsorted integers, and the extra space that you gain is precisely equal to the extra memory needed to do the radix sort. They also give an impractical algorithm which supports read-only keys.


Reference book for Parallel Computing and Parallel algorithms. Please suggest some books on Parallel Algorithms which teach efficient programming techniques like the ones taught in Udacity course(Introduction to Parallel Programming with CUDA). Also wanted to know that from which reference book or papers are the concepts in the udacity course on Parallel Computing taught...? I wish to study more about such techniques which will make me an efficient parallel programmer...!

Also wanted to know that from which reference book or papers are the concepts in the udacity course on Parallel Computing taught...?

The History of Parallel Computing goes back far in the past, where the current interest in GPU computing was not yet predictable. Some important concepts date back to that time, with lots of theoretical activity between 1980 and 1990. Compared to the complicated trade-offs for current heterogenous systems, those old theoretical algorithms and concepts feel nice, powerful and easy to understand. Uzi Vishkin is a researcher who worked during that period, who still believes in those concepts (without overly compilicated trade-offs):

  Alas, the software spiral is now broken: (a) nobody is building hardware that provides improved performance on the old serial software base; (b) there is no broad parallel computing application software base for which hardware vendors are committed to improve performance; and (c) no agreed-upon architecture currently allows application programmers to build such software base for the future

I recently learned about those old concepts, and corresponding interesting survey articles:

Parallel Algorithms (64 pages)
https://www.cs.cmu.edu/~guyb/papers/BM04.pdf
by Guy E. Blelloch and Bruce M. Maggs – 1996

Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques (104 pages)
http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf
by Uzi Vishkin – October 12, 2010

A Survey of Parallel Algorithms for Shared-Memory Machines (70 pages)
https://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/5865.html
https://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-408.pdf
by Richard M. Karp and Vijaya Ramachandran – March 1988

Limits to Parallel Computation: P-Completeness theory (327 pages)
https://homes.cs.washington.edu/~ruzzo/papers/limits.pdf
by R Greenlaw, H Hoover, W Ruzzo – 1995

Parallel Algorithms (347 pages)
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.466.8142&rep=rep1&type=pdf
by H Casanova, A Legrand, Y Robert – 2008


Uncomputing measurement gate? So one of Aaronson's lecture note (https://www.scottaaronson.com/democritus/lec10.html) pointed out that, if we'd like to simulate a BQP-oracle, technically speaking, the oracle of address-target form.
$$
\forall x\in\{0,1\}^n, b\in\{0,1\}: |x,b\rangle\mapsto|x,f(x)\oplus b\rangle
$$

Because such oracle should linearly extend to superposition inputs, we must detangle the output bit with internal (intermediate) qubits. Then one way is to "un-compute"  the entire program, namely for BQP circuit $\tilde{f}$ computing $f$.
First compute $\tilde{f}$, then apply a CNOT on the answer bit, finally uncompute everything except the CNOT-source bit.

So my problem is, in the previous paragraph, he just simulate the measurement gate by a unitary gate. When we perform the un-computing step, we also uncompute that "fake measurement gate". However, it seems not even make sense to un-measure a state. How should I argue that these techniques would work and eventually take us to $BQP^{BQP}=BQP$ result?

You seem to be under the impression that we need to measure a qubit in order to copy it. That is not the case because the copy operation is performed by the mapping $|a,b\rangle \mapsto |a,a \oplus b\rangle$ which, when $b = 0$, can be realized by a CNOT gate. There is no measurement involved at all. You only need to know how many ancilla bits (i.e., initialized to zero) you need beforehand so as to have an adequate quantum circuit size.


Does a term being normalizable mean the same as the term has a normal form? From Types and Programming Languages by Pierce

  A term $t$ is in normal form if no evaluation rule applies to it—
  i.e., if there is no $t'$ such that $t -→ t'$.

and

  A term $t$ is typable (or well typed) if there is some $T$ such that $t : T$.

In the pure simple typed lambda calculus:

  we consider another fundamental theoretical property of the
  pure simply typed lambda-calculus: the fact that the evaluation of a well-
  typed program is guaranteed to halt in a ﬁnite number of steps—i.e., every
  well-typed term is normalizable.

Does a term being normalizable mean the same as the term has a normal form?

Here is a term which has no normal form in the untyped lambda calculus:

  Recall that a term that cannot take a step under the evaluation relation is
  called a normal form. Interestingly, some terms cannot be evaluated to a nor-
  mal form. For example, the divergent combinator

  $$omega = (λx. x x) (λx. x x);$$

  contains just one redex, and reducing this redex yields exactly omega again!
  Terms with no normal form are said to diverge.

In the pure simple typed lambda calculus,

is $omega$ typable (i.e. well-typed)?
is $omega$ normalizable?
does $omega$ have a normal form?

Yes, a term is normalizable if, and only if, it has a normal form.

It is well known that $\omega = (\lambda x . x x) (\lambda x . x x)$ is not typeable, nor is it normalizable. It is not normalizable because it has an evaluation step ($\beta$-reduction) which evaluates it to itself, so we get $\omega \mapsto \omega \mapsto \omega \cdots$.

To see that it is not typeable, observe that already its subexpression $\lambda x . x x$ is not typeable. For if $x$ has type $T$ then in order for $x x$ to have a type, $T$ must be of the form $T \equiv T \to S$ (because $x$ is applied to something, therefore by the typing rules it must have a function type). But there is no type $T$ such that $T \equiv T \to S$, because the type on the right-hand side is larger (as a syntactic expression) than the type on the left-hand side.


Partitioning a set based on binary predicate Given a collection of objects $X = (x_0,x_1,...,x_{N-1})$ and a binary predicate $F$ which takes as parameters elements of the collection, find a better than $\mathcal{O}(N^2)$ algorithm which partitions the set as:

$X= \bigcup X_j$

such that for any $j$ it holds that $F(x_k,x_l) = 1$ if $x_k,x_l \in X_j$ and $F(x_k,x_s) = 0$ if $x_k \in X_j \land x_s \notin X_j$ (boolean values are being used at True/False).

My initial guess was to use a divide and conquer algorithm but was not able to find a merging algorithm which would make the divide-and-conquer strategy worth it in terms of complexity gain.  I imagine this is a standard problem but I am not sure where to look for a solution or if such a solution exists for an arbitrary binary predicate.

There is no deterministic algorithm whose worst-case running time is asymptotically better than $O(N^2)$.  One can prove this with an adversarial argument.

Consider running the algorithm on the following input:

Input #1: $F(x_i,x_i)=1$, and $F(x_i,x_j)=0$ if $i \ne j$.

Keep track of the sequence of pairs $(x_i,x_j)$ of objects that $F$ is evaluated on before it terminates.  If the running time of the algorithm is is $o(N^2)$, then for some sufficiently large $N$ the algorithm must make strictly fewer than $N^2-N$ queries to $F$, so there must be some pair of objects that it doesn't evaluate $F$ on, say $F(x_3,x_7)$.  But then consider running the algorithm on the following input:

Input #2: Same as input #1, except that $F(x_3,x_7)=1$.

Since the algorithm does not evaluate $F(x_3,x_7)$, the algorithm cannot distinguish these two inputs, and must produce the same output on Input #1 and Input #2.  However, the correct answer is different for these two inputs.  This means that the algorithm's output will be incorrect for at least one of these two inputs.

Therefore, any deterministic algorithm whose worst-case running time is asymptotically better than $O(N^2)$ is not correct on all inputs.


Partially diagonalizing a matrix Suppose I have an $n\times n$ matrix. I would like to keep an $m\times m$ subblock undiagonized, while keeping the rest diagonized. Is there any algorithm for this?

More precisely, I mean using unitary matrix $U$ to realize

$$  U^* \pmatrix{ A & B \\ C & D }  U =  \pmatrix{A' & 0  \\ 0 & D'  }   $$ where submatrix $A'$ is diagonal, and $D' \approx D$.

In general $U$ will only be unitary if your composed matrix is hermitian.
I will answer the more general problem that the matrix is partially diagonalizable:
$$U^{-1} \begin{pmatrix}A & B \\ C & D\end{pmatrix} U = \begin{pmatrix}A' & 0 \\ 0 & D'\end{pmatrix}.$$
The diagonal matrix $A'$ contains the eigenvalues on its diagonal. You must already know them and their corresponding left and right eigenvectors. Now let $U_\text{eig}$ consist of the right eigenvectors and $V_\text{eig}$ consist of the left eigenvectors as columns. Then choose
$$U=(U_\text{eig}|V_\text{eig}^\perp)$$
where $\perp$ denotes an orthogonal complement (a basis of the null space).

Proof: Say, you have a matrix $U$ represented by $(U_\text{eig}|U_\text{rem})$ that partially diagonalizes your matrix. Then split its inverse like so: $V = (V_\text{eig}|V_\text{rem})$ with $U^{-1} = V^T$. We know that $V_\text{eig}$ contains left eigenvectors as columns.
It holds
$$I = U^{-1}·U = V^T·U
     = (V_\text{eig}|V_\text{rem})^T · (U_\text{eig}|U_\text{rem}).$$
Separated:
$$
\begin{array}{cc}
I = V_\text{eig}^T · U_\text{eig} & 0 = V_\text{eig}^T · U_\text{rem} \\
0 = V_\text{rem}^T · U_\text{eig} & I = V_\text{rem}^T · U_\text{rem}
\end{array}
$$
The equation $0 = V_\text{eig}^T · U_\text{rem}$ means that $U_\text{rem}$ is an orthogonal complement to $V_\text{eig}^T$.
You may not know the precise content of $V_\text{eig}$,
but orthogonality to $U_\text{rem}$ is invariant under change of the basis or re-ordering of columns.
Thus for your computation you can choose any left eigenbasis for your selected eigenvalues.


Can all $O(n)$ problems be solved without nested loops? There are examples of algorithm implementations that contain nested loops but are of complexity O(n), and some of them have corresponding implementations that contain no nested loops. So here comes a question, can all such implementations be simplified or converted to an implementation with only top layer loops? Namely, can all problems that have an $O(n)$ algorithm be solved with an algorithm without nested loops?

You can write an interpreter for any reasonable instruction set usin a single loop with a very, very long if/ else if / else if... statement. That should cover about all solvable problems. You can calculate the Ackerman function with one loop without recursion (not in the lifetime of the universe for n >= 4, but in principle).


What do `i` and `Number` represent in the Bakery Algorithm? I am studying the bakery algorithm, and I am unsure of what the variable i represents in it. I understand that Entering represents a bool value to protect Nummber while it is updating, but I'm having a hard time finding clear explanations as to what variable is doing what.

Is Number an array of threads? Is i a particular thread? Or the value being updated?

What do i and Number actually represent?
What is passed in via Thread(integer i)? The value we are locking? Or a thread ID number?
Is there a value that represents a value being locked?

For reference, here is the Bakery Algorithm I am referencing, from Wikipedia:

   // declaration and initial values of global variables
   Entering: array [1..NUM_THREADS] of bool = {false};
   Number: array [1..NUM_THREADS] of integer = {0};

   lock(integer i) {
       Entering[i] = true;
       Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
       Entering[i] = false;
       for (integer j = 1; j <= NUM_THREADS; j++) {
           // Wait until thread j receives its number:
           while (Entering[j]) { /* nothing */ }
           // Wait until all threads with smaller numbers or with the same
           // number, but with higher priority, finish their work:
           while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ }
       }
   }

   unlock(integer i) {
       Number[i] = 0;
   }

   Thread(integer i) {
       while (true) {
           lock(i);
           // The critical section goes here...
           unlock(i);
           // non-critical section...
       }
   }

As the Wikipedia page says, (emphasis mine),

  Lamport envisioned a bakery with a numbering machine at its entrance so each customer is given a unique number. Numbers increase by one as customers enter the store. A global counter displays the number of the customer that is currently being served. All other customers must wait in a queue until the baker finishes serving the current customer and the next number is displayed. When the customer is done shopping and has disposed of his or her number, the clerk increments the number, allowing the next customer to be served. That customer must draw another number from the numbering machine in order to shop again.

  According to the analogy, the "customers" are threads, identified by the letter i, obtained from a global variable.


Alternative Method for Computing Two's Complement Binary -> Decimal I proposed this method of converting a two's complement binary number to decimal to my professor and he said it was wrong. Some older guy in the class just shook his head at me and gave me a condescending stare. I'm willing to admit I'm wrong when I'm wrong but I can't find a case where it doesn't work.

Example

Take a two's complement binary representation of -38

1 0 1 1 0 1 0

The method I was taught is, starting at the right, keep the bits until you encounter a 1. Then flip all bits after that one. Which gives

0 1 0 0 1 1 0 = 38

The method I thought was easier since it doesn't involve any binary manipulations is treat the most significant bit as having a minus sign. So you would simply calculate the answer as

1*(-64) + 0*(32) + 1*(16) + 1*(8) + 0*(4) + 1*(2) + 0*1 = -38

What is wrong with my method?

No error. in fact, if you add the binary representation of (-38) and 38 as unsigned 7-bit integer without overflowing, you'll get $10000000_2$, then due to overflow the lowest 7 bits is preserved, resulting 0. This property holds for all $0<x<2^6$, ie. denoting $u(x)$ the unsigned value from 2's component representation of $x$, then $$u(-x) + x = 2^7, (x>0)$$ thus $$\begin{align}-x =& u(-x)-2^7\\=&(u(-x)-2^6)+(-2^6)\end{align}$$ ie. subtract the highest bit, and add back the minus bit. This can be extended from 7-bit to n-bit.


If $L = L(M)$ then $L$ is a subset of $L(M)$ and $L(M)$ is a subset of $L$ If $L = L(M)$ then $L$ is a subset of $L(M)$ and $L(M)$ is a subset of $L$.

Can anyone clarify what does this mean?

This is just a set-theoretical equality. Two sets are equal precisely when they are included in one another: $A = B$ iff $A\subseteq B$ and $B\subseteq A$. The notation is applied in the context of languages of automata. In order to show an automaton $M$ defines language $L$, you have to show it accepts all strings from $L$, and no more than those strings.

Basic, when doing automata and language theory, I am afraid.


Counting islands in Boolean matrices Given an $n \times m$ Boolean matrix $\mathrm X$, let $0$ entries represent the sea and $1$ entries represent land. Define an island as vertically or horizontally (but not diagonally) adjacent $1$ entries.

The original question was to count the number of islands in a given matrix. The author described a recursive solution ($\mathcal{O}(nm)$ memory).

But I was unsuccessfully trying to find a streaming (left to right, and then down to the next row) solution that dynamically counts islands with $\mathcal{O}(m)$ or $\mathcal{O}(n)$ or $\mathcal{O}(n+m)$ memory (there are no limits for the time complexity). Is that possible? If not, how can I prove it?

A few examples of expected outputs for certain inputs for the count function:

$
count\begin{pmatrix}
010\\
111\\
010\\
\end{pmatrix} = 1; %
count\begin{pmatrix}
101\\
010\\
101\\
\end{pmatrix} = 5; %
count\begin{pmatrix}
111\\
101\\
111\\
\end{pmatrix} = 1;
$

$
count\begin{pmatrix}
1111100\\
1000101\\
1010001\\
1011111\\
\end{pmatrix} = 2$

$
count\begin{pmatrix}
101\\
111\\
\end{pmatrix} = 1$

Orlp gives a solution using $O(n)$ words of space, which are $O(n\log n)$ bits of space (assuming for simplicity that $n=m$). Conversely, it is easy to show that $\Omega(n)$ bits of space are needed by reducing set disjointness to your problem.

Suppose that Alice holds a binary vector $x_1,\ldots,x_n$ and Bob holds a binary vector $y_1,\ldots,y_n$, and they want to know whether there exists an index $i$ such that $x_i=y_i=1$. They run your algorithm for the $2\times(2n-1)$ matrix whose rows are $x_1,0,x_2,0,\ldots,0,x_n$ and $y_1,0,y_2,0,\ldots,0,y_n$. After the first row is read, Alice sends Bob $\sum_i x_i$ as well as the memory contents, so that Bob can complete the algorithm and compare $\sum_i (x_i+y_i)$ to the number of connected components. If the two numbers match, the two vectors are disjoint (there is no index $i$), and vice versa. Since any protocol for set disjointness needs $\Omega(n)$ bits (even if it can err with a small constant probability), we deduce an $\Omega(n)$ lower bound, which holds even for randomized protocols which are allowed to err with some small constant probability.

We can improve on Orlp's solution by using noncrossing partitions. We read the matrix row by row. For each row, we remember which 1s are connected via paths going through preceding rows. The corresponding partition is noncrossing, and so can be encoded using $O(n)$ bits (since noncrossing partitions are counted by Catalan numbers, whose growth rate is exponential rather than factorial). When reading the following row, we maintain this representing, and increase a counter whenever all ends of some part are not connected to the current row (the counter takes an additional $O(\log n)$ bits). As in Orlp's solution, we add a final dummy row of zeroes to finish processing the matrix. This solution uses $O(n)$ bits, which is asymptotically optimal given our lower bound.


Proof that fast broadcasts have to target larger cycles first I am having trouble trying to formulate a simple proof. I can clearly see that what I am trying to prove is correct but to prove it I am not sure what to do.

The problem is a broadcasting problem on a graph. My graph contains two cycles. The two cycles are joined by a single vertex $v$. If the vertex $v$ contains some info that it wants to broadcast to all other vertices on the graph what is the minimum number of rounds required to achieve this.

So a proof I am trying to formulate is that in order to achieve the minimum broadcast time I would have to first broadcast on the largest of the two cycles.

I was thinking of a proof by contradiction. Something like assume that we first broadcast on the smaller cycle and somehow show that it could lead to a broadcast time that is larger than the time if we were to start on the larger cycle.

To clarify, suppose we have two cycles $C_1$ and $C_2$ such that $|C_1| \ge |C_2|$. So the minimum broadcast time from vertex $v$ denoted by $b(v)$ would require us to broadcast on the larger cycle first.

Let $b_0$ be the minimal broadcasting time of an information from vertex $v$ to the cycle $C_0$ and $b_1$ be the minimal broadcasting time of an information from vertex $v$ to the cycle $C_1$.

Remark that since $C_0$ and $C_1$ are cycles the fastest way to broad cast is for $v$ to broadcast first one of his neighbor and then the other.

Since $C_0$ and $C_1$ are only connected by $v$ and $v$ already have the information we know that spreading the information through $C_i$ will not improve the minimal broadcasting time for $C_{1-i}$.

3 cases (first one developed the others just ideas):

$b_0>=b_1+2$ (hence $|C_1|>|C_2|+3$) if $v$ start broadcasting his two neighbor in $C_0$ and then those of $C_1$. The time the information reach the last vertex in $C_0$ will be $b_0$ and the last vertex in $C_1$ $b_1+2$ hence $b_0$ in total. And you can't do better by definition of $b_0$
$b_0=b_1+1$ if you start twice by $1$ you will do at best $b_0+2$ and you do better by choosing $0$
$b_0=b_1$ it doesn't really matter but if the parity of the two cycle is different you may want to start by the odd one (or even not sure :D)


Time complexity of $L=\{a^nb^n | n \ge 1\}$ Consider the following language:
$$L=\{a^nb^n | n \ge 1\}$$
I constructed the following Turing Machine:
\begin{eqnarray}
T &=& (Q, \Sigma, \Gamma, \delta, q_0, B, F) \nonumber \\
Q &=& \{q_0, q_1, q_2, q_3, q_4\} \nonumber \\
\Sigma &=& \{a, b\} \nonumber \\
\Gamma &=& \{a, b, X, Y, B\} \nonumber \\
F &=& \{q_4\} \nonumber
\end{eqnarray}

When the input comes as $aabb$, the Turing Machine works like this:

How can you know the time complexity of this Turing Machine?

If I correclty understand the algorithm, your TM starts "marking" the first $a$, then it finds the first $b$ and marks it, then it comes back the the first unmarked $a$ and so on. So, assuming that you have in input a string $w$ of lenght $n$ that belongs to the language $L$, you have $\frac{n}{2}$ $a$'s that have to match with the same number of $b$, each $a$ is paired to a $b$ that is $\frac{n}{2}$ cells away, so to perform a complete matching you need $\frac{n}{2}$ transitions from an $a$ to reach the $b$ to be coupled with it, and again $\frac{n}{2}$ transitions to reach the next $a$, so in total $n\cdot \frac{n}{2}$ transitions (actually, you have to perform an extra transition for each letter to put the head in the right place, so the exact amount of transitions is $\frac{n^2}{2}+n+1=O(n^2)$).
Now, let us consider a word $w$ of lenght $n$ that does not belong to the language $L$. If it start with $b$, it is immediately rejected, so suppose $w=a^hb^kv$, where $v\in a\Sigma^*$ has lenght $j>0$ and $h+k+j=n$. If $k\leq h$, then the TM will performs $\frac{k^2}{2}+k+1$ transitions before stopping (and rejecting $w$), while if $k>h$, then it will make $\frac{h^2}{2}+h+1$ transitions. So, the worst case correspond to the maximum of the function
$$
f(h,k,j)=\cases{\frac{k^2}{2}+k+1, \quad k\leq h\\ \frac{h^2}{2}+h+1,\quad k> h}
$$
on the constraint $h+k+j=n$, $j>0$, and it is not difficult to see that it is reached for $|h-k|=1$ and $j=1$.
Summing up: the worst case is reached when $w$ belongs to the language $L$, and the TM must carry out $O(|w|^2)$ transitions.

If you want to play with your TM and see the exact number of transitions, go here, compile and load a word, enjoy!


Subtlety of a bar in introduction rule I am going through the following lecture notes by Frank Pfenning :

http://www.cs.cmu.edu/~fp/courses/15317-f17/lectures/02-natded.pdf

In page no 5 I cam across the introduction rule  .

The rule reads that $A$ is contained in $B$ if $B$ is true  under the assumption that  $A$ is true .

But in the text a subtle point about the beginning bar of the proof is mentioned which are a below in the images :

Why would it be incorrect to say that "The truth of A leads to the truth of B " . Even if the truth of A has been
introduced durng the process of proving the truth of B , it surely means that the truth of A leads to truth of B . As in
the graph or pictorial representation there are no other statement which are in conjuction with "A" anywhere .

What is the subtlety here in emphasing a misconception or a misleading picture obtained from omiting the bar ?

P.S : I did go through the following paragraphs illustrating the proof of a statement . This paragraph
emphasizes on some phenomenon called discharging of assumptions , which I feel would require a detail understanding
and might come up in the next question that I would be posting so as to gain a better understanding of the content .
But for the time being , I would try to understand the matter in this question with the hope that it might help while
understanding the following topics .

Let's try an example. Let's say you're trying to prove the following:

Simple Theorem over the natural numbers: If $n$ is even, then $n+1$ is odd.

What he's trying to say is that you don't need an independent proof that $n$ is even. In the natural numbers, this isn't even true, since not all numbers are even. What he's trying to say is that when trying to prove an implication like the Simple Theorem above, you're allowed to introduce the assumption that $n$ is even, and from that assumption, together with whatever other axioms you're using, try to prove that $n+1$ is odd. If you succeed in this, you can now correctly conclude that the implication is true.

From his paper:

  The rule makes intuitive sense, a proof justifying A ⊃ B true assumes, hypothetically, the left-hand side of the implication so that A true, and uses this to show the right-hand side of the implication by proving B true. The proof of A⊃B true constructs a proof of B true from the additional assumption that A true.

The whole painful stuff with the bars and labels is a variation of the pain that comes with other deduction systems when you're trying to create a proof context to hold the introduction of an assumption. When these contexts get nested in a complicated proof, it requires machinery analogous to lexical variable scoping rules in programming languages. The assumptions have to come and go properly so they don't allow unsound deductions in other parts of the proof.

EDIT: per request of original poster.

OK, let's dig into this some more. I'm going to use some different notation. The notation

$$
\Gamma \vdash \sigma
$$

means some set of axioms $\Gamma$ proves some formula $\sigma$, where the turnstile $\vdash$ means "proves". Now the inference rule we're looking at can be written like this. We can conclude

$$
\Gamma \vdash A \rightarrow B
$$

if we can prove

$$
\{\Gamma; A\} \vdash B
$$

where the semicolon means we've added formula $A$ to the set of axioms $\Gamma$. Note that this also creates what I've been calling a "proof context" where we're keeping track of assumptions we've been making. The Pfenning paper uses labels on bars to do the same thing.

Let's try it on a complicated example with nested proof contexts: prove the tautology

$$
A \rightarrow (B \rightarrow (C \rightarrow B))
$$

In our notation, proving this tautology looks like this:

$$
\{\} \vdash A \rightarrow (B \rightarrow (C \rightarrow B))
$$

That is, $\Gamma$ is empty since we're proving a tautology.

Here we go, using our rule of inference.

We can prove

$$
\{\} \vdash A \rightarrow (B \rightarrow (C \rightarrow B))
$$

if we can prove

$$
\{A\} \vdash B \rightarrow (C \rightarrow B)
$$

Let's keep going.

We can in turn prove

$$
\{A\} \vdash B \rightarrow (C \rightarrow B)
$$

if we can prove

$$
\{A, B\} \vdash (C \rightarrow B)
$$

One more application of our rule:

We can prove

$$
\{A, B\} \vdash (C \rightarrow B)
$$

if we can prove

$$
\{A, B, C\} \vdash B
$$

But this follows easily: since B is already an axiom, it follows that we can prove it. But we only got this axiom from our inference rule that allowed us to add it safely.


Origin of quantum complexity theory Who was/were the first person/people to introduce the topic of quantum complexity theory and problem classes like BQP and QMA?

The class BQP (see also Complexity Zoo: BQP) was defined by

E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing 26, pp. 1411-1473 (1997).

The class QMA (see also Complexity Zoo: QMA) was defined by

A. Kitaev. Quantum NP. Talk at AQIP’99: Second Workshop on Algorithms in Quantum Information Processing, DePaul University (January 1999).

which apparently built on the idea of a "quantum proof" suggested by

E. Knill. Quantum randomness and nondeterminism. Technical Report LAUR-96-2186, Los Alamos National Laboratory (1996). [arXiv:quant-ph/9610012].

An important relative to QMA, which is perhaps more delicate but which in a certain respect is a more exact analogue of NP for quantum computation, is the class QMA1 (Complexity Zoo), in which the completeness constraint is perfect (i.e. for YES instances, there is a "quantum proof" with acceptance probability 1, albeit for a noiseless quantum computer). This was defined in

S. Bravyi. Efficient algorithm for a quantum analogue of 2-SAT (2006).
[arXiv:quant-ph/0602108]

There are other interesting quantum classes, of course. If you want an introduction to the subject, a good start would be

John Watrous. Quantum Computational Complexity. Encyclopedia of Complexity and System Science, Springer (2009). [arXiv:0804.3401].


VC dimension of monotone disjunctions of length k over n variables? There are of course $n \choose k$ monotone disjunctions which bounds the VC dimension at $\log_2 {n \choose k}$. I'm wondering if this is bound at $k \log_2 n$? (Possibly follows from combinatorial identities).

More generally I'm looking at the claim in An algorithmic theory of learning: Robust concepts and random projection: "Further, it is NP-hard to learn a disjunction of $k$ variables as a disjunction of few than $k \log n$ variable." The author states this without proof; I'm assuming it's well-known or obvious but am trying to figure out why or where it is proved.

Yes.  This bound follows by a little bit of straightforward manipulation:

$${n \choose k} = {n \times (n-1) \times \dots \times (n-k+1) \over k!} \le {n \times n \times \dots \times n \over 1} = n^k.$$

Now taking the logarithm of both sides, we see that

$$ \lg {n \choose k} \le \lg(n^k) = k \lg n.$$

The bound can also be derived from bounds listed in Wikipedia: it follows from the fact that ${n \choose k} \le n^k/k!$.  Check out Wikipedia in the future -- it's often helpful!


Is the credit assignment problem a well-posed one? Credit assignment is the process of assigning credit (or blame) to a particular move in a sequence of moves (temporal credit assignment) or to a particular node (structural credit assignment) among many nodes, for example, in a network.

My question is somewhat philosophical: Does it even make sense to speak of credit assignment as a problem to be solved?

Take the example of a football (soccer) team. (I read in a paper that robo-soccer teams face a version of the credit assignment problem). However, even in the case of a real-life soccer team composed of humans players, it is virtually impossible to separate the performance of an individual in scoring a goal from the contribution of the rest of the team in the most general case. If quantifying and assigning credit to players is so difficult, does it even make sense to try to assign credit to nodes in a complex system, with many pieces that are interacting in subtle ways?

If you can do it well, it is useful.  If you can accurately identify which move was to blame for bad outcomes -- or which one is to credit for good outcomes -- that is useful in helping you learn to make better moves.  I'll let you decide whether that's enough for it to make sense to speak of it as a problem to be solved. I'm not very knowledgeable about philosophy, so I don't know whether that qualifies.


How to compute time complexity of a program if the time complexity of a function called inside a loop is known? This is the question-

  Let $A[1,....,n]$ ba an array storing a bit $(1\,\,or\,\,0)$ at each location, and $f(m)$ is a function whose time complexity is $\theta(m)$. Consider the following program -

counter = 0;
for( i = 1; i <= n; i++)
{
    if(A[i] == 1)
        counter++;
    else
    {
        f(counter);
        counter = 0;
    }
}

  Options are :
  (A)$\Omega(n^2)$
  (B)$\Omega(n\log n)$ and $O(n^2)$
  (C)$\Theta(n)$
  (D)$\mathcal{O}(n)$

The solution says - "Since it contains only one loop, so compute with linear complexity, hence the complexity will be $\Theta(n)$".
My doubt is, what if the time complexity of the function $f(m)$ was given to be $\theta(2^n)$ or of the order that grows in exponential time? Would the solution given in the book be correct in case of exponential time?

This is actually an example of amortized analysis. The easiest way to see what's going on is to separate $A$ as follows: $A=1^{n_1}01^{n_2}0\cdots1^{n_k}$. You can check that the function $f$ is called with arguments $n_1,n_2,\ldots,n_{k-1}$. Since $n_1+\cdots+n_k = n-(k-1)$, in particular $n_1+\cdots+n_{k-1} \leq n$, and so the total time spent running $f$ is $O(n_1+\cdots+n_{k-1}) = O(n)$. The time spent on executing the rest of the program is $\Theta(n)$, and so the total running time is $\Theta(n)$.

If we did want to use amortized analysis, the idea would be as follows. Suppose for simplicity that $f(m)$ runs in time $m$ (exactly). Each time the counter is incremented, we set aside another "time unit", and withdraw the time units set aside when $f$ is called. You can check that we always have enough time units in store. Under this scheme of accounting, incrementing the counter takes time $O(1)$, and calling $f(m)$ takes no time; this can only overestimate the actual running time (since we might have leftover time units). Therefore the total running time is $O(n)$.


Applications affected by memory performance I'm writing a paper on the topic of applications affected more by memory performance than processor performance. I've got a lot written regarding the gap between the two, however I can't seem to find anything about the applications that might benefit more from memory performance.

I suppose these are applications that make a large amount of memory references, but I have no idea what kind of applications would make such large number of references to make it stand out?

Can you please give me any pointers on how to proceed, some links?

Memcache and other memory heavy software
software with large working sets
Diskless Servers
Software backed by Ramdisk
Any software that needs fast access to data (other than Databases)


When does this algorithm fail? The problem

Given $n$ stacks of $k$ integers each. What is the maximum sum that can be achieved by removing exactly $p$ integers?

The following example illustrates the problem.

$n$ = 3, $k$ = 4, $p$ = 3

stack 1: 2, 5, 12, 5

stack 2: 10, 3, 12, 50

stack 3: 7, 4, 20, 20

Note that the top of a stack is the leftmost element.

Here, the optimal solution is to pick all the first three numbers from stack 3, which gives a sum of 31.

The algorithm

I came up with the following algorithm.

The idea is to calculate the best possible sum for each stack if all $p$ elements were chosen from that particular stack. This sum only considers the integers that can possibly be taken.

Then, greedily take the top element from the stack with the best possible sum. And update the sum for all stacks because now only $p-1$ integers need to be popped.

The question

is this algorithm always going to produce a correct answer? If not, when would this fail?

Disclaimer

I am aware that a dynamic programming solution can solve the problem in $O(npk)$ time.

This is based on the following problem from a previous contest on google coding competitions platform. (https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d40bb)

Here is a counterexample, with $p = 2$:

stack 1: $600,600$.
stack 2: $1000,0$.
stack 3: $1000,0$.

Your algorithm will choose the top element from stack 1 and one of the top elements from the other stacks, but it is better to choose the top elements of stack 2 and stack 3.

Disclaimer: This is based on your description of the algorithm. I don't understand some of the notation in the algorithm itself.


Is my algorithm a $O(nm \lg m)$ solution for sorting a row and columnwise sorted $2D$ array? The problem (from MIT 6.006 course) is the following:

  In this problem, you are given a $2D$ array of integers $A$ that has $n$ rows and $m$ columns. (Assume $m$ is much (e.g., exponentially) smaller than $n$.) Array $A$ has one special property: the integers in every row of $A$ and every column of $A$ are non-decreasing. More formally, $A[i, j] ≤ A[i, j + 1]$ for every $i = 1, 2, \ldots , n$ and $j = 1, 2, \ldots , m−1$, and $A[i, j] \leq A[i+1, j]$ for every $i = 1, 2, \ldots , n−1$ and $j = 1,2, \ldots ,m$.

  Describe and analyze an algorithm with running time $O(nm \lg m)$ that produces a sorted $1$~$D$ array of length nm that has exactly the same elements as $A$. For example, for the $2D$ array given above, the algorithm should return $[1, 2, 3, 4, 4, 5, 5, 6, 8, 10, 19, 30]$.

The solution to this problem is to use the merge routine from merge-sort, along with a min-heap or an AVL tree.

This works by maintaining m pointers, one for each column of the $2D$ input array.
The pointers start at the top of each column and we put each value of where the pointers point to into a min-heap (thus, the min-heap will at any given time contain at most m elements). We then use the merge routine from merge-sort to combine all the columns into a $1D$ array. The min-heap tells the merge routine which item to put next into the resulting array. When extracting an element from the heap, the pointer of the column of that element is advanced one element "down" and the corresponding value is inserted into the min-heap. This process is being performed until all the elements are processed.

I came up with a slightly different solution and was wondering if the time complexity still turns out to be $O(nm \lg m)$.

My solution works as follows (essentially a modified version of merge-sort):

Start with the entire array
Split the array in $2$ halfes by performing a column split (each of size $n \times m/2$)
Recursively split the subproblems into halfes until we reach the base case
Base case: the problem has size $n \times 1$ (a single column of the input array) and we simply return it (a $1D$ array that is already sorted)
For every other step than the base case, merge the two $1D$ arrays into a $1D$ array that contains all the elements of the two columns but now sorted

Concerning the time complexity, my thoughts are:

We split each subproblem into half the number of columns, thus resulting into $O(\log n)$ splits.
At each level of the recursion we perform $O(nm)$ work (for merging).

Combining the two parts, this gives: $O(nm \lg m)$. Is this correct or am I missing something here?

My attempt:

$T(m,n) = 2T(\frac{m}{2}, n) + O(nm)$.
If I guess $O(nm \lg m)$ as a solution to this recurrence $\forall k$, $k < m$, this is what I get by induction:

\begin{align}
T(m, n) &= 2T(\frac{m}{2}, n) + O(nm) \\
&= 2T(\frac{m}{2}, n) + c \cdot nm \\
&= 2(c \cdot n\frac{m}{2} \lg\frac{m}{2}) + c \cdot nm \\
&= c \cdot nm (\lg m - \lg 2) + c \cdot nm \\
&= c \cdot nm \lg m - c \cdot nm + c \cdot nm \\
&= c \cdot nm \lg m
\end{align}

As far as I can see, this is the desired complexity but I still feel like I am missing something here.

You should be careful using standard big-O analysis with more than one variable, I read a paper recently pointing out that this analysis can fail if certain assumptions are not met. In any case, let's assume for simplicity that $m$ is a power of 2. If it is not, the analysis will be very similar, just with some extra floors and other ugly stuff. In this case, we merge last two $n\times m/2$ arrays in time $2\cdot c\cdot (m/2)\cdot n$. Before that, we merged four (2x2) $n\times m/4$ arrays in time $4\cdot c\cdot (m/4)\cdot n$. Seeing the pattern, we add all of these times to get
$$\sum_{k=1}^{\log_2m}2^k\cdot c\cdot (m/2^k)\cdot n=\sum_{k=1}^{\log_2m}c\,m\,n=c\,m\,n\log_2m=O(n\,m\log m)$$
As a formality for the curious, I now cover the case where $m$ is not a power of 2. Then instead of two $n\times m/2$ arrays, we will have an array of size $n\times\lfloor m/2\rfloor$ and an array of size $n\times\lceil m/2\rceil$. Similarly, in the next step we get four arrays of sizes $n\times\left\lfloor\frac{\lfloor m/2\rfloor}{2}\right\rfloor$, $n\times\left\lceil\frac{\lfloor m/2\rfloor}{2}\right\rceil$, $n\times\left\lfloor\frac{\lceil m/2\rceil}{2}\right\rfloor$, and $n\times\left\lceil\frac{\lceil m/2\rceil}{2}\right\rceil$. Recursively, we have a runtime of
$$T(n,\,m)=T(n,\,\lfloor m/2\rfloor)+T(n,\,\lceil m/2\rceil)+c\,m\,n$$
Nobody wants to solve that, so I simply show that the complexity is still $O(n\,m\,\log m)$ if we take $m$ to be the next largest power of 2, call it $m'$. So I want to show that
$$\frac{n\,m'\,\log m'}{n\,m\,\log m}=O(1)$$
Say $m'=2^k$ and $m=f\cdot2^k$ for some $0.5\leq f<1$ ($f$ as in fractional coefficient). We can write $m$ this way, since it is between $2^{k-1}$ and $2^k$ by construction of $m'$. This means that $m'=f^{-1}m$. Then we have
$$\frac{n\,m'\,\log m'}{n\,m\,\log m}=\frac{n\,f^{-1}m\,\log(f^{-1}m)}{n\,m\,\log m}=\frac{n\,f^{-1}m(\log m+\log f^{-1})}{n\,m\,\log m}=f^{-1}+\frac{f^{-1}\log f^{-1}}{\log m}=O(f^{-1}+f^{-1}\log f^{-1})=O(1)$$
Then the case when $m$ is a power of 2 can be applied in general.


Binary trees and preallocated nodes I want to design a binary tree with preallocated nodes, in order to avoid calling malloc/free every time I want to insert/delete a node. The problem is I don't know ahead of time how many nodes the tree will have, so I am thinking I need to allocate a block of nodes at a time, then allocate another block when the first gets used up, etc.

As far as I can tell, I need 3 data structures to accomplish this, but I'm hoping someone can recommend a simpler, more elegant method.

The three data structures I am thinking of are:

Binary tree
Stack (to store the preallocated nodes and easily find the next one to use)
Linked list (to store the different allocated node blocks so they can be located and freed eventually).

The way these would work is:

Initialization

Allocate one block of N nodes
Push each node in the block onto the Stack
Append block to Linked List.

Tree Insert

If stack is empty, allocate another block of N nodes, push them onto the Stack and append it to Linked List
Pop node from stack and store tree node data in it
Add node to tree structure, do balancing, etc

Tree Delete

Find item in tree and remove from tree
Push node back onto Stack to be used later for insert

Cleanup

Destroy tree
Traverse Linked List and delete all node blocks

Using a Stack to store all the preallocated nodes seems like a good idea, since insert/delete operations would be $O(1)$. However, each time a new block of N nodes needs to be allocated, I need to push them all onto the Stack $(O(N))$ and insert it into the Linked List $(O(1))$. Finally, cleanup at the end requires traversing the Linked List $(O(NB))$ where $NB$ is the number of node blocks allocated.

It seems to me I should able to do this with less complexity (maybe 2 data structures instead of 3). Does anyone know of a more elegant method?

What you are doing is called (simple) "object pooling", a topic that has been discussed numerous times. It can be said to have nothing to do binary trees.

The simplest and yet efficient approach is to use a single stack or list, just like the C++ vector class or Java ArrayList, so that you do not have to maintain the "linked list" to keep track of the different allocated node blocks. Initially a block of $N$ nodes is allocated. Use a tail pointer to remember the first free node. Whenever it runs out of free nodes, just allocate $2N$ nodes or $cN$ nodes for a factor $c>1$ of your choice. Memory copy the existing nodes to the new block and free the previous block. Do not worry about the performance of copying nodes, which is just one (system) call that should have been optimized by your language runtime and operating system.

In general, do not write these kinds of utilities from scratch by yourself unless as an exercise to broaden your skill set or enhance your understanding. For example, there is an object pool in boost library if you can use C++. Also, do not do it just for the sake of performance unless you have identified node allocation and deallocation is the performance bottleneck. The recent c/c++ runtime might be fast enough for you on object allocation and deallocation.

I would recommend that you search "object pooling" on the web or, more directly, inside github.com with your choice of language, C if you want to dive further. You will be able to find many articles and many working implementations, (for example, simple object pool.

Finally, in many cases, especially in many programming contests, all you need to do is to preallocate a huge number of nodes like a few millions of them upfront. Then just use them without deallocation. Simple, stupid and wonderful.


Should activation function be monotonic in neural networks? A lot of activation functions in neural networks (sigmoid, tanh, softmax) are monotonic, continuous and differentiable (except of may be a couple of points, where derivative does not exist).

I understand the reason for continuity and differentiability, but can not really understand a reason for monotonisity.

During the training phase, backpropagation informs each neuron how much it should influence each neuron in the next layer.  If the activation function isn't monotonic then increasing the neuron's weight might cause it to have less influence, the opposite of what was intended.  The result would be choatic behavior during training, with the network unlikely to converge to a state that yields an accurate classifier.


Determining whether a change in an memoized algorithm will improve the performance I have an algorithm that constructs an optimal binary tree using dynamic programming.  After introducing what I thought would be an optimization, the algorithm became over 2 times slover. Question: Is there an analytical way to determine whether such change will improve the runtime of an algorithm with memoization?

Python code and description follow:

def solver(problem, memo={}):
    try:
        return memo[problem]
    except KeyError:
        if is_base_case(problem):
            memo[problem] = base_solver(problem)
            return memo[problem]

    best_score, best_solution = INFINITY, None

    for left_subproblem, right_subproblem in all_splits(problem):

        left_solution = solver(left_subproblem, memo)

        if (base_score(problem) + score(left_solution) >= best_score):  #optimization
            continue                                                #optimization

        right_solution = solver(right_subproblem, memo)

        current_score = base_score(problem) + score(left_solution) + score(right_solution)
        if (current_score < best_score):
            best_score = current_score
            best_solution = combine_solutions(problem, left_solution, right_solution)

    memo[problem] = best_solution
    return memo[problem]

The function iterates over all ways to split an instance problem into two subproblems, recursively solves them and stores the solutions.
Optimal tree is a tree that has the lowest score, determined by the score() function. The score of a tree is always positive and is a sum of a base score of the root node plus the score of the subtrees.
The optimization in question are the lines marked as #optimization. It's supposed to avoid solving the right subproblem, if, based on the left result, it's impossible to create a solution with a better score than the current best.
Intuitively I understand that the reason why the function became less efficient is because it avoids solving the right subproblem sometimes, which means that it also memoizes less cases, which in turn makes it perform more work. However, this is just my hindsight and I would like to have a rigorous way to analyse the problem, in case an algorithm like this was presented to me in pseudo-code.

Intuitively I understand that the reason why the function became less efficient is because it avoids solving the right subproblem sometimes, which means that it also memoizes less cases, which in turn makes it perform more work.

This is impossible. Not solving and memoizing a subproblem can never make the algorithm slower. Either the subproblem will never be needed (in which case not memoizing it only saves work) or it will turn out to be necessary after all, in which case we would have to compute it. However, the worst case is only that we do not save any time: if we skip the computation now, we might have to do it in the future, but this is not more work than doing it now.

The optimization you've done will never cause more work to be done on computing subproblems. Thus, the only reason it could make the algorithm slower is if the optimization itself is expensive to compute. It seems likely either score or base_score are very slow methods, and your optimization causes them to be evaluated an additional time. You might be able to speed it up by storing base_score and score(left_solution) in a temporary variable.


Could the empty language be NP-Complete? I think the empty language is NP but I'm not sure if it is NP-Complete

You are correct that $\emptyset\in NP$, since we already know that $\emptyset$ can be decided in constant time (a TM that immediately rejects), and $DTIME(O(1))\subseteq P\subseteq NP$.
But $\emptyset$ is not NP-complete, regardless of whether $P=NP$. Indeed, by definition, a NP-complete language $A$ is such that every language $B \in NP$ admits a Karp reduction to $A$, i.e., a function $f$ that is computable in polynomial time and such that $x \in B \iff f(x) \in A$.
If $A= \emptyset$ and $B \neq \emptyset$ then no such function exists, since there is no way to satisfy $x \in B \implies f(x) \in A$.


How to exclude all points adjacent to a given point from the feasible region of IP Consider a basic integer program such as:

$$\begin{align}
\min_x & \quad c^Tx \\
\text{s.t.} & \quad Ax \leq b \\
&\quad x_i \in \{-100,\ldots,100\}
\end{align}
$$

where $x \in \mathbb{Z}^n, A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R^m}$.

Say that I have a feasible point $y \in \mathbb{Z}^n \cap [-100,100]^n$ with the property that all points adjacent to $y$ cannot be optimal. In other words, given $y$, all points in the set:

$$\mathcal{A}(y) = \Big\{ z \in \mathbb{Z}^d ~\big|~ z_i = y_i \pm 1 \Big\}$$

could be excluded from the feasible region of the IP.

I am wondering if there is an elegant way to formulate constraints that will exclude all points that adjacent to $y$ from the feasible region.

You can't eliminate all points in $A(y) \setminus \{y\}$ without also eliminating $y$, as the conjunction of a bunch of linear inequalities always gives a convex region, and $A(y) \setminus \{y\}$ is non-convex.

Here I am assuming we're not allowed to introduce new variables.  If we're allowed to introduce new variables, there are many uninteresting ways to achieve it, by taking advantage of the fact that with integer variables you can express any logical predicate you like; however, it seems unlikely that this will be useful for anything in practice.


Efficiently compute a complete set of representatives of cyclotomic cosets of $2$ modulo $2^n-1$ Let $n > 1$. For an integer $k$ with $0 \leq k \leq 2^n-2$ the cyclotomic class $C_k$ of $2$ modulo $2^n-1$ is the set given by
$$C_k = \{k, k\cdot 2, k \cdot 2^2 , \ldots, k\cdot 2^{n-1} \pmod {2^n-1}\},$$
where the entries are reduced modulo $2^n-1$. Note that either $C_k = C_i$ or their intersection is empty. A set $\{a_1, \ldots, a_m\}$ of integers in $[0, 2^n-1]$ is called a complete set of representatives of the classes if $C_{a_j} \neq C_{a_i}$ whenever $i \neq j$ and
$$
\bigcup_{i=1}^m C_{a_i} = \{0, 1, \ldots, 2^n-1\}.
$$

I am interested in, given $n$, efficiently computing the corresponding complete set of representatives of the cyclotomic classes. Any ideas? I'm hoping to be able to compute this for large enough $n$. Thanks!

You can use simple enumeration.  This will be about as fast as you can achieve, for a modulus of the form $2^n-1$.

Namely, for each possible $k$, you check whether $C_k$ is a new set (distinct from the ones you already know about).  If it is, you add it to the set; if it isn't; you skip it and move onto the next $k$.

This gives an algorithm like the following:

Set $S := \emptyset$ and $A := \emptyset$.  ($A$ holds the set of representatives; $S$ holds the set of elements covered by one of the corresponding cyclotomic classes.)
For each $k=1,2,\dots,2^n-1$:

If $k \notin S$, add $k$ to $A$ and set $S := S \cup C_k$.

The running time of this algorithm will be $\Theta(2^n)$.

This is also within a $\Theta(n)$ factor of optimal.  In particular, any algorithm must have running time at least $\Theta(2^n/n)$.  The reason is that, for a modulus of the form $2^n-1$, the output size of any correct algorithm must be $\Theta(2^n/n)$: there are $\Theta(2^n/n)$ distinct cyclotomic classes.  Therefore, no algorithm can run faster than $\Theta(2^n/n)$ time, since it will take at least $\Theta(2^n/n)$ time to print/construct the desired output.

Why is the output size $\Theta(2^n/n)$.  Well, for the specific modulus $2^n-1$, it is guaranteed that each cyclotomic class has size $n$.  (Proof: $2^n \equiv 1 \pmod{2^n-1}$, so no cyclotomic class can have size larger than $n$.  Also $2^j < 2^n-1$ when $j<n$, so $2^j \not\equiv 1 \pmod{2^n-1}$ when $j<n$.  Therefore each cyclotomic class has size exactly $n$.)  This result is specific to the particular kind of modulus you are focusing on.


Algorithm for searching in BST with only < How could one construct an algorithm for finding a node in a binary search tree that only requires the presence of $<$ on the key type. The ones I can easily also requires $=$.

If what you mean is that you want to build a BST and you only have the $<$ operation, and you only know the algorithms with the $\leq$ operation, you can notice that :
$$a \leq b \Leftrightarrow \neg (a > b)$$
$$\Leftrightarrow \neg(b < a )$$
Hence, using a negation in the right place, you can build your usual algorithm.