texts: Retrieving the shortest path of a dynamic graph

texts:
I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is dynamic? By saying dynamic I mean that we can insert or remove vertices during the execution of the program. I'm trying to find an efficient algorithm for updating the shortest paths from a vertex $v$ to every other vertex $u$, after inserting an edge $e$, without needing to run the shortest path algorithm in the new graph again. How can I do this? Thanks in advance.

Note: the changes can be done after the first iteration of the algorithm
Note[2]: two nodes are given, $s$ the source and $t$ the target. I need to find the shortest path between these nodes. When the graph is updated I only have to update $\pi(s,t)$, which is the shortest path between $s$ and $t$.
Note[3]: I'm only interested in the edge insertion case.

  A formal definition: Given a graph $G = (V,E)$. Define an update operation as 1) an insertion of an edge $e$ to $E$ or 2) a a deletion of an edge $e$ from $E$. The objective is to find efficiently the cost of all pairs shortest paths after an update operation. By efficiently, we mean at least better than executing an All-Pairs-Shortest-Path algorithm, such as Bellman-Ford algorithm, after each update operation.

Edit: Below there is a simplified version of the problem:

  A weighted graph $G(V,E)$ is given, consisting of unidirectional edges, and two critical vertices $s$ and $t$. A set $C$ of candidate bidirectional edges is also given. I have to build an edge $(u,v) \in C$ to minimize the distance from $s$ to $t$.


texts: Why does this BFS solution work for this question about euclidean distance and what's its complexity?

texts:
Given a matrix of 1s and 0s where 0 represents houses and 1 represents stores, find the square of minimum Euclidean distance of every house to nearest store. Return it as a vector of vector.

[[1, 1, 0],
 [0, 0, 0],
 [0, 0, 0]]

should return

[[0, 0, 1],
 [1, 1, 2],
 [4, 4, 5]]

Basic BFS: ( approach-1)

If there are N elements in the matrix, one could do BFS starting every house to solve this. The worst case complexity of this approach is: Worst number of BFSes * O(E+V), where E is the number of edges in the matrix and V number of nodes = N * O(N + 4N) as number of edges is a constant factor of 4N.
Time complexity: O(N*N)

multi-source BFS (approach-2)

Initialize the queue with all nodes (i, j) where i is the row number and j is the column for all stores. For each node (i, j) in the queue also store its corresponding (si, sj) node for the store that gives it the minimum square of euclidean distance (call it sqDist). For each store node (i, j), (si, sj) would be same as (i, j)
Initialize the distance answer that we are looking for each house with -1
During multi-source BFS, for a node (i, j) and it's best store (si, sj) in the queue, look at each of 8 adjacent nodes (since it's euclidean distance, we need to consider all 8 nodes not only 4 of left, right, top, down). If the current distance value for any of those nodes (nexti, nextj) is > the sqDist if (si, sj) is chosen as the best store for (nexti, nextj), then

update distance of (nexti, nextj) with the lower value
add (nexti,nextj) along with its best store as (si, sj) to the queue

Keep doing this until queue is empty

My question:

1) why does this work? Since we're looking at euclidean distance it's possible that (nexti, nextj) may not be added to the queue (or have their distance updated) for a certain (si, sj) but that (si, sj) node may still update the distance for nodes that are farther to it than (nexti, nextj) due to nature of euclidean distance. So (si, sj) may still need to be in the queue. How does this solution work inspite of this issue or what's the intuitive conceptual idea of why this works despite this issue as it's not obvious?

2) What's the time complexity?

it seems in the worst case you could add a node in the queue N times. So it becomes N * O(N *4N) where 4N is the number of edges in the matrix.
So is it not any better than doing BFS individually for each house?


texts: Was it known that $\mathsf{LTIME \subsetneq NLTIME}$?

texts:
$\mathsf{LTIME = DTIME(\log n), NLTIME = NTIME(\log n)}$.

For example, it seems that NTM can find an element in unsorted array in log-time by use of non-deterministic binary search (check if first half leads to solution and if second half leads to solution).

Obviously, it can't be done by log-time deterministically. I couldn't find anything about this despite the fact this is so simple.

So, was it known and does it imply any consequences? (DFA vs NFA, for example).

I also believe it doesn't imply $\mathsf{P \subsetneq NP}$ because $\mathsf{LTIME}$ is smaller class than $\mathsf{P}$ and inequality between bigger classes is stronger statement (maybe it's some kind of any hierarchy rule). Or does it?


texts:
I faced some problem that involves arithmetic over asymptotic functions. These are as follows:

  Let f(n)= Ω(n), g(n)= O(n) and h(n)= Ѳ(n). Then [f(n). g(n)] + h(n) is:

  (a) $Ω(n)$
  (b) $O(n)$
  (c) $\Theta(n)$
  (d) None of these

Solution to this was discussed as follows:

Let

$n = 5$
$f = 6$ so that $f = Ω(n)$ and
$g = -6$ so that $g = O(n)$ and
$h = 5$ so that $h = Ѳ(n)$
$f.g + h = -36 + 5 = -31 < n → f.g + h = O(n)$

Now let,

$g = 4$ so that $g = O(n)$ and
$f.g + h = 24 + 5 = 29 > n → f.g + h = Ω(n)$

Hence option 4 is correct, None of these.

Then I came across another problem

  Let $f(n)=Θ(n),g(n)=Θ(n)$ and $h(n)=Ω(n)$. Then $h(n)+f(n)g(n)= ?$

  (a) $Ω(n)$
  (b) $Ω(n^2)$
  (c) $Θ(n)$
  (d) $Θ(n^2)$

This problem was solved in completely different approach:

Using the definitions of notations:

$f(n)= θ(n)→ c_1.n<=f(n)<=c_2.n$        ... for $n>n_0$

$g(n)= θ(n)→ c_3.n<=g(n)<=c_4.n$        ... for $n>n_0$

$h(n)= Ω(n)→ h(n)>=c_5.n$        ... for $n>n_0$

Using the extended notations forms:

$c_1.c_3.n^2<=f(n)g(n)<=c_2.c_4.n^2$        ... for $n>n_0$

Taking $c_1,c_3=k_1$ and $c_2.c_4=k_3$

$k_1.n^2<=f(n)g(n)<=k_2.n^2$

Adding h(n)

$k_1.n^2+c_5.n<=h(n)+f(n).g(n)<=k_2.n^2$        ... for $n>n_0$

As $n^2>n$ for all $

$k_3.n^2<=h(n)+f(n).g(n)<=k_2.n^2$

Which simplifies to :

$f(n).g(n) + h(n) =Ω(n^2)$

Though I am able to appreciate both approaches, this leaves me a lot of confusion. I am not able to confidently apply these methods to each other, nor to other similar problems and reach the correct solution. Are these methods correct? In fact are these questions themselves correct? Is there more straightforward approach to solve such kind of problems?


texts: Benes (Fat Tree) Network for number of inputs/outputs that is not 2^n

texts:
I was reading about Benes Network construction in this book.
Their construction is easy for a number of inputs and outputs that is an exponent of two.

However it seems to me that for a number of i/o that falls between $2^{n}$ and $2^{(n+1)}$ one has to construct a network with $2^{(n+1)}$ ports and leave many unattached, which is wasteful.
Is there a synthesis method for Benes networks or maybe an alternative topology that has the same properties (re-arrangeable not blocking) for arbitrary number of I/O?


texts: Terminology for describing a kind of server

texts: What is the adjective used to describe the fact that a server keep track of queries made by a user. I take the example of a database server.


texts: Generating uniformly distributed random numbers using a coin

texts:
You have one coin. You may flip it as many times as you want.

You want to generate a random number $r$ such that $a \leq r < b$ where $r,a,b\in \mathbb{Z}^+$.

Distribution of the numbers should be uniform.

It is easy if $b -a = 2^n$:

r = a + binary2dec(flip n times write 0 for heads and 1 for tails)

What if $b-a \neq 2^n$?


texts:
For UCT (Upper Confidence bounds applied to Trees), why If given infinite time and memory, UCT theoretically converges to Minimax. ?

Besides, I do not quite understand how UCT deals with the flaw of Monte-Carlo Tree Search, when a program may favor a losing move with only one or a few forced refutations, but due to the vast majority of other moves provides a better random playout score than other, better moves.


texts: Interpretation of Turing's statement on universal computers

texts:
I'm currently reading a book about artificial intelligence and i frequently come across the concept of universal computers, as it is essential to understand the book i would like to know the meaning of author's statement referring to Turning's paper of 1936:

  If a type of computer can perform a certain bare minimum set of operations, then it's  universal in the sense that given enough resources, it can do anything that any other computer can do.

Maybe the above statement is on its own very clear, but i have difficulties to understand. I'm afraid i interpret the concept in a wrong way.

Consider a simple calculator we were using in school, how can we provide it with enough resources so it can do anything that any graphical calculator nowadays can do? We if add components to the existing computer then it wouldn't be the same computer as it used to be. So my conclusion is the term enough resources doesn't mean any physical alterations.


texts: Positioning items to maximize separation

texts:
Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \le r_i$. My problem is: given a specific item s, how do I compute the maximum gap possible to the right of s? By maximum gap to the right of s I mean the distance between s and the next item to its right.

Mathematical Description:

More formally, given $s \in [n]$, and $(l_i,r_i)$ for $i\in[n]$ I want to find
 $$f(s) = \max_{p_1,\dots,p_n} p_t - p_s$$ subject to
\begin{align*}
1)\,& l_i \le p_i \le r_i\, \forall\,i \in [n] \\
2)\,& \forall\,i\ne s,t, \text{ either } p_i \le p_s \text{ or }p_i \ge p_t \text{ (there is no item between s and t)}
\end{align*}

In the absence of the second constraint the problem would have been a linear program. The second constraint makes it difficult.

I know how to model this question as an integer program (see https://bit.ly/2Jhf7kJ), but I am interested in an actual algorithm.


texts: Hardness of approximating 0-1 integer programs

texts:
Given a $0,1$ (binary) integer program of the form:

$$
\begin{array}{lll}
\text{min} & f(x) & \\
\text{s.t.} & A x = b \\
 & x_i \ge 0 & \quad \forall i\\
 & x_i \in \{0,1\} & \quad \forall i
\end{array}
$$

Note that the size of $A$ is not fixed in either dimension.

I believe this problem has been shown to be hard to approximate (strongly ${\sf NP}$-Complete) by Garey & Johnson. If so, is this still the case when $A, b$ have binary entries and $f(x)$ is a linear function ( $f(x) = \sum_i c_i x_i$ )?


texts: Problem with manipulation of colored graph

texts:
Consider a finite set of colors and a given an unweighted graph with the following properties:

1) Graph is connected.

2) All vertices of the graph has a color in the given set of colors.

3) No two adjacent vertices have the same color.

Define a flip as the following: change the color of a given vertex V AND all reachable vertices from V only if those reachable vertices have the same original color with V (that is, all vertices that have a path to V consisting of only vertices of the same colors have their color changed).

What's the optimal strategy to find the smallest amount of flip in order so that all vertices have the same color?

For example the following graph needs 2 flips:

R
| \
B  B
|  |
Y  Y

First flip is from vertex red to color blue:

B
| \
B  B
|  |
Y  Y

Then flip the top blue vertex and change it to yellow, triggering all the other blue vertices to yellow:

Y
| \
Y  Y
|  |
Y  Y

I was thinking of exploring all possibilities by try flipping all vertices, but this seems to be inefficient as I might have to explore all the flipping possibilities before finding the optimal one.


texts: Calculating the number of operations in an algorithm

texts:
I just started working on algorithms and am having some trouble understanding how you can correctly analyze the number of operations of computations that are done.
According to the paper I am reading, the following two steps take 3 multiplications and 2 exponentiations.
$$m' = m \cdot \frac{P}{p_k} \cdot (P^{-1}\mod p) \mod n^2$$
$$\mathcal{E}(m')=g^{m'} \cdot r^n \cdot h^{n-a}\mod n^2$$
I am not really sure if I am understanding this incorrectly, but I would suspect that, since you see at least 3 exponents, these operations must take at least 3 exponentiations? That same for the multiplication signs, I see at least 4, so how can this be reduced to 3?


texts: Language that system calls are implemented in

texts:
Lately, I have been reading about operating systems design.  The idea that all user space programs utilize Kernel services via a "System Call Interface" have got me thinking further into this.

Is system call implemented in specific language like C/C++ on each operating system or it is some sort of assembly language or machine code?


texts: applying CTL/LTL model-checking on some system

texts:
I apologies if my title is vague, I'm trying to apply CTL/LTL model-checking on some system written in java, however, I still don't understand how to reach a result using either of the approaches mentioned. Do I model my LTS/write specification and use a tool like SPIN to validate that or? I'm mainly looking for a point at a direction that will help me in making a start.

Again sorry but I made this thread after so much frustration searching for an explanation to my problem.

Thank you


texts: what will be space complexity for snippet for(i=1 to n) int x=10;?

texts:
The space complexity of the code snippet given below:
int *a = malloc(n * sizeof(int));
int sum=0;
for (i = 0; i < n; i++)
{
    scanf("%d", &a[i]);
    for (j = 0; j < n; j++)
    {
        int x = a[i];
        sum = sum + x;
    }
}
free(a);

This is question of a test.
I answered it $O(n)$, considering space only for array and constant space for rest of the code.
But in the answer they given $O(n^2)$ and there explanation is "The array is of size $n$ and the inner most loop we are declaring a variable $x$ every time the loop is executed, this loop is executed $O(n^2)$ time hence overall space complexity is $O(n^2)$."
Now my doubt is what should be space complexity of
for (i = 1; i <= n; i++)
    int x = 10;

What i thought is that it should be $O(1)$ because in each iteration variable $x$ gets destroyed.


texts: if P=NP then $L\leq L'$ for all languages

texts: How can I prove that if P=NP then for each non-trivial language $L,L'\in NP$ there exists a polynomial reduction $L\leq L'$?


texts: How extended logical blocks are mapped to physical device pages?

texts:
I'm reading "Decibel: Isolation and Sharing in Disaggregated Rack-Scale Storage" (PDF). On page 6, the author illustrates the concept of "Extended Logical Block"), which is similar to "Data Integrity Field" provided by SCSI devices.

I directly quote the text here:

  Several enterprise SCMs support storing per-block metadata alongside
  data blocks and updating the metadata atomically with writes to the
  data. The block and metadata regions together are called extended
  logical blocks (shown in Figure 5). Block metadata corresponds to the
  Data Integrity Field (DIF) provided by SCSI devices and is intended
  for use by the storage system. Decibel utilizes this region to store a
  CRC32-checksum of every block.

  Block checksums are self-referential integrity checks that protect
  against data corruption, but offer no guarantees about metadata
  integrity, as V2P entries pointing to stale or incorrect data blocks
  are not detected. Metadata integrity can be ensured either by storing
  checksums with the metadata or by storing back-pointers alongside the
  data. To avoid updating the mappings on every write, Decibel stores
  back-pointers in the metadata region of a block. As the data,
  checksum, and backpointer are updated atomically, Decibel overwrites
  blocks in-place and still remains crash consistent.

How is that possible? I mean most flash devices provide 4KB atomic write. Is that metadata field belong to next block?(if yes, how it is atomic?) Is that kind of additional storage provided by device just for metadata (which is atomically updated alongside with data block)? Is it excluded from total device size?


texts: Motivation behind the definition of order-$k$ (edge) expansion?

texts:
I'm trying to understand the motivation behind the idea of order-$k$ (edge) expansion for partitions of a graph, defined below:

For simplicity, let's focus on $d$-regular graphs. The definitions I'm working with are:

The edge expansion of a subset of vertices $S$ is $$\phi(S) = \frac{E(S,V \setminus S)}{d \cdot |S|},$$ where $E(A,B)$ counts the number of edges with one endpoint in $A$ and the other in $B$.

Let $S_1, \ldots, S_k$ collection of disjoint vertices, then their order-$k$ expansion is $$\phi_k(S_1, \ldots, S_k) = \max_{i=1,\ldots, k} \phi(S_i).$$ The order-$k$ expansion of a graph $G$ is $$\phi_k(G) = \min_{S_1, \ldots, S_k \text{ disjoint} } \phi(S_1, \ldots, S_k).$$

My question is: why do we consider the $\max$ in the definition of $\phi_k(S_1, \ldots, S_k)$? If $S_j$ is the subset of vertices for which $\phi(S_i)$ is a maximum, this means there are "a lot" of edges from $S_j$ to $V \setminus S_j$, relative to $d|S_j|$. Isn't the $\min$ more interesting here? Doesn't the $\min$ correspond to $S_k$ that can easily be removed from the graph (few edges need to be cut), and yet the subgraph being removed is relatively dense?


texts: Show that SQUARED-SUM-PARTITION is NP-complete

texts:
Consider the following problem SQUARED-SUM-PARTITION. You are given positive integers $x_1, \dots, x_n$,
and numbers $k$ and $B$. You want to know whether it is possible to partition the numbers $\{ x_i \}$ into $k$ sets $S_1, \dots, S_k$ so that the squared sums of the sets add up to at most $B$:
$$ \sum_{i=1}^k \left( \sum_{x_j \in S_i} x_j \right)^2 \leq B $$
Show that this problem is NP-complete.

My solution:

We know that the PARTITION problem (Partition a set of numbers into two sets with equal sum) is NP-complete. Let $S = \{ x_1, \dots, x_n \}$ be an instance of PARTITION. Let $T$ be the sum of all elements in $S$. Then we construct instance of SQUARED-SUM-PARTITION by setting $B = (T/2)^2$ and $k=2$ and $S$ remains the same. Then there is a solution for this instance of SQUARED-SUM-PARTITION if and only if there is a solution for PARTITION.

Can I check if this solution is correct? Does anyone have other interesting ways to solve this?


texts: find function which is in o(log^k(n)) for fixed value of k and in ω(1)

texts: I need to find a function $f$ which is in $o(\log^{k} n)$ for fixed value of $k$ with $f = \omega(1)$. I know that for little $o$ the function should be strictly less than $c\log^k n$ for all $c$ and large enough $n$; and for little $\omega$ it should be strictly greater than $c\cdot 1$ for all $c$ and large enough $n$, but I am stuck here. How does one usually solve such type of problems?


texts: Find a linear bounded automaton that accepts the language $L = \{ a^{n!} : n \geq 0 \}$

texts: I need to construct linear bounded automaton for the language $L = \{ a^{n!} : n \geq 0 \}$. I know how LBA functions, however, I don't have a thought how it can check the n! that to in the power of a. I might want to hear a few suggestions, as I am experiencing difficulty in developing the specific LBA for it.


texts: Longest path among subset of given points

texts:
I am looking for an efficient algorithm to solve the following problem:

Given $n$ points in 2D Cartesian space $p_1,\dots,p_n \in \mathbb{R}^2$ and an integer $m$, we want to find $s_1,\dots,s_m$ such that $1 \le s_1 < s_2 < \cdots < s_m \le n$ and that maximizes

$$\sum_{i=1}^{m} \|p_{s_i} - p_{s_{i+1}}\|_2,$$

where $\|p-q\|_2$ represents the $L_2$ distance between two points.  In other words, we want to find a subsequence of the points $p_1,\dots,p_n$ such that the distance of following that path is maximized.

Is there an efficient algorithm for this problem?

In my application $m$ is at least 3 orders of magnitude smaller than $n$ and neighboring points $p_i,p_{i+1}$ are close to each other, which makes the search space structured.  I have tried simulated annealing with and without an adaptive neighbourhood and get decent results, but I want to know if there is a optimal algorithm.  Does anyone know other algorithms and ideally their complexity?


texts: Connection between convergence complexity of gradient descent and complexity of exactly solving convex program?

texts:
Let $f: \mathbb{R}^n \to \mathbb{R}$ be a convex function. Let $V \subseteq \mathbb{R}$ be some closed convex set. Consider the following convex minimization problem:
\begin{align}
\min_{\mathbf{x} \in V} f(\mathbf{x}) \label{minconv}\tag{1}
\end{align}
Let $\mathbf{x}^*$ be the minimizer of $f$, i.e., $\mathbf{x}^* = \min_{\mathbf x \in V} f(\mathbf{x})$.
Let $\varphi:  \mathbb{R}^n \to \mathbb{R}^n$ be any discrete dynamical map. For any initial $\mathbf{x}_0 \in \mathbb{R}^n$, define the sequence $\{\mathbf{x}_i\}_{i=1}^{\infty} = \{\varphi(\mathbf{x}_{i-1})\}_{i=1}^{\infty}$.
Assume that the following convergence bound holds:
\begin{align}
f(\mathbf{x}_t) - f(\mathbf{x}^*) \leq g(t)
\end{align}
where $g(t)$ is a decreasing function in $t$.
Is there a relationship between the complexity of solving the convex minimization problem $(\ref{minconv})$ and the convergence bound $g(t)$?
My question stems from a lack of understanding of the connection between the complexity of  solving a convex program exactly and solving a convex program using iterative methods. Are there convex programs that we can solve approximately fast via iterative methods (with theoretical guarantees, i.e., linear or sublinear convergence bounds) that we cannot solve in polynomial time exactly? In particular, what is the relationship between the convergence rate of (generalized) projected gradient descent on a convex program and the exact complexity of solving the same convex program.


texts:
This question follows on previous questions (1), (2), where we define an initial space of possibilities and reason about how a solution is chosen from that.

Consider a problem P where we are given:

the initial space of possibilities is exponential in the size of the input,
the search space decreases monotonically as we read the input,
for the algorithm that correctly computes P and has the minimum worst-case performance, the search space is still exponential in the size of the input even after the final input is read.

Can we conclude that P requires exponential time? If not, what would a polynomial-time counterexample look like?


texts: Constant-depth threshold circuit for $\mathrm{PP}$

texts: Is it proven that $\mathrm{PP}$ has uniform constant-depth threshold circuit?


texts: How does negation as failure work with variables?

texts:
Let's say we have the following rule:

p -: X ≠ Y, X = Y

Stating that $\forall x.y. x \neq y \land x = y \implies p$. Now let us suppose that we are searching for a proof of $p$. Such a proof does not exist, of course, but we will search for it.

Our starting goal is p. We replace it with the subgoals X ≠ Y and X = Y. To resolve X ≠ Y, we use negation as failure. We must show that exists an $x$ and $y$ such that $x = y$ is unprovable. So we know have a goal of X = Y. Since $x$ and $y$ are not the same variable (remember, $x$ and $y$ were bound by the quantifier of the top level rule), there is no way to resolve $x = y$. So we fail to show $x = y$, and the subgoal X ≠ Y is resolved. We now resolve the subgoal X = Y. This is done by unification, which means we set Y := X. Since all subgoals have been resolved, the original goal p has succeeded, with the solution X := X and Y := X.

However, this is obviously incorrect since $p$ should not be provable. $x \neq y \land x = y$ is always false, so we can not use the rule to deduce it.

The problem seems to be that negation as failure is not actually negation. Being unable to show that $x \neq y$ does not mean it is false. Resolving something like I did above "loses" consequences of negated statements.

What is the correct way to resolve rules like the above?


texts: What does a ball of center v and radius r with at most r hops away mean?

texts:
I am trying to understand what that sentence means. Intuitively, its obvious a radius ball means in a $ \mathbb{R}^{n}$ with respect to some norm. Its just the following set:

$$ B(v, r) = \{ x \in \mathbb{R}^n : \| v - x\| \leq r\}$$

i.e. its just all the points that are distance $ \| v - x\|^2 $ away from the center with respect to some norm $ \| \cdot\|$. However, in graph theory, if we have a graph $G = (V,E)$ I seem to have a much harder time to rigorously understand what this set means. Can someone help me define this set rigorously so that there is no doubt in my mind what it means to have a radius ball with at most radius $r$ in a fixed known graph $G = (V,E)$? In particular this is the sentence I am having a hard time understanding rigorously:

  a ball with center v and radius r is the set of vertices at most r
  hops away from v

For example, if I have a path from v1 to v2 to v3, then it has 3 hops. But if v1 also has v4 as a neighbor and we want a ball radius 3, does it mean that v4 should also be part of the set of radius 3 with center v1?

In fact, is the radius ball defined as follow:

$$ B(v,r) = \{ x \in V : \exists path(v,x) s.t.| path(v,x)| \leq r \}$$

or maybe it should be defined with shortest paths $\delta(v, \cdot)$:

$$ B(v,r) = \{ x \in V : \delta(v,x) \leq r \}$$

i.e. if you can get to a node from v in less that $r$ hops then its part of the radius ball on the graph.

In particular, consider the example. If we have a bounded degree say $d$ and the graph is undirected, if we have the radius be some finite number, do we necessarily have to include everyone's neighbor i.e. consider all the nodes in the degree?


texts: state of the art of subset, set containment and partial match queries

texts:
The subset query problem is defined as:
Given a list D of size N where the entries are subsets of a universe with m elements, create a datastructure that detects for every query-set Q if there exists a set P in D so that Qis a subset of P

I was wondering what are the best known algorithms to solve this problem. I couldn't find any recent publications, just this work from 2002:
Subset Queries

There it is stated, that the subset query problem is equivalent to the set containment problem as well as the partial match problem.

Any help would be appreciated.


texts: Why can't we use a hash tables for collision resolving in hash tables?

texts: To prevent collisions, hash tables with open addressing use a methodology to chain the contents. Why can't we use another hash table allocated to each slot of the primary hash table?


texts: Finding a maximal set of nonintersecting line segments in a unit circle

texts:
Let P be a set of n points that divides the unit circle into equal pieces. Let S be a set of m line segments such that their end points are points in P. The points aren't unique per line, meaning several lines can share points.
I need to find the biggest subset of S of non intersecting lines. Lines that share an end point are treated as intersecting.

In the great piece of art above, n = 3 and m = 2, connecting all dots will form an equilateral triangle, and the two lines are intersecting.

What I tried doing is to apply dynamic programming, but I can't formulate a recursive relation. I tried enumerating the point P = {1,2,...,n} and claiming something like "Let C[k] be the largest subset using only point from 1 to k etc..." but couldn't relate it to k - 1, plus I didn't take advantage of the fact the the points divide the circle into equal pieces.

Any clues\help will be vastly appreciated. :)


texts:
Are the definitions of loop in CS and in programming (standard/common) identical?
If not, what is the main difference / what are the main differences?


texts:
I can't think of any definition for half-space that would involve some sort of quantity not being homogenous.
This term is used in the paper Robust Concepts and Random Projection in the following paragraphs:

The next problem we consider is learning an intersection of t half-spaces in Rn, i.e., the positive examples all lie in the intersection of t half-spaces and the negative examples lie outside that region. It is not known how to solve the problem for an arbitrary distribution. However efficient algorithms have been developed for reasonably general distributions assuming that the number of half-spaces is relatively small [8, 44]. Here, we derive efficient learning algorithms for robust concepts in this class.
We assume that all the half-spaces are homogenous. Let the concept class of intersections of half-spaces be denoted by H(t,n). A single concept in this class is specified by a set of t half-spaces P = {h1, . . . , ht}, and the positive examples are precisely those that satisfy hi · x ≥ 0 for i = 1 . . . t. Let (P, D) be a concept-distribution pair such that P is -robust with respect to the distribution D. We assume that the support D is a subset of the unit sphere (and remind the reader that this as well as homogeneity are not really restrictive, as they can be achieved by scaling and adding an extra dimension, respectively; see e.g. [44]).

It's not clear to me from context, not defined in the paper and I haven't been able to find a clear definition from searching for it.


texts:
I'm having difficulty understanding the big-O analysis of the selection sort algorithm. Here is my pseudocode (with line numbers):

    procedure SELECTION (A(n), limit)
1.  for j <- 0 to limit - 1 do
2.      min_index <- j
3.      for k <- j + 1 to limit do
4.          if A(k) < A(min_index)
5.              min_index <- k
6.          end-if
7.      end-for
8.      temp <- A(min_index)
9.      A(min_index) <- A(j)
10.     A(j) <- temp
    end-for
end-SELECTION

Our professor wants us to work from the inside out; in other words, analyze the statements the furthest away from the conceptual vertical line that denotes hierarchies. Therefore, I start at line 5, and work out from there. Here's what I've understood so far:

The time complexity of lines 4-6 is O(1) (constant).
Because lines 4-6 are "contained" in the for loop on line 3, you must use the rule of sums to multiply line 3 and lines 4-6. In other words, if line 3 is a program fragment f(x) and lines 4-6 are a program fragment g(x), then the time complexity of lines 3 - 6 is f(x) * g(x).

This is where I get confused. Because var limit is referencing the size of the array, wouldn't the for loop on line 3 run limit-1 times, because k is equal to 1 and is running to limit? To put it another way, if k were equal to zero, wouldn't the loop run limit times? Every video and website I've looked at has not given me a clear representation of that expression, because they've analyzed it differently.

On top of this question, how do I determine which asymptotic notation to use to describe this problem? Is it Big-Oh, Big-Omega or Big-Theta?

Thank you.


texts: Semantic readings of the Lambek sequent calculus

texts:
I am reading Categorial Grammar: Logical Syntax, Semantics, and Processing by Glyn Morrill and I am stuck with the Fig. 3.9:

Can someone explain this set of formulas and |.| function specifically?

This figure displays the definition of the |.| function that maps some proof (of some formula) in Lambek calculus (as fragement of intuitionistic logic) into lambda-term (by Curry-Howard correspondence there is correspondence between proof in some logic and terms in lambda calculus). I understand Lambek calculus and lambda calculus but I can not understand this picture? It is said in this book, tht |.| function is applied to proof, but this picture say something different - this function is applied to proof rules, that is completely different structure. What does small indices mu(ni, psi) and so on mean?

This was very good book up to this chapter, I am completely lost.


texts: Why did Hopcroft and Karp write $M_0, M_1, M_2, \cdots, M_i, \cdots$? (Hopcroft - Karp Algorithm)

texts:
I am reading “An $n^{\frac{5}{2}}$ Algorithm for Maximum Matchings in Bipartite Graphs” by Hopcroft and Karp.
Please see the image below.
Let $s$ be the cardinality of a maximum matching.
I think any of $M_0, M_1, M_2, \cdots, M_s$ is a matching and $M_s$ is a maximum matching.
So, I think $P_s$ doesn't exist.
But the authors wrote $M_0, M_1, M_2, \cdots, M_i, \cdots$ and $|P_0|, |P_1|, \cdots, |P_i|, \cdots$.
Why?
Maybe I am confused.


texts: Finding a lower bound for the expression $\log(n!)$

texts:
Problem:
Is $\log(n!) \in$ $\Omega( n^n )$?
Answer:
Since $n! > n^n$ for all $n > 1$ we can conclude that: $\log(n!) \in$ $O( n^n )$.
Let us look at the special case where $n = 4$.
\begin{align*}
n! &= 4(3)(2) = 24 \\
n^n &= 4^4 = 256
\end{align*}
Let us look at the special case where $n = 5$.
\begin{align*}
n! &= 5(4)(3)(2) = 5(24) = 120 \\
n^n &= 5^5 = 3125
\end{align*}
Let us look at the special case where $n = 8$.
\begin{align*}
n! &= 8! = 40320 \\
n^n &= 8^8 = 16777216
\end{align*}
It looks to me that $n^n$ is growing faster but that is not a proof. To prove it, I need to
show that there exists an $M > 0$ and $n_o > 0$ such that the following statement is true for
all $n \geq n_0$:
$$ n! \leq M n^n $$
I select $n_0 = 4$ and $M = 1$. Hence the expression reduces to:
$$ n! \leq n^n $$
We have already shown that this expression is true for the special case of $n = 4$. Now, if we
add $1$ to $n$ we have:
$$ (n+1)! \leq (n+1)^{(n+1)} $$
This must be true because the left hand side increased by a factor
of $n+1$ and the right hand side increased by more than a factor of $n+1$. Now we add $1$ to $n$
again. The left hand side increases by a factor of $n+2$ and the right hand side increases by more
than a factor of $n+2$. Hence the right side increases more. We can repeat this process for ever. Therefore, I conclude the statement is true.
Do I have this right?


texts: PTAS for Multiple Knapsack with Uniform Capacities, fixed number of Knapsacks

texts:
Consider the following problem:

We are given a collection of $n$ items $I = \{1,...n\}$, each item has a size $0 < s_i \le 1 $ and a profit $ p_i > 0 $. There are $m$ (a fixed number) of unit-size knapsacks. A feasible solution is an $m$-tuple $U=\{U_1,...,U_m\}$, such that the size of items in each knapsack doesn't exceed its capacity, and each item is packed in no more than one knapsack. more formally:

for every $j, 1 \le j \le m, U_j \subseteq I$ and $ \sum_{i \in U_j}s_i \le 1$
for every $j,l,  1 \le j < l \le m,  U_j \cap U_l = \phi $

the profit of the feasible solution is $ \sum_{j=1}^m\sum_{i \in U_j}p_i $. The goal is to find a feasible solution of maximal profit.

I'm trying to show a PTAS for the problem.

It was suggested to use linear programming. I thought about the following (basic) linear program:

maximise  $ \sum_{j=1}^m\sum_{i=1}^n x_{ij}p_i $

under the constraints:

for every $ 1 \le j \le m \sum_{i=1}^n s_ix_{ij} \le 1  $ (the size of items in each knapsack doesn't exceed its capacity)
for every $ 1 \le j \le n \sum_{j=1}^m x_{ij} \le 1  $ (each item is packed in no more than one knapsack).

I don't know how to proceed from here. I'm not sure how to develop an algorithm (choose in which knapsack to put each item) based on this linear program. Can anyone pls give me a clue?

Thanks.


texts: Running Time Analysis of a Simple Binary Search Algorithm

texts:
I'm stuck with the following problem by Skiena (The Algorithm Design Manual, p. 106):

  Problem: Give an efficient algorithm to determine whether two sets (of
  size $m$ and $n$, respectively) are disjoint. Analyze the worst-case
  complexity in terms of $m$ and $n$, considering the case where $m$ is
  substantially smaller than $n$.

  Solution: First sort the big set – The big set can be sorted in
  $O(n\log n)$ time. We can now do a binary search with each of the m
  elements in the second, looking to see if it exists in the big set.
  The total time will be $O((n + m)\log n)$.

My question: Why is the running time $O((n + m)\log n)$? I would have to perform m binary searches in total (one binary search for every element in $m$) - as one binary search has a running time of $O(\log n)$, I would have to perform $m \cdot \log n$ operations in the worst case. How does this - if at all - translate into $O((n + m)\log n)$?


texts: How/when is calculus used in Computer Science?

texts:
Many computer science programs require two or three calculus classes.

I'm wondering, how and when is calculus used in computer science? The CS content of a degree in computer science tends to focus on algorithms, operating systems, data structures, artificial intelligence, software engineering, etc. Are there times when Calculus is useful in these or other areas of Computer Science?


texts: How the states are chosen in this Tree Automaton Example

texts:
I have a few basic questions about how the states work in Tree Automata.

  Example 1.1.2. Let $F = \{f(,),g(),a\}$. Consider the automaton $A = (Q, F, Q_f, \Delta)$
  defined by: $Q = \{q,q_g,q_f\}$, $Q_f = \{q_f\}$, and $\Delta =$

  \begin{align}
a &\to q(a)\\
g(q(x)) &\to q(g(x))\\
g(q(x)) &\to q_g(g(x))\\
g(q_g(x)) &\to q_f(g(x))\\
f(q(x),q(y)) &\to q(f(x,y))
\end{align}

Another similar example is this:

  \begin{align}
a &\to q(a)\\
g(q_a(x)) &\to q_g(g(x))\\
g(q_g(x)) &\to q_g(g(x))\\
f(q_g(x),q_g(y)) &\to q_f (f(x,y))
\end{align}

The questions I have are:

How the states were chosen. Wondering how you are supposed to decide how many to pick.
I noticed $g(q_g(x)) \to q_g(g(x))$ moves outward and stays with $q_g$. Wondering if you are allowed to move "backwards" with states, or between states arbitrarily at different nesting levels. Sometimes the state $q$ moves outwards, other times it moves inward.
If the rules are applied (or defined) in any particular order.


texts: Example using Penetrance & Branching Factor in State-space Heuristic Search

texts:
I need an example for how to calculate penetrance and branching factor of the search tree in in state-space heuristic search. The definitions are as following. Penetrance $P$ is defined by

$\qquad \displaystyle P = \frac{L}{T}$

and branching factor $B$ is defined by

$\qquad \displaystyle \frac{B}{(B-1)} \cdot (B^L – 1) = T$

where $L$ is the length of the path from the root to the solution and $T$ the total number of nodes expanded.


texts:
Cutting problems are problems where a certain large object should be cut to several small objects. For example, imagine you have a factory that works with large sheets of raw glass, of width $W$ and length $L$. There are several buyers, each of which wants an unbounded number of small glass sheets. Buyer $i$ wants sheets of length $l_i$ and width $w_i$. Your goal is to cut small sheets from the large one, such that the total used is maximized and the waste is minimized (there are also other types of cutting and packing problems).

One common restriction in cutting problems is that the cuts must be guillotine cuts, i.e., each existing rectangle can be cut only to two smaller rectangles; it is impossible to make L-shapes etc. Obviously, the maximum used area with guillotine cuts might be smaller than the maximum used area without restriction.

My question is: Are there upper and lower bounds on the ratio between the optimal guillotine cut and the optimal general cut?

Related work: Song et al. (2009) describe an algorithm that uses a restricted type of guillotine cuts – twice-guillotine cuts. They prove, using geometric constraints, that the ratio between the maximum twice-guillotine cut to the maximum guillotine cut is bounded by $\frac{6}{7}$. I am looking for a comparable result about the ratio between the maximum guillotine cut to the maximum general cut.


texts: How to partition a set into disjoints subsets each of given size?

texts:
The input: Given a set $U=\{1, \ldots, k\}$ called the universe. Let $C=\{S_1, \ldots, S_n\}$ be a collection of subsets of $U$ and let $ s_j$ be a nonnegative integer for all $j=1,\ldots,n$ such that $\sum_{j=1}^{n} s_j=k$.

The question: Are there $n$ subsets $A_j$ of $S_j$ (i.e., $A_j\subset S_j$) such that

$$
\quad\bigcup\limits_{j=1}^{n}A_j=U,\\
\quad \quad\;\;\;\,\;\;\,A_j \cap A_i = \emptyset, i\neq j,\\
|A_j|=s_j.
$$

Is this problem NP-hard?

I was trying to reduce PARTITION to this problem by setting $n=2$ and $k$ an even number and $s_j=k/2$ but the constraints $|A_j|=k/2$ do not help me.


texts: Running time of Goldberg's densest subgraph algorithm for integer edge weighted graphs

texts:
The running time of the original non-weighted algorithm is  $\mathcal{O}(M(n, n + m)\,log(n))$,
where $M(n, m)$ is the execution time for finding a min-cut in a network with $n$ nodes and $m$ edges and $log(n)$ is the number of times the while loop must be executed.
The changes he makes to the original solution are:

the capacities of the edges are set equal to the weights of the corresponding edges,
the degree of each node is now equal to the sum of the weights of the edges incident on the node,
and the upper bound for highest density u starts from W (the sum of all weights of the graph)

Meanwhile the smallest distance between two values of the solution remains $$\frac{1}{n(n-1)}.$$
My question is, the only thing that changes, from an asymptotic perspective on the running times, is the number of times the while loop is executed, right?
I mean, if before it was upper bounded by $log(n)$ now it's upper bounded by $log(W)$, everything else look the same to me.
So it is fair to say that the running time for the integer edge weighted case is
$\mathcal{O}(M(n, n + m)\,log(W))$ ?


texts: Characterization of P in the context of probabilistically checkable proofs

texts:
The PCP theorem characterizes NP as the class of problems checkable probabilistically using log(n) bits and a constant number of random bits and yields $NP=PCP(O(log(n)),O(1))$ .

Is there a pair $(f,g)$ of functions such that $P=PCP(O(f(n)),O(g(n))$ where $g(n) \ne 0$?  Or is there any research in that direction or an obvious reason why this is a naive approach?


texts: Turing Machine That Accepts Machines With Undecidable Languages

texts:
So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) is undecidable }. (in words, a Turing machine that accepts encodings of machines that accept undecidable languages.)

I'm trying to reduce the accepting Turing machine (A TM) to Undecidable TM in the following manner:

Take Turing machine M and string x as inputs.
Create M' that works as follows: For input y, M' simulates M on x. If M accepts x, then M' acts on y as some Turing machine that accepts an undecidable language. Else, M rejects y.
Pass M' to Undecidable TM. Iff Undecidable TM accepts M', then M must accept x, else M' does not accept an undecidable language.
Thus, we can decide whether a machine M accepts input x.

The problem is that I cannot create a machine that accepts an undecidable language to put inside M' for this reduction. I have read my lecture notes and looked for advice on Google, but haven't made any headway. I'd appreciate it if someone has some insight on how to finish this proof or approach this another way. Thanks a lot.


texts: Some nodes in binary search had broken.how we can fix it in-place by swapping nodes?

texts:
Given a binary search tree(can have any height) .Some nodes its value
changed and violate bst property  how we can recover binary search
tree property in-place by just swapping a node with its children's.

I think it can be done in $O(n^2)$ because a bst has height at most $n$ and start from parent of leaves and if two nodes violate bst property we can swap it by parent,but i want give a formal prove,anyone have any suggestion?


texts: Is there a difference between total-ordering consistency and linearizability?

texts:
By total-ordering I mean the following definition[0]:

  Total Event Ordering: Controller replicas should process events in the
  same order and subsequently all controller application instances
  should reach the same internal state.

If my understanding is correct, there isn't any difference and the two words can be used interchangeably. However, I would like to make sure I am not mistaken.

In the case both concepts are different, could you stress their differences and perhaps provide an example? That would be very much appreciated!

Thank you,

[0] - https://www.cs.princeton.edu/~jrex/papers/ravana15.pdf


texts:
Suppose a given piece of work can be done at two processors. One at r and another at v. The job can run only at one processor at a time.

r = R1, R2 ... Ri, ...Rn

v = V1, V2,... Vi, ...Vn

There is a time penalty to switch between r and v, which is a constant say k. But I will have to maximize the total work done within x hours.

Xi represents the amount of work done in the ith minute.

I was thinking that comparing the Vi and Ri every minute and then if one is greater than the other by k make a switch. But that won't be optimal.

How can this be approached?


texts: Is there something as good as a GRU or LSTM but simpler?

texts:
I was just reading this paper: Gate-Variants of Gated Recurrent Unit (GRU) Neural
Networks Rahul Dey and Fathi M. Salem

It seems to me that perhaps the architecture of LSTMs and GRUs are overly complicated. And that the same problems could probably be solved with a simpler architecture.

I get the theory behind LSTMs and GRUs as they are kind of trying to model the short term memory. But really all the need to do is get rid of the gradient exploding problem of RNNs.

What is the latest research. Is there something simpler than a GRU?

Edit: Actually I found something called a MGU (minimal gated unit) which claims to be simpler. What's the latest?


texts:
I've recently stumbled across the field of Set constraints for program analysis, that is, solving equations of the form $exp_1 \subseteq exp_2$, where (depending on the particular variant of the problem), $exp_i$ is a term involving $\cup, \cap, \sim$, some set of "constructor" functions, and variables. The goal is to see if there is an assignment to the variables that satisfies the system of inclusions.

In the literature about this, the applications to program analysis are repeated over and over again, but the complexity results given seem to be abstract, and pretty removed from any realistic implementation.

For example, it's been shown that set-constraints-sat with projections are satisfiable using a variant of tree automata. A broad overview can be found in Chapter 5 of this free book

I'm wondering:

Are these ever used in practice, or does the $DEXPTIME$ and $NEXPTIME$-completeness of most variants mean that it's never been put to use in practice?
Is there any research on practical implementations of these algorithms, trying to obtain performance for typical inputs despite the complexity? Research like this is pretty common for NP-complete problems (sespecially SAT).
Are set constraints out-dated i.e. has program analysis moved on from them? Is looking into them a dead end?


texts:
Let $\Theta$ and $o$ be defined as usual (Landau-notation).
For two equivalence classes defined by $\Theta$ we define
$$\Theta(f) <_o \Theta(g) :\Leftrightarrow f \in o(g)\qquad.$$
Let $$\mathbb{F}:= \{\Theta(f)\mid f:\mathbb{N}\rightarrow\mathbb{N}\}$$

My question:
Is $\langle \mathbb{F},<_o\rangle$ Dedekind-complete, i.e. given a set $F\subseteq \mathbb{F}$ with an upper bound $f_u,\forall f \in Ff\in o(f_u)$ are there $f_\inf$ and $f_\sup$ s.t.
$$\forall \Theta(f)\in F: \Theta(f_\inf) <_o \Theta(f) \qquad{(1)}$$
$$\forall g: (g\text{ fulfills (1)} \Rightarrow g \in o(f_\inf))$$

($f_\sup$ is defined analogously)?

Note: We don't need to assume a lower bound, since there is no infinite strictly decreasing series of $n \in \mathbb{N}$, i.e. $\Theta(0)$ is always a lower bound.

Background: I'd like to consider $\inf \{f \mid L \in N/DTIME/SPACE(f)\}$ for some Language $L$, but that only makes sense if such a (class of) function(s) exist(s).


texts: How to solve $T(n)=4T(\sqrt{n}/3)+(\log n)^2$ with the master theorem?

texts:
Can somebody help me with this recurrence please?
$T(n)=4T(\sqrt{n}/3)+(\log n)^2$


texts: What about problems that are fixed parameter tractable with an algorithm that does not inspect the parameter?

texts:
A parameterized problem is a subset $L \subseteq \Sigma^* \times \mathbb N$, where $\Sigma$ is a finite alphabet. A parameterized problem is fixed parameter tractable, if it could be decided in time $f(k)|x|^{O(1)}$ for some $(x,k) \in L$.

In terms of the problem definition, a Turing machine for $L$ has access to the parameter. I noted that for some algorithms, for example the kernelization of vertex cover, the algorithm indeed must have access to it, whereas for others, for example clique parametrized by maximal degree, it does not need access to the parameter. The algorithm for the latter simply looks into the neighbourhood of every vertex if it contains a clique, hence it runs in time $O(2^{\Delta} |x|)$, where $(x, \Delta) \in L$.

Was this ever noted? And if so, is there some notion like FPT without access to the parameter, i.e., a problem $L\subseteq \Sigma^*$ is in "FPT without access to the parameter", if it runs in time $f(k)|x|^{O(1)}$ for $x \in L$ and some number $k$ that depends on $x$ (I avoid the term parameter, as it is not given as input)? Or would it not make sense to consider such a class?


texts: Different ways to generate a big number with some small numbers

texts:
Imagine we have a set of numbers $\{x_1,x_2,\dots,x_m\}$. We want to compute the different ways to make a big number $P$ by those small numbers.

For example, if $P = 5$ and we have $\{1,2,3,4,5\}$ we can make $P$ by:

1+1+1+1+1 or
2+3 or
1+4 or ...


texts: Dijkstra complexity analysis using adjacency list and priority queue?

texts: I just got to look at the Implementation of Dijkstra using adjacency list and priority queue. The time complexity is $O(E\log V +V)$, I tried looking for the proof but couldn't find one. Any help will be appreciated.


texts:
In Weihrauch's Type-2 computability theory, a string function $f\colon\subseteq \Sigma^{\omega}\rightarrow \Sigma^{\omega}$ (the $\colon\subseteq$ indicates that $f$ may be a partial function) is computable iff there exists a Type-2 Turing machine that exactly realizes $f$, which implies that the Turing machine must fail to produce an output on inputs that are not in the domain of $f$.

To extend this to functions between arbitrary domains $D_1$ and $D_2$, one specifies representations $\gamma_i\colon\subseteq\Sigma^{\omega}\rightarrow D_i$, and Weihrauch defines $f\colon\subseteq D_1\rightarrow D_2$ to be $(\gamma_1,\gamma_2)$-computable iff there exists a Type-2 computable string function $g$ such that $f(\gamma_1(y)) = \gamma_2(g(y))$ whenever $f(\gamma_1(y))$ is defined.

But $\gamma_2(g(y))$ is allowed to be defined even when $f(\gamma_1(y))$ is not.

Why is it defined this way? It seems to me more natural to require $f\circ\gamma_1 = \gamma_2\circ g$, i.e. the domain of the realization $g$ must match the domain of $f$. With Weihrauch's definition we have the odd condition that, for a string function $f$, the statements "$f$ is Type-2 computable" and "$f$ is $(\mathrm{id},\mathrm{id})$-computable" (where $\mathrm{id}$ is the identity function) are not equivalent.

Reference: Weihrauch, K. (2000), Computable Analysis: An Introduction, Springer.


texts: What are string matching algorithms used in text editors like Atom and sublime

texts:
I know there are many algorithms for finding a pattern in a text like Boyer Moore, KMP, RabinKarp and so on.
I want to know what is the one that is mostly prefered by text editors and IDEs, as I find them efficient.


texts: all-to-all personalized vs all-to-all in a ring

texts:
I'm discovering parallel programming and I found a lot of slides online from various lectures explaining different kind of communications like these links:
http://web.cse.msstate.edu/~luke/Courses/fl14/CSE4163/Slides/DPA_Communication.pdf
http://parallelcomp.uw.hu/ch04lev1sec5.html#:~:text=In%20all%2Dto%2Dall%20personalized,message%20to%20all%20other%20nodes.
and few others.
They all use same illustrations and only include the algorithm for all-to-all personalized on hypercube but not for a unidirectional ring even though they included the all-to-all for rings.
Could someone please give an algorithm for all-to-all personalized on a ring and explain how would it be different from the normal all-to-all?
I thought of a simple algorithm with just 2 nested loops since they mentioned matrices in thoses pdf, but I feel there is a more efficient way to do it.
Thanks in advance


texts: Doubt in the correctness of decision tree models for constructing a lower bound

texts:
If we were to intuitively construct a lower bound for searching an element in a list $A$ containing $n$ integers, it would be in $\Omega(n)$.

But with the decision tree model, the number of leafs is $n$, so we conclude that the lower bound is $\Omega(\log{n})$.

This is the same as finding the maximum element in a list. Intuitively, it is in $\Omega(n)$, but with the decision tree model it is $\Omega(\log{n})$.

Can someone help me understand this discrepancy ?

Thank you in advance.


texts: Assign weights to the edges in a DAG so that, for all S and T, all paths from S to T have equal weight

texts:
I have a DAG, and on each edge, I have a minimum and maximum weight.  I would like to assign (or determine it's impossible to assign) exact weights to each edge so that

Each edge's weight is between its min and max
For any two nodes $S$ and $T$ in the DAG, all paths from $S$ to $T$ have equal weight (where the weight of a path is the sum of all the weights of the edges in that path)
[Bonus points] The total weight of all edges in the graph is minimized

I know I can set this up as a linear program, but that feels like overkill.  There has to be a simpler way to do this.  I've tried to think of a way to reduce it to a min-cost flow problem, but I've had no success so far.  I think that might not be the right direction.  Any ideas?

EDIT: As a starting point, for why I think this is at least tractable, here's how I would set up the linear program.  Each edge is a bounded variable.  To get the constraints, we can just do a breadth first search, keeping track of which edges have been traversed, to get values for each node.  Arbitrarily assign the first node to value 0.  When we traverse edge A, the value of the node that edge leads into is "A".  An edge B coming from that node leading into a new node gets value "A + B".  If we hit a node that's already been assigned a value, then we know those two values must be equal, so that becomes a constraint in the linear program.  Each edge can only add at most one constraint, so the number of constraints is at most linear in the number of edges.


texts: How does the destination IP address go from Application\End to End Layer to the Network Layer?

texts:
If the TCP segment does not contain the destination IP in its header, how does the(first) network layer decide the first link to traverse, to get closer to the destination IP.

I have learnt that the network layer prepares a header that has the source and destination IP, adds it to the TCP segment to make the IP packet.

The application layer which decides to send a message, should provide the destination IP. It doesn't make sense for the application layer to delegate this to the network layer which doesn't care about the end to end communication but does routing and forwarding alone. We resolve the host name to IP address using DNS, but how is this "IP address" information passed down to the lower Network layer without the TCP segment having mention this explicitly in its header.

I hope the Operating System, providing a socket as an abstraction to end to end communication does this. I have seen a socket getting created with parameters  as follows,

Socket socket = new socket("destination IP: port", "transport protocol")

Is it true that the application/transport/end to end layer drops the message into this socket and the Network layer obtains the "destination IP" information from this socket? I hope it goes as follows,

1> Resolve host name to IP address using a default DNS entry (to solve the "chicken egg" problem)

2> Create a socket with the IP address so obtained and some suitable transport protocol as parameters

3> Use this socket for further communication with the remote system

I'm missing a lot of details as I'm new to socket programming and networks. Help me understand this process. Will be glad if someone can cite a detailed material that gives a complete walk-through of this process.


texts: Turing machines: can a machine write to a finite number of memory cells, but not halt?

texts:
I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine $M$ writes to an arbitrary amount of memory, and false if it writes to a finite amount of memory cells. I am now thinking, is writing to a finite amount of memory cells equivalent to halting, or can there be cases where a machine writes to a finite amount of memory cells without halting?

Thank you in advance!


texts: Turning generative recursion results (leaves of a tree) into connected components (where each neighbour differs by one element)

texts:
I'm generating valid timetables for my uni with a simple generative recursion algorithm like this (disregarding handling of course-specific labs and tutorials)

def generate(current_timetable, unallocated_courses):
    if conflicts(current_timetable):
        return
    if not unallocated_courses:
        results.add(current_timetable)
        return
    course = first(unallocated_courses)
    for section in course:
        new_timetable = copy(current_timetable) + section
        generate(new_timetable, rest(unallocated_courses))

(Storing results as a flat list for now)

Probably room for memoization in there, but that part of the program is fast enough already.

Now, since this generates too many timetables to easily compare, I decided to group them into 'families', which are connected undirected graphs of timetables in which you can navigate between any two nodes by swapping one section at a time for another. As a result, I get around ~10 very differently shaped timetables that I can subjectively compare.

My naive O(n^2) approach was to take every single combination of 2 nodes, build an adjacency list based on the delta between each pair, and then find connected components with BFS.

If I store results in a tree (i.e. non-leaves are incomplete timetables, root is empty, each child has 1 more course allocated than its parents, and the leaves are the completed timetables), is there any insight about this structure that could make finding connected components faster?

I realize that immediate siblings would be connected in the final graph, since their only difference is which section (of the course that their parents is missing) was picked, but there can also be leaves that are identical except for e.g. their grandparents, and those are the ones that I can't seem to detect without the O(n^2) approach.

To clarify: Each course has a bunch of sections. At each level of the tree, a certain course is considered, and for each section in that course, a subproblem is created.

For example:

At level 1, different sections of course A are considered. At level 2, different sections of course B are considered.

Here's sample output with 2 families (sorry about the current interface): https://dmitry.lol/public/timetablor/


texts: Upper bound for size of minimal covers of a set

texts:
Would appreciate any insight about the following regarding set covers:

Begin with a universe set $X = \{x_1,x_2,...,x_n\}$ and a set $S=\{s_1, s_2,...,s_p\}$ such that each $s_i \subseteq X$ and $\bigcup S = X$.    Consider the task of finding all inclusion-minimal covers of $X$.  (Covers are inclusion-minimal if the removal of any subset $s_i$ from the cover destroys its coverage property.)

Given the set of inclusion-minimal covers $C=\{c_1, c_2, ... c_m\}$, what is an upper bound for $\max|c_i|$, that is, the largest inclusion-minimal cover?   It seems fairly straightforward to show that one upper bound is $|X|$ (that is, an inclusion-minimal cover will contain at most the same number of subsets as there are elements in  $X$ itself).

But can a better bound be found?

Additional information:   No restrictions are assumed for $S$.   The bound would ideally be expressed in terms of one or more properties of $S$ (in whatever form those might take).

A conjecture: If $\min |s_i| = k$, then $\max |c_i|$ (the size of the largest inclusion-minimal cover) is bounded above by $|X| - k + 1$.  This is based upon two observations:

(1) In constructing any inclusion-minimal cover, we start with any element from $S$ (call it $s_{1'}$).  As $s_{1'}$ covers a particular subset of elements from $X$, the next added cover element (call it $s_{2'}$) must cover at least one new element from $X$ not covered by $s_{1'}$.

(2) If $\min |s_i| = k$, then we can choose the first element $s_{1'}$ in our cover to have size $k$.  This leaves $|X| - k$ elements in $X$ left uncovered. By the first observation, each additional $s_i$ must cover at least one new element in $X$, so we can add at most $|X| - k$ additional elements to the cover, leading to a cover size at most $|X| - k + 1$.

As noted in the comments, this type of bound might not be significantly smaller than $|X|$ itself.  However, I am hoping to use this in a combinatorial context, so any savings helps.  Even smaller bounds would still be useful.


texts: Longest substrings of common length with the same parity

texts:
Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions:

length of both $A$ and $B$ is equal to $x$;
sum of elements in $A$ has the same parity as sum of elements in $B$.

Lengths of $a$ and $b$ are up to $5\times10^5$, so simple $O(n^2)$ solution won't do.

Example:
$a = [0, 1, 2, 3, 4, 5]$
$b = [3, 1, 3, 6]$
Answer: 3 (one of the possible solutions is $A = [2, 3, 4], B = [3, 1, 3]$).

I've thought about it for hours and can't find a solution. How to do this in linear or linearithmic time complexity?

I'm quite sure the problem can be simplified to for index $i$, storing only sum of elements up to $i$ modulo $2$. However, it doesn't help me much.

(The problem comes from a rather-old Israeli book תכנות תחרותי: סביב אתגרים ('Competetitive programming') by Mordechai Ben-Ari. The book isn't well known and I couldn't find any solution in Hebrew, so I translated the problem into English for a better chance of getting answer.)

Any help will be appreciated.


texts: I read a question and I don't understand it, is the set consisting of: production rules of Grammars that are CFGs, itself a regular set? The only thing I know is that the type 3 is under the type 2 in CNF.


texts: Does $20n$ belong to $O(n^{1-\epsilon})$ for some $\epsilon > 0$?

texts:
I am quite new to master theorem and I would like to ask the following question for $$()=4(/4)+20.$$
If there is a constant value like $20n$ does it affect the equation?
Would the equation look something like this for test case 1:

Is $f(n) = 20n \in O(n^{log_ba-\epsilon}) \in O(n^{\log_4^4-\epsilon}) \in O(n^{1-\epsilon})$ for some $\epsilon > 0$?


texts: Integer Problem Solving with two boolean selection variables

texts:
I am trying to solve a two dimensional combinatorial problem.
Hereis my input space {{RA1,RA2},{RB1,RB2},{RC1,RC2}} and i have to choose two out of three elements{A,B,C} and one out of two possible variations for each of these elements {1,2}. I have an objective function to maximize and i have some constraints. Based on these i have to make above selections. Can anyone please tell me if there is any optimization algorithm already available which serves my purpose. In reality i have a huge input space, so any existing algorithm is prefered


texts: Understanding of recurrence relation for number of 2-nodes in 2-3 tree

texts:
$$A_N = A_{N-1} - \frac{2A_{N-1}}{N} + 2\left(1- \frac{2A_{N-1}}{N}\right),\quad \text{for}\ N > 0, A_0 = 0.$$

Probability for 2-node to become 3-node is $\frac{2}{N}$ and for 3-node to become 2-node is $\frac{3}{N}$. 2-node contains 1 element, 3-node contains 2 elements.

I think that $A_{N}$ is the number of 2-nodes on $N$th step. So, $\frac{2A_{N-1}}{N}$ is the expected number of 2-nodes which turn to 3-nodes.

From where $\left(1- \frac{2A_{N-1}}{N}\right)$ came?

EDIT:
To give a context i provide picture of the exercise from An Introduction to the Analysis of Algorithms:


texts: Is it true that $f(n) = c\cdot g(n) + O(g(n))$ implies $f(n) = O(g(n))$?

texts:
Is this true for all $n$ and some $c>0$? I'm thinking the answer is yes, but I'm not sure. My thinking is as follows:
$f(n) = c\cdot g(n)$ for all $n$ and some $c>0$ is the definition of Big-Oh.
So, $O(g(n))$ is substitutable for $c\cdot g(n)$:
$f(n) = O(g(n)) + O(g(n))$
And by the max rule of sum:
$f(n) = O(g(n))$


texts: Disjoint union of NP-hard problem and P problem is NP-hard

texts:
Let $Σ = \{0, 1\}$ and let $A, B ⊆ Σ^*$ be languages. Prove that if $A$ is NP-hard, $B$ is in P,
  $A ∩ B = ∅$, and $A ∪ B ≠ Σ^*$, then $A ∪ B$ in NP-hard.

How can I go about proving $A ∪ B$ is NP-hard given the conditions? Any help would be appreciated.


texts: Comparing growth of two sums of functions

texts: Does $n+n^4$ grow faster than $n^2+n^3$? If so, why?


texts:
Highest Safe rung problem : There are many rungs on a ladder in increasing order of height. A bottle is thrown from a rung, and depending on the height of the rung, the bottle may break or may not (bottle breaks for higher height rungs, and doesn't for lower rungs). We need to find the maximum height safe rung for which the bottle doesn't break given that:

(1) We have only 1 bottle with us.

(2) We have infinite bottles with us.

(3) We have exactly 2 bottles with us.

(4) We have k bottles with us. ($1 \leq k$).

Design algorithms for solving (1) - (4) in best possible time complexity. (Also note that (3) and (4) should be an asymptotic improvement over (1).]

My method: (1) is just a linear search and (2) is a divide and conquer approach to solving the problem. I cannot find an asymptotically improved algorithm for (3) - the only methods which I kept thinking of provide some constant factor improvements in time complexity over (1), I am absolutely clueless on how to solve for (3) and (4).

P.S: This is a problem from Chapter 1 of Kleinberg and Tardos. I couldn't find it's solution online.


texts: Showing strong connectivity is in DSPACE((logn)^2)

texts:
$ST-CONN = \text{{(G,s,t) | G is directed graph, there's path from s to t}}$
I've learned the following deterministic algorithm to solve the problem in $log^2n$ space:
$\psi(G,s,t,k) :$
$\hspace{1cm}\text{if k == 1: return 1 if there's edge from s to t, else return 0;}$
$\hspace{1cm}\text{foreach } v \in V(G) \text{:}$
$\hspace{2cm}L=\psi(G,s,v,\lceil{\frac{k}{2}}{\rceil});$
$\hspace{2cm}R=\psi(G,v,t,\lfloor{\frac{k}{2}}{\rfloor});$
$\hspace{2cm}\text{if L == 1 and R == 1, return 1;}$
$\hspace{1cm}\text{return 0;}$
The professor said in class that the algorithm takes at most $\mathcal{O}(\log^2n)$ space, where $n$ is the number of vertices. But don't we pass the entire graph each call? I'll expect to see a $|V|+|E|$ factor in the big-oh, or maybe I miss something here.


texts: How to find the Branch factor of 8 Puzzle

texts:
I would like to know how to find the average branching factor for 8 puzzle.While referring Artificial Intelligence by George F Luger it says that:

  Suppose,for example we wish to establish the branching factor of the 8-puzzle.We calculate the total number of possible moves: 2 from each corner for a total of 8 corner moves,3 from center of each side for a total of 12, and 4 from the center of the grid for a grand total of 24.This divided by 9,the different possible locations of the blank, gives an average branching factor of 2.67.

Why do we have to divide by 9(possible locations of the blank space) to get the average branching factor.I'm confused with how the blank space affects the branching factor?


texts: I want to search from a given set of elements. Along with that I also want to remove that searched element. The problem is that the number of these queries is $q=O(n)$, where $n$ is the number of total elements. Which data structure should I use. Also, I want to avoid hashing.


texts: Improving an integer factoring algorithm

texts:
I've written an algorithm for integer factorization (specifically RSA-like coprimes - products of two large primes, roughly of the same number of decimal digits) which is not based on QS, GNFS or any similar known one. https://github.com/plktrautman/BlueShift

For any given n=p*q, consider a quadron with 5 parameters: UpperLeftStretch (ULS), UpperRightStretch (URS), LowerLeftStretch (LLS), LowerRightStretch (LRS), PositionTowardsTarget (PTT), all integers.
 Moving a quadron
 Move in the direction lower-left (LL):
PTT -= LLS
ULS -= 2
LRS += 4
LLS += 4

 Move in the direction lower-right (LR):
PTT += LRS
LLS += 2
URS += 2

moveLL and moveLR can be generalized to move quadron by more than a unit at once.

 Factorization

IDEA: keep moving quadron in LL/LR in order to obtain a target dualon with the parameter PTT=0. If that happens, one of the factors of n is equal ULS.
* Take the initial quadron for the given n (assume it's given at the start -- it's easily construable).
* If PTT >= LLS, then if PTT==LLS - factorization is complete.
** If PTT > LLS, then calculate n-CAPACITY:= how many times can we move quadron in the direction LL so that the shifted quadron has property PTT < LLS. Then shift (move multiple times at once) the quadron in the direction LL, shift_strenght = n-CAPACITY.
* if PTT < LLS, then move quadron in the direction LR.
Keep the process until PTT = 0.

 How can we leverage the fact, that near end of each factorization, the sequence of LL shift capacities form a sequence, which is not constant, but values of which have an amplitude equal 1?

Example. In case of n=161, the visualisation would look like this (initial quadron is marked in black and has PTT=2; in this case factorization is simply LR(1)->LL(1)->LR(1)->LL(1). The green target quadron has ULS = LRS = 7 which is factor of 161 (=23*7). You can see that in essence ULS, URS, LLS, LRS are distances from surrounding quadrons, forming an infinite graph.


texts: Sort array of duplicate integers in place

texts:
Given an array of integers within [1, n] where n = size of array, some elements may appear more than once.

Could we sort it with just 1 extra space and in O(n) time?


texts: How to determine if a language produced by grammar is recognizable by deterministic pushdown automaton (DPDA)?

texts:
I have a following grammar:
S -> aSa | bSb | $\lambda$.

And I have to figure out whether the language produced by this grammar is recognizable by DPDA.
I can't find any theorems about it.
Obviously, it's a context-free language and can be recognized by non-deterministic pushdown automation, but what about deterministic?

EDIT:
I built first, follow and select sets and discovered that this is not an LL(1) grammar. Does it mean that DPDA doesn't exist?

first: {a, b, $\lambda$}

follow: {-|, a, b}

select(S->aSa) = {a}

select(S->bSb) = {b}

select(S->$\lambda$) = {-|, a, b}


texts: How to solve variable sized bin packing when the items have equal weights, or is it still NP-hard?

texts:
Consider the variable sized bin packing

$$
    \begin{align*}\tag{P1a}\label{P1a}
      & {\underset{\mathbf{ x }, \mathbf{ y }}{\text{minimize}}}
      & & \sum_{j=1}^nf_jy_j\\[3pt]
      & \text{subject to}
      & & \sum_{i=1}^{m} w_{i}x_{ij} \leqslant C_{j}y_j,\forall\,j\in\{1,\dots,n\}\tag{P1b}\label{P1b}\\[3pt]
      & & & \sum_{j=1}^n x_{ij}=1, \forall\, i \in\{1,\dots,m\}\tag{P1c}\\[3pt]
      & & & x_{ij}, y_j \in\{0, 1\}, \forall\, i\in\{1,\dots,m\}, j\in\{1,\dots,n\}\tag{P1d}.
    \end{align*}
$$

The problem \eqref{P1a} can be found for example in variable sized bin packing problem.

The problem \eqref{P1a} can be seen as:

We have set of bins $\{1,\dots,n\}$ each with a weight $f_j$, a set of items $\{1,\dots,m\}$ each with a weight $w_i$. For each bin $j$, there is a capacity $C_{j}$.
We would like to assign all items to the bins such that every item is assigned to exactly one bin and the weights of items assigned to bin $j$ does not exceed the capacity $C_{j}$.

I am curious about the case where the weights of the items are all equal, say $w_i=1$ for all $i$. Can we derive an optimal algorithm in this case or it is still NP-hard?

I can't find an NP-hardness reduction but I think that we can do this algorithm:

sort the bins by $C_j$ in decreasing order;
start with bin 1, fill it with items until $C_1$ is reached;
go to the next bin and loop.

I have tried this algorithm with few examples but I cannot prove its optimality though.

Could you help please?


texts: Explanation of pseudocode and time complexity analysis

texts:
I am trying to work my way through some computer science training and I am not able to properly understand the following pseudo code:
COUNTING-1 (n)             cost          times

1  for r=1 to n            c1               n+1

2    for c=1 to n          c2               n(n+1)

3      sum = sum+1         c3               n2

4  return sum              c4               1

T(n)=c2*n(n+1)+c3*n2 +c1*(n+1)+c4=an2+bn+c

Could someone explain why the outer loop is n+1, and not just n?
Also what are the constants c, a and b? I don't understand why they need to factor into the explanation equation as it isnt clear what their value will.
Apologies if these are really simple questions. If there are some useful things I should read I would appreciate a pointer in the right direction.
*Edit: I think looking at it again the c constant is the cost of the operation which for each is constant time, so 1. Is the cost of a single operation ALWAYS 1? If it is (which it appears to be in this RAM model) what is the point in over complicating the formula underneath with those values?
Why not just T(n)=n(n+1) + n2 + (n+1)


texts: How to solve this recurrence involving binomial coefficients?

texts:
How to solve the following recurrence involving binomial coefficients, where $c$ is a constant non-negative integer, and $n$ and $k$ are non-negative integers ($n \ge k \ge 0$)?

$$
A(n,k) = A(n-1,k) + A(n-1,k-1) + c, \\
A(n,0) = 1, A(n,n) = 1
$$

My Attempt:
Without the constant $c$ (or $c=0$), $A(n,k)$ is just $\binom{n}{k}$.

I have tried the generating function
$$
g(x,k) = \sum_{n=0}^{\infty} A(n,k) x^n.
$$
I need to evaluate
$$
\begin{align}
\sum_{n=0}^{\infty} A(n+1,k) x^n &= \sum_{n=0}^{\infty}\big(A(n,k)+A(n,k-1) + c\big)x^{n} \\
&= g(x,k) + g(x,k-1) + \frac{c}{1-x}
\end{align}
$$

On the other hand,
$$
\begin{align}
\sum_{n=0}^{\infty} A(n+1,k) x^n = \frac{1}{x} \big(\sum_{n=1}^{\infty} A(n,k) x^n\big) = \frac{1}{x}\big(\sum_{n=0}^{\infty} A(n,k) x^n - A(0,k)\big).
\end{align}
$$
How to handle with $A(0,k)$? How to establish an equation for $g(x,k)$?


texts: How to score a given arrangement of windows on a screen to produce good layouts

texts:
(this is related to my other question, see here)

I would like to write a function that scores a given arrangement of windows on a screen.

The purpose of this function is to determine whether a particular layout is good and by going over other possible layouts, finding the one with the highest score.

Here are some characteristics that I think make a good layout:

maximizing amount of space used by windows (or in other words, the free space on the screen should be minimized)
windows are (more or less) evenly sized

Bonus: assigning each window a priority and giving a higher score for layouts where windows with a higher priority take more space.

Here's an example: Suppose our screen is 11x11 and we want to put two windows on it. Window A's initial size is 1x1 and window B is 2x1.

When we resize windows, we preserve their aspect ratio. So here are two possible layout:

The function should give the one on the right a higher score.

Another nice thing to have is the option to 'dock' a window to one or more sides of the screen. Then suppose we want to dock A to the bottom-left of the screen, the scoring function should prefer this layout than the above one on the right:


texts: Can $\emptyset$ be reducible to any other language?

texts:
While solving some question, that involved the empty set $\emptyset$, I was really wondering, is $\emptyset$ reducible to any other language, i.e., $\emptyset \leq A$ such that $A$ is a language over a given alphabet $\Sigma^*$?

I mean, one can never take $x \in \emptyset$, right? or am I missing anything?

Maybe $\emptyset \leq \emptyset$? because if I take a reduction $f$ such that $x \in \emptyset \Leftrightarrow f(x) \in \emptyset$, this is always true, because $x \in \emptyset$ is never true and $f(x) \in \emptyset$ is also never true, so that function is a reduction function in the empty-concept, no?


texts: Prove existence of different programs printing each other code

texts: How to prove that there exist two different programs A and B such that A printing code of B and B printing code of A without giving actual examples of such programs?


texts: Which is harder, an NP-complete problem or the Raz-Tal oracle problem?

texts:
This is a (hopefully) sharper version of a question that I asked previously.

Which of these algorithms is believed to have a longer asymptotic runtime?

The optimal algorithm guaranteed to solve some NP-complete problem using a standard Turing machine.
The optimal algorithm guaranteed to solve the problem described by Raz and Tal using a Turing machine with access to the oracle described in their paper. (This is the oracle $O$ that achieves the oracle separation $\mathrm{BQP}^O \nsubseteq \mathrm{PH}^O$.)

(I understand that this is somewhat of an "apples-to-orange" comparison because the two Turing machines have different capabilities, but you can still compare the algorithm runtimes.)

Figure 3 of this essay suggests to me that NP-complete problems are much "harder" than BQP-complete problems, which would seem to suggest that algorithm 1 would need to take longer than algorithm 2. But Raz and Tal's result seems to identify an oracle problem in BQP that is outside of the entire polynomial hierarchy (including all of NP), which would seem to suggest that algorithm 2 would need to take longer than algorithm 1. Which of these intuitions is/are incorrect?


texts:
I ask a question before, Questions on Graph and Hamiltonian, but i ask it here with different challenging contest.

From this book and other study in complexity theory, I have seen the following statement:

  The definition of NP is not symmetric with respect to yes-instances and no-instances.  For example, it is an open question whether the following problem belongs to NP: given a graph G, is it true that G is not Hamiltonian?

However, I was wondering if this this problem was NP-Complete.  Could someone let me know if the following statement true?

  Determining a that a Graph is not Hamiltonian is in NP-Class.

I read another book on this book on end of page 306, the authors wrote this is NP-Hard. anyone could clarify me?


texts: Is this padded version of the Halting Problem in NP?

texts:
I'm using the following definition of $NP$:

$$A \in NP \Longleftrightarrow A(x) = \exists w: B(x,w) $$
where $B \in P$ and $|w| = poly(|x|)$.

Now instead of the problem whether the program $\Pi$ halts on input $x$, I'll use the close cousin that asks whether $\Pi$ halts on $0$. Then I can write:

$$HaltsOnZero(\Pi) = \exists t: HaltsOnZeroInTime(\Pi, t) $$

where $HaltsOnZeroInTime$ is the decidable problem of checking whether $\Pi$ halts on input $0$ after $t$ steps. Comparing this with the definition of $NP$ $HaltsOnZeroInTime$ is already in $P$ as long as $t$ is encoded in unary. After all running $\Pi$ for $t$ steps takes only about $t$ steps, so this is a linear algorithm.
The only issue is that $t$ isn't in $poly(|\Pi|)$ because programs of size $|\Pi|$ when given $0$ as input run for $BusyBeaver(|\Pi|)$ time, which isn't even computable, much less polynomial. But now suppose we insist that $\Pi$ is padded until it reaches length $BusyBeaver(|\Pi|)$ and call that new input $\Pi'$. Then $t$ would be polynomial (in fact linear) in the size of $\Pi'$ and $HaltsOnZero(\Pi')$ would be in $NP$.
At this point there's of course a voice inside me shouting that this is all nonsense because $BusyBeaver$ isn't computable. Well I certainly haven't reduced the classical formulation of the Halting Problem to a problem in $NP$ because I had an uncomputable step in the reduction. But it seems to me like I've still defined a problem in $NP$ with the strange property that just writing down a problem instance requires uncomputable superpowers.
Is this really a bona fide $NP$-problem or am I making a subtle mistake somewhere?


texts: Using Huffman Encoding to improve Lempel-Ziv Encoding

texts:
Can anyone think of a way to use Huffman Encoding to improve the compression rate of Lempel-Ziv Encoding?

My initial idea was to encode with higher probabilities given to shorter strings (i.e. the string "e" would have a higher probability than the string "ef").

Does anyone know of a good way?


texts:
I'm trying to prove that for a flow network, maximum flow f, and each minimum cut S that f(S)=c(S).

Max flow min cut promises that there exists a cut where f(S)=c(S); I want to prove that given multiple minimal s-t cuts Si, that c(S1)=f(S1)=c(S2)=f(S2)...,  meaning all outgoing edges of all minimal cuts are fully saturated.

It seems very intuitive to me but I can't seem to get it.

I want to say that the flow for any s-t cut is equal to the flow going into t.  How can I prove that?

I'm guessing that I need to rely on the fact that for each vertex the incoming flow equals the outgoing flow but I don't really see how.


texts: Find a sequence of integer powers faster than the naive algorithm

texts:
Let $k\in \mathbb{N}$ be fixed. The naive way to compute a sequence of values $a_1^k,\ldots,a_n^k$ where $a_i\in \mathbb{N}$ for all $1\leq i\leq n$ is compute $a_i^k$ individually with the exponentiation by squaring. This takes a total of $O(n\log k)$ multiplications.

Is this optimal? What if for each $a_i$, we have $\frac{1}{c} a_i \leq a_{i+1}\leq c a_i$.

I come up with this question because I was doing a binary search over $f(n)=n^k$.


texts: How to make a "Secure by Design" client-server communication?

texts:
Is there a way to have a secure by design client-server communication in a sense that the server can check if the client is not a modified version?

What I'd like to do is give the user access to both the client's and the server's source code, but keep him from communicating with a modified version.

As a practical example, let's suppose a multiplayer race game. Is there a way to give the user access to the source (and to compiling it and playing it on the server if he wants) but keeping him from, let's say, altering the speed of his car to 2x normal speed and using this new version to play?

As I understand, the compiled program could generate some hash and send it together for the server to verify. But then there also comes stuff like being able to get this code and making another version send it, etc.

If this is a known problem, please also provide further information about it.
(Any recommendations on books or papers related to that are also welcome)


texts: Producing an algebric equation from a graph

texts:
I'm writing a computer game and one of my game's objects must follow a movement path that is very similar to the following graph.

The bold lines are the Y and X axis. In order to be able to code this movement thought I need the algebric equation that translates to this graph. For example f(x) = x^2.

Is there any mathematic technique I could use to obtain the algebric from of this function?


texts: Show that the set of all TMs that move only to the right and loop for some input is decidable

texts:
I am trying to prove that

$\qquad L=\{\langle M\rangle \mid M \text{ is a TM }, \exists w. \text{ in }  M(w) \text{ the head moves only right and } M(w)\!\uparrow \}$

is decidable.

I thought about the following solution:
Lets build $\hat{M}$, a TM that will decide L:
M on input $\langle N \rangle$:
 1. $\Sigma^{Q+1} $ is decidable so it has an enumerator f.
 2. for every word $ w\in\Sigma^{Q+1} $ simulate parallel N on w for |Q|+1 steps:
  $\space \space \space$ - if N got to a blank then N moved only right and is stuck in a loop.
3. if all of those words stopped the simulation at a blank accept. else reject.

I am quite sure I am missing something here. Can you help please?


texts: Implications of $NP = \Sigma_2 P$ for PH collapse

texts:
A simple fact is that $P = NP \to P = coNP$, which follows from the observation that $P$ is closed under complement.

I am having trouble seeing that an analogous statement is true at higher levels of $PH$.  For example, is it known that $NP = \Sigma_2 P$ implies $NP = \Pi_2 P$?  If so, is there an easy proof?  Would such a statement have any other interesting implications (For example $NP = coNP$)?

It seems somewhat likely to me that this is true, based on the observation that $NP = \Sigma_2 P$ means that $\exists \forall$ quantifier patterns can be replaced with $\exists$ quantifier patterns, and so all higher levels of $PH$ would at least collapse to $\Pi_2 P$.


texts:
I'm wondering how a set  of keys  could  be  assigned  to  nodes  in a 2-3-4 tree  in  order  to  minimize  the  height of the tree?

Does the sequence of insertion matter with 2-3-4 trees?


texts:
I have a rough idea of what coalescing in terms of memory access by threads is, but now, when learning about compilers, the term coalescing also appears when talking about register allocation.

In my book, it is just briefly mentioned, that coalescing for register allocation is just merging nodes from the graph (I assume the nodes of the graph show the variables that can be stored in a register).

Can someone explain a bit more thoroughly what coalescing in this sphere means?


texts: Modelling using propositions, syntax and standards

texts:
One of the first programs I wrote when learning Java was a console application modelling the operation of an elevator. I'm trying to teach myself propositional logic and so I thought, why not use the same example?

So, suppose I have been given the task of modelling the main functions of an elevator system using propositions and predicates...

Opening and closing doors (allowing entrance and exit at appropriate
times)
Storing and responding to floor requests from users
Processing information from sensors (elevator load, floor position
and speed sensors)
Displaying status information on the displays (at each floor and in
the cab)

My Google searches have returned very little in the way of useful insight into how this should be done or any standards that might exist. What would be the best way to do this?

Would something like this be appropriate?:

$$ F = requestedFloor, L = loadSensor(load), C = loadSensor(capacity) $$
$$ F ∧ L < C → move(F) ∧ display: print(currentFloor)  $$
$$ floorSensor(currentFloor) < F  → move(up)$$
$$ floorSensor(currentFloor) > F  → move(down)$$

Which is simple enough, right? If there is a floor requested and load is less than capacity then move to that floor. Also, print the floor to the display.

If anyone has any suggestions or can provide some examples of how I might model this I'd love to hear them.


texts: Is a forever running program computable? For example a program which calculates the biggest natural number.


texts: Middle ground between model-based and model-free approaches

texts:
In the context of the reinforcement learning domain, the dichotomy between model-based (learn a model and used it to determine a controller) and model-free (learn a controller without learning a model) approaches is a contested one.

There are many algorithms that have been developed for both approaches.

My question is, are there any approaches that are between model-based and model-free? One example could be to specify a controller that is the combination of a learned controller (when there is sufficient information to do so) and a pre-determined controller based a model (when we cannot learn the controller).


texts: Finding the shortest time to go from one stop to another stop in a train system with many train lines with connection stations

texts:
So I was thinking after discussing with my friend the other day, how would I use something like breadth-first or depth-first search to find the fastest time to go from one station to another station if there are a number of different train lines in a subway system. They may cross over each other, maybe multiple times even.

Train line in this case means a train that goes from a starting station to a ending station, with many station stops on the way, where certain station stops may give the option for the rider to swap to another "line" that also has its starting and stoping station. A simple example is a two-line subway system like so:

o : station   - : track

                     Line 2
                     START
                       |
                       o
                       |
Line 1 START o -- o -- o -- o -- o -- o END
                       |
                      END

I live in Taipei, Taiwan, so you may reference the MRT train map there for reference but it may look fairly complicated. I was looking for tips for a simpler start and ways to work out a solution to a smaller problem first, but the MRT system is my friend and I's target goal.

What I have though of so far

Have an array that holds each stop name on along with the time it
takes for previous stop to reach this stop represent a single train
line, with each connection to another train line being a nested array
at that item.
Figure out how to tell the algorithm to look through each route to find the destination stop, adding the time taken along the way
comparing to find the shortest time.

Things to Consider

The time between each station is known to us. But for the purpose of this question just assume its 5 minutes between each station.
A train line has a starting stop and a ending stop, but on the way it may stop on a stop that connects to any other train line.
Any connection to another train line may connect to another line - but access to this third line may be reached by taking a further more complicated route by switching train lines. Meaning if I try out all possibilities it may take looping routes and test forever.

Its possible to take a transfer from one line to another, and go either left or right on the new line, i.e. the trains are not one-way.

So how is it possible to

Avoid our algorithm making loops, e.g.:

If line 1 connects to line 2 on its third stop, and that connects to a third line, and then back to line 1 later on down line 3. Then if we were to try find the shortest way to go from a stop in line 1 to another stop in line 1, the algorithm may test going from line 1 to line 2 taking the connection then to line 3 back to line 1 and back around.

And also, how do we make it decide where to make the turns, and what is a better way to represent this problem and find the shortest time?


texts:
A Horn clause is a disjunctive clause of literals containing at most one unnegated literal. Examples are
$$
\neg p \lor \neg r \lor \neg q,\\ \neg s \lor q,\\ \neg s \lor \neg q\lor r,\\ s,\\ \neg r \lor t,\\ \neg q \lor \neg t\lor p.
$$
Determining whether or not a set of Horn clauses is simultaneously satisfiable takes polynomial time: this is the problem known as HORNSAT. The algorithm does the following:

If there is a clause containing only a single positive literal, set the letter of that literal to true; then remove the negation of that literal from all clauses containing it. Repeat until no such clauses exist.
Then, if there is an empty clause, the set is not satisfiable.
If there is no empty clause, the set is satisfiable, with satisfying assignment given by setting all unset letters to false.

Following the algorithm, you can quickly see that the above set of clauses is not simultaneously satisfiable, since the last five clauses force all used letters to be true, while the first clause asks at least one to be false.

Now, the problem #HORNSAT asks the following: given a set of Horn clauses, how many simultaneously satisfying assignments are there? One might expect the problem to be easier than #SAT, since HORNSAT is so much easier than SAT; on the other hand, it "feels" NP-hard.


texts: Avoiding underflow when identifying neighbours of a cell in a grid by using modulo

texts:
I'm going through a tutorial that is using the Game of Life as example code. It has a function in it that finds the neighbor of a given cell. It is explained quickly that "When applying a delta of -1, we add self.height - 1 and let the modulo do its thing, rather than attempting to subtract 1" which would require a bunch of conditional logic to check for edge cases (when the cell we are checking is on the edge and simply adding or subtracting from its position would put it out of bounds)... This is the algorithm:

for a given 0-indexed row and col in a 2d space with area width * height:

for delta_row in [height - 1, 0, 1]
    for delta_col in [width -1, 0, 1]
        if delta_row == 0 && delta_col == 0
            continue // this is the cell we are checking

        neighbour_row = (row + delta_row) % height
        neighbour_col = (col + delta_col) % width

Anyways, I'm just wondering, how does someone figure this out from the naive case, where you just add and subtract and check for bounds? I'm not great with math but I'm assuming there might be a way to explain this algebraically? I worked through this with actual numbers for a while to verify it and just want to get a better understanding of how this works so maybe I can use this concept again later.


texts: Kraft's inequality and Shannon's noiseless coding theorem for an encoding

texts:
A discrete memoryless source W has words $w_1,w_2,w_3,w_4,w_5,w_6$ that occur with probablilities $0.05,0.05,0.15,0.2,0.25,0.3$ respectivley.

Does there exist a compact instantaneous binary encoding for this source with word lengths $2, 2, 4, 4, 5$ and $5$?

Shannon's Noiseless coding theroem that says a compact encoding has expected wordlength $n$ where $n\leq \frac{H(W)}{\log_2(D)}$.
I get $H(W)=2.328$ and $n=1.901$, but in this case the expected word length is $3.67$ so it cannont be a compact encoding.

I feel like I have gone wrong here, could somebody tell me how? Because I have gone on to the next question where I perform Huffman coding to achieve a compact instantaneous encoding however the word length for this encoding is still higher than $1.901$ so fee like I must have my value for $n$ wrong but can't see how?


texts: How can I represent state or environment in the $\lambda$-Calculus?

texts:
I have seen in different tutorials how to represent numbers and booleans in the pure $\lambda$-Calculus, and  how to define some arithmetic and logic operations. But what if I want to represent other constructs, not usually encouraged in pure functional languages, like state (assignment of values to variables) and sequencing (evaluating $e_1$ before $e_2$)?

For example, how would I encode an assignment "$v := e$" (where $v$ is a variable and $e$ an environment)?  And what about encoding "$x := 2; y := y + x$"? (The point is that there is a dependency among statements, and they should be evaluated/executed in the correct order.)


texts: What does it mean that a let-binding can be treated polymorphically, only if its right-hand side is a syntactic value?

texts:
Types and Programming Languages by Pierce says:

  22.7 Let polymorphism

  A ﬁnal point worth mentioning is that, in designing full-blown
  programming languages with let-polymorphism, we need to be a bit
  careful of the interaction of polymorphism and side-eﬀecting
  features such as mutable storage cells. A simple example illustrates
  the danger:

let r = ref (λx. x) in
(r:=(λx:Nat. succ x); (!r)true);

  ...

  It is better to change the typing rule to match the evaluation rule.
  Fortunately, this is easy: we just impose the restriction (often
  called the value re striction) that a let-binding can be treated
  polymorphically—i.e., its free type  variables can be
  generalized—only if its right-hand side is a syntactic value. This
  means that, in the dangerous example, the type assigned to r when we
  add it to the context will be X→X, not ∀X.X→X. The constraints imposed
  by the second line will force X to be Nat, and this will cause the
  typechecking of the third line to fail, since Nat cannot be uniﬁed
  with Bool.

I am trying to understand the above sentence in bold.

In the example, is the let binding not treated polymorphically, because  ref (λx. x) is not  a syntactic value?
Could you give an example, where the let binding can be treated polymorphically?

Is the above  sentence related to  the following three sentences in bold? Or are they talking about several different things?

  23.8 Fragments of System F

  The most popular of these is the let-polymorphism of ML (§22.7), which
  is sometimes called prenex polymorphism because it can be viewed as a fragment of System F in which type variables range only over quantiﬁer-free types
  (monotypes) and in which quantiﬁed types (polytypes, or type schemes) are not
  allowed to appear on the left-hand sides of arrows. The special role of let in
  ML makes the correspondence slightly tricky to state precisely; see Jim (1995)
  for details.

  23.2 Varieties of Polymorphism

  More common
  in practice is the form known as ML-style or let-polymorphism, which restricts polymorphism to top-level let-bindings, disallowing functions that
  take polymorphic values as arguments, and obtains in return a convenient
  and natural form of automatic type reconstruction (Chapter 22).

Thanks.