Algorithm to pick elements in one array that sum to a setpoint, and corresponding elements in other array to average to a setpoint? Note: The input file is an excel file. However, I am only looking for help with the algorithm as I can then code it in VBA.

I need to scan both columns (shown below) to find any number of column 1 values that when summed match the setpoint (E2) and column 2 values that when averaged match the setpoint (E3). One constraint is that the chosen values in column 1 and column 2 must be from the same row (or same 'index', shown in the image highlighted in blue and green).

Explanation of the solution below:
What it should do is say 'A2 and A6 sum to 7 (match cell E2), and the corresponding B2 and B6 average to 3' (match cell E3). Therefore, these rows should be selected/highlighted in any appropriate way. (note that technically the first solution would be rows 2 and 3 as they fit the sum/average setpoints also).

Example that does not work as a solution:
It can't be A4 and A5 because although they add to 7, B4 and B5 average to 1.5, not the setpoint of 3.

Image of the problem (with a solution highlighted):

A solution for one of the cases (below) works only for the case where there are two rows that will sum/average to the setpoints. It will not work for cases where more than two rows are required. The solution should work for any number of rows required.

Example where three rows would be required (Solution is the first three rows):

Reason for this solution: B6:B8 sums to the setpoint of 8 and C6:C8 average to the setpoint of 3

I am looking for help with an algorithm. If the solution is a large number of rows required (>100), how can I iterate through the combinations efficienctly to find a set of rows that both sums/averages to the setpoints?

It may not be possible to find a solution to both setpoints, in this case finding a solution within an error is also ok

Note: If there is a more suitable stack exchange please advise.

Finding an algorithm is NP-Hard, therefore I am also looking for appropriate simplifications to avoid this. An error term may be an example of one simplification.

In general, no; this problem is NP-hard.  Even matching just the sum (without getting into anything about the average) is NP-hard, as it is the subset sum problem.  Thus, you should not expect any efficient algorithm for your problem that works for all possible inputs.

I notice that in your examples, the numbers are all small.  For that special case, there are reasonably efficient algorithms using dynamic programming: see, e.g., https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution.

The dynamic programming algorithm in that link describes how to make the sum match, but you can adapt it to make both the sum and average match.  In particular, you have an array $Q[t_1,t_2,i,k]$, which you will fill in with True if there exists a subset of $k$ out of the first $i$ rows whose first column sums to $t_1$ and whose second column sums to $t_2$.  You can use dynamic programming to fill in this array (in order of increasing $i$) in $O(N^4M^2)$ time, where $N$ counts the number of rows in your spreadsheet and $M$ is the largest number in the spreadsheet.  Then, once you've filled in this array, there will be a selection that sums to $s$ and averages to $a$ if and only if there is some $k$ such that $Q[s,ak,N,k]$ is True.

I recommend implementing this in a programming language (e.g., VBA, not Excel).  Implementing it in Excel might be possible but it sounds painful.  See https://cs.stackexchange.com/tags/dynamic-programming/info for our reference material on dynamic programming; if you're not familiar with that subject, you might want to read a textbook introduction to it.


Meyniel's theorem + finding a Hamiltonian path for a specific graph family Let's say we have a directed graph $G = (V, E)$ for which $(v, w) \in E$ and/or $(w,v) \in E$ holds true for all $v, w \in V$. My feeling is that this graph most definitely is Hamiltonian, and I want to find a Hamiltonian path in it (from any vertex to any other vertex, I don't care where to start or stop).

I wanted to refer to Meylien's theorem for this:

  A strongly connected simple directed graph with $n$ vertices is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to $2n − 1.$

There are two subtleties that I'm not sure about with this theorem:

What is meant by "adjcent vertices". Does the order matter here? Is the pair $(v,w)$ adjacent even if $(w,v) \in E$ but not $(v,w)$ itself? If that is the case and the graph is strongly connected, than it must obviously be Hamiltonian, since there are no non-adjacent pairs of vertices at all.
A graph with the above property is not necessarily strongly connected. I think this is easy to solve: We can just decompose the graph into SCCs. We will still have no non-adjacent pairs of vertices in the components and all of them are Hamiltonian. We can then construct a Hamiltonian path of the whole graph by connecting them in topological order.

Is the above reasoning correct and the theorem applicable? Or is there some other argument we can use to show that there is a Hamiltonian path in the graph?

In the end I want to actually find the Hamiltonian cycles in the SCCs, but haven't had much luck finding a constructive proof of the theorem, let alone an algorithm that solves this. Can it be done in a straightforward way? I feel like some kind of greedy approach could work, where we take the nodes in decreasing order of outdegree or something similar.

It is enough to prove your claim for the case of a tournament, in which for every pair of vertices $v\neq w$, exactly one of the edges $(v,w),(w,v)$ is in the graph. Wikipedia has an algorithmic proof that every such graph has a Hamiltonian path. If the tournament is strongly connected, it has a Hamiltonian cycle.


Efficiently inserting into list keeping number of inversions minimal Assume two lists of comparable items: u and s. Let INV(u) be the number of inversions in u.

I am looking for an efficient algorithm to insert the items of s into u with a minimal increase of INV(u).

Basically I would like to insert objects into a list while keeping it "as sorted as possible" while keeping the order of the first list.

Example:

u = [4,6,2,9,7]
INV(u) = 3 ((4, 2), (6, 2) and (9, 7)

s = [8,3,10]

one optimal solution u' = [3, 4, 6, 2, 8, 9, 7, 10]
INV(u') = 5 ((4, 2), (7, 2) and (9, 7) + (3,2), (8,7))

different optimal solution u' = [3, 4, 6, 2, 9, 7, 8, 10]
INV(u') = 5 ((4, 2), (7, 2) and (9, 7) + (3,2), (9,8))

As you can see there is no unique optimal solution.

I'd be glad for any sort of ideas or direction to look into.

This is an elaboration on on trevore's answer. It's too long to fit in a comment and contains the proofs of his solution (or at least how I understand it).

You can show that in any optimal solution, the elements of $s$ will appear ordered. If not, assume $s_1 < s_2$ and they appear in reverse order in an optimal solution. Let $\sigma_1$ be the number of elements between $s_1$ and $s_2$ that are less than $s_1$ and $\beta_1$ be the number of those that are bigger than $s_1$. Define $\sigma_2$ and $\beta_2$ similarly for $s_2$. Note that $\sigma_1 \leq \sigma_2$ and $\beta_2 \leq \beta_1$. Swapping $s_1$ and $s_2$ will change the number of inversions by $-\beta_1 + \beta_2 - \sigma_2 + \sigma_1 - 1$ which is at most -1.

It is not hard to see that elements of $s$ can be inserted independently. Since they appear ordered, the elements of $s$ do not "feel" each other's presence. That is, pairs of elements from $s$ do not contribute to the inversion count. To do that, insert the median of $s$ optimally in linear time. Then, recursively, insert elements of $s$ less than the median to the left of the median and elements bigger than the median to its right.

Let the median be inserted in position $k$, the runtime of this satisfies, $T(|s|, |u|) = T(|s| / 2, |u| - k) + T(|s| / 2, k) + |u| + |s|$, the linear $|s|$ factor is for finding the median and shuffling the elements of $s$. It is easy to show by induction that $T(|s|, |u|) = O(|s| \log |s| + |u| \log |s|)$.

Note that the dependence on $|s|$ here is optimal. Since solving the problem with empty $u$ is equivalent to sorting $s$ using only comparisons. The dependence on $|u|$ is also optimal, since the problem for a singleton list $s$ and a list $u$ must require linear work.


Comparing DFA's produced languages I'm working on some questions to bone up on my knowledge of DFA's for a computing class and I've run across the following problem that is giving me some issues. If we have some
DFA M = (Q, Σ, δ, q0, F) and some other DFA M' = (Q, Σ, δ, q0, F') where F is a proper subset of F', are the following relations possible or not between the two produced languages?

1) L(M) ⊂ L(M')

2) L(M) ⊃ L(M')

My current theory is that the first one is not possible, due to the fact that the first machine has fewer finish states than the other, thus the language must be larger and cannot be subset to M'. This would of course mean that the second relationship is possible, since M must contain M'. Am I on the right track here and if so, how could I prove this?

L(M) ⊂ L(M') can be proved as below:

Suppose a string 'w' ∈ L(M') .Since it is given that F is a proper subset of F' , there exists a state q1 such that
q1 ∈ F' but not to F.
Since the transition function is same for both the DFAs, hence there is a transition possible as below:
δ(q0, w) = q1which means the state change takes place from the initial state to the state q1 on reading the input symbols from the string 'w'.

Since q1 ∈ F' but not to F, we can say that 'w' does not belong to L(M).
On the same lines it can also be proved that any string in L(M) is also present in L(M'), thereby proving the relation.


creditcard validation - why does nit not fail for 7 digits? using luhns credit card check algorithm why is digits with 7 length allowed ?  for example 1111111 is a verfied credit card number meaningly if it has only six digits its not. this does not look like a credit card number to me, am i missing something ?

go to any online credit card validation site and try 1111111 and see that it returns valid. why ?

I have tried going to the following websites: http://www.dcode.fr/luhn-algorithm and a few others.

Luhn's algorithm, as described in Wikipedia, works for any number of digits. It will detect any single digit change and most swaps.

As for an internet website which accepts credit card numbers of the wrong length - the blame should be on the designers of the website who neglected to enforce this restriction, not on Luhn's algorithm, which performs as advertized.


Power of adjacency matrix Let $G$ be a weighted graph with a weight function $w \longrightarrow \mathbb{R}^{+}$. Let $G'$ denotes the weighted matrix with adjacency matrix
$$A_{G'} = \sum_{i=0}^{k} (xA)^{i}$$
where $k$ is integer and $x$ is a variable.
I am not getting what is $A_{G'}$ matrix? Is it contains all walks of length $k$ or is it something else?

As you probably know, $A^i_{st}$ is the total weight of walks of length $i$ from $s$ to $t$. Since
$$
\sum_{i=0}^k (xA)^i = \sum_{i=0}^k A^i x^i,
$$
the $s,t$ coefficient of $A_{G'}$ is
$$
\sum_{i=0}^k A^i_{st} x^i.
$$
This is a polynomial in which for $0 \leq i \leq k$, the coefficient of $x^i$ is the total weight of walks of length $i$ from $s$ to $t$.


Why is this algorithm $O(n^3)?$ In a programming book that I'm currently reading it's stated that

$$\sum\limits_{i=1}^{n}i^2$$ is $O(n^3)$. My understanding was that $i\times i$ is a primitive operation and the complexity would be $O(n)$. What am I missing?

The expression
$$ \sum_{i=1}^n i^2 $$
is not an algorithm. It is just a number. In fact, what the book really means is the function
$$ n \mapsto \sum_{i=1}^n i^2. $$
Since
$$ \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} = \frac{2n^3+3n^2+n}{6}, $$
we see that this sum is indeed $O(n^3)$, in fact, even $\Theta(n^3)$.

We often use big O notation in analyzing the running time of an algorithm. Quicksort runs in time $O(n\log n)$ (on average) since the function $T(n)$ measuring its average running time on inputs of length $n$ is $O(n\log n)$ — the function $T(n)$, not the algorithm itself.


What is the space complexity of function $f(x) = \sum_{i=1}^x g(i)$ where g(n) is O(n)? What is the space complexity of function $f(x) = \sum_{i=1}^x g(i)$ where g(n) is O(n)?

Is it O(n) because the maximum stack size is n, or is it O($n^2$) because there are $n(n+1)/2$ memory references?

Space complexity is about the maximum stack size, so this function uses $O(n)=O(\log(x))$ space. Your intuition about this is right: each call to $g$ uses and overwrites memory previously used by the previous call to $g$, so the stack grows to $O(n)$

Why the $\log(x)$ factor? If $g$ uses $O(n)$ memory for an $n$-bit input, then it uses $O(n)=O(|x|) = O(\log(x))$ memory for input $x$, which is of length $|x|=\log(x)$.


Why does the recurrence equation for QuickSort consider all the elements in the array? I have been taught that QuickSort has the following recurrence equation in the best case:

$T(n) = \begin{cases} c & \text{if } n=1 \\ 2\ T(\frac{n}{2}) + c \cdot n & \text{if } n>1 \end{cases}$

where $c \in \Theta(1)$ and $c \cdot n \in \Theta(n)$. As well for the general case:

$T(n) = \begin{cases} c & \text{if } n=1 \\ T(q) + T(n-q) + c \cdot n & \text{if } n>1 \end{cases}$

Moreover, the algorithm used in the lecture was the following:

Procedure QuickSort(A[p,...,r])
    if p < r
        q = Partition(A, p, r)
        QuickSort(A, p, q-1)
        QuickSort(A, q+1, r)

As you can see, the recursive calls don't take care of the pivot element $q$. I understand this occurs as Partition moves elements around until the pivot is where it should be is the array ordered. The following is the Partition algorithm:

Function Partition(A[p,...,r], p, r)
    x = A[r]
    i = p-1
    for j = p to j = r-1 do
        if A[j] <= x
            i = i+1
            Exchange(A[i], A[j])
    Exchange(A[i+1], A[r])
    return i+1

My question is: Why do the recurrence equations assume the algorithm takes all the elements of the array (let it be $n$) if the actual algorithm only takes $n-1$ elements?

Why can't it be the following?

$T(n) = \begin{cases} c & \text{if } n=1 \\ 2\ T(\frac{n-1}{2}) + c \cdot n & \text{if } n>1 \end{cases}$

Or, more generally, this one?

$T(n) = \begin{cases} c & \text{if } n=1 \\ T(q) + T(n-q-1) + c \cdot n & \text{if } n>1 \end{cases}$

When you're looking at the behaviour of the algorithm as $n\to\infty$, the difference between $n$ and $n-1$ becomes negligible. The simpler form is easier to deal with and it gives the same answer.


Complement of NP-complete can be in NP Here are a couple of questions I struggle with.  (We use $A'$ to denote the complement of the problem $A$.)

A problem $A$ is NP-complete if and only if $A'$ is in NP?
A class problem $A$ is NP-Complete iff $A'$ is in NP?  (Is there any difference between these two?)

I got this claim to be true that

  If there is an NP-complete language $L$ whose complement is in NP, then the complement of any language in NP is in NP.

And this claim also to be true:

  $A$ is NP-hard iff $A'$ is coNP−hard

Then is the upper claim also true?

A problem $A$ is NP-complete if and only if $A'$ is in NP?

This is false. Take $A'=\emptyset$: then we have $A'\in\mathrm{NP}$ but $A=\Sigma^*$ is not $\mathrm{NP}$-complete.

  If there is an NP-complete language $L$ whose complement is in NP, then the complement of any language in NP is in NP.

This follows from the following three facts, which you should attempt to prove yourself.

The complement of an $\text{NP}$-complete problem is $\text{co-NP}$-complete;
if any $\text{co-NP}$-complete problem is in a class $\mathcal{C}$ that is closed under polynomial-time reductions, then every $\text{co-NP}\subseteq\mathcal{C}$;
$\text{NP}$ is closed under polynomial-time reductions.


Binary Indexed Trees: Why does i & -i work? I already read this related question on the intuition behind binary indexed trees, and while the answer explains how the tree structure works, it does not really explain how this correlates back to the array representation where the next node is accessed based on the current nodes index according to $i \mathrel{\&} -i$.

I know physically that $i \mathrel{\&} -i$ gives you the highest power of 2 that divides $i$, essentially the least significant set of bits, but I don't see why adding or subtracting this to/from the current index allows you to jump around to get to the wanted node.

Linking this back to the tree representation,

      4
   /     \
  2       6
 / \     / \
1   3   5   7

I see how the left parent of a node with index N is $(N - 2^h)$ and the right parent is $(N + 2^h)$ where h is the height of the subtree from N down (including N), and this seems to be related to why the $i \mathrel{\&} -i$ works.

However, what about the cases like finding the previous node of 5, which according to $5 - 5\mathrel{\&}-5$ is 4? The formula $N - 2^h$ also seems to work except there is no direct link between 4 and 5. How do you prove that it works in these cases too?

Assuming that your tree is storing cumulative sums, one query you would like to make is "what is the cumulative sum to index n".  Suppose the tree is as shown in the OP, and n is 5.  The answer to the question would be found by adding the sum in node 4 and the sum in node 5.  This is because each node is storing the cumulative sum of itself plus its left subtree (if any).  Thus, node 4 has the cumulative sum of indices 1-4 and node 5 has the cumulative sum of index 5 (just itself).  Because of the way the tree is built, you basically need to visit one node for each 1 bit in the binary representation of your index.

So the algorithm to compute the cumulative sum is to start at the given index, in this case 5.  Note that 5 is 101 in binary.  Add its sum to the total.  Then, to get to the next node needed, we want to remove the least significant bit (we want to get from 101 to 100).  The least significant bit of i is i & -i.  To remove the least significant bit, i -= (i & -i).  That gets us to node 4.  We add node 4's sum to the total.  Then we remove the next significant bit, leaving 0 which means we are at the end.

If the tree were bigger, and the starting index were 50 (which is 110010 in binary), we'd have to visit node 50 (110010), node 48 (110000), and node 32 (100000).  In this example, node 32 contains the sums of 1-32, node 48 has the sums of 33-48, and node 50 has the sums of 49-50.


$\text{"The error entries in the goto table are never consulted"}$ - intuitive explanation of the above claim with respect to $LR$ parsing tables I was going through the text : Compilers: Principles, Techniques and Tools by Ullman et. al where I came across a claim:

$\text{"The error entries in the goto table are never consulted"}$

I feel that whenever there is a reduce move, the current state pointer moves some states back. Suppose that $A\rightarrow \alpha$ is the production used and for the viable prefix $\gamma\alpha$ the current state pointer moves back those many states (so as to pop the $\alpha$ from the stack) and goes to state say $I_n$ and there is a move from $I_n$ on $A$ to some state $I_{n'}$.

The goto table is only used immediately after a reduction action, which has just restored the parser state to the state in which the reduced non-terminal follows the dot. So the goto table for that state must have a state transition for that non-terminal; it's not an error entry.
So the error entries are never consulted.


Strongly NP-hard problems and Dynamic Programming Dynamic Programming seems to result in good performance algorithms for Weakly NP-hard Problems. Two examples are Subset Sum Problem and 0-1 Knapsack Problem, both problems are solvable in pseudo-polynomial time using Dynamic Programming. It turns out this is a pretty good result in most cases.

On the other hand, Strongly NP-hard Problems seem to be essentially exponential even by using Dynamic Programming. For example, the Multiple 0-1 Knapsack Problem (page 11).

Is this a true claim if I generalize my observations and state Dynamic Programming is good for Weakly NP-hard Problems but it is not suitable for Strongly NP-hard Problems?

You're generalizing too much from a small sample size.  There is no guarantee that all weakly NP-complete problems can be solved using dynamic programming; I'd expect probably there are some that dynamic programming isn't much good for.

And, there is no guarantee that a strongly NP-hard problem will take exponential time to solve.  There are NP-complete problems that can be solved faster than exponential time.  (See also the exponential time hypothesis.)

Dynamic programming is just one algorithmic technique among many.  There's nothing magical about it, and it's not a be-all and end-all.  There are other algorithmic methods other than dynamic programming.


What is the correct algorithm to see whether N points lie on the same side of a line? What I tried first was to find the equation of the line and then compare its y-intercepts with the y-intercepts of each point. I just need the proper approach to this algorithm.

A quick theorem, in general:

A hyperplane in $\mathbb{R}^d$ can be defined by a vector
$\mathbf{v}$ and scalar $b$ as the set of points $\mathbf{x}$ such that $\mathbf{v}^T\mathbf{x} =
b$. It splits the
space $\mathbb{R}^d$ up into two half-spaces, one where $\mathbf{v}^T\mathbf{x}
\geq b$ and one
where $\mathbf{v}^T\mathbf{x} < b$.

So in 2D, if your line is defined by $\mathbf{v}, b$, all you have to do is check whether
either $\mathbf{v}^T\mathbf{x} \geq b$ or $\mathbf{v}^T\mathbf{x} < b$ holds for all your points $\mathbf{x}$.

You are probably used to a line being defined as $y = ax + b$. Note that we have
$\mathbf{x} = \begin{bmatrix}x\\y\end{bmatrix}$ (beware of the bold $\mathbf{x}$ as opposed to $x$).
Thus we can rewrite to a matrix equation:
$$y = ax + b$$
$$-ax + y = b$$
$$\begin{bmatrix}-a, 1\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} = b$$
$$\mathbf{v}^T\mathbf{x} = b$$
and we recover the above form, where $\mathbf{v} = \begin{bmatrix}-a\\1\end{bmatrix}$.
Thus all we have to do to check is if your points are a list of $(x, y)$ pairs is if either $-ax + y \geq b$ or $-ax + y < b$ for all of them.


Which algorithm is this? I'm looking for someone who can tell me which algorithm this is and help me to clearify what the variable mean.

$g_j$ : the shortest path length from $1$ to $j$
$t_{i,j}$: the length from $i$ to $j$
$\mathrm{SCS}$: successive set
$S$: Start node, $G$: Goal node

\begin{align}
   &f_G = 0 \\
   &f_i = \infty, \forall i ≠ G \\
   &t_{i,j} = \infty, \forall (i, j) \notin T \\
   &t_{i,j} > 0 , \forall (i, j) \in T\\
   &T = \{1, 2, . . . , N − 1, N\}, \quad Ť = \{\emptyset\} \\
   &\text{Do while $T$ is not empty} \\
   &\qquad j^* = \arg\min_{j\in T} f_j \\
   &\qquad \text{for }i \in \mathrm{SCS}(j^*)\\
   &\qquad\qquad f_i  = \min \{f_i , t_{i,j}^* + f_j^*\}\\
   &\qquad \text{Remove $ j^*$ from T, add $j^* $ to Ť} \\
   &\text{Stop while }j^*= S
\end{align}

It looks like a Dijkstra algorithm to me.

I see the algorithm begins at the "do while" line and everything before are the input for the algorithm. With your clue that G is the goal node, and $t_{i,j}$ are lengths, it is easy to see $f_i$ is the distance from $i$ to G as we know so far within the loop.

So the algorithm means the following:

Every iteration, we find the node $j^*$ within T that has min distance to G
Then we scan each of its neighbor $i$, update their distance to G

update rule: they reach G with traversing $j^*$ or without (i.e., the old $f_i$), so min of these two will be the new known min distance to G

After this scan, all nodes that can possibly reach G via $j^*$ are updated. And we remove $j^*$ from T, meaning that in the future, any other node (not neighbor to $j^*$) to reach G via $j^*$ should only be via one of its neighbor $i$

Here the $t_{i,j}$ are positive, so that adding to $f_{j^*}$ can only increase the distance. And hence all $f_i$ will only be decreasing in each iteration. In this case, this algorithm is a dynamic programming by iteratively reducing the problem to a smaller set of nodes until a solution is found.


Asymmetric encryption puzzle I came across this riddle link question:

Your name's Graham.
Bob wanted to send Alice a secret msg m. However, he was concerned about the security. He encrypted his message with a keyword that both of them knew. Several weeks before this, you overheard them exchanging the keyword k = 'EZRA'. Now, Bob has asked you to deliver the letter to Alice. You want to find out what's the letter about. Decrpyt the secret message m using the ciphertext c='MEDMTBJBMAE'.

The answer to this question was HELLO GRAHAM. How could one deduce that without knowing the answer of course.
What can we deduce from the keyword EZRA?

Convert A = 1, B = 2, ..., Z = 26. Take the difference of (cipher text - key) modulo 26. Extend "EZRA" with itself. The third row is the difference between the first and second rows. There might be an error on 'B' and 'G'.

 M  E  D  M  T  B  J  B  M  A  E
13  5  4 13 20  2 10  2 13  1  5

 H  E  L  L  O  G  R  A  H  A  M
 8  5 12 12 15  7 18  1  8  1 13

 5 26 18  1  5 21 18  1  5 26 18

 E  Z  R  A  E  Z  R  A  E  Z  R
 5 26 18  1  5 26 18  1  5 26 18


Copy operation in under 9 states? There is a long row of cells. Each cell contains 0 or 1. A machine is positioned immediately to the right of a series of uninterrupted 1’s followed by an uninterrupted series of 0’s. In the following graphic the machine is denoted by a yellow line. It is immediately to the right of a series of three 1’s followed by many 0’s.

The machine is tasked to make a copy of the 1’s. When finished, the copy must be separated from the original by a single cell containing a 0. The final resting place for the machine is immediately to the right of the original 1’s. The following graphic shows the cells after the machine has fulfilled its copy task.

At each step the machine must decide whether to move left one cell or right one cell, and whether to write 0 or 1 to the cell that it is currently positioned at. The machine cannot see what is in the neighboring cells. It can only see the value in the current cell. The machine makes its decision based purely in the current cell’s value and on the decisions it made previously.

I was able to program the machine to perform the copy operation using nine states (S0 – S8).

QUESTION: Is there a way for the machine to perform the copy operation in less than nine states?

The above graphics show just one example, in which three 1’s are copied. Of course, the machine must be able to perform the copy operation on any number of 1’s.

The diagram below shows the nine states that I needed. But first, here is an explanation of a notation used in the diagram:

Here is the strategy I used: As described above, the 1’s must be copied. How to know which 1’s have been copied and which remain to be copied? Answer: Shift the leftmost 1 to the left one cell and then copy it. Repeat for the next leftmost 1. And so on. There will be a series of shifted 1’s that have been copied and a series of unshifted 1’s that remain to be shifted and copied. Once there are no more unshifted 1’s, the machine is done. State 0 is the final state. State 1 is the starting state.

Input: 0^a 1^b 0^c with a + c >= b + 1

Output: 0^z 1^b 0 1^b with b + z + 1 = a + c

Strategy:

Move 1^b to the back of the tape
Copy 1^b immediately to the left
Clean up

States:

q0: scan left until you see 1; if beginning of tape, continue with state q3. Otherwise, change 1 to 0 and continue to q1
q1: scan right until blank or 1; then, move left and continue with state q2
q2: change 0 to 1, go left, and continue with q0
q3: scan right until you find 1; if you do, change 1 to 2, move left and continue with step q4; otherwise continue with state q6
q4: scan left until you find 0; then, move right and continue with state q5
q5: scan left until you find 0; when you do, change it to 2, move right, and continue with state q3
q6: scan left until you find a blank, changing all 2s to 1s along the way. then, halt-accept.

If you count halt-accept as its own state, this has 8 states, so it's at least one better than the one you gave (if this one works). Here's how I'd see it processing your example:

   0000001110: q0
-> 0000001101: q0, q1, q2, q0
-> 0000001011: q0, q1, q2, q0
-> 0000000111: q0, q1, q2, q0
-> 0000020211: q0, q3, q4, q5, q3
-> 0000220221: q3, q4, q5, q3
-> 0002220222: q3, q4, q5, q3
-> 0001110111: q3, q6, halt-accept


Are there adversarial inputs for randomized quicksort? Someone recently claimed that there's an adversarial input for randomized quicksort; he referenced this paper. This defies my intuition because there are results that say that randomized quicksort runs in $O(n \log n)$ time with high probability. (See, for example, the book Randomized Algorithms by Motwani&Raghavan.) I am refering to the version of randomized quicksort that picks the pivot uniformly at random at each recursive call.

So my question is: are there indeed adversarial inputs for randomized quicksort? Please give an intuitive reason as to why such an input can exist.

Update. It seems to me that the adversary in the paper is granted unrealistic capabilities (generate array on the fly), which explains why it can make any quicksort perform poorly. Under reasonable assumptions I would say there is indeed no adversarial input for randomized quicksort.

There are implementations of Quicksort (the partitioning algorithm, specifically) which deal badly with duplicates. No matter how much you randomize -- shuffling the input, random choice of the pivot, random choice of the pivot with sampling, ... -- if all entries are the same (or there are only constantly many distinct values), these bad implementations will result in worst-case behaviour, always.

You can find details e.g. here and in the literature.

Note bene: The reason why many TCSists would claim the opposite with a passion it that they forget that most classical analyses are performed under permutation models. That does not give the whole truth, though, particularly if you use sorting in practice. Duplicates are relevant, for instance if you sort lists of binary values.


A question on the linear speedup theorem I am trying to understand the linear speedup theorem:

Let $L$ be a decidable language. Let $X^L$ be the set of all deterministic Turing machines which decide $L$. For a word $x \in \Sigma^*$ define:
$t^L(x) := \min_{M \in X^L} t_M(x)$ where $t_M(x)$ is the time of $M$ on input $x$. Now let's choose some machine $M$ which satisfies $t^L(x) = t_M(x)$. Then for all $A \in X^L$ we have:

$$t_M(x) \le t_A(x)\,.\qquad(**)$$

Now let's apply the linear speedup theorem for the machine $M$: We get a new machine $N$ such that:

$$t_N(x) \le t_M(x)/2 + |x| + 2\,.$$

But by (**) we have: $t_M(x) \le t_N(x)$ hence it follows, that
$t_M(x) \le t_N(x) \le t_M(x)/2 + |x| + 2$. From this it follows that
$t_M(x) \le 2 |x| + 4$.

But how can this be? It means that, for every word $x \in \Sigma^*$ there exists a deterministic Turing machine $M$ which decides $L$ such that the time of $M$ on input $x$ is at most $2|x| + 4$.

This seems very absurd. What am I doing wrong?

I didn't check your working but your conclusion isn't at all absurd.  For every Turing machine that decides $L$, and for every $x\in\Sigma^*$, there is another Turing machine $M_x$ that decides $L$ and that runs for exactly $|x|+1$ steps on input $x$. Note that this is more than twice as fast as your conclusion of $2|x|+4$. This also means that, for all languages $L$ and all strings $x\in\Sigma^*$, $t^L(x)=|x|+1$.

$M_x$ operates as follows. First, it reads the first $|x|+1$ characters of the input.  If these are the string $x$ followed by a blank, it accepts if $x\in L$ and rejects if $x\notin L$; if they are not $x$ plus a blank, it returns to the left-hand end of the tape and does whatever $M$ would do. Note that $M_x$ does not need to contain any algorithm to decide whether $x\in L$. If $x\in L$, the machine is programmed "If my input is $x$, accept it; otherwise, rewind and do what $M$ would do.", and if $x\notin L$, the machine is programmed "If my input is $x$, reject it; otherwise, rewind and do what $M$ would do."


Data structure for a tree of points moving in space I'm trying to come up with a data structure for a following model: Nodes representing points in space are structured in a tree (general rooted tree with no restrictions). Let's call these nodes "joints". Joints contain information about their position and their axis of rotation: Whole subtrees may rotate around their parent joint's axis by any given angle.

The described tree can be treated as the input. I need to store this data in some data structure, that would provide these two operations as efficient as possible:

rotate(id, angle): Rotate a given joint with its subtree by a given angle around its parent's axis.
get_position(id): Retrieve the current position of a joint (including leaves) by its id.

(The id may be the original coordinates, some arbitrary integer stored inside the joint etc.)

There are no strict limits on the time complexities of these operations. But obviously I'm looking for a complexity better than linear (logarithmic would be ideal), as that could be achieved with a straightforward approach. Neither there are any strict limits on space complexity. This structure doesn't have to be dynamic necessarily: I don't need insert or delete operations, I only need to store the information about the joints once.

The input tree is not balanced, and there is no way to balance it, as it would loose information about the subtrees' dependencies. So I thought the natural approach would be to construct a different tree structure with some relation other than simply parent node -> subtree as joint -> joints dependent on its rotation. But what relation could give me some good results?

You can solve this with a heavy-light decomposition of the tree.  This will give you a data structure where the "rotate" operation runs in $O(\log n)$ time and the "retrieve position of leaf" operation runs in $O(\log^2 n)$ time, where $n$ is the number of nodes in the tree.  Heavy-light decomposition is a big cannon, so it's possible there might be some simpler solution, but this should work.  Let me explain the ideas in several steps.

Closure property of affine transformations

If $T$ is a a rotation around some point in space, note that it can be represented as an affine transformation.  Also, the set $\mathcal{T}$ of affine transformations is closed under composition.  In particular, if $T_1,T_2$ are two affine transformations, let $T_2 \circ T_1$ denote the result of first applying transformation $T_1$, then applying transformation $T_2$; then $T_2 \circ T_1$ is itself an affine transformation, and its parameters can be efficiently computed from the parameters of $T_1,T_2$.  So, if we have a sequence of transformations that should be applied to a point, we can concisely represent the composition of the sequence of transformations by $O(1)$ parameters (namely, the parameters of their composition).  This will be useful in a moment.

In particular, rather than updating the position of individual nodes, we will store information to help us recover the transformation that should be applied to any particular node.  When we want to retrieve up the location of a node, we first look up this transformation, then apply it to the original location of that node to obtain its current location, and output that.

Warm-up: a path

As a warm-up, let's consider the most extreme special case of your situation: where the tree is a path of length $n$, i.e., each node has exactly one child, and there is a single leaf.  I'll assume each node in this original tree may have a position associated with it.

Data structure. We can build a data structure for this case where all operations run in $O(\log n)$ time.  Build a complete binary tree (of height $\lceil \lg n \rceil$) over these $n$ nodes; to give it a name distinct from your original tree, call this the "index tree".  Each node of the original tree is a leaf in the index tree.  Each node $w$ of the index tree corresponds to a consecutive subpath of the original tree/path (namely, the ones corresponding to the leaves of the index tree that are descendants in the index tree of $w$).

Now each node $v$ of the original tree has a transformation $T_v$ associated with it.  Suppose a node $w$ of the index tree corresponds to the subpath of nodes $v_1,\dots,v_k$ in the original tree.  Then we will label $w$ with the transformation $T_{v_k} \circ \cdots \circ T_{v_1}$.  This will help us to retrieve the position of points in the original tree.

Rotation operations. To support rotation operations, if we want to rotate node $v$ in the original tree and all its descendents, then we follow the path  (in the index tree) from $v$ to the root of the index tree.  By construction, there are only $\lg n$ such nodes to visit.  We'll need to update the label on each of these nodes in the index tree.  That is easy.  In particular, the label $T_w$ on each node $w$ in the index tree can be computed from the labels $T_{w_1},T_{w_2}$ on its two children $w_1,w_2$ as $T_w = T_{w_2} \circ T_{w_1}$.  So, to handle a rotation operation on node $v$ in the original tree, we update the the label on $v$ in the index tree, then follow the path (in the index tree) from $v$ to the root of the index tree and recompute the label of each such node in the index tree.  All of this can be done in $O(\log n)$ time.

Retrieval operations. If we want to retrieve the location of the point associated with node $v$ in the original tree, we can do that in $O(\log n)$ time, too.  Consider the path in the original tree from its root to $v$.  This is a subpath of the original tree.  It turns out that it can be expressed as the disjoint union of $O(\lg n)$ subpaths, where each subpath corresponds to a node in the index tree.  Let $w_1,\dots,w_k$ be those nodes in the index tree.  Then the transformation that needs to be applied is $T_{w_k} \circ \cdots T_{w_1}$; we apply this to the original location of $v$, and output that.  This can all be done in $O(\log n)$ time.

So this handles the case of a path, i.e., a tree of depth $n$.  This shows that it is possible to handle imbalanced trees.  But how do we handle the general case?  I'll show that next.

General case: an arbitrary tree

To handle an arbitrary tree, we will first build a heavy-light decomposition of the tree.  This expresses the edges of the tree as a union of (disjoint) heavy paths, plus some light edges; with the property that any path from the root to some leaf visits at most $O(\log n)$ light edges.  We'll treat each individual heavy path as a case of the warmup above, i.e., we'll build one index tree per heavy path, to keep track of the transformations associated with the nodes in the heavy path.  Also, we'll have a path tree that stores the light edges, and we'll store the transformation associated with the head of a light edge in that node of the path tree.

Rotation operations. To handle a rotation operation, we update the associated node in the path tree (if it is the head of a light edge) or do the appropriate update operation on the corresponding index tree (if it is the head of a heavy edge).  This can be takes $O(\log n)$ time at worst.

Retrieval operations. To retrieve the location of a node $v$ in the original tree, we follow the path in the path tree from the root to $v$.  This will involve traversing at most $O(\log n)$ light edges.  It also traverses at most $O(\log n)$ heavy paths.  In each heavy path, we might potentially traverse many vertices of the heavy path (possibly much more than $O(\log n)$ of them), but we don't need to visit all of them; since that is a consecutive subpath of the heavy path, we can quickly retrieve the transformation associated with that subpath (i.e., the composition of the transformations of the nodes in that heavy path) using the index tree for that subpath.  This takes $O(\log n)$ time per heavy path, and there are at most $O(\log n)$ heavy paths to visit.  Finally, we compose all of these transformations and apply it to the original location of $v$.

Naively, the running time seems to be $O(\log n)$ time for the light edges, plus $O(\log n) \times O(\log n)$ time for the heavy paths, for a total of $O(\log^2 n)$ time.

This achieves all of your goals, and gives a guaranteed worst-case running time of $O(\log n)$ for the rotate operation and $O(\log^2 n)$ time for the lookup operation, no matter what shape the original tree has.


Does RAM take the copy of the program or does it load programs from the hard disk? I guess it copies, since it is a temporary memory, it will erase if power is not supplied, so, that will lead to data loss right, but still, I need clarification.

Ram used to load a program because ram is a volatile memory i.e. after. Power cut or after the task is over the data in ram is lost so all the data is saved in. Our hard disk
Here. Copying and loading are equivalent in this case


How to calculate virtual address space from page size, virtual address size and page table entry size? I try to solve an exercise, unfortunately without any success yet.

From the following given information, the virtual address space should be calculated:

Page size is 16 KB
Logical address size is 47 bit
3 levels of page tables; all have the same size
Page table entry size is 8 byte

My idea is to find out how many pages can be addressed. The page count should lead then to the size of the virtual address space, right?

  Virtual address space = page size * page count

As far as I understand is the page count defined by the logical address size. The logical address is split up in 3 levels of page tables plus the offset. Due the page table entry size is 8 byte (2^6 = 64 bit), 6 bits of the logical address are used for each stage to address it. The offset will have the size of 30 bits.

Each page stage can address 64 bit plus the 30 bits offset. So does this result in the page count?

  Page count = 64 * 3 + 30 = 222

With the page size and the page count I get the virtual address space of 3552 KB.

I think this is wrong. It should be much larger. What is not correct? Any help is appreciated!

Since Logical address size is 47 bit, that means logical address space is 2^47 bytes ( assuming system is byte addressable ).

Otherwise in general if the logical address is not given then also it can be found.

Page size is 16 KB
Logical address size is 47 bit
3 levels of page tables; all have the same size
Page table entry size is 8 byte

From the information assuming the entire page is being used,

number of entries in each page = (page size) / (page table entry size ) = (2 ^ 11)

Now consider the outermost page table. It has 2 ^ 11 entries, which means the second level page table has 2 ^ 11 pages and each page has 2 ^ 11 entries.

Going by this logic it can be derived that the number of pages in process ( logical address space ) = 2 ^ 33

And given page size = 16 KB
Therefore, the logical address space size = ( 2 ^ 33) * 16 KB = 2^47 bytes


"Practical" bounding box? For the sake of simplicity, lets say I have a bunch of 2d points, each have X and Y. The points are distributed somewhat randomly but not completely, they will be biased to be closer to the world center (where ever that might be, completely random) and they are likely to have some kind of a shape. You can imagine that like a bunch of stars forming a galaxy around a black hole...

Now I need to process these points (each of them have a lot of calculations) and to optimize the processing, it would greatly help if I knew whether they were north of most of the other points or south, east or west and nort/south more or less than east/west. The exact specifity of the distribution is not important, right now I'm imagining 8 sectors (NNE, NEE, SEE, SSE, SSW, SWW, NWW, NNW like on the map).

2 simple but incomplete solutions to this are:

average the position of all the points creating the center of the collection and compare the position of each point to that. This has 2 problems. For one, 99% of the points could be in a tight circular group while one point could be waay far out somewhere. This would shift the center towards that point and in the worst case scenario, the 99% of the points would only be distributed between 2 sectors. Second problem is that the distribution doesn't have to be circular, they are just as likely to show up in the shape of a giraffe. Due to the long neck on the giraffe, the Y amplitude would be much greater than X so the processing will be incorrectly biased 50% of the time between X or Y.
Also compare the x and y of each point to a global min/max creating a bounding box, the bounding box can then be used to normalize x/y distribution but would suffer even more from the one lone point that could be way out there.

So in essence, I'm looking for a way to find the average position and the bounding box without being affected by the potential flyaway. The quality of those 2 pieces of data would be defined as follows: After cutting the BB into 8 sectors like a pie originating from the center point, if a point is assigned to the NNE sector for example then

the greatest percentage of other points must be towards its south
the second greatest towards its west
the third greatest towards its east
and least amount of points towards its north

Any ideas?

For all I can understand of your problem, you want to find a median
point serving as center such that half your points are north, half
south, half west, half east.

This is not a center of gravity, since distances do not seem to
matter. This can be done by computing separately the median for all $X$s and
for all $Y$s. There are no giraffe effect, or lone star effect, or other.

Computing this median $X_M$ and $Y_M$ for all $X$s and $Y$s can be done in linear time $O(n)$
where $n$ is the number of points, as indicated in wikipedia and StackOverflow.

Then for any point $(X,Y)$ you can know  whether it has more points
south (low ordinates) by checking whether $Y > Y_M$, and conversely
for more points north.

Similarly by comparing $X$ to $X_M$ you can tell whether ther are more
points east or west of point $(X,Y)$

You can get similar results along any direction.


Given a NP Algorithm for SAT, do we expect to have Correct and Incorrect Solutions? I am reading about Boolean Satisfiability Problem and Nondeterministic Algorithms, in the latter defination it says :

  In computational complexity theory, nondeterministic algorithms are ones that, at every possible step, can allow for multiple continuations $...$ These algorithms do not arrive at a solution for every possible computational path; however, they are guaranteed to arrive at a correct solution for some path

Assume we have a Non-deterministic algorithm for (SAT), does that mean the algorithm will show some computational paths leading to incorrect solutions (Non Satisfying Assignments) and other computational paths leading to correct solutions (Satisfying Assignment) ?

Or it is supposed to show only the correct solutions ?

Usually, when one develops an algorithm, there is a proof of correctness. From what I know, "nondeterministic" means the algorithm may or may not give you the correct answer, but it will definitely not give you an incorrect one.


calculating a shortest path in a table structure that changes in real time I have a table that looks like this

In table NPC - are AI like characters that move from one point to another. Player - a character that is controlled by the user.

In any moment the player character might move to any cell of the table. But NPC has a particular goal cell that they should reach while moving. For example, blue NPC needs to read blue cell.

Other NPC are also moving. My goal is to write an algorithm that would allow NPC to reach the cell using the shortest path. As far as I understand it is a typical shortest path problem.

My question is - is there some algorithm that particularly optimized to handle such workflows, or any algorithms will suffice - just with recalculating the path after each move?

There are many; you can find a list here. The most applicable is probably D*-lite.

However, there are not many off-the-shelf implementations for it, so the vast majority of games just recalculate the best path using A*.  There are many visual and technical tricks for recalculating as infrequently as possible without negatively affecting the game, but that's more of a question for gamedev.stackexchange.com.

For NPCs in particular, you may also want to look into pathfinding with many units at once.  Some typical search-terms for this are "swarm pathfinding", "boids", "flocking behaviors", and "collision avoidance pathfinding"


Why can useless states in TMs not be found by traversing the state graph? Can anyone explain why can't we use a Turing machine's transition diagram?
For e.g.
The definition of a USELESSTM is as follow:

  A useless state in a TM is one that is never entered on any input string.

    USELESSTM = { ⟨ M, q⟩ ∣ q is a useless state in M }

I know this problem can be proved to be undecidable by reducing ETM to it, but I want to know why can't we do a breadth first search of the Turing machine's state diagram to find states that are unreachable. Then based on whether or not we found any unreachable states, we can say that there are or there are not any useless states.

Your proposed algorithm finds some useless state, but not all of them.

Remember that you have tape content to deal with. Say, for instance, a state is reachable when there's a symbol 2 on the tape. It is reachable in the state graph, but if the TM gets only binary input (and never write a 2 itself) it will never be attained by the machine.

The proof you have tells you that there is no way to fix this.

Note that this problem is similar to detecting dead code; maybe this metaphor works better for you.


Running time analysis for algorithm that merges $k$ sorted arrays to one sorted array Given $k$ sorted arrays, the size of each array is $n$ and we want to sort them to one sorted array. assume that $k=2^p$ i.e $k\in\{ 2^1,2^2,2^3,2^4,\dots\}$
I the first step we will merge (the first and the second arrays),(the third and the fourth arrays),(the fifth and the sixth arrays),... till we get sorted arrays with length of $2n$
In the second step we will merge again each successive pair till we get sorted arrays with length of $4n$

I need to find the time complexity of this algorithem.
What I tried:
I know that merging two sorted arrays one with length $t$ and the other with length $r$ takes $\Theta (t+r)$ .
In this case the length of each array in the first iteration is $n$, so:

In the first iteration: merging each pair takes $\Theta(n+n)$  and there are $k/2$ merges so $\Longrightarrow \frac k 2 \Theta(2n)$

In the second iteration: merging each pair takes $\Theta(2n+2n)$  and there are $k/2^2$ merges so $\Longrightarrow \frac k 4 \Theta(4n)$

In the third iteration: merging each pair takes $\Theta(4n+4n)$  and there are $k/2^3$ merges so $\Longrightarrow \frac k 8 \Theta(8n)$

In the i-th iteration: merging each pair takes $\Theta(2^in)$  and there are $k/2^i$ merges so $\Longrightarrow \frac k {2^i} \Theta(2^in)$

I got stuck here, I know that binary search takes $\Theta (\log n)$ because it divides the array to two in each iteration and here it should be ralated to $\log $ somehow,

You are almost there. In the first merge pass we do $\frac{k}{2}$ merges each taking time proportional to $2n$. In the second merge pass $\frac{k}{4}$ merges each taking $4n$ (note how nicely the factors 2 and 4 cancel and each merge pass runs in $\Theta(nk)$ time). Finally, since we need only $p = \log_2k$ merge passes, we obtain the running time of $\Theta(nk \log k)$.


Finding pairs of points that have a given offset Problem: Given a set of points $S = \{x_1, x_2, x_3, ..., x_n\}$ from $\mathbb{R}^m$ and an offset vector $v \in \mathbb{R}^m$, find a set $Z \subseteq S \times S$ containing $k$ pairs of points $(x_i, x_j)$ such that the quantity $|x_i-x_j-v|$ (Euclidean norm) is smaller for any pair $(x_i,x_j) \in Z$ than that of any pair not in $Z$.

One obvious approach would be to maintain a max-heap of size $k$ and run through all pairs of points $(x_i, x_j) \in S^2$, inserting pairs into the heap if $|x_i-x_j-v|$ is smaller than the current maximum.  This algorithm has $O(mn^2 \log k)$ running time.

Is there a faster algorithm?  Is there a lower bound on the complexity of this problem?

This problem is motivated by an application where $50 \leq m \leq 1000$, $10^5 \leq n \leq 10^6$, and $5 \leq k \leq 100$, and the running time should be in seconds, not minutes or hours (which is I the naive approach above is not applicable).

One optimization I would propose is over the brute force search:

$$
\begin{align*}
d(\mathbf{x}_i, \mathbf{x}_j) &= \lVert (\mathbf{x}_i-\mathbf{x}_j) - \mathbf{v} \rVert^2\\
&= \sum\limits_{k=1}^N (x_i^k - x_j^k-v^k)^2\\
&= \sum\limits_{k=1}^N ((x_i^k-x_j^k)^2+(v^k)^2-2v^k(x_i^k-x_j^k))\\
&= \sum\limits_{k=1}^N ((x_i^k)^2+(x_j^k)^2-2x_i^kx_j^k+(v^k)^2-2v^k(x_i^k-x_j^k))\\
\end{align*}
$$
as $(v^k)^2$ is the same for all pairs, we could simply drop it - doesn't effect minimization.

\begin{align*}
d(\mathbf{x}_i, \mathbf{x}_j) &= \sum\limits_{k=1}^N ((x_i^k)^2+(x_j^k)^2-2x_i^kx_j^k-2v^kx_i^k+2v^kx_j^k)\\
&= \sum\limits_{k=1}^N (x_i^k)^2 + \sum\limits_{k=1}^N(x_j^k)^2 - 2\sum\limits_{k=1}^N x_i^kx_j^k - 2\sum\limits_{k=1}^N v^kx_i^k + 2\sum\limits_{k=1}^N v^kx_j^k\\
\end{align*}

Let's go back to matrix notation:

\begin{align*}
d(\mathbf{x}_i, \mathbf{x}_j) &= \lVert \mathbf{x}_i \rVert+\lVert \mathbf{x}_j \rVert - 2(\mathbf{x}_i \cdot \mathbf{x}_j)- 2(\mathbf{x}_i \cdot \mathbf{v}) + 2(\mathbf{x}_j \cdot \mathbf{v})\\
\end{align*}

Note that all the terms, except the middle one is free of the pairwise computations and can be computed in $O(N)$ time and stored. To compute $(\mathbf{x}_i \cdot \mathbf{x}_j)$, one can assemble matrix $X$, which contains $\mathbf{x}_i^T$ at each row and compute $D=XX^T$. Each element in this huge symmetric matrix, would then give you the dot product per pair: $D(i,j)=(\mathbf{x}_i \cdot \mathbf{x}_j)$. If memory is of concern, you can simply revert to iterative computation and not store the intermediate dot products. All in all, this would save a lot of time in pairwise comptutations, speeding up the entire search. I assume that you could couple this easy to implement approach with any other optimization to further boost the performance. In all the calculations I omitted $sqrt$ because it doesn't influence the relative comparison of distances.

If the assumption is that $\mathbf{v}=\mathbf{0}$ ($\mathbf{v}$ is null), the entire procedure boils down to a fast computation of distance matrix - this view might benefit certain applications.


set of Kolmogorov-random strings is co-re given  RC = {x : C(x) ≥ |x|} is a set of  Kolmogorov-random strings.

How can I show that  RC  is co-re

I have been reading this paper What Can be Efficiently Reduced to the
Kolmogorov-Random Strings? which just says that we know that by Kum96 we know that RC is Co-re

I was not able to find the proof of how that is proved

We want to show $\overline{R_c}\in RE$.

$\overline{R_c}=\left\{x|\exists M\hspace{1mm} s.t. \hspace{1mm} M(\epsilon)=x,|\langle M\rangle|<|x| \right\}$, i.e. $x$ is not a Kolmogorov-random string if there exists a Turing machine which outputs $x$ (say, when initialized with blank input), with description $\langle M\rangle$ shorter than $|x|$.

Given $x$, run all the Turing machines $M$ with description $|\langle M\rangle|<|x|$ with empty input $\epsilon$, simultaneously (i.e. dont execute any machine for $i+1$ steps before executing all of them for $i$ steps). This is possible since the set of all Turing machines of length $\le |x|$ is finite. If one of the machines halts and outputs $x$, accept, otherwise keep running. If all the machines halted with output different then $x$, reject.

Clearly if $x\in \overline{R_c}$ then our machine accepts, otherwise it either rejects or doesn't halt (which is the case if none of the machines outputs $x$ after some finite number of steps, and at least one of them doesn't halt).


Dovetailing in Turing Machines? I was going through TM here and encountered a term "Dovetailing".

What is exactly the dovetailing in Turing Machines?

Can anyone mind to provide a good explaination with some examples?

Dovetailing is when you simulate two or more Turing machines in parallel on a single Turing machine. Your operating system uses this technique all the time.

Why is dovetailing useful? Here is one example. Suppose that $L$ is recursively enumerable (there is a Turing machine enumerating all words in $L$) and also co-recursively enumerable (there is a Turing machine enumerating all words not in $L$). Then $L$ is recursive (there is a Turing machine that, given a word $x$, decides whether $x \in L$). For the proof, we simulate the first two machines in parallel, wait for $x$ to appear, and the answer accordingly.

How is dovetailing implemented? Typically, we alternately simulate one step of each machine.

In contrast to your operating system, in theoretical computer science we are sometimes interested in dovetailing infinitely many computations. This can be accomplished by running the first machine for one step, then the first two machines for one step, then the first three machines, and so on. Perhaps you will encounter examples illustrating why this is useful later in your academic life.


Fuzzy string matching algorithm with allowed events? I want to be able to locate a substring in a string allowing for a specified number of mismatches, insertions and deletions - and at the same time know how many mismatches, insertions and deletions were used for any match.

Using brute force backtrack I can find the matches, but I cannot guarantee that the match was produced using the fewest permutations possible.

Using dynamic programming I can find the matches and guarantee that the match was produced using the fewest permutations possible, but I cannot specify a number of allowed mismatches, insertion and deletions - only a total edit distance.

What you want is the so-called (optimal) local alignment of two strings. You can use the standard local alignment algorithm but allow insertions/deletions at the beginning and end (of the the shorter string) for free.

In the classic dynamic programming algorithm, this corresponds to initialising the first row (resp. column) with zero, removing the penalty for steps along the last row (resp. column) and finally looking for the minimum cost in the last row (resp. column) and backtrack from there. You can find alternatives in the Wikipedia article.

Restricting the number of deletions or insertions used can be implemented by adding counters to the cell values; if adding one would take one over the respective limit (stored globally), assign cost $\infty$ to the respective operation.


What is the difference between a fraction and a float? I understand any fraction to be a quotient of integers which isn't 0, but after coming across the term "float" in various programming languages (such as JavaScript) I misunderstand why it is even needed and we don't say a fraction instead.
What is the difference between a fraction and a float?

Computers usually deal with floating-point numbers rather than with fractions. The main difference is that floating-point numbers have limited accuracy, but are much faster to perform arithmetic with (and are the only type of non-integer numbers supported natively in hardware).
Floating-point numbers are stored in "scientific notation" with a fixed accuracy, which depends on the datatype. Roughly speaking, they are stored in the form $\alpha \cdot 2^\beta$, where $1 \leq \alpha < 2$, $\beta$ is an integer, and both are stored in a fixed number of bits. This limits the accuracy of $\alpha$ and the range of $\beta$: if $\alpha$ is stored using $a$ bits (as $1.x_1\ldots x_a$) then it always expresses a fraction whose denominator is $2^a$, and if $\beta$ is stored using $b$ bits then it is always in the range $-2^{b-1},\ldots,2^{b-1}-1$.
Due to the limited accuracy of floating-point numbers, arithmetic on these numbers is only approximate, leading to numerical inaccuracies. When developing algorithms, you have to keep that in mind. There is actually an entire area in computer science, numerical analysis, devoted to such issues.


Adding orders of growth I am confused as to how this is true:
O(n log n) + mO(log n) = O((m + n) log n)

I understand that O(n) + O(m) = O(n + m). I'm mostly confused as to how to deal with the coefficient preceding O(log n).

We can prove that if $f(n)$ is $O(\log{n})$ and $g(m)$ is $O(m)$ then $f(n)g(m)$ is $O(m \log{n})$. To say that $mO(\log{n}) = O(m \log{n}))$ is an abuse of notation.

See Wikipedia for similar properties of big O: http://en.wikipedia.org/wiki/Big_O_notation#Properties.


Is the way an OS schedule threads related to parallel computing? From Wikipedia:

  Operating systems schedule threads in one of two ways:

  Preemptive multitasking is generally considered the superior approach, as it allows the operating system to determine when a
  context switch should occur. The disadvantage of preemptive
  multithreading is that the system may make a context switch at an
  inappropriate time, causing lock convoy, priority inversion or other
  negative effects, which may be avoided by cooperative multithreading.

  Cooperative multithreading, on the other hand, relies on the threads themselves to relinquish control once they are at a stopping
  point. This can create problems if a thread is waiting for a resource
  to become available.

I wonder if in  parallel computing (writing and running parallelized programs in OpenMP, OpenMPI, pThread), which of Cooperative multithreading and Preemptive multitasking is/are used, or does the way OS scheduling threads have nothing to do with the multi-process or multi-thread within a parallelized program?

There is a relationship between what Wikipedia is calling "preemptive multitasking" and running multiple threads in parallel, but it's somewhat indirect.

Suppose you have two threads of computation that are independent (the memory locations they touch are non-overlapping).  Then we say that those two threads can run concurrently.  "Preemptive multitasking" is a way of giving the illusion that the threads are running concurrently, even though we only have a single physical processor.  The single processor gets interrupted (usually by some timer hardware) every once in a while (e.g., 100 times a second), and chooses which thread to run.  Since the processor is switching back and forth so quickly it is hard to tell that you aren't running simultaneously on two (slow) processors.

If you actually run the two threads on two different processors then you are really running in parallel, and there is no switching back and forth to share a single resource.

The similarity comes up because in both true parallelism and preemptive multitasking any ordering of the instructions between the two threads is possible.  Thus if there is any sharing of resources, memory, or locks you need to reason about the correctness of that sharing by proving that nothing bad can happen in any possible interleaving.

With cooperative multithreading you break the illusion of having multiple processors.  If a thread gets scheduled it runs as long as it wants to (and knows that the other thread is not running) and only gives up the processor by calling some system call (often called something like yield().)  On the one hand, you've lost the illusion of two processors, which is problematic if one of the threads forgets to yield().  The advantage is that you know when the the threads are switching back and forth, so the number of possible interleavings you need to reason about is much smaller.


Term for index-like data structures There's a class of data structures where you preprocess some other data structure in order to answer queries about it more efficiently.

That includes trivial things like sorting/hashing, less trivial things like quad trees, and includes far less trivial things such as dominator trees, interval decompositions of DAGs or distributed data structures using labelings.

I was wondering what is a common term for such data structures, and if there isn't, how to describe them best. "index-like" comes to mind, but there aren't yet any tags with the word "index" here so it does not seem to be common.

These are sometimes called (static) online data structures or online query data structures. It's actually rather hard to find a definition written down and the notion is "soft", in the sense that you can reasonably argue that almost anything would qualify especially if you allow updating. Here's one definition and mini-taxonomy:

  Online data structures support query operations in a continous manner. When the data items do not change and the data strucuture can be preprocessed before any queries are made, the data structure is known as static. When the data structure supports insertions and deletions of items, intermixed with the queries, the data structure is called dynamic.

The term online algorithm is used with a related meaning. It seems to be more widespread (as a term) than its counterpart for data structures. Since the query is the stuff/input that's online in your case, "data structure for online query" is more explicit; searching this as an entire phrase doesn't find much, but as nearby terms you'll get relevant hits e.g. from books [1] [2] [3] [4] etc. Likewise one can speak of "data structure" for "online updating".


Is it a valid graph canonical form? This question is motivated from this post. Let $G$ be a given graph, for each vertex $v \in V$, I will label $v$ with $Triangle(v)$.

$Triangle(v) : $ means number of distinct triangles contain $v$.

Question : Is it a valid canonical form? Is computing this function easy (mean polynomial time)?

A canonical form of a graph is a mapping $C$ from the set of graphs to the set of graphs such that $C(G)$ is isomorphic to $G$, and $C(G) = C(H)$ iff $G$ is isomorphic to $H$. Your function doesn't map graphs to graphs, so it's not a canonical form.

A more relevant notion is a (complete) invariant. This is a mapping $I$ from the set of graphs to some other set such that $I(G) = I(H)$ iff $G$ is isomorphic to $H$. Your mapping, as stated, is not a graph invariant. For example, consider the graph consisting of a triangle plus an isolated vertex. Consider the graph $G$ in which the triangle vertices are $1,2,3$, and the graph $H$ in which the triangle vertices are $1,2,4$. The two graphs are isomorphic, but the vector $\mathit{Triangle}(\cdot)$ is different.

We can try to fix this problem by sorting the vector. This will ensure that the vectors corresponding to $G,H$ above are the same. However, consider $H'$, which consists of a triangle connected by an edge to a vertex. The graphs $H$ and $H'$ have the same sorted triangle vector, but are not isomorphic. So your suggestion is not even a complete invariant.

Finally, you ask how easy it is to calculate your function. There is a trivial $O(n^3)$ algorithm which goes over all triples of vertices, and this can be improved to $O(n^\omega)$ using fast matrix multiplication: if $A$ is the adjacency matrix of the graph, then $(A^3/2)_{vv}$ is the number of triangles containing $v$.


Can a schedule be conflict serializable but not serializable? A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. Then,
My question is: Can a schedule be conflict serializable but not serializable?
Please explain why.

NO. As you can see in the following picture, conflict serializable schedules are a subset of serializable schedules, therefore all of them are serializable.


Can we read N numbers in O(N) time? In a different post it came up that
(using the Turing machine model of computation),
it is not even safe to say that $N$ numbers can be read in $O(N)$ time.
To me this is boggling since
it's something I take for granted in the RAM model of computation,
and I admittedly only have a cursory understanding of Turing machines.

However, the more boggling part is that
the same person claimed that in the Turing machine model
we cannot read $N$ numbers even in exponential time,
BUT that we can read the input for Knapsack and fill a table of size $N$ by $w$ in exponential time.

How can filling a two-dimensional $N$ by $w$ array take less time than
an $N$ by $1$ array?

The complexity of an algorithm is defined in the size of input. You can talk about the running time of algorithm in other parameters but the classic complexity classes like $\mathsf{P}$ and $\mathsf{NP}$ are defined in the size of input (in Turing machine model).

For an algorithm to read $N$ numbers in $O(N)$ time it needs to be able to read a number in constant time. This might seem OK at first but it is not. The time that it takes to read a number depends on the number of bits needed to store it. If you want to read a number which has $2$ bits and a number which has $2^{100}$ bits to see even on an actual computer it really depends on the number of bits.

This confusion about reading a number in constant time comes because in programming languages the data types for numbers has a maximum number of bits. For example, in many programming languages an integer variable cannot store a number more than 64 bits. So it always reads 64 bits and therefore seems constant time. But if you don't have an upper bound on the size of numbers that you might read it can take arbitrary large amount of time.

Therefore we cannot bound the running time of an algorithm reading $N$ numbers simply in $N$, it depends on how large those numbers are.

OK, so does this mean we shouldn't use the RAM model based analysis for algorithms since it hides these issues? Well, we can use them, and it is usually much easier to use them. But one should be careful about these issues. That is the reason we put emphasis on what is the size of the input for a problem when teaching data structures and algorithms.

But it is not just the input. Take for example the following program:

Input: n
x = 2
for i from 0 to n
  x = x*x
return x

At first glance this looks like to be a polynomial time algorithm. We have a loop that is executed $n$ times and inside the loop we perform a single simple multiplication. So this is polynomial time?

No, it is not. The size of input is $\lg n$ (the number of bits used to give $n$) so this the loop is executed exponentially many times. But that is not the only problem. Let's look at

Input: n
x = 2
for i from 0 to log n
  x = x*x
return x

Is this one polynomial time?

It is not. Although the loop is executed only a linear number of times in the input length the number $x$ grows and it grows it takes more time to multiply it. To see this ask we can look at the number of bits $x$ the algorithm returns. Surely an algorithm running in polynomial time cannot return exponentially many bits, right?

$$
(0,2)\\
(1,4)\\
(2,16)\\
(3,256)
.\\
.\\
.\\
(i, 2^{2^{i}})
$$

So the output is $2^{2^{\lg n}}$ which has $2^{\lg n}$ bits, exponentially more than the number of bits in input.

Now why this algorithm is not polynomial time? Well, multiplying two numbers is not constant time, and as $x$ grows the multiplication will take longer and longer time,
and the amount of time it takes to multiply two numbers grows with the number of bits they have.

In a language like C you will quickly overflow if you define $x$ to be of the standard data types for storing integers.

OK, so why people use the RAM model for algorithms analysis then? Because it is much easier to analyze algorithms in the RAM model and if one is careful the result is correct. for example, if you only use operations which are polynomial time in the size of their input (like multiplication) and during the execution you only store and use objects which are of polynomial size in the size of input then if your algorithm executes a polynomially many operations then your algorithm is actually polynomial time.

Now, returning to the dynamic programming algorithm for the Knapsack problem. The space complexity of the algorithm is roughly $w^2n$ and the number of operations executed by the algorithm is $wn$. The size of input is something between $n+\lg w$ and $n\lg w + \lg w$ since we can assume all numbers are at most $w$ (otherwise we can ignore them). The exact size of input depends on the size of the numbers given to use. So it is not going to be polynomial time in general.

However, when $w$ is exponentially small relative to $n$, i.e. $w \approx \lg n$ the size of input becomes roughly something between $2n$ and $n^2$ and the running time becomes roughly $n^2$. In this case the running time is going to be bounded by a polynomial in the size of input.

When $w \approx \lg n$, it means that the numbers are so small that you can encode them in unary in place of binary with a at most polynomial increase in the size. This is why people sometimes say that Knapsack is polynomial time when the input numbers are encoded in unary. That is essentially the same as saying $w \approx \lg n$.

Note that if we encoded the numbers in the input in unary, the size of input would be between $n+w$ and $nw+w$ and then the algorithm is polynomial time in the size of the input.

In short, dynamic programming for Knapsack is polynomial time when the number $w$ is at most a polynomial in the total length of the input. This can be phrased in different ways but that is what essentially pseudo-polynomial means.

I think these confusion happen partly because people forget to emphasis the encoding used for input and output and without fixing those encodings the computational problem is not completely defined. All objects whether numbers, graphs, strings, etc. should be encoded with the basic objects that the machine deals with, which is usually bits. And there are many different ways of encoding other objects with bits, this is particularly important in practice when dealing with graphs. Some graph problems can be solved faster using adjacency matrix, other graph problems can be solved faster using adjacency lists, etc. and until the encodings are not fixed the complexity of the graph problem is not well defined.


Finding the hidden treasure Let's assume I am trying to find a hidden treasure.

The treasure is hidden at an uknown position x. We know that the position x of the treasure is somewhere on the integer axis (in other words x is an integer). In order to find the treasure I have to take with me a detector. The detector can spot the treasure only if it is above it.

My starting position is the 0 point and I can move back and front until I cross the treasure, so that my detector can track it. I am always moving on the integer line. Which is the most efficient way to move through the axis in order to track the treasure?? I have to find an algorithm that allows me to find the treasure by covering a distance $O(|x|)$

My approach: After some consideration, I think that the most efficient way to find the treasure is the following: Starting from 0 I move front until I reach number $2$. Then I move back until I reach number $-2^2$. Then I move front until I reach number  $2^3$. Then I go back again until I reach number $-2^4$ and so on...

However, I am having difficulties on proving that there is a constant $c$ (for which I have to calculate an upper bound) so that my algorithm is going to help me find the treasure at $c |x|$ moves at most.
Any help is much appreciated! Thanks in advance!

P.S. I am new at the computer science stack exchange so I am not sure about the tags. Correct them or add more if necessary.

Your problem is known variously as the lost cow problem or the cow-path problem, and is a standard example in online algorithms. The algorithm you describe is 9-competitive, which is optimal for deterministic algorithms. For randomized algorithms the competitive ratio is roughly 4.6. See for example a writeup apparently by Rudolf Fleischer.


The relation between 2SAT and 3SAT Show that proving 2SAT is not NP-Complete would prove that 3SAT is
  not in P.

Or eqivalently -

  Show that proving 3SAT is in P would prove that 2SAT is NP-Complete.

I can see there is an easy reduction from 2SAT to 3SAT and it seems like it is the key here, but I can't quite prove the statement above. Can anyone help?

This is (sort of) a trick question. This is not about a connection between 2SAT and 3SAT, it is that if 3SAT is in P, then anything which is in NP and has at least one true instance and one false instance becomes NP-complete! Let's imagine that we are in a world where 3SAT is in P.

Now consider the simple problem 1-VAR-SAT, which is SAT where we have one variable, and at most two clauses. There are 3 1-VAR-SAT problems, $x$, $!x$, and $x \vee !x$. The last is the only unsolvable one.

Turns out, if 3SAT is in P, then 1-VAR-SAT is NP-complete! Here is the model.

Take a 3SAT instance, and solve it (that's polynomial time, 3SAT is in P). If the problem is solvable, output $x$. If it is unsolvable, output $x \vee !x$. We have turned a 3SAT instance into a 1-VAR-SAT problem, which is solvable if and only if the original is solvable, in polynomial time!


Subgraph isomorphism in planar graphs I'm a computer engineer trying to understand this Eppstein paper for matching subgraphs in planar graphs.

I'm trying to find subgraph matches to map an application graph (the subgraph) to a network-on-chip (the large graph).

I have already implemented Ullman's subgraph isomorphism algorithm and I'm successfully listing all valid mappings. However it is quite slow for larger inputs. After some research I found that the problem becomes easier for planar graphs. The Eppstein paper provides the mathematics behind planar subgraph isomorphism and claims $\mathcal{O}(n)$ runtime instead of $\mathcal{O}(x^n)$.

Because I don't have a strong mathematics background I was wondering if someone could provide me with:

  An explanation that is simpler than the attached paper of planar subgraph isomorphism. I got as far as tree decomposition but I'm finding the rest very difficult to grasp.
  The pseudo-code algorithm to find subgraphs in planar graphs according to the Eppstein paper, or if there is something with similar/better runtime.

I'm not aware of any implementations of planar subgraph isomorphism algorithms, sorry. Note that "SubGemini", which is a (1993) circuit/netlist-oriented subgraph isomorphism solver, doesn't use a planar algorithm, seemingly because they did not want to make planarity assumptions.

For subgraph isomorphism in general (i.e. not planar), the practical state of the art seems to be:

Lee, J. et al. (2012) "An In-depth Comparison of Subgraph Isomorphism
Algorithms in Graph Databases". The paper says they've released source code for their [re]implementations, but I'm having trouble find it... so you may want to email the corresponding author.
Solnon, C. (2010): "AllDifferent-based Filtering for Subgraph Isomorphism." Its implementation is found in LAD.
Cordella, L.P et al. (2004) "A (sub)graph isomorphism algorithm for matching large graphs"; this is basically describing the implementation in vflib and in NetworkX.

All of these papers have experimental results, so you can get an idea what problem sizes they can handle (which might not be a bad idea to specify in your question).

The paper by Dorn (2009) suggested by Luke Mathieson above seems your best bet if you want to implement planar subgraph isomorphism, but that paper has no experimental results, so... you'll probably be the first to experiment with it.

Alternatively, since we're talking subcircuit extraction (SCE) here, you could look at  Jiang and Bunke's Marked Subgraph Isomorphism approach for SCE. The assumption there is different than planarity:

  In this case we know a priori that the degree of some vertices is preserved under the subgraph isomorphism mapping. This information is explicitly utilized to develop a polynomial-time algorithm.

I'm a bit skeptical about the applicability of that paper to real-life SCE because the paper was published at somewhat obscure workshop that is not even circuit-focused... But they claim to have soundly beaten SubGemini. The subgraphs searched there are pretty small, a 6 node cell (presumably 6T SRAM cell) is searched and found (in many copies) in a RAM array of several thousand copies. If your application looks like this... it might be what you want.

The 2003 IEEE Potentials article about SCE even though co-authored by Frank Harary alas ignores this paper of Jiang and Bunke entirely, which not really a surprise to me given where it was published. You may want to read that brief for pointers to other approaches to SCE, including genetic algorithms, neural networks etc. A couple of SCE papers indicated in that brief as claiming good practical results are:

Chang et al.'s DECIDE "A novel subcircuit extraction algorithm by recursive identification scheme"
Zhang and Wunsch "A fuzzy attributed graph approach to subcircuit extraction problem".

Not covered in that review because it's slightly newer is FROSTY; it works by matching smaller directed (sub)graphs by doing a first pass identifying gates. In its paper, results are only compared to SubGemini though, which isn't that hard to beat.

Somewhat similar (in the sense that it relies on higher-level graphs that are in a certain sense directed) but broader in scope (in the sense that it handles both exact and approximate matching) is "Pattern Search in Hierarchical High-Level Designs" by Terem et al. from Intel + Moshe Vardi. The way they handle both exact and approximate matching is setting up both problems a constraint satisfaction problems.

Also probably worth looking at is a series papers by N. Rubanov 2006; 2002; his methods are probabilistic, but they all beat SubGemini by orders of magnitude. Rubanov worked in the EDA industry (Circuit Semantics, Magma Design Automation, Cadence).

There also three fairly recent Oracle (prbably Sun labs) patents by Douglas C. Meserve in this area: US7958468,
US7861193,
US8788990. I couldn't find any academic publication related to these patents.

The most recent comprehensive SCE work I found (insofar) is a 2009 Ph.D. thesis "Hierarchical Pattern Matching in VLSI" by M. Miloševic.

As an interesting addendum, SubGemini is based on the Conneil and Gotlieb partitioning, which has its issues, in these sense that its correctness is based on a conjecture that was eventually proved false by counterexample.


representing set of non-overlaping string in formal notation I want to represent a set of any substrings which come from an original string with constraint that all substrings should not be overlapped. To be more clear please consider the example below:

e.g.

orignal_string = "ABCDEFG"      // this can be any characters.
substring = {"ABC", "DE", "FG"} // right.
substring = {"A", "BCD"}        // right.
substring = {"BC", "FG"}        // right.
substring = {"AB", "ABC"}       // wrong, AB are overlapped.
substring = {"ABCD", "CDEFG"}   // wrong, CD are overlapped.

How to represent this in formal notation?

Idea: represent substrings by their resp. start and end index.

Let $w = w_1 \dots w_n \in \Sigma^*$ a string for some alphabet $\Sigma$. Denote (indexed) substrings of $w$ by pairs $(i,j)$ with $1 \leq i \leq j \leq n$. The actual sequence of symbols represented by $(i,j)$ would be $w_{i,j} = w_i \dots w_j \in \Sigma^*$.

Denote the set of all indexed substrings of $w$ by

$\qquad\displaystyle S_w = \{ (wi, j) \mid 1 \leq i \leq j \leq n \} \subseteq [1..n]^2$.

Note how $\{ w_{i,j}  \mid  (i,j) \in S_w\}$ is can have fewer elements due to duplicate substrings.

Non-overlapping substrings

Two indexed substrings $(i,j), (k,l) \in S_w$ with $i \leq k$ overlap if and only if $k \leq j$. Otherwise, we call them non-overlapping.

Sets of non-overlapping substrings

A set $A \subseteq S_w$ of substrings of $w$ is non-overlapping if and only if

$\qquad \forall\, u, c \in A.\ u$ and $v$ do not overlap¹.

The set of all non-overlapping sets of substrings

The set of all non-overlapping sets of substrings is

$\qquad \mathcal{N}_w = \{ A \subseteq S_w \mid A \text{ non-overlapping²} \}$.

If you so desire, input the formal definition of "do not overlap" here, i.e. $u = w_{i,j}$ and $v = w_{k,l}$ with $i \leq k$ and $k > j$. Or invent notation for the predicate "do overlap", e.g. $\operatorname{overlap}(u,v)$ or $\eta(u,v)$ or ...
Again, you can replace "non-overlapping" with the definition. I don't think that makes things more clear. The whole reason for defining shorthand is to express more complicated things easily and succinctly, after all.


Why can't we say that NP is closed under complement given that we can say it is closed under intersection I found online solutions which prove the closure of NP under intersection in the following way: given machines $M_1,M_2$ for accepts nondeterministically languages $L_1,L_2$, we construct the following machine $M$ which accepts nondeterministically $L_1 \cap L_2$:

$M$ = ”On input $w$:

Run $M_1$ on $w$. If $M_1$ rejected then reject.
Else run $M_2$ on $w$. If $M_2$ rejected then reject.
Else accept."

Is this proof correct? Can't we use similar ideas to show that NP is closed under complementation, which is supposedly an open problem?

There are several ways to describe the semantics of nondeterministic Turing machines. Perhaps the most colorful is the "guess and verify" semantics. We enhance a vanilla Turing machines with a guess tape, whose exact semantics will be explained below. Our Turing machine communicates its computation with the user by means of the state at which it halts. Some states are marked ACCEPT, the rest are marked REJECT. The semantics of the machine are as follows:

A nondeterministic machine accepts an input $x$ if there exists a string $y$ such that if we run the machine with $x$ on the input tape and $y$ on the guess tape, then it accepts (i.e., halts at a state marked ACCEPT).
Conversely, the machine rejects an input $x$ if whenever we run the machine with $x$ on the input tape and arbitrary contents on the guess tape, it always rejects (i.e., halts at a state marked REJECT), whatever we wrote on the guess tape.
A nondeterministic machine accepts a language $L$ if it accepts all $x \in L$ and rejects all $x \notin L$.
A nondeterministic machine runs in polynomial time (polytime for short) if there is a polynomial $p(n)$ such that whenever we run the machine with $x$ on the input tape and arbitrary contents on the guess tapes, it always halts within $p(|x|)$ steps.

(We are slightly cheating here: the definitions of acceptance and rejection are complementary only if the machine is promised to always halt, which is indeed the case for machines running in polynomial time.)

When describing the operation of a nondeterministic machine, we will often use the keywords "guess" and "verify". They have the following meaning:

Guess $w$: Copy a string $w$ (delimited in some fixed way) from the guess tape to the work tape.
Verify property $A$: Check whether property $A$ holds. If so, continue with the execution of the algorithm. Otherwise, halt at once at a state marked REJECT.

Another important convention is:

If the algorithm runs its course without rejecting, then the machine halts at a state marked ACCEPT.

Here is an example, a machine for SAT:

Input: A formula $\varphi$ in conjunctive normal form.
Operation: Guess an assignment $a$, and verify that it is a satisfying assignment.

A more exact description of the machine would be:

Copy an assignment $a$ from the guess tape to the work tape.

Check whether $a$ satisfies $\varphi$.

If $a$ doesn't satisfy $\varphi$, halt at a state marked REJECT.

Otherwise, halt at a state marked ACCEPT.

Let us now consider the proof that NP is closed under intersection. Let $M_1,M_2$ be polytime nondeterministic Turing machines accepting languages $L_1,L_2$ (respectively). The following polytime nondeterministic Turing machine $M$ accepts $L_1 \cap L_2$:

Verify that $M_1$ accepts the input.
Verify that $M_2$ accepts the input.

In more detail:

Decode the contents of the guess tape into two guess words.
Run $M_1$ on the inputs and the first guess word. If it halts at a state marked REJECT, enter a state marked REJECT and halt.
Run $M_2$ on the inputs and the second guess word. If it halts at a state marked REJECT, enter a state marked REJECT and halt.
Enter a state marked ACCEPT and halt.

Why does this work? Let $L$ be the language accepted by this machine. We have to show that $L = L_1 \cap L_2$.

$L_1 \cap L_2 \subseteq L$: Suppose that $x \in L_1 \cap L_2$. Since $x \in L_1$, there exists a string $y_1$ such that $M_1$ accepts when run on $x$ with $y_1$ on the guess tape. Similarly, since $x \in L_2$, there exists a string $y_2$ such that $M_2$ accepts when run on $x$ with $y_2$ on the guess tape. If we run $M$ on $x$ with $(y_1,y_2)$ on the guess tape, then it will accept, and so $x \in L$.

$L \subseteq L_1 \cap L_2$: Suppose that $x \in L$. Thus there is a string $y = (y_1,y_2)$ such that when $M$ is run on the input $x$ and $y$ on the guess tape, it accepts. The machine $M$ verifies that $M_1$ accepts when run on the input $x$ and $y_1$ on the guess tape, and that $M_2$ accepts when run on the input $x$ and $y_2$ on the guess tape. Therefore $x \in L_1$ and $x \in L_2$, and so $x \in L_1 \cap L_2$.

Now let us try to prove that NP is closed under complementation. Let $M$ be a polytime nondeterministic Turing machine accepting a language $L$. We construct the following Turing machine $M'$:

Run $M$. If $M$ accepts, reject. Otherwise, accept.

Let us see what are the semantics of this machine. The machine $M'$ accepts an input $x$ if there exist a string $y$ such that when running $M$ on $x$ with $y$ on the guess tape, it rejects. Conversely, the machine $M'$ rejects an input $x$ if $M$ accepts $x$ regardless of the contents of the guess tape.
This is not quite what we want, and to demonstrate it, let us consider the machine $M$ accepting SAT described above. Recall that the machine interprets its input as a formula $\varphi$, and the contents of the guess tape as an assignment $a$. The machine $M$ accepts iff $a$ satisfies $\varphi$. The corresponding machine $M^c$ has the following semantics:

The machine $M^c$ accepts a formula $\varphi$ if some assignment $a$ doesn't satisfy $\varphi$.

The machine $M^c$ rejects a formula $\varphi$ if all assignments $a$ satisfy $\varphi$.

In other words, the machine $M^c$ accepts the language of all formulas which are not tautologies. This is not what we were aiming for: we wanted $M^c$ to accepts the language of all unsatisfiable formulas. As an example, $M^c$ accepts the formula $x_1 \lor x_2$ even though it is satisfiable, because it's not a tautology (if $x_1$ and $x_2$ are both false then $x_1 \lor x_2$ is also false).


Why operating system needs interrupt stack, if it has process control block? I'm reading about an operating system but some concept confuses me.

What doesn't confuse me:

When an interrupt or system call or processor exception occurs, it happens when user mode tries to switch to the kernel mode, the operating system uses PCB(process control block) to save needed stuff, namely - hardware completing previous instructions, saves program counter, stack pointer, registers, changes execution state and so on. For each process has a separate process control block. This seems logical.

What confuses me:

But after several subchapters, I've read that interrupt or system call or processor exception occurs, an operating system needs to save some information - program counter, stack pointer, registers, execution state and so on. But this time saves not in PCB, it saves in "interrupt stack". It also said for each process needs the separate location of "kernel stack".

After that appears a few questions:

Is "interrupt stack" and "kernel    stack" the same thing, just
different named?
If the operating system already has PCB, why it needs to use "kernel
stack. Yes, for each process operating system has separate PCB. And
the separate location for each process in kernel stack.
Does the operating system use both kernel stack and PCB? If it does,
why not just one of these?
What difference between PCB and kernel stack, if they are used for the
same tasks

P.S Operating System Principles and Practice

The operating system cannot continue using user-accessible memory when it is handling an interrupt, that program may be buggy, malicious, or worse. It may overwrite any part of its address space at any time. That includes the stack.

The stack is often a critical part of the execution of a program, so the operating system has no choice other than to switch to another stack, which the user mode program can't corrupt.

The PCB holds information about a task. When that task is not running, the PCB may hold the context.

There may be two different kinds of context saves, one for switching from one task to another, and one just for when it is preempted by an interrupt. The latter is held on the interrupt stack, which as mentioned is separate from the user mode stack for security and correctness reasons.

Unless there is some microarchitectural reason to have a special stack for interrupts, kernel stacks and interrupt stacks are very similar, only differing in when they are used. The specifics about the stack are implementation details.


Concentration bound for sum of dependent geometric random variable? consider following persudocode:

i=0
while(i< k):
    uniformly pick u,v in V
    if(uv in E):
        remove uv form E;
        i++;

let $T$ be the number of iteration of this process,
I know how to compute the expectation, but what is well bound for
$P(|T -E[T]|)$? And is this process independent?

No. It is not true. If the uniformly picked edge $u$ have more neighbors, the probability of edges which have $u$ is more than others! Hence, it's not uniform. Moreover, the number of neighbors of each node is changing over time, and this can be more unbiased over the time. Therefore, your selections are not independent of each other.

A solution to uniformly removing an edge can be indexing all edges from $1$ to $|E|$ (using an adjacency list for example) and then pick a random number from $1$ to $|E|$ as your uniformly picking edge in your graph. And do it for the new graph after removing the randomly picked edge.

Hint: As uniform version will remove an edge each time, the probability in this version can be an upper-bound for the $\mathbb{P}(|E[T]-T|)$ in your solution.


Show that $T(n) = 2T(\lfloor n/2\rfloor) + n$ is $\Omega(n\log n)$ using substitution I have to solve this using the substitution method.

Floor functions cannot be skipped.

IH: Assume that $T(k) \geq  ck\log(k) $ for all $k \leq n$, where c is a constant.

IS: Must prove $T(k) \geq  ck\log(k) $

Proof:

\begin{align*}
T(n) &= 2T(\left \lfloor{k/2}\right \rfloor ) + k\\
     &\geq 2 c\left \lfloor{k/2}\right \rfloor\log(\left \lfloor{k/2}\right \rfloor) +k
\end{align*}

We now have two cases: $k$ is even and $k$ is odd. It is easy to prove this case when $k$ is even, however I run into trouble when $k$ is odd.

When k is odd, $\lfloor k/2\rfloor = (k-1)/2$, which gives

\begin{align*}
T(n)&\geq 2 c\tfrac{k-1}2\log(\tfrac{k-1}2) +k\\
&=  c(k-1)\big(\log(k-1)-1\big) +k \qquad\qquad\text{(Since $\log2 = 1$)}\\
&=  c\big(k\log (k-1) - k -\log(k-1) + 1\big) +k\\
&=  ck\log (k-1) - ck -c\log(k-1) + c +k\\
&=  ck\log k  + ck\log\big(1-\tfrac{1}k\big) - ck -c\log(k-1) + c +k\,,
\end{align*}
where the last equality is because $\log(a-b) = \log\big(a\big(1-\tfrac{b}a\big)\big)$.

And here is where I am stuck. I have gotten the $ck\log k$, but cannot find the $c$ that will let me finish the problem.

Any help would be appreciated.

One way to go around the difficulties is as follows.

First, you prove that $T(n) = \Omega(n \log n)$ when $n = 2^k$.

Second, you prove that $T(n)$ is monotone (given monotone base cases).

Third, you finish the proof as follows. Let $m \leq n < 2m$, where $m = 2^k$. Then
$$
 T(n) \geq T(m) = \Omega(m \log m) = \Omega(n \log n).
$$
Details left to you.


Maximize 5-independent gifts on a path Question: Assume there are $n$ distinct gifts on the real line. Their
positions are $\{x_1, ..., x_n\}$ and each of them has an individual
value $p_i$.
Now you can choose a subset of them such that any two gifts in your
choice are at a distance more than 5. What’s the maximum total value you
can get? Design an algorithm to solve this problem, analyze the running
time and prove the correctness.
You can assume the gifts are given in order of their locations, i.e.,
$x_1 < x_2 < ... < x_n$.
I have tried memoization and breaking down the problem into smaller
steps but I am not sure what this specific sub case would look
like.

Here is some pseudocode that illustrates the recursive idea.

If you choose to take this element, then you have to skip ahead 6 steps.
Otherwise you skip this element and go to the next.

def solve(array, index):
    if index >= len(array):
        return 0
    this_one       = array[index]             # the value x_i
    opt_five_steps = solve(array, index + 6)  # the opt of array[i+6:]
    opt_successor  = solve(array, index + 1)  # the opt of array[i+1:]
    return max(this_one + opt_five_steps,
               opt_successor)

Clearly, this can be turned into a DP algorithm, or memoized as is.