Interpolate on a cylic x axes Let's assume you are in 2D space and you have a set of fix points FIX_POINTS = [(x1, y1), (x2, y2)]. I want to interpolate the y value for a given x value using the provided points as fix points for a piecewise linear interpolation.

Caveat: The x-axis is cyclic, so it wraps around at a certain known value.

I'm searching a neat algorithm (or way to write this down) which can do this interpolation, so take an x value on the cyclic x-axes and compute the y- value using piecewise linear interpolation.

Example: Given FIX_POINTS = [(10, 50), (90, 100)], and a "cyclic interval" (so the value at which the x axes wraps) of 100, the interpolation would lead to the following results:

  interpolation(10) = 50 # No interpolation necessary, directly on fix points
  interpolation(90) = 100 # Same

  interpolation(50) = 75 # Normal Interpolation
  interpolation(0) = 75 # Wrap around interpolation
  interpolation(1) = 72.5 # Same
  interpolation(99) = 77.5 # Same

I'm not too curious in the actual programming, I'm searching for a way to write this down nicely. Maybe there is even an existing implementation for this? I'm having troubles asking google for the lack of search terms.

I implemented it myself, but it got a lot of code, so I'm in search of something simpler: https://gist.github.com/theomega/9782be548fd452e1f1469757387b35e4 . This implementation also is far from optimal on the computational side (scanning over the array).

I'm not sure if this is the stack exchange for this. Feel free to point me in a different direction.

Find the fixed point $(x_l,y_l)$ just to the left of your $x$-value, and the fixed point $(x_r,y_r)$ just to the right of your $x$-value.  Then use the line between those two fixed points to interpolate.

To find the fixed point to the left and the fixed point to the right, store the fixed points in sorted order (sorted by their $x$-coordinate).  Then you can use binary search to find the fixed point to the left and to the right.

To deal with wrap-around, take the left-most fixed point and add a wrapped-around copy above the upper limit, and similarly add a copy of the right-most fixed point.  For instance, suppose the limit is 0..100, and the left-most fixed point is $(5,20)$ and the right-most fixed point is $(98,3)$.  Then you should add the two additional points $(105,20)$ and $(-2,3)$.  Now apply the algorithm above.


What are the challenges of using gradient descent on hyper parameters λ and η to find out their optimum values? A question from chapter 3 of Michael Nielsen's [Neural Networks and Deep Learning]:

  It's tempting to use gradient descent to try to learn good values for hyper-parameters such as the regularization parameter $\lambda$ and the learning rate $\eta$. Can you think of an obstacle to using gradient descent to determine values of $\lambda$ and $\eta$?

What are the challenges of using gradient descent on hyper parameters λ and  η to find out their optimum values?

C is the L2 regularized cost function.

n is the length of the training data

w is the weight

The Learning rule for the weights will be:

I am having trouble understanding how λ and η will affect the cost function.
I know that we should decrease η as we get closer to the Cost function minima.
I don't have a clue how to optimize λ.
I think that the values of the hyper parameters will change for every epoch so there can't be constant optimal values.

The cost function $C(w,\lambda)$ is not a function of learning rate $\eta$. You can't compute the gradient of $\eta$.

$\lambda$ is part of the cost function. You can indeed compute its gradient and apply SGD on $\lambda$. However, when you do that, $\lambda$ will keep decreasing because its optimal value is obviously $-\infty$.

Note that it is possible to optimize hyperparameters like $\eta$ and $\lambda$ with another neural net, but that is a different story.


Hausdorff distance between two binary images according to distance maps I want to compute the Hausdorff distance between two (very large) binary images X and Y, which is:

$$H(X,Y) = \max\left\{\,h(X,Y), h(Y,X)\right\}\!$$

with

$$h(X,Y) = \sup_{x \in X} \inf_{y \in Y} d(x,y)$$

$d$ being the euclidean distance (or any kind of distance, as it doesn't matter).

The naive algorithm for $h$, comparing each pixel of $X$ to each pixel of $Y$, leading to a complexity of $O(X*Y)$, is way too slow.

I have read many papers saying it is possible to compute the Hausdorff distance in $O(X+Y)$ by first calculating the distance map (distance transform) of $X$ and $Y$.

I can easily compute these distance maps, but I don't see how they can lead to the Hausdorff distance, and I did not manage to find the algorithm in any of these papers.

So the question is, does anyone know how to compute the Hausdorff distance of two images according to their distance map ?

So I finally managed to do it, here's the answer for future reference.

The idea is not to compute the distance map of the image, but of its complement.

Here's a example to better understand :

You have these binary images, where our objects are in black :

Object $X$

Object $Y$

To compute $h(Y, X)$, you need to compute the distance map $dX$ of the complement of $X$ (here using 4-adjacency, but work the same with any distance):

The distance is 0 on the object.

You now only need to find the $max(dX[i,j])$ such as $Y[i, j]$ is in the object.

Here's our example with $Y[i, j]$ in the object in orange, and the $max(dX[i,j])$ in red :

So $h(Y, X) = 3$.

$h(X, Y)$ is computed in a similar fashion, using $dY$ and $X$.

Now that you have $h(X,Y)$ and $h(Y,X)$, you can easily compute the Hausdorff distance $H(X,Y) = \max\left\{\,h(X,Y), h(Y,X)\right\}\!$.

If you already have your distance map, the complexity of the Hausdorf distance is obviously $O(X + Y)$ with this algorithm since you only need to iterate one time over each image.

Note that computing the distance matrix is also done in linear time, so its always better to go with this method instead of the naive one.

Here some sources:

A Linear Time Algorithm of Computing Hausdorff Distance for Content-based Image Analysis (M. Julius Hossain, M. Ali Akber Dewan, Kiok Ahn and Oksam Chae)
An image algorithm for computing the Hausdorff distance efficiently in linear time (R. Shonkwiler)


Isn't std::bernoulli_distribution inefficient? Designing a bit-parallel Bernoulli generator C++11 has a convenient Bernoulli RNG, illustrated at
http://en.cppreference.com/w/cpp/numeric/random/bernoulli_distribution .
However, distilling an entire random integer into a single random bit seems inefficient when the expectation parameter $p$ is rational with a small or power-of-two denominator.
Is there a reasonably fast way to generate 32 random Bernoulli bits at once in such cases? My application uses long streams of bits, so I can keep track of statistics if needed (but this would consume runtime).

Actually, generating a pseudorandom integer is very fast, so the simple approach will likely be quite efficient.  As always, beware premature optimization.  Benchmark it first before assuming it'll be too slow.

If you have a power-of-two denominator, it's easy to come up with a procedure that doesn't require as many random bits -- but in practice this doesn't matter, because with most PRNGs, it's just as fast to generate an entire word as to generate a few pseudorandom bits.


Need a polynomial time reduction from 3SAT to INDEPENDENT-SET In order to show that a problem is NP hard one must provide a reduction from a known NP hard problem to this problem.
My question is how to reduce 3SAT to INDEPENDENT-SET?

3SAT is a satisfiable 3 literals in a clause Boolean conjunctive normal formula.
INDEPENDENT-SET is a set of vertices in a graph, no two of which are adjacent.
I do know how to reduce 3SAT to a Clique, would that help?

The simplest is to reduce Clique to Independent Set using the complement graph, as discussed in the comments.

Alternatively, you can construct a graph to directly reduce 3SAT to Independent Set using "gadgets". One possible start is to do the following: for each clause, construct one node for each of the three variables in the clause. Now, we want to place edges such that:

No two variables in the same clause can be members of the same independent set.
No two variables which are the negations of each other can be members of the same independent set.

If you can accomplish this, then for a boolean formula with $m$ clauses, there is an independent set of size $m$ in your constructed graph if and only if the boolean formula is satisfiable, thus giving the desired reduction.


How to Sort 2D array with out 1D array Hello I am a new Computer Science student
Ok, so I am trying to sort the 2D array I know you can actually sort a 2D array by copying it into a 1D array sort it using any Algorithm, and then place back into the 2D array but here is the problem aren't we using more space and time because we have to copy the array back.
What I have tried so far
#include<stdio.h>

#include<stdlib.h>
#include<time.h>

#define ROWS 3
#define COL 5

void sort(int array[], int size);
void random(int rows, int col, int array[][col]);
void print(int rows, int col, int array[][col]);

int main(void)
{
    int set = ROWS*COL;
    int array[ROWS][COL];
    random(ROWS, COL, array);
    print(ROWS, COL, array);
    sort(array[0], set);
    printf("\n\n\n");
    print(ROWS, COL, array);
    return 0;

}
void print(int rows, int col, int array[][col])
{
    int idx, kdx;

    for(idx = 0; idx < rows; idx++)
    {
        for(kdx = 0; kdx < col; kdx++)
        {
            printf("%d ", array[idx][kdx]);
        }
        printf("\n");
    }
}
void random(int rows, int col, int array[][col])
{
    int idx, kdx;

    for(idx = 0; idx < rows; idx++)
    {
        for(kdx = 0; kdx < col; kdx++)
        {
            array[idx][kdx] = rand() % 10;
        }
    }
}
void sort(int array[], int size)
{
    int temp, idx, kdx;
    for(idx = 0; idx < size; idx++)
    {
        for(kdx = 0; kdx < size; kdx++)
        {
            if(array[kdx] > array[kdx+1])
            {
                temp = array[kdx + 1];
                array[kdx + 1] = array[kdx];
                array[kdx] = temp;
            }
        }
    }
}

But it's not any kind of algorithm and it will not work with dynamic memory you can say since it is just taking benefit of the way c store arrays. But things are different for dynamic arrays in c
Is there any Algorithm to sort 2D array.

By dynamic I presume you mean either:
int* array = malloc(sizeof(int)*col*rows);
or
int* array = new int[rows][col]();
In which case its fairly simple:
void sort(int* array, int size)
{
    int temp, idx, kdx;
    for(idx = 0; idx < size; idx++)
    {
        for(kdx = 0; kdx < size; kdx++)
        {
            if(array[kdx] > array[kdx+1])
            {
                temp = array[kdx + 1];
                array[kdx + 1] = array[kdx];
                array[kdx] = temp;
            }
        }
    }
}

//in main or wherever
int* array = malloc(sizeof(int)*col*rows);
random(array, col*rows);
sort(array, col*rows);
free(array);

Although that is a very sloooooowwwwww sorting operation. How about researching logsort or quicksort?


Wave propagation in digital image I believe the following question in summary is: How to approximate Euclidean distance in a digital plane?

  When a pebble falls on a calm surface of water a circular wave propagates. I want to color the pixels with time to show this effect. So I discretize the time and in each time step, starting  from the center, I color one pixel away in all directions. But this gives a square wave. I guess what is wrong is that I have approximated the Euclidean distance with the infinity norm.

How do I approximate Euclidean distance to get the a circular wave on the pixels? I don't want to measure the distance from each pixel to the center in each time slot. That will be very heavy. I am looking for a simple algorithm like coloring the next pixel adjacent to last colored pixel.

Here's a trick that video game designers have used for years. A computationally cheaper approximation to Euclidean distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is to use
$$
d=\max(|x_1-x_2|, |y_1-y_2|)+\min(|x_1-x_2|, |y_1-y_2|)/2
$$
The relative error between this and the Euclidean distance is no more than 11.8%, which might be good enough for your purposes.


Interrupt driven I/0 handling Suppose in an architecture, interrupt driven IO is used. And suppose a program is to be loaded from an IO device into the RAM. I have been studying IO mechanisms and I came to know that upon receiving a request to load a program, the processor generates control signals to the IO module and then the data is loaded into the IO module interface buffer. When its done loading, it will generate an interrupt to CPU.

But how does a complete file or program gets transferred to RAM? I mean does the processor issues requests only for a byte/word transfer at a time and the interrupt is raised each time a word gets transferred from io device to module? Or is it something else? Please help me understand.

I modern architectures the peripheral has direct access to the system RAM independent of the CPU and what it is executing. This is called a DMA (direct memory access) transfer.

In other words when the interrupt is raised the entire transfer is already completed and you can read the data transferred.


Time-complexity of recursive defined code How would I set up a recursive formula for time-complexity for this code:

int b(int n, int x) {
    int erg = x;
    if (n>1) {
        for (int i = 1; i <= n; i++) {
           erg = erg+i;
        }
        for (int k=0; k<3; k++) {
           erg = erg + b(n/3,erg/9);
        }
    }
    return erg;
}

Is my assumption correct, that it would be something like this? $$T(n)=n(T(\tfrac{n}{3})+n)$$

But how to deal with the if statement and the second for loop, since it is independent of $n$?

The time complexity depends only on $n$ but not on $x$. You can assume $T(n)$ denote the time complexity. For $n\leq 1$, $T(n)=O(1)$ apparently. For $n>1$, the first for-loop takes $O(n)$ time and the second for-loop takes $3T(n/3)$ time since it calls $b(n/3,\cdot)$ three times.


Computing FIRST and FOLLOW sets Suppose we have the following grammar:

S -> A ( S ) B | ε
A -> S | S B | x | ε
B -> S B | y

where S is the start symbol, S, A, B are non-terminal symbols, x, y, (, ) are terminal symbols, and ε is the empty string.

I'm trying to compute the FIRST() and FOLLOW() sets of S, A, and B.

FIRST(S) = FIRST(A ( S ) B) ∪ {ε}
FIRST(A) = FIRST(S) ∪ FIRST(SB) ∪ {x} ∪ {ε}
FIRST(B) = FIRST(S B) ∪ {y}

How can I compute FIRST(S), since I don't know what the FIRST(A) is? How should I attack the problem? Any ideas?

If you just keep applying FIRST, it not hard to understand where to stop.

FIRST($\mathtt{S}$) =  FIRST($\mathtt {A(S)B}$) ∪ {ε}

In your example, FIRST($\mathtt{A}$) includes ε, so

FIRST($\mathtt{S}$) = FIRST($\mathtt {A}$)\{ε} ∪  FIRST($\mathtt {(S)B}$) ∪ {ε} = FIRST($\mathtt {A}$)\{ε} ∪ {$\mathtt{(}$} ∪ {ε}

Now, as FIRST($\mathtt{A}$)\{ε} = FIRST($\mathtt{S}$)\{ε} ∪ FIRST($\mathtt{SB}$)\{ε} ∪ {$\mathtt{x}$}, then

FIRST($\mathtt{S}$) = FIRST($\mathtt{S}$)\{ε} $\cup$ FIRST($\mathtt{SB}$)\{ε} ∪ {$\mathtt{x}$} ∪ {$\mathtt{(}$} ∪ {ε}

Notice that the appearances of $\mathtt{S}$ on the left side are redundant here, so we get (again, because FIRST($\mathtt{S}$) includes ε):

FIRST($\mathtt{S}$) = FIRST($\mathtt{B}$)\FIRST($\mathtt{S}$) ∪ {$\mathtt{x}$} ∪ {$\mathtt{(}$} ∪ {ε}

The end result is FIRST($\mathtt{S}$) = {$\mathtt{y}$, $\mathtt{x}$, $\mathtt{(}$, ε}


Is thread in operating system = thread function in programming languages? I'm new to Operating System, just learnt about process and now is about to learn about threads. From what I understand,

a program is an executable file, program code
a process is a program in execution
a thread is part of a process
in a process, there might be multiple threads. e.g. MS Word
in a programming code, there is the main function and there're might be other functions also
because there is only one main function, usually the program would just run from top of the main function to down.

My question are:

Q1. Is thread in operating system = function in programming language?

Q2. Is function in programming language = thread function in
programming language?

Q3. Is thread in operating system = thread function in programming language?

Q4. Thread function allows multiple functions to be performed simultaneously, like having multiple main functions. Is this correct?

Q5. Where is thread written in operating system/ programming language?

I appreciate it greatly if somebody can explain these in simple terms, and examples from analogy or simple programming languages (C/C++/java).

EDIT:
What I mean by thread function (I'm not sure if this is a correct term) is like,

pthread.h in POSIX thread programming
thr_create, thr_join etc in Thread Functions in Solaris and Windows 9x/NT
CreateThread (included in windows.h?) in Create Threads using C in Windows.

I guess that "thread function" = "thread".

If so, then, from David's answer,

  Q2. Is function in programming language = thread function in programming language?

no.

And from a Q&A in Quora here, it says that

  Q: What is the difference between a thread in a programming language, like Java or Python, and a Linux thread?

  A: There is no difference; it is the same word with the same meaning (as opposed to one word that's overloaded to mean multiple things). The operating system will execute threads in parallel as requested by the software that creates the threads.

So, I guess that the answer for my third question,

  Q3. Is thread in operating system = thread function in programming language?

yes.

And, from POSIX Thread

  Initially, your main() program comprises a single, default thread. All other threads must be explicitly created by the programmer

so I guess the answer for

  Q4. Thread function allows multiple functions to be performed simultaneously, like having multiple main functions. Is this correct?

I think yes.

Q6. Will the program not be able to do multithreading if it doesn't include these thread functions?

I think yes.

Although I'm not sure how it is included/written in programming code that doesn't explicitly use thread functions directly like CreateThread etc., which is my fifth question.

For example, in Tetris code in C, I didn't see any "thread" word inside the code. Instead, it uses conio.h, which is from wikipedia

  conio.h is a C header file used mostly by MS-DOS compilers to provide console input/output. It is not part of the C standard library or ISO C, nor is it defined by POSIX.

Q7. So does this mean this particular programming code in Tetris code in C is single-threaded only?

Q8. Is it by including windows.h, a programming code can perform multithreading?

Please correct me if I'm mistaken.

The remaining questions are Q5, Q7, Q8.

because there is only one main function, usually the program would just run from top of the main function to down.

That's a long way from being the case. Loops, conditional statements and function calls mean that the control flow of any non-trivial program is much more complex than just running from the top of main() to the bottom.

  Is thread in operating system = function in programming language?

No. A thread is, essentially, a subprocess. A process may have several threads, and each of these threads executes semi-independently while sharing some common information. A function, on the other hand, is typically a somewhat self-contained unit of work.

An analogy might be that a process is like a company (there can be many different processes, they're kept separate from each other but they can arrange to cooperate with each other in various ways, governed by the law of the country they're in), a thread is like an employee of a company (employees share access to the company's resources and cooperate closely under rules defined by the company) and a function is a specific task that might be performed by an employee (making coffee, typing a letter, attaching a door to a car, etc.)

  Is function in programming language = thread function in programming language?
  Is thread in operating system = thread function in programming language?

The things you're calling "thread functions" are just programming language libraries that access the operating system's interface for creating and managing threads

  Thread function allows multiple functions to be performed simultaneously, like having multiple main functions. Is this correct?

Well, threads allow multiple functions to be performed simultaneously. main() is just the entry point to the program as a whole: it's the place where execution starts.

  Where is thread written in operating system/ programming language?

I'm not sure what you mean by this but it's going to depend on the OS and programming language in question.

  Will the program not be able to do multithreading if it doesn't include these thread functions?

A program will need some way of telling the operating system to make a new thread. In practical terms, using a library that somebody has already written is going to be more convenient than trying to manage the interaction with the operating system yourself.


Analysis of an approximation claim Consider the load balancing problem on two machines. Thus we want to distribute a set of $n$ jobs with processing times $t_1,...,t_n$ over two machines such that the makespan (maximum of the processing times of the two machines) is minimized. Professor Smart has designed an approximation algorithm Alg for this problem, and he claims that his algorithm is a $1.05$ approximation algorithm. We run Alg on a problem instance where the total size of all jobs is $200$, and Alg returns a solution whose makespan is $120$.

(i) Suppose that we know that all job sizes are at most $100$. Can we then conclude that professor Smart's claim is false?

(ii) Same question when all job sizes are at most $10$.

Let's talk about the case (i):

We know that $\sum{t_i} = 200$ and that $t_i \leq 100$. The makespan of the Algorithm $Alg = 120$, so $Alg \leq 1.05 * OPT$. We have no other information about the algorithm used. A lower bound would be $LB = max( \frac{\sum{t_i}}{2}, max(t_i)) = max (100,100) = 100$ so I would say for that particular instance we'd have $120 \leq 1.05 * 100 = 105$ which means the claim would be false.

Likewise for the case (ii).

My answer is marked as incorrect, and I am struggling to do the right analysis.

Can anyone help please ?

You case (i) analysis is wrong, consider the input $60 + 60 + 60 + 20 = 200$. The most even split you can do is $60 + 60$ and $60 + 20$ which has a makespan of $120$, thus there is at least one feasible input for which professor Smart's algorithm returns the optimal result.

For case (ii) we know each job size is at most 10. Professor Smart's algorithm returns a makespan of $120$, which means one machine has a sum of jobs of $120$ and thus the other $200 - 120 = 80$.

But since we know each job has at most a size of $10$ we could move jobs over from the bigger instance to the smaller instance at least until the bigger instance hits $110$ and the smaller $90$ while being guaranteed that each job moved reduces the makespan. But $110 \cdot 1.05 < 120$ thus the algorithm is not a $1.05$ approximation algorithm.


Kth largest subset for small K The $K$th Largest Subset problem is often given as an example of an NP-hard problem. However, the assumption is that $K$ is unconstrained, and can be as large as $2^n$. Clearly, if $K \le 3$ the solution in $O(n)$ time is trivial.

Are there any general results for time complexity of this problem for a given (and potentially small) $K$?

There is a simple algorithm whose complexity is $O(Kn)$. The algorithm computes, for each $m \leq n$, the $K$ largest sums of the first $m$ numbers. Given the list for $m$, the list for $m+1$ is computed by adding the $(m+1)$st element to the old list, merging the two lists, and keeping only the top half. Since merging sorted lists can be done in linear time, the resulting complexity is $O(Kn)$.


Implementing Nesetril and Poljak's clique detection algorithm I want to implement the clique detection algorithm by Nesetril and Poljak described in [1].

However, I can't seem to understand how the auxiliary graph $H$ is to be created and how it can be used to detect a clique. For instance, the paper suggests that to detect a clique of size $3\ell$ in a graph of size $n$, we construct an auxiliary graph $H$ of size $n^\ell$. For the detection of a clique of size $6$ in a graph $G$ of size $8$ for example, then the size of $H$ would be $64$ (i.e. $8^2$) and then checking for the presence of a triangle in $H$ which would indicate the presence of a clique of size $6$ in $G$.

Further down, while describing how to construct $H$, they stated that the vertex set of $H$ should be a subset of the vertices of $G$, and that the size of this subset is $\ell$. This is the first conflict. The second conflict is in the construction of the edge set. What is meant by $Y'$ in this sentence: $E(H)=\{ \{Y,Y'\} ; Y \neq Y' \text{ and } Y \cup Y' \text{ forms a complete subgraph in } G \}.$

The paper did not at any point after this sentence define what $Y'$ was.

Any explanation will be appreciated.

[1] J. Nešetril, S. Poljak, On the complexity of the subgraph
problem, Comment.Math. Univ. Carolinae 14 (1985) 415–419.

The high-level idea is this: the existence of a triangle in $H$ corresponds to the existence of a clique of size $3\ell$ in $G$, and we know how to detect triangles using matrix multiplication.
So let $\ell$ indeed be divisible by three. The auxiliary graph $H$ has a vertex for every $K_\ell$, and an edge between two vertices precisely when the corresponding vertices form a $K_{2\ell}$. Then $G$ has a $K_{3\ell}$ iff $H$ contains a triangle.

Example: Suppose we wish to find cliques of size 6 from a given graph $G$. The trivial algorithm that checks all 6-sets of $V(G)$ runs in time $\Theta(n^6)$. Let's see how we can improve on this.
Observe that $\ell = 2$, i.e., we are looking for cliques of size $3\ell = 6$. To build $V(H)$, we check all 2-sets in $O(n^2)$ time (but of course now the $K_2$'s are precisely the edges of $G$). Similarly to build $E(H)$, we spend $O(n^4)$ time. The graph $H$ has $\Theta(n^\ell)$ vertices, so a triangle can be detected in time $O(n^{\omega \cdot \ell})$ in it, where $\omega < 2.376$ is the exponent of matrix multiplication. In our case, this simplifies to $O(n^{4.752})$ time, beating the naive brute-force algorithm above.


What is complexity of checking whether a natural number is a perfect square? As the title says, what is complexity of checking whether a natural number is a perfect square?

For a given number $n$, binary searching for the square root $\sqrt n$ solves this problem in time $O(\log n)$.


Find the max of a convex function in fewest samples Suppose there is a convex function, and a certain domain interval.  I want to find the max of this function within the interval.  The goal is to minimize the number of times the function is evaluated, because evaluating it is expensive.

I can think of a naive solution involving evaluating the function at two points of the interval (thereby partitioning the interval into three sub-intervals) and discarding the edge sub-interval of the point with the lower function value.  But, I am not sure whether it's optimal.

As the function $f$ is convex, its maximum value in interval $[a,b]$ is either $f(a)$ or $f(b)$.  Otherwise, it will violate Jensen's inequality.


When are edges adjacent? What conditions must be fulfilled for two edges of a graph to be called adjacent?

I found a lot about adjacent nodes, but our CS course script refers to adjacent edges, with no explanation.

Two edges are adjacent if they're incident on the same vertex:

Two edges are adjacent if they have exactly one common endvertex.
—Bollobás, Modern Graph Theory (Springer, 1998; page 2).
Two edges $e\neq f$ are adjacent if they have an end in common.
—Diestel, Graph Theory (2nd Edition, Springer, 2000; page 3).


Why does Dijkstra's algorithm not account for updating node distances after expanding a node? Why does Dijkstra's algorithm not re-evaluate/re-expand nodes who have been expanded and later had their weight changed?

For example, in the accepted answer of this question (link), if the algorithm simply understands that d(b) has been updated and it should re-expand b, the shortest cost would be found.

Am i missing something?

Since Dijkstra's algorithm always expands the shortest path first, the first time we reach a node will be along the shortest path to that node. That is the key insight that allows the algorithm to be efficient compared to a breadth-first-search.

There is no way to construct a graph where no costs are negative and there exists a path from a to b shorter than the one Dijkstra's algorithm finds.


Prove that a language is bounded if and only if it's finite Let's assume $L$ is a language. $L$ is bounded if for some natural number $n \in \mathbb N$ applies $|x| ≤ n$, where $|x|$ is a length of a string, with every $x \in L$. Let's also assume that $L$ lies in a finite set of alphabets $\Sigma$.

How to prove that $L$ is bounded if and only if it's finite?

The claim holds only for languages over finite alphabets.

Bounded $L$ $\implies$ Finite $L$

Let $\Sigma$ be the alphabet of $L$ and $L$ be bounded by some $n \in \mathbb{N}$.

The largest possible such $L$, call it $L^\#$, is $\bigcup_{\,i=0}^{\,n} \Sigma^i$ elements. $L^\#$ is finite since $|L^\#| = \sum_{i=0}^{n} |\Sigma|^i$. Therefore, any $L \subseteq L^\#$ must also be finite.

Finite $L$ $\implies$ Bounded $L$

Let $x^\#$ denote the longest string in $L$. Such a string must always exist since $L$ is finite.

Then, $\forall x \in L \ldotp |x| \leq |x^\#|$ and thus, $L$ is bounded.

A simple counterexample to the infinite alphabet case:

Consider an infinite alphabet $\Sigma = \{ s_0, s_1, ... \}$. The language $L = \Sigma$ is bounded since $\forall x \in L \ldotp |x| \leq 1$, but is infinite.


Time complexity of code running at most summation(N) times in a loop Let’s say I have a JavaScript loop iterating over input of size N. Let’s say all elements in N are unique, so the includes method traverses the entire output array on each loop iteration:

let out = []
for (x in N) }
  if (!out.includes(x)) {
    out.push(x)
  }
}

The worst case runtime of the code inside the loop seems to be not O(N), but the summation of N, which is substantially faster.

Is this properly expressed as O(N^2) overall or is there a standard way to convey the faster asymptotic behavior given the fact that the output array is only of size N at the end of the loop?

If i understand you correctly, then the following holds:
$\sum_{k=1}^nk= \frac{n(n+1)}{2} \ge \frac{n^2}{2} = \Theta (n^2)$

Thus there is no asymptotic gain.


Collection of APX-hard problems Everyone knows "Garey & Johnson", which is my go-to reference whenever I need a problem to transform from for an NP-hardness proof. However I recently find myself in need of an APX-hardness proof, and I wonder if there is a similar (and more up to date..?) collection of problems that have been shown to be APX-hard.

Does anybody know of anything like this? I find it hard to believe that there is no website systematically collecting such problems, but my Google skills seem to be insufficient.

I've used this compendium a few times...
Is this what you were aiming for?


How many operations to produce this superposition of 3 qubits? Suppose I have three qubits that of course represent $2^3=8$ states. I want to put these qubits so that they are in the particular superposition say...

$$a|000\rangle + b|001\rangle + c|010\rangle + d|011\rangle + e|100\rangle + f|101\rangle + g|110\rangle + h|111\rangle\,.$$

Here's the question: do I perform a 2d rotation on each qubit (each having its own $2\times2$ rotation matrix) for a total of three operations, or do I perform a single 8d rotation using an $8\times8$ rotation matrix?

Follow up question: if the answer is 'make an $8\times8$ matrix', doesn't this at some point boil down to just applying a rotation to each qubit?

You don't need a full 8x8 three-qubit operation, but you will need a two-qubit operation of some kind. If you only rotate each qubit independently, you'll find you can only make un-entangled states like:

$(a_1 \left| 0 \right\rangle + b_1 \left| 1 \right\rangle) \otimes (a_2 \left| 0 \right\rangle + b_2 \left| 1 \right\rangle) \otimes (a_3 \left| 0 \right\rangle + b_3 \left| 1 \right\rangle)$

$= a_1 a_2 a_3 |000\rangle + a_1 a_2 b_3 |001\rangle + a_1 b_2 a_3 |010\rangle + a_1 b_2 b_3 |011\rangle + b_1 a_2 a_3 |100\rangle + b_1 a_2 b_3 |101\rangle + b_1 b_2 a_3 |110\rangle + b_1 b_2 b_3 |111\rangle$

But as soon as you have a non-trivial two-qubit operation, like a controlled-NOT, to go with your single qubit gates, you can approximate any larger operation or state arbitrarily well. (This is different from classical reversible computing, where you need a doubly-controlled-not before you get universality.)

The basic idea of how it's done is:

Break a large operation into lots of single-qubit operations, but allowing each to have lots of controls.
Use the fact that all single-qubit operations have a square root to knock controls off of multi-controlled operations until you're left with singly-controlled operations.
Replace controlled-whatevers with controlled-NOTs by finding $A$, $B$, $C$, $\theta$ such that $ABC = I$ but $AXBXC e^{i \theta} = U$ for each single-qubit operation $U$.

The details of these kinds of constructions are covered in textbooks.


show that if L is a regular, then drop(L) is a regular I am trying to prove the following problem, but honestly I don't know what "proof" is considered a good proof.

I tried to prove it by constructing an NFA that start with w1 and ends with wk, but I feel something is missing.

I also tried to prove it by showing that w1 ∈ L1, w2 ∈ L2, …, wk ∈ Lk and a ∈ La.

thus Language L can be represented by:

L = L1*La*L2*La*…LaLk
If L is regular then L1,L2,...,Lk and La are also regular.

Finally drop(L) can be presented as follow:
drop(L) = L1*L2*…*Lk, since L1,L2,...Lk are regular is drop(L) (because we know that it is closed under concatenation)

I feel that there are some notation that I am not using correctly, I don't know why I feel something is missing but can't figure it out.

I'm not sure what $L1, \dots, Lk$ are since you did not define them. The easiest way is probably that of starting with a DFA for $L$ and constructing a NFA for $drop(L)$ (hint in the spoiler below).

   Replace all transitions labelled with "a" in the DFA for $L$ with $\epsilon$-transitions in the NFA for $drop(L)$.

Then it should be easy to show that:

If $w \in drop(L)$ then the NFA accepts $w$: use the definition of the function $drop$ to conclude that there must be a suitable word $w' \in L$.  Start from an accepting path $\pi$ for $w'$ in the DFA for $L$ and modify $\pi$ to be an accepting path for $w$ in the NFA for $drop(L)$.
If the NFA accepts a word $w$ then $w \in drop(L)$: look at an accepting path in the NFA for $drop(L)$ and use it construct a word $w'$ that is accepted by the DFA for $L$. Use the fact that you just proved that $w' \in L$ and the definition of the function $drop$ to conclude that $w$ must belong to $drop(L)$.

I'm purposefully being a bit vague on the details, so I don't completely give away the solution. Comment if you need more help.


Build LL(1) parsing table for grammar S -> iSeS | iS | a Task

Bulid parsing table for grammar S -> iSeS | iS | a
Resolve conflicts in this table and simulate parser work for word iiaea

Problem

I know how to make a parsing table for unambiguous grammar, and how to simulate parser. However this grammar is an example of dangling else problem.

What I tried

I was tought that I should remove left recursion and left factoring. Then make a table using first and follow. Whatever I tried I got two grammar expressions in the same row of table. Please provide me some hint what to do in this situation.

After left factorization

S ->  iSS' |a
S'-> e S | ε

Because we will never use S' ->  ε (there are no other values which can give us e in the Table except Table[S'][e] ) we can remove this production from parsing table.

Final solution

Eventually you will end up with having to choose  between $S'\to\epsilon$ and $S'\to eS$.

The grammar says that's a conflict.  But can't we deduce which is correct? What if we choose $S\to\epsilon$? Will we ever be able to match the e?


Asymptotic Notation Analysis 2^n=O(3^n) : This is true or it is false if n>=0 or if n>=1
since 2^n may or not be element of O(3^n)
I need a hint to figure the problem

It is a common misconception that O(g(N)) notation represents a function. It actually represents a set of functions whose asymptotic complexity is bounded by the function g(N) as N approaches infinity. In your example, g(N) = 3^N.

So to ask is 2^n = O(3^n) is mixing apples and oranges, or in this case you are comparing a function with a set of functions. We often write it this way, but it is understood that we are talking about membership in a set of functions, not equality.

The more correct way to state this is:

Is function 2^n contained in the set of functions represented by O(3^n)?

With the question phrased this way, the exact values of n do not enter into it because now you are asking if the function 2^n is a member of the set O(3^n).

The short answer is: yes it is.

But to understand why, you need to understand the formal definition of big-O notation which is:

   f(x) is contained in O(g(x))

if and only if for all sufficiently large values of x, the absolute value of f(x) is at most a positive constant multiple of g(x). That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that

|f(x)| <= Mg(x) for all x >= x0

So for 2^n and O(3^n), we can set M to 1 and x0 to 1, and we get:

|2^n| <= 3^n for all n >= 1

With n=1, we have 2 <= 3, which is true.
With n=2, we have 4 <= 9, which is also true,
and informally we can see that 3^n grows faster than 2^n, so we know this relationship holds for all n > 2 as well, and thus:

2^n is contained in O(3^n)

For a more complete description of big-o notation, refer to this excellent post  https://cs.stackexchange.com/a/23594/87624 or for something specific to BigO notation, read the Wikipedia article on big-o notation


All nearest neighbor in a changing 2d euclidean space I am in need of an algorithm for a part of a game (a mod) I am making. I have abstracted the problem:

Given a 2D space with $N$ random points $p_1...p_n$, calculate the nearest neighbor of each of the points, where the distance is at most $C$.

Note that our list of points is unsorted, and that each point is an actual object so I could give it any property I want.

Now this can easily be done in $O(n^2)$ time, it is also the easiest and not really an issue.
However, the time it takes when a new point is added or a point is removed is also $O(n^2)$, and I would like to get that down, because this is done during gameplay (while the initial step is only done at start).

Does anyone know a possible improvement over the simple 'bruteforce'? I tried sorting, twice, and keeping it up to date (using a 4x linked list (up, down, left, right)) but that did not seem to work.

You want a data structure that supports nearest neighbor search in 2D.  There are many options, but a simple one that is widely used for practical situations is a quadtree data structure.  It supports both efficient lookup and efficient insert operations.


NFA for words which start and end with different letters with $O(\log(| \Sigma |))$ states I'm trying to build a NFA for the following language
$ L = \{ \sigma_1 \sigma_2 \sigma _3 \ldots \sigma _n \mid \sigma _1 \neq \sigma _n \}$.
The catch is that for $ \Sigma $ such that $ |\Sigma|=2^k $, the NFA should have $\Theta(k)$ states.
I was thinking of representing the letters in binary but I'm not sure what I should do exactly.

The original question referred to DFA (and not NFAs). However, no DFA for $L$ with $O(k)$ states exists.
Consider $\Sigma$ as a set of words (i.e., each word consists of a single  character from $\Sigma$).
Given any two distinct words $a,b \in \Sigma$, the word $a$ is a distinguishing extension for $a$ and $b$. I.e., $aa \not\in L$ but $ba \in L$.
This shows that the number of equivalence classes of $L$ w.r.t. the equivalence relation "not having a distinguishing extension" is at least $|\Sigma|$.
By the Myhill-Nerode theorem, any DFA for $L$ must have at least $|\Sigma|$ states.

The idea to build a NFA with $O(k)$ states is as follows:
in addition to an initial state $s$, and to an accepting final state $t$ there are $2k$ states indexed with $1, \dots, 2k$.
Assign a distinct integer $x_a$ from $0$ to $2^k-1$ to each character $a \in \Sigma$ and consider the binary string $b_a$ of length $2k$ obtained by concatenating the binary string of length $k$ representing $x_a$ in binary, with its complement.
For each character $a \in \Sigma$ let $S_a$ be the set of all states $i$ such that the $i$-th least significant bit in $b_a$ is $1$, and define $\overline{S}_a = \{1, \dots, 2k\} \setminus S_a$.
For each $a \in \Sigma$, add the following transitions:

A transition from $s$ to each state $i \in S_a$.
A transition from each state $i \in \{1, \dots, 2k\}$ to itself.
A transition from each state $i \in \overline{S}_a$ to $t$.

Given a word $\sigma_1, \sigma_2, \dots, \sigma_n$ with $\sigma_1 \neq \sigma_n$, let $i$ be an index such that the $i$-th least significant bit of $b_{\sigma_1}$ is $1$  while the  $i$-th least significant bit of $b_{\sigma_n}$ is $0$ (such an index always exists).
Then, $s \to i \to i \to \dots \to i \to t$ is an accepting path in the NFA.
Conversely, any accepting path is of the form $s \to i \to i \to \dots \to i \to t$ for some $i$. This implies that $i \in S_{\sigma_1} \cap S_{\sigma_n}$, i.e., $b_{\sigma_1}$ and $b_{\sigma_n}$ differ (at least) on the $i$-th least significant bit. This shows that $\sigma_1 \neq \sigma_n$.
The number of states of the NFA is $2k+2$.
Here is an example for $\Sigma = \{x,y,z,w\}$. All edges for which no label is shown are actually labelled with $x,y,z,w$.


Divide and Conquer 3D Convex Hull http://cs.jhu.edu/~misha/Spring14/Preparata77.pdf

This is a divide and conquer algorithm for computing the convex hull in 3 dimensions.

I am having trouble understanding the merge step, which is titled Merge in 3 Dimensions, outlined in the paper.

I am specifically having trouble understanding how the number of comparisons made is done in O(n) time for the whole hull.

On page 92 in the last paragraph on the left column, it says that the number of comparisons made is bounded by the number of edges which is linear for each hull. But what if each vertex had p edges (so you are checking duplicates), then that would add up to quadratic running time. Or, if the number of edges each time was monotonically increasing from 1 to p-1, that still adds up to quadratic running time for the comparisons. For instance, a tetrahedron has 4 vertices and each vertex has a degree of 3, so the number of comparisons made would be 12.

The paper explains why the number of comparisons is $O(n)$ in the next few sentences immediately after the statement you're asking for a justification of.  Just keep reading for a few more sentences, and you'll immediately find the justification.  As it says,

  "First of all, we notice that each type 1 comparison definitively eliminates one edge ...  Since the numbers of edges of A and B are at most $(3p-6)$ and $(3q-6)$, respectively, the number of type 1 comparisons is bounded by ..."

and so on.  So to find the explanation for that statement, just continue reading a few sentences onward.

And, as the paper says in the introduction,

  "[our algorithm]" is based on the property that the number of edges of the convex hull of $n$ points is at most linear in $n$."

Therefore, your examples are not possible.

See also the 3rd paragraph of Section 4 for more elaboration ("It is a crucial observation that...").


Necessary and sufficient condition for unique minimum spanning tree This is an exercise problem (Ex.3) from the excellent lecture note by Jeff Erickson Lecture 20: Minimum Spanning Trees [Fa’13]
.

  Prove that an edge-weighted graph $G$ has a unique minimum spanning tree if and only if the
  following conditions hold

  For any partition of the vertices of $G$ into two subsets, the minimum-weight edge with one endpoint in each subset is unique.
  The maximum-weight edge in any cycle of $G$ is unique.

Consider the "$\Rightarrow$" direction and the following graph $G$.

$G$ has a unique MST. However, for the partition $\{A\}$ and $\{B,C\}$, the minimum-weight crossing edge is not unique.

  Did I misunderstand some points? Or if there are flaws in the theorem, how can we fix it?

Answer my own question by simply copying the comment made by @JeffE, the author of the lecture note：

  Oops! Yes, this is a bug. (Note to self: Change every instance of "Prove" to "Prove or disprove".) – JeffE


How can a machine with fixed output for all inputs be considered a Turing machine? From this answer, and the comments that follow:

To clarify, this machine T′ with the fixed output for all inputs is a Turing machine? – Shashank V M

@ShashankVM, Yes, T′ is a Turing machine. – D.W.♦ (When can a deterministic finite-state-automata (DFSA) along with its input sequence be said to be a part of another DFSA?)

From what I understand, a machine with fixed output for all inputs is a Turing machine.
Consider this thought experiment, I have a "machine" which is a wall with a slit through which I can pass a tape in. The "output" of this machine is on the wall, i.e. it is painted on the wall as a fixed string $S$, which for the purpose of this experiment is "Hello". So no matter what is written on the tape, the output of this "machine" is "Hello". From what I understand this "machine" is a Turing machine.
Is my understanding correct or am I missing something?
Because I find it hard to believe that this wall with a slit can be considered a Turing machine, when a supercomputer is considered a Deterministic Finite State Automaton.
Also I cannot see how this "machine" can emulate any another Turing machine or do any useful computation.

There's no notion of "can be considered to be a Turing machine".  Something either is a Turing machine, or it isn't.  There's a formal mathematical definition of what a Turing machine is: https://en.wikipedia.org/wiki/Turing_machine#Formal_definition
I never claimed that just because some process always produces the same output, that process must be a Turing machine.
There might be some confusion about Turing machines vs DFAs.  A computer could be modelled as a DFA (if we treat its memory size as fixed), or it could be modelled as a Turing machine (if we imagine that it's possible to gain more memory; or we just don't care to make use of the fact that memory size is fixed).  These two different ways to think about a computer have different advantages and disadvantages.  I suggest reading Is a PDA as powerful as a CPU? and How many gates until Turing Complete and How does an automaton model a computer or something else? and How does an automaton actually "compute"?, as I suspect they get at the core issue you are struggling with.


NP-complete problems not "obviously" in NP It occurred to many that in all the $\textbf{NP}$-completeness proofs I've read (that I can remember), it's always trivial to show that a problem is in $\textbf{NP}$, and showing that it is $\textbf{NP}$-hard is the... hard part. What $\textbf{NP}$-complete problems are these whose polynomial-time verifiers are highly non-trivial?

There are at least four such $NP$-complete problems listed in the appendix of Garey and Johnson's COMPUTERS AND INTRACTABILITY: A Guide to the Theory of NP-Completeness.

[AN6] NON-DIVISIBILITY OF A PRODUCT POLYNOMIAL
INSTANCE: Sequences $A_i = \langle (a_i[1],b_i[1]), ..., (a_i[k],b_i[k]) \rangle,\ 1 \leqslant i \leqslant m,$ of pairs of integers, with each $b_i[j] \geqslant 0,$ and an integer $N$.
QUESTION: Is $\displaystyle \prod_{i=1}^m \left( \displaystyle\sum_{j=1}^k a_i[j] \cdot z^{b_i[j]} \right)$ not divisible by $z^N - 1$?
Reference: [Plaisted, 1977a], [Plaisted, 1977b].  Transformation from 3SAT.  Proof of membership in NP is non-trivial and appears in the second reference.

The other three I found in the appendix are:

[LO13] MODAL LOGIC S5-SATISFIABILITY
[LO19] SECOND ORDER INSTANTIATION
[MS3] NON-LIVENESS OF FREE CHOICE PETRI NETS


Nondeterministic PDA for the following language with Kleene star I had a question regarding converting a language with the Kleene star production into a PDA. Here's the particular language I was looking at in my textbook:

$$L = (aaa^*bab)$$

My normal approach to constructing PDA's for languages would be to determine the pattern or rule of the language, and think to myself that it's sort of like counting the number of symbols using a stack, and determining whether the stack is empty at the end of the computation.

However, I'm not sure how to construct a PDA for languages like the one above where there isn't a particular rule regarding the $a^*$ production.

How would one normally handle these types of situations? Thank you.

I figured out the answer and hope this will help anyone with similar confusion in the future.

Since a pushdown automaton is essentially a finite automaton with an extra component called the stack which is used for storage, if we are presented with a regular language like the one given above, we simply need to create a PDA that does not use the stack. This concept confused me at first, but here's what I mean:

$$L = (aaa^*bab)$$

$\space$

$$M = (Q, \Sigma, \Gamma, \delta, q_0, z, F)$$
$$Q = \{q_0,\ q_1,\ q_2,\ q_3,\ q_4,\ q_5\}$$
$$\Sigma = \{a,\ b\}$$
$$\Gamma = \{$\}$$
$$z = \$$$
$$F = \{q_5\}$$

$\space$

$$\delta(q_0, a, $) = \{(q_1,\ $)\}$$
$$\delta(q_1, a, $) = \{(q_2,\ $)\}$$
$$\delta(q_2, a, $) = \{(q_2,\ $)\}$$
$$\delta(q_2, b, $) = \{(q_3,\ $)\}$$
$$\delta(q_3, a, $) = \{(q_4,\ $)\}$$
$$\delta(q_4, b, $) = \{(q_5,\ $)\}$$

$\space$

I'm not completely certain about the stack start symbol, because I've noticed some resources use it regardless, while others assume that at the beginning the stack is empty ($\lambda$) and push the start symbol at the first step.

Anyway, I hope this answer helps anyone else.


Are the definitions of constructs in terms of lambda terms issues in implementation/design or uses of functional languages? In Lambda Calculus, natural numbers, boolean values, list processing functions, recursion, if function are defined in terms of lambda terms. For example, natural numbers are defined as Church numerals, and recursion is defined in terms of a fixed point of a function.

Functional languages are said to be based on Lambda Calculus.

Who shall be concerned about the above concepts in terms of lambda terms: the implementer/designer of the languages, and/or programmers in the languages?

Do functional programming languages define/implement the above concepts in terms of lambda terms?
As programmers in regular functional programming languages (such as Haskell, Lisp, ML),  is it correct that the above concepts are always given in the same way as in imperative languages, and we never have to understand or deal with their definitions in terms of lambda terms?

Thanks.

Those features are almost never implemented like the lambda calculus in modern programming language implementation. In some cases, using the lambda calculus representation for datatypes has performance improvements (this is associated with so-called tagless representations). Historically, the Haskell compiler did use this representation early on, but has since dropped it. In either case, it never affected user code, and was an implementation detail.
Unless there's a compelling reason to, most code does not use said representations, so the programmer will never interface with them. So those concepts are generally the same as in imperative languages, although keep in mind that there are differences since most functional languages are expression-oriented; e.g. 'if ... then ... else ...' is an expression which returns a value, rather than a statement.


Given an integer n, print all integers from 1 to 2^n. Why does this not prove that P!=NP? I only just recently learned about the P=NP problem in introduction to algorithms class, and I'm still trying to wrap my head around it. I thought of this situation while cleaning my room today and couldn't think of a way to disprove it to myself. Perhaps it

Obviously, the algorithm described in the title would have to iterate 2^n times to print all numbers from 1 to 2^n. As a result, this algorithm would never be able to be done in polynomial time and P is indeed a proper subset of NP. What is the error in my reasoning here? Is it that this problem is not in NP?

NP is the set of problems that can be verified in polynomial time, i.e. there is a polynomial-time algorithm that can verify a purported solution. P is the set of problems that can be solved in polynomial time, i.e. there is a polynomial-time algorithm that can find a solution.

“The problems in NP are those not able to be solved in polynomial time” is completely wrong. This is not at all what NP means. The N in NP is for “nondeterministic”, not for “not”. A problem in NP may be solvable in polynomial time — P is a subset of NP. The question “P = NP?” is in fact whether all problems in NP are solvable in polynomial time.

The set of problems that cannot be solved in polynomial time is the complement of P.

Note that “problem” has a specific technical meaning: it's a decision problem, i.e. an function from some input space to $\{\mathrm{yes}, \mathrm{no}\}$.

Counting is not a decision problem, so it doesn't fit in the classification that includes P and NP.

If you found a decision problem that cannot be solved in less than $2^n$ steps where $n$ is the size of the input, then that problem would not be in P. It might not be in NP either: it would only be in NP if there was a way to verify a solution in polynomial time.


Proving Clique Number of a Regular Graph I am very new to Graph Theory and I am trying to prove the following statement from a problem set for my class:

Prove that if G is a regular graph on n vertices $(n \ge  2)$, then  $\omega(G) \in \{1, 2, 3,... \lfloor n / 2 \rfloor, n\}$

I am confused by the part where it places the clique number to be in this set: $\omega(G) \in \{1, 2, 3,... \lfloor n / 2 \rfloor, n\}$. Why can the clique number be only in the first half of this set (or it can be n) and why can't it be anything between $\lfloor n / 2 \rfloor$ and $ n$?

How can I go about proving this claim? Any tips would be appreciated.

Let $G$ be a $d$-regular graph on $n$ vertices containing an $a$-clique $A$, and let $B$ denote the other $b:=n-a$ vertices. Suppose that $a>b$.

Let $e$ be the number of edges connecting $A$ to $B$. Every vertex in $A$ has $a-1$ edges going to the other vertices in $A$, and so $d-(a-1)$ edges going to vertices in $B$. Hence $e = a(d-(a-1))$. Similarly, every vertex in $B$ has at most $b-1$ edges going to the other vertices in $B$, and so at least $d-(b-1)$ edges going to vertices in $A$. Hence $e \geq b(d-(b-1))$. It follows that
$$ b(d-(b-1)) \leq a(d-(a-1)). $$
Subtracting the left-hand side from the right=hand side, we get
$$
0 \leq (ad-a^2+a)-(bd-b^2+b) = (ad-bd)-(a^2-b^2)+(a-b) = (a-b)(d-a-b+1).
$$
Since $a > b$, it follows that $d \geq a+b-1 = n-1$. In other words, $G$ is the complete graph.

Summarizing, if a regular graph contains a clique on more than half the vertices then it is the complete graph. Therefore the clique number of a regular graph is either at most $\lfloor n/2 \rfloor$ or $n$.

Let us now show that the upper bound $\lfloor n/2 \rfloor$ is tight. That is, for every $n$ there exists a regular graph on $n$ vertices whose clique number is $\lfloor n/2 \rfloor$.

When $n$ is even, there exist regular graphs on $n$ vertices with clique number $n/2$, for example two disjoint copies of $K_{n/2}$.

When $n=4m+1$, there exist regular graphs on $n$ vertices with clique number $2m$: take two disjoint copies of $K_{2m}$, add a new vertex connected to $m$ vertices from each copy of $K_{2m}$, and add a matching between the remaining $m$ vertices of each copy of $K_{2m}$. When $m=1$, this gives the 5-cycle.

When $n=4m+3$, the following construction gives a regular graph on $n$ vertices with clique number $2m+1$. Take two disjoint copies of $K_{2m+1}$, say on vertices $x_1,\ldots,x_{2m+1}$ and $y_1,\ldots,y_{2m+1}$. Connect $x_i$ to $y_i$ for all $i$, and connect $x_i$ to $y_{i+1}$ for $i=1,\ldots,m$. Finally, add an additional vertex connected to $x_{m+1},\ldots,x_{2m+1}$ and to $y_1,y_{m+2},\ldots,y_{2m+1}$.


Height of data structures Why the height complexity of a data structure, generally expressed in terms of $\log n$, do not contain a ceiling or floor ?

Asymptotically, $\log n$ and $\lfloor \log n \rfloor$ (or $\lceil \log n \rceil$) are the same: a function is $\Theta(\log n)$ iff it is $\Theta(\lfloor \log n \rfloor)$. Therefore there is no need for floor or ceiling.


What is the difference between "use case" and "function"? In the use case diagram, we draw use cases as an ellipse. Are the use cases the same as functions? I mean by functions, those functions which we write in the program.Thank you in advance.

If by "function" you mean functionality then a single use case may require more than one function to achieve and a single function may serve multiple use cases.

Here's a concrete example:

Use case:

Allow user to withdraw money

Functions:

Check user balance
Prompt user to enter amount and check against balance
Check amount against money in machine
Output money

Depending on how you go about documenting your design you can argue that the 4 functions above can be written as a single function. Though doing this misses the important realization that Check user balance is a function that can be reused in another use case (Allow user to see his balance), even if we reduce them to one function the use case and function would be different ways to say the same thing:

Use case:

Allow user to withdraw money

Function:

Withdraw money

So, at its core level a functionality is an implementation of processes for a use case.

Why do we need two different names? Sometimes it makes it clearer to talk about a requirement and the solution to it. Similar to how in programming we have classes and objects.


Do all the numbers belong to same slot in the Hashtable? I was reading the CLRS. In the Hashing Chapter on page 262 a statement says: "For example, if we know that the
keys are random real numbers $k$ independently and uniformly distributed in the range $0 \leq k < 1$, then the hash function $h(k)= \lfloor km \rfloor$."

Question: Does Uniformly distributed meant all numbers have equal probability.
if so then all numbers have the same $k$ values and belong to the same slot.

Keys are uniformly distributed means that they are drawn from a space with equal probability.

So if we set the hash function to be $h(k)=\lfloor{km}\rfloor$, then each given element is equally likely to hash into any of the $m$ slots. (Refer to the definition of simple uniform hashing in page 259 CLRS)

Yes, it is true that each element with key $k$ will be hashed to the same slot. But the point is the elements are chosen uniformly independently, so they have the same probability to hash to any of the $m$ slots.


Existence of Optimal Policy for infinite-state MDPs It is well-know from Puterman's book (1994) that in any finite-state MDP, if there exists an optimal policy, then that policy is stationary and deterministic. How about MDPs with continuous state spaces with finite-action space? Assume that the rewards are bounded.

If the state set is Polish (e.g the set of all real numbers), finiteness of action spaces suffices to conclude that the MDP always has an optimal stationary policy - refer to "Markov Decision Processes" by Puterman for the details.


Proper network address Which of the following are proper network (not host) addresses?

192.168.23.0/24
193.205.16.132/26
172.16.4.0/20
10.57.13.64/28

How can I tell? What is a proper network address?

Is a proper network address when the IP address is the same as the network address? For example in the first one that is the case.

I think proper here just means that the IP address in CIDR notation is the first address in the range specified by the IP address and its prefix.

This is the case for 192.168.23.0/24 and 10.57.13.64/28 and not the case for 193.205.16.132/26 (whose first address in the network range is 193.205.16.128) and 172.16.4.0/20 (whose first address is 172.16.0.0).


Composition of compostion as a functor "Composition of Composition" (i.e., (.) . (.)) in Haskell), has type (a -> b) -> (c -> d -> a) -> c -> d -> b. Apparently, this is an instance of fmap, i.e. a functor between two categories.

The question is: what is the domain and the codomain of this functor? How do we interpret this functor in terms of functional programming?

Consider

(.) :: (a -> b) -> (d -> a) -> d -> b

is the fmap for functor $F_d\colon \mathfrak{C} \rightarrow d/\mathfrak{C}$ from category of types $\mathfrak{C}$ to its coslice category $d/\mathfrak{C}$ on object $d$.  Similarly,

(.) :: ((d -> a) -> d -> b) -> (c -> d -> a) -> c -> d -> b

is considered the fmap for functor $G_c\colon d/\mathfrak{C} \rightarrow c/\big(d/\mathfrak{C}\big)$.

These two functor can be composed to get $G_c \circ F_d\colon \mathfrak{C} \rightarrow c/\big(d/\mathfrak{C}\big)$. Like all compositions of two functors, the fmap of the composed functor is the composition of fmap its two functor operands. In this case, the fmap of $G_c \circ F_d$ is

(.) . (.) :: (a -> b) -> (c -> d -> a) -> c -> d -> b

as in the opening question.


Using Limits to Determine Asymptotic Relationship Let's say we have $3^{4n}$ and $4^{3n}$. With the note of  The Asymptotic Cheat Sheet from MIT.
We should first calculate the lim n->infinity   $3^{4n}$/$4^{3n}$. and it result is $\infty$.
In the we have
lim n→∞ f(n)/g(n) != 0,∞  ⇒  f=Θ(g)   Note 1

and
lim n→∞  f(n)/g(n)=∞     ⇒ f=ω(g)   Note 2

My questions is:
Given that f(n) is $3^{4n}$ and g(n) is  $4^{3n}$ in this case, which "case" should we apply ?
How should one read Note 1 correctly ? Does it mean  "lim n→∞ f(n)/g(n) not equal to 0, but equal to infinity? then f=Θ(g) " Or
"lim n→∞ f(n)/g(n) not equal to 0 and not equal to infinity, then f=Θ(g)?
Also if f(n) = $\theta $ g(n)? doesn't that already mean f(n) = $O$ g(n)?
if so, then note 1 should read as
"lim n→∞ f(n)/g(n) not equal to 0 and not equal to infinity, then f=Θ(g)?

Knowing $3^4=81$ and $4^3=64$, we have $f(n)=81^n$ and $g(n)=64^n$. Using this we obtain:
$$\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}=\lim\limits_{n \to \infty}\left(\frac{81}{64}\right)^n=+\infty$$
so you have your "Note 2". By definition last limit mean $\forall C>0$ we have  $\exists N \in \mathbb{N}$, such that $\forall n>N$ holds $\frac{f(n)}{g(n)} \geqslant C$ so we have $f\in \Omega(g)$.
For further let's assume, that we have positive functions and $g$ have not $0$s subsequence.
Following question. Your "note 1" means that $\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}$ is not $0$ and is not $\infty$, but equals to some number between them.
And last. Suppose $\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}=A>0$. This means, that $A-\varepsilon<\frac{f(n)}{g(n)} < A+\varepsilon$, for appropriate $n$, and so we can conclude $f \in \Theta(g)$.


Why is the halting problem semi-decidable? This is what is known about the halting problem and semi-decidability :-

The halting problem says that for a given input x and a machine H, we can't say whether the machine H halts or not on input x.

A language is said to be Semi-decidable if there exists a Turing machine which halts if a word belongs to the language (YES cases) and may reject or go into infinite loop if the word doesn't belong to the language (NO case).

Now, in the halting problem we can't say whether the machine will halt even if the input belongs to the language (YES cases). Then how is it Semi-decidable? I think it should be non-recursively enumerable or undecidable.

Tl;dr: "(say) whether or not it halts" and "(say) if it halts" are not the same thing. Use mathematics to avoid confusion induced by language ambiguity.

  Halting problem says that for a given input x and a machine H, we can't say whether the machine H halts or not on input x.

No, that's not what it says. The halting problem is the computational problem of deciding whether $H$ halts on $x$, given $x$ and $H$ as input. It is important to note that "decide" here means "say yes if it is so, and say no if it is not".

The undecidability of the halting problem states that there is no single algorithm (Turing machine) that solves the halting problem for all $H$ and $x$.

  Now, in halting problem we can't say whether the machine will halt even if the input belongs to the language (YES cases). Then how is it Semi-decidable?

After the above clarification, your confusion here should be clear. It doesn't matter what "we can say". The "semi halting problem" is relaxed: the algorithm still has to say "yes" if $H$ halts on $x$, but it can do whatever it please if it does not (except answer "yes").

This is trivial to implement: just run $H$ on $x$. If it halts, answer "yes". If not, it doesn't matter since we're allowed to loop.


How to prove that { : M1 and M2 are two DFAs and L(M1) $\neq$ L(M2)} is in NL? My idea is to find a turing machine which recognizes this language in $\log N$ space, could anyone give me some clue on how to find such turing machine?

Yuval's answer describes the main component. For the sake of completeness I'll precise a couple of details.
First, $L(M_1) \neq L(M_2)$ means that there is a string that is accepted by one of the automaton but not the other. Let's "build" an automaton $M$ that accepts precisely such strings, and we will then want to check whether it accepts a least one string. Then $M$ has states $(q^1_i, q^2_j)$ for each state $q_i$ of $M_1$ and $q_j$ of $M_2$. A state $(q^1_i, q^2_j)$ of $M$ is accepting if and only if $q_i$ is accepting in $M_1$ and $q_j$ is not accepting in $M_2$ or vice versa. Now, in order to tell if $M$ accepts a string, we need to know if there's an accepting node that is reachable from $(q^1_0, q^2_0)$. We can first guess such a state $(q^1_m, q^2_n)$ as its representation uses only a logarithmic number of bits. Then we can, one step at a time, guess a path of states from $(q^1_0, q^2_0)$ leading to $(q^1_m, q^2_n)$. Of course after each guess we need to actually verify that there is an edge in $M$ from the previous state to the recently guessed one. In order to do that we can always keep two states in memory, the current one and the state we just guessed as the next one, this uses logarithmic memory still.


What is the difference in SMO algorithm for SVM and SMO for one class? Please let know if this is not the correct forum to ask this question. If not can anyone please tell where can I ask this question?

I am trying to understand the difference between the paper :
https://pdfs.semanticscholar.org/59ee/e096b49d66f39891eb88a6c84cc89acba12d.pdf

and the paper http://users.cecs.anu.edu.au/~williams/papers/P132.pdf

The first paper is about SMO for SVM and the second paper is about SMO for one class. The question is what are the difference between this two algorithms? Also what are the common factors in both the paper?

The second paper has not shown any details of the algorithm so not sure what minimal change to be done on the first to get the second algorithm?

Given the code for the SMO for SVM, what minimum change would require to make the code suitable for one class SMO?

Both the papers attempt to develop Sequential Minimization Optimization (SMO) approaches for two kinds of Support Vector Machine (SVM) formulations, which include the conventional SVM and one-class SVM. The basic idea behind the SMO approach is to make the underlying SVM formulation scalable for larger datasets. This is a challenge since the SVM is a kernel method, and using it for large datasets requires computation of the kernel matrix whose size is of the order of the number of training samples. Thus, there is a high memory and computational requirement, moreover, issues pertaining to matrix stability may arise. In order to address this issue, the SMO approach adopts a method where pair-wise Lagrange multipliers are optimized instead of solving the entire Quadratic Programming Problem (QPP) as in the conventional case. The selection of the Lagrange multipliers may be based on heuristics. This (SMO) makes the approach (SVM) scalable for larger datasets, which is the underlying similarity between the use of SMO for SVM and one-class SVM.

In order to understand the difference between the two, it is important to understand the difference between the purpose of the SVM and one-class SVM, and subsequently the difference in their formulations (the optimization problem for each). This eventually translates into the difference in applying the SMO strategy for each of these cases.

The conventional SVM for binary classification aims to find a separating hyperplane $w^Tx+b=0$ with coefficients $w$ and bias $b$ for training data $x$ (and class labels $y$) with maximum margin ($\frac{1}{\|w\|_2}$) which is at least unit distance from points of the two classes which lie close to the separating hyperplane. This is achieved by the soft-margin formulation involving trade-off using positively constrained slack variables $\xi$ and user-defined parameter $C$ as below:

$\min_{w,b,\xi} \frac{1}{2}  \|w\|_2^2 + C \sum_i \xi_i$

subject to

$y^i (w^T x^i + b) + \xi_i\geq 1$,
$\xi_i \geq 0$

In  practice, the kernel trick is used to map the data to a high-dimensional kernel space $K$ that induces linear separability and the dual of the above formulation in terms of the Lagrange multipliers $\alpha$ is solved, which is given as

$\min_{\alpha} \frac{1}{2} \sum_i \sum_j y^i y^j K(x^i,x^j) \alpha_i \alpha_j - \sum_i \alpha_i$

subject to

$\sum_i \alpha_i y^i = 0, \alpha_i \geq 0$

On the other hand, in case of the one-class SVM, we would like to determine whether the test sample belongs to a specific class, determined by the training data (having $M$ samples), or not. Consequently, the one-class SVM is solved by

$\min_{w,b,\xi} \frac{1}{2} \|w\|_2^2 + \frac{1}{C M} \sum_i \xi_i - b$

subject to

$w^T x^i \geq (b - \xi_i)$,
$\xi_i \geq 0$

The dual for the one-class SVM is then given as

$\min_{\alpha} \frac{1}{2} \sum_i \sum_j  K(x^i,x^j) \alpha_i \alpha_j$

subject to

$0 \leq \alpha_i \leq \frac{1}{CM}, \sum_i \alpha_i = 1$

The derivation of the SMO algorithm follows the steps presented in the two papers, and the difference arises out of the nature of the two SVM formulations and their corresponding dual problems. Details of the derivation may be found in the respective papers, and newer strategies for selection of the Lagrange multipliers for optimization may also be found in literature.


What's the difference between the rank and the degree of a type function? 1 Context

Near pg. 184 of Lambda Calculus and Combinators, the author is discussing the theory of dependent types. In particular, we are extending the lambda calculus to look at terms of form

$$
\Pi x : \sigma . \tau (x)
$$

Now terms of this form denote type functions with degree and ranks, unless I am mistaken.

2 Textbook Passage on Degrees vs. Ranks

Here is what the textbook states:

  The definition assumes that we are given a set (possibly infinite) of
  atomic type constants, $\theta^n_i$, each with a degree $n$. Each atomic type constant with degree $n$ will represent a type function
  intended to take $n$ arguments, the value of which is a type.

and then later:

  Definition 13.7 (Type functions and types) Type functions of given degrees and ranks are defined in terms of proper type
  functions, which are defined as follows.

  An atomic type constant of degree $n$ is an atomic proper type
  function of degree $n$ and rank $0$.
  If $\sigma$ is a proper type function of degree $m > 0$ and rank
  $k$ and $M$ is any term, then $\sigma M$ is a proper type function of
  degree $m - 1$ and rank $k$.
  If $\sigma$ is a proper type function of degree $m$ and rank $k$,
  then $\lambda x . \sigma$ is a proper type function of degree $m+1$
  and rank $k$.
  If $\sigma$ and $\tau$ are proper type functions of degree $0$ and
  ranks $k$ and $l$ respectively, and if $x \notin FV(\sigma)$, then
  $(\Pi x : \sigma . \tau)$ is a proper type function of degree $0$ and
  rank $1 + k + l$.

  A type function of degree $m$ represents a function of $m$ arguments
  which accepts types as inputs and produces types as outputs. THe rank
  of a type function measures the number of occurrences of $\Pi$ in the
  normal form of the term representing it.

3 Question

Question: I am totally confused between the notion of a type function's degree versus its rank.

The book states that the rank of a term is the number of $\Pi$'s in its (normal) form. But doesn't the number of such $\Pi$'s correspond exactly to the number of arguments it takes? That is, if a type function takes $n$ arguments, then doesn't that just mean there must be $n$ $\Pi$ symbols to capture those $n$ arguments?

The book states that the rank of a term is the number of $\Pi$'s in its (normal) form. But doesn't the number of such $\Pi$'s correspond exactly to the number of arguments it takes? That is, if a type function takes $n$ arguments, then doesn't that just mean there must be $n$ $\Pi$ symbols to capture those $n$ arguments?

Nope. Let $\sigma, \tau$ be types (i.e., type functions with degree=rank=$0$). The type
$$
\prod_{x:\sigma} \tau
$$
is the type of functions $\sigma \to \tau$, which do not take type arguments -- they take value arguments (of type $\sigma$). So, the degree is $0$ (not $1$), while the rank is $1$.


Application of Brent's Cycle Detection Algorithm I would like to find cycles in a finite length list of numbers where there is no function:

xn = f(xn-1).

For example, in the list:

3, 12, 11, 46, 1034, 23, 12, 11, 46, 1034, 5

x0 = 3, x1 = 12, etc. and the cycle starts at x1 with a length of 4.

There is a Java implementation of Brent's Cycle Algorithm here which includes some sample data with the expected output.

Brent Cycle Algorithm Test

Enter size of list
9

Enter f(x)
6 6 0 1 4 3 3 4 2

Enter x0
8

First 9 elements in sequence :
8 2 0 6 3 1 6 3 1 6

Length of cycle : 3
Position : 4

Here you can see that x0 = 8 and that the 8th entry in the entered list is 2 (using a zero based index), which when used as an index gives 0, which when used as an index gives 6 and so on producing the first 9 elements in the sequence 8, 2, 0, 6, etc.

My problem (likely due to my lack of understanding about the purpose or use of Brent's Algorithm) is that the numbers in the list I provided (3, 12, 11, 46, etc.) cannot be used as indexes (indicies?) to access the next number in the list.  In other words, there is no f(x) such that xn = f(xn-1).

Does this put Brent's Algorithm out of reach for my application?  Maybe there's a simple modification to Brent's Algorithm that hasn't occurred to me.

If the numbers in the list are stored in memory as a list, you can just use a hashtable to look for duplicates, or you can sort them and then look for duplicates.

Brent's algorithm is primarily useful in situations where you don't want to store all of the numbers in memory, because the memory cost would be too high -- but that doesn't apply if you have a list with the numbers, because then you're already committed to storing all the numbers in memory.


Is this a standard representation of a 'space' character? I recently came across a handwritten note with directions to push a string of text into a database. There was a strange character in the string I've never seen before, a lower case 'b' with a forward slash through it:

I asked the author about it and he said it was an old-school way of representing a space.

My question is whether or not this was a standard/widely used representation of a space character and if so, whether or not it's still commonly used.

The symbol ␢ has a unicode representation: 2422-unicode-blank-symbol.

It is an old typographic symbol for specifying explicit blanks in code.
As Wikipedia states:

  This was used in the early years of computer programming when writing
  on coding forms. Keypunch operators immediately recognized the symbol
  as an 'explicit space'.

ps. I also learned this symbol as Turing tape blank. I will check an old book later. Nowadays I would use B or if I am feeling adventurous ␣ 'open box' (U+2423) $\text{\textvisiblespace}$.


Longest Even-Length Palindromic Subsequence (with distinct adjacent characters except for the center 2 letters) You are given a string S containing lowercase English characters. You need to find the length of the largest subsequence of S that satisfies the following pattern:
X1,X2,X3...Xn,Xn,...X3,X2,X1
where Xi is some character of S. The only constraint is that no adjacent character should be the same except Xn, that is Xi != X(i+1) for all 1<=i<
n.

Input: The string: S
Output: The integer: 2n
Constraint: 1<=|S|<=10^3

Sample input 1: "acdbdea"
Sample output 1: 4
Explanation: "adda" is the longest subsequence following the given pattern.

Sample input 2: "abbacdeedc"
Sample output 2: 6
Explanation: "cdeedc" is the longest subsequence following the given pattern.

Sample input 3: "taker"
Sample output 3: 0
Explanation: No subsequence follows the given pattern.

This question was asked in a coding interview and I didn't know how to solve it. I understood how to find the longest palindromic subsequence but don't know how to implement the distinct adjacent character part. Please help. Pseudocode is fine.

Golden Rule
Here is the golden rule of dynamic programming.
When solutions to smaller subproblems cannot be combined into solutions to larger subproblems because of missing information, extend the subproblems by adding parameters that give that missing information.

First attempt
$S$ is a sequence of $n$ letters or, $S[0:n].$
Let $L[i][j]$ be the length of the longest palindromic subsequence of $S[i:j]$. It is easy to figure out the base cases and, by increasing $i$  and/or decreasing $j$, the recurrence relations for $L[i][j]$.

Now add the condition of even length. Let $E[i][j]$ be the length of the longest even-length palindromic subsequence of $S[i:j]$. We can figure out the base cases and the recurrence relations for $E[i][j]$, similar to those of $L[i][j]$.
Now add the condition of distinct adjacent letters, i.e., no letter can appear twice in a row except the letter at the center. Let $D[i][j]$ be the length of the longest even-length distinct-adjacent-letter palindromic subsequence of $S[i:j]$. As you might have noted, we cannot figure out the recurrence relations for $D[i][j]$, since extending such a subsequence to a longer one might introduce repeated letters.
The golden rule comes to rescue. Add another parameter that classifies the letter at the end of the longest subsequence found so far, so that we can determine how to extend that subsequence properly.
Let $D[i][j][\lambda]$ be the length of the longest even-length distinct-adjacent-letter palindromic subsequence of $S[i:j]$ that ends in letter $\lambda$. That is, we will compute $D[i][j][\text{'}a\text{'}]$, $D[i][j][\text{'}b\text{'}]$, $D[i][j][\text{'}c\text{'}]$, $\cdots$, $D[i][j][\text{'}z\text{'}]$.

The final answer is the larger of $\max_\lambda D[0][n-1][\lambda]$ and $0$.

Suppose the first $\text{'}a\text{'}$ in $S$ at or after $S[i]$ appears at $S[\vec {i_{\text{'}a\text{'}}}]$. Suppose the first $\text{'}a\text{'}$ in $S$ appears at $S[\overleftarrow{j_{\text{'}a\text{'}}}]$ before $S[j]$ searched backwards. $\vec {i_{\text{'}a\text{'}}}$ or $\overleftarrow{j_{\text{'}a\text{'}}}$ is set to $-1$ if $\text{'}a\text{'}$ is not found respectively. We have, for $j\ge i+2$,
$$D[i][j][\text{'}a\text{'}] =  \begin{cases}
\max(2, 2 + \max_{\mu\not=\text{'}a\text{'}}D[\vec {i_{\text{'}a\text{'}}}+1][\overleftarrow{j_{\text{'}a\text{'}}}][\mu])& \text{ if } 0\le \vec{i_{\text{'}a\text{'}}}  \lt \overleftarrow{j_{\text{'}a\text{'}}},\\
 -1 &  \text{ otherwise,}\\
\end{cases} $$
where $\mu$ runs through all lowercase English letters.

The base case is $$D[i][i][\text{'}a\text{'}] = 0.$$

Generalizing $\text{'}a\text{'}$ to variable $\lambda$, we can write the recurrence relation and base case for $D[i][j][\lambda]$.
Note that with the extra information embodied in the $\lambda$ parameter, it is easy to deduce the recurrence relation.
While this attempt is successful, we can do better.

Second attempt
We can simplify the subproblems.
Let $F[i][j]$ be the length of the longest such subsequence that starts at $S[i]$ and ends at $S[j]$. Then we have
$$F[i][j] =  \begin{cases}
\max(2, 2 + \max_{\mu\not=S[i]}F[\vec{i_\mu}][\overleftarrow{j_\mu}])&\text{ if } S[i] = S[j],\\
 -1 & \text{ otherwise,}\\
\end{cases} $$
where $-1$ stands for "Not Found". For all lowercase English letter $\mu$, $S[\vec{i_\mu}]$ is the first $\mu$ that appears after $S[i]$, and $S[\overleftarrow{j_\mu}]$ is the first $\mu$ that appears before $S[j]$ searched backwards.  If one of them cannot be found, the term $F[\vec {i_\mu}][\overleftarrow{j_\mu}]$ is ignored.
The final answer is the larger of $\max_{i, j} F[i][j]$ and 0.


Find all disconnected directed (cyclic) subgraphs and transform them into stars I have a graph $G=(V,E)$ that consists of many disconnected directed subgraphs, some of them may be cyclic. (Basically a "forest" consisting of directed trees and some directed disconnected cyclic graphs added into it).

I want to find all of these disconnected subgraphs and turn them into stars given by the key of the node.

I've built a directed graph (using Python's networkx library) and now I am kinda stuck how to find those disconnected subgraphs, because some of those subgraphs will have source and some of those wont.

How to proceed? Thanks!

Probably you want to compute weakly connected components, a subgraph having a path between every two vertices in the underlying undirected graph. Computing the weakly connected components is easy: first transform the directed graph into undirected by removing "directions" of each edge and run DFS/BFS on that graph (by looping on vertices!). Alternatively, if you're interested in the strongly connected components then you should run one of the algorithms computing SCCs. This gives you components $C_1, \dots, C_n$.

Then you can do whatever you want to do on these components.


how does rotation works in AVL trees and what is a good way to understand it? If we consider this tree with T1 and T2 as subtrees, and we want to rotate on x (rotating the edge between T1 and x), what is the result? how does it work then? Does the x stay in its place and T1 switch with T2? I saw multiple examples online but they had too many nodes and i couldn't really understand the concept of rotating and that's why i chose this simple example so that i (hopefully) can apply it in all other situations.

One needs three subtrees to describe rotation, as the operation reconnects the three subtrees of a pair of nodes, one the child of the other.

The operation can be seen as a associative property: $T_1\;p\; (T_2\; q\; T_3) = (T_1\; p\; T_2)\; q\; T_3$ of the inorder traversal of the nodes in a binary tree.

Both the left and right diagram have the inorder $\mathrm{in}(T_1)\; p\; \mathrm{in}(T_2) \; q\; \mathrm{in}(T_3)$, where $\mathrm{in}(T)$ is the inorder of subtree $T$.

It is pretty well explained at wikipedia Tree rotation, even with animated pictures.


Why are regular expression quantifiers greedy by default? I can't count the number of times I've seen questions on StackOverflow related to regular expressions where the problem was due to the programmer not understanding the impact of greedy quantifiers. Most recently, Python regex issue — [\S\s]* vs \d*.

I wonder why regular expression quantifiers were defined to be greedy. It seems like this is less intuitive than non-greedy regular expressions. If someone writes a regexp like

BEGIN(.*)END

they intuitively expect the capture group to grab everything between adjacent BEGIN and END brackets. But if there are multiple BEGIN...END pairs, it will span all of them. You have to write

BEGIN(.*?)END

to express this. And I think non-greedy quantifiers like this didn't even exist until PCRE -- matching this was even more complicated then.

Non-greedy quantifiers are not a magic bullet solution for all such problems, but it seems like there would be fewer problems if they were the default.

EDIT:

I think I see a possible reason. If there's nothing after the quantifier, you usually want it to be greedy. My original answer to the above question had a bug, the regexp ended with Answer:\s*(.*?). By making this non-greedy, the last capture group matched an empty string rather than everything after the final Answer: prefix.

And also consider the \* there -- we want that to capture all the whitespace after the prefix, before grabbing the text in the capture group.

So the appropriate default really depends on what (if anything) is after the quantifier. And greediness is also often only an issue with .*, not if you quantify something more specific than ..

Is this all there is to it?

A regular expression, as the term is used here, is a mathematical construct; it is the formalism used to define regular languages. In that context, the Kleene star operator is neither greedy nor abstemious. Rather, it is non-deterministic: it will match as many times as necessary.

It's worth pointing out here that regular expressions define a "language", not a substring. In that sense, the regular expression matches (or recognises) the entirety of a sentence.

Using regexes to find substrings was a (very useful) adaptation of a theoretical concept to practical programming problems. But it introduces an ambiguity which was not present in the original: if the regex can match more than one different substring, which one should it choose?

The original regex libraries all chose the first matching substring (in a left-to-right scan), and of those matches which all start at the same position, they chose the longest one. These are the Posix semantics for regular expressions, which also define how subpatterns ("captures" between parentheses) correspond to substrings of the matched string. ("Captures" form no useful part of the theoretical model of regular expressions.)

The regular expression formalism has the enormous advantage that it can be compiled into a Deterministic Finite Automaton (DFA) which can then be used to perform a match -- or even a substring search -- in linear time. In effect, the DFA recognizes all possible matches in parallel; it is easy to make it recognize the longest match, by simply continuing until no further advance is possible. It would also be easy possible to recognize the shortest match, although that is not as common as you might think. (Consider, for example, recognizing numeric or identifier-like tokens: you really want to match the longest possible string.)

However, implementing abstemious repetition is not the same as implementing shortest match. Rather, it requires ordering possible matches by examining a subcomponent of the match. Since regular expressions do not need to be deterministic in submatches (and usually are not), ordering by subcomponent is non-trivial; it requires significant extra memory and time because many alternative partial matches may need to be remembered during the scan.

Once you have substring matches, possibly with captured submatches, you need to start worrying about resolving these ambiguities. And the Posix semantics are not always what are desired. Sometimes -- often, even -- one would want to find the shortest matching substring. (As in the BEGIN.*?END example you mention.)

Consequently, many regex libraries do not use this algorithm, preferring a backtracking recursive solution. One of the advantages of the backtracking algorithm is that it can cope with a number of extended regex operators which cannot be implemented with a DFA, including back-references which are not even context-free (in general). On the flipside, these operators can introduce pathological slow-down, and it is relatively easy to craft regexes which take exponential time to do a search. If you allow user-supplied ("tainted") regexes, this is a vector for DoS attacks. Even if you don't allow tainted regexes, you sometimes have to think carefully about how to write a given regex in order to produce as efficient a search as possible.

Over the years, regexes have drifted further and further away from their theoretical regular language roots. However, there are still contexts in which the original formulation and its guaranteed linear time complexity are useful:

Lexical scanners, in which the regular expressions are not dynamic and therefore are usually compiled into the scanner. Since simple regular expressions are perfectly adequate for tokenising most programming languages, the efficient linear-time algorithm is preferred.
As mentioned, tainted regular expressions, such as on-line search engines. See, for example, Russ Cox's re2 library, based on a (re-)discovery of the linear-time algorithm, which he wrote in order to protect the Google Code search engine from potential denial of service attacks.


Priority queue of constant size fit for extraction of K highest priority elements In an algorithm I'm designing, I need to do this cycle on a priority queue of constant size N many times, as quickly as possible:

get $K$ highest priority elements (do on them some outside calculation)
append $4K$ kind-of-sorted elements back into the priority queue, removing and ignoring the first $K$ elements from step 1
remove the $3K$ lowest priority elements (in order to keep constant queue size), and return them

In reality, steps 2-3 will probably be merged somehow and so on, but these are the main implementation details.

I'm looking for the fastest implementation of these actions on a priority queue, for a relatively large $N$ and relatively small $K$ (E.G $K=32$, $N=2048$), that can be tweaked a little if needed (E.G change $N\rightarrow 2500$ if it's faster).

I'm not so familiar with data structures, but here's an assortment of things that might work:

a sorted array, using $O(1)$ extracts and $O(N)$ merges
a pairing heap? weird extract times, but $O(1)$ merges
a more exotic heap type? I've found this question for example, with priority queues that technically are quicker at extracts

If that's practical question, sorted array may be faster than other approaches. The only O(N) operation you will do is memcpy in L1 cache whose speed using AVX2 is 32 bytes per CPU cycle, i.e. ~100 GB/sec.

You will need 2 arrays to make merge. But then you can use spare space for other computations. More complex data structure may easily run out of L1 cache size.


How could I prove that $B$ reduces to $A$ in polynomial time in this case? Let $A$ be a decision problem with at least one yes instance and at least one no instance. Also let $B \in \textbf{P}$. How could I prove that B reduces to A in polynomial time?

Thanks in advance.

Take $a\in A$ and  $b \notin A$.

the reduction defined as follows:
$$f(x)=\begin{cases}
a & x\in B\\
b & x\notin B
\end{cases}$$

It is easy to see that $f \in \text{POLY}$ since $B\in\text{P}$, and the correctness is trivial.


Results on the languages recognized by undirected DFAs For my Bachelor's thesis, I consider the class of languages recognized by symmetrical DFAs, that is, deterministic (complete) finite automata satisfying the following condition:

Let $A$ be a complete DFA over the alphabet $\Sigma$. If, for every $a\in \Sigma$ and every transition $u \stackrel{a}{\longrightarrow}v$ in $A$, there is a transition $v \stackrel{a}{\longrightarrow}u$ in $A$, we call $A$ a symmetrical DFA (SDFA). If $A$ is not complete, we call it a partial SDFA. We can regard an SDFA as an undirected, labeled graph in a natural way.

I could find an algebraic characterization of the class of languages recognized by (complete as well as partial) SDFAs and deduce some closure properties. However, neither me nor my supervisor are aware of previous results concerning this particular class of regular languages (barring results like Reingold's $\mathsf{SL = L}$ which might seem related).

Motivated by a comment that J.-E. Pin passed on a related question I asked, my question is now:

  Are there results concerning these automata?

I can only give a partial answer. Let $\mathcal{S}$ be the class of all regular languages recognized by a complete SDFA. Then $\mathcal{S}$ is a subclass of the class $\mathcal{G}$ of group languages. A group language is a language  whose syntactic monoid is a finite group , or equivalently, recognized by a finite permutation automaton (each letter induces a permutation on the set of states). The inclusion $\mathcal{S} \subset \mathcal{G}$ is strict. However, the following result holds, showing that $\mathcal{S}$ is a kind of generator for $\mathcal{G}$:

For every group language $L \subseteq A^*$, there is an alphabet $B$, a monoid morphism $f: A^* \to B^*$ and a language $K \subseteq B^*$ in $\mathcal{S}$ such that $L = f^{-1}(K)$.

Proof. Let $\mathcal{A} = (\{1, ..., n\}, A, \cdot, 1, F)$ be a permutation automaton recognizing $L$. It is a well-known fact that the group of all permutations on $\{1, ..., n\}$ is generated by the set $B$ of its transpositions (a transposition permutes two states and fixes all the other states). By construction, the automaton $\mathcal{B} = (\{1, ..., n\}, B, \cdot, 1, F)$ is a SDFA and hence recognizes a language $K$ of $\mathcal{S}$. Now, for each letter $a \in A$, there is a word $u_a \in B^*$ which defines in $\mathcal{B}$ the same permutation as $a$ in $\mathcal{A}$. Let $f: A^* \to B^*$ be the morphism defined by $f(a) = u_a$ for each letter $a \in A$. It should now be clear that $f^{-1}(K) = L$.

The class $\mathcal{PS}$ of languages recognized by a partial SDFA is of course larger than $\mathcal{S}$, but does not exhaust the class of all regular languages. Actually, one can show that if $L$ is in $\mathcal{PS}$, then the syntactic monoid of $L$ is an inverse monoid and in particular, its idempotents commute. This latter property is shared by the slightly larger class of reversible automata. See

J.-É. Pin, On the languages accepted by finite reversible automata, in 14th ICALP, Berlin, (1987), 237-249, LNCS 267, Springer Verlag


In Asyptotic notation if g(n) < f(n) is it possible to have f(n)<=c*g(n) I am studying asymptotic notation and I was thinking of a possibility where if g(n) < f(n) is it possible to have f(n)<=cg(n). For example if -
f(n)=6n+5 and g(n)=4n+5, such that it possible to say (6n+5)<=2(4n+5) where 2 is c. Are f(n) and g(n) here valid function in term of asymptotic notation.

Everything depends on the type of relation you want to define between f and g.

In O and Ω you just have to find one c>0 and one N for which the corresponding inequality between f and g holds and the relation shall be established.

In o and ω you have to show that for every c>0 you can find some N such that the corresponding inequality shall hold for all n > N.

Perhaps this can help you understand it better.


How to calculate the maximum sum over all arrays? Following question was asked in a online hackathon that has been concluded.
Given arrays $A_1,\ldots,A_n$ of length $\ell_1,\ldots,\ell_n$, we want to find cyclically rotate each array in a way which maximizes $$ \sum_{i=1}^{n-1} i|A_i[\ell_i] - A_{i+1}[1]|. $$

For example, on input $2,3,1 \mid 3,2 \mid 4,5$ the best cyclic rotation is $2,3,1 \mid 3,2 \mid 5,4$, and so the answer is $1|1-3| + 2|2-5| = 8$.

There could be up to $10^5$ arrays, and the sum of all elements in all arrays can be at most $10^6$.

I tried solving this by focusing on the two last arrays, but this turned out to be the wrong approach. I am unable to figure out the correct one. How can this be calculated efficiently?

You can solve this using dynamic programming. For each $1 \leq m \leq n$ and $1 \leq t_m \leq \ell_i$, calculate the maximal value of $\sum_{i=1}^{m-1} i|A_i[\ell_i]-A_{i+1}[1]|$ given that $A_m$ is rotated by $t_m$ places. This solution takes time $O(\sum_{i=1}^{n-1} \ell_i \ell_{i+1}) = O(\ell^2/n)$, where $\ell = \sum_{i=1}^n \ell_i$.

We can significantly improve on this algorithm by noticing that the objective function depends on the $i$th array via $\pm (i-1) A_i[1] \pm i A_i[\ell_i]$. This means that the shift we choose must maximize one of the following four quantities:
$$
\begin{align*}
+(i-1)A_i[1] + iA_i[\ell_i], \;+(i-1)A_i[1] - iA_i[\ell_i], \\-(i-1)A_i[1] + iA_i[\ell_i], \;-(i-1)A_i[1] - iA_i[\ell_i].
\end{align*}
$$
This means that there are at most four values of $t_m$ that we need to consider (and at most two for $m \in \{1,n\}$). We can find these value in $O(\sum_{i=1}^{n-1} \ell_i) = O(\ell)$, and the dynamic programming part now takes only $O(n)$. In total, we obtain an $O(\ell)$ algorithm, that is, a linear time algorithm, which is asymptotically optimal.


Does UDP always deliver packets inorder to the application layer I was reading about UDP and TCP. TCP is a stream-oriented, connection-oriented protocol and always delivers the segments in order to the application layer.

But UDP being connectionless, does it also always deliver the datagrams to the application layer in order?

Conversely from TCP, UDP does not guarantee a reliable or ordered delivery of the packets.
As the RFC states:

  This protocol  provides  a procedure  for application  programs  to send
  messages  to other programs  with a minimum  of protocol mechanism.  The
  protocol  is transaction oriented, and delivery and duplicate protection
  are not guaranteed.  Applications requiring ordered reliable delivery of
  streams of data should use the Transmission Control Protocol (TCP)

Indeed, if you look at the UDP header there is nothing such as Sequence Number or Acknowledgment Number.

             0       7 8     15 16    23 24      31
             +--------+--------+--------+--------+
             |     Source      |   Destination   |
             |      Port       |      Port       |
             +--------+--------+--------+--------+
             |                 |                 |
             |     Length      |    Checksum     |
             +--------+--------+--------+--------+

Note also that using UDP does not mean that an ordered delivery of packets to the application layer cannot be achieved.
Indeed, UDP can be used in conjunction with an upper layer protocol that adds additional information, such as the sequence number.
See, e.g., RTP which is a Session layer protocol (OSI model) or Application layer (TCP/IP model).