texts: Optimal path through a DAG with sparsely available edge weights

texts:
I would like to create a plot of certain metrics that are collected at revisions of a software system.  The objective of the software engineers is to minimize those metrics.

For version control, the engineers are using Git, so there is a DAG of commits (revisions).  However, the metrics are only available for a subset of those commits.  It is not feasible to collect metrics for all of the commits.

What path finding algorithm would yield the most relevant data to plot a "downward trend" in the metrics that is minimally erratic, resolving ties in favor of the path with maximum detail?

Definitions

erraticism: The sum of the absolute differences between the metric at each pair of adjacent commits along the path.  Example: For path A-B-C where A=10, B=7, C=5, the erraticism is (10 - 7) + (7 - 5) = 3 + 2 = 5.

detail: The quantity of commits that have known metrics along a path.  Example: for path D-E-F where the metric at D and F is known, but E is unknown, the detail is 2.

Scenarios to illustrate objective function

Metrics available for all paths

Say that D is the most recent commit. D has two parents, B and C.  B and C share a single parent A.

  10 -> A
       / \
11 -> B   C <- 7
       \ /
   5 -> D

In this scenario, all four commits have metrics available. In this case, the least "erratic" path is preferred.

If A=10, B=11, C=7, and D=5, the path A-C-D is preferred.

Metrics available for only one competing path

If the metric is unavailable for commit C, then the path A-B-D is preferred.

  10 -> A
       / \
11 -> B   C <- unknown
       \ /
   5 -> D

Metrics available for no competing paths

If the metrics are only known for commits A and D, then it doesn't matter whether we traverse through commit B or commit C, because neither commit will be displayed on the plot.  The plot will display path A-D.

       10 -> A
            / \
unknown -> B   C <- unknown
            \ /
        5 -> D

Competing paths of various lengths

Maximum detail

This is where it gets complicated.

Generally it is preferable to have more detail in the plot.  So in the following example, path A-C-E-F is preferred:

       10 -> A
            / \
      7 -> B   C <- 8
           |   |
unknown -> D   E <- 6
            \ /
        5 -> F

Path A-B-D-F has erraticism=5, detail=3.  Path A-C-E-F has erraticism=5, detail=4.  Detail breaks the tie, and path A-C-E-F is selected.

Minimally erratic

However, we do not prefer the path with greater detail when that path is more erratic than the alternative.  In this case, path A-B-F is preferred:

       10 -> A
            / \
      7 -> B   C <- 11
           |   |
unknown -> D   E <- 6
            \ /
        5 -> F

Path A-B-D-F has erraticism=5, detail=3.  Path A-C-E-F has erraticism=7, detail=4. Path A-B-D-F is selected.


texts: Is a Karp–Levin reduction a Levin reduction?

texts:
My understanding is that Karp many-one reductions are more general than Levin many-one reductions, and that Levin many-one reductions must allow for the number of certificates for a problem $A$ reduced to $B$ to be recovered from a single oracle call giving the number of certificates for $B$.

So, what exactly is a Karp–Levin reduction? Quoting the paper "Witness Encryption and its Applications",

  We now formally describe our encryption systems. For building them we will assume the existence of a witness encryption scheme for an NP-Complete language $L$ for which there exists a Karp–Levin reduction. We focus on presenting the constructions in this section and defer the proofs to Appendix A.

Other instances of "Karp–Levin" reductions can easily be found elsewhere.

From slide 11 of this presentation on PCPs by Mario Szegedy, it seems like a Karp–Levin many-one reduction is just a Levin many-one reduction. Is that correct?

Update: To explain why I am uncertain about Yuval Filmus' answer below, and why I'm asking this question, quoting from page 17-4 of the "Hardness of Approximation" chapter of the Handbook of Approximation Algorithms and Metaheuristics, a chapter written by Mario Szegedy (a Godel prize winner for his contributions to the PCP theorem),

  Reduction is perhaps the most useful concept in algorithm design. Interesting, it also turns out to be the most useful tool in proving computational hardness [21-23]. When a problem $A$ Cook reduces to $B$, the hardness of $B$ follows form the hardness of $A$. Unfortunately, Cook reduction does not ensure that if $A$ is hard to approximate then $B$ is hard to approximate. For reducing hardness of approximation new definitions are necessary.

  Let $F_1(x, y)$ and $F_2(x', y')$ be functions that are optimized for y and y' (maximized or minimized in an arbitrary combination). Let $OPT_1(x)$ and $OPT_2(x')$ be the corresponding optimums. A Karp–Levin reduction involves two maps:

  a polynomial-time map $f$ to transform instances $x$ of $OPT_1$ into instances $x' = f(x)$ of $OPT_2$ [Instance Transformation];
  a polynomial-time map $g$ to transform (input, witness) pairs $(x', y')$ of $OPT_2$ into witnesses $y$ of $OPT_1$ [Witness Transformation];

  Observe that the witness transformation goes from $OPT_2$ to $OPT_1$. Let $opt_1 = OPT_1(x)$, $opt_2 = OPT_2(f(x))$, $appr_1 = F_1(x, g(f(x),y'))$, and $appr_2 = F_2(f(x),y')$.

So Yuval Filmus' answer below appears to only cover the "[Instance Transformation]" part of a Karp–Levin reduction, and not the "[Witness Transformation]" part, which seems to be interpretable as a way to recover certificates from some problem $A$ in $NP$ reduced to $B$ in $NP$ provided the number of certificates for $B$.

Am I off the mark here?  And how is a Karp–Levin reduction different from a Levin reduction?

If there is non-standard terminology, or if definitions are supposed to be "understood" depending on whether one is talking about reductions among perhaps counting problems where witness transformations matter, please understand that this is intimidating for someone coming from outside of computer science!  People's patience here is very much appreciated.


texts: How to find the symmetry group of a polynomial

texts:
Say I have a polynomial in $n$ variables of maximum degree $m$. I define its symmetry group to be the subgroup of the permutation group which fixes the polynomial when it acts on the variables. Example: $x^2+y^2+z$ has the subgroup $\langle(x,y)\rangle$. Given such a polynomial, what is the best way to find such a polynomial.

Usage Note: I need this algorithm to terminate in "a short amount of time" for $n$ about 15, $m$ about 10. Short being, I guess, less than 1 minute.

Partial progress: If all I do is test particular elements of $S_n$, this problem is basically intractable as I need roughly $(n-2)!$ tests. Current implementation does basic checks such as the following. In my example $x$ cannot map to $z$ because $z^2$ terms do not exist. In this way we can eliminate much larger fractions of permutations. However, since $S_n$ is so large, this approach is still too slow.


texts: Are tiny point-symmetric grids of two Pentominos impossible to solve?

texts:
The game of Pentomino is a tiling puzzle game played on a grid. A Pentomino piece is a two dimensional shape of five non-diagonally connected tiles. There are exactly 12 unique pieces (ignoring rotation/reflection). The goal of the game is to fill the board with the available pieces without overlapping.

This question concerns point-symmetric boards (not necessarily rectangular) of 10 spaces, i.e. with room for exactly two pieces.

Filling such a board is, of course, trivial when using the same piece twice.

Using the Y-piece twice on a point-symmetric hourglass board:
####
 O#
OOOO

However, it seems impossible to do when using two different pieces. Is this true? How could this be proved?

This is not the case for larger boards or larger pieces (more than 5 tiles). Of course, the standard 6x10 board using 12 Pentomino pieces is also a counter example when using more than two pieces. Small counter examples:

Three 5-tile Pentomino pieces (V, P and L pieces) on a 3x5 grid:
vvvpp
vLppp
vLLLL

The 5-tile pieces P, T and F on an oval-shaped point-symmetric grid.
 ppTF
pppTFFF
  TTTF

Two 8-tile pieces on a 4x4 grid:
####
#OOO
#OOO
##OO


texts: An example of a computable problem that is not in P

texts: I am trying to find a simple example of a problem that is computable but not in P, I know very well that it would be enough to get one in NEXTIME-complete however the problems that I find in this set are very artificial


texts: Writing a constructive proof for closure of a regular language under homomorphism

texts: I've spend the last few days searching online for an example of a constructive proof of regular languages being closed under homomorphism, but I have not seen one. I am mostly unsure of how to show the construction of a DFA for a homomorphism in general. For example, if I were to create a mapping between an alphabet $A$ and the binary alphabet $B$, how would I go about showing the construction of a DFA to recognize this mapping? I would really appreciate any help, whether with an actual example, or just an idea of what I would need to do.


texts:
I've taken an introductory database course where like many good database courses, they taught relational algebra, including $\theta$-joins. However, I've recently read E. F. Codd's 1970 paper, A Relational Model of Data for Large Shared Databanks, and the concept of $\theta$-joins is nowhere to be found. He does use the symbol  $\theta$ in the paper in section 2.2 though, but to refer to something much more general than joins.

In fact, Natural Joins are even defined slightly differently then the definition I'm familiar with. It requires that the original relations be completely recoverable from the joined relation.

So my question is when/in what paper/by who was the modern notion of the $\theta$-join introduced that is often taught by universities?

(A link to Wikipedia's definition of a $\theta$-join, similar to the one I learned in my course)


texts: What does the number of bit of microprocessor mean?

texts: Intel 8085 is a 8 bit processor whereas 8086 is a 16 bit processor,what does the number of bit specify?


texts: How to draw flowchart for if condition within nested loops?

texts:
Please find my program logic as below :

Please find my flowchart for the above program logic as below:

My superior asked me correct the flowchart. But I couldn't identify my mistakes.

Please guide me to correct my flowchart in correct manner. Thanks in advance.


texts: Complexity of maximization of entropy of Hamming distance of bitstrings

texts:
We have a set of possible "key"s $S$ represented by bitstrings of length $k$. In other words, $S$ contains an arbitrary subset of all bitstrings of length $k$. For example, when $k=3$, it can be $S = \{001, 010, 011, 000, 111\}$. I would like to find a "guess", which maximizes the Hamming distance of itself and the possible keys, assuming that the keys in $S$ are drawn with equal possibility. For instance, say the guess is $g = 001$, then the Hamming distances are $H(001, 001) = 0$, $H(001, 010) = 2$, $H(001, 011) = 1$, $H(001, 000) = 1$, and $H(001, 111) = 2$. It follows that the entropy is $E = -\left[\frac{1}{5}\log(\frac{1}{5})+\frac{2}{5}\log(\frac{2}{5})+\frac{2}{5}\log(\frac{2}{5})\right]$. A superior guess would be $g = 000$ or $g = 111$, which actually maximizes the entropy. There will be multiple guesses that maximize the entropy, and finding any of them is enough.

I actually have two related questions:

How hard is it to find an optimal guess that maximizes the entropy? (In terms of N/NP/NPC/NPH, etc)
How hard is it to find the maximum entropy?

I have previously posted a related question on math.SE, and a comment suggested that full enumeration is probably the best algorithm I can get. The problem sounds even harder than the $k$-partition problem, so I guess it is NP-complete or NP-hard.


texts: How can I find data to compare with my work's results?

texts: My Masters thesis is on task graph scheduling for multi core processors. I have developed a new task clustering and scheduling algorithm. I wanted to know about how can I find data to compare it with my work? Me and my supervisor have tried contacting the authors of a few similar works for data but none of them is sharing their data. Is there any benchmark for comparing such types of problems?


texts: How does KMV (k minimum value) perform set intersection better than hyperloglog?

texts:
In this paper, the author seems to suggest that theta sketches(a variant of kmv) outperforms hyperloglog in cardinality estimation on the intersection of n way streams.

Set Intersection. multiKMV can be tweaked in a natural way to handle set intersection and other set operations.

I am having a hard time understanding how intersection on kmv set can perform intersection accurately

The way I understand it, KMV can be describe by the following

Given a stream of number $x = [x_1, .... x_n]$ if we hash each number in $x$ and produce $h = [hash(x_1).....hash(x_n)]$

KMV attempts to represents and capture the characteristic of the stream by storing $k$ minimum value of $h$

The intersection of 2 streams is basically the naive intersection of 2 kmv set.

However this can't be true because if its true the operation is lossy, and probably cannot sustain more than a couple intersection without loosing its accuracy on estimating cardinality.

Can someone point me a direction on how kmv achieve accurate cardinality estimation of 2 or more streams?


texts: Prove L = L(R) based on a regular expression

texts:
I'm given the following language:

L = {w∈{0,1}* | w ends in 010 and contains 011}

The task is to find a regular expression R that describes this language and prove L = L(R).

I have found the regular expression : ^([011])[01]*010$.

But have no idea how to prove L=L(R)?


texts: Support Vector Machines vs K-Nearest Neighbors

texts:
Let's say we have trained a Support Vector Machine with a Gaussian Kernel. When we feed our model an example, it classifies it based on its similarity to landmarks (distance to examples in our training set).

If instead our model is a K-Nearest Neighbors algorithm, with k=size of the training set, it classifies a given example based on its distance to examples in our training set (similarity to landmarks).

I know the math behind SVM and KNN is different, but on a high level, are they both employing the same idea? What am I missing if I think they are doing the same thing in different ways?


texts: Are recursively enumerable languages closed under shuffle?

texts:
For languages $L_1, L_2$ over some alphabet $\Sigma$, we define

$$ \textit{Shuffle}(L_1, L_2) =  \{a_1b_1a_2b_2 \cdots a_nb_n : n \geq 1 \wedge a_1, \ldots , a_n \in L_1 \setminus \{ \varepsilon \} \wedge b_1, \ldots , b_n \in L2 \setminus \{ \varepsilon\}\}$$

I think that RE are closed under shuffle, I tried to use the multitape TM model with 3 tapes, one for the input, one for the $a_1, \ldots , a_n \in L_1 \setminus \{ \varepsilon \}$, and the last one for $b_1, \ldots , b_n \in L_2 \setminus \{ \varepsilon \}$, but the problem is that $a_1, \ldots , a_n, b_1, . . . , b_n$ are words from the languages,not symbols, so we do not know when $a_1$ ends and $b_1$ begins,
any suggestions for proving closure under shuffle ?


texts: Subset Sum algorithm, why not split by 3+?

texts:
A classic algorithm for Subset Sum is to first split the input into two sets (A and B), evaluate the sums of the subsets of each, sort those sums for each A and B, then cleverly filter whole ranges of combinations by comparing the highest and lowest sums from each A and B.

Do we know (or does someone have an argument) why not to split the input into 3 or more sets rather than two?

I presume that there would be a combinatorial proof that doing so would either require the same or more number of steps.


texts:
I have an upcoming CS course in uni that uses C and I want to get ahead a little bit this Christmas break but I'm having a hard time figuring out where I can actually code using C. My school uses this compiler called Seashell but it's not available until the term starts.

I've looked at visual studio but I only see C++, and I've heard of stuff like Vim, GCC, but I'm pretty new to CS and I don't know what any of that really means...

Help?


texts:
$S -> AB$

$A -> aA / epsilon$

$B ->aBb / epsilon$

What is the class of language generated by the above grammar ?

I think that it generates $a^* a^n b^n |  n>=0$ so it should be regular as regular is concatenated with DCFL which is able generate epsilon. But the answer is CFL .

I think that answer would be CFL if n would have been greater than equal to 1 and not 0

Can someone please point out my mistake ?


texts: Are there regular languages between every two non-regular languages?

texts:
I have a question regarding regular languages. Given that $L_1$ and $L_2$ are non-regular languages, can a regular language $L$ exist so it is a subset of $L_2$ and $L_1$ subset of $L$?

To be more specific:

$\qquad L_1 \subset L \subset L_2$

for $L_1, L_2$ non-regular Languages.


texts: Lamport's distributed mutual exclusion: wait-chain order clock

texts:
Regarding Lamport's mutual exclusion... Where messages are exchanged in the following sequence between nodes S, G1, and G2. G1 and G2 are the members of the group.

(for this, lets just assume that a1 is an acknowledgment of m1; a2 is an acknowledgment of m2)

S sends m1 to G1
S sends m1 to G2
G2 sends a1 to S
S sends m2 to G1
S sends m2 to G2
G2 sends a2 to S
G1 sends a2 to S
G1 sends a1 to S

Let the Lamport clocks at each node start at: S: 5, G1: 2, G2: 1...

In which order and at what times are m1 and m2 delivered and how would you list the sequence of messages with their times?

I appreciate any replies (NOTE: this is just an example problem - as I am actually trying to figure out how a calculated result looks like).


texts: Show that function is not turing-computable?

texts:
We have two functions:

$f_1: \mathbb{N}\rightarrow \mathbb{N} \quad $
$f_2: \mathbb{N}\rightarrow \mathbb{N}$

By definition $f_1$ is turing-computable while $f_2$ is not.

Then we define a third funtion $g(n) = f_1(n) + f_2(n)$.

I want to show that $g(n)$ is not turing-computable:

So first assume that $g(n)$ is computable.

That means I can write it like this:

$f_2(n) = g(n)-f_1(n)$

Which (is where I'm not sure) means that $f_2$ can be computed which is a contradiction to the definition, which results that $f_2$ is not turing-computable.


texts: Why is $\{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ an inherently ambiguous language?

texts:
I came across a very hard interview question in last month’s Ph.D. entrance exam. It was asking which one of the languages is inherently ambiguous. Short answer says 2). Why is the language in 2) an inherently ambiguous language?

1) $L = \{a^n b^{2n} c: n\geq 0\} \cup \{a^{2n} b^n d: n\geq 0\}$

2) $L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$

3) $L = \{a^n b a^{2n}: n \geq 0\} \cup \{a^{2n} b a^n: n\geq 0\}$

4) $L = \{\omega: \omega \in \{a,b\}^*: \omega \text{ does not have substring $baba$}\} \cup \{\omega : \omega \in \{a,b\}^*: \omega \text{ does not have substring $abab$} \}$


texts:
Given $k$ numbers $A_1 \leq A_2 \leq ... \leq A_k$ such that $\sum\limits_{i=1}^k A_i = k(2k + 1)$ is there an assignment of numbers $i_1, i_2, ... , i_{2k}$ which is a permutation of $1, 2, ... , 2k$ such that

$i_1 + i_2 \leq A_1\\ i_3 + i_4 \leq A_2\\ .\\.\\.\\ i_{2k-1} + i_{2k} \leq A_k$

?

I cannot find an efficient algorithm and that solves this problem. It seems to be a combinatorial problem. I was unable to find a similar NP-Complete problem. Does this problem look like a known NP-Complete problem or can it be solved with a polynomial algorithm?


texts: How to determine minimum word length of regular language

texts:
Given a regular language $L$ and a regular expression $r$ with $L=L(r)$. Is it possible to determine the minimum length of words of $L(r)$ by the structure of $r$?

A straightforward example:

Let's say we have a regular expression $r=aac^*aa$, then $L(R) = \{aaaa, aacaa, aaccaa, \dots, aac^naa\}$. To determine the minimal length I would erase everything that is postfixed with $*$, leaving $r'=aaaa$. Now I would count the concatenations and add 1, which would yield in this example, not unsurprisingly, a minimum length of 4.

Is there a general approach to do this for more complex expressions?

Sidenote: I need to achieve this without the help of automata.


texts:
When attempting to find the following loop invariant for:

int log(int x)
{
  int i = 0;
  int j = x;
  while (j > 1) {
    j = j / 2;
    i = i + 1;
  }
  return i;
}

I come up with the following loop invariant:

j >= 0 and i >= 0 must be true before, during and after each iteration.

For case where x >= 0, upon checking the condition the first time, the loop invariant holds true.

For case where any input x >= 0, the invariant loop also holds true.

However, going through some of the other loop invariant reads found here on stackexchange, I am convinced that this is not the loop invariant for this particular algorithm as it does not solve the problem we are trying to accomplish. More specifically, this loop invariant holds true, but without pointing out explicitly that this is a logarithm calculator, the loop invariant is invalid.

I am unsure of the loop invariant I provided as I don't even think it is sufficient for proving out the correctness of the algorithm. How would I create an effective loop invariant that will satisfy the simple algorithm above?


texts:
I have the following problem. The problem can be formulated in three different ways

Given sets $B_{-n},\ldots,B_n \subset \{1,\ldots,m\}$.

Find $i,j \in \{-n,\ldots,n\}$ with $|i| \neq |j|$ and $i,j \neq 0$ that satisfy $B_i \cap B_j = \emptyset$

"Invert" the sets $B_i$

Define $A_k=\{i: k\in B_i \}$. $A_1, \ldots, A_m \subset \{-n,\ldots,n\}$.

Find $i,j \in \{-n,\ldots,n\}$ with $|i| \neq |j|$ and $i,j \neq 0$ that satisfy the property $\{i,j\} \not\subset A_k$ for all $k=1,\ldots,m$

Relation instead of set of sets

Define relation $R\subset\{1,\ldots,m\}\times\{-n,\ldots,n\}$ with $kRi \equiv k \in B_i$.

Find $i,j \in \{-n,\ldots,n\}$ with $|i| \neq |j|$ and $i,j \neq 0$ that satisfy the property for no $k=1,\ldots,m: kRi \land kRj$

Naive Algorithm

As far as I can tell, the 3 problems are the same thing viewed from slightly different perspectives. One possible algorithm would be to iterate through all pairs $(i,j)$ and check if the condition is satisfied. This algorithm has runtime of $\mathcal{O}(n^2\cdot f(m,n))$ with the runtime $f$ of the check if the pair satisfies the property.

Specifically for the first case:
Assuming the sets are implemented sorted lists the intersection can be checked to be empty in $\mathcal{O}(m)$ time via a simple mergesort-like scan.

Question

Is there an algorithm for this problem that solves it in $\mathcal{o}(n^2)$ time? (maybe with some tradeoff in the $m$ component)


texts: Cover points with minimal number of spheres of fixed radius

texts:
I have a set of k n-dimensional points:

P1(x11, x12, ..., x1n), P2(x21, x22, ..., x2n), ..., Pk(xk1, xk2, ..., xkn).

A distance D(Pa, Pb) is defined between any two points, which satisfy usual properties:

D(Pa, Pb) >= 0
D(Pa, Pb) = 0 <=> Pa = Pb
D(Pa, Pb) = D(Pb, Pa)
D(Pa, Pc) ≤ D(Pa, Pb) + D(Pb, Pc)

What is the algorithm to find areas in which these points aggregate?
More specifically, given a radius R find the smallest set β of n-dimensional "balls" B(C) such that every point lies inside at least one of the balls:

ⱯPa ƎB(C) ∈ β => D(Pa, C) ≤ R

There is definitely more than one solution (in most cases a ball could be moved a little so that it would still contain the points) and probably there is something else I am missing. But I need an algorithm that would provide at least one solution.

Example:

If
k = 5, n = 2, R = 2, D(Pa, Pb) = euclidean distance on a plane
P1(0,0), P2(1,1), P3(4.5, 4), P4(-4, 1), P5(4,4),

Then
B1(0.5, 0.5) (contains first two points), B2(-4,1) (contains only 4th point), B3(4,4) (contains 3rd and 5th points)


texts: Set of $\mathsf{NP}$-hard languages closed under set inclusion?

texts:
As the title says, my question is whether the set of $\mathsf{NP}$-hard languages is closed under set inclusion, i.e. whether for any $\mathsf{NP}$-hard language $L$, all subsets of $L$ are also $\mathsf{NP}$-hard. This question is related since $\emptyset$ is not $\mathsf{NP}$-hard as there is nothing we could map "yes"-instances to and $\emptyset \subseteq L$ for all $\mathsf{NP}$-hard $L$.

However, what about non-trivial subsets, i.e. languages $L'$ of the form $\emptyset \neq L' \subsetneq L$ for $\mathsf{NP}$-hard $L$? We know that $\emptyset \neq 2SAT \subsetneq SAT$ and while $SAT$ is $\mathsf{NP}$-hard, $2SAT$ is in $\mathsf{P}$. This suggests to me that whether the set of $\mathsf{NP}$-hard is closed under "non-trivial" inclusions depends on whether $\mathsf{P} = \mathsf{NP}$. Am I mistaken here?

In one sentence, my question is this: is the set of $\mathsf{NP}$-hard languages closed under nontrivial set inclusion (1) assuming $\mathsf{P} = \mathsf{NP}$ and (2) assuming $\mathsf{P} \neq \mathsf{NP}$?


texts: Applying Expectation Maximization to coin toss examples

texts:
I've been self-studying the Expectation Maximization lately, and grabbed myself some simple examples in the process:

From here: There are three coins $c_0$, $c_1$ and $c_2$ with $p_0$, $p_1$ and $p_2$ the respective probability for landing on Head when tossed. Toss $c_0$. If the result is Head, toss $c_1$ three times, else toss $c_2$ three times. The observed data produced by $c_1$ and $c_2$ is like this: HHH, TTT, HHH, TTT, HHH. The hidden data is the result of $c_0$. Estimate $p_0$, $p_1$ and $p_2$.

And from here: There are two coins $c_A$ and $c_B$ with $p_A$ and $p_B$ being the respective probability for landing on Head when tossed. Each round, select one coin at random and toss it ten times; record the results. The observed data is the toss results provided by these two coins. However, we don't know which coin was selected for a particular round. Estimate $p_A$ and $p_B$.

While I can get the calculations, I can't relate the ways they are solved to the original EM theory. Specifically, during the M-Step of both examples, I don't see how they're maximizing anything. It just seems they are recalculating the parameters and somehow, the new parameters are better than the old ones. Moreover, the two E-Steps don't even look similar to each other, not to mention the original theory's E-Step.

So how exactly do these examples work?


texts: simple but (seemingly?) tricky recurrence

texts:
I'm cross-posting from math stack exchange after receiving no answers there.

I came across the following very simple recurrence-style expression but am having trouble solving it:
$$T(2n) \in \theta(T(n) \log(T(n)))$$
for sufficiently large $n \in \mathbb{N}$.

My first thought was to take the logarithm of both sides and apply the Master Theorem but the "$f(n)$" term unfortunately is not in the right form. Repeated expanding quickly yields a mess. Wolfram Alpha was no use.

Plugging in $T(n) = n^a$ makes the left side grow too slowly so $T$ must grow faster than any polynomial. But plugging in $T(n) = \exp(\log(n)^b)$, $b>1$, causes the left side to grow too fast so $T$ must grow more slowly. So it seems $T$ is super-polynomial but barely.

What approaches are viable for such an equation?


texts: How to calculate run time of insertion sort and Merge sort?

texts:
I am currently studying computer science and we were given assignment to implement two algorithm(Insertion sort and Merge sort) and run them in order to track their running times across different input arrays. And ask us to do: "Your task is to run each algorithm 3 times on 5 input arrays with 5, 50, 500, 5000, and 50000 random integers each, and report their running times both as a table and "n vs. time" plots"

I have already implemented algorithm but I am not sure how to calculate runtime of both algorithm. Any help would be appreciated. Thank you.


texts: Can a calculus have incremental copying and closed scopes?

texts:
A few days ago, I proposed the Abstract Calculus, a minimal untyped language that is very similar to the Lambda Calculus, except for the main difference that substitutions are O(1) (i.e., variables only occur once) and copying is an explicit, constant-time and incremental operation. Here is an example:

let (a & b) = (λx. λy. λz. y) in (a & b)
---------------------------------------- step 0
let (a & b) = (λy. λz. y) in (λx0. a) & (λx1. b)
------------------------------------------------ step 1
let (a & b) = (λz. y0 & y1) in (λx0. λy0. a) & (λx1. λy1. b)
------------------------------------------------------------ step 2
let (a & b) = y0 & y1 in (λx0. λy0. λz0. a) & (λx1. λy1. λz1. b)
---------------------------------------------------------------- step 3
(λx0. λy0. λz0. y0) & (λx1. λy1. λz1. y1)

Here, the let (a & b) = t in k syntax substitutes the occurrences of a and b in k by t, except it does so incrementally: notice how each lambda is pulled one by one.

There is a problem, though. Eventually, you'll try to pull a lambda which has a variable that is bound in t. That's occurs with y behind step 1. To solve that issue, whenever that happens, the bound variable y is replaced by y0 & y1, which are bound to each of the two copied lambdas, respectively. The problem with that is this requires us to abandon the notion of scopes, as, now, the bound variable of a λ can occur outside its own body (such as y0 and y1 behind step 2)!

Despite sounding bizarre, the language operates very well. You can represent the usual λ-encodings on it, implement recursive algorithms and it is compatible with the oracle-free fragment of the optimal reduction algorithm. Yet, some have questioned the absence of scopes. I've spent some time reasoning about this and couldn't find a way to have both things. In fact, it looks impossible. As a sanity check, I'd like to know if my reasoning makes sense.

Thus, my question is: is that possible? Can we have both incremental copying and closed scopes in a calculus?


texts: Why can't we just use preorder traversal to check if a tree is subtree of binary tree?

texts:
Is preorder traversal enough to check if a tree is subtree of a binary tree?

Are there any scenarios which I can miss if I use just the preorder traversal?

What other methods can be used to check if a tree is subtree?

Also, what happens if my binary tree contains non-unique values at nodes?


texts: Number of words in $\{pi,po\}^*$ of length at most 9

texts:
I have a language $L^*$ for $L = \{pi,po\}$ (I think pi counts as one letter and po also as one letter otherwise a max length of 9 is not possible).

The question is how many words I can make with $L^*$ where the maximum length is 9.

The answer is 31, but I do not know how it got calculated. How is this calculated?


texts: On the complexity analysis of weighted quick union in algorithms 4th edition by Sedgewick and Kevin Wayne

texts:
I've been studying Sedgewick's book and tried to count the number of array accesses for weighted quick union in the worst case. There is a diagram for this on the left side of page 229 in the fourth edition.

We start with 8 sites:

0 1 2 3 4 5 6 7

So N = 8

Then we form pairs:

For each of the pairs theres is one access to the array to compare , according the the find() method:
    private int find(int p)
     {
      while (p != id[p]) p = id[p];
      return p;
     }

And also there is one array access to actually put one site under the other. So 3 accesses for each one of the pairs we can form:

(N/2)*(3)

Now we go ahead and form the 4 sites trees. This in turn requires 2+1 accesses to the array in the find method, for each tree of two sites, and one access more to put one tree under the other:
(2 + 1) + (2 + 1) + 1 (number of array accesses to form one tree of 4 sites using two trees of two sites)

The above is done two times since we can form 2 trees of size 4:

(N/4)*(7)

And finally we join the two trees of size 4 to get one tree of size 8. This means doing 2 + 2 + 1 accesses on each tree inside the find method and one final access to put one tree under the other:

(N/8)(2+2+1+2+2+1+1) = (N/8)(11)

so the computational cost of forming a single tree (one component) is

C(N) = (N/2)3 + (N/4)(7) + (N/8)*(11)

In general it looks like the cost in the worst case scenario for getting to a single tree is :

Now the book says that this cost is O(N), which means that we should be able to prove that

C(N) < c.log(N)

However I can't see how this can be proven since there is an N multiplying inside the summation... I was wondering if someone here could point me in the right direction on this.

Thanks!


texts: $O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem

texts:
The prefix parity problem can be defined as follows. You are given a string $S$ of length $n$ and initially every character is $0$. Then you want to build a data structure that can support updates such as follows.

For a given $i$ change $S[i]$ to either $0$ or $1$
for a given $i$ find the parity of $S[1]+S[2]+...+S[i]$.

From the top of my head, there is a solution that can support these type of queries in $O(\log n)$ time, while only using linear space and linear preprocessing time to build the data structure. The idea is to build a complete binary search tree on top of the string where the leafs correspond to individual characters of $S$ and in every internal node we store the sum of all the characters that are leafs in the sub tree defined by that node. In this way we can trivially support both of the updates in $O(\log n)$ time.

However, I found a paper proving a lower bound for this problem, stating that you can not do better than $O(\frac{\log n}{\log \log n})$ for the updates, and I also found the following paper http://link.springer.com/chapter/10.1007%2F3-540-51542-9_5, and a direct link to the pdf, giving an algorithm achieving that bound, thus being optimal.

I would like to understand this algorithm however the explanation is like 1 page, and a lot of details are missing.

So I was wondering if there is any other source on this problem, because I find it very hard to find any, or is this is the only source available?

thank you in advance


texts:
A unary Turing Machine X has input alphabet Σ and tape alphabet Γ. We represent the blank symbol belonging to the tape alphabet as _ . Given as input 11111 X writes 1_1_11_1 as output.
Is the blank symbol discarded when considering the output, ie. is the input equivalent to the output in this case (regardless of how many blanks and where they are placed (1_11_11 = 1111_1 = ... = 11111)) or are they differnt?


texts: I'm thinking of doing a project on deepfake detection, but I'm not entirely sure if it is viable. Based on my understanding, how it works is that deepfake generation programs have a generative and discriminative network, and eventually after training, the systems reaches an equilibrium where the discriminative network can't detect real vs fake faces. I was thinking of building a CNN-LSTM architecture where I analyze not only single image frames, but image frames over time as well to better discern between real videos and deepfakes, but I'm not sure if this is viable? Any help or resources would be appreciated.


texts: Can I solve my decision problem in $O(n)$ time?

texts:
My algorithm solves a custom string problem but it loops twice making it $O(n^2)$ time. I'm asking here as I'm a beginner in self-learning algorithms.

Decision Problem: Given an input list $A$, can our target string $S$ be made from any of the elements of $A$?

If just one element does not exist in $A$ (which exists in $s$) then the algorithm returns false.

A = input_array
s = input_target_array

for i in s:
  if i in A:
    (all elements ∈ s) ∈ A
  else:
    break

(if any element ∈ s) ∉ A:
  return False
else:
  return True

Output

Enter your input for A and include spaces:
Enter letters WITH SPACES: "ab" "cd" "ac"
enter your input for s:
 "abxd"
^ False ^
 "abcd"
^ True ^

I'm looking for an algorithm that solves my made up decision problem faster than $O(n^2)$ time.

Question

Are there any methods that can be used from an algorithmic standpoint that would make this $O(n)$ time?


texts: Coverage problem (transmitter and receiver)

texts:
I try to solve the following coverage problem.

  There are $n$ transmitters with coverage area of 1km and $n$ receivers. Decide in $O(n\log n)$ that all receivers  are covered by any transmitter. All reveivers and transmiters are represented by their $x$ and $y$ coordinates.

The most advanced solution I can come with takes $O(n^2\log n)$. For every receiver sort all transmitter by it distance to this current receiver, then take the transmitter with shortest distance and this shortest distance should be within 0.5 km.

But the naive approach looks like much better in time complexity $O(n^2)$. Just compute all distance between all pairs of transmitter and receiver.

I am not sure if I can apply range-search algorithms in this  problem. For example kd-trees allow us to find such ranges, however I never saw an example, and I am not sure if there are kind of range-search for circles.

The given complexity $O(n\log n)$ assumes that the solution should be somehow similar to sorting.


texts: Question in coreset construction fro K-median clustering

texts:
I was reading Ke chen's paper about coreset construction for K-median clustering. In this paper, he assumed that $A$ is an $[α, β]$-bicriteria approximation for K-median clustering for some $α, β=O(1)$. I am wondering if the construction still work if $A$ is an arbitrary set of $αk$ centers?
Can anyone help prove the correctness of my suggestion?


texts: How does this recurrence relation fit the algorithm?

texts:
I have the following pseudo code:

Multiply(y,z)
1. if (z==0) return 0
2. else if (z is odd)
3.    then return (Multiply(2y, floor(z/2)) + y )
4. else return (Multiply(2y, floor(z/2)))

Towards analysing this procedure's runtime, this recurrence relation is given as answer:

$\qquad \displaystyle T(z) = \begin{cases} 0 & z=0 \\ T(z/2)+1 & z>0\end{cases}$

Why is $T(z)=0$ when $z=0$? Shouldn't it be $1$ for this case?

And, the $+1$ in $T(z/2)\mathbf{+1}$ is because the worst case is
(multiply(2y, floor(z/2)) + y (note the + y). Am I correct?


texts:
I am using method 3.3 described in Outlier Detection using Isolation Forest and Local Outlier
Factor .
It states:
Specify a dataset: $={_1, _2, ..., _}$.
Here,  is the sample number of . $_$ is an attribute in $$, and $_={_1,
_2, ..., _}.$ $_$
is a certain data value of the attribute $_$
.
The outlier coefficient of the attribute is defined as:

Here, $\bar{}$ is the mean of the attribute $_$ and $_$
is used to
measure the degree of dispersion of the attribute $_$
. Calculate
the outlier coefficient of each attribute in the dataset, and
get the outlier coefficient vector $_$ of the dataset, which is
recorded as:
$_ = _1, _2, ..., _n$
However, I do not understand what value to select for $x_j$.  What does a 'certain data value' mean in this case?


texts: Logarithmic reduction to another LOGSPACE problem

texts:
For words of the same length $u = u_1..u_n, v = v_1..v_n$ over an alphabet $A$ let $$u \circ v = u_1v_1...u_nv_n$$

Prove that if $L$ over $A \times A$ in in LOGSPACE then $$L' = \{uv : u \circ v \in L\}$$
is also in LOGSPACE

My solution:
We try to log-reduce $L'$ to $L$. So, I mean when a machine $M_L$ tries to read an input then reducing function $f$ gives another input.

Let $I$ be an input tape, word $w = uv = u_1..u_nv_1..v_n, |w| = 2n$ and $w$ starts at 0th cell.

Now, we define $f$:
$$
      f(i) = \left\{\begin{array}{lr}
        I[i/2] & \text{for } i \ even \\
        I[i/2+n] & \text{for } i \ odd
        \end{array}\right]
  $$

My doubts:

Is it ok?
I used in $f$ division. Is is possible in $LOGSPACE$?


texts: How does 'deforestation' remove 'trees' from a program?

texts:
I think understand how deforestation consumes and produces a list at the same time (from a fold and an unfold function -- see this good answer on CodeReview here), but when I compared that with the wikipedia entry on the technique it talked about 'removing trees' from a program.

I understand how a program can be parsed into a syntactic parse tree (is that right?), but what is the meaning of this use of deforestation for some kind of simplification (is it?) of programs? And how would I do it to my code?


texts: I am trying to show that $L^* \in P $ does not necessarily mean that $L \in P$. My idea was to find a language $L \notin P$ , apply $*$ operator and show that $L^* \in P$ by showing that $L^*$ can be decided with a polynomially bounded Turing machine, which will be a contradiction to $L^* \in P \Rightarrow L \in P$. However, I am having trouble in finding such $L$. Is there a trivial $L$ that I'm not thinking of? Or should change my method? Any help will be appreciated.


texts: Information Systems (IS) and Data Warehouse

texts:
I'm working on a research project about the adoption of DWH systems and doing some literature review I find many documents that refer to Information System. I tried to find the right definition of information system and if a data warehouse can be considered an IS or not, or is just a subset of it.
In the wider definition IS comprises also persons and policy and not only the technology (software or hardware). So it become complicated in my opinion to define it. From my personal work experience a DWH is an IS, the hearth of IS. But what about from the academic and computer science point of view?
If any system with data can be an IS, the extent is that an spreadsheet might be considered as an IS.


texts:
Let $T$ be a function.

Is it true that if $\exists f\forall n,m> 0.\\ \frac m {f(n)} \leq T(n,m)\leq m$

Then $\exists g.T(n,m)=\Theta(m\cdot g(n))$?

In words: is such a case, is there a function $g$ dependent only on $n$ that satisfies the above?

It looks to me true, but I am really stuck and don't know how to prove it rigorously.


texts: Best and worse case inputs for heap sort and quick sort?

texts:
So given a input of lets say 10 strings, what way can we input these so we get the best or worst case for these two given sorts?

Heap sort:
best case - nlogn
worst case - nlogn

Quick sort:
best case - nlogn
worst case - n^2

Where i get confused on these two is:

heap- Since the best and worst case are the same does it not matter the input order? The number of comparisons and assignments will always be the same? I imagine in a heap sort it may be the same since the real work is done in the insertion, but the sorting only uses the removal of the max/min heap? Is that why?

quick sort- This one I don't know for sure. I'm not sure what the best case and worst case situations are for this. If its a already sorted list of 10 strings for example wouldn't we always have to choose the same amount of pivots to get complete the recursive algorithm? Any help on this explanation would really help.

Thanks


texts: The question is quite straightforward: Why do Karnaugh maps work? What was the reasoning that led Maurice Karnaugh to come up with these maps? At first glance, it doesn't seem a natural approach, instead it feels somewhat arbitrary yet surprising that it works.


texts: CTL vs LTL - when a formula satisfy a model

texts:
I'm trying to understand the difference between LTL and CTL. In particular, i'm trying to understand when a model (a transition system eg. Kripke structure) satisfy a formula.
This is my point of view:

a model satisfy an LTL formula if an only if all its path starting
from its initial state  satisfy the formula
a model satisfy a CTL formula if and only if all of its state satisfy the formula. So i have to check that it is valid for all the
path (or for some path if there's a E quantifier) starting from each
state.  -

Is it correct? can someone help me?


texts: When directed graph is linear, return the nodes in order. Otherwise fail

texts:
The Problem

I have a set of edges (a, b), where a and b are nodes in a directed, acyclic graph (DAG).

The number of edges is guaranteed to be the number of nodes - 1.

I am looking for an algorithm that finds a sequence of nodes [n_1, ... n_n] so that the sequence contains all nodes in the graph, and that all edges (n_i, n_i+1) for 0 < i < n exist in edges.
If that sequence is not possible because the given set of edges is not equal to the set of edges required, then I need an error to be thrown.

Edit: the graph may have an arbitrary number of disconnected components. I obviously don't consider a graph with multiple disconnected components as linear.

Ideas so far

Note that I am checking that the number of edges is exactly the number of edges required for such a sequence to exist. As a result, the algorithm can fail when there are two edges that share a source or a destination. However, I still need to get that sequence.

I realize that topological sort returns a linear order of a directed graph, which satisfies my requirements. However, I still want to fail when the graph is not exactly linear like that, instead of getting a linear order anyways.

Maybe I can validate, then do a topological sort. But that sounds inefficient. I am also not sure about the formal names of things in this problem, so it's hard to simply look up an algorithm. I feel like I am missing some simple connection or trick here.

Could you provide me with an algorithm that accomplishes this? I'll take pseudocode or any language of your choice.


texts: Soundness and completeness w.r.t. programming languages

texts:
I'm studying programming languages (more specifically type systems) and came across a concept I couldn't quite wrap my head around: soundness and completeness.

I'm taking a class, and according to my instructor:

  Soundness is an analyzer's ability to prove the absence of errors. If a program is accepted by an analyzer, then the program is guaranteed to be safe.

  On the other hand, completeness is an analyzer's ability to prove the presence of errors. If a program is rejected, then that program has errors.

An example that I thought of is: If an analyzer is designed to accept all programs, does this mean the analyzer's system is sound but incomplete? I'm not quite sure if my reasoning is correct.

I've taken a look at other answers on this community:

Is there a relationship between “sound and complete” in logic and “type safety” in PLs? and

Example of Soundness & Completeness of Inference

but still am not quite sure how the logical concepts apply to type systems of programming languages.

Would anyone be kind enough to explain the differences?

Thank you.


texts: Are there models of type theory that allow the real numbers to be a type?

texts: Do there exist models of type theory that allow types to contain an uncountable number of inhabitants? Traditionally type theory seems to be swirled in with computable programs as constructive proofs so types are always countable. I want to know if we go outside computable programs do we get types that have an uncountable number of inhabitants?


texts: Analysis of komi values for increasing Go board sizes and agents strength

texts:
Komi is the additional number of points given to the non-starting player in the game of Go.

For 19x19 board, currently it is 6.5 under Japanese rules, 7.5 points under Chinese rules. In the past it was lower, even 2.5 points.

A question arises: what value it should be so that it is a fair game?
Draws allowed.

(This handles the unlikely to me case, in which Go is already fair, without komi. Then one would just discover that komi should be 0. So, I'm  not assuming that Go without komi is unfair)

The following idea came to my mind:

Let's take e.g. 5x5 board and an agent A. Let it self-play many games, plot the average of points won by the starting player in the end of the game, stop simulations when the value converges.

Do the same for 6x6, 7x7 board and so on up to 19x19 (or further).

So, for a given agent A, we will have a list of mean scores for a starting player on increasing board sizes, e.g. [25, 14.2, 9.6, ...], meaning that on a 5x5 board, on average, the first player wins with 25 points. On 6x6 board, on average, with 14.2 points, and so on. These could be the komi values.

Now, maybe the values in the list will be always decreasing. Maybe they converge to some value as the board size grows. Is it already described somewhere?

The values will probably depend on the agent A. Maybe one could also find a relationship between the strength of the agent A and the values in the list. E.g. maybe the stronger the agent, the values decrease slower.

So, one could start with a weak agent. See what values in the list it produces. Then, improve agent A (using e.g. some reinforcement learning algorithm or giving more time to the search) and produce another list of mean values. And so on.

Maybe the variance of results (or some other function) could be a nice measure of how far the current agent is from the optimal one (because the optimal one vs optimal one will always result in exactly one outcome, variance 0). So e.g. maybe agent who has scores vs himself in [-2; 2] is closer to the optimal one than the agent with scores in [-20; 20].

Say for the weakest agent A the list would be [25, 14.2, 9.6, ..., 6.6] and for the strongest agent A (ideally this agent would play optimally) [25, 18, 14, ... 8.2]. Now one knows that the sensible komi for 19x19 is in the range of 6.6 and 8.2.

My questions are:

1) Have you seen something similar done before? I would be happy to read. I've read Solving Go for Rectangular Boards, which solves Go up to 5x5. If such analysis wasn't described, I could do one out of curiosity.

2) Do you see some problems, refinements or other interesting things to check?


texts: how to interpret O(1) + O(2) + ... + O(n)?

texts:
in the book "Introduction to algorithms"(CLRS) page 49 it says:

  "The number of anonymous functions in an expression is understood to
  be equal to the number of times the asymptotic notation appears. For
  example, in the expression:

  $\sum_{i=1}^n O(i)$

  there is only a single anonymous function (a function of i). This
  expression is thus not the same as $O(1) + O(2) + O(3) + ... + O(n)$,
  which doesn’t really have a clean interpretation."

what is the difference between these 2 equitions and how should interpret each one??


texts: An argument for error accumulation during complex DFT

texts:
I am doing FFT-based multiplication of polynomials with integer coefficients (long integers, in fact). The coefficients have a maximum value of $BASE-1, \quad BASE \in \mathbb{n},\quad BASE > 1$.

I would like to put forward a formal argument that if we use complex DFT for computing a convolution on a physical machine, it will yield incorrect results at some transform length $n\in \mathbb{N}$.

What was easy to prove was the fact that at some big $n$ computing the convolution with DFT will not at all be possible, since, for example, the following difference of primitive roots modulo $n$:  $\omega_n^1 - \omega_n^2 \rightarrow 0$ when $n \rightarrow \infty$, and if we are restricted by some machine epsilon $\epsilon$, at some $n$ it will make the values indistinguishable and interpolation impossible.

But the boundary I've received using such an argument was way too big: only for $n=2^{60}$ I've received $\omega_n^1 - \omega_n^2$ that had both components, $Re$ and $Im$, less than representable by $double$-precision type. This certainly is a boundary, but not very practical one.

What I would like to show (if it is possible), is that much earlier than interpolation becomes theoretically impossible, the round-off errors will start to give wrong coefficients in the convolution, so that

$$a\cdot b \neq IDFT(DFT(a)\times DFT(b)),$$

where $DFT$ and $IDFT$ are algorithm implementations that I use to calculate the Fourier transform.

Maybe it is possible to make use of the fact that the value of the primitive root modulo $n$, $\omega_n = \exp(-2\pi i / n)$, is an irrational number for the majority of $n$'s. It will thereby be computed with inevitable error $\psi$, defined as the value needed to "round off" everything that's less than the machine epsilon $\epsilon$. Thus all the values used for DFT,

$$\omega_n^0, \omega_n^1, ..., \omega_n^{n-1},$$

except for $\omega_n^0$ will also be computed with errors.

Since I'm not a good mathematician at all, I don't know if and how I could use this fact to prove that the situation is going to worsen with increasing $n$ and that eventually the convolution is going to be computed incorrectly.

I would also like to have and argument for OR against the following claim: for fixed $n$, the maximal error will be produced when all the coefficients of both polynomials are $BASE-1$.

Thank you very much in advance!


texts:
How to solve the recurrence $T(n) = T(n/2) + T(n/4) + T(n/8)$?

We assume that $T(n)$ is constant for sufficiently small $n$.


texts:
I've got a few questions related to the different types of memory that we can find:
To my understanding, since there are registers that are close physically to the CPU, these are much faster to access, same goes for the cache that is further to the CPU but still relatively closed, and the RAM which is further than everyone else and which is the slowest to gain access too. My question is: Why can't we simply put all of the RAM memory close physically to the CPU since apparently this is what is required in order to be fast. Is there another criteria to being fast apart from being close ? As I've seen, apparently since the RAM has a bigger memory size, the address in bits to access a register is longest and therefore require more time to gain access to the latter register. What if we had let's say 1000 units of cache memory each one size 8mb, in order to have a fast access to each one of them and still store 8GB of memory ? I think this would fail because since we have 1000 cache units, we'd still have to precise which one of the units we would want to have access to and therefore we'd still have the problem of having more bits in the address (at least I think so), if not, why would this logic fail ? Thank you for your help


texts:
Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices
So that all the vertices in the graph can be reached.

I thought to run an SCC algorithm to find binding components and then return them. This is true? Or is there a better algorithm?


texts: Is there a strong argument to use shell sort over insertion sort on an array of 10 elements

texts:
I'm trying to come up with an argument of why shell sort should be used over insertion sort for an array of 10 elements. And I'm wondering if there is one at all. I know that insertion sort is more efficient for the mostly sorted array, but in all other cases the shell sort should be faster. Or there will no significant performance difference for the array of 10 elements?

I have no knowledge about the data of an array.


texts: Pumping lemma for regular languages confirmation

texts:
I have the language $\Sigma = \{0,1,+,= \}$ and
$$\mathrm{ADD} = \{x = y + z \mid \text{$x$, $y$, $z$ are binary integers and $x$ is the sum of $y$ and $z$}\}$$

And with the pumping lemma I find what a think is a counter example to the $xy^iz \in \mathrm{ADD}$ with $i = 2$, $p = 4$ and $s = 0+1^p$:

$x = 0, y=+1, z= 111 \rightarrow 0+1+1111$

Which becomes the addition of 3 binary integers so I would say that it does not belong in ADD and so the language is not regular. Or is it still regular cause I can just simplify things down to the addition of two binary integers, e.g 1+1111 or 0+10000

Update on comment from Yuval:

So if I can only assuming a P satisfy the lemma then with

s = $0+1^p$ can I still assume that say $x=0$,$y=+1^p$,$z=\{\}$?

Then again in general for any $i \ge 0$ we can have something in the form if $i=2$

$0+1^p+1^p$

which again is brings me back to my first question if that is still considered in ADD or not as it is addition of 3 binary integers.


texts: Do finite state machines need transitions for all symbols?

texts: I want to know if I want to draw up a finite state machine, say for example binary strings and I want a finite state machine that accepts only one kind of binary string e.g: 0110. Do I, for each state have to account for another symbol of the binary language being read during transition. Like for the first transition, this will be caused by 0 being read, but what if a 1 is read...do I have to implement a trap state or do I just not account for the fact that a 1 could be entered 1st?


texts: NP-complete problems and sub-expenential sized circuits

texts: If one were to show that an NP-complete problem had $2^{n^{O(1)/\log{\log{n}}}}$ circuit complexity, what would the consequences of this be?


texts: Checking whether union of two languages is regular

texts:
How to check if

$L = \{c^ka^nb^n \mid k>0 \wedge n\geqslant0\} \cup \{a, b\}^*$

is regular ,where

$L_1 = \{c^ka^nb^n \mid k > 0 \wedge n\geqslant0\}$ is clearly not regular and $L_2 = \{a, b\}^*$ is... ?


texts: I am a 16 year old male who has recently been gifted a big encyclopedia on computer science by a friend of mine. I am usually not that interested in computers and technology, but computer science has started to fascinate me. I do however intend to study Physics and/or Mathematics and not CS, so my question is, would it be useful to conduct a self-study of computer science? I'm not of course going for the level of a BSc but just the basics of CS (it is an encyclopedia with ~600 pages).


texts: Minimal DFA that accepts binary strings whose decimal equivalent is divisible by 32

texts:
I thought the answer would be 32 for remainder $0,1,2,\dots, 31$. But answer given as $6$.
and explanation is given as if the number is $2^n$ then number of states required would be $n+1$.


texts: Are event and mode well defined terms in CS literature?

texts:
From my experience in programming small imperative scrips for personal usage with JavaScript,
I can conclude that an event is "A perceived change in the output of a system" (such as clicking a link from client side or refreshing a page from server side),
while a mode is a situation or "state of affairs" of a program (such as a "saved game" state we can later "load") and if a certain state has happened the program can behave in some way (such as terminating itself).

But if at all, are event and mode well defined terms in CS literature and if so, what is the difference between them?


texts: Interactions between predictive analytics, ML, and case-based and rules-based reasoning

texts:
For my studies on economy, I work on prediction of judicial decisions. I don't really understand the interactions between several concepts:

predictive analytics
machine learning
case-based reasoning
rules-based reasoning

At the moment, I understand that predictive analytics is an area of statistics that deals with extracting information from data and using it to predict a outcome, like a judicial decision. In predictive analytics there are 2 kinds of tools: econometric tools like MCO regression and machine learning tools like neural networks.

Among ML tools, we can distinguish between 2 approaches: rules-based reasoning and case-based reasoning. Given a given legal problem, with the rules approach, the algorithm learns the rules that led to these data, deduce a linear model and then we can confront the problem to the model to deduce the solution given by a court. With cases approach, the algorithm brings the given problem closer to similar cases found in the data, and deduces a solution given by a court.

Is it correct?

Are different kind of ML tools like K-NN or neural network only used for one type of reasoning? or they can be used for both?


texts: graphs - finding a shortest path length not achievable by breadth first search

texts: supposedly for some graphs there exists valid shortest path lengths between two nodes of the graph that cant be constructed by breadth first search. what defines these shortest paths that breadth first search cant reach?


texts:
I've played with 2-tag systems a bit and read all about tag/lag systems. They're great for experimenting with computation, and obviously useful as intermediaries in various proofs.

My question is: does anyone understand how to actually program in them? I mean, Turing Machines, if I sit down and work through it, I can eventually design one to do something I want, and/or understand what's going on under the hood.

Contrast this to 2-tag systems, where I am lost. I think the most complex thing I was ever able to make without brute forcing it was one that added two numbers (well, concatenated two strings) together.

Does anyone have any advice on how to look at tag systems as a programming paradigm? Or are they just too chaotic to be intentionally used in that way?


texts: Find language (and/or regular expression for automaton)

texts:
How do I go about finding a language recognized by the following automaton? And is it possible to find a corresponding regular expression? I've read some posts about the same issue here on CS.SE but none of the approaches seem to give me a solution.

EDIT:
I've just learned Arden's theorem and the method of solving this with a system of regular expressions (as this is actually not covered in my course but looks a lot more practical and easier than just 'guessing').

What I've got so far:

If we label the states clockwise from 1 to 5, such that the accepted state is $X_3$, I get the following equations.

$$\begin{cases} X_1 = 0X_1 + 1X_4 \\ X_2 = 0X_2 + 1X_1 \\ X_3 = 0X_3 + 1X_2 + \epsilon \\ X_4 = 0X_4 + 1X_5 \\ X_5 = 0X_5 + 1X_3 \end{cases}$$

If I apply Arden's theorem to every one of these, I get:

$$\begin{cases} X_1 = 0^*1X_4 \\ X_2 = 0^*1X_1 \\ X_3 = 0^*(1X_2 + \epsilon) \\ X_4 = 0^*1X_5 \\ X_5 = 0^*1X_3 \end{cases}$$

Substituting until reaching an equation for $X_3$ gives me the following:
$$X_3=0^*10^*10^*10^*10^*1X_3+0^*$$
And apply Arden's theorem one last time:
$$X_3=0^*(0^*10^*10^*10^*10^*1)^*$$
Which would be the regular expression for this automaton, however this does not seem to be right at all. Any suggestions or tips where I (could) have gone wrong?


texts: social network analysis - relations between people with weights

texts:
I asked this question on datascience.stackexchange but they directed me here.
I have a social network represented as a set of people S and individual weights for each of person (weight is the cost of person).
I also have defined relationships between these people (whether people know each other or not).
I must find such a subset D, such that every person in this subset either belongs to the set S or knows someone from the set S directly.
There will be a lot of such subsets.
I want the subset whose sum of weights of people is the smallest.
Let's see example:
D = {(John(7), Adam(15), Viktor(6), Bob(2)} and connections are John - Adam - Viktor - Bob. Solutions are Adam,Bob(17) OR John,Victor(13) OR Adam,Victor(21) OR John,Bob(9). The best is the last one - John,Bob(9).
I thought to create a directed graph where:

Each vertex represents person
Each vertex has a weight assigned to it
Edges between vertices indicate whether the people know each other or not

I imagine this as a minimum spanning tree on directed graphs problem. I found Chu-Liu/Edmond's algorithm, I know that this algorithm works for edge-weighted graphs and I have vertices-weighted, so I just set the edge weights to what are the weights of the vertices at the end of the edge. But this is not optimal solution. I don't need direct connections between people in the set D.
So after I have result from that algorithm, I can apply on it some greedy algorithm, which will go recursively over each element and check how removing it from the subset D will affect the structure - when the sum of the weights will be minimal and will ensure that no element falls out of set D (check below).
Refer to an example, my MST result will be John,Adam,Victor,Bob(27). Best solution is John,Bob(9). Interesting bad solution is Viktor,Bob(8) - the sum is minimal, unfortunately John will fall out of the D subset.
Also I assume that:

cost of a person doesn't correlate with their degree in the network (numbers of
acquaintances)
the maximum number of people and acquaintances (vertices and edges) is about 400

Is my way to solve this problem is good? Do you suggest any other solutions for that?


texts:
I am reading "Introduction to the Theory of Computation" (2ed) by Michael Sipser. In Example 1.35, it says the NFA accepts $\epsilon$, which I understand, since the state can stay at $q_1$ upon input of $\epsilon$:

But in Example 1.38, it shows to be an empty set for $q_1$, $q_3$, and $q_4$:

I thought it should be $\delta(q_1, \epsilon)=\{q_1\}$ at least, for instance. I always assume there is an "implicit self-$\epsilon$-transition" at every state, but why it is $\emptyset$ now? I also noticed the lack of a "self-$\epsilon$-transition" in the proof of Theorem 1.45 (no staying at $q_0$ upon the input of $\epsilon$). Have I missed something important?


texts: Distributed Algorithm for Minimum Cost Maximum Matching in General Graphs

texts:
What are the fastest distributed algorithms for minimum cost maximum matching in general graphs?

I found two papers that talk about approximation algorithms but I want algorithms that solve the problem exactly.

Paper 1 - Distributed Weighted Matching, Mirjam Wattenhofer, Roger Wattenhofer
Paper 2 - Simple Distributed Weighted Matchings, Jaap-Henk Hoepman, 2004

I am okay with any model of distributed computing as long as the algorithm solves the problem exactly.


texts: Papers on depth separations in neural networks

texts:
I am new to the domain of Machine learning. I have been asked to present a paper related to the mathematics behind the depth separations in Neural Networks (by Itay Safran, Ronen Eldan and Ohad Shamir). I have been having a hard time in understanding the paper.
I am looking for easy papers to learn the foundation so that I can move on to this paper. Please drop the link to any papers that you think I should read first.


texts: Stable matching problem is greedy or Dynamic?

texts: Is the stable matching problem greedy or Dynamic ? Please anyone can give a strong explanation as i tried to find it on the net but it isn't available.


texts: Lost Update Problem and Recoverability and Commits

texts:
Does lost update problem must have Read first?
Can Lost-Update problem occur in:
1] Conflict Serializable
2] Strict Recoverable
I'm totally confused about basic.
R2(X) R1(X) W1(X) C1 W2(X)
Does this create lost update? As even after commit of T1, update of T1 is lost.
But Schedule is strict recoverable, Right?
Please help me understand where my concepts are going wrong?


texts: Christofides' 1.5-approximation considers complete graphs as inputs, and as I understand this is essential. If the input graph is not complete, how can I add new edges with suitable weights such that the resulting complete graph still satisfies the triangle inequality, and, of course, the TSP solution for the complete graph only uses original edges? Thank you.


texts: Building functionally complete boolean circuits out of trinary logic

texts:
There are some not-very-commonly considered forms of trinary logic using 3 truth values. Even entire (unusual/rare) ternary computers have been built from it.

  Is there some knowledge or reference of how to convert some trinary logic systems into functionally complete boolean circuits/logic?

"Functionally complete" means all boolean functions can be computed. I am asking the more general question above in case the following more specific question does not have an answer. The motivation is more this specific following case. Consider the following "trinary truth table" for a single trinary operator.

   a b c

a  a c a
b  c b b
c  a b c

  Is it possible to somehow create functionally complete boolean circuits out of the single above trinary truth table operator? Or, maybe it can be definitively proven it's not possible?

I am also looking for any reference to that or something similar.


texts:
Summation of $O(n)$ from $1\le k\le n$.

I think it should be $O(n)$ only. Because we are addition $O(k)$ and maximum order will be $O(n)$. But answer is given as $O(n^2)$.

Correct me if I'm wrong.


texts:
Which calculus is based on first-order functions and is Turing complete?

I know of calculi which are Turing complete, but based on higher-order functions:

Lambda calculus
SKI combinator calculus

There is also a calculus based on first-order functions, but is not Turing complete:

Kappa calculus

I know that first-order functions by itself aren't Turing complete,
but first-order functions with recursion and primitive types as $\mathbb{N}$ is.


texts: Any references/current work on anomaly detection in conversations?

texts: Suppose I have a lot of data on conversations between humans and chatbots (human text, chatbot text, times, media used for chat, etc), and I want to be able to detect anomalies in these conversations. For example, an anomaly would be if the chatbot was supposed to help customers with navigating a website, but the website was down and displayed some sort of error. As a result, the chatbot gets a lot questions about that error in a "short window" of time. I want to be able to detect this quickly, so I can then make the chatbot be able to better handle questions about that error. I read "Incremental Tensor Analysis: Theory and Applications" by Sun, Tao, et al. but I was curious if there were other works that were more applicable to text and conversations that I should check out.


texts: How best to allocate stock buys and sells when using specific id to maximize long term capital gains

texts:
Setting aside the fact that tax lots (using specific id) should usually be assigned at the time of the trade (for stocks in the USA), let's assume instead we want an algorithm to optimally allocate them once we have the whole list of trades in hand for a single security. Each trade comprises: date-time, number-of-shares, total-dollar-amount and can be either buy or sell.
Our goal is to maximize the capital gains allocated to long term rather than short term, defined when a matching buy and sell are more than a year apart. A capital gain is the proceeds from the sale of the shares less the cost of those shares.
Example:
Buys
100 shares on Jan 01 2020 total cost \$100
200 shares on Aug 01 2020 total cost \$125
Sells
150 shares on Sep 01 2020 total proceeds \$110
150 shares on Mar 01 2021 total proceeds \$185
Total capital gain is \$(185+110-125-100) ie. \$70 which will be partly short term and partly long term such that short term capital gains + long term capital gains = \$70.
What's the optimal algorithm to allocate tax lots when doing it in retrospect, ie.
What is a general algorithm identifying which share purchase to match to each share sold in order to maximize the long term capital gain portion?
So output might be something like, for the 150 shares sold on 9/1/2020, 100 should come from the first buy, 50 from the second buy. For the 150 sold on 3/1/2021, all 150 come from the 2nd buy.


texts: Image registration using gradient descent

texts:
I have a target image $f(x,y)$ (where $x \in [0, 250]$ and $y \in [0,300]$), and a source image $g(x,y)$

I want to align $g$ to $f$ using the transformation :
$$\Psi(x,y;t_x, t_y, \theta) = \begin{pmatrix}\cos(\theta) & -\sin(\theta) & t_x \\
\sin(\theta) & \cos(\theta) & t_y\end{pmatrix}\begin{pmatrix}x \\ y \end{pmatrix}$$

I'm trying to do this by minimizing the squared error :
$$l(p) = \sum_{x,y}{(f(x,y) - g(\Psi(x,y;p))}^2$$

I first computed the gradients :
$$
\begin{align}
\frac{\partial l(p)}{\partial t_x} & = \sum_{x,y}\left(2(f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial t_x}g(\Psi(x,y,p))\right)\right) \\
& = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial t_x}g(\Psi(x,y,p))\right)\right) \\
& = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial \Psi_x}g(\Psi(x,y,p))\frac{\partial \Psi_x}{\partial t_x}\right)\right)\\
& = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial \Psi_x}g(\Psi(x,y,p))\right)\right)\\
\frac{\partial l(p)}{\partial t_y} & = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial \Psi_y}g(\Psi(x,y,p))\right)\right)
\end{align}
$$
However, for $\theta$, I find this :
$$
\begin{align}
\frac{\partial l(p)}{\partial \theta} & = \sum_{x,y}\left(2(f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial \theta}g(\Psi(x,y,p))\right)\right) \\
& = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial \theta}g(\Psi(x,y,p))\right)\right) \\
& \text{by chain rule } \frac{\partial}{\partial \theta}g(\Psi(x,y,p))
= \frac{\partial}{\partial \Psi_x}g(\Psi_x(x,y;p), \Psi_y(x,y;p))\frac{\partial \Psi_x}{\partial \theta} + \\
& \frac{\partial}{\partial \Psi_y}g(\Psi_x(x,y;p), \Psi_y(x,y;p))\frac{\partial \Psi_y}{\partial \theta} \\
& = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial \Psi_x}g_\Psi\frac{\partial \Psi_x}{\partial \theta} + \frac{\partial }{\partial \Psi_y}g_\Psi\frac{\partial \Psi_y}{\partial \theta}\right)\right)
\end{align}
$$

Since $\frac{\partial \Psi_x}{\partial \theta} = -x\sin(\theta) - y\cos(\theta)$, it can reach high values such as $300$ (depending on $\theta$).
This means that $\frac{\partial l(p)}{\partial \theta}$ have values way bigger than $\frac{\partial l(p)}{\partial t_x}$ for instance, which feel quite wrong.

I think I did a mistake calculating the gradient, but I don't understand where?


texts:
Languages like Java, C#, Eiffel, and C++ have subtype hierarchies which are directed acyclic graphs, due to interfaces in Java and C# and multiple inheritance in Eiffel and C++. An obvious way to check whether type $A$ is a subtype of type $B$ is to traverse the graph of the subtype hierarchy starting at $A$ to see whether type $B$ appears 'above' it. This surely is not the most efficient way to implement subtype tests.

  What techniques exist to efficiently implement subtype testing for modern OO languages?

I'm interested in efficiency both in terms of time and memory and any trade-offs between the two.


texts: Segmented Paging mechanism virtual and physical pages

texts:
I have a system which uses segmented paging. Every address is divided as follows:
(s,p,d) = 2,2,11. Main memory has a capacity of 32KB. There are 4 segments which have 4 virtual pages each. I have to find the number of physical and virtual pages. For the virtual pages i suppose that the answer is 16 because every segment has 4 virtual pages. To calculate the number of physical pages i converted the 32KB of memory to bits and divide the number by 2^11 so the answer is 125. Is that correct?


texts: Number of spanning trees in undirected simple graph

texts:
What is the number of spanning trees in an undirected simple graph?

My attempt:

Let $m$ be the number of edges in a simple graph, and let $n$ be the number of vertices.

Then number of spanning trees is $\binom{m}{n-1}$ minus the number of cycles of length $n-1$.

I read on Wikipedia that the number of spanning trees in the complete graph $K_n$ is $n^{n-2}$.

According to the formula I stated above, it should be $\binom{n(n-1)/2}{n-1} - \binom{n}{n-1} (n-1)!$.

How do I show that this is equal to $n^{n-2}$ for $K_n$?


texts:
I'm studying CS online, and I'm reading this lecture on recursion, see "3.2. A Mathematical Example".

I understood the beginning and I even made a program that calculates $X$ to the power of $N$ using recursion.

Reading on, I quote from the lesson's content:

  Find an algorithm for raising a number $X$ to the power $N$, where $N$ is a positive integer. You may use only two operations: multiplication, subtraction. We would like to multiply $N$ copies of $X$ all at once, but, like the piles of books, we do not have an operation that directly allows us to do that: we can only multiply two numbers at a time. In other words, the problems we can solve directly are these:

  Raise $X$ to the power $1$: answer = $X$.
  Raise $X$ to the power $2$: answer = $X \times X$.
  Any other problem we have to solve indirectly, by breaking it down into smaller and smaller problems until we have reduced it to one of these base cases.
  So, if $N > 2$, we split the original problem into two subproblems:

  $P1$: raise $X$ to the power $I$. The answer to this is $S1$.
  $P2$: raise $X$ to the power $N-I$. The answer to this is $S2$.
  To get the final answer, $S$, combine $S1$ and $S2$: $S = S1 \times S2$.

  How do we solve $P1$ and $P2$? They are problems of exactly the same type as original problem, so we can apply to them exactly the same strategy that we applied to the original problem. We check to see if we can solve them directly... if $I=1$ or $I=2$ we can solve $P1$ directly; if $N-I=1$ or $N-I=2$ we can solve $P2$ directly. The problems we cannot solve directly, we solve recursively, as just described. An interesting feature of this strategy is that it works no matter how we split up $N$.

What I don't understand is, how I'm supposed to split it up into bigger chunks to achieve greater speed.

Since the game rules are that I can only use multiplication and subtraction operators, so how can I divide $X$?
If I know that $N-I=2$, how can I solve $P2$ directly, it's $X \times X \times X$, meaning two multiplications?
Is each $P$ a separate recursion?


texts: Decidability of halting problem for DPDAs with $\epsilon$-transitions?

texts:
For LBAs it's rather easy to prove the decidability of the halting problem, as there can only be a finite number of different configurations when using limited space.

But what about PDAs with $\epsilon$-transitions?  Is the halting problem decidable for deterministic PDA's with $\epsilon$-transitions?  Given such a DPDA $P$ and an input $x$, can we decide whether $P$ will halt on input $x$?

The stack may be infinitely large, so it seems like it might be much harder here to see if the PDA is in an infinite loop or not.

I don't think it's as easy as answered here for non-$\epsilon$ PDAs:

  [For] DFAs or PDAs, the halting problem is decidable: the machine
  always halts because it halts when it reaches the end of its input,
  the input is finite and the machine consumes one character of input at
  every step.

  Is the halting problem specific to Turing machines?)

The answer to my earlier question (Is a PDA's stack size linear bounded in input size?) also seems to point in a direction of a higher difficulty of proving this.


texts: What does $\{$ a set $\}^{+}$ mean in the context of languages?

texts:
I came across this notation and I don't know the meaning of it, or if it's a typo:  $\{$ some set $\}^{+}$

What does the + mean, i.e., the plus operator applied to a set?


texts: How many virtual machines run inside MS Windows?

texts:
In my Computer Systems (first year) module as part of my EE degree I'm studying virtual machines, memory management, hardware abstraction etc. I have come across the information that the OS creates and uses a few virtual machines to provide hardware and I/O abstraction.

I assume that there are multiple VMs doing different tasks, but how are they organised?

Are they one VM per task, e.g. one for disk I/O and the filesystem, one for human interface devices, etc; or are they all general purpose and are one VM per process?

Many thanks,
Ben Adamson


texts: How to prove the existence of the spectral expander with the given parameteres?

texts:
I need to prove the existence of the $(1944, 144, 0.5)$ spectral expander. I tried to construct it using tensor product of the following graphs:
$$
(1944, 144, 0.5) = (9^2, 9, 1/3) \otimes (24, 16, 0.5)
$$
I already know that expander with parameters $(9^2, 9, 1/3)$ exists and corresponds to the affine expander, but I am not sure about $(24, 16, 0.5)$ one.


texts: Is Turing Reduction always in context to decidable languages?

texts:
According to Wikipedia's article on Turing Reduction

  It can be understood as an algorithm that could be used to solve A if it had available to it a subroutine for solving B.

Does solving mean always halting (accept/reject)? Should B assumed to be decidable language for the sake of proofs ?


texts: Compare regex in programming languages with regular expression from automata/formal language?

texts:
I'm trying to reconcile the differences/similarities between regular expression from formal language theory and automata, and the "regex" offered by programming languages.

These two differ not just in "syntax" (the union + in regular expressions means | in regex, and there's no such meta-character as . in regular expressions, etc.), but also in "semantics", e.g. the regular expression (a+b)*c describes the regular language, L={a,b}*{c}, which the string abcd is not a member of, but the equivalent regex (a|b)*c would actually find a "match" in the string abcd (unless I do (a|b)*c$). Not to mention that "regex" can describe some non-regular languages as well.

Is there a good resource/summary that compares regular expression with "regex"?


texts: What's the advantage of "value restriction" over its alternatives?

texts:
What is the motivation to pick "value restriction" over other candidates?

Examples of alternatives:

Enclosing pureness into the function type, for example:

pure_function : x -> x
impure_function : x => x

Polymorphism by name (call by name) as in Xavier Leroy, 1993

Xavier Leroy, 1993. Polymorphism by name for references and continuations. In 20th symposium Principles of Programming Languages, pages 220-231. ACM Press, 1993.


texts: Find minimum amount of feature combinations reproducing certain coloring of objects

texts:
PROBLEM

Given a set of features $A = \{a_1, a_2, \ldots, a_m\}$.
You have a set of objects $X = \{x_1, x_2, \ldots, x_n\}$ such that each object has certain combination of features. Some objects can have no features at all. Some other objects may have all of them. Two different objects may have same sets of features.

In addition the objects are painted in colors belonging to set $C = \{1, 2, \ldots, l\}$.

The input data might be visualized as in the following table:

+--------+-------------------------+-------+
| object |          features       | color |
|--------|-------------------------|-------|
|   1    | s1 = { a1, a2 }         |   1   |
|   2    | s2 = { a2, a5, a7 }     |   1   |
|   3    | s3 = { a1, a9 }         |   2   |
|   4    | s4 = { a8, a9, ... }    |   3   |
|  ...   | ........                |  ...  |
|   n    | sn = { a2, a15, ... }   |   1   |
+--------+-------------------------+-------+

where $s_k$ is a set of features assigned to object $x_k$.
In the other words $s_k \in S$ where $S = P(A)$, i.e. $s_k$ is an element of the power set of $A$.
We will also say that $c_k$ is color of object $x_k$.
Two different objects $k \neq j$ may have same color: $c_k = c_j$

You need to describe colors of objects via their features.

More precisely, you need to find the minimum possible subset $Q \subset P(A)$ such that:
$\forall k, j: c_k \neq c_j \implies q_k \neq q_j$ (objects of different colors must be described by different sets of features)
and
$\forall k: q_k \subset s_k$ (subset of features describing an object must be built only of the features assigned to the object).
where $q_k \in Q$.
Under minimum possible subset I mean subset with minimum cardinality $|Q|$.
It is possible and even desirable that for some $k \neq j$ you have $q_k = q_j$.

You can assume that features are assigned in such a way that solution exists or you might design an algorithm which is able to detect cases when solution does not exist - whatever is more convenient.

CONEXT

We have objects. User can supply them with meta-information (features) and modify some properties of them (colors). Our goal is to automatically build queries by features which would find appropriate objects and do the modifications same as user's. Thus we want to guess how user's work might be automated and provide him/her with re-usable ready solutions.

QUESTION

Does anybody know an algorithm to solve the given problem?
Any references would be very welcome.
Or maybe you know the common name of this problem?


texts:
Let H be a class of all functions, mapping M possible keys to N integers. Is it true that H is a 2-universal family? Is it a good idea to use H in applications?
I don't even know where and how to start. Can you give me a hint on how to prove this?
Is it even possible to prove this?


texts: Shortest hamiltonian path for different dimension points

texts:
The shortest Hamiltonian path (solution) for a set of points in $\mathbb{R}^k$ (in Euclidean space) changes subject to $k$.

For example if for $k=1$, the shortest Hamiltonian path will be the sorted set of points, which can be achieved in $O(n\log n)$.

My question is what happens when $k$ increases - does the solution become more and more complex or is it the same for all values of $k$ larger than $1$?


texts:
An (unweighted) $k$-spanner of a graph $G$ is a subset of edges $S$ such that the distance between any two vertices of $G$ when using only edges in $S$ is at most $k$ times the distance in graph $G$. The goal is to find a small set $S$ that satisfies this constraint.

Recently, I've looked at some algorithms for this problem such as A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Interestingly, all of them seem to compute a $(2k-1)$-spanner that have at most $O(k n^{1+1/k})$ edges, for integers $k\ge 1$.

This made me wonder about the following:

  Is it impossible to construct a $k$-spanner for even $k$, e.g., $k=2,4$, in general graphs?


texts: fundamental doubt in definition of routing table

texts:
I have some very simple doubt in definition of routing table, and would be thankful if anybody could clarify it.

The doubt is that can the routing table of any node, say w, be smaller than the degree of w?

In other words, to route packet from w to its neighbour, say y, is it required that there should be some entry corresponding to y in the routing-table(w), or is it possible that the information(address) of y is contained in the header of the packet that arrived at node w?

Thanks.


texts: What are some concrete examples of what typed lambda constants are?

texts:
I was reading the following and found the following paragraph that I didn't understand:

  Let us also consider a set Σ of typed λ -constants, that is, pairs σ : t,
  where t is some type. Like for type assignments, we assume that Σ
  does not contain constants with multiple types and let Σ(σ) denote
  the type t such that σ : t ∈ Σ.

can I have some concrete examples of what lambda-constants are?


texts: Can I decrypt an RSA algorithm using only the message I am wanting to decrypt, an "e" value and a "n" value?

texts:
I have a ciphertext $c$ encrypted with RSA algorithm that needs to decrypt. I have the public key $(n,e)$.

Is it possible to decrypt with this amount of information?


texts: help with intuation regarding littles law - if arival rate > service rate, shouldnt the queue explode?

texts:
Little law states that the average arrival rate(AR) multiple the average rate of service time(SR) equals the number of customers in the system.
But intuitively, if AR > SR shouldn't the system exploded with customers? because on avg, we 'can't keep up' with the number of customers that arrive?
In a deterministic system ar>sr indeed it's stated that the system will explode. but not when it's on average :/
Can't wrap my head around that "contradiction"


texts:
There are already good answers from several perspectives regarding the "hardness" of $PSPACE$-complete problems, such as this: What is practical difference between NP and PSPACE-complete?

But what are the practical implications when we actually try to solve (decide) a $PSPACE$-complete problem on a deterministic Turing machine? If $PSPACE \neq NP$ (or $PSPACE \neq P$, should it make a difference) then obviously it will take super-polynomial (exponential?) time. But what about space? Is there some $k>1$ that we know of such that it will definitely take $\Omega(n^k)$ space? And do we know for sure that it won't take more than $O(n^l)$ space for some $l$?

(Or is the question itself stated badly for some reason?)


texts: long-lived scheduling using max-flow & push/relabel

texts:
I'm writing a scheduler of long-lived Processors which execute long-lived Tasks. Processors and Tasks may each come and go over time, at any time (when a Processor departs, its assigned Tasks now become available for other Processors). Additional constraints exist which can be modeled as a flow network (eg, Tasks can desire multiple distinct assigned Processors, which must also be balanced across racks/regions).

At time{0} and all future time{N}'s a feasible maximal assignment can be induced by solving the max-flow problem. That much seems clear.

However "handing off" a task from one Processor to another incurs (sometimes significant) startup cost. Therefore at time{N}, the solution would ideally deviate as little as possible from that of time{N-1} to minimize incurred cost. Intuitively, I seek to minimize something like the "edit distance" of the two solutions (with full knowledge that the structure of the graph itself has likely changed).

One approach would be to model this as a min-cost max-flow problem, where costs between Tasks and Processors at time{N} encode the assignments of time{N-1}. This would work, but I do worry about scaling (scheduler iterations should be fast), and about code complexity & correctness (targeting Golang, and no implementation appears readily available).

I'm thinking of another approach which I'd appreciate feedback on, which would be to slightly tweak the push/relabel algorithm for max-flow by using the following selection criteria:

Where there is an applicable arc "push" operation such that the directed arc also had non-zero flow at time{N-1}, that operation is preferred.

Where multiple such arcs exist, further rank them by the degree of flow at time{N-1} (the intuition is to saturate arcs having higher flow at time{N-1}, first).

If no such applicable arc exists, use the common FIFO selection rule with discharge.

My intuition is that:

As the generic form of the push/relabel algorithm doesn't depend on any particular operation order for correctness, this selection criteria cannot break the algorithm; and
Applying this criteria will greedily lead to a pre-flow best matching the time{N-1} assignment, from which it will induce a maximum flow using a minimal number of additional push/relabel operations.

Questions:

Is 2) above approximately true, in that it may not be minimal but will be close? Any sense of what bounds, if any, might exist ?

Any other research avenues I should be looking down, or prior work of this kind?

Thanks!


texts:
I have heard that we can convert any text to hash code , but hash code can't be converted back to text without brute force.
Suppose we consider the text "mal". The hash codes of the individual letters are

m= 6f8f57715090da2632453988d9a1501b
a= 0cc175b9c0f1b6a831c399e269772661
l= 2db95e8e1a9267b7a1188556b2013b33

Those of the prefix "ma" and of "mal" itself are

ma= b74df323e3939b563635a2cba7a7afba
mal= 749dfe7c0cd3b291ec96d0bb8924cb46

Each hashcode has 32 elements, which can be either numbers from 0 to 9 or letters from a to f.
What I observed was some when we add a letter some numbers are kept like it is just changing it's order. Is there some logic in it? Is there some easier method?


texts: Does quantum computing convert any O(2^n) algorithm into a polynomial running time and how?

texts: For example, if it is a $ O(2^n) $ algorithm that loops through 0 to $ 2^n - 1 $ and check whether the number of 1 bits is divisible by 3, 5, 7, 9, 11, does quantum computing reduce it to non-exponential time and how?


texts: Büchi automaton to Linear Temporal Logic

texts:
Given a Büchi automaton what is the procedure to build an equivalent LTL formula? And what is its size?

I'm looking for references but I haven't found them so far.


texts: Are universal types a sub-type, or special case, of existential types?

texts:
I would like to know whether a universally-quantified type $T_a$: $$T_a = \forall X: \left\{ a\in X,f:X→\{T, F\} \right\}$$ is a sub-type, or special case, of an existentially-quantified type $T_e$ with the same signature: $$T_e = \exists X: \left\{ a\in X,f:X→\{T, F\} \right\}$$

I'd say "yes": If something is true "for all X" ($\forall X$), then it must also be true "for some X" ($\exists X$). That is, a statement with '$\forall$' is simply a more restricted version of the same statement with '$\exists$': $$∀X, P(X) \overset?\implies ∃X, P(X).$$

Am I wrong somewhere?

  Background: Why am I asking this?

  I am studying existential types in order to understand why and how "Abstract [Data] Types Have Existential Type". I cannot get a good grasp of this concept from theory alone; I need concrete examples, too.

  Unfortunately, good code examples are hard to find because most programming languages have only limited support for existential types. (For instance, Haskell's forall, or Java's ? wildcards.) On the other hand, universally-quantified types are supported by many recent languages via "generics".

  What's worse, generics seems to easily get mixed up with existential types, too, making it even harder to tell apart existential from universal types. I'm curious why this mix-up occurs so easily. An answer to this question might explain it: If universal types are indeed only a special case of existential types, then it's no wonder that generic types, e.g. Java's List<T>, can be interpreted either way.


texts: NP-completeness and reduction of MAX-XOR-SAT and MAX-2-XOR-SAT

texts: It is often stated that the MAX-XOR-SAT problem is NP-hard, and that likewise is the MAX-2-XOR-SAT problem. However, I cannot find a reduction from SAT to either of these problems, nor a proof of NP-hardness. Is one published anywhere?


texts: Algorithm for automatic/optimal database joins?

texts:
I'm curious if there is existing literature or well known algorithms out there for a problem I am working on.

Given a normalized relational database with valid foreign key constraints and a list of fields across different tables, what is a good or at least consistent algorithm for determining the (inner) joins required to provide that information? Ideally using the minimal number of joins possible.

Given a graph and a set of nodes that I want. How do I find a subgraph which is connected that contains all those nodes.

My initial thoughts:

I see the table as a directed graph with tables as vertices and foreign keys as edges between them. For the purposes of the algorithm treating the graph as undirected seems like it might be useful.

Shortest path between tables seemed obvious but as soon as more than 2 tables are requested then I would be finding the shortest path that visits all nodes (traveling salesman territory ACK!). My second thought is the minimum spanning tree of the subgraph. However, how would I choose the subgraph?

Edit:
After thinking about it more I think this could work. Run Kruskal's minimum spanning tree on the graph beginning from a desired node. Assign weights to the edges like so weight=1 if (a,b) is between two desired nodes. Weight = n^2, where n is the number of nodes, if (a,b) is between a desired node and a undesired. Weight = n^4 if between two undesired nodes. The weights are arbitrary. I just thought it would be better to use values that couldn't overlap.

Once all desired nodes are added to the MST, exit Kruskal's. Then from the root (starting node) walk down to each leaf. If a leaf is not desired node, then delete it. Repeat until no nodes are deleted.


texts: The well-known classifiers that can be trained/tested in linear time

texts:
I am interested in collecting the list of the classifiers that (depending on their setting) can have linear time complexity (both in training and testing step) with respect to the number of samples $n$, the number of features of each sample $m$, and the number of classes $c$.

In other words, I am seeking for a list of the well-known classifiers that can have the complexity of $\mathcal{O}(mnc)$ or lower.

1- I know that Naive Bayes classifiers are so; given that the parameters of the utilized probability distributions can be estimated in linear time (e.g. Poisson Naive Bayes and Multinomial Naive Bayes)

2- I also know that when K-NN is utilized as classifier (counting the K-nearest neighbors and choosing the most-voted class), it is also included in this list.

Although this list, in theory, can be extended infinitively, I am interested in completing the list by the well-known classifiers by the CS community.

I searched the web, a lot, but seemingly, there is no page even speaking about such subject or such list. The only thing that I found was a lot of info about "linear classifiers" whose scope is much more general than my question (even their list includes SVM and etc.).


texts: How to write a DFA where the second digit is equal to the last digit of binary strings?

texts:
I'm having some trouble writing a DFA for the language  $$\{w =b_1\dots b_k \in\{0, 1\}^* \mid b \ge 2 \text{ and } b_2=b_k\}\,.$$

What I thought for this is writing a DFA where there are 4 states, that accepts at the states (00) and (11), where the 1st element in the state is the 2nd element in the string, and the 2nd element in the DFA is the last element in the string. After trying to draw out examples this clearly doesn't work. I'm quite lost, any advice?


texts: How can I find the derive tight asymptotic bounds on the following recurrence

texts:
$$T(n) = 2 T(n/2) + \sum_{k=0}^n (k+2)^2$$
I want to use the substitution method. How can I generate my guess and how can I determine the growth of summation in the recurrence?


texts: Is there a language which has a polynomial length certificate but not known to have a polynomial time verifier?

texts: The question came to my mind while studying the NP definition. Do we know any such languages?


texts: Which machine learning should I choose for a one->list relation

texts: I'm trying to write machine learning software that will predict a list of 3 values from a given number input (reverse grayscale). There is a function determining values of the list to the grayscale, but finding the inverse by hand seems impossible. I think something like Markov Chains or a random forest algorithm might be useful but I wanted to know if there were any others/better ones?