texts: Understanding the equivalence of a Turing machine and an enumerating machine

texts:
The normal argument for a decidable language to build an enumerating machine is given as follows:
Let $M$ be a Turing machine which decides a language $L$, and let $s_1,s_2,\ldots$ be a list of all strings in $\Sigma^{*}$.
Consider the following enumerating machine:

Ignore the input
Repeat the following for $i = 1,2,3,\ldots$:

Run $M$ on $s_i$
If it accepts, print out $s_i$

This is what I see as a standard way of building an enumerating machine in case of decidable Turing machine.
I have few doubts about it:

How are we going to run $M$ on $s_i$? Are we going to write $s_1, s_2,\ldots$ one by one on enumerating machine working tape?

Is an enumerating machine made to run on all words in $\Sigma^{*}$  one by one?

If yes, then consider the enumerating machine constructed for a general Turing machine. The standard way is:

Ignore the input
Repeat the following for $i=1,2,3,\dots$:
Run $M$ for $i$ steps on each input $s_1,s_2,s_3,\dots$
If any computations accept, print out the corresponding $s_j$

The above is a standard way also mentioned in the Sipser book.
Now here how are we making $M$ on $s_1,s_2,s_3$, say in step 3?
Will this go to enumerating machine working tape?
Will the working tape be generated by the enumerating machine or fed as in in the case of a Turing machine?

If enumerating machine is not made to run on all words in $\Sigma^{*}$  one by one,
then in the above construction of our enumerating machine, how are we going to get the words $s_1,s_2,\ldots$ on its working tape?

I am confused about the way enumerating machine works.


texts: Are there any algorithms or data structures that need to find the median value of a set?

texts: I have been reading this book for my class, Randomized Algorithms. In this particular book, there is a whole section dedicated to finding the median of an array using random selection, that leads to a more efficient algorithm. Now, I wanted to know if there are any practical applications of this algorithm, in the domain of computer science, besides a theoretical improvement. Are there any algorithms or data structures that need to find the median of an array?


texts:
Let me define a volatile graph first:

It is an undirected graph in which the weight of each
edge varies every time we query it. That is, when we request the weight
w(e) of edge e, we obtain an approximate value ˆw(e) defined as follows:
wˆ(e) = w(e) + η, where η ∼ N (0, σ).
Here, N (0, σ) is a Gaussian distribution with mean zero and standard
deviation σ.

How to obtain a shortest path for such a graph. Let it be denoted as (G, u, v, p).
Find the correct shortest path between vertices u and v on a volatile graph G with confidence p. We can define p in any manner we want as long as it is consistent to the fact that as p grows, the probability that our algorithm returns the true shortest path should also grow


texts: Why larger input sizes imply harder instances?

texts:
Below, assume we're working with an infinite-tape Turing machine.

When explaining the notion of time complexity to someone, and why it is measured relative to the input size of an instance, I stumbled across the following claim:

  [..] For example, it's natural that you'd need more steps to multiply two integers with 100000 bits, than, say multiplying two integers with 3 bits.

The claim is convincing, but somehow hand-waving. In all algorithms I came across, the larger the input size, the more steps you need. In more precise words, the time complexity is a monotonically increasing function of the input size.

  Is it the case that time complexity is always an increasing function in the input size? If so, why is it the case? Is there a proof for that beyond hand-waving?


texts: Understanding The Mapping Of Edges to Nodes In A Graph Theory Problem

texts:
I am really confused with this problem.

Here's the problem:

You have $N$ points numbered $1$ through $N$,inclusive, and $N$ arrows again numbered $1$ through $N$,inclusive. No two arrows start at the same place, but multiple arrows can point to the same place and arrows can start and end in the same place. The arrow from place $i$ points to place $a[i-1]$,($a$ being an array representing the game board with $N$ elements and $i$ is between $1$ and $N$, inclusive).There are $0$ to $N$ tokens,inclusive, placed in those places and that, in each round, move along the arrows from their current place. If two or more tokens are in the same place, then you lose that game. But if that doesn't happen for the $K$ rounds specified, then you win the game. There may be multiple ways to solve the problem, but  Two ways are different if there is some $i$ such that at the beginning of the game place $i$ did contain a token in one case but not in the other. Count those ways and return their count modulo $1,000,000,007$.

The whole problem is confusing to me, but what really confuses me is that it states that the arrow that starts from $i$ goes to  $a[i-1]$. How I understand it, for the first example,( $\{1,2,3\} \;5$ Returns:$8$ ), if $a[1]=1$, $a[2]=2$, and $a[3]=3$, then $3$ maps to $2$ and $2$ maps to $1$, but then $1$ maps to $0$,(but point $0$ doesn't exist).

What would be more correct would be if $a[0]=1$, $a[1]=2$, and $a[2]=3$, but then all the points would map to themselves,(though it says in the example that the tokens don't move during the rounds).

I am probably way off, but I couldn't find many explanations, and the ones I found didn't make any sense to me, and I couldn't find many visual depictions either.


texts: Maximal number of parallel cellular calls with no adjacent cells in a hexagonal setting

texts:
Is it possible to find an optimization to the following theoretical case?

Given is a cellular (phone) system with hexagonal cells, where the volume of transmission and the size of the cells are designed such that the same band (frequency) can be used by two cells that don't share a common edge. It can be assumed that the collection range of bands (frequencies) can be divided into $n$ equal groups of band (frequencies) ranges in order to maximize the number of cellular calls that can be made in parallel in a given cell.

How can we find $n$?

I thought about the clustering of frequencies, i.e, a function $\{f_1,...,f_n\}$, and then, using the given topology (hexagonal), construct the clustering using the intuition that a cluster of size $n$ can be constructed if and only if $n=i^2+j^2+ij$. However, I think I am going in the wrong direction since I am not sure how to handle that the "same band (frequency) can be used by two cells that don't share a common edge". Here I am lost.

Is there an efficient solution to that?

A relevant picture:


texts: Linear congruential generator with uniform distribution

texts:
I am currently studying linear congruential generators, and there was an example in which I didn't get the code:

public class Random {

static final int a = 48271;
static final int p = 2147483647; //2^31 - 1
static final int q = p/a;
static final int r = p%a;
int state;

public Random() {
    this ( (int)(System.currentTimeMillis()%Integer.MAX_VALUE ));
}

public Random(int initialValue) {
    if (initialValue < 0)
        initialValue += p;
    state = initialValue;
    if (state == 0)
        state = 1;
}

public int randomInt() {
    int tmp = a * (state % q) - r * (state/q);  //line I don't get
    if (tmp < 0)
        state = tmp+p;
    else
        state = tmp;
    return state;
}
}

The teacher said that it was so that all numbers can be expressed in 32 bits (or somethig like that). The thing is that a LCG should have a period of exactly $p-1$ and I don't get why it should be the case with this line.

Could you also explain why the following code would not work?

public int randomInt() {
    int tmp = (a*state)%p;
    if (tmp <= 0) state = tmp+p;
    else state = tmp;
    return state;
}

Thanks in advance for any answer.

Edit: I compared both generators by generating numbers in the interval $]0,1[$ with the following codes:

    //Generators
    public int randomInt() {
        int tmp = (a*state)%p;
        if (tmp <= 0) state = tmp+p;
        else state = tmp;
        return state;
    }

    public int randomInt2() {
        int tmp = a * (state % q) - r * (state/q);
        if (tmp < 0) state = tmp+p;
        else state = tmp;
        return state;
    }

    public double randomReal() {
        return randomInt()/(double)p;
    }

    public double randomReal2() {
        return randomInt2()/(double)p;
    }

And the Main method:

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;

public class Main {

public static void main(String[] args) {

    File file = new File("resultatsGC.xls");
    FileWriter fw = null;
    Random rand = new Random();
    Random rand2 = new Random();
    double x, y;
    int[] tab = {0,0,0,0,0,0,0,0,0,0};
    int[] taby = {0,0,0,0,0,0,0,0,0,0};

    try {

         for (int i = 1 ; i < Math.pow(2, 31)-1 ; i++) {
            x = rand.randomReal();
            y = rand2.randomReal2();
            for (int j = 0 ; j < 10 ; j++) {
                if (x > j/(double)10 && x < (j+1)/(double)10) {
                    tab[j]++;
                }
                if (y > j/(double)10 && y < (j+1)/(double)10) {
                    taby[j]++;
                }
            }
            if (i%100000000 == 0)
                System.out.println(i+") "+x);
        }

        fw = new FileWriter(file, false);

        //Write in file the results
        for (int i = 0 ; i < 10 ; i++) {
            double a = ((double)i)/10;
            double b = ((double)(i+1))/10;
            String str = "["+a+";"+b+"]\t";
            fw.write(str);
            fw.write(tab[i]+"\t");
            fw.write(taby[i]+"\n");
        }

        fw.close();

    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    } finally {
        try {
            if (fw != null)
                fw.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
        System.out.println("DONE!");
    }
}
}

And here is what it graphically gives:

Orange columns are the results of the algorithm that I had a question about. Clearly, it is better (much more uniform), but my question remains: why is it correct (even more correct than the other)?


texts: Transitive closure of a directed graph (reachability) algorithm intuition/explanation

texts:
Consider $n\times n$ matrix $T$ which represents transitive closure of a directed graph. That means $T_{uv}=1$ if and only if there exist a directed path between vertices $u$ and $v$. Initially, $T$ is a identity matrix (every vertex has a self-loop). Now consider following function:
function insertEdge(u, v):
  for x from 1 to n:
    if T[x][u] == 1 and T[x][v] == 0:
      for y from 1 to n:
        T[x][y] = max(T[x][y], T[v][y])

This function adds a directed edge from $u$ to $v$, while maintaining the transitive closure of the matrix $T$. However, I have no idea how and why this algorithm works. So I'll be glad for any intuition or explanation of this algorithm.


texts:
This is a HW question that I'm stuck on and was hoping for some help.
we're supposed to prove that:

  PSPACE not equals DTIME($2^{cn}$) for every $c>0$ (or actually for the union of all $c>0$)


texts: Were boolean logic used in the analog computers?

texts:
I began a simple collection of the events behind todays computers. My knowledege in these fields is so limited, and I read:
"In the 1930s and working independently, American electronic engineer Claude Shannon and Soviet logician Victor Shestakov both showed a one-to-one correspondence between the concepts of Boolean logic and certain electrical circuits, now called logic gates, which are now ubiquitous in digital computers.[70] They showed[71] that electronic relays and switches can realize the expressions of Boolean algebra. This thesis essentially founded practical digital circuit design."
from https://en.wikipedia.org/wiki/History_of_computing_hardware#Digital_computation
I wonder if it's correct to say that "bools law were not used in the analog computers" (the early computers).
Greetings


texts: Parallel programming models: Why do OpenMP and MPI dominate?

texts:
In a lecture on HPC parallel programming (for CPUs) we discussed various models available from Pthreads to OpenMP to MPI and others like Charm++, X10, UPC, Chapel…. The main focus was clearly on the first three. Intrigued by the topic I did some research on my own but could find sources, examples and discussions mainly for those first three. Later I discovered "AMPI" which can even run legacy MPI application with many of the benefits Charm++ offers but nobody seems to use it.

Why are the other models so neglected? Compared to the rather crude MPI alternatives like Charm++ and UPC appear more convenient as they handle a lot of the "dirty work" neatly in the background.


texts: Example for Converting 3SAT to unary 2DFA

texts:
I have been told (generic explanation) that 3SAT could be converted to unary 2DFA with endmarkers (assuming each variable of 3SAT as a prime number and then for each clause creating a cycle in unary 2DFA).

Can someone please provide an example of the above with explanation of the process (a small example, say 3-4 clauses would be fine). Tried it but have not background in unary 2DFA.


texts: Mapping between kernel-level thread and user-level thread

texts:
This is my understanding:

There are two types of processes: user and kernel(OS). Each process can have single or multiple threads. The threads of a user process are called a user-level thread and the threads of a kernel process are called kernel-level threads. Scheduler, dispatcher etc. contains kernel-level threads. Both user-level threads and kernel-level threads can able to run on CPU.

There may be several user-processes in ready queue for execution, scheduler(kernel) decides which user process/ thread to run on CPU, dispatcher(kernel) gives control to the corresponding user-thread on CPU, the corresponding user-thread executes and terminates.

Consider the following statement (From Galvin os textbook):

To run on a CPU, user-level threads must ultimately mapped to an associated kernel-level thread.

My doubt is as follows:

What is the need of such mapping? Where am I going wrong?


texts: Fast and space efficient data structure for nearest neighbors in 3 dimensions?

texts:
I am looking for data structures to answer nearest neighbor queries in 3D which are reasonably space efficient (ie use at most $O(n^{1+\epsilon})$ space) and fast ($O(n^{\epsilon})$ or $O(log^k(n))$ query time in the worst case).

As a summary of what I already know:

1D is trivial (just sort the points and use binary search).
2D is a bit trickier, but with a point location data structure + voronoi diagram you can do it in $O(n)$ space and $O(log(n))$ query time.
In 3D and above, that solution breaks down since the Voronoi diagram of a set of points is $O(n^{floor(d/2)})$.

I am aware of approximate techniques based on kd-trees or grid based methods, though these are dependent on assuming either a uniform distribution of points or something about the distance to the nearest neighbor, and don't perform so well in all cases.  I am not interested in these randomized or approximate solutions - I want something that works for any data set in the worst case.  Is there anything out there that does this, or is there some lower bound which blows this idea out of the water?


texts: What if the travelling salesman travelled by plane?

texts:
It seems intuitive to solve a 2D dot-to-dot travelling salesman problem by eye using a greedy strategy. However we can only solve the TSP by eye if the graph is topographically accurate e.g. if A to B is 10 and A to C is 10 then B to C can't be 1000.

Is the greedy strategy still sub-optimal when we obey 2D scaling, ie travelling by plane? Below I managed to create a topographically accurate example where the greedy strategy is indeed sub optimal:

Starting at S:

Greedy: S B C A S => 2.83 + 4 + 5 + 2.2 => 14.03
Optimal: S A B C S => 2.2 + 3 + 4 + 3.16 => 12.36

Is there something special about the example above that will be common to all suboptimal greedy routes? Can geometry be used to minimize error?


texts: Did Menezes et al. switch the letters $\mu$ and $\lambda$ in Floyd's cycle detection note 3.8?

texts:
The letters $\mu$ and $\lambda$ are usually used to represent, respectively, the length of the tail of the graph and length of the cycle in the graph.  But Menezes on note 3.8, page 91 (or PDF-page 6), seems to have swapped their roles.

$\mu$ and $\lambda$ in Floyd's cycle detection algorithm">

There's nothing wrong with the description, but isn't there a usual-role swap there?


texts: How to create a model which predicts the radius of a circle?

texts:
My training set is made up of 2d images with one imperfect but broadly circular shape in them (plus plenty of noise).  I wish to train a model to predict the "radius" (obviously it's a somewhat subjective concept here) of the shape.

Let's say that I know the approximate center of the shape.

What approach would you use?  Have each input to the model be one of the pixels including that pixel's distance from the center, as well as its colour?

What if I also wanted to predict the volume of the shape, and it was less regular?


texts: How many combinations will be generated if below conditions are put?

texts:
I need a generalized formula for a set having size(s) having below restrictions,

for ex. X = 2,7,11,17,26

I want only the first combination 2+7 & ignore all of the combinations that start from 2+? (2-num combinations only) same for 3-num consider 2+7+11 & ignore all 2+7+?

Formula should be applicable for any set X without size restriction.


texts: Showing the following language is decidable

texts:
Let $BAL_{DFA} = \{<M> \mid M \text{ is a DFA that accepts some string containing an equal number of 0's and 1's } \}$ Show that $BAL_{DFA}$ is decidable.

Generally such questions seem to be solved by constructing a DFA that accepts all strings that have equal number of 0's and 1's and then constructing a DFA that accepts the intersection of the one we constructed and M. Then we can run $E_{DFA}$ to check. Here we can't construct a DFA that accepts $0^n1^n$ as it is not regular, but we could construct a PDA. I think Sipser's book gives a way. But intersection of two PDA's need not necessarily be a PDA. Also we don;t have anything like $E_{PDA}$ which is decidable. I am not aware. How could we solve this. I know this is a solved excercise in Sipser, but I want to understand how one could approach such questions.


texts:
I have been reading about the Strassen Algorithm for matrix multiplication.

As mentioned in Introduction to Algorithms by Cormen , the algorithm is not intuitive. However I am curious to know if there exists any rigorous mathematical proof of the algorithm and what actually went into the design of the algorithm.

I tried searching on Google and stackoverflow, but all links are only on comparing Strassen's approach to standard matrix multiplication approach or they elaborate on the procedure presented by the algorithm.

Note: The same question has been asked on https://stackoverflow.com/questions/19229454/strassens-algorithm-proof , but without any definite answers


texts: All words containing at least twice as many zeroes as ones

texts:
Consider the language
$$
\{ w \in \{0,1\}^* : \#_0(w) \ge \#_1(w) \}
$$
consisting of all words over $\{0,1\}$ in which the number of zeroes is at least twice the number of ones.
Is this regular, context-free, Turing decidable?
My Idea
It's not regular, because we need to track the number of zeros and so it cannot be done with
a finite number of states.
I am not sure if this argument is a formal one.
Turing Decidable - Yes
Take a machine which reads 1 from the end, writes an X there and then traverses the tape and X's two 0's.
If after all ones are gone the tape is empty of there are still zeroes left then it's accepted. Otherwise, if there are ones left
on tape after this operation, it's rejected.
Context-Free
I am unable to find any context free grammar for it. Neither can I prove that it's not context-free.


texts: Can someone explain how to calculate what time each host started and finished?

texts:
The diagram at right shows a WIFI network with an access point, X and three hosts, A, B and C. The large circles indicate the coverage areas of the three hosts. The coverage area
for X is not shown, but you may assume that it includes all three hosts. Assume RTS/CTS are not used.
Suppose X is transmitting a packet at time 0 and finishes sending it at time 100 µs. Also,

A gets a packet to send at time 50 that takes 100 µs to send and is assigned a backoff timer of 70.
B gets a packet at time 70 that takes 200 µs and is assigned a backoff timer of 200.
C gets a packet at time 120 that takes 150 µs and is assigned a backoff timer of 150.

For each of the three hosts, what time do they start sending their packets? You may ignore the inter-frame spacing and the time required for acks.
A starts sending at time 170
B starts sending at time 300
C defers while A is sending, so it starts at time 120+100+150=370.
Of the three packets sent, which are successfully delivered on the first attempt?
Only the packet from A is delivered.


texts: Understanding how to decide whether a language for a DFA is decidable

texts:
So from what I understand, if a language is recognisable then using a TM it can be accepted and halted or rejected or halted, however a language that is decidable can be accepted and always halts on rejection?

Given the language $A_{\mathrm{DFA}} = \{\langle A \rangle\mid A \text{ is a DFA and } L(A) = \{0, 1\}^∗\}$ , I want to determine if it is decidable.

What I have come up with so far is that it is a recognisable language, I don't believe it can be rejected, only accepted and halted due to the fact once the read head comes across a blank it can just accept it.  Is this the way I should be thinking?  Am I correct in thinking it is not decidable or is this not a valid way to argue the point?

What should my process of thinking be when I am trying to prove it by contradiction if it is not decidable?

Thanks in advance for any tips!


texts: Why is the usual simulated annealing algorithm using a Boltzmann probability?

texts:
I've coded a personal version for the simulated annealing problem, and I was wondering why, (other than by analogy to the physics), the probability is
$$ p = e^{-\dfrac{\Delta \text{length}}{T}}$$ (assuming we're applying to the TSP problem, so the parameter is here the length of the circuit).

Is there any way to explain why this law and not another? Is this one optimal?


texts: Graph algorithm or framework for determining node affinity based on utilities

texts:
I'm looking for an algorithm or framework for thinking about how to determine affinities between nodes. Perhaps affinity is poor choice of wording, but basically I want to use utilities between nodes to determine how alike or unalike they are from each other. I've attached an example diagram to illustrate what I mean:

In this example, Entities A and B are not well-aligned due to the negative utility between them. An appropriate algorithm or framework should identify that they belong to different groups, clusters, etc.

Additionally, I should be able to infer that Entities B and C are likely to be well-aligned, due to the mutual misalignment with A.

The utility magnitudes should also reflect the degree of alignment or misalignment. For example A2 and B3 should more more misaligned than A1 and B3.

To complicate things further, the utility "units" may be different, with multiple edges between nodes. As a simplifying assumption, I may be able to normalize utilities into a single edge and unit.

I apologize if this question is vague and/or ill-suited for this StackExchange. However I really don't have a good lead on how to tackle such a problem.


texts: How fast can we compute the size of maximum matching in an unweighted bipartite graph?

texts:
Is there a way to compute the size of a maximum matching
in an unweighted bipartite graph
more efficiently (e.g. faster) than computing a maximum matching?

It is a long shot but
it is often an interesting problem to avoid throwaway computations like these.

Motivation
The problem I am trying to solve is match-2
where the two sets are of different sizes.
I need to determine whether there is a matching
that covers all the vertices from the smaller set.
Knowing the size of the maximum matching
would let me check if it is is equal to or
smaller than the size of the smaller set
(if such a thing is possible then whenever the result is
"yes, there is a matching that covers the small set"
you would effectively know what its size is but only in that case),
but that is not strictly necessary:
if there is a way to compute the answer without computing the size
it is good for me.


texts: job scheduling with deadline and two cascaded machines

texts:
Given a set of $N$ jobs and two machines A and B, each machine can process only one job at a time. Each job, if processed, must be processed by machine A before processed by machine B. The processing time of job $i$ at machine A and B is $t_{i}^{A}$ and $t_{i}^{B}$ respectively. The deadline and the profit of job $i$ are $d_i$ and $p_i$ respectively. All jobs are available at time 0.

Problem: find a job scheduling that maximizes the total profit.

This problem is a reformulation of a small problem I face in my research. I know the job scheduling with deadline problem, but my problem is different.  I am not a computer scientist, so any suggestions about how to solve my problem would be very helpful.


texts: Statistical anomaly detection in time series

texts:
I'm looking for some algorithms that detect statistical anomaly in time series.

For example, Google Trend automatically detects peaks of a specific search query in time, and associates those peaks with most popular news stories at that time.
See this for example: http://www.google.com/trends/explore#q=titan

I'm looking for this kind of algorithms that detect those peaks, or just anomaly in general.

I can think of a simple way to do it, i.e. using short-run EMA minus long-run EMA as a signal. But I'm sure people have done more comprehensive analysis of tasks of this kind, and I want to learn more about that. Thanks for any pointers!


texts: Upper bounds for $NP$ based on $NEXP = EXP$

texts: It's open whether $EXP = NEXP \to P = NP$ (the other direction can be shown by padding).  My question: has there been any progress along these lines at all?  For example, can we show that $EXP = NEXP \to NP \subset SUBEXP$ (where $SUBEXP = \cap_{\epsilon > 0} 2^{n^\epsilon}$)?


texts: Expected number of random interval flips needed for sorting a random array

texts:
This question is inspired by the Bogo-Sort algorithm and the discussion of whether there are any worse sorting algorithms than Bogosort.
Assume that $A$ is an array initialized by a random permutation on the set $I_n=\{1,2,\ldots, n\}$.
Consider the next algorithm:

While $A$ is not sorted:

Pick two random numbers $i\leq j\in\{1,2,\ldots, n\}$ uniformly and reverse $A[i\ldots j]$.

For example, if the initial array was $A=1,4,2,3,5,6$ and the algorithm  picks $i=2,j=5$ then the value of $A$ after the reversal would be $1,5,3,2,4,6$.
Notice that this algorithm halts after finite number of iterations with probability 1.

What is the expected number of iterations for the algorithm?


texts: Is the equality of two DFAs a decidable problem?

texts:
So given two DFAs, is the problem of finding if they generate the same language a Decidable problem?

I already know that Equality of two CFL is not Decidable

but what about Equality of two DFAs? considering most of the problems with DFAs are decidable, is this decidable as well ?


texts: How to find the top k pairwise product of in an array of integers?

texts:
Input: An array $a$ of integers $[a_{1}, \cdots, a_{n}]$, and a positive integer $k$.

Output: The the top-k products of pairs in $a$.

Example: $a = [7,6,5,4,3,2,1],k=3$ , output $(42,35,30)$, with corresponding pairs $(7,6),(7,5),(6,5)$.

A naive solution would can be done in $O(k^{2}\log{k} + n\log{n})$, which sort the array first and enumerate over the cartesian product of the first $k$ elements.

I can afford the cost of sorting the array but when $k$ is large, $k^{2}\log{k}$ is costly, is there any better solution?


texts: What is the name of this type of function composition?

texts:
If standard function composition is defined as:

 (define compose
   { (B → C) → (A → B)
             → (A → C) }

   F G -> (λ X (F (G X))))

What type of composition does the below function describe? Is there a particular name for it in category theory?

 (define compose-2
   { (A → (X → C)) → (B → X)
                   → (A → B → C) }

   F G -> (λ Y (compose (F Y) G)))


texts:
Could someone explain me how to form a context-free grammar with all rules R by this example language, please?
\begin{equation}
L:=\left\{w c v c \overleftarrow{w} | w, v \in\{a, b\}^{+}\right\}
\end{equation}
The arrow over w means, that the word w is written backwards.

I already know that \begin{equation}
\Sigma=\{a, b, c\}
\end{equation}
and V (non terminal symbols) maybe have to be \begin{equation}
V=\{S, A, B, C\}
\end{equation}

Thank you for helping.


texts: Deterministic Time Hierachy Proof by Arora and Barak: Question about time to simulate Turing Machine $M$ that decides separating language

texts:
In the book "Computational Complexity: A modern approach", Arora and Barak proof the statement that $DTIME(n) \subsetneq DTIME(n^{1.5})$ by constructing a separating language $L \in DTIME(n^{1.5})$ but $L \notin DTIME(n)$. The language $L$ is the one decided by the following Turing Machine $D$:

  On input $x$, run for $|x|^{1.4}$ steps the Universal Tm $U$ of Theorem 1.9 to simulate the execution of $M_x$ on $x$. If $U$ outputs some bit $b \in \{0,1\}$ in this time, then output the opposite answer (i.e. output $1-b$). Else output $0$.

They now assume towards a contradiction that there would be a TM $M$ that for any $x \in \{0,1\}^*$ halts within $c|x|$ steps and outputs $D(x)$.

They write:

  The time to simulate $M$ by the universal Turing machine $U$ on every input $x$ is at most $c' c |x| \log(|x|)$ for some number $c'$ that depends on the alphabet size and number of tapes and states of $M$ but is independent of |x|.

But Theorem 1.9 about the Universal Turing Machine states:

  There exists a TM $U$ such that for every $x, \alpha \in \{0,1\}^*, U(x,\alpha) = M_{\alpha}(x)$ [...]. If $M_{\alpha}$ halts on input $x$ within $T$ steps, then $U(x,\alpha)$ halts within $C T \log(T)$ steps, where $C$ is a number independent of $|x|$ and depending only on $M_{\alpha}'s$ alphabet size, number of tapes, and number of states.

Given this theorem, wouldn't that mean that the time to simulate $M$ by the universal Turing machine $U$ is at most $c' \cdot c |x| \log(c \cdot |x|)$? If not, or it does not matter, why is that?


texts: Binary exponentiation of matrix - complexity

texts:
I want to calculate complexity for binary exponentiation of matrix of size $k$. Let's say that I'm using the simplest approach to multiply matrices (so with three for loops). The complexity of this operation would be $O(n^3)$. Now, the powering of matrix. Pseudo code (n is the power, A matrix):
power(n, A)
 if n == 0
  return 1
 else
   res = power(n/2, A)
   if n%2 == 0
     return res * res
   else
     return res * res * A

If I write the equation:
$$T(n)=T(n/2) + O(k^3)$$
where $T(n)$ is the complexity, is it correct to think of cost to be $O(k^3)$?
Then we sum
$$\sum_{i=0}^{\log_2n}O(k^3) = O(k^3\log_2n)$$
and for us $k=27$ is constant.
Hence $T(n)=O(\log_2n)$


texts: Maximum Sum SubArray - Naive Implementation

texts:
I am looking at a problem that is often asked in interview settings. The problem statement is:

  Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

I want to talk about the naive solution, where we generate all contigous subarrays, take their sums, and find the maximum sum. Here is an implementation of the naive solution:

function maxSubArray(arr) {
  let max = null;

  for (let i = 0; i < arr.length; i++) {
    const startIdx = i;

    for (let j = i; j < arr.length; j++) {
      let sum = 0;

      for (let k = i; k <= j; k++) {
        sum = sum + arr[k];
      }

      if (max === null || max < sum) {
        max = sum;
      }
    }
  }

  return max;
}

I know that this solution runs in O(n^3), but I do not understand why that is the case. If we "generate" all possible contigous subarrays, I can explain why that is an O(n^2) operation:

  Let's say that our input array is 4. We can create 1 contigous subarray of length 4; 3 contigous subarrays of length 3; 3 contigous subarrays of length 2, and 4 contigous subarrays of length 1. In other words, the number of contigous subarrays for an array of length n is the sum of 1 to n, or (n * (n + 1)) / 2. In asymptotic analysis, that is O(n^2).

Now, I understand that summing up each individual subarray is **not* free, but here is where I am stuck. I do not know how to "add the work that we do to get the sum of each subarray" to my existing time complexity of O(n^2).


texts: Finding a partition with minimum "maximal length"

texts:
We're given $n^2$ different points in $(0,1)$ : $x_1<  x_2 < \dots < x_{n^2}$.

We are required to choose $n$ points $x_{i_1}<\dots<x_{i_n}$ such that the value of $\max\,\{x_{i_1}, x_{i_2}-x_{i_1}, x_{i_3}-x_{i_2},\dots,x_{i_n} - x_{i_{n-1}}, 1-x_{i_n}\} $ is minimal.

It feels a lot like a dynamic programming problem, but I didn't manage to divide it into appropriate subproblems.

Any ideas?


texts:
I just started reading communication networks.
Now, routers contain the network layer, data link control layer and physical layer.
That being true I am confused as to why the network layer is required or to be more specific what is its function.
In "Computer Networks A top-down approach", it is written that the network layer inspects the datagram header to look at the source and host addresses and then passes the datagram to the data link layer of the next link for it to decide where to pass the data packet to.
                Network layer does not seem make any changes to the headers associated with the data packet or modify the headers in any way.
This begs the question, what does the network layer then do???


texts: How can Kneser-Ney Smoothing be integrated into a neural language model?

texts:
I found a paper titled Multimodal representation: Kneser-Ney Smoothing/Skip-Gram based neural language model. I am curious about how the Kneser-Ney Smoothing technique can be integrated into a feed-forward neural language model with one linear hidden layer and a softmax activation. What is the purpose of the Kneser-Ney in such a neural network, and how can it be used for learning the conditional probability for the next word?
EDIT:
Authors mention that we may obtain different mulitple labels from n-1 words integrating Kneser-Ney smoothing. It is not clear for me what these labels are. As I know, the output of a LM could be the next word. How is it possible to get more labels with the Kneser-Ney smoothing ?


texts:
I am interested in such a combinatorial problem: given a graph $G=(V, E)$ and a weight functions $w_v: V \mapsto R$, and $w_e: E \mapsto R$ we are asking about such a induced subgraph $G' = (V', E')$ of $G$ that maximizes the sum:
$
\sum_{e \in E'} w_e(e) + \sum_{v \in V'} w_v(v)
$.

The problem is NP-Hard (by the reduction from maximum clique problem) so any suggestions for approximation solutions (even greedy) and links to the literature would be appreciated.


texts:
Given is an alphabet $\Sigma = \{ 0, 1, 2 \}$ and a function quer to calculate the cross sum of a word.

$quer : \Sigma^*\to \Bbb N$ with:

$$quer(w)=\begin{cases} 0, &\text{when } w=\epsilon\\
quer(v)+x, &\text{when } w=vx, x\in\Sigma
\end{cases}$$

Where $\epsilon$ is the empty string.

Prove by Induction on words that $\forall w\in\Sigma^*$, $quer(w)\le 2*|w|$.

I can prove that the statement holds for $\epsilon$.

Base case: $quer(\epsilon) = 0 \le 2 * |\epsilon| = 0 $

How can I show that the statement holds in the inductive step?


texts: Two flavors of red-black trees with different performance

texts:
I've implemented two red-black trees (using the pseudo-code in CLRS) with slightly different flavors:

1) In the first tree, all the data is stored in the leaves.

2) In the second tree, the data is stored in the internal nodes.

In an application I have, I have many insertions and deletions.  The performance of the first red-black tree is orders of magnitude faster than the second (about 200 times faster).

I expected the second tree to be faster because it has about half as many nodes.  So this performance difference surprised me.

While it is possible that I did not implement them comparably, are there any other reasons for this performance difference (perhaps pertaining to the many insertions and deletions in the application)?


texts: Given a sorted array $A$, how can it be efficiently determined whether $\exists i . A[i] = i$?

texts: Given an array $A$ of integers in ascending order, how efficiently can it be decided whether there exists an integer $i$ such that $A[i] = i$? How would an optimal algorithm for this problem work?


texts: Decidablity of Languages of Grammars and Automata

texts:
Note this is a question related to study in a CS course at a university, it is NOT homework and can be found here under Fall 2011 exam2.
Here are the two questions I'm looking at from a past exam.  They seem to be related, the first:

Let
$\qquad \mathrm{FINITE}_{\mathrm{CFG}} = \{ < \! G \! > \mid G \text{ is a Context Free Grammar with } |\mathcal{L}(G)|<\infty \} $
Prove that $\mathrm{FINITE}_{\mathrm{CFG}}$ is a decidable language.

and...

Let
$\qquad \mathrm{FINITE}_{\mathrm{TM}} = \{ < \! M\!> \mid M \text{ is a Turing Machine with } |\mathcal{L}(M)|<\infty \}$
Prove that $\mathrm{FINITE}_{\mathrm{TM}}$ is an undecidable language.

I am a bit lost on how to tackle these problems, but I have a few insights which I think may be in the right direction.  The first thing is that I am aware of is that the language $A_{\mathrm{REX}}$, where

$\qquad A_{\mathrm{REX}} = \{ <\! R, w \!> \mid R \text{ is a regular expression with } w \in\mathcal{L}(R)\}$

is a decidable language (proof is in Michael Sipser's Theory of Computation, pg. 168).  The same source also proves that a Context Free Grammar can be converted to a regular expression, and vice versa.  Thus $A_{\mathrm{CFG}}$, must also be decidable as it can be converted to a regular expression.  This, and the fact that $A_{\mathrm{TM}}$ is un-decidable, seems to be related to this problem.
The only thing I can think of is passing G to Turing machines for $A_{\mathrm{REX}}$ (after converting G to a regular expression) and $A_{\mathrm{TM}}$.  Then accepting if G does and rejecting if G doesn't.  As $A_{\mathrm{TM}}$ is undecidable, this will never happen.  Somehow I feel like I'm making a mistake here, but I'm not sure of what it is.  Could someone please lend me a hand here?


texts:
How do I see if the following ciphertext eaeairtntrnaeemtve is a transposition cipher, using letter frequency?

This article suggest how to detect by using letter frequency detection and cryptanalysis but I am unsure of how to do this. Any suggestions?


texts: Tarjan's Strongly Connected Component algorithm

texts:
I am trying to understand Tarjan's strongly connected component algorithm and I have a few questions (the line numbers I am referring to are from Algoritmy.net):

On line 33 why is node.lowlink = min(node.lowlink, n.index) — shouldn't it be same as line 31: node.lowlink = min(node.lowlink, **n.lowlink**)?
Do we have to generate the components on line 40 in the while loop as we pop? Isn't it true that when the algorithm finishes, all the vertices grouped by lowLink should be the SCC?
Is it ever true that after we recurse in line 30, n may not be in stack? If not and (1) is true we can simplify line 29-33 as follows:

if n.index == -1
   tarjanAlgorithm(n, scc, s, index)
if stack.contains(n)
   node.lowlink = min(node.lowlink, n.lowlink)

I went ahead and implemented the algorithm in Scala. However, I dislike the code - it is very imperative/procedural with lots of mutating states and book-keeping indices. Is there a more "functional" version of the algorithm? I believe imperative versions of algorithms hide the core ideas behind the algorithm unlike the functional versions. I found someone else encountering the same problem with this particular algorithm but I have not been able to translate his Clojure code into idomatic Scala.

Note: If anyone wants to experiment, I have a good setup that generates random graphs and tests your SCC algorithm vs running Floyd-Warshall

Here is the full pseudocode (© Algoritmy.net, MIT licensed).

index = 0

/*
* Runs Tarjan's algorithm
* @param g graph, in which the SCC search will be performed
* @return list of components
*/
List executeTarjan(Graph g)
Stack s = {}
List scc = {} //list of strongly connected components
for Node node in g
if (v.index is undefined)
tarjanAlgorithm(node, scc, s)

return scc

/*
* Tarjan's algorithm
* @param node processed node
* @param SCC list of strongly connected components
* @param s stack
*/
procedure tarjanAlgorithm(Node node, List scc, Stack s)
v.index = index
v.lowlink = index
index++
s.push(node) //add to the stack
for each Node n in Adj(node) do //for all descendants
if n.index == -1 //if the node was not discovered yet                  // <--- line 29
tarjanAlgorithm(n, scc, s, index) //search
node.lowlink = min(node.lowlink, n.lowlink) //modify parent's lowlink  // <--- line 31
else if stack.contains(n) //if the component was not closed yet
node.lowlink = min(node.lowlink, n.index) //modify parents lowlink     // <--- line 33

if node.lowlink == node.index //if we are in the root of the component
Node n = null
List component //list of nodes contained in the component
do
n = stack.pop() //pop a node from the stack
component.add(n) //and add it to the component                         // <--- line 40
while(n != v) //while we are not in the root
scc.add(component) //add the compoennt to the SCC list


texts: What are the uses of multi-dimensional arrays?

texts: While studying arrays a question came to my mind. If only 1D and 2D arrays can be used, then why multi-dimensional arrays exist? Is there any use of multi-dimensional arrays?


texts: Decode Reed Muller codes efficiently given only a syndrome

texts:
So given some erroneous Reed Muller code-word's syndrome as well as the Parity-Check/Generator Matrix how would one find the error vector?

The approach I took naively was to build the syndrome table, and use the syndrome to find the expected error vector, but unfortunately its too costly and for systems where $m \geq 10$, my machine definitely cannot handle it. Most decoding schemes I found require not just the syndrome but the message/erroneous code-word as well, which in this case isn't given.

Any help would be greatly appreciated.


texts: A systematic approach to creating a simple test parser

texts:
I need to create a simple text parser that replaces {tokens} with text from a table. The more complicated bit is the {?text?} tag where text must be included only if the preceding AND the following tokens exist and are not empty. You could do {?text} where it looks for a non-empty neighbouring tag only on that side.

I am not a CS student and I don't have any formal education, but I am interested in this stuff.

I know I can bodge this via common sense and general logic but I would like to approach this in a more systematic manner, as this seems simple enough and like an excellent learning opportunity.

I am aware of the concept of formal languages and grammars, but I'm not sure where to start apart from randomly jumping over wikipedia pages that seem relevant(like Context-free grammars and Parse trees), until something starts making sense.


texts: No of ways in which n indistinguishable items can be placed in m indistinguishable boxes

texts:
This problem is the same as
number of ways to partition n into exactly m parts.

The recurrence given in Wikipedia has

p(n,k) =  the number of partitions of n using only natural numbers ≥ k

How to find no of partitions of n which has exactly k non-zero parts? Is there a recurrence relation to solve this?


texts: Is it correct to say L is RE if I can map reduction from LH to L?

texts:
I seem to be not understanding correctly what reductions means for Languages.

for example, Lets say there is a Language called LM.

I want to see if LM is recursive or not, to do that lets say I find a reduction from L-Halting problem to LM.

and I assume that LM is recursive, so I show that then L-Halting problem is also recursive, which of course is false therefore LM is not recursive.

but can I say that LM is RE because I found a way to reduce LH to LM?
if not how can I show that LM is RE?


texts: Solve a 2D grid which is already connected

texts:
You are given a 2d grid where each grid item has a value of 1 or 0, you can only move horizontally or vertically and if both blocks have value of 1. You are also given a starting index, the output should have the "connected" grid items property to true.

For example:

input = [
  [{value: 0}, {value: 1}, {value: 1}],
  [{value: 0}, {value: 0}, {value: 1}],
  [{value: 1}, {value: 1}, {value: 1}]
];

startRowIndex = 2;
startColumnIndex = 0;

output = [
  [{value: 0}, {value: 1, connected: true}, {value: 1, connected: true}],
  [{value: 0}, {value: 0}, {value: 1, connected: true}],
  [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}]
];

}

This is the first part of the question, this can be easily solved using either DFS or BFS.

The second part is you are given the output of the first function and the same start indices. Along with these two input arguments, you are also given a flipIndex. The grid item at the given flip index will have the value flipped. Now give the updated matrix with the updated "connected" path.

input = [
  [{value: 0}, {value: 1, connected: true}, {value: 1, connected: true}],
  [{value: 0}, {value: 0}, {value: 1, connected: true}],
  [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}]
];

startRowIndex = 2;
startColumnIndex = 0;

flipRowIndex = 1;
flipColumnIndex = 2;

output = [
  [{value: 0}, {value: 1}, {value: 1}],
  [{value: 0}, {value: 0}, {value: 0}],
  [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}]
];

Is there an effective algorithm to solve the above problem?


texts: Get specified bit in addition of two large binary numbers

texts:
I am performing an addition operation on two large binary numbers that have an equal number of bits. Both numbers are stored in an array of length $N$, which is rather large.

At first I tried running a loop over them and keeping track of carry bits. This wasted time, because the aim is to get the bit at a specific position in this sum.

So I modified my approach in following way. Starting from the specified index, I am looping until I find a 0 bit in same position on both numbers; I add only those parts to each other and return the bit at the specified position.

This seems okay, but is this the best I can do? Recall that I want to get the value of one specific bit of the sum, given by its position.


texts: Solving a recurrence relation using Divide and Conquer Master Theorem

texts:
For the recurrence relation

$$T(n) = 16T(n/4) + n!\,,$$

I have found that $T(n)\in Θ(n!)$.
Can this be deduced using the Master Theorem?


texts: What, if any, is the term for a node whose children are all leaf nodes?

texts:
More specifically, I'm interested to know if there is a term that describes a tree node that meets two conditions:
- It has >= one child
- Any children that it has are all leaf nodes.


texts: Check if a relation is reflexive, symmetric and transitive

texts:
I want to better understand how this actually works, as my solutions are
sometimes not 100% correct.
I have the following relation:

Check if the following relation is reflexive, symmetric, and/or
transitive:
$$ R_1 = \{ (x,y) \mid x,y \in \mathbb{R}, x=0 \land y \geq 0 \}. $$

so by that
$$ R_1 = \{ 00, 01, 02,03,04,05,06,07,08,09,010, \dots, 0R_+ \} $$
Basically $R_1$ is 0 and any $R_+$ number.
It is not reflexive, as $(a,a)$ is not in $R_1$.  I only have 00, but
not 11 or 22 and so on.
It is also not symmetric, as I don't have 01 and 10 or 02 or 50 and
05. So $xRy$ and $yRx$ are not true for $R_1$.
As for the transitivity, well, if $xRy$ and $yRz$ then $xRz$.  Well,
this one is hard to understand. I could use 00 as an example: If $y = 0$
and $z \geq 0$ then $xRz$ would work.  So I would say it is transitive.
Can anybody confirm if this would be correct? If not, i would really
appreciate a correct approach then for this task.


texts: What is the branch of Computer Science that studies how Anti Virus programs work?

texts:
It is a trivial exercise in finite automata to show that there is no algorithm that can detect all the viruses, yet there are many software companies selling Anti Virus Software.

Is there any part of CS that deals with Viruses and Anti Viruses ?

PS : I am not asking about non CS related justification of to have AV or not, but only what category/subject within CS they come under, if any. If AV is not a subject within CS then that is also an acceptable answer, are there any refrences within CS context to Viruses and AV's?


texts: Question regarding coin change algorithm (DP and greedy)

texts:
The question goes something like this:

Suppose you are living in a country where coins have values that are powers of p, V = [1, 3, 9, 27]. How do you think the dynamic programming and greedy approaches would compare?

Intuitively I want to answer that DP will be faster because greedy runs the same number of comparisons regardless of the relationship between the elements in V. But DP is a recursive call on previous elements, so the fact that there is always a ratio of p between each denomination of V would suggest that DP will end up making less recursive calls. Can anyone confirm my answer or tell me why I'm wrong?


texts:
Does $n\log n = O(n \log n + n)$ hold?

I don't think it does trivially because I think as $n$ grows larger, $n\log n$ will converge to one value, and as the $+ n$ grows, $n\log n + n$. But I am uneasy about my initial thoughts about this. For example, mergesorting a list and then iterating through each element to compare for the smallest difference would result in a running time of $O(n\log n+n)$, yet mergesort is $O(n\log n)$.


texts: Counting distinct elements in array using hash table and measuring efficiency

texts:
I need to implement an algorithm to solve the Count-distinct problem given an array of $N$ elements using a hash table, and devise metrics with which to measure my algorithm efficiency. I was told I can't have a table with $N$ cells. My current solution is to have $\lceil\sqrt{N}\rceil$ cells in the table and collisions are resolved using lists so, on average, each cell will hold at most $\lfloor\sqrt{N}\rfloor$ elements thus finding if an element is already present in the table is done, on average, in $O(\sqrt{N})$, and I get that, on average, inserting all element into the table and counting how many distinct elements there are is done in $O(N\sqrt{N} + \sqrt{N}) = O(N\sqrt{N})$
I have 2 main question:

Can I make it even more efficient? e.g making lookups in $O(\log{n})$ by utilizing binary search tree or limit the number of elements in each of table lists, although this means the number of cells will be dependent on $N$
How do I measure the efficiency? Solving the problem using sorting algorithms my metrics were number of comparisons and number of assignments, but using hash table there are no assignments (except for in the table), so I'm left with only comparisons in the lookup function.


texts: Finding simple min-weight path between two vertices in graph with negative edge weights

texts: Given a weighted graph (negative weights are allowed) and two vertices $u$ and $v$, can we find the simple min-weight path between $u$ and $v$? There can be a negative cycle on the path from $u$ to $v$, but we want to ignore that, and calculate the weight of a simple path between them. Can this be done in polynomial time?


texts: Complexity of matrix inverse via Gaussian elimination

texts:
I'm trying to determine the exact complexity of finding an $n\times n$ matrix inverse of $A$.
If it is known that the complexity of Gaussian elimination is $\frac{2}{3}n^3 + \frac{1}{2}n^2+O(n)$, then is it true that the complexity of finding $A^{-1}$ should be about twice same, since we are effectively doing two sets of Gaussian eliminations in parallel plus some row interchanges and multiplications?

Please correct me if I'm wrong.


texts: In an M/M/1 Queue, what does exponential distribution of service time mean?

texts:
I was reading about the M/M/1 Queue and that we assume new customers arrive according to a Poisson distribution, and each customer takes an amount of time to service that is drawn from an exponential distribution?

I understand what it means to have an arrival rate based on Poisson distribution - if an average of 10 come per hour, you'll have 9 a few times, 6 very infrequently, 11 pretty often etc - but what does it mean that service is exponential?

Does this mean that as you serve more customers, the average time it takes to service them rises exponentially? Wouldn't the system crash soon after a few customers?


texts: Is a single symbol, not in a set, a language?

texts:
I was reading about Turing machines and realized I'm not sure about the difference between the following scenario. Given the alphabet $\Sigma = \{a, b \}$, we have the following assertions:

$a \in R $
$\{a\} \in R$

I think that assertion $1$ is incorrect because $a$ is just a symbol, not a language. On the other hand $\{a\}$ is the language which contains only the $a$ symbol. Given that information, we can prove that $\{a\} \in R$ by trivially building a TM. Here, $R$ denotes the set of recursive languages.

Is my reasoning wrong? Thanks in advance.


texts: Can you give an example of a problem in $EXP^{RE}$ but not In $P^{RE}$?


texts: Huffmann algorithm if all frequencies are different

texts:
I need to Huffmann-ecode the following sequence S=AAGAATCACAGGGACTAA. We observe that the frequences are: f(A)=9, f(G)=4, f(C)=3, f(T)=2.
In the exercices I have seen so far, 2 leaves with same frequencies are joint to create a new root. And then you join them in each step.
In this example all frequencies are different though. I thus chose first to join C and T given that they are of minimum weight. In a second step I joined A and G. In a third step I joined these two trees by creating a final root. This was evaluated as wrong.
What is the correct way of building the Huffmann tree in this example. Thanks.


texts: Performance of Modified Dijkstra's algorithm with Binariy heap as Priority Queue

texts:
we know the performance of Dijkstra's algorithm with binary heap is O(log |V |) for delete_min, O(log |V |) for insert/ decrease_key, so the overall run time is O((|V|+|E|)log|V|).

Now let's modify the Dijkstra to stop once it reaches T (Destination) from S(Start). The given performance is:

Understand that we don't need to explore the full G in the modified Dijkstra run.
Can someone explain why it is the diamond shape(the 45 degree rotate of a perfect square)?

What does it means with the radios of |m|+|n|, (typo of radius ?)

What is m and n in this case? (m means vertices? n means edges?) seems to me that $(|m|+|n|)^2$ is half of the vertices and edges visited，which is half of the Diamond/Square. Then not sure how is it is computed.

added new pic for the additional questions


texts: $\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ even} \} $ is context free language

texts:
Let $\mathcal{L}$ be context free language over alphabet $\Sigma$. Define $\mathcal{G}$ as
$$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ even} \} $$

I have seen a similar question (asked 5 years ago) but I am not sure how it can work.

Proposition

$\mathcal{L}$ is CFL so it has own push-down automata. So let copy states of $\mathcal{L}$ and if it has a state called $S$ and it gets to state $T$ upon letter $x$ then $\mathcal{G}$ will have states $S_1, S_2, T_1, T_2$ and letter $x$ turns $S_1$ to $T_2$ and $S_2$ to $T_1$.

My question is why it is correct apporach? $\mathcal{G}$ automata won't read any of $v_1, v_3, v_5,... v_{k-1}$ so how it can ensure that this word belongs to $\mathcal{L}$?


texts: Help understanding this algorithm that's supposed to solve the critical section problem through mutual exclusion

texts:
Our professor gave us the following algorithm that's supposed to solve the critical section problem. I'm guessing the code is just pseudocode so I'm not trying to focus on the strange syntax and just trying to understand what it does.

 Main
  begin
   process_number=1;
   parbegin
    process1;
    process2;
   parend;
  end

Process1;
  begin
   while process_number=2 do;
   critical_section1;
   process_number=2;
   other_stuff;
  end;

Process2;
 begin
  while process_number=1 do;
  critical_section2;
  process_number=1;
  other_stuff;
 end;

After the code he says the following:

"Algorithm Guarantees mutual exclusion.

Price is high: P1 must go first, so if P2 is ready
to enter its critical section, it must wait.

When P1 enters and leaves its CS, P2 must go
next even P1 is ready, and P2 is not ready.

If one of the processes is terminated, then
eventually the other will not be able to proceed"

I don't even know what's going on. My best guess is that since process 1 and process 2 are running concurrently, and the variable process_number is originally equal to 1, Process 1 is going to stop at the condition (while process_number = 2). But for process 2 the condition (while process_number = 1) is true, so...it will do whatever lines of code follow it. But the lines of code that follow it are (critical_section2;) and why in the world would it be running critical_section2 if it the variable process_number = 1 is true. I..honestly have no idea what my professor was trying to get across in this confusing code.


texts: sort n numbers in the range [0,1] without multiplying or dividing

texts:
Given an array with n real numbers, each in the range [0,1], I need to sort them. Moreover, the only operations that are allowed are comparisons or copying.

It means I cannot multiply or divide the numbers, which prohibits me from using bucket sort.

From what I learned, when you use only comparisons you cant sort any faster that O(nlogn). That means that I can just use any sort algorithm that achieves this bound, let's say heapsort, and be done with it.

However, in this way i don't use the info that the numbers are from the range [0,1]. For this reason,  I'm not sure if I'm right.


texts: What is the big-$\Omega$ complexity of Fermat's Little Theorem?

texts:
Fermat's Little Theorem states that if an integer $n$ is prime them
$$
a^n \equiv a \pmod n \hspace{10mm} (*)
$$
for any $a \in \mathbb{N}$

My question is, is it correct to say that testing $(*)$ for some given $a$ has complexity $\Omega (n)$, since we would have to calculate $a^n$ which would require $n$ (multiplication) operations?

Additionally, what is the big-O complexity of testing this congruence?


texts: Why is every finite language A ⊆ Σ* regular

texts: So I've been doing regular languages a while and still need a better understanding of why all finite languages A ⊆ Σ* are regular? Is there a formal proof of it or is it just because a DFA can represent any finite language since the states would be finite as well?


texts: If a Ptime function loses x bits of data at every call, is it a one way function?

texts: If we have a computational function $f(x)=g(f(x-1)^2)$, where $g(y)$ is a floating point operation, mapped onto a given number of bits say 32 bits (thus leading to loss of a given number of precision bits every time), is the function a one-way function?


texts:
Suppose we have a set of functions $f_i: \mathbb Z \rightarrow \{0,1\}, i=1, \dots,n $, with the following property:

For each $i =1,\dots ,n$, there exists an $x\in \mathbb Z$ such that $f_i(x)=0$ and $f_j(x)=1$ for each $j\in \{1,\dots,i-1,i+1,\dots,n\}$. Also, there exists an $x \in \mathbb Z$ such that $ f_i(x)=1$ for each $i$.

Let $x\in \mathbb Z$. In order to determine whether $f_1(x)$ AND $f_2(x)$ AND ... AND $f_n(x)$, is it necessary to compute each $f_i(x)$ until one of these functions is found to be zero or until all functions are found to be one, which would take $\Omega(n)$ time in the worst case scenario?

Added to clarify: The functions $f_i$ are known. The input is $x \in \mathbb Z$.


texts: Distribution of beans in jars to k members

texts:
Here is the problem. We have N jars. Each jar can have any number of beans. These beans have to be distributed among C children. The resulting distribution should serve two goals Now

the number of beans that each child gets must be the same (+/- 1 when total number of beans is not a multiple of C)
each child to get all the beans from minimum number of distinct jars. Why? It is possible that beans in a jar may be contaminated. We want as few children to get infected as possible. E.g. if we have two jars with N beans each and two children, each child gets N beans. we would want child one to get N beans from jar 1 and child two to get beans from jar 2. As opposed to a solution, wherein child 1 gets half beans from jar 1 and half beans from jar 2. In former solution, if jar 1 is contaminated, only child 1 is infected. In latter solution, both children are infected.

So if

C = 5
beans = {B0:12, B1:12, B2:12, B3:12, B4:12} // Jar:<Bean-Count>

Distribution should be

{C1:{B0:12}, C1:{B1:12}, C2:{B2:12}, C3:{B3:12}, C4:{B4:12}}

Because each child has beans from exactly one jar. Following distribution will be less preferred

{C0:{B0:6, B1:6}, C1:{B0:6, B1:6}, C2:{B2:12}, C3:{B3:12}, C4:{B4:12}}

What will be the algorithm for achieving the distribution strategy with above goals in mind?


texts: Why do researchers only count the number of multiplications when analyse the time complexity of Matrix Multiplication?

texts:
In this article about the recent breakthough in Matrix Multiplication, it quotes Chris Umans's words:

Multiplications are everything. The exponent on the eventual running time is fully dependent only on the number of multiplications. The additions sort of disappear.

I was wondering how I should understand this. Why the number of additions doesn't matter?


texts: Can any finite problem be in NP-Complete?

texts:
My lecturer made the statement

  Any finite problem cannot be NP-Complete

He was talking about Sudoku's at the time saying something along the lines that for a 8x8 Sudoku there is a finite set of solutions but I can't remember exactly what he said. I wrote down the note that I've quoted but still don't really understand.

Sudoku's are NP complete if I'm not mistaken. The clique problem is also NP-Complete and if I had a 4-Clique problem is this not a finite problem that is  NP-Complete?


texts: building a polynomial algorithm that solves SAT when given a polynomial TM that solves SAT on two formulas

texts:
Here's the question:

  Assume there exists a polynomial time machine $M$ that receives two formulas $\varphi_1,\varphi_2$ and satisfies the following:

  If $\varphi_1 \in \mathrm{SAT}$ and $\varphi_2 \notin \mathrm{SAT}$, then $M(\varphi_1,\varphi_2)=1$
  If $\varphi_1 \notin \mathrm{SAT}$ and $\varphi_2 \in \mathrm{SAT}$, then $M(\varphi_1,\varphi_2)=0$

  Show that there also exists a polynomial time algorithm for SAT.

  Note that we have no guarantee for the output of $M(\varphi_1,\varphi_2)$ whenever $\varphi_1,\varphi_2$ are both satisfiable (or when both are not).

Can I get any hint on how to start the solution?


texts: Intersection/Union of recursively enumerable languages that aren't decidable?

texts:
For $L_1,L_2 \in RE - R $ , I want to prove or disprove if the following can occur:

$L_1 \cap L_2 \in R$
$L_1 \cup L_2 \in R$
$L_1 \cap L_2 \in R$ and $L_1 \cup L_2 \in R$

What I did:

I think any two disjoint languages suffice, since the empty set is decidable.
I think something along the lines of a language and its complement but I'm struggling to think of an example.
It seems impossible but I have no idea how to prove it.

Any help/further insight would be welcomed!


texts: metrics for evaluating the performance of a load balancing algorithm

texts:
I have proposed a load balancing algorithm for distributed systems which monitors the load on each device in this system and moves excess load from over-loaded device to less-loaded device. What are best metrics for evaluating the result before and after load balancing?

I studied several papers and found metrics like "average response time" and "average waiting time" for tasks. What are some other metrics that I can use to evaluate the result of my load balancing algorithm?


texts:
I solved a recurrence to get the formula $T(n) = \sum_{i=1}^{k}2i+1$ for $k = \frac{n-1}{2}$, namely

$$ T(n) = 1 + 3 + \dots + (n-4) + (n-2) + n, $$

but I'm not sure how to finish off the problem by writing the summation and solving for the complexity.


texts: Can a runtime environment detect an infinite loop?

texts:
Would it be possible for a runtime environment to detect infinite loops and subsequently stop the associated process, or would implementing such logic be equivalent to solving the halting problem?

For the purpose of this question, I define an "infinite loop" to mean a series of instructions and associated starting stack/heap data that, when executed, return the process to exactly the same state (including the data) as it was in before initiating the infinite loop. (In other words, a program generating an indefinitely long decimal expansion of pi isn't "stuck" in an "infinite loop," because at every iteration, it has more digits of pi somewhere in its associated memory.)

(Ported from https://stackoverflow.com/q/16250472/1858225)


texts:
I need to change x1 = 0.3 and x2 = -0.29 to a FP(floating point) number with one sign bit, a 4 bit mantissa, a 3 bit exponent. The results I got are:

x1: 0 001 0011

x2: 1 001 0010

I am also trying to calculate the number of significant digits of x1 and x2 and I have found 2 for each, but I am unsure of this result.

The question also requires me to find z = (FP)x1 + (FP)x2 and the number of significant digits of z. But I am not sure how to proceed with this part of the question. Therefore, any guidance on how I could proceed would be greatly appreciated.

Thank you very much!


texts: How can I efficiently construct a CFG from a language

texts:
I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}.
So m can be infinitely bigger than n but n can only be up to 3 more bigger than m and they can be the same. I have no idea how to make a CFG for this.
What I came up with was:
S -> AB | _
A -> a | aa | aaa | C | _
C -> aC | a | _
B -> bB | b | _

But I think this is not even close...
Any help/tips/advice would be much appreciated!


texts:
Let $X_1,...X_n$ denote some bins, and $w_1,...w_m$ some positive real numbers, where $m \in \mathbb{N}$, and the order matters, so e.g. we can't switch the position of $w_n$ and $w_1$. The goal is to take a subset of $\{w_1,...w_m\}$ and assign it for each bin, i.e. $\{w_1,...w_{i1}\}$ would go to bin 1, $\{w_{i_1+1},... w_{i_2}\}$ would go to bin 2,...$\{w_{i_{n-1}+1},...w_{m}\}$ would go into bin $n$, such that each bin contains "roughly" an equal sum of $w_i's$, e.g. the sums for $X_1,...X_n$ could approximately equal $100$, so $X_1$ could have a sum of 104, $X_2$ could have a sum of 97,... etc. Let's say this "equal sum" is $Z$.
Letting $Y_i$ be the sum for each $i^{th}$ bin, is there a way to choose Z such that the error is minimized, error being defined as $\sum_i |Y_i-Z|$, where $1 \leq i \leq n$?


texts: best way to solve max-flow min-cut on paper

texts:
I am looking at 7.10 from the Algorithms textbook known as DPV (Dasgupta,C. H.Papadimitriou,and U. V. Vazirani)
The graph has vertices s,t and A through F with 10 edges.

What is the best way to find the max flow and min-cut on paper?  I started out with pencil and an eraser, a table with columns for forward edges and backwards edges but it seems very unwieldy to do this manually for anything more than 5 vertices and 6 or 7 edges.
I specifically need to do this on paper for an algorithms course where a question like this could show up on exams.


texts: Game with Random Digits (Markov Chain / Coupling)

texts:
I've been self-studying Markov Chains and came across a problem online here: http://websites.math.leidenuniv.nl/probability/lecturenotes/CouplingLectures.pdf

I'm not asking for anything too formal (I'm still a newbie on the subject), but I would appreciate an intuitive explanation.

I'll summarize the problem as follows:

I draw 100 digits uniformly at random, with replacement, from the set of numbers {1, 2, . . . , 9, 0}, and list them in the order in which they were drawn. Then, two players A and B each follow these set of rules:

Randomly choose one of the first 10 digits.
Move forward as many digits as the number that is hit, except move forward 10 digits when a 0 is hit. For example, if a player randomly chooses the digit 3, move 3 steps to the right, and observe the digit at that spot.
Repeat.
Stop when the next move would go beyond the 100th digit, and record the last digit that you stopped at.

It turns out that the probability that the two players record the same last digit is approximately 0.974. Why is this probability so close to 1?

So obviously this problem is about coupling. I have a couple questions about it:

1) I can see that the longer this game goes on, it becomes more likely for players A and B to eventually converge to the same digit, after which they are in lock-step. Even at the very beginning, the probability that A and B both randomly happen to choose the same digit is >= 1/10, and the probability can only increase from there. However I don't know how one could actually compute the probability of convergence in this case or even to put a reasonable lower bound on it. Perhaps someone could give a more detailed (albeit informal) explanation?

2) I wonder if, for a particular list of 100 randomly chosen digits, it is possible to simply observe this list and somehow figure out with some high confidence which number you're likely to end up at, given the above rules. I suspect it should be possible (without running a bunch of brute-force simulated trials), but is it as simple as, say, just playing the game yourself (once) and choosing the last digit you ended up at?


texts: What is the pushdown automata for the language {0, 1}* Where |0| = 2 * |1| or |1| = 2 * |0|?

texts:
Having a lot of trouble figuring this out.

It seems to me to be impossible. I could do one side of the OR - but the fact that the string can begin with 100 1's and then have 200 b's seems like it can't be accounted for. Am I supposed to just stack every single a and b it traverses, and then somehow find a way to compare the numbers of each? Seems impossible.


texts: Confusion about assignment axiom in Hoare logic

texts:
I wanted to know if we are given the f.f.g. Hoare triple:

{x = 43}x := x + 1{x = 44}

How do we show that this is a valid Hoare triple?

My attempt was:

Using the assignment axiom:
{x + 1 = 43} x := x + 1 {x = 44}

But this doesn'the make sense. I also want to know what went wrong in my attempt?


texts: PAC learning: success of learning when receiving a sample from a different distribution

texts:
I've come across this question and I think I'm on the right track with the idea I just don't really know how to formalize it properly or understand why everything said in the question is required for the proof. The question is as follows:

Let $\mathcal X$ be a finite example domain and let $\mathcal Y = \{0, 1\}$. Let $H ⊆ \mathcal Y^ \mathcal X$ be a finite hypothesis
class. Let $\mathcal D$ be a distribution over $\mathcal X \times \mathcal Y$. Let $\mathcal G$ be a different distribution over $\mathcal X × \mathcal Y$, such
that $G_{Y |X} = D_{Y |X}$. Suppose that an ERM algorithm $\mathcal A$ receives a sample from $\mathcal G$ instead of
a sample from $ \mathcal D$, that is: $S \sim \mathcal G^m$.
Prove that if $\mathcal D$ and $\mathcal G$ are realizable by $\mathcal H$, and $supp(\mathcal D_\mathcal X) ⊆ supp(\mathcal G_\mathcal X)$, then for every
$\epsilon, \delta \in (0, 1)$, there exists a sample size $m$ (that can depend on $\mathcal D, \mathcal G, \mathcal H, \epsilon, \delta)$ such that
$\mathbb P_{S\sim \mathcal G^m}[err(\mathcal A[S], \mathcal D) \geq \epsilon)] \leq \delta$.

My idea was that since the conditional distributions are equal and the realizability assumption holds it must be that the labeling function for each distribution, say f and g, are the same as well.
Now since the support of D is contained in the support of G, any example that can be observed in the sample drawn from D can also be observed in a sample drawn from G, hence enough examples drawn from G will suffice to achieve a training set S that contains all of the support of D. However, I can't quite formalize this idea.
Thanks in advance!


texts: Reweight general weighted graph to distinct graph for using Borůvka's

texts:
Is it possible to re-weight a generally-weighted graph to a distinctly-weighted graph to apply Borůvka's algorithm (wiki) for minimum spanning tree to it?

I can't seem to think of a way to make a distinction between the same weights, it feels unnatural.


texts: The most efficient algorithm for computing cardinality of sumset

texts:
Let A and B be two finite non-empty sets of positive integers. Their sumset is the set of all possible sums a + b where a is from A and b is from B. For example, if A = {1, 2} and B = {2, 3, 6} then A + B = {1 + 2, 1 + 3, 1 + 6, 2 + 2, 2 + 3, 2 + 6} = {3, 4, 5, 7, 8}.

As we can see, cardinality #(A + B) is less than sum of cardinalities #A + #B. So i wonder whether we can calculate #(A+B) faster than just calculating all #A + #B sums and inserting them in some set-like data structure.

I've tried searching "sumset cardinality algorithm" and so on but didn't succeed.

P.S. We may assume that there is some constan K, not very lare - for example 10^5, such that 1 <= #A, #B <= K and all the elements of A and B are between 1 and K


texts: Clever memory management with constant time operations?

texts:
Let's consider a memory segment (whose size can grow or shrink, like a file, when needed) on which you can perform two basic memory allocation operations involving fixed size blocks:

allocation of one block
freeing a previously  allocated block which is not used anymore.

Also, as a requirement, the memory management system is not allowed to move around currently allocated blocks: their index/address must remain unchanged.

The most naive memory management algorithm would increment a global counter (with initial value 0) and use its new value as an address for the next allocation.
However this will never allow to shorten the segment when only a few allocated blocks remain.

Better approach: Keep the counter, but maintain a list of deallocated blocks (which can be done in constant time) and use it as a source for new allocations as long as it's not empty.

What next? Is there something clever that can be done, still with constraints of constant time allocation and deallocation, that would keep the memory segment as short as possible?

(A goal could be to track the currently non-allocated block with the smallest address, but it doesn't seem to be feasible in constant time…)


texts: How does the processor find kernel code after an interrupt?

texts:
When an interrupt occurs, the processor preempts the current process and calls kernel code to handle the interrupt. How does the processor know where to enter the kernel?

I understand that there are interrupt handlers which can be installed for each interrupt line. But since the processor only executes 'hardwired logic', there has to exist some predefined place that points to either an interrupt handler itself, or some code that executes before the handler (since there can be multiple handlers for one interrupt line, I assume the latter).


texts: How does the computer determine whether a number is smaller or greater than another?

texts: It might sound like a stupid question but I'm really curious to know how a computer knows that $1<2$? Also, how does a computer know that the order of integer is $1,2,3,4,5,\ldots$ and alphabet is A,B,C,D,...? Is it somewhere stored in the hardware or does the operating system provide this kind of information?


texts: Proving that pairs of words in resp. not in a TMs language are neither semi- nor co-semi-decidable

texts:
I have a homework assignment in which I am required to determine if
$$L = \{ \langle M,x,y \rangle : x\in L(M),y\notin L(M) \}$$
is in $$R,RE-R,coRE-R \text{ or } \overline{RE \cup coRE}$$

Now, my instinct tells me that $L_1 \in \overline{RE \cup coRE}$, because how can you show that a machine $M$ does not recognize a string $y$? However, I don't know how to prove it. The only such language I know is
$$EQ_{TM} = \{ \langle M_1,M_2 \rangle :  L(M_1)=L(M_2)\}$$
and I don't see a reduction from the latter to the former.

Any suggestions please?


texts: Is there a university that accepts students for CS Masters Degree without needing Bachelor's degree?

texts:
I am looking for a university/college that offers courses in English language and accepts students for Masters Degree in Computer Science and/or Mathematics without asking for a Bachelor's Degree. I have been studying online (doing courses from Coursera, EdX etc.) and have about the same knowledge as undergraduate students. So, does such university exist or should I just forget about it? Is there any way I can get accepted in any Graduate level studies in the above mentioned fields without having a bachelor's degree?

p.s. I hope I am asking this question in a right place (if I'm not, please let me know and I will delete it).


texts: What is the complexity to show this theorem?

texts:
Given a sum of regular expressions, where each regular expression in the sum is n-1 concatenations of 0, 1 and (0+1).

There is need to show that the sum of all regular expressions is either equal to or not equal to the regular expression, which is n-1 concatenations of (0+1).

I want to know what is the complexity to show this theorem?

Actually it is possible to open up all brackets and parentheses, but this increases number of regular expressions in the sum to some exponential number.

Proof in this way is very long and requires a lot of large papers.

I want to know if there is more easier, efficient and faster way to do this proof?


texts: the difference between Idle point and Idle slot

texts:
I believe that I don't understund well the difference between an idle processor point and an idle slot
Thanks


texts: Identifying set of longest time periods excluding overlapping time ranages

texts:
Suppose I have set of time records as follows

08:00 - 12:00
10:00 - 12:00
08:00 - 13:00
13:00 - 19:00
12:00 - 17:00

Now I want to select set of time records that are not overlapping and has the largest sum.

 08:00 - 13:00 + 13:00 - 19:00 = 12hours

My current approach is

Sort the records by start time
Select the first record and compare with each record and get the sum and store sum and the index of records.
Then select the second item repeat the process.
Loop through sum array and find the largest sum and indexes of records

Is there any better approach I can follow ? Is this a problem related to Dynamic programming ?

Thanks.


texts: Is this a proper Max Heap Data Structure

texts:
I was trying to understand the concept of Max-Heap. And to my understanding its a complete binary tree and each parent has a value greater than its children.The example I was going though had the following array which it said was a Max-Heap.

BookArray [] = {45,10,11,3,2,7,9,1,0}

I then decided to shuffle the elements (so they are no longer in binary heap) and got this.

Shuffled[] = {11,1,0,7,9,3,2,10,45}

I then decided to write a program that would sort the elements in the array in Min-Heap
so I got this array

Sorted[] = {45,11,3,10,7,0,2,1,9}

My question is if my sorted array is also a valid max-heap ? since my array does not match the bookArray


texts: Why did RSA encryption become popular for key exchange?

texts:
This is a soft question.  I don't know a lot about cryptography or its history, but it seems like a common use for RSA is to do key exchange by encrypting a symmetric key to send a longer message (e.g., the description of iMessage here).  Isn't this exactly the thing that Diffie-Hellman key exchange, which is older (and to me seems simpler) is for?  Looking at Wikipedia, they were also both patented, so this wouldn't have been responsible for the choice.

To be clear, I'm not asking whether it's theoretically important that public key cryptography is possible.  I'm asking why it became a standard method in practice for doing key exchange.  (To a non-cryptographer, DH looks easier to implement, and also isn't tied to the details of the group used.)


texts: The decidability of a problem involving univariate integer polynomials

texts:
Suppose that we are given $f_1(x),...,f_n(x) \in \mathbb{Z}[x]$. Decide whether there exist $a_1,...,a_n \in \mathbb{Z}$ such that

$\sum_{i=1}^{n} a_if_i(x) = p(x)^2 $

$p(x) \in \mathbb{Z}[x]$.

In other words, decide whether there are integer coefficients such that a linear combination of the given polynomials is a perfect square.

For example, if we have

$f_1(x) = x$ and $f_2(x) = x^2 + 1$

as input, then we have that

$2f_1(x) + f_2(x) = x^2 + 2x + 1 = (x+1)^2$.

So given the input $f_1(x), f_2(x)$ we would want to answer yes.

My first thought of attacking this problem was to plug in a sufficient number of points for $x$ so that we can solve it as a system of diophantine equations with some non-linear constraints.

So we would get a system like:

$\sum_{i=1}^{n} a_if_i(1) - b_1 = 0$

$\sum_{i=1}^{n} a_if_i(2) - b_2 = 0$

...

$\sum_{i=1}^{n} a_if_i(k) - b_k = 0$

$c_1^{2} - b_1 = 0$

...

$c_k^{2} - b_k = 0$

for $a_i, b_i, c_i \in \mathbb{Z} $ and for sufficiently large k.

I am not sure whether this is an erroneous way of trying to attack the problem, but looked reasonable to me as a first guess.

Whether a solution exists to a non-linear diophantine equation in general is an undecidable problem. So it appears plausible that this problem is undecidable as well, but a proper proof looks beyond my ability. So, does anyone have any suggestions, further information on related problems or even an undecidability proof?


texts: Set cover such that every vertex appears in at most k sets

texts:
Given a set $\{x_1,x_2,\dots, x_n\}$ and sets $\mathcal(F)=\{f_1,f_2,\dots, f_m\}$.

Is there any hardness result or approximation algorithm to find a set cover with this extra condition.
For every vertex $x_i$ appears in the intersection of at most k sets.


texts: Counting number of sums from contiguous subarrays of an array

texts:
We are given an array $a[1 \ldots n]$ with all $a[i]>0$.

Now we need to find how many distinct sums can be formed from its subarrays (where a subarray is a contiguous range of the array, i.e., $a[j\ldots k]$ for some $j,k$, the sum is the sum of all of the elements of the subarray). For example, if $a=[1,2,1]$, then the answer is 4: we can form $ 1,2,3,4$.

I know how to count the number of distinct sums in $O(n^2)$ time.

Furthermore, I have come to realise this is similar to the classical problem where we need to find the number of distinct substrings of a string. I was thinking of the possibility of constructing a suffix array and solving it in a similar fashion (in $O(n)$ time). But I have not been able to figure out how to modify that to work here. For example, if we use suffix array for $a=[1,2,1]$ we will get 5 cases instead of the four acceptable ones. Is this possible to do this using suffix arrays or am I thinking in the wrong direction?

Also there is one more direction I have been thinking in. Divide and conquer. Like if I divide the array into two parts every time until it is reduced to a single element. A single element can have one sum. Now if we combine two single elements, It can be done in two ways: if both single ranges have same element then we get 2 different sums, or if both have different elements we get 3 different sums. But I am not being able to generalize this for merging arrays of length greater than 1. Is it possible to merge two m size arrays and get the answer in $O(m)$?


texts: Minimizing sum of recursive pairwise sums

texts:
What is the best algorithm for this?

We are given an array of positive integers and we want to minimize the total cost of recursively adding together all the integers to one integer, two integers at a time. The cost of each addition is the sum of the two integers, and this sum adds up cumulatively. After each addition, the two integers are removed from the array, but their sum is added, until only one value remains.

I think I have figured out so far that the optimal solution is to add up the two smallest values in the array at every step (as the earlier the figure is used the more times it is included in the cumulative cost.) Perhaps there is another way to think about the problem, though.

Is there some mathematical fact that trivializes the solution perhaps?

Example A:

Input: [1, 5, 3, 7]
Adding 1 and 3 together (Cost 1+3 = 4)
State: [5, 7, 4]
Adding 4 and 5 together (Cost 4+5 = 9)
State: [7, 9]
Adding 7 and 9 together (Cost 7+9 = 16)
State: [16]

Total cost: 4 + 9 + 16 = 29

Example B:

Input: [1, 1, 1, 1, 1]
Adding 1 and 1 together (Cost 1+1 = 2)
State: [1, 1, 1, 2]
Adding 1 and 1 together (Cost 1+1 = 2)
State: [1, 2, 2]
Adding 1 and 2 together (Cost 1+2 = 3)
State: [2, 3]
Adding 2 and 3 together (Cost 2+3 = 5)
State: [5]
Total cost: 2 + 2 + 3 + 5 = 12

(I made these examples up myself; let me know if the examples are not actually the optimal solutions, although I am pretty confident they are.)


texts: Can pushdown automata be without epsilon transitions?

texts: Are pushdown automata without $\varepsilon$-transitions as powerful as those with them? Intuitively, if we need to make such a transition, we could just add the letters on the next transition we take, but I'm not convinced by that reasoning.


texts: Satisfy edges' constraints when updating node in directed acyclical graph

texts:
I have a directed acyclical graph. Each node represents an event with start and end dates and each edge represents a constraint between to events with 2 properties:

max interval between previous event end and next event start
min interval between previous event end and next event start

When an event's date is updated, all edge constraints should be respected and every other event's date should be recalculated if those constraints are violated. Problem is that there might be multiple conflicting constraints and I'm struggling to find best way to traverse the graph updating events without breaking previously satisfied constraints.

I have no formal CS education and my knowledge in this area is quite limited. Is there an existing algorithm to solve my problem?


texts: Algorithm to generate the number of tuples that satisfy the sum equals product problem.

texts:
Problem Statement:
Let $n\geq 2$ be a natural number. We are interested in sequences $(x_1,x_2,...,x_n)$ of natural numbers such that
$$x_1+x_2+...+x_n = x_1x_2...x_n\text{ and }x_1\leq x_2\leq...\leq x_n.$$
Let $A(n)$ denote the set of all such sequences. Moreover, we denote by $a(n)$ the cardinality of the set $A(n).$  The goal is to generate $a(n)$ for $n\geq 2.$

Attempt: Naive attempt in Python 3.5

from itertools import product

def prod(tup):
    """
    Computes the product of all elements in the tuple.
    """
    p = 1
    for i in tup:
        p = p*i
    return p

def a(n):
    """
    Check Sum Equals Product Property.
    """
    list_of_tuples = list(product(range(1,2*n+1), repeat = n))
    count = 0
    for tup in list_of_tuples:
        if sum(tup) == prod(tup):
            count = count + 1
    return count

It can be proved that for all $n\geq 3$ that
$$x_1+x_2+...+x_n\leq 2n.$$
So I just used the bound $1\leq x_i\leq 2n$ for all $i=1,2,...,n.$ I know this is really bad because it is $O((2n)^n)$ and I not generating non-decreasing sequences. I guess one would want to reduce the number of tuples to check, but I am not sure how to do this. Perhaps someone has an idea?


texts: Complexities of basic operations of searching and sorting algorithms

texts:
Wiki has a good cheat sheet, but however it does not involve no. of comparisons or swaps. (though no. of swaps is usually decides its complexity). So I created the following. Is the following info is correct ? Please let me know if there is any error, I will correct it.

Insertion Sort:

Average Case / Worst Case : $\Theta(n^2)$ ; happens when input is
already sorted in descending order
Best Case : $\Theta(n)$ ; when input is already sorted
No. of comparisons : $\Theta(n^2)$ in worst case & $\Theta(n)$ in best case
No. of swaps : $\Theta(n^2)$ in worst/average case & $0$ in Best case

Selection Sort:

Average Case / Worst Case / Best Case: $\Theta(n^2)$
No. of comparisons : $\Theta(n^2)$
No. of swaps : $\Theta(n)$ in worst/average case & $0$ in best case
At most the algorithm requires N swaps, once you swap an element into place, you never touch it again.

Merge Sort :

Average Case / Worst Case / Best case : $\Theta(nlgn)$ ; doesn't matter at all whether the input is sorted or not
No. of comparisons : $\Theta(n+m)$ in worst case & $\Theta(n)$ in best case ; assuming we are merging two array of size n & m where $n<m$
No. of swaps : No swaps ! [but requires extra memory, not in-place sort]

Quick Sort:

Worst Case : $\Theta(n^2)$ ; happens input is already sorted
Best Case : $\Theta(nlogn)$ ; when pivot divides array in exactly half
No. of comparisons : $\Theta(n^2)$ in worst case & $\Theta(nlogn)$ in best case
No. of swaps : $\Theta(n^2)$ in worst case & $0$ in best case

Bubble Sort:

Worst Case : $\Theta(n^2)$
Best Case : $\Theta(n)$ ; on already sorted
No. of comparisons : $\Theta(n^2)$ in worst case & best case
No. of swaps : $\Theta(n^2)$ in worst case & $0$ in best case

Linear Search:

Worst Case : $\Theta(n)$ ; search key not present or last element
Best Case : $\Theta(1)$ ; first element
No. of comparisons : $\Theta(n)$ in worst case & $1$ in best case

Binary Search:

Worst case/Average case : $\Theta(logn)$
Best Case : $\Theta(1)$ ; when key is middle element
No. of comparisons : $\Theta(logn)$ in worst/average case & $1$ in best case

I have considered only basic searching & sorting algorithms.
It is assumed above that sorting algorithms produce output in ascending order
Sources : The awesome CLRS and this Wiki


texts: Inserting a new face in a Half Edge data structure (open-mesh and not)

texts:
I'm trying to figure how to implement face insertion in a halfedge data structure to represent 3D meshes, I think it's safe to assume I'll only deal with meshes that have disc topology.

Although I've asked here to help me out with the understanding of the algorithm (taken from the open-mesh library). However I just read through the documentation and openmesh can also handle non manifold meshes, therefore maybe understanding that algorithm doesn't have any benefit on the case of manifold surfaces.

If you have any understanding of open-mesh can you please share, if you know, how the insert face works?

Otherwise, for the case of disc topology meshes, can you tell me how the new face insertion should work?

The bit I get confused is how to guarantee the disc topology is preserved when one of bounding vertices is already incident to some faces.

Even a reference would be great.

More detail:

In a mesh library like CGAL or OpenMesh the first step in creating a mesh is to specify vertices. I.e. suppose you have vertices $v_1,\ldots, v_n$ this would be added to a mesh with function calls like vh[i] = m.add_vertex(v[i]) here vh[i] is the vertex handle (usually returned) by inserting v[i]. Once this is done we can specify connectivity of such vertices.

As mentioned in openmesh to PolyConnectivity class as a method add_face whose input is a list of vertex handles, if you read through the code you can see how the connectivity is updated. As I mentioned I've tried to read through the code, but is quite hard for me to understand why some halfedges are updated in a certain way.


texts: machine learning- Hoeffding’s inequality and PAC Model

texts:
I have the following Question:
A speed-dating event consists of n women and n men. An event has many rounds: In a round, each woman meets one man for 5 minutes, and decides whether to go out on a real date with the man.
In the first round, 50% of the women agreed to a date, and in the second round, 40% of the women agreed to a date. The third round is about to begin.

Suppose we view all the women in the first round as Bernoulli random variables from distribution D1, with probability of agreeing p1.
We view all the women in the second round as Bernoulli random variables from distribution D2, with probability of agreeing p2. And we view the women in the third round as Bernoulli random variables from distribution D3, with probability of agreeing p3.

I need to find a minimum value of δ for which the following theorem holds:
Theorem: With probability 1- δ, p1≠p2.
This means that the probability of agreeing to a date depends on the round.

I'm very new to this topic so I would like to get some advice on how should I view this question,where do I begin,is there any theorem I should use in order to solve it?I suppose I should use Hoeffding’s inequality for this,but I find it hard to see the connection.
Any advice or help would be appreciated


texts: How can we reduce a vertex cover problem to shortest acyclic orienatation?

texts:
I want to show that shortest acyclic orientation(SAO) is NP complete.Since vertex cover in Np complete so if vertex cover is reduced to shortest acyclic orientation then it will also be NP complete.

SAO take input a graph G and integer k and answers if G has acyclic orientation with no directed k+1 path.


texts: How does a computer determine the data type of a byte?

texts:
For example, if the computer has 10111100 stored on one particular byte of RAM, how does the computer know to interpret this byte as an integer, ASCII character, or something else? Is type data stored in an adjacent byte? (I don't think this would be the case as this would result in using twice the amount of space for one byte.)

I suspect that perhaps a computer does not even know the type of data, that only the program using it knows. My guess is that because RAM is RAM and therefore not read sequentially, that a particular program just tells the CPU to fetch the info from a specific address and the program defines how to treat it. This would seem to fit with programming things such as the need for typecasting.

Am I on the right track?


texts: Is the language of all deciders recognizing empty language decidable?

texts:
I TA for a course in theory of computation and this came up as an interesting question.

$E_{TM}$ is the set of TM descriptions where the machine's language is empty.

Of course, $E_{TM}$ is undecidable for arbitrary TMs (as well as $A_{TM}$).

Now suppose we restrict our attention to decider TMs (ones that always halt).

$A_{decider}$ is the set of TM decider descriptions and strings such that the TM accepts that string, and $E_{decider}$ is the same as $E_{TM}$ except for deciders.

Of course, $A_{decider}$ now is decidable because we just simulate the decider on the input, and it will always stop.

Is $E_{decider}$ decidable now, or does it remain undecidable?
The reduction to show that $E_{TM}$ was undecidable originally goes in the wrong direction here.


texts: Find disjoint contiguous sub-arrays in better than $\mathcal O(n^2)$

texts:
Given an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.

The sub-arrays should not overlap and it can not be empty.

eg [2 -1 -2 1 -4 2 8]

ans (-1 -2 1 -4) (2 8)

diff = 16

Better than $\mathcal O(n^2)$ solution was expected.


texts:
I am working through creating a LALR(1) parser generator. I have the following grammar which I designed to highlight the epsilon for rule 3.

0. S' -> A
1. A -> a B b
2. B -> b
3. B ->

This recognizes ab and aab. It is my assumption that with one symbol of look-ahead, I would know whether to reduce using rule 3 or shift using rule 2. That is, when scanning ab, I need to reduce using rule 3 to get a B onto my stack. But when the input is abb I want to just shift the first b, then reduce it by rule 2.

As I work through creating a LALR(1) parsing table, I get the following:

 , $ , a , b , A , B
0,   , s2,   , g1,   ,
1, a ,   ,   ,   ,   ,
2,   ,   , s5,   , g3,
3,   ,   , s4,   ,   ,
4, r1,   ,   ,   ,   ,
5,   ,   , r2,   ,   ,

The issue is that there is an ambiguity on state [2, b]  A 'reduce by 3' was rejected. Of course, this is why I chose the grammar.

I calculated first and follow as:

**************
* First sets *
**************
A { a } epsilon=false
B { b } epsilon=true
S' { a } epsilon=false

***************
* Follow sets *
***************
S' { $ }
    A { $ }
B { b }

Anyway, I have implemented this as best I know how and the ambiguity remains. Am I doing something wrong? Am I expecting too much from LALR(1)?

EDIT - one possible place where I am confused could be when 'lookahead' occurs. If the lookahead symbol is only used to make a decision on whether a reduction should occur, then to be successful we require enough information after we shift the first a. Basically, if we see two b's coming, we can infer our only chance of success is to shift the first one and then reduce it to B. If there is only one B, we'll need to reduce the epsilon to get a B onto the stack.  Then we'll be set up to successfully reduce aBb. By this metric, this would be an LALR(2) grammar. Does this make sense (in the scope of LALR(k) parsers,) or am I just wrong?