texts: Upper bound on graph diameter. Linear certificate

texts:
Consider the next problem. Given a large oriented graph find its diameter: maximal length over all shortest directed paths between every pair of vertices. Graph is strongly connected. It is allowed to give lower and upper bounds on the answer. Time complexity should be linear or close to it.

Suppose I solved the problem and I want to prove it. Moreover I want the proof can be checked in linear time: graph is large.

Lower bound is easy. Just let me give two vertices on neccessary distance. Upper bound is harder. I can give a vertex and ask to estimate the furthest vertex reachable by forward, and then by backward, edges. Then I sum up these distances and call it upper bound.

The problem that my upper bound doesn't look tight. Can anybody suggest something better?


texts: Analysis and classification based on data points

texts:
I'm not sure if this is the correct stack exchange or correct tags, but my question is as follows:

I am working on a sort-of ratings system for players in a particular game. After allowing the ratings to develop for many games, I have set up a "database" (not sure if this is the correct term) for matches: a point in the database would consist of the score difference between the players (i.e if it's >0 player 1 won) and the rating discrepancy between the two players before this match.

The idea is to use this database in order to predict the score difference of a match that has not yet occurred: I measure the rating discrepancy between the 2 players, and lookup in my database for the score differences in games of a "similar" rating discrepancy, and based on these games I am able to predict, say, a rough probability of each score difference occurring in this match that has not yet happened.

I actually have two questions:

1) what is a good approach to using the database to predict the probability of each score difference, i.e what qualifies as a "similar" rating discrepancy, how do I deal with extreme cases where the rating discrepancy is very large and I have few data examples of such matches (should I relax my definition of "similar"?), etc. A bit of googling shows that maybe I am looking for something relating to data clusters.

2)how would I go about implementing an algorithm as above? are there good standard implementations of such classification algorithms? I am writing in C# if it makes a difference.


texts: What was the major breakthrough between Hoare-Floyd logic and Scott–Strachey semantics?

texts:
I'm reading through a commentary on Milner's "The use of machines to assist in rigorous proof" by Mike Gordon. In this paper, he explains how LCF was born from the ideas of denotational semantics by Dana Scott and Strachey.

It seems to me that Floyd-Hoare logic wasn't enough for developing LCF, but I'm not sure why this is the case. At the end, in Hoare logic we deal with program states that satisfy some precondition $P$ and that through a relation $r$ conform to some postcondition $Q$ and I can provide a formula for this. Wikipedia claims that denotational semantics:

  is an approach of formalizing the meanings of programming languages by
  constructing mathematical objects (called denotations) that describe
  the meanings of expressions from the languages.

I'm familiar with some intuitions on how for instance recursion is modeled in this approach as a fixed point of some relation while in Hoare logic I didn't really remember dealing with recursion. Still both approaches seem to try to describe relations between inputs and outputs using mathematical relations.

Question

So what is it that made a difference between Hoare logic and denotational semantics? Does denotational semantics manage better some complexities of programs? If so, please illustrate with an example.

Maybe the following quote of Milner referring to denotational semantics is interesting to guide your answer:

  I could write down the syntax of a programming language in this logic
  and I could write the semantics in the logic.


texts: Solving $\text{key}=(\sum_{K=0}^n\frac{1}{a^K})\bmod m$ with High limits

texts:
I was solving this equation:
$$\text{key}=\left(\sum_{K=0}^n\frac{1}{a^K}\right)\bmod{m}.$$
Given
$$ 1,000,000,000 < a, n, m \; < 5,000,000,000, $$
$$ a, m \text{ are coprime}. $$
I solved it by brute force, but it won't work in the given constrains so I need a faster algorithm or is there is something I can notice to make the formula easier to solve ?


texts: Use max operation in a constraint in Linear Programming

texts:
I have liner programme with set of $x_{3n}$ variables where $x_{ij}$ are {0,1}. I am solving this linear programme using LP-Solve.

Using these variables, I want to form following constraint :

$max(x_1 , x_2.., x_n) + max(x_{n+1} , x_{n+2}.. , x_{2n}) + max(x_{2n+1} , x_{2n+2}..., x_{3n}) >= q$

Constraint is :
Sum of max variable in set of variables should be greater than q.

How can I write constraint using $max$ operation in LP Solve?


texts: Converting a decimal to IEEE754 32-bit binary number


texts: Please help me understand this proof of the undecidability of "Do two halting Turing machines accept the same language?"

texts:
Do two halting Turing machines accept the same language?
Proof that it is undecidable(credit to another user on this website: "Tom van der Zanden"):
Let M be an arbitrary Turing machine. Let M′ be a Turing machine that on input x, simulates M (on some predefined input) for |x| steps and accepts if (and only if) M halts within |x| steps. If M doesn't halt then M′ accepts the empty language. If M does halt then the language M′ accepts is non-empty. This gives a reduction from the Halting problem to the problem of detecting equality, since we just need to ask whether M′ is equal to the machine accepting the empty language.
How is this proof using "reduction from the Halting problem to the problem of detecting equality?" Asking whether a TM halts in a finite number of steps (|x| in the proof above) is decidable. So how would the problem of detecting equality outlined above provide a way of solving the halting problem?
In other words my problem with understanding the proof is this: How does detecting equality in the way described above decide whether the machine M halts on input x?


texts: Maximum variance and useful information of dataset

texts:
I am reading through PCA and it says that the maximum variance principal component has most of the information. Can we apply that to any data set? If a data set has n attributes and most of the attributes show high variance then can we infer that the dataset has captured lot of useful information?

I am trying to understand how a high variance dataset contains useful information?


texts: Modelling 2 object situation with Propositional Logic

texts:
I'm reading up on propositional logic, and I'm completely stuck on this example - spent the past few hours trying to figure it out! Any pointers would be appreciated.

There's 2 trees, each with signs on.

Sign 1/Tree 1: There are leaves on this tree, and no leaves on the other

Sign 2/Tree 2: There are leaves on one of these trees, but none on the other.

Exactly one of the signs is true, and the other is false. Which tree has leaves on (without looking)?

I'm starting to doubt that it's possible to tell, but I'm sure there's some logic that says otherwise!


texts: How do we define if a Turing machine goes to the right or left?

texts:
In my college course notes, we are given two examples.

  Example 9.1.1:
  $$ M(K, \Sigma, \delta, s) $$
  where

  $ K = \{q_0, q_1\} $
  $\Sigma = \{a, \# \}$
  $s = q_0$
  $ \delta = \begin{array}{|c|c|c|c|}
\hline
q & \sigma & \delta(q, \sigma) \\ \hline
q_0 & a & (q_1, \#) \\
q_0 & \# & (h, \#) \\
q_1 & a & (q_0, a) \\
q_1 & \# & (q_0, R) \\ \hline
\end{array}$

  Note that state $(q_1, a)$ cannot happen if the start state is $q_0$. This is included only for completeness (to make $\delta$ a total function).

  This machine will scan right, changing any $a$ that sees to a $\#$. When it first hits a $\#$, it will halt.

  Example 9.1.2:
  $$ M(K, \Sigma, \delta, s) $$
  where

  $ K = \{q_0\} $
  $\Sigma = \{a, \# \}$
  $s = q_0$
  $ \delta = \begin{array}{|c|c|c|c|}
\hline
q & \sigma & \delta(q, \sigma) \\ \hline
q_0 & a & (q_0, L) \\
q_0 & \# & (h, \#) \\ \hline
\end{array}$

  This machine will scan left until it encounters $\#$, then halt.

One TM goes to the right while the other goes to the left. Obviously this is determined by the transition rules, but how do we explicitly know/define where to start (either on the left of the string or right?).

I am asking because I have a Turing machine that works for a problem I have, but I must start from the right of the string and scan left... How do I define this?


texts:
The following is my own set-up code:

Search_and_Sum(key, A,n)    A[1..n]
    int sum = 0;
    for(int i=0; i<=n+n+1000; i++){
        for(int j=A.length; j>=1; j/=2){
            if(key==A[j]) break;
            else          sum+=j;
        }
    }
    return sum;

Well, I think the first loop has time complexity $O(n)$ and the inner loop has time complexity $O(log\ n)$, so in the worst case, the running time is $O(n\ log\ n)$.

But, I can't figure out how to find the running time in the best case. Any ideas?

Edit:

Is this is an equivalent formulation of the code with the same running time?

Search_and_Sum(key, A,n)    A[1..n]
    int sum = 0;
    int k = A.length;
    while(k>=1 && key!=A[k]){
        sum=*key;
        k/=2;
        }
    }
    return sum;


texts:
I looked at some old OS theory books of mine and noticed that one glaring omission in all of these OS books is how to actually keep track of physical pages that are free (i.e. algorithms for actually implementing the free list). I know pretty well how userland memory allocators work, but a big difference with physical page allocation is that fragmentation of physical pages shouldn't be an issue, since the page table can just pick and choose the physical pages without having to care about whether they are contiguous or not. Since avoiding fragmentation is one of the main concerns of userland allocators, it seems like physical page allocation is fundamentally a different problem. I guess that this is not completely accurate if one wants to support superpages to reduce pressure on the TLB.

My question: What are techniques are used in modern high-performance kernels for this problem? Also, does this problem become significantly more complicated in NUMA systems?


texts: Showing a partition-like problem is NP-complete

texts:
Given a set $A=\{a_{1},a_{2},a_{3},\ldots,a_{n}\}$, then construct  a set $P=\{p_{1}, p_{2}, p_{3}, \ldots , p_{n}\}$ such that

$|p_{i}|=a_{i}$, and
$\sum_{i = 1,}^{n}p_{i} = 0$.

This problem is NP-complete, which I want to prove.

How do I do it?

I am thinking of a reduction from the subset sum problem. But the problem is that because of the mod.


texts: What is the fastest algorithm for finding shortest path in undirected edge-weighted graph?

texts:
I am looking for the most efficient algorithm for finding shortest path between two Vertices.

The graph is:

undirected
edge-weighted
Non-negative
less then 300 nodes

I understand that most of the algorithms based on Dijkstra's shortest path algorithm. But which one is the most efficient for the case a specified above. Thank you.


texts:
I am really new concerning loop invariants and I am currently trying to figure out a loop invariant of an algorithm for prime numbers. I tried a lot of ideas, but I still have problems since there are two nested loops. I am also really grateful if someone have any tips regarding finding a loop invariant.
My idea is that all $i$ which are primes are set on true and all $i$ which are not primes are set on false.. but I don't think that this is the loop invariant.

PRIME_FILTER(n)
1  P = INIT(n) // Initialize array P[1::n] with True
2  P[1] = False
3  i = 2
4  while i * i <_ n
5     if P[i] == True
6       j = i * i
7       while j <_ n
8          P[j] = False // Not prime
9          j = j + i
10    i = i + 1
11 return P


texts: Generate random labeled tree with constrained edge lengths

texts:
Let $T$ be a labeled tree with vertices $V = \{1, \dots, n\}$ and edges $E$. Define the length of an edge $e = \{ u, v \}, u \in V, v \in V$ to be $l(e) = |u - v|$, i.e. the distance between the nodes in the linear arrangement of the tree. Let the length sequence $L$ of $T$ be the sorted sequence of lengths of all the edges in $T$.

An example tree is shown below. Each edge is marked with its length. The length sequence for this tree is $(1, 1, 1, 1, 2, 2, 3)$.

My question is: Given a length sequence $L$, is there an efficient algorithm to generate a labeled tree $T$ with length sequence $L$, randomly at uniform from the set of all such trees? Or failing that, to enumerate the set of trees with a given length sequence $L$?

To clarify, here is an extremely inefficient algorithm that does what I want. We have a desired length sequence $L$, let's say (1,1,1,1,2,2,3). To generate a random tree with the desired edge lengths:

Generate a random labeled tree $T$ on $n=8$ nodes by sampling a random Prüfer code.
Check if the length sequence of $T$ matches $L=(1,1,1,1,2,2,3)$. If yes, accept $T$. If not, goto 1.

This is very inefficient because there are $n^{n-2}$ possible trees generated in step 1, and only a very small number of those trees matches the desired $L$, especially as the trees get large.

Update: I have an algorithm that seems to work, but it seems like it could be made more efficient.

Algorithm:

Let $T$ be a graph with nodes $V$ and empty edge set $E$.
For each possible edge length $l$ in $\{1, \dots, \text{max}(L)\}$,
Let $k$ be the number of entries in $L$ matching $l$. So for example, if $L=(1,1,1,1,2,2,3)$ and $l=1$, then $k=4$.
If $k=0$, skip to the next $l$.
Generate the set of possible new edges $P = \{(u,v) : u \in V, v \in V, (u,v) \not\in E, u = v+l \text{ or } u = v-l\}$
If $P$ is empty, fail and start over again from 1.
Generate the set $Q$ of all combinations of size $k$ of elements of $P$
Randomly choose an element of $Q$, which is a set of $k$ edges. Add this set of edges to $E$.
If the resulting $T$ is not a forest, fail and start over again from 1. Otherwise, continue to the next $l$.

Basically, this generates the random graphs matching $L$, then filters them to be trees.


texts: Why does parallelising slow down this simple problem against looping through all the data?

texts:
I've been using multiprocessing and parallelisation for the first time this week on a very large data set using 32 CPUs. I decided to explore it for a smaller task just to see if I could learn anything, just on the 4 CPUs of my Mac.

I created a task to add 100 to every element in a 500,000 element list. To my surprise, I noticed that batching this data and using Python's parallelising tools to implement this actually slowed it down hugely, compared to just looping through the 500,000 elements and adding 1.

I'd like to understand why.

Consider the two methods for doing this task below:

import numpy as np
from sqlitedict import SqliteDict
from multiprocessing import Pool, cpu_count
from gensim.corpora.wikicorpus import init_to_ignore_interrupt
from itertools import zip_longest
import timeit as t

def grouper(iterable, n, fillvalue=None):
    args = [iter(iterable)] * n
    return zip_longest(*args, fillvalue=fillvalue)

class Add100ToData():
    def __init__(self):
        self.data = [np.random.randint(0, 100) for _ in range(500000)]

    def add100(self):
        for i in range(len(self.data)):
            self.data[i] = self.data[i] + 100
        return self.data

class Add100ToDataMultiprocess():
    def __init__(self):
        self.data = [np.random.randint(0, 100) for _ in range(500000)]

    def process_batch(self, batch):
        new_data = []
        for i in batch:
            new_data.append(i + 100)
        return new_data

    def add100(self, batch_size):
        processes = cpu_count()
        pool = Pool(processes, init_to_ignore_interrupt)
        gr = grouper(self.data, batch_size)

        for batch_result in pool.imap(self.process_batch, gr):
            count = 0
            for i in batch_result:
                count += 1
                self.data[count] = i
        return self.data

if __name__ == "__main__":
    add1 = Add100ToData()
    start = t.default_timer()
    final1 = add1.add100()
    end = t.default_timer()
    print("Looping run-time: {:.2f} seconds".format(end - start))

    add2 = Add100ToDataMultiprocess()
    start = t.default_timer()
    final2 = add2.add100()
    end = t.default_timer()
    print("Looping run-time: {:.2f} seconds".format(end - start))

This gives me:

Looping run-time: 0.13 seconds
Multiprocessing run-time: 1.23 seconds

Why is there an improvement in simply looping through the data as opposed to parallelising and batching with simple tasks?

When I was doing this for a far more labour-intensive task (one task was transforming 800,000 sentences into their 300-dimensional word embeddings, and another was applying a classifier to these), I gained huge speed improvements using 32 CPUs on the Google cloud, with a very similar code structure to this.

Can someone help me to understand why I'm not getting speed improvements here?


texts: CFG and PDA for the set of strings in $\{a, b, c\}^∗$ such that the number of b’s is equal to the sum of number of a’s and c’s

texts:
I'm trying to find the CFG and PDA for the above language. I have so far come up with this
$S \to S_1S_2 \\ S_1 \to aS_1b \\ S_2 \to bS_2c$
However, I realized that this is just a subset of the required language. How do I consider the remaining ones? Also, how do I construct a PDA for it? Any help is appreciated.


texts:
I know I must be getting stuck on notation.  However, I'm having trouble following the logic in Example 1.2 in https://arxiv.org/pdf/cs/0611018.pdf.  They define what preserving a propositional formula means.

So, I'm trying to understand a basic example.
Take X = A or (Not B) or (Not C) as an example Horn Clause.  Define the assignments f1 and f2 by f1(A) = f1(B) = f1(C) = true and f2(A) = f2(B) = f2(C) = false.  Both f1 and f2 satisfy X.

What does it mean to say AND preserves X with respect f1 and f2?


texts:
From Wikipedia:

  The prefixes of a string is the set of all prefixes to a string, with respect to a given language:
  $$
    \operatorname{Pref}_L(s) = \{t \mid s=tu \mbox { for } t,u\in \operatorname{Alph}(L)^*\}
$$
  here $s\in L$.

So is it equivalent to
$$
    \operatorname{Pref}_L(s) = \{t \mid t \mbox { is the first $n$ part of $s$}, \forall n \in \{1, \dots, \mbox { length}(s)\} \}?
$$


texts: Artificial Intelligence: Condition for BFS being optimal

texts:
It is said in the book Artificial Intelligence: A Modern Approach for finding a solution on a tree using BFS that:

  breadth-first search is optimal if the path cost is a nondecreasing function of the
  depth of the node. The most common such scenario is that all actions have the same cost.

From that I understand that if the path cost is non decreasing function of depth, the BFS algorithm returns an optimal solution, i.e., the only condition is the cost function being nondecreasing. But I think the only way for BFS to be optimal is the scenario in which all the path costs are identical, therefore a node found in a certain level is necessarily the optimal solution, as, if they exist, the others are. Therefore I think for BFS to be optimal, cost function should be non decreasing AND the costs of nodes should be identical. However, the book says only one of the conditions (former one) makes BFS optimal.

Is there a situation in which the costs are not identical, the cost function is nondecreasing and the solution returned by BFS is guaranteed to be optimal?


texts:
I know a simple reduction from 3-color to 4-color. But how do you reduce 4-color to 3-color ?

I have been searching for the right way to make this reduction for a while now. I would love some pointers.


texts: Does XML covers the representation of any structured data and knowledge

texts:
I see nowadays XML is used to structure any file or data. It can represent both flat and hierarchical relationships. For example, it can be used to show the parse tree of a sentence in a natural language.

I am not familiar with different types of data and knowledge structures, but I would like to know if XML is theoretically the ultimate representation scheme which can model and structure any data and knowledge?

What are the reasons behind the popularity of XML?


texts: Define a length function over $A^{*} \leftarrow{N}$ such that $length(l)$ outputs the length of $l$

texts:
Consider the following definitions

LIST:

$\overline{nil}  \ \ \ \ \ \frac{l}{a \ l}$ $a \in A$

$A^* = \mu \widehat{LIST}, \ A^{\infty} = v \widehat{LIST}$

NAT:

$\overline{0} \ \ \ \ \ \frac{x}{s(x)}$

$ N = \mu \widehat{NAT}, \ N^{\infty} = v \widehat{NAT}$

Given those definitions I have to define a length function over $A^{*} \leftarrow{N}$ such that $length(l)$ outputs the length of $l$.

I have tried to do this problem using structural induction on a given $l$ but I don't seem to get any relevant result.

In general, how would you approach this kind of problem?


texts: Closed form for the recurrence T(n) = T(n-1) + n²

texts:
Given the following recurrence:

$$ T(n) = T(n-1) + n^2$$

How can I prove it to be $O(n^3)$ with the substitution method? The $O(n^3)$ guess derives from the fact that at every step of the recursion we pay $n^2$ and we have $n$ steps of recursion therefore having: $n \times n^2 = n^3$.

I would even expect this to be $\Theta(n^3)$, but I can't even prove $O(n^3)$.

I tried with the guess:

$$ T(n) \leq n^3 + n^2 \cdot c_1 + n \cdot c_2 + c_3 $$

but that yields:

$$ T(n) \leq n^3 + n^2 \cdot (3 + c_1) + n \cdot (c_2 - 2c_1 -1) + (c_1 - 1 - c_2 + c_3) $$

which yields:

$c_1 = c_1 + 3$
$c_2 = c_2 - 2c_1 - 1$
$c_3 = c_1 - 1 - c_2 + c_3$

But even from the very first ($c_1 = c_1 + 3$) we find that no $c_1$, $c_2$ or $c_3$ satisfy the equations.

What did I do wrong?


texts: Do the polynomials in "polynomial time" have integer, real or complex coefficients?

texts:
This is probably a very basic question but do the polynomials in "polynomial time" have integer, real or complex coefficients?

Everywhere I looked it just says "polynomial expression". I am guessing the polynomial must have integer coefficients?


texts: Dynamic Modelling improvement suggestions

texts:
I'm encountering a dynamic modelling problem. I've tried a lot of methods but it seems that all of them are of time complexity O(MNK), like the basic algorithm. I wonder if any guys can make some suggestions about any possible improvement of my time complexity?

A dynamic model is defined as follows:

 State(n,m,t) is the state of the node (n,m) at time t. This value is either 0 or 1.

 A neighbourhood of node (n,m) consists of 8 nodes around it. Denote LifeAround(n,m,t) as the number of nodes in the neighbourhood of (n,m) at time t that are in state 1.

 Evolution:

 If state(n,m,t)=0 (dead) then state(n,m,t+1)=1 (alive) iff LifeAround(n,m,t)=3

 If state(n,m,t)=1 (alive) then state(n,m,t+1)=0 (dead) iff LifeAround(n,m,t)<2 or LifeAround(n,m,t)>3

a. Write a function that starts with the given state and develops the model through k steps on a fixed grid with zeros outside the boundary. b. Write a similar function that has no boundary.


texts: Are there any LTL to _non_ deterministic Rabin automaton translators?

texts:
I know of two translators LTL -> deterministic Rabin automaton:

Rabinizer3
ltl2dstar

They produce deterministic automata, which can be much larger than their possible non-deterministic variants. Is there a translator LTL -> non deterministic Rabin?

(my synthesis tool could handle small non-det Rabin automata but not large though det ones)


texts: Abstract Data Types and their Implementation

texts: I wanted to know if there is good resource to learn about the ADTs like set ADT, list, array, boolean etc and their implementation.


texts:
I have the following problem:

  You have n objects that have identical weight except for one that is a
  bit heavier than the others. You have a balance scale. You can place
  objects on each side of the scale and see which collection is heavier.

  Goal is to find the heavier object, with the minimum number of weigh.

I know the best algorithm that can solve this problem. Here is the pseudocode:

function findDiffWeight(L[1:n]){

   if(L.size == 1) return L[1]

   int x = sum(L[1 : n/2])
   int y = sum(L[n/2+1 : n])

   if(x>y)  call findDiffWeight(L[1 : n/2])
   if(y>x)  call findDiffWeight(L[n/2+1 : n])
}

But I am struggling with finding the lower bound for this problem. I don't think that there can be a better algorithm that can solve this in less than logn operations.

However how to prove it?
Could you give me some idea about finding lower bound for this problem?


texts: Maximize function over a set with a transitive and antisymmetric relation

texts:
Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$.

For any set $S\subseteq X$ define $\Gamma(S)=\left\{y\in S  \mid \not \exists x\in S  . (x,y)\in\mathcal{R}\right\}$. (Thus, $y \in \Gamma(S)$ if it belongs to $S$ and no other element in $S$ "dominates" it.)

Suppose that each element is assigned a weight. This is represented by the function $w:X\to \mathbb{R}^+$.

The problem is to find a subset $S \subseteq X$ to maximize $\sum_{z \in \Gamma(S)}w(z)$.

Is this problem polynomial-time solvable?


texts: Cube 3x3: Using just face rotations, transform the cube from configuration A to B

texts:
I'm looking for some tips on how to best implement the algorithm to accomplish the following:

Imagine a 3×3 cube with a rubik's cube mechanism, i.e. you can freely rotate any of the 6 faces.
You don't care about colors.
Instead you index the component 26 cubes A–Z and ignore the middle.

Illustration image (component cubes): https://paste.pics/AOYUS
Now, I would like to generate a list of face rotations that would get me from this configuration to some other configuration. E. g. this: https://paste.pics/AOYWM
Note: I don't care which component cubes end up in positions labeled as *
Ideally the algorithm produces the shortest list of transformations necessary, but it's not a firm condition. Any suggestions welcome, thanks!


texts: Curry howard Isomorphism what the propositions A , B ranges over

texts:
In CH-I what the propositions A , B ranges over too ?

An update :

From Pfennings notes :

"A denotes proposition about the mathematical objects such as integer or a real number."

From :
 Per martin lof "On the meanings of logical constant" pdf cs.cmu.edu/~crary/819-f09/Martin-Lof83.pdf , 17-18 page
"We may substitute for A and B now range over arbitrary complete expression we want" but he never completely explains what this expression really means.

If i put in place of A , "It is raining." what is the proof and even if we say proof is just seeing out of the window, what is the corresponding lambda expression / term and type ??

Can someone explain it ?


texts:
By Information-Theoretic definitions, the One Time Pad (OTP) is called/was proved to be a Perfectly Secure Cipher. For the sake of completeness, we define

OTP: An enc/dec function, $f:\mathcal{P} \times \mathcal{K} \rightarrow \mathcal{C}$
Perfect Security: Given $m, m^* \in \mathcal{M}$,
$$P\big(m=m^* \mid E_\mathcal{K}(m) = c\big) = P(m=m^*) $$

I ask, Are there any more Perfectly Secure Ciphers known other than the OTP?


texts:
Here is a problem vaguely related to the dining philosophers problem. Three metaphysicians go to a restaurant for dinner. When it is time to pay the bill, they decide that they want one of them to pay the entire bill, but without the other two knowing who paid the bill. Ideally, they'd put three tokens in a bag, one white and two black, and secretly draw a token at random. But this is not allowed. They each have a random generator (coin, dice), and they are limited to exchanging information between each other, either publicly or in private between two of them. For example, all three of them may flip a coin, take note of their coin flip (H or T) and inform their left neighbour of the result. Then the metaphysician whose coin flip equals the coin flip of his right neighbour pays, and the other two don't pay (and don't know who paid). This only works, however, for THH, TTH, HTT, HHT, HTH, and THT; but not for HHH and TTT (since in those cases, all three of them would be paying the entire bill).

Here is my attempt at a solution. Let $R$ be a finite event space for the random generator, ${r_1,...,r_n}$, let $S$ be $\{0,1\}$, and $T$ be a suitable set. Let $f$ be a mapping from $R$ to $S$ and $g$ be a mapping from $R$ to $T$. $f$ maps the outcome $r_i$ to heads or tails as in the coin flipping example. $g$ is a function that masks the $r_i$ while providing enough information to decide whether the procedure needs to be repeated (because the $f$ results are of the HHH or TTT type). The metaphysicians reveal their outcome $f(r_i)$ only to their left neighbour and announce $g(r_i)$ publicly. Here is what $f$ and $g$ need to be able to do: (i) knowing all $g$ values determines whether $f(r_1)=f(r_2)=f(r_3)$ or not; in the former case repeat the procedure. In the latter case apply the coin flipping example to determine who pays. (ii) the probability of $f(r_L)=f(r_\mbox{me})$ conditional on knowing $(g(r_L),g(r_{\mbox{me}}),g(r_R))$ and $f(r_\mbox{me})x≠f(r_R)$ is $0.5$ so that I don't know who pays the bill if my coin flip differs from the coin flip of my right neighbour. $r_L$ is my left neighbour's outcome, $r_R$ my right neighbour's outcome. If I had functions $f$ and $g$ fulfilling these constraints, I'd have a solution for my problem, but I don't know what $f$ and $g$ might look like. $g(r_i)$ could be something like an md5sum, not allowing me to infer $f(r_i)$ which determines the payor.


texts: How to draw a graph to disprove this statement?

texts:
The Problem: Indicate whether the following statements are true or false:

     a. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of at least one minimum spanning tree of the graph.
     b. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of each minimum spanning tree of the graph
     c. If edge weights of a connected weighted graph are all distinct, the graph must have exactly one minimum spanning tree
     d. If edge weights of a connected weighted graph are not all distinct, the graph must have more than one minimum spanning tree

I read from Min Edge that every MST must contain the minimum weighted edge and from Partial Solutions that two of the assertions are true while the rest of the two are false.
From those two statements, I concluded that the first two statements(a, b) are true while the last two statements(c,d) are false.

Here is the diagram I used to illustrate that the last option, d, is false.

The edge weights are not distinct(two twos) and there is only one minimum spanning tree.
Can anyone give a counterexample graph to choice option c? I tried some examples(too many to include in here) but each time with distinct weights, using Prim's algorithm, I only found one MST.


texts: Let $L=\{a^nb^nc^n | n\geq 0\}$ , then $\overline{L}$ is context free

texts:
I need help with this problem.
I proved that $L$ is not context free (using Ogden's lemma), but I can't prove that $\overline{L}$ is context free. I'm thinking about a proof by cases (if $\#(a)=\#(b) \neq \#(c)$ or something else) but the proof could be so extensive.


texts:
In order to find the appropriate length of chromosomes in GA programming, the author of this book states:

  Suppose six decimal places for the variables' values is desirable.
  It is clear that to achieve such precision each domain Di = [ai,bi] should be
  cut into (bi - ai) * 10^6 equal size ranges. Let us denote by mi the
  smallest integer such that (bi - ai) * 10^6 <= 2^mi - 1. Then, a
  representation having each variable xi coded as a binary string of
  length mi clearly satisfies the precision requirement. Additionally, the following formula interprets each such string:

  xi = ai + decimal(1001...001) * (bi - ai)/(2^mi - 1)

  where decimal(string) represents the decimal value of that
  binary string.

So here is my question: Why is the author using (bi - ai)/(2^mi - 1)? Why not (bi - ai)/(2^mi)? What is that -1 for?

I searched it and I thought it might have something to do with the Mersenne Prime numbers because of the formulation!! I also checked out the Schema as I thought it might be related to that, but these all seem completely unrelated!


texts: When are 2 decision/optimization problems equivalent?

texts:
Does anybody know a good definition of 2 decision / optimization problems being equivalent?

I am asking since for example allowing polynomial time computations any 2 problems in NP could be considered equivalent.


texts: How to write all $r$-tuples with a certain property in a list

texts:
I have the following question:

Let $a,b,c,d$ be four natural numbers with $a \leq b$ and $c\leq d$.

I have written a program that produces a list, which has as entries all 2-tuples $(x,y)$ with $x\in [a..b]$ and $y \in [c..d]$.

Now, I have a new list, let's call it list_1. It consists of elements indexed by the $(x,y)$.

For example, let a=3, b=4, c=7, d=8.

Then my programm produces list=[[3,7],[3,8],[4,7],[4,8]].

Now, my list_1 is [M_{3,7},M_{3,8},M_{4,7},M_{4,8}].

  I would like to have a new list, call it list_2, which has exactly the following entries.

  list_2 shall contain all $r$-tuples (for $r\in\{1,...,m\}$; $m$ is the size of list_1) with the form

  $(M_{i_1},...,M_{i_r})$, such that $i_j$ is an entry of list, that comes before $i_k$ for all $j<k$.

  For example, $i_j=[3,8]$ comes before $i_k=[4,7]$.

In our example, list_2 looks like this:

$(M_{3,7}),(M_{3,8}),(M_{4,7}),(M_{4,8}),
(M_{3,7},M_{3,8}),(M_{3,7},M_{4,7}),(M_{3,7},M_{4,8}),(M_{3,8},M_{4,7}),(M_{3,8},M_{4,8}),(M_{4,7},M_{4,8}),
(M_{3,7},M_{3,8},M_{4,7}),(M_{3,7},M_{3,8},M_{4,8}),(M_{3,7},M_{4,7},M_{4,8}),(M_{3,8},M_{4,7},M_{4,8}),(M_{3,7},M_{3,8},M_{4,7},M_{4,8})$.

I would like to have this in general for arbitrary natural numbers $a,b,c,d$ with $a \leq b$ and $c\leq d$.

I would be very grateful, if somebody was able to send me a pseudo-code.

Thanks for the help!


texts: Find shortest path that goes through at least 5 red edges

texts:
Let $G=(V,E)$ be a directed graph, $\omega : E \rightarrow R$ a weight function, and $s,t \in V$ a pair of different nodes. It's given that $G$ doesn't have a negative cycle. Moreover, 10 of its edges are colored in red (let's say that the rest are colored in blue).

I want to find an efficient algorithm that find the shortest path between $s$ and $t$ that goes through at least 5 different red edges.

Notice that going more than once through the same red edge is still considered as going through 1 red edge in the path.

One idea that I had was creating a graph $G'$ that will have a copy of every node for every possible set of red edges in $G$. That means that if we go through some red edge $e$, then the path will "move" to a variation of $G$ where $e$ is colored in blue and all the rest is the same.

However in this solution I will have to copy each node and each edge around 400 times. This will result in the same complexity asymptotically, but with such a big constant it seems really not efficient.

Another idea, was to somehow build the new graphs "on the run" of Bellman-Ford algorithm, but I don't really know how to do it.

I'll appreciate some help.


texts: Generalizing the linear subset scan algorithm to a wider class of objective functions, maybe by finding a paper

texts:
Given a list of pairs $(a_1,b_1),\ldots,(a_n,b_n)$, where all $a_i \geq 0$ and all $b_i > 0$, my general problem is when we can use linear subset scan (described below) to solve the optimization problem of finding the optimal combination of pairs,

$$I^* = \hbox{argmax}_I F(\sum_{i \in I} a_i) / G(\sum_{i \in I} b_i)$$

where $F,G$ are given increasing positive functions for positive inputs.

I have found a class of functions where there is a fast solution, namely $F(x) = x + A$ and $G(x) = (x + B)^\beta$ where $A,B \geq 0$ and $0 \leq \beta \leq 1$.  In this case, the optimal solution can be found by sorting all pairs $(a_i,b_i)$ in decreasing order according to $a_i/b_i$, and then trying the first $k$ pairs in sorted order for all $k$ and choosing the best solution, and this gives the optimal solution.  (This is an example of linear subset scan optimization.)

Now I want to know, if there a general class of functions $F,G$, ideally defined by abstract properties, where this linear subset scan approach works, where pairs are sorted either according to $a_i/b_i$ or perhaps sorted according to $H(a_i,b_i)$ where $H$ depends on $F,G$?  This could be a question where someone has a new insight and proof, or simply someone has seen something like this in the literature.  At any rate, I feel like the class of $F,G$ I stated where I have a proof is perhaps not the most general possible, and I'm missing some key abstract property that makes the linear subset scan work.


texts: Finding the smallest tree of given weight

texts: Take a node-weighted, undirected graph $G$, and a node $r$ in $G$. Is there an efficient algorithm to find a tree in $G$ rooted at $r$ which has total weight at least $w$ and contains a minimal number of nodes?


texts: What is the name of this prime number algorithm?

texts:
Does the following recursive algorithm have a name? If so, what is it?

procedure main():
 myFilter = new Filter( myPrime = 2 ) //first prime number
 print 2 //since it would not otherwise be printed
 for each n in 3 to MAX:
  if myFilter.isPrime(n):
   print n

object Filter:
 integer myPrime
 PrimeFilter nextFilter = NULL

 procedure isPrime(integer n):
  if n is multiple of myPrime:
   return FALSE
  else if nextFilter is not NULL:
   return nextFilter.isPrime(n)
  else
   nextFilter = new PrimeFilter(myPrime = n)
   return TRUE

Sample implementation in Java here

This is similar to the Sieve of Eratosthenes though after some discussion in the CS chat, we decided that it is subtly different.


texts: Is running AES NI in parallel possible (one encryption per core/thread)?

texts: AES NI seems to perform AES operations much faster than doing in software. However, if I have a machine with a large number of cores (say 32 cores), can I perform 32 AES encryptions using AES NI instruction i.e. one per core? Or can I just run one AES instruction?


texts: How many edges before a random graph is connected?

texts:
Let $G$ be a undirected graph with $n$ vertices and no edges, and let $f(k)$ be the probability that if we add $k$ edges randomly to $G$ that $G$ will be connected. How would one determine $f(k)$ for a given $n\in\mathbb N$?

Specifics:

When we add an edge to the graph $G$, any edge that can exist would be equally likely to be added. We can not add the same edge twice, so when $k=\frac{n^2+n}2$ (the number of possible edges in a graph with $n$ verticies), then $f(k)=1$.

Definition for connected may be found on wikipedia.


texts: Show that { xy ∣ |x| = |y|, x ≠ y } is context-free

texts:
I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question?

Anyway, here's the question:

  Show that the language $L = \{xy \mid |x| = |y|, x\neq y\}$ is context free.


texts: Proving the validity of a sequent using Modus Tollens

texts:
Problem: Prove $p \rightarrow (q \vee r), \neg q, \neg r \vdash \neg p$ using Modus Tollens.
I need to prove the validity of the above sequent by using natural deduction. Initially, I didn't read the entire problem, and went the long way by doing an implication-elimination, two negation-eliminations, an or-elimination, and finally a negation-introduction. Then I read the problem and realized I had to use MT, and now I'm stuck. I don't have the greatest grasp on propositional logic and natural deduction. Am I allowed to do the following?
Since I have $\neg q$ and $\neg r$ as my premises, can I use an and-introduction and do $\neg q \wedge \neg r$, which would allow me to immediately use MT to deduce $\neg p$? If not, could someone point me in the correct direction? Thanks.


texts: Maximum Weight Planarization of Size $n$

texts:
Problem: Maximum Weight Planarization

Given a weighted non-planar graph with $n$ vertices, and $m = \mathcal O\left(n^2\right)$ edges.
Find the subgraph with $n$ nodes (but possibly removing edges to make it planar) that has the most weight (i.e the sum of the weight of the edges in this subgraph).

Questions:

Is this a known problem with a name?
Any efficient solutions?
If no efficient solution is known, what about a variation when the maximum degree is limited by a constant, $k$?


texts:
We know that $\mathsf{DSPACE}(\log\log n) = \mathsf{DSPACE}(1)$ according to this proof.
Can we claim that $\mathsf{DSPACE}(n)=\mathsf{DSPACE}(n/\log\log n)$ or something like $\mathsf{DSPACE}(n^3)=\mathsf{DSPACE}(n^3/(\log\log n)^k)$ for some $k\in \mathbb{N} $?


texts: How do I follow the text of this Longest Common Sequence proof?

texts:
I'm working through a proof that is a simplified version of David Maeirs LCS reduction from the VERTEX-COVER problem and I had a question about a specific set of instructions and how to execute them by hand.

Background Information
This works out to look like the below as a graph (please excuse the grid lines)

The part I don't understand of the proof

Now I think this would imply that I need to line up S0-S7 vertically and using that rule show I can find the LCS, which was shown in my proof to be

  $$00000001000000000000000000000100000000000000100000001$$
  $$0^710^{21}10^{14}10^71$$

I tried doing that but was unable after many attempts to show that I could in fact induce $Topt$ from the sequences below. Could someone explain where I'm going wrong here? Did I misinterpret the instructions?

  $S0 =00000001000000010000000100000001000000010000000100000001$

  $S1 =00000000000000100000000000000100000001000000010000000100000001$

  $S2 =00000001000000000000001000000000000001000000010000000100000001$

  $S3 =00000001000000000000001000000010000000000000010000000100000001$

  $S4 =00000001000000010000000000000010000000100000000000000100000001$

  $S5 =00000001000000010000000000000010000000100000001000000000000001$

  $S6 =00000001000000010000000100000000000000100000000000000100000001$

  $S7 =00000001000000010000000100000001000000000000001000000010000000$

EDIT: I tried everything I could think of to see if I could make any of them work but didn't think it was relevant enough to include, if you want to know what I did I can list them.


texts:
Today I stumbled upon a problem which looked like the partition problem but certainly is different.

Given array of positive integers, guaranteed to not be divisible into two continious subsets of equal sum, remove a ceratin continious subset to form two subsets of equal sum.

Example:

Array: 7 5 9 1 3 9 6
Remove elements 9 and 1 to form array 7 5 3 9 6  that is divisible
into two subarrays of equal sum {7,5,3} and {9,6}

Another example:

Array: 1 10 100
Whichever subset to remove in the second case, it is not possible
to split the array into two parts with the same sum.

The limits for the array are 8000 elements and each element can be 1 bilion in size.

I'am just looking for algorithm help as I thought this was a variation of the partition problem and tried for some time to solve it, but i figured out it's beyond my knowledge. Any kind of help would be appreciated.


texts: Efficient membership check in multiple ranges

texts:
Suppose a program has a set $S$ of $n$ numerical ranges, each described by a pair: (lower bound $l_n$, upper bound $u_n$).

The program receives a number $x$; it must return all ranges in $S$ that enclose $x$.

An example in practical terms: in timeseries data, you have a set of $n$ independent events that occur over ranges of times. Given a point in time, you want to find the events that coincided with that point.

The naîve $O(n)$ solution:

out ← {}
for r in S:
  if (r.l ≤ x and r.u ≥ x):
    out.add(r)
return out

Is there a strategy for sublinear membership checking (in terms of $n$)?


texts: Can Haskell ensure a Functor (or other typeclasses) satisfies its law?

texts:
It seems that Functor definitions in Haskell can be accepted if the type is correct.
This code compiles, but it doesn't satisfy the functor law:

data Bst a = NIL | Node a (Bst a) (Bst a) deriving (Eq, Ord, Show)

instance Functor Bst where
  fmap _ NIL = NIL
  fmap f (Node v left right) = Node (f v) (fmap f right) (fmap f right)

Is is possible for Haskell to check if the functor definition satisfies the functor law?
If Haskell cannot, can Agda/Idris do this?


texts:
There is a very simple randomized algorithm that, given a 3SAT, produces an assignment satisfying at least 7/8 of the clauses (in expectation): choose a random assignment. A random assignment satisfies each clause with probability 7/8, and so linearity of expectation shows that the expected fraction of clauses satisfied by a random assignment is 7/8.

Can this be done in a deterministic way? If so, why are we interested in the randomized algorithm?


texts:
I know the basic idea and difference between hard and soft RTOS.

I wanted to know a large scale and specific example of soft RTOS. I read in this site that even LINUX is a soft RTOS.

Is the performance degradation due to non-predictability of the task the main advantage of this OS or are there some more disadvantages?

Also, what are its advantages over hard RTOS? Apart from it's not that time strict?


texts: How to generate all combinations given an array of elements using backtracking?

texts:
Given an array, generate all combinations

For example:

Input: {1,2,3}

Output: {1}, {2}, {3}, {1,2}, {2,1}, {1,3}, {3,1}, {2,3}, {3,2}, {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}

I am practicing Backtracking algorithms and I think I understand the general idea of backtracking. You are essentially running a DFS to find the path that satisfies a condition. If you hit a node that fails the condition, exit the current node and start at the previous node.

However, I am having trouble understanding how to implement the traverse part of the implicit tree.

My initial idea is to traverse down the left most path which will give me {1}, {1,2}, {1,2,3}. However, once I backtrack to 1, how do I continue adding the 3 to get {1,3} and {1,3,2} afterwards? Even if I have 2 pointers, I would need it to point to the 2 to eventually get {1,3,2}.

Am I approaching this problem correctly by drawing this implicit tree and trying to code it? Or is there another approach I should take?

I am not looking for code to solve this, rather I am looking for some insight on solving these kinds of questions.


texts: Finding the Entropy of a random experiment with probability of $\frac{1}{3}$

texts:
Entropy is the randomness collected by an operating system or application for use in Cryptography or other uses that require random data. The formula for Entropy is $$H(p_1, ..., p_k)=-\sum_{i=1}^{k} p_i\log_2(p_i)[bit]$$

So if I were to calculate the Entropy of a coin toss. it would be
$$H(\frac{1}{2}, \frac{1}{2})=-(\log_2(\frac{1}{2})+\frac{1}{2}\log_2(\frac{1}{2}))=-(0-1)=1 Bit$$

But why is there a $\frac{1}{2}$ before the $\log$? Also if I were doing an experiment where the probability of an outcome is $\frac{1}{3}$ and there are $3$ outcomes, so would the entropy be

$$H(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})=(\log_2(\frac{1}{3})+\frac{1}{3}\log_2(\frac{1}{3})+\frac{1}{3}\log_2(\frac{1}{3}))$$


texts: Using the pumping theorem to show that this language is not context-free

texts:
Let $\sigma = \{a,b,c\}$ and let $L = \{s | s = a^jb^jc^k\}$ where $k=i\cdot j$ and $i,j \geq 0\}$. Using the pumping theorem, prove that $L$ is not context-free.
I really don't know where to start, here. Nobody in the class knows what to do and we're all failing pre-curve.


texts: How to sort objects based only on "less than" relationships?

texts: Say I have n objects, each with an unknown value, and a n by n matrix Z. Such that Z(i,j)=1 if the value of object i is less than the value of object j, and Z(i,j)=0 otherwise. How can I sort these n objects, given only the matrix Z?


texts:
I am looking for a reference on the following variant of a Voronoi diagram:

Instead of seed points, there are seed rectangles which are axis-parallel and pairwise-disjoint.
Instead of Euclidean distance, we are interested in Manhattan distance.

The goal is to partition the plane into regions, such that the points in each region $i$ are closer (in Manhattan distance) to rectangle $i$ than to every other rectangle.

What would such cells look like? Are there algorithms for finding them?


texts:
I am curios how simon's algorithm works and I have read this post
Simple explanation of Simon's Problem but still is not clear for me.

I have found on th internet this example https://www.cs.vu.nl/~tcs/ac/ac-11_simon_algorithm.pdf. Can somebody explain how are calculated the value of Simon's algorithm?

If we take the above example:

f(000) = f(011) = 010.

How are the values obtained?

Can somebody explain the algorithm or knows a good source where this is explained well?

Thank you


texts:
I stumbled upon this wikipage that has got this proof :

I rechecked sum rule of differentiation.

And i can not understand where is this wrong.

Any Tips ?

I think that the second line

x^2 = x + x +... x times...

being used for differentiation is wrong. but i am not sure .


texts: Effiecient Repeat Evaluation of Large Multivariable Expressions

texts:
I am working with a professor to implement an optimization algorithm for determining the maximum and minimum of large (100+ variable) multi-variable expressions (not restricted to polynomials). Part of this process involves picking random values for all variables and then evaluating the expression for near "neighbors" (slight variations in all sub-sets of the variables).

Simplified Example:

f(x,y,z) = x^2 + sin(y/x)/log2(3z)

Start at random point (1,1,1)
Test all neighbors by altering each variable by +/- 0.1:

{1,1,1.1}, {1,1.1,1}, {1, 1.1, 1.1}, {1.1,1,1}, {1.1,1,1.1}, {1.1,1.1,1], ...

Over the course of the optimization the same expression will be evaluated many millions of times. It seems like there must be an efficient way to prevent reevaluating portions of the expression that have already be evaluated, or at least recently evaluated. I am struggling to come up with an efficient way of doing this. I understand that computers are smoking fast at math calculations so maybe attempting this optimization is unwarranted even with large expression size, however expression evaluation is the bottleneck in the process at the moment. Thanks for you time and thoughts on this!


texts: Practical implications of strongly polynomial time algorithm for linear programming

texts: Why do people care about whether a strongly polynomial time algorithm for linear programming exists or not? Does this have any practical improvement?


texts: Smaller approximation ratio for larger input size?

texts: Is it possible for an approximation algorithm (for minimization optimization problem) to obtain smaller approximation ratios for inputs of larger size? For example, is $1/n$- or $1/\log n$-APX reasonable? If it is, do you know any natural problems?


texts: When our two-state PDA constructed from CFG is non-deterministic PDA?

texts:
We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule which applied for differing between DCFG and non-Deterministic-CFG also applied here. i mean when we have non-Deterministic δ (delta) implied non-Deterministic edge in our PDA. if my suspicion is right , then for every DCFL exist at least one DPDA with two state. Am i right?

R ≝ Production Rules of CFG
(x,y,"LBL") is a labeled-edge between x and y with “LBL” as a label
∀r∊R: r= (A,aⱰ) ( A∊V ⋀ a∊T ∧ Ɒ∊V*) add (q,q,"a,A/Ɒ") to E
Add (q,q,"ε,z/Sz′") to E
Add (q,f,"ε,z′/z′") to E


texts: Is queue a storage allocation area in memory?

texts: We mainly study about heap and stack data structures which act as storage allocation area in memory. Is it that queue is also a storage allocation area in memory? As far as I know, process control blocks are made in OS region and actually they also act as storage allocation area only so can I consider queue to be a storage allocation area in memory?


texts:
An object K in a category C is called a generator if, for all pairs of
  morphisms f, g : A → B between arbitrary objects A and B, f = g iff ∀e
  : K → A. f ◦ e = g ◦ e.

Source: http://events.cs.bham.ac.uk/mgs2012/lectures/ReddyNotes.pdf (Page 7, Definition 3)

Can someone help me break down the meaning of this definition?

  for all pairs of morphisms f, g : A → B  between arbitrary types A and B

A morphism can be thought of as a a mapping from one type to another?

f and g are morphisms from type A to type B?

  f = g iff ∀e : K → A. ...

Morphism f is equivalent to morphism g if and only if for the morphism type K to type A

  f ◦ e = g ◦ e

e applied to f is equivalent to e applied to g

Is my interpretation of this correct?

The number of steps in this definition blows my mind, can anyone help me visualize the entire definition?


texts: Analogy between Gödel's incompleteness proof and Richard's argument

texts:
If we take a look at Gödel's paper “On formally undecidable propositions”,
the first self referential proof given in the paper, with the following formula:

$$n \in K \equiv \overline{\textit{Bew}}[R(n); n]$$

Which look like this in more modern mathematics:

$$K = \{n \in \mathbb N : \lnot\text{provable}(R_n(n))\}$$

Gödel says:

  The analogy of this argument with Richard antinomy leaps to the eye

I'm trying to figure out how this is the case:

I know Richard's Paradox basically uses Cantor's diagonal argument.

Which begins its set description like so:

$$X = \{s \in S : s \not\in f(s)\}$$

We can see the similarity between this and and Gödel's argument, especially given that both set/class descriptions end up with a self-referential contradiction.

However, I'm trying to construct a more rigorous comparison between Richard and Gödel's arguments, and how they are considered to be analogical of each other.

In particular, how the contradictions are seen to be analogous by Gödel.

Can anyone help out?


texts: What complexity class is this ciruit problem?

texts:
I'm exploring an algorithm that solves k-SAT.  It uses a ton of preprocessing, so I'm thinking that this will be a circuit bounds.

Without knowing the runtime, I speculate on how quickly it will solve k-SAT instances.  It will either solve all instances of k-SAT with probability $p$, or it won't be able to solve any instances.  The runtime is based on $p$.  Essentially, it runs in quasi-polynomial time.

So essentially, what we have is an algorithm that runs in time $2^{O((\log{n})^{c_1})}\cdot O(c_2 + q)$, and solves all instances with probability $\frac{2^q-1}{2^q}$, or it can't solve any instances.  Here, $c_1$ and $c_2$ are constants.

It also requires space polynomial in $q$.

I'm trying to find what complexity class this is, and what is known about it.

SOME NOTES

Just to ensure I've described this correctly, I have an algorithm that either solves all instances, or it can't solve any.  We can say it uses $2^{2^n}$ preprocessing.  Then, it runs in time that is quasi-polynomial multiplied by a function of $q$.

THE QUESTION, AGAIN

What complexity class is this, and what is known about it?


texts: What is the actual formula for the efficiency in CSMA/CD?

texts:
Let there are $n$ devices in the setup. Let each device sends data with a probability $p$.
Successful transmission for a slot (hence of the setup in general) occurs when only one device communicates.
Hence using the binomial theorem, we have $P_{success}= \binom{n}{1}\times p \times (1-p)^{n-1}$.
Differentiating $P{success}$ with respect to $p$ and equating it with $0$, we have $p=\frac{1}{n}$. So,
$P_{success} |max = (1-\frac{1}{n})^{n-1}$
For infinitely large number of devices we have $P_{success} |max  = \frac{1}{e}$.
So the probability of success in the system is $\frac{1}{e}$ and let be $n$ trials.
So expected number of successes = $n \times p = \frac{n}{e}.$
Now for 1 success, we have $1 = \frac{n}{e} \implies n=e$.
Or in other words there is success in $1$ out $e$ trials. [$P_{success} |max  =\frac{1}{e}$ ] So the number of trials to get one success is $e$.
Here we are finding the average situation. Before a success there are $e-1$ no. of failure in a slot with $e$ trials.$^\dagger$ So these slots with $e$ trials repeat. And hence if $c$ is the no. of failures,
$$\text{Efficiency} = \frac{T_t} {2*c*T_p+T_t+T_p}$$
$$= \frac{1}{2\times c\times a+1+a}= \frac{1}{1+(2c+1)a}= \frac{1}{1+(2(e-1)+1)a}$$
$$ =\frac{1}{1+4.4a}$$
[Here is a material from MIT]
But in many places, I find the formula as $\frac{1}{1+6.44a}$. (Simply because in the $\dagger$ they assume $c=e$ which is not correct. Just as in here.)
Again in the Computer Networking : A Top-Down Approach by Kurose and Ross states the formula to be:
$$\text{Efficiency}=\frac{1}{1+5. \frac{T_p}{T_t}}$$
Which is the correct one and which one to follow?


texts: Minimally satisfying multiple qualitative requirements at once

texts:
I am trying to design an algorithm that will generate the full list of ways to minimally satisfy multiple requirements, given information on how the individual requirements are fulfilled.

For example, let's say you can either have (1) or not have (0) four different foods: Apple, Banana, Carrot, Donut.

Requirement 1 says "You must have an Apple and a Banana." (1,1,0,0) satisfies this. So do (1,1,1,0), (1,1,0,1), and (1,1,1,1), but these are not minimal solutions, since you could take away the Carrot and/or Donut and still satisfy it.

Requirement 2 says "You must have three foods." (1,1,1,0), (1,1,0,1), (1,0,1,1), and (0,1,1,1) are all minimal solutions for this. (1,1,1,1) is not minimal.

I already have ways of generating the minimal satisfying solutions above. They aren't optimal but the search space for each individual requirement is small enough that it doesn't matter. Here's where it gets sticky: generating a list of ways to minimally satisfy both at once.

The brute-force approach to minimally satisfying both at once is then easy, as long as no requirement turns from satisfied to unsatisfied by adding a food (i.e. there's no requirement that says "You must not have a Donut"). Simply (first) look at all combinations of successful arrays, one from each requirement, and take the maximum of each element. For example, combine (1,1,0,0) from Requirement 1 with (1,0,1,1) from Requirement 2 to get (1,1,1,1) to satisfy both. Then (second) prune out non-minimal solutions by comparing each array that satisfies all requirements against each other to get the minimal solutions (1,1,0,1) and (1,1,1,0).

But this is very slow! The runtime grows very quickly with the number of requirements, or successful arrays per requirement. And it generates a lot of redundant output before pruning (for example, (1,1,0,0) plus either (1,0,1,1) or (0,1,1,1) both make (1,1,1,1)).

I'm at a bit of a loss as to how to attack this differently so as to avoid searching every combination, and would appreciate any help. I only have minimal theoretical-CS training and feel like there's probably some terminology or analogous known algorithm I'm not aware of.


texts:
I've been struggling with this problem for days now, making no progress:

There are N points on an XY plane. In one turn, you can select a set of collinear points on the plane and remove them. Your goal is to remove all the points in the least number of turns. Given the coordinates of the points, calculate two things:

The minimum number of turns (T) needed to remove all the points.
The number of ways to to remove them in T turns. Two ways are considered different if any point is removed in a different turn.

-- https://www.hackerrank.com/challenges/points-in-a-plane
I've tried a greedy exhaustive solution, where I draw a line between each pair of points, then start to eliminate the lines in descending order based on the number of points they cross. Unfortunately, there is at least one case where this approach produces suboptimal results:
For ease of discussion, I will call lines "longer" or "shorter", based on how many points they include. The greedy algorithm is simply to eliminate lines in order of descending length.
Suppose we have a set of N longer lines, and another set of M shorter lines. Our greedy algorithm will eliminate the long lines first. But what if every single point of the long lines is also included in a short line?  In that case,our initial elimination of the N longer line was a waste, since we would have gotten those lines "for free" had we just eliminated the shorter lines. Specifically, our greedy approach will require N + M eliminations, where we could have cleared all points in just M steps.
The simplest example input demonstrating this is:
(0, 1), (1, 2), (2, 4), (3, 3)
(0, 0), (1, 0), (2, 0), (3, 0)
(0,-1), (1,-2), (2,-4), (3,-3)

As you can see, we have a line of length 4 running along the X axis, and 4 shorter vertial lines of length 3 perpendicular to it. Our greedy algorithm will first eliminate the longest line, after which there will be 8 sets of points remaining, with no more than 2 of them collinear. Eliminating those will thus take 4 steps, for a total 5, where we could have eliminated all points in just 4 steps, had we simply eliminated the 4 vertical lines first.
Could someone provide at least a hint at the general body of knowledge required to approach this? I solved many other HackerRank questions, but can't make any headway with this one.


texts: Efficient algorithm for this optimization problem? Dynamic programming?

texts:
I've created a diagram that depicts what I'm trying to accomplish.

Full-size Image

In the input sequence, the nodes are as close together as possible. But I want the white nodes to be as close to their respective black nodes as possible. The edges between nodes can be lengthened to try to minimize this error. They cannot be shortened. So, 1 -> 2 can be no less than 4, for example.

I've included a possible solution. The edges that have been lengthened are labeled. Note that lengthening an edge shifts all the nodes to its right.

This axis is continuous, but I could possibly discretize it if that helps.

I'm thinking a dynamic programming approach could work here but I'm not sure - I was never very good with DP.

What's the fastest running algorithm that can solve this? Can this be categorized / re-framed as a well-known problem?


texts:
I can't help but notice the uncanny resemblence JavaScript has to LISP.  JSON (JavaScript Object Notation), for instance, is a data structure that can be reconstituted into an object by subjecting it to an eval() function. Likewise, LISP data can also be executed as code.

This leads to my question: Is JavaScript Homoiconic or at least partially so? If not, why?


texts: Finding a specific "balls-into-bins" partition given its index in the lexicographical ordering

texts:
Given numbers $n,k\in \mathbb{N}$, we consider $\mathcal P$ to be the set of all possible partitions of $n$ balls into $k$ bins.

Alternatively, $\mathcal P$ is the set of all $k$-ary vectors in $\{0,1,\ldots,n\}^k$ such that the sum of the entries is exactly $n$.

For example, if $n=4$ and $k=3$, we get:
$$\mathcal P =$$$$ \{<0,0,4>,<0,1,3>,<0,2,2>,<0,3,1>,<0,4,0>,<1,0,3>,<1,1,2>,<1,2,1>,<1,3,0>,<2,0,2>,<2,1,1>,<2,2,0>,<3,0,1>,<3,1,0>,<4,0,0>\}$$

Simple combinatorics (Stars and bars) tells us that $|\mathcal {P}| =$$n+k-1 \choose n$.

Now the goal would be to compute $p\in \mathcal P$ given it's index in a lexicographical ordering on $\mathcal P$ (alternatively, consider each vector as a number in base $n+1$ and order $\mathcal P$ based on the number).

In the example above $\mathcal P$ is ordered, so for example, given the input $3$, we'd like to output
$<0,2,2>$.

So the question is:

  How to we compute $\mathcal P(i)$ efficiently (without enumerating all $\leq i$ partitions)?


texts: Detailed explanation about Damerau Levenshtein Distance algorithm?

texts:
I'm a fresh year Computer Science student. Our teacher gave us damerau levenshtein distance algorithm pseudo code (which he got from Wikipedia apparently) and asked us to explain how the algorithm works step by step. I've been looking around the net to find an article about that but nothing that explain how the algorithm works step by step. I tried to understand it myself but still have no idea how that works. Below is the pseudo code that he gave us :

algorithm DL-distance is
    input: strings a[1..length(a)], b[1..length(b)]
    output: distance, integer
    da := new array of |Σ| integers
    for i := 1 to |Σ| inclusive do
        da[i] := 0
    let d[−1..length(a), −1..length(b)] be a 2-d array of integers, dimensions length(a)+2, length(b)+2
    maxdist := length(a) + length(b)
    d[−1, −1] := maxdist
    for i := 0 to length(a) inclusive do
        d[i, −1] := maxdist
        d[i, 0] := i
    for j := 0 to length(b) inclusive do
        d[−1, j] := maxdist
        d[0, j] := j
    for i := 1 to length(a) inclusive do
        db := 0
        for j := 1 to length(b) inclusive do
            k := da[b[j]]
            ℓ := db
            if a[i] = b[j] then
                cost := 0
                db := j
            else
                cost := 1
            d[i, j] := minimum(d[i−1, j−1] + cost,  //substitution
                               d[i,   j−1] + 1,     //insertion
                               d[i−1, j  ] + 1,     //deletion
                               d[k−1, ℓ−1] + (i−k−1) + 1 + (j-ℓ−1)) //transposition
        da[a[i]] := i
    return d[length(a), length(b)]

I'm still trying to get the idea how it works step by step but if someone can help me I'll be very thankful.


texts:
Does finding the successor of an element in a heap take $O(\log n)$?
An heap is not a binary search tree, so couldn't an element's successor be found in $O(n)$ time?


texts: Does assembly language get translated to binary code? If so, is assembly language portable across machines?

texts:
I've tried to find the answer through Google but I've come across conflicting uses of terminology, so I just wanted to be absolutely clear.

Here is my understanding: High level code written in a high level language (C I think is one of the lowest-level high level languages) gets translated to assembly code by that language's compiler.

That assembly code then gets translated to machine code (aka binary code aka hexadecimal code) by something (not sure what does this translation).

Does that mean that assembly code, but not machine code, is portable across computers? Or is assembly also not portable, and the only thing portable is code written in a high level language?


texts:
Given

a unbalanced k-ary tree base (with internal nodes that represent operators and leafs representing values) from the space of all unbalanced k-ary trees T
a distance function delta(t, t') = number of edit operations to transform t into t'
the edit operations add(t) (adding a random leaf), remove(t) (removing a random subtree), relabel(t) (relabel a random node) merge(t, t') (merge t and t')

For a genetic algorithm I need to generate a population of n trees that are not more than k edit operations away from base. I must prove that any tree within this space has equal propablity to be generated and that any tree can be generated.

The only idea I can think of was:

draw a random number l within [0, k]
define a random sequence seq of size l edit operations
apply seq to base

This aproach though does not garanty that any tree less than k away from base is generated?!

//EDIT

My other approach:

Generate a random tree rt
Measure distance d and calculate seq the optimal set of edit operations beween rt and base
apply [k-d, d] edit operations to rt

I am not shure if in that way any tree can be generated with the same propability.


texts: The Urgent Flag(URG) is set whenever the sender's Application Layer wants to send some urgent data to the receiver. In this case, the Transport Layer does not wait for enough data to achieve maximum segment size. Now, my question is how do the routers in between recognize that the packet needs to be forwarded urgently(they do not have the transport layer)?


texts: Turing machine with "move to origin" instead of "move left"

texts:
You have a Turing machine which has its memory tape unbounded on the
  right side which means that there is a left most cell and the head cannot move left beyond it since the tape is finished. Unfortunately, you also find that on execution of a head move left instruction, rather than moving to the adjacent left cell, the head moves all the way back to the initial left most cell of the tape. Now figure out whether you can still use this TM effectively. The Turing machine with left initialize is similar to an ordinary Turing machine, but the transition function has the form

  $$\delta  \colon Q × Γ → Q × Γ × \{R, \mathit{INIT}\}.$$

  If $\delta(q, a) = (r, b, \mathit{INIT})$, when the machine is in state $q$ reading an $a$, the machines head
  jumps to the left-hand end of the tape after it writes $b$ on the tape and enters state $r$. Show
  that you can program this TM such that it simulates a standard TM.

I can't figure out how to simulate this as standard TM. One thought I have is to copy the content of the tape which is afterwards the left move to the starting point of the tape before making a left move. Any further help would be appreciated.


texts:
I am trying to solve the problem of finding the permutation, amongst all possible ones, of an array of strings, where the concatenation of them compares smallest lexicographically. I solve it with an sort with the following comparison

def concat_cmp(x, y):
    return cmp(x + y, y + x)

+ is the string concat operator.

The solution passed all the test cases, but I cannot prove its correctness. Specifically, I cannot prove that this binary relation is transitive. Any help?


texts: Criteria for selecting language for first programming course

texts:
As a university-level CS educator, the issue of which programming language to teach in the first programming course often comes up for discussion. There are thousands of languages to choose between, and lots of religious fever (or fevour) supporting one language camp over another. All of this subjective bias surrounding each programming language makes it very difficult for an educator to choose one.

My question is:

  What objective criteria can an educator use to select a programming language to use as the basis for a first year university programming course? What is the basis for these criteria?

Note: I do not want to see a list of programming languages and why they are the best one to use. The question isn't about the best language, it is about the criteria for selecting a language. Answers may however be use programming languages to illustrate particular points.

This question was inspired by another question which was deemed off-topic: https://cs.stackexchange.com/questions/1946/criteria-for-choosing-a-first-programming-language.


texts: How to find unary potential in belief propagation algorithm for Markov Random Field with a tree structure?

texts:
Given that I have a Markov Random Field with a tree structure, which means that belief propagation (or sum product) algorithm will give me the exact solution when I query for marginal probabilities.
I am trying to implement this where I am given the pairwise potentials of all edges and the unary potential of the root edge (but not the unary potential of the other nodes).
In order to implement the algorithm in Jordan, Michael I.: An Introduction to Probabilistic Graphical Models, chapter 4, I need to get the unary potential for all the other nodes. How can this be done? I did marginalization of the pairwise potentials to get the unary potential but this seem to get me the wrong answers when I query for a conditional marginal.


texts: Thomas write rula andview serializability

texts:
Yesterday our Professor told in the class that Thomas Write rule ensures view serializability, but while surfing on this topic today on internet I am not able to find any information about that claim. So is it always $TRUE?$

What he told was this-->

  Timestamp ordering ensures conflict serializability

  Thomas write rule ensures view serializability


texts: How to systematically think about building implicit tree or a search space graph?

texts:
I often see DFS is used interchangeably with backtracking specially in many permutation, combinations and subset problems. But usually DFS has implicit tree and does backtracking at leaf nodes whereas backtracking is on an implicit tree and does use pruning each branch.

My question is how to systematically think about relating a DFS graph explicit one to building an implicit search space graph?

Here is a backtracking framework:

boolean solve(Node n) {
    if n is a leaf node {
        if the leaf is a goal node, return true
        else return false
    } else {
        for each child c of n {
            if solve(c) succeeds, return true
        }
        return false
    }
}

Here is a DFS:

procedure DFS(G,v):
     label v as discovered
     for all edges from v to w in G.adjacentEdges(v) do
         if vertex w is not labeled as discovered then
             recursively call DFS(G,w)

Here is DFS used in permutation:

private void dfs(String str, int start, int k, StringBuffer sb, boolean[] marked, List<String> res) {
    if (start == k) {
        res.add(sb.toString());
        return;
    }
    for (int i = 0; i < str.length(); i++) {
        //if element is not visited yet
        if (!marked[i]) {
            //if input string has duplicates, ignore them and continue
            if (i > 0 && str.charAt(i) == str.charAt(i - 1)) {
                continue;
            }
            sb.append(str.charAt(i));
            marked[i] = true;
            // recursively go to next element
            dfs(str, start + 1, k, sb, marked, res);
            sb.deleteCharAt(sb.length() - 1);
            marked[i] = false;
        }
    }
}

how to visualize DFS in a search space rather than in a graph which already exists and interchangeably understand DFS and backtracking.

Search Space Sample for permute (ABC):

         ROOTNODE
       /     |     \
     A       B      C
   /   \    /  \    / \
  B    C    A   C  A   B
  |    |    |   |  |   |
  C    B    C   A  B   A

When i tried to solve myself i usually come up with the recursive solution but i did not start solving by visualizing using a general graph techniques like most solution online.

References:

http://exceptional-code.blogspot.com/2012/09/generating-all-permutations.html
https://discuss.leetcode.com/topic/46162/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partioning
https://stackoverflow.com/questions/1294720/whats-the-difference-between-backtracking-and-depth-first-search
https://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html
http://rangerway.com/way/algorithm-permutation-combination-subset
http://www.dataeng.net/2016/10/generating-all-permutations-of-string.html


texts: Verifying the minimum cost from each node to a sink node in linear time

texts:
Problem Statement:

Let $G= (V, E)$ be a directed graph with costs $c_e \in \mathbb{R}$ on each edge $e \in E$. There are no negative cycles in $G$. Suppose there is a sink node $t \in V$, and for each node $v \in V$, there is a label $d_v \in \mathbb{R}$. Give an algorithm that decides, in linear time, whether it is true that for each $v \in V$, $d_v$ is the cost of the minimum-cost path from $v$ to the sink node $t$.

Attempt:

The biggest challenge I find is the linear time limitation. The most relevant algorithm to consider here is the Bellman-Ford algorithm, but runs in $O(|V|\,|E|)$ time which is too slow, so it requires modifying for this problem.

I have also made an observation: If, for example, $(u,v) \in E$ and $c_{(u,v)} = 1$, and $d_u = 3$ and $d_v = 5$, then the label $d_v$ is wrong. This is because passing from $v$ to $u$ with a cost of $1$ and travelling from $u$ to $t$ in a minimum cost of $3$ for a total cost of $4$ is shorter than the supposed minimum cost from $v$ to $t$ given by $d_v$, which is $5$. I'm not sure if I can use this insight to produce a linear algorithm, but it's the furthest I have gotten so far.

EDIT:

This problem is not a duplicate of the other problem proposed, since the edge weights can be negative in this problem, but the edge weights are positive in the other problem.


texts:
I am working on this exercise with the purpose of learning how to provide proper proofs and I would like to know if my proof for the following problem is correct.

  Given a sorted array $A$ (of $n$ distinct elements) and three elements $x$, $y$, and $z$, where $x < y < z$. The problem is to determine whether $x$, $y$, and $z$ are in $A$ or not. Prove that any comparison-based algorithm for this problem needs at least $3\log n-c$ comparisons in the worst case, where $c > 0$ is some constant.

My current proof using a decision tree goes as follows:
A comparison based algorithm must have at least 2 outcomes per a single comparison. For example: >= or <. It can also have 3 outcomes: < or = or >. But it has to have at least two.

When trying to decide whether an element is in the array or not it could be equal to any of the $n$ elements or it might not be in the array. Thus we have $n+1$ leaves in the decision tree.

Because of this the height of the decision tree is at least $\log_2(n+1)$. This is a lower bound for deciding whether one element is in the array or not. If we want to decide if the 3 elements $x, y, z$ are in the array or not and we know that $x< y< z$ we can use this information to speed up the search by searching for $y$ first.

For example if the outcome of the first comparison is < then since we know that $x < y$ we can skip that comparison when searching for $x$ and save at least a step. Similarly, if the outcome of the first comparison is > then since we know $y < z$ we don’t have to redo that comparison when searching for $z$ and save at least one step.

So if the search for $y$ starts with some constant $c$ left-branches we save that many steps when searching for $x$ and if the search for $y$ starts with $c$ right-branches we save that many steps when searching for $z$.

Thus, if it takes $k$ steps in the worst case to search for the 3 elements a lower bound is:
$$ k \ge 3\log_2(n+1)-c \ge 3\log_2 n-c, $$
where $c$ is some positive constant.

Is this a correct proof? What I am unsure about is if the last statement is ok, where I just discard the "+1". And whether this holds true for "any comparison based algorithm". Any critique or suggestions are greatly appreciated.


texts: Partition into paths in a Directed Acyclic Graphs

texts:
I have a directed acyclic graph $G=(V,A)$, I want to cover the vertices of $G$ with a minimum number of paths such that each vertex $v_i$ is covered by $b_i$ different paths.

When $b_i=1$ for all the vertices, the problem can be solved in polynomial time. But I am searching for the complexity of the problem  when $b_i>1$ for at least one vertex $v_i$, do you know about any results that may help me?


texts: Algorithm for identifying correct subset

texts:
My raw data is composite, but for simplicity sake let's say they consist of three elements. One might consider a sample set thusly.

[A,a,1]
[A,b,1]
[B,b,1]
[B,b,2]
[C,b,3]
[A,c,3]

I need to create a subset that satisfy two key criteria.

All combinations of the two last columns is represented (lower case and numeric)
All upper case (first column) is represented at least once.

... in as few rows as possible. The data is not evenly distributed, meaning that e.g 80 percent of the rows in the input data may have b,1.
If that was the case, it would be wasteful to include  A,b,1 row, because I would have to include A,a,1 as well in order to make sure that a,1 combination is represented.

Though large data, the data is in memory. Accessing and iterating is relatively cheap. The data is static and may be processed over multiple passes .

Language is C#.

I'm not too happy about the title of this question, so if there is any key term that better describes this problem, feel free to comment/edit.


texts: What characterises vertices at fixed indices in all topological orderings?

texts:
Let $G$ be a DAG with $v \in V$. Suppose that there exists some $i$ such that for all topological orderings $v_1, \ldots, v_n$ we have $v_i = v$.

What's a set of necessary and sufficient conditions about $v$ for this to occur?


texts: Show that the regular language is contained in another

texts:
Let L1 and L2 be two non empty regular language. How can I show that the following expression is correct with an example ?
$\bigotimes$ denote the transducer cross product.

$L_1^+ \bigotimes L_2^+$ contains $(L_1 \bigotimes L_2)^+$

============================================================================

Thanks PHPNick. Would my version (rewritten from yours) be correct ? I am just trying to make it more explicit to verify my doubts. If my understanding of the cross product and the + operator is correct.

Let $L_1$ and $L_2$ be the following

$L_1 = \{u_1,u_2,u_3\} $ $L_2 = \{v_1,v_2,v_3\} $

Then $L_1^+$ and $L_2^+$ would be the set of all strings that can be made by concatenating finitely many (and at least one) strings (corrected by David Richerby)

$L_1^+ = \{u_1,u_1u_1,u_1u_1u_1,...,u_2,...,u_3,..., u_1u_2,u_1u_2u_1,\dots\} $

$L_2^+ = \{v_1,v_1v_1,v_1v_1v_1,...,v_2,...,v_3,..., v_1v_2,v_1v_2v_1,\dots\} $

The two sets defined in the question are thus

$L_1^+ \bigotimes L_2^+ = \{ (u_1,v_1), (u_1,v_1v_1), \dots, (u_1u_1,v_1), \dots, (u_1u_1,v_1v_1), \dots \}$
$(L_1 \bigotimes L_2)^+ = \{ (u_1,v_1), (u_1,v_2), (u_1,v_3), \dots, (u_2,v_1), \dots \}$

The set $L_1^+ \bigotimes L_2^+$ thus contains $(L_1 \bigotimes L_2)^+$ because we can see that $(u_1,v_1), (u_1,v_2)$ etc are present in $L_1^+ \bigotimes L_2^+$


texts: What is the difference between a state machine and a database

texts:
I didn't study computer science as a degree, so whilst having studied computer science, there are still gaps in my knowledge. Everything I read about 'state' sounds like some form of 'data' but kept in memory as opposed to a database. This keeps leading me to the question: is a state machine not just a way of storing data, like a database.
There is probably a very obvious answer to this, but I can't seem to find anything about it when searching Google, which leads me to think I'm way off in my understanding somewhere. Any pointers (not the memory type) into some good reading would be super helpful. Thanks!


texts: How can OS schedule disk requests efficiently without knowing the LBN to PBN mapping ?

texts:
I learn from the OS schoolbook that the OS has the function that schedule the disk requests with the knowing algorithms such as SSTF, SCAN .. However, the date layout inner disk drives now is very complex that we may can't know. Disk zoning, disk skew, disk slipping and many other features of disk drives changes the distribution of data layout.  So how can the OS do this work ?
Thanks!


texts: Algorithm to determine if a top-down non deterministic tree automata accepts some tree?

texts:
Given a non-deterministic top-down tree-automata.
is there an algorithm,
that can determine if there exists any tree that accepted by this automaton? if so, what is the most efficient algorithm known?
Thanks.


texts: Karp reduction from optimization problems to decision problems

texts:
When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other.

Focusing on Cook reductions, there exists a natural Karp reduction from the decision version of a problem to optimization version. Is the converse also true?


texts: Algorithm for compressing binary data that can efficiently be partially decompressed

texts:
So I have been given the following problem and since I have no experience at all in this field, I would really appreciate some advice/guidance.

These are the requirements:

So three times per second a certain amount (fixed per session) of 32-bit values come in. These values have to be stored into a file with a timestamp per data-entry and it must be possible to at any time, with a given timestamp and interval, read out the values that are stored in that file.

This is all relatively simple to do, but this produces a 5GB file every 24 hours. If this file is zipped, it just leaves a 500MB file, so it is compressable but in that case you can't instantly retreive datapoints because you would have to unzip the entire file.

So I was thinking that this could be solved like this:

Buffer the first 10MB of sensor data.
Then sort all the values by the amount of times that they contain the same value. (Sensor data, so quite a few of the channels will
mostly contain stable values)
Run an algorithm that detects recurring patterns, replaces those patterns with shorter values and defines a table with the recurring patterns and their replacements.
The compress the buffer and save it to the disk and compress every new series of sensor data with the pre-defined table.

If this would be implemented properly, it should be possible to uncompress an individual datapoint and the file is sorted by timestamp so finding the right one should be trivial with a binary search.

So I guess the questions I'm having are the follwing

Is this at all possible? I do not expect compression results near Zip and 2x - 5x would be enough.
What is a good (and if possible semi-easy to implement) algorithm to find patterns in binary data? I have been doing some research and I mostly ran into algorithms that only apply to text data.

Any form of help is greatly appreciated!


texts: Count all pairs of x,y such as x + y = c && x XOR y = d

texts:
Given two decimals $c$ and $d$;  $1 \le c,d \le 10^{12}$. Count all pairs of $x$ and $y$ that satisfy the following statements:
  $$
x+y = c\\
x \text{ XOR } y = d
$$

Killed already a day still can't solve that task in 2s. Even with optimizations brute-force algorithm doesn't terminate when $c$ and $d$ closer to upper bound.

UPDATE
Took a while to figure, here is solution:

void solve( Scanner in, PrintWriter out ) {
    long sum = in.nextLong();
    long xor = in.nextLong();

    long andMask = andMask( sum, xor );
    if( andMask == -1 ) {
        out.print( 0 );
        return;
    }

    long sample = sample( sum, andMask );
    if( sample == -1 ) {
        out.print( 0 );
        return;
    }

    out.print( combinations( sample, andMask ) );

}

long andMask( long sum, long xor ) {
    if( ( sum - xor ) % 2 != 0 ) return -1;
    return ( sum - xor ) / 2;
}

long sample( long sum, long andMask ) {
    if( ( ( sum - andMask ) & andMask ) != andMask ) return -1;
    return sum - andMask;
}

long combinations( long sample, long andMask ) {
    long combinations = 1;
    int major = major( sample );
    for( int i = 0; i < major; i++ ) {
        if( bitValue( sample, i ) == 1 && bitValue( andMask, i ) != 1 ) {
            combinations *= 2;
        }
    }

    if( andMask == 0 ) {
        combinations -= 2;
    }
    return combinations;
}

int major( long sum ) {
    int major = 0;
    while( sum > 0 ) {
        major++;
        sum = sum >> 1;
    }
    return major;
}

int bitValue( long value, int bit ) {
    return ( int ) ( value >> bit & 1 );
}


texts:
Since a MILP problem is not necessarily NP hard. How could I demonstrate that a  MILP problem is actually NP hard? There exists some smart and easy method to do that?
Many thanks!


texts: All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?

texts:
My book states this

  If a decision problem B is in P and
  A reduces to B,
  then decision problem A is in P.
  A decision problem B is NP-complete if
  B is in NP and
  for every problem in A in NP, A reduces to B.
  A decision problem C is NP-complete if
  C is in NP and
  for some NP-complete problem B, B reduces to C.

So my questions are

  If B or C is in NP-complete, and all problems in NP reduce to an NP-complete problem, using the first rule, how can any NP problem not be NP complete?
  If A reduces to B, does B reduce to A?


texts:
I'm trying to solve the following recurrence relation. I've gotten through two iterations, but I don't see any pattern. I would appreciate any help with this.

$T(1)=1$

$T(n)=6\ T(n/6)\ +\ 2n\ +\ 3$

I've manually ran through two iterations and found the following:

$T(n/6)= 36T(n/36)+14n+21$

$T(n/36)=216(n/216)+86n+129$

The pattern that I see is:

$T(n) = 6^k(n/(6^k))+ (I\ can't\ determine\ the\ pattern\ of\ these\ terms)$


texts:
Let M a finite state transducer define as : $M=<X,Y,S,\delta,\lambda>$
What we mean by quasi-linear finite automata?


texts: Large non-array data structure to describe order of elements

texts:
I'm looking to store the order of a series of elements and access the elements in "pages" (elements numbered 101-150, for example) as well as add and delete them. This is being implemented in a graph database which does not support arrays; unfortunately the clear choice is not an option. Additionally it will sometimes contain hundreds of thousands of entries.

I've considered BTrees pretty heavily - they seem to provide a lot of the functionality that we need and have low computational complexity for all operations. Since we'll be selecting based on paged retrieval time and ease of implementation, a good fit will have a low computational complexity while a bad fit will be linear or worse. We only need addition to the end of the sequence, deletion (we'll have a reference to the data which will be deleted), and retrieval of a page. Pages can overlap and their size will vary. We also will want to search based on something other than order.

Are there any data structures which will be a good fit for this use case?


texts:
TL;DR: If you have two entangled qubits in the state $|00\rangle + |11\rangle$, what is the result of applying the Hadamard gate on the second qubit, and why?

I am trying to understand $\text{PSPACE} \subseteq \text{QIP}(3)$ (Watrous, 2003), and have troubles understanding the following.

Hadamard gate: Given some qubit, one can test that it is in a uniform superposition by applying the Hadamard gate on it as it will map it to $|0\rangle$ in this case,
$$H(|0\rangle + |1\rangle) = |0\rangle.$$
By measuring it, you have some probability to get a $1$ iff. the qubit was not in a perfectly uniform state.

With entanglement: Now, the paper claims that you can use the Hadamard gate to detect entanglement as well. Given two qubits, $x,y$, that are perfectly entangled, you can have them in the superposition
$$xy = |00\rangle + |11\rangle.$$
I understand that if you measure $x$, then apply the Hadamard gate to $y$, it will not map it to $|0\rangle$ as it will be entirely determinated by the measurement made on $x$.

What I don't understand: They do not claim to be able to measure/collapse the qubits that are entangled with the qubits they want to test, so how does it work? If you have two entangled qubits in the state $|00\rangle + |11\rangle$, what is the result of applying the Hadamard gate on the second qubit, and why?

Where is it in the paper:

When skecthing the protocol at the end of the introduction section (End of first paragraph, page 2):

  If there is significant correlation between the low-index prover responses and the high-index verifier-messages, the uniformity test [Hadamard gate, measure 0s] will fail with high probability

When discussing the completeness of the protocol, in particular step 2. of the verifier (start of page 8):

  Next, the verifier applies the Hadamard transform to every qubit in each register of $\bar{R^u}$. If $\bar{R^u}$ now contains only 0 values, the verifier accepts, otherwise the verifier rejects. In short, the verifier is projecting the state of $\bar{R^u}$ onto the state where $\bar{R^u}$ is uniformly distributed over all possible values. It is easy to check that in the case of the honest
  prover the registers $\bar{R^u}$ are not entangled with any other registers, as each register of $P^u$ depends only on those of $R^u$, and are in a uniform superposition over all possible values. Thus, the verifier accepts with certainty in this case.

Also in the proof of soundess, same page


texts:
I've came across this expression regarding function composition in some notes by people from computer science, and I don't know what the notation "$::$" means.

\begin{equation}
g \circ f : A \rightarrow C :: a \mapsto g(f(a))
\end{equation}

I get what this expression is trying to tell me, but I am pretty disturbed by the fact that I don't know what "$::$" means exactly and how to read it. Can anyone tell me what is "$::$"?


texts:
We have that MIMA (Neumann MInimal MAchine) has the following commands:

I want to implement the Mima-command EQL adr (equal?) with the other Mima-commands.

We have that for that command it holds the following: $$\text{Accu} \leftarrow \left\{\begin{matrix}
-1 , &\text{ Accu }=M(adr)\\
0 , &\text{otherwise}
\end{matrix}\right.$$

I have done the following:

My idea is to compute -M(adr) and then to add it to Accu, and then to check if it i <0.
And then to compute the inverse of the result and check if it is <0.
Is it correct?

LCD const
LDV adr
NOT
STV adr
ADD adr
STV adr
JMN x
LDC -1
JMP z
x: LCD 0
z: NOT
   JMN m
   LDC -1
   JMP n
   m: LCD 0
   n: STV adr

Is the implementation correct? Could I improve something?


texts: Algorithm to test a graph for $t$-transitivity

texts:
I am looking for an algorithm, which given a graph $G$ and a natural number $t$, determines if $G$ is $t$-transitive.

I am also interested in knowing if this problem is in P, NP, NPC or some other interesting facts about its complexity class.


texts: How do we construct reductions for NP-Completeness

texts:
I'm wondering in what direction we construct reductions to prove that a problem is NP-complete. Say the question is asking to prove that the vertex cover problem is NP-complete given that the independent set problem is NP-complete.

In this case, do we start with an instance of the vertex cover problem and show how we can transform this instance into an instance of the independent set problem? Or, do we start with an instance of the independent set problem and transform it into an instance of the vertex cover problem?

I understand the relationship between vertex cover and independent set, however, I am confused on the direction of reduction.


texts:
I found this in information theory paper, P.3883*
the authors states the following

Most existing theoretic studies of network coding focus on DAGs due to its simpler structure and dure to the fact that one can always convert a cyclic network to its acyclic counterpart by taking into account the time index and the causality of information transmission. Nonetheless, when studying Pair Intersession Network Coding on a cyclic network, one cannot rely on this cyclic-to-acyclic conversion since after conversion, there are T symbols in the $(s_1, d_1)$ (resp. $(s_2,d_2)$) multicast session and network coding allows complete freedom of mixing the $2T$ symbols $[X]_1^T$ and $[Y]_1^T$.

It looks ambiguity because does it mean that we have input from 1 to T; or Is it field = T and size = 1 (since capacity = 1)? so I hope I find answer here.
Thank you ..
*for those who doesn't have access go to this site Paper

Responsing to D.W. (The following information is for reference about the paper.)
C-C. Wang and N. B. Shroff. Pairwise Intersession Network Coding on Directed Networks. IEEE Tran. on Info. Theo., Vol. 56, No. 8, August 2010.


texts:
What kind of data is stored in the RAM when it  is fresh out of manufacture?
Apart from certain basic instructions (if yes, what are they), are there numbers stored as well or are most of the memory cells just empty?


texts: Problems for which a small change in the statement causes a big change in time complexity

texts:
I know that there are several problems for which a small change in the problem statement would result in a big change in its (time) complexity, or even in its computability.

An example: The Hamiltonian path problem defined as

  Given a graph, determine whether a path that visits each vertex exactly once exists or not.

is NP-Complete while the Eulerian path problem defined as

  Given a graph, determine whether a trail that visits every edge exactly once exists or not.

is solvable in linear time with respect to the number of edges and nodes of the graph.

Another example is 2-SAT (polynomial complexity) vs K-SAT (NP-complete) although someone could argue that 2-SAT is just a specific case of K-SAT.

What do you call this kind of problems --if they even have a name? Can someone provide a list of other examples or some references?


texts: Parallel Algorithm for Donor/Recipient Matching - Graph Matching/Optimization

texts:
I'm not certain I can accurately describe the problem using my knowledge of discrete math, so pardon any inaccuracies. Happy to clarify any part of the question which is unclear.

Given the following constraints:

Two sets, each with 'n' elements: 'donors' and 'recipients'. $|D| = |R| = n $
Each donor has a maximal number of times they are able to be matched with a recipient: "max donations". $ maxd: D \to \mathbb{Z}_{+}$
A distance function, returning a real number representing the suitability of match between a donor and a recipient, given the number of times a donor has already "donated" / been matched with a recipient. $ distance: D \times R \times \mathbb{Z}_{+} \to \mathbb{R}_{+} $

Devise a parallel algorithm to determine the list of optimal matching. i.e. find functions $m: D \to \mathcal{P}(R)$ which defines a partition of $R$ and $l: D \times R \to \mathbb{Z}_{+} $ such that $\forall d \in D$   $ | m(d) | \leq  maxd(d)$

which minimize the following cost:

$$
\sum_{d \in D} \sum_{r \in m(d)} distance(d, r, l(d, r))
$$

Intuitively, I think this is NP-hard. So I was satisfied with my solution - using BSP treat the donations per donor in phases, where each iteration is a graph matching problem.

Is this the best I can do? Any suggestions?