texts: Solomonoff's theory of induction, Kolmogorov complexity and Bayesian Inference

texts:
My motivations for asking this question are philosophical in nature. I'm by no means a computer scientist though, and I feel as though this question should be answered by someone who is since it's one thing to read about a subject second hand and another to understand it first hand. I'm an A-level student of philosophy, physics and mathematics (UK qualification) if that helps you formulate an answer at all.

The question relates to the problem of induction in that, we have little reason to believe the universe is uniform and apply that expectation to science and inference. However, I've seen the claim made that this guy Solomonoff created a theory of induction that uses a Bayesian framework as well as something called 'Kolomogrov complexity' as an objective measure of 'complexity' in a model or hypothesis. For example, if we observe over and over again that all A's are B's, we might be tempted to formulate the hypothesis:

"All A's are B's",

This would be afforded the maximum credence from a bayesian framework since it predicts that A's are B's with a probability of 1 and we're attaching ourselves to the likelihood lover's principle. However, you could also formulate the hypothesis:

"All A's are B's until a time t where they are C."

And there are infinitely many of these hypothesis since the 'C' can represent literally anything. This has a bayesian multiplier equal to the previous hypothesis so technically have an equal credence if we don't prefer one of these in our priors. And the only way (it would seem) to decide between the two is to see if hypothesis 2 shows it's prediction at time t. So we would otherwise have to always wait until time t to see if hypothesis 1 is correct.

My question can be split up into three parts:

1) Is "Kolmogrov complexity" generally considered a genuine formulation of an objective definition for complexity/simplicity?

2) Would the former hypothesis, with such an understanding of complexity be considered more 'simple'?

3) How would this understanding of complexity be used practically when distinguishing between hypotheses? Or is it just obvious that the former type of hypothesis is more simple?

Although this is really a philosophical question, I suppose I would also like to know if anyone here has any ideas about why we should prefer more simple hypotheses. And perhaps, how would you increase your bayesian prior probability given some measure of complexity for a hypothesis?

Thank you in advance for any answers.


texts: Does the Y combinator contradict the Curry-Howard correspondence?

texts: The Y combinator has the type $(a \rightarrow a) \rightarrow a$. By the Curry-Howard Correspondence, because the type $(a \rightarrow a) \rightarrow a$ is inhabited, it must correspond to a true theorem. However $a \rightarrow a$ is always true, so it appears as if the Y combinator's type corresponds to the theorem $a$, which is not always true. How can this be?


texts: What does a square mean in a Boolean formula

texts:
I am reading the paper Measuring the hardness of SAT instances by Ansótegui, Bonet, Levy and Manyà (Proc. 23rd AAAI Conf. on AI, pp. 222–228, 2008) (PDF) and I would like to know what the square symbol in the following means

  Lemma 3 The space satisfies the following three properties:

  $s(\Gamma \cup \{\Box\})$ = 0
  For any unsatisfiable formula $\Gamma$, and any partial truth assignment $\phi$, we have $s(\phi(\Gamma))\leq s(\Gamma)$.
  For any unsatisfiable formula $\Gamma$, if $\Box\notin\Gamma$, then there exists a variable $x$ and an assignment $\phi\colon\{x\}\to\{0,1\}$, such that $s(\phi(\Gamma))\leq s(\Gamma)-1$.

  The space of a formula is the minimum measure on formulas that satisfy (1), (2) and (3). In other words, we could define the space as:3

  $$s(\Gamma) = \min_{x, \overline{x}\in\Gamma, b\in\{0,1\}} \big\{
\max\{s([x\mapsto b](\Gamma))+1, s([x\mapsto\overline{b}](\Gamma))\}\;\big\}$$
  when $\Box\notin\Gamma$, and $s(\Gamma\cup\{\Box\}) = 0$.

  3 Note that, since $\Gamma$ is unsatisfiable, it either contains $\Box$ or it contains a variable with both signs.


texts: Structure of a Pumping Lemma proof: contradiction or counterexample?

texts:
This site is full of Pumping Lemma questions, and I do admit I've not read them all. I've tried some proofs myself and they seem to work, but I can't find anywhere what is the (general) exact structure of a proof where you show a language is not regular or context-free?

Wikipedia and most proofs start with "Suppose $L$ is a regular language", which would mean it is a proof by contradiction, because it isn't.

But the lemma has the quantifiers $\exists, \forall, \exists, \forall$ in order. And in the proof you assume a given constant given by the first $\exists$, and then you come up with some word (the first $\forall$), format it in some given substring division (the second $\exists$) and again come up with some $k$ (second $\forall$) for which you show it is not in $L$.

This seems to me like a counterexample proof ("this is not context-free/regular because I can come up with a counterexample which fails the pumping lemma"), and not a proof by contradiction?


texts:
Given an array A(1 indexed based) of positive  integers.For each element A[i] find the minimum index (say idx) such that the product of all the elements from index 1 to idx is divisible by A[i].where(1<=idx<=i).

constraints are: the number of elements of the array 1<=n<=10^5 and

1<=A[i]<=10^5.

For example let A[]={2,4,6,8}

The output should be {1,2,3,2}

I could only think of O(n^2) solution but that gives a T.L.E.

I also looked up to the code of successfully accepted solution but could not understand the logic.I only understood that it is first calculating the smallest prime factor using seive and then calculating the prime factors of each A[i] using its smallest prime factor.However I am not able to understand the later part of the solution.

Here is the code of one of the accepted solution.

int main() {

ll n,arr[500001],minP[500001];
cin>>n;
for(int i=0;i<n;i++){
    cin>>arr[i];
}
for(int i=2;i<=500000;i++){
    minP[i]=i;
}
for(ll i=2;i*i<=500000;i++){
    if(minP[i]==i){
        for(ll j=i*i;j<=500000;j+=i){
            minP[j]=min(minP[j],i);
        }
    }
}
vector<ll> v[500001];
for(int i=0;i<n;i++){
    ll temp = arr[i],mx=0;
    while(temp>1){
        v[minP[temp]].push_back(i);
        temp/=minP[temp];
    }
    temp = arr[i];
    while(temp>1){
        ll x=minP[temp],cnt=0;
        while(temp%x==0){
            temp/=x;
            cnt++;
        }
        mx=max(mx,v[x][cnt-1]);
    }
    cout<<mx+1<<" ";
}

}

Also,Suggest me some relevant material to understand the underlying concept used above.

Here I have tried to implement the solution using binary search can anybody point the error as I am still getting the wrong answer upon submission.

 void Bsearch(int low,int high,int key,long long product[])
    {

    int ans;
    int mid;
    long long midVal;
    while (low <= high)
    {
    mid = low + (high - low + 1) / 2;
    midVal = product[mid];

    if (midVal% key!=0)
    {
        low = mid + 1;
    }
    else if (midVal%key==0)
    {
        ans=mid;
        high=mid-1;
    }
}
     cout<<ans+1<<" ";
}
  int main()
  {
int n;
cin>>n;
int arr[n];
long long product[n];
int i;
for(i=0;i<n;i++)
cin>>arr[i];
product[0]=arr[0];
for(i=1;i<n;i++)
product[i]=product[i-1]*arr[i];//prefix product array
for(i=0;i<n;i++)
{
    int temp=arr[i];
    Bsearch(0,n-1,temp,product);//Using binary search to find the minimum
                                  index.
}
}


texts: Not able to devise a concrete solution for the given graph query

texts:
I was trying to solve the following problem:

You are given a grid of size N×N that has the following specifications:

Each cell in the grid contains either a policeman or a thief.

A policeman can only catch a thief if both of them are in the same row. Each policeman can only catch one thief.

A policeman cannot catch a thief who is more than K units away from the policeman.

Write a program to find the maximum number of thieves that can be caught in the grid.

example:

N=3,K=1

P T P

T T P

T P T

Answer:3

I tried a simple BFS solution but my code if failing in which there are alternative P and T,am not able to handle this case with BFS.

My solution:solution(Its a bit lengthy,so didn't paste it here.)

It would be really helpful and highly appreciating if someone could suggest some algorithm or pseudo code for this problem statement.

PS:This was the question of this test.It was a timed test, couldn't solve it.

Thanks.


texts: Meaning of this python modulo operator exercise?

texts:
I just got started with Python PCEP course material on netacad.com.

I've come across the following exercises:

   2 % -4 = -2
   2 % 4 = 2

As I understand it, the modulo operator returns the remainder of a division. So 2 divided by (-4) gives (-0.5). How does Python3 calculate the remainder of that as 2?

I know it's stupid but what's the reasoning behind that result?


texts: Counting words: performance of loop vs. list comprehensions

texts:
I am no computer scientist, so I can be naively missing some commonly implemented optimization strategies but...

Looking at two ways of counting words in a text (shown below), I tend to think that the iterative method, as it runs through each word in the text only once, will use less memory than the second method, expressed as a list comprehension.

The iterative method:

wc = {}
for w in text.split(' '):
    wc[word] += 1

The list comprehension method:

wc = [text.split(' ').count(w) for w in set(text.split(' '))]

I tend to think that the list comprehension will use N^2 memory because it goes through all the words in the text for each word in the text.

Is this reasoning correct? In practice, interpreters and compilers optimize for this kind of situation?


texts: How literally is "optimization" or "optimization algorithm" used in CS?

texts:
I have been confronted with two meanings of the term "optimization" or "optimization algorithm":

to find the absolute maximum in a set $X$ according to some criterion $f:X\to \mathbb R$
to find a "relatively high" or "increasingly high" or "locally maximum" element in a set $X$ according to some criterion $f:X\to \mathbb R$

A friend of mine claimed that nr $1$. is the only "official" meaning of the term, and that only laymen or people who speak informally use the meaning of $2$. Is my friend correct?


texts: What does "terms evaluated in related environments yield related values" means in the context of typing judgements?

texts:
I am reading Theorems for free! by Philip Wadler which is a paper about how to derive theorems from the type signature of a function.

  Parametricity is just a reformulation of Reynolds’ abstraction theorem: terms evaluated in related environments yield related values.

What is an environment in this case ?
More generally, how do I interpret the statement in bold ?

I think I understand the parametricity thing correctly but somehow I cannot map this sentence to something more intuitive.


texts:
This is a Hackerrank challenge

$Knight$ is a chess piece that moves in an L shape. We define the possible moves of $Knight(a,b)$ as any movement from some position $(x_1, y_1)$ to $(x_2, y_2)$ satisfying either of the following:
 $x_2 = x_1 \pm a$ and $y_2 = y_1 \pm b$, or
 $x_2 = x_1 \pm b$ and $y_2 = y_1 \pm a$

Given the value of $n$ for a square chessboard, answer the following question for each $(a, b)$ pair where :
$1 \leq a \leq b \lt  n$

Constraints
$1 5 \leq n \leq 25$

What is the minimum number of moves it takes for $Knight$ to get from position $(0, 0)$ to position $(n-1, n-1)$? If it's not possible for the Knight to reach that destination, the answer is -1 instead.

If $a = b$ then it is simply $(n-1) / 2a$ if it is evenly divisible

What I cannot figure out is when some of the steps need to be backwards $x_2 \lt x_1$.

Can this be solved with an algorithm other than brute force?
If so what is the algorithm?

Brute force to me is iterate over all possible moves.

If brute force is it safe to assume $a$ and $b$ would never both be negative on a move? Answer is no.  If brute force could it be limited to one diagonal or the other?  Answer is no.


texts:
I want to create a PRNG for an integer only (with a max of 32767) system and tried to use an LCG. So I've chosen as $m = 32767$ and $c = 3$ and I tried to figure out a good $a$. However for the full period I have to choose $a = 32768$ which cannot be used since the maximum is 32767.

Can anyone help me creating a "good" LCG?

Another question: Since the maximum (could be / is) 32767 I don't know how to calculate the successor because $a * y_{-1} + 3$ could become greater than 32767 and this is not allowed in the system. So should I use $a * (y_{-1} \mod ((32767+3)/a) + 3$ then?


texts: Use AVL trees instead of Chord algorithm for Distributed Peer to peer Hash tables

texts:
In distributed systems we use the Chord algorithm to create a p2p distributed hash table. While this algorithm is very useful and efficient wouldn't it be better if we used an AVL tree? Chord algorithm relies a lot to the hash function (in order for the nodes to be distributed evenly).

An AVL tree on the other is always balanced so in the worst case it will take $O(h)$ time to search for something, whereas h is the height of the tree and given that AVL trees are always balanced the height of the tree is at most $logN$ (whereas N is the number of living nodes in the network).

In my opinion AVL trees can give the same search speed (or maybe even better). So what is the need to use Chord algorithm instead of an AVL tree? I understand that Chord Algorithm is more of a Peer to peer system as many nodes know many others while in an AVL tree each node knows two descendants. Is this the sole purpose of not using AVL trees?

Is there an issue with handling churns that makes one better than the other?


texts: How does "δ:Q×Σ→Q" read in the definition of a DFA (deterministic finite acceptor)?

texts: How do you say $\delta\colon Q \times \Sigma \to Q$ in English? Describing what $\times$" and $\to$ mean would also help.


texts: Why and how geometric series are used for proofs?

texts:
I often see that someone uses geometric series for proofs related to time complexity, but also I can't understand why they are used. Are they making proving easier? And how can I use this 'tool' for proofs? Can I transform problems to fit to geometric series?

For example the time complexity of this simple function to get a random prime is estimated by a geometric series, I don't see this is naturally (or rather intuitively) a geometric series.

The number of primes is guessed by $m / ln(m)$, so the expected value is
$$\sum_{i=1}^\infty i\left(1 - \frac{1}{\ln m}\right)^{i-1} \frac{1}{\ln m} = \frac{1}{\ln m} \cdot \frac{1}{1/(\ln m)^2} = \ln m.$$


texts: How can I learn Sunday's string searching algorithm?

texts:
How does Sunday's string searching algorithm work?

I am highly unskilled in processing mathematical lingo, so I would appreciate a use case/example.

A link would be ok. I tried searching the first 6 pages for terms "sunday's algorithm", "sunday's string search", "sunday algorithm example" but all I ever found were comparisons to other algorithms, or horrible, incomprehensible google translates to English.


texts: Correct bracketing check with rotate operation on position i

texts:
Given sequence (length $N$) of brackets like $($ and $)$. The task is to implement data structure which supports following operations:

Check whether the sequence is correctly bracketed
Rotate bracket at position $i$

I dont want a solution, but some feedback if I am on a good way.

There is no time complexity constraint in the instructions. So I suppose, it should be better than $O(N)$. Because trivial solution with stack leads to $O(N)$.

The only options are:

It can be done in logarithmic time by use of some smart tree data structure.
Or it can be done in amortized constant time which I actually believe to.

I have following ideas:

Define function $w(i)$ for each position $i$ by $w(0)=0$ and $w(i)=w(i-1)+d_i$ where $d_i=+1$ if the bracket is $($ and $d_i=-1$ otherwise. First bracket have index $1$.
Fact: The sequence is not correctly bracketed if and only if $w(N) > 0$ or there exists such $j$ for that: $w(j) < 0$.
So I want to keep tracking mimum $m$ of those $w(i)$. And for the first query I able to answer in constant time just by checking that $m < 0$ and $w(N) > 0$.
The problem is how to track the value of $m$ to achieve the best time.
If I rotate bracket on position $i$, all $w(i)$ from $i$ to $N$ are changed by constant $\pm2$. It implies the change of $m$. If I would update those $w(i)$ directly it would lead to again to linear time.
So I was wondering how to enclose this behaviour to another datastructure (post is here) in some smart way. But I just cant get over that. Everything I was thinking about is just linear. So is it possible at all?


texts: Number of buckets for bucket sort (most significant bits)

texts:
Wikipedia has this pseudocode on bucket sort:

  function bucketSort(array, n) is
    buckets ← new array of n empty lists
    for i = 0 to (length(array)-1) do
      insert array[i] into buckets[msbits(array[i], k)]
    for i = 0 to n - 1 do
      nextSort(buckets[i]);
    return the concatenation of buckets[0], ...., buckets[n-1]

It also explains:

  Here array is the array to be sorted and n is the number of buckets to use. The function msbits(x,k) returns the k most significant bits of x (floor(x/2^(size(x)-k))); different functions can be used to translate the range of elements in array to n buckets...

What baffles me is: Why would one want to initialize buckets with n buckets when 2^k is the maximum number of values that msbits can possibly generate, given the way it's defined?


texts: Logspace algorithm for balanced parentheses problem

texts:
Currently I want to learn the complexity of space, I read a few of the books on it. On this I encountered this example problem. I would just like to know how to show that the following problem $\in L $ (deterministic logarithmic space).

Input:  series of open or closed parentheses

Question: Are these parentheses properly balanced?

Example:  $((() ()) (()))$ should be accepted but $()) ()$ should be rejected.


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

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

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


texts: Doubt in derivation of a proof in Information Theory

texts:
In my class we were trying to derive Shannon's Source Theorem, first by proving the equivalent form in a weaker version.

The question is: Consider a biased coin with probability of heads $p \geq \frac{1}{2}$.We want to transfer this information with the code of minimum expected length.

To prove this, we can construct a code such that for any $\epsilon $, for large $n$, there exists a code such that average code length is less than $(1+\delta)nH(p) $ and also the lower limit of the code length is $(1-\delta)nH(p) $

We tried to prove it by first getting the inequalities
$$ \frac{2^{nH(p)}}{n+1}\leq{n \choose np} \leq 2^{nH(p)}$$
Both these inequalities are easy to derive. The problem comes with deriving the lower limit we try to prove that in an optimal code the length of the lower probability event is greater than equal to higher probability code, and then try to find the length of one of the events of higher probability an conclude by showing that since the lengths of events with lower probability is going to be more than this the expected length is more than  $(1-\delta)nH(p) $

Hence, since  $ \frac{2^{nH(p)}}{n+1}\leq{n \choose np} $, one of the events containing $np $ heads will be of length greater than $log_{2}\frac{2^{nH(p)}}{n+1}$ . That is $ nH(p) -\log_{2}(n+1) $ . However to complete this part of the proof I need to prove the probability of all events with less than $np$ heads is a constant. Is it true for a binomial distribution that for an event with probability of success greater than $c$ where $c$ is some constant independent of $p$? By proving this we can prove that the expected length of the code is greater than $ c \times (nH(p) -\log_{2}(n+1)) $ which comes up to $(1-\delta)nH(p) $


texts: Finding longest chain in poset in subquadratic time

texts:
Let $(A,\leq)$ be some finite poset. For $a,a' \in A$ we can determine in constant time whether or not $a \leq a'$. The height of an $A$ is by definition the greatest $n$ such that there are elements
$$
a_0 < a_1 < \cdots < a_n
$$
of $A$. By treating $(A,\leq)$ as a directed acyclic graph, we can determine the height of $A$ as the length of the longest path in this graph, which we can compute in linear time in the size of the graph; that is, in $\mathcal O(|A|^2)$.

Can we do any better for this special case where $A$ is a poset?

Edit: if it matters, I am especially interested in the case where the length of the longest path is already known to be significantly shorter than the size of $A$.


texts: Does interpreter for language L1 have to be written in lower level language L0?

texts:
While reading A.S. Tanenbaum's book "Structured Computer Organization", I had come to this paragraph. The text is about how interpretation of a program works.

  The other technique is to write a program in L0 that takes programs in L1 as input data and carries them out by examining each instruction in turn and executing the equivalent sequence of L0 instructions directly. This technique does not require first generating a new program in L0. It is called interpretation and the program that carries it out is called an interpreter.ote

My question is; does this program have to be written in L0 Language, by means of lower level language?
Can this program(interpreter) be written in L1 language and have its output to be L0 language?


texts: Determining which states in a transition system satisfy a specific CTL formula

texts:
Trying to answer the following question:

However, my answer is that only one of these states satisfy the TS (which is for sure wrong since the next part of this question asks to remove states that don't satisfy the formula and compute the new TS).

Reasoning follows:

1 - does not satisfy the formula since if you go to 4, EXISTS NEXT c is violated

2 - does not satisfy the formula since if you go to 4, EXISTS NEXT c is violated

3 - does not satisfy the formula since if you go to 1, EXISTS NEXT c is violated

4 - satisfies the formula since all paths satisfy EXISTS NEXT c

5 - does not satisfy the formula since if you go to 6, EXISTS NEXT c is violated

6 - does not satisfy the formula since if you go to 4, EXISTS NEXT c is violated

Can anyone see where I have gone wrong with my reasoning?

Something else I'm not sure about is for example if we take 4, it is satisfied since all paths lead to other states that (together) satisfy the equation. Do we need to include these 'other states' in the satisfaction set?

Really grateful for any help.


texts: Constructing non intersecting segments from distinct sets of points

texts:
Given 2 sets of points in the plane, $A$ and $B$, each of size $n$,
I need to construct n line segments of the form ($a$–$b$) ($a$ in $A$, $b$ in $B$) such that none of them intersect.

The coordinates are comparable signed reals (no constraints here about that) and no 3 points are on the same line. There can be no segments sharing an end point because we need to construct $n$ pairs of points from $2n$ points, and there are no duplicate points.

I tried to sort each of the sets according to $x$ or $y$, and pair the appropriate points from each of the sorted sets, but I found a counterexample for that:
a set of points whose sorted $x$ order was $(a_1,b_1,a_2,b_2)$ and sorted $y$ order was $(a_2,a_1,b_1,b_2)$.


texts: Find all pairs (i, j), such that i + (i+1) + (i+2) + ... + j = n

texts:
We have give positive integer $n$, and we want to find all the pairs $(i, j), i\leq j$ such that: $$i + (i+1) +(i+2)+(i+3)+ \dots + j = n$$

Clearly we can try all possible pairs in $O(N^2)$, but that is pretty slow. Here is my observation.

We already know that the sum of numbers from $1$ to $n$ equals $\frac{n\cdot(n+1)}{2}$. Using simple math we can show that the sum of the numbers in the range from $i$ to $j$ equals $\frac{(j-i+1)\cdot(i+j)}{2}$. If we fix number $i$ using this formula we can find $j$, and check if it is positive integer, but this is $O(N)$, can we go faster?


texts: Generalized Geography problem time and space complexity

texts:
We all know the algorithm that solves the Generalized Geography problem using polynomial space (it's described on wiki). My question is: what is the time complexity of this algorithm? I'd like a more precise answer than just 'polynomial'. As far as I understand, we're making $|V|$ calls at most? We won't call the function from the same node more than once because nodes are deleted once visited. And we also have to estimate how much does one iteration take, which, I assume, would be $O(|E|)$ since we're going through all vertices connected to the current one? So that would make the overall time complexity $O(|V|\cdot|E|)$.

I'm also curious about exact space complexity, not just 'polynomial' (I can see that), but something precise like $O(|V|^2)$. If I understand correctly, recursion depth in $O(|V|)$, would that mean that overall space complexity is $O(|V|)$ or am I missing something here?


texts:
Is there any known $NP$-complete problem which hardness proof is non-constructive.

A constructive $NP$-completeness proof is a proof that $L_1\leq_p L_2$ by a reduction $r$ and from the argument therein, one can extract two polynomial-time algorithms $f$ and $g$ such that:

  For every instance $x\in L_1$, given a certificate $w_1$ for $x$, we
  must have that $w_2=f(w_1)$ is a certificate for $r(x)\in L_2$

  For every instance $x\in L_1$, given a certificate $w_2$ for $r(x)\in L_2$, we  must have that $w_1=g(w_2)$ is a certificate for $x\in L_1$.

In $NP$-completeness result, that does not describe $f$ and $g$, we can say that it is a non-constructive proof. Given a certificate for an instance of $L_1$, one does not know how to construct a certificate for the corresponding instance of $L_2$ and vice versa.

In a sense, the proof only establishes the existence of corresponding certificates.

More specifically, do we have an existence-only proof for some $NP$-complete problem?


texts: How to find the supremum over all the "good" (interior) polytopes for a given set of 3D points?

texts:
Let $S \subset \mathbf{R}^3$ be a set of points in 3D and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.

We consider a convex polytope $P$ good / interior if:

$P$ is wholly contained within the interior of the convex hull of $S$:
$P \subsetneq \text{convexhull}(S)$.
$O$ is contained within the interior of $P$, namely: $O \in P$.
none of the points in $S$ are in $P$ namely $S \cap P = \emptyset$.

Out of all good convex polytopes, we want to find either the maximum (supremum) of their volumes, i.e. $\sup  \text{Vol}(P)$ where $P$ ranges over good polytopes.

Here is a 2D modest illustration (the green polytope might not be really the optimal):

The black dots are the set $S$, the origin $O$ is in the middle. The red lines go through the points in $S$ which define the boundary of $S$ (not a good polytope) and the green lines go through a good polytope.

Is there an efficient algorithm to compute this best convex and non-convex polytopes for a given set $S$ of points and origin $O$?

I would like to formulate this problem as an optimization problem or to come up with some algorithm using triangulation, $\alpha$-shapes or $\beta$-skeleton geometric transformation + convex hull, linear programming, maybe working in the dual space? etc.

One idea which I have is "pumping down" the convex hull of Delaunay Triangulation:

  DT $\leftarrow$  delaunayTriangulation($S \cup O$)

  CH $\leftarrow$  convexHull(DT)

  while  Not empty(DT) and $O \notin CH$:

  $\quad$ i.  previousDT $\leftarrow$ DT

  $\quad$ ii. update DT $\leftarrow$ DT $\setminus$ CH

  return previousDT

EDIT: I think what I am looking for in a one-liner of math symbols is:

$$\text{argmax}_{P} \text\{\text{Vol}(P) \,  | \, O \in P \setminus \partial P \, ; \,
 S\cap P = \emptyset  \, ; \, P \subsetneq \text{convexhull}(S) \} $$

Where $\partial P$ is the boundary of a polytope $P$.


texts:
Does exist an algorithm to find all equivalence classes of given regular expression without kleene star?

If yes then what is it?

Note that alphabet of the given regular expression is binary, i.e. it contains only 2 symbols exactly.

This is important, because I can easily construct NFA from the given regular expression and then construct the DFA from that NFA, but the result DFA is not minimal and the result DFA's number of states is exponential.

Of course I can run Hopcroft's algorithm to minimize the DFA, but if DFA's number of states is Θ(2n) then Hopcroft's algorithm runs in Θ(2nlog(2n)) = Θ(2nn) = Θ(n2n) and this might take too much time to get the minimal DFA for the given regular expression.

Also my computer has only 4GB of RAM.

If the given regular expression is long and the result NFA is big, then in the middle time conversion from NFA to DFA, there might be out of memory exception thrown and my application won't make it to call Hopcroft's algorithm at all.

For the given regular expression, running the algorithm to find all it's equivalence classes is considered to be much better than constructing NFA from the regular expression, constructing DFA from the NFA and run Hopcroft's algorithm to minimize it, but if and only if the algorithm to find all the equivalence classes won't use too much resources and won't take too much time to finish, then I can use the equivalence classes to efficiently construct the minimal DFA quickly for the given regular expression.

I tried to google the answer for this question, but I didn't find it yet.

Thinking about this algorithm myself is very difficult and hard.

I am very curious to find out what is this algorithm already.


texts:
let say I have a sequence of values ...
The values X and Y can be either number or data structures or states ... and so on ...
Example:
Value X can be followed by any of "n" other values  Y1,Y2,Y3, .... Yn
When I arrive at X I predict one of the Y values. If I predict correctly I should get a reward, penalty otherwise.
In addition every visit to a value I increment a counter I keep for every value.
/Visits can be viewed as Probability ... taking into account all Y's/
So I have two pieces of information Probability and Predictability.
What I want is to create a score that combines this information AND also an update formula for this score.
I will use this score to "correctly" predict what is the most probable and correct value Y after X.
It is repeatable process, so the scores will change over time.
I'm looking for the most plausible and common sense interpretation i.e. the prediction should be based on how often value Yx followed X, but also how correctly it was predicted, unless you can persuade me otherwise.
My thinking is that this will better capture the fluid nature of change in what follows X over time.
/I can also for-see using discount factor somehow/
The best idea I had so far is that Predictability is an S-curve function [0 .. 1 ] and the score is :
 Score = Probability * Predictability

I would also prefer to hold/store single value as a Score, rather than two values which I combine.

cont >>
Now that I though more about it, here is how I imagine it.. Probability describe occurrence, I need something to describe more like a pattern ... lets take the following sequences
  1,1,2,1, ... next value is 1 or 2 ..50%/50%, because 1:1 and 1:2 occur once
  1,1,1,2,1, ... next value is 1, because 1:1 is 66%, 1:2 is 33%

now if i have :
 1,1,2,2,1,1,2,1,2,1,1,..

still 50/50 , but the more prevalent pattern is 1,2 it occurred twice more recently, also 2 follow 1,1
The thing is probability is only part of the picture ... it has to be something that capture patterns of occurrence.
What I suspect I need is some sort of RL Q-value calculation, but there is no goal and reward (or may be the good/bad prediction is reward/penalty) and it is for sequence of states, rather then sequence of state-action..
i.e. i'm just passive observer..
I think what I'm looking is Expected value, rather than Probable value ...


texts:
Suppose we have a statement: "Tom has a car" and we have an auxiliary clause that is
has(x, y): x has y then to write the statement in logic I am guessing the following ones:
$\exists$y has(Tom,y)
or
has(Tom,car)
The reason I am not sure which to select is I don't know whether or not "car" is a specific constant similar to Tom?


texts: How to estimate the computational cost in a neural network?

texts:
Given a neural network(assuming no regularisation/dropout), I want to determine the computational cost of doing a forward and a backward pass of a datapoint. I want the measure to be of independent of the programming language/operating system involved. I can think of it as a graph model, with some activations applied on nodes, then I think it can be estimated by hand.
Also is there any online tool/package which would do the estimate if I input the neural network ?
I am new to computer science, so probably it is a very naive question to most of the users, I am offering my apologies it is so.


texts:
Consider the F-measure $F_{\beta}$. I know that with $\beta < 1$ precision is given more importance, ending with $F_{0} = precision$. With $\beta > 1$ means recall gets the upper hand, with the other extreme at $F_{inf} = recall$.

\begin{equation}
F_{\beta}  = (1+ \beta^2) \cdot \frac{Precision \cdot Recall}{(\beta^2 \cdot Precision) + Recall}
\end{equation}

I understand why for $\beta < 1$ precision is given more importance, but I don't understand for $\beta > 1$


texts: Convex Hull for known output size in O(n)

texts: Given a set $S$ of $n$ planar points, we know that the $|CH(S)| = 17$. How can I create an algorithm that computes $CH(S)$ in $O(n)$ time? Why is it really $O(n)$?


texts: Why does linear search have $\frac{n}{2}$ comparisons on average?

texts:
I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $\frac{n}{2}$ comparisons.

I tried working this out on my own.

First I considered the number of cases. There are $n$ cases corresponding to when the target value is the $1$st, $2$nd, ..., $n$th entry of the list. There is also the case where the entry is not in the list at all, so we have $n + 1$ cases.

Next I consider the individual number of comparisons needed per case. For the cases where the target value is in the list, we need $1, 2, \dots, n$ comparisons respectively. For the case where the target value is not in the list, we need $n$ comparisons (after which the search terminates and concludes with a return value of NIL).

Finally, I sum up the individual number of comparisons to get the total number of comparisons, and divide by the number of cases to get average number of comparisons. I get

$$\frac{1 + 2 + \dots + n + n}{n + 1} = \frac{n^2 + 3n}{2n + 2}$$

which is different from $\frac{n}{2}$.

May I where is the fallacy in my reasoning? Thank you!


texts:
I was asked which among the following is true:

  $\Sigma^*-\{\epsilon\} = \Sigma^+$
  $L^* - \{\epsilon \} = L^+$

As I can see, both $\Sigma^*$ & $L^*$ are sets. I thought both were true because of set difference, but the answer lists only the first option as correct and the second as false. How so?


texts:
I have an interval graph $G=(V,E)$ and a set of colors $C=\{c_1,c_2,...,c_m\}$, when a color $c_i$ is assigned to a vertex $v_j$, we have a score $u_{ij}\geq 0$. The objective is to find a coloring of $G$ with at most $m$ colors that maximizes the total score (sum of the scores of the vertices).

Do you know about any results in the literature that may help me to find the complexity of this problem?


texts: What is the relationship between Turing Machines with a finite tape and Finite State Automata?

texts: I seem to recall from an undergraduate class that for a Turing Machine with a finite tape there will always exist a corresponding Finite State Automata, but I've been unable to find this confirmed anywhere on the internet. Is this actually the case or am I misremembering?


texts: Time complexity of comparing $N$ strings

texts:
I would like to double check myself.
As I understand time complexity of comparing two strings in the worst case is $O(n)$, where $n$ is the length of the strings (let's say they are equal length).
In case I have $N$ strings and I would like to know whether they are all different.
Is there an algorithm for this that is faster than $O(n \cdot N^2)$?


texts: Amortised complexity of dynamic array using potential function

texts:
I'm trying to find out how potential function works. I'm trying to compute an amortised complexity of $n$ operations on dynamic array. To make it simple, assume, that we can't delete items and we can add item only to end of the array, so something like push. Let's assume that allocation is for free and if the array is full, we reallocate new array of double size and copy (cost 1 for each copy) all items into the new array.

It seems that $Ĉ$ - amortised price of one push is $2$. But how to create a potential function?

POTENTIAL_FUNCTION(Di) - $i$ is the number of items in the array

PUSH: $Ĉi$ = 1 + n + 1-n = 2
COPY: $Ĉi$ = i + ???

Please could you simple explain how to create potential function for this?


texts: Prove that the language is not regular through Myhill-Nerode Equivalence

texts:
The language is given by: $$L=\{a^nb^m|n<m\}$$
I have proven that the language is not regular using the pumping lemma but I need help with proving it through Myhill-Nerode Equivalence.
Any help would be appreciated.


texts: Write a pseudo code for a Graph algorithm

texts:
Given a DAG $G=(V, E)$ and a function $f(v)$ which maps every vertex to a unique number from 1 to $|V|$, I need to write a pseudo code for an algorithm that finds for every $v\in V$ the minimal value of $f(u)$, among all vertices $u$ that are reachable from $v$, and save it a an attribute of v. The time complexity of the algorithm needs to be $O(V+E)$ (assuming that time complexity of $f(v)$ is $\Theta (1)$).
I thought about using DFS (or a variation of it) and/or topological sort, but I don't know how to use it in order to solve this problem.
In addition, I need to think about an algorithm that gets an undirected graph and the function $f(v)$, and calculate the same thing for every vertex, and I don't know how to do it either.


texts:
So I'm interested in learning Machine Learning and in specific in the Healthcare domain. But I'm so overwhelmed at the different learning paths the internet holds. Can someone help me out with how I should be going about learning ML. It would be better if its including the Healthcare stuff.
Thank you
ps: if you've got resources, drop the link if it's not a problem :)


texts: What is the difference in 'logical array blocked' and array list B, and what do they represent?

texts: In Johnson's 1975 Paper 'Finding All the Elementary Circuits of a Directed Graph', his psuedocode refers to two separate data structures, logical array blocked and list array B. What is the difference in them and what do they represent? Moreover, what does 'Vk' mean?


texts: Karp hardness of searching for a matching erosion

texts:
First, read the previous question: Karp hardness of searching for a matching cut

As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the problem has been proven to be $\mathrm{NP}$-hard even when restricted to bipartite graph of bounded diameter.

Now, I wanna restrict the notion of a matching cut even further to a matching erosion. A matching erosion is a matching cut whose removal separates the original graph into two connected components $A$ and $B$, where all the vertices of $A$ belong to the matching itself. In other words, a matching erosion is just a matching cut that peels off $A$ from $G$ like cutting a thin slice of meat off a big meat block in a cafe bar.

All the literature constructions seem not to be able to yield such a nice, thin matching erosion cut.

Our problem is defined as: Given an undirected graph, determining if there exists a matching erosion.

The question is what is the complexity of our problem?


texts: Recalculating dominance after changing the entry node

texts:
I'm working with a control-flow graph, which is simply a directed (usually cyclic) graph with an entry (initial) node, and I have calculated all the dominators on the graph. It's noteworth that every node has either 1 or 2 transitions.

I need now to change the entry node of the graph to a node to which the entry node has a transition to. Since I do use dominator information for the internal representation of the graphs (similar to nested scopes in programming languages), I'm basically rewriting the graph after a single transition from the entry node.

For example, I have Graph 1 and I want to rewrite it to Graph 2:

Here I'm changing the entry node from a to b (and this is the only possible transformation, since a only had a transition to b). On Graph 2 I could possibly do the same (but then I'd have two options, moving the entry node to c or d).

Since I need the dominance information, I'd have to recalculate it after every change. My question is: is there any property for directed graphs that would allow me to do this in an optimal way, instead of recalculating all dominators from scratch?

(Also, since I do use dominance information for the internal representation... could there be a purely syntactical transformation to find dominance information?)


texts:
Consider such question:

(Prove or disprove) There exists a language in $TIME(2^{n^2})$ that is not in $NTIME(n)$.

I guess that answer is yes because $TIME(2^{n^2})$ and $NTIME(n)$ are totally different classes ($TIME(2^{n})$ and $NTIME(n)$ are the same classes, i guess). How to prove it strictly? (Or my guess is incorrect?)


texts: All superlinear runtime algorithms are asymptotically equivalent to convex function?

texts:
Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$?

All the examples that I could think of satisfy the above mentioned requirement. For example, all polynomials are convex on $\mathbb N_+$. Additionally, $n\log(n)$ is convex from $n=2$ and on, so it's asymptotically equivalent to convex function.


texts: Can I assume that a percentage of the time can be parallelized?

texts: I study computer science and hardware. Some problem are about parallel computing and applied Amdahl's law. For instance, some calculation is that the sequential part of a program takes x seconds and the parallel part takes y-x seconds. Can I then safely assume that it is the same percentage of the time that is parallel for different number of CPU:s or will that vary with different number of CPU:s?


texts: Logarithm and square root in prime fields

texts:
I got an interesting question.
Introduction:
Let $p$ be a prime number and $a,b\in \mathbb{Z}$ with $\gcd(a,p)=1$ and $\exists r\in \mathbb{Z}:r^2\equiv a\mod p$ as well as $\exists l\in \mathbb{Z}:b^l\equiv a\mod p$.
I want to show that there exists a $z\in \mathbb{Z}$ for which $b^z\equiv a\mod p$ and $z^2\equiv a\mod p$.
My thoughts:
Choose $r$ such that $r^2\equiv a \mod p$ and $l$ such that $b^l\equiv a\mod p$. By Fermat’s theorem, I know that $a^{p-1}=1\mod p$. Therefore, I know that $(l+kp)^2\equiv a\mod p$ and $b^{l+k'(p-1)}\equiv a\mod p$ for $k,k'\in \mathbb{Z}$. Now I want to show that $r+kp=l+k'(p-1)$ for some $k,k'$, but that is the point I am struggling with.
My question:
How can I show the existence of $k,k'\in\mathbb Z$ such that $r+kp=l+k'(p-1)$, and if I can’t, how can I show the existence of $z$?


texts: How to understand the reduction from 3-Coloring problem to general $k$-Coloring problem?

texts:
3-Coloring problem can be proved NP-Complete making use of the reduction from 3SAT Graph Coloring (from 3SAT). As a consequence, 4-Coloring problem is NP-Complete using the reduction from 3-Coloring:

  Reduction from 3-Coloring instance: adding an extra vertex to the graph of 3-Coloring problem, and making it adjacent to all the original vertices.

Following the same reasoning, 5-Coloring, 6-Coloring, and even general $k$-Coloring problem can be proved NP-Complete easily. However, my problem comes out with the underlying mathematical induction:

  My Problem: What if the induction goes on to $n-1$-Coloring and $n$-Coloring problem, where $n$ is the number of vertices in the graph? I certainly know that $n$-Coloring problem can be solved trivially. So, is there something wrong with the reasoning? How to understand the reduction from 3-Coloring problem to the general $k$-Coloring one?


texts: What is difference between a formal system and a model of computation

texts: I don't exactly know the difference--partly because I cannot find a mathematical definition for a model of computation (also why is this)?


texts:
I am reading Programming Language Pragmatics by Michael Scott. He says that on a first pass, a compiler will break a program into a series of tokens. He says that it will check for malformed tokens, like 123abc or $@foo (in C).

What is a malformed token? A variable that does not meet the rules of variable-naming? An operator that does not exist (ex. "<-")?

Is this analogous to a misspelled word?


texts: Example of P-Complete Problems reducible to Quadratic Halting Problem

texts:
According to wikipedia (https://en.wikipedia.org/wiki/P-complete):

The most basic P-complete problem is this: given a Turing machine, an input for that machine, and a number T (written in unary), does that machine halt on that input within the first T steps? It is clear that this problem is P-complete. if T is written as a unary number (a string of n ones, where n = T), then it only takes time n. By writing T in unary rather than binary, we have reduced the obvious sequential algorithm from exponential time to linear time.

Are there any natural $P-Complete$ problems such that:

They are similar to the Halting Problem above on the Deterministic Turing Machine with a few differences as below.
Instead of Linear, their run-time (represented in unary) is quadratic to the input to the problem.
Moreover, this run-time is known to be optimum (i.e.its provable that no polynomial time algorithm can exist that runs in sub-quadratic time).


texts:
I have been told than $n^{1000001} = O(1.000001^n)$. If that's the case, there must be some value $n$ at which $1.000001^n$ exceeds $n^{1000001}$.

However, when I consult Wolfram Alpha, I get a negative value for when that occurs.
http://www.wolframalpha.com/input/?i=1.000001%5Ex+%3D+x%5E1000001

Why is that? Shouldn't this value be really big instead of negative?


texts: Possible to get the Sum x with maximal two summands?

texts:
Suppose we have $n$ different summands. Is it possible to get the sum x with a maximum of two of the $n$ summands (Below the m summands there can be several times the same one). For example you have the summands (2,4,6,7). So its possible to get the sum $2+4 =6$,$6=6$ but its impossible to get the sum $3$ or $1$ ect.

My idea of an algorithm would have the runtime $\mathcal{O}(n\log(n))$. Now I'm not sure if this is already aymptotically optimal ?


texts: Help with problem 4.1-1 from CLRS 2nd edition

texts:
The exercise says "Show that the solution of $T(n) = T(\lceil{n/2}\rceil) + 1$ is $O(\lg(n))$." I came up with a solution for this exercise using the substitution method but I don't know if it is correct. My solution goes like this: I claim $T(n) \leq c\lg{n}$ and assume it holds for $\lceil{n/2}\rceil$, then
$$
\begin{aligned}
T(n) &\le c\lg(\lceil{n/2}\rceil) + 1 && \text{Inductive Hypothesis}\\
&= c\lg(n/2) + 1 && \text{Omitting ceiling}\\
&= c\lg{n} - c + 1 && \text{Algebra}\\
&\le c\lg{n} && \text{for $c\ge1$}
\end{aligned}
$$
I omit the ceiling function according to the text.
I, however, found another solution on the internet that is slightly more complicated which makes me think my solution is probably wrong. It states that $T(n) \leq c\lg(n - b)$ and assumes it holds for $\lceil{n/2}\rceil$, consequently:
$$
\begin{aligned}
T(n) &\le c\lg({\lceil{n/2-b}\rceil}) + 1 \\
&\lt c\lg(n/2-b + 1) + 1\\
&= c\lg\big(\frac{n-2b+2}{2}\big) + 1\\
&= c\lg(n-2b+2) - c\lg2 + 1\\
&\le c\lg(n - b)
\end{aligned}
$$
Where the last inequality requires that $b \ge 2$ and $c \ge 1$.
My question is if my solution is correct, then why subtract $b$ from $n$ in the second solution? If my solution is not correct, is subtracting $b$ from $n$ absolutely necessary and why is my solution not correct?


texts: Expression Problem – looking for a similar standard problem

texts:
The Expression Problem, populated by Philip Wadler,  is a often used to standard problem to evaluate programming languages.

I think it is a very clear and popular example and I wonder if there are any similar standard problems that are possibly also as widely used and as clear.

So, are there any similar standard problems?

(In the case of Feature Oriented Programming (link link) I found some standard problems, like:
- implementation of a stack with different features
- implementation of linked lists
- implementation of a calculator
- the graph product line
- stock broker and bank account examples
- hierarchical display
)


texts:
If $L_1,\,L_1L_2$ are regular languages with $L_1\neq \emptyset,\,\lambda\notin L_1,\,\lambda\notin L_2,$ is $L_2$ regular?

I think I found a correct proof for this question but my professor says it cannot work. Her issue is with the right quotient step but I cannot see why it is incorrect. Can anyone shed some light on this?

$$
L_1L_2 = \{ w_1w_2 : w_1 \in L_1,\, w_2 \in L_2 \} \qquad \vert w_1 \vert \ge 1,\, \vert w_2 \vert \ge1
$$

$$
\left( L_1L_2 \right)^R = \{ w_2^Rw_1^R : w_1 \in L_1,\, w_2 \in L_2 \}
$$

$$
\left( L_1L_2 \right)^R / L_1^R = \{ w_2^R : w_2 \in L_2 \} \qquad (w_1^R \in L_1^R)(\forall w_2^Rw_1^R) \implies w_2^R \in \left( L_1L_2 \right)^R / L_1^R
$$

$$
\left( \left( L_1L_2 \right)^R / L_1^R \right)^R = \{ w_2 : w_2 \in L_2 \} = L_2
$$

$$
L_2 \, \text{is regular by closure of reversal and right quotient on regular languages.}
$$


texts: Complexity of Solving a System of Polynomial Equations

texts: It can be easily seen that solving systems of polynomial (i.e. not necessarily linear) equations is NP-Hard via reduction from SAT. Furthermore, because the existential theory of the reals is decidable in PSPACE, solving systems of polynomial equations is as well. What else is known about the complexity of this problem? For example, I have been unable to determine if it is known to be $\exists R$-Complete, or PSPACE-Complete.


texts:
I have a LR analyser and I can't find out how to know whether the grammar is or is not LALR(1).

I think that I have to merge states with the same rules. So I have to merge states: $2 - 12, 3 - 13, 4 - 15, 7 - 9 -17, 8 - 16, 10 - 18 $

I think that LALR conflict is for example if I merge $ 2 - 12$ because in the rules $A -> .bS$ there are the same contexts $b$. Is it true? What should I do to know whether is there a LALR conflict? And LR conflicts?


texts: Is clrs really needed to be a computer scientist

texts:
I want to dive in alghorithms and data structures and maybe AI this year. When I searched on internet everybody was recommending to read clrs. But I found it very complicated, because of the amount and the level of math in it. Is reading clrs really important to be a true computer scientist. If yes, how it can be easier to accomplish.
Note: I started reading Data Structures and Algorithm Analysis in C++, but I'm planning to read other books also.


texts: Are all functions with constant space complexity in $REG$?

texts: The Wikipedia article about regular languages mentions that $DSPACE(O(1))$ is equal to $REG$. Can I conclude from this that every function in $R$ with constant space complexity is in $REG$?


texts: Generate a graph to exact size using Kronecker product graph model

texts:
In network science, we can take sample a complex system and derive from this sampling a representative network (or graph) that describes the system to some extent. A model of a network, is a powerful mathematical abstraction of the observed system. The model can be used to generate networks similar to the observed network, i.e., synthetic models will have similar network characteristics.

Learning a model of a network is done with exponential random graph model and Kronecker product graph model. The latter is described in a series of papers like this one. KronFit is a software tool that processes the graph/network of reference and learns/derives a set of parameter for the model to grow/generate synthetic graphs. In the case of Kronecker product graphs, the software is used to find the parameters of the model, aka a seed 2x2 matrix.

However, you can only build graphs where the size of the synthetic graphs is forced to powers of 2. Is there an extension to this model that grows graphs to exact size without padding the input? For example, if my original graph has 10000 nodes, how do I generate a network using the Kronecker product to exactly 10000 nodes?  In the classical way, I would have to pad my original graph with disconnected nodes to a total size of 2^14 nodes that's over 50% more nodes.


texts: Curry-howard isomorphism in object oriented programming languages

texts:
I want to get a better intuition for the curry howard isomorphism, and my intuition is mainly based on object oriented programming languages like JavaScript.

So as an example, I am going to formalize the notion of "topological space" in a hypothetical object oriented programming language with dependent type theory and see if it makes sense:

public class TopologicalSpace
{
    BaseSet:Type
    Topology: (BaseSet -> Boolean) -> Boolean
    public TopologicalSpace(X:Type,T:(X -> 2) -> 2,
         p_axiom1:Axiom,p_axiom2:Axiom2,p_axiom3:Axiom3 )\\constructor
    {
        BaseSet = X;
        Topology = T;
        proof_axiom1 = p_axiom1;
        proof_axiom2 = p_axiom2;
        proof_axiom3 = p_axiom3;
    }

    Axiom1: Topology (function (x:BaseSet) return True) = True
        AND Topology (function (x:BaseSet) return False) = True \\empty set & domain
              \\ are in topology
    public readonly proof_axiom1:Axiom1

    Axiom2: \\\etcetcetc
}

Does this approach make sense? Is there a kind of object oriented type theory + curry howard isomorphism like this?


texts:
The question statement is as follows:

Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other. All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".

The problem can be found here.
The algorithm is a greedy one, which basically works as follows:
Maintain a maximum heap of available characters, sorted by the the number of occurrences.
For each position i,
    add to the heap the chosen character at i - k
    pop out the character c with the highest number of occurrences
    set the i-th position to hold the character c
    decrease its number of occurrences by 1

This algorithm intuitively feels correct, because the characters with more occurrences are more "urgent", but I would like to prove its correctness, or at least have a proof sketch.
Currently I think this may be proved by induction on the i-th positions. Here is what I have right now:

Base case: $i=0$
In this case, all the characters are available to choose. Let's say $a$ has the maximum count but we choose $b$ instead, $count(a) > count(b)$. Then we can construct a counter example, $aab$ with $k=2$, such that if we choose b instead of a for position $0$, we fail to make the string 2 distance apart.

Induction Rule:
Suppose at position $i$, choosing the available character $a$ which has the maximum count can lead to the optimal solution. Need to prove that for $i+1$, we still need to choose the character with the maximum count.

I don't know how to finish the induction part, i.e. how to prove $i+1$ from $i$. Also, I feel the proof for the base case using counter examples is not convincing enough. Can anyone give some hints on how to prove this?


texts: NL and NP compute different binary relations, so what?

texts:
Let the binary relation computed by a nondeterministic transducer be the relation between input strings and the possible output strings the transducer can produce (and accept) for the given input string.

It is easy to see that the nondeterministic transducers using polynomial time can compute different binary relations than the nondeterministic transducers using logarithmic space. (Trivial examples like $\{(1^n,ww^R):n\in\mathbb N, |w|\leq n\}$ suffice to see this. Edit: This assumes that the output is generated symbol by symbol, see András Salamon's comment. If random access to write only output memory is assumed, then $\{(1^n,w):n\in\mathbb N, w\in D_2, |w|\leq 2n\}$ where $D_2$ is the Dyck language of all strings of matching brackets over two pairs of brackets, say $\{ [,], (,) \}$ is an example. However, proving that this example really works is non-trivial.)

Can anything of interest be concluded from this basic observation? For example, concluding that there must exist an oracle $A$ such that $NL^A \neq NP^A$ would be of interest, but things don't work that way. Or concluding that directly programming in NP is easier that directly programming in NL, because more powerful subroutines are available. That sort of sounds true, even so subroutines generally can have more that a single input string and produce more than a single output string. (So one could try to prove that if all those possible subroutines would be equal, then there could not exist an oracle for which the relativized decision problems are different. But even this will probably fail.)

Edit:

WLOG, we can restrict us to NL tranducers that never repeat a configuration. These are exactly those NL transducers that only use polynomial time.
The random access to write only output memory is well outside NL. But it is still inside NP, so the composition of those NL transducers could be done inside NP. This should be good enough to conclude things about powerful subroutines or oracles, if this is possible at all. (Even the symbol by symbol output tape was outside of NL, it was just less obvious.)
The oracles $A$ such that $NL^A \neq NP^A$ are white box oracles, where the problem $A$ is (expected to be) outside of the considered complexity classes. The conclusions about subroutines from the basic observation might tell us something about black box oracles from the same or weaker complexity classes. Or they might at least provide a motivation to prove black box separations between complexity classes relative to oracles from weaker complexity classes.


texts:
Im studying for the computer science subject GRE test, as an exercise i need to implement the followin algorithm in java, any idea on how to aproach it?.

Given a set $X$ and $z$ not in $X$, indicate between which would be the immediate positions $z$ in $X$


texts: Monotone Frameworks: Transfer functions for flow edges instead of labels

texts:
So, in generic program analysis, we have a lattice $L$ with a join operation $\sqcup$, program with statements labelled, and for each label $b$, a transfer function $F_b : L \rightarrow L$.

The goal is to find, for each label $b$, a fix-point $x$ such that $F_b(x)=x$. This is a common approach used in dataflow analysis,

In "Principles of Program Analysis" by Nielson, Nielson and Hankin, they reference that "Some formulation of monotone frameworks associate transfer functions with edges (or flows) rather than nodes (or labels)." However, in the textbook, they simply reference an exercise where the reader is asked to implement such a framework.

I'm wondering if anyone has a reference to either a book or paper where such a formulation is given. In particular, I'm wondering how a typical worklist algorithm for finding a fixed-point would be formulated.


texts: Calculate the number of trailing zeros in equation f(n) = f(n-1) * f(n-2) where f(0) and f(1) are any given arbitary numbers

texts:
This question is doable if you can calculate the number by multiplying f(n-1) and f(n-2).

Is it possible to do this question if we entirely want to skip multiplying these 2 numbers and still be able to calculate say the number of trailing zeros in f(20).

Why do I want to skip multiplying these two numbers?
Because as this function grows exponentially, so does the value. We might get an integer overflow on some languages. Hence.
Also, our aim is to calculate the number of trailing zeros and not calculate the number itself.

What I tried. To try and calculate trailing zeros and f(n-1) and f(n-2), So that I deduce the number of trailing zeros in f(n) and go on from there.

But to calculate trailing zeros in f(n-1), I need to know what f(n-1) is? Which is where my whole approach fails.


texts: optimization problem: Find Phase of input for minimized max output

texts:
Let the $\textbf{bold characters}$ represent the vectors/matrices.All the vectors/matrices/scalars only refer to real numbers.

In a continuous LTI system.

$\frac{d\mathbf{T}(t)}{dt}=\mathbf{A}\mathbf{T}(t)+\mathbf{B}$

in which $\mathbf{T}=[T_i]_{N\times 1}$, $\mathbf{B}=[B_i]_{N\times 1}$ and $\mathbf{A}=[A_{i,j}]_{N\times N}$. $\mathbf{A}$ is a given constant matrix. $\mathbf{T}(t)$ are real valued function of $t$. All $\mathbf{T}(t)$, $\mathbf{B}$ and $\mathbf{A}$ only contain real numbers.$t>0$.

$B_i$ is different square-pulse input, that $B_i(x_i)=u(x_i)-u(x_i-K_i)$, where $K_i$ is the given pulse width and $K_i>0$.
$u(t)$ is a continuous unit-step function as $u(t)=1$ when $t\geq 0$; $u(t)=0$, otherwise.

How can we find a phase $\mathbf{X}=[x_i]_{N\times 1}$ such that the output $\max(\mathbf{T}(t))$ can be minimized?

So far, my idea is to use Sinusoidal to approximate the square inputs signal, then calculate their phase. Then, use superposition method. However, it still need to use numerical method to check the $t_i$ for different $B_i$. Is there any simpler way? Any paper talk about this? Thank you.


texts:
Referring to this Question, where an answer is stating that all Type 3 languages are LL(1), I'd like to know if all Type 3 grammars are possibly LL(1).

If not, why is it so? Are there maybe ambiguous grammars in the set of the Type 3 grammars?


texts: Objective function and constraint satisfaction over a set of multi-attributes elements

texts:
I'm looking for an approach to solve a problem consisting of maximizing an objective function over a set of discrete elements, while respecting a set of constraints.

To illustrate my point, I'll try to come up with an example.

A bag contains several items with the following attributes:

Value (Int)
Size (Int)
Material (Enum)
Origin (Enum)

As an example, we can imagine a bag consisting of the following items:

value     size     material    origin
    4        1         wood        FR
    4        2        stone        US
    3        3         gold        JP
    2        2         wood        FR
  ...      ...          ...       ...

The goal is to maximize the total Value, while at the same time respecting a set of constraints. An example set of constraints would be:

total size < 80
between 20 and 35 items in total
at least five elements with origin FR
at least two elements with material wood OR at least two elements with material stone
strictly less elements with material gold than elements of material stone
no more than 5 elements with size > 10

Below are some approaches I've thought about, and the reason why I can't use them directly:

(Integer) Linear Programming: here we're not dealing with the full space of Integers, but instead only with the values found in the bag (and tied to the other properties for each item)
Stochastic Constraint Satisfaction: it would be easy to stochastically come up with a selection of Items which respects the constraints, but here we're not looking for any solution, instead we're looking for the solution which yields the highest total Value, which would need us to exhaustively list all possible satisfying solutions before picking the one with highest value (which may be a very inefficient approach)
SMT solver: I think it could be the way to go, but so far I can't see how to model the link between the constraints, the objective function and the bag of elements

Can you think of an approach to solve this kind of problems?


texts: Is it even theoretically possible to invent coumputers that are more intelligent than humans?

texts:
I've read an article recently where Stephen Hawking claims that in hundred years there will be computers, which are more intelligent than humans.

Link: http://www.computerworld.com/article/2922442/robotics/stephen-hawking-fears-robots-could-take-over-in-100-years.html

Assuming that would be the case at someday. Wouldn't that mean that those computers could then develop other computers that are again smarter then the original ones. And so on and so on.

That seems somehow irrational to me.

Please share your thoughts with me on this topic.


texts: If a one-way functions (OWF) exist, then there exits a OWF that is computable in quadratic running time by a padding argument

texts:
I believe this question should be extremely easy but I am having a (embarrassing) hard time figuring out why its true if there exist OWF (computable in polynomial time) then there exits a OWF that is computed in $O(n^2)$.

This is what I have/tried.

Let $ \ f(x)$ be a OWF that can be computed in $k^c$. Then we can construct a OWF:

$$
f'(x'||\ x'') = f(x') || \ x''
$$
where:
$$
|x'| = k \\
|x''| = k^c
$$

Notice the size of the input for $f'$ is $n = k^c + k$.

Its intuitively "obvious" f' is a OWF since f is OWF (or you can go ahead and prove it by contradiction if you want to be pedantic). But how come it takes $O(n^2)$ to compute the OWF f'? Does this depend on the Turing Machine model being used to compute f'?

It seems to me you can just parse the input $x'||x''$ (separate it so that you can feed the appropriate thing to the original f) in O(n) and then compute $f(x')$ in $k^c = O(n)$
and then concatenate it to $x''$ and print f(x')|x'' (printing takes at most $O(n)$). It seems to me it takes $O(n)$ and that the bound $O(n^2)$ is unnecessarily un-tight (I know $cn + d = O(n) = O(n^2)$). Or maybe the parsing algorithm is "harder" than I expect it... even if you just append the lengths at the beginning just for parsing purposes , isn't the time to compute $f'$ just $O(n)$?

Does someone understands why my O(n) argument is wrong?


texts: What's the meaning of "Front" in "Pareto-Optimal Front"?

texts: I'm reading a paper about Multi-Objective Optimization Problem. I understand Optimal in Pareto sense, and I even know what is Pareto-Optimal Front somehow. But I can't find a relationship between the word Front and the concept. So, what's the meaning of this word in this context?


texts: Linear Search Proof of Correctness (trouble with case where $ A[j] = v $ )

texts:
There's lots of answers on the proof but I didn't find anything that regarded my difficulty directly.
Question ( From " Introduction to Algorithms ( Cormen ) " ):

Answer ( Found on the net ):

I don't understand the case where $ A[j] = v $ when we prove the maintenance step for before the j+1-th iteration ( after assuming $ A[j] \neq v $ for before j-th iteration ). why does the loop invariant hold in such case?
I don't exactly see how it makes sense since the program terminates in such case and so we're left out without having proved that $ A[j] \neq v $ for before the j+1-th iteration, but on the contrary we've shown that $ A[j] = v $ for before the j+1-th iteration, hence contradicting the assumption that $ A[j] \neq v $ for before j-th iteration.


texts: $\text{"The error entries in the goto table are never consulted"}$ - intuitive explanation of the above claim with respect to $LR$ parsing tables

texts:
I was going through the text : Compilers: Principles, Techniques and Tools by Ullman et. al where I came across a claim:

$\text{"The error entries in the goto table are never consulted"}$

I feel that whenever there is a reduce move, the current state pointer moves some states back. Suppose that $A\rightarrow \alpha$ is the production used and for the viable prefix $\gamma\alpha$ the current state pointer moves back those many states (so as to pop the $\alpha$ from the stack) and goes to state say $I_n$ and there is a move from $I_n$ on $A$ to some state $I_{n'}$.


texts:
Say i have code snippet like -->

m -= n;

is minus and assignment considered as a single token or they will be considered as different token?

So the total token count will be 4 or 5?


texts: Difference between data flow and control flow

texts:
I am trying to read a paper. I can’t understand the difference between data flow and control. Maybe control flow means OS's or hardware's steps taken for execution of statements whereas data flow stands for passage of data as a result of execution of statements. Link of paper is

https://www.usenix.org/system/files/osdi18-cui.pdf, named
REPT: Reverse Debugging of Failures in Deployed Software

I have problem with following:

  REPT reconstructs the execution history with high fidelity by
  combining online lightweight hardware tracing of a program’s control
  flow with offline binary analysis that recovers its data flow.

Kindly explain me the difference between dataflow and control flow.

Zulfi.


texts:
Given a 3SAT instance (a Boolean expression in three conjunctural normal form), we draw a directed graph, where for each Boolean variable $x_{i}$ we have the nodes $x_{i}$ and $!x_{i}$; for each clause, for example $\left(x_{a} \vee x_{b} \vee x_{c}\right)$, we draw the following arrows $!x_{a}x_{b}$, $!x_{a}x_{c}$, $!x_{b}x_{a}$, $!x_{b}x_{c}$, $!x_{c}x_{a}$, $!x_{c}x_{b}$.
Is it possible understand from the graph if there is a variable $x_{i}$ such that $x_{i}\Leftrightarrow !x_{i}$ ($!x_{i}$ is $not\left(x_{i}\right)$)?


texts: Minimum number of adjacent swaps needed to sort a circle of elements

texts:
I have been thinking about some problems in combinatorics and I came across a problem I'm having trouble with.

Suppose you have a list $L$ of length $n$ (wlog the elements of the list are 1,2,3,...,n) and you want to sort it circularly (meaning [3,1,2] is sorted) with swaps of adjacent elements, but you are also allowed to consider the first and last elements as adjacent. What is the minimal number of swaps required?

The way to think about this, I think, is to consider the elements of $L$ arranged around a circle, in order. There are $n$ ways to do this, each with a different element at the top. What I want to do is just arrange $L$ in each way, sort it while counting the swaps, then take the minimum.

The problem I have is that elements of the list don't stay fixed: for example I can move 1 into the correct place, but when I move 2 into the correct place, I might move it past 1, which would mess up the position of 1. I am not really sure this is a good idea, since I'm not sure where the "correct place" of an element is, since any place around the circle could be correct.

Another idea I have is to fix 1 and sort the circle around 1 (i.e. I move 2 into place relative to 1, then 3 and so on). Then do it for 2 and so on, then take the minimum of the number of swaps I did while fixing each element. But is it true that this gives the optimal sequence of swaps?

This doesn't seem like an efficient solution either, since I am actually doing swaps on a list rather than some clever calculation. I know that the number of swaps in e.g. bubble sort is the number of inversions in the list. Is there a similar calculation I can do for circular lists?


texts:
I believe the following question in summary is: How to approximate Euclidean distance in a digital plane?

  When a pebble falls on a calm surface of water a circular wave propagates. I want to color the pixels with time to show this effect. So I discretize the time and in each time step, starting  from the center, I color one pixel away in all directions. But this gives a square wave. I guess what is wrong is that I have approximated the Euclidean distance with the infinity norm.

How do I approximate Euclidean distance to get the a circular wave on the pixels? I don't want to measure the distance from each pixel to the center in each time slot. That will be very heavy. I am looking for a simple algorithm like coloring the next pixel adjacent to last colored pixel.


texts: Pass by Value or by Reference and Impure or pure functions

texts:
Beginner question: I am teaching myself the two passing techniques: Pass by Value and Pass by Reference.

Can Pass by Value change the states of an object? If yes, how? Which of the two techniques changes the states of an object?
Also, are Impure Functions based on Pass by Ref. and Pure Functions on Pass by Value?

I'd be glad if someone clears my concept.


texts: Any proof of correctness of the Toom-Cook algorithm?

texts:
I found the toom-cook algorithm here: http://www.cs.cmu.edu/~ab/Desktop/15-211%20Archive/res00037/Multiplication_1_print.pdf

and have been trying to chase down proof of it being correct, but can't find anything. Does anyone know how to go about proving the algorithm? I was thinking induction but I can't even figure out how to do it.

This is just for the three-way splitting, page 6. Any ideas?


texts: Why does a color video compress better than a black and white video?

texts:
It was asked in an exam why a color video compress better than a black and white (grayscale) video using MPEG but can't find anything explaining it.

In other words, we would apparently get a better compression ratio when compressing color videos than when compressing BW videos.


texts: Computational Complexity of Promise Monotone 1 in 3 SAT

texts:
Given a 3SAT problem where each clause is a Monotone Clause (i.e. each clause with all positive or negative literals).

Moreover, we are promised that each solution for the above SAT problem (if any exists at all) will be of the form 1 in 3 SAT.

Monotone 1 in 3 SAT is NP Complete, but with the additional promise above, does the problem still remain NP Complete (it obviously is NP) ?


texts: Designing bidirectional search algorithm

texts:
Write down the algorithm for bidirectional search, in pseudo-code. Assume that each search will be a breadth-first search, and that the forward and backward searches takes turns expanding a node at a time . Be careful to avoid checking each node in the forward search against each node in the backward direction.
Artificial Inteligence, A Modern Approach. Stuart Russel and Peter Norvig, ch 3, p89, ex 3.10

After googling a correction, I wasn't even able to find an "official" algorithm version. I'm not sure if my bidirectional search pseudo-code version respects the very last condition given by Russel. Could you help me improving my pseudo-code ?
For both start and goal nodes
boolean founded = false
While founded = false
    if pulse == distance_n
        if(!founded_n)
            founded_n=true
            pulse ++
        else
            founded = true
            break
        end if
    end if
end while

When one of the algorithm find a node the orhter algorithm has already visited we have found a solution.


texts:
Consider the case where you have two types of flow, let's say "red" flow and "blue" flow. You want to send $k_r$ red flow and $k_b$ blue flow through a DAG $G$ from a source $s$ to a sink $t$ in such a way that no edge carries both red and blue flow. Is there an efficient way to determine if an assignment of $k_r$ red and and $k_b$ blue flow exists? If so, can it be extended to multiple "colors"?

An extremely naive solution would be to take every subset of edges $E'$ and check whether or not you can send $k_r$ flow through $G[E']$ and $k_b$ flow through $G[E\setminus E']$.

I was looking at this question of assigning people to rooms with constraints and thought that if you could solve the above edge disjoint flow problem, you could solve the linked question as well (it wouldn’t be faster than the claimed $O(n^3)$ time algorithm, though).


texts:
The Problem

I have a set of sets of time intervals (hour, minute, day of the week). I want to select exactly one interval from each of set, and I want to minimize...

the number of pairwise intersections,
the total number of days,
the total time,
minus (the average start time), and
the average end time.

The number of intersections is always the most important, but the precedence of the other four is not known in advance. The number of sets is small (generally around 8), but the number of options can be pretty big (around 10), so trying all ~1E8 permutations is impossible.

What I've Tried

My current solution is to backtrack until I find a solution without intersections, giving up after a completely arbitrary number of iterations, and trying again with a higher number of allowed intersections. After repeating this process a few times, I select the  best one.

This is probably really naive, so I came here hoping for a better approximation.


texts: Introductory explanation of the Big-Oh properties

texts:
I've noticed that Big-Oh notation actually has some properties such as summation, product but i couldn't find an introductory explanation for their use or how they can help to solve asymptotic problems.

1) Is it possible to explain these properties in plain English?

2) Can these properties be applied to Big-Omega and Big-Theta notations?

Please leave any intuitive material that can help the understanding of these properties (and others).

Thanks.


texts: Probability of colisson for classes of hash functions

texts:
I am going through some old exams in one of my courses, and I don't have access to solutions. I've found a problem which I am not sure how to tackle. I am not looking for the answer but some help/guidance if possible.

Consider a class of hash functions , $\mathcal{H}$, over a finite universe ${U}$ into $\{0, ... , n-1\}$. Where $|U| > 1$ and $n > 1$.

Show that for any family of hash functions $\mathcal{H}$ the following holds:
$$
Pr[h(u_1) = h(u_2)] \geq \frac{1}{n} - \frac{1}{|U|}
$$
Here, the probability is over the choice of the hash function $h$ drawn uniformly at random from the family $\mathcal{H}$.


texts: (semaphore y=1; int x=5) vs (semaphore x=5)?

texts: Last time, I was asked to solve a concurrency problem involving 100 similar processes constrained to fit into 5 buffers. (I'm talking about the Dining Savages problem.) I thought that it was alright to use a semaphore with value 5 (Semaphore x=5) for constraining the 100 proceses. As it turned out, the solution given uses a semaphore with value 1 and then an int was used to check whether the number of entries in the buffer is less than 5. Are there general pointers to remember when to use int x=5 instead of semaphore x=5?


texts: The communication complexity of the distance between two strings

texts:
Assume that Alice and Bob are respectively given two strings $x \in \{0,1\}^n$ and $y \in \{0,1\}^n$ such that the hamming distance between $x$ and $y$ is either $> n/2+\sqrt{n}$ or $< n/2-\sqrt{n}$.

Alice picks a set $A \subseteq \{1,...,n\}$ of size $k$ uniformly at random, and sends to Bob the set $\{(i,x_i) \mid i \in A\}$. Bob compares $x_i$ with $y_i$ for every $i \in A$ and accepts iff the majority of these indices agree. What is (asymptotically) the minimal $k$ for which this protocol succeeds (i.e. Bob accepts iff the distance is $< n/2-\sqrt{n}$) with probability at least $2/3$?

I guess that $k$ should be $\Omega(n)$, and that in order to show this we should bound the tail of the distribution (e.g. by using the Central limit theorem or something similar), but I don't see how this can be done.


texts: Relating decidable, undecidable, recognizable, co-recognizable, unrecognizable, countable and uncountable languages

texts:
I went through a lot of texts and came up with following diagram to summarize the relation between decidable, undecidable, recognizable, co-recognizable, unrecognizable, countable and uncountable. Am I correct with it?

Note that this makes unrecognizable proper subset of undecidable. Also countable and uncountable makes up whole space, that is, there is no language which is neither countable nor un-countable.

In tabular format:

Edit 1

I dont know if we can classify every language as countable or uncountable and if there is no third possibility. I guess there should be another language class, possibly named enumerable, which will have languages having injective function from themselves to real numbers (sort of "well ordered"). Countable languages have injective function from themselves to natural numbers (sort of "strictly well ordered"). With this definition will Countable $\subset$ Enumerable ? Also we will then require un-enumerable class (instead of uncountable class), which will neither have injective function to natural numbers nor to real numbers (sort of "un ordered"). Something like this:

Am I sounding stupid here?

Edit 2

So if thoughts in edit 1 is correct, definitions of various terms will be:

Note:

O entry in the table means may or may not hold the property.
Counting procedure means given string present in language, it can eventually confirm that string was indeed part of language, but may not be able to confirm if the string does not belong to the language.
Membership procedure means given string, it can confirm whether the string belongs to language or not.

PS: I have not given second thought to first table after edits. It might not align with thoughts in edits.


texts: As much I know about a memory and storing data there would always be a managing type feature in every memory which manages all the data and its location. So, what is the file system of a RAM. I also like to know the format or type (mp3, pdf, png, txt, jpg or binary) of data stored in.


texts:
I have come up with a type of simulation "game" but I cannot find anything describing it online.

The simulation has a 2D "world" with a number of automatons on a discrete grid, similar to the game GNU Robots, although for an interesting game, their behavioral rules should be much more complex:

#.......
#...#...
...#....
....#..#
..#.....

Where each # is a robot.

What's this class of simulations called?


texts: On complete problems for $P/poly$ and $BPP$

texts:
Is there a complete problem for $P/poly$?

Decision version of permanent more or less acts as a complete problem for $PP$ while its weaker sibling has no known complete language. Why? I saw wiki reason but it is not clear to me. In https://en.wikipedia.org/wiki/PP_(complexity)#Complete_problems_and_other_properties it is stated 'Unlike BPP, PP is a syntactic, rather than semantic class. Any polynomial-time probabilistic machine recognizes some language in PP. In contrast, given a description of a polynomial-time probabilistic machine, it is undecidable in general to determine if it recognizes a language in BPP'.


texts: How does the structure of a Luk-Vuillemin multiplier differ from a Wallace or Dadda multiplier?

texts: I've read that Luk-Vuillemin multipliers are similar to Wallace multipliers but partition their inputs in a different way. How exactly does this partitioning work, how does it change the structure of the multiplier, and why does it give it a more regular structure which is preferred for fabrication?


texts: There is trivially $\emptyset\in\text{NP}$. From the definition of $\text{co-NP} = \{L : \overline{L} \in \text{NP}\}$ where $\overline{L} = \{0, 1\}^*-L$ follows $\{0, 1\}^*\in \text{co-NP}$. Is this true? If so, it is also true that $\{0,1\}^*\in \text{NP}$?


texts: What the type of an overloaded function should be?

texts:
Anecdotally, Virgill III language forbids overloading since overloading resolution is at odds with the language support of functions as first-class citizen, when resolution can't happen at compile time.
In my book, proper typing of overloaded function resolves this friction. Then, which typing would it be?

Take +, whose type could either be int * int -> int, float * float -> float and some more. Let discard overflow considerations here.

Caml "solves" the issue by having two distinctly named functions, + and +.. Ugly, not generic.
Haskell's typeclass seems pretty circular. Type would be Num -> Num -> Num, where Num is a type that supports addition. I read that as "+ is defined on types that define +".
Why not combining the possible types (union type), where the domains should be disjoint to prevent ambiguity.
Also, the type could be extended depending on context. For instance, if you import a linear algebra module, Matrix * Matrix -> Matrix would become part of the type.
Is there some type system along those lines?

Maybe the correct answer is "overloading resolution shall always happen at compile time anyway".   In that case, what would be the justification of such a commandment?


texts:
Is there an efficient algorithm which gives the minimum cost closed walk in an undirected graph, which visits all vertices?

Does this problem have a name? I tried to reduce this to similar problems (in particular the traveling salesman problem) to see if it was NP-hard, but was unsuccessful.

Here's an example:

Then a possible closed walk is: A,B,C,D,C,B,A, with a cost of 6.

Thanks!


texts:
Suppose there is a directed graph $G=(V,E)$, with source $s$ and sink $t$, and I compute the max flow on it. Then I know that I can find a min-cut $(A,B)$, by letting $A$ be the set of vertices that are reachable from the source $s$.

My question is is this set $A$ the smallest possible $s$-component? I think it is.
To be precise, does there exist a subset of vertices $A^*$, such that $(A^*, V\setminus A^*)$ is a min-cut, and for all other possible subsets of vertices $A$ such that $(A, V\setminus A)$ is a min-cut, we have $size(A^*) \leq size(A)$.

Furthermore, for any other min-cut $(C,D)$, do we have $A \subset C$?.  I also think this is the case. But I can't prove it.

Any intuition / hints are much appreciated!

Edit

Definition of $s$-component:
The min-cut is the partition of the vertices of $G$ into two disjoint sets $(A,B)$, where $A$ contains the source $s$ and $B$ contains the sink $t$. The $s$-component w.r.t. a min-cut is then the set $A$.

By "smallest" $s$-component I mean $s$-component with smallest cardinality. I'm wondering if there can be several different minimal $s$-component w.r.t. set inclusion, i.e. $s$-components with same cardinality, but are not equal as sets. Equivalently, wondering if there is a minimum $s$-component; a set of vertices that is in ALL $s$-components.


texts:
Prove or disprove: Complement of language
  $L=\left\{baba^2ba^3b...ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ is
  context-free.

I'm not quite sure how this is done. I would first try to find out whether $L=\left\{baba^2ba^3b...ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ itself is context-free.

The language creates words $x$ of length $|x|= n+1+\frac{n(n-1)}{2}= \frac{n(n+1)}{2}$

So $L$ is not context-free. But I was looking for the complement of $L$, i.e. $\bar{L}$, the language.

Is it possible to argue that $\bar{L}$ is context-free because $L$ is not?

Or how would you show it better?


texts: Are Interfaces counted as Functional Dependency?

texts:
I'm doing some homework where I have to count the number of functional dependencies (direct and indirect).

But then I'm faced with an unexpected situation, where a class has a relation with an interface. I can find no bibliography on the subject and the teacher didn't talk about this.

Intuituvely, I thought as it being a dependency, for it is used as parameter and attribute of the analyzed class. But should I also count its implementations as dependencies? They are not referenced directly, but can be used in a polymorphic approach.

Here's a basic example for understanding (its not the exercise, but something that came to my mind quickly to explain):


texts: SMO, Random forest and Bayes net algorithms: why does Random forest perform better?

texts:
I analyzed a dataset using those 3 different algorithms.
As I can see, Random forest performs better in most cases.
My dataset is composed of 4000 instances of two classes (class A 2000 elements, class B 2000 elements).
I use 207 metrics to classify the instances, but I also use the first 20 or 10 best metrics for InformationGain.
My question is: why sometimes an algorithm performs better than another one (in this case I'm only comparing this 3).
I read about them but I would like to have a complete scenario of why in some case RF is better than Bayes net and why sometimes is the opposite. And why SMO is always worst than the other two, in my experiences. Thank you so much!


texts: Hardness of multiplicative vs. additive approximation

texts:
Chlebik and Chlebikova prove that the problem "maximum 3-dimensional matching" is NP-hard to approximate within a multiplicative factor of $95/94$.
This means that, unless $P=NP$, there is no polynomial-time algorithm that finds a 3-dimensional matching with at least $(94/95)\cdot OPT$ edges, where $OPT$ is the number of edges in a maximum matching.
Suppose we would like an additive approximation algorithm, that finds a 3-dimensional matching with at least $OPT-1$ edges. Is such algorithm theoretically possible (if $P\neq NP$)?


texts:
We covered this in class today. I understand the mechanics of it, but aside from being a nice example of recursion does it serve any purpose?

Searching the web reveals lots of pages with the formula and it's implementation in code, some talk about the author, but nothing about it's purpose.


texts: Estimate complexity of integer sequence enumeration

texts:
I would like to seek help on the complexity of the following problem.  Given positive integers $m$, $n$, $D_1$ and $D_2$, find all sequences $a_1\lt a_2 \lt  \dots \lt a_n$ are there such that:

each $a_i\in\{1, \dots, m\}$
$\sum_{i=1}^n a_i = D_1$
$\sum_{i=1}^n a_i^2 = D_2$.

I want to know the complexity with respect to $m$, $n$, $D_1$ and $D_2$.

For example, when $m=12$, $n=4$, $D_1=26$ and $D_2=214$ the solutions are

$$    3,5, 6, 12\qquad
    2, 5, 8, 11\qquad
    1, 7, 8, 10$$


texts:
Let $G = (X+Y,E)$ be a bipartite graph and $k\geq 1$ an integer. A maximum $k$-matching is a subset of $E$ in which each vertex of $X$ is adjacent to at most $k$ edges and each vertex of $Y$ is adjacent to at most $1$ edge.
A maximum-cardinality $k$-matching can be found by the following algorithm:

Create $k$ copies of each vertex $x\in X$, such that each copy is adjacent to all neighbors of $x$ in $Y$.
Find a maximum matching in the resulting graph.

Its run-time complexity for a graph with $n$ vertices and $m$ edges, using the Hopcroft-Karp algorithm, is $O(k m\sqrt{k n}) =O(k^{3/2}\cdot m\sqrt{n})$.
I am interested in the following alternative algorithm:

Repeat $k$ times:

Find a maximum matching in $G$.
Remove the matched vertices of $Y$ from the graph.

Its run-time complexity is $O(k \cdot m\sqrt{n})$.
But does this algorithm always find a maximum $k$-matching?


texts: How is it possible to compare $P$ class with $BQP$?

texts:
BQP : (bounded-error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.

Question : We know that $\mathsf{P}$ and $\mathsf{NP}$ classes are defined on Turing model of computation where as $\mathsf{BQP}$ is defined over quantum model of computation. When there model of computation are different how we can say that $\mathsf{P} \subseteq \mathsf{BQP} $?


texts: How to create a regular expression for this language?

texts:
I have a language:

$$ \{a^jb^k \mid j \neq k \text{ and } j \equiv k \pmod 3 \}$$

I want to prove that this language is regular. My first thought was to create a regular expression that accounts for all three of the cases of modulo 3 like such:

$$(aaa)^*(bbb)^* | a(aaa)^*b(bbb)^* | aa(aaa)^*bb(bbb)^*$$

However, this doesn't account for the fact that $j$ cannot equal $k$. Is there a way to exclude certain cases like this in a regular expression?


texts: If $L$ is a regular language then so is $\sqrt{L}=\{w:ww\in L\}$

texts:
I am interested in proving that $\sqrt{L}=\{w:ww\in L\}$ is regular if $L$ is regular but I don't seem to be getting anywhere. If possible I was hoping for a hint to get me going in the right direction. Thank you for your help.

My idea for demonstrating regularity of the square root language was to try to consider two machines running in tandem. One of them accepts the original language $L$ and the other runs the same machine backwards (I expect that this will be an NFA). I then wanted to accept words that met in the middle (i.e ${(q,q):q∈Q}$  where $Q$  are the states of the DFA accepting $L$ ). However, I do not think this will work.


texts:
We have

Some big hashed array of data with boolean values, we know keys, but don't know values.
Oracle who have input of array of keys and can tell how much of them are true (it Answers with number T)

Number of keys N, true values M, for example M/N = 0.4

How to find a way to make own array of keys, length be M and if we ask oracle about those keys we should get T/M > 0.8 with minimum as possible questions to oracle ?

I tried to divide array by halfs and check which is bigger, and so on, but not moved far on this way. number of questions when testing was far more than N.

examples:

// test = {a: true, b: false, c: true, d: false}` M=2 N=4
T=oracle(["a", "b"]) //1
T=oracle(["a", "c", "d"])  //2

//we searching for a and c keys
T=oracle(["c", "b"]) //1
areWeDone(T/M) > 0.8 // 0.4 (false)
//.......
T=oracle(["a", "c"]) //2
areWeDone(T/M) > 0.8 // 1 (true)


texts: Find the subset of k element between n that maximize the total distance

texts:
Given a set $Q\subset \mathbb{N}^m $ of $n$ points, we want to find the subset $S_{max}\subset Q$ of $k$ elements that maximize the total distance between them, according to the $\ell^1$ norm.

$$S_{max} = \arg \max_S\sum_{i,j \in S, i \ne j} d(x_i,x_j)$$

In my specific case, $Q\subset \{ 0, 1 \} ^m $, thus  $d(\cdot,\cdot)$ is equal to the Hamming distance.

Is there any efficient way to solve this problem? Is it possible to rewrite it in another simpler way?


texts: The number of different regular languages

texts:
Given an alphabet $\Sigma = \{ a,b \}$, how many different regular languages are there that can be accepted by an $n$-state non-deterministic finite automaton?

As an example, let us consider $n=3$. We then have $2^{18}$ different transition configurations and $2^3$ different start- and end state configurations, so we have an upper bound of $2^{24}$ different languages.
However, many of these will be equivalent and since testing for that is PSPACE-Complete, it is probably unfeasible to test each setting.
Are there other means or combinatorial arguments that bound the number of different languages accepted by a given resource?


texts: Reducing infinite paths of a transition system to its set of sets of states

texts:
Consider a transition system defined by $\langle S,T \rangle$, where $S$ is a set of states and $T \subseteq S \times S$ is a set of transitions, where $T$ is total, i.e. for every state $s$ there is at least one outgoing transitions $(s,s') \in T$.
Each path corresponds to a set of states, namely, the states visited along that path.  Given a transition system $\langle S,T \rangle$ and an initial state $s_0 \in S$, I would like an algorithm that outputs the list of all sets of states that can arise from all infinite paths in $\langle S,T \rangle$ that start at $s_0$.
As a trivial example consider $S = \{s_0, s_1, s_2 \}$, $T = \{(s_0,s_1),(s_0,s_2),(s_1,s_1),(s_2,s_2)\}$, with initial state $s_0$; I would like the algorithm to output $\{s_0,s_1\}, \{s_0,s_2\}$.
Is there an algorithm for this problem?
I believe this can be accomplished with strongly connected components, but I don't know what to search for in the literature.


texts:
Logical Min Cut (LMC) problem definition

Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can make $t$ unreachable from $s$ by the removal of some edges of $G$ following the following constraints:

The number of the removed edges must be minimal.
We cannot remove every exit edge of any vertex of $G$ (i.e., no vertex with outgoing edges can have all its outgoing edges removed).

This second constraint is called logical removal. So we look for a logical, minimal removal of some edges of $G$ such that $t$ would be unreachable from $s$.

Solution attempts

If we ignore the logical removal constraint of LMC problem, it will be the min-cut problem in the unweighted digraph $G$, so it will be solvable polynomially (max-flow min-cut theorem).

If we ignore the minimal removal constraint of the LMC problem, it will be again solvable polynomially in a DAG: find a vertex $k$ such that $k$ is reachable from $s$ and $t$ is not reachable from $k$. Then consider a path $p$ which is an arbitrary path from $s$ to $k$. Now consider the path $p$ as a subgraph of $G$: the answer will be every exit edge of the subgraph $p$. It is obvious that the vertex $k$ can be found by DFS in $G$ in polynomial time. Unfortunately this algorithm doesn't work in general for an arbitrary directed graph.

I tried to solve the LMC problem by a dynamic programming technique but the number of required states for solving the problem became exponential. Moreover, I tried to reduce some NP-Complete problems such as 3-SAT, max2Sat, max-cut, and clique to the LMC problem I didn't manage to find a reduction.

I personally think that the LMC problem is NP-Complete even if $G$ is a binary DAG (i.e., a DAG where no node has out-degree greater than 2).

Questions

Is the LMC problem NP-Complete in an arbitrary digraph $G$? (main question)
Is the LMC problem NP-Complete in an arbitrary DAG $G$?
Is the LMC problem NP-Complete in an arbitrary binary DAG $G$?