How does size of a number in an array affect time complexity algorithm analysis? This question stems from this question and this answer. I also want to preface this question by stating that this question is done from the perspective of a RAM (or PRAM if it's more accurate term) model.

From the comments in the answer, it seems like when doing algorithm analysis for the solution:

  $O(n)$ solution (guaranteed): sum up the elements of the first array. Then, sum up the elements of the second array. Finally, perform the substraction.

for the problem of:

  finding the number that is different between two arrays (I'm assuming
  a fixed size structure, if it matters) of unsorted numbers (paraphrased by me)

that it isn't as black and white as just coming to the conclusion as $2n$ (1 pass for each array), because you have to take into account the size of the number too. That is the part I am confused about. I've asked one of the commenters to elaborate a bit more for me:

  My idea is that while the time to add two numbers is proportional to their length, but there are $O(\log n)$ extra bits that the partial sums have over the longest input. Now, there are two things that complicate things. First, the inputs need not have the same length, but we'd like complexity in terms of their total length. If your addition is proportional to the longer number, you might rack up $O(n^2)$ quite easily. The solution is to add in place, which means the addition is proportional to the addend length - if not for carry. Now you just need to find how many carries you can have.

Despite this pretty detailed comment, I'm still having difficulty understanding why it's different. (I suspect the reason is due to my ignorance of the lower level ongoings of a computer and numerical representations). Not wanting to test their patience, I googled it and asked here, but unable to properly articulate the question, the most I found was this answer, which seems to echo the quote above (I think), thus didn't help me further.

Is it possible to simplify the explanation by perhaps illustrating it or elaborating further? Or is this as simple as it can get (and I just need to get the prerequisite knowledge)?

Actually, you can avoid any higher precision calculations.

Assume you are adding n k-bit numbers in one array, and adding n+1 k-bit numbers in the other array. The difference is a k-bit number (the one extra number that was added to the other array).

So you can perform the addition, and just ignore anything beyond k bits. Instead of getting the sum, you get the sum modulo $2^k$, but that is enough to get the correct result.


Understanding Wirth's symbol table entry N.Wirth's book on compiler introduces the concept of symbol table and states that
every declaration statement results in a new entry in symbol table.

Then after showing how an entry in symbol table looks like he talks about types which can be specified anonymously like the following :

$\ VAR a: ARRAY 10  OF INTEGER $

Then it is written that  named types are represented in the symbol table entry by an entry of type object -----(1)

which in turn refers to an  object of type "Type" and provides the following snippet :

$\ Type = POINTER TO TypDesc;
TypDesc = RECORD
 form, len: INTEGER;
 fields: Object;
 base: Type
END  $

The book is written in pascal or oberon and I don't understand its syntax but
I want to know how to interpret this type desc .

Does whatever follows typedesc , describes the fields of the record ? Form ,length,fields and base being the columns of the record ?

Wirth ,for the following declaration :

TYPE R = RECORD f, g: INTEGER END ;
VAR x: INTEGER;
 a: ARRAY 10 O OF INTEGER;
r, s: R;

shows the following symbol table entry :

The picture , I am getting from this is every object will point to its "type" ,.

In case of records , the type will point to the first field . I guess each field is being implemented something like a C structure ,having the pointer to the next field and pointer to its base type as its member . And here in the diagram ,the attribute "next" is pointing to "g" and its attribute "type" is pointing to "integer" .

The above was just an attempt to interpret what the author exactly means by it . Is my understanding correct ?

Pretty much, yes. The list of variable names form a linked list, and the fields within a record are basically a nested symbol table.


Time complexity of this solution to N-queens problem I'm trying to figure out the time complexity of this implementation of classic N-queens problem on geeksforgeeks. The goal is to find just one such non-attacking solution(as opposed to finding all of them). The relevant code is briefed below.

bool isSafe(int board[N][N], int row, int col)
{
    int i, j;

    /* Check this row on left side */
    for (i = 0; i < col; i++)
        if (board[row][i])
            return false;

    /* Check upper diagonal on left side */
    for (i=row, j=col; i>=0 && j>=0; i--, j--)
        if (board[i][j])
            return false;

    /* Check lower diagonal on left side */
    for (i=row, j=col; j>=0 && i<N; i++, j--)
        if (board[i][j])
            return false;

    return true;
}

/* A recursive utility function to solve N
   Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
    /* base case: If all queens are placed
      then return true */
    if (col >= N)
        return true;

    /* Consider this column and try placing
       this queen in all rows one by one */
    for (int i = 0; i < N; i++)
    {
        /* Check if queen can be placed on
          board[i][col] */
        if ( isSafe(board, i, col) )
        {
            /* Place this queen in board[i][col] */
            board[i][col] = 1;

            /* recur to place rest of the queens */
            if ( solveNQUtil(board, col + 1) )
                return true;

            /* If placing queen in board[i][col]
               doesn't lead to a solution, then
               remove queen from board[i][col] */
            board[i][col] = 0; // BACKTRACK
        }
    }

     /* If queen can not be place in any row in
        this colum col  then return false */
    return false;
}

/* This function solves the N Queen problem using
   Backtracking. It mainly uses solveNQUtil() to
   solve the problem. It returns false if queens
   cannot be placed, otherwise return true and
   prints placement of queens in the form of 1s.
   Please note that there may be more than one
   solutions, this function prints one  of the
   feasible solutions.*/
bool solveNQ()
{
    int board[N][N] = { {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0}
    };

    if ( solveNQUtil(board, 0) == false )
    {
      printf("Solution does not exist");
      return false;
    }

    printSolution(board);
    return true;
}

From what I can tell, the recurrence is T(n) = n*T(n-1) + N*n, which leads to O((n+1)!). When one more recursive call is made, at least one more isSafe() should return false. So the number of recursive calls decreases by at least 1 each time. And for the overhead in isSafe(), since col rows has been filled already, there are at most min(col, N-col+1) iterations of for (i = 0; i < col; i++). But the for loop in solveNQUtil() runs a fixed number of N. That's why N*n exists.

But many people argue that N-queen runs O(n!) with recurrence T(n)= n*(T(n-1) + O(n)), such as here and comment on geeksforgeeks. So I start doubting myself.. surely O((n+1)!) != O(n!).

Could anyone here throw some light on this? Have been struggling with it for a while.

Your analysis would be reasonable for rooks, but not for queens. For example, in the second row there are not n-1 possible positions, but n-2 in two cases and n-3 in most cases. Now big-O provides an upper bound, but it is an upper bound that vastly overestimates the effort needed.


number of permutation with k inversions We are given two numbers N and K.

N <= 10^9.

K<=min{1000,(N*(N-1))/2}

We need to find numbers of permutations of ( 1 to N ) such that inversions are exactly K.

If N was <= 10^3. It would be a simple Dynamic programming question.

https://www.geeksforgeeks.org/number-of-permutation-with-k-inversions/

can we optimize it?

This is only a sketch of solution (there might be some off-by-ones)

Looking at a permutation of $\{1\ldots,n\}$ is equivalent at looking its inversion table $(a_1, \ldots, a_n)$ where $a_i$ is the number of elements to the left of $i$ that are greater than $i$. Basically that gives you a bijection between $S_n$ and $\prod_{1\le i\le n} \{0,\ldots,i-1\}$ and the number of inversions of the permutation is exactly the sum of all $a_i$ corresponding to it (see for example Knuth TAOCP volume 3 for a nice development).

So the problem is equivalent to computing the cardinal of:

$$\{(a_1, \ldots, a_n) \in \prod_{i=1}^{n}\{0,\ldots,i-1\}, \sum_{i=1}^n a_i=k\}$$

This way, we find a DP algorithm with $n\times k$ states:

$$\text{dp}(n,k)=\sum_{i=0}^{\min(k,n-1)}\text{dp}(n-1,k-i)$$

Thus:

When $n$ is small ($n\le k+1$):

$$\text{dp}(n,k)=\sum_{i=0}^{n-1}\text{dp}(n-1,k-i)=\text{dp}(n,k-1)+\text{dp}(n-1,k)$$

So you can compute these in $O(k^2)$. In particular, we will need the following vector of size $k$:

$$\begin{bmatrix}
\text{dp}(k+1,0)\\
\vdots\\
\text{dp}(k+1,k)
\end{bmatrix}$$

When $n$ is large ($n>k+1$):

$$\text{dp}(n,k)=\sum_{i=0}^{k}\text{dp}(n-1,k-i)=\sum_{i=0}^k \text{dp}(n-1,i)$$

In this case $\text{dp}(n,\cdot)$ depends linearly on $\text{dp}(n-1,\cdot)$, the matrix being a $k\times k$ lower triangular matrix with nonzero coefficients being all 1-s. More formally, you can rewrite the previous equality as:

$$\begin{bmatrix}
\text{dp}(n,0)\\
\vdots\\
\text{dp}(n,k)
\end{bmatrix}=
\begin{bmatrix}
1&0&\ldots&\ldots&0\\
1&1&0&\ldots&0\\
\vdots&\vdots&\ddots&\ddots&\vdots\\
1&1&\ldots&1&0\\
1&1&\ldots&1&1
\end{bmatrix}
\begin{bmatrix}
\text{dp}(n-1,0)\\
\vdots\\
\text{dp}(n-1,k)
\end{bmatrix}$$

Just let me note:

$$A=\begin{bmatrix}
1&0&\ldots&\ldots&0\\
1&1&0&\ldots&0\\
\vdots&\vdots&\ddots&\ddots&\vdots\\
1&1&\ldots&1&0\\
1&1&\ldots&1&1
\end{bmatrix}$$

Now if you iterate the relation, you will get for any $i$:

$$\begin{bmatrix}
\text{dp}(n+i,0)\\
\vdots\\
\text{dp}(n+i,k)
\end{bmatrix}=
A^i
\begin{bmatrix}
\text{dp}(n,0)\\
\vdots\\
\text{dp}(n,k)
\end{bmatrix}$$

In particular:

$$\begin{bmatrix}
\text{dp}(n,0)\\
\vdots\\
\text{dp}(n,k)
\end{bmatrix}=
A^{n-k-1}
\begin{bmatrix}
\text{dp}(k+1,0)\\
\vdots\\
\text{dp}(k+1,k)
\end{bmatrix}$$

The vector on the left hand side is what we want ($\text{dp}(n,k)$), the vector on the right hand side is what we computed in the first step (when $n$ is small). So if we can compute the $k\times k$ matrix $A^{n-k-1}$, computing the answer can be done in $O(k^2)$.

Now let's see how fast we can compute $A^{n-k-1}$. I suggest three different ideas (I assume that you want the answer modulo some prime $p$):

1) Matrix exponentiation: if we can multiply $k\times k$ matrices with coefficients in $\mathbb{Z}_p$ in time $O(k^\omega)$), you can use fast exponentiation to have a $O(k^\omega \log n)$ algorithm ($\omega =2.38$ nowadays). Actually, if you are fine with a $O(k^3 \log n)$ algorithm, this should be easy to code (with the naive matrix multiplication algorithm)

2) Polynomial interpolation: if you look at the coefficients of $(A^T)^n$, it looks like:

$$(A^T)^n=\begin{bmatrix}
P_1(n)&P_2(n)&\ldots&P_k(n)\\
0&P_!(n)&\ldots&P_{k-1}(n)\\
\vdots&\ddots&\ddots&\vdots\\
0&\ldots&0&P_1(n)
\end{bmatrix}$$

where $P_1, \ldots, P_k$ are polynomials with integer coefficients and $P_i$ is of degre $i-1$. They satisfy some kind of "generalized Pascal triangle relationship":

$$P_i(n)=1+\sum_{j=0}^{n-1}P_{i-1}(j)$$

So it's possible to compute $P_i(j)$ for $1\le i \le k$ and $0\le j\le k-1$ in $O(k^2)$. We can find coefficients of $P_i$ by doing a Newton interpolation in $O(k \log k)$, so this should give a $O(k^2 \log k)$ algorithm.

3) Find a closed form for $A^i$ with the help of some well-known combinatorial objects. As I said in the comments, the polynomials $P_1, \ldots, P_k$ are close to Faulhaber's polynomials which can be computed in linear time. This might require some heavy handmade computation. I think it should lead to a  $O(k^2)$ algorithm.


Determining a value in an algorithm on its first run I was given the following algorithm as a solution to one of my problems.
However, I am baffled at understanding how c' is ever initialized. The first if statement can never be reached, as c' is never set the first time. Can someone explain this to me? Am I just missing where c' gets set?

This is for Kleinberg and Tardos, Chapter 11, Question 12.

Posting Yuval Filmus's comment as an answer since they didn't:

  It’s a typo - should be $c’=$ instead of $c’-$ in line 5.


Decidability of whether a language described by Turing machine is regular I am trying to prove decidability of problem whether language described by Turing machine is regular. My idea is that I can simulate finite automaton with a subset of Turing machine instructions, namely ones that check for symbol and then move right. If the language is not regular, then simulated FA will eventually come across a string that it cannot process, and give it a FALSE. On the other hand, if the language is regular, FA will successfully accept every string. The problem is that the language has infinite number of strings, and the simulated FA will be checking then forever and never giving affirmative answer. That would make said problem undecidable. Is my reasoning here correct? And if it is, can it be considered a valid proof, or do I need to prove it some other way?

EDIT: The exact wording of the exercise translated as best as I can: You're given a problem of whether language of given Turing machine is regular. Decide whether this problem is decidable and whether is partially decidable. Formally prove your argument.

This language/problem is neither decidable nor partially decidable (r.e). You can use Rice's theorem to prove it. The following proves that the language is not decidable.

"$L$ is regular" is a nontrivial property of recursively enumerable languages since there are regular and non-regular languages which are r.e. For example, $L_1 = \{0^{2n} \mid n > 0\}$ is regular, while $L_2 = \{0^n1^n \mid n > 0\}$ is not regular, but both are r.e. Hence, by Rice's theorem the language $\{\langle M \rangle \mid L(M) \text{ is regular } \}$ is not decidable.

In order to prove that this language is not r.e. you could use Rice's theorem for recursively  enumerable index sets.


How can you compute the expected edit distance in $O(2^{3n/2})$ time? In a coding challenge an answer claimed to be able to compute the expected edit distance between two binary strings of length $n$ in $O(2^{3n/2})$ edit distance calculations by dynamic programming. A naive solution would requite $O(2^{2n})$ edit distance calculations.

The answer gives optimized code but no mathematical or algorithmic explanation.  I cannot see how to achieve the claimed complexity. How is this possible?

Heh…for the record, all I said was that the time seems to scale as approximately $\tilde O(2^{1.5n})$. If this was anything more than a conjecture based on the timing data that I included in the post, I would have said something more specific!

I’m sure you’re familiar with the usual Wagner–Fischer algorithm for Levenshtein distance, where we compute $d_{i,j} = d(a_{[0, i)}, b_{[0, j)})$ based on $a_{i-1}, b_{j-1}, d_{i-1,j-1}, d_{i-1,j}, d_{i,j-1}$.  From there, my algorithm is based on two observations.

Firstly, each column $d_{*,j}$ is a function of the previous column $d_{*,j-1}$, the string $a$, and the bit $b_{j-1}$.  We iterate over all strings $a$ (modulo symmetries), but instead of iterating over all strings $b$, we map each possible column $d_{*,j-1}$ to the two possible columns $d_{*,j}$, storing the collection of possible columns in a hash map with a counter for duplicates.  This allows us to deduplicate some work when many different prefixes $b_{[0, j)}$ lead to the same column $d_{*,j}$.

Secondly, using a separate dynamic programming algorithm, we can precompute an upper bound $w_{i,j}$ on $d(a_{[i, n)}, b_{[j, n)})$ based only on $a$.  Then, given a column $d_{*,j}$, the final distance $d_{n,n}$ can never be more than $m = \min_i (d_{i,j} + w_{i,j})$, so we can replace each $d_{i,j}$ with $\min \{d_{i,j}, m - |i - j|\}$ without affecting the final result.  This lets us recognize more columns as duplicates and deduplicate more work.


Is JavaScript a homoiconic language? I can't help but notice the uncanny resemblence JavaScript has to LISP.  JSON (JavaScript Object Notation), for instance, is a data structure that can be reconstituted into an object by subjecting it to an eval() function. Likewise, LISP data can also be executed as code.

This leads to my question: Is JavaScript Homoiconic or at least partially so? If not, why?

Given your definition, the answer is "no". JavaScript syntax is not a subset of JavaScript's literal syntax. The fact that a value a literal represents can be produced by evaluating the literal is what makes a literal a literal and is true in any language. The only real difference is JavaScript has a richer literal syntax than many common programming languages, though this is certainly not a rare thing.

The answer is "no" for pretty much any reasonable definition that doesn't make practically every language "homoiconic".

My impression is there is not a clear consensus of what "homoiconic" means within the Lisp community. Part of that is it seems many Lispers are confused1 about "homoiconicity"2. I recommend this article which goes over the variety of possible definitions of "homoiconic" and the issues with each. As the title of that article is "Don't Say 'Homoiconic'", this suggests worrying about whether a language is "homoiconic" is not a great idea and you should be more specific about what it is you are care about.

If we use the definition referenced in the article, namely "having the internal and external representations be the same", then this definitely doesn't apply to JavaScript (to the extent that it even makes sense). It arguably doesn't apply to Lisp either, but there are various ways where Lisp gets closer to this. One small indicator is that Lisp's eval takes in Lisp lists while JavaScript's takes in strings. This separation holds for the actual Lisp implementation as well as parsing is viewed as conceptually outside of the implementation and so the implementation conceptually works upon Lisp lists. This has non-trivial consequences like being able to provide circular syntax and an abstract syntax graph in general.

1 Frankly, understandably so as the explanations tend to be vague. There is also, at this point, a lot of misinformation.2

2 There are many definitions floating around that whatever "homoiconic" should mean if anything doesn't mean these things such as "supports higher-order functions".


Find the Simple Cycles in a Directed Graph This problem, for me, looks very interesting. It was about to find a simple cycle (i.e. cycle where are not repeat nodes) in a directed graph.

My solution is going like this, i.e, this graph is a case problem:

I know that there is a cycle in a graph, when you can find "back edges" in a depth-first-search (dashed in my picture in DFSTree), and for a moment I can sure for a few cycles, but not for all, simple cycles. Because, the directed egdes so important to from a cycle, i.e (0123) != (0321)

I'm thinking in make a dfs for each node with back-edges, but I'm not sure, and it's not clear. So, I ask you, if you guide me. Thanks!.

Here is my count of simple loops for my case problem.

This question appears to be very Googleable. For example, you may be interested in the algorithm presented in this paper:

Finding all the elementary circuits of a directed graph. Donald B. Johnson. SIAM J. COMPUT. Vol. 4, No. 1, March 1975

  Abstract. An algorithm is presented which finds all the elementary circuits-of a directed graph in time bounded by O((n + e)(c + 1)) and space bounded by O(n + e), where there are n vertices, e edges and c elementary circuits in the graph. The algorithm resembles algorithms by Tiernan and Tarjan, but is faster because it considers each edge at most twice between any one circuit and the next in the output sequence.

The paper contains a complete algorithm.


Maximum number of states in minimized DFA from NFA with $n$ states If an NFA with $n$ states is converted to an equivalent minimized DFA then what will be the maximum number of states in the DFA? Will it be $2^n$ or $2n$?

The maximum number of states is $2^n$. Conversion from NFA to DFA is done by subset construction and the number of states of the resulting DFA is in the worst case $2^n$. Minimization of the resulting DFA in the worst case might not reduce the number of states.

An example of this is automaton that accepts strings over $\Sigma = \{0, 1\}$ which have $1$ as the $n$th symbol from the end. Of course, $n$ is a concrete number. A NFA has states $q_0...q_n$ and the following transition function:

$$(q_0, 0) \rightarrow \{q_0\} \;\;\;\; (q_0, 1) \rightarrow \{q_0, q_1 \}$$
$$(q_i, 0) \rightarrow \{q_{i+1}\} \;\;\;\; (q_i, 1) \rightarrow \{q_{i+1}\} \;\;\;  1 \leq i \leq n-1$$

Intuitively, the corresponding DFA needs to remember last $n$ symbols since it does not know has it seen the end, which means there are $2^{n}$ states. For more details, I suggest looking into this book. It has a more detailed proof and generally covers these topics in thorough.


A question about the polynomial hierarchy Why does $\Pi_i^p \subseteq \Sigma_i^p$ imply $\Pi_i^p = \Sigma_i^p$?

Hint: $L \in \Sigma_i^p$ iff $\overline{L} \in \Pi_i^p$. (Here $\overline{L}$ is the complement of $L$.)


Triple nested loop complexity I'm trying to determine the complexity of the following structure:

for (i = 1; i < n; i++)

for (j = 1; j < o; j++)

for (k = 1; k < p; k++)

print "Hello world!"

Normally, for a triple loop like this, I believe the complexity is O(n^3), but the undefined variables "o" and "p" are throwing a wrench in the works. I've done
some hunting around, and the best I can surmise is that it might be O(n * o * p), depending on what values are assigned to n, o and p. Thanks for taking a look!

$O(nop)$ is indeed exactly the best upper bound one can conclude for this program without additional information. The bound $O(n^3)$ cannot be shown unless you know $o$ and $p$ are themselves $O(n)$. On the other hand, if you knew $o$ and $p$ were actually constants, then you could prove a bound of $O(n)$ for the entire program.


Recursive and regular languages I'm trying to study for an exam and having difficulty with the following practice questions. Any help would be appreciated.

Give a language $L$ such that $L$ is not recursive but $\text{prefix}(L)$ is regular.
Give two languages $L_1$ and $L_2$, such that $L_1$ and $L_2$ are not recursive, but $L_1\cap L_2$ is recursive.
Give a language $L$ such that $L$ is regular but $\text{unary}(L)$ is not context-free.

Tips.

Any (infinite) unary language has regular prefix language.
$L_1 = a \cdot K$ and similary
$L_2 = b \cdot K$  where $K$ is a well-chosen horrible language.

Question.

What is unary($L$)? If it is what I think, there is an easy example. Powers of two are not context-free: $\{ a^{2^n} \mid n\ge 1\}$.


Special Monotone SAT problem: NP complete? Say we have the set $X=\{ x_1, x_2, \dots \}$ of variables. Then we consider the following problem: Is the formula
$$\bigwedge_{(a,b,c) \in A}(a \vee b \vee c) \wedge \bigwedge_{(a,b,c) \in B}(\neg a \vee \neg b \vee \neg c)$$
for $A,B \subset X^3$ satisfiable.

This problem has been called Montone-3-Sat before and it is known to be NP-complete.

My question is: If we assume that $A=B$ has to hold, is the problem still NP-complete? I.e. we ask if we can color vertices in such a way that always specific three of them do not have the same color.

The results I have found on the internet confuse me a bit, because I believe the definitions of Monotone-Sat, Not-All-Equal-Sat are not always the same.  The definitions of NAE3SAT I've seen allow arbitrary 3-CNF-formulae as input, so this doesn't seem the same as that.

The variant where $A=B$ is known as monotone not-all-equal 3-satisfiability, i.e., Monotone NAE3SAT.  According to Wikipedia, it is NP-complete.  It is not the same problem as Monotone-3-SAT.


Regarding programming languages, what is meant by "hook"? My professor gave this assignment question, where he asks us to compare the expressive ease and the expressive range of Low Level and High Level theoretical programming languages.

While in context, I could understand that "hook" seems to refer to the opposite of an abstraction, I don't understand precisely what it means. Is it a real term, or did my professor (who isn't being helpful) make it up?

This is the question, cut from the assignment:

Typically, a hook is an non-abstract method defined in an abstract class, that can be optionally implemented and overridden in subclasses to modify behaviour. I think this is best exemplified in the template method pattern, where the (abstract) superclass defines the overall semantics for a process, but leaves primitive operations to be implemented by sublasses:

A template method is defined inside an abstract class:

public abstract class AbstractLogger {

    /*
     * Template method, made final to make
     * sure the flow is not modified by subclasses
     */
    public final void logMessage(String msg) {
        msg = preProcess(msg);
        writeToLog(msg);
    }

    /*
     * Abstract primitive operation that must be
     * implemented by subclasses
     */
    protected abstract void writeToLog(String str);

    /*
     * Hook method that can be optionally overriden to
     * modify the template method's behaviour
     */
    protected String preProcess(String str) {
        return str; // default behaviour: do nothing
    }

}

Concrete subclasses make use of the hook-method to augment behaviour:

public abstract class TerminalLogger extends AbstractLogger {

    /*
     * This primitive operation must be implemented
     */
    protected void writeToLog(String str) {
        System.out.println(str);
    }

    /*
     * Override super.preProcess() to modify behaviour
     * of the template method
     */
    protected String preProcess(String str) {
        return str.toLowerCase();
    }
}

Pardon the contrived example - I hope it illustrates the point clearly enough.
For more info on hook methods and template methods see:

http://en.wikipedia.org/wiki/Hook_method#Hook_methods

http://en.wikipedia.org/wiki/Template_method_pattern

The template method pattern wiki presents a fuller example than mine - you might want to check it out.


How does reducing the Halting problem prove the reduction cannot exist? For example, take the problem "Does M Halt on the Blank Tape?".

My approach was to reduce the halting problem to prove this problem is also undecidable. I generated a Mw by

Writing w on the tape
Moving to the leftmost blank
Running M

Then, of course there is the M-halt-on-blank function:

if(Mw halts)
    true
else false

Where I am having difficulty is understanding how this "proves" the halting problem. The halting problem is supposed to take in an input w and a machine M and tell if M halts on w. If we are creating Mw by taking w and modifying it, and running M on the modified tape, then M isn't really running on w at all. Instead, it is running on this modified tape. This would mean there is an infinite amount of w's that cannot even be run on M. So by using M-halt-on-blank as a decider, how is that solving the halting problem, and thus proving itself to be undecidable?

I understand there are a few similar posts but I am more concerned with the ends than the means for this problem, and I didn't find previous posts to answer this.

First, I think you're confused about some terminology.

You don't "prove the halting problem". In computer science, problems are computational tasks: you don't prove tasks; you perform them. Or, in this case, you you prove that there is no algorithm that decides the halting problem.
You don't "reduce the halting problem". A reduction is a conversion between two problems so, when you talk about reductions, you need to say what you're reducing from and what you're reducing to.

Second, you've confused which way this reduction is going. You're trying to prove that the blank-tape halting problem is undecidable, and you do this by proving that a problem that is known to be undecidable (in this case, the halting problem) reduces to it. That is, you prove that, if you could solve the blank-tape halting problem, you could solve the ordinary halting problem.

The reduction works like this.  Suppose there is an algorithm that decides whether a Turing machine that's given as its input halts when started with a blank tape.  The input to this algorithm is a description of the Turing machine (its "source code", if you like) and it somehow analyzes its input and says either "Yes, that machine halts when started with a blank tape" or "No, it doesn't."  We'll use this machine to determine if a given Turing machine $M$ halts when started with input $w$ (i.e., to solve the ordinary halting problem).  The new algorithm is this: we take the description of $M$ and the string $w$ and we produce a new Turing machine description $N$. The source code for $N$ says, "First, delete your input. Then, write $w$ to the tape, one character at a time. Then, rewind the tape to the start and do exactly what $M$ does (i.e., it then includes a copy of $M$'s source code)." Note that each different value of $M$ and $w$ will give a different machine $N$. Now, we just ask our algorithm for the blank-tape halting problem if $N$ halts when given no input, and that tells us whether $M$ halts when given input $w$.

That is, we've used the blank-tape halting problem to solve the ordinary halting problem. However, we know that the ordinary halting problem is undecidable so something must have gone wrong.  The translation of $M$ and $w$ to $N$ is completely fine: it's just some small edits to a machine's source code. So the impossible thing must have been the assumption that we have an algorithm for the blank-tape halting problem. There must be no such algorithm, which is the very definition of the problem being undecidable.


What does the halting problem mean for a Babbage machine? I read that the Babbage machine is Turing complete. Which means that no decision Turing machine will halt on the question "does the Babbage machine computes the logarithms of its input?" (for example).

The way I imagine that is there is no finite method (i.e. algorithm) which would examine the Babbage machine, possibly by testing it, but most probably by dismantling it like a watch and concludes that it indeed computes logarithms.

Would that be a correct way of thinking the halting problem on the Babbage machine?

No. The undecidability of the halting problem for a particular model of computation means that there's no algorithm that takes as input a description of an arbitrary machine $M$ in that model and an input $x$ and determines whether $M$ halts when run with input $x$.

As a consequence, there's no algorithm that takes as input a description of a machine and determines whether that machine computes logarithms. However, that doesn't mean that you can't prove that a specific machine computes logarithms. Indeed, people do this all the time, as exemplified by Knuth's famous quote, “Beware of bugs in the above code; I have only proved it correct, not tried it” (emphasis mine). Proving the code correct requires proving that it terminates and computes the thing it's supposed to compute.


How does the undecidability of Extensional Martin-Löf Type Theory apply to real type-checking compilers? It is claimed in many sources (for example, here) that adding a rule like "if Id(X,Y) then X really equals Y" to a type theory is "problematic" because then its type-checking becomes undecidable. I have read Martin Hoffman's proof ("Extensional concepts in intensional type theory", Section 3.2.2), as well as this SE question, but I still don't see how this creates a problem for a "down-to-earth" programming language.
I understand that deciding whether x:A has type B can get difficult, because there might exist a proof of Id(A,B). But the purpose of any "normal" type-checker is to verify, not to decide, so how is it problematic?
As I see it, nothing prevents the compiler from functioning like this: whenever the user tries to use a value of type X where a Y belongs, if the user has previously provided a proof that Id(X,Y), then we allow it, as if X and Y were syntactically identical. But if such a proof hasn't been provided, we treat it as an error, because the user "hasn't made his case".
My question is: what difficulties, if any, can arise from treating identity types like that?

You can't expect to find a ready-to-use proof of Id(a,b) when you need one. For instance, you have proofs of Id(a,c) and Id(c,b), but not of Id(a,b). You would need some intelligence to find automatically new proofs of equality, and avoid always having to ask the user to do the job manually. But there is no perfect algorithm to implement such an intelligence: whatever you implement, it will always have limitations.
There are however solutions to this difficulty, see for instance the Andromeda project.


Performance of microkernel vs monolithic kernel A microkernel implements all drivers as user-space programs, and implements core features like IPC in the kernel itself. A monolithic kernel, however, implements the drivers as a part of the kernel (e.g. runs in kernel mode).

I have read some claims that microkernels are slower than monolithic kernels, since they need to handle message passing between the drivers in user space.  Is this true?

For a long time, most kernels were monolithic because the hardware was too slow to run micro-kernels quickly. However, there are now many microkernels and hybrid kernels, like GNU/Hurd, Mac OS X, Windows NT line, etc.

So, has anything changed about the performance of microkernels?  Is this criticism of microkernels still valid today?

As is always the answer (or at least the preface) to performance-related questions: know your problem domain, run comparative benchmarks, and remember what premature optimization is.

First, no comprehensive benchmarking trials have compared monolithic kernels to current-generation microkernel systems that operate in an equivalent manner. So, while there may be trials that compare specific elements of those kernels, they're not going to be representative of the "big picture" that your question is looking to paint.

With that being said, there are wildly divergent observations of kernel performance across microkernels; for example, the L4 microkernel family can be said to have IPC performance an order of magnitude higher than the Mach kernel. But every Apple device from this decade is running Mach, and they seem to work plenty fast, right?

The moral of the story is that anybody who's deciding what kernel architecture to use needs to first decide what their ultimate goal is. Microkernel systems are (when properly implemented, of course) more secure, maintainable, and modular. However, they can be tough to architect properly, and may have performance overhead over a monolithic implementation. A monolithic kernel will be faster, but security will be harder to implement and it will be less modular and less easy to customize.

Your kernel architecture should be based on what your end goal is.

(And when all else fails, try it both ways and see what happens.)


What is an extremely basic asymmetric cipher that I can present at the pub? I'm trying to explain the basics of Bitcoin to my parents.

One of the core components of bitcoin, is signing transactions to make sure your identity can't be impersonated, and thus the need to explain a simplified asymmetric cipher.

What's an extremely simple asymmetric cipher I can use as an example?

How can this simplified cipher be used for signing?

If you want to present public key cryptography to your parents or friends, then I suggest you follow some guidelines. First, don't talk about specific functions, nobody cares about SHAxxx, keep your talk conceptual. The problem solved by public key cryptography is allowing two parties who never met before to securely exchange information in a public channel. Do not confuse this with other applications that are achieved by public key encryption, such as digital signatures or authentication.

An illuminating simple illustration of this that I have seen is the following. Suppose that two parties have a bucket and a number of colors, and they want to agree on a specific secret compound. They are allowed to send each other a bucket with a certain compound, but anything sent is exposed to an evil adversary. The underline assumption is that mixing colors is easy, but decomposing a mixture to its ingredients is hard. This assumption (which is easily connected to the formal side of things) allows you to achieve their goal. Pick a public color $P$, and allow both parties to pick a secret color, let us denote them by $S_1,S_2$. The first party then sends a bucket of a mixture of $P,S_1$. Similarly, the second party sends a bucket containing a mixture of $P,S_2$. Finally, each side adds his private color to the mixture he received, and now both parties have a mixture of $P,S_1,S_2$, which (by our assumption) remains secret from any eavesdroppers. A formal version of this is the Diffie-Hellman key exchange protocol, which relies on the hardness of discrete log.

Now, my understanding of the bitcoin protocol is limited, but when talking to your parents about it, I see no reason to go into cryptography. Most of the popular explanations I have seen unnecessarily delve into implementation details, and start talking about finding a preimage of a hash such that the result would have $x$ number of zeros, loosing sight of the actual problem. As before, I suggest to keep the talk conceptual. What problem is the bitcoin trying to solve, and why isn't this trivial? To my understanding, the bitcoin solves the problem of maintaining a distributed ledger, specifically avoiding the double spending problem. The motivation is to avoid having a central authority, and this can be achieved by allowing each participant to approve a transaction (instead of giving this authority to the bank). To avoid adversarial participants approving their own invalid transactions, the concept of proof of work is introduced. POW uses the hash as a black box, so you can avoid mentioning specific candidates.


what algorithm is used to calculate the exponential function $e^x$? I am using Matlab daily. But I just realized that I even do not know what algorithm Matlab is using for calculating the exponential function $e^x$.
The power series expansion is obviously not appropriate for a big $|x|$.

Let $x = n \log_e(2) + x'$, then $e^x = 2^n \cdot e^{x'}$.
You can pick n so that $- 0.5\cdot \log_e(2) ≤ x' ≤ +0.5 \cdot \log_e(2)$.
$e^{x'}$ is easy to calculate because $x'$ is small, and $2^n$ can be calculated easiest by producing the bit represenation of $2^n$ as a floating point number.
That's the principle. You'll want to take care that x' is calculated with the highest possible precision, and that $e^{x'}$ is also calculated with the highest precision. And you want to take care if x and x+eps use different values n, that $e^x$ and $e^{x+eps}$ fit together nicely; you wouldn't want a sitation where $e^{x+eps} < e^x$ with eps > 0.


Meta-grammar for context-free grammars Formal grammars like regular expressions (REs) or context-free
grammars (CFGs) specify languages, i.e. sets of strings over an
alphabet.

Grammars themselves can be seen as languages, e.g.
the set of REs over $\{0, 1\}$. In that sense we
can specify a grammars by means of a meta-grammar. For example the language of all REs over a fixed alphabet can be
specified as a context-free grammar (CFG), e.g. like so

$$
   R \quad::=\quad 0 \ |\ a \ |\ RR \ |\  R+R \ |\ (R) \ |\  R^*
$$

where $a$ ranges over the ambient alphabet. One advantage of thinking of grammars in terms of their meta-grammar is that we can parse REs and check them for syntactic correctness.

What kind of meta-grammar (context-free or otherwise) allows us to
specify the language of CFGs over a given alphabet? What about subsets
of CFGs like LL(k) or LR(k)? I'm sure this has been investigated before as there are many tools that take grammars as input, e.g. parser generators.

Backus–Naur Form's syntax can be represented with a BNF itself. Here is an example taken from this Wikipedia article:

<syntax>         ::= <rule> | <rule> <syntax>
<rule>           ::= <opt-whitespace> "<" <rule-name> ">"
                     <opt-whitespace> "::=" <opt-whitespace>
                     <expression> <line-end>
<opt-whitespace> ::= " " <opt-whitespace> | ""
<expression>     ::= <list> |
                     <list> <opt-whitespace> "|" <opt-whitespace> <expression>
<line-end>       ::= <opt-whitespace> <EOL> | <line-end> <line-end>
<list>           ::= <term> | <term> <opt-whitespace> <list>
<term>           ::= <literal> | "<" <rule-name> ">"
<literal>        ::= '"' <text> '"' | "'" <text> "'"

"" denotes the empty string. The article provides some more details on undefined here rules for <rule-name>, etc.


Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model From a comment, an interesting question popped up. The class of CFLs (the languages recognized by PDAs) are obviously not closed under nondeterminism - what I mean by this is that deterministic PDAs are not equivalent in power to nondeterministic PDAs.

However, all CFLs are decidable, and in this case, any deterministic TM is equivalent in power to a nondeterministic TM.

Now, this is a large gap - what is the smallest language "above" CFLs that is closed under nondeterminism?

The notion of a PDA can be generalized to an $S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA). It consists of

a read-only input tape, surrounded by endmarkers,
a finite state control,
a read-write storage tape of length $S(n)$, where $n$ is the length of the input string, and
a stack

In "Hopcroft/Ullman (1979) Introduction to Automata Theory, Languages, and Computation (1st ed.) we find:

Theorem 14.1 The following are equivalent for $S(n)\geq\log n$.

$L$ is accepted by a deterministic $S(n)$-AuxPDA
$L$ is accepted by a nondeterministic $S(n)$-AuxPDA
$L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$.

with the surprising:

Corollary $L$ is in $\mathsf P$ if and only if $L$ is accepted by a $\log n$-AuxPDA.

The proof consists of three parts: (1) If L is accepted by a nondeterministic $S(n)$-AuxPDA with $S(n)\geq \log n$, then $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$. (2) If $L$ is in $\operatorname{DTIME}(T(n))$, then $L$ is accepted in time $T^4(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input). (3) If $L$ is accepted in time $T(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input), then $L$ is accepted by a deterministic $\log T(n)$-AuxPDA.

Part (1) is basically a rigorous proof that the "halting problem is decidable", where the number of operations was counted thoroughly. Part (2) is the creative idea that prepares the stage for part (3). Part (3) uses the auxiliary storage for tracking the time step, which allows to reconstruct the head position due to the very simple forward-backward head scan pattern, and the stack for recursive backtracking.

The above is a copy of large parts of an answer to another question. So in which sense does it answers the current question? It is not the smallest imaginable class that contains $\mathsf{CFL}$ and is closed under nondeterminism. But it is a very well known class (i.e. $\mathsf P$) and a natural machine model, which has been studied thoroughly in the past, and is still studied today (with an additional runtime restriction) in the context of LogCFL. Indeed, LogCFL is also closed under nondeterminism and is closer than $\mathsf P$ to $\mathsf{CFL}$, proving my point that the above (i.e. $\mathsf P$ = $\log n$-AuxPDA) is not the smallest imaginable class of this kind.


How can I build a fool proof security system? From what I understand, designing an IT security systems requires to build an algorithm D which can decide whether any program M is malicious or not.

That tasks looks very similar to me than deciding a non-trivial property of an arbitrary large set of programs. And as we know by Rice or diagonalization or many different methods, this problem is undecidable.

That means (if I am not wrong) that for some input D might run forever without sending a reply. Obviously that's not acceptable for a security system. Let's assume for sake of simplicity, that I need a guaranteed YES or a NO.

How can that be implemented in reality? And what are the consequences for the results?

It is true that there is no general algorithm $D$ which can take as input any program $M$ and decide whether $M$ is malicious or not. Rice's theorem applies, here.

However, Rice's theorem does not imply that there is no $D$ that can do its job on a useful subset of programs $M$. This subset can not be the whole set of programs, according to Rice, but it could still be large enough to be useful in practice.

I'd say that most of the research in formal verification is about finding such a $D$ for specific cases. Usually the typical verifier $D$ outputs results meaning "I established that $M$ is malicious", "I established that $M$ is not malicious", or "my analysis was inconclusive, $M$ is too complex for me".

Essentially, we allow $D$ to throw the sponge, but hope that it won't.
We can't have a guaranteed YES or NO without also having, in infinitely many cases, the "inconclusive" result.

A naive technique to implement a $D$ could be to run $M$ for 1000 steps, and sees is $M$ does something bad. If it does, output "$M$ is malicious", otherwise output "inconclusive".

Static analyzers and model checkers (to mention two common approaches) only succeed on a subset of cases, but they can still be quite useful.


Asymptotic time complexity for finding maximum element in an array Consider a simple algorithm to find the maximum element of an array containing integers. We just loop through the array, storing the maximum found so far and updating it whenever an element larger than the existing maximum is encountered.

This algorithm is often considered to have $O(N)$ complexity. But doesn't accessing the array take $O(\log N)$ time in each iteration of the for loop? After all, an array of size $N$ requires $\log N$ address bits, so accessing each element should take $\log N$ time steeps? So the total time complexity should be $O(N \log N)$, unless I'm missing something here?

The usual model of computation used to analyze algorithms is the unit-cost RAM model, in which machine words have width $O(\log n)$, and operations on machine words (including dereferencing) take constant time.

In this model of computation, you can find the maximum of an array of length $n$ words in linear time.


Number of permutations of set {1, 2, ..., n} for which insertion sort will perform exactly n permutations I have had the following problem at my last exam:

For how many permutations of set {1, 2, ..., n} where n > 2 will insertion sort (without guard element) perform exactly n comparisons.

My thinking was: there must be exactly one inversion of succeeding elements so any of the pairs (2, 3) or (3, 4) ... or (n-1, n) has to be swapped in the sorted sequence. So I answered n-2 because there's n-2 such pairs. But the answer was 2(n-1). Why?

Your analysis looks correct to me. The answer should be N-2, not 2(N-1).

It wouldn't be unheard of for graders/teachers to work with an incorrect solution.


Worst case analysis of bucket sort using insertion sort for the buckets Suppose I am using the Bucket-Sort algorithm, and on each bucket/list I sort with insertion sort (replace nextSort with insertion sort in the wikipedia pseudocode).

In the worst case, this would imply that we would have $O(n^2)$ performance, because if every element was in one bucket, then we would have to use insertion sort on $n$ elements which is $O(n^2)$.

So the first thing that comes to mind to fix the worst case running time is to not use insertion-sort, because it is $O(n^2)$. Instead we could use merge-sort or heap-sort m, because the worst case running time for both of those algorithms is $O(n\log n)$. However, if we use merge-sort and heap-sort, do they preserve the expected linear running-time of bucket-sort?

You should first understand the proof that bucket sort runs in expected linear time if insertion sort is used. At some point in the proof, the worst-case running time of insertion sort  shows up. See what happens when you plug in instead the worst-case running time of any other sorting algorithm.

The reason insertion sort is used in practice is that we expect the buckets to be small, and for small lists, insertion sort is much faster than anything else. Even when implementing merge sort or quicksort, insertion sort is used when the list gets small enough (say below 20 items or so).


How to compute linear recurrence using matrix with fraction coefficients? What I'm trying to do is generate Motzkin numbers mod a large number $10^{14} + 7$ (not prime), and it needs to compute the $n$th Motzkin number as fast as possible. From Wikipedia, the formula for the $n$th Motzkin number is defined as following:

$\qquad \displaystyle \begin{align}
  M_{n+1} &= M_n + \sum_{i=0}^{n-1} M_iM_{n-1-i} \\
          &= \frac{2n+3}{n+3}M_n + \frac{3n}{n+3}M_{n-1}
\end{align}$

My initial approach is to use the second formula which is obviously faster, but the problem I ran into is the division since modular arithmetic rule doesn't apply.

void generate_motzkin_numbers() {
    motzkin[0] = 1;
    motzkin[1] = 1;
    ull m0 = 1;
    ull m1 = 1;
    ull numerator;
    ull denominator;
    for (int i = 2; i <= MAX_NUMBERS; ++i) {
        numerator = (((2*i + 1)*m1 + 3*(i - 1)*m0)) % MODULO;
        denominator = (i + 2);
        motzkin[i] = numerator/denominator;
        m0 = m1;
        m1 = motzkin[i];
    }
}

Then I tried the second formula, but the running time is horribly slow because the summation:

void generate_motzkin_numbers_nested_recurrence() {
    mm[0] = 1;
    mm[1] = 1;
    mm[2] = 2;
    mm[3] = 4;
    mm[4] = 9;
    ull result;
    for (int i = 5; i <= MAX_NUMBERS; ++i) {
        result = mm[i - 1];
        for (int k = 0; k <= (i - 2); ++k) {
            result = (result + ((mm[k] * mm[i - 2 - k]) % MODULO)) % MODULO;
        }
        mm[i] = result;
    }
}

Next, I'm thinking of using matrix form which eventually can be speed up using exponentiation squaring technique, in other words $M_{n+1}$ can be computed as follows:
$$M_{n+1} = \begin{bmatrix} \dfrac{2n+3}{n+3} & \dfrac{3n}{n+3} \\ 1 & 0\end{bmatrix}^n \cdot \begin{bmatrix} 1 \\ 1\end{bmatrix}$$
With exponentiation by squaring, this method running time is $O(\log(n))$ which I guess the fastest way possible, where MAX_NUMBERS = 10,000. Unfortunately, again the division with modular is killing me. After apply the modulo to the numerator, the division is no longer accurate. So my question is, is there another technique to compute this recurrence modulo a number? I'm think of a dynamic programming approach for the summation, but I still think it's not as fast as this method.  Any ideas or suggestions would be greatly appreciated.

Your matrix formulation doesn't work- you need to use different $n$s in the matrices.

One idea to rescue your original approach is as follows. First, factor $10^{14} + 7 = 98794607 \times 1012201$ (only the second factor is prime). It is enough to compute $M_n$ modulo the two factors. The first factor is smaller than $2^{32}$, so you can store the first $10000$ Motzkin numbers modulo it using only 40KB. The second factor is prime and larger than $10003$, so you can use modular division, in which you multiply with the inverse (see here for how to calculate the inverse). This only works since $n+3$ will actually have an inverse, and that's why we factored $10^{14} + 7$.


Are fractions more computationally "expensive" than whole numbers? I have a problem where the values are represented to humans as [0, .5, 1, ..., 8]

But the function is massively recursive (game trees for a set of increasingly intractable problems) so I'm wondering is it more computationally efficient to use the values [0, 1, 2, ..., 16] and only divide by 2 when outputting for humans?

(Possibly this is a non-issue with high level languages and modern processors.  The hardware we'll be running on is smartphones, but everything has to be local.)

This link below compares all arithmetic operations between floating point and integer variables on various architectures and processors.

With the general conclusion drawn that additions and subtraction are roughly equal, the performance impact arises in multiplication and division operations; with integer being faster. (Except for x86-64 AVX and POWER8 AltiVec where it is faster in the former for floating point and equal in the latter.)

Integer and Floating-Point Arithmetic Speed vs Precision: http://nicolas.limare.net/pro/notes/2014/12/12_arit_speed/


Data structure for efficient group lookup I need a data structure, which allows efficient queries for 'give me the group of x'.
Let me give you an example:
Group 1: [a, b, c]
Group 2: [d, e]
Group 3: [f]

getGroupOf(d) -> [d, e]

There are no significant constraints on storage or construction time. I only need getGroupOf to be O(logn) or faster.
I am thinking about using a Dictionary<Element, Set<Element>> where entries for all elements in a group share the same set reference. This would make lookup effectively O(1) or O(logn) depending on the dictionary implementation, but would result in a lot of entries.
This feels fairly bloated, and I am wondering: is there is a more elegant data structure to accomplish this?
Edit: the elements in a group can be completely arbitrary and they have no ordering.

If the groups are static, your data structure is perfectly reasonable.
You can also consider the Union-Find data structure.  Find is the getGroupOf operation.  It is quite fast, and also allows you to modify the data structure by merging groups and adding a new item in its own group.


What is a forwarded clock? I'm reading the overview book of the Intel QuickPath Interconnect and it says there:

The physical connectivity of each interconnect link is made up of twenty differential signal pairs plus a differential forwarded clock.

I can't find what is a forwarded clock, does anyone know what it is and if there is some material for reading about it?

According to lecture notes of Sam Palermo, there are three common I/O clocking architectures:

Common clock (synchronous)
Forward clock (source synchronous)
Embedded clock (clock recovery)


Go-Back-N Protocol not efficient? Let's say we have five packets

p1 p2 p3 p4 p5

to be sent sequentially:
and for some reasons, p3 got delayed so it the the last packet to arrive recevier.
so below is the receiving order on the receiver's end

p1 p2 p4 p5 p3

and according to the Go-Back-N Protocol, the receiver will only send acknowledge of p2 when it receive p5.
then the receiver receives p3 right after p5, and then it sends acknowledge of p3 to the sender.
But there will still be a timeout and the sender still has to re-send p4 and p5,even though the receiver did receive all packets, isn't this Go-Back-N Protocol really inefficient?

The Go-Back-N protocol is often presented for didactic purposes as a first, maybe crude attempt at tackling loss of packets or of order in connection-oriented communications, without obeying the constrains of Stop-and-Wait protocols, also introduced for didactic purposes.  It is no wonder it appears inefficient -- it probably was never meant to be so.  Selective Repeat can be considered as a performance improvement in terms of retransmissions over Go-Back-N, and in practice TCP itself relies on a hybrid solution of the two.


How many possible ways are there? Suppose I have the given data set of length 11 of scores:

p=[2, 5, 1 ,2 ,4 ,1 ,6, 5, 2, 2, 1]

I want to select scores 6, 5, 5, 4, 2, 2 from the data set. How many ways are there?

For the above example answer is: 6 ways

{p[1], p[2], p[4], p[5], p[7], p[8]}
{p[10], p[2], p[4], p[5], p[7], p[8]}
{p[1], p[2], p[10], p[5], p[7], p[8]}
{p[9], p[2], p[4], p[5], p[7], p[8]}
{p[1], p[2], p[9], p[5], p[7], p[8]}
{p[10], p[2], p[9], p[5], p[7], p[8]}

How can I count the ways in general?

Say you want to pick, out of a multiset $S$, the numbers $x_1$, $x_2$, ..., $x_n$ with multiplicity $m_1$, $m_2$, ..., $m_n$  (i.e., you want to pick $x_1$ exactly $m_1$ times).
Furthermore, assume that in $S$ the numbers  $x_1$, $x_2$, ..., $x_n$ have multiplicity $s_1$, $s_2$,..., $s_n$.  (we assume for every $i$, $s_i \ge m_i$, otherwise no solution exists).

Consider the first element $x_1$:
you have exactly $s_1 \choose m_1$ different ways to pick $m_1$ occurrences of $x_1$ from the $s_1$ times it appears in $S$.

In a similar way for all the other elements,  the answer would be
$${s_1 \choose m_1} {s_2 \choose m_2} \cdots {s_n \choose m_n} = \prod_{i=1}^n {s_i \choose m_i}$$

For your example, set $x_1=6$, $x_2=5$, $x_3=4$, $x_4=2$.
In the data set they appear with multiplicity $s_1=1$, $s_2=2$, $s_3=1$, $s_4=4$ and you want to have $m_1=1$ sixes, $m_2=2$ fivess, $m_3=1$ fours and $m_3=2$ twos, so the number of different options is
$$ {1 \choose 1} {2 \choose 2} {1 \choose 1}{4 \choose 2}  = 1 \cdot 1 \cdot 1 \cdot 6$$


Period in postulate; what does it mean? While I am learning a lot from others here at the Computer Science site, I must admit that I don't get as much out of some questions and answers since I typically don't understand the theorems to the level necessary. I am currently reading How To Prove It - A Structured Approach which is starting to make the theorems easier to read, but still does not get me to the point of being able to understand the theorems to the point that they add great insight to the question or answer.

For this question Is it possible to always construct a hamiltonian path on a tournament graph by sorting?

there is a use of a peroid in the premise.

  $\qquad \displaystyle a \leq b \iff (a,b) \in E \lor \left(\exists\, c \in V. a \leq c \land c \leq b\right)$

What does the period mean? I would be expecting either a comma to mean conjuction or or to mean disjunction, but not a period. I don't see how this could be converted to logical statements.

Note: Jukka Suomela has already provided the answer in this CS meta question.

After an $\exists$ the period can be read as "such that".
For example,
$\exists x\in \mathbb{N}. x>4$ can be read as "there exists a natural $x$ such that $x$ is greater than 4."

After a $\forall$ it can be read as "it is the case that". For example,
$\forall x\in\mathbf{N}. x +  1> x$ can be read as "for all natural numbers $x$, it is the case that $x+1$ is greater than $x$.

Generally one can omit "it is the case that" and the sentence still works.


How can I combine 2 PDA's into 1 I need to form PDA for this language: {$a^nb^m|n=m \vee n=2m$}
I know the idea of building each one separately but how do I combine them into 1 PDA?
LHS: for every 'a' I push 'A' inside stack and for every 'b' I eject 'A'.
RHS:for every 'a' I push 'A' inside stack and for every 'b' I eject 2 times 'A'.
How can I combine them? Can I somehow use non determinism?

Construct one PDA for $n=m$ and another one for $n=2m$. Branch to one of them using an $\epsilon$ transition at the very beginning.


What is a task type? I have an unlabeled dataset: 500 X-rays of seeds in husk. In each image there are different number of seeds, for instance, from $10$ to $50$.

A seed has some features. The main features are a seeds' square and a husks' square in pixels. I need to calculate the these features ratio.
I am looking for an objects recognize algorithm.
My problem is: I don't know what is a task type.

The dataset is unlabeled and I can use unsupervised learning and identify a similarity in groups (clustering task). Or I should to label data and use supervised learning and identify a real values (regression task)?
Question What is a task type?
Literature

The Plant Pathology 2020 challenge dataset to classify foliar disease of apples
Exploring Survival on the Titanic

This is likely to be a challenging task, and if you're not familiar with image classification, I suspect it may be beyond what you can reasonably do right now.
I would suggest you investigate classical image processing techniques.  You might try applying morphological operators, such as closing (dilation followed by erosion) or opening followed by thresholding.  You may need to experiment.  If you search on Stack Overflow and Signal Processing sites, you'll find many examples.
See also blob detection and watershed segmentation.


optimal testing strategy Here I have a problem in understanding the optimal testing strategy.

In a scenario, You have been given two laptop batteries and a testing device. The testing device will make the battery connected to it (one battery can be connected at a time) deliver x mA, where x is an integer. The testing device is constructed in such a way that the battery will always explode if there’s any risk of explosion at that current.

Now we want a program that receives inputs. Input consists of multiple lines, one line per case (at most 200 test cases). Each line contains a single positive integer n between 1 and 4711 inclusive, giving the current at which the battery is known to explode. Input is terminated by a line containing 0, which should not produce any output.

And produce Output, where for each case, print one line containing the worst-case number of tests to perform when using an optimal testing strategy.

|-----------------|------------------|
|  Sample Input   |  Sample Output   |
|--------- -------|------------------|
    1                0
    2                1
    10               4
    23               7
    0

This was a programming contest question marked as an easy question. but I do not get the definition of the optimal testing strategy.
What can be the boundaries? Generally what this question means?

in my opinion, The designer of this question just wanted to make a famous algorithm problem a bit complicated but made it totally nonsense.

This is the famous two egg problem where

  You are given two eggs and access to a 100-story building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.


Generate a random combination in O(k) time and space? How to generate a random combination of $k$ numbers from $n$ choices in $O(k)$ time and space, if we can generate a random number between 1 and $O(n)$ in $O(1)$ time?

I know only 3 algorithms: with $O(n)$ time and space, $O(k\log k)$ time and $O(k)$ space, $O(k)$ average time and $O(n)$ space. Is it even possible to solve this task on $O(k)$ both?

Suppose that $k \leq n/2$ (the constant $1/2$ is arbitrary) – otherwise you can just use the $O(k)$ time, $O(n)$ space algorithm, which is the second algorithm that you mention.

One way of solving your problem is as follows:

Start with the empty list.
Repeat $k$ times:

Generate a random number from $1$ to $n$.
Check if it is already in the list.
If so, go back to step 1.
Otherwise, add it to the list.

The expected number of steps in this algorithm is
$$
\frac{1}{1-0/n} + \frac{1}{1-1/n} + \cdots + \frac{1}{1-k/n} = n \left(\frac{1}{n} + \cdots + \frac{1}{n-k}\right) \leq \frac{k}{2},
$$
since $k \leq n/2$.

Using a hash table, use should be able to implement step 2 in $O(1)$ expected time and $O(k)$ space.


Versions of NP with different logical unifiers One formulation of NP is this: a language is in NP if it can be solved in polynomial time by an algorithm that has access to a special "Nondeterministic Bit" function, which branches the world into two alternate universes, writes a $1$ on the worktape in the first universe and a $0$ in the second, finishes the computation in each universe, and then returns the OR of the computation value of each universe.

If we replace the OR in this formulation with an AND, we get coNP.

I'm wondering what complexity class is described if we use the other nontrivial symmetric binary logical operators.

$\text{OR} \to NP$

$\text{AND} \to coNP$

$\text{XOR} \to \,?$

$\text{NAND} \to \, ?$

$\text{NOR} \to \,?$

$\text{EQUALS} \to \, ?$

In the case of XOR or EQUALS, you get the class $\oplus$P, which includes the graph isomorphism problem.

In the case of NAND or NOR, I believe that you get PSPACE. Indeed, PSPACE is an upper bound, and you should be able to solve QBF in this model.


Simulate $n$-PDA with $n-1$-PDA I've heard that every $n$-PDA when $n > 2$ is as powerful as $2$-PDA. Unfortunately every proof I'm able to find uses references to Turing Machines, which I haven't learned about yet. I'm sure there must exist an alternative proof, supposedly one that converts $n$-PDA to $n-1$-PDA, and then proceeds by induction, but I'm unable to find it. Any references, or hints are greatly appreciated.

What I tried: to simulate two stacks using just one, therefore going from $n$ to $n-1$. But it would also mean that $2$-PDA are as powerful as $1$-PDA, so it's clearly a wrong way.

Yes, any PDA with $n>2$ stacks can be simulated by a pda with $2$ stacks. It is possible to show this without explicitly using Turing machines.

Assume that you have $n$ stacks, with contents $\alpha_1$ to $\alpha_n$. Store all these stacks on top of each other, with special separator symbols $\square_i$. So a single stack contains $\square_1\alpha_1 \dots \square_n\alpha_n$ (top left). Now assume that I want to perform an operation on stack $k$ (look at the top, check it is empty, push or pop symbols). In order to do this use the second stack. Move all stacks up to the $k$th to the second stack (popping from the one pushing to the other). The two stacks are now $\square_1\alpha_1 \dots \square_k\alpha_k$ and $\alpha^R_n\square_n\dots \alpha^R_{k+1}\square_{k+1}$. it is now easy to operate on stack $k$ (since it is on top of one of the stacks). and in general we continue moving the $n$ stacks around between the two stacks to  continue the simulation.


Can we have a general function of any function this way? Lets say we need a function to add two numbers and another function to multiply two numbers.

To take a trivial example, consider the function $F(a, b, c, d) = a \cdot (c+d) + b \cdot (c\cdot d)$
If $a=1$ and $b=0$, then $F$ adds $c$ and $d$.  If $a=0$ and $b=1$, then $F$ multiplies $c$ and $d$.

So to evaluate both add and mult I can have only one function $F$ with variable inputs.

Can we have a general function that can evaluate any arbitrary function ? of course with an upper bound on the complexity ? If yes how do we prove in theory that such a general function is possible ? What is this called in theory ?

The function you are describing is known as a universal Turing machine. A universal Turing machine is given a Turing machine $T$ and an input $x$, and outputs $T(x)$ (if $T$ doesn't halt, the universal Turing machine also doesn't halt).

If you want your function to have restricted complexity, you can just stop the computation once it has gone on for too long, and output zero, say. For any Turing machine with the correct complexity, the restricted universal Turing machine will still be correct. A variant is to accept a clocked Turing machine, which provides its own bound on the running time (which you can choose to ignore at your discretion).


"Regular languages over a common alphabet are closed under union." I just want to make sure I understand what this means. I am new to Formal Languages and this is my first week of courses.

Suppose we have two regular languages, $L_1$ and $L_2$, with a common alphabet.

The union of $L_1, L_2$ is $\{x:x∈L_1∨x∈L_2\}$

Does this mean that, for any string $s \in L_1$, we also have $s \in L_2$?

I see two possible points of confusion in your question, and I will address them separately.

What is meant by the title of your post: ""Regular languages over a common alphabet are closed under union."
"The union of $L_1,L_2$ is $\{x:x∈L_1∨x∈L_2\}$
Does this mean that, for any string $s∈L_1$, we also have $s∈L_2$?"

What is "Closure Under Union"?

Regular languages are a class of languages that exhibit the closure property with the union operation.

The closure property means that when an operation is applied to language(s) of a certain class the resulting language will also be of that class.

In this case the class of languages is the regular languages and the operation is union.

So all this means is that the union of two regular languages is also a regular language.

What is the union of two languages?

Languages can be thought of as sets of strings, so the union operation works the same way as in typical Set Theory.

I would read $\{x:x∈L_1∨x∈L_2\}$ as "the set of strings such that the string is in $L_1$ or the string is in $L_2$."

This does NOT mean that for any string $s∈L_1$, we also have $s∈L_2$.

We only have that for any string $s$ in the union of languages $L_1$ and $L_2$, denoted $s \in (L_1\cup L_2$), that string $s$ is in either $L_1$ or $L_2$.


Using random projections for locally sensitive hashing I recently came to see that this library sparselsh uses random projection to perform locally sensitive hashing of documents.

The proof is such that based on cosine similarity to the vector. In other words if the dot product of a random projection vector and a feature vector > 0, it would mean that the angle is obtuse and <0 if the angle is acute. However, i cannot seem to understand it.

Assuming v is a feature vector containing a bag of words, and the random projection vector being drawn from a normal distribution. I can safely say that v will never have negative elements since the bag of words vector can never have a negative value. In this case, How would there be a situation when r.v give an obtuse angle? Am i misunderstanding something?

I have referred to this question but to no avail. Locality-sensitive hashing random projection

Let me state my confusion clearer.

Consider a 2 dimensional vector space, Given that r.v < 0 if the angle between the two vectors are less than 90degrees and >0 when they are above 90 degrees. This would mean that the probability of the blue vector dot product with another data point giving a r.v > 0 is zero. This would mean that i can only draw vectors in the negative space?

$r \cdot v$ can be negative even if all elements of $v$ are positive: consider, e.g., $r = (2,-3)$ and $v=(1,1)$.  Then $r \cdot v = -1$.

Also, using random projections is not the same as defining a hash to be 1 if the dot-product is $\ge 0$ and 0 if it is $<0$.  You can still use a random projection without using that particular hash function.  I haven't looked at the sparselsh code, but it's also possible that it could be using a random projection but without using that specific hash function.


Enumerate all greedy choices of maximum independent set Following what is stated in the question Why is greedy algorithm not finding maximum independent set of a graph?,
I have the following question:

Even enumerating and testing all possible choices of the greedy algorithm (namely, when there are two possible choices, test both) and verifying which returns the highest value, can it return an approximate result? (ignoring the computational cost)

Take the graph in the answer you linked to, and add another vertex G that has an edge to every other vertex except C.  Now C has the unique fewest number of neighbours, so it will necessarily be chosen first; then you can choose at most one of A, E, F or the new vertex G since each of these 4 vertices is linked to each of the others by an edge, so the algorithm forces you to produce an independent set of size 2 (either {C, A}, {C, E}, {C, F} or {C, G}).  But the same size-3 independent sets as before still exist (e.g. {B, D, F}).


Lost in a "one directional" concert You and a friend lost each other on the line to a concert, and neither is sure which of you is further ahead. Formally, each is at some integer coordinate and may only walk towards a higher coordinate or stay in place.

Assuming you and your friend are following the exact same algorithm (and no, you may not say "if (name=="R B") do something :) ), and the initial distance between the two of you was $x$ (which is not known to you).

  What is the algorithm which minimizes the expected walking distance till you and your friend meet?

You may assume both your friend and yourself are moving in the same constant speed.

An example simple algorithm would be something like:

  At stage $n$ (starting from $0$):

  Walk $3^n$ steps to the right w.p. $\frac{1}{2}$ or wait $3^n$ time units otherwise.

To see this algorithm makes the friends meet with probability 1 consider what happens at stage $(\log_3 x+1)$. Even if the friend that was $x$ step ahead always walked and the other always stayed in place, the distance between the two would be:
$$x+1+3+9+\ldots+3^{\log_3 x}=2x+\frac{x-1}{2}\leq 3x$$

Therefore, at the $\log_3 x+1$ iteration, the friend which chooses to walk will cover distance of $3^{\log_3 x+1}=3x$, hence with probability $\frac{1}{4}$, the friend which is behind will catch up and they will meet.

A simple optimization (to reduce walking distance) would be, instead of walking $3^x$ steps, walking $c^x$ steps, where $c$ is given by:
$$2+\frac{1}{c-1}=c$$

Hence the optimal $c$ for this algorithm is $c=\frac{3+\sqrt 5}{2}\approx 2.618$

Unfortunately, while this algorithm guarantees that the friends will meet with probability 1, the expected walking distance is infinite, which is something I'd like to avoid if possible.

  Is there a more efficient algorithm?

At step $k$, draw a random number $q$ uniformly between $1$, $2$, and $3$.

  if $q = 1$, walk $2^{k-1}$, wait $2^{k+1}$, walk $2^{k-1}$
  if $q = 2$, wait $2^{k-1}$, walk $2^{k-1}$, wait $2^{k}$, walk $2^{k-1}$, wait $2^{k-1}$
  if $q = 3$, wait $2^k$, walk $2^k$, wait $2^k$

At each step $k$, both friends will walk $2^k$ steps. If $k < \log_2(x) + 1$, they won't meet during that step, however if $k >= \log_2(x) + 1$, they will meet if and only if they don't draw the same number. The probability that this doesn't happen is only $1/3$ at each step.

Hence the expected walking distance is (bounded above by):

$$2\left(\sum_{k=0}^{\lceil\log_2(x)\rceil}2^k+3^{\lceil\log_2(x)\rceil}\sum_{k=\lceil\log_2(x)\rceil+1}^{\infty}\left(\frac{2}{3}\right)^k\right)$$

Which is finite, and equal, if my napkin maths are to be trusted, to $2^{\lceil\log_2(x)\rceil+3}-2 \le 16x$.

By the way, if $d$ is the random variable representing the distance walked, we still have that $\forall D>0, \mathrm{P}(d>D) > 0$, i.e. the distance is unbounded and can end up being arbitrarily high. Luckily this probability vanishes fast enough to ensure that the infinite sum $\sum_{D=0}^{\infty}\mathrm{P}(d=D)\cdot D = \mathbb{E}[d]$ converges. Having a finite upper bound for $d$ is a much stronger property and I reckon it's not possible to find a solution satisfying it.


First Harshad number with given sum How can we compute the least Harshad number with given sum of decimal digits $S$? Harshad number in base 10 is any number divisible by sum of its decimal digits.

I think that some kind of dynamic programming should be used.  But which one?

Thanks in advance for any ideas.

You solve the following more general problem: find the least number $N$ with sum of digits $T$ such that $N \mod M = R$ (the inputs are $M,T,R$). Initially, $T=M=S$ and $R=0$. Now you go over all possible least significant digits $b$. Using the formula
$$
(10n+b) \pmod{M} = 10(n \pmod{M}) + (b \pmod{M}),
$$
you reduce the problem to a smaller one, and so on.

The total amount of work appears to be $O(S^2)$, since the number of possible values for $T$ and $R$ is $O(S^2)$. Care needs to be taken with zero digits, however, a detail which I leave you to ponder.


Minimum sum of distance from entrance gate Assumes we have N position, and 3 entrance gate. For example 10 position:

1--2--3--4--5--6--7--8--9--10

For each entrance gate, there is some people waiting to enter and fill positions, first number is position of gate, associated with chair(front of what chair) and second number is number of people to enter:

5 -> 4

6 -> 2

10 -> 2

If each people seats on chair front of gate, it's cost is 1, for every chair in right or left, the cost increase by 1. What is minimum total sum of cost of people distance to their gates?
For example:

10 (number of chairs)

4 5 ( gate front of seat 4 with 5 people)

6 2 (gate front of seat 6 with 2 people)

10 2 (gate front of seat 10 with 2 people)

Minimum cost is 18. The seats cost is is:

4 3 2 1 2 1 2 0 2 1

Zero means nobody sits on chair 9.

For above example number of gate associated with each people is:

1 1 1 1 2 2 1 0 3 3

Another example:

10

8 5

9 1

10 2

Answer is 24 and positions are:

0 0 7 5 4 3 2 1 2 1

And number of gate associated with each chair is:

0 0 2 1 1 1 1 1 3 3

What algorithm do you propose?

I will try to give a solution. Tell me if I am mistaking anywhere.

First observation : When we have equal number of chairs and persons the solution is trivial.Ask all the people from 1st gate to fill chairs from start. then next gate starts where 1st gate stopped. I leave it to you to check that this is the optimal solution.

Second observation : We can use dynamic programming here and start removing chairs. (Here I must say I am sorry as my notations might not match with general notations but I will try my best)

Let us denote the first problem as $f(10,(4,5),(6,2),(10,2))$. 10 is number of chairs, rest are ordered pairs stating number of gate and number of people. Now we will start removing chairs. There are 4 cases : chair is removed before 1st gate or between 1st and 2nd gate or 2nd and 3rd gate or after 3rd gate.

Now we can make the following observation : $f(10,(4,5),(6,2),(10,2))=\min[f(9,(3,5),(5,2),(9,2)),f(9,(4,5),(5,2),(9,2)),f(9,(4,5),(6,2),(9,2))]=\min(19,20,18)=18$ (Note that there are 3 cases here as the 4th case doesn't make sense.)

Here as there are 9 people we get the result (of $f$ using the first observation) from here. This is how you can do the problems. There might even be more gates you just have to generalize the function.

Did you understand what I tried to do?


Little O notation relationship Given the functions $()=^{n}$ and $()=10^{10n}$, I am trying to establish the following relationship: $()\notin o(())$.

I know to show for the opposite, $()\in o(())$,  I would need to choos $c$ and $n_{0}$ such that $\exists$ $c$, $\exists$ $n_{0}$, $\forall n\geq{n_{0}}$ then $f(n)\leq c. g(n)$, but how should I choose $c$ and $n_{0}$. Note that I am beginner in studying CS and any help would be greatly appreciated.

One possibility is to merely apply the definition. That is, we see that if $\lim_{n \to \infty} f(n) / g(n) = 0$, then $f(n) = o(g(n))$. Computing this, we have that $$\lim_{n \to \infty} f(n) / g(n) = \lim_{n \to \infty} n^n/10^{10n} = \infty \neq 0.$$ We conclude that $f(n) = o(g(n))$ does not hold.


$O(n^{k-1}$) algorithm for K-clique problem Clique problem is a well known $NP$-complete problem where the size of the required clique is part of the input. However, k-clique problem has a trivial polynomial time algorithm ($O(n^k)$ when $k$ is constant). I'm interested in the best known upper bounds when k is constant.

  Is there an algorithm with run time $O(n^{k-1})$? A $o(n^k)$-time algorithm is also acceptable. Also, Is there any complexity-theoretic consequence for the existence of such algorithms?

A 3-clique can be found in an $n$-vertex graph $G$ in time $O(n^\omega)$, where $\omega < 2.376$ is the matrix multiplication exponent, and in $O(n^2)$ space by a result of Itai and Rodeh [1]. Basically, they show that $G$ contains a triangle if and only if $(A(G))^3$ has a non-zero entry on its main diagonal. Because a triangle is also a cycle $C_3$, one can use general cycle finding methods for detecting triangles. Alon, Yuster and Zwick show how triangles can be detected on an $m$-edge graph in $O(m^{2\omega/(\omega+1)}) = O(m^{1.41})$ time [6].

For a long time, the result of Nesetril and Poljak [2] was the best known; they showed the number of cliques of size $3k$ can be found in time $O(n^{\omega k})$ and $O(n^{2k})$ space. Finally, Eisenbrand and Grandoni [3] improved on the result of Nesetril and Poljak for a $(3k+1)$-clique and a $(3k+2)$-clique for small values of $k$. Specifically, they gave algorithms for finding cliques of size 4, 5, and 7 in time $O(n^{3.334})$, $O(n^{4.220})$, and $O(n^{5.714})$, respectively.

As far as I know, for general $k$, the problem of designing better algorithms is open. For possible consequences or complexity theoretic considerations, Downey and Fellows (see e.g. [4]) showed $k$-clique with parameter $k$ is $W[1]$-hard. The class $W[1]$ denotes the class of parameterized decision problems reducible to CLIQUE with parameterized reductions. It is believed that CLIQUE is not fixed-parameter tractable. There are hundreds of other problems known to be equivalent to CLIQUE under parameterized reductions. Furthermore, Feige and Kilian [5, Section 2] have a result saying that when $k$ is part of the input and $k \approx \log n$, then a polytime algorithm is not likely to exist.

If you consider some restricted graph classes, you can solve the problem in linear time on chordal graphs. Simply compute a clique tree of a chordal graph $G$ in $O(n+m)$ time, and then check if any clique is of size exactly $k$. On planar graphs, one can also find triangles in $O(n)$ time using the methods of [6].

[1] Itai, Alon, and Michael Rodeh. "Finding a minimum circuit in a graph." SIAM Journal on Computing 7.4 (1978): 413-423.

[2] Nešetřil, Jaroslav, and Svatopluk Poljak. "On the complexity of the subgraph problem." Commentationes Mathematicae Universitatis Carolinae 26.2 (1985): 415-419.

[3] Eisenbrand, Friedrich, and Fabrizio Grandoni. "On the complexity of fixed parameter clique and dominating set." Theoretical Computer Science 326.1 (2004): 57-67.

[4] Downey, R. G., and Michael R. Fellows. "Fundamentals of Parameterized complexity." Undegraduate Texts in Computer Science, Springer-Verlag (2012).

[5] Feige, Uriel, and Kilian, Joe. "On Limited versus Polynomial Nondeterminism". Chicago Journal of Theoretical Computer Science. (1997)

[6] Alon, Noga, Raphael Yuster, and Uri Zwick. "Finding and counting given length cycles." Algorithmica 17.3 (1997): 209-223.


Divide sequence of numbers from 1 to n into 2 groups with minimum difference Let's say for some $n$ we have the sequence $1, 2, 3, \dots , n$, what we want with this sequence is to divide it in two sets such that each element of the sequence will be in only one set, and the difference in sums of the two sets will be minimum possible.

Example

Let $n = 4$, and $A$ and $B$ are our sets, we can divide the numbers in this set such that the difference in sum between them will be $0$, $A = \{1, 4\}$ and $B = \{2,3\}$

My thinking

I noticed we can divide like this $1$ and $n$ in set $A$, then $2$ and $n-1$ in set $B$, then $3$ and $n-2$ in $A$, etc..

My algorithm gives correct result if $n$ is divisible $4$, but when it is not divisible by $4$ it will return that the difference between the sets is bigger than it actually is, how can we divide the numbers optimally.

It turns out that the strategy depends on $n$ mod $4$.

To see why, one computes the total sum of all these numbers, which is $n(n+1)/2$. The parity of this sum depends on $n$ mod $4$: if $n$ is congruent to $0$ or $3$ mod $4$, the total sum is even; otherwise the total sum is odd.

When the total sum is odd, it is not possible to divide the set into two parts with equal sums. The minimum difference you can expect is therefore $1$.

If $n = 0$ mod $4$: you already figured out how to do that.

If $n = 1$ mod $4$: divide $2, \cdots, n$ using your strategy, and add the extra $1$ to any side. This achieves the minimum difference $1$.

If $n = 2$ mod $4$: divide $3, \cdots, n$ using your strategy, and add the extra $1$ and $2$ to each side to get the minimum difference $1$.

If $n = 3$ mod $4$: divide $4, \cdots, n$ using your strategy, and add $1$ and $2$ to one side, and $3$ to the other side to get the minimum difference $0$.


Extracting a spanning tree from a directed acyclic graph with minimum total distance between terminal nodes I have a directed acyclic graph that has uniform edge weights. I would like to extract from this graph a spanning tree (an arborescence) with the property that the total distance between all pairs of leaf nodes (the sum of combined distances from each pair's nearest common ancestor) is minimized.

What I'm ultimately trying to accomplish is to find the best way of ordering the leaf nodes in such a way that the most closely related nodes are closest to each other in the list. If I can find the spanning tree as described, I can easily order the leaf nodes in the way I need.

Can anyone point me to a solution to this problem other than just brute force optimization?

Note that the tree that I seek does not need to span all nodes in the graph, only all leaf nodes and the root node. Also I'm willing to adopt a solution that is not globally optimal if it avoids the need for a brute force search. At the moment I'm investigating an approach involving searching and pruning paths beginning at the leaf nodes.

Your problem is similar to the directed Steiner tree problem. In this problem we are given a directed graph, a set of terminal vertices and a specified root. The goal is to find a minimum cost tree that connects all terminal vertices to the root.

This is not exactly what you are asking for, but perhaps a solution to such a problem (or a suitable variant) is good enough.


What does an admissible numbering of computable functions look like? I'm trying to understand how we can construct an admissible ordering of the computable (meaning, partial recursive) functions.
Initially my take on such an enumeration was from the point of view of an enumeration of programs. For instance, we could enumerate all possible Turing machines using some set of rules (for instance, first the 1-state machines, then the 2-state machines, with some sort lexicographic order within each of the groups). Or alternatively, perhaps we could encode each program uniquely via some numbering system and then simply take them in increasing order.
These produce computable maps from $\mathbb{N}\to$ set of computable functions. But of course these are not bijections since multiple programs will compute the same function.
So my question is, for the purposes of something like Rice's theorem, how does one construct an admissible numbering of the computable functions?

The encodings you mention are admissible. Why do you think they need to be bijections?
In fact, there is no admissible numbering of partial computable maps that is a bijection. If there were one, we could decide equality if partial computable maps, which would allow us to implement the Halting oracle.


why is every self-reducible language in pspace I understand that every self reducible language recursively queries its oracle with strings of length less than the input size. But how does that show that every such language can be solved in polynomial space?

You haven't defined self-reducible languages, so I'll take as an example SAT, and let you generalize the idea.

In order to solve SAT, we use the following recursive procedure:

If there are no variables, output the value of the formula.
Set the first variable to TRUE, and simplify the formula. Recurse. If TRUE is returned, return TRUE.
Set the first variable to FALSE, and simplify the formula. Recurse. If TRUE is returned, return TRUE.
Return FALSE.

When we set the first variable to TRUE, we need to keep a copy of the formula. At depth $k$ of the recursion, we have $k$ formulas, the size of each at most the size of the original formula. So for a formula of size $n$ having $m$ variables, the total space usage is $O(nm) = O(n^2)$, which is polynomial in the input size.

For general self-reducible languages the same technique applies, with similar results. The details depend on your notion of self-reducibility.


NP-hardness of existence of spanning tree with given maximal degree I am trying to solve the following exercise:

Let $G = (V,E)$ be a graph. Show that the following two problems are NP-hard:

$G$ has a spanning tree where every node has at most $k$ neighbors, and $k$ is part of the input.

$G$ has a spanning tree where every node has at most 5 neighbors.

It's written that 1 is supposed to be a hint for 2. You can of course choose to ignore it and solve 2 directly.
I tried to reduce $k$-MST to Steiner tree, but I don't know if this is a right way. I read that can use a Hamiltonian circuit, but I don't understand how. Can anybody help me?

Hint for part 1: What does it mean when $G$ has a spanning tree where every node has at most 2 neighbors?

Hint for part 2: Suppose you know that it is NP-hard to show that $G$ has a spanning tree where every node has at most 2 neighbors. Can you reduce this problem of at most 2 neighbors to the current problem of at most 5 neighbors?

This post is made out of user53923's comment as I have verified it is useful.


Prove that if we take all the edges in directed graph that are on some shortest path from 1 to N we will get a DAG We are given directed weighted graph with edges having strictly positive weight(>0) with possibly some cycles with $N$ nodes and $M$ edges. Let's observe all the shortest paths from $1$ to $N$ in this graph, finding the single-source-shortest paths from $1$ in the normal graph and the single-source-shortest path from $N$ in the inverse graph we can check for each edge whether it belongs to some shortest path or not.

If we take all the edges that belong on some shortest path and build a separate graph we will get a directed acyclic graph. How can we prove that this graph will never have a cycle? I haven't written many proofs on graphs before, so I solved the problem, however I'm not sure why this will always hold.

Suppose there is a cycle $v_1v_2\ldots v_kv_1$ such that every edge in this cycle belongs to some shortest path. Suppose $v_1v_2$ belongs to the shortest path $1\ldots u_1v_1v_2u_2\ldots N$ and $v_2v_3$ belongs to the shortest path $1\ldots u_3v_2v_3u_4\ldots N$, then the weight of the path $v_2v_3u_4\ldots N$ is no greater than that of the path $v_2u_2\ldots N$1. Hence, $1\ldots u_1v_1v_2v_3u_4\ldots N$ is another shortest path.

Repeating similar argument for the edges $v_3v_4,\ldots,v_kv_1$, we can get a shortest path $1\ldots u_1v_1v_2\ldots v_kv_1u_{2k}\ldots N$. This is impossible because $1\ldots u_1v_1u_{2k}\ldots N$ is obviously shorter.

1 Otherwise the weight of the path $1\ldots u_3v_2v_3u_4\ldots N$ is greater than that of the walk $1\ldots u_3v_2u_2\ldots N$, which contradicts to the assumption that $1\ldots u_3v_2v_3u_4\ldots N$ is a shortest path.


Bellman-Ford: Find all nodes that have minus infinite distance to source Given a weighted, directed graph (V, E) may contains some negative cycles and a source node s, I would like to know for all node u, if there is a path from s to u but there is no shortest path from s to u (the distance from s to u is minus infinite). To do this I implemented a version of the Bellman-Ford algorithm:

Do V iterations of Bellman-Ford, save all nodes relaxed on Vth iteration to a queue `Q`
Do BFS with `Q` and find all nodes reachable from `Q`
All those nodes and only those can have infinite distance from `s`

Here is BFS:

visited(Q.first) = true
while Q not empty:
    u <- Q.deQueue()
    shortest[u] = 0 // there is no shortest path from `s` to `u`
    for all (u, v) in E:
        if not visited(v):
            visited(v) = true
            Q.push(v)

This algorithm is the best I can come up with and sadly it fails some test cases. I would be greatly appreciated if you guys can help, thanks.

Well after a morning of testing, I just figured out that my solution is RIGHT, the problem I had before is because of overflow (I use 10^19 to declare infinity for all vertices at the beginning and it can leads to overflow for some test cases).


Hash function which is invariant under small changes I am looking for a hash function which is invariant under small changes.

E.g., if I have two strings MyString and MySttring which slightly differ, their hash values should only differ slightly as well.

Actually, this is the opposite of the normal concept of a hash functions (Avalanche effect) where even slight changes in the input lead to big changes in the output.

Does any one know of such a concept or a hash function?
(It should not be the identity function ;))

Background:
I want to store personal data (name, surname, date of birth). Due to data privacy laws, it is not allow to store the data in clear text. So, I need to hash it.
There might be typing errors or OCR errors when storing the data. So, two hash values of the same person might differ. But they should only differ a little, so I know that the input data must have been very similar.

Use locality-sensitive hashing. Make sure you're not breaking the law.


Why superscalar processors use dynamic branch prediction I'm studying for an exam on Advanced Computer Architecture and in an exam question the question above is asked.

I know that branch prediction is crucial in superscalar processors in order to exploit ILP as much as possible, but I was wondering what could be the precise reason why superscalar processors use dynamic branch prediction instead of static one.

Update:

Hi again, as the two comments below suggested, I tried to think about it and thought that in case of a misprediction a processor using branch predictor has to flush the pipeline from the incorrect instructions issued because of the prediction.

So, for a superscalar processor issuing multiple instructions at the same time, the penalty would be much higher, but I'm still not sure this is the real point...

Any other help?

What you want from a branch predictor: Low implementation cost, prediction speed (you don't want to wait for branch prediction), and high accuracy (high percentage of correctly predicted branches).

So compare static and dynamic branch prediction: Dynamic branch prediction is more expensive, after all it needs to store the history of branches. Dynamic branch history is as fast as static prediction, but its accuracy is enormously higher.

The logical consequence is that when you build a chip that is going to be expensive and high performance anyway, you are not going to scrimp on the cost of branch prediction and use the more accurate method.

And look at Pseudonym's comment: Look at what a static branch predictor does, and see why it will be often less good than dynamic prediction. (Not always. Any dynamic branch prediction can be tricked into always predicting wrong).


Can an LL(k) parser parse any grammar without left recursion or common prefixes? I'm being asked to create a "top down grammar" for a certain language (I'm pretty sure there's no such thing as a "top down grammar" but I think it means write a grammar that an LL(k) parser can parse).

I'm pretty sure the language is not LL(1), but I can remove left-recursion and common prefixes from it and still have an unambiguous grammar. But I'm a little confused about the significance of that. If I successfully removed left-recursion and common prefixes and the grammar is still unambiguous, is the language LL(k)? And does that mean it can be parsed by a top-down parser?

A 'top down parser' is usually understood to be a hand-written $LL(1)$ parser, or $LL(k)$ for some low $k$, which would explain the use of this terminology. These two concepts are therefore essentially the same.

I'm unsure what you mean exactly by 'common prefixes' - I guess you are talking about common lookaheads. If you ensure that you can always uniquely distinguish which production you need to expand by looking at the next letter, then your language is $LL(1)$ (and also contains no left recursion). Doing that usually means you change your grammar structure a bit so your parser is never confused by 'k letter prefixes' of the part of the input that you haven't looked at yet.

If you are really talking about common prefixes in the language-theoretic sense, then all your words would have to start with a unique letter, which means your language is finite and therefore $LL(1)$.


Why did Alan Turing have to define computation before demonstrating undecidability? It seems to me that Turing could've just presented the following argument:

Theorem: Given a computational model $\mathcal{M}$ capable of conditional branching and indeterminate repetition the halting problem of $\mathcal{M}$ is undecidable from within $\mathcal{M}$.

Proof: Suppose $H$ solves the halting problem in $\mathcal{M}$. Namely $H\in\mathcal{M}$ and
$$
H(A) =
\begin{cases}
1 & \text{if $A(A)$ halts}\\
0 & \text{if $A(A)$ doesn't halt}
\end{cases}\qquad\forall A\in\mathcal{M}
$$

Then construct
$$
\begin{split}
\overline{H}(A)
& =
\begin{cases}
\infty & \text{if $H(A) = 1$}\\
0 & \text{if $H(A) = 0$}
\end{cases}\\
& =
\begin{cases}
\infty & \text{if $A(A)$ halts}\\
0 & \text{if $A(A)$ doesn't halt}
\end{cases}
\end{split}
$$
($\infty$ indicates an infinite loop. The $0$ could've just as well been a $1$ without affecting the argument.)

Because $H\in\mathcal{M}$ so is $\overline{H}$. After all, it only adds conditional branching and an infinite loop. So we can ask whether $\overline{H}(\overline{H})$ halts - yielding a contradiction in either case. $$\tag*{$\Box$}$$

It seems to me that with this argument Turing could've just said "I don't care how you define computation. Try coming up with the most powerful notion you can conceive of, then run through this argument, and voila, there's still undecidable problems."

Without fixing a concrete model of computation, you can't show that you can actually do the "then construct" part of your argument, so it's not a proof.