texts: Confirmation of alternative correctness proof for Floyd-Warshall's all-pair shortest-path algorithm

texts:
The most common proof for Floyd-Warshall's algorithm is an induction proof on the outer-most loop, which says

$\delta^k(i,j)=\begin{cases}
\min\{\delta^{k-1}(i,j),\delta^{k-1}(i,k)+\delta^{k-1}(k,j)\} & \text{for}\,k\geq 1\\
w(i,j) & \text{for}\,k=0\,\text{(i.e., base case)},
\end{cases}$

where $d^k(i,j)$ is the shortest path from $i$ to $j$ using $k$. Here I present another proof using induction on the length of any shortest path. I have a feeling that the main idea of my proof is the same as above, but I'm not sure if it is correct (missing something important). Here is the proof below:

Proof. (induction on $l$, the lengths of all shortest paths between all pairs of vertices $x_i$ and $x_j$ in the graph)

Base case $l=1$: the shortest path between some pair of vertices $x_i$ and $x_j$ is exactly the edge $(x_i x_j)$. In this case, $d_{ik}+d_{kj}\geq d_{ij}=k((x_i x_j))$ for all $k$ by the fact that $(x_i x_j)$ is the shortest path. The algorithm will not change $d_{ij}$ in this case, so it is correct.

Now, suppose that the algorithm will correctly find the length of all shortest paths of length up to some $c$, and that the shortest path between some pair of vertices $x_i$ and $x_j$ is $(x_i x_{p_1} x_{p_2}\cdots x_{p_c} x_j)$, which has length $c+1$. Now, let $x_{p_m}$ be the vertex in the path that has the biggest index in the distance matrix, and consider the path divided into $(x_i\cdots x_{p_m}\cdots x_j)$; let $P_1=(x_i\cdots x_{p_m})$ and $P_2=(x_{p_m}\cdots x_j)$. For $P_1$, the algorithm will correctly find its length by the inductive hypothesis, since it is of length at most $c-1$ and it is the shortest path between $x_i$ and $x_{p_m}$; similarly the algorithm will correctly find the length of $P_2$, since it is of length at most $c-1$ and it is the shortest path between $x_{p_m}$ and $x_j$. The algorithm will correctly do the comparison $d_{i p_m}+d_{p_m j}<d_{ij}$ when $d_{i p_m}$ and $d_{p_m j}$ are the length of $P_1$ and $P_2$, respectively, and update $d_{ij}$ correctly. This is because $p_m$ has the biggest index in the matrix, meaning that the algorithm would have already correctly found the length of $P_1$ and $P_2$ and stored them in $d_{i p_m}$ and $d_{p_m j}$, since they share intermediate vertices of smaller index and therefore would have been found in previous iterations of the outer-most loop.

P.S. To clarify, this is for a homework problem (as these problems typically are), and I am asking this after the due date. Most large universities in the U.S. nowadays employs graders (I am one myself), which means that my alternate proof may or may not receive a careful look. My point is that I want to know whether I missed something in the proof.


texts: Which bound is better, a logarithmic or a polynomial with arbitrarily small degree?

texts:
I have a randomized approximation algorithm which can be tuned by selecting the randomization probabilities. I found out that:

For any $\epsilon >0$, there are probabilities for which the approximation factor is $O(n^\epsilon)$.
There are probabilities for which the approximation factor is $O(\ln n)$ (smaller factor is better).

I know that $O(\ln n)$ is asymptotic smallerer  than any $O(n^\epsilon)$ when $\epsilon$ is fixed, but here $\epsilon$ can be made arbitrarily small, so I don't know, which of these two bounds is considered better? Specifically:

A. Theoretically, which of these two bounds should I report in a paper? Is the bound $O(n^\epsilon)$ interesting, or is it considered useless given the logarithmic bound?

B. Practically, if I have to run the algorithm on very-big-data, with no possibility of making tests in advance, which tuning is better?

(Just to get some feeling, I compared $n^{0.1}$ with $\ln n$. It turns out that $n^{0.1}$ is better even for very large $n$ - they become equal at about $n=4 \cdot 10^{15}$)


texts: Use tree in-order traversal to determine whether a BST or Heap

texts:
Given these in-order traversal lists:
1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19
2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17

I need to determine whether each one of those lists represent a valid BST / min or max heap, or none.
I was trying to figure how to approach this, but besides brute-forcing every possible option I couldn't figure a "smart" way to solve this.

What indicators can I use, if there are any, or the way to solve this would be literally brute forcing every option?


texts:
SSUM is the same as the Subset Sum Problem with the only additional requirement is all the numbers must be unique in the subset.

To prove it's NP complete, the verifier is quite easy to construct being the same as one for the Subset Sum except you add the additional requirement of making sure all numbers are unique.

With the reduction, I assume you can use the same reduction as before from 3SAT, I'm just figuring out a way when evaluating that reduction, to determine if two or more numbers are the same. I'm using the 3SAT reduction in Sipser with the table of columns and rows. If one needs any more information I would be happy to provide.


texts: one-to-many matching in bipartite graphs?

texts:
Consider having two sets $L$ (left) and $R$ (right).
$R$ nodes have a capacity limit.
Each edge $e$ has a cost $w(e)$.

I want to map each of the $L$ vertices to one node from $R$  (one-to-many matching), with minimum total edge-costs.

Each vertex in $L$ must be mapped to one vertex in $R$ (but each node in $R$ can be assigned to multiple $L$-nodes).

Examples: Consider the capacity of $R$ nodes is $2$.

1) This is NOT correct, since one node from $L$ has not assigned to a node in $R$.

2) This is NOT correct, since the capacity of a node in $R$ is violated.

3) This IS correct. All $L$ nodes are assigned to a node in $R$, and the capacity of $R$ nodes is not violated.

Any idea how can I solve this?


texts: PAC learning vs. learning on uniform distribution

texts:
The class of function $\mathcal{F}$ is PAC-learnable if there exists an algorithm $A$ such that for any distribution $D$, any unknown function $f$ and any $\epsilon, \delta$ it holds that there exists $m$ such that on an input of $m$ i.i.d samples $(x, f(x))$ where $x\sim D$, $A$ returns, with probability larger than $1-\delta$, a function which is $\epsilon$-close to $f$ (with respect to $D$). The class $\mathcal{F}$ is efficiently PAC learnable if it is PAC learnable, and $A$ runs in time $\text{poly}(1/\epsilon, 1/\delta, n)$ (where $|x| = n$) and the description of $f$.

Is there a case where a class $\mathcal{F}$ is not efficiently PAC learnable, yet it is efficiently learnable on the uniform distribution?


texts:
There is a flash game that you can very easily find on Google called Blockage.

  Rules & Goal of the game : Get all coloured blocks from
  their initial position to a corresponding target spot of the same color. Once a block is placed on a target spot of the same color, it cannot move anymore. You can select a specific block and move it left or right. Blocks are also subject to gravity (moving them vertically until they hit a wall or another block). There can be many blocks of the same color and more blocks than target spots. Obstacles include walls and other blocks (two blocks cannot be at the same position).

I would like to implement an $A^*$ algorithm that finds the sequence of steps to win this game.

I am currently thinking about a good heuristic $h(n)$ to use. The best one I could find is the following : the sum of the Manhattan distances between each colored block and its closest target.

Any idea on a better heuristic?


texts: How do I describe formally complexity of 2-sum problem algorithm?

texts:
I have algorithm that finds if there are two elements in sorted array that have sum zero.

1.ZeroSumPair(A[1..n]) // A[1..n] <-- sorted
2.    l <- 1, r <- n
3.    while(l < r)
4.        while(l < r or A[l] + A[r] > 0)
5.            r--
6.        if(A[l] + A[r] = 0)
7.            return true
8.        l++
9.    return false

Intuitively I know that this algorithm is $O(n)$, but how do I deduct it using proof with summations like in CLRS book?

I've also saw How to develop an $O(N)$ algorithm solve the 2-sum problem?, but I didn't see any formal proof.


texts:
A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family corresponds to a path from the root to a leaf. For example, the following family is treeable:
{ {1, 2, 6}, {1, 3, 4, 5, 6} }

A possible tree is:
1 -> 6 -> 2
     |
     + -> 3 -> 4 -> 5

However, the following family is not treeable:
{ {0, 1, 2}, {0, 2, 3}, {0, 3, 1} }

Is it possible to decide in polynomial time whether a given set-family is treeable (and construct a tree)?


texts: Representing abstract syntax tree as a graph

texts:
Does it make sense to represent an AST as a graph? How can one achieve a mapping between ASTs and graphs that preserves both semantic and syntactic properties of source code?
The goal and application of such a transformation would be to use graph neural networks and other deep "graph" learning techniques to extracts features, clustering source code, find code similarities and suggest code completion tasks.
Any suggestion of current algorithms and research in this area?


texts:
Let's say I'm writing a GA to find an optimal path to travel from point $A$ to point $B$. Genotypes are a list of directions (north, south, east, west) to follow.

So a genotype "NENWEE" will move north once, east once, then north again, west once, and finally east twice.

The directions are encoded as follows:

N : 00
E : 01
W : 10
S : 11

Our first genotype, "NENWEE" (let's call it $P$), will thus be encoded as follows:
$00\,01\,00\,10\,01\,01$

Let $Q$ be a second genotype, say "EENEWW", which is encoded as follows:
$01\,01\,00\,01\,10\,10$

Now let's do a one-point crossover operation on genotype $Q$, from $P$. The randomly-chosen crossover point is between the $9$-th and $10$-th bit, so bits $10$, $11$ and $12$ from genotype $P$ will replace those same bits from genotype $Q$. Let's call the resulting genotype $Q'$.

P  :  00 01 00 10 01 01
Q  :  01 01 00 01 10 10
Q' :  01 01 00 01 11 01

After decoding $Q'$ we find that the result is "EENESE". However neither $P$ nor $Q$ contained direction south.

My question is, do crossover operators imply a certain degree of mutation by definition?


texts: List of major Open Problems in Computational Complexity and their Likelihood?

texts:
I remember reading an article/paper (or perhaps a talk, most probably by Scott Arranson) where he lists the major open problems and their likelihood of being true or false in a table/graph. This is listed along with the 'surprise factor' of each result if its true/false.

I am unable to locate the article though. I wonder if someone remembers the article and can help. I am aware of a similar one by Ryan Williams but I am looking for the other one.

P.S. I know its a silly request. Apologies. But, still need it.


texts: Reduce ATM to the language of TM encodings concatenated by a string where the TM accepts both the string and its reverse

texts: Prove that the language $LM =\{\langle M,x\rangle\mid \ M \text{ accepts }x\text{ and rev}(x) \}$, where $\mathrm{rev}(x)$ is the reverse of the string $x$, is undecidable with a reduction from $A_{\mathrm{TM}}$. Note that the empty string belongs to $LM$.


texts:
Is $n^{1/\log \log n} = O(1)$ ?

Suppose that $n^{1/\log \log n} = c$ where $c$ is constant.

Taking logs of both sides,

$$\frac{1}{\log \log n}\log n = \log c.$$

I am not able to spot an error. Please help


texts: How to assign the increasing keys to the nodes of a complete binary tree on n nodes in inorder?

texts:
I'm looking at the Multiplicative Binary Search and come across this.
It's the preparation you need to do for you to use the Multiplicative binary search procedure.

I somehow do not know how to do number 1. Can you explain how?

I thought it was getting like the formula for the binary search wherein
the index = floor of((lower+upper)/2) such that instead of using floor you'll do ceiling instead.

However I came across this example,

and see that that method only worked for full binary tree but not for those who are not full but complete binary tree.
Can you explain how the complete binary tree was deduced from the original table?


texts: RAM BSS model based (or its variant) computer recognizing Boolean languages

texts: Can any RAM BSS model based machine, or machines which are variants, recognize boolean languages(languages such as P, NP, or the like)? If so which languages are recognizable by RAM/BSS nachines, or its variants?(A variant could be to allow comparison. Or a RAM/BSS with weaker assumptions).


texts: MCTS how to prevent Selecting a TERMINAL state in TRAVERSAL Phase?

texts: Hello I am currently working on an implementation of MCTS and I ran into the problem that my tree traversal policy selects nodes with terminal game states. Furthermore how do I prevent selecting a Node that only has children Nodes with terminal game states ( and so on and so on )?


texts:
Given a tree
To search for value 1, I do the following splay operations:
i) Zag on 7

ii) Zag on 1

And hence obtain 1 in the root. But why would this be incorrect?
i) Zag on 1

ii) Zag on 1

The final tree in this case is different.


texts: Solve modulus with constraints for multiple equations

texts:
I'm trying write a program to solve equations from the following form:

$$ \begin{align}
a \bmod x &= t_1 \\
b \bmod x &= t_2 \\
\end{align} $$

where $a$, $b$, $t_1$ and $t_2$ are known values.

I have multiple equations of the same form and I'd like to solve them for $x$.
Assuming I have constraints on $t_1$ and on $t_2$ for some constant $C$:

$$ \begin{align}
0 \le t_1 \lt C \\
0 \le t_2 \lt C \\
\end{align} $$

e.g :
for $a=150$, $b=50$, $t1=2$, $t_2=1$:
$$ \begin{align}
150 \bmod x &= 2 \\
50 \bmod x &= 1 \\
1, 2 \lt 5 \\
\end{align} $$

What would be the most efficient way to program such a thing?


texts:
Once you encode your message as a polynomial you can effectively generate and stream an endless number of points on that polynomial of which only a finite subset would be required to recover the polynomial.

Why isn't Reed Solomon also a Fountain code? I have never seen it listed as such and I looked.


texts: Why is it important to solve a problem in Polynomial time, In cryptography?

texts:
I have just started to learn Cryptography.

I am trying to learn "Merkle-Hellman Knapsack Cryptosystem".

So, right at the beginning of the discussion, a question came in my mind:

Why is it important to solve a problem in Polynomial time?


texts: Finding minimum number of edges such that when adding into the graph, the graph is a 2-connected graph

texts: Given is a undirected and 1-connected graph G=(V,E). Between every two node b=(u,v) in graph G there is a cost c_b to build another edge(Regardless of whether (u,v) ∈E or not). We use a C={c_b |c_b∈Z^+,b∈V×V} to represent costs between every node regardless of whether (u,v) ∈E or not. Now, we want to add some edges M⊂E into the graph G which makes graph G^'=G+M is a 2-connected graph (G^' allow the appearance of multiple edges while graph G is not) such that weights of edge set of M is minimize.


texts: Let's say we have the language L = {w $\in$ {a,b}$^*$ : ($\exists n \in \mathbb{N}  $)[$w|_b = 5^n$]}. I want to know if this is a regular language or not. How do I go about doing this? I'm familiar with the Myhill-Nerode theorem but I don't know how to apply it.


texts: Check two balanced binary search trees that sub set of each other

texts:
Given two balanced binary search trees $T_1,T_2$. We want to check,
are $T_1\subseteq T_1$ or not. $T_1$ have $n_1$ nodes, and $T_2$ have
$n_2$ nodes.
Instructor say it can be done in $O(n_1+n_2)$ time complexity with
$O(\log n_1+\log n_2)$ space.

My idea:
I use in order traverse on two trees , and compare first node in order traverse  $T_1$ with first node in in order traverse $T_2$, and etc. if all nodes in $T_1$ present in $T_2$ then  we say $T_1\subseteq T_2$, but i can't prove my space complexity followed from mentioned complexity. Any one can help to guarantee my space complexity be $O(\log n_1+\log n_2)$.


texts: Intuitive self-contained proof of Farkas' Lemma

texts:
I've been studying the proof of Farkas' Lemma, and given my rather fuzzy memory of Linear Algebra, am having some trouble with it. One version of Farkas' lemma states:

For any convex cone generated by vectors $a_1, a_2, ...a_m \in \mathbb R^n, C=\{x: x=\sum_{i=1}^m \alpha_ia_i,\alpha_i \geq 0\}$, any point $y \in \mathbb R^n$ in the space

either belongs to the cone OR

there is a halfspace through the origin that contains the cone and does not contain $y$, i.e. there is a vector $w \in \mathbb R^n$ such that $w^Ta_i \geq 0$ for all $1 \leq i \leq m$ and $w^Ty < 0$.

I think I understand the first part of the proof -- namely that if (1) if true, then (2) cannot be true, because if both were true, then it means all of the following is true: $Ax=y$, $w^TAx < 0$, and $w^TAx \geq 0$ the latter of which is a contradiction. Please let me know if I've made any errors here.
The second part of the proof -- namely, if (1) is false then (2) must be true -- is where I'm having issues. I've read a few proofs, but most of them either appeal to a different theorem (i.e. separation lemma) or have explanations / notations that are too confusing. Is it possible to come up with a nice, self-contained, intuitive proof for Farkas' Lemma?


texts: Efficient search for solving a Jigsaw Puzzle?

texts:
I believe that solving a Jigsaw puzzle is in general NP-complete based on the two questions linked below. However, I'd like to implement a heuristic algorithm that works well in practice.

Let's assume the puzzle pieces are encoded as 4-vectors of integers representing the four sides. A negative integer indicates an indentation that must be matched with corresponding positive integer representing an extrusion. Zero represents a smooth edge (i.e., a border piece.) Rotations then correspond to cyclic shift (assuming the indentations/extrusions are rotationally symmetric.)

My heuristic for an efficient solution is to try to tile the puzzle in an inward spiral starting from the borders. What is the best strategy for building a chain of fitting pieces that avoids exhaustively trying all combinations/rotations?

I found some related SE questions that are relevant:

https://cs.stackexchange.com/questions/13849/are-zero-one-jigsaw-puzzles-np-complete
https://stackoverflow.com/questions/15121903/algorithm-for-solving-tiling-jigsaw-puzzle
Partially filled jigsaw puzzle with six types of tiles


texts: Integer sampling with exponentially decreasing probability

texts:
Given a probability $p$ and an integer $N$, I would like to generate a sample $S$ of the population $P=\{0,1,...,N\}$ such that integer $m\in P$ is sampled with probability $p^m$.
It is trivial to do this in time $O(N)$. I am looking for an algorithm that can perform this sampling in (expected) time proportional to the output, say $O(|S|)=O(\tfrac{1-p^{N+1}}{1-p})$.
Numerical precision is very important, and in most cases $p$ is very close to $1$ so that the expected size of the sample will remain constant as $N$ increases.
If the sampling probability were constant I could use a Poisson distribution to "jump" over unsampled integers (among other methods), but in this case the probability is not constant. What do I do?


texts: Intuition for convolution in image processing

texts:
I have read many documents about convolution in image processing, and most of them say about its formula, some additional parameters. No one explains the intuition and real meaning behind doing convolution on an image. For example, intuition of derivation on the graph is make it more linear for example.

I think a quick summary of the definition is: convolution is multiplied overlap square between image and kernel, after that sum again and put it into anchor. And this doesn't make any sense with me.

According to this article about convolution I cannot imagine why convolution can do some "unbelievable" things. For example, line and edge detection on the last page of this link. Just choose appropriate convolution kernel can make nice effects (detect line or detect edge).

Can anyone provide some intuition (doesn't need to have to be a neat proof) on how it can do that?


texts: Primitive Recursion equipped with an evaluator function

texts:
The wikipedia article for primitive recursion mentions a limitation that primitive recursive function can't compute the function $ ev(i,j) $ which computes the $ i $th primitive recursive function on input $ j $.

I was wondering what you can compute with primitive recursion equipped with $ ev $, which I will refer to as secondary recursive functions.

More formally,

any primitive recursive function is secondary recursive
secondary recursive functions are closed under composition and primitive recursion (just like primitive recursive functions)
$ ev $ is secondary recursive
$ ev $ indexes function such that computing the index of a projection, composition, or recursion is primitive recursive.

Note that in the above, $ev$ is still only computing primitive recursion.  Thus, secondary recursion always halts - $ ev $ always halts and the other ways of building secondary recursive functions can't turn halting functions into non-halting functions.

I've found that some "nice" examples of non-primitive-recursive functions are secondary recursive.

For example, for any fixed $ n $ , the function $ f_n(a,b) = a \uparrow^n b $ is primitive recursive.  Given arbitrary $ n $, we can compute the index of $f_n$ (with some work), then use $ ev $ to compute $ arrow(a,b,n) = a \uparrow^n b $ which is not primitive recursive (it can be used to compute the Ackermann function).

We can also further generalize this to $n$-ary recursion, with $1$-ary recursion being primitive recursion, and $(n+1)$-ary recursion being primitive recursion equipped with an function that evaluates $n$-ary recursive functions.  (Then we can generalize this even further, with $ \omega $-ary recursive functions which are the union of $n$-ary recursive functions for all $n$, $(\omega+1) $-ary recursion being primitive recursion equipped with a function that evaluates $\omega$-ary recursion etc. )

I have 2 questions:

Have these been studied?  Do they have a name?
Are there any "nice" examples of functions which are recursive but not secondary recursive?


texts:
I'm having trouble proving the following: If $L_1$ and $L_2$ are languages then: $$(L_1^*L_2^*)^* = (L_1\cup L_2)^*$$
I could be on the wrong track here, but I figured an inductive approach is a good way?

My approach was this: If I use my notation $L^{(n)} = \lambda+L+L^2+...+L^n$ so that I have a kind of 'partial' Kleene star I start the induction:

1.) Base case $n=0$:

$(L_1^*L_2^*)^{(0)} = \lambda = (L_1\cup L_2)^{(0)}$ and so this works

2.) Assume true for some $n=k\geq0$ such that $(L_1^*L_2^*)^{(k)} = (L_1\cup L_2)^{(k)}$

3.) Now I want to see how $(L_1^*L_2^*)^{(k+1)}$ evaluates to:

$(L_1^*L_2^*)^{(k+1)} = (L_1\cup L_2)^{(k)}+(L_1^*L_2^*)^{k+1}$ where I used the inductive hypothesis. I know I should try to see if this RHS can give me the union with a (k+1) but I don't know how to manipulate this anymore. Am I on the wrong track or am I just not seeing the algebra properly?


texts: Textbooks about the verification of computer programs that use Z as the specification language

texts: I'm looking for textbooks/lecture notes about the verification of computer programs, i.e. proving their correctness, that use Z as the specification language against which the correctness is verified.


texts: What is the machine epsilon and number of mantissa bits for TI-83?

texts:
I am trying to determine how many bits the TI-83 Plus uses to store floating point numbers. I am using the algorithm for approximating the machine epsilon given in "Numerical Mathematics and Computing" by Cheney and Kincaid. In TI-BASIC, it looks like this:
: 1 -> E
: While (1+E) > 1
: E/2 -> E
: End
: Disp 2*E

The program returns 9.31322575E-10, which is equal to $2^{-30}$. This is an approximation within a factor of 2.
Here's where I get confused. In the textbook I mentioned above, they say that the number of binary digits used in the mantissa, $k$, is given by $u=2^{-k}$, where $u$ is the number we just found. This is easy to verify for things like IEEE-754 format, because the mantissa is stored as its base 2 representation, so k is the number of bits allocated to the mantissa. However, as far as I can tell from sources like this, the TI-83 does not use IEEE-754 floating point, but different floating point encoding scheme with 7 bytes of binary-coded decimal for the mantissa (that's 14 decimal digits). If that is true, then it seems to me like the machine epsilon should be $10^{-14}$. Furthermore, this means the number of mantissa bits is 56, rather than 30.
How can I rectify these two things?


texts: Books for the Mathematical Theory of AI/ML

texts: I am interested in the mathematical foundations of Artificial Intelligence and Machine Learning. Are there any books which will describe and present the mathematical foundations in detail? I am not that interested in coding and would prefer a text which is heavy in mathematics and the theory.


texts: Operating Systems - Why Stack Growths For a Fixed Parameter N Are Inconsistent?

texts:
I am taking an Operating Systems course and as a project, we are printing the content of the PCB of a process from task_struct of that process and its mm_struct & vm_area_struct pointers. During my stack growth experiments, I used a recursive summation method with parameter n, which returns the sum of first n integers. However I realized that in some cases, same parameters do not result in same growths. What might be the reason for this?

Here's how we find the stack boundaries, in case it is necessary:

Using for_each_process, we find the task_struct of the process with
pid = x
From task struct, we get the process' mm_struct & vm_area_struct
pointers
Using a linear search, we detect the stack as follows: vma->vm_start < mm->start_stack && vma->vm_end >= mm->start_stack; where vma is a virtual_area_struct

Note that this procedure is done with a kernel module.


texts:
I am trying to train an autoencoding neural network (autoencoder) to reconstruct seismograms. Previous studies employing this technique (e.g. Valentine & Trampert, 2012) used an L2 (mean squared error) loss function to assess the network's performance, but I'm wondering if there are better loss functions out there for this type of data. Seismograms are rather spurious, in the sense that the signal rapidly oscillates around zero, which makes it hard to get a good point-by-point comparison. For instance, if the reconstructed seismogram has a slight time lag but is otherwise a perfect reconstruction of the original input (see image), the L2 loss could be enormous due to this slight misalignment.

My question: how would you evaluate the quality of the reconstruction in terms of the approximate position, duration, amplitude, etc.?


texts:
Can anyone please help me try to understand what will the state diagram look like for this question:

Let $L = \{x_0y_0z_0x_1y_1z_1\ldots x_{n-1}y_{n-1}z_{n-1} \mid \exists n,x,y,z \, x+y=z \land x=\sum_{j=0}^{n-1} x_j2^j \land y=\sum_{j=0}^{n-1} y_j2^j \land z=\sum_{j=0}^{n-1} z_j2^j \land \forall i \, x_i,y_i,z_i \in \{0,1\}\}.$ Show that $L$ is regular. It is sufficient to draw a state diagram.
Try to design your state diagram in a systematic way. Arrange your states in 3 columns (with 1 exception), such that before reading the $j$th bit you are in column $j$. If at this time, the DFA has to remember 2 bits, you could draw the states in lexicographical order of these 2 bits.

Any help is much appreciated. I've spent more than an hour just trying to understand the question and still could not figure it out.


texts: How can one tell when will the state of the circuit components change?

texts:
The system clock is needed to synchronize all components on the motherboard, which means they all do their work only if the clock is high; never when it's low. And because the clock speed is set above the longest time any signal needs to propagate through any circuit on the board, this system is preventing signals from arriving before other signals are ready and thus keeps everything safe and synchronized. The CPU clock has the same purpose, but is only used on the chip itself. Because the CPU needs to perform more operations per time than the motherboard, the CPU clock is much higher. And because we don't want to have another oscillator (e.g. because they also would need to be synchronized), the CPU just takes the system clock and multiplies it by a number, which is either fixed or unlocked (black edition models).

\bib{38243}{misc}{
    title={What are system clock and CPU clock; and what are their functions?},
    author={Benjoyo (https://cs.stackexchange.com/users/27547/benjoyo)},
    note={URL: https://cs.stackexchange.com/q/38243 (version: 2015-02-11)},
    eprint={https://cs.stackexchange.com/q/38243},
    organization={Computer Science Stack Exchange}
}

This answer states that the clock components change state only when the signal is high. Why is it so?


texts: What is the correct definition of coNP/poly?

texts:
Complexity Zoo defines coNP/poly as
Complement of NP/poly
Thanks to Emil, I understand it as
"the class of decision problems whose complement can be solved in polynomial time by a non-deterministic Turing machine that has access to a polynomial-bounded advice function."
(A polynomial-bounded advice function is a function $f$ that maps each positive integer $n$ to an advice string $f(n)$ of length polynomial in $n$. To be clear, the advice string depends only on $n$; it is independent of the input to the Turing machine.)
I don't clearly understand this definition. A decision problem is basically a yes/no question, and I suppose "solving a decision problem" means answering the yes/no question correctly. But, if that is the case, then solving a decision problem is same as solving the complement of the problem. So, I wonder
What is the meaning of the word 'solve' in the definition of coNP/poly (or NP/poly)?
I am also interested in whether we can define coNP/poly (or NP/poly) in terms of deterministic polynomial time verifiers (as in the definition of NP). The best I could come up with are the following.
NP/poly is the class of decision problems whose yes certificates can be verified in polynomial time by a (deterministic) Turing machine that has access to a polynomial-bounded advice function.
coNP/poly is the class of decision problems whose no certificates can be verified in polynomial time by a (deterministic) Turing machine that has access to a polynomial-bounded advice function.
Are these definitions correct?
Disclaimer: I have asked a related question in cstheory.stackexchange. At the time of asking that question, I did not know that the problem is in my understanding of the definition. They recommended that I ask the question here. (I shall delete my other question if the only problem is my understanding of the definition).
Thank you


texts:
I've recently become interested in randomly generating Voronoi diagrams to create "territory" maps (similar to this) for a project I've been working on.

Traditional Voronoi diagrams using an Euclidean metric don't present sufficient cell variation for my liking so I've been attempting to utilize a L∞ metric instead, using Fortune's Algorithm as the means to create the diagrams.  Fortune's method utilizing a L∞ metric, unlike its Euclidean counterpart, is not particularly well-documented and my understanding as a result has been less than clear.

Specifically, I'm unsure whether my understanding of how spike events (called circle events in the Euclidean instance) are determined - and thus the vertices of the Voronoi diagram discovered - is correct or not, and I would very much appreciate some help in either confirming my method or correcting it.

My understanding thus far is based on the following: that the L∞ distance between two points p and q is defined d(p,q) = max(|px-qx|, |py-qy|), and the bisector between p and q is representative of all points equidistant using that formula.

I believe then, as stated in the last paragraph on pg. 12 in this paper by Evanthia Papadopoulou, that a square containing both points and whose sides are equal to the L∞ between them (rather than the Euclidean circle) can be used to check for spike events.

Two squares (one solid, one dashed) containing points p and q (Figure 1).  The point in the middle of each square (blue) would seem to suggest a spike event, or vertex, when it is resolved (below, Figure 2).

The same method applied to points p, q, and r yields the following (Figure 3):

It seems to work well, but I'm uncertain because Papadopoulou goes on to add

  [the Euclidean incircle test] now simplifies to a test involving the
  square defined by the three elements. (Note that three elements need
  not always define a square). In the worst case the L∞ incircle test
  corresponds to 1) determining the intersection point I of two lines
  (bisectors), 2) determining the intersection point J of a line and a
  45◦ line through I, and 3) comparing the horizontal or vertical
  distances between I and J and between I and one of the defining
  elements (12)

and

  A spike event C takes place at t = xc + w where xc is the
  abscissa of the intersection point and w is the distance of the
  intersection from the inducing element (14).

I'm not entirely sure whether the method is consistent with the above, as I'm not entirely sure what she means.

Additionally, I'm concerned because in Figure 3 the first vertex to the right (point a below, Figure 4) potentially should not exist because its partner vertex b would fail to be created as a third point, q, would lie inside the second square of p and r.

As Fortune's Algorithm traces the Voronoi edges when it creates the diagram with the movement of the sweep line, would the theoretical edge being traced from a to b not already be past the point next to a when the sweep line arrives at q?  Or, since b is not created, does the edge moving left from a simply not grow until the point next to it is found?

Thank you in advance for any feedback/insight/comments/answers.  I think I'm nearly there but any affirmation or corrections would be extremely appreciated and welcome.  I hope I've explained myself sufficiently (and that my post is not too open-ended) but please let me know if I can clarify or elaborate on anything.


texts: Is this language equivalent to this grammar?

texts:
The book that I'm reading says it is equivalent

But what about the aa string ? i produce it this way :

$$
S\Rightarrow S_1B\Rightarrow aS_1bB\Rightarrow aaB\Rightarrow aa
$$
But that language doesn't have aa in it, what am i doing wrong here?


texts: Don't understand minimax algorithm in terms of chess

texts:
I'm new to minimax algorithm, but i understand it's entire concepts as it's easy, my biggest issue is understanding it's implementation to my chess game, no internet solution answers this question

black or white players comprises of several pieces, so what piece is the AI predicting moves for, as the player could move any of their 16 pieces?

all i keep seeing is that we need to write the code to look several moves ahead in which the player could potentially make, my issue is that there are multiple pieces the player could pick from so what moves exactly are we talking about and how would the AI determine which of its pieces to move based on that.

I just need a brief explanation, no source code or how to's. I've spent days trying to wrap my head around this concept.


texts:
If I've  RFID Collision Arbitration System that is based on multi-frame dynamic frame ALOHA. How can compute the probability of the average tag resolution $L_n$? ,$P_s$ is probability for packet trasmission that no other packet arrives in the previus slot.  $P[N(t+T,t)=0)]=e^G ; S=Ge^G$;S stand for Throughput.

$G=Tx\lambda$  G is traffic Distribuited according to Poisson process end $\lambda$ is Packet arrivals poisson process with paratameter $\lambda$ end T is last trasmission.

Knowing that  $N_{population Tag=}=5$ end $r_{slotsize}=3$?
i'know that if i want to compute $L_n$, i've to apply recursive formula, that is :  $$L_n=r+\sum_{i=0}^n P(S=i)L_{n-i} $$
end in this case i'd have to obtain :

$$L_5= 3+P(S=0)L_5+P(S=1)L_4+P(S=2)L_3P(S=3)L_2P(S=4)L_1P(S=5)L_0$$
for me here it's ok until i've to compute P(S=0)...but for the other how could compute it?


texts: There are several pseudorandom number generators that we have no known polynomial time algorithms for inverting (finding the initial seed). Is it correct to say that inverting these generators is an NP problem?


texts:
Show that the following problem is solvable.Given two programs with their inputs and the knowledge that exactly one of them halts, determine which halts.
lets P be program that determine one of the program will be halted.
P(Program x,Program y){

    if(x will be halted)

          then return 1;

    else

           then return 2;
}

since we know that exactly one of them will be halted,if 1 then program x will be halted.Otherwiae program y will be halted.
then we construct a new program call D
D(X,Y){

     if(P(X,Y) == 2)

         D will halt;

      else

         while(1)//D will not halt;

  }

lets S be aritbrary program.
So if we have D(D,S)
if D will halt then D will not halt
if D will not halt then D will halt
It impiles a contradiction same as halting problem.
But the question stated that it is solvable.


texts: Is there a term for these "descendancy" subgraphs of directed acyclic graphs?

texts:
Consider a directed acyclic graph $G$ with vertex set $V$.  Choose a vertex $v$, and let $H$ be the subgraph containing $v$ and all other vertices in $G$ that are reachable from $v$ (along with the associated directed edges).

(In other words, if we choose $v \in V$, then we are interested in the subset consisting of $v$ and all of its descendants).

Is there an accepted term for this particular subset of vertices (or the subgraph)?  It seems to be a fairly elementary concept so I expected to find a commonly used phrase for this, but my search is coming up empty so far.   Thanks for any answers or leads!


texts: Rules to follow to create edges in graph

texts:
I am currently writing a graph object in Swift, I see that there are different types of graphs, some that are undirected and some that are directed. Here are my questions :

Can a graph be both directed and undirected, is there a specific name for such graph?
What is the common approach to make an edge that would be bi-directionnal but whose weight depends on the direction you are following. Would it be acceptable to make an edge that hold two weights, one for each direction? Or should I create two edges?

Thank you.


texts:
I have a directed acyclic graph with a score on each edge.  The score of a path is defined to be the sum of the scores on the edges along this path.  The probability of a path is the score of such a path divided by the sum of the scores of all paths.

I would like to compute the marginal probability of each edge; i.e., the probability that the edge is present in a path drawn randomly from the above probability distribution on paths.  Is there an efficient algorithm to do this?

I know that I could simply calculate the probability of each path through the graph and then for each edge sum the probabilities of the paths on which the edge occurs but this seems a very inefficient way of doing things. Is there some way to use dynamic programming to solve this issue?


texts:
The Kurose & Ross book uses "store-and-forward delay" as a synonym for the transmission delay of a packet over a network link.

As a newcomer to computer networks, it isn't immediately obvious to me how these two terms are synonymous. My current understanding is that if not for the store-and-forward behavior of packet switches, the transmission delay of a link would be negligible as it would be pipelined with the propagation delay of the previous link; i.e. as the bits propagate across Link A, they are transmitted and stream into Link B. However, due to store-and-forward, no bits are transmitted onto Link B before all the bits have crossed Link A, and hence, we need to add the transmission delay of Link B.

Is this correct?


texts: Is there an optimization algorithm that could help match the maximum number clients to servers with constraints?

texts:
How do you go about solving the following problem that tries to match the greatest number of clients with servers with constraints? I'm trying to identify an algorithm or simulation that could help me solve this problem as optimally as possible.
Assume you are given a 2d map of servers and clients randomly scattered. Each server can handle a certain radius of clients but never two clients that are near each other (this is the constraint). While it makes sense for a server to handle all the clients near it, some clients may need to be handled by another server nearby. Picking which of those clients should be handled by another server (potentially farther but still in reach) such that the maximum number of clients can be handled is the objective.
Not all clients necessarily can be handled, but the problem should be able to match the most number of clients with servers possible, and the constraint must be upheld.


texts: Is there an efficient method to store large DAGs?

texts:
I have a DAG representing strict partial order where each node is an assignment of variables $V$ to their values $v$. Each arc $(u,w)$ represents a change in one variable value such that $u\succ w$.

So if I have $n$ binary variables, I will end up with $2^n$ nodes which is exponential to the size of variables $n$. is there any method to store such DAG efficiently?


texts:
Wikipedia defines straight-line programs in the following manner:

  In mathematics, more specifically in computational algebra[disambiguation needed], a straight-line program (SLP) for a finite group G = 〈S〉 is a finite sequence L of elements of G such that every element of L that belongs to S, is the inverse of a preceding element, or the product of two preceding elements. An SLP L is said to compute a group element g ∈ G if g ∈ L, where g is encoded by a word in S and its inverses.

This is a fairly confusing definition to unpack. However, in some meaningful sense, I believe the main idea here is that there are no comparisons allowed. Since there are no comparisons, the "computation tree" ends up being a straight line - hence the name "straight-line program."

In modern terms, is this the correct idea? Or are there even more subtle restrictions than this on what sorts of programs are allowed to be straight-line programs?


texts: How do bridges divide a larger network into smaller broadcast domains?

texts:
I am recently brushing up my computer network knowledge, and came across a seemingly peculiar statement:

  A network bridge divides a network into smaller broadcast domains.

As far as I could grasp the details, a bridge operates on the two lower layers of the ISO OSI model - the physical and the data link layers.
What this means is bridge selectively forwards data link frames on the basis of the destination MAC address that can be found on each received frame.

But, the doubt arises when we consider the fact that the broadcasts are achieved using a broadcast IP address of that particular network. Now, due to the broadcast address being an entity/property of the network layer, should principally be not paid attention to by the bridge, and be flooded into all the interfaces available to it.

Then, how exactly does the bridge manage to filter the broadcast packets?


texts: How to find a subset of potentially maximal vectors (of numbers) in a set of vectors

texts:
I have a set S (so no duplicates) of d-dimensional vectors of non-negative real numbers (or if you would prefer, floats).

I say a vector u "covers" a vector v if, in every dimension 1..d, u[i] >= v[i]. So for d=3, (3,3,2) covers (2, 3, 1), but (3, 3, 1) doesn't cover (2, 2, 2).

I am interested in finding a subset T of S, such that for every v in T, there is no u in S with u != v, such that u covers v.  Alternatively, I'm interested in removing from S those vectors that are covered by other vectors in S.

What is an efficient algorithm for this?  Barring that, what is at least the "real name" of this problem to help me search for it?

An O(n^2) algorithm is obvious: for every vector in S, check it against every other vector in S, and add it to T if nothing covers it.  I'm having trouble doing much better than that.

I have considered trying to use kd-trees and range trees, but this is for a real world problem, and in practice d is too high and the number of vectors too low, so that e.g. the O(n * log^d(n)) running time is actually worse than the naive O(n^2).  (d is approximately 20-40, and the number of vectors is in the millions).

Edit - Particular Problem Details

As requested, more information about the specific problem I am trying to solve.

The implementation problem at hand involves several sets of vectors, approximately 60-100 sets, each with about 10-20 vectors in them. For every set s, for every vector v in s, v has dimension d, and all axes of v are zero save for one which is positive. A result vector is formed by choosing precisely one vector from each set and adding them together, and a given result vector is strictly worse if it is covered (or apparently the real word is 'dominated') by another result vector. You can assume the non-zero axis of a base vector varies uniformly in [.9, 1.1].  In practice most intermediate results appear to be dominated, and size(T) << size(S)


texts: Inserting at the head of a linked list is O(1), but this involves moving pointers, and they are not constant size

texts:
I don't understand how linked list insertion is constant time.  The larger the list gets, the more bits are required to specify memory locations, and then the more bits that must be edited to account for changes in pointers.

Where is my mistake here?


texts: Oriented undirected edges in directed graph

texts:
I have a graph with $n$ vertices and $m$ edges. Some edges are already oriented, some are not. How do I determine how to orient all undirected edges so that each vertex has the same outgoing and incoming degrees, and whether it is even possible to do so?
P.s This graph for example:


texts: Simple Bayesian classification with Laplace smoothing question

texts:
I'm having a hard time getting my head around smoothing, so I've got a very simple question about Laplace/Add-one smoothing based on a toy problem I've been working with.

The problem is a simple Bayesian classifier for periods ending sentences vs. periods not ending sentences, based on the word immediately before the period. I'm collecting the following counts in training: number of periods, number of sentence-ending periods (for the prior), words and counts for words before sentence-ending periods, and words and counts for words before not-sentence-ending periods.

With add-one smoothing, I understand that

$$P(w|\text{ending}) = \frac{\text{count}(w,\text{ending}) + 1}{\text{count}(w) + N},$$

where $P(w|\text{ending})$ is the conditional probability for word $w$ appearing before a sentence-ending period, $\text{count}(w,\text{ending})$ is the number of times $w$ appeared in the training text before a sentence-ending period, $\text{count}(w)$ is the number of times $w$ appeared in the training text (or should that be the number of times it appeared in the context of any period?), and $N$ is the "vocabulary size".

The question is, what is $N$?

Is it the number of different words in the training text? Is it the number of different words that appeared in the context of any period? Or just in the context of a sentence-ending period?


texts: Solving a variant of interval scheduling problem

texts:
I am trying to solve a problem of finding compatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.

I have a set of jobs with start and finish time and I want to find the smallest subset of this jobs such that all the jobs are incompatible with at least one job of this subset. And all the jobs in this subset are compatible

Suppose

job  start   end
1    1       3
2    2       11
3    4       6
4    12       14

My required job set J is {2,4} since  all the jobs are incompatible with at least one job of the job set J. And all the jobs in the job set J are compatible. I tried using earliest deadline first and schedule but it doesn't work. Any suggestions?

Am I going the right way?


texts: A deterministic FA for $0^*1^*$ is required

texts:
A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required.
Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$,
both are accepting, $Q_1$ is initial, there is a move under $0$ from $Q_1$ to $Q_1$, a move under $1$ from $Q_1$ to $Q_2$ and finally a move from $Q_2$ to $Q_2$ under $1$.


texts: A problem X is NP-hard if every problem in NP can be reduced to X. But every problem in NP has a polynomial time verification algorithm, so then does that not mean that I can also verify X in polynomial time because every NP problem is reducible to X? Can someone please explain or give an example.


texts: Reference introductory books or articles to Game Semantics

texts:
Where can I find introductory books, articles, notes or slides on Game Semantics?

I have searched a lot on the internet but I'm not satisfied by the material I found. It either is too informal, or it assumes too much knowledge of/attitude to other kind of semantics, and it's hard to follow for a beginner.

Ideally the material shouldn't have any prerequisites, except a little of game theory and few concepts of semantics.

Examples of the material that I've found are:

Notes on Game Semantics: These are quite good, but they lack a bit of formalism at the beginning and I find some explanations or examples difficult to follow.
Tutorial on Game Semantics: Slides; they lack oral explanations.


texts: I can verify solutions to my problem in polynomial time, how would a non-deterministic algorithm arrive to a solution if it always takes $2^n$ bits?

texts:
Decision Problem: Given integers as inputs for $K$ and $M$. Is the sum of $2^k$ + $M$ a $prime$?
Verifier
m = int(input('Enter integer for M: '))
sum_of_2**K+M=int(input('enter the sum of 2^k+m: '))

if AKS.sum_of_2**K+M == True:

  # Powers of 2 can be verified in O(N) time
  # make sure there is all 0-bits after the 1st ONE-bit

  # Use difference to verify problem

  if sum_of_2**K+M - (M) is a power_of_2:
    OUTPUT Solution Verified

The powers of 2 have approximately $2^n$ digits. Consider $2^k$ where $K$ = 100000. Compare the amount of digits in $K$ to the amount of digits in it's solution! Also take note that the powers of 2 have $2^n$ bits as its 0-bit Unary essentially for the exponent $n$.
Question
How would a non-deterministic machine solve this problem in polynomial time?


texts: Direct conversion from regular expression to MSO

texts:
A language $L \subseteq \Sigma^*$ can be described by a regular expression iff it can be defined by a formula in monadic second order with words as structure $(\{0, \dots, n-1\}, <, (P_a)_{a \in \Sigma})$. The proof I know is an indirection construction over automata, i.e. we show that DFAs and regular expressions / formulas are equivalently powerful.

However, I am interested in a direct transformation process to make analysis of complexity properties easier. If I remember correctly, there is a construction based on the inductive nature of regular expressions and formulas, but I cannot find it. Just a link to a paper presenting these two algorithms (reg.exp. to MSO and back) would suffice for me.


texts: SAT solvers that can compute prime implicants and/or minimization

texts:
I'm looking into computing the prime implicants of a Boolean function. I have found many different algorithms in the literature, many of them relying on SAT solvers. However, I have not been able to find a SAT solver that already provides this feature. Are there any?
Similarly, are there any SAT solvers/SMT solvers/related tools out there that work efficiently in practice for minimizing Boolean formulas?


texts: Help interpreting this deadlock question

texts:
I have this assignment question but I am a bit unsure how to go about answering it. The question is as follows and accompanied by the image below:

Three processes are competing for six resources labelled A to F as shown
below.

Using a resource allocation graph, show the possibility of a deadlock in
the implementation above.

I know how to do the graph but what I am struggling to understand is, do I take the Release(); methods into consideration or only the Get(); methods. And also, would P0() access resources A, B and C first or will each process run simultaneously meaning P0() access resource A, P1() access resource D and P2() access resource C, and then the second set of Get() methods are requested simultaneously? Lastly it does not specify how many instances (dots) are in each resource, is there any indication as to how to determine/go about working with this? As soon as I can clear up these misunderstandings I can draw the diagram


texts: All paths of less than a given length in a directed graph between couple of nodes

texts:
Counting all possible paths, or all possible paths with a given length, between a couple of nodes in a directed or undirected graph is a classical problem. Attention should be given to what all means, due to the possibles cycles.

This question is slightly different, or at least I think.

INPUT:  Be G a directed graph. G can have cycles and also selfconnected nodes. Let A(G) be the adjacency matrix of G (with a 1 in Gi,j if there's a link going from i to j and a 0 otherwise). Define T and B two subset of nodes of G, possibly with void intersection.

OUTCOME: A list of all paths of length at most k going from one node in T to one node in B. Paths can contain multiple time the same edges, as long as they go from the source node to the target node in strictly less than k+1 steps.

QUESTION: I would like to know which algorithm perform best in this task. I'm trying to develop a possible answer based on the fact that the n-th power of the adjacency matrix, if computed symbolically (with a different variable for each entry instead of a 1), keep traks of all this paths (and it reduces to the counting of paths if computed numerically with 1 in the entries). But I really don't know if this is the fastest way of doing the task (probably not).

CAVEAT: I'm not asking for the counting problem, nor for the shortest paths, the length of a path is defined as the number of edges used (counting the repetition). I'm using R, but if you prefer think about it in any other language! I'm really sorry if the question was already posed and solved. Thank you for the kind help!

additional info: I tried a matrix power series approach (A^3 gives all the 3 long path, ...) and dfs / bfs. I think the latter two are far from optimality as they don' take into account that I'm working on sets of sources and targets, and hence do a lot of redundant work...


texts: What does Dijkstra's algorithm become, when you replace path cost with edge cost?

texts:
Consider a variant of Dijkstra's algorithm (for a directed graph) where nodes are visited not in order of total path cost, but in order of incoming edge cost. (Assume here that all edge costs are positive and distinct). Nodes are never re-visited. What can we say about the resultant paths?
One obvious result is that they are minimax paths (that is, the maximum edge cost of a path found is the minimum of that of any path to that goal). But the condition seems to be stronger than that: An edge pair will tend to have a large number of tied minimax paths (since only one edge really constrains the path), but this algorithm seems to robustly prefer paths with fewer high-cost edges.
What I think is going on is, the edge costs for the found path from a to b, if sorted in descending order, produce a sequence that is the lexicographic minimum over all paths from a to b. In a sense, it's more "strongly" minimax, with ties broken by the second-highest-cost edge, and so on. But I can't prove this to myself, even informally.
Is this a known algorithm? Does it actually have that property?


texts: Checking if the graph provided by a distance matrix is a tree

texts:
I came across this problem in an online judge: We are given a distance matrix consisting of $N$ rows and columns. The $i$th line of $j$th row is the distance between node $i$ and $j$ (not necessarily neighbors). The task is to find out if there exists a tree satisfying the given distance matrix or not. The only constraint is $1 \le N \le 2000$ and the time limit is 1 second.

Some sample test cases for clarity:

Input:
N = 3
0 2 7
2 0 9
7 9 0
Output:
True

Input:
N = 3
0 1 1
1 0 1
1 1 0
Output:
False

I couldn't find an answer that is feasible for implementing in a short period of time (this is kind of important for me as I participate in competitions sometimes). An idea came to my mind is that to take the distance matrix as it was an adjacency matrix and compute MST, and then run Dijkstra's SSSP from each vertex through this MST and generate a new distance matrix and finally compare if the initial distance matrix and the matrix we found are identical. I know that this solution is not efficient nor logical (and also I'm not sure if this would work correctly) and that's why I'm posting here for an answer. I can tell that the solution involves DSU (Disjoint Set Union) and DFS from the problem tags but it just didn't come to my mind.


texts: Is there any bitwise multiplication algorithm that is sub O(n^2)?

texts:
The following program implements a simple algorithm for binary multiplication:

-- Numbers as infinite streams of bits, least significant bits first
data Bits
  = O Bits
  | I Bits

-- Increments a number
suc :: Bits -> Bits
suc (O xs) = I xs
suc (I xs) = O (suc xs)

-- Adds two numbers
add :: Bits -> Bits -> Bits
add (O xs) (O ys) =      (O (add xs ys))
add (O xs) (I ys) =      (I (add xs ys))
add (I xs) (O ys) =      (I (add xs ys))
add (I xs) (I ys) = (suc (I (add xs ys)))

-- Multiplies two numbers
mul :: Bits -> Bits -> Bits
mul (O xs) ys =        (O (mul xs ys))
mul (I xs) ys = add ys (O (mul xs ys))

(The complete program can be seen here.)

This algorithm, although simple, has O(N^2) complexity. Are there similarly simple algorithms with lower complexities?


texts:
To store say integers (positive), we prefer to use red black BSTs. I have never seen a explicit use of a trie anywhere to store numbers.
I believe we can convert numbers to string and store them in tries for fast retrieval.
Is it a bad idea to use tries?
We don't use them because they are hard to code and there are libraries for BSTs or is there some other reason?


texts: Algorithm suggestion to order data with specific condition

texts:
Suppose, we want to rearrange all possible $n$-bit binary strings (i.e., we have $2^{n}-1$ possible strings) in a 1-D array $X$; given that stings with smaller hamming distance should be placed as much closely as possible. Is there any algorithm to find the best solution efficiently?
Note: I belive, for this problem, we need to maximize $\sum_\limits{i=0}^{2^{n}-2}\sum\limits_{j=i+1}^{2^{n}-1}\bigg(d(X[i],X[j]) \times |i-j|\bigg)$. Here, $d(X[i],X[j])$ is the hamming distance between $i$th and $j$th element of the array $X$.


texts:
I'm struggling in understanding how to recognize irregular languages.
I know what the meaning of irregular language but still find it hard to recognize.
Are there any tips to recognize better and to know which is regular and which not?
For example, which of the following is not regular, and what gives you the intuition?
\begin{align}
L_1 &= \{a^ib^i \mid i \ge 0 \} \\
L_2 &= \{a^ib^j \mid i,j \ge 0\} \\
L_3 &= \{a^nb^nc^md^m \mid n,m \ge 1 \}
\end{align}


texts: Sorting an unordered pile of items into drawers with minimal drawer movements

texts:
A while ago, I was doing my laundry late at night.  When I brought my laundry back to my dorm, I started to put it away.

My wardrobe is set up as follows:

My drawers are categorized by the type of clothing they hold, and I'm very particular about that; this means I can't put t-shirts in my pants drawer (otherwise I'll be too flustered over it to sleep).  Of course, I know this categorization, and I know which drawer is which even in the dark.
I have $N$ pieces of clean laundry, and $M$ drawers arranged vertically (with the drawer at the top being $D_0$)
I can open and close drawers as I see fit, but if drawer $D_i$ is open, I can't put any clothes in drawer $D_{i+1}$ (because it's blocked by $D_i$).
All of my drawers are already closed when I enter the room.
When I finish, I have to close all open drawers.

Considerate gentleman that I am, I don't want to wake up my roommate (this was a college dorm, so we slept in the same room).  I resolved to not turn on the lights and make as little noise as possible.

This means that I have to put away my laundry under the following constraints:

I can't see into my laundry bag, so I only know what I grab as soon as I pull it out.
Opening and closing a drawer makes noise.  Pulling items out of my laundry bag, or actually putting them in the drawer, does not.
I can only put away one item of clothing at a time; I can't fold like clothes and put them in piles (and then put those piles away) because the floor's too dirty and there's no space on the furniture within reach of me.
I can put an item of clothing back in my bag and take out another, but the one I take out next could be the one I had just put back in (remember, I have no control over what I pull out of the bag).

Given this, I have three questions:

How can I put my laundry away while opening and closing the drawers as few times as possible?
Has anyone else thought of this problem or something similar?
Does this problem have any practical applications?


texts: Is it possible to prove EQTM is undecidable by the Rice theorem?

texts:
Given the problem $EQ_{TM} = \{ \langle M_1,  M_2\rangle \mid M_1 \text{ and } M_2 \text{ are } TM, L_{M_1} = L_{M_2}\}$, is it possible to prove that this is undecidable by using (a variant of) Rice theorem?

I have proven this problem by reduction to $E_{TM}$, but was wondering if it was easier to do with Rice.


texts: What is an efficient algorithm to see if a set of nodes ultimately depend on a certain node in a DAG?

texts:
Hopefully this question makes sense. Basically, given a DAG, a set of nodes A, and another node b, I'd like to know if node b is an ancestor of any of the nodes in A in that graph.

This is my current implementation:

def is_ancestor(graph, A, b):
    nodes_visited = set()
    frontier = list(A)
    while frontier:
        node = frontier.pop()
        if node not in nodes_visited:
            if node == b:
                return False
            nodes_visited.add(node)
            # add immediate predecessors to the frontier
            frontier.extend(graph.predecessors_iter(node))
    return True

However, in the worst case this is O(|graph|), and this would be a function I would need to call very often, so I'm wondering if I'm missing anything that might make this run faster, preferably without requiring quadratic memory, because then I could just store everything and get O(1).


texts: Optimization problem vs decision problem - reduction

texts:
Assume we have an optimization problem with function $f$ to maximize.

Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to the optimization problem: calculate the optimal solution and check if it is $\ge k$.

Now, I was wondering, is it always possible to do the reduction (in polynomial time) the other way around?

For an example consider MAX-SAT: to reduce the optimization problem to the decision problem we can do a binary search in the integer range from 0 to the number of clauses. At each stoppage $k$ we check, with the decision problem solver, if there is a solution with $\ge k$.


texts: Help in understanding 'reasonable' encoding of inputs

texts:
I read that a reasonable encoding of inputs is one where the length of the encoding is no more than a polynomial of the 'natural representation' of the input. For instance, binary encodings are reasonable, but unary encodings are not.

But say that the input is a graph, and its natural representation is a vertex and edge list. Suppose that the graph has $k$ vertices. If I use unary to encode, the overall length of the input referring to the vertex list would be $O(k^2)$, i.e. $=|1^1|+|1^2|+|1^3|+...+|1^k|$. Isn't this unary encoding still a polynomial with respect to the number of vertices of the graph (which is $k$)?

What am I missing here?


texts: Image registration algorithms for images with varying distances

texts:
I have two cameras side by side. I'd like to register two images taken from each camera. I think global transformation will not work for this issue since changes of distances between two images for the closer objects are significantly higher. What should I do in this case? I tried to read some papers but I am not sure which one is the perfect match for me. Do you have any suggestions such as "read this paper", "apply this algorithm", "know this and that" etc.

edit: I forgot to say that the project is real-time. Image registration will be implemented in the GPU.


texts: Removing edges from a fully connected weighted graph

texts:
Given a fully connected graph $G(V,E)$ with associated edge weights and a set of constraints specifying distance $D(V_i, V_j) < M_{ij}$, where $\left\{V_{i..j}\right\} ⊂ V$, how can I go about finding the smallest subset graph $G'(V', E')$ such that none of the constraints are violated?

In other words, find the smallest subset of the graph such that the distance between a given set of vertices does not exceed some constant.


texts: Is there a way to store an arbitrarily big BigInt in a bit sequence, only later to convert it into a standard BigInt structure?

texts:
I am trying to imagine a way of encoding a BigInt into a bit stream, so that it is literally just a sequence of bits. Then upon decoding this bit stream, you would generate the standard BigInt sort of data structure (array of small integers with a sign). How could you encode the BigInt as a sequence of bits, and how would you decode it? I don't see how to properly perform the bitwise manipulations or how to encode an arbitrary number in bits larger than 32 or 64. If a language is required then I would be doing this in JavaScript.
For instance, this takes bytes and converts it into a single bit stream:
function arrayOfBytesTo32Int(map) {
  return map[0] << 24
    | map[1] << 16
    | map[2] << 8
    | map[3]
}

How would you do that same sort of thing for arbitrarily long bit sequences?


texts: Can a non-regular language be made regular via concatenation when they don't share characters?

texts:
So this is a follow-on question to my other question (Can we make a non-regular language regular via concatentation?).

Given the following,

$L = \{0^n1^m2^m \mid n>1, m>1\}$

$A = \{0^n \mid n>1\}$

$B = \{1^m2^m \mid m>1\}$

Is $L$ in fact just $A$ and $B$ concatenated (I believe it is, but I want to verify that)?

Further, does proving $B$ non-regular prove that $L$ is non-regular since they don't share characters?


texts: Linear/affine lifetimes without subtyping

texts: Are there any type systems similar to rust that don't depend on subtyping ? Can we express that one value must be consumed or dropped before another? For instance if I had an array of huge values on the heap and I would like to operate on a single item using a reference to it, the compiler would need to be sure I had finished with the reference before I could mutate or drop the parent array.


texts: Minimum-area enclosing equilateral triangle for a point set

texts:
We have $n$ points $P$ in $2D$ space. We want to find an enclosing  equilateral triangle $\Delta$ with minimum area in $O(n\log n)$. Suppose  We know that at least on side of $\Delta$ covers at least two points of $P$.
My first attempt: I try to compute convex hull of points, then I select three points of the hull and construct a triangle with minimum area, touching these points. The running time becomes $O(n^3)$ because we need to check each combination of three points from $O(n)$ points - so it's inefficient.
Second try: I think this problem have is related with lover envelope, but I can't formulate it in dual manner. Any help to solve this problem in $O(n\log n)$ will be appreciated.


texts: How does SARSA handle episode termination

texts:
When applied to domains that are episodic and have a "final" state but no final action, like a game, how does SARSA update the Q-values?

e.g. A game agent would receive this series:
$$
    s_0,a_0,r_0,s_1,a_1,r_1,.....s_{N-1},a_{N-1},r_{N-1},s_N
$$
Based on the traditional definition, which updates the current Q-value using the *future Q-value, shouldn't it be impossible to apply SARSA, since there's no future action to use when plugging in the $(s_t, a_t, r_t, s_{t+1}, a_{t+1})$ values?


texts: How is it possible for a problem to be NP-Complete under polylog-time reductions?

texts:
I have no source for this, but I've heard people offhandedly mention problems that are NP Complete under polylog reductions (I think SAT was one of them).

This confuses me - it seems to me that this is a violation of the nondetermistic time hierarchy.  If SAT (or whatever) can be solved in $NTIME(n^c)$ for some $c$, and any $NP$-problem can be reduced to SAT in $O(n^k)$ time for some fixed $k$, then it seems that we can solve any $NP$ problem in $O(n^{c+k})$ nondetermistic time -- obviously false.

So, it seems to me that SAT (or whatever) can only be NP-Complete under polytime reductions, and that for any polynomial, we can find a problem whose reduction to SAT takes more than that polynomial amount of time.

What am I missing?


texts: Generating numbers to be averaged efficiently

texts:
During my research, I had encountered the following issue. Consider the equation
$$\sum_{k=1}^K\alpha_k P_k = P$$

where $\sum_{k=1}^K\alpha_k=1$, $\alpha_k > 0$, $P_k > 0, P>0$.

So you are given $\{\alpha_k\}$, $K$ and $P$. The task is to generate randomly $\{P_k\}$ such that the above equation is satisfied. I am looking for an efficient way to generate these numbers.

My strategy

I have one method. Basically, we generate $K$ distinct uniform numbers between $(0,1)$. Call them $\{b_k\}$. Then we compute $\sum_{k=1}^K\alpha_k b_k = B$. Now the sequence $\{\frac{b_kP}{B}\}$ is the desired sequence.

However, if you observe, using this method, $P_k$ can never exceed $P$ and in my work, I require some of the values to exceed $P$. E.g. if $\alpha_1=0.5, \alpha_2=0.5$, even $(2P,0)$ is a valid solution.

Is there a way to generate these numbers so as to circumvent this issue?

Update:
Given $\{\alpha_k\}$, it follows that $P_k \leq P/\alpha_{\min}$.
Note: The above counter example is not valid. Apparently the algorithm works fine.


texts: Trying to convert algorithm from recursive to iterative

texts:
I have this algorithm to sum binary tree branches from leftmost branch to rightmost one, so the solution is an array of sums:
class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function branchSums(root) {
  let sums = [];
    _doSum(root, 0, sums);
    return sums;
}

function _doSum(root, currentSum, sums) {
    if (!root) {
        return;
    }
    if (!root.left && !root.right) {
        sums.push(currentSum + root.value);
    } else {
        _doSum(root.left, currentSum + root.value, sums);
        _doSum(root.right, currentSum + root.value, sums);
    }
}

It's working fine, but now I'm trying to solve the same problem in an iterative fashion.
I have tried this:
function branchSums(root) {
  let stack = [];
    let sums = [];
    let sum = 0;
    stack.push(root);
    while (stack.length > 0) {
        const node = stack.pop();
        sum += node.value;
        if (!node.right && !node.left) {
            sums.push(sum);
            sum -= node.value;
            continue;
        }
        if (node.right) {
            stack.push(node.right);
        }
        if (node.left) {
            stack.push(node.left);
        }
    }
    return sums;
}

But it doesn't work. After debugging, I have noticed that the error is because I'm only decreasing sum when I reach a leaf node, after pushing to sums. But I need to do it also when depth changes. I don't know how to explain it.
Is it possible to wirte an iterative solution to this problem?


texts: Amortized time complexity of append on a dynamic array that resizes according to geometric base 1.25?

texts:
I'm trying to prove that the amortized time complexity of appending to a dynamic array that resizes in accordance with capacity = $N$ to $N+\lceil{\frac{N}{4}}\rceil$ is $O(1)$. I'm assuming that resizing an array from $x$ to $y$ "costs" $y-x$ primitive operations.

Here is my reasoning so far. Assume that an array is full when it has a capacity $k$. Upon the next append call, the array resizes to $k+\lceil{\frac{k}{4}}\rceil$. Thus there are $\lceil{\frac{k}{4}}\rceil$ new cells in which elements can be appended to. This array will be full when all new $\lceil{\frac{k}{4}}\rceil$ cells are filled. After this takes place, another resize event will have to occur. This resize event changes the capacity as follows:
$$k+\left\lceil{\frac{k}{4}}\right\rceil \to \bigg(k+\left\lceil{\frac{k}{4}}\right\rceil\bigg) + \left\lceil{\frac{k+\lceil{\frac{k}{4}}\rceil}{4}}\right\rceil$$

So, in the $\lceil{\frac{k}{4}}\rceil$ between resizing events, we need to "save" up primitive operations. For append to $O(1)$, we need to "save" a constant real number $b$ of primitive operations per cell, i.e. $b$ must not depend on $k$. Mathematically, we want to show:
$$\exists b \in\mathbb{N}\; s.t. \; \forall k\in\mathbb{N}, \;\; b\left\lceil{\frac{k}{4}}\right\rceil\ge \left\lceil{\frac{k+\lceil{\frac{k}{4}}\rceil}{4}}\right\rceil $$

We note a couple of things. Firstly, $\lceil{x}\rceil = x+\theta$ for some $\theta\in [0,1)$. Secondly, $b$ and the ceilings in the above inequality are all positive, so the inequality holds:

$$\iff b\bigg(\frac{k}{4}+\theta_1\bigg)\ge \frac{k+\frac{k}{4}+\theta_1}{4}+\theta_2$$
$$\iff bk + 4b\theta_1 \ge \frac{5k}{4}+\theta_1 +4\theta_2$$
$$\iff b \ge \frac{1}{k}\bigg(\theta_1-4b\theta_1+4\theta_2\bigg)+ \frac{5}{4}$$

The problem I have is this suggests that $b$ need not be that large at all, some I'm pretty sure I've done something wrong intuitively.


texts: Why does SAT-UNSAT $\in NP \implies NP = coNP$

texts:
I was reading this post about the DP completeness of the problem SAT-UNSAT (both are well defined in this post). The answer added a note at the end that states the class complexity DP differs from NP, unless NP = coNP.
I fail to see why.
I searched and I came across multiples posts such at this one and that one that prove that if SAT-UNSAT is in coNP, then NP = coNP. But unless the fact that SAT-UNSAT $\in NP \implies$ SAT-UNSAT $\in coNP$ (which I do not see), then those proofs are not exactly what would help me. The same goes for this question, I would need SAT-UNSAT $\in coNP$.
Question : Considering the first question (and the answer associated), if the problem SAT-UNSAT $\in NP$, why does NP = coNP.
My take :
Well, I can see that the problem SAT-UNSAT is NP-hard and coNP-hard. If SAT-UNSAT $\in NP$, then SAT-UNSAT is NP-complete. This implies things such that the problem UNSAT (which is coNP-complete) is NP-hard since we can reduce UNSAT to SAT-UNSAT which is NP-complete. That's all I got and that doesn't really help.
I'd appreciate any clarification on the subject. Thanks to you all


texts: Can String be a subtype of Character in a programming language?

texts: Could a programming language be designed so that there is an inheritance relationship between string and character (both of which are native types), such that the inheritance alone resolves the use of an arbitrary binary operator between the two types: <string> @ <character>; coercion and overloading cannot be used. My intuition is that string would be a subtype of character because a string may be composed of characters, and all basic methods defined for a character work with a string. As a subtype, string could have very specific functionaity such as a length method or attribute. On the other hand, I can see how it might make sense that string is the supertype and character is the subtype. Namely, a character could be thought of as a string of length 1. Which interpretation is correct, or at least which interpretation is more sound?


texts: Finding the most efficient paths to cover an area from multiple starting locations

texts:
I'm looking to design an algorithm for a problem I have, and was hoping there may be someone that could provide some insight on where to start.

In my picture above, the grid is the area they needs to be explored by the circles. Each cell is a unit of work, so currently I've got lat/lng coordinates for the exact center of each of the grid cells. The goal is to visit every cell in the grid. Circles must start in their home locations, and must end in their home locations.

In my current algorithm (SUPER simple, but it works), I'm simply taking the center coordinates of each of those grid cells, splitting them up into lists (number of lists = number of circles), then adding the home location to the beginning and end of each of those lists. As you can imagine, this leads to some very inefficient routes.

The grid areas can vary wildly, as well as the location of the "Homes", so an algorithm that simply determines the best possible route, by minimizing the total distance travelled for each circle to complete the entire task, is what I'm looking for.

I'm thinking this may be some sort of variant of Dijkstra's algorithm, where the distances between all the different center points as well as the home locations are all calculated before determining the lowest possible solution. Where my understanding kind of falls apart is Dijkstra's algorithm is shortest path from A to B, whereas this algorithm is more of a "shortest path from A to A, given that an individual circle can complete X many units of work, with the end goal of the entire grid area being completed".

With this algorithm, I'm picturing that it would take into account the return trip, since its part of the calculated distance I'm trying to minimize, so it would try to complete units of work that are on the way back home.

Any insight or guidance is greatly appreciated. Thank you.


texts: Kleene Star regex question, sed behavior?

texts:
Kleene Star with 'sed' is behaving as expected for me, with exception of a case where the input pattern is "ab" and the regex is "b*".  Does anyone know why this regex is not being matched against the pattern space?

This is the failure case:

$ printf "ab\n" | sed -En 's/b*// p' | od -t c
0000000   a   b  \n
0000003

SOLUTION
'b*' expects 0 or more occurrences of 'b'.  If 0 occurrences of 'b' the empty string $\epsilon$ is expected.  In the string above, 'ab' is preceded by the empty string and it is matched in the beginning of "ab" pattern space as follows:

printf "ab\n" | sed -En 's/b*/x/ p' | od -t c
0000000   x   a   b  \n

where 'x' is substituted for empty string.

In order to match b, I had to use the following form:

Kleene Plus in addition to Kleene Star as follows:

 printf "ab\n" | sed -En 's/(.*)(b+)(.*)/\1/ p' | od -t a
0000000   a  nl

This case, without Kleene Star, behaves as expected:

$ printf "ab\n" | sed -En 's/b// p' | od -t c
0000000   a  \n
0000002

I'm trying to match the 'b' and replace it with nothing.

The pattern space is 'ab', beginning of line is unspecified, so I'm confused why /b*/ would not match a pattern of zero or more 'b's, in this case 'b'.

Oddly, this case works with the '.' prepended to the '*':

# fails to match
$ printf "abb\n" | sed -En 's/b*// p' | od -t c
0000000   a   b   b  \n
0000004
# matches with .* !
$ printf "abb\n" | sed -En 's/b.*// p' | od -t c
0000000   a  \n
0000002

Kleene Star matches zero or more occurrences of the preceding alphabet (in this case a single character).

By definition:

$V^0 = \{\epsilon\}$

$V^1 = V$

$\forall i ( (i \gt 0) \land (V^{i + 1} = \{ wv : w \in V^i \land v \in V )\} $

Therefore $V^0 = \{ \epsilon\}$, $V^1 = \{ \epsilon \cdot b\}$, $V^2 = \{ \epsilon \cdot b \cdot b\}$.

$V^* = \bigcup\limits_{i\ge0} V^i = V^0 \cup V^1 \cup ...$ which I have specified by /b*/.

The following cases agree with my understanding of sed and Kleene Star:

# * : matches 0 or more occurances
# no match
$ printf "a\n" | sed -En 's/b*// p' | od -t c
0000000   a  \n
0000002

# match a
printf "a\n" | sed -En 's/a*// p' | od -t c
0000000  \n
0000001

# match a
printf "ab\n" | sed -En 's/a*// p' | od -t c
0000000   b  \n
0000002

# match aa
printf "aab\n" | sed -En 's/a*// p' | od -t c
0000000   b  \n
0000002

I tested using BSD and GNU sed, both have the same results.

Thanks!


texts: Understanding an algorithm for the gas station problem

texts:
In the gas station problem we are given $n$ cities $\{ 0, \ldots, n-1 \}$ and roads between them. Each road has length and each city defines price of the fuel. One unit of road costs one unit of fuel. Our goal is to go from a source to a destination in the cheapest possible way. Our tank is limited by some value.

I try to understand the algorithm, so I manually wrote down steps to calculate the solution. Unfortunately I got stuck - at some point there are no edges to consider, I don't know why, maybe I'm missing something.

Example:
road:
0 ----------- 1 ------------ 2 -------------- 3
(it doesn't have to be that simple, it could be any graph i.e. there could be roads between 0->2, 0->3, 1->3 etc.)

Source: 0, Destination: 3, Tank: 10 units
Fuel prices: 0: 10 units, 1: 10 units, 2: 20 units, 3: 12 units
Lengths: 0->1: 9 units, 1->2: 1 unit, 2->3: 7 units
Optimal solution: fill 9 units at 0 and 8 units at 1. Total cost then is 170 units (9 * 10 + 8 * 10).

So I tried to calculate it as shown here (paragraph 2.2)

GV[u] is defined as:
GV[u] = { TankCapacity - length[w][u] | w in Cities and fuelPrice[w] < fuelPrice[v] and length[w][u] <= TankCapacity } U {0}

so in my case:
GV[0] = {0}
GV[1] = {0}
GV[2] = {0, 3, 9}
GV[3] = {0}

D(u,g) - minimum cost to get from u to t starting with g units of fuel in tank:
D(t,0) = 0, otherwise:
D(u,g) = min (foreach length[u][v] <= TankCapacity)
         {
           D(v,0) + (length[u][v] - g) * fuelPrice[u]                             : if  fuelPrice[v] <= fuelPrice[u] and g <= length[u][v]
           D(v, TankCapacity - length[u][v]) + (TankCapacity - g) * fuelPrice[u]  : if  fuelPrice[v] > fuelPrice[u]
         }

so in my case:
D(0,0) = min { D(1,0) + 9*10 }  - D(0,0) should contain minimum cost from 0->3
D(1,0) = min { D(2,9) + 10*10 } - in OPT we should tank here only 8 units :(
D(2,9) = min { ??? - no edges which follows the condition from the reccurence

Nevertheless D(0,0) = 90 + 100 + smth, so it's already too much.

To achieve the optimal solution algorithm should calculate D(2,7) because the optimal route is:
(0,0) -> (1,0) -> (2, 7) -> (3, 0) [(v, g): v - city, g - fuel in tank].
If we look at G[2] there is no "7", so algorithm doesn't even assume to calculate D(2,7),
so how can it return optimal solutions?

Recurrence from the document doesn't seem to work or what's more likely I do something wrong.

Could anybody help me with this?


texts: Implementing regular expression matching using Brzozowski derivatives

texts:
I have been taking a language theory class, and we learned about Brzozowski derivatives recently. At class it occurred to me that they could be used to implement a simple regular expression matcher. If you take the derivative of a regular expression with respect to a given string and the resulting expression matches the empty string ($\varepsilon$), then the original expression matches the string used in the derivative:

$$
w \text{ matches } e  \Leftrightarrow \varepsilon \text{ matches } D_w(e)
$$

I did a web search and, as expected, other people had the same idea before. There is an implementation here and another one here. They are short and simple.

Is this used in practice anywhere? I'm not sure, but I believe that most regular expression matchers are implemented using either finite automata or  backtracking algorithms (like Perl regular expressions). Why is this the case? Is the technique I mentioned too slow? Is it missing functionalities? Does anybody know what the complexity of regular expression matching using derivatives is?


texts:
I am given a set of pairs of dates and would like to extract features I can put into an machine learning algorithm.

Thus far I have already written two different metrics, however I didn't find much literature on that topic. I know there is a lot of literature about on computing the distance or similarity of strings. There are even python packages offering various algorithm. However I have not found something similar for dates.

Does someone know, if something like this exists? If yes, what and where?

Specifics for the dates: They have the form: "DD-MM-YYYY" with the letters representing each a digit in 0 to 9, or being left empty. For example: 0-0-0 would be as valid as 3-12-2017


texts: Solve recurrence relation that depends on depth of recursion

texts:
The specific problem I'm working on is the puzzle presented in this video. For those who don't want to watch the video, my summary of the puzzle is:

A frog is sitting on the edge of a pond facing the opposite bank. In front of the frog, running along the pond's diameter, is a line of $N$ lilypads. This is a very athletic frog: it is able in a single leap to land on any of the $N$ lilypads in the pond or on the opposite bank (for a total of $N + 1$ possible destinations). The frog first considers all $N+1$ positions in front of it, chooses one randomly with uniform probability, and then jumps to this location. It then repeats the process of choosing a new random position from those remaining in front of it (never jumping backwards). This goes on until the frog eventually reaches the opposite bank.
The puzzle is twofold: First, if $N=10$, what is the expectation value of the number of jumps the frog will take to reach the other side of the pond? Second, find an explicit formula (NOT a recurrence relation!) for the expectation value of the number of jumps in general for $N$ lilypads.

(It's a great puzzle; if you haven't yet given it a shot, I'd highly recommend doing so before reading any possible spoilers in the rest of this post!).
To attempt this puzzle, I first calculated the first few terms by hand and then tried to generalize my result. I eventually came up with a recursive algorithm for the expectation value $f$:
def f(n, depth=1):
    if n == 0:
        return depth
    else:
        return (n * f(n - 1, depth) + f(n - 1, depth + 1)) / (n + 1)

However, the second part of the puzzle explicitly disallows recurrence relations as solutions, so I am trying to un-roll/solve the recurrence relation. There are already several questions on strategies for solving recurrence relations (see this and this), but none I can find on solving recurrence relations which are dependent on the depth of recursion. Any help on how to do this is appreciated.


texts: Condition of square root algorithm (Newton's method)

texts:
I am reading the book Algorithm 4th and see this square root algorithm using Newton's method (java sample code):

public static double sqrt(double c)
{
    if (c < 0) return Double.NaN;
    double err = 1e-15;
    double t = c;
    while (Math.abs(t - c/t) > err * t)
        t = (c/t + t) / 2.0;
    return t;
}

I wanna know what's the rule behind the while loop condition,

Math.abs(t - c/t) > err * t

Why is it (|t-c/t|)/t > err?
For exmaple, can't the condition simply be  |t-c/t| > err?

I know that, t-c/t -> 0 when loop count -> ∞.

I remember that I encouter many "manually choose approximation condition" when learn Probability Theory. But now I totally forget it. So any related,basic background knowledge explanation or introduction would be much appreciated.

Newton's method from my original math textbook:

$$ a>0, x_0>0, \\ \{X_n\}: X_n = \frac{1}{2}(x_{n-1} + \frac{a}{x_{n-1}}) \\ \lim{x_n} = \sqrt{a}\ $$


texts:
How do we test the following function?

bits(bitstring, i, j)

which returns a copy of the substring from i to j of some bitstring.

Consider the fixed 32-bit value:

bitstring=0x12345678

We could manually pre-determine the correct return values for ~500 different combinations of i and j. But this only covers 0x12345678.

There are 232 ≈ 4 billion different strings like 0x12345678.

Even for a non-exhaustive test,  manually recording the constants we expect to get from any combination of (bitstring, i, j) does not seem like the best solution.

I imagine we can use the fact that bit strings map to unsigned integers and do some arithmetic to compare the return value of bits to bitstring.

Any help with vocabulary or classifying this validation problem would be appreciated, too.

Technical side note: My uncertainty lies in whether the bit manipulations are being performed correctly, since the bit substring does not necessarily begin or end on a byte boundary.

Another note: After a few edits I have realized the important question here is what are the different ways we can check that one bit string is a substring of another? But the original question has a broader scope so I will leave it as it is.


texts: Red-black tree trinode restructuring after insertion and deletion

texts:
When performing an insertion/deletion on a red-black tree, how can be argued or proved that it requires at most one/two trinode restructuring(s) respectively?
My thoughts so far were: after inserting a node and two consecutive red nodes exist along a path from root to a leaf a restructuring is done followed by recoloring, resulting in a red-black tree. Does this mean that after inserting a node there can only exist at most one double red problem in the tree which requires one restructuring to fix it?


texts: Confused by proof of correctness of Majority

texts:
I have been studying a streaming algorithm to determine if there is a majority element in a stream. But am confused by a proof for it.
The algorithm works as follows. You keep one counter $c$ and a store for one item called $a^*$. When a new item arrives, first you check if $c == 0$. If so you set $c=1$ and $a^*$ stores the arriving item. Otherwise, if $c>0$ and the arriving item is the same as $a^*$ you increment $c$ or decrement $c$ if not.
If there is a majority element then it will be stored in $a^*$ at the end.
In the notes from http://www.cs.toronto.edu/~bor/2420f17/L11.pdf there is a proof of this fact (called simpler proof).

I can see that if there is a majority item then $c'$ will be positive at the end of the stream.  But:

How do we know that $a^*$ will hold the majority item at the end?
Does $c'$ being positive imply that $c$ will be positive too?


texts: How AC-3 (Arc Consistency) with backtracking works

texts:
I'm trying to understand the AC-3 algorithm with backtracking to implement a Rat in Maze algorithm via C++. So far I've base on these links I have a basic idea in terms of AC-3 and how to implement this link_1, link_2, link_3, link_4.
So... so far as I understand the AC-3 algorithm it's working something like this as an overview explication. So correct me if I'm wrong.
How I understand that AC-3 work:
function AC-3(variable, domain, constrains):
   while constrains not empty (example: variable != 1, domain.size() > variable, etc)
         bool condition = constrains[0](variable, domain)
         constrains.pop()
         if condition then
              domain.remove(variable)

So basically I'm just removing the elements from the domain if they match the constraints. I found it odd, and I think I didn't understand it right because I don't see the point of this AC-3 then. Also, I'm trying to understand it and its purpose in terms of simple examples first, all the documentation that I found so far it's way too complicated or abstract. I just want to understand it's core in terms of simplicity use.
My question:
If I did understand the AC-3 right, then how can I solve the Rat in Maze problem? What I mean by that is...
So far as I understand I will take my domain (in my case the matrix in which the rat is moving)
and I will then check that each cell it meats my constraints (which so far as I understand the problem is just one constrain, that been either or not the cell it's empty or 0) or I can also add as constrains if the next cell in which my rat can move is or not out of the boundary of the matrix. If any of my cells don't meet my constraints I will remove them from the matrix.
If I understand that right my matrix actually in the case of AC-3 should be a directed graph and I found some ways to convert a 2d matrix into a directed graph. But why do I need an AC-3 in the first place?
I mean what the difference in terms of functionality or performance between a breadth-first search or just a simple backtracking and AC-3 + backtracking I see this just as an unnecessary step to find the path between rat and cheese.
So to summarize my question, can anyone helps me to understand how can I use AC-3 + backtracking to solve Rate in Maze problem. Or at least could you give me some references from where I can get a clear idea of AC-3?


texts: Is there way to compare computing power used in two blockchains when every one of them is using different mathematical function as a Proof-of-Work?

texts:
If I am a Bitcoin node, I can evaluate two blockchains in terms of each one consisting of more Terahashes than the other and thus deduct which one is the "correct" one. There is impartial source of consensus - hashes done. But what if I had two blockchains, each one making a different function, e.g. one is Bitcoin and making SHA-256 and another is making other random computation. Could I impartially deduct which "chain" has the most computation power spent even if in those two chains the "way" this computation power is spent is different? Is there common impartial denominator then?
Or, to make it even more interesting, if a blockchain had self-amending possibility like Tezos, and in a certain point of time it reached a consensus to change it's Proof-of-Work method to e.g. more memory-hard (in order to discontinue usic ASICs) then could a node that wasn't connected to the network before that change somehow use a common denominator of computing power (now not necessarily Hashes used) to evaluate the right chain by checking how much computing power was spent on chain both before the amendment (when e.g. SHA-256 was used) and after change (when some new Proof-of-Work is used)?


texts: Eigenvector centrality of graph with negative weights

texts: Eigenvector centrality can be calculated for graphs with non-negative weights for the edges. Is  there any version of it which can be used for graphs with negative weights?


texts: Best way to merge different trees to single data structure?

texts:
I trained an XGBoost model that classifies 50 different classes, therefore it generates a lot of boosters (trees). Also, I wrote a script that turns trained model to C++ code and it works really fast because every tree is simply nested if-else statement. What I noticed is that many trees are similar and I was wondering if there is a way to merge all of those trees into one tree or maybe to reduce number of trees by merging some of them? Maybe even convert everything to some different data structure?

This is what dump looks like:

booster[0]:
0:['::'] yes=2,no=1
    1:['=>'] yes=4,no=3
        3:['es'] yes=8,no=7
            7:['ef'] yes=10,no=9
                9:leaf=-0.0339584
                10:leaf=0.0612883
            8:leaf=-0.0484913
        4:leaf=0.0358804
    2:[';\s'] yes=6,no=5
        5:leaf=0.373993
        6:leaf=-0.0376609
booster[1]:
0:['</'] yes=2,no=1
    1:['h\n'] yes=4,no=3
        3:[':v'] yes=8,no=7
            7:leaf=-0.0487989
            8:leaf=0.0200258
        4:['_t'] yes=10,no=9
            9:leaf=-0.03375
            10:leaf=0.172536
    2:['*\s'] yes=6,no=5
        5:leaf=0.354577
        6:leaf=0.0165644

// etc.. boosters go on and on...

Let me explain how it works by going through booster[0].
First we check if sample we're classyfing contains '::'; if yes we jump to branch 2. There we check if sample contains ';\s' and if yes, we jump to branch 6. Branch 6 is leaf so we just take value -0.0376609 and we add it to probability that sample is class '0'.

We do the same for booster[1] and it gives us probability that sample is of class '1'. It goes on and on for all 50 classes and then the process is repeated for many iterations that gives us 50 * num_iterations of trees. It comes up around 10k of trees.

Anyone has any idea if there is a better way of representing these trees so our classification works even faster?


texts: What does the actual parameter A[i] refer to in this example of call by value-result?

texts:
From Programming Languages: Principles and Paradigms, by Maurizio Gabbrielli, Simone Martini

void fiefoo (valueresult int x, valueresult int y) {
x = x+1;
y = 1;
}
...
int i = 1;
int[] A = new int[5];
A[1]=4;
fiefoo(i,A[i]);

  we are to execute fiefoo with parameters passed by value-result. On
  termination, we will have A[1] with value 1 and i with value
  2, while the rest of the array A has not been touched.

Why is it A[1] instead of A[2] whose value is 1?

My thought is that when returning from the function fiefoo, x's value 2 is assigned to i, so A[i] is evaluated to be A[2], and y's value 1 is assigned to A[i].

My thought is according to what the book says

  It should be clear that, as in call by value, the following questions
  about evaluation order in call by return must be answered. If
  there is more than one result parameter, in which order (for example,
  from left to right) should the corresponding “backward assignment”
  from the actual to formal be performed?

  Finally, when is the actual parameter’s l-value determined? It is
  reasonable to determine it both when the function is called and when
  it terminates. We can construct an example which gives different
  results if the l-value of the actual is determined at call time or
  when the procedure terminates.

Thanks.