Definition of opposite category From page 29 of The algebra of programming :

  For any category C the opposite category $C^{op}$ is defined to have
  the same objects and arrows as C, but the source and target operators
  are interchanged and composition is defined by swapping arguments:

  $$ f \cdot g \text{  in  } C^{op} = g \cdot f \text{ in } C. $$

This doesn't makes sense. Suppose C is the categories of all functions, and we have $f: A \leftarrow B$ and $g: B \leftarrow C$, then $g \cdot f$ doesn't even exist. Or, suppose $f: A \leftarrow B$ and $g: B \leftarrow A$, then $f \cdot g : A \leftarrow A$, and $g \cdot f : B \leftarrow B$, this is not interchanging source and target, this is changing both!

The problem in your first example is that the arrows don't compose. In the first, you have $f: A \leftarrow B$ and $g: C \leftarrow B$, so $f\circ g$ is not in $C$, hence in $C^{op}$ $f : B \leftarrow A$ and $g : B \leftarrow C$, and they still don't compose.

If you had $f: A \leftarrow B$ and $g: B \leftarrow C$, then they compose to $f\circ g =h : A \leftarrow C$ in $C$. In $C^{op}$ you have $f : B \leftarrow A$ and $g : C \leftarrow B$ and get $g\circ f = h : C \leftarrow A$ (remember in $C^{op}$ you want every thing running backwards) .

Your second example is fine, you just have $f : A \leftarrow B$ and $g : B \leftarrow A$ in $C$ and hence $f\circ g : A\leftarrow A$ and $g\circ f:B\leftarrow B$ in $C$. In $C^{op}$, they switch: $f :B \leftarrow A$, $g : A \leftarrow B$ are in $C^{op}$ and so are $g \circ f : A \leftarrow A$ and $f\circ g : B\leftarrow B$.

I wonder perhaps if the phrasing used by Bird is causing a problem. The rule is better stated:

  If $h = g \circ f$ in $C$ , then $h = f \circ g$ in $C^{op}$.

There's also a kind of name overloading going on here, from a programmer's perspective, reusing the same names for the opposite versions is a bit odd, it might make more sense to think along the lines (restating one of the rules):

  If $f : X \leftarrow Y$ is in $C$, then $f^{op} : Y \leftarrow X$ is in $C^{op}$.


Finding the kth smallest element of an array using DAC I'm trying to find the $k^{th}$ smallest element of an array by using Randomized Quicksort, But below code giving erroneous result can anybody help.

from random import randint

lst=[1,3,5,2,4,6]
k=6
n=6

def swap(i,j):
    t=lst[i]
    lst[i]=lst[j]
    lst[j]=t

def rand_partition(p,q):
    # i is the pivot position
    i=randint(p,q)
    while(p<q):
        if(lst[p]>lst[i]):
            swap(p,p+1)
            p+=1
        else:
            p+=1

    swap(p,q)
    return q

def select(p,q,k):
    r = rand_partition(p,q)
    t = r-p+1

    if(k==t):
        return lst[r]
    elif(k<t):
        return select(p,r-1,k)
    else:
        return select(r+1,q,k-t)

res=select(0,n-1,k)

print('%dth Smallest Element = %d' %(k,res))

The problem is in your rand_partition(p,q) function.

I made some changes with comments.

def rand_partition(p,q):
    i=randint(p,q)               # get a random index between p and q
    swap(i,q)                    # move the pivot element to the end
                                 # after now, do the same as normal partitioning
    pivot=lst[q]                 # save pivot
    s=p-1
    j=p
    while(j < q):                #keep invariants (this would be better with a for loop):
        if(lst[j] <= pivot):     # lst[p...s] <= pivot,
            s+=1                 # lst[s+1...j-1] > pivot
            swap(s,j)
        j+=1

    swap(s+1,q)                  # put the pivot in the correct place
    return s+1

Also, you can set a base case for select(p,q,k) (although this is not critical):

def select(p,q,k):
    if (p==q):
        return lst[p]
    #...

For more info: Introduction to Algorithms (Cormen, Leiserson, Rivest & Stein)


Why is T not a minimum spanning tree of G? The Problem: Let T be a tree constructed by Dijkstra's algorithm in the process of solving the single source shortest-paths problem for a weighted connected graph G.
        a. True of false: T is a spanning tree of G?
         b. True of false: T is a minimum spanning tree of G?

I read from Single source shortest paths problem  is a problem  "in which we have to find shortest paths from a source vertex v to all other vertices in the graph."  I read from Partial Solutions that only one of the options is true.

From my intution and the statements above, I reasoned that a is true while b is false. This is because if T is a minimum spanning tree of G, be definition it should also be a spanning tree of G. I am trying to show that b is false with a counterexample but I can't find/draw a graph in which T isn't a min spanning tree.

Can anyone show me a counterexample to b? To me, Dijkstra's algorithm is similar to Prim's algorithm to find MSt, so in the end T should be a min spanning tree.

Vertices: {A,B,C}

Edges: (undirected)
{A,B,4}
{A,C,3}
{B,C,2}

So basically it's a triangle with the given weights. Starting from A, Dijkstra's algorithm will give you (A,B) and (A,C) but the minimum spanning Tree will give you (A,C) and (C,B).


Complexity of while loop using series For the following code fragment:

i = 1;
s = 1;

while(s <= n) {
    i++;
    s = s+i;
    printf("x");
}

How can we go about proving the time complexity of this code is $\Theta(\sqrt{n}))$?

Usually, I use sigma series analysis to figure the time complexity but I am having trouble turning this code into series notation and then using the series to find out the time complexity.

As you see, in each iteration i is increased by 1. Hence, value of s would be $1 + 2 = 3, 1 + 2 + 3 = 6, 1 + 2 + 3 + 4 = 10, \ldots,  \sum_{i=1}^{k}= n$

Hence, $k$ is the time complexity of this code. As we know that $\sum_{i=1}^{k} = \frac{k(k+1)}{2} = \Theta(k^2)$, and $\Theta(k^2) = n$, we can conclude that $k = \Theta(\sqrt{n})$.


What textbooks includes explanations of advanced data structures found commonly in competitive programming? While looking through some problems on CodeForces, I noticed that there were several problems that required knowledge of techniques that just aren't covered in standard algorithm texts.

Topics that I want to understand include

segment trees, least common ancestor, range-minimum query
Fenwick trees
heavy-light decomposition
interval trees
Hopcroft–Karp algorithm
implementations of tries
wavelet trees

There doesn't seem to be any book that comprehensively looks at any of those techniques. The only organized resource that I could find was a list of articles on GeeksForGeeks, but much of the site doesn't seem self-contained and linearly ordered the way a textbook would be. It's fine if not all of the techniques I've listed are covered, but I'd prefer a book that covered as much of it as possible. Any help?

Here are two books written especially for competitive programming:

"Guide to Competitive Programming", Antti Laaksonen:

The book is based on the book "Competitive Programmer's Handbook" by
the same author, which was already really good. This handbook is
still available for free on the author's
website. The commercial version is more comprehensive and contains more topics.
"Competitive Programming 3", by Steven Halim and Felix Halim:

Pretty much the classic book for learning competitive programming.
Maybe a little bit dated.


Is there a bounded-time algorithm for Envy-free cake-cutting? I am engineering student,i have doubts regarding the topic can anyone help me to find solution.

A bounded-time algorithm for the problem has been presented by Haris Aziz and Simon Mackenzie (A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents, arXiv:1604.03655, April 2016).


Minimum square side length to enclose n circles of radius r I thought of a problem but have no idea how to solve it. The problem is as follows:

Given 2 numbers, n and r, find the side length (S) of the smallest square that encloses n circles each of radius r without any overlap among any of the circles.

I though about a greedy approach that would find the optimal position for each circle locally and placing it before moving onto the next one, but realized that it would be difficult without being given definitive positions of each of the circles. Is there a solution to this problem?

This is known as circle packing in a square.  The Wikipedia article I link to has a citation to this webpage, which lists the best packings known for $n \le 10000$, and also has many references to papers that study this problem.  I suggest studying them to see what methods they have used.


Algorithm for queue with multiple repeated different interval events I have N events, each repeats after some time ti. I want a queue where I can pop out next event.

For example, I have events A,B,C with intervals 2,3,5 At the beginning they all are in the queue with values:

A-2, B-3, C-5

When I take out event, it should be A, after that I put it back, but add +2.

B-3, A-4, C-5

Next is B. I add +3

A-4, C-5, B-6

Next is A, I add +2

C-5, B-6, A-6

and so on.

What could be the best algorithm for that?

Use an efficient implementation of priority queues, such as binary heaps. Then, your algorithm would look like this:

proc triggerEvents(events : Array[(String, Integer)]) {
  q = new MinHeap()
  for ( i=0; i<events.size; i++ ) {
    // use event index as key, interval as priority
    q.add(i, events[i][2])
  }

  while ( true ) {
    (i, p) = q.popMin()
    trigger(events[i][1])
    q.add(i, p + events[i][2])
  }
}

With $n$ the number of events, this will take time $\Theta(n \log n)$ for the initialisation¹ and then $O(\log n)$ time for each iteration of the while loop plus whatever trigger does.

In practice, be mindful of overflows.

You can not be asymoptotically faster than that; otherwise we could sort² in time $o(n \log n)$ which is not possible (for unrestricted inputs).

Can be sped up to $O(n)$; see e.g. here.
Add one event per element with its value as time interval. Drop the re-adding from the algorithm and execute $n$ iterations of the while-loop. Trigger just prints the element.


Parameterized vertex cover on $r$-regular graphs I am trying to solve the following exercise from this book:

  Show that CLIQUE PROBLEM, parameterized by the solution size $k$, is
  Fixed-parameter tractable (FTP) on $r$-regular graphs for every
  fixed integer $r$.

Here, the CLIQUE PROBLEM is given a instance $(G, k)$, decide whether $G$ has a clique of size $k$ or not.

First of all, for an instance $(G, k)$,  if $k > r+1$, then the answer is NO, because each vertex is connected with exactly $r$ elements, the maximum size of a clique is $r + 1$ (vertex plus $r$ neighbours). So, we can assume that $k \le r+1$.

Let $N(v)$ be the set of neighbours of $v$.

I thought of that simple algorithm

.... for each vertex $v \in V(G)$

........ check if for any subset $X \subset N(v)$, such that $|X| = k - 1$, $X \cup \{v\}$ is a clique.

Since there is only $\binom r k$ such subsets $X$ for each vertex and we take time polynomial in $k$ to check if $X \cup \{v\}$ is a clique, then, this algorithm is already a FTP and is of the form $\left( k^{O(1)}\binom{r}{k} \right)n$.

If everything is right, them I have solved the exercise. However, the next thing I have to do in the exercise, is to show that this problem is also a FTP considering the parameter $k + r$ (so, $r$ is no longer seen as a constant), and the same algorithm works in this case. Since I was expecting to face a harder exercise in this case of $k + r$, I started to think my solution is not right.

So, what is wrong?

There's nothing wrong with your solution, the exercise is just easier than you expected.

Your analysis correct, apart from missing out the $-1$, so it should be $k^{\mathcal{O}(1)}\cdot\binom{r}{k-1}\cdot n$, which is, of course, of the required form $f(k+r)\cdot n^{\mathcal{O}(1)}$, and the $-1$ doesn't really change anything.

The biggest mistake is writing $\mathrm{FTP}$ instead of $\mathrm{FPT}$. The first is a protocol, the second is a complexity class.

Moving to pure speculation, I would guess the authors were, in the second part, simply looking for reinforcement of the difference between $\mathrm{FPT}$ and in class $\mathrm{X}$ for every fixed value of some parameter (in this case, something like $f(k)\cdot n^{r}$ would work for the first part of the exercise, but not the second. The Hitting Set problem, as an example, has such an algorithm, where the parameter $k$ is the size of the solution, and $r$ is the size of the input sets; it's in $\mathrm{FPT}$ for every fixed $r$, but not in $\mathrm{FPT}$ for parameter $k+r$).


Transition systems that satisfy LTL but not CTL, and vice versa I am learning about temporal logic and model checking systems. One conceptual exercise that I am struggling with is how to create a transition system which satisfies only one of two given properties, when one is in LTL and one is in CTL. For example:

Find a transition system that satisfies only one of the following two properties: $FGp$, $AFEGp$
Find a transition system that satisfies only one of the following two properties: $FGp$, $EFEGp$
Find a transition system that satisfies only one of the following two properties: $GFp$, $AGEFp$

How should I begin when trying to reason about these types of problems? In general, is it easier to design transition systems for LTL properties or CTL properties? Or does it depend on the situation?

Any insight would be appreciated!

Technically, LTL and CTL are incomparable in their differentiating power over Kripke structures. So intuitively, it shouldn't be easier to design one or the other.

However, most people tend to find it easier to think in linear time. Making sure a certain property holds for all paths is easier than studying a branching-time property. In particular, this is because a counter-example for the satisfaction of an LTL formula is a path, whereas a counterexample for a CTL formula may be a tree.

To demonstrate how to approach the questions at hand, let's consider the first one. First, consider what the formulas mean:

$FGp$ means "in every path, after a finite prefix, $p$ always holds".

$AFEGp$ means "in every path, after a finite prefix, a state is reached from which there exists a path in which $p$ is always true."

Now, if $FGp$ holds, then $AFEGp$ must also hold, because in every path, eventually a state is reached from which $Gp$ holds. Thus, our search should restrict to finding a system which satisfies $AFEGp$, but not $FGp$.

To achieve this, we need to at least have a state that satisfies $Gp$, so let's start with that. Take the state $A$ to have the transition $A\to A$, and $A$ is labeled with $p$. Let's also have $A$ as the initial state (this is arbitrary). So far, this system also satisfies $FGp$, so now we fix that by adding a "bad path": we add a state $B$, labeled by $\neg p$ with the transitions $A\to B$ and $B\to A$.

The path $A,B,A,B,...$ does not satisfy $FGp$, so this is good. However, every path eventually reaches $A$, in which $EGp$ is true, so $AFEGp$ holds, and we are done.


Is Hidoku NP complete? A Hidoku is a $n \times n$ grid with some pre-filled integers from 1 to $n^2$. The goal is to find a path of successive integers (from 1 to $n^2$) in the grid. More concrete, each cell of the grid must contain a different integer from 1 to $n^2$ and each cell with value $z ≠ n^{2}$ must have a neighbor cell with value $z + 1$ (can also be diagonally).

Is it NP hard to decide whether a given Hidoku is solvable? What reduction could be used?

Edit: according to the comments, I give a little clarification. Given is a grid of cells, some of them already contain values (integers from 1 to n²). We must fill all remaining cells with integers from 1 to $n^2$, such that no two cells have the same value and that every cell with value $z ≠ n²$ has a neighbor with value $z + 1$. That is, after filling out the cells, we must find the path $1, 2, 3,\cdots, n^2$. In the grid, which logically visits each cell.

An example of a Hidoku woud be http://www.janko.at/Raetsel/Hidoku/018.c.gif.
An already solved Hidoku is http://diepresse.com/images/uploads/3/f/7/586743/spectrumsommerraetsel_7august_hidoku_schwer_loesung20100810172340.gif, where you can see the path I was refering to.

I think it is $\sf{NP}$-complete: as noticed by Raphael, Hamiltonian cycle on grid graphs with holes problem is NP-complete (Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter: Hamilton Paths in Grid Graphs. SIAM J. Comput. 11(4): 676-686 (1982)).

So given a grid graph $G$ with holes, you can easily build an equivalent Hidoku game where the initial fixed cells fill all the even diagonals; the empty odd diagonals form an undirected graph that is equivalent to the original grid graph $G$ and the Hidoku has a solution if and only if the original grid graph has an Hamiltonian path.

Figure 1: a grid graph with holes and the equivalent $12 \times 12$ Hidoku puzzle (blue cells represent the initial fixed numbered cells ($1$ is the first, $144$ is the last), white cells are the cells that the player must fill, purple line indicates the sequence of the initial fixed numbered cells).

Auxiliary (filled) lines can be added to the bottom or right side to make it a square.

Another example of reduction from a grid graph to an Hidoku puzzle: the 6x4 grid graph is embedded in a larger 13x13 grid; the even diagonals are filled with fixed numbers, and the remaining free cells are equivalent to the original grid graph.

The full picture with transformation can be downloaded here.

Some additional notes to complete the answer:

the problem is also known as Hidato; the board can have an arbitrary shape (but as a generalization of the square case, it remains NP-hard);
as correctly evidenced by Steven Stadnicki in his answer it is not obvious that the problem is in NP if the initial partially filled grid is not given as an $n \times n$ array of integers but is given in some succinct representation; however it is clearly in NP if the initial board is given using the reasonable list of integers representation;
I think that the original rules of the game  say that the solution should be unique; so the problem is in US (US-hard), and unlikely to be in NP.

In summary, if we drop the unique solution constraint and specify the initial board with a list of $n^2$ integers the game is $\sf{NP}$-complete.


Binary heap removal peculiar potential function analysis Given the potential function $\phi$, it seems that remove max may take $O(1)$ amoratized,
meaning that $n$ removals would take $O(n)$, which can't be, as it means we get a linear time comparison based sort if we build the heap in $O(n)$.

Where is the falling point in this potential function, and does it not give a $O(1)$ time guarantee and why?

\begin{align*}
    \overline C_i     =&  C_i + \phi_i-\phi_{i-1} \\
    \phi_i  =& \sum_{a\in Heap}{depth(a)} \\
\end{align*}

meaning the potential function is the sum of depths of all nodes in the tree.
\begin{align*}
    C_i           &= \log n \\
    \phi_{i}      &= \phi_{i-1} - \log n \\
    \overline C_i &= \log n + \phi_{i-1} - \log n - \phi_{i-1} = 0
\end{align*}

Amortized analysis relies on $\sum_{i=1}^n \overline{C_i} = \sum_{i=1}^n C_i+\phi_n-\phi_0$ being an upper bound for $\sum_{i=1}^n C_i$. This requires $\phi_n$ to be at least as large as $\phi_0$. Your potential function does not satisfy this requirement, aince $\phi$ will get smaller with each step.


Given a Red-Black Tree of n keys, is there a way to quickly determine if a red-node exists? My best attempt at a specific case of the problem where $n =$ 256:

For a specific case that a RB tree has 256 nodes, we can use the RB tree theorem to deduce that the height of the tree $h \leq 2*lg(n+1)$ then $h\leq 16$ for $n  =$ 256.

But this doesn't exactly help me deduce whether the last row is all black nodes (thereby implication the parent of these black nodes are red)

Can someone hep me carry this further?

Five rules for RB-Trees:

  Every node is black or red,
  Root is black,
  Every leaf is black,
  If a node is red then both its sons are black,
  All paths from a single node to any leaf must contain an equal amount of black nodes.

A common implementation has a NIL leaf set as a parent of root and son (left and right at the same time) of all leaves - in this case the NIL is black, and so it's parents can be black or red (as NIL is the only leaf.) This is the reason for a common misconception that leaves can be any color.

I am almost sure that any RB-Tree containing at least 2 elements (except NIL) will have at least one red node. This is due to an observation of the Insert algorithm. The inserted node is always coloured red at first, but any later modifiaction (if the colouring needs to be repaired) either does not change the colour of the newly added node (so it remains red) or makes at least one other node red.


Finding a fixed-size set whose members are contained by the largest number of other sets I've been thinking about a problem, inspired by meeting a beginner-level foreign language professor at the Goethe-Institut who learned the five most common languages spoken by students in order to communicate with as many students as possible.

Consider some finite population of people, each of whom speak any number of languages. For the purposes of the problem, we'll ignore some of the things that make languages complex in real life (for example, that people speak several languages but at different levels, that people who understand one language might be able to understand closely-related languages, and so forth).

So, for example:

P1 speaks {English, German}.
P2 speaks {Spanish, Italian, French}.
P3 speaks {Mandarin, English}.
P10000 speaks {Afrikaans, Swahili, English}, and so forth.

I am writing some document which I wish to have translated so as to be understood by as many people as possible. Unfortunately, my budget is limited, and I can only afford a translation into N different languages.

For a given value of N, how do I calculate the optimimum set of N languages to reach the largest number of people out of the intended population?

The problem sounds like it could be easily generalized as a set-theory/combinatorics problem, and so I'm certain somebody has done work on something like it before. I would like to take a look at the existing literature, but I don't know how to find it.

Is there a name for this type of problem? If not, could it be reduced to another known problem?

I believe your problem is a direct instance of the NP-hard Maximum Coverage Problem, which is related to Set Cover.

From wikipedia, Maximum Coverage Problem:

  As input you are given several sets and a number k. The sets may have some elements in common. You must select at most k  of these sets such that the maximum number of elements are covered, i.e. the union of the selected sets has maximal size.

So, in your case, there is a set for each language with cardinality equal to the number of students speaking that language. The input is the number N of maximum number of translations.


Compute several histograms with multiple filter conditions I have a numerical dataset of $N$ columns ($\approx 150$) and $K$ rows ($\approx 60000$).
On a user interface, you can apply a filter to one or more columns. We can call the number of filters = $Z$ (with $Z \le N$). Those filters are double sliders allowing to get a min/max for the column. For each filter, I would like to compute the histogram by applying all filters except this one.
The simplest method would be for each filter, to apply all other filters in the complete dataset and compute the histogram of this remaining column. That leads to a $O(Z^2)$ filtering on the dataset and poor performance with an important number of $Z$ and also $K$.
Is there a smarter way ? I have a "feeling" there is probably a way in $O(Z)$ but I am not able yet to clear it in my mind to write it :). It looks quite similar to the problem of the product of an array except self in term of thinking.
Maybe a more concrete example may help
On a e-commerce, you are selling RAMs and you have a filter by:

price
number of modules
frequency
memory size

If you filter the price between 100€-200€ and a frequency above 3000Mhz, you will mainly have a memory size of 16Gb.
The benefit of the histogram is to see on the "price" slider, in which direction you may have more result with the smallest change. For example going below 100€ will not provide a lot more result as there is nearly no ram below 90€. However, if you increase to 250€ you may have a lot more choice for this range of frequency. Similarly, if you reduce the frequency, you will end up with more choice (lower frequency is cheaper so maybe 32gb will be available at 200€.
To see that:

you need to compute the distribution of the price after applying the filter on frequency only
then compute the distribution of the frequency after applying the filter on price to have the number of product available below 3000Mhz.

The objective is to be able to render something like :

The histogram is available on the complete range of even if there is a filter on this given range (blue section). This is quite simple if there is only 1 filter as you compute only once the histogram but on my case, depending on other filters, this histogram varies.
I hope this example makes it clear.

I'm going to assume that each filter is a predicate on rows that identifies whether that row should be kept or discarded.  If so, then yes, this can be solved with many fewer than $O(Z^2)$ applications of the filters.  I'll describe two algorithms with different tradeoffs between time vs space: the first applies $O(Z)$ filters but uses $O(ZK)$ memory; the second applies $O(Z \lg Z)$ filters and uses just $O(K \lg Z)$ memory.  In both, let $F_1,\dots,F_Z$ denote the filters.
Algorithm 1: minimizing computation time
Here is an algorithm that applies $O(Z)$ applications filters and uses $O(ZK)$ memory.  (This corresponds to something like $O(ZK)$ time and $O(ZK)$ memory.)  Roughly speaking the algorithm computes a "prefix sum" and a "suffix sum", using two linear scans.  In more detail:

For each $i$, compute the subset $S_i$ of rows that are retained if you apply filters $F_1,\dots,F_i$.

For each $j$, compute the subset $S'_j$ of rows that are retained if you apply filters $F_j,\dots,F_Z$.

For each $i$, compute the intersection $S_{i-1} \cap S'_{i+1}$; this is the set of rows that are retained if you apply all the filters except for $F_i$.

Note that step 1 can be done in a linear scan using a total of $Z$ applications of filters, as you can obtain $S_{i+1}$ from $S_i$ using a single application of $F_{i+1}$.  Similarly step 2 can be done using $Z$ applications of filters, for a total of $2Z=O(Z)$ applications of filters.  Unfortunately you have to store all of $S_1,\dots,S_Z,S'_1,\dots,S'_Z$, which takes $O(ZK)$ memory.
Algorithm 2: minimizing memory usage
A divide-and-conquer algorithm can solve the problem with $O(Z \lg Z)$ applications of filters and $O(K \lg Z)$ memory.  (This corresponds to approximately $O(ZK \lg Z)$ time and $O(K \lg Z)$ memory.)  The algorithm works like this:

If $Z=1$ or $Z=2$, the problem is trivial; this is the base case.  Otherwise:

Compute the subset of rows that are retained if you apply filters $F_1,\dots,F_{Z/2}$.  Then, recursively apply the algorithm to this reduced set of rows and to the filters $F_{Z/2+1},\dots,F_Z$.

Compute the subset of rows that are retained if you apply filters $F_{Z/2+1},\dots,F_Z$.  Then, recursively apply the algorithm to this reduced set of rows and to the filters $F_1,\dots,F_{Z/2}$.

Notice that you can compute the subsets of rows in steps 2,3 with $O(Z)$ applications of filters.  So, if we let $T(Z)$ denote the number of filter applications used by this algorithm when running on $Z$ filters, we have the recurrence relation
$$T(Z) = 2 T(Z/2) + O(Z),$$
which has the solution $T(Z) = O(Z \lg Z)$.  The claimed running time follows; and it's not too hard to see that the amount of memory used is as claimed, too (as there are $O(\lg Z)$ levels to the recursion tree, and you store $O(K)$ records per level of the recursion tree at a time).
Can we do better?
A natural question is to ask whether it is possible to find an algorithm that is optimal in both time and memory usage: e.g., $O(Z)$ applications of filters and $O(ZK)$ memory.  I don't know whether that is possible or not.


Forcing an edge to be in S-T min-cut Given a flow-network $N=(G,c,s,t)$ and an edge $e=(u,v)$, I am trying to build an algorithm that finds a minimum $(S,T)$ cut in the given network, that includes e.

So, I tried couple of steps, first, I know I must saturate $e$ so it could be in any min-cut. I tried to add a supersource that connects to $u$ (with infinite capacity) and a supersink that connects to $v$. But that will only saturate $e$ if it is not yet been saturated, not force it to be in a min cut $s,t$.
I also thought maybe to reduce an epsilon from the capacity of $e$, but I am not sure if it is enough.

I also tried to connect the supersource to all of u neighbors and the supersink to all of v neighbors and then reduce an epsilon from e. Again I don’t know if that’s enough.

I’m not sure how to continue (or if i can) from here or if I’m missing something.

Remove $u$ and $v$ (as well as all edges connected to them), and for any removed edge $(u,x)$, add an edge from $s$ to $x$ with the same capacity; for any removed edge $(y,v)$, add an edge from $y$ to $t$ with the same capacity. Now find a min cut in this new graph. The partition of nodes in this cut suggests a min cut among those including $e$ in the original graph.


Clustering data for compression with PCA If I have datapoints in a high dimensional space and want to find a (linear) subspace onto which a data-set projects well, I can use PCA and then discard less important dimensions of the new basis to get compressed datapoints. However, often the data can be projected onto lower dimensional spaces with much smaller error if one first separates them into a couple of classes and then performs PCA for each class individually. What kind of algorithm can find such clusters? Just clustering based on distance in the high dimensional space won't be very useful:
Example:

If I'd just cluster first based on distance in the high-dimensional space, I would arrive at the bad clustering. There are 5 clusters and the green and red clusters don't project very well onto a 2D subspace.
As a human looking at the data, I see however that if I separate the data as indicated, red and blue will project very well onto a plane each and green will project very well onto a line, so I can run PCA for each group individually and store the red data points with 2 values each and the gree ones with 1 value each (plus a 2bit index on each datapoint to label which group it belongs to) and get a very low error upon uncompressing.
How can I automate this clustering based on how well it will project onto as low-imensional subspaces as possible?
Something like minimize E = SumOverClusters(SumOverPoints(SquaredDist(projected_point, original_point)) * (number_dims_projected / number_dims_original)) + C * number_of_clusters
What technique is well suited to do that?
(edit: while the example shows a 3d space, I'm more interested in doing that in about 64dimensional spaces)

(Not really an answer, more like a suggestion)
Since it's almost surely NP-hard, we need some heuristics. The idea is, for each point, to build the cluster it's contained in:
def clustering(P):  # P is the set of points
    for each p in P:
        build a somewhat-optimal cluster C containing p
        remove C from P

Now, for each point we will build a cluster, one dimension at a time. We will build vectors $(v_1, \ldots, v_k)$, until the objective doesn't improve:
def build_cluster(p, P, t):  # t is a projection distance threshold
    S = ()  # current span
    for k = 1, 2, ...:  # cluster dimension
        sample m vectors v_1, ..., v_m
        for each v_i:
            compute the number of points in P within a distance t to p + span(S, v_i)
        select the best such v_i
        if adding v_i to S is not beneficial:
            break
        S = union(S, v_i)

Now, there is a lot of engineering which can be done, except for defining stop conditions. E.g. we can sample vectors, and then iteratively improve them (minimizing the loss, I.e. the distance to the span from vertices within distance t) (and we can also decrease t in the process of improvement).
Also, maybe we should do something better than sampling random vectors since we are unlikely to hit the right one. We may try to compute some candidates based on our data.
Hope it helps.


Is a subgraph either a spanning subgraph or a full subgraph? A graph $G' = (N' ,A')$ is a spanning subgraph of a graph $G = (N, A)$
iff $N ' = N$ and $A' \subseteq A$.
A graph $G' = (N',A')$ is a full subgraph of a
graph $G = (N, A)$ iff $N' \subseteq N$ and $A' = \{(x,y) \in A \mid x,y \in N '\}$.

I have to prove that "If $G'$ is a subgraph of a graph $G$, then either
G' is a spanning subgraph of $G$, or $G'$ is a full subgraph of $G$. If this statement
is valid, provide a proof that it is valid, otherwise provide a counterexample" but isn't a full subgraph actually a spanning subgraph?

I mean that any subgraph of $G$ is a full subgraph in the end, right?
Any ideas how I can prove the statement?

My second question is how to calculate the number of spanning subgraphs of $G$ as a function of the number of nodes in $N$. How can I do this without knowing $A$ or how many edges I have in the graph?

On your question "isn't a full subgraph actually a spanning subgraph?". The answer is no, a full subgraph doesn't need to be a spanning subgraph. By your definition, a full subgraph can have lesser number of vertices than in the original graph. However, a spanning subgraph must have exactly the same set of vertices in the original graph.

On your second question "how to calculate the number of spanning subgraphs of $G$ as a function of number of nodes in $N$." Since it is a fact that graph $G = (N,A)$ with differing $A$ will have differing number of possible spanning subgraphs, I suspect you might have misunderstood the question. For example, does the question actually only ask for an upper bound of the number of possible spanning subgraphs as function of $|N|$?


What is language density used for? If we have a langage $L$ over an alphabet $\Sigma$, then we can defined the density function of $L$ as :

  $$ p_L(n) = | L \cap \Sigma^n | $$

I am wondering why it’s useful to study this function and what informations it gives on $L$.

Moreover, we can then defined the entropy of $L$ as :

$$E_L(n) = \frac{1}{n} \log p_L(n) $$

Once again I am wondering what information does this function reveal about $L$. Moreover, is there any way to think intuitively what the entropy of a language really represents?

Thanks you !

The number of words of given length in a language is a very natural parameter. Here are some examples to pique your interest:

The density of $(1+01)^*$ is the Fibonacci sequence.
The density of a regular unary language is eventually periodic.
The density of a regular language is of the form $\Theta(n^k \lambda^n)$ for some integer $k \geq 0$ and real $\lambda \geq 0$.

The parameter $E_L(n)$ measures the entropy per character of a random word of length $n$ in $L$, chosen uniformly at random. For example, if $L$ consists of all binary words containing $\lfloor pn \rfloor$ ones (where $n$ is the length of the words), then $E_L(n)$ converges to $h(p)$, the binary entropy function.


Number of words in $L$ of length $n$? Be $L$ a formal language over the alphabet $\Sigma$. $L$ can be defined by induction:
$L^0 = \{\epsilon\}$ and for $i>0: L^i = \Sigma*L^{i-1}$.
Means that $|L^n|$ is the number of words in $L$ of length $n \in \mathbb{N}$ letters from $\Sigma$.
Find $|L^n|$.

For $\Sigma = \{a,b\}$, $|L^n| = 2^n$ scince $|\Sigma| = 2$ and $|K*\Sigma| = |K|*2$ (with $K$ being an arbitrary set). Right?
But what happens if $\Sigma = \{a,b,aa,ab,ba,bb\}$ ?
For some $n$ some elements can be created in multiple ways (e.g. $a$ and $ba$ result in $aba$ and $ab$ and $a$ result in $aba$). Therefore $|L^n| \neq 6^n$.
The problem clearly is, that some letters of $\Sigma$ (e.g. $aa$) consist of other letters of $\Sigma$ (e.g. $a$).
So far i looked at some results (no guaranty for correctness):

$|L^1| = 6$
$|L^2| = 28$
$|L^3| = 120$
$|L^4| = 496$
$|L^5| = 2016$
$|L^6| = 8128$

And found a formula for these values: $|L^n| = 2^n*(2^{n+1}-1)$
However, i can't explain or prove it. What is the correct way to approach this? Which words can be created in multiple ways?

Means that $|L^n|$ is the number of words in $L$ of length $n\in \mathbb{N}$ letters from $\Sigma$.

Actually, $L^n$ consists of the words that are composed of $n$ copies of words from $L$. The precise lengths of these words differ.

This exercise starts however with a very specific set $L$, it consists of all words of length 1 or 2. That means that $L^2$ consists of all words of length 2,3 or 4. (No need to verify in how many ways that can be done.) And this are 4+8+16 = 28 strings, exactly like you claimed.

This can be generalized for $L^n$.


Proving $A^\ast = A$ on a given set I am working on some set theory and am trying to prove how a set can have the property $A^* = A$.

For set $A=\{0^n1^n \mid n \ge0\}$, I still do not understand exactly what $A^*$ is. For example, I thought $A^*$ is the enumeration of the set $A$ so

$A^* = \{\epsilon,01,0011,000111,00001111,....\}$

Any helping in at least understanding what $A^*$ is for this problem would be much appreciated!

What you have written (i.e., $\{ \varepsilon, 01, 0011, 000111, \ldots \}$) is simply $A$ itself.

(Assuming $A^\ast$ is the Kleene star operation) you cannot prove $A = A^\ast$ because it is not correct.

The Kleene star $A^\ast$ is defined as the union of the powers $A^i$, where $A^0 = \{ \varepsilon \}$ and $A^{i+1} = A^i \cdot A = \{ w \cdot w' \mid w \in A^i, w' \in A \}$. An inductive argument easily shows:
$$A^i = \{ w_1 \cdots w_i \mid w_1, \ldots, w_i \in A \}
= \{ 0^{n_1} 1^{n_1} \cdots 0^{n_i} 1^{n_i} \mid n_1, \ldots, n_i \ge 0 \}$$

Since $A^\ast$ is the union over all such $A^i$, we obtain
$$A^\ast
= \{ 0^{n_1} 1^{n_1} \cdots 0^{n_i} 1^{n_i} \mid i, n_1, \ldots, n_i \ge 0 \},$$
which is obviously not equal to $A$.


Finding a small element in a changing array Consider having an integer array $A$ with $n$ elements, in addition to any data structure you like.

The array is initialized to zeros.

The goal to to support two operations:

Update(k,v) - sets $A[k]=v$.
Small() - returns an index in which the element is smaller than or equal to the median.

Assuming that finding a small item has to be done in $O(1)$ time, how fast can we perform updates?

Some notes:

You can use preprocessing to initialize any data structure you wish before the sequence of updates starts.
I'm only looking for deterministic algorithms. A randomized algorithm for this problem is trivial.
Making update run in $O(\log n)$ is straightforward (e.g. using a balanced BST).

Can we improve to $o(\log n)$ or show an $\Omega(\log n)$ lower bound?

Here is an amortized solution to the problem in which updates may only increase values:

Maintain:

A linked list of some of the items less than the median
A linked list of all items greater than the median (and some items less than it)

To return a small item, return an item from #1.

To update an item greater than the median, change its key in #2.

To update an item less than the median, remove it from #1 and add it to #2. If this makes #1 empty, rebuild both lists using a linear-time partitioning algorithm.

Update takes amortized constant time, using physicists argument and a potential function of twice the size of list #2 or the bankers argument and two coins on each item in list #2.

Here is an amortized solution in which updates may increase or decrease values:

To start, build three linked lists of size $n/3$. All items in list #1 should be less than all items in list #2, and all items in list #2 should be less than all items in list #3. One more list will be maintained; I'll call it the junkyard.

To change the key of an item:

When increasing the key of an item in #1, move it to the junkyard.
When decreasing the key of an item in #3, move it to the junkyard.
When changing the key of an item from #2, move it to the junkyard.
When changing any other key, do not remove it from or add it to any list.

The junkyard is called "full" when it has size $n/6$. Until then, all items in #1 are less than the median. Once the junkyard is full, rebuild.

The amortization argument works the same, but now the potential is six times the size of the junkyard, or, equivalently, each move to the junkyard requires 6 coins.

Here is a complete deamortized solution:

All operations can be done in constant time using a technique called incremental global rebuilding.

Maintain three copies of the second version of the structure designed above, along with three pointers to them, called PAST, PRESENT, and FUTURE. If a structure is pointed to by A and we want to point to it from B, we call that "renaming A to B".

We will proceed in four stages. After stage 4, we will rename PRESENT to PAST, rename FUTURE to PRESENT, and point the FUTURE pointer at empty space (or the null pointer). Then we will start with stage 1 all over again.

Each stage lasts $n/36$ updates. Queries are always answered from PRESENT

Stage 1:

When this stage starts:

We will never query the structure pointed to by PAST again. It is dead, so we don't really care about its contents.
PRESENT's junkyard has at most $2n/36$ items in it.
FUTURE is just a null pointer.

During this stage, updates are performed on PRESENT as usual, but for each update, we perform 36 steps of destructing PAST. As a result, by the end of this stage, $n$ destructing steps have been performed on PAST and it is empty, using no memory.

At the end of this stage, PRESENT's junkyard might be as large as $3n/36$.

Stage 2:

When this stage starts, we allocate an empty linked list that we call FUTURE.

During this stage, for each update to PRESENT we also copy 36 items into FUTURE. Also, for each item that is updated, we update its key in FUTURE if it already has been copied. Note that the update in FUTURE doesn't touch any junkyards, since FUTURE is just a linked list at this point.

At the end of this stage, PRESENT's junkyard might be as large as $4n/36$, and the items in PRESENT and FUTURE are identical.

Stage 3:

When this stage starts, we allocate an empty queue that can hold representations of update operations (for instance, as a pair containing a pointer to the item and its new value).

During this stage, for each update to PRESENT we also enqueue a representation of that update into the update queue, and we perform 36 steps of the initialization of FUTURE into the structure described in section 2 above. As a result, by the end of this stage, $n$ initialization steps have been performed on FUTURE and it is completely initialized, with a junkyard size of 0. However, because updates were queued, it does not hold the same data as PRESENT, which we will have to fix in Stage 4.

At the end of this stage, PRESENT's junkyard might be as large as $5n/36$ and the queue has size $n/36$.

Stage 4:

During this stage, for each update to PRESENT we also enqueue a representation of that update into the update queue and dequeue two operations to play back in FUTURE. During this stage the queue grows by $n/36$ operations and shrinks by $2n/36$, leaving it empty at the end of the stage.

At the end of this stage, PRESENT's junkyard might be as large as $6n/36$ and FUTURE's junkyard might be as large as $2n/36$. We now switch names as described above, renaming PRESENT to PAST, FUTURE to PRESENT, and pointing FUTURE at the null pointer. The prerequisites for Stage 1 are now met, and at no point did PRESENT have more than $n/6$ items in its junkyard.


Intuition for irregular languages I'm struggling in understanding how to recognize irregular languages.
I know what the meaning of irregular language but still find it hard to recognize.
Are there any tips to recognize better and to know which is regular and which not?
For example, which of the following is not regular, and what gives you the intuition?
\begin{align}
L_1 &= \{a^ib^i \mid i \ge 0 \} \\
L_2 &= \{a^ib^j \mid i,j \ge 0\} \\
L_3 &= \{a^nb^nc^md^m \mid n,m \ge 1 \}
\end{align}

The language $L_1$ is the quintessential example of a non-regular language. Intuitively, finite automata cannot count, so they cannot ascertain that the number of $a$'s is the same as the number of $b$'s. Alternatively, an automaton must "remember" how many $a$'s it has seen, which is impossible since there are infinitely many possible number of $a$'s. This intuition can be formalized using Myhill–Nerode theory: if $q_n$ is the state that a DFA for $L_1$ is at after reading $a^n$, then $q_n \neq q_m$ for $n \neq m$, since $a^nb^n \in L_1$ while $a^mb^n \notin L_1$; so there must be infinitely many states.
The language $L_2$ corresponds to the regular expression $a^*b^*$, so is regular.
The language $L_3$ is a "generalization" of $L_1$ (this can be made precise: $L_1$ is a quotient of $L_3$, $L_1 = L_3/\{cd\}$). Once again, an automaton needs to count how many $a$'s there are, which is impossible.


question about the construction of BSTs using a repeated sequence of rotations How can I show that any binary search tree can be balanced with at most O(n log n) rotations (“balanced” here means that the lengths of any two paths from root to leaf differ by at most 1).

Actually any BST can be transformed into balanced BST using $\mathcal{O}(n)$ rotations.

High level explanation: We convert given BST to right going chain(see fig-1 below). Then we convert that chain to balanced BST.

First convert given BST into right-going chain. Which can be accomplished using $n-1$ right rotations as follow.

Consider initial-right-chain $C$ of $root$ and all node that can be reachable from $root$ by following only right pointers.

Now, note that for any node $N$ in $C$ left child of node $N$ can be added into $C$ by right-rotating $N$. In doing that we don't loss any node from $C$.

So, by at most $n-1$ right rotation all node will be in $C$ because root will always be in $C$ from start.

Now, consider sequence of rotations $R: r_1, r_2, ..., r_m$ required to convert tree $T_1$ to right-going chain.

Now, consider sequence of rotations $S: s_1, s_2, ..., s_k$ required to convert balanced BST (containing same number of node as $T_1$) to right_going chain.

Then apply $r_1, r_2, ..., r_m, s_k', s_{k-1}', ..., s_1'$ to $T_1$. Here $s_i'$ denotes inverse operation of $s_i$.

Which will transform $T_1$ to balanced BST using at most $2n-2$ rotations.

   1
    \
     2
      \
       3

 figure - 1

Ref: CLRS 3e exercise 13.2.4


Is there an efficient algorithm to extract the farthest ends of a thin contour? Let's say you have pixel bitmaps that look something like this:

From this I can easily extract a contour, which will be a concave polygon defined by a set of 2D points. The question is what is the fastest algorithm to pick, from the set of polygon points, the ones that are closest to the natural "endings" of the contour (i.e. the two tips at the end of the U in this case) - so there are $2$ points in the output.
Somehow it looks like it should be related to curvature, although the algorithm should support a large variety of possible shapes, including S, W and other largely curved shapes so I'm hesitant to set any kind of threshold on curvature.
I've tried convex hull methods as well as a couple of variations of the rotating calipers method but still I've found nothing that will convince me that I can reliably and quickly identify the endings/tips of any curved thin line. It's always impressive how humans can pick up on these natural features so fast!

Run Flood Fill from any point and the farthest points in the both directions are your result. If you find that the distance in one of the directions is zero it means that it was one of them.

Exploiting the very same idea, if you try finding pixels with the least number of surrounding pixels and apply limited BFS Flood Fill to find out where it can go - at the endpoints there is only one way out. Also going by curvature and then applying the same idea would tell apart the extra bends from results.


Difference between DNS Spoofing and DNS Hijacking? DNS Spoofing and DNS Hijacking, both of them basically are type of attacks where the request is redirected to some other malicious website or some other web page. But I did not find some concrete difference between them, Can someone please explain the primary difference between DNS Spoofing and DNS Hijacking..

One way of explaining the primary difference between DNS Spoofing and DNS Hijacking is given by this site as:

While DNS spoofing is often confused with DNS hijacking as both happen at the local system level, they are two different types of DNS attacks.
Most of the time, DNS spoofing or cache poisoning just involves overwriting your local DNS cache values with fake ones so you can be redirected to a malicious website.
On the other hand, DNS hijacking (also known as DNS redirection) often involves malware infections in order to hijack this important system service. In this case, the malware hosted on the local computer can alter the TCP/IP configurations so they can point to a malicious DNS server, one that will eventually redirect the traffic to a phishing website.

So, DNS spoofing is where some malware or something else changes values in your local DNS cache (on your PC, for example), with fake values so you would query and go to the wrong destination.
DNS hijacking, on the other hand, is not so much about attacking your local DNS cache, but something else like the TCP/IP configurations so your PC's pointer to DNS is diverted to a malicious DNS server that could redirect traffic to a malicious website.


No of ways in which n indistinguishable items can be placed in m indistinguishable boxes This problem is the same as
number of ways to partition n into exactly m parts.

The recurrence given in Wikipedia has

p(n,k) =  the number of partitions of n using only natural numbers ≥ k

How to find no of partitions of n which has exactly k non-zero parts? Is there a recurrence relation to solve this?

The number of partitions of $n$ with exactly $k$ parts is the coefficient of $x^n y^k$ in the generating series
$$ \prod_{l=1}^\infty \frac{1}{1-x^ly}. $$
Asymptotically, this is probably $\Theta_k(n^{k-1})$ (i.e. the constant depends on $k$).

The number of partitions of $n$ in which each part is at least $k$ is
$$ \prod_{l=k}^\infty \frac{1}{1-x^l}. $$
Asymptotically, my guess is that it's $\Theta_k(p(n))$, where $p(n)$ is the number of all partitions of $n$.

We can write a recurrence relation for $p(n,k)$: $p(0,k) = 1$ and for $n > 0$,
$$ p(n,k) = \sum_{t \leq \lfloor n/k \rfloor} p(n-kt,k+1). $$


Is the Choice operator implementable on $\pi$-calculus? I was reading about $\pi$-calculus, and some authors include in the basic operations a Choice operator $P \oplus Q$ which means that either $P$ or $Q$ will be executed, but not both.

On page 8 of "Applied $\pi$ - an introduction" (available on http://www.cl.cam.ac.uk/~pes20/apppi.ps ), the author says that the coice operator is not necessary because it can be implemented as:

$$
P \oplus Q  \triangleq \textbf{new} \  x \  \textbf{in} \  ( \bar{x}z.0 | xz.P | xz.Q )
$$

But it did not convince me. For example, taking $P=ab.0$ and $Q=cd.0$:

$$
\bar{a}y.0 | (ab.0 \oplus cd.0) \rightarrow 0 | 0 \rightarrow 0
$$

but

$$
\bar{a}y.0 |(\textbf{new} \  x \  \textbf{in} \  ( \bar{x}z.0 | xz.ab.0 | xz.cd.0 )) \rightarrow
$$
may reduce to
$$
\bar{a}y.0 |0|ab.0|(\textbf{new} \  x \  \textbf{in} \  xz.cd.0 ) \rightarrow 0 | (\textbf{new} \  x \  \textbf{in} \  xz.cd.0 )
$$
but it may also reduce to
$$
\bar{a}y.0 |0|cd.0|(\textbf{new} \  x \  \textbf{in} \  xz.ab.0 )
$$

which will deadlock without ever sending $y$ through $a$. My question is: where are the mistakes? Is my reasoning wrong? Is this implementation of the choice operator wrong? Is the $\pi$-calculus required to backtrack and find the path with the most reductions?

I'm really sorry if my question makes no sense, I have very little formal training on this subject it is mostly curiosity so that I can implement a $\pi$-calculus simulator.

The issue is that you are manipulating $\oplus$ but you don't have any rules (besides its definition) telling you what reductions you can do. The whole point of the paragraph that presents this definition is that there are multiple notions of choice and some but not all are encodable.

  Many process calculi have explicit choice or summation operators for
  nondeterminism, allowing for example $P+Q$ which can behave either as
  $P$ or as $Q$ (this is imprecise – in fact several different operators
  are possible).  [...] In some cases a form of choice is encodable
  in a choice-free calculus – for example a purely internal choice can
  be encoded in the π-calculus given in Section 1.1 above by [expression from question] but
  in  other  cases  non-encodability  results  can  be  proved [...].


How can I generate first n elements of the sequence 3^i * 5^j * 7^k? How can I efficiently generate the first N elements of the sequence $3^i 5^j 7^k$, where $i,j,k \in \mathbb{N}$?

I've googled around a bit and found the sequence in OEIS, but I don't really see a simple way of generating it.

Here I assume $0\in \mathbb N$. If you disagree start with $105$.

Let $S$ be the sequence of numbers of the form $3^i5^j7^k$. Our task is to generate these numbers in order.
Apart from $1$ each number added is of the form $3\cdot x$, $5\cdot y$ or $7\cdot z$ where $x,y,z$ are previous numbers in the sequence. We can generate $S$ by shifting $x,y,z$ along the sequence.

So, first put $1$ into $S$, and set $x,y,z$ equal to $1$.

Now repeat: Take the minimum value $m$ of $3\cdot x$, $5\cdot y$ and $7\cdot z$, and add $m$ to the sequence $S$. The $x,y,z$ for which the minimum was taken are shifted to the next element of $S$. This might be more than one, or even all three.

$\newcommand{\ul}[1]{\underline{#1}}$
$\begin{array}{r|rr|rr|rr} S & x & {}*3 & y & {}*5 & z & {}*7 & \\\hline
1 & 1 & \ul{3} & 1 & 5 & 1 & 7 \\
3 & 3 & 9 &   & \ul{5} &   & 7 \\
5 &   & 9 & 3 & 15 &   & \ul{7} \\
7 &   & \ul{9} &   & 15 & 3 & 21 \\
9 & 5 & \ul{15} &   & \ul{15} &  & 21 \\
15 & 7 & \ul{21} & 5 & 25 &   & \ul{21} \\
21 & 9 & 27 &   & \ul{25} & 5 & 35 \\
25 &   & \ul{27} & 7 & 35 &   & 35 \\
27 & 15 & 45 &   & \ul{35} &   & \ul{35} \\
35 &    & \ul{45} & 9 & \ul{45} & 7 & 49 \\
45 & 21 & 63 & 15 & 75 &   & 49
\end{array}$

Works in linear time, as we need to take the minimum of three numbers in each step.


What does 'computable in the limit from above' mean? $H(x)$ is the program size complexity of $x$ for some universal Turing machine $U$. $H$ is not computable, however $H$ is "computable in the limit from above".

From my notes:

  i.e the set $\{(x,n) \mid x \in B^*,n \geq 0, H(x) \leq n\}$ is computably enumerable.

Can someone tell me what this means? I understand the incomputability of $H$ but the term "limit from above" is confusing me.

To quote Wikipedia/Scholarpedia,

  A partial function $f$ from the rational numbers to the real numbers is
  upper semicomputable if it is defined by a rational-valued partial
  computable function $\phi(x,k)$ with $x$ a rational number and $k$ a
  nonnegative integer such that $\phi(x,k+1)≤ϕ(x,k)$ for every $k$ and
  $\lim_{k \to \infty}\phi(x,k)=f(x)$. This means that $f$ can be computably approximated
  from above.

Further, using the squeeze theorem, we could conclude:

  If a function $f$ is both upper semicomputable and lower semicomputable
  on its domain, then we call $f$ computable


What complexity class does this variation of traveling salesman problem belong to? Given a TSP instance $T$, decide whether changing the city coordinates by adding a vector of coordinates $v$ will change the optimal TSP objective by atleast $x$. The city coordinates are integers.

The problem is in PSPACE but even the verification problem seems to be NP-hard. Is that true?

If the verification problem is NP-hard, what exact complexity class does this problem belong to?

I'm assuming that you're thinking of the Euclidean traveling salesman problem, where $c$ and $v$ are vectors in $\mathbb{Z}^{2n}$, with two coordinates for each city.  Let $minTSP(c)$ denote the length of the minimum traveling salesman tour for the cities with coordinates $c$.  Then your problem asks whether
$$
minTSP(c + v) \ge min TSP(c) + x.
$$
But then the special case $c=0$ is equivalent to asking whether $minTSP(v) \ge x$, which is coNP-hard.


Efficient way to implement periodic events I need to implement a system that can schedule and dispatch periodic jobs and needs to support a very high load (millions of jobs per second). Each job in the system has a period that is some multiple of 15 seconds, with the maximum allowed period being 1 day.

The system needs to support adding new jobs and removing / replacing existing jobs. However, these occur relatively infrequently (aside from when the system starts up and has to add the initial batch of jobs), so it is okay to make trade-offs with regards to insertion / deletion time.

Jobs scheduling times should be spread out so as to avoid "spikes" in number jobs dispatched. For example, if we had a million jobs that all had a period of 15 seconds, we wouldn't want to dispatch all of them at the exact same time every 15 seconds, and then wait another 15 seconds not doing anything before doing it again. It would be better to spread them out so around 60-70k jobs are dispatched every second, as long as each job is still scheduled to run 15 seconds apart.

Currently, around 10% (maybe less) of the jobs in the system have a period of 15 seconds (the minimum possible), while the remaining jobs have periods between 30 seconds and 1 day.

Our current implementation uses something like a hashed timer wheel, which has 15,000 buckets representing the number of milliseconds in every 15 second interval. Jobs are added to a random bucket in the wheel, and on every tick of the wheel, we iterate through every job in the bucket, dispatching the ones that are "expired" and incrementing a counter for the remaining jobs. For example, a job with a 60 second period would only be dispatched once every 4 turns of the wheel, even though it is iterated over on every turn of the wheel. The problem here is that on each tick of the wheel, the majority of the jobs in the next bucket are not actually ready to be dispatched, but we have to iterate over them anyways to increment their counter.

Is there a better algorithm / data structure I can use to make this more efficient? I am considering implementing hierarchical timing wheels, so that the only times we need to iterate over a job are when it is re-inserted into a lower wheel, or when it is ready to be dispatched. My concern with this approach though, is that unlike the current hashed timer wheel approach, we need to remove and re-insert the job every time its period expires.

A standard approach for scheduling is a priority queue of future jobs: each job has a time at which it should be dispatched, and that time is the key for the priority queue.

When a new job arrives, pick a random time within its period, and schedule it to occur at that period.  For instance, if a job arrives with a period of 75 seconds, pick a random number $t$ in the range [0,75), then schedule it to be first dispatched $t$ seconds from now.  To schedule it, add it to the priority queue with its dispatch time as the key.

Each second, retrieve all jobs scheduled to be dispatched in this second, delete them from the priority queue, and dispatch them.  Also schedule each to occur at a time in the future based on its period (thus inserting it back into the priority queue with a later dispatch time).

The randomization should ensure a reasonable balance of jobs, especially when you have a large number of jobs to schedule, and the priority queue should make it efficient to insert, delete, and dispatch jobs.  In particular, all of those operations can be done in $O(\log n)$ time, where $n$ is the number of jobs.

You could check whether that will meet your requirements.  If not, that should help clarify your specific requirements.


Communication complexity: fooling set bound for inner product function I am trying to prove that the fooling set method does not give a good lower bound for the communication complexity of the inner product function. Specifically, I am trying to show that the best bound we get using the fooling set method is $$D(IP) \geq \Omega(\log n) $$

$D(IP)$ is the deterministic communication complexity of the inner product function. This implies that any fooling set for the inner product cannot have more than $n^2$ elements. How do I show this? I can verify the statement for specific instances, but I have no intuition for the proof.

Let $(x_i,y_i)$ be a fooling set for inner product, of size $m$. Construct an $m \times n$ matrix $X$ whose rows are $x_i$ and an $n \times m$ matrix $Y$ whose columns are $y_i$, and consider the matrix $M = XY$ (arithmetic is over the field $\mathbb{F}_2$). The decomposition $M=XY$ shows that $M$ has rank at most $n$.

Suppose first that $\mathrm{IP}(x_i,y_i) = 1$ for all $i$, and so for each $i \neq j$, either $\mathrm{IP}(x_i,y_j) = 0$ or $\mathrm{IP}(x_j,y_i) = 0$.
Consider the Hadamard (entrywise) product of $M$ and $M^T$. It is known that rank is submultiplicative with respect to entrywise product, and so the rank of $M \circ M^T$ is at most $n^2$. On the other hand, $M \circ M^T$ is the identity matrix, and so has rank $m$. We conclude that $m \leq n^2$.

When $\mathrm{IP}(x_i,y_i) = 0$ for all $i$, we consider the matrix $M' = M+J$, where $J$ is the all ones matrix. Since $J$ has rank 1, the rank of $M'$ is at most $n+1$, and so the argument in the preceding paragraph shows that $m \leq (n+1)^2$.


Where can I find an original reference for this integer square root algorithm As an exercise, I converted an old method I learned for calculating square roots on a rotary decimal hand calculator to binary.

I'm sure this is not original; can anyone provide a reference?

// All arithmetic is truncating unsigned integer arithmetic
// Actual implementation uses bit shifts
// Indention level defines statement scope

def sqrt(r)                         // r is an unsigned integer
    residue = r                     // residue will be the 'remainder'
    root = 0                        // root will be the integer square root (floor(r**0.5))
    onebit = 2**(bitlength(r)-2)    // onebit is a moving 'bitpicker'
    while onebit > r
        onebit = onebit / 4         // find highest bitpicker less than r
    while onebit > 0
        x = root + onebit           // Current root plus onebit
        if residue >= x             // Room to subtract?
            residue = residue - x   // Yes - deduct from residue
            root = x + onebit       // and step root
        root = root / 2             // Slide evolving root 1 bit down the residue
        onebit = onebit / 4         // Slide the bitpick 1 bit down the root
    assert(root**2 + residue == r)
    assert((root+1)**2 > r)
    return root, residue

The wikipedia article on Methods of computing square roots: base 2 presents a strikingly similar snippet of C-code [a], but the link to the source is dead. Let's try to do better.

The snippets from both wikipedia and the question are very similar to Martin Guy's widely circulated C implementation [b]. which contains a comment: From a book on programming abaci by Mr C. Woo. Search engine use suggests this is [1] - one edition seems to be from 1930; it has been reprinted, e.g. [2].

The age of the method is bound to be on the order of two millenniums - the original reference might be difficult to obtain.

A purportedly[z] very similar Algorithm has been presented by TIJ Rolfe, who in turn refers to [3].

Woo, C.C. The Fundamental Operations in Bead Arithmetic. How to Use the Chinese Abacus, China Lace Co., Ltd., Hong Kong
Kwa Tak Ming, C. C. Woo, The Fundamental Operations in Bead Arithmetic. How to Use the Chinese Abacus, Literary Licensing, LLC, United States, 2012, 9781258466855
Hart, W.L. "College Algebra" 4th ed., Boston, 1955, p.424


What is the meaning of the mutation rate in genetic algorithms? Let us suppose that we have a mutation rate of 5%. What does this mean?

Each gene of each individual has 5% of probability of change to another value? At the end, around 5% of the genes of each individual in the population will be changed.
Each individual in the population has 5% of probability of having a random gene changed to antoher value? At the end, 5% of the population will have a change in some of its genes.

Besides that...Should I apply the mutation operator over all individuals or only to the children generated by the crossover operator?

In general each child is mutated separately, only once at 'birth', and not during their 'adulthood'. Depending on how individuals are specified, '5% mutation' might mean that a random 5% of the bits in the individual's source code are flipped.


A totally-ordered set of functions When we analyze algorithms using the $O$ notation, we usually use only a small set of the space of all functions. E.g., we use $\Theta(n)$ but not $\Theta(2n)$, as these two are equally well represented by $\Theta(n)$. This makes me ask whether it is possible to define a set of "representative functions" which are totally ordered by the $o$-notation?

Concretely, let $F$ be the space of all positive, monotonically increasing real functions on $N$ (the natural numbers). I am looking for a subset $G\subseteq F$ with the following properties:

For every two functions $g_1,g_2 \in G$, either $g_1(n) = o(g_2(n))$ or $g_2(n) = o(g_1(n))$.
For every function $f\in F$, there is a function $g\in G$ with $g(n)=\Theta(f(n))$

Does there exist such a set? If so, how can it be represented (e.g. how many real parameters are required?)

This question is very natural since most if not all common functions that appear in the runtime-analysis of algorithms form a totally ordered set in terms of little $o$-notation or big $\Omega$-notation such as shown in this answer by Robert S. Barnes or this answer by Kelalaka.

However, there is no such totally-ordered set of representative functions for all positive increasing functions.

The basic reason is the first property, when applied to $F$, does not define a total-order.

Define two strictly increasing $f_1(n)$ and $f_2(n)$ from $\Bbb N$ to $\Bbb N$.

$$f_1(n)=2^{(2\lceil\frac {n+1}2\rceil)^2+n}$$
$$f_2(n)=2^{(2\lfloor\frac {n}2\rfloor+1)^2+n}$$

Then
$$\sup\lim _{n\to\infty}\frac {f_1(n)}{f_2(n)}
\ge \lim_{n=2i+1\to\infty}\frac {f_1(n)}{f_2(n)}
=\lim_{i\to\infty}\frac {2^{(2(i+1))^2+2i+1}}{2^{(2i+1)^2+2i+1}}
=\lim_{i\to\infty}2^{4i+3}=\infty$$

$$\sup\lim _{n\to\infty}\frac {f_2(n)}{f_1(n)}
\ge \lim_{n=2i\to\infty}\frac {f_2(n)}{f_1(n)}
=\lim_{i\to\infty}\frac {2^{(2i+1)^2+2i}}{2^{(2i)^2+2i}}
=\lim_{i\to\infty}2^{4i+1}
=\infty$$

In plain words, neither of $f_1(n)$ and $f_2(n)$ grows asymptotically the same or faster than the other one ignoring a constant factor.

Let $F$ and $G$ be defined as in the question. Suppose $G$ exists. Then there is $g_1, g_2\in G$ such that $g_1(n)=\Theta(f_1(n))$ and $g_2(n)=\Theta(f_2(n))$. Then $g_1(n)>c_1(f_1(n))$ for some constant $c_1>0$ and $g_2(n)<d_2(f_2(n))$ for some constant $d_2$. (In usual cases, we have to say "for $n$ large enough". However, that clause can be omitted since all values here are positive. Anyway, we can add that clause as well.)

$$\sup\lim _{n\to\infty}\frac {g_1(n)}{g_2(n)}
\ge \sup\lim_{n\to\infty}\frac {c_1f_1(n)}{d_2f_2(n)}
\ge \frac{c_1}{d_2}\sup\lim_{n\to\infty}\frac {f_1(n)}{f_2(n)}
=\infty
$$

Symmetrically, $\sup\lim_{n\to\infty}\dfrac {g_2(n)}{g_1(n)}=\infty$. We see that $g_1\not=g_2$ but neither $g_1(n) = o(g_2(n))$ nor $g_2(n) = o(g_1(n))$. This contradition shows $G$ does not exist.

How about if we drop the first requirement so that the functions in $G$ are not required to dominate each other?

Then this question becomes closely related to the question Big O notation and the maximal set of comparable functions as found by OP, where a couple of enlightening answers explain the situation pretty well, indicating there is hardly any hope for a nice positive answer. Even countably-infinitely real parameters cannot parametrize continuously a set of representative functions in the equivalence classes of increasing functions where two functions are in the same equivalence class if they are related by $\Theta$ and each function only uses finitely-many parameters.

Explicit rigorous answers to the following exercises might be long. However, the ideas should be simple for experienced users.

(Exercise 1.) For any given positive integer $n$, construct $n$ increasing functions from $\Bbb N$ to $\Bbb N$ such that for any two of them, $f_1$ and $f_2$, neither $f_1=O(f_2)$ nor $f_2=O(f_1)$.

(Exercise 2.) Construct a set of infinitely many increasing functions from $\Bbb N$ to $\Bbb N$ such that for any two of them, $f_1$ and $f_2$, neither $f_1=O(f_2)$ nor $f_2=O(f_1)$.

(Exercise 3.) Let $h(n)$ be a given function from $\Bbb N$ to $\Bbb N$. Construct a set of infinitely many increasing functions from $\Bbb N$ to $\Bbb N$ such that for any two of them, $f_1$ and $f_2$, neither $f_1=O(h\ f_2)$ nor $f_2=O(h\ f_1)$.


What sort of code is this? Here is a question I encountered:-

Read this section of program code that inputs 10 positive numbers and then outputs the smallest number input. Identify three changes you would need to make to find the largest number input instead of the smallest number.

    Small = 1000
    Counter = 0
    REPEAT
    INPUT Num
    IF Num < Small THEN Small = Num
    Counter = Counter + 1
    UNTIL Counter = 10
    PRINT Small

The question refers to a vague 'program code'-which I do not know of. Neither does this seem like pseudocode due to presence of the equals sign as an assigning operator instead of the arrow '←'.Clearly, not a low-level programming language. So what is it?

Note:I am high school student. This code is part of the 0478 Computer Science IGCSE curriculum here:http://www.cambridgeinternational.org/programmes-and-qualifications/cambridge-igcse-computer-science-0478/past-papers/
If anyone of you know about what this code is and why it is used as part of this IGCSE, please include that in your answer.

This is still a form of pseudocode, obviously just not of the form you might have seen thus far. It is worth noting that there is not strict standard or rules for writing pseudocode, as long as it describes the solution to a problem in such a way that someone could then implement it in a language of their choice.

The term pseudocode simply refers to some notation resembling a programming language, aimed more towards human readability and understanding rather than some language-specific syntax.


Which sort algorithm can I use as a metaphor for this learning philosophy? TL;DR

Which sort algorithm:

Works in multiple passes.
Performs less and less of the total work at each subsequent pass.
When visualized, makes it clear that the decreasing amount of work at each stage is the result of "reaping the benefits" of the work done in previous stages.

The Long version

My nephew is having trouble with math at school and his teacher's methods don't seem to be doing him much good either, so I've begun to tutor him here and there and it's become clear that he has some gaps in his understanding which are hindering his progress. However, he resisting review of things he feels he is already familiar with because this feels like a waste of time to him, after all he "knows that already!". He's a bright kid but like so many children these days (and possibly since the dawn of mankind) he seems to want to rush ahead as quickly as possible, which hurts him in the long run.

There's ample pedagogical evidence that the mastery of a subject before progressing yields better results in the long run, but this can obviously feel like progress is much slower when you're just getting started. I've certainly felt that way and had to discipline myself to believe that deep understanding will beat mechanical routine in the long run (proficiency is important as well, of course).

So partly in an effort to make this case to him convincingly and perhaps mostly because I have a natural tendency to think about such things in algorithmic terms, I'm asking: which (if any) sorting algorithm(s) serve as a good illustration of this principle, that slow progress (more work?) in the initial stages makes subsequent steps easier (less work).

Quicksort's recursive nature isn't a good fit, and neither is merge sort. Insertion sort takes longer at each step (on average, about $k/2$ comparisons at stage $k+1$, I think) while bubble sort only does one comparison less at each pass.

I'm not concerned about $O(n^2)$ vs. $O(n\log n)$, sorting is an imperfect analogy for learning anyway. I'm just looking for a process I can visualize for him, that will set him thinking and that, hopefully, will give him a model to grab onto for use as a mental model for the process of learning (math), a model that places emphasis (and justifies the hard work involved in) on understanding of concepts instead of the memorization of procedures, even when it seems this gets you to the final answer more slowly.

The answer doesn't have to be a sorting algorithm actually, it just seems like the most natural place to look for such an example.

* Bonus points for providing an animation.

Bubble Sort

After each iteration the amount of elements to be compared reduces by one. Will serve a good analogy to working in passes and the amount of work decreases on each pass.

If there is no constraint for analogy the analogy to be from sorting only, then you can use memoization .


In which situation do we choose randomized binary search instead of the normal binary search? Both randomized and normal binary search takes O(log n) time complexity but why does the randomized version exist? In other words what is the advantage of randomized binary search even if it has same time complexity like that of the original binary search ?

Randomized binary search makes sense if your randomness source has a good bias towards your search target. You can then use it to reduce the expected search time (even retaining the $O(\log n)$ asymptotic worst-case complexity) as described in this answer.

If your randomness source is simply a uniform distribution, then you won't get much out of it. If you use it naively (i.e., simply choosing the midpoint according to your randomness source), it will actually perform worse than standard binary search since the worst-case complexity will be $O(n)$, not $O(\log n)$ (consider the case where your interval is $[1,n]$, your target 1, and your randomness source outputs $n-1, n-2, n-3, \dots$).


Minimizing sum of $w_i(y_i - y_c)$ over $y_c$ A person wants to connect $n$ circuit points to the clock signal. Now, the clock signal is going to pass parallel to the x-axis and all those circuit points are going to be connected by vertical to the clock line. Suppose the widths of the vertical wires in the given diagram also vary varying.

If the coordinates $(x_i,y_i)$ for each circuit point $c_i$ to be connected  are given, find $y=y_c$, through which the clock line should pass to minimize the expression
$$L = \sum_{i=1}^n w_i(y_i - y_c)$$
Also prove that your solution is optimal.

$x_i$ is irrelevant, it doesn't appear in the objective function.
$y_i$ and $w_i$ are constant.
So the minimization simplifies to:
$$\operatorname*{argmin}_{y_c} \sum{i=1}^n w_i(y_i - y_c) = \operatorname*{argmin}_{y_c} \sum_{i=1}^n w_iy_i - \sum_{i=1}^n w_iy_c,$$
which is either
$$\operatorname*{argmin}_{y_c} -\left(\sum_{i=1}^n w_i\right) y_c $$
or
$$\operatorname*{argmax}_{y_c} \left(\sum_{i=1}^n w_i\right) y_c $$
So depending on whether the sum of your weights is positive or negative, either the highest or lowest $c_i$ should be $c$.


parse datetime number in html field This is a sample of datetime field:
1615717137369

It means 2 days ago (from 16 march, 13:24)
How can I parse the number?
P.S:
These are some examples:
16 15 89 8678037    16 March 16:15 ( 5 min ago)

16 15 89 8259356    16 March 16:08 (12 min ago)

16 15 89 791 8713   16 March 16:03 (17 min ago)
16 15 89 791 4439   16 March 16:03 (17 min ago)
16 15 89 791 0813   16 March 16:03 (17 min ago)

16 15 89 210 4036   16 March 14:20 ( 2  hr ago)

16 15 64 022 8942   13 March       (3 days ago)

16 10 43 350 1644   13 Jan         (2 month ago)
```

As Emil said, That is the number of milliseconds since the Unix epoch (1 Jan 1970 midnight UTC).


is it possible to minimize pushdown automata? is it possible to minimize pushdown automata?
If no, why?
Is it because for minimization the equivalence classes need to have a finite index and we cannot guarantee that for CFG?

Unfortunately the problem is not computable.  It is undecidable even to tell if two arbitrary PDAs are equivalent; minimizing a PDA is even harder.


Constructing a list of functions/formulas which describes a set of grid points in a 3D matrix Given a 3D matrix of size $N \times N \times N$, let $\mathcal{S}$ be a set of points in the Matrix and $\mathcal{S}'$ be the complement of $\mathcal{S}$. Can we find a set of equations of the form:

$F: (f_1 \land f_2 \land \ldots \land fn)$

where $f_x$ is of the form

$f_x \implies ai + bj + ck + dN + e \text{ } \{<,>,=,\neq\} \text{ } 0$

$f_x$ is true if a point satisfies the aforementioned function and false otherwise

where $i,j,k$ are the indices of the grid points in the Matrix (which vary from 1 to $N$) and $a,b,c,d,e$ are integers such that

$F(\text{all points in }\mathcal{S}) = True$
$F(\text{all points in }\mathcal{S}') = False$

For example:
If $N = 4$, and $S = \{(1,1,1),(2,2,2),(3,3,3),(4,4,4)\}$, we can say that the functions $f_1 \implies i-k=0$ and $f_2 \implies j-k=0$ are one solution for this set.

Ideally we are interested in a solution with the minimum number of equations, but this is not necessary.

Yes.  You can.  You can use linear algebra and linear programming to find a $F$ that is true for all points in $S$ and false for all points in $S'$.

Small simplifications.
Note that $d$ is unnecessary.  $N$ is a constant, so without loss of generality we can assume $d=0$ (otherwise replace $e$ by $dN+e$).  So, we will assume each $f$ has the form $ai+bj+ck+e \bowtie 0$.  Also note that the contents of the matrix itself are irrelevant and all that matters is the set $S$.  Finally, I will assume you are looking for integer values of $a,b,c,e$, with no limit on how large or small they are.

Finding a $f$.
Let's start by showing how, given $S$, you can find a $f$ that is true for all points in $S$.  There are several cases, according to which relational operator $f$ uses:

Equality: For $f$ of the form $ai+bj+ck+e=0$, consider the $a,b,c,e$ as four unknowns.  For each point $(i,j,k) \in S$, we obtain a linear equation on these four unknowns.  You can use linear algebra to find a value for $a,b,c,e$ such that $ai+bj+ck+e=0$ is true for all $(i,j,k) \in S$, if one exists: basically, you use Gaussian elimination to invert the matrix resulting from this system of equations.  Moreover, you can find a basis for the set of all $a,b,c,e$ that are valid solutions.

In this way, we either find zero, one, two, three, or four independent equality constraints $f$ that will be true for all points in $S$.
Less than or equal to: For $f$ of the form $ai+bj+ck+e \le 0$, we can use linear programming to find $a,b,c,e$ that make this inequality true for all $(i,j,k) \in S$.  Each $(i,j,k) \in S$ yields a single linear inequality on the unknowns $a,b,c,e$.  Form a system of inequalities obtained by all the points in $S$.  Solving this then gives us a valid combination of values for $a,b,c,e$.  There may be many solutions; linear programming will give you an arbitrary solution, not necessarily the best one.

You can improve this to check whether there exists a single linear inequality that separates $S$ from $S'$: simply add the linear inequality $ai+bj+ck+e \ge 1$ for each $(i,j,k) \in S'$ to the system of linear equations above, and check whether it has a valid solution.  If yes, then you have a single linear inequality $f$ that yields a minimal solution (an $F$ containing only a single $f$), and you are done.  If not, next try the following heuristic to find a $f$ that separates $S$ from $S'$ as well as possible:

Introduce unknowns $x_{i,j,k}$ for each $(i,j,k) \in S'$, and constrain them by $0 \le x_{i,j,k} \le 1$.  Add constraints $ai+bj+ck+e \ge x_{i,j,k}$ for each $(i,j,k) \in S'$.  Now use linear programming to search for values for $a,b,c,e$ that maximize the objective function $\sum_{(i,j,k) \in S'} x_{i,j,k}$.  This will force $f$ to be true for all points in $S$ and aim to make it false for as many points in $S'$ as possible.

If you want $a,b,c,e$ to be integers, use integer linear programming instead of linear programming.
Less than: For $f$ of the form $ai+bj+ck+e < 0$, we can adjust the above approach by using linear inequalities of the form $ai+bj+ck+e < 0$ (or $ai+bj+ck+e \le -1$ if we require $a,b,c,e$ to be integers) and carrying on as before.
Inequality: Simply swap the roles of $S$ and $S'$ and then use the approach for equalities.

Finding $F$.
So, given sets $S,S'$, this shows how to find a single constraint $f$ that could be included in $F$.  But how do we find a full $F$?

I don't know of any efficient way to find the optimal $F$.  However, I can suggest a heuristic that I suspect will work well: use an iterative greedy algorithm, where at each iteration you find a $f$ that is true for all points in $S$ and that is false for as many points that haven't been covered yet as possible.

In particular, at each stage, we will have a candidate $F$ that is true for all points in $S$, and is false for some points in $S'$.  Define $T = \{(i,j,k) \notin S : F(i,j,k)=\text{True}\}$.  Our goal will be to find $f$ that is true for all points in $S$ and is false for as many points in $T$ as possible; then we will replace $F$ with $F \land f$.

Given $S,T$, how can we find $f$ that is true for all $S$ and false for as many points in $T$ as possible?  Well, I've already described how.  For each relational operator $\bowtie \in \{=,\ne,<,>\}$, use the procedures above to find a candidate $f$ that uses that operator and is true for all of $S$ and false for as much of $T$ as possible.  This gives you four candidates for $f$.  For each candidate, count how many elements of $T$ it is false for, and keep the best one you find.

In this way, I expect you'll fairly rapidly converge to a $F$ that is either optimal (contains the minimal number of clauses) or is close to optimal.


Why is the complement of SAT in IP? It is mentioned in Sipser's text that the complement of SAT is in $IP$, before $IP$ is formally introduced. After looking at the definition and some of the results, I still don't see why this is the case.

Is this supposed to be seen directly? Or is it easier to show that it is in $NPSPACE$, which would prove the claim since $IP = PSPACE = NPSPACE$?

This is of course a consequence of $coNP \subset PH \subset PSPACE = IP$. But it can also be proven directly for UNSAT.

The basic idea is reducing the problem to zero-testing a sum over a polynomial in a suitable finite field. It's a bit too technical to repeat neatly here, but I can give you an informal idea of how it is done.

Let's consider a formula $\phi$, define $p_\phi$ to be the polynomial where you think of $x_i$s as variables, replacing $\neg x_i$ by $(1 - x_i)$, each $\wedge$ by $\times$ and each $\vee$ by $+$. Notice that the formula is unsatisfiable iff $p_\phi(x_1, \dots, x_n) = 0$ for all $x \in \{0, 1\}^n$ or equiavalently if

$$
\sum_{x_1 \in \{0, 1\}}\sum_{x_2 \in \{0, 1\}} \dots \sum_{x_n \in \{0, 1\}} p(x_1, x_2, \dots, x_n) = 0
$$

This follows from the fact that $p_\phi \geq 0$ for any $0/1$ assignement.

The interaction is essentially the prover trying to convince the verifier that the sum is indeed zero. The interaction is done on the sum above modulo a suitable prime to keep computations manageable for the verifier.  The full details are explained here. The main proof that you need to follow and convince yourself of, is that the prover cannot fool the verifier with large probability.


Playing to win strategy algorithm Here is the game's setup:

  You're given a formula for a binary expression using and or not as the connectives. The connectives are combining many variables for which two players will assign truth values to them in the order specified beforehand.
  For Example:

formula: ((x and y) or ((y and z) or (not y and not z)))
turns: AAB
variables: xyz

  In this example Player A will assign a truth to x first, then y, then
  Player B will assign a truth to z. (The variables will always show up
  in the order of appearance in the formula).
  After all of the truth values are assigned to each variable, the formula is evaluated and the truth is returned and a winner is declared. Player A is trying to make it False and B is trying to make it True.

Assume that the other player and will always choose the best value for his variable on all of his turns. If there is no way for a player to make the formula win during his turn, or if choosing either true or false would lead to winning, then false is returned if it is player A’s turn, and true is returned if it is player B’s turn.

Our job is to give the best move for the current turn given a formula the previous moves and the order of moves for the game.

What would the strategy for approaching something this look like? I know this is a homework question but I've spent a week trying to figure this out without any avail. If you need further clarification about the problem as I know it's a big pill to swallow just comment below I'll be sure to reply.

EDIT: For further clarification, variables can show up more than once in the formula

Your game is equivalent to the PSPACE-complete problem TQBF. The quantified Boolean formula corresponding to your example is
$$
\forall x \forall y \exists z (x \land y) \lor (y \land z) \lor (\lnot y \land \lnot z).
$$
Since it is PSPACE-complete, in particular it is NP-hard, and you there is no efficient general way to find out who wins in this game.

There is an exponential time strategy which involves constructing the game tree. While this strategy is feasible when the number of variables is small (like in your example), it is not practical when there are many variables.


NP-hardness given some reducible language While reading a passage in an older textbook I came upon this problem which I am having difficulty in justifying whether its true or false. Is this possible?

If some problem $A$ is NP-hard, and if that problem $A$ can be reduced to problem $B$, and there exists some polynomial-time algorithm which solves $B$, then P=NP?

While I understand that the view is $P≠NP$, if the above case were true would $P=NP$?

Hint: if $A$ is NP-hard, and it can be reduced in polynomial time to $B$, what can you say about $B$? Then if you have a polynomial time algorithm for $B$, what does that imply? (Check out the definition of NP-hardness and NP-completeness).


How to prove 2-EXP != EXP I am guessing that this is correct for 3-EXP, 4-EXP etc...

Basically I should find a problem in 2-EXP that is not in EXP.
Any examples ?

It is a direct consequence of the time hierarchy theorem:

Time Hierarchy Theorem: if f and g are time-constructible functions and $f(n) \log f(n) =
o(g(n))$ (e.g. $f(n) = n^2, g(n) = n^3$), then $DTIME(f(n)) \subsetneq DTIME(g(n))$


Lamport Timestamps: When to Update Counters In the timepiece (excuse the pun) that is Time, Clocks and the Ordering of Events, Lamport describes the logical clock algorithm as the following:

Each process $Pi$ increments $Ci$ between any two successive events.
If event a is the sending of a message m by process $Pi$, then the message $m$ contains a timestamp $Tm = Ci(a)$.
Upon receiving a message $m$, process $Pi$ sets $Ci$ greater than or equal to its present value and greater than $Tm$.

However, the algorithm as it is described on Wikipedia (and other websites) is a little different:

A process increments its counter before each event in that process.
When a process sends a message, it includes its counter value with the message.
On receiving a message, the receiver process sets its counter to be greater than the maximum of its own value and the received value before it considers the message received.

This leaves me with the following questions:

Should be increment the counter before sending a message, as the sending of a message is itself an event. This incremented timestamp is the value that is sent with the message.
When a message is received by process $Pi$ Lamport states that $Pi$ logical clock should be set to $max(Tm + 1, Ci)$. However, the Wikipedia article says that this should be $max(Tm, Ci) + 1$. Is Wikipedia wrong?

Considering that any local action (e.g. increasing a counter) done by a process is an event, the Wikipedia sentence

  "A process increments its counter before each event in that process."

does not make any sense to me. Let me try to answer your questions:

  Should we increment the counter before sending a message, as the sending of a message is itself an event. This incremented timestamp is the value that is sent with the message.

Both actions (i.e. increasing the counter and sending the message) happen atomically in the same event. The same is true when a message is received: The receive event already includes the counter update.

  When a message is received by process Pi Lamport states that Pi logical clock should be set to max(Tm+1,Ci). However, the Wikipedia article says that this should be max(Tm,Ci)+1. Is Wikipedia wrong?

Note that, according to Lamport's paper, the logical clocks must satisfy the following property:

  If $a$ happens before $b$ then $C(a) < C(b)$.

In particular, this means that clock values (of events) at the same process must be strictly increasing.
Therefore, the correct update rule is $\max(Tm,Ci)+1$, as otherwise two subsequent events at the same process might have the same value.


Using software to calculate the complexity of an algorithm I am somewhat a beginner, and I have often seen complexity being calculated for various algorithms but they never actually gave me a very clear idea about how it is done. Can someone please point some resources where I can learn to calculate the complexity of an algorithm?

Secondly, is there some software that calculates the space and time complexity for an algorithm? I have seen that cyclomatic complexity can be calculated by software.

Depending on your background, the CLRS book is a solid introduction. I think in the very first chapter, they walk you through of how to analyze a simple algorithm in terms of both correctness (showing the algorithm really solves the problem) and complexity (how many steps the algorithm performs). There are lots of other books out there some other people might prefer more.

In general, there is no software that does this for you. Coming up with right invariants etc. is somewhat of an art requiring insight and experience. Read more about complexity theory, and you'll discover some inherit impossibilities and problems related to automating such analysis.


Traverse Matrix in Reverse Diagonal strips I thought this problem had a trivial solution, couple of for loops and some fancy counters, but apparently it is rather more complicated.

So my question is, how would you write (in C) a function traversal of a square matrix in diagonal strips.

Example:

1 2 3
4 5 6
7 8 9

Would have to be traversed in the following order:

[3],[2,6],[1,5,9],[4,8],[7]

Straight lines are defined by linear equations. Assuming arrays indexed from zero, as in C, you want the lines $x-y=c$ for $c=2,\,1,\,0,\,-1,\,-2$. This gives something like

for c := 2 to -2 step -1
    for x := 0 to 2
        y := x-c
        if 0<=y<=2
            print A[x,y]


If one-way functions exist are we definitely using them? I know that if one-way functions exist then there are certain universal one-way functions that exist, but to my knowledge they are too impractical to implement (which is the main reason why they are not being used in modern cryptographic protocols).  However, if one-way functions exist are the modern implementations (like RSA and its computational equivalents) definitely one-way?  Conversely, if it can be shown that these cryptosystems are insecure, do one-way functions definitely not exist?

One-way functions are an asymptotic concept. A function such as modular exponentiation with specific parameters doesn't qualify for being a one-way function since it only exists for a specific size. The same can be said about hash functions such as SHA1. In order to ask the question, you will need to specify an infinite family of functions of the type you're interested in.

Once you've specified your infinite family of functions, the answer to both of your questions is negative: even conditional on the existence of one-way functions, we don't know whether these particular families are one-way, and conversely, it could well be that one-way functions exist, but these families are not one-way.

Should we care? Probably not. Even if a family of functions is one-way, that doesn't mean that using one of these functions is secure. One-way functions is an asymptotic concept, and a family of one-way functions can have significant weaknesses unless the key length is $10^{100}$, and still be one-way. What we need is more concrete guarantees.

In practice, functions we use are deemed secure since generations of researchers have tried to break them and failed (or at least failed to let us know that they succeeded). There is no relation to theoretical cryptography.


Rule of thumb to know if a problem could be NP-complete This question was inspired by a comment on StackOverflow.

Apart from knowing NP-complete problems of the Garey Johnson book, and many others; is there a rule of thumb to know if a problem looks like an NP-complete one?

I am not looking for something rigorous, but to something that works in most cases.

Of course, every time we have to prove that  a problem is NP-complete, or a slight variant of an NP-complete one; but before rushing to the proof it would be great to have certain confidence in the positive result of the proof.

This is my personal approach to determine whether a problem (i.e. a language $L$) is NP-complete or not. If both these conditions are verified:

I feel that testing if an instance $I$ is in $L$ implies that I need to check all combinations of some sort
and that there is no way to split such a combination into two smaller ones

then $L$ may very well be NP-hard.

For example for the subset sum problem, I have to list all subsets of $S$ and check if there is one whose sum is zero. Can I split $S$ into two smaller subsets $S_1$ and $S_2$ on which I will check a similar property? Humm... not really. Maybe if I checked for all combination of $S_1$ and $S_2$ but that would be really long...

Usually the ability to break into smaller pieces is a good indicator for a problem to be in P. This is the divide and conquer approach. For example to find the shortest path between two points, you can use the property that if the shortest path from $A$ to $C$ go through $B$ then it is not longer than the shortest path from $A$ to $B$ plus the shortest from $B$ to $C$.

Quite frankly this approach is very basic: I try to find a (polynomial) algorithm for the given problem. If I can't find one then the problem becomes "hard" in my point of view. Then comes all the NP-completeness reasoning: will I be able to encode an existing NP-complete problem into this one? (And since this is usually much harder, I try once more to find a polynomial algorithm..)

I suspect that this is the usual way of thinking. However it remains quite hard to apply on unknown problems. I personally remember being surprised by one of the first examples of NP-completeness I was told: the clique problem. It seemed so simple to check! So I suppose that experience has a lot to do with it. Also intuition can be useless sometimes. I remember being told several times two almost identical problems but one was in P and the other one with a small variation was NP-complete.

I am yet to find a good example (I need help here), but this is like the post correspondence problem: this is an undecidable problem but some variants are decidable.