Help with graph search problem For the next problem I can not think of how to find a solution with graph searches (I thought it was backtracking but my college professor told me that I should use graph searches, which I do not know much about, to solve it).

As input we obtain a matrix (3x4) of connections ("|" or "-") which we must decode in the least amount of movements, to avoid that the bomb explodes. As an output inform one of the possible solutions.

The decoding consists in that the matrix must contain only characters "-". To achieve this they tell us that if we move an element of the matrix, both the values of the column and row of the matrix change. For example if I move the element (0,0) of the matrix in this case the "-" change to "|" and vice versa in the column 0 and row 0. In the image (where (1) represents the input matrix and (2) the decoded matrix) a solution to inform would be:

move (0,3) and  then (2,1)

How to design an algorithm that solves this problem without using backtracking directly?

"Graph search" is a very general term that includes breadth-first-search and depth-first-search. Let's say you wanna do BFS on this problem.

For this problem, think of a matrix, or a state, as a node in the graph. The pseudocode might look like this:

Push the "input node" into a queue.
While desired output node is not found:

Pop an element from the queue
Go through all the "moves" that could be done on that node. For a 3x4 matrix there would be 12 possible moves.
Push the results of each move into the queue.

Hope this helps!


Are today's massive parallel processing units able to run cellular automata efficiently? I wonder whether the massively parallel computation units provided in graphic cards nowadays (one that is programmable in OpenCL, for example) are good enough to simulate 1D cellular automata (or maybe 2D cellular automata?) efficiently.

If we choose whatever finite grid would fit inside the memory of the chip, can we expect one transition of a cellular automaton defined on this grid to be computed in (quasi)constant time?

I assume 2D cellular automata would require more bandwidth for communication between the different parts of the chips than 1D automata.

I'd also be interested by the same question in the case of FPGA programming or custom chips.

Excellent question. I believe the answer is yes.

Evolving a cellular automaton is essentially equivalent to performing a stencil computation. On some 1D, 2D, or 3D grid, successive values of points (or cells) are computed based on the last value of point's neighborhood. In a simple 1D CA, this neighborhood might be the cell and the two cells to the left and right. There are lots of examples of stencil computations being performed on GPUs; ORNL's SHOC benchmark suite for OpenCL/CUDA contains a 2D stencil example, for instance.

The basic idea is to have each thread get a local copy of the neighborhood for several points, then compute the next values for points determined by that neighborhood. By appropriately using the memory hierarchy in e.g. CUDA (registers, shared, constant, texture, and global memories) and the SIMT processing model (e.g., by appropriately computing the transition function without introducing excessive warp divergence), good performance can be achieved.

This answer would be a lot better if I were to give an example, but I am too busy to write any code right now... But in theory, I think it should be feasible to efficiently simulate CAs on GPUs by modeling them after stencil computations. Lots of considerations go into writing a good stencil computation for GPUs, though.


Hash tables versus binary trees When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL library implements dictionaries (they call them maps) using (balanced) binary search trees, and the .NET framework uses hash tables under the hood.

  What are the advantages and disadvantages of these data structures? Is there some other option that is reasonable in certain situations?

Note that I'm not particularly interested in cases where the keys have a strong underlying structure, say, they are all integers between 1 and n or something.

A whole treatise could be written on this topic; I'm just going to cover some salient points, and I'll keep the discussion of other data structures to a minimum (there are many variants indeed). Throughout this answer, $n$ is the number of keys in the dictionary.

The short answer is that hash tables are faster in most cases, but can be very bad at their worst. Search trees have many advantages, including tame worst-case behavior, but are somewhat slower in typical cases.

Balanced binary search trees have a fairly uniform complexity: each element takes one node in the tree (typically 4 words of memory), and the basic operations (lookup, insertion, deletion) take $O(\mathrm{lg}(n))$ time (guaranteed asymptotic upper bound). More precisely, an access in the tree takes about $\mathrm{log}_2(n)$ comparisons.

Hash tables are a bit more variable. They require an array of around $2n$ pointers. Access to one element depends on the quality of the hash function. The purpose of a hash function is to disperse the elements. A hash table “works” if all the elements you want to store in it have different hashes. If this is the case, then the basic operations (lookup, insertion, deletion) take $O(1)$ time, with a fairly small constant (one hash calculation plus one pointer lookup). This makes hash tables very fast in many typical cases.

A general problem with hash tables is that the $O(1)$ complexity is not guaranteed.

For addition, there's a point where the table becomes full; when that happens (or, better, a little before that happens), the table needs to be enlarged, which requires moving all of its elements, for an $O(n)$ cost. This can introduce “jerky” behavior when a lot of elements are added.
It's possible for the input to collide over a few hash values. This rarely happens naturally, but it can be a security problem if the inputs are chosen by an attacker: it's a way to considerably slow down some servers. This issue has led some programming language implementations (such as Perl and Python) to switch from a plain old hash table to a hash function involving a random number chosen when the hash table is built, together with a hash function that spreads this random datum well (which increases the multiplicative constant in the $O(1)$), or to a binary search tree. While you can avoid collisions by using a cryptographic hash, this is not done in practice because cryptographic hashes are comparatively very slow to compute.

When you throw data locality into the mix, hash tables do poorly. They work precisely because they store related elements far apart, which means that if the application looks up elements sharing a prefix in sequence, it will not benefit from cache effects. This is not relevant if the application makes essentially random lookups.

Another factor in favor of search trees is that they're an immutable data structure: if you need to take a copy of a tree and change a few elements in it, you can share most of the data structure. If you take a copy of a hash table, you need to copy the whole array of pointers. Also, if you're working in a purely functional languages, hash tables are often not an option.

When you go beyond strings, hash tables and binary search trees make different requirements on the data type of the key: hash tables require a hash function (a function from the keys to the integers such that $k_1 \equiv k_2 \implies h(k_1) = h(k_2)$, while binary search trees require a total order. Hashes can sometimes be cached, if there is enough room in the data structure where the key is stored; caching the result of comparisons (a binary operation) is often impractical. On the other hand, comparisons can benefit from shortcutting: if keys often differ within the first few bytes, a negative comparison can be very fast.

In particular, if you're going to need the order on the keys, for example if you want to be able to list the keys in alphabetical order, then hash tables are no help (you'll need to sort them), whereas you can straightforwardly traverse a search tree in order.

You can combine binary search trees and hash tables in the form of hash trees. A hash tree stores keys in a search tree according to their hash. This is useful, for example, in a purely functional programming language where you want to work on data that does not have an easy-to-compute order relation.

When the keys are strings (or integers), a trie can be another option. A trie is a tree, but indexed differently from a search tree: you write the key in binary, and go left for a 0 and right for a 1. The cost of an access is thus proportional to the length of the key. Tries can be compressed to remove intermediate nodes; this is known as a patricia trie or radix tree. Radix trees can outperform balanced trees, particularly when many keys share a common prefix.


Proving that any CF language over a 1 letter alphabet is regular I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far:

Let $L$ be a context free language. So, $L$ satisfies the pumping lemma. Let $p$ be $L$'s pumping constant. Let $L = L_1 \cup L_2$ where $L_1$ consists of $w$ where $|w| < p$ and and $L_2$ consists of $w$ where $|w| \ge p$. We have a single letter alphabet and since $L_1$ has a restriction on the length of its words, $L_1$ is a finite language. Finite languages are regular so $L_1$ is regular. If I can show that $L_2$ is regular, I can use the fact that the union of regular languages is regular. But I am struggling on showing that $L_2$ is regular. I know that since $w \in L_2$ has to satisfy $|w| \ge p$, by the pumping lemma, $w$ can be written as $w = uvxyz$ where $|vxy| \le p$, $|vy| > 0$ and $\forall t \ge 0$, $uv^txy^tz \in L$. Since we have a single letter alphabet (say the letter is $a$), $uv^txy^tz = uxz(vy)^t = uxz(a^{|vy|})^t \in L$. Now what?

Let $L$ be a unary context-free language. According to the pumping lemma, there is a constant $p$ such that if $a^n \in L$ then either $n < p$ or there exists $q \in \{1,\ldots,p\}$ such that $a^{n+tq} \in L$ for all $t \geq 0$ (actually, the pumping lemma gives $t \geq -1$). Let $L_0$ be the set of words in $L$ of length smaller than $p$, and for $q \in \{1,\ldots,p\}$, let $L_{q_0}$ be the set of words in $L$ of length at least $p$ for which the pumping lemma gives $q = q_0$. I claim that
$$
L = L_0 \cup \bigcup_{q=1}^p \{ a^{n+tq} : a^n \in L_q, t \geq 0\}.
$$

Proof of $ \subseteq $: If $x \in L$ then either $|x| < p$, in which case $x \in L_0$, or $|x| \geq p$, in which case $x \in L_q$ for some $q$, and so $x$ belongs to the $q$'th summand on the right (choosing $t \geq 0$).

Proof of $ \supseteq $: This follows directly by definition of $L_0$ and $L_q$.

Since $L_0$ is finite, it is regular. Hence it suffices to prove that for each $q \in \{1,\ldots,p\}$, the following language is regular:
$$
R_q := \{ a^{n+tq} : a^n \in L_q, t \geq 0\}.
$$
Let us write, for $0 \leq r \leq q-1$,
$$
R_{q,r} := \{ a^{n+tq} : a^n \in L_q, t \geq 0, n \equiv r \pmod q \},
$$
so that $R_q = \bigcup_{r=0}^{q-1} R_{q,r}$. Thus it suffices to prove that each $R_{q,r}$ is regular.

If no $a^n \in L_q$ satisfies $n \equiv r \pmod q$, then $R_{q,r} = \emptyset$ is clearly regular. Otherwise, let $n_{q,r}$ be the minimal $n \equiv r \pmod q$ such that $a^n \in L_q$. I claim that
$$
R_{q,r} = \{a^{n_{q,r} + tq} : t \geq 0\} = a^{n_{q,r}} (a^q)^*,
$$
and so $R_{q,r}$ is regular.

Indeed, clearly $R_{q,r}$ contains the right-hand side. On the other hand, suppose that $a^m \in R_{q,r}$. Then $m = n+tq$ for some $n \equiv r \pmod q$ and $t \geq 0$ such that $a^n \in L$. But then $m = n_{q,r} + (t+(n-n_{q,r})/q)q$ (our choice of $n_{q,r}$ guarantees that $n \geq n_{q,r}$ and that $n-n_{q,r}$ is divisible by $q$), and so $a^m$ is an element of the right-hand side.


Longest subsequence such that A[i].x < A[i+1].y I have an issue for which I am looking for an algorithm (if it exists)

What I have:
An array of items which have certain properties, e.g. item $A$ has properties $x$ and $y$.

Example: $[ A(x,y), B(x,y), C(x,y), D(x,y), E(x,y) ]$

What I want:
A result list consisting of elements of the original list, such as $[ A(x,y), C(x,y), E(x,y) ]$, for which the following properties are true:

No reordering of elements, they are in the same order as the original list
The result has the maximum number of elements, i.e. the longest 'path' possible
For each pair of consecutive items $(A(x,y), B(x,y))$ in the result, $A.x \lt B.y$. In other words, an item's $x$ must be less than the next item's $y$.

Complexity: The list in the case I have is about 35 items long, so an algorithm which is $O(n!)$ might not work.

Does such an algorithm exist?

It's easier to change notation.  Suppose the array is $A$, with the $i$-th element denoted $A[i]$ for $i=1,2,\dots,n$, and that element $i$ has attributes $A[i].x$ and $A[i].y$.  Associate a directed graph $G$ with the array as follows.  The vertices of $G$ are the indices $1\dots n$ of the array.  Vertex $i$ is connected to vertex $j\ $ if both conditions $i<j$ and $A[i].x < A[j].y\ $ hold.

You are then asking for a longest directed path in $G$.

Note that $G$ is actually acyclic, since the arcs form a subset of the usual order on the set $\{1,\dots,n\}$.
Any standard linear algorithm can then be used to compute the longest path, such as a topological sort.


Towers of Hanoi but with arbitrary initial and final configuration Recently, I came across this problem, a variation of towers of hanoi.

Problem statement:

  Consider the folowing variation of the well know problem Towers of
  Hanoi:

  We are given $n$ towers and m disks of sizes $1,2,3,\dots,m$ stacked on some
  towers. Your objective is to transfer all the disks to the $k^{\text{th}}$ tower
  in as few moves as you can manage, but taking into account the
  following rules:

  moving only one disk at a time,
  never moving a larger disk one onto a
  smaller one,
  moving only between towers at distance at most $d$.

  (Limits in the original problem:
  $3 \le n \le 1000$ and $m \le 100$. Number of test cases $\le 1000$.
  You can assume that all the problems can be solved in not more than
  $20000$ moves.)

It's an interesting one. The classic towers of hanoi problem has one source, destination and temporary tower that is used to move the disks from source to destination. The problem pitched on that site basically has an initial and final configuration.

How does one approach this problem?

The most succesful approach to deal with the original version of the Towers of Hanoi is using Pattern Databases (PDBs). The current state of the art is described in "Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem"

Pattern Databases are an automated means for deriving admissible heuristics which are necessary in order to find optimal solutions (as your problem requires). In the particular case of the Towers of Hanoi, some discs are preserved while others are just ignored. This results in a smaller state space which can then be fully traversed with a backward breadt-first search algorithm. It is traversed with a breadth-first search to derive optimal lengths in this abstract state and it is traversed from the goal node $t$ (i.e., backwards), to ensure that the optimal lengths computed are relative to the goal. Since the abstract space is smaller, these distances are admissible estimates in the original state space.

This said, I would highly recommend using PDBs again for solving this particular problem since "moving only between towers at distance at most $d$" is trivial since pegs are not abstracted, only the discs.

I do not see, indeed, any reason to change the typical approach just in view of this particular constraint.

Hope this helps,


Bin packing problem or not? Suppose I have $N$ bins and $M$ items as depicted in the figure below (3 bins and 3 items):

Suppose that every bin has unit capacity and the weights of the items depend on the bins used. I want to maximize the number of items in the bins subject to:

One bin contains at most one item.
If item $i$ is on bin $j$ then $g_{ij}\geq1$ must hold now if all other bins are empty.
If item $i$ is on bin $j$ (so $g_{ij}\geq1$ must hold now) and item $i^\prime$ is on bin $j^\prime$, then $g_{ij}\geq g_{ij^\prime}$ and $g_{i^\prime j^\prime}\geq g_{i^\prime j}$ must both hold now.
If item $i$ is on bin $j$ (so $g_{ij}\geq1$ must hold now) and item $i^\prime$ is on bin $j^\prime$ (so $g_{ij}\geq g_{ij^\prime}$ and $g_{i^\prime j^\prime}\geq g_{i^\prime j}$ must both hold now) and item $i^{\prime\prime}$ is on bin $j^{\prime\prime}$, then $g_{ij}\geq g_{ij^\prime}+g_{ij^{\prime\prime}}$ and $g_{i^\prime j^\prime}\geq g_{i^\prime j}+g_{i^\prime j^{\prime\prime}}$ and $g_{i^{\prime\prime} j^{\prime\prime}}\geq g_{i^{\prime\prime} j}+g_{i^{\prime\prime} j^{\prime}}$ must all hold now.
And so on and so forth.
In general I will have the following constraint: $g_{ij}x_{ij}\geq\sum\limits_{i^\prime=1,\;i^\prime \neq i}^{M}\sum\limits_{j^\prime=1,\;j^\prime \neq j}^{N}g_{ij^\prime}x_{i^\prime j^\prime}$, where $x_{ij}$ equals $1$ if item $i$ is in bin $j$ and equals $0$ otherwise.

Finally, I have the following problem:

Maximize $\sum\limits_{i=1}^{M}\sum\limits_{j=1}^{N}x_{ij}$

subject to

$\frac{g_{ij}x_{ij}}{\sum\limits_{i^\prime=1,\;i^\prime \neq i}^{M}\sum\limits_{j^\prime=1,\;j^\prime \neq j}^{N}g_{ij^\prime}x_{i^\prime j^\prime}}\geq x_{ij},\; \forall i, j,$ (C1)
$\sum\limits_{j=1}^{N}x_{ij}\leq1,\; \forall i,$ (C2)
$\sum\limits_{i=1}^{M}x_{ij}\leq1,\; \forall j,$ (C3)

and $x_{ij}\in\{0, 1\},\; \forall i, j,$ (C4)

The input of the problem is $M$, $N$, and $g_{ij},\;\forall i,j$. The right hand side of constraint (C1) is to say that when item $i$ is not in bin $j$ (i.e., $x_{ij}=0$) then (C1) is not violated. (C2) and (C3) say that one item goes to one bin and one bin contains one item, respectively. Finally, (C4) is the variable of the problem which is a binary variable.

My question is: Can I say that this problem is a bin packing problem and it is therefore NP-hard? If not, Can you suggest a reduction idea from an NP-complete problem?

Thank you for your help.

You can't simply say: "This is a bin packing problem and therefore NP-hard."
Consider the problem of $N$ unit bins and $M$ unit items with the target of maximizing the usage of the bins. Clearly this is also a bin packing problem, but it is not NP-hard.

However, you can reduce to the decision variant of your problem from partition:

  Given a set of items with sizes $a_1, \dotsc, a_k$, can it be partitioned into two subsets of equal size.

Given items $a_1, \dotsc, a_k$, we construct an instance of your problem as follows:

Let $A_i = \sum_{j=1}^i a_j$ amd $A=A_k$.
We introduce $2A+2$ items and $2A+2$ bins.
$g_{i,j} = \begin{cases}
A-a_l & A_{l-1}<i=j\leq A_l\\
A-a_l & A+A_{l-1}<i=j\leq A+A_l\\
0 & A_{l-1}<i,j\leq A_l,~ i\neq j\\
0 & A+A_{l-1}<i,j\leq A+A_l,~ i\neq j\\
2 & A_{l-1}<i\leq A_l,~ A+A_{l-1}<j\leq A+A_l\\
2 & A+A_{l-1}<i\leq A+A_l,~ A_{l-1}<j\leq A_l\\
0 & j>2A,~ i\neq j\\
\frac A2 & i=j>2A\\
0 & i=2A+1,~ j\leq A\\
0 & i=2A+2,~ A<j\leq 2A\\
1 & \text{otherwise}
\end{cases}$
We ask for an assignment with $\sum_{i=1}^{A}\sum_{j=1}^{A} x_{i,j} \geq A+2$.

The construction works as follows:

Any solution will satisfy $x_{i,j}=1 \Rightarrow i=j$.
Items/bins $i$ with $A_{l-1} < i \leq A_l$ resp. $A+A_{l-1} < i \leq A+A_l$ correspond to $a_l$. In a solution, exactly one of the groups will be taken, corresponding to $a_l$ being in the first resp. second set of the partition.
The threshold can only be reached, if the last two items are placed, ensuring that the partition is into two sets of size $\frac A2$.


Implementing Dynamic Programming Solutions I know there alot of questions on Dynamic Programming and I feel I have a handle on the theory, use the answers from sub problems to answer the current problem, without the redundancy of recursion.  My confusion comes from implementation.  Here is a specific question.  Every question I look at builds its grid differently, for example, 0,1 knapsack you go back down the row and up one.  For coin changing its just back down the row.  For Fibonacci and stair steps its the sum of the last two.      If I am tasked with a Dynamic Programming problem is there any kind of base approach I can take to building out my grid?

One easy way to do dynamic programming is memoization -- just do the regular recursion, but store any results computed and reuse them if the same (sub)problem shows up. Recursion is at the very hearth of dynamic programming, what is usually programmed is a careful unrolling of the recursion.


LFSR sequence computation I need to calculate the output of the sequence generated by this shift register but I cannot find anywhere how to do it. Everywhere the results are just given but there is no explanation how to do compute them. I know the the sequence will repeat every 2^3-1=7 times. Could anyone explain me how to do it. Thank you.

The answer seems to be simple:

First, we XOR the two least significant bits (LSB) to get the most significant bit. The two LSB are obtained by right-shifting. So, calculating in this way, we get the sequence 110, 111, 011, 001, 100, 010, 101.


Understanding addition overflows when performing full, signed multiplication of two 64-bit numbers I am close to solving question 3.59 from Computer Systems: A Programmer's Perspective 3rd Editionby Randal E. Bryant and David R. O'Hallaron, however I am having difficulties with understanding the result.

Question 3.59 asks you to examine a sample of C and x86_64 assembly code that performs a full, signed multiplication of two 64-bit numbers, producing a 128-bit result, and explain how the code is working. The C and assembly is below.

1  #include <stdint.h>
2  typedef __int128 int128_t;
3
4  void store_prod(int128_t *dest, int64_t x, int64_t y) {
5      *dest = x * (int128_t) y;
6  }

# x in %rsi, y in %rdx
1  store_prod:
2    movq    %rdx, %rax
3    cqto
4    movq    %rsi, %rcx
5    sarq    $63, %rcx
6    imulq   %rax, %rcx
7    imulq   %rsi, %rdx
8    addq    %rdx, %rcx
9    mulq    %rsi
10   addq    %rcx, %rdx
11   movq    %rax, (%rdi)
12   movq    %rdx, 8(%rdi)
13   ret

The book suggests thinking about the problem by recognizing that when $x$ and $y$ are extended to 128-bits, they can be written as $x = 2^{64}x_{h} + x_{l}$ and $y = 2^{64}y_{h} + y_{l}$, where $x_{h}$, $x_{l}$, $y_{h}$, and $y_{l}$ are 64-bit values.

I see that mathematically

$$
\begin{align*}
xy &= (2^{64}x_{h} + x_{l})(2^{64}y_{h} + y_{l}) \\
   &= 2^{128}x_{h}y_{h} + 2^{64}(x_{h}y_{l} + x_{l}y_{h}) + x_{l}y_{l}.
\end{align*}
$$

Since $x_{h}$ and $y_{h}$ are the sign extended parts of $x$ and $y$, we do not care about the $2^{128}x_{h}y_{h}$ term in the final value, so we really only care about $2^{64}(x_{h}y_{l} + x_{l}y_{h}) + x_{l}y_{l}$, which is how the value is calculated in the assembly code.

My misunderstanding comes about in lines 8 and 10 in the assembly code. Line 8 calculates $x_{h}y_{l} + x_{l}y_{h}$ and line 10 calculates $2^{64}(x_{h}y_{l} + x_{l}y_{h}) + x_{l}y_{l}$.

My question is why do we not have to worry about overflows when executing the addition instructions on these lines. Even if an overflow occurs, why are the bits of the result correct? Is it because any value resulting from an overflow would en dup going beyond 128-bits, which we then don't care about?

Your explanations are a bit incorrect. What line 10 does is to add the high 64-bit word of $x_l y_l$ (%rdx after line 9) to $2^{64} (x_h y_l + x_l y_h)$. The low 64-bit word has been computed in line 9 and is in %rax.

Now, all the overflows that have been ignored will affect bit 128 only, i.e. the obtained result can differ from the correct result only by a multiple of $2^{128}$. But since one is interested in the result modulo $2^{128}$, such overflows do not matter.


Iterative Byzantine consensus in directed graphs with unbounded malicious nodes I've found many articles describing iterative procedures to reach Byzantine agreement on a graph (for instance http://www.crhc.illinois.edu/wireless/papers/icdcn14-vaidya.pdf or http://arxiv.org/pdf/1203.1888v1.pdf) but they all assume that a fraction of the peers aren't faulty or malicious.

Are there procedures to reach consensus among honest peers when there is an unbounded amount of faulty peers, but such faulty peers are only very sparsely connected to the cluster of honest peers?

A typical example would be a web of trust where it is trivial for an attacker to create millions of peers, but hard to receive trust from the main cluster.

I realize that, as such, the problem isn't very well defined. The honest cluster may have sub clusters, and it's unclear why they should be able to influence each other's consensus, while clusters of dishonest nodes may not. Typically, a solution would exhibit a threshold effect depending on connectedness.

As you are probably well aware, it is provably impossible to reach consensus if a majority of the peers are faulty, malicious, or dishonest, if we assume they are all fully connected (as is typically the assumption for distributed systems).

If you are imagining that for some reason honest peers are better-connected than faulty/malicious peers, well, there are two problems with that model:

The first problem is that the model is not realistic.  In practice, faculty/malicious peers are typically just as well-connected as honest ones.  In the case of unintended software faults, there is no reason to expect that connectivity will be at all correlated to software failure rates.  In the case of malice (e.g., peers that are compromised or dishonest), well, attackers can typically arrange to be as well-connected as the honest peers, and can often arrange to be even better-connected.
The second reason is that if we really did have such a separation, the problem would become trivial.  For instance, we could just pick a threshold and ignore all peers whose connectivity is below that threshold.  If this ensures that a 2/3 majority of the remaining peers are honest and non-faulty, then this reduces to the standard Byzantine consensus problem.

But ultimately I think it is the first problem that is the big one.  It would only make sense to even think about such a setting if we had some sample application where there is evidence that your assumption is valid.  Lacking that, there is not a clear reason to study such a model.

The web of trust doesn't actually seem to meet your assumptions, unless you are very careful about how you define them.  An attacker can create one dishonest node $x$ (that is connected to a few honest peers), and then create lots of additional dishonest nodes $y_1,y_2,\dots,y_n$ and have $x$ endorse all of the $y_i$'s.  The $y_i$'s can also endorse lots of honest nodes.  Now, at least by some measures, the $y_i$'s are well-connected.  There is also the risk of Sybil attacks, where the attacker creates many fake identities ("Sybils") and gets them connected to many honest nodes.

In the cryptographic world, you could look at the research directions under the catch-phrases "reputation systems" and "trust metrics".  Some of them are designed to estimate the amount of trust one can have in a node, based upon its connectivity and the endorsements that nodes make in each other.  However, academic research hasn't had a ton of impact in practice, because it is hard to make them work well in practice, and because Sybil attacks are hard to stop.


$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ even} \} $ is context free language Let $\mathcal{L}$ be context free language over alphabet $\Sigma$. Define $\mathcal{G}$ as
$$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ even} \} $$

I have seen a similar question (asked 5 years ago) but I am not sure how it can work.

Proposition

$\mathcal{L}$ is CFL so it has own push-down automata. So let copy states of $\mathcal{L}$ and if it has a state called $S$ and it gets to state $T$ upon letter $x$ then $\mathcal{G}$ will have states $S_1, S_2, T_1, T_2$ and letter $x$ turns $S_1$ to $T_2$ and $S_2$ to $T_1$.

My question is why it is correct apporach? $\mathcal{G}$ automata won't read any of $v_1, v_3, v_5,... v_{k-1}$ so how it can ensure that this word belongs to $\mathcal{L}$?

This answer assumes that $v_i \in \Sigma$ are individual symbols.

You can prove this using closure properties. The advantage is that any class of languages closed under the requisite closure properties will be closed under this operation. Specifically, we will need closure under homomorphism, reverse homomorphism, and intersection with regular language, which are exactly the so-called "full trio".

Let $\Sigma' = \{ \sigma' : \sigma \in \Sigma \}$ be a copy of $\Sigma$. Define homomorphisms $r,d\colon \Sigma \cup \Sigma' \to \Sigma$ by $r(\sigma) = r(\sigma') = \sigma$ and $d(\sigma) = \sigma$, $d(\sigma') = \epsilon$. Then
$$
\mathcal{G} = d(r^{-1}(\mathcal{L}) \cap (\Sigma' \Sigma)^*).
$$

Some families of languages, for example context-sensitive languages, are closed under the so-called "trio", in which homomorphism is replaced with $\epsilon$-free homomorphism (meaning $h(\sigma) \neq \epsilon$ for all letters $\sigma$). We can accommodate these as well with a slightly more complicated argument.

Let $e\colon \Sigma' \times \Sigma \to \Sigma \cup \Sigma$ be given by $e(\sigma',\sigma) = \sigma' \sigma$, and let $p\colon \Sigma' \times \Sigma \to \Sigma$ be given by $p(\sigma',\sigma) = \sigma$. Then
$$
\mathcal{G} = p(e^{-1}(r^{-1}(\mathcal{L}) \cap (\Sigma'\Sigma)^*)).
$$


Is building this tournament fixture an NP-Hard / NP-Complete problem? I'm curious to know if this problem is NP-Hard / NP-Complete, which I believe would mean I'm unlikely to find a polynomial-time algorithm to solve it.

I have written a program which randomly generates a tournament fixture, and I call it many times to try to pack the matches into the smallest number of rounds.

When it comes to complexity theory I am still a novice, so laymen's terms would be appreciated.

Inputs:

a set of countries, each of which may enter one or more entrants to the tournament (e.g. Australia might enter two entrants, UK might enter three entrants, and South Africa might enter one entrant)

Constraints:

each match consists of two entrants playing against each other
during a round, an entrant can only play in a single match
no entrant wants to compete in a match against another entrant from the same country
no entrant wants to compete against another entrant more than once in the tournament
each entrant must play the exact same number of matches overall
the number of matches each entrant must play is determined by MIN(for each entrant, total number of possible matches that satisfy the other constraints)

For example, say we have the following entrants:

AU #1 and #2
UK #1, #2 and #3
SA #1

The possible matches in this (artificially small) case are:

AU1 v. UK1   AU1 v. UK2   AU1 v. UK3   AU1 v. SA
AU2 v. UK1   AU2 v. UK2   AU2 v. UK3   AU2 v. SA
UK1 v. SA    UK2 v. SA    UK3 v. SA

Since we want each entrant to play the exact same number of games, the maximum number of games per entrant is three (this can be derived from the total number of entrants (6) less the number of entrants from the largest country (3)).

Since there are six entrants in total, and there are two entrants to each match, the maximum number of courts we can utilise in a round is 3.

A sample fixture is:

          Court 1      Court 2      Court 3
Round 1   AU1 v. UK1   AU2 v. UK2   UK3 v. SA
Round 2   AU1 v. UK2   AU2 v. UK3   UK1 v. SA
Round 3   AU1 v. UK3   AU2 v. UK1   UK2 v. SA

This is a nice example because it's easy to find a solution where each entrant has played exactly 3 games each, and they all pack perfectly into 3 rounds across 3 courts. Two of the possible 11 matches have not been played, but we don't care. We sum the results from each entrant's 3 games to determine an overall ranking, which is then used to generate the finals matches.

I have other scenarios where there are more entrants and I have been unable to pack them so neatly, but by running my program many times it almost always finds a near-optimal packing where the number of rounds and unused courts is minimised.

Output

The first problem is if there is a polynomial-time algorithm to generate an optimal fixture.

The optimal fixture is defined by:

minimum number of unused courts (which implies minimising the number of rounds)

The second problem is, given a fixture "A", how to determine if it is an optimal solution, i.e. is it possible to prove that there can exist no better packings for a given set of entrants. If "A" involves no unused courts in any round, then the answer for that one is clearly "Yes" - but if there are any unused courts in any round, the answer is, I think, difficult to derive.

At first glance, even a simple solution would appear to merely be ${\cal O}(n^2)$, which is obviously polynomial time. To make the rest of my answer more readable, I'm going to define the following variables:

numEntrants = the total number of entrants
largestNumEntrants = the number of entrants from the country with the most entrants
numRounds = numEntrants - largestNumEntrants

For the purposes of the rest of my answer, I will assume that numEntrants is even. If it is not even, then some odd number of entrants must have a bye each round and that greatly complicates matters when trying to make sure every entrant plays the exact same number of matches.

As you correctly observed in your question statement, the largest possible number of rounds is the total number of entrants minus the number of entrants from the country with the most. We can quickly observe that numRounds is in ${\cal O}$(numEntrants). Furthermore, the number of possible matches within a round is also in $\cal O$(numEntrants). Specifically, it is exactly numEntrants / 2.

My suggested solution would then be as follows:

Arrange the entrants in an ordered list (which I'll call entrantList) in such an order that all of the entrants from a particular country are adjacent to each other.

for (int round = 0; round < numRounds; round++)
{
    for (int i = 0; i < (numEntrants / 2); i++)
    {
         Match entrantList[i] with
             entrantList[(i + largestNumEntrants + round) % numEntrants] for round.
    }
}

This algorithm clearly runs in $\cal O$(numEntrants$^2$) time and, as far as I understand them, satisfies all of your constraints, at least when numEntrants is even. Obviously, ${\cal O}(n^2)$ means that the problem is in P and is definitely not NP-Hard or NP-Complete.

This algorithm ensures that each entrant plays each other entrant a maximum of 1 time because it simply selects the entrant after the one it was previously matched with on each iteration. It ensures that no entrant from the same country plays another entrant from the same country because all entrants from the same country are adjacent to each other in the list and it starts with an offset of largestNumEntrants.


Can you have a binary search tree with O(logn + M) property for the following case Let $n$ be the number of strings which are sorted in lexicographical order and stored in a balanced binary search tree. You are provided with a prefix $x$ of which $M$ strings have the prefix $x$. I have devised the following algorithm, where I search until I find the first occurence of the prefix $x$ in one of the nodes. After that I run an inorder traversal on it, such that I print only the ones, that have prefix $x$ and are in order.

For example of sorted strings: $[ACT,BAT,CAT,CAB]$ and the prefix $x = CA$, I would print $CAT$ and $CAB$.

The data structure you are looking for is called a range tree. Range trees are usually used for geometric data, but they can be used here as well. In 1d, a range tree is simply a balanced binary search tree with the data stored at the leaves and the internal nodes augmented with the min and max element stored in the subtree. They have running time $O(\log n+ k) $  where $n$ is the total number of objects in the tree and $k$ is the number of objects reported. You will have to structure your queries slightly differently to use a range instead if a prefix. So add a special min and max character to your alphabet, call them 0 and 1 for convenience. Now to find all strings with prefix "CA", " you would search for all strings in the range (CA0, CA1).

As noted in the comments above, a trie is the structure one would normally use for this type or query. But the computational model used is slightly different, so it's hard to compare. The running time would be the length of your longest output string + k.


How can we prove that in binary search, low – high ≤ 1 How can we prove that in binary search
$$\mathit{low} - \mathit{high} ≤ 1$$
Below is a sample algorithm for Binary Search.
while (low<=high) {
  int mid = low + (high-low)/2;
  if (data[mid]<value) low = mid+1;
  else if (data[mid]>value) high = mid-1;
  else return &data[mid];
}
return nullptr;

A good stranger told me that

typically you would want to avoid unprotected mid-1 and mid+1 for fear of over- and underflow and have a special case for when the difference between high and low is less than 2.

What I still want to know is a formal proof that $\mathit{low} - \mathit{high} ≤ 1$ provided that you started off with $\mathit{low} ≤ \mathit{high}$.
My idea so far has been to adapt the explanation on loop invariant here but I can assure you I haven't made any progress, yet.

Let's denote the indices by $l,h,m$. If $l \leq h$ and $h-l$ is even then $m = \frac{l+h}{2}$ and so in the following iteration, the new values $l',h'$ will either be $\frac{l+h}{2}+1,h$ or $l,\frac{l+h}{2}-1$. In the first case
$$
l'-h' = \frac{l-h}{2}+1 \leq 1,
$$
and in the second case
$$
l'-h' = \frac{l-h}{2}+1 \leq 1.
$$
If $l \leq h$ and $h-l$ is odd then $m=\frac{l+h-1}{2}$ and so either $l',h' = \frac{l+h+1}{2},h$ or $l',h' = l,\frac{l+h-3}{2}$. In the first case
$$
l' - h' = \frac{l-h+1}{2} \leq \frac{1}{2}
$$
and so $l'-h' \leq 0$, since $l'-h'$ is an integer. In the second case
$$
l' - h' = \frac{l-h+3}{2} \leq \frac{3}{2},
$$
and so $l'-h' \leq 1$, since $l'-h'$ is an integer.
Put together, we have shown:

If $l \leq h$ then $l'-h' \leq 1$.

Now let's use it to show that $l-h \leq 1$ always holds.
We first prove by induction on $t$ that if the loop executes at least $t$ times, then after $t$ iterations of the loop, $l-h \leq 1$. The base case $t = 0$ is by assumption. Now suppose that after $t$ iterations, we have $l-h \leq 1$. If $l > h$ then the loop terminates, and so there is nothing to prove. Otherwise, $l \leq h$, and so $l-h \leq 1$ at the end of the iteration, as shown above.
This shows that when the loop terminates (if it terminates — which has to be shown separately), $l-h \leq 1$ necessarily holds. In fact, we can say more: since the loop terminated, we must have $l > h$, and so $l-h = 1$.


minimize $l_1$ distance between vectors Given two vectors $a$ and $b$ I need to find $k$ such that $\sum_i|a_i - kb_i|$ is minimal.  In other words, my goal is to find $k$ that minimizes the $l_1$ norm distance between $a$ and $kb$.

How should I approach such problem? The $l_1$ norm has weird derivative. Is there some analytical solution, or should I use something like ternary search?

Define $r_i=a_i/b_i$.  Sort the vectors in increasing order of $r_i$.  Let's assume (wlog) the $r_i$'s are in increasing order, i.e., $r_1 \le r_2 \le r_3 \le \cdots$.  Let $R=\{r_1,r_2,\dots,r_n\}$.

Notice that your objective function is differentiable at all $x$ such that $x \notin R$.  In fact, it is linear on each open interval $(r_i,r_{i+1})$.  It follows that it attains a maximum at one of the values $r_i$.

So, it suffices to try each of $r_1,r_2,\dots,r_n$ as possible values for $k$, and see which minimizes the objective function.  This leads to a simple $O(n^2)$ time algorithm.  With some optimization and clever tricks you can get this down to $O(n \lg n)$ time, by avoiding re-computing the objective function from scratch each time and re-using work.


Is is possible to determine if a given number is xor combination of some numbers? I have been given a number Y which is ($a$ xor $b$ xor $c$ xor $d$ xor $e$ ) of some numbers ($a$,$b$,$c$,$d$,$e$) and another no X. Now i have to determine if X is a xor combination of ($a$,$b$,$c$,$d$,$e$)

e.g - ($a$ xor $d$) , ($b$ xor $c$ xor $e$) , ( $a$ xor $e$ )

What i know clearly is that lets say X= ($b$ xor $d$) , Now if I xor X and Y i get
($a$ xor $c$ xor $e$), as ( $b$ xor $b$=0 ) and if it was some number not a xor combination (say $p$ ) then i would have got ($a$ xor $b$ xor $c$ xor $d$ xor $e$ xor $p$)

How should i approach this question?

Suppose that your numbers are $n$-bit long. Then you can think of them as elements of the vector space $\mathbb{F}_2^n$. The number $X$ can be written as an XOR of $a_1,\ldots,a_m$ if $X$ is in the linear span of $a_1,\ldots,a_m$. In order to determine whether $X$ is in the linear span of $a_1,\ldots,a_m$, you can use Gaussian elimination.


What is the complexity of finding the predecessor of a node in a doubly linked list? This is a question from Cormen 3rd edition(exercise 10.1). I am of the opinion that the complexity should be O(1), as we just have to look into the next pointer of the current node.

But the answers from the web suggest that it should be O(n). Where am I getting it wrong?

Can someone please help me out???

Thanks in advance!

Both answers look wrong. Time is indeed $O(1)$ because you can look into prev (not next) pointer of the node. The answers you found on the web are probably about single-linked lists.


One-taped RAM vs Multi-taped RAM In Turing Machine, we know that there's (fine-grained complexity) difference between one-tape, 2-taped and multi-taped TM, even though they could be simulated efficiently.

(Well, actually I'm not quite sure they are indeed seperated: i.e. $TIME(t)\neq TIME_{2-taped}(t)\neq TIME_{multi-taped}(t)$ )

But today I'd like to focus on RAM model, is there any complexity seperation between one-taped RAM model and multi-taped model? Though we might expect it be quite small because of random accessibility.

Random-access machines support the following operation in constant time:
$$
x \gets M[y],
$$
where $M$ is the memory array, and $y$ is an index whose allowable size depends on the exact model. Whether $M$ is an array of bits or an array of words depends on your exact model.

If you had several different memory arrays, say $M_1[y],\ldots,M_r[y]$, then you could simulate the command
$$
x \gets M_i[y]
$$
with the command
$$
x \gets M[ry + i]
$$
which also takes constant time.

Therefore there is nothing to be gained by allowing several "memories".


Classes of NFAs which allow efficient subset testing or unambiguity conversions I'm doing some research regarding NFAs and inclusion problems with them. I know that in general, the inclusion problems, and converting to an unambiguous NFA, are both PSPACE-complete.

I'm wondering, are there any sub-classes of NFA for which these can be decided efficiently? In particular, the NFAs I'm looking at accept finite language where all words have the same Parikh vector.

here are three refs that may be helpful.

Efficient Inclusion Testing for Simple Classes of
Unambiguous $\omega$-Automata
Dimitri Isaaka, Christof Lodinga

  We show that language inclusion for languages of infinite words defined by non-
  deterministic automata can be tested in polynomial time if the automata are
  unambiguous and have simple acceptance conditions, namely safety or reachability conditions. An automaton with safety condition accepts an infinite word
  if there is a run that never visits a forbidden state, and an automaton with
  reachability condition accepts an infinite word if there is a run that visits an
  accepting state at least once.

this 2nd ref is more indirect & would rely on a mapping between NFAs and tree automata.

Antichain-based
Universality and Inclusion Testing
over Nondeterministic Finite
Tree Automata
Ahmed Bouajjani, Peter Habermehl,
Luka´ˇs Hol´ık, Tayssir Touili, and
Toma´ˇs Vojnar

  We show the signiﬁcantly improved efﬁciency of this framework through a series of experiments
  with verifying various programs over dynamic linked tree-shaped data structures

the above ref also cites the following:

Antichains: A New Algorithm for Checking
Universality of Finite Automata, M. De Wulf, L. Doyen, T. A. Henzinger, and J.F. Raskin

  We show that on the difficult instances
  of this probabilistic model, the antichain algorithm outperforms the standard one by several orders of magnitude. We also show how variations
  of the antichain method can be used for solving the language-inclusion
  problem for nondeterministic finite automata...


Proof that finite automata is closed under intersection I'm looking at a proof that says that:
If $M_1=(Q_1, \Sigma , q_1, A_1, \delta)$ and $M_2=(Q_2, \Sigma , q_2, A_2, \delta)$ are two finite automata(FA) then $M=M_1 \cup M_2$ is also an FA. We define $M=(Q, \Sigma , q, A, \delta)$ where $Q=Q_1 \times Q_2$, $q_0=(q_1,q_2)$ and $\delta((p,q),\sigma)=(\delta(p,\sigma),\delta(q,\sigma))$.

I'm just having one problem. We have to prove that $\delta^*((p,q),x)=(\delta^*(p,x),\delta^*(q,x))$. (x is a string in $\Sigma^*$)
We do it by induction. I've already proven the base case, and I'm now trying to prove it holds for $x'=x\sigma$. This is what I've gotten so far:

$\delta^*((p,q),x')=\delta(\delta^*((p,q),x),\sigma)=\delta(\delta^*(p,x),\delta^*(q,x)),\sigma)$

I don't really know how to proceed from here. Can someone help?

A possible source of your confusion is that the transition functions of $M_1$, $M_2$ and $M$ are different functions, yet you call all of them $\delta$. If instead you use $\delta_1$ resp. $\delta_2$ for the transition function of $M_1$ resp. $M_2$, the definition of $\delta$ changes to $\delta((p,q),\sigma)=(\delta_1(p,\sigma),\delta_2(q,\sigma))$. You should be able to add the subscripts in the appropriate positions of your partial proof yourself.

Now, after noting that $\delta_1^*(p,x)\in Q_1$ and $\delta_2^*(q,x)\in Q_2$, the proof can be completed by a straightforward application of the definitions of $\delta$ and $\delta_i^*$.


How to find Maximum perimeter of rectangle in a grid with obstacles? (Dynamic Programming) Can someone tell me what am I doing wrong?

Problem: https://codeforces.com/contest/22/problem/B
Editorial: https://codeforces.com/blog/entry/507 ( I followed the DP solution O((n*m)^2) )

Eg:
00001
00000
10100     //ans is 12

####1
####0
10100

My approach: rectangle with coordinates (x1, y1, x2, y2) is correct if and only if rectangles (x1, y1, x2-1, y2) and (x1, y1, x2, y2-1) are correct, and board[x2][y2] = ‘0’.

ie: dp[x1][y1][x2][y2]=(dp[x1][y1][x2-1][y2] && dp[x1][y1][x2][y2-1] && (board[x2][y2]==0))

If it is correct then find it's perimeter (perimeter = 2*(x2-x1+y2-y1+2)) ie ans=max(ans,perimeter)
And dp[x1][y1][x2][y2]=1 for all i,j when board[x2][y2]==0. Because from point p1 to point p1, ie the same point always have a perimeter is the base case.

Your approach is basically correct. However, be sure to pay attention to a few boundary cases besides the general cases for x2>x1 and y2>y1.

Initialize the tables on a single square, i.e., dp[x][y][x][y] = (board[x][y] == 0);
Compute the case when the table can be on a single column, dp[x1][y][x2][y] = dp[x1][y][x2-1][y] && (board[x2][y] == 0), where x2>x1.
Compute the case when the table can be on a single row, dp[x][y1][x][y2] = dp[x][y1][x][y2-1] && (board[x][y2] == 0), where y2>y1.

For brevity, those boundary cases are not mentioned explicitly in the editorial. Once those cases are included, the algorithm will be fully correct.


What context free grammar generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$ I am struggling to think of the context-free grammar that generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$, where $i$, $j$ and $m$ are natural numbers.

Also, in general, are there any good methods or ways of thinking that help one to think of context free grammars that generate a given language. Any tips are much appreciated, thanks.

EDIT:
 I've tried S →ABCD, A →aA | λ, B →bB | λ,
C →ccC | λ, D →dD | λ

However, this doesn't allow for always generating twice the amount of c's as there are a's.

For matching number of a and c you need to do something like this:

$$
S \rightarrow AB \\
A \rightarrow aAcc \\
A \rightarrow C \\
C \rightarrow bC | λ \\
B \rightarrow dB | λ
$$

You need to produce them in one rule to be sure the ratio is kept.


Using all the entropy in an biased bit Suppose we have $n$ bits of random-looking data, and we want to encode it in such a way that instead of 1/2 the bits being 1's, we have (say) 3/4 the bits being 1's. The entropy of each bit in the new encoding is $-0.75\log_2(0.75)-0.25\log_2(0.25)\approx 0.81$, so we should be able to do it in about $1.23n$ bits.

(By 3/4 the bits being 1's, I mean that each bit should be indistinguishable from an event that happens with probability 3/4; as opposed to a long block of unbiased random bits followed by an equal length block of 1's.)

We could try, for each bit, put the next bit of the original data with probability 1/2, and put a 1 with probability 1/2. Then somehow include extra information about which bits encode the original data, and which are filler. But this reqiures at least $2n$ bits, well above the theoretical minimum. So how can the minimum actually be achieved?

Suppose you want exactly $3/4$ of the bits to be 1. If the encoded vector is of length $m$, it can be identified as a subset of $\{1,\ldots,m\}$ of size $(3/4)m$, of which there are $\binom{m}{(3/4)m}$. If $\binom{m}{(3/4)m} \geq 2^n$ then you can encode every $n$-bit string as such a subset using the technique of binomial encoding. Since $\binom{m}{(3/4)m} \approx 2^{mh(3/4)}$, this works as long as $m \gtrsim n/h(3/4) \approx 1.23n$.

Binomial encoding relies on Pascal's identity
$$ \binom{a}{b} = \binom{a-1}{b-1} + \binom{a-1}{b}. $$
To encode a number $x$ in the range $[0,\binom{a}{b})$, we act as follows:

If $x < \binom{a-1}{b-1}$ then we recursively encode $x$ as a subset $S$ of $\{1,\ldots,a-1\}$ of size $b-1$, and output $S \cup \{a\}$.
If $x \geq \binom{a-1}{b-1}$ then we recursively encode $x - \binom{a-1}{b-1}$ as a subset $S$ of $\{1,\ldots,a-1\}$ of size $b$, and output $S$.

The procedure can easily be reversed (exercise).


Approximating the dominating set on a certain kind of DAG A dominating set on a directed graph $G=(V,E)$ is a subset $D$ of $V$ such that for all $v\in V$ it holds that $v\in D$ or there is an $u\in D$ such that  $(u,v)\in E.$

For a concrete problem (size reduction of endgame tablebases), I want to approximate the dominating set of a directed acyclic graph with the following properties:

Each vertex $v\in V$ has a nonnegative integer $\mathop{\mathrm{DTM}}(v)$ assigned to it (with DTM standing for distance to mate)
For each pair of vertices $(u,v)$, if $(u,v)\in E$, then $1+\mathop{\mathrm{DTM}}(u)=\mathop{\mathrm{DTM}}(v)$ (if a move leads from $v$ to $u$, then the distance to mate from $v$ is one larger than that from $u$)
For each vertex $v\in V,$ there exists a vertex $z\in V$ with $\mathop{\mathrm{DTM}}(z)=0$ such that a path from $z$ to $v$ exists (each position can be brought to mate)

Given these boundary conditions, is there an efficient way to approximate $D$ for large graphs (more than 100'000'000 nodes?)

That problem is hard to approximate by reduction from set cover:

max(DTM) = 2    and    exactly one vertex has  DTM = 0

and    the vertices with  DTM = 1  are exactly the sets    and

the vertices with  DTM = 2  are exactly the set-elements

To push a solution forward, just add in the  DTM = 0  vertex.

To pull a solution back, remove that vertex if it's present, and for each

DTM = 2  vertex, replace that vertex with any one of the sets that element is in.

However, you presumably have another property:  low maximum degree .

That is useful because:

Your problem is a special case of set cover:  The elements are the vertices and the

sets are those formed as [v in V such that u=v or (u,v) in E] for elements u of V.

The size of those sets is bounded above by one plus your graph's maximum out-degree.

Theorem 3.1.6 says the greedy algorithm does significantly better on such instances.


Can the Y-combinator really terminate? My understanding of the Y-combinator is that it never terminates (Yg = g(Yg)). Its termination is only decided externally to the $\lambda$ specification when it has reached a fixed point (g(x)=x) because based on its $\lambda$ expression there is no exit from the infinite loop even when the fixed point is reached.
Am I wrong?

Terms containing the Y combinator can be weakly normalizing: they can terminate for a certain order of evaluation, i.e. for a certain evaluation strategy. No term containing the Y combinator applied to another term can be strongly normalizing, i.e. no term containing Y applied to another term terminates for all evaluation strategies, since the infinite reduction chain $Y \, M \to_\beta^* M \, (Y \, M) \to_\beta^* M \, (M \, (Y \, M)) \to_\beta^* \ldots$ is possible.
There are terms $M$ such that $Y \, M$ has no normal form, i.e. such that there is no reduction strategy that reduces $Y \, M$ to a value. For example $Y (\lambda x. x) \to_\beta^* (\lambda x.x) (Y (\lambda x.x)) \to_\beta Y (\lambda x. x)$ is a recursive functions that just spins (let x = x). (The lack of another reduction chain that terminates is left as an exercise for the reader.)
Under call-by-value (only ever reducing $M \, N$ when $M$ and $N$ are values), $Y \, M$ only converges if $M$ does not use its argument, i.e. if $Y \, M$ is not “really” recursive. Under call-by-name (always reducing the outermost redex first), $Y \, M$ converges if the recursive function that it defines terminates.


Relation between interactive proof systems (IP), NP, coNP, PSPACE I would like to ask you some clarification on the following question:
know that ${\sf NP}$ is a subset of ${\sf IP}$
and also ${\sf coNP}$ it is a subset of ${\sf IP}$.
So ${\sf IP}$ is a biggest class, but how much it is big?

May i say that ${\sf PSPACE}$ is a subset of ${\sf IP}$? or that they may intersect?

Can you give me a easy clarification about it?

IP = PSPACE is a famous result (and indeed paper) by Adi Shamir in 1992.

Furthermore, we clearly have NP $\subseteq$ PSPACE and coNP $\subseteq$ PSPACE, but we don't know how NP relates to coNP.  There are several reasons to believe that determining the relationship between NP and coNP is difficult, some of which are discussed in this recent thread.


Algorithm for finding optimal branch points I'm developing software to run variations on a base process flow (see #1, below). A user specifies in a text file what steps in the process to modify. Because each step takes a long time to run, I'd like to minimize the amount of duplicate processing required. For example, if variations occur at step B, I could run step A one for all results before "branching" at step B (see #2 below). Similarly, I could branch again at step D if additional variations on step D are indicated (see #3 below).

1) Base Process:

input --> A --> B --> C --> D --> E --> result

2) Modification of Step B:

input --> A --> B1 --> C --> D --> E --> result1
                B2 --> C --> D --> E --> result2

3) Modification of Steps B and D:

input --> A --> B1 --> C --> D1 --> E --> result1
                             D2 --> E --> result2
                B2 --> C --> D1 --> E --> result3
                             D2 --> E --> result4

Is there a simple algorithm to determine the the common process steps and the branch points as in #3 given a base flow as in #1 and a list of steps to change, e.g.

Variation  StepB  StepD
   1         1      1
   2         1      2
   3         2      1
   4         2      2

The above example is simple but there could be hundreds of variations modifying dozens of different steps in actual usage.

If whatever happens after $B$ depends on that, you can't "reuse" any runs after a modified $B$. So the tree-like scheduling is really the best that can be done.

If the later steps are independent of (some) of the previous steps, things get more interesting... but that presumes you have a completely reliable way of determining that. The simplest way to get the most efficient runs without too much extra work in this case would be just to store away the results of all runs, and instead of running any of them first check if the result is already stored (memoisation). Might need to supplement with some logic to clean up (delete results that won't be used ever again, or use some heuristic to delete them).


Horspool's String Search on 0s and 1s I'm confused in trying to solve the following problem:
Find the number of comparisons made by Horspool's string search algorithm in the following case:

String: 001001001001
Pattern: 111

Attempt 1
The shift table value for 0 as per the algorithm should be 3 i.e. length of the pattern, because 0 is not part of the pattern.

001001001001
111

001001001001
---111

... and so on. This leads to 2 comparisons in each of the 4 shifts i.e. 8 comparisons.

Attempt 2
Instead, the answer, and also my intuition, suggests 5 comparisons:

001001001001
111

001001001001
--111

001001001001
-----111

... and so on. 2 comparisons needed in the first run and only 1 in each of the following 3 shifts i.e. total of 5.

Intuitively, it makes sense NOT to slide along the pattern 3 spaces [attempt 1] in the first run of the algorithm because we are not taking into account that the first character of the pattern - 1- is the same as the last character of our previous string match block - 001.

I would like help in correcting my understanding of the algorithm.

Both - attempt 1 and 2 - are incorrect executions of the Horspool's algorithm. After the first round of trying to match the pattern in the text:

001001001001
111

There are two comparisons made of which the second one 0 == 1 fails. Now, the shift is determined by the last character in the section of the text being matched i.e. shift value of 1 which is 1. The next search round looks like:

001001001001
-111

This has only one comparison 0 == 1 which fails. The shift is now decided by the value of shift value of 0 which is 3, thus making the next round as follows:

001001001001
----111

This also has only one comparison, just like the previous one resulting in another shift of 3. The next round is also the same, with one comparison.

The total now, correctly, stands at 5.


Theta bound for runtime analysis of nested while loops I am trying to fully analyze the running time of $\texttt{nestedLoops}$ in terms of $n$ with a Theta bound.
The Java code I have is as follows:
public void nestedLoops(int n) {
     int i = 1;
     while (i < n) {
          int j = i;
          while (j > 1) {
               int k = 0;
               while (k < n) {
                    k += 2;
               }
               j = j // 2
          }
          i *= 2
     }
}

I know that the innermost while loop has an obvious runtime of $\lceil \frac{n}{2} \rceil$.
But I get stuck on the next while loops. I think the middle while loop has a runtime of $\lfloor
\log_2\texttt{i} \rfloor$, but that is very confusing for me.
Any help would be taken with much gratitude.

The innermost loop has running time $\Theta(n)$. The middle loop runs for $\Theta(\log i)$ iterations. If $2^m < n \leq 2^{m+1}$, this means that the total running time is proportional to
$$
n (\log 1 + \log 2 + \cdots + \log 2^m) = n \log 2(0 + 1 + \cdots + m) = \Theta(n m^2) = \Theta(n\log^2 n).
$$


Converting DFA to Regular Expression Using State Removal I'm trying to convert the following NFA to a regular expression.

I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been working at it for quite a while. Can anyone tell me where I went wrong? And if it happens to be correct, can you tell me why?

Thanks a lot in advance.

Think of it this way. You can reach 2 from 1 in two ways

$1\rightarrow 2$
$1\rightarrow 3 \rightarrow 2$

Then from 2, you can move to 1 by $2\rightarrow 1$. From there again, move to 2 from 1 in the above two ways. So this NFA can be expressed as an RE as follows:

$$RE = (1\rightarrow 2 + 1\rightarrow 3 \rightarrow 2) \cdot [(2\rightarrow 1)\cdot (1\rightarrow 2 + 1\rightarrow 3 \rightarrow 2)] ^*$$

Now its just the matter of finding the REs for $1\rightarrow 2$, $1\rightarrow 3 \rightarrow 2$ and $2 \rightarrow 1$.


When is the empty word part of $A^+$? My professor mentioned the below statement in class but without a proof. I am trying to prove it for myself as I don't understand 100% why this is always the case.
Given is A, a subset of {0,1}$^*$.

ε $\in\ A^+$ <-> ε $\in\ A$, where ε is the empty word.
I thought of doing a proof by contradiction to show -> by assuming the empty word is not part of A$^+$.

Any help is much appreciated!

You can look at the length of words.

Any element of $A^+$ is a concatenation

$$ a_1 a_2 \ldots a_n $$

where $a_i \in A$ and $n \geq 1$. The length of such a word is

$$ L(a_1 a_2 \ldots a_n) = L(a_1) + L(a_2) + \ldots + L(a_n) $$

But the length is always nonnegative; for example,

$$ 0 \leq L(a_1) \leq L(a_1) + L(a_2) + \ldots + L(a_n)$$

If you're given that

$$ \epsilon = a_1 a_2 \ldots a_n $$

then putting all of the above together gives

$$ 0 \leq L(a_1) \leq L(\epsilon) = 0 $$

and thus $L(a_1) = 0$, so $a_1 = \epsilon$ and $\epsilon \in A$.

If you were to assume that $\epsilon \notin A$, you could modify the above argument by the fact that $L(a_i)$ must be positive, and so

$$ 0 < L(a_1) \leq L(a_1) + L(a_2) + \ldots + L(a_n) $$

and then the final deduction would be

$$ 0 < L(\epsilon) $$

which is a contradiction.


What is the complement of ACFG What is the complement of $\mathrm{ACFG} = \{ G \mid G \text{ is a CFG and }L(G) = \Sigma^* \}$?

I think it is $\mathrm{ECFG} = \{ G \mid G\text{ is a CFG and }L(G) = \emptyset \}$.

It makes sense to me because the complement of the empty language is the universal language?

Am I correct?

First of all, the complement of a set is only defined when there is an (understood) universal set. In this case, the universal set is probably the set of all context-free grammars, but it could plausibly be the set of all grammars.

The complement of a set $A$ given a universal set $U$ is defined as the set of elements in $U$ but not in $A$; it is understood that all elements in $A$ are also in $U$. So if $U$ is the set of all context-free grammars, then the complement of ACFG is the set of all context-free grammars $G$ such that $L(G) \neq \Sigma^*$.
If $U$ is the set of all grammars then the complement of ACFG is slightly more complicated: it consists of all non-context-free grammars together with all context-free grammars $G$ such that $L(G) \neq \Sigma^*$.

If $G$ is a context-free grammar and $L(G) = \emptyset$ then $G$ certainly belongs to the complement of ACFG1; but other context-free grammars also belong there.

1This actually depends on your definition of grammar and on the value of $\Sigma$. If $\Sigma$ is understood and non-empty then what I wrote is correct; if $\Sigma$ is part of the grammar and is always non-empty, again what I wrote is correct; but if $\Sigma$ could be empty, then $\Sigma^* = \emptyset$, so what I wrote is wrong.


Complexity for merging 3 sorted arrays using this specific algorithtm During an interview I was asked to calculate the big theta complexity for the following algorithm that receives 3 sorted arrays of variable size and returns a new array which has the elements of the original 3 arrays.

The algorithm is pretty basic: we set indexes at the beginning of each array and use such indexes for accessing the elements, in that fashion  we find the minimum element for the 3 arrays (at the position given by the indexes) and then we insert the element into the resulting array and we increase such index. We repeat until we are done processing every element.

My answer was that the complexity was linear because we are processing n elements and we are doing a constant number of comparisions for finding the minimum element out of the 3 arrays (at the given index position). Yet, I was told that the complexity is not linear but it is higher than nlogn.

I have a few ideas but could someone explain  the actual complexity of this algorithm for me?

Thanks for your time.

Assuming that you're using some random-access model of computation (i.e., not an ordinary Turing machine) and that comparisons can be done in constant time, the algorithm you describe is linear. Each element of the final array is produced by comparing at most three elements of the original arrays, so each element of the output is produced in constant time.

Perhaps you misunderstood the question and they were actually asking about something else? Perhaps they mis-stated their question and they were trying to ask about the complexity of three-way mergesort (sorting an array by splitting into three parts, recursively sorting the parts, then merging them)? Perhaps they were just wrong.


What are witnesses C and k for an O-bound? Can someone explain the following about big-O from the textbook to me? (I'm trying to catch up after missing classes due to illness.)

  Show that $f(x) \in O(x^2)$ where $f(x) = 8x+9$. List the witnesses $C$ and $k$.

From what I have gathered I am looking at/for a distinct point witnessed by $C$/$k$ wherein there is a (lower bound?) point to where one of the functions ($f(x)$ or $g(x)$) is increasing at a faster rate for any given point $\geq C$?

The textbook talks testing/trying out different $C$ witnesses (ex. 1) to where I then solve for $8x+9\leq(1)x^2$ or (ex. 2) and solve for $8x+9\leq(2)x^2$, but I'm not sure where I go from there. If I'm letting $C=1$ then I get:

\begin{gather*}
8x+9\leq(1)x^2\\
0\leq x^2-8x-9\,.
\end{gather*}

Then from here I have tried the quadratic equation resulting in $(8 \pm \sqrt{100})/(2)$ or I saw where $0\leq x^2-8x-9$ could be factored to $(x+1)(x-9)$ so I know $-1$ and $9$ make zeroes on my number line, and I tried plugging in test points where I found everything less than $-1$ or greater than $9$ yields a positive, and everything between $-1$ and $9$ yields a negative, but from this point I am lost.

Can someone explain what I'm supposed to be doing and how to go about it?

I am going to guess what $C$ and $k$ mean in your context:

$f(x) = O(g(x))$ if and only if $\exists C, k \;\; \forall x \ge k \;\; (f(x) \le C|g(x)|)$.

You are asked to find constants $C$ and $k$ and prove that for all $x \ge k$ you have $8x+9 \le C x^2$.

I am going to take $C = 1$ and $k = 9$. We have $x \ge 9$ so $C g(x) = C x^2 = x^2 \ge 9 x = 8x + x \ge 8x + 9 = f(x)$.


Relation between simple and regular grammars I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with
simple and regular (especially right linear) grammars which are very similar to each other.

What relation exists between these? What is the difference?
Can you create (non-deterministic) finite automata for simple grammars (obviously without using a stack)?

A Simple Grammar (s-grammar) is one in which every production is of the form $A \rightarrow aB_1B_2...B_n$ where $a$ is a terminal and all $B_i, i\geq0 $ are non-terminals, and there is only one production with any pair $\langle A,a\rangle$.

Clearly, every s-language (produced by an s-grammar) is unambiguous and easily parsed, since each terminal symbol from left-to-right and non-terminal uniquely determine the production to apply.  For example, if the string is $abc$, then the pair $\langle S,a\rangle$ uniquely determines the first production of the parsing, and so on for each terminal and the non-terminal to its immediate right.  Thus, a language defined by an s-grammar can be parsed one symbol at a time, without lookahead, yielding linear parsing time, in fact, time $|x|$.

S-grammars are not terribly important in their own right, since most real languages exceed their power. But they are a stepping stone to other grammars parsed in linear time, such as $LL(k)$ grammars in which there is a bound $k$ on the lookahead needed to determine a production during parsing. In effect, an s-grammar is an $LL(0)$ grammar.

The connection to automata is that an s-langauge can be parsed with a pushdown automaton with a single state which just looks at the input symbol and top stack symbol to determine a string of stack symbols to push.  But since the s-grammar...

$S \rightarrow aSB|\#\\ B\rightarrow a$

...generates non-regular $\{a^i\#a^i:i \geq 0\}$, s-languages cannot in general be recognized by finite-state automata, deterministic or non-deterministic.


Dynamic algorithm: what's the difference between memorization and bottom-up algorithm? Here are two ways to output a subset of activities S such that no activities in S overlap and profit(S) is maximum.

I can't see what's the difference between these two algorithms except the first one use a if statement and the second one use a for loop. They both store result in OPT[n] first.

The algorithms are indeed very similar, but there are several differences:

Order of evaluation: The bottom-up algorithm specifies a particular order of evaluation, which ensures that when OPT[i] is due to be computed, all the prerequisites have already been computed. In the memoization algorithm, this is taken care of automatically.
Evaluated entries: The bottom-up algorithm evaluates all entries of OPT, even though only OPT[n] is needed. The memoization algorithm only computes the entries that are necessary for computing OPT[n].

Two other differences, which are not encountered in this example:

Indexing: The bottom-up algorithm stores its entries in a simple array. The memoization algorithm, in more general instances, uses an association array (i.e., dictionary or hash table).
Memory term: The memoization algorithm remembers all entries which have been computed. A smart bottom-up algorithm could "forget" some of them.

Summarizing, the memoization algorithm is simpler to program. In terms of efficiency, the memoization algorithm has the advantage that only the necessary entries are calculated. In other instances, however, a lot can be saved by implementing a dedicated algorithm, in terms of indexing cost and, especially, memory usage.


How can I estimate Bhattacharyya parameter for BSC channel, used for Polar codes In polar codes, the frozen bits in each message are determined through the worst channel, where the relevant parameter is the Bhattacharyya .

How can I estimate Bhattacharyya parameter for BSC channel?

I do not think you can use formula (14) on page 5 of 'How to construct polar codes'. I think you want to compute Bhattacharyya parameters after channel polarization. Hence, you need to compute transition probabilities of synthesized channels firstly, and then compute Bhattacharyya parameters using formula (14) on page 5 of 'How to construct polar codes'. The formula of transition probabilities of synthesized channels is give by Arikan in his TIT paper, but it is not easy to implement it.


SAT algorithm for determining if a graph is disjoint What are some good algorithms to have a SAT (CNF) solver determine if a given graph is fully-connected or disjoint?

The best one I can think of is this:

Number the nodes 1..N, where N is the number of nodes in the graph.
define N^2 variables with the ordered pair (P, Q), where P = 1..N and
Q = 0..N-1.
Set (1,0) to true.
Set (A,P+1) to true iff there is an
edge connecting node A and node B and (B,P) is true.
If there exists
a true (X,Y) variable for all possible nodes X, then the graph is
connected.

Effectively, (X,Y) means "Node X is Y steps away from node X".

This seems inefficient at O(N^2) variables. Can this be improved?

A comment (from when I posted this on cstheory.stackexchange.com) asked why I would need a SAT-based algorithm when O(N) algorithms for connectivity are well-known. The reason is simple -- I have many other SAT-based constraints on the graph that also need to be satisfied at the same time.

Given a graph $G = (V,E)$, here is a SAT instance which is satisfiable iff the graph is not connected.

Pick an arbitrary vertex $v_0 \in V$, and add the following clauses, over the variables $x_v$ for $v \in V$:

$x_{v_0}$.
For every $(u,v) \in E$, $\lnot x_u \lor x_v$ and $\lnot x_v \lor x_u$.
$\bigvee_{v \neq v_0} \lnot x_v$.

Here is a SAT instance which is satisfiable iff the graph is connected.

Pick an arbitrary vertex $v_0 \in V$, and add the following clauses, over the variables $x_{v,i}$ for $v \in V$ and $i \in \{0,\ldots,n-1\}$:

$\lnot x_{v,0}$ for all $v \neq v_0$.
For every vertex $v \in V$ and $i \in \{0,\ldots,n-2\}$, $\lnot x_{v,i+1} \lor x_{v,i} \lor \bigvee_{u\colon (u,v) \in E} x_{u,i}$.
For every vertex $v \in V$, $x_{v,n-1}$.


Voronoi Diagram Drawing Variations and Charateristics I am learning about Voronoi diagrams and I have seen that the Voronoi diagram of a set of points is drawn with straight line segments and rays.

Similarly how can we draw the Voronoi diagram for the following:
(a) A set of lines and points?
(b) A set of disjoint line segments?
(c) A set of line segments forming a convex polygon?
(d) A set of circles (non intersecting and no circle contains another)?

For each of these sets of objects, how can we describe the shape of the boundary pieces that form the Voronoi diagram.

I believe that the distance between a point and another object is the smallest distance between the point and any point of the object.

The Voronoi diagram of disjoint segments (b) has been thoroughly studied.

Image from GIS.

See:

  CGAL Manual, Chapter 43:
  2D Segment Voronoi Diagrams. CGAL link.

For the Voronoi diagram of circles (d), see:

  Jin, Li, Donguk Kim, Lisen Mu, Deok-Soo Kim, and Shi-Min Hu. "A sweepline algorithm for Euclidean Voronoi diagram of circles." Computer-Aided Design 38, no. 3 (2006): 260-272. Journal link.

  Huber, Stefan. Computation of Voronoi diagrams of circular arcs and straight lines. Magisterarbeit, 2008.

To quote the latter: "Lemma 1.4. The bisector between two circles (...) consists of ellipses and hyperbolas."
PDF download.


How to express taking the next bit of an infinite string in small-step semantics? I have to write a rule as part of a small step operational semantics (https://en.wikipedia.org/wiki/Operational_semantics).

Whenever this rule is applied, the next bit belonging to an infinite
bit string must be taken.
Therefore, in the premise of the rule, I have to express that the next bit of a (previously) fixed bit string is taken.

To represent the set of infinite (bit) strings, it is usually used the notation $\{0,1\}^{\omega}$.

So, the first idea is to write the premise of the rule in the following way:
$ b= nextBit(str) \quad str \in \{0,1\}^{\omega}$.

What do you think about that?
In my opinion, it doesn't make explicit that the infinite string $str$ is chosen once and then fixed.
Is it something like

$ b = nextBit(str  \rvert_{str \in \{0,1\}^{\omega}})$

reasonable or it is too fuzzy/ non standard?

How would you express it explicitly that $str$ is fixed and it doesn't change during the run?

In general, the only persistent pieces information in a deduction rule (like the ones in the wikipedia article) are the variables which are shared between one of the premises and the conclusion of the rule.

So in effect, a findOne function that operates on a given (fixed) string and returns the position of the first bit which is one would have to pass the string to the conclusion of the rule. Thus one possible formulation would be

$$ \frac{\mathrm{findOne}(str)}{\mathrm{findAux}(str,0)}$$

where findAux is defined by

$$ \frac{\mathrm{findAux}(str, n)\quad \mathrm{nextBit}(str)=0}{\mathrm{findAux}(\mathrm{getTail}(str),n+1)}$$

$$ \frac{\mathrm{findAux}(str, n)\quad \mathrm{nextBit}(str)=1}{n}$$

And nextBit is defined by other rules. One often uses pattern notation instead, so if strings of bits are represented $1.0.0.1.1.0.0.1\ldots$ (so concatenation is "$.$"), the first rule would be

$$ \frac{\mathrm{findAux}(0.str, n)}{\mathrm{findAux}(str,n+1)}$$

Note that the free variables $str$ and $n$ are implicitly universally quantified, so the first rule reads

  For any value of $str$, the value of $\mathrm{findOne}(str)$ is the value of $\mathrm{findAux}(str, 0)$.

Having "side conditions" such as $str\in\{0,1\}^\omega$ can clarify, but is usually clear from the context. Note that the $str$ in the premisse and the conclusion are the same, by definition of what a deduction rule is.


kNN: how to improve Spam classification? Currently I'm trying to classify spam emails with kNN classification. Dataset is represented in the bag-of-words notation and it contains approx. 10000 observations with approx. 900 features. Matlab is the tool I use to process the data.

Within the last days I played with several machine learning approaches: SVM, Bayes and kNN. In my point of view, kNN's performance beats SVM and Bayes when it comes to minimize the false positive rate. Checking with 10-fold Cross-Validation I obtain a false positive rate of 0.0025 using k=9 and Manhattan-Distance. Hamming distance performs in the same region.

To further improve my FPR I tried to preprocess my data with PCA, but that blow away my FPR as a value of 0.08 is not acceptable.

Do you have any idea how to tune the dataset to get a better FPR?

PS: Yes, this is a task I have to do in order to pass a machine learning course.

You could consider querying the k-nearest neighbours and weight them following some schema like this one. There are quite a few in the literature. The general idea is to give more relevance to those neighbours lying closer to your sample. It has the effect of regularizing your classifiers (smooth out your decision surfaces).

You evaluated your algorithm using 10-fold CV. What is the dispersion of your measurements?. If you see wide dispersion, you could use bagging. It is very easy to implement. It is specially meaningful when overfitting is strong.


The characterization of a problem as PSPACE-complete is ...? Let's assume that you found out that some problem $\mathit{\Pi}$ is PSPACE-complete (with respect to your favorite kind of reductions, say, logspace reductions). However, as there are dozens of well-known and very different PSPACE-complete problems, this characterization doesn't tell you much about the real hardness of deciding membership in $\mathit{\Pi}$ (and you determine to refine the hardness of membership in $\mathit{\Pi}$ further by some other means, i.e., different from the good old standard complexity classes).
Now, how do you express in plain English the unsatisfactory fact that the PSPACE-completeness of $\mathit{\Pi}$ doesn't tell you too much? Do you say that the PSPACE-completeness characterization of $\mathit{\Pi}$ is

coarse
coarse-grained
coarsely grained
coarsely granular
crude
gross
grainy
granular
rough
unrefined
... (your choice goes here) ...

?

Which word is idiomatic?

Several are idiomatic: "coarse", "coarse-grained", "crude", "rough", "unrefined". These all (roughly) mean 'lacking in [fine] detail'.

"Coarsely grained" and "coarsely granular" don't work well in this case (though the meaning would not be lost, it just reads strangely). These two imply that you're talking about properties of the object (in this case the characterisation - the first that it has a grain of some kind which is coarse, the second that it comes in rough lumps).

"Gross", "grainy" and "granular" don't work at all, and would require the reader to guess that you actually meant to write something else. The "grain" in "coarse-grained" refers to meaning 5, not meaning 1 as described here, so the adjective granular is incorrect. "gross" at its root means "large", so doesn't give the right intent here either.

As an alternative with a different core meaning, you could say that it's "unenlightening", or "unilluminating", suggesting that it doesn't tell you much, rather than it's rough.


Regularity of unary languages with word lengths the sum of two resp. three squares I think about unary languages $L_k$, where $L_k$ is set of all words which length is the sum of $k$ squares. Formally:
$$L_k=\{a^n\mid n=\sum_{i=1}^k {n_i}^2,\;\;n_i\in\mathbb{N_0}\;(1\le i\le k)\} $$
It is easy to show that $L_1=\{a^{n^2}\mid n\in\mathbb{N_0}\}$ is not regular (e.g. with Pumping-Lemma).
Further, we know that each natural number is the sum of four squares which implies that for $k\ge 4$ all languages $L_k$ are regular since $L_k=L(a^*)$.

Now, I am interested in the cases $k=2$ and $k=3$:

$L_2=\{a^{{n_1}^2+{n_2}^2}\mid n_1,n_2\in\mathbb{N_0}\}$, $L_3=\{a^{{n_1}^2+{n_2}^2+{n_3}^2}\mid n_1,n_2,n_3\in\mathbb{N_0}\}$.

Unfortunately, I am not able to show whether this languages are regular or not (even with the help of Legendre's three-square theorem or Fermat's theorem on sums of two squares).

I am pretty sure that at least $L_2$ is not regular but unhappily thinking is not a proof. Any help?

Let's start with $L_2$. It is known that the upper density of integers which are the sum of two squares is 0. If $L_2$ were regular then it would be eventually periodic, and so, since its upper density is 0, finite. But we know that there are arbitrarily large integers in $L_2$, so that $L_2$ cannot be regular.

Regarding $L_3$, consider the words $w_k = 1^{4^k 7}$. I claim that for $k < \ell$, the words $w_k,w_\ell$ are inequivalent. Indeed, $w_k 1^{4^k 8} \notin L_3$ while $w_\ell 1^{4^k 7} \in L_3$. The Myhill–Nerode criterion then shows that $L_3$ is irregular.


Advantages of Lambda calculus over Turing machine and vice versa What kind of advantages does Lambda calculus have over Turing machine, and vice versa?

The lambda calculus and Turing machines are equivalent models of computation, each of which formally captures the informal notion of effective calculation (this is the Church-Turing thesis). The lambda calculus is a more abstract and algebraic approach, whereas Turing machines offer a more concrete, algorithmic approach.


Identity of object in OOP In the object oriented programming  concepts I found the term "Identity of object". What does it mean by "Identity of object"?

Depending on the programming language, some or all objects might have reference semantics. What this means is that when you assign the object to a variable or pass it to a method, it's still the same object, not a copy. This means the object maintains identity independent of the values it holds.

For example, in C#, classes have reference semantics, while structs do not. This means that for a class C and struct S:

C c1 = new C();
c1.Name = "c1";
C c2 = c1;
c2.Name = "c2";
WriteLine(c1.Name); // writes "c2"
WriteLine(c1.Equals(c2)); // writes "True"

S s1 = new S();
s1.Name = "s1";
S s2 = s1;
s2.Name = "s2";
WriteLine(s1.Name); // writes "s1"
WriteLine(s1.Equals(s2)); // writes "False"

As you can see, changing the class instance through one variable affects the other variable too, showing that both refer to the same object. Also, you can see that the two variables are equal. So, classes in C# maintain object identity.

For the struct, each variable is independent: changing one does not affect the other. This means that structs in C# do not have object identity in C#.

Other languages behave differently. For example, Java does not have structs at all, all user-defined types have reference semantics.

As another example, in C++, you can decide to use reference semantics or not on a case-by-case basis, by choosing to use pointers (or references) or not.

Note: Equals() in C# can be overridden. But since C or S do not override it, the default implementation of Equals() mostly behaves the way we want for both.


Converting this NFA-e to DFA I came across this question about NFA-e and thought to convert it into DFA:

This is what I did.

$\begin{array}{|c|c|}
\hline
& a \\ \hline
 q_1&q_2 \\ \hline
 q_2&\phi \\ \hline
 q_3&\phi  \\ \hline
\end{array}$

Found epsilon closure of states:

$\varepsilon(q_1) = q_1$

$\varepsilon(q_2) = [q_2, q_3, q_1] = P$ (let)

$\varepsilon(q_3) = [q_3, q_1] = Q$ (let)

Defined new transition rule for the states:

$\delta'(q_1, a) = \varepsilon\{\delta(q_1, a)\} = \varepsilon(q_2) = P$

$\delta'(P, a) = \varepsilon\{\delta(q_2, a) \cup\delta(q_3, a) \cup \delta(q_1,a)\}=\varepsilon\{\phi\ \cup\ \phi\ \cup q_2\}=P$

$\delta'(Q,a)=\varepsilon\{\delta(q_3,a) \cup \delta(q_1,a)\}=\varepsilon\{\phi \cup q_2\}=P$

$\begin{array}{|r|r|}
\hline
&a\\\hline
q_1&P\\\hline
*P&P\\\hline
Q&P\\\hline
\end{array}$

Now I'm stuck on how to make the FSM. There is no transition to $Q$ from $q_1$ or $P$. What did I do wrong?

Alright we've to remove the unreachable state that is $Q$, for which we have to follow these steps:

Initialize a set $R$ containing the initial state.
Create a set $M$ which'll contain the states which are reachable from states in $R$ in single transition.
Perform $R = R\cup M$.
Repeat from step 2 until $R$ stops getting new states.
Remove states from complement of $R$.

Create set $R = \{q_1\}$.

Calculate $M$ by finding states which can be reached from $\{q_1\} = \{P\}$.

Perform $R = R\cup M:\{q_1\}\cup\{P\}=\{q_1, P\}$.

Calculate $M$ again from $\{q_1,P\}=\{P\}$.

Perform $R=R\cup M:\{q_1,P\}\cup\{P\}=\{q_1,P\}$. $R$ has no new states to add. Therefore, we'll remove states from complement of $R: \{q_1, P, Q\} - \{q_1,P\}=\{Q\}$. The FSM will be:

I learned this here http://www.cs.um.edu.mt/gordon.pace/Research/Software/Relic/Transformations/FSA/remove-unreachable.html


Relations and Zero One Matrices I was studying but realized that I am having trouble grasping the representations of relations using Zero One Matrices.  For example if I have a set A = {1,2,3} and a relation R = {(1,1),  (1,2), (2,3), (3,1)}.

What is the resulting Zero One Matrix representation?
How exactly do I come by the result for each position of the matrix? How to tell if it is reflexive, transitive, antisymmetric or symmetric?

The resulting zero-one representation is the $|A|\times |A|$ matrix $M$ with $M_{ij} = 1$ if $(i,j) \in R$, and $M_{ij} = 0$ if $(i,j) \notin R$. In our case, the matrix is
$$ M = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}. $$
Take it as an exercise to prove the following properties:

$R$ is reflexive iff the diagonal of $M$ is all 1s.
$R$ is symmetric iff $M$ is symmetric.
$R$ is antisymmetric iff the off-diagonal entries of $M+M^T$ are 0/1 (but not 2).
$R$ is transitive iff the support of $M^2$ is a subset of the support of $M$, where the support is the set of non-zero entries.


Is integer factorization reducible to subset sum? Is it possible to solve the FACT (integer factorization) problem in polynomial time if we know the polynomial Subset Sum algorithm?

We assume that we know the algorithm solving the problem of Subset Sum with complexity: $n ^ 4 \cdot m ^ 4$ (for example), where $n$ is the number of elements in the set, and $m$ is the size of the largest element (absolute value).

Theoretically, we can perform a reduction from FACT to 3SAT and from 3SAT to Subset Sum.

However, the reduction from 3SAT to Subset Sum has a problem.

After such a reduction (from 3SAT), the numbers in Subset Sum are very large.

For example, let's see page number four in this document.

The search number is: $11133$ for a logic function composed of only three variables and two clauses.

The number we are looking for is always around $ 10 ^ {v + c} $ where $v$ is number of variables and $c$ is number of clauses.

We can solve the Subset Sum in time $n ^ 4 \cdot m ^ 4$ but if $m$ grows exponentially, then the whole grows exponentially.

Is there any way to solve this?

---- Update:

I found this answer. It directs me to the conclusion that there is no classic decimal notation. Maybe this is some unary notation? Do I presume well? I am concerned, however, about the value of "3" in $k$ (the last row in the table on the fourth page in document). How can we encode it in decimal / binary form?

Yes, such a reduction exists.  Subset Sum is NP-complete.  FACT is in NP.  Therefore, by the definition of NP-complete, there exists a reduction from FACT to Subset Sum.

To find such a reduction explicitly, work through the proof of NP-completeness for Subset Sum; it will describe such a reduction.  (Implicitly, we get a reduction from FACT to SAT by Cook's theorem, and from the proof of NP-completeness for Subset Sum you will be able to extract a reduction from SAT to Subset Sum.  Now compose those two reductions.)


How to Determine Places, Transitions and Tokens in a Scenario when Modeling with Petri Nets? When modeling a scenario with Petri nets how should I determine the places, transitions and tokens?

Example:

There are two exam assistants in an exam hall observing the exam. They stand in front of the exam hall. When a student has a question one of the assistants goes to him and answers his question while the other stays in front of hall. When the question is answered, the assistant goes back to the front of the hall.

By modeling this scenario it must be distinguished which assistant stays in front of hall. Then the Petri net must be expanded so that the assistants take turns answering the questions.

Here is my solution:

p0 represents the front of the exam hall. The two tokens represent the assistants and p1 is where the student seats. I also limited the capacity of p1 to one.

The given solution is however totaly different:

How should I generally think and how can I determine which part of a given scenario is represented by which part of the Petri net (places, transitions and tokens)?

Generally, the idea of a (normal) petri-net is to efficiently represent a system to model an arbitrary amount of 'agents' that change their state depending on certain transitions. (This would quite quickly get out of hand in a state machine)

So, the basic strategy is to first determine what your 'agents' are and model them as your tokens. The state of an individual agent corresponds to the places and the state transitions correspond to transitions in the petri-net.

Depending on what you want to model, you need to do a bit more and also consider different (in your modeling interpretation, not as far as the petri-net is concerned) tokens that are created by some action of other tokens, but the general idea of what tokens, places and transitions are remains the same.

Your answer follows the basic strategy, but it fails to meet the requirement that the tokens are distinguishable and that at least one of them must remain in front of the hall. In a normal petri-net, we cannot distinguish tokens from another, so if a token moves to $p_1$, we cannot know which.

A solution is to construct different transitions such that we know which assistant moves, based on the transition taken. The 'given solution' you provide does this and adds some restrictions to model the requirement that at least one of them must remain in front of the hall.


Does the intersection of VC and CLIQUE belong to NPC? Define: $$L=\{(G,k) :  G\text{ has a vertex cover of size at most $k$, and a clique of size at least $k$}\}$$

I need to determine whether $L\in \mathrm{NPC}$ or $L\in \mathrm{P}$. I suspect that $L\in \mathrm{NPC}$, been trying to prove it by looking for a reduction from Vertex Cover, but couldn't find one.

The graphs with clique size at least $k$ and VC at most $k$ have a particular
structure: They can be partitioned into three sets, $C$, $I$ and a singleton
$\{s\}$; $G[C]$ is a clique, $G[I]$ is an independent set and $s$ is just a
vertex.  $G[C \cup I]$ is what's called a split
graph.

Proof: If a graph $G$ contains a clique of size $k$, then that clique uses up
(at least) $k-1$ of your vertex cover budget.  Let $G,k$ be a yes instance and
$C$ any $k$-clique.  Observe that $G - C$ is a star with possibly isolated
vertices.

There are two cases: $G-C$ has edges, and $G-C$ does not have edges.  The latter
case is trivial, since we can let $C$ be the solution.  In the former case,
$G-C$ is the star graph with isolates.  Let $s$ be the vertex with non-zero
degree.

Both these cases lead to polynomial recognition algorithm.  The one in which
$G-C$ is an independent set, is the case where $G$ is a split graph.  The other
case has one vertex $s$ for which $G-s$ is a split graph.  Guess $s$, and you're
back at case 1.

As xskxzr pointed out, there is not necessarily a unique "split partition", that is, a partitioning of a split graph into the vertex sets $C$ and $I$, however, there are at most $n$ such partitions, and you can try all.  This leads in the end to an $O(n^3m)$ algorithm for VC∩C, which I'm sure can be improved.


Decision if there exists a path between $s$ and $t$ of length $k$ I conisder a problem:

  It is given a graph $G$, vertices $s,t$, $k$- length of the graph. Prove that decision whether there is a path between $s$ and $t$ of length $k$ is NP-complete.

Please note that in our problem we have a path, not a **simple path* **

*It is trivial when we have a simple path (define as sequence of vertices where every vertice occurs at most once (there is no cycle) ).

I don't know how to start. I cannot come up what's problem I should reduce. Please hint me.

I think you (or whoever asked you this question) probably does mean "simple path" (that is, a path that does not contain any vertex more than once), since this problem is indeed NP-hard.

If paths that may repeat vertices (often called "walks") are permitted, the problem is not NP-hard any more: It can be solved in polynomial time using matrix multiplication.  Specifically, if $A$ is the adjacency matrix of the graph, then $A^k[i, j]$ (the element at row $i$, column $j$ in the matrix $A$ raised to the $k$-th power) is the number of walks of length exactly $k$ from $v_i$ to $v_j$.  You can compute $A^k$ in $O(n^3 \log k)$ time using exponentiation by squaring.


"For small values of n, O(n) can be treated as if it's O(1)" I've heard several times that for sufficiently small values of n, O(n) can be thought about/treated as if it's O(1).
Example:

The motivation for doing so is based on the incorrect idea that O(1)
is always better than O(lg n), is always better than O(n). The
asymptotic order of an operation is only relevant if under realistic
conditions the size of the problem actually becomes large. If n stays
small then every problem is O(1)!

What is sufficiently small? 10? 100? 1,000? At what point do you say "we can't treat this like a free operation anymore"? Is there a rule of thumb?
This seems like it could be domain- or case-specific, but are there any general rules of thumb about how to think about this?

This is largely piggy-backing on the answers already posted, but may offer a different perspective.

It's revealing that the question discusses "sufficiently small values of n".  The whole point of Big-O is to describe how processing grows as a function of what's being processed.  If the data being processed stays small, it's irrelevant to discuss the Big-O, because you're not interested in the growth (which isn't happening).

Put another way, if you're going a very short distance down the street, it may be equally fast to walk, use a bicycle, or drive.  It may even be faster to walk if it would take a while to find your car keys, or if your car needs gas, etc.

For small n, use whatever's convenient.

If you're taking a cross-country trip, then you need to look at ways to optimize your driving, your gas mileage, etc.


DSPACE(f(n)) closed under complement I think you can create the complementary language that is an element of DSPACE($f(n)$), where $f(n) \geq \log(n)$ by adding a step to the algorithm that reverses the answer. By that the function $f(n)$ does not change, therefore DSPACE($f(n)$) is closed under complement.

I know that most likely my answer is wrong. Can someone explain why?

Your reasoning is essentially correct. Assuming your TMs are deciders (i.e., they must also properly reject their inputs), you don't even need an extra step in your algorithm; you can just swap the accept and reject states of your TM (just like you do with DFAs!).

In case your TMs are only defined as acceptors (i.e., a word not in the language will not necessarily be explicitly rejected, just not accepted), things are a bit more complex. In fact, we must then require more of $f$, namely that it is space-constructible; that is, given $n$ (unary encoded), we should be able to compute $f(n)$ (binary encoded) in space not greater than the value $f(n)$ itself. This property holds for practically all "standard" functions you know.

If that is the case, then, given a TM $A$ which accepts a language in space bounded by $f$, we proceed as follows:

Compute $f(n)$ (using $f(n)$ space).
Initialize a counter with the value $f(n)$. This counter need not use more space than what was already used in step 1; for example, we store it in a separate track of the TM tape.
Simulate $A$. For every step $A$ takes, decrement the counter. If the counter reaches zero, then enter the reject state (or loop without ever accepting).

This takes at most $f(n)$ space in steps 1 and 3 (and we reuse the tape in step 3), while step 2 does not take any additional space at all since representing the counter uses space on the order of $\log f(n)$, which is smaller than $f(n)$ (which is necessarily an integer), and we use a separate track for it.