texts:
I have to be able to perform insert, delete, range-value-sum, and range-2-max-values with a data structure.

Range-value-sum(xl,xr): with a range [xl,xr] (for a range query), it reports the sum of values of all elements whose keys are in the range of [xl,xr], where xl and xr are real numbers and xl ≤ xr

Range-2-max values reports the largest value and the second largest.

Approach: This is my take on it so far, to use a single balanced binary search tree that is sorted by its keys. The augmented fields  would be the value (of the key-value pair), subtree min and max keys, sum of the subtree, and the 1st and 2nd maximum of its subtree.
The sum and 1st and 2nd max are of the values, not keys since the values don't have to be ordered in this case.
For range-value-sum the recursion is to pretty much keep track of the 1st and 2nd max values that are within the range.
Finally, you return the top 2 in each recursive step, excluding unnecessary values.

Thoughts? Ways to make more specific? For the time analysis, I'm relying O(logn) due to it being a binary search tree and its height.


texts: How to identify when to use Genetic Algorithm/Programming

texts:
I have been reading/studying on genetic algorithm/programming, and have implemented Traveling salesman problem.

TSP is basically a permutation/combination problem, and I can understand how GA helps to narrow down to the solution.

As far as I see GA is helpful in finding solution to

similar permutation/combination problems and
problems like pattern recognition.

Where/What are the other problem areas where GA could be applied and How(just provide a simple explanation) and What/Where GA can not be applied?

One case where I think GA can not applied are where there is no patterns, like Coin-Toss-Guess-Heads-Or-Tails Program, where outcome is purely luck.

Note: I am not looking for practical uses like printing circuit board or NLP. I am looking for what problems GA solves? or How to recognize that GA will help solve a certain problem instead of writing a complex algorithm.

Like TSP is a permutation/combination problem where possible solution could end up in 2.4 billion or more, and finding the right answer would be nearly impossible, Hence GA(or other optimization algorithm like simulated annealing) is useful in finding an optimal solution.


texts: thread scheduling in multi core architecture

texts:
In multi core architecture, let us say we have M cores and N threads (N > M) and a process once assigned to a core can't migrate to another core's ready queue. We have to design scheduling policy to balance load.
I read about this area and found this -
1) Block multithreading, Interleaved multithreading and Simultaneous multithreading (https://en.wikipedia.org/wiki/Multithreading_(computer_architecture))
2) Round Robin, FIFO, preemptive scheduling
(https://en.wikipedia.org/wiki/Scheduling_(computing))
3) Threads inherit priority number from processes and go to relevant core
My question asks me to compute thread load before scheduling and then assign that thread to core which is less loaded. Is there any research work done in this area ? If not, is there any research work done which computes a thread's computational load at compile time ?


texts: Question on Recurrence $T^2(n) = T(n/2) * T(2n) - T(n) * T(n/2)$

texts:
Need help solving this recurrence:

$T^2(n) = T(n/2) * T(2n) - T(n) * T(n/2)$


texts: LP - given m constraints for 2 variables find maximal radius of circle

texts:
Given $m$ constraints for 2 variables $x_1,x_2$ :

$d_ix_1 + e_ix_2 \leq b_i$ for $i = 1,...m$

need to create a linear program that finds the maximal radius of a circle such that all the points inside the circle are in the feasible range of the above constraints.  The circle can be located anywhere -- not necessarily centered at the origin.

so I know the formula for distance between some $(x,y)$ and some $ax +by + c = 0$

then I have tried -

$Maximal$ $R$ s.t
$d_ix_1 + e_ix_2 \leq b_i$ for every $i$
$R \leq |d_ix_1 + e_ix_2 - b_i| / {\sqrt{{e_i}^2 +{d_i}^2}}$   for every $i$
$R \geq 0$

I know the standard linear program doesn't get absolute value function but obviously we can just have 2 inequalities to get rid of it.

I'm not sure if this is the correct answer.

furthermore, is it possible that for some constraints if will force the radius to be 0?


texts:
From http://web.mit.edu/6.031/www/fa19/classes/12-interfaces-enums/#implementing_generic_interfaces
"That means B is only a subtype of A if B’s specification is at least as strong as A’s specification. When we declare a class that implements an interface, the Java compiler enforces part of this requirement automatically: for example, it ensures that every method in A appears in B, with a compatible type signature. Class B cannot implement interface A without implementing all of the methods declared in A.
But the compiler cannot check that we haven’t weakened the specification in other ways: strengthening the precondition on some inputs to a method, weakening a postcondition, weakening a guarantee that the interface abstract type advertises to clients. If you declare a subtype in Java — implementing an interface is our current focus — then you must ensure that the subtype’s spec is at least as strong as the supertype’s."
However, later they define a generic class Set with method contains(E e) and a non-generic subclass CharSet with method contains(Character e). Does this count as strengthening pre-condition? If so, does it contradict the above?


texts: Comparison of Decision Trees: RTED vs MLE

texts:
I read two papers discussing how to compare between decision trees. One of them is RTED (that is specifically for trees and sub-case is decision trees) can be found here (RTED: A Robust Algorithm for the Tree Edit Distance)here:
and additional approach is COMBINING CLASSIFICATION TREES USING MLE by Shannon and Banks (Shannon, W. D., & Banks, D. (1999). Combining classification trees using MLE. Statistics in Medicine, 18(6), 727-740.). I would like to know if the MLE method is a sub case of RTED algorithm for comparison between decision trees?
"Comparison between decision trees" I mean, given 2 decision trees we would like to compare the structure of them. It means by the location and the name of each node. The RTED transfers the trees into a Bracket Tree Format that contains the names of the tree nodes and compares between the 2 strings. The output is a number that is the Tree distance value (also know in literature Edit Distance).
The question is if the algorithm described by Shannon and Banks (called MLE) is a specific case that is covered by RTED algorithm. If the final result of comparison between 2 decision trees will yield same result. If the answer is No, what are the cases in which the different algorithms will give different results?


texts: Zero-knowledge proof of $\beta\eta$ equality

texts:
Is there some way to give a zero-knowledge proof that two $\lambda$-terms are convertible, i.e. equal modulo $\beta\eta$?

A usual (and not zero-knowledge) proof that two terms are convertible is a path of terms between the two such that each step is either a single $\beta$ reduction or a single $\eta$ expansion, or the reverse of either one. Testing that two terms are convertible is only semi-decidable because no bound can be given a priori on the length of that path.

The question is the following: Alice has two $\lambda$-terms $t_1$ and $t_2$, and a proof that they are convertible. Can she convince Bob that they are convertible without helping Bob find the path?

One way to do this would be that Alice gives Bob a third term $t_3$ that she knows is convertible to the two others, and then Bob gets to ask her either to prove that it's convertible to $t_1$ or that it's convertible to $t_2$. I'm not sure how the term $t_3$ can be chosen though.


texts: Common name for inverse of beta reduction

texts:
For some transformation, I am currently working on, it is useful to "pull out" subexpressions and replacing them with variables.

i.e. $\textbf{transform}(42 + 3 * 4) = (\lambda x. 42 + x) (3*4)$

This has, of course, the same result (if it does not extract bound variables and is correct only modulo evaluation order, i.e. termination properties might change).

Such a basic operation probably has an established name, but I never heard it. Is it "beta-expansion"?


texts: Find a particular connected graph within a complete graph keeping all vertices

texts:
My problem is as follow, imagine a complete undirected graph with weighted edges, i would like to extract a connected graph keeping all the vertices and where the edge with the highest weight is the minimum one compared to all others possible configurations.

Is there another solution than bruteforce it.


texts: Generating all words of length $n$ avoiding $A^2$ and $B^3$

texts:
I need to find a way to iterate over all sequences of words in two letters $A,B$ avoiding the sequence $A^2 = AA$ and $B^3 = BBB$.  First of all, what is the regular expression for such a thing?

I need a way of iterating over all such possible words.  I tried this one:
$$ w \mapsto \{ wA, wB, wBB\} $$

however, if I run this function again, we obtain:
$$ w \mapsto \{ wAA,wAB,wABB,wBA,wBB,wBBB,\dots  \}$$
and you can see we have obtained the expressions we are trying to avoid.

I need way of generating all the words in $\{A,B\}$ of length $n$ avoiding these two patterns.


texts: Using finite state machines for lexical analysis

texts:
I'm a high school student and I'm passionate about everything language related - lexers, parsers, compilers, interpreters and so on. Some time ago I've written a calculator in Python (now willing to use a better language), which uses the Shunting yard algorithm and my own lexer.
So I want to start learning more about this topic and found this Compilers course. I pretty much understand how RegExp are used to specify the language but when the professor started talking about finite-state machines I just got lost in all the theory.
So this is my question: How do I use DFAs and NFAs for lexical analysis ?
What does "state" mean in this context ?


texts: If Halting problem is decidable, are all RE languages decidable?

texts:
Assume the halting problem was decidable.
Is then every recursively enumerable languagerecursive?


texts: Rigorous error bounds for eigenvalue solvers

texts:
I computed the first four eigenvalues of a quite large ($2^{24}\times 2^{24}$) but very sparse matrix. I used pythons in-build function sparse.linalg.eigsh to compute them.
I need a validation that the results are correct up to an error of at most $10^{-3}$.

Very specifically I want to ask if there is a rigorous error-analysis involving rounding errors up to machine precision in each step.

More generally: Are there other practical algorithms for eigenvalues with such a rigorous error analysis.


texts: Finding an Algorithm for the HAPPY-CAT problem

texts:
I'm trying to develop an the algorithm for the problem:
The cat-and-mouse game is played by two players, “Cat” and “Mouse,” on an arbitrary undirected graph. At a given point, each player occupies a node of the graph. The players take turns moving to a node adjacent to the one that they currently occupy. A special node of the graph is called “Hole.” Cat wins if the two players ever occupy the same node. Mouse wins if it reaches the Hole before the preceding happens. The game is a draw if a situation repeats (i.e., the two players simultaneously occupy positions that they simultaneously occupied previously, and it is the same player’s turn to move).
In other words, we have to decide: HAPPY-CAT = {<G, c, m, h> | G, c, m, h are respectively a graph, and positions of the Cat, Mouse, and Hole, such that Cat has a winning strategy if Cat moves first}.
I came across this algorithm:

Mark all nodes (a, a, x) where a is a node in G, and x is turn {cat, mouse} for whoever goes next.
If for a node u = (a, b, cat), there is a node v = (c, b, mouse) which is marked and (u, v) is an edge then mark u.
If for a node u = (a, b, mouse), all nodes v = (a, c, cat) are marked and (u, v) is an edge then mark u.
Repeat steps 2 and 3 until no new nodes are marked.
Accept if start node s = (c, m, cat) is marked.

But I'm having difficulty envisioning the first step. For example, in the picture below (where cat starts at 1, mouse starts at 5, and the hole is at 10), cat wins at vertex 4 in two ways:

c -> 12, m -> 4, c -> 6, m -> 2, c -> 4, m -> 4
c -> 12, m -> 4, c -> 3, m -> 2, c -> 12, m -> 4, c -> 4

So then at step 1 of the algorithm, would node 4 in our new marked set contain (4, 4, cat) or (4, 4, mouse)?


texts: Find no of acyclic paths of any length in a directed graph from a single source given that every node has at most 4 in/out degree

texts:
let A,B,C be nodes of directed graph with edges A->B,B->A,A->C,C->A,B->C,C->B then no of paths will be 5 that is A,A->B,A->C,A->B->C,A->C->B

If i apply dfs and increase counter for every node i visit, it wont find all paths for example if it finds A,A->B,A->B->C then after backtrack it wont traverse A->C and further A->C->B because C and B are marked as visited.

So i modified the dfs where i unmarked the visited node when algorithm backtracks to its parent.

Procedure dfs(arr,s,vis):  #s is source node
  vis[s]=True              #mark as visited
  count+=1                 #no of paths
  for all i adjacent to s:
    if not vis[i]:
        dfs(arr,i,vis)
  vis[s]=False             #mark visited as false again(modification)

After modification, algorithm gives correct result but the time complexity goes exponential.

Is there any optimized way to do it? Note that i am developing a game and in my specific scenario

In-degree/Out-degree of any node is at most 4
In-degree/Out-degree of source node is at most 2

Any idea?


texts: L contains the concatenations of all k-bit long strings. Why is it decided in PSPACE(loglogn)?

texts:
(This exercise is from Computation Complexity: A Conceptual Perspective by Oded Goldreich):

For any k $\in \mathbb{N}$, let $w_k$ denote the concatenation of all k-bit long strings (in lexicographic order) separated by *'s (i.e, $w_k = 0^{k-2}00*0^{k-2}01*0^{k-2}10*...*1^k$). Show that the set $S = \{w_k:k\in\mathbb{N}\} \subset \{0,1,*\}$ is decidable in double-logarithmic space.

The basic idea of the solution, if my understanding of it is correct, is:

iterate from i to k until the structure of the input suits some $w_k$, for example $\{0,1\}^k*\{0,1\}^k*...*\{0,1\}^k$.
For each pair of adjacent binary numbers, make sure $b_{i+1} = b_i + 1$

According to the guideline in the book, step 2 takes space $O(log(k))$.

Why do I need $log(k)$ space to check if $b_{i+1} = b_i + 1$? Can't it be done in constant space?


texts: Perturbing a Markov chain to be closer to a target stationary distribution

texts:
Suppose we are a given a Markov chain $A_0 \in \mathbb{R}^{n \times n}$ and a desired stationary probability vector $\pi_0 \in \mathbb{R}^n$. I would like to find a Markov chain that is as close as possible to $A_0$ and whose stationary probability is as close as possible to $\pi_0$. For example, I would like to solve

$$ \min_{{\rm stochastic}~ A} ||A-A_0||_F + ||\pi(A)-\pi_0||_2$$

Is this doable in polynomial time? For example, for any fixed $\epsilon > 0$, can I find something $\epsilon$-close to the optimal solution in time polynomial in $n$? If not, what sort of approximation guarantees can we obtain for this?

I am pretty flexible on the problem statement; ultimately, the solution will be validated based on performance on a particular application. So if the problem is solvable by replacing the $2$- and Frobenius norms with something else, or via formalizing the problem in some other way, that would also be perfect.


texts: Lamport logical clock: why event occurs in a process with smaller pid is treated earlier?

texts:
In lamport's paper1, he define global local timestamp, which is composed of process id and local lamport timestamp.

This timestamp is used to order all the events in a distributed system.

The rule to compare two events is following.

My Question

Imagine we have two events, one happens in process 1 (P1), with local timestamp 9, another event happens in process 2 (P1), with identical timestamp 9.

Based on lamport's rule, the first one is earlier than second one.

C1(9) => c2(9)

But why?

From my understanding, it does't make sense. An event is treated earlier just because it is born in a process which has smaller pid?

Reference

Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System.”


texts: Is this algorithm bubble sort or selection sort?

texts:
#include <iostream>

int main() {
    int arr[10]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    for (int i = 0; i < 10; i++) {
        for (int j = 0;  j < 9; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
    // now the array is sorted!

    return 0;
}

I've just studied bubble sort and tried to implement that in c++ as the code above.

I've taught my friend the algorithm, but he implemented it as the following code, which worked and sorted the array, but I don't know what the name of algorithm he used. Here is a sample of what he used:

#include <iostream>

int main() {
    int arr[10]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    for (int i = 0; i < 10; i++) {
        for (int j = i + 1;  j < 10; j++) {
            if (arr[i] > arr[j]) {
                std::swap(arr[i], arr[j]);
            }
        }
    }
    // now the array is sorted!
    return 0;
}

Is this selection sort?


texts: Algorithm to merge two incomplete lists of symbols (strings) into a complete one

texts:
I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution.

Let's say we have two ordered lists of symbols (strings):

A = "foobarquuz123"
B = "foobar456quuz"

my goal is to have a way to merge the two incomplete lists into the following, completed with parts from both:

C = "foobar456quuz123"

As you can see there is no intrinsic "sorting value" associated to the symbols, only their position, which is just a relative measure. Moreover, the symbols might be also repeated in arbitrary points of the strings.

Maybe the algorithm I am looking for might have been used in bioinformatics, for example for DNA or protein sequence alignment, but I am no expert of this.

What would you recommend? Do you have some pointers to algorithms that may solve this problem? I think that someone should already have figured out a solution with upper-bound computational complexity $O(k(n+m))$ where $k$ is a constant and $n$ and $m$ are the lengths of the strings.

I would be very happy to get also suggestions for books that illustrate this and similar problems.


texts: How to find vertices of bounded region made by intersection of lines

texts:
Suppose we have random lines made with 2 points. and point has (x,y)
For example:

Now when we draw a random line you will see many lines intersect with each other. This eventually gives rise to bounded regions. How to find the vertex points for each bounded region?
My approach:
First we find all the intersection points of the various lines. In some cases multiple lines intersect at the same point.
However I am not sure how to pick the points that make up a bounded region.
Thanks in Advance.


texts:
The original question is the following

  prove that $2·\sum_{i=0}^{n-1} 3^{i} = 3^n-1$ for all n $\geq$ 1

I know that I have to prove by induction and have successfully done the base case, my IH is the following:

Assume $2·\sum_{i=0}^{n-1} 3^{i} = 3^n-1$ holds for all n $\geq$ 1 to prove $2·\sum_{i=0}^{n} 3^{i} = 3^{n+1}-1$

then I did this:
$2·\sum_{i=0}^{n} 3^{i} = 2·\sum_{i=0}^{n-1} 3^{i} +3^n$

then by my IH: $2·\sum_{i=0}^{n-1} 3^{i} +3^n = 3^n-1+3^n $

after this I struggle to continue, I know I have to find a way to rewrite it to $3^{n+1}-1$ and I know this is equal to $3·3^n-1$ but I don't see how to get from the one to the other. Anyone who can help?

edit: I mistook a 2 for a 3, can anyone help now?


texts: Efficient algorithm for getting from 1 to n with 3 specific operations

texts:
The question:

  Given those 3 valid operations over numbers and an integer $n$:

  add $1$ to the number
  multiply the number by $2$
  multiply the number by $3$

  describe an efficient algorithm for the minimal number of operations of getting from $1$ to $n$ with the 3 operations mentioned above.

  For example for $n=28$ the answer is $4$ : $1\times 3\times 3\times 3+1=27+1=28$.

My approach:

I noticed that there is a recursive algorithm that will provide the answer but even when I used memoization the algorithm took a lot of time to end with $n\geq 1000$. I thought of a way to start with $n$ instead and try to reduce it to $1$ with the inverse operations of subtracting $1$ dividing by $2$ or by $3$ and trying to get it to be devisible by $3$ or by $2$ by subtracting $1$'s and checking the mod. But my second approach had some (more than some) mistakes where It stated that the smallest number of operations is more than it is. Please help or give a hint I clearly missing some kay fact about the nature of such operations.

Edit:

def ToN(n):

d=dict()
def to(x,num,di):
    if (num==x):
        return 0
    elif (num>x):
        return num
    elif num in di:
        return di[num]
    else:
        if num+1 not in di:
            di[num+1]=to(x,num+1,di)
        if num*2 not in di:
            di[num*2]=to(x,num*2,di)
        if num*3 not in di:
            di[num*3]=to(x,num*3,di)
        di[num]=min(di[num+1],di[num*2],di[num*3])+1
        return di[num]
return to(n,1,d)

I wrote the code above in python and it takes a lot of time to end for num=1000. Can you help me understand what is wrong w.r.t. efficiency.


texts:
I just wonder where the ROB is in.
Is ROB in the memory or cache or where??


texts: How to merge tesselating regions into larger ones?

texts:
I have a map, which is broken into adjacent regions. Regions do not overlap. Regions are of complex shapes (they are administrative districts).

I want to display these regions on Google Map. But the problem is that the regions are of very different sizes. If zoom level fits largest regions into map frame, then there are numerous small regions, which overload the widget, but doesn't actual visible by user.

I would like to merge smaller regions into bigger ones by some reasonable algorithm.

Can you hint me onto some keywords?

Here is my proposed algorithm for now:

At each scale I am taking a grid. The grid is the same as grid of tiles google map uses, i.e. tile is 256 pixles wide, zoom level 0 means entire world in one tile.

For each region I am calculating a tile, to which center (center of tile) region's centroid ("center" of region) is closest.

If zoom is too small, small regions turn to belong to same tiles and
these are regions I merge. On picture occasionally there are no regions to merge because they are all assigned to different tiles.


texts: Does a problem stay NP-hard when an additional constraint is added to it?

texts:
I have the following problem $(P)'$:

\begin{align*}
 {\rm max}_{x_1,...,x_K}\quad & \sum_{k=1}^Kf(a_k,x_k) \cr & & (P)'\cr {\rm subject\ to}\quad & 0 \le x_k \le A, k=1,\ldots,K.
\end{align*}

This problem is proven NP-hard. An instance of $(P)'$ is given by $(K,a_i,A)$.

I have another problem $(P)$:

\begin{align*}
 {\rm max}_{y_1,...,y_N}\quad & \sum_{n=1}^Nf(b_n, y_n) \cr & & (P)\cr {\rm subject\ to}\quad & 0 \le\sum_{n=1}^Ky_n \le B, \cr \quad & y_n\geq 0, n=1,\ldots,N.
\end{align*}
And an instance of $(P)$ is given by $(N,b_i,B)$.

Can I say that problem $(P)$ is NP-hard?


texts: Relational Algebra: existential quantifiers

texts:
So i have the following question and template answer:
Question: List the names of managers who have at least one dependant.
Answer: {e.Fname, e.Lname | EMPLOYEE(e) AND (∃d)(∃t)(DEPARTMENT(d) AND DEPENDANT(t) AND e.Ssn = d.Mgrssn AND t.Essn = e.Ssn) }
My answer was exactly the same except that instead of the (∃d)(∃t)(...) section I said (∃d)(DEPARTMENT(d) AND e.Ssn = d.Mgrssn) AND (∃t)(DEPENDANT(t) AND t.Essn = e.Ssn).
My question is basically are these equivalent?


texts: 3-partition problem: why $b/4 < x_i < b/2$?

texts:
Why does the definition of the 3-partition problem contain the condition
$$\frac{B}{4}<x_i<\frac{B}{2}?$$

I don't understand why leaving out this condition changes the 3-partition problem.


texts: SMT solves with functions for free varibles

texts:
So this sounds like this might lead to an undecidable theory but I thought I would give it a try and ask about it after I found nothing on the subject. I am somewhat interested in finding functions which are counter examples to predicates (or solutions to the inverse rather). I would like to restrict the functions to some small class however (possibly even smaller than primitive recursive) so I think there is hope of this working if I restrict them enough.

Has any work been done in this area? Have any tools been written for such things?


texts: How can I show mathematically the time complexity of this function is O(N)?

texts:
int foo(N){
   if(N <= 1){
       return 0
   }else{
       return 1 + foo(N-1)
   }
}

I can tell that the time complexity of this program is O(N) but I am unsure on how to prove it mathematically? If I can get some hints I'd grealy appreciate it.


texts:
How can we show $P/poly^{P/poly}=P/poly$?

What tricks are generally used for self lowness of a class such as $BPP$, $SPP$ etc?


texts:
Are there any "natural problems" which are known to be NPI under weak assumptions.
By weak assumptions I mean something like $P \neq NP$ or $NP \neq Co-NP$


texts: Prove vertices of polygon are endpoints of disjoint line segments

texts: If we are given a set of disjoint line segments in the plane, can we prove (or disprove) that we can always join the line segments to make a simple polygon where the vertices of the polygon are the endpoints of the segments and every segment is an edge on the boundary of the polygon.


texts: Is $L = \{a^jb^ia^{j-i}\mid i,j \ge 0\ , j > i\}$ context-free?

texts:
I'm exercising for an upcoming exam and I find this exercise:

  Say whether or not the language
  $$L = \{a^jb^ia^{j-i}\mid i,j \ge 0\ , j > i\}$$
  is a context-free language. Justify your answer.

I have already tried (using the pumping lemma for CFL) with two different words:
$$w1 = \  a^pb^{p-1}a$$
$$w2 = \  a^{2p}b^pa^p$$

but I'm stuck when the case is that $vwx$ (considering $uvwxy = w$) take letters from both the first group of $\bf{a}$ and the group of $\bf{b}$.
Have I chosen a wrong format for the word or am I simple missing some trivial condition?


texts: Finding a kernel for d-Bounded degree deletion

texts:
In $d$ Bounded degree deletion problem, we are given an undirected graph $G$ and a positive integer $k$, and the task is to find at most $k$ such vertices whose removal decreases the the maximum vertex degree of the graph to at most $d$.
The question is to how to find a polynomial kernel (in $k$ and $d$) for this problem.
I seem to be able to get the only reduction rule that if any vertex has degree $ > k+d$, it has to be there in the deletion set (if the answer to instance is yes). Because if it isn't, then at least $k+1$ of its neighbors have to be in deletion set. I can't seem to move beyond this point.
The exercise is from this book (exercise $2.9$).
I am also aware that we can remove edges between vertices with degree $< d$, and find solution in the modified graph (hint from the book). But I am not sure how it will be useful, in getting a bound over number of vertices/edges in $k$ and $d$.
I would appreciate only hints if possible (something maybe beyond the book hints).
PS: for $d=0$ this reduces to vertex cover problem.


texts:
Suddenly a thought came to my mind and I thought of resolving it as follows.
We know that:
String is a finite sequence of symbols from an alphabet $\Sigma$

i.e. we cannot have an infinite sequence representing a string, which means there is no definition such as
$w = "abcabe...........$

which is unending

Now when we consider the definition of ${\Sigma}^*$, we see that the set is infinite, which implies that there could be strings having infinitely large length => which seems to sort of contradict the basic defintion of strings at a first glance.

But if we look into the matter closely then we shall see that for whatever value of length of the strings ($n$) we choose, we get a string of finite length, no matter however large $n$ is .

Is the way in which I resolved it correct or a more refined method of resolution exists?


texts: Generalized sorting algorithm on partially ordered set generated by a relation

texts:
Assume we have a finite set $X$ of elements and any relation $\preceq$ on $X$. Such a relation may or may not generate a reflexive transitive anti-symmetric relation $\leq$ on $X$ (a partial order). Recall:

reflexive: We always have $x\leq x$.

transitive: If $x\leq y$ and $y\leq z$ then also $x\leq z$.

anti-symmetric: If $x\leq y$ and $y\leq x$ then $x=y$.

I'm looking for an efficient algorithm that decides whether $\preceq$ extends to a partial order and if yes, returns one or one with uniform probability or all possible orderings of $X$ which respect the partial order.

This naturally decomposes into two subtasks (not claiming that the best algorithm decomposes this way):

Decision whether $\preceq$ extends to $\leq$ or, in other words, extending by transitivity does not violate anti-symmetry. If it does, describing the partial order $\leq$.
Finding the possible orderings.

The second points is related this question.


texts: Graph partitioning with parts of equal size

texts:
Partition an undirected graph of $n$ nodes into $k$ subgraphs so that total vertices inside all subgraphs is maximum.
Restriction: all subgraphs have the same number of nodes (so $k$ divides $n$); $k$ is given initially.

I'd like to receive pointers to the solution as well as papers or blogs related to or expanding on it.


texts:
The algorithm for the union of two sets represented by treaps is defined in this paper and on Wikipedia, but the algorithm seems flawed.

Take for example the following loop.

X := {a}
for (i := 0; i < 1000; i := i + 1)
  X := X ∪ {a}

At the end of execution, the variable $X$ contains the set $\{a\}$, but the priority of the element $a$ is elevated and not random because the union algorithm always picks the element with the highest priority.

Am I missing something?


texts: Implications of Babai's Proof that Graph Isomorphism is Quasi Polynomial Time

texts:
In the context of the very recent talk by Lazlo Babai outlining that Graph Isomorphism (GI) is Quasi Polynomial Time, what are the broader implications of this result?  (I'm assuming the claim will stand peer review)

http://people.cs.uchicago.edu/~laci/quasipoly.html

https://twitter.com/gabegaster

Apart from the inherent satisfaction of having solved a difficult open problem, what are the broader implications for Theoretical Computer Science from this result, if any? Specifically, should it impact our beliefs / strategy about P?=NP?

PS. Too bad GI was not NP-complete eh?


texts: I have an image, like the one below that has different paths. I want to be able to detect the thin parts of these paths and highlight them. What is the best way to go about this?


texts: Modifying the Erroneous Pairwise Distances of 4 Points to Get Coplanarity

texts:
Consider four points
$i,j,k,l$
and their pairwise Euclidiean distances
$d(ij)$
$d(ik)$
$d(il)$
$d(jk)$
$d(jl)$
$d(kl)$

Say that, we know the coordinates of the points $j$, $k$ and $l$.
However, we do not know where $i$ is and the measured distances to $i$ are erroneous depending on an error rate $e\%$.

That means, given the distance $d(ij)$, the actual distance is between $d(ij)*(1-e)$ and $d(ij)*(1+e)$.

Given the fact that those 4 points are coplanar, which means Cayley-Menger determinant (CMD) of the distances is zero, I seek an efficient way to find the values for $d(ij)$, $d(ik)$, $d(il)$.

So far, I have thought about dividing the distance interval into $k$ and trying all the possible combinations, which gives me $O(k^3)$ complexity.

for(ij=ijMin; ij<=ijMax; ij+=(ijMax-ijMin)/10)
    for(ik=ikMin; ik<=ikMax; ik+=(ikMax-ikMin)/10)
        for(il=ilMin; il<=ilMax; il+=(ilMax-ilMin)/10)
            if(CMD(ij, ik, il, jk, jl, kl) == 0)
                return {ij, ik, il};

However, this method is
i) Inefficient brute-force and
ii) Does not guarantee to return a solution.

If you propose an algorithm that is efficient is OK for me. I do not seek for an exact solution. But also I do not want to spend $O(k^3)$ time.


texts: Strict Positivity of Indexed Datatype in Agda

texts:
Agda is ruling out definitions like

data Bad : Set where
 bad : (Bad → Bad) → Bad

Because "Non strictly-positive declarations are rejected because one can write a non-terminating function using them." (as one may read in Agda wiki). I know also that disabling strict positivity checking allows constructing inhabitant of empty type.

But Agda also complains about definition like this:

  data Bad? : ℕ → Set where
    badZ : Bad? zero
    badS : ∀ {n} → (Bad? n → Bad? n) → Bad? (suc n)

telling me that:

Bad? is not strictly positive, because it occurs
to the left of an arrow
in the type of the constructor badS
in the definition of Bad?.

What i know is that i can create valid definition without inductive datatypes:

  Bad?′ : ℕ → Set
  Bad?′ zero = Unit
  Bad?′ (suc n) = (Bad?′ n) → (Bad?′ n)

  badZ′ : Bad?′ zero
  badZ′ = tt

  badS′ : ∀ {n} → (Bad?′ n → Bad?′ n) → Bad?′ (suc n)
  badS′ x = x

My question is:

Can "Bad?" datatype lead to similar inconsistencies, and this is the reason why it is rejected by Agda?

Or is it the case that positivity checking in Agda is too "cautious", and can't figure out that indexing is making it strict positive?


texts: Bipartite Problem is Log-Space Reducible To $s$-$t$ Undirected Connectivity

texts:
Prove that the problem of determining if graph is bipartite is computationally equivalent under log-space reductions to $s$-$t$ undirected connectivity.

Problem of $s$-$t$ undirected connectivity is the following given an undirected graph $G = (V, E)$ and two designated vertices, $s$ and $t$, determine whether there is a path from $s$ to $t$ in $G$.

I assume the idea is to consider mapping from graph $G$ to bipartite graph $G'$, there should be a correspondence between edges of $G$ and edges of bipartite graph $G'$, and between edges of $G$ and the edges that violates the bipartite property of graph $G'$. The problem is I cannot come up with such correspondence.

I would appreciate any idea.


texts: How to find max flow in a graph after decrementing an edge capacity?

texts:
We're given a graph $G=(V, E)$, with source $s$ and sink $t$, $s\neq t$, and that all capacities are non-negative integers. Also the max flow itself is given, so we receive the value of max flow for each edge.  We're also given some edge $e'$.

How can the max flow be found if we decrement the capacity value of an edge $e'$ by $1$ in linear time?


texts: LazyHeap data structure with $O(n)$ Insert, Delete, and Return operations

texts:
Consider a data structure called LazyHeap that supports the following operations:

INSERT(x): Given an element $x$, insert it into the data structure. It has no cost.
DELETE(x): Delete $x$ from the data structure. It has no cost.
RETURN: Return an element $x$ such that its order, if the elements are sorted, satisfies:

$$k/2 - k/100 \le \mathrm{order}(x) \le k/2 + k/100\,,$$

where $k$ is the number of elements in the data structure (at the time RETURN is called). RETURN also has no cost.

Come up with a strategy for the comparisons so that the running time for any sequence of $n$ operations is less than $1000n$.

I know that sometimes you have to make comparisons between two elements so that you can perform RETURN operation correctly, where one comparison costs one unit. However, I'm not sure where to go from there. Any help would be appreciated!


texts: Induction on typing derivation in refinement types system

texts:
From the text Principles of Type Refinement page 14:

The author introduces in definition 2.2.7 the rule:

$$ \dfrac{\Pi \vdash t : R \qquad R \le S}{\Pi \vdash t : S} $$

and gives the following contravariant form:

$$ \dfrac{\Omega \le \Pi \qquad \Pi: t : R}{\Omega \vdash t:R} $$

where $\Omega,\Pi \sqsubset \Gamma$ and $\Omega \le \Pi$ is interpreted as if the type assigned to each variable in $\Omega$ is a subtype of the type assigned to the same varaible in $\Pi$.

The author then states that this rule is admissible in the refined simply typed lambda calculus and that this can by shown by induction on typing derivations.

I'm used to natural and structural induction. But what does it mean to perform induction on typing derivations? Can you given an example?


texts: How to use Sigma Scaling in a genetic algorithm

texts:
I have a genetic algorithm in Java and I'm testing new types of selections.

For my tests I'm using the De Jong Half Sphere, my fitness function is $x^2 + y^2$.

The selection method used is Sigma scaling :

fscaled = S + (fraw −fmean)/2σ

Example using S=1

 - a) Fitness = 5.927822124 |  After Scaling = 0.900756351532265  | 17.74410992 %
 - b) Fitness = 3.431749363 |  After Scaling = 0.5720553077878213 | 10.27246375 %
 - c) Fitness = 8.428103101 |  After Scaling = 1.2300115637030606 | 25.22835279 %
 - d) Fitness = 2.548825744 |  After Scaling = 0.455785494144756  | 7.629554871 %
 - e) Fitness = 13.07076638 |  After Scaling = 1.841391282832097  | 39.12551868 %

I know that sigma scaling should be used with a proportional selection.

Is this the right way to implement this type of selection?
If I wanted to minimize the function instead of maximize it how can I accomplish it, should I subtract the mean to each fitness and get the percentage this way or is there a better way?


texts:
I working through some textbook exercises, and came across a problem that I'm struggling with.
Give a CFL $L$ such that $\{x|\forall y \in \Sigma^* \space xy \in L\}$ is not a CFL.
I've got the idea that we can let $L$ be formed by taking a language that is not CFL, and following each element by every string, and also add in the prefixes of elements of the non CFL language. But I'm not sure how to find a language such as this that is a CFL.
However, I'm struggling to think of an example with such a property.
Any help would be appreciated.


texts: Non-Approximate Dynamic All-Pairs Shortest Path algorithm for Undirected, Unweighted Graphs?

texts:
I am looking for an algorithm involving adding unweighted edges to an empty, undirected graph (with vertices) and then for each, updating the table of shortest paths.

An example is if we have vertices 1 to 5. We can see that initially, all of the paths are infinite except for the diagonal entries, i.e.:

  1 2 3 4 5
1 0 i i i i
2 i 0 i i i
3 i i 0 i i
4 i i i 0 i
5 i i i i 0

where i means "infinite". But if we add an edge (1, 2) then the 1-2nd and 2-1st entries of the table are updated:

  1 2 3 4 5
1 0 1 i i i
2 1 0 i i i
3 i i 0 i i
4 i i i 0 i
5 i i i i 0

Now, if we add the edge (2, 3), then obviously the 2-3rd and 3-2nd entires are updated, but also are 1-3rd and 3-1st (which has length 2, since the path is 1->2->3 and 3->2->1):

  1 2 3 4 5
1 0 1 2 i i
2 1 0 1 i i
3 2 1 0 i i
4 i i i 0 i
5 i i i i 0

Now, the more edges and vertices we add, the more complex the problem becomes, since we need to update other entries in the matrix if they are connected. The one fact that I know about this kind of graph is that it is symmetric along the diagonal.

I've been looking at this problem for a few hours and I do not think there is a generic algorithm that will solve the problem for a general unweighted, undirected graph. Are there resources on the problem?


texts:
This is a practice question I have, but I can't wrap my head around it.
.............
Let L = {M | M is a TM that halts with exactly two words on its tape in the form Bw1Bw2B}.
B = Blank Position

the problem of deciding whether an arbitrary Turing machine will accept an arbitrary input, is undecidable. Use this result to prove, formally using problem reduction, that given an arbitrary Turing machine M, the problem of deciding if M ∈ L is undecidable.
............
I have no knowledge of proofs. I don't have a clue how to tackle this question, can someone point me to a tutorial that works with proofs by reduction along with Turing machines.


texts: Is the union of infinitely many regular languages always regular?

texts:
Prove or disprove or this statement:

The union of an infinite number of regular languages is regular.

Can someone help?


texts: Modeling $(x > 0 \wedge y > 0) \Leftrightarrow z > 0$ in a linear program: impossible?

texts:
In this question, we see how to model boolean logic in $0 - 1$ ILPs. Moving to a relaxation, modelling $(x > 0 \vee y > 0) \Leftrightarrow z > 0$ with $x,y,z \in [0,1]$ with linear constraints is quite simple:

$$z \geq x\\
z \geq y\\
x+y \geq z$$

However, if I want to replace $\vee$ with $\wedge$ in that statement, I'm unable to do this. Can this be done? It seems to me this might imply something about quadratic problems in general, but I'm not familiar with that problem, and I can't prove that it can't be done either. Assuming we could linearize this $\wedge$ relation, would this imply something like polynomial-time equivalence between LP and QP?

Thinking about it geometrically, the set $\{(x,y,z) \in [0,1]^3: (x > 0 \wedge y > 0) \Leftrightarrow z > 0\}$ is equivalent to the unit cube $[0,1]^3$ minus the three faces that intersect the origin, but plus the two edges that emanate from the origin that satisfy $z=0$. This is neither an open nor a closed set. I don't know whether that tells us anything about the applicability of linear programming, but considering I've never come across a linear program with strict inequalities, I suspect it might be a problem.

In fact, strict inequalities can't be allowed in linear programs since

$$\min x\\
x>0$$

has no solution.

@KlausDraeger pointed out that the above constraints and the logical statement with $\vee$ aren't equivalent, and for reasons similar to those that apply to the case with $\wedge$, I suspect we can't find equivalent constraints. The subset of $[0,1]^3$ defined by $(x > 0 \vee y > 0) \Leftrightarrow z > 0$ is also neither open nor closed. I overlooked this because for the purposes I had in mind, it seemed to suffice that the linear constraints implied the truth of the logical statement - which isn't the case, I need equivalence between the set of linear constraints and the logical statement.

(Just in case someone is interested, there is a simpler constraint that also implies the truth of $(x > 0 \vee y > 0) \Leftrightarrow z > 0$, and that's $0.5(x+y) = z$; I could not find a set of constraints equivalent to the logical statement, though.)


texts: How to correct distortion from stitching dual camera to estimate homography

texts:
I am trying to distort the image obtained from two cameras that generate a stitching image. Unfortunately, I do not have access to the cameras and I would like to know what could be the best way to apply to correct the image and get the lines below to be straight.

The next step I am trying to do is to calculate the homography with respect to the field. And the only thing that I find is that: transformation between the image field and the template field plane has to be done through a linear transformation.


texts: Formalisms in concurrent and/or distributed programming?

texts:
My background came from imperative languages, primarily C, C++, and Python. I picked up Scala, Erlang, and a bit of Haskell a few years later and have since become very interested in functional programming and the formalisms behind it.

I am also interested in concurrent and distributed programming and have been looking into formalisms behind that, especially those that have seen at least a tiny bit of the "light of day" (e.g. real world use, or at least an implementation somewhere). So far I know of Communicating Sequential Processes, the Actor model, Algebra of Communicating Processes, and the Calculus of Communicating Systems. Among these I know the Actor model has realized itself in languages like Erlang, Scala, and Haskell.

I am wondering if there are foundations I should learn and practice before tackling these fields, if there is a "classic" one that I should study first, and if there are any other popular ones that I may have missed?


texts:
I'm looking for an actual definition of a stream processing unit (SPU), preferably sourced. The context is not specifically graphics cards.

I can find many, many articles explaining what they contain, or what they do in specific cases, but I need a definition for an informal class presentation. I have a general sense of what they are, but can't find much literature to back that up. However, even an informal definition would help.

Would really appreciate any input.


texts: Why is encrypting with the same one-time-pad not good?

texts:
To encrypt a message $m_1$ with a one-time-pad key $k$ you do
$Enc(m_1,k) = m_1 \oplus k$.

If you use the same $k$ to encrypt a different message $m_2$ you get
$Enc(m_2,k) = m_2 \oplus k$, and if you perform Xor of the two ciphertext you get
$$( m_1 \oplus k) \oplus ( m_2 \oplus k) = m_1 \oplus m_2$$

so, OK, there is some information leakage becuse you learn $m_1 \oplus m_2$, but why is it not secure? I have no way to learn (say) $m_1$ unless I know $m_2$. So why is it wrong to use $k$ twice??


texts: What mathmatical model shall be used for describing P2P processes interaction?

texts:
I am creating a distributed service system. It runs in the cloud on heterogeneous hardware. I am using C# .NET for business logic and C++ for different physics\chemical calculations. Having three logic applications and 2xN heavy calculation applications. There are external web clients, which connect to logic applications, but for now, we do not care for them. Therefore, server side connected applications:

They interact via heavily extended proprietary ZeroMQ analog middleware - so there is a finite set of communication patterns between applications.
There is a protocol (Protobuf based) via which applications encode messages. Different types of messages are sent on same communication channels (for example 10 types of requests with 10 types of responses for each Request-Reply channel)

I wonder if there is a mathematical model in terms of which I can describe my Peer to peer services system. Of course, I need a model that can be useful: one that after its creation I would be capable to gain some new knowledge about properties of my distributed application.

I looked at a few

Petri networks and they can provide reachability, liveness
Queueing theory, which generally seems to lead to Stochastic Petri Nets

After few days of research, my small brain collapsed because I need a Colored Hierarchical Stochastic Petri Net and all I would get from it would be reachability and liveness of components and connections may be also maximal/normal messages passing volumes.

To create such model timing, message type’s interaction and publishing stats would be required as well as directions of message streams. Computational logic can stay as a black box.

So I wonder - is there any other mathematical model which could provide more data on system behavior in terms of prediction/reasoning, what data it would require?


texts: Are intersection and union redundant? Possibility to get smaller output without negation?

texts:
I've just started learning relational algebra, so I'm reading a lot of articles for this topic. Not so long ago I've encountered two statements that seem to be quite weird to me.

∩ and ∪ (intersection and union) are in fact redundant in relational algebra and you can rewrite any expression without them.

You can't get a smaller result without using negation. So expressions without it are always monotone

There were no explanation for those, so I'm not sure if those are true. Could you give some examples?


texts: Given max-flow determine if edge is in a min-cut

texts:
We were given an exam question of: Given a flow network G=(V,E) with integer edge capacities, a max-flow f in G, and a specific edge e in E, design a linear time algorithm that determines whether or not e belongs to a min-cut.

From the grading rubric we are told a correct algorithm - I got dinged for not having the correct algorithm according to the rubric. I have flushed out my algorithm and can’t see why it is wrong. There are similar posts, but they all solve problem by running max-flow after adjusting e downwards, which is at best a polynomial algorithm O(mn) Orlin+KTR, and at worst pseudo-polynomial O(Cm) Ford-Fulkerson.

Here is rough description:

Since have max flow, create residual graph Gf. O(m)
Find the first min-cut by the normal method of BFS search for all nodes reachable by S in Gf. Check if edge e is in this cut. If it is in min-cut we are done.
Since it was not in the min-cut, look for the next min-cut if there is one. Do this by modifying Gf by removing the nodes in the min-cut set and adding a forward edge from a new S to the nodes on the other side of the min-cut. That way the edges from the new S to the existing nodes on the other side of the min-cut will not be part of any min-cut.
We then repeat 2 using this new graph which will find the next min cut.
We stop when we can get to t, which at this point if edge not found then it is not in min-cut

Since we traverse the tree only once this is generally O(m), although in the modifications to Gf we may have to traverse a node twice (think a straight line graph with every edge being a minimum cut) so it is worst case O(m + 2m) -> O(m)

Update:

After researching more (Does Ford-Fulkerson always produce the left-most min-cut), refining my claim that the above algorithm will find every edge e that is part of a min-cut (not every minimum cut which is exponential).

Looking at my example below, you will see that there are 4x4x4x4 = 256 minimum cuts in the graph, but only 4+4+4+4 = 16 edges that appear in a minimum cut.

Proof:

Let’s say that this algorithm misses an edge that is in a minimum cut. If this is the case, when we did a BFS in the residual graph we were able to traverse through that edge. But the only way BFS can traverse that edge would be if it has forward capacity, but since this is an edge in a minimum cut this is not possible, a contradiction. If we can reach the node on the other side of that edge during our BFS that also means that this edge can’t be part of a min-cut, which the algorithm would figure out.


texts: Constructing Noneterministic Finite Automata (NFA) with a "not" condition

texts:
I have a question about some theoretical CS. Particularly, designing an NFA diagram (nondeterministic finite automata) from some conditions.

I think I understand how to construct NFA's under most simple circumstances, however, the types that I am struggling with are not conditions.

Here is one that has me really stumped:

Σ = { a, b, c }

Consider the language L:

L = { ω | ω ϵ Σ*, ω does not contain "cbac" }

I'd like to use the lambda-transition (λ-transition) to simplify this a bit. I am struggling with. How do I consider this condition?

Any help would be greatly appreciated!


texts:
I want the regula falsi to get x +- .0001 so that f(x) = 0. But all the implemetations I see get x so that f(x) +- .0001 = 0 which doesn't make much sense. (f(x) = x^3).
How do I  stop the regula falsi method when the error is .0001 on the x-axis?
I have this scilab code:
function salida = falsaposicion(fun, tolerancia, a, b)
   deff("y=f(x)", "y="+fun);
   if (f(a)*f(b)>0) then
       disp("Error");
   end

   cAnt = 1e100
   c =  b - f(b)*((b - a)/(f(b) - f(a)));

   while 0 == 0
       if f(b) - f(a) == 0 then
           disp("Error");
           break;
       end

       if abs(f(c)) < tolerancia then
           break;
       elseif f(a)*f(c) < 0 then
           b = c;
       elseif f(b)*f(c) < 0 then
           a = c;
       end

       cAnt = c;
       c = b - f(b)*((b - a)/(f(b) - f(a)));
   end

   salida = c;
endfunction

disp(falsaposicion("x^3", 0.0001, -6, 3));

```


texts: ln(n) + 1 Approximation for Set Cover constructions

texts:
Set Cover Problem: Given a set $X$ and a collection of subsets $S_1, S_2, \ldots S_m \subseteq S$, we want to find the smallest cardinality of a set of $k$ elements $\{i_1, \ldots i_k \}$ such that $\displaystyle \bigcup_{i = 1}^k S_{i_j} = X$.

Let $o$ be the size of optimal solution for the Set Cover problem. We know that there exists an approximation algorithm which yields solution $k$ such that $\frac{k}{o} \leq \ln(n) + 1$. As such, the approximation ratio is unbounded and can achieve large values for large $n$. Note that this algorithm is greedy and repeatedly chooses the set which covers the largest amount of elements that haven't been covered yet.

What is a methodical way to construct a set of size $n$ and all of the input subsets, such that increasing the size of $n$ monotonically increases the approximation ratio?


texts: The range of significance in Type Theory

texts:
What exactly does "Types as ranges of significance of propositional functions. In modern
terminology, types are domains of predicates" mean?

Update:
I found in this paper (Pag 14 or 234) by Russell, where he defines what is ranges of significance, not exactly including types else propositions.

  A function is said to be significant for the argument $x$ if it has a value for this argument. Thus we may say shortly $\phi x$ is significant,
  meaning the function $\phi$ has a value for the argument $x$. The range of significance of a function consists of all the arguments for which the
  function is true, together with all the arguments for which it is
  false.


texts: Converting a context free grammar to a PDA -- is my solution correct?

texts:
I'm reviewing for my midterm and wanted to post this to see if anyone can spot any errors. Im supposed to make a PDA that recognizes this CFG:

$\qquad\begin{align}
  S &\to R1R1R1 \\
  R &\to 0R \mid 1R \mid \varepsilon
\end{align}$

Here is my solution; I'm aware that I forgot to draw the second circle around my accepting state.


texts: Show that $f(n) = O(g(n))$ or $f(n) = \overset{\infty}{\Omega}(g(n))$

texts:
Before you downvote, please note that this question is distinct from this similar looking question
I came across the following the problem in "The Introduction to Algorithms" by Cormen et. al.
Show that for any two functions $f(n)$ and $g(n)$ that are asymptotically non negative, either $f(n) = O(g(n))$ or $f(n) = \overset{\infty}{\Omega}(g(n))$ or both.
In this book, $\overset{\infty}{\Omega}(g(n))$ is defined as follows:
$f(n) = \overset{\infty}{\Omega}(g(n))$ if there exists a positive constant $c$ such that $f(n) \geq cg(n) \geq 0$ for infinitely many integers $n$. Please note that here it says integers.
Proof from a solution manual
One approach is to show that if $f(n) \neq O(g(n))$ then $f(n) = \overset{\infty}{\Omega}(g(n))$.
In the book big Oh is defined as follows:
$f(n) = O(g(n))$ if there exists $n_0 > 0$ and $c > 0$, such that $\forall n \geq n_0$, $0 \leq f(n) \leq cg(n)$. Please note these inequalities are valid not just for integer $n$'s but for all $n \geq n_0$.
$f(n) \neq O(g(n)) \implies $ $\forall n_0 > 0$ and $\forall c > 0$ there exists $n \geq n_0$ such that $f(n) > cg(n)$
I am not going into the details but, by choosing different values for $n_0$ we can show that there are infinitely many real $n$ such that $f(n) > cg(n)$. However to prove that $f(n) = \overset{\infty}{\Omega}(g(n))$ we need to show that these infinitely many $n$'s are integers.
My question is could you please show that there are infinitely many integers not just real numbers, that satisfy $f(n) \geq g(n) \geq 0$ when $f(n) \neq O(g(n))$


texts:
I am reading Kolmogorov Complexity by Li and Vitányi:

"Let $x$ be a finite binary string. We write '$x$ is random' if the shortest binary description of $x$ with respect to the optimal specification method $D_0$ has length at least $x$."
By length $x$ I understand the natural number that the binary string maps to canonically.

[proof which I do not understand follows]

"This shows that although most strings are random, it is impossible to effectively prove them random."

However, I am able to produce a counterexample and can find a proof that $x$ is random effectively (there is an algorithm). Iterate over all the words of size up to $x-1$ of a description language. If you find a description $\alpha_x$ such that $D_0(\alpha_x)=x$ ($\alpha_x$ describes $x$) then terminate with verdict that $x$ is not random. If you exhaust all the words of length $<x$(there are finitely many since $x$ is finite so the program halts) and none of them describes $x$ and then terminate with result that $x$ is random.

What is wrong in my counterexample?


texts: Estimate the running time of counting nodes in a binary tree

texts:
I am asked to write an efficient method that computes the number of nodes in T, and here is what I did:

public int numOfNodes(Node t)
{
    if (t==null)
        return 0;

    return numOfNodes(t.left) + numOfNodes(t.right)+1;
}

Every node needs invokes two recursive calls, so the running time is $O(2^N)$.

Is my estimation of the running time correct? It seems to be too slow.


texts: Number of triangles in an undirected graph

texts:
How do we count the numbers of traingles (i.e., different triads of vertex $u,v,w$ such that edges $u-v,v-w,w-u \in E$ ) in a given graph $G$?

It is obvious that it can be done in $O(N^2)$: is there anything better?


texts: How to speed up finding a subset of a given set?

texts:
Is there a data indexing technique that speeds up finding subsets of a given set in a collection, or do I always have to scan all of the data?

For example, let's say that I have a collection of sets:
(a, b)
(b, c)
(a, b, c, d)
(a, b, c)
(b, c, d)
(b, e)
(d, e, f)
(d, f, g)
(d, e, f, g)

I want to find subsets of (a, b, c, d), so the output should be:
(a, b)
(b, c)
(a, b, c, d)
(a, b, c)
(b, c, d)

Is there a method to index/hash data in a way that will limit the number of collection elements that I have to scan in order to find all matches?


texts:
I'm looking for a solution to search for strings in a large text file. I would like to match strings with as many of those words in close proximity as possible.
For example, if a query is for the string "what is the term for a supreme court justice"

"a supreme court justice has lifetime tenure, meaning"
"the term of justice in the supreme court is.."

Would be matches in they are in the document being searched.
I'm sure that algorithms for this type of searching already exist, but I don't know what they are called or exactly what it is that I'm looking for.


texts:
I try to understand the details regarding using Hidden Markov Model in Tagging Problem.

The best concise description that I found is the Course notes by Michal Collins.

The goal is to find a function $f(x)=arg max_{y \in Y} p(y|x)$, where $y$ is the tag set for sentence $x$.

Question 1. It's suggested to use a generative model and to estimate joint probability $p(x,y)$ from the trainig examples, however what the the reason to use generative model and increase the number of computation why not directly to estimate $p(y|x)$, I think it's possible to estimate the conditional probability straightforward from the training data.

Addendum. Do you know the reason why at all we should try to use a generative model in this case (POS tagging). As I  understand if we can estimate $p(x,y)$ that exactly with  the same success we can estimate $p(y|x)$  and directly find the answer to the question, what is the best tagging - $\hat{y}$ without weak assumption of generative model. There is the reason to use generative model, and I don't see it yet. Can you explain me what the reason?

Question 2. Assume we decided to use a generative model and made estimation to $p(x,y)$ why we decide to decompose it as follows $p(x,y)=p(y)p(x|y)$ and not  $p(x,y)=p(x)p(y|x)$?

Addendum. I do understand that it's very logical to use the decomposition $p(y)p(x|y)$ just because by doing it we approach $p(y|x)$, so mathematically it seems very reasonable, however according to the task I don't see what the problem to decompose it like $p(x,y)=p(x)p(y|x)$, there should be sore reason why we can not decompose it so and I don't understand why.

I appreciate your help.


texts: Algorithm to test dependency preservation

texts:
Is there an algorithm to test whether the decomposition of relation $R$ into relations $R_1,\dots,R_n$ is dependency-preserving?

In more detail, I am given a relation $R(x_1,\dots,x_m)$ on $m$ variables.  I am given a decomposition of $R$ into relations $R_1,\dots,R_n$, where each relation $R_i$ refers to a subset of the variables $\{x_1,\dots,x_m\}$.  I am also given a set of functional dependencies $F$ for $R$.  I would like to know whether this decomposition is dependency-preserving.  Is there an efficient algorithm to answer this question?

Recall the definition of "dependency-preserving" from database theory: the decomposition of $R$ into $R_1,\dots,R_n$ is dependency-preserving if $F^+=G^+$, where $G=G_1 \cup \dots \cup G_n$ and $G_i$ is the restriction of $F$ to the variables of $R_i$ (so $G_i$ is a set of functional dependencies for $R_i$).


texts: Complexity of deciding whether there is a winning strategy in the following game

texts:
The sum divider game for $n$ starts with the set $M_0 = \{1,\dots,n\}$. Player A chooses a number $m_1$ from $M_0 \setminus \{1\}$ and B has to choose a divider $m_2$ of $m_1$ from $M_1 = M_0 \setminus \{m_1\}$. The players continue to choose a number $m_i$ from $M_{i-1} = M_{i-2} \setminus \{m_{i-1}\}$ alternatingly, where every $m_i$ has to divide $\sum_{k=1}^{i-1} m_k$. A player wins, if the other player is unable to do so and $M_{i-1} \neq \emptyset$, $M_{i-1} = \emptyset$ is considered a tie.

My questions:

Is there an $n > 2$, for which A has no winning strategy?
Given some $n$ (in unary representation), how hard is it to decide whether there is a winning strategy for A

where A wins in at most $k$ steps ?
where A chooses no prime numbers ?


texts: How to do binary search on a path in a binary heap

texts:
I am trying to solve this question:
Let's say you have a binary heap and an index $i$, design an algorithm that finds if a number $x$ appears in the path between the root of the heap and $heap[i]$ in time $O(\log(\log n))$.
My solution:
Before the loop, I will create a new linked list and initiate $heap[i]$ to be the first item in the list.
Then, I will run a loop on the heap that will start from index $i$, and in every iteration, it will extract the parent of the item in the index $i$ to a new array and will break after extracting the root of the heap.
Then, I will use binary search on the new array (I know that every parent in the heap is bigger than its children. So the new array is already sorted).
The problem is that the extraction of the parents cost me $O(\log i)$ which can be in the worst-case  $O(\log n)$, and for that reason, my solution can't work.
I will be grateful for any help.


texts: Is this an accepted/valid clustering evaluation metric?

texts:
We have a clustering algorithm where the number of clusters isn't known to the algorithm - it iteratively creates clusters out of similar-looking data points.

The evaluation metric we're currently using is:

for each pair of elements in the dataset:
    if both elements belong to the same class:
        if both are in the same cluster:
            truePositive++
        else:
            falseNegative++
     else: // elements belong to different classes
        if both are in same cluster:
            falsePositive++
        else:
            trueNegative++

Is this a good/valid evaluation metric? Please note that the number of predicted clusters are usually more than the number of classes/natural clusters in the dataset, and hence can't usually map a cluster to a class label. What other metrics might be suitable in this case?


texts: Doubt regarding Cantor's diagonalization argument

texts:
So, we use Cantor's diagonalization argument to prove that the Universal Turing Machine is not a decider.

I understand the overall argument but have a problem regarding one caveat mentioned in my book.

My book says that some real numbers like 2.000... and 1.999... have different decimal representations but are actually the same real numbers. Suppose we have a bijection $ f: N \rightarrow R$ where $N$ and $R$ are the sets of natural and real numbers respectively. Now, suppose $f(1) = 1.999...$ and no $x \in N$ exists such that $f(x) = 2.000...$. In such a scenario it is possible that the diagonalization argument ends up constructing the real number $2.000...$ which is already in our list since $1.999...$ and $2.000...$ are the same real numbers. To get around this problem, we never select 0 or 9 when constructing our number.

I don't understand two things. First, why do $1.999...$ and $2.000...$ represent the same real number? Second, how never selecting 0 or 9 solves the problem this poses?


texts:
I have to solve the following $n^2+n \in O(n^2−n)$.

I did it this way:
$n^2+n \in O(n^2−n) = n^2 \in O(n^2−n) = n^2 / n^2-n = 2n / 2n-n$ which is infinite.

I don't know if this is correct because the $-n$ in the $O$ notation is confusing me and I haven't found anything about it online. I know if this would be at example -1000 that $n^2+n \in O(n^2−n)$ would be correct.

Could someone explain it to me ?


texts: Maximum Pairwise GCD of an even subsequence

texts:
I am trying to solve a particular problem, where I have been given an array of integers and an integer X and I need to choose a subsequence of the array whose pairwise gcd is maximum given that the size of the subsequence must not exceed 2*X.

So for example, my array is [5, 7, 10, 8, 3, 4] and X is 2:
the answer would be 9 since GCD(5, 10) + GCD(8, 4) = 9

The only approach I've been able to come up with was: At each step I'll find the maximum pairwise GCD of the numbers and then remove the 2 numbers from the array.
Will keep adding it to a sum(which I have to output), under the constraints that I dont take in more than 2*X numbers.


texts: Task assignment problem with capabilities and time restrictions

texts:
I have the following optimalization problem. I use the notations below because maybe it would be easier to understand that way, but I'm not good at conventions – I'm not sure if I'm using it all the right way – so feel free to correct me on this.

We have multiple tasks, $T_1,…, T_n$. Each of them has exactly one type (or is of a specific kind), $K_1,…K_s$ (notice that number of types is independent from the number of tasks). Each of them also has its start and end time, $S_k$ and $S'_k$.

We also have multiple workers, $W_1,…W_r$. Each of them is available for a limited number of time and finishes its work on $E_k$ (like expiration). Every worker is capable of performing specific types of tasks, so $C(W_k) = \{K_{a_1}, …, K_{a_n} \}$ (C from capabilities). Each worker can only perform one task at a time, but we may have multiple workers with the same capabilities.

Now, our task is not to plan the whole flow – new workers may come and we don't know anything about this. The thing is, a worker ($W_a$) comes to us at a specific time and asks for a task ($T$) to perform. We know the worker's "expiration date" ($E$), so we know we can't give him task where $S'_k > E_a$ (he won't be able to finish it). We have to give him a specific task, preferably the one that starts soon, but that's not a strong constraint. We have to maximize the number of tasks performed, knowing all the workers that we now have and knowing that we'll have them until they expire.

An example, maybe?

Let's say we have 4 kinds of tasks, $K_1, K_2, K_3, K_4$. We have three workers with the following capabilities:

$C(W_1) = \{K_1, K_2, K_4\}$

$C(W_2) = \{K_1, K_2\}$

$C(W_3) = \{K_1, K_2, K_3\}$

And we have our tasks, let's say four of them. Here are the types with start and end times:

$T_1$ (type $K_1$) spans from $0$ to $20$

$T_2$ (type $K_2$) spans from $10$ to $40$

$T_3$ (type $K_3$) spans from $15$ to $50$

$T_4$ (type $K_4$) spans from $25$ to $50$

So it looks like this:

         |------T3------|
      |-----T2----|
|----T1----| |----T4----|

So let's say we're at the time $0$ – the beginning of my beautiful illustration – and the worker $W_3$ comes to us. We could give him task $T_1$ – he's capable of doing it – but then nobody could do the task $T_3$, since he's the only one for that job. So we tell him to wait and then do $T_3$.

$W_1$ would do $T_1$ and $T_4$. $W_2$ would be left with $T_2$.

That was a rather simple example, but I hope you get the idea.

I have read numerous articles about different types of task assignment problems, but I didn't find anything similar (or specific) enough.


texts: Turing, RAM, or Von Neumann --- which theory/model is the consensus?

texts:
I am not a formal student for CS nor have I ever been, I just want to understand something simple about your field for general knowledge, in plea.
Turing, RAM, or Von Neumann --- which theory/model is consensually accepted to describe how "generally every computer works" (among computer scientists)?


texts:
I am attempting to prove via the pumping lemma that $1^{n^2}$ is not a regular language. I started with

$w = 1^{p^2}$

I then divided $w$ into $xyz$, where:

$x = 1^{l}$

$y = 1^{m}$

$z = 1^{{p^2}-l-m}$, where $l+m \le p$ and $m \ge 0$.

Now, when I choose $i=2$ in order to get $xy^2z$, I end up with:

$1^{{p^2}+m}$, since $0 > m \le p $, the sum $m+p^2$ could certainly not be a square because the difference between $p^2$ and the next square is always greater than $p$ for all natural numbers.

Q.E.D

However, even if the basic logic of the proof is right, it does not seem as if my conclusion is as strong as it should be. Is there a more formal, proof-like manner to reach my conclusion with the same $s$ and $xyz$?


texts:
Having a simple 2-SAT problem where the equation is simply: $a \lor b$

We have two implications:

$\lnot a \Rightarrow b$
$\lnot b \Rightarrow a$

Thus, in the graph we build we add edges similar to the arrows above.

What exactly do the arrows symbolise in this instance? I've read that they means if $a$ is true, $b$ must be true as well. The same for false. Why can we model this equation in such a way?


texts: Find whether a word is in a rational expression

texts:
You are given a word $w$ and a rational expression $R$ ($R$ is represented as a binary tree). Find an efficient algorithm that says whether $w \in L(R)$ or not.

I think I found a quadratic algorithm. First let denote $n$ the size of $R$ (i.e. the number of nodes). Then apply Glushkov's algorithm. So we get an automata that recognize $L(R)$ in time $O(n^2)$. Now just do a BFS to see if this automata accepts $w$. Hence this algorithm is in $O(n^2)$.

Now my question is: is it possible to do any better? Is there a way to solve this problem without computing the automata that recognized $L(R)$?


texts:
This is mostly a terminological question: Is there a fundamental difference between "optimization problems" and "search problems"? Apologies if this is an obvious question
As I understand it, we can define the two as follows (note, I consider the problem for a fixed input size for brevity):

Search problem. Given a set $X$ of candidate solutions, and a property $P:X\to \{\text{True}, \text{False}\}$, find an $x\in X$ such that $P(x)$.
Optimization problem. Given a set $X$ of candidate solutions, and a criterion function $F:X\to \mathbb R$, find an $x\in X$ such that $x\in \arg\max_{y\in X} F(y)$.

But it seems to me that to say that a search problem $P_S$ is "reducible" to an optimization problem $P_O$ is an understatement: They seem to be exactly the same apart from a "stylistic" difference:

Given a search problem $P_S=(X,P)$, define optimization problem $P_O=(X,F)$ where $F(x) = \begin{cases}1 \quad \text {if }  P(x)\\0\quad \text {if } \neg P(x) \end{cases}$
Given a optimization problem $P_O=(X,F)$, define search problem $P_S=(X,P)$, with $P(x)=  \begin{cases}\text{True} \quad \text { if }  x \in \arg\max_{y\in X} F(y)\\\text{False}\quad \text { if } x \notin \arg\max_{y\in X} F(y)\end{cases}$

Is there really not a fundamental difference between these two problems? Or are they fundamentally different in some way that I'm overlooking?


texts: Finding the minimum number of calls in a tree

texts:
I was asked this question in an interview and struggled to answer it correctly in the time allotted. Nonetheless, I thought it was an interesting problem, and I hadn't seen it before.

Suppose you have a tree where the root can call (on the phone) each of it's children, when a child receives the call, he can call each of his children, etc. The problem is that each call must be done in a number of rounds, and we need to minimize the number of rounds it takes to make the calls. For example, suppose you have the following tree:

   A
  / \
 /   \
 B    D
 |
 |
 C

One solution is for A to call D in round one, A to call B in round two, and B to call C in round three. The optimal solution is for A to call B in round one, and A to call D and B to call C in round two.

Note that A cannot call both B and D in the same round, nor can any node call more than one of its children in the same round. However, multiple nodes with a different parent can call simultaneously. For example, given the tree:

      A
    / | \
   /  |  \
   B  C   D
  /\      |
 /  \     |
E   F     G

We can have a sequence (where "-" separates rounds), such as:

  A B - B E, A D - B F, A C, D G

(A calls B first round, B calls E and A calls D second, ...)

I'm assuming some type of dynamic programming can be used, but I'm not sure which direction to take this in. My initial inclination is to use DFS to order the longest path from the root to leaves in decreasing order, but when it comes to the nodes actually making calls, I'm not sure how we can achieve optimality given any tree, nor how we can output the paths that the optimal calls would make (i.e. in the first example we could output

  A B - B C, A D


texts: How to express modalities in lambda calculus - are some extensions required?

texts:
Lambda calculus can be used for encoding semantics of natural language, e.g. http://yoavartzi.com/tutorial/ contains full details about semantic parsing of natural language: converting natural language texts into lambda expressions - Cornell Semantic Parsing Framework is used https://github.com/cornell-lic/spf.

My question is - how to express modalities in lambda calculus - are some extensions required? E.g. usual classical modal logics can express beliefs/duties-permissions/knowledge and other kind of modalities. Relational (Kripke) semantics is used for modal logics. So - how can we extend of combine lambda calculus to express modalities?

There is idea to express modalities as just another kind of predicates https://www.amazon.co.uk/Toward-Predicate-Approaches-Modality-Trends-ebook/dp/B016XM48V0 but are there some alternatives, more "natrual" ways to introduce modalities in lambda calculus? Full handling of natural language certainly requires this.


texts:
I have a $n \times m$ matrix $M$ and a permutation of sequence $P$ of numbers from $1$ to $n$.

I have to fill the matrix using numbers $1$ to $n \times m$ in such a way that for each row $i$, the function $f(i) > 0.5$ where:

$f(i)$ is the probability that a number chosen randomly from row $i$ will be greater than a number chosen randomly from row $P[i]$. ($i$'s corresponding row according to permutation.)

For an example, let $n=3$,$m=3$,$P=[3, 1, 2]$ and $M=$

2 6 7
3 4 8
1 5 9

According to the given permutation, you will have to compare the number chosen from 1st row with 3rd row and similarly.

In the given matrix number are arranged in such a way that $f(1) = f(2) = f(3) = 5/9$.
Observe that there are 5 pairs in the Cartesian product $\{2,6,7\}\times\{1,5,9\}$ which the first element is larger than the second.

My question is how to construct such a matrix provided $n,m,P$ as input?


texts:
Lets say, we have a lot of lists (sequences of variable length) of some limited set of elements:

[A, B, D, E, Q], [A, D], [A, C, E, F, G, H, Y, Z], [B, A, E, D, Z, Y], ...

The problem is to get the single order, based on "how typical" some position is, eg, in our case it can be (coincidence with alphabetical order is just a coincidence):

[A, B, C, D, E, F, G, H, Q, Y, Z]

But lets say [Z, Q, Y, C, B, A, D, E, F, G] is "surprising" order, far from being "typical".

The questions are:

are there any "official" CS terms for the situation (so I can do further searches)?
what are practically popular definitions / metrics for "how typical" (or "surprising") in the above description?

My idea so far is to count "average position", normalized to the max length of the list. Then the order will be by increasing normalized average positions. I feel, maybe term rank and some statistics' techniques are also applicable to this, but I am more interested in some easily (one pass) computable metrics. Any pointers?

One more idea is to calculate probability of every pair where one element is before another, and sort based on whether probability is less than 0.5 or more. But this may need a triangular matrix and a lot of computations. (For the example above, p(A before D|both occur) = 1, but p(A before B) = 0.5).

One gotcha may be that is some element is usual for the beginnings and ends, but never the middle, the average result may still be in the middle... But I guess it may be too subtle to satisfy.

For now, using very rough method:

def approx_position(position, length, master_length):
    return int(position * master_length / float(length))

seqs = ['A', 'B', 'D', 'E', 'Q'], ['A', 'D'], \
    ['A', 'C', 'E', 'F', 'G', 'H', 'Y', 'Z'], ['B', 'A', 'E', 'D', 'Z', 'Y']

master = []
for s in seqs:
    total = len(s)
    est_len = len(set(master) | set(s))
    for i, item in enumerate(s):
        if item not in master:
            new_pos = approx_position(i, total, est_len)
            master.insert(new_pos, item)

print master
# ['A', 'C', 'B', 'D', 'F', 'G', 'H', 'E', 'Y', 'Z', 'Q']
# when seqs in reversed order:
# ['B', 'C', 'A', 'F', 'E', 'G', 'H', 'D', 'Q', 'Z', 'Y']

NB. Python insert works on intervals between list elements. So 0 corresponds to the place before first element.

Not ideal, but at least almost one pass (one hidden pass in set union).

Something similar is for example discussed here:
https://stackoverflow.com/questions/4645874/merging-some-sorted-lists-with-unknown-order-sequence However, my problem is overdetermined, so the question is how to do relaxation, while the results are still near optimal (the criteria is part of the answer).

(trying to widen my horizons as it is usually hard to find a right term for something if one has never encountered that term before)


texts: Finding the shortest path in non-complete node-weighted graph

texts:
Normally, Simulated Annealing (SA) is used in TSP problem to find the near-to-optimal solution, and the graph structure in TSP is a complete graph. Therefore, I want to know whether or not I can use SA for finding the shortest path/optimal solution in a non-complete(connected undirected) weighted graph in the 2 dimentional Euclidean space.

If I cannot use SA in this case, could you recommend me a good algorithm for this?
*** Note: the weight here is referred to the weight on each node, not edge weight.

Thanks in advanced!


texts: Recursion for runtime of divide and conquer algorithms

texts:
A divide and conquer algorithm's work at a specific level can be simplified into the equation:

$\qquad \displaystyle O\left(n^d\right) \cdot \left(\frac{a}{b^d}\right)^k$

where $n$ is the size of the problem, $a$ is the number of sub problems, $b$ is the factor the size of the problem is broken down by at each recursion, $k$ is the level, and $d$ is the exponent for Big O notation (linear, exponential etc.).

The book claims  if the ratio is greater than one the sum of work is given by the last term on the last level, but if it is less than one the sum of work is given by the first term of the first level. Could someone explain why this is true?


texts: Does KMP Algorithm handle finding multiple matches in overlapping cases?

texts:
I am wondering if KMP algorithm can find multiple matches in a given string when there is an overlap.

Here is an example.

  Word to Search from (S): abcabcabc
   Search word (W): abcabc

If you look at "W", it matches "S" from index 0 as well as from index 3

(abcabc)abc
abc(abcabc)

When I looked at the pseudo code on Wikipedia and implemented it, KMP algorithm seems to return only after the first match ((abcabc)abc).

Am I implementing it wrong or does KMP doesn't handle overlapping cases?


texts: Is it possible to "unshift" onto a queue using this theoretical "queue automaton"?

texts:
I have been playing Manufactoria, a game in which one has to build a production line that tests/modifies "robots". Each robot has a "tape" where each cell is colored either red, green, blue or yellow. The production line can test/modify a robot by popping colors off the start of its tape, by moving the robot to different lines depending on the color popped off, and by pushing more colors onto the end of its tape. The tape is effectively a queue.

One level ("Robostilts") asks you, the designer, to build a production line that modifies each robot's tape to put a "green" at the start, and a "yellow" at the end. It turns out this challenge is easily completed because all robots start with only red and blue colors on the tape, and no green or yellows.

However, I initially misinterpreted the challenge, thinking that the input tapes were completely arbitrary. This seemed challenging, and now I think it's impossible. However, I don't know how to show this precisely, but I thought someone here might be able to. I have formalized the problem below.

$A$ is the four-letter alphabet $\{ R, G, B, Y \}$.

An automaton is $(S,sInit,sTerm,d)$ where

$S$ is a set of states
$sInit \in S$ is the initial state
$sTerm \in S$ is the terminal state
$d$ is a transition function $: (S \times A) \rightarrow (S \times A\star)$. (Note: $A\star$ denotes lists of $A$ elements.)

The automaton steps through a series of configurations $(s, x) \in (S \times A\star)$.

For a given "input string" $i \in A\star$,
the initial configuration is $(sInit, i)$.

The function $step : (S \times A\star) \rightarrow (S \times A\star)$ is given by

$
step (s, [x] \mathbin{+\mkern-10mu+} xs) =\\
\qquad\mathbf{let}\quad(s', new) = d(s,x)\\
\qquad\mathbf{in}\quad(s', xs \mathbin{+\mkern-10mu+} new)
$

The task is to define such a machine which,
starting with configuration $(sInit, i)$ for an arbitrary $i$,
after a finite number of applications of the step function,
reaches configuration $(sTerm, [G] \mathbin{+\mkern-10mu+} i \mathbin{+\mkern-10mu+} [Y])$.

Is this possible? If yes, how? If no, why not?


texts: Can an $NDTM$ simultaneously perform a set of operations on all strings of a given length?

texts:
Can an $NDTM$ perform a set of operations on all strings of a given length $b$, at the same time? Aka can it operate on all strings of a given length by doing something like: spawn $2^b$ branches then operate on each string of length b on each branch?
How could it do this tho if the branches can't communicate? That's what I'm having a hard time with. How does any given branch, if it doesn't know what strings the other branches are running, know what string to run the operations on (so that all the strings are covered by $2^b$ branches)?


texts: How can I compute the time complexity of this image processing algorithm?

texts:
Well, my question is simple, I would like to compute the complexity time of an algorithm related to image processing.

I simplified the algorithm ... so that we focus only on the problematic part.

Algorithm

You have an image/matrix of $N =n \times m$ size and a block of size $b \times b$ (block is just a window or rectangle that will slid through the picture of pixels or the matrix of intensities).

The algorithm goes through most pixels in the image (as center of the block, so it may step over the end of the line or the beginning) by a step of size $s$. The step is inferior to the size of the block $s<b$, so there is some overlapping (because some pixels are being considered in multiple blocks), and then it performs some operations with a complexity relative to the size $b$ equals $O(b^2)$.

Concretely, the algorithm starts in line $1$, and process blocks starting at $1, s+1, 2s+1, ... $ columns, then it goes to the $s+1$ line and do the same as on line $1$, then to $2s+1$ line and so on. Every iteration, the algorithm computes some operations related to the size of the block (which can be $3 \times3$ or $5 \times 5$, ... and $s$ is $1/8$ the $b$ for instance).

Any help, or reference related to this topic is a welcome.


texts: How to calculate a specific time complexity of inverse calculation of matrix?

texts:
I am a green-hand in calculating the time complexity. Given a calculation as follows:

\begin{equation}
\mathbf{x}=\mathbf{A^T}(\mathbf{AA^T}+\lambda\mathbf{I}_n)^{-1}\mathbf{b}
\end{equation}
where $\mathbf{A}\in R^{n\times p}$, $\mathbf{I}_n\in R^{n\times n}$, $\mathbf{b}\in R^{n}$ and $\lambda\in R$.

Could some one kindly give me the complexity of the above formula in details? Thanks a lot.


texts: Why are types and grammar non-terminals so distinct?

texts:
Sorry ahead of time if some of my terminology is inaccurate, my formal training isn't quite to the level it should be.

Almost all programming languages with types separate built-in functions a + b and user defined functions f(x) into different steps of the compiler. a + b is dictated by some grammar that says something like expr ::= expr + term, and is dealt with by the parser. The precedence/associativity of operations is also defined by the parser, and all user defined functions are dumped into a common bucket. f(x) is defined by a declaration that requires x to be some type, and the result to be a particular type - which is then commonly checked post-parse in static analysis.

Thinking about it, it seems as though f (assuming for example, f goes from int to bool) could be defined in a grammar similar to

bool ::= "true" | "false" | bool-expr
bool-expr ::= "f" "(" int ")"
int ::= int-constant | int-expr ...

But doing some searches, it seems as though computer science research around types and grammars are formal, but always distinct.

Sure, there are practical concerns. Grammars tend to be static, preventing user defined functions from being... user defined. Grammars tend to be hard to make correctly/unambiguously, and letting random users meddle is troublesome. Having huge grammars would be more troublesome than doing the same sort of work split off to a more limited type-checker.

But there's all sorts of research which is done regardless of practical concerns. I find it hard to believe that the two research areas wouldn't benefit from ideas from each other. And by treating types like non-terminals (or vice versa), it seems as though you get quite a few benefits not commonly available (function overloading by return type, extensible language using types rather than a separate meta-language, better integration of user defined operators).

Given my lack of training though, I'm guessing there's simply something I'm missing that breaks the correspondence or that it was researched and promptly discarded due to something obvious to others. So what am I missing?

Clarification for svick's comment

function overloading by return type:

Since statements/expressions would need to be integrated with types, statement would need to map to void or unit or some analogy - and expressions would be typed as above. For example, f(x:int) -> void and f(x:int) -> int, only one is viable as a statement. This requires function signatures to be processed before implementations (akin to C), but that is rather implied for all of the approach.

extensible language without meta-language:

By making types act like grammar non-terminals, it would allow the parser behavior to vary based on function declarations (and the various symbols in scope). Consider the above example where statements are required to be void. f(x) would not even parse without some declaration that both matches that input and results in void. The function/variable/type declarations of the language effectively become the meta-language. But that's what programmers do already...

better integration of user defined operators:

Previous extensible languages had approaches to user defined operators, requiring the user to define precedence (usually some numeric value, relative to the built-in operators), and associativity. Having user defined and built-in operators/functions "speak the same language" as it were should provide a more uniform interaction between the two.

But mostly, the benefits I would expect are more theoretical. Things that can be proven/used about grammars could be applied to type checking and vice versa if types and non-terminals had some correspondence.


texts: Increasing every starting edge by a constant, then the shortest path tree remains the same?

texts:
Consider a directed graph G = (V,E) with non-negative costs on each edge.
  With s being a starting vertex. Prove that by adding a constant k to each edge
  (s,u) ∈ E such as u ∈ V, the shortest path tree starting from s will remain the same.

In an attempt to solve the above question (with a proof)
I thought that if we add the same constant factor to every edge the relative order of path weights is preserved.
  However, I am not sure how to state the proof correctly.

I have searched a lot, any help would be greatly appreciated.


texts: What to do with operators with the same precedence in an unambiguous grammar?

texts:
I'm trying to create an unambiguous grammar for a calculator that uses $+$, $-$, $*$, $/$ and $()$.
From watching videos and reading articles online, I understand how to create the grammar with $+$, $*$, $()$ (or 3 different precedences).
i.e. $E \to E + E \mid E * E \mid (E) \;\mid \;\text{num}$
$$\begin{align}
E &\to E + F \mid T\\
T &\to T * F \mid F\\
F &\to(E)\;|\; \text{num}\\
\end{align}$$
How would I include $-$ and $/$ in this? Would this approach be correct (unambiguous)?
$$\begin{align}
E &\to E + F \mid E - F \mid T\\
T &\to T * F \mid T / F \mid F\\
F &\to(E)\;|\; \text{num}\\
\end{align}$$


texts:
I am trying to understand interactive proof systems and tried the following problem as an exercise. We know that $PH \subseteq PSPACE$ and $IP=PSPACE$, so come up with (easy to understand) interactive proof systems for $PH$?

An interactive proof system for $NP$ is trivial, but I failed to get an interactive proof system even for $coNP$. Do you know of an explicit interactive proof system (by explicit I mean without going through the $IP=PSPACE$ route) for $coNP$?


texts: Find maximum scoring characters with non overlapping occurrences from a string

texts:
I have a problem related to Episode Mining in which I need to find the maximal utility of a episode given its occurrences in an event sequence.But I am presenting the question in a different form so that it's easier to explain.

There is a long string, S, where each of its character have some positive score. Given another string, T, find a match with S containing all occurrences of the sequence of characters of T such that :-

The occurrences are non-overlapping.
The sequence of characters in S must be same as present in T but it can be discontinous.
Each occurrence should lie in a given window.
The total score of a match can be found by simply adding the scores of the characters at each occurrence.The problem is to find a match with maximum score of all the matches possible.

Example - String S - a(2) b(3) e(1) d(10) d(7) c(1) a(5) d(8) b(5) d(6)

String T - a b d

Window size - 5

Two matches of string T are:-

[1,2,4], [7,9,10]. Score - [2+3+10] + [5+5+6]= 31
[1,2,5], [7,9,10]. Score - [2+3+7] + [5+5+6]= 28. And the score is maximum in match 1 so it is the required answer.
We didn't consider the occurrence [1,2,8] or [1,2,10] as they are not in the given window as (8-1) > 5.

So, I would like to know if there is some solution to find the set of occurences or match that gives the maximum score efficiently.


texts: How to determine the pre and post conditions of a program (Hoare-logic)

texts:
Problem
Below is a program named X:
y = 1;
while(y < x){
    y = 10 * y;
}

What does this program X do? What are appropriate pre and post conditions?
 (Assume that x and y are integers).

My solution
Given a whole number x > 1, X should give us a power of 10 greater than or equal to x.
pre-condition: (|x = x0 ∧ x0 > 1|)
post-condition: (|y ≥ x ∧ ∃n(y=10n)|)
However, I don't know if my solution is correct. It would be nice to know how to solve this trivial problem.


texts: Does it matter if I reverse the arguments order of a lambda calculus function?

texts:
what is the difference between the below functions?
$$\lambda x.\lambda y.f(x, y)$$
$$\lambda y.\lambda x.f(x, y)$$

And it appears that there is a $\texttt{reverse operation}$ in lambda calculus which can reverse the order of the arguments. So does the order actually matter?

I am asking this question because I am reading this paper, in which the author reverse the argument order in the 5th page:
$$ [\![ R[b]]\!] = \lambda y.\lambda x.[\![b]\!](x, y)  $$
Here $R$ is the ${reverse}$ $operator$. I am not sure why the author did this. And why it matters to change the order in which the arguments are taken.


texts:
I need to disprove that a PARITY gate can be simulated using a single MAJORITY gate, or even a THRESHOLD gate. How do I go about doing this? Some ideas as to how to go about contradiction or otherwise would be helpful.

One possible argument would be monotonicity of MAJORITY and THRESHOLD while PARITY is non-monotone (Page 134 of this paper). But, I do not find this sufficiently convincing.


texts: How to evaluate the learned prototypes for multivariate time-series (e.g. motion)?

texts:
Consider a method which finds prototypes for multivariate time-series (MTS) data, and is designed to find prototypes for each class of data.
For example, the {walking} class consists of some slightly different types of {walking} sub-classes, but they are not annotated. So i want to check if my prototypes can adequately represent the variations within each class and to measure the quality of the estimated prototypes.

In fact, I can calculate the distance of the prototype to the data points, but since it is possible to have more than one prototype per class/cluster, i cannot decide to which data point i should calculate this distance.

If the data is related to motion data, it is possible to watch the resulted prototypes to check how sensible they are. However, i'm not sure how to measure their quality in a numerical way?


texts: Relations between P^#P, NP^#P and (CO-NP)^#P

texts:
I was wondering if there were relation between the complexity classes
$P^{\#P}$, $NP^{\#P}$, $(Co-NP)^{\#P}$ ?(except the trivial inclusions)

I've the feeling that when taking a $NP^{\#P}$ machine, we can transfer the non-determinism inside the non determinism of the counting oracle, and thus leading to the inclusion $NP^{\#P} \subset P^{\#P}$.

Moreover I've for the same reason the feeling that $NP^{\#P} = (Co-NP)^{\#P}$, in the sense that you can take a Co-NP machine in the oracle (instead of a NP one ) and it does"t change anything in the resulting complexity class.


texts: Which programming language is used at the Large Hadron Collider?

texts:
First off I am new to computer science (first semester) and do not know anything about physics, so I am appologizing up front for this not very scientific question.

I've been wondering how data is processed at the LHC. I am sure CERN doesn't just use one programming language to write code but I am curious what the fastest (machine nearest?) language is, keeping in mind that particles at LHC are nearly moving at the speed of light.

So if for example a sensor senses a particle on one side of the LHC, and there is a sensor on the other side of the LHC, data from one side to the other would have a direct and shorter way, but the processing would have to take less than a 50 millionth of second (est.), right?


texts:
In Gonzalez et al it is mentioned that Tapered Quantization is

I am unable to figure this thing out. I have searched the whole internet, but nothing of the same appears. I need a help in understanding this matter, and if you can provide a picture that will be really helpful.


texts: Why is $L=wxw^R|w,x\in\{0,1\}^+$ regular?

texts:
I was taught that if you can create a DFA to accept a language, then the grammar that is generating the language is regular.

AND

A DFA is a finite automata that accepts a language and also rejects the strings that aren't a part of the language.

It says if we replace $x$ with $c$ where $c \in \{0,1\}^+$, then $L$ is regular.

But the DFA should reject the string $abbaaaba$ since it doesn't fit the $wxw^R$ criteria and that isn't happening, so how is it regular?


texts: Sliding window protocol when number of packets is equivalent to the window size

texts:
I am currently taking a course in computer networking and I am curious about the following situation:

Given $n$ packets and a window size of $n$ (i.e., the number of packets is equivalent to the window size), what would happen in the following scenario?:

Packet 1 is sent by Host A and the corresponding ACK is received. Do the window boundaries need to be updated to $[2:n + 1]$ or would it remain as $[1:n]$ (as there would be $n - 1$ remaining packets (strictly less than the window size, $n$)?


texts:
If I have a set $A$ with positive and negative numbers, and a number to find C.

It is possible to reduce the problem to one with only positive numbers in set $A$?

I mean, it is possible to find a new set $A$ and a new number $C$, so $A$ were only positive numbers, but the same problem?