Shortest path algorithm using Dijkstra with Fibonacci heap Given an undirected connected graph $G=(V,E)$ with positive weights, where $|V|>2009$, and each vertex is of degree of at most $10$.
Give an efficient algorithm to find the $2009$ closest nodes to a given source vertex $s$ (with respect to edge weight).

Is it correct to say that Dijkstra's algorithm with Fibonacci heap will run in $\mathcal O(\log V)$?

Reasoning:
Dijkstra's algorithm with Fibonacci heap runs in $\mathcal O(E+V\log V)$. the amount of vertices pulled out of the heap is $2009$, and the amount of key decreased is at most $2009*10$. Therfore the running time of Dijkstra's algorithm for this case is $\mathcal O(2009*10+2009 \log V)=\mathcal O(\log V)$

I do not think you can take $|V| = 2009$ because you are saying that $|V|>2009$, which means that in the best case $V = 2010$ but it does not say anything about the worst case (which is what big oh notation is about). So you cannot say that $|V|$ is constant as is implied in your question.

The correct process would be this: $O(|E| + |V| log |V|) = O(|V|*10 + |V| log |V|) = O(|V| + |V| log |V|)$
The only assumpution you can make is that $|E| = |V|*10 = |V|$. Remeber that you should only get rid of a variable in asymptotic notation if it is equal to a constant.

You can safely assume that $|E| = |V|*10$ because in the worst case every node will have 10 edges as stated in your question.

According to your reasoning dijkstra algorithm will only need overall 2009 extractions from the heap because you are looking for 2009 nodes close to $s$. That is not correct because is not possible in the algorithm to know beforehand which will be the exactly 2009 nodes that are close, say for example that the cheapest node $c$ has a shortest path of length $k$ and $k > 2009$, where $k$ is the number of nodes in the shortest path. Dijkstra algorithm will need to transverse the previous nodes and that will require more than 2009 operations in the heap because you have to process the nodes to reach node $c$ first.

Example:

Suppose you do not want to find 2009 closest nodes but 4 and that our source vertex is $7$, so following your question there should be overall 4 operations to get the 4 closest nodes. Given the following graph:

When you start the algorithm node $7$ is pushed into the heap, then nodes $0,1,2,3$ are pushed, in this case the number of times the nodes are pushed is the same number of times the nodes are popped from the heap (which may not be the case), now, as the algorithm proceeeds it will push nodes $4$ and $5$ until it reaches $6$ which in fact, is the closest node to $s$, if the path to node $6$ would have been longer a bigger number of push/pops would have been done in the heap. In a extreme case between node $3$ and $6$ there may be 90 nodes so that number of operations must be done in order to reach node $6$ which totally exceeds $4$ which is what is stated in your question.

The assumption that for every node $i$ that is extracted from the heap after any node $x$ follows that $d(s,i) > d(s,x)$ (where is $d(u,v)$ is the cost of the shortest path from $u$ to $v$) is not correct, because is possible that in the future you may insert another node into the heap that has a smaller distance, in fact that is what makes dijkstra algorithm actually compute optimal paths.


Maximise sum of "non-overlapping" numbers in square array - help with proof A question was posted on Stack Overflow asking for an algorithm to solve this problem:

  I have a matrix (call it A) which is nxn. I wish to select a subset
  (call it B) of points from matrix A. The subset will consist of n
  elements, where one and only one element is taken from each row and
  from each column of A. The output should provide a solution (B) such
  that the sum of the elements that make up B is the maximum possible
  value, given these constraints (eg. 25 in the example below). If
  multiple instances of B are found (ie. different solutions which give
  the same maximum sum) the solution for B which has the largest minimum
  element should be selected.

  B could also be a selection matrix which is nxn, but where only the n
  desired elements are non-zero.

  For example: if A =

|5 4 3 2 1|
|4 3 2 1 5|
|3 2 1 5 4|
|2 1 5 4 3|
|1 5 4 3 2|

  => B would be

 |5 5 5 5 5|

I proposed a dynamic programming solution which I suspect is as efficient as any solution is going to get. I've copy-pasted my proposed algorithm below.

Let $A$ be a square array of $n$ by $n$ numbers.
Let $A_{i,j}$ denote the element of $A$ in the ith row and jth column.
Let $S( i_1:i_2, j_1:j_2 )$ denote the optimal sum of non-overlapping numbers for a square subarray of $A$ containing the intersection of rows $i_1$ to $i_2$ and columns $j_1$ to $j_2$.

Then the optimal sum of non-overlapping numbers is denoted S( 1:n , 1:n ) and is given as follows:

$$S( 1:n , 1:n ) = \max \left \{ \begin{array}{l}  S(   2:n , 2:n   ) + A_{1,1} \\
                             S(   2:n , 1:n-1 ) + A_{1,n} \\
                            S( 1:n-1 , 2:n   ) + A_{n,1} \\
                            S( 1:n-1 , 1:n-1 ) + A_{n,n} \\
                            \end{array} \right.$$

Note that S( i:i, j:j ) is simply Aij.

That is, the optimal sum for a square array of size n can be determined by separately computing the optimal sum for each of the four sub-arrays of size n-1, and then maximising the sum of the sub-array and the element that was "left out".

S for |# # # #|
      |# # # #|
      |# # # #|
      |# # # #|

Is the best of the sums S for:

|#      |      |      #|      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |      #|       |#      |

This is a very elegant algorithm and I strongly suspect that it is correct, but I can't come up with a way to prove it is correct.

The main difficulty I am having it proving that the problem displays optimal substructure. I believe that if the four potential choices in each calculation are the only four choices, then this is enough to show optimal substructure. That is, I need to prove that this:

|   #    |
| #   # #|
| #   # #|
| #   # #|

Is not a valid solution, either because it's impossible (i.e. proof by contradiction) or because this possibility is already accounted for by one of the four "n-1 square" variations.

Can anyone point out any flaws in my algorithm, or provide a proof that it really does work?

Actually, I don't believe your proposed solution is correct. An example where you might need this case

|   #    |
| #   # #|
| #   # #|
| #   # #|

might be

| 1 2 1 1|
| 2 1 1 1|
| 1 1 1 2|
| 1 1 2 1|

The optimal solution consists of all 2s, while there are only 1s in the corners; therefore, you cannot find an optimal solution just by starting at the corners.


Error in Generating Function Solution I am currently working my way through An Introduction to Analysis of Algorithms to stay sharp with recurrences as well as learn generating function techniques. However my analyses and the books analyses for the first few sample problems on ordinary generating functions differ. I've checked and rechecked [my work as well as errata on the webpage], but cannot see how the authors made certain leaps. For example:

Given the recurrence $a_{n} = a_{n-1} + 1$ for $n \geq 1$ with $a_0 = 0$ and letting $A(z) = \sum_{n \geq 0} a_n z^n$ I have the following steps:
$$ \begin{align*}
\sum_{n \geq 1} a_n z^n &= \sum_{n \geq 1} a_{n-1} z^n + \sum_{n \geq 1} z^n \\
A(z) - a_0&= zA(z) + \frac{z}{1-z} \\
A(z)(1 - z) &= \frac{z}{1-z} + a_0\\
A(z) &=\frac{z}{(1-z)^2} + \frac{a_0}{1-z}
\end{align*}$$

Since $a_0 = 0$ we just end up with $$A(z) = \frac{z}{(1-z)^2} \\ a_n = n$$.

However, the authors' derivation is the following:
$$ \begin{align*}
\sum_{n \geq 1} a_n z^n &= \sum_{n \geq 1} a_{n-1} z^n + \frac{1}{1-z} \\
A(z) - 1 &= zA(z) + \frac{1}{1-z} \\
A(z) &= \frac{z}{(1-z)^2} \\
a_n &= n\\
\end{align*}$$
Am I crazy, how did they get $A(z) - 1$ in the 2nd step? They do the exact same thing in the next example for $a_n = 2a_{n-1} + 1$. Is this just a typo? I would expect them to subtract $a_0z^0 = a_0$. Where did that $-1$ come from?

This answer is just so that the question is not left unanswered.

The OP is correct: the book got it wrong.


Can I use "XORing" in my thesis? I'm currently writing my bachelor thesis and explain some algorithms where the XOR-operation is used.

Can I use "XORing" or "XORed" in my thesis or is this too informal?

For example: "xoring the plaintext with the stream cipher results in the cypher text" and "the plaintext is XORed with the stream cipher..."

Also what would be the correct way to write it? Completly lowercase or with an uppercase XOR?

Hope this is the right community to ask this question.

Some useful guidelines for writing are:

Who is my audience?
Will my audience understand what I am writing?
Will my usage of language be distracting or otherwise take attention away from the message I'm trying to make?

In this case, your audience is probably another computer scientist who has at least some knowledge of your area.  Therefore, yes, I would expect that another computer scientist will understand your meaning if you write "XORing" or "XORed".  Also, it's common enough that I don't think it will be distracting.  Whether it's too information is perhaps a bit subjective, but I don't view it as too informal.

I've seen it both ways: "xoring" and "XORing".  Personally, I find the all-caps jarring, so my eye prefers "xoring", but I think that is a matter of taste.

Note that "ciphertext" is normally spelled that as one word, and with an "i", not a "y".  Right: "ciphertext".  Wrong: "cyphertext", "cypher text", "cipher text".


What are the disadvantages of Fibonacci Heaps? A Fibonacci heap is a data structure for priority queue / heap operations. It seems to have the best complexity for all operations:

Since it has the best performance, why not use it everywhere?
What are the disadvantages of it?

$O(1)$ merely means that no matter how large your heap grows, the operation will always take roughly the same time to execute. It doesn't mean "the fastest".
Wikipedia article you linked has section named "Practical considerations":

Fibonacci heaps have a reputation for being slow in practice due to
large memory consumption per node and high constant factors on all
operations. Recent experimental results suggest that Fibonacci heaps
are more efficient in practice than most of its later derivatives,
including quake heaps, violation heaps, strict Fibonacci heaps, rank
pairing heaps, but less efficient than either pairing heaps or
array-based heaps.


Decide whether a DFA accepts the empty language Let $X = \{\langle M \rangle\ |\ M\text{ is a finite state machine and }L(M) = \emptyset\}$ where $\langle M \rangle$ is an encoding of the
machine $M$.  Is $X$ Turing decidable?  Why or why not?

Re-read your textbook chapter on DFAs and NFAs -- you'll find everything you need to know there.

See also the following questions, which both have answers to your question embedded in their answers (make sure to read carefully):

Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?
Undecidable among these for turing machine

Next time, tell us what you have tried, to solve the exercise on your own.


generating all pairs suppose I have 6$\{0,1,2,3,4,5\}$ numbers.I should generate following 4 pairings of numbers where there will be 3 pairs in each pairing s.t

each number should be in one pair and also every number should be paired
a pair(like 0-1) should be present in only one of the pairing. and also every possible pair should be present somewhere

i)   0-1   , 2-3  ,4-5

ii)  0-4   , 1-2  ,3-5

iii) 0-3   , 1-4  ,2-5

iv)  0-2   , 1-5  ,3-4

v)   0-5   , 1-3  ,2-4

similarly if I have N numbers. I need $(N-1)$ pairing of numbers s.t  in each pairing there are $N/2$ pairs.

essentially this is grouping $\binom{n}{2}$ combinations into  $n-1$ groups s.t each number is present exactly once in each group

As pointed out by @Pseudonym, this problem is identical to finding a round robin tournament schedule. A straightforward implementation would be the following:

def get_sets(a: list):
    # Simple implementation of
    # https://nrich.maths.org/1443
    center, *rest = a
    for _ in range(len(rest)):
        rest = rest[1:] + rest[:1] # put 1st element to back of list
        solution = [[center, rest[len(rest) // 2]]] # combine middle element with center
        for i in range(len(rest) // 2):
            solution.append([rest[i], rest[~i]]) # combine i-th element from front with i-th from back
        yield solution

for s in get_sets(list(range(50))):
    print(s)

Note that this implementation creates a new list for each "set" in the output.
This is not strictly necessary, as the same result could be achieved by using only the initial list (actually array) and use smart indexing.


TSP Variant --- Colored Path Recently I came up with a traveling-salesman-esque problem. As usual, we have $n$ vertices, and a weighted edge between any two vertices. However, each vertex is associated with a color, which may be repeated. Then, you are given a sequence of colors, and you want to find the shortest path that follows this sequence. If all vertices are the same color, this is the same as TSP. However, if all vertices are different colors, there is only one solution.

Is this variant at all studied? Let $c$ be the maximum number of vertices which are the same color. Is the decision problem this variant NP-complete for some fixed, $c$, or alternatively is there a simple way to solve the decision problem polynomially for any finite $c$? Alternatively, one can bound $k$, the mamximum amount of times a given color appears in your path.

For $k=1$, it is polynomial. WLOG we can assume the path goes through colors $1,2,3,\ldots,x$. For each vertex of color 1, we consider each edge to a vertex of color 2. We keep track of the shortest path from color 1 to each vertex of color 2. Rinse and repeat for each color. This only requires $|\mathrm{color}\  i||\mathrm{color}\  i+1|$ additions and comparisons to get the shortest paths to each vertex of color $i+1$.

Additionally, I realize $k$ only matters if it is less than $c$, so bounded $c$ is polynomial if bounded $k$ is polynomial and bounded $k$ is NP-Complete if bounded $c$ is NP-Complete.

In this answer we prove the colored path problem is NP-hard for $c\ge 7$. I don't know whether it is NP-hard for $2\le c\le 6$. Without loss of generality, we prove the NP-hardness for  the Hamiltonian Path problem variant, i.e., asking whether there exists such a colored Hamiltonian path, insteand of the TSP variant.
We use the normal reduction from 3SAT (with $n$ variables and $m$ clauses) to Hamiltonian Path with the following changes:

For each variable, we only have $2m$ nodes: $v_1,v_2,\ldots,v_{2m}$. The $i$th clause corresponds to nodes $v_i,v_{i+1}$ and $v_{2m-i+1},v_{2m-i}$, i.e., if the $i$th clause contains the positive literal of this variable, we have the path $v_i\rightarrow c_i\rightarrow v_{i+1}$, where $c_i$ is the node corresponding to the $i$th clause; and if the $i$th clause contains the negative literal of this variable, we have the path $v_{2m-i+1}\rightarrow c_i\rightarrow v_{2m-i}$. In addition, we add a blank node $b_i$ between $v_i$ and $v_{i+1}$.

For each variable, for each $i$, we give $v_i$ and $v_{2m-i}$, $b_i$ and $b_{2m-i}$ the same color. In addition, we give $c_i, b_i, b_{2m-i}$ the same color if the variable is contained in the $i$th clause.
The following graph is constructed from $(x_1\vee \neg x_2\vee x_3) \wedge(x_2\vee \neg x_3\vee \neg x_4)$. The number above a node represents its color.

We remove the edges to the sink node $t$. Instead, we add paths that pass through the blank nodes that may potentially not be visited due to visits of clause nodes. In the example above, the added edges form the following structure.

In the example above, we ask whether there is a Hamiltonian path with colors 1-2-3-4-5-4-3-2-6-3-7-8-7-3-6-...-11-3-8-14. You can check this reduction indeed works.


How can blank be written on the tape if it is not part of input alphabet? I have read that input alphabet of Turing machine is subset of tape symbols because in input alphabet we don't allow blank symbol. But when ever there is a transition to final state the transition as (Blank,Blank,R/L) (First parameter here is input,second is what machine will write on tape,third is direction).It means whenever we have processed input,we will read Blank and replace Blank by Blank and goto final state.But how can blank be written on the tape if it is not part of input alphabet?

With this knowledge I am trying to answer the following statement

"It is decidable that Turing machine will print some non blank character
".

Because Turing machine will always write something on the tape so it should be decidable. But is it possible that there are only two states and there is only one transition as "(Blank,Blank,R/L)"?

The formal definition of a turing machine is a 7-tuple $(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$, where:

$Q$ is a finite set of states.
$\Sigma$ is a finite set of input symbols (input alphabet).

$\Sigma$ does not contain the blank symbol ($\sqcup$).

$\Gamma$ is a finite set of tape symbols (tape alphabet).
$\sqcup \in \Gamma$ and $ \Sigma \subseteq \Gamma$.
$\delta : Q^\prime \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} $ is the transition function.

$Q^\prime = Q - \{q_{\text{accept}}, q_{\text{reject}}\}$

$q_0 \in Q$ is the start state.
$q_{\text{accept}} \in Q$  is the accept state.
$q_{\text{reject}} \in Q$ is the reject state.

The part you want to pay attention to is the definition of the transition function:

  $\delta : Q^\prime \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} $

Note that the transition function accepts inputs that are of the tape alphabet, and writes output that is also of the tape alphabet.

The turing machine is decidable only if it recognizes some language L and and halts for every input.


On the recurrence $T(n) = T(n/a) + T(n/b) + n^c$ Consider the recurrence
$$T(n)=T(\tfrac{n}{a}) + T(\tfrac{n}{b})+O(n^c).$$
What is the condition on $a,b$ that guarantees $T(n)=O(n^c)$?
With substitution I get
$$T(n)=T(\tfrac{n}{a}) + T(\tfrac{n}{b})+O(n^c)\le (\tfrac{n}{a})^c +  (\tfrac{n}{b})^c + n^c =  n^c ((\tfrac{1}{a})^c +  (\tfrac{1}{b})^c + 1)$$
I need $(\frac{1}{a})^c +  (\frac{1}{b})^c + 1$ to be less than one if I want to show that it is $\le n^c$.
So $\frac{1}{a^c} +  \frac{1}{b^c} \le 0$. But I have trouble with that and I don't know if my idea of showing this is right.

Suppose that $$ T(n) = T(n/a) + T(n/b) + n^c. $$
Let's try to prove by induction that $T(n) \leq Mn^C$:
$$
T(n) \leq M(n/a)^c + M(n/b)^c + n^c = \left((a^{-c} + b^{-c})M + 1 \right) n^C.
$$
Therefore we need $(a^{-c} + b^{-c})M + 1 \leq M$, which we can satisfy as long as $a^{-c} + b^{-c} < 1$.
When $a^{-c} + b^{-c} = 1$, the answer is likely $T(n) = \Theta(n^c\log n)$.


How does one generate all the terms of a multivariate polynomial algorithmically? I was interested in writing a program that given the number of variables and the degree of the multivariate polynomial, it was able to output the multivariate polynomial itself or evaluate it at a specific point (in reality I will feed it vectors with a value for each polynomial and I want to evaluate the polynomial). So here is an example input output in pseudocode:

f(variables=[x1,x2],Degree=D) = 1+x1+x2+x1x2+x1^2+x2^2

when there is a general number of variables and Degree it gets tricky.

I noticed that this problem is equivalent to considering tuples/sequences with that satisfy the following:

$$ S_D = \{ (d_0, ..., d_N) : \sum^N_{i=0} d_i = D \}$$

then my answer would be the set:

$$ S^{*}_D = \cup^D_{d'=0} S_{d'} = \{ (d_0, ..., d_N) : \sum^N_{i=0} d_i \leq D \} $$

I started with an example to try to actually compute that set, say degree 3 and 3 variables. I considered N = 3 and got the tuples:

(3,0,0), (0,3,0), (0,0,3)
(2,1,0), (2,0,1)
(0,2,1), (1,2,0)
(0,1,2), (1,0,2)

I also tried higher numbers but I didn't really see an obvious way to generalize it wrt to N or D. Any hints on how to do it? (Also the full solution is welcome so I can implement it for my real task)

You can generate all non-negative integer solutions to $d_0 + \cdots + d_N \leq D$ recursively. The recursion is as follows:

If $N = 1$, generate $0,1,\ldots,D$.
Otherwise, for each $d_N \in \{0,1,\ldots,D\}$, generate all solutions for $N:=N-1$ and $D:=D-d_N$, and append $d_N$ to all of them.

If you don't like recursion, you can also implement this iteratively. Start with the zero solution, and repeatedly try to "increment" it. To increment a solution, find the largest $i$ such that $d_0 + \cdots + d_i < D$ (if any; otherwise, you're done), increment $d_i$, and set $d_{i+1} = \cdots = d_N = 0$. This generates all solutions in lexicographic order.

As an optimization, you can store and update the running sums $s_i = d_0 + \cdots + d_i$ to speed up the procedure. This optimization should make the increment routine run in amortized $O(1)$ time.


A state machine that is either DFA or NFA: is it possible? I am studying Crafting Interpreters, and although I understand the responsibility of the Scanner (or Lexer), I still cannot understand if it is a deterministic finite automaton or non-deterministic finite automaton. The code responsible for scanning the input text in the book is:
    private void scanToken() {
        char c = advance();
        switch (c) {
            case '(': addToken(LEFT_PAREN); break;
            case ')': addToken(RIGHT_PAREN); break;
            case '{': addToken(LEFT_BRACE); break;
            case '}': addToken(RIGHT_BRACE); break;
            case ',': addToken(COMMA); break;
            case '.': addToken(DOT); break;
            case '-': addToken(MINUS); break;
            case '+': addToken(PLUS); break;
            case ';': addToken(SEMICOLON); break;
            case '*': addToken(STAR); break;
            case '!':
                addToken(match('=') ? BANG_EQUAL : BANG);
                break;
            case '=':
                addToken(match('=') ? EQUAL_EQUAL : EQUAL);
                break;
            case '<':
                addToken(match('=') ? LESS_EQUAL : LESS);
                break;
            case '>':
                addToken(match('=') ? GREATER_EQUAL : GREATER);
                break;
            case '/':
                if (match('/')) {
                    while (!isAtEnd() && peek() != '\n') {
                        advance();
                    }
                } else if (match('*')) {
                    do {
                        if (peek() == '*' && peekNext() == '/') {
                            advance();
                            advance();
                        } else {
                            advance();
                        }
                    } while (!isAtEnd());
                } else {
                    addToken(SLASH);
                }
                break;
            case ' ':
            case '\r':
            case '\t':
                // Ignore whitespace.
                break;
            case '\n':
                line++;
                break;
            case '"': string(); break;
            default:
                if (isDigit(c)) {
                    number();
                } else if (isAlpha(c)) {
                    identifier();
                } else {
                    Lox.error(line, "Unexpected character.");
                }
                break;
        }
    }

According to several sites out there, the FA definition is:

Finite Automata(FA) is the simplest machine to recognize patterns.The
finite automata or finite state machine is an abstract machine which
have five elements or tuple. It has a set of states and rules for
moving from one state to another but it depends upon the applied input
symbol. Basically it is an abstract model of digital computer.
Following figure shows some essential features of a general
automation.

A DFS consists of the following:
Q : Finite set of states.
Σ : set of Input Symbols.
q : Initial state.
F : set of Final States.
δ : Transition Function.

and for NFA:
Q : set of all states.
Σ : set of input symbols. ( Symbols which machine takes as input )
q : Initial state. ( Starting state of a machine )
F : set of final state.
δ : Transition Function, defined as δ : Q X Σ --> Q.

My lexer can start in any state, does that mean it is either DFA or NFA? How can I conclude if it is one or the other?

Any piece of code can never be non-deterministic (a non-deterministic process can "multiply itself" by a constant factor every step, and obviously computers can't just multiply by their own free will).
Hence it is a DFA.

Also, your lexer will start always at the initial state $s_0$, and from it, depending on what it reads - it moves to different states.


What is "extended polynomials" I've heard that the functions that are definable in simply-typed $\lambda$-calculus is the class of extended polynomials.

However, it is still not clear to me what exactly is extended polynomials. Could someone explain that to me? Some pointers would be good as well.

Thanks.

It turns out the definition is straightforward as seen in [1]. And as an example, exponentiation is not definable in simply-type $\lambda$-calculus.

  The class of extended polynomials is the smallest class of func- tions
  over N which contains:

  the constant functions: 0 and 1,
  projections,
  addition,
  multiplication,
  the function ifzero(n, m, p) = if n = 0 then m else p

Definable functions in the simply typed lambda-calculus by M. Zakrzewski (2007)


Generating a random minimum spanning tree I am tring to find the simplest method of generating a random minimum spanning tree.

My intention is to randomly generate a Level in a game where there are n amount of fixed sized rooms existing on a grid which all connect together in a random way.

One method I have come across is to generate random points on a grid and run a Randomized incremental Delaunay triangulation algorithm (Explained quite nicely here) on it with the weights of the nodes being determined by their distances from eachother. Couple this with Kruskal's algorithm and then I will have my minimum spanning tree.

I'm relatively new to this field of Maths and was having trouble creating the Delaunay algorithm (and even more trouble understanding some libraries out there) and thought perhaps there is a simpler method to get the same result.

One method that came to mind was to create a fully connected graph of random points (much simpler for me to do) and then run Kruskal's algorithm on that, However my intuition tells me that this would not be so efficient even though I am only talking about a maximum of 10 or 15 nodes for my intended use.

Are there any other methods I should consider to generate such a graph?
I've come across the Prüfer sequence which seems incredibley simple, however with my current understanding of it I do not see how I can take into account the positions of the Rooms/Nodes on the grid or perhaps even chose where to place the nodes on the grid.

Since there are just about 10 random points, the following simplest algorithm is should be fast and easy enough for your need.

Generate random points $p_i$, $0\le i\le9 $ in the grid, in whichever way you prefer.
Compute all Euclidean distances between each pair of points. (In fact, I believe for your purpose, the Manhattan distance should be fine as well. What is nice about Manhattan distance is that it is much easier to code and compute. The MST generated will be roughly the same.)
Compute the MST of the points with the distances between them.

There are many existing libraries that computing MST. You can just select any popular one that is convenient for you. I guarantee you that they will be fast enough for your need.


What Exactly Does the Term "Key" Mean with Regards to a Hash Table? I know it is supposed to be some arbitrary term that is a stand-in for a large class of possible objects.

But I still don't understand what part of the array the term "key" is meant to represent or denote.

Does it mean an element of the array? The index of the element of the array? Some arbitrary function from the elements of the array to some subset of the natural numbers?

EDIT: Since many people seem not to understand the question, here is a quote from Introduction to Algorithms by Cormen et al.

  "With direct addressing, an element with key $k$ is stored in slot
  $k$. With hashing, this element is stored in slot $h(k)$; that is, we
  use a hash function to compute the slot from key $k$. Here $h$ maps
  the universe $U$ of keys into the slots of a hash table $T$... We also
  say that $h(k)$ is the hash value of key $k$."

It seems to me that the key, element index, and hash value are all different based on this.

Here is where the term is introduced in the chapter for the first time in a formal manner:

  "Suppose that an application needs a dynamic set in which each element has a key drawn from the universe $U=\{0,1,\dots,m-1\}$, where $m$ is not too large. We shall assume that no two elements have the same key."

From this I would draw the conclusion that a universe of keys cannot exist for a multiset of integers which allows duplicate values, since the former is a finite set which is in bijection with all possible elements of the array (implying that the set of all possible elements of the array is finite), whereas the latter has no bound on its cardinality (since it can increase in size with every operation, hence the "dynamic", and there is no bound to the number of elements which can be added because (1) duplicate elements are allowed and (2) the number of possible integers is infinite).

Context:

For instance, when discussing the "pth-smallest key" algorithm, you want to find the "key" with the pth-smallest "rank" -- so the "rank" is different from the "key", and you want to sort the "ranks" of the "keys", but usually the "keys" are numbers too, so why not sort them? And why would there be a "rank", a "key", a "hash value", an array element, and an array element index?

As another example of where seemingly imprecise terminology is confusing me, consider a dynamic multiset $S$ of integers which allows duplicate values. Would this object allow a hash function? If it would, what would be the "keys", and what would be the "hash values"? Both the universe of keys and the target space for the hash function are supposed to be finite, whereas $|S|$, the cardinality of $S$, is clearly potentially unbounded, and in fact any integer can appear arbitrarily many times -- so how could anything associated with this problem be a "key"?

It is seemingly similar to other problems that admit hash functions.

Their difference is the role that they have in the ordering and addressing of the table. The key is used to address a specific object (it's usually calculated using some algorithm or hashing function), while the rank is used to order objects and their respective keys using a specific ranking rule.


Prove: If $T'$ is not a MST one of its edges may be replaced by a lighter edge in order to get a lighter spanning tree Prove: If $T'=(V,F')$ is a spanning tree, but not a MST of $G=(V,E)$, then there are edges $e' \in F'$ and $e \in $ $E$ \ $F'$ such that $w(e)<w(e')$ and $T'$ \ $\{e'\} \cup \{e\}$ is a spanning tree.
My idea:
Let $T=(V,F)$ be a MST of $G$
for all $e \in T$, try to insert it into $T'$ and see if there is an edge in the cycle created that is heavier than $e$. If we found such $e$ we are done.
If not, define $G'=(V,F \cup F')$
This graph obviously has a MST, because $F \subset F' \cup F$
We didn't find a suitable $e$ in the previous part so all edges in $F$ may be colored in red in the generic algorithm for finding a MST in the graph $G'$.
That means there is a MST $T''=(V,F'')$ such that $F'' \subseteq F'$ but that is impossible because $T'$ is not a MST of $G'$, because $T$ is lighter (by definition $w(T)<W(T')$)
Does that seem correct?

I have a proposal for a proof that doesn't involve "coloring" since it sounds vague.
Let $T' = (V,F')$ be a spanning tree but not a MST of $G=(V,E)$. Let $T = (V,F)$ be a MST of $G$.

You already did the following:
Now go through all $e \in F-F'$ and add $e$ to $T'$. Resulting graph contains a cycle if there is another edge $e'$ on the cycle such that $e\neq e',w(e) < w(e')$ we are done because $T'$ could be augmented.

My approach for the rest using Kruskal's algorithm:
Otherwise we construct a graph $G' = (V,F'\cup (F-F')) = (V, F'\cup F)$.
For all $e \in F-F'$ and for all cycles $e$ lies on (in $G'$) $e$ is clearly one of the edges with the max weight.
Now run Kruskal's algorithm on $G'$ with a modified sorting procedure. Every edge is primarily sorted by its weight and secondary by the boolean if it belongs to $F'$ or not in such a way that for two edges with different weights the edge with the least weight comes first, but if two edges have the same weight the one belonging to $F'$ comes first (if both belong to $F'$ the order doesn't matter).
We are allowed to make this modification to the sorting procedure because Kruskal's algo doesn't care in which order edges with equal weight appear.
The algorithm proceeds to sort all edges in mentioned order. Thus for every cycle in $G'$ all edges in the cycle are considered before the an edge $e\in F- F'$ is considered. Since we know that Kruskal's algo connects two nodes always when they do not create a cycle and we know that edges $F-F'$ are considered last for every cycle the MST found by the algo is $T' = (V,F')$.
Contradiction:
But from our assumption we know that the weighted sum of $T$s edges is clearly lower than that of $T'$s edges and that $T$ is a spanning tree of $G'$. So actually $T$ is the MST of $G'$. Thus we have a contradiction and can conclude that there must be an $e \in F- F'$ such that it augments $T'$.


Reduction from Maximum Independent Set to Independent Set Decision Problem I was hoping someone would be able to help me with this question.

The Maximum Independent Set search problem is, given an undirected graph G, to output an independent set in G of maximum size.

Give a polynomial time algorithm for the Maximum Independent Set search problem which can use an oracle that solves instances of the Independent Set decision problem.

I can't see how you would do this without inputting every possible combination of the vertices into the Independent Set Problem, which obviously won't be polynomial time.

It is certainly possible to do so, as every $\mathcal{NP}-$complete problem is self-reducible.

Let us first remember the definition of decisional maximum independent set: given an undirected graph $G=(V,E)$ and $k \in \mathbb{N}$, does there exist $S \subseteq V$ with $|S| = k$ such that $\forall x,  y \in S \ . \ (x, y) \notin E$ ?

By a standard binary search argument, we can find the size of the maximum independent set with a polynomial number of queries to that oracle.

Let $s$ be the size of the maximum independent set of $G$. We pick some $v \in V$ and we use our construction to determine the size of the maximum independent set of $G \setminus v$. That can be either $s$ or $s-1$. If it's $s$, then there exists a maximum independent set in $G$ that does not include $v$, therefore we can exclude $v$ from our search.

Eventually, we'll reach a point where we can't exclude any other node. That means that the remaining nodes form a maximum independent set.


What is the minimum pumping length of the following languages? How to determine the minimum pumping length of union of two languages?  How do I proceed after determining the individual pumping lengths?

0*1+0+1* U 10*1 - Here the minimum pumping length of the first expression is 1 and of the second is 2. I am  stuck here ! Now what do I do?
001 U 0*1* : The min PL of first expression is 4 and of the second is 1 , now what's the overall minimum PL?

I understand that a pumping length for a language $K$ is a constant $c_K$ such that each string that has at least that language can be pumped within the language. Here "pumped" can remain somewhat abstract: it may be regular or context-free "uvwxy" pumping for instance.

It is clear that we can take $c_{K\cup L}\le \max\{c_K,c_L\}$. Any string in $K\cup L$ of at least this length can be pumped within either $K$ or $L$ depending or where it comes from.

It seems we cannot say more than that. The main reason is that we can pump one language into the other. Look at a variant of your last example. If $K$ is finite, say it contains all words shorther than $m$, then $c_K = m$, as no word in $K$ can be pumped. Let $L$ be the complement of $K$ containing all words of length at least $m$. Then $c_L = m+1$ (assuming that pumping incluses "pumping down" where we obtain shorter strings). However $c_{K\cup L}=c_{\Sigma^*}=1$.

I am afraid that for concrete examples you have to do a separate analysis.


Why is Oracle Turing Machine important? As you know, an Oracle Turing Machine (OTM) is a "black box" which somehow can tell us whether a given Turing machine with a given input eventually halts. By Church's Thesis it is impossible to design an algorithm which is able to solve such a problem.

If we will never get such a black box then why is it important and, in computer science, do they talk about it?

Why are oracles used in the context you mentioned (where we have an oracle for the halting problem)?  Because that allows us to answer questions that are fascinating, questions like "Are there problems that are even harder than the halting problem?".  I'm not saying these questions are necessarily useful or important in practice -- but they are fascinating, fun, and lead to a deep theory.  Just as not all art has to be directly useful, not all theory has to be directly useful.

Why are oracle Turing machines important, more broadly?  They are used widely in computer science theory, to help us study the relative difficulty between different problems.  They help us encode the notion of Turing reductions.  They help identify some barriers to proving results in complexity theory, like proving that $P \ne NP$ (see e.g. relativizing proofs).  They are useful in other places as well.

See also Are there any existing problems that wouldn't be solvable with a halting oracle?, Are all undecidable/uncomputable problems reducible to the Halting problem?, and Reductions among Undecidable Problems.


Can this algorithm still be considered a Binary Search algorithm? While doing the second code kata (which asks you to implement a binary search algorithm five times, each time with a different method), I've come up with a slightly different solution which works as follows:

If i have a sorted array of lenght 100 and I see its starting field contains the number 200 and its ending field contains the number 400, me, as a maths studying human, would be likely to start searching around field 35 if I was searching the number 270, and not the field 50 like in a normal binary search algorithm.

Then, if the number on field 35 of the array is 270, 35 is the index I was searching for.

If that isn't the case I can compare the number I got (say 280) and repeat the operation taking the lower part of the array (so I have 35 fields with the starting field containing 200 and the ending field containing 280) if the number I found is greater than what I'm searching for, or the upper part of the array (say I got 260: now I have 65 indexes, the first one containing 260 and the final one containing 400. Orientatively, I would head torward index 4 of this sub array, which is index 39 of the entire array) if the number I got is smaller than the number I'm searching for.

The question is: can this algorithm be considered a binary search algorithm? If not, has it got its own name?

I would not call this a binary search.

It is clearly similar to binary search and it's natural to see it as a refinement of binary search.  However it has significantly different algorithm complexity characteristics, Interpolation Search has expected run time of O(log(log(n)) assuming the data is uniformly distributed, however it pays for this by having O(n) worst case run time.

I prefer to say "The worst case run time of binary search is O(log(n))" rather than "Depending on the choice of bounding elements the worst case run time of binary  search is O(log(n))".  This means that I can not classify Interpolation search as a binary search algorithm.


Why are all polymorphic functions between functors natural transformations? Bartosz Milewski's Category Theory for Programmers says the following:

  A parametrically polymorphic function between two functors (including the edge case of the Const functor) is always a natural transformation.

Why is this true?

Something along the lines of an informal proof would help me.
It would also help to have an intuition about this.
Milewski says that naturality can be thought of as "separation of concerns" and provides an eggy metaphor:

  One [functor] moves the eggs, the other boils them.

How could ad-hoc polymorphism mix the concern of moving the eggs with the concern of boiling the eggs?

As you can see, I'm pretty fuzzy on this topic.

I think the easiest thing is to refer you to the famous Theorems for free! paper, which explains the intuition behind the use of the Reynolds parametricity theorem.

Intuitively, in System $\mathrm F$ a function $\alpha$ of type $\forall X. F\ X \rightarrow G\ X$, is so polymorphic, that $X$ can be instantiated by a morphism $f$ rather than just types. When one makes this precise, one sees that an arrow $F\ f\rightarrow G\ f$ can only be a commuting square, which exactly expresses the fact that $\alpha$ is a natural transformation.

The proof itself can be derived from Reynolds' classic result from Types, Abstraction and Parametric Polymorphism, which builds a model of System $\mathrm F$ where every type is interpreted by a relation over programs.


GOTO statement in programming environments for beginners? As a student, back in the day, I was exposed to high level programming languages that not only had a GOTO statement, but on which its use was common. I also did my fair share of programming in assembly code, but always had the impression that my understanding of the semantics of subprograms was enormously facilitated by my familiarity will programs constructed without them, in high level imperative languages, even though I never used them (or felt the need) in my life as a programmer, ever since.

In my experience as a teacher, the passage from non-modular to modular programming is always a struggle, and I keep asking myself the following question:

Would the careful and well-supervised reintroduction of the jump command in languages and environments devoted to introductory lessons in programming be of help students with the passage from non-modular to modular programming?

For clarity: the usage of the GOTO statement I am talking about here is restricted to programming environments used exclusively for teaching the basics of programming, while (or where) it is still done using imperative (monoparadigm) languages. Informed opinions based on experience and/or indications of research available on the subject (I didn't find anything substantial) are really welcome.

This doesn't seem like a good idea. Normally, we teach people using a system with restrictive safety features and only remove those safety features when the learner has demonstrated competence: consider training wheels on a bike, children's safety scissors and so on. You're suggesting that we teach using a "dangerous" system (goto) and then remove the dangerous parts once the learner has demonstrated competence.

Also, I don't see how using goto would help the transition to modular programming. Modular programming doesn't tend to use goto, so it seems you're trying to aid the transition from A to B by introducing something that doesn't help with B. To use a rather melodramatic analogy, it's like proposing to help somebody transition from a tricycle to a bicycle by giving them a pair of scissors to use while riding: it introduces a dangerous habit that doesn't even contribute to the desired goal.


What is the name of this prime number algorithm? Does the following recursive algorithm have a name? If so, what is it?

procedure main():
 myFilter = new Filter( myPrime = 2 ) //first prime number
 print 2 //since it would not otherwise be printed
 for each n in 3 to MAX:
  if myFilter.isPrime(n):
   print n

object Filter:
 integer myPrime
 PrimeFilter nextFilter = NULL

 procedure isPrime(integer n):
  if n is multiple of myPrime:
   return FALSE
  else if nextFilter is not NULL:
   return nextFilter.isPrime(n)
  else
   nextFilter = new PrimeFilter(myPrime = n)
   return TRUE

Sample implementation in Java here

This is similar to the Sieve of Eratosthenes though after some discussion in the CS chat, we decided that it is subtly different.

O'Neil [1] call this the "unfaithful sieve". It's much slower than the sieve of Eratosthenes.

For each prime $p$ you do work $\sim p/\log p$ and so the total number of divisions up to $x$ is roughly $x^2/(2\log^2 x)$ if you assume composites are free. (That's essentially true: they take at most $2\sqrt x/\log x$ divisions each for a total of at most $2x^{3/2}/\log x$ divisions.)

Divisions take longer than unit time, so the total bit complexity is about $O(x^2\log\log x/\log x)$.

[1] Melissa E. O’Neill, The Genuine Sieve of Eratosthenes


how to construct a formula with an opposite SAT value of another one given a formula S (that is built of binary variables and "or", "not", "and" gates).
IS there a polynomial algorithim that builds S' that satisfies:
S' satisfied if and only if S doesn't satisfied.
which means: S' is in SAT if and only if S not in SAT

The existence of such an algorithm would imply co-NP is included in NP which is unlikely

Checking that a formula is satisfiable: NP, generate proof by providing a solution

Checking that a formula is unsafisfiable: co-NP, generating proof can be harder, in classical proof systems the shortest proof of unsatisfiability of an arbitrary formula can be exponentially long

The algorithm you are looking for would mean all problems in co-NP have a short refutation, by providing a solution to the "opposite" formula. Therefore we are unaware of the existence of such an algorithm.


Set cover problem and the existence of such cover In the set cover problem we want to find in the $\mathbb{S} \subset 2^\mathbb{U}$ the subset $\{s_i\}_{1..k}$, such that $\cup s_i = \mathbb{U}$ for given $K$, where $k \le K$.
But how to reduce the set cover problem to the set covering decision problem (determining whether is there such cover or not)? The same with problems like a TSP is always easy enough: we exclude some elements, check if the needed condition is still met and know already, are these elements needed or not. But it doesn't work here and I am stuck. I would be appreciated if you could give me some hints for this problem.

There are two approaches for this:

The "hands on" way: first, find the minimal $k$ for which there is a set cover, by repeatedly calling an oracle for the decision problem (you can even do a binary search, but it isn't necessary).
Once you have the minimal $k$, choose a set $s_1\in S$, and check if there is a set cover of size $k$ in $S\setminus\{s_1\}$. If there is, you don't need $s_1$, so throw it away. If there isn't, remove $s_1$ from $U$, and repeat the process with $k-1$, until you have the set cover, which will be minimal.

The more theoretical approach is as follows. Since SET-COVER is NP-complete, there is a reduction from it to SAT, and a reduction from SAT to SET-COVER. If you examine the standard reductions (i.e. the Cook-Levin theorem, and a textbook reduction for $SAT\le_p SET-COVER$), you will see that both reductions are Levin reductions, which means that not only they are reductions, but they also preserve witnesses. That is, given a solution to the output of the reduction, you can generate from it a solution to the input.

Now you can proceed as follows. Given an instance for SET-COVER, find the minimal $k$ as before, and then reduce the problem with this $k$ to SAT. Now, if you have an oracle for the decision problem, you can reduce SAT to the SET-COVER, so you can also solve SAT using this oracle. For SAT we know how to find a solution using an oracle (just try bit-by-bit), so you can find a witness, and from this generate a witness for SET-COVER.

The latter works with any NP-complete problem.


For every $\mathrm{NP}$ language $L$, is there a verifier such that, for all the certificates $u$ of other verifiers of $L$, it accepts $(x, u)$? Let $L$ be an $\mathrm{NP}$ language.
Then there exists a verifier $V$ of $L$ and a polynomial $p\colon \mathbb{N} \to \mathbb{N}$, such that for every $x \in \Sigma^{*}$, $x \in L$ if and only if there exists a certificate $u \in \Sigma^{p(|x|)}$ for $x$ satisfying $V(x, u) = 1$.
Suppose that $\mathcal{V}_{q}$ be all the verifiers of $L$ such that the length of the certificates of $x$ is $q(|x|)$.
And for every $V \in \mathcal{V}_{q}$, let $V_{x}$ be all the certificates of $x$.
For every polynomial $q\colon \mathbb{N} \to \mathbb{N}$ satisfying $\mathcal{V}_{q} \neq \varnothing$, I want to know whether there is a verifier $\bar{V} \in \mathcal{V}_{q}$ such that for every $x \in L$,
$$\bar{V}_{x} = \bigcup_{V \in \mathcal{V}_{q}} V_{x}.$$

Fix $x \in L$ of length $|x|=n$. Suppose that $\mathcal{V}_q \neq \emptyset$, and let $m = q(n)$. Choose some $V^0 \in \mathcal{V}_q$. For any $s \in \{0,1\}^m$, let $V^s(y,u) = V^0(y,u \oplus s)$ for inputs of length $n$ and witnesses of length $m$, $V^s(y,u) = 0$ for inputs of length $n$ and witnesses lengths different from $m$, and $V^s(y,u) = V^0(y,u)$ otherwise. Then $V^s$ is a verifier for $L$ for all $s$, and so $\bigcup_{V \in \mathcal{V}_q} V_x = \{0,1\}^m$.
This means that if a verifier $\bar{V}$ exists, then $\bar{V}_x$ is the set of all strings of length $q(|x|)$. This means that $\bar{V}$ need not consult its witness, showing that $L \in \mathsf{P}$.


Arden's Rule, DFA & NFA to regular expressions I have been trying to figure out the Arden's Rule and the equational method to transform DFA's & NFA's to RE. I know what the rule state:

if   x = s + xr
then x = sr*, with $s,r\in$ Regular Expressions

With that said, when I'm trying to transform one DFA in a RE this questions pop:

For example regarding this DFA

The $\epsilon$ is added in the entry stage A or in the final stage D and A ?
The equations should be written regarding the transitions in or out of a given state

2.1 For example A = $\epsilon$ + 0B + 1C  or A = $\epsilon$ + 0C
Can the equational method and Arden's Rule be applied to a NFA with multiple initial states ?

Final thoughts, I have been trying out and it seems that when we count the transitions out of a state the $\epsilon$ should be added to the final state. When we count the transitions into a state the $\epsilon$ should be added to the initial state.

Keep in mind that I SERIOUSLY doubt my conclusions and I really need some help.

You can use either way. In both cases you construct a mapping from the states of the automaton to regular expressions, $[-]: Q\to RE$.

Let $(s, l, t)$ denote a transition from $s$ with label $l$ to target state $t$.

Also, let $\oplus_{i\leq n}r_i = r_1 + \ldots + r_n$.

1st case: By incoming edges.

Add a final state, $F$, and an $\varepsilon$-transition from each previous final state to $F$.
For every state $X$ with $n$ incoming edges $(s_i, l_i, X)_{i\leq n}$, make an equation $[X] = \oplus_{i\leq n}([s_i]l_i)$.
Use rule: $X = s + Xr \Longrightarrow X = sr^*$ on the equations
The final regular expression is $[F]$.

2nd case: By outgoing edges.

Add a new initial state, $S$, and an $\varepsilon$-transition from $S$ to the previous initial state.
For every state $X$ with $n$ outgoing edges $(X, l_i, t_i)_{i\leq n}$, make an equation $[X] = \oplus_{i\leq n}(l_i[t_i])$.
Use rule: $X = s + rX \Longrightarrow X = r^*s$ on the equations
The final regular expression is $[S]$.

Both methods work for NFAs as well. None of the above transformations depend on determinism.

Regarding your final thoughts, when you count the outgoing edges, if you add the $\varepsilon$-transition in the final states, then $[F] = \emptyset$, because $F$ (the new final state) has no outgoing edges, and this doesn't contribute to the equations. What you want to add is a new initial state, so that you can compute $[S]$. For your DFA example, $[S] = \varepsilon[A]$. Similarly, adding a new initial state is useless when transforming by incoming edges. In this case, $[S] = \emptyset$ and what you want is $[F]$, which for your example, would be $[F] = [A]\varepsilon + [D]\varepsilon$.


Dangerous interrupts Let's say we have a fictional operating system in the user mode. Whenever an interrupt or a trap occurs, the os would switch to the Kernel mode jumping to the address determined from the interrupt vector. A malicious user could take advantage of the loophole by executing a malicious program in the kernel mode.

Why is it dangerous ? What could have the user possibly done to achieve this and what kind of remedy would you suggest for the loop hole ?

The malicious user has to first get the malicious code into kernel space somehow. User and kernel address spaces often look contiguous under linux and various unixes, but user space isn't mapped into kernel space, and vice versa. Some variations of Unix (the Masscomp system, as I recall) made this more explicit by having user space and kernel space start at 0x00000000. So, that's the first problem: code at 0x0804890c (or where ever) writeable by the user doesn't exist in the kernel's address space.

Secondly, the malicious user would have to have the ability to change the interrupt vector. This vector conceptually could live in either kernel or user space, but probably resides in kernel space. If the interrupt vector resides in kernel space, the user doesn't have write access.  If the interrupt vector resides in user space, it's marked read-only, and the addresses in it point to code in kernel space. Which is why problem (1) above for the malicious user exists.


XOR of one-way function Considering the top answer to the question “If xor-ing a one way function with different input, is it still a one way function?”…

  The function is no longer one-way.

  we build a counter example in the following way. Assume $g$ is a one-way function that preserves size, and define $f$  on input $w=bx_1x_2$ in the following way,
  $$f(bx_1x_2) = \begin{cases} g(x_1)\,x_2 & b=0 \\ x_1\, g(x_2) & b=1 \end{cases}$$
  (assuming $b\in\{0,1\}$ and $|x_1|=|x_2|$.)
  It is easy to see that $f$ is also one-way — to invert it, you need to either invert $g$ on the first half or invert $g$ on the second half.

  Now we show how to invert $h$. Assume you are given $h(u,v)=Z$, we write it as $h(u,v)= z_1z_2$ with $|z_1|=|z_2|=n$.
  Then a possible preimage of $Z$ is
  $$u=0 \,0^n \,\langle g(0^n)\oplus z_2\rangle$$
  $$v=1 \, \langle g(0^n)\oplus z_1\rangle \, 0^n$$

  because $f(u) = g(0^n)\, \langle g(0^n)\oplus z_2\rangle$ and
  $f(v) = \langle g(0^n)\oplus z_1\rangle \, g(0^n)$ thus their XOR gives
  exactly $z_1\,z_2$ as required.

Wouldn't this counter-example imply that we've inverted $f$?

Consider the reduction where we take in $f(x_1)$ and $f(x_2)$: then we could compute $f(x_1) \oplus f(x_2)$, invert this to $x_1x_2$, and then we have inverted $f$ as well.

Is the quoted answer correct? If so, why, given my considerations outlined above?

There are two reasons that counter-example wouldn't "imply that we've inverted".

(a)

Despite that answer's (probably-not-necessarily-correct) opening sentence,

it's only a counterexample to "$h$ is necessarily one-way", not to "$h$ is one-way".

(b)

That answer's attack does not require inverting  $\hspace{.04 in}f(x_1) \oplus f(x_2)$  "to $x_1x_2$",

it just involves finding a preimage of  $\hspace{.04 in}f(x_1) \oplus f(x_2)$  under $h$.


Existence of boolean function with exponential average case hardness Show that for every large enough $n$, there is a boolean function $f\colon \{0,1\}^n\longrightarrow\{0,1\}$, whose average case hardness is exponential. The question is taken from Arora Barak Computational Complexity textbook, Chapter-16, Ex-3.
Average case hardness of a boolean function $f$ is defined as, the largest $S(n)$ s.t. for all circuit $C_n\in \operatorname{Size}(S(n))$, $\Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$. Here $U_n$ is uniform distribution over $\{0,1\}^n$. I want to show there are boolean functions having $S(n)$ exponential in $n$. My approach is to pick a random $f$ and show via Chernoff bound, the probability of having such function is $>0$.
Formally, I am following this approach, I need to show, $\Pr_{x\in U_n}[C_n(x)=f(x)]-1/2<1/2^n$, $S(n)=2^n$ . Take $Y$ another random variable, $Y=1$ iff, $C_n[x]=f[x]$ else $0$. I express $\Pr_{x\in U_n}[C_n(x)=f(x)]=\frac{1}{2^n}\sum Y_i$,  Now, by Chernoff bound if I can bound the probability $\Pr[\frac{1}{2^n}\sum Y_i-1/2]>1/2^n$ over $C$, I can take the union bound over all $C$ to show that probability is less than $1$. But, I am not sure if I can replace $\mu$ of Chernoff bound with any constant like $1/2$.
Is my approach correct? Can anyone help with my query? $U_n$ is uniform distribution.

Let $C$ be a fixed function, and let $f$ be a random function. For $z \in \{0,1\}^n$, let $X_z = 1$ if $C(z) = f(z)$, and $X_z = -1$ otherwise. Thus
$$
2^{-n} \sum_z X_z = \Pr[C(z) = f(z)] - \Pr[C(z) \neq f(z)] = 2\Pr[C(z) = f(z)] - 1.
$$
Therefore $\Pr[C(z) = f(z)] \geq 1/2+\delta$ iff $2^{-n} \sum_z X_z \geq 2\delta$. According to Bernstein's inequality,
$$
\Pr\left[2^{-n} \sum_z X_z \geq 2\delta\right] \leq \exp \left(-\frac{42^n\delta^2}{2(1+2\delta/3)}\right) \leq e^{-2^n\delta^2}.
$$
(The true exponent is more like $-2^{n+1}\delta^2$.)
The number of (de Morgan) circuits of size $s$ is at most roughly $e^{2s\log s}$ (according to notes of Trevisan; the bound is not tight). According to the union bound, the probability (over $f$) that some circuit $C$ of size $s$ satisfies $\Pr[C(z) = f(z)] \geq 1/2+\delta$ is at most $e^{2s\log s} \cdot e^{-2^n\delta^2}$. If $2s\log s < 2^n\delta^2$ then this probability is less than $1$, and so there exists some function $f$ such that $\Pr[C(z) = f(z)] < 1/2+\delta$ for all circuits of size $s$.
You're interested in the setting $\delta = 1/s$. The argument works as long as $2s^3\log s < 2^n$, and in particular, when $s\approx2^{n/3}$.


How do I interpret this question? For any language $L \subset \Sigma^*$, define $S(L)$ to be $$\{x\in L \mid \neg \exists y \in L: \exists z \in \Sigma^*: (z \ne \epsilon) \land (x=yz)  \}$$

Show that $S(L) = S(S(L))$

I'm confused about the question here. The way we define $S(L)$ takes elements from $L$ $(x \mid x \in L)$, but $x=yz$ and $y \notin L$. How is it possible for x to concatenate an element from $\bar{L}$ (complement of $L$ since $y \notin L$) and still be an element of $L$?

The formula means "it is not true that there exists $y \in L$ and $z \in \Sigma^*$ such that $z \ne \epsilon$ and $x=yz$."  That is, there is no way of writing $x=yz$ such that $y\in L$ and $z\neq\epsilon$.


Are the non-regular languages closed under reverse, union, concatenation, etc? My question: do the non-regular languages have closure properties? For example, if the reverse of L is non-regular, then L is non-regular ? thank you :-)

Non regular languages are closed under reverse, because $L = (L^R)^R$. Same is true for complement.

Non regular languages are not closed under most other basic operations though. Consider, for example, that $L \cup \overline{L} = \Sigma^\star$. Similarly, if $L = \{1^{x^2} | x > 1\}$ then $\overline{L} \circ \overline{L} = 1^\star$.

There is no complete list of operations on languages, so a complete answer cannot be given.


Computer science asymptotic terminology I have been hearing the phrases quasipolynomial, superpolynomial and subexponential.

I think know what quasipolynomial and subexponential is. I believe these are functions respectively of form $n^{\log^c n}$ and $n^{n^{1/c}}$ for some $c>1$.

What does superpolynomial mean?

Superpolynomial means $n^{\omega(1)}$, that is, growing faster than any polynomial. More clearly, $n^{f(n)}$ for some function $f$ satisfying $\lim_{n\to\infty} f(n) = \infty$.


A repository for max flow and mincut datasets I am not 100% sure if this is the right stackexchange to ask. I have a  max-flow algorithm and I am also computing the min-cut from that algorithm.

I want to test the correctness and speed of it and I am trying to find if there are some datasets against which I can test my algorithm. The dataset should preferably have the max-flow value and the set of edges belonging to min-cut.

To test correctness: the set of edges belonging to a min-cut is not unique in general, so a dataset like you ask would not really be helpful, apart from checking that the value of the cut is the right one. However, it is easy to check correctness yourself by using the output of your algorithm if you compute both the max-flow and the min-cut; just check that the first is a valid flow, the second is a valid cut, and that their value is the same. By the max-flow/min-cut theorem, they must then both be optimal.

To test speed: it's pretty old (1990-91), but you may want to have a look at the archive of the DIMACS implementation challenge on the Maximum Flow problem. It includes many generators and several other codes. For a more modern dataset (1998-2013), here is a collection of Maximum Flow problems arising in computer vision. Also, Andrew V. Goldberg has a page on network optimization software with several useful links (although the Min Cut one seems to be dead).


Proving that EXP doesn't have polynomial-size circuits How to prove for all $i\in\mathbb{N}$, there exists a language $A\in\mathrm{EXP}$ such that no family of boolean circuits of size $n^i$ decides $A$?

I have a reminder that says
$$ \mathrm{EXP} =\bigcup_{c\in\mathbb{N}} \mathrm{DTIME}\left(2^{n^c}\right). $$

Thought of building a TM that on input $x$ of size $n$, finds a function $f_{n}$ such that there is no circuit of size $n^k$ that calculates it. Go through all functions and for each one go through all the circuits and check whether they calculate the function. If none of them calculates it then it's what we want.

I don't know how to show this is $\mathrm{EXP}$ or how to prove this solves the problem.

You can consider a circuit as a directed graph where nodes are inputs and gates. For a circuit of size $n^k$ on input of size $n$, there are at most $(n+n^k)^2$ edges, and each node (gate) has three possibilities, so the number of such circuits is at most

$$3^{n^k}\cdot2^{\left(n+n^k\right)^2}=O\left(2^{n^{2k+2}}\right).$$

So you need only to enumerate at most $O\left(2^{n^{2k+2}}\right)$ functions. In addition, checking whether a circuit of size $n^k$ calculates a function costs $O(n^{2k}2^n)$ time since computing on each input costs $O(n^{2k})$ time (here we compute the running time under a RAM rather than a TM without loss of generality) and there are $2^n$ inputs. Note for each function, you need to go through all circuits, and for each circuit, you need to check whether it calculates the function, so the total running time of the RAM on input of size $n$ is

$$ O\left(2^{n^{2k+2}}\right)\cdot O\left(2^{n^{2k+2}}\right)\cdot O(n^{2k}2^n)=O\left(2^{n^{2k+4}}\right). $$

So the language decided by this RAM is in $\mathrm{EXP}$ (note $k$ is a fixed constant). Obviously no family of circuits of size $n^k$ decides this language by the construction of the RAM.


Sorting tuples with respect to multiple criteria Given $n$ rows with $k$ columns, is there a storage mechanism/data-structure and/or algorithm that enables dynamic restructuring such that I can get the top $t=\mathcal{O}(1)$ results efficiently?

Example strategy 0

$$k_0 \le k_1 \le \cdots \le k_{n-2} \le k_{n-1}$$

Example strategy 1

$$k_{n-1} \le k_{n-2} \le \cdots \le k_1 \le k_0$$

Given [ [0,1] [2,3] [1,2] ] strategy 0 returns: [ [0,1], [1,2] ], where $t=2$.

Restructuring with strategy 1 returns: [ [2,3], [1,2] ]. New strategies can be provided "at runtime".

Given a data-structure solution, here are the methods that it should expose:

insert_row (*row) -> inserts a row of $k$ elements into the structure
delete_row (*row) -> delete the precisely specified row from structure
new_strategy(*k_prioritisation) -> rebalances the structure given the specified strategy
top_rows() -> provides top rows after a strategy has been "installed". Number of rows to return is specified at compile time (as a source-code constant).

PS: Bonus points if you can enables strategies like $k_0 \le [\text{all other } k \text{ except } k_0]$, with embedded strategies of much the same.

Multivariate optimisation (a subproblem of sorting) is usually hard, even offline, because there are no longer "optima" but you have to deal with several Pareto-optimal elements.

Luckily, you have specified that such ties should be broken by strict priorities. In that case, lexicographic sorting (w.r.t. your criteria and in order of the priorities) solves the problem.


Efficient algorithm to replace list of integers with nearest bigger element The original question was in the context of an array, but I just used a list without changing the length for easier debugging purposes of toString().

  Given an unsorted list of integers, design a O(n) algorithm to transform the list such that the integers are replaced by the next bigger integer on their right. If there is no bigger integer on its right, the integer remains the same.

  For example [2,1,4,5,3,6,7,9,4,8] becomes [4,4,5,6,6,7,9,9,8,8].

I have come out with an algorithm after a long time, but a recent test case reveals that my algorithm doesn't cover all cases. Here is my attempt written in Java. Can anyone suggest the algorithm for this problem?

The issue is how to find "the next bigger integer on their right", which sounds like a stack operation.

Here is the algorithm in its essence.

Create an empty stack.
Iterate over the given list of integers from left to right.

Push the current integer to the stack.
While the top of the stack is smaller than the next integer in the list, replace the integer in the list that corresponds to the top of the stack by that next integer in the list followed by popping the stack.

The idea of the algorithm is to let the stack store the integers for which we have not found their next bigger integers yet, in the natural order in which they have been examined. Those integers will be strictly decreasing.

In the actual implementation, in order to locate the integer in the given list that corresponds to the top of the stack, the indices of the integers should be stored in the stack instead of the integer themselves.

Here is code in Python:

l = [2, 1, 4, 5, 3, 6, 7, 9, 4, 8, 5, 1 ,3, 8]
s = []
for i in range(len(l) - 1):
    s.append(i)
    while s and l[i + 1] > l[s[-1]]:
        l[s.pop()] = l[i + 1]
print(l)

For readers who does not use Python, s[-1] is the last element of the list s.

Since each index of the given list is appended once and popped at most once and the last index is not even included, the time-complexity of the algorithm is $O(n)$, where $n$ is the length of the given list.


Proving equality between foldl recursive and iterative fold Hi I have two definitions of fold. I will call them foldl which is recursive and fold$_{itr}$ which is iterative.

I am looking for an algebraic proof that the two definitions are equal ideally through structural induction.

Definition for foldl

foldl(c,h) nil = c

foldl(c, h) (list, element) = h (foldl (c, h) list, element)

Definition for fold$_{itr}$

fold$_{itr}$ (c, h) nil = nil

fold$_{itr}$ (c, h) (element, list) = fold$_{itr}$ (h(c, element), h) list

The two definitions are not equal. Consider $h$ defined by
\begin{align*}
h(c, a) = 10 \cdot c + a
\end{align*}
and $c = 0$. Then
$$\mathsf{foldl} \, (c,h) \, [1,2,3] = 321$$
but
$$\mathsf{fold}_{itr} \, (c,h) \, [1,2,3] = 123.$$


Getting a variable assignment of a Tseitin transformed formula Let $\phi$ be a Boolean formula and $\mathrm{Tseitin}(\phi)$ the corresponding Tseitin transformed equisatifiable formula.

It is well-known that one can get a variable assignment for $\phi$ by solving $\mathrm{Tseitin}(\phi)$ and dropping the auxiliary variables. For example, see Wiki, quote: "When a satisfying assignment of variables is found, those assignments for the introduced variables can simply be discarded."

After a long search through SAT papers I just could not find any paper which proves this statement. Because I do not want to re-invent the wheel: Does anyone know such a reference I can use to cite?

Given a circuit $C$ on variables $V$ which has gates $G$, the Tseitin transformation produces a formula $T(C)$ on the set of variables $V \cup G$, with the property that the formula holds iff

The value of every gate variable $g \in G$ is exactly the value of this gate given the assignment to the inputs, and
The circuit outputs TRUE.

You can prove property (1) by induction. Property (2) holds since you add a specific clause stating that the top gate in the circuit is TRUE. Given this, there is an assignment causing the circuit $C$ to output true iff $T(C)$ is satisfiable, and moreover you can read this assignment from a satisfying assignment to $T(C)$ — just ignore the gate variables.

The crucial point is that in any satisfying assignment of $T(C)$, the value of the gate variables is completely determined by the value of the input variables.


Definition of 'Record' Given the definition of 'record': "a collection of field values for a given entity", is this a set of field values for ALL the fields of the entity, or only one particular field [so that you get a different set for each field]?
Also, is the relationship b/w a field & field value essentially equivalent to a function?
NOTE: Total beginner learning data struc. & algos.

All of the fields.  For instance, here is an example of a record:
{name: D.W., favoritecolor: blue}

You can think of a record as a function from field (key) to value.  For instance, the above would correspond to a function $f$ defined by $f(\text{name})=\text{D.W.}$, $f(\text{favoritecolor})=\text{blue}$.


Karp hardness of directed monochromatic triangle problem Monochromatic problem is a classic NP-complete problem.
Does the complexity stay NP-complete if we use directed graph?
DIRECTED MONOCHROMATIC TRIANGLE problem:

Input: A digraph $G(V,A)$
Output: YES if there exists a triangle-free bipartition of $A$, otherwise NO.

A triangle-free bipartition of $A$ is a partition $A=A_1\dot{\cup}A_2$ such that both $G[V,A_1]$ and $G[V,A_2]$ are triangle-free.
Note that a triangle in a digraph is the set of $3$ vertices $\{u,v,w\}$ such that $(u,v),(v,w),(w,u)\in A$. It means that we only allow triangle that has consecutive arcs. For example, $(u,v),(u,w),(w,u)$ does NOT form a triangle.

All directed graphs can be edge-partitioned into two subgraphs that are acyclic and therefore triangle free.

Let $\prec$ be any total ordering of the vertices. For each edge $(u, v) \in A$, put it in $A_1$ if $u \prec v$, and in $A_2$ otherwise. Both $(V, A_1)$ and $(V, A_2)$ must be acyclic.


Math behind Multi-class linear discriminate analysis (LDA) I have a question about Linear Discriminant Analysis (LDA) for the purpose of Dimensionality Reduction.

So I understand for the algorithm to calculate for $k$ projection vector(s) you need to determine the eigenvector(s) that corresponds to the top $k$ eigenvalue(s). But can anyone explain what you do with those eigenvectors after you have calculated them to get a final output?

My guess is to multiply all of the eigenvectors (projection vectors) together and then multiply that with each point, $x$, in the original dataset to produce a new corresponding point $y$. Does this sound right?

Given normalized top $k$ eigenvectors $v_1,\ldots,v_k$, you send a point $x$ to the tuple $(\langle x,v_1 \rangle, \ldots, \langle x,v_k \rangle)$.

Alternatively, you put the eigenvectors as rows in a matrix $M$, and you map the column vector $x$ to $Mx$ (this is exactly the same thing as above).

Multiplying vectors is an operation that doesn't have much semantic sense here. (How would you multiply them anyway, and why?)

There are reasons why we apply this particular operation, and they have to do with the goal of LDA. If you want to know more, I suggest picking up a decent textbook that explains LDA not only via formulas and algorithms, but also as the solution to an optimization problem.


Finding the max XOR of two numbers in an interval: can we do better than quadratic? Suppose we're given two numbers $l$ and $r$ and that we want to find $\max{(i\oplus j)}$ for $l\le i,\,j\le r$.

The naïve algorithm simply checks all possible pairs; for instance in ruby we'd have:

def max_xor(l, r)
  max = 0

  (l..r).each do |i|
    (i..r).each do |j|
      if (i ^ j > max)
        max = i ^ j
      end
    end
  end

  max
end

I sense that we can do better than quadratic. Is there a better algorithm for this problem?

We can achieve linear runtime in the length $n$ of the binary representation of $l$ and $r$:

The prefix $p$ in the binary representation of $l$ and $r$, that is the same for both values, is also the same for all values between them. So these bits will always be $0$.

Since $r>l$, the bit following this prefix will be $1$ in $r$ and $0$ in $l$. Furthermore, the numbers $p10^{n-|p|-1}$ and $p01^{n-|p|-1}$ are both in the interval.

So the max we are looking for is $0^{|p|}1^{n-|p|}$.


Prove that $ln(n)^r \in o(n^p)$ for $p>0$ and $r\in \mathbb{R}$ I am trying to proof $f\in o(g)$
Let be $r,p\in \mathbb{R}$ with $p>0$
We have $f(n)=ln^r (n)$ and $g(n)=n^p$
I have already proofed that $ln(n)\in o(n)$ via l'Hospital
$\lim\limits_{n\to \infty}\frac{\frac{1}{x}}{1}=0\Longrightarrow \lim\limits_{n\to \infty}\frac{ln(n)}{n}=0\Longleftrightarrow ln(n)\in o(n)$
I tried substituting n with ln(n) to recieve
$\forall c>0 \exists n_0 \forall n\geq n_0 : ln(ln(n))\leq cln(n)$
Then i tried splitting $c=\frac{a}{b}$ to get $\forall \frac{a}{b}>0\exists n_0 \forall n\geq n_0 : ln(ln(n)) \leq \frac{a}{b}ln(n)$
With this information i said, that $\frac{a}{b}*\frac{b}{a}*b*ln(ln(n))=b*ln(ln(n))\leq \frac{a}{b}*\frac{b}{a}*\frac{a}{b}*b*ln(n)=\frac{a}{b}*b*ln(n)=a*ln(n)$
to conclude $ln(n)^b=e^{\frac{a}{b}*\frac{b}{a}*b*ln(ln(n))}\leq e^{\frac{b}{a}*b*ln(n)}=e^{b*ln(n)}=n^a$
At this point i realized a huge problem. I assumed $\frac{a}{b}$ to be positive. But i need it to work for r and p, where only p is known to be postive, which in the other hand means, that r can be negative, what would make $\frac{p}{r}$ negative.
It means that my approach is propably not working a

You just need to show that
$$
\lim_{n \to \infty} \frac{\log^r n}{n^p} = 0.
$$
This is trivial if $r \le 0$ since $\frac{\log^r n}{n^p} = \frac{1}{n^p \log^{-r} n}$ and $\lim_{n \to \infty} n^p \log^{-r} n = +\infty$.
For $r>0$, you can use  l'Hôpital's rule $\lceil r \rceil$ times to obtain:
$$
\lim_{n \to \infty} \frac{\log^r n}{n^p}
= \lim_{n \to \infty} \frac{r \log^{r-1} n}{pn^{p}}
= \dots
= \lim_{n \to \infty} \frac{\prod_{i=0}^{\lceil r \rceil-1} (r-i) \cdot \log^{r-\lceil r \rceil} n}{p^{\lceil r \rceil} n^{p}} \\
=
\frac{\prod_{i=0}^{\lceil r \rceil-1} (r-i)}{p^{\lceil r \rceil}}\cdot \lim_{n \to \infty} \frac{ \log^{r-\lceil r \rceil} n}{ n^{p}} =0,
$$
where $\frac{\prod_{i=0}^{\lceil r \rceil-1} (r-i)}{p^{\lceil r \rceil}}$ is a positive constant and
$
\lim_{n \to \infty} \frac{ \log^{r-\lceil r \rceil} n}{ n^{p}}
$
is equal to $0$ since it falls into the previous case.


Controlled NOT gate a type of measurement? I'm trying to understand the theory of quantum computing, and I'm a bit confused on a particular circuit:

Would the controlled NOT gate be a type of measurement, causing Q1 to be either |0> or |1>, or would the circuit be in a superposition of the |00> and |11> states until an actual measurement of Q1 or Q2 took place?

A controlled-NOT gate is meant to be a reversible operation which, for ordered pairs of bits $(a,b) \in \{0,1\}^2$, performs the operation
$$ \mathrm{CNOT} (a,b)\; = \;(a, b \oplus a)$$
where conventionally we represent the "control" by the first bit and the "target" by the second. (In a physical implementation, essentially the same physical interaction but in a different orientation would be used to implement the transformation $(a,b) \mapsto (a\oplus b, b)$ and so this is also called a "controlled-NOT", rarely with any distinction from the one described above.) This gate is obviously reversible, as one can easily verify that $\mathrm{CNOT} \circ \mathrm{CNOT} = \mathrm{id}\,$.

As is usual in quantum computation, we "lift" reversible operations such as $\mathrm{CNOT}$ to distributions over inputs by describing it as a permutation of computational basis states. In particular, because
$$\begin{align*}
(0,0) \;&\xrightarrow{\;\mathrm{CNOT}\;\;}\; (0,0) \\
(0,1) \;&\xrightarrow{\;\phantom{\mathrm{CNOT}}\;\;}\; (0,1) \\
(1,0) \;&\xrightarrow{\;\phantom{\mathrm{CNOT}}\;\;}\; (1,1) \\
(1,1) \;&\xrightarrow{\;\phantom{\mathrm{CNOT}}\;\;}\; (1,0)
\end{align*}$$
the permutation matrix which we use to represent $\mathrm{CNOT}$ is
$$ \mathrm{CNOT} \;=\; \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}\; .$$
It is easy to verify that this (and all other permutation matrices) are unitary. This is the operation which transforms the state of the first two qubits. Because the state of those two qubits just before the $\mathrm{CNOT}$ gate is given by
$$ |\psi_1\rangle \;=\; (H \otimes \mathbf 1) |0\rangle |0\rangle \;=\; \tfrac{1}{\sqrt 2} \Bigl[ |0\rangle |0\rangle  + |1\rangle |0\rangle \Bigr] \;=\; \tfrac{1}{\sqrt 2} \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} \,,$$
the state that we obtain afterwards is given by
$$ |\psi_2\rangle \;=\; \mathrm{CNOT} |\psi_1\rangle \;=\; \tfrac{1}{\sqrt 2} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} \;=\; \tfrac{1}{\sqrt 2} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \end{bmatrix}  \;=\; \tfrac{1}{\sqrt 2} \Bigl[ |0\rangle |0\rangle  + |1\rangle |1\rangle \Bigr] \,.$$
In this case, it's probably easiest to see that you can apply the action of $\mathrm{CNOT}$ on the standard basis states $|0\rangle|0\rangle$ and $|1\rangle|0\rangle$ separately, which form the components of $|\psi_1\rangle$, to obtain components  $|0\rangle|0\rangle$ and $|1\rangle|1\rangle$ respectively; this is possible because the $\mathrm{CNOT}$ operation (and all other permutations and unitary operators) is linear.


Non-deterministic algorithm to check if a list has some given value I know that I can build a non-deterministic algorithm with a CHOICE function that verifies if a value x is in an array in O(1) time complexity.

The usual algorithm to do that is

find (A, x)
    j = CHOICE(1, .. , A.length)
    if A[j] == x
        return VALID
    return FAIL

But, it works because we are able to access the position j directly, in constant time.

So, if I change the problem: instead of an array A, use a linked-list L, then, how can I construct my non-deterministic algorithm using the CHOICE function to check if a value x is in L or not ?

Will it still have O(1) time complexity ?

If the only way you have to access the last element is to step through the whole list, one item at a time, you can't possibly use less than $O(n)$ time, even nondeterministically. If you used less than that, none of the paths through the computation would be able to access the end of the list, so none of them would be able to check whether it contained the desired entry.


Connection of different buses to memory The  address bus(of cpu) is connected to a digital decoder inside the memory which sets 1 pin logic high and activates the read/write operation of the memory let's say DRAM. Is the data bus(of cpu) connected directly to the bit line of the DRAM(columns) or are there some in between steps?

With all due reserve.
DRAM chips today are placed on DIMMs which look like

The black chips seen on the DIMM are the DRAM chips. DRAM chips inside look like

Each big gray square is called a bank. One bit of DRAM looks like

You see that between the output of the DRAM chip and the bit stored in the capacitor there is a sense amplifier. That is used to amplify the voltage of the stored energy. You need this because the energy stored in one capacitor is not strong enough to just be sent over to the bus. The sense amplifier is detailed at http://pnrsolution.org/Datacenter/Vol3/Issue2/119.pdf.

Sense amplifier is not only an amplifier but a positive feedback device that quickly pushes the readout voltage to 1 or 0. The gates of the DRAM cells are  tied to the row decoder and the bit-line pairs are connected to the sense amplifier.

A detailed explanation of the hardware interface of DRAM chips is found at https://compas.cs.stonybrook.edu/~nhonarmand/courses/sp15/cse502/res/dramop.pdf. This pdf is very detailed. For the read operation it says:

To read the data from a memory cell, the cell must be selected by its row and column coordinates, the charge on the cell must be sensed, amplified, and sent to the support circuitry, and the data must be sent to the data output. In terms of timing, the following steps must occur:

The row address must be applied to the address input pins on the memory device for the prescribed amount of time before RAS goes low(tASR) and held (tRAH) after RAS goes low.

RAS must go from high to low and remain low (tRAS).

A column address must be applied to the address input pins on the memory device for the prescribed amount of time (tASC) and held (tCAH) after CAS goes low.

WE must be set high for a read operation to occur prior (tRCS) to the transition ofCAS, and remain high (tRCH) after the transition of CAS.

CAS must switch from high to low and remain low (tCAS).

OE goes low within the prescribed window of time. Cycling OE is optional; it may be tied low, if desired.

Data appears at the data output pins of the memory device. The time at which the data appears depends on when RAS (tRAC),CAS (tCAC), and OE (tOEA) went low, and when the address is supplied (tAA).

Before the read cycle can be considered complete,CAS and RAS must return to their inactive states (tCRP, tRP).

To be clear, this is how DRAM chips work with their own pins. This is not how the DIMM itself works. The DIMM is a bit different. You can look at JEDEC specifications on DDR RAM to see how DRAM work a bit better. For example, the JESD79-4 standard is about the DDR4 SDRAM (Synchronous DRAM) (http://www.softnology.biz/pdf/JESD79-4B.pdf). In this document is stated how bank groups and banks are selected. The address pins are multiplexed meaning that depending on if RAS or CAS is set then address pins will either select a column or a row. Page 5 is especially interesting because it describes the actual pins of the DDR4 DRAM chip.
To determine how actual DIMMs work, one can look at other JEDEC specifications (https://www.jedec.org/standards-documents/docs/module4_20_26_annexa). This website presents the actual document that you must be registered to download. This documents specifies the pin description of DDR4 DIMMs. The DDR4 DIMM is 288 pins (144 on each sides). The pins that are important for your question are the DQ pins. There are 64 DQ pins which is not for no reason. It is because DDR4 supports 64 bits machines. The DQ pins are probably connected to the data bus of the computer.
For actual interface between memory and Intel CPUs you can look at the External Memory Interface Handbook Volumes 1, 2 and 3 from Intel. These volumes are available on internet and are pretty lengthy. They are pretty hard to understand. The document at https://www.intel.com.br/content/dam/doc/datasheet/core-i5-600-i3-500-pentium-6000-datasheet-vol-1.pdf is a description for the core i5 processor which is pretty good. It has a pin description at the end of the document for the processor. There are 64 bidirectional SA_DQ pins and 64 SB_DQ pins. These pins are used for I/O to and from RAM.

The Integrated Memory Controller (IMC) supports DDR3 protocols with two independent, 64-bit wide channels each accessing one or two DIMMs.

Based on the above statements, there are several interfaces between the data bus and the actual bit line of the memory cell. A path will have to eventually be opened between the processor SA_DQ pins and the DQ pins of the DIMM using the data bus. The DQ pins of the DIMM are themselves connected to the output data buffers of the banks of the DRAM chips.


Ideal value of d in a d-ary heap for Dijkstra's algorithm I stumbled upon the following statement:

  By using a $ d $-ary heap with $ d = m/n $, the total times for these two types of operations may be balanced against each other, leading to a total time of $ O(m \log_{m/n} n) $ for the algorithm, an improvement over the $ O(m \log n) $ running time of binary heap versions of these algorithms whenever the number of edges is significantly larger than the number of vertices

Applications of d-ary heaps

I don't understand why we choose to have a heap where nodes have exactly $ m/n $ children to speed up Dijkstra's algorithm. Remove min takes overall $ O(n \log_d n) $ time and  decrease takes $ O(m \log_d n) $, so total runtime is $ O(m \log_d n) $.

What I don't understand is say we have $ m=3, n=1 $, $ m/n $ gives 3, but $ O(m \log_3 n) $ is slower than $ O(m \log_4 n) $, so why not choose 4 as value of $ d $ instead? What motivates taking $ m/n $?

Thanks!

Please note that $ m \leq n(n-1)/2 $, thus $m/n < n/2$. So the example $m=3, n=1$ does not happen.

First, the article clearly claims that this improvement is achieved whenever $ m $ is larger than $ n $,

  By using a $d$-ary heap with $d = m/n$, ..., an improvement over the O(m
  log n) running time of binary heap versions of these algorithms
  whenever the number of edges is significantly larger than the number
  of vertices.

Secondly, the article claims that $d$ must create a balance between $m$ and $n$ in order to improve the running time,

  By using a $d$-ary heap with $d = m/n$, the total times for these
  two types of operations may be balanced against each other...

Generally, we need $n$ min-extract and $m$ decrease-key operations. In the case of $d=2$, each of these operations takes $O(\log n)$ time. However, when you increase $d$, the decrease-key operation becomes faster, but min-extract can become slower. Because, within each min-extract, we also need to run min-heapify that depends on the number of children of the parent in each level.

In the extreme case, if you consider $ d=n $ then $m \log_n n < m \log_{m/n} n$, but the running time won't be better in practice. Because you need at most $ n $ min-extract operations, each includes a min-heapify. Therefore, you need $ n $ min-heapify operations, that will cost $ O(n) $ in this case (because $d=n$ and there are $n$ numbers in the next level of your tree). Thus the running time of your algorithms becomes $O(n^2)$ ($n$ times running min-heapify).


What is the reason behind a specific ordering of the rows in the generator matrix for Hamming codes? What order the rows are in a Hamming generator matrix are irrelevant for the Hamming coding to work, given the check matrix is built accoridngly.

In order to limit cognitive overload, it could have been decided that the "official" way of doing it should be either all data rows first then all parity rows after, all in ascending order, or just all rows in ascending order. In that case, in the description of a communications protocol it would be enough to specify the number of bits without providing the generator matrix, and everyone would know how to implement it. Very simple software libraries could be written which implement it.

However, after looking at some implementations, this is not the case. People seem to use arbitrary matrices, such as

$$\begin{pmatrix}
1 & 1 & 0 & 1  \\
1 & 0 & 1 & 1  \\
1 & 0 & 0 & 0  \\
0 & 1 & 1 & 1  \\
0 & 1 & 0 & 0  \\
0 & 0 & 1 & 0  \\
0 & 0 & 0 & 1
\end{pmatrix}$$

Is there a reason why one such ordering would be superior to other orderings?

If a single-bit error correction is attempted, the ordering presented in the example guarantees that the syndrome vector (the result of the multiplication of the checking matrix and the received data), if interpreted as an integer, will indicate the position of the error. Otherwise, a lookup table would have to be used.


The language of TMs accepting some word starting with 101 I have a homework question about the properties (decidability, Turing-recognizability, etc.) of the language

$$ L = \{ \langle M \rangle | \text{$M$ is a TM and $M$ accepts some string $w$ which has 101 as a prefix} \}. $$

I have made an attempt at showing decidability of $L$:

On input $\langle M, w\rangle$ (where $M$ is a TM and $w \in \sigma^*$):

Simulate $M$ on $w$.
If $M$ rejects and halts, reject. If $M$ accepts and halts, accept.

However, I'm not sure about moving forward after this. I do not want a solution, but I want some ideas/techniques as to what else I can prove about $L$.

First, it should be intuitive that L is not decidable.
Decidable means that you can can tell in finite amount of time if a word (in this case, coding of turing machine) is in L.
In m opinion, this should be one of the first things that should come in mind while solving these kinds of questions.

Note that there are infinitely many string that have $101$ as prefix (for example $101, 1011, 10111$, or in general, $101^i$ for $ i \geq 1$).

There are several problems with your solution.
First, the input for a TM for $L$ is $\langle M\rangle$, and not $\langle M, w\rangle$.
Second, what happens if $M$ doesn't halt on $w$? Your TM for $L$ also doesn't halt, and hence can't decide $L$.

You can show that $ L \in RE\setminus R $.

Show that $L \in RE $ by describing a TM $M'$ that recognizes $L$ (meaning, on input $\langle M\rangle$, if $ \langle M\rangle \in L$ then $M'$ accepts $\langle M\rangle$, otherwise $M'$ rejects or doesn't halt.

An easy way to show that $L\notin R$ is a reduction $f$ from the halting problem $HP$ to $L$, such that if $\langle M,w\rangle \in HP$ , then $f(\langle M,w\rangle) \in L$ (Hint: $f(\langle M,w\rangle)$ we accept any input if and only if $M$ stops on $w$).


Do I understand pseudo polynomial time correctly? The running time of knapsack is $O(n*W)$, but we always specify that this is only pseudo-polynomial. I was wondering if somebody could tell me if I understand the notion of pseudo-polynomial time correctly.

My current understanding is that pseudo polynomial time means polynomial in the magnitude of the input, and polynomial time is polynomial in the number of bits it takes to represent the input. Thus, looking through each element of an array is $O(n)$ in the magnitude of its length (pseudo-polynomial), but it is exponential in the number of bits in the length of the array. In the same way, binary search is $O(log_2 n)$ in the magnitude of the length of $n$, but is linear in the number of bits in $n$ making it "pseudo-logarithmic".

If I am correct, why do we never specify that binary search is linear in the number of bits, but we always specify that knapsack is exponential in the number of bits?

The running time for binary search that you quote applies for the so-called RAM model. I think that it is usually assumed that the machine words have size $\Theta(\log n)$ bits, where $n$ is some natural parameter like the length of the input.

For binary search, the input has size $\Theta(n)$, assuming that the array's datatype fits in a constant number of machine words, and so the running time $O(\log n)$ is logarithmic in the input size. The running time of the dynamic programming algorithm for knapsack is $\Theta(nW)$, but the size of the input is $O(n\log W)$ (in fact somewhat less, since machine words have superconstant size). This is not polynomial in the size of the input. However, if the weights are encoded in unary, then the size of the input is $O(nW)$ (again, actually somewhat less), and so the algorithm is pseudo-polynomial. It's a matter of encoding - whether you encode the weights in binary or in unary.


Running-time cost of Tweaked Nested Loop I understand that the following nested for-loop:

for(i=0; i<n/2; i++)
    for(j=0; j<n/2; j++)
         print(j)

has the runtime complexity of

which has a simplifed complexity of

but what is the resulting complexity of making j bound to i/2 in the inner loop? For instance:

for(i=0; i<n/2; i++)
    for(j=0; j<i/2; j++)
         print(j)

Would this be

?


Show that a language consisting of strings of a prime number of 1s is irregular using pumping lemma Question:

L is a language defined as $\ L = \{1^l | l\in primes\}$  (strings of 1s having a prime length). Show that this is not a regular language ($\ L \notin REG$). You may either use the theory of closure or the pumping lemma to prove this.

My try:

So far I have tried to take a word $\ w  | w=1^p$ ($\ p$ being the pumping value), but in this case I don't know how to prove that every decomposition of the form  $\ w=xy^i z$ is invalid. When  $\ |y|=p$ (and therefore  $\ x=z= \epsilon $) the lemma is clearly untrue, because when  $\ i = 2$,  $\ |w'| = 2p$ which is not prime. But in the case that  $\ y<p$, and  $\ x \neq \epsilon$ and/or  $\ z \neq \epsilon$, I don't see a way to prove that  $\ w' = x y² z$ is not prime.

Your attempt doesn't work, since you need the word you pick to belong to the language. Therefore I suggest picking $w = 1^p$, where $p$ is a prime which is larger than the pumping constant. The pumping lemma shows that there is a decomposition $w=xyz$, where $y \neq \epsilon$, such that $xy^iz \in L$ for all $i \geq 0$. Let $x=1^r$, $y=1^s$, and $z=1^t$, so that $r+s+t=p$. Then $xy^iz = 1^r 1^{si} 1^t = 1^{r+si+t} = 1^{p+(i-1)s}$. Thus, $p+(i-1)s$ has to be prime for all $i \geq 0$. However, when $i = p+1$, we get $p+(i-1)s = p+ps = p(1+s)$, which isn't prime.


Equivalence of Büchi automata and linear $\mu$-calculus It's a known fact that every LTL formula can be expressed by a Büchi $\omega$-automaton. But, apparently, Büchi automata are a more powerful, expressive model. I've heard somewhere that Büchi automata are equivalent to linear-time $\mu$-calculus (that is, $\mu$-calculus with usual fixpoints and only one temporal operator: $\mathbf{X}$).

Is there an algorithm (constructive proof) of this equality?

The constructive equivalence of linear-time fixed point formulae (the logic is called $\nu$TL by some) and Buechi automata is given in a paper by Mads Dam from 1992.

Fixed Points of Buchi Automata, FST&TCS 1992.

See page 4 for the construction of a $\nu$TL formula from a Buechi automaton. The construction of a Buechi automaton from a $\nu$TL formula is more complicated and takes the rest of the paper.
The rest of this reply is a brief argument that this result existed in the literature in far less direct form. Pierre Wolper showed that there were omega-regular properties that were not LTL-definable and gave an extension of LTL (called ETL) that could express omega-regular properties.

Temporal Logic can be more expressive, Pierre Wolper, Information and Computation, 1983.

It is also known that one can translate ETL formulae into $\nu$TL formulae, so by combining these results you can read off a translation of Buechi automata into $\nu$TL. In the other direction, it follows from the work of Buechi that S1S (the second order theory of one successor) formulae can be compiled into Buechi automata and by translating $\nu$TL formulae into S1S, we obtain a translation of $\nu$TL to Buechi automata.
If you want a more in-depth introduction to these topics, I suggest Mads Dam's lecture notes, or the work of Roope Kaivola (sadly not as widely known as much related work).

Temporal Logics, Automata, and Classical Theories - An Introduction, Mads Dam, ESSLLI 1994.
Using Automata to Characterise Fixed Point Temporal Logics, Roope Kaivola


Proving that A(B ∩ C) ⊆ AB ∩ AC A(B ∩ C) = { UV | U ∈ A, V ∈ B and V ∈ C } for the left part.

ΑΒ = { UV | U ∈ A, V ∈ B },

ΑC = { UV | U ∈ A, V ∈ c },

AB ∩ AC = { UV | U ∈ AB and AC, V ∈ AB and AC } for the right part.

How can I continue further into the proof?

As Yuval indicated, the most powerful and most popular proof technique is to use definitions.

The first principle of mathematical proof is by definitions. Always check the definitions. Whenever you are stuck in an unfamiliar area, look up the definitions first. We can not succeed in overemphasizing the importance of definitions. I can remember I had been chewing the definitions a dozen times in a row from time to time.

Here our task is to prove $A(B \cap C) \subseteq AB \cap AC$.

What is the definition of "$\subseteq$"?

  If $X$ and $Y$ are sets and every member of $X$ is also a member of $Y$, then $X$ is a subset of $Y$, denoted by $X\subseteq Y$.

So according to the definition, you are supposed to show

  if $w$ is a member of $A(B \cap C)$, then $w$ is also a member of $AB \cap AC$.

What does it mean by $w$ is a member of $A(B\cap C)$? It means $w=uv$, where $u\in A$, $v\in B$ and $v\in C$ as noted correctly in the question.

What are the members of $AB\cap AC$?

  The intersection of two sets $X$ and $Y$, denoted by $X \cap Y$, is the set of all elements that are members of both the sets $X$ and $Y$.

So you are supposed to show $w$ is a member of both $AB$ and $AC$. Since $w=uv$, where $u\in A$, $v\in B$, you know $w$ is a member of $AB$. Similarly, $w$ is a member of $AC$. Done.

  $AB \cap AC = \{ UV \mid U \in AB \text{ and } AC, V \in AB \text { and } AC \}$ for the right part.

Can you see where you made a mistake?