texts: Getting the idea behind pumping length correct

texts:
I am unsure whether I got the notion behind the pumping length correctly. I know its definition, and just want to make sure that I understood everything correctly.

Suppose we have an automata that accepts $0^{*}1^{*}$. The longest word accepted is $01$ without an iteration, whose length is $2$. So $n=2$, am I correct?

In case of $0......01^{*}$ where there are $n$ zeroes, the constant would be simply equal to $n+1$.

Is my thinking correct?


texts: Can we create the level graph from sink to source in Dinitz?

texts:
One of the steps of the Dinitz algorithm for computing maximal flows is to create a level graph. It is created from source to sink using BFS.

Could we create the level graph from sink to source instead of source to sink? Of course when subsequently doing the DFS on the level graph we would have to go down the levels rather than up.

I would expect this slight variation to lead to less dead ends during the DFS, resulting in a somewhat faster algorithm. I implemented the change and it supports my expectations. The performance improvement is minor but consistent in my test cases (e.g.: random graphs).

I could not find any literature about this online, and I study CS by myself so I cannot ask a teacher.

Is the change valid, or does it break the algorithm in a way I did not anticipate?
I can think of graphs in which the change would have a worse performance (i.e.: simple paths from source to sink, complicated paths from sink to dead ends). Is there a class of problems where these graphs are commonplace?
Anything else I should know or worry about?


texts: Is the variation of partition problem where instead the sum of the sets only be equal to a value $B$, they could also differ by two ( i.e., the sum of one set could be $B-1$ and the other $B+1$ ) still $NP$-complete?


texts: How can i prove this asymptotic comparison?

texts:
This is an exercise that's part of my assignment, but it is optional and flagged as a "challenge". I would like to discuss its solution:

Prove that: $$ 27\log{n} + \sqrt{n} = \theta(\sqrt{n})$$

Clearly this is correct, because the dominant term ($\sqrt{n}$) is present in both sides. But i wasn't able to give a mathematic explanation why it's correct.


texts: Can the output value be solved and/or written as Taylor expansion?

texts:
imho this is not at all a duplicate, because the other question does
  not address the "recursive" case $T(d,n) = ....T(d-1,T(d-1,n))....$,
  which appears to be part of the Taylor expansion of this function.
  Also I don't know how to write this as a Taylor expansion. If I would,
  I would still not know how to solve this specific instance.

Consider the following function. Maybe it could be more efficient, but I'm only interested in the output value, not the runtime complexity. All variables are whole numbers.

function branch(currentDepth, maxDepth, n, k) {
    if (currentDepth == maxDepth) {
        return n;
    }
    sum = 0;
    for (i=0; i<=k; i++) {
        tmpN = branch(currentDepth+1, maxDepth, n, i);
        sum += branch(currentDepth+1, maxDepth, tmpN, k-i);
    }
    return sum;
}

For $2 < k << n$ and $2 < d = O(\log n)$, is there a formula in terms of $d$, $k$ and $n$ (either exact, big-O or Theta), that predicts the output for

branch(0, d, n, k);

Will it be exponential in $n$? Can we maybe solve this for small $k$? ($k\le7$).

Application: the output value is a factor of the runtime complexity of a Fixed Parameter algorithm I made up, but I don't think it will beat existing algorithms. However I still wanted this solved.


texts: If a problem is not in NP, prove that every NP problem can be efficiently reduced to it

texts:
I understand that an NP-hard problem is a problem X such that any problem in NP can be reduced to X in polynomial time.

Does there exist a problem that is hard to solve but problems in NP cannot be reduced to it in polynomial time i.e. it does not satisfy the definition of NP-hard but is strictly not in NP? If not, what is the proof that if I can efficiently solve a problem that is strictly not in NP, then I can efficiently solve every problem in NP?

I suppose an analogous question can also be asked for P and NP. If a problem is in NP, then can every problem in P be reduced in polynomial time to it?

Note: The linked question asks the converse problem - does there exist a problem outside NP that cannot be reduced to a problem in NP. Indeed there are, for example the "(Non-)equivalence of two regular expressions" problem. However, from my understanding, every problem in NP can be reduced to this problem in polynomial time. Please correct me if I have misunderstood.


texts:
I wanted to clarify my understanding that both the theorems of Barron about approximating functions by neural nets are about one hidden layer net. Is this right?

Is there any Barron's theorem for high depth neural net?

Is there any lecture notes or such which gives a detailed exposition of the Barron's theorem? I only found this, https://dl.dropboxusercontent.com/u/27883775/wiki/math/pdfs/barron1.pdf


texts: Minimal Spanning Tree vs Minimum Spanning Tree

texts:
I got confused about minimal and minimum in context of graph theory.
Although, I have understanding that minimal means more than one minimum i.e. none qualifies as actual minimum so we say them minimal.
What exactly does minimal spanning tree mean? Also, what exactly does 'minimal edge' mean?
How do they differ from minimum spanning tree?
How are 'minimal edge' different from minimum edge?
This doubt arose due to the statement:
S: There exists a minimum weight edge in G, which exists in every minimum spanning tree of G.
Can we say on using word 'minimum' it's implied that there is only one minimum weight edge. Besides, statement used "exists" which is singular.


texts: An n-dimensional index where the search key specifies an exact match on certain dimensions?

texts:
I'm working on a project where I want to to search for vectors in the form (x1, x2, x3,...xn), and be able to search for them by specifying a specific x value and getting all vectors with that x value for that dimension. The value n, the number of dimensions, will be 4 or 5 in most cases.

For example, if I have a vector (1, 5, 9, 3, 7), I would want to be able to find such a vector by searching in the index with a search key specified as (*, *, 9, *, *), where * is a wildcard, and finding that vector and all other vectors with the value 9 in the 3rd position.

The reason for doing this is that I am building a path index for a graph database, where I precompute a large number of paths in a graph of length 4 or 5. These paths I store as vectors, where the first index in the vector specifies which path this is, and the remaining items specify the id of the nodes along that path.
 You can you use this to quickly answer graph queries such as:

"MATCH (person)--[likes]-->(food)--[madeBy]-->(company),

RETURN person, food, company".

You determine what ID you assigned the [likes],[madeBy] path, search in the B+tree for this ID, and now you have all the nodes on that path.

However, if you delete a specific food node from the graph, finding the relevant nodes in the B+Tree is not possible, since you don't know which paths it could be in. Therefore, finding it is O(n) in the index. You can also look at that node in the graph and compute all the paths it is in, which is another option I am looking in to, but it would be nice if there was a way to do this in the index itself. Such as, if you deleted a node with ID 5,  for a 5-dimensional index you could perform deletions: (*, 5, *, *, * ), (*, *, 5, *, * ), (*, *, *, 5, * ), (*, *, *, *, 5).

I appreciate any insight anyone has. Multi-dimensional indexing is new to me, and I have limited time to complete the project.


texts:
I have a file with a list of non-overlapping rectangles covering the entire space (they are adjacent). I would like to plot efficiently the graph edges that connect each rectangle center point with the adjacents rectangle center points. Which is the best data structure to use to load the rectangle list? Which is the best algorithm to find all the adjacent rectangles in x and y directions?

Thank you.

More details:
In the picture below a visual example with 12 axis-aligned rectangles. The red paths are the desired output.

The numbering is from the random order in the input file:

rect1   (19,0)  (23,19)
rect2   (0,3)   (4,16)
rect3   (8,17)  (11,19)
rect4   (8,6)   (19,17)
rect5   (0,0)   (11,3)
rect6   (4,3)   (15,6)
rect7   (4,6)   (8,8)
rect8   (15,3)  (19,6)
rect9   (11,0)  (19,3)
rect10  (0,16)  (4,19)
rect11  (4,8)   (8,19)
rect12  (11,17) (19,19)

The desired output is the adjacent combinations of rectangles and their length:

(1,4) (1,12) (1,8) (1,9) (2,5) (2,10) (2,11) (2,7)
(2,6) (3,4) (3,12) (3,11) (4,6) (4,7) (4,8) (4,11)
(4,12) (5,6) (5,9) (6,7) (6,8) (6,9) (7,11) (8,9) (10,11)


texts: How to quickly determine whether a poset is a lattice?

texts:
Recently I encountered an interesting problem while studying discrete mathematics:

Give the pseudo code to judge whether a poset $(S,\preceq)$ is a lattice, and analyze the time complexity of the algorithm.

I am an algorithm beginner, and I am not familiar with various advanced algorithms. I have no idea about this problem at present, but I have some thoughts as follows:

Partially ordered sets can be transformed into Hasse diagrams, the algorithm to solve this problem may be a graph-related algorithm.
To determine whether a poset is a lattice, each pair $\{a,b\}$ in the poset must be considered, so will it be a graph traversal algorithm?

Could you provide some specific ideas for this problem? Or even further, could you give the corresponding pseudo code?
Thank you in advance for your help!


texts: What will be minimum no of operation to make whole matrix zero if one is allowed to multiply a row or column by zero?

texts:
Suppose we are given an M×N matrix, with some elements are zero, some non-zero. We know the co-ordinates of non-zero elements. Now, if I am allowed to multiply a whole row or a whole column by zero one at a time what will be minimum number of operations (i.e multiplications) I will need. For example, for the matrix

$\begin{pmatrix}
    0 & 1 & 0 \\
    0 & 0 & 0 \\
    1 & 0 & 1
  \end{pmatrix}$

the answer is two. For this example

$\begin{pmatrix}
    1 & 1 & 1 \\
    0 & 0 & 1 \\
    0 & 0 & 1
  \end{pmatrix}$

the answer is two not three.

Any help to go for head start is appreciated.


texts:
Ok, I dont understand whats the difference between:
write code for stack operations and write adt for stack operations?
lets say the operation is push() and pop(). So what different code is to be written for adt?


texts: How to Convert from Decimal to Qm.n format

texts: How would you convert decimal 0.0650 to 1.15 Q format 16-bit of course? I'm kinda stuck in this for 3 days, can someone kindly help me out in this


texts: Is "promoting a key" a part of deleting internal node key in B+ Tree?

texts:
I was trying to learn B+ tree deletion operation and trying to contrast it with B tree deletion operation. However barely any book provided detailed step by step B+ tree deletion operation. So I was referring B+ tree key deletion from here.

The page says deleting 15 from this:

yields this:

Thus this somehow demotes key 13 to its right child and promotes key 11 to its parent. I do not find "promoting" any key specified in the B+ tree deletion algorithm given on the same page.

In step 4 of the B+ tree deletion algorithm on the same page, it says:

  If the node has too few keys to satisfy the invariant, and the next oldest or next youngest sibling is at the minimum for the invariant, then merge the node with its sibling; if the node is a non-leaf, we will need to incorporate the “split key” from the parent into our merging.

If I am not wrong, if we follow this step, it should yield something like this:

So is the example wrong? I am not able to confirm as I am not able to find precise step by step procedure. The steps given on this page sounds a bit fuzzy.


texts:
I am trying to find an algorithm for finding an optimal solution to a puzzle of a given format. The 7 by 6 puzzle board is made out of the following pieces:

The tears are as follows:

Tears and grommets can be rotated and moved around the board, but spools, tie-offs and blockers cannot.

A simple example of the puzzle in it's starting state is:

While a more complicated version and a possible solution is:

The puzzle is scored by how many pieces are used in the solution (more is better) and how quickly the puzzle is solved.

I have so far written functions to detect and read in the board, as well as a function to check that the board is valid.

In order to solve the board, I have so far tried a brute force method, which randomly shuffled and rotated the movable pieces in the puzzle and then checked if the result was a valid solution, but this was fairly slow even for the simple boards, and extremely slow for more complex boards, and of course, did not come up with an optimal solution.

I then refined it a bit by excluding obvious wrong piece placements, but this was still over a second for small boards, and anywhere from 5 to 30 seconds for larger boards, and was also not an optimal solution.

I have heard about possibly using various path finding algorithms such as Djikstra's or A* but I'm struggling to see how these algorithms can be used to find the longest valid path, especially when branching pieces such as the 'T' and '+' pieces come into play.

Any help would be much appreciated!


texts:
There is a class of DP related problems where you have a set of consecutive steps, say $1 \ldots n$, and two places e.g. $A$ and $B$.

At each step $i$ there are two choices: stay where you are or change. Whatever you choose you pay a cost $A_i$ or $B_i$ depending on where you are, anyway if you change you pay also an addition that is usually a constant value.

For example, in Kleinberg's problem 6.4 you have two cities (New York and San Francisco), a set of $n$ months, a moving cost $M$ and two sequences of operating costs: $N_1 \ldots N_n$ and $S_1 \ldots S_n$. A plan is a sequence of $n$ locations, such that the $i$-th location indicates the city in which you will be based in the $i$-th month. The cost of a plan is the sum of the operating cost of each of the $n$ months, plus a moving cost of $M$ for each time you switch cities. You have to find a plan of minimum cost.

You eventually approach such problems using two variables. For example defining $OPT(i,j)$ with $i \in \left\{1\ldots n\right\}$ and $j\in \left\{N,S\right\}$ as the cost ending up in month $i$ at $j$ city .
$$
OPT(i,N) = \min\left(N_i + OPT(i-1,N), N_i + OPT(i-1,S) + M \right)
$$
$$
OPT(i,S) = \min\left(S_i + OPT(i-1,S), S_i + OPT(i-1,N) + M \right)
$$

At the end of the process, solution is given by $\min\left\{ OPT(n,N), OPT(n,S) \right\}$.

This is pretty straightforward, but i perceive it as a pragmatic way. How may we prove that two variables are strictly required here? Is there any particular property related to this class of problems?

I'd like to know also if there is a way for solving it with a different recurrence with a variable only, or why if it is not possible.


texts: Determine whether there exists a path in a directed acyclic graph that reaches all nodes without revisiting a node

texts:
For this I came up with a DFS recursion.

Do DFS from any node and keep doing it until all nodes are Exhausted. I.E. pick the next unvisited node once you cannot keep recursing.

The element with the highest post number or the last element you visit should be the first element in your topological ordering.

Now do another DFS recursion that executes on every node called DFS_find:

DFS_find(Node):
    if (node has no neighbors):
        return 1;
    otherwise:
        return 1 + the maximum of DFS_find(Node) for all neighboring nodes

Execute DFS_find(Node) on the first node in your topological ordering. If it returns a number equal to the number of vertices, then a directed path that crosses every node once, exists. Otherwise it does not.

How can I prove whether or not this algorithm is correct?

I think this may be a little less time efficient than the classical way to just do a topological sort and then check if each consecutive pair has an edge between them.


texts: Is stack based memory allocation memory allocated at run time or compile time?

texts: In stack-based memory allocation: is memory allocated at compile time? If so, then how can we allocate space for, say, n number of recursive calls made during the execution of the program?


texts: Are most metaheuristic algorithms different metaphors for the same method?

texts: Most times I encounter this random metaphors for metaheuristic optimization they seem like a modified genetic algorithm to me. What do you think? Is there a way to remove the analogies/metaphors to better compare algorithms?


texts:
Given a full tree $\ T = (V, E, w) $ I need to find the path with maximum length from root $\\ s $ to any of the leaves.
I was thinking I could use some sort of BFS. Because I'm looking for maximum length path, I must go through all of the edges of the tree and I will start at the vertex $\ s $. So I'll use a dictionary $\ lengths = \{\} $ where each vertex in the $\ lengths $ dictionary is a key and its value is the total length from $\ s $ to that vertex. Then I'll just choose a the leaf with the highest value. From what I've seen online the solution to the problem is actually using Shortest path for DAG and multiply lengths by $\ -1 $ and the multiply back once algorithm finish. So not sure if my solution is ok?
Thanks,
EDIT: added proposed solution
 weights = {}

 def max_path(root, w):
     if root in weights:
        return weights[root]
     else:
        weights[root] = w + max(max_path(root.leftchild, root.weight), root.rightchild, root.weight))


texts: Is the complexity of this algorithm O($\sqrt{n}$) or linear?

texts:
Let's say I have two identical jars and I want to find the height that the jars will breaks when dropped from various heights. I can drop the jars from height increments using steps on a staircase. I want to solve this problem sublinearly.

I decided to increment using square numbers (1, 4, 9, 16..etc) for a complexity of O($\sqrt{n}$), where n is the number of steps on the stairs, so I know that I have an upper and lower bound once the first jar breaks. If the jar breaks at 16, I know that the height that it breaks at is between 9 + 1 and 16. If I were to run the algorithm linearly (on the second jar) from 10 to 16, would this make my algorithm linear?


texts: Looking for memory-efficient way to detect hash collisions

texts:
Given a hash function H, it's possible that H(a) = H(b) = c

Let's assume we have a big data set [N1 ... Nk], with K items and we hash each item in this set

After operation is done, we'd get a set of hashes [H1 ... Hm] where m < k, meaning we had collisions

What would be the most memory-efficient way(without storing all of hashes and hashed items) to determine if we've ever hashed item X before and if we did, did it collide with anything?

Is it even possible to relax memory constrains on such kind of task?


texts: If A is polynomial time reducible to B does that imply not(A) is polynomial reducible to not(B)

texts:
$A\leq_p B \iff \bar{A}\leq_p \bar{B}$ (if A is polynomial time reducible to B does that imply that complement of A is polynomial reducible to complement of B)

I was told that this is the case based on the definition of $\leq_p$ but I am having trouble proving this.


texts: Localizing a plane in 3-D using distance geometry

texts:
Assume that I have a set of coplanar points $P = \{p_1, p_2, ... , p_n\}$
The equation of the plane is unknown.
$\forall p_i,p_j \in P$, pairwise euclidian distance $d(p_ip_j)$ is known.

And I have a set of points of whose coordinates are known $Q = \{q_1, q_2, ..., q_m\}$

If I know some of the pairwise distances $d(pq)$ $p \in P$, $q \in Q$;

At least how many $d(pq)$ distance measurements do I need to find the equation of the plane that points in $P$ lie on?


texts: What is a good design for expanding opcodes?

texts:
Are there any tutorials on YouTube or good text tutorials on designing expanding opcodes? I always make mistakes on switching from one line to another and "counting" in binary. I pretty much know how to design them, but I don't really understand it and I make so many mistakes. I also don't have any examples to go by and check my answer.
Here's one example of what kind of designing and exercises I need:
Design 1 three-address instruction, 10 two-address instr, 7 one-address instr and 4 zero-address instr. The addresses are 8 bits each and 2 bits for an instruction (style: 00 xx yy zz)

So I went about doing designing it like this:

00 xx yy zz

00 00 yy zz
00 01 yy zz
00 10 yy zz
00 11 yy zz
10 00 yy zz
10 01 yy zz
10 10 yy zz
10 11 yy zz
11 00 yy zz
11 01 yy zz

11 10 00 zz
11 10 01 zz
11 10 10 zz
11 10 11 zz
11 11 00 zz
11 11 01 zz
11 11 10 zz

11 11 11 00
11 11 11 01
11 11 11 10
11 11 11 11

and the last one is all 1s so I guess it's correct. Maybe if there are no tutorials on YouTube, someone can simplify it or explain it here in text?


texts:
Assuming a problem has complexity $O(3^{n/3})$,

Which is its class of complexity ?

Despite that it is not as $2^{n}$ ,we can say  is an exponential ?


texts:
In the book Operating System Concepts, it is said that:

  A claim edge $P_i \rightarrow R_j$ indicates that process $P_i$
  may request resource $R_j$ at some time in the future.

[emphasis added]
Here one can assume two different things from this line:

$P_i$ may request for $R_j$ in the future, but we don't know about it.
We know that $P_i$ will request for $R_j$ in the future.

We know that resource allocation graph algorithm comes under Deadlock Avoidance under which it is clearly stated that:

  An alternative method for avoiding deadlocks is to require additional
  information about how  resources are to be requested.

Which clearly means that we should know processes' requests in advance. Therefore the second assumption fits.

Now, it is stated in the book that:

  When a resource $R_j$ is released by $P_i$, the assignment edge $R_j
 \rightarrow P_i$ is reconverted to a claim edge $P_j \rightarrow R_j$.

But this would mean that we're sure that $P_i$ will request for $R_j$ in the future. But this would only be in the case when $P_i$ requests for multiple instances of $R_j$. But, this isn't given. So, why do we reconvert the assignment edge back to a claim edge?


texts: Is there a name for a useful Turing-like machine that is more powerful (meaning accepts more languages) than a Turing machine?

texts:
Disclaimer: I'm a software engineer with only an undergrad education and have never published or anything so please forgive any minor notation or jargon blunders - but of course feel free to point them out because I want to learn.

When I was in school for CS undergrad one of my professors explained that there are more languages than Turing machines.  This irked me (Are there questions (languages) than answers (algorithms) in the world?) until I realized that Turing machines can be generalized to fix this discrepancy so that all Languages have a corresponding machine:

Suppose I have some language $L$ that has no corresponding Turing machine.

I will define a Unit Turing Machine ($UTM$) to be a Turing machine that accepts only 1 string and rejects all others.  So the language of $UTM_0$ is $\{0\}$, $UTM_1$ is $\{1\}$, $UTM_2$ is $\{10\}$, etc.  There's a $UTM$ for each non-negative integer that corresponds to the binary representation of that integer as the single string it accepts.

Note that $L$ is a language so it is a subset of all finite-length binary strings, so $L$ can be enumerated (although if it were finite it would have a Turing machine, so it's countably infinite).

So let's say we had some enumeration of $L=\{l_0,l_1,l_2,...\}$.

Let's say I map elements in $L$ to their corresponding $UTM$ so that I now have a set of $UTM$ and call it myTuringMachineList.  Since $L$ is countable, so is the mapped myTuringMachineList.

Now I can perform the following pseudocode algorithm on myTuringMachineList to decide input string input:

function computeTheUncomputable(myTuringMachineList, input)
{
    found := false;
    i := 0;
    while not found
    {
       j := 0;
       while not found and j <= i
       {
           // executes the jth myTuringMachineList Turing machine
           // through i steps with input input.
           result := execute(myTuringMachineList[j], input, i);
           if result = accepted // could also be rejected or undecided
           {
              found := true;
           }
           j++;
       }
       i++;
    }
}

I think this approach is called dovetailing.  Every string in the "un-acceptable" language $L$ will now be accepted in a finite amount of steps through this algorithm, which I think can execute any countable finite set of Turing machines in parallel.

While this algorithm seems like it would be a Turing machine itself, it relies on having access to this infinite list of Turing machines (and a way to execute them as a black box), which effectively allowed me to construct a more powerful Turing-like machine that has an infinite number of states and transition rules...  By breaking out of finite-ness to my states and transition rules I gained something useful: languages I could not otherwise accept in a finite amount of steps.  Although this implementation suffers from the inability to reject in a finite number of steps.

My question is: Is there a name for a useful Turing-like machine (such as the one described above) that is more powerful than a Turing machine?  Alternatively, if has someone already given this proof (or an analogy or more generalized version) then that reading that would probably tell me what they called their machine and answer my question.


texts: Decidability of fullness of intersection of a CSL with a regular language

texts:
Let $L_r$ be a regular language with alphabet $\Sigma$ and $L_{\text{csl}}$ be a context sensitive language. Are any of the following questions decidable?

$L_r \cap L_\text{csl} \stackrel{?}{=} L_r$
$\Sigma^* \cap L_\text{csl} \stackrel{?}{=} L_r$
$L_r \cap L_\text{csl} \stackrel{?}{=} \Sigma^*$
$\Sigma^* \cap L_\text{csl} \stackrel{?}{=} \Sigma^*$

I understand that (1) implies the others. I am also looking for any "near variants" that might be decidable.


texts: If A is mapping reducible to B then the complement of A is mapping reducible to the complement of B

texts:
I'm studying for my final in theory of computation, and I'm struggling with the proper way of answering whether this statement is true of false.

By the definition of $\leq_m$ we can construct the following statement,

$w \in A \iff f(w) \in B \rightarrow w \notin A \iff f(w) \notin B$

This is where I'm stuck, I want to say that since we have such computable function $f$ then it'll only give us the mapping from A to B if there is one, otherwise it wont.

I don't know how to phrase this correctly, or if I'm even on the right track.


texts:
I developed an algorithm that can prune down neural networks while retaining most of the accuracy. For example, it can take a trained neural network (relu activation functions) with a hidden layer of 200 nodes and an output layer of 10 nodes and prune the 200 node large hidden layer down to 10 nodes while bringing the accuracy from about 97% down to an accuracy of about 82% with zero additional retraining after pruning. It does this by modifying the weights of the remaining nodes to preserve the information of the nodes that are being removed.
I have three questions for people who are familiar with this type of thing.
First, are there any algorithms that you know of that already exist that can do this? I couldn't find any when searching online. Second, is there any real practical use for this? Third, if it actually is original, and I can find some practical use for it, is it worth trying to publish somewhere?


texts: Does real linear programming produce bipartite perfect matching using maxflow reduction?

texts:
Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram:

We can formulate max flow as an linear programming problem  with integer variables in latter.

If we do not use integer variables does solving for maxflow in linear programming formulation with only real variables still produce valid perfect matching of given graph?

Is there a formal proof of this?


texts: Randomly choose vector b in range such that $\vec{a} \cdot \vec{b} = 1$

texts:
Given

I have a $n$ dimensional $\vec{a}$.
All elements of $\vec{a}$ are between 0 and a positive number $K$.
$n$ is about 15 to 20.

Problem

I want to randomly and unbiasedly choose a vector $\vec{b}$ such that:

Elements of $\vec{b}$ are between 0 and 1.
$\vec{a} \cdot \vec{b} = 1$

How to do that?

Attempt

I thought about the following:

Choose $\vec{c}$, a random direction perpendicular to $\vec{b}$.
Find range of $\theta$ such that $\vec{b} = \frac{\vec{a}}{\lVert \vec{a} \rVert} + \theta\vec{c}$ is within bounds.
Randoly choose a $\theta$

The problem is that this is not unbiased. Some directions have a larger range of legal $\theta$, and those directions should be chosen more often.


texts: Does randomness make exponential difference?

texts: Schwartz–Zippel lemma can solve the polynomial identity testing in expected poly-time. As far as I know, there is no deterministic poly-time algorithm for the problem, but we do not know if the problem is NP-hard or not, right? Is there any NP-hard problem that can be solved in expected poly-time using a randomized algorithm? What are the consequences if such a thing exists?


texts: Proof for Unusual QuickSort Partition Scheme

texts:
TL:DR
I wrote code for a QuickSort variant. It seems a bit off from original QuickSort. Can anyone tell me why and how this works? Is it a quicksort?

The following is code I wrote for a middle pivot quicksort for a high school class of AP CS.

It works for some reason. I've also found a few versions that are same or similar to this. But I'm not sure if this is the same thing as the Hoare implementation scheme. I've tried to analyze it but found out it was quite different from the quicksort I knew of -> which takes form of: elements smaller than piv | piv ~ piv | elements greater than piv. But this one acts like elements not greater than piv | elements not less than piv. Elements that are equal to the pivot can end up anywhere in between. But it works. Is this even quicksort?

public static void middlePivSort(int[] a, int start, int end) {
    if(start < end) {
        int i = start - 1;
        int j = end + 1;
        int m = start + (end - start) / 2;
        int v = a[m];

        while(true) {
            while (a[++i] < v);
            while (v < a[--j]);

            if (i >= j) break;

            swap(a, i, j);
        }

        middlePivSort(a, start, j);
        middlePivSort(a, j + 1, end);
    }
}


texts: Big-O notation for the given function whose runtime complexity grows faster than the input

texts:
I struggle to determine the runtime complexity of a function I thought of while trying to solve this LeetCode quiz. The quiz itself goes like this:

Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 are the first 11 ugly numbers (n=1 up to n=11). On the other hand, 14 does not classify as an ugly number because it has the factors of 2 and 7. The same goes for 33, which has factors of 3 and 11.

If hypothetically, I come up with a function isUgly(i) which can determine whether a given number classifies as an ugly number in O(1) time, I can just brute-force it by testing for every number from 1 to infinity. What would be the algorithmic complexity of such implementation the with respect to the value of n?

int nthUglyNumber(int n):
  nth = 1
  for i = 1..INFINITY:
    if (isUgly(i)):
      nth++;
    if (nth == n):
      return nth;

boolean isUgly(int i):
  # a function that runs in O(1) time that can determine
  # whether a number classifies as an ugly number by returning true / false

The function will return 12 for n=10, and 1536 for n=100 and based on our brute force implementation the function has to iterate 12 and 1536 times to come up with those answers.

We can generalise that if the function returns x for some n, it will have to iterate x times. Therefore, is it acceptable to conclude that this function runs in O(fn(n)) time?

NOTE: There exist a more efficient solution to the problem but that is not what I'm interested in. I am here to understand how to describe the algorithmic complexity of the definition above.


texts: What is meant by $\operatorname{poly}(|F|, n, e)$?

texts:
When I am reading a paper I found a notation $\operatorname{poly}( |F|,n,$$\frac{1}{\epsilon}) $.
Its not clear to me that what this notation represents. Can you please help me out?


texts: What language should the following DFA recognise?

texts:
My question is: what language should the following DFA recognise?

It seems that it should contain an odd number of substrings in the form 11*0. However, I am not sure whether there are any other conditions.


texts: Which of the following problems can be reduced to the Hamiltonian path problem?

texts:
I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:

  Assume that P ≠ NP. Consider undirected graphs with nonnegative edge
  lengths. Which of the following problems can be solved in polynomial
  time?

  Hint: The Hamiltonian path problem is: given an undirected graph with
  n vertices, decide whether or not there is a (cycle-free) path with n
  - 1 edges that visits every vertex exactly once. You can use the fact that the Hamiltonian path problem is NP-complete. There are relatively
  simple reductions from the Hamiltonian path problem to 3 of the 4
  problems below.

  For a given source s and destination t, compute the length of a shortest s-t path that has exactly n - 1 edges (or +∞, if no such path
  exists). The path is allowed to contain cycles.
  Amongst all spanning trees of the graph, compute one with the smallest-possible number of leaves.
  Amongst all spanning trees of the graph, compute one with the minimum-possible maximum degree. (Recall the degree of a vertex is the
  number of incident edges.)
  For a given source s and destination t, compute the length of a shortest s-t path that has exactly n - 1 edges (or +∞, if no such path
  exists). The path is not allowed to contain cycles.

Notice that a Hamiltonian path is a spanning tree of a graph and only has two leaf nodes, and that any spanning tree of a graph with exactly two leaf nodes must be a Hamiltonian path. That means that the NP-Complete problem of determining whether a Hamiltonian path exists in a graph can be solved by finding the minimum-leaf spanning tree of the graph: the path exists if and only if the minimum-leaf spanning tree has exactly two leaves. Thus, problem 2 is NP-Complete.

Problem 3 is NP-Hard; here is a paper that proves that.

That means, between 1 and 4, one is NP-Complete, another is in P. It seems like problem 4 reduces trivially to the the Hamiltonian path problem, but I'm not able to understand how having a cycle makes it solvable?


texts:
I have 2 search algorithms and I have derived the following tight bound representations:

$$ nlog(n)+mlog(n) $$

$$ m∗n $$

Now i want to find a function $f(n)$ so that when $m$ is an element of tight bound $f(n)$, both algorithms have equal asymptotic run time.

Now I'm not sure if its just as simple as setting the two equations equal to each other and isolating 'm' or of it is more than tha


texts: Travelling salesman problem with detours

texts:
I am interested if there exists a following version of the travelling salesman problem:

INSTANCE: A finite set $C = \{1,2,\dots,k\}$ of cities, a positive integer distance $\delta(i,j)$ for each pair of cities, and two positive integers $d$ and $B$.
QUESTION: Is there a tour that visits every city in $C$, includes exactly $d$ detours, and has total length no more then $B$?  In other words, suppose $OPT$ is the optimal permutation of the cities; that is, $OPT(i)$ is the next city after city $i$ in an optimal traveling salesman tour.  Is there an ordering $x(0), \dots, x(k-1)$ of the cities such that $$\sum_{i=1}^{k} \delta(x(i), x((i+1) \bmod k)) \leq B$$ and there are exactly $d$ indices $i$ where $x((i+1) \bmod k) \ne OPT(x(i))$?

The $d$ implies that if my shortest tour is $a\rightarrow b \rightarrow c\rightarrow a$ but $d=1$ then what would be the shortest path if I had to first go to $c$, $ a \rightarrow c \rightarrow ...$. So $d$ tells me that I have to make $d$ number of wrong choices but I can choose these choices in any way I want to to minimize the length of the path.
Is this a problem worthwhile describing? Or if it has been described where could I see an example?


texts: How do you write a python\pseudo code that generates all pair permutations?

texts:
What would be a good pseudo code or Python 3 code for the following permutations problem?
Let us define a n-permutation as a bijective function $\pi: \{0,...,n-1\}\rightarrow \{0,...,n-1\} $ and represent it using a list, meaning that $\pi(i)=j $ iff list[i]=j. Let us also define a pair permutation as a permutation in which for every $ i\neq j , \thinspace \pi(i)=j \Leftrightarrow \pi(j)=i $ .
I need to write a recursive function code, that takes an interger n, and generates all n-pair permutations (every permutation appears, and only once).
[This question appeared on a test, that it's solution remains confidential :(  ]


texts: Machine code: How can an OS prevent user-level programs from accessing each other's memory?

texts:
Okay, I’ve done a lot of research on this, but I can’t seem to wrap my head around it. Essentially, the question is as follows: How can an operating system prevent a machine instruction from a user-level program (Firefox, Word, etc.) from accessing memory locations that it isn’t supposed to access?

Here’s what I think I understand so far: Machine code, as you would for example find it in a .exe file after building your C/C++ program, is a sequence of binary instructions. These instructions can run directly on the CPU (assuming that the program was compiled for that CPU’s instruction set, e.g. x86). So, you don’t technically need an operating system to “run a program” in a broader sense – which isn’t surprising, since an operating system is just a program itself. Also, the CPU doesn’t work in terms of “programs” or “processes”, but in terms of individual instructions.

Now, if we do have an operating system (e.g. Windows), part of its job is to assign an encapsulated memory segment to each running user-level program (e.g. Firefox, Word, my own C++ program, …), and to make sure that they can’t read/corrupt each other’s memory.

This is where things get fuzzy for me. If I were to write my own operating system (or other bare-metal program), I would need to be able to use machine instructions to read/write to and from any existing location in the entire memory, right? So, how does an operating system make sure that no user-level program sends such instructions to the CPU on its own, without “asking the OS for permission” to access a certain memory location?

I would actually love to learn more on the entire topic of going from high-level code to machine instructions. For instance, I would also like to understand what user-level program threads and OS-level processes look like on bare-metal, etc. So, if anyone could point me to a good resource, that would be highly appreciated. Nonetheless, this isn’t the core of my post, just a side note.


texts: How to prove that the probability that a random graph has a stable set of size $2\lceil \log n\rceil$ is sub-constant?

texts: Given a random graph on $n$ vertices where each edge is included with probability $1/2$. Lets call it $G=(n,1/2)$. How can we show that the probability that this graph has a stable set of size at least $2\lceil \log n\rceil$ is sub-constant?


texts:
We know that computing a maximum flow resp. a minimum cut of a network with capacities
is equivalent; cf. the max-flow min-cut theorem.

We have (more or less efficient) algorithms for computing maximum flows, and computing a minimum cut given a maximum flow is neither hard nor expensive, either.

But what about the reverse? Given a minimum cut, how can we determine a maximum flow?
Without solving Max-Flow from scratch, of course, and preferably faster than that, too.

Some thoughts:

From the minimum cut, we know the maximum flow value. I don't see how this information helps the standard approaches augmenting-path and push-relabel, although adapting the latter seems slightly more plausible.
We can not use the minimum cut to split the network in two parts and recurse since that won't shrink the problem in the worst case (if one partition is a singleton); also we would not have a minimum cut of the smaller instances.
Does knowing the value of the maximum flow speed up solving the Max-Flow LP, maybe via the complementary slackness conditions?


texts: Why does response time increase with throughput?

texts:
I'm seeing this pattern that the response time increases as throughput increases, and that the throughput has a peak after the response time starts rising. This seems counter-intuitive. It seems like as the response time starts to rise, the throughput should flatten out due to queuing or simply exhaustion of resources.

Is it related to synchronization? More clients, more threads etc.

Why does this happen?

Here's an example from oracle:

And a few more from google searches:


texts: Binary subtraction with numbers in 2's complement

texts:
How can i perform binary subtraction of two numbers that are already in 2's complement?
I have to subtract 01010011 from 10100110,both numbers are in 2's complement.
I know that 10100110 is -90,and 01010011 is 83,so the result should be -173.
So if i use 8 bits that means that there's overflow.
But i don't get how can i perform the subtraction when both the numbers are in 2's complement.
If i just perform the subtraction i get the same number 01010011. How do i show the result and that there's overflow?


texts: constant factor of strassen's algorithms

texts:
Many references say that the large constant term is hidden in the calculation of the time complexity of the Strassen algorithm.

I want to know how the huge constant term is constructed or how it is calculated mathematically. (assuming when n matrices are given)

You can add more matrix constraints to help with the solution.

Thank you


texts: If parity is set to be 1 then how to check for error bit in hamming code without knowing the if the parity is even or odd?

texts:
A seven-bit Hamming code is received as 1110101. What is the correct code? Assume the parity to be one.
The problem I am facing here is I don't know how to check parity without knowing it is even or odd.


texts:
Here's an old puzzle: Let $s$ be a string of decimal digits ($s[i] \in \{0,\dotsc, 9\}$). Define a function $f(s)$ as follows:

Interpret $s$ as a decimal number, $n_{10}$, and convert $n$ to its octal equivalent, $m_8$.
Now treat $m$ as a decimal number, $m_{10}$ and convert it to its hexadecimal equivalent, $h_{16}$, and return its hex representation as a string.

For example, if $s= \langle245\rangle$ we would have $245_{10} = 365_8$ and $365_{10} = 163_{16}$ so in this case, $f(\langle245\rangle) = \langle163\rangle$. Similarly, $f(\langle155\rangle)=\langle \mathrm{E}9\rangle$

What are the fixed points of $f$? In other words, for which digit strings $s$ is $f(s)=s$?

I have a few questions about this puzzle:

It's not hard to show that $\{0,\dotsc, 7, 64,\dotsc, 69\}$ are all fixed points. Are these the only ones? I have a proof that they are, but it's inelegant, basically showing that after a certain point, $p(s) < s$, or $p(s)$ isn't a decimal string. Does anyone have a nicer proof, for some value of "nicer"?
I've spent more time than I should in a so-far futile search for a reference to this problem. Does anyone have one? All I know is that it's decades old.


texts: What are the disadvantages of having many registers?

texts: IA-64 is an architecture that has 128 general purpose registers, are there any disadvantages (beside being more expensive and larger instruction size) to having many registers?


texts: Streaming maximum pair matching with limited memory

texts:
I am trying to find as many pairs of elements as possible from two distinct data streams, while being constrained by the number of elements I can hold in memory at any given time. Once a pair of elements is found, it can be removed from memory.
This problem feels like a streaming variant of the maximum coverage problem, except that I'm trying to figure out the optimal strategy for determining which elements I should keep and which ones I should prune when a new element arrives and my data structure is at its maximum capacity.
More generally, I would like to find which classical problem this can be reduced to.
A more formal phrasing of my question would be : given two streaming multisets of integers $S_1$ and $S_2$ and a positive integer capacity $C$, what is the optimal strategy to find the maximum number of pairs of identical integers from $S_1$ and $S_2$ such that at any point, the number of integers in memory is less than $C$ ?


texts: Is it decidable whether a given context free grammar generates an infinite number of strings?

texts: Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or not, we can write a program that would test this but would not halt. So it should be undecidable. Is this so?


texts:
I have multiples arrays. I'd like to enumerate all sets containing exactly one item from each array in a (pseudo-)random order, without explicitly building the array of all sets.

Any solution, even with poor pseudo-randomization, is welcome.

EDIT: Example for clarity:

Say I have arrays

A = { a1, a2 }, B = { b1, b2 }, C = { c1 }

I want to enumerate all the sets containing exactly one ax, bx and cx

{ a1, b1, c1 }, { a1, b2, c1 }, { a2, b1, c1 }, { a2, b2, c1 }

I want to enumerate them in a random order. The naïve solution would be to enumerate them in an array, then shuffle this array. But the solution is huge and I don't want to store it explicitely in memory.


texts: Is this possible: In OOP, private methods in a class form a F-coalgebra and public methods in a class form an F-algebra?

texts:
I recently found out that OOP classes turn out to be F-coalgebras:

https://www.semanticscholar.org/paper/Objects-and-Classes%2C-Co-Algebraically-Jacobs/c7c45abf7d99e0aef627fd5223023bf82e70dc71

  The coalgebraic perspective on objects and classes in object-oriented
  programming is elaborated: objects consist of a (unique) identifier, a
  local state, and a collection of methods described as a coalgebra;
  classes are coalgebraic (behavioural) specifications of objects. The
  creation of a 'new' object of a class is described in terms of the
  terminal coalgebra satisfying the specification

In here,
https://stackoverflow.com/questions/16015020/what-does-coalgebra-mean-in-the-context-of-programming the top answer's author describes this class

class C
  private
    x, y  : Int
    _name : String
  public
    name        : String
    position    : (Int, Int)
    setPosition : (Int, Int) → C

as a coalgebra like this:

data C = Obj { x, y  ∷ Int
             , _name ∷ String }

and the public methods like this

position ∷ C → (Int, Int)
position self = (x self, y self)

name ∷ C → String
name self = _name self

setPosition ∷ C → (Int, Int) → C
setPosition self (newX, newY) = self { x = newX, y = newY }

My question is this: Is it possible to actually define the public methods as an F-algebra?

Would this make an OOP class actually a bialgebra like described in here?
https://www.researchgate.net/publication/220976988_Categorical_Programming_with_Abstract_Data_Types

  The main idea is to represent an ADT by a bialgebra, that is, an algebra/coalgebra pair with a common carrier

Which would explain why so often classes are used to define abstract data types in OOP languages?


texts: PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it

texts:
I know the grammar for the language $\{ xy : |x| = |y|, x ≠ y \}$ if $\Sigma=\{a,b\}$:

$$
\begin{align*}
&S→AB∣BA \\
&A→a∣aAa∣aAb∣bAa∣bAb \\
&B→b∣aBa∣aBb∣bBa∣bBb
\end{align*}
$$

I know this is a grammar, but I need a PDA for this language, and intuition how $\{xy: |x|=|y|,x \neq y\}$ is a CFL while $\{xy: |x|=|y|,x=y\}$ is a CSL but not a CFL. How is this possible?


texts: How to learn Bayesian Network's parameters using KL divergence and stochastic optimization?

texts:
I have a problem to resolve:

A Bayesian Network structure is given to me, with a dataset of values for each variable. I also have a set of queries, like P(A=1 | B=0) or P(L=0, B=1 | C=1).  The goal is to find the parameters of the model.

The first task was to use the frequentist approach. So, for the first query P(A=1 | B=0) we would simply go through the dataset and count how many times (A=1 & B=0) and divide it by how many times (B=0). That was easy.

The second task is to use KL divergence and stochastic optimization to find the parameters. I understand that we want to find Theta = argmin_theta(KL(Pr || Ptheta)). For that, we will go the opposite direction of the gradient of KL, with a step k. I know that to compute the gradient, I can compute the Expectation with respect to Pr of (x - Sigmoid(theta)). x being the value of the current variable. I also have the expression of the expectation.

I get the idea that we want to minimize the gradient of the KL divergence because we want to minimize the difference between our prediction and the truth.

What I don’t understand, is how I’m going to use the structure of the network, the queries, and the dataset to achieve that. I think I’m a bit confused to the end result we really want.

I hope my explanations were not too confusing. If you have any insights I’d take it.

Victor


texts: What is the time complexity of the piece of code given below

texts:
int IsPrime(n)
{
    int i, n;
    for (i=2; i<=sqrt(n);i++)
        if(n%i == 0)
            {printf("Not Prime \n"); return 0;}
    return 1;
}

Here the loop executes for $ \Theta (\sqrt{n}) $ time . But my teacher said that it is not  because the lower bound is $ \omega (1) $ I was not able to understand why it so .

Q1] Could some of you explain which one of us is right justifying reason ?

Q2] What is the importance of  " return 0 " ? What would have been the change if there had no " return 0 inside looping function ?

Q3] In general What is the meaning of return 0, 1, -1 in C programming language ? I have read this from stackoverflow but that didn't solve . Need little bit explanation


texts:
We have alphabet $\Sigma = \{ { a, b} \} $.

How to construct CFG for language $\Sigma^{\ast} - \{a^{n}b^{n} | n \ge 0 \}$.

I suggest that is very easy, but I can't invent. I know PDA for this language if it can help.


texts: Are two states equivalent in a DFA if on the same input the states transition to each other?

texts:
Suppose you have three states in an DFA $q_{1}$, $q_{2}$ and $q_{3}$, all non-accepting. Suppose $a$ and $b$ are two symbols, such that:

$\delta(q_{1},a)=q_{2}\\ \delta(q_{2},a)=q_{1}$

and

$\delta(q_{1},b)=q_{3}\\ \delta(q_{2},b)=q_{3}$

Are the states $q_{1}$ and $q_{2}$ considered equivalent?


texts: Why is the Nintendo Entertainment System (NES) referred to as an 8-bit system, rather than a 1-byte system?

texts:
As far as I've understood it, referring to this system as an 8-bit system points out that one can access 8 bits of data in one instruction.

While I understand that we're not saving vast amounts of time by calling it "one byte" instead of "eight bits", is there a particular reason why the latter is/was preferred?


texts: Unambiguous CFG for $a^ib^j$ where $i \le j \le 2i$

texts:
could you please help me for finding an unambiguous CFG for the following expression:
$a^ib^j$ where $i \le j \le 2i$


texts:
As I understand, Decision graph is a directed graph where each vertex is a "Question" (decision to make), and each edge is an "Answer" (decision made for the vertex this edge is coming from). The terminal nodes of that graph is a solution.

Problem: With this structure - each "Answer" can lead only to a single consequent "Question". However in my real-world problem "Answer" can lead to multiple consequent "Questions".

What is the right data structure and algorithms for such kind of decision making , finding optimal solution problems.


texts: Why $\operatorname{gap-A}[1.5a, 1.5b + 1/4]$ has an efficient solution?

texts:
Let $0<a < b<1/2$. Suppose that there's an efficient $a/b$-approximation for $A$, where $A$ is a maximization problem. Why does $\operatorname{gap-A}[1.5a, 1.5b +1/4]$ also has a polynomial solution?

We've learned in class that if $gap-A[a,b]$ has a polynomial solution then there's a $\frac{a}{b}$ approximation. That is,

$$\frac{a}{b} opt(x) \le val(y_x) \le opt(x)$$

So let's assume by contradiction that $\operatorname{gap-A}[1.5a, 1.5b +1/4]$ is hard.
Then, there's no polynomial time $\frac{1.5a}{1.5b + 1/4} $-approximation algorithm.

$$\frac{1.5a}{1.5b + 1/4} = \frac{a}{b+1/6}$$

Then, $gap-A[a,b+1/6]$ is hard to decide, but that doesn't help with reaching a contradiction.

EDIT:
We define for a maximization problem $A$ the decision problem $\operatorname{gap-A}[a,b]$ as:

Let $Y$ to be the set of solutions for $x$.

for a given $x$, the algorithm needs to decide:

there's a $y_x\in Y$ such that $y_x > b$.
for every $y_x\in Y$: $y_x < a$

If $x$ is not in one of the above the result could be arbitrary.


texts: Are problems in NP decidable in polynomial time by NDTMs, or just recognisable?

texts: So if we have a problem in NP, does that mean that we can create, by definition, a NDTM that always accepts or rejects in polynomial time?  The alternative I'm thinking of would be if the NDTM could only be guaranteed to accept in polynomial time.  Rejecting could take longer or forever.


texts: counterexample for this graph isomorphism algorithm

texts:
I'm trying to learn about graph isomorphism and I stumbled upon coloring. When given 2 graphs, you give each vertex a color according to properties of their neighbors and any vertex on graph 1 can only map to any vertex on graph 2 with the same color. This way you cannot have false negatives (if the algorithm says there's no mapping, it is so) but you may have false positives. So now I'm looking for a false positive of my particular graph isomorphism coloring algorithm.

We're going to assign each vertex a "breadth" and a "color", which are both strings. Assume both graphs have n vertices.

Step 1: we assign depth=0. We pick a starting vertex and assign it
(breadth, color) = ("0;","0;").
We assign a set S={that vertex}.

    Step 2: depth++;
    set T=[all neighbors that don't have a color yet of all vertices in S].

        Step 2.A: for each vertex in T, name it t and set t.breadth = depth + ";"

        Step 2.B: for each t in T:
        t.breadth += '[' + (concatenate all colors of all
        neighbours of t that are in S, in lexicographically sorted order) + '];'

        Step 2.C: for each t in T:
        t.color = t.breadth + '{'+(all breadths of all neighbours
        of t that are in T, concatenated in lexicographically sorted order)+'}'

    Step 2.D: S=T; goto step 2 unless T is empty.

Step 3: Save the resulting coloring, clear S and T and the coloring and
repeat from step 1 for *each possible starting vertex for both graphs*.

Step 4: We now have n colorings for both graphs. Deduce if this leads to a
negative. If not, for now assume that the graphs are isomorphic.

A bit of explanation on step 4: Suppose I pick a starting vertex for graph 1, we need to look at each starting vertex for graph 2. If a starting vertex for graph 2 then leads the exact same number of colors for each color of graph 1, we have possible vertex mappings from graph 1 to graph 2. If this is also the case for another starting vertex of graph 2, we have extra mapping possibilities. with 1 starting vertex for graph 1, we look at all starting vertices from graph 2 and union the results together.

When looking at another starting vertex for graph 1, we get another set of mappings. Each starting vertex of graph 1 leads to a set of mappings, and we're looking at the interesection of those sets. If that intersection is empty, the graphs are not isomorphic.

Now, I'm looking for two graphs for which this algorithm says they're isomorphic, while they're not.

I'm assuming that the graphs are connected.

Note that the colors might grow exponentially large this way, but we can avoid that by replacing parts with placeholders.


texts: Context Free Grammar for $\{0^n1^n \mid n \geq 0\}^*$

texts:
Give a context free grammar for the following language over $\Sigma = \{0,1\}$:
  $ L = L_1^* $
  where $ L_1 = \{0^n1^n : n \geq 0\}$.

Not really sure where to start with this one. Any help is appreciated


texts:
We know about calculability of a function or computability. We looks for the ability to solve a specific problem / compute a function with calculus method.

But if we define a calculus method, is there a way to find generals limits of the method  ?

Can we say that if the method can give same results as logical connective/operators, this method would solved anything computable by logical operators ?

EDIT :

I an other way the question could be : How can we define the "computation power" or "computability space" of a method (Turing machine, logical operators, lambda cacul, celular automaton, etc....) ?


texts: Master Theorem: How to find the value of b in this recurrence relation

texts:
The master theorem is used with recurrences of the form T(n) = aT(n/b) + f(n) where a >=1 and b > 1, in which case the value of b can be easily seen from the recurrence, however I have a recurrence of the form

T(n) = T((n/4)+3) + f(n)

How do I get the value of b in this case?

This question Particularly Tricky Recurrence Relation (Master's Theorem) is the only thing I found that has a similar case with T(n/4 +1) but gives no detail about how the b was calculated.


texts:
Consider Ford–Fulkerson algorithm (FF).

Look to wiki :

  The following example shows the first steps of Ford–Fulkerson in a flow network with 4 nodes, source A and sink D. This example shows the worst-case behaviour of the algorithm. In each step, only a flow of 1 is sent across the network. If breadth-first-search were used instead, only two steps would be needed.

In practice this example does not work, because each vertex has fixed (determenistic) order of outgoing edges.

We've introduced simple test for "determenistic order of edges" with number of pathes $2^{n/4}$.

At beggining of FF you may shuffle all the edges. After it during the algorithm the order of the edges is immutable. The optimization breaks our simple test with $2^{n/4}$ pathes, but there is another test with subexponential number of pathes: $2^{n/(8logn)}$. More precisely: probability that "number of pathes is $2^{n/(8logn)}$" over all $m!$ shuffles of $m$ edges seeks to $1$ with $n$ seeks to $\infty$.

Look more to wiki:

  Non-terminating example

If you use dfs with deterministic order of edges (as in practice!) then FF always terminates. Even for graphs with real capacities of edges.

Our question.
Do you know papers, books, lection notes, which contain such tests and the proof of the proposition "FF, implemented via dfs, always terminates"?


texts: How to measure the degree of randomness in Disk I/Os?

texts:
Most disk-based system's performance heavily depends on its disk access patterns. So maximizing the sequential I/Os while avoiding the random I/Os is a typical goal in performance perspective.
I am working on the same problem.

I have some difficulties in measuring the degree of randomness of Disk I/Os. I can measure the disk throughputs in MB/sec using the performance monitoring tools. However, MB/sec is a result of such and such possible causes including the disk access patterns. I want to directly measure how much random disk I/Os are occurring at a certain moment.

Is there any metric that is commonly used to represent the degree of randomness in Disk I/Os?

If there is, how can I measure those?


texts: A data structure for holding numbers in 2 sets, using BST?

texts:
Design a data structure for holding numbers in two sets:

Init - initiate the DS with two empty sets. O(1)

Insert(a,S) - insert number a to set S (S could be X or Y). O(log(n)). (n is the total number of numbers in the DS)

Find - find a number a in the DS such that the number of numbers in X that are smaller than a equals the number of numbers in Y that are bigger than a, if exists such number. O(1)

My attempt is using 2 augmented balanced binary search trees, each one presents set X or Y, insert into it the new number and saving in each node information for finding what is the number of numbers in X that are smaller than this node and the number of numbers on Y that are bigger than that node.

But given that information how could I implement the Find procedure in O(1)? Or maybe someone have better design (preferably using augmented BST)?


texts:
From classical results of universal simulation of Turing machines there exists a Universal Turing machine simulating any Turing machine with time complexity () in time ()log().
Is there is an analogue for circuits? Since circuits can only accept a fixed input size it would only be able to simulate circuits that can be encoded as that input size; so, considering such a set of circuits (or a set of circuits that makes more sense) can the circuit efficiently simulate these?
ex: you can simulate polynomial time Turing machines with polynomial size circuits, can you simulate polynomial size circuits with polynomial size circuits (something like this)?


texts: Regular expression - every b preceded and followed by an even number of a's

texts:
I'm trying to write a regular expression over the alphabet $\{a, b\}$ for the language in which every $b$ is preceded and followed by an even number of $a$'s.

I think the regular expression should include something like $((aa)^*b(aa)^*)^*$ but I don't know how to extend it in order to get to the correct form. Can anyone help me by providing a step-by-step solution?


texts: Select the maximum number of links to satisfy per-link constraint. How to prove is NP-hard?

texts:
I asked, incorrectly, my previous question here. I would like to thank D.W. for his answer though. He answeres that the problem is polynomial time solvable. The thing is that the cited paper shows that it is NP-hard. So I corrected my question. But I don't understand, am I missing something? In the paper, as shows the figure (page 2, right column in the paper), the authors says:

They show that that problem is NP-hard.

So here is the new question.

Instance: A matrix of size $n\times n$ of non-negative real numbers $\mathbf{G}=\left[g_{ij}\right]$, a positive number $k\le n$, and a positive number $\tau$ and a positive number $\epsilon$.

Question: Is there a subset $S$ of $\{1,\ldots,n\}$ of cardinality $|S|\geq k$ such that

$$\dfrac{g_{ii}}{\epsilon-g_{ii}+\sum\limits_{j\in S}g_{ij}}\geq \tau,\text{ for all } i \in S.$$

Can you see a simple, direct reduction from an NP-hard problem?

Note.  This problem is studied in wireless communication where the set represents links in a wireless network, the $g_{ij}$ represents the powers and the constraint represent a quality of service guarantee.

I believe a more general problem is proven NP-hard, see for example paper, but the reduction is very hard for me.


texts: Longest path in directed graph cyclic graph where each node has one children

texts:
Consider given directed unweighted cyclic graph with $N$ nodes, and $N$ edges, and each node has at most one out-going children. Find the longest path.

Example

Consider the following graph, the path $2, 3, 1$ is the longest covering all 3 nodes.

What I think for the solution

Because every node has at most one children we form some type of equation that for node $a$, and it's children $b$, the path starting from node $a$ = path to start from $b + 1$, but I think because there are cycles this wont work.


texts: Is one of the Advantages of AI symbolic systems the fact they are good at abstraction and modularity according to Minsky and Papert?

texts:
I was reading Perceptron's by Minsky's and Papert's book and there is a part where they discuss symbolic systems and one part of it says:

  Symbolic systems yield gains of their own...Above all else they offer
  us the prospect that computers share: of not being bound by the small
  details of the parts of which they are composed.

I am having issues knowing if I understand this. It seems that the fact that "Symbols" point to "ideas" and the small details don't matter resonates with the idea of abstraction. Furthermore the fact that one of these "Symbols" might be composed of others resonates with modularity.

Is this what Minksy's and Papert were after in that paragraph? Its just not clear to me. What advantages of computers are they referring too?


texts: How many bytes of memory is used just to "acknowledge" that a certain file is a .jpg?

texts:
I'm rather new to computers and how they work in the microscopic scale, but here's the little bit that I know.

  Computers have lots of transistors in them, both in memory and processor, and each transistor has two states, on and off. They are translated to binary equivalents 0 and 1. All data is stored in computers as combinations of 0s and 1s. Each 0 or a 1 is called a bit, and 8 bits make up a byte. A single byte is too small so units like kilobytes, megabytes, and gigabytes are more common.

I know that .jpg images occupy some memory in the computer, usually in the orders of kilobytes. However, the computer must know that the 0s and 1s that make up the image are for the image, and the computer must acknowledge this. In order to inform the computer that these 0s and 1s are assigned for a .jpg image, there must be a few bytes of data to inform that the rest of the bytes are a part of the image file. How many bytes would just acknowledging the file type take?


texts: What is OUTER UNION and why is it partially compatible

texts:
I am trying to understand how a OUTER UNION $∪^✳$ works, and why it is only partially compatible.

I am aware this operation was created to take union of tuples from two relations if the relation are not type compatible (which I understand).

Examples of this operation will be great!


texts:
The Cook-Levin theorem shows that any NP problem is reducible to an NP-complete problem.

Therefore if a polynomial-time algorithm for an NP-complete problem is found, it will mean that all problems in NP can be solved in polynomial time.

But If an NP problem is shown to have an exponential lower bound, would that prove that P != NP?


texts:
Is $L=\{ xyx \mid x,y \in \{a,b\}^* \text {and } |x| \ge 1 \}$ context-free?
If yes, please explain how we can write grammar or create a PDA for it. If not a CFL, then prove it through pumping lemma.

I have tried to apply the pumping lemma with $w = a^nb^naba^nb^n$ as the word in $L$, but without success.


texts: no of ways to fill a row (1xN grid) with a set of 1D bars with some constraints?

texts:
Given a row of length N, and a set of 1D bars having lengths A[1...M], how many ways I can fill the row?
A is an integer array,
the bars are having dimensions $\{1\times A_1,1\times A_1,1\times A_1,..., 1\times A_M \}$
The row can also be considered as $1\times N$ grid.

2 Bars with equal length has to be considered as 2 distinct bar not 1.
 Bars are same from either direction, so just by reversing bars there wont be any new arrangement
A bar can be placed with a maximum of 50% out of grid(on either side of grid) PROVIDED ALL BARS ARE HAVING EVEN LENGTH

Example :
$N=4,\space A=\{2,4\} \\
Answer=6 $

Explanation : consider strings to represent bars are XX and YYYY
Now six arrangements will be
$$\\
XYYY \\
X\_YY \\
XXYY \\
YYYX \\
YY\_X \\
YYXX \\
$$

Except the last condition rest is already solved here in previous post


texts: How can I prove that a complete binary tree has $\lceil n/2 \rceil$ leaves?

texts:
Given a complete binary tree with $n$ nodes. I'm trying to prove that a complete binary tree has exactly $\lceil n/2 \rceil$ leaves.
I think I can do this by induction.

For $h(t)=0$, the tree is empty. So there are no leaves and the claim holds for an empty tree.

For $h(t)=1$, the tree has 1 node, that also is a leaf, so the claim holds.
Here I'm stuck, I don't know what to choose as induction hypothesis and how to do the induction step.


texts: Does Amdahl's law apply to modern multi-code processors?

texts: I was reading about Amdahl's law and it state that value of Amdahl's law always lies between 0 and 1. My question is, is it still true in today's case/scenario? When we have system like core i7?


texts: Showing that a bijection preserves homomorphism

texts:
I have the vocabulary $\tau = \{+, 0 \}$ and the structure $R = (\mathbb{R}, +^R, 0^R)$ where $+^R$ is a binary function symbol representing the normal addition of numbers and $0^R$ is the constant $0$ in $\mathbb{R}$. I 'm trying to prove that the bijection $$\sigma : \mathbb{R} \rightarrow \mathbb{R} \text{ with } \sigma(x) = -x$$
is an automorphism of $R$.
What I (think I) only need to show: the homomorphism property for each function symbol, in this case  $$+^R : \sigma (x +^R y) = \sigma(x) +^R \sigma(y) \ \forall x, y \in \mathbb{R}$$ holds. We don't need to worry about $0$, since it's covered by our bijection's definition.
So, the homomorphism property seems to work for every $x$ and $y$ I pick, for example:
$$\sigma(1+^R1) = \sigma(2) = \sigma(1) +^R \sigma(1) = -1 +^R -1 = -2$$
$$\sigma(2+^R1) = \sigma(3) = \sigma(2) +^R \sigma(1) = -2 +^R -1 = -3$$
etc.
We can't prove by induction because we're not working in $\mathbb{N}$. Can anyone show me or give me a hint how I can formally prove this for all numbers in $\mathbb{R}$?


texts: Problem with understanding the Mathematical Equations related to Testing Tool

texts:
I have downloaded the slides from the site:
[Compliance and Violation Patterns
It says No writes after calls. I can understand this concept. It’s a remedy for reentrancy problem. But it shows compliance and security patterns in some technical language related to Datalog or to some language related to software representation. Can some body please guide me what is the meaning of those equations?

Zulfi.


texts:
On the circulation problem page on wikipedia, the multicommodity circulation problem formulation seems to be insufficient, since we can just set all but one flow to $0$, and reduce it to a circulation problem.

I can't find any concrete description of multicommodity circulation problem to verify the correctness. There is only one paper I can find and it's behind a pay wall.

Here is a formulation I thought to make more sense:

Let $G=(V,E)$. $l_i,u,c_i:E\to \mathbb{R}$ for $1 \leq i\leq n$. We want to find a sequence of flow function $f_i$, such that:

$$
\begin{align}
\text{min} & \sum_{(v,w) \in E} c_i(v,w)f_i(v,w) \\
\text{s.t.} & \sum_{(v,w) \in E} f_i(v,w) = 0 \text{ for } 1 \le i \le n, v \in V, \\
& l_i(v,w) \leq f_i(v,w) \text{ for } 1 \le i \le n, (v,w)\in E\\
& \sum_{i=1}^n f_i(v,w) \leq u(v,w) \text{ for } (v,w)\in E\\
\end{align}
$$

Is this a formulation of multicommodity circulation problem?


texts:
I am master student, and I work on project with camera tracking based on sphered Infrared (IR) markers.

Now I have to implement multi-camera calibration system with a wand like this one:

And I want to find out the details of each step, understand it.

My cameras has IR filter, and it helps to discard another information (example of image, it is not a calibration wand on a photo):

To find a center of sphere (actually, the projection of sphere will be  ellipse in general case):

Find countours;
Fit the ellipse to contour;
Calculated weighted center of fitted ellipse

$\bar{u}=\frac{\sum_{i=1}^{n}\sum_{j=1}^{m} u_iw_{i,j}}{\sum_{i=1}^{n}\sum_{j=1}^{m} w_{i,j}};$

$\bar{v}=\frac{\sum_{i=1}^{n}\sum_{j=1}^{m} v_jw_{i,j}}{\sum_{i=1}^{n}\sum_{j=1}^{m} w_{i,j}};$

where $u_i$ - x coordinate of pixel, $v_i$ - y coordinate of pixel, $w_{i,j}$ - gray-scale value of pixel.

But what do I have to do after that? I just don't know how to connect pinhole camera matrix with this centers. I know that:

$\lambda m_1=K_1[R_1T_1]M$ and $\lambda m_2=K_2[R_2T_2]M$,

where $m_i=[u_i,v_i,1]$ - coordinate on pixel map, $K%$ - intrinsic parameters of camera, $R$ - rotation matrix, $T$ - translation matrix, $M=[X,Y,Z,1]$ - coordinate in 3D world.

Also I have to include distortion model, but I miss the chain, which connect general matrix model with these centers of spheres.

I also can let, that these 3 IR markers have $Y=0, Z=0$, because they are situated on the line. Is it true assumption?

If you refer me to any book, paper or something, I will be very glad of it.


texts: How to define an automata for zig zag concatenation?

texts:
I have two DFAs one for language A and one for language B.
I'm asked to make an FDA that is the zig-zag concatenation of letters of A and letters of B.
This is described by the following: {w: w = $a_1 b_1$...$a_k b_k$ and $a_1...a_k \in A$ and $b_1 ... b_k \in B$}. With $1 \leq i \leq k$ and $a_i \in \Sigma$ and $b_i \in \Sigma$

This automata should be described as a 5-tuple {Q, $\Sigma$,$\delta$,$q_0$,$F$}.

I simply do not know how I would go about defining the total function $\delta$.

This is what I tried:

$Q = Q_A \cap Q_B$ // We only want the words that contains both a and b

$F = F_A \cap F_B$ // The accepted states should contain both letter from a and from b.

$q_0 = q_A$ //because the word starts with a letter from a.

$\Sigma$ // in this problem we aren't interested in defining the alphabet we just leave the symbol as is in the 5-tuple.


texts: Show that $A_\mathrm{LBA}$ is PSPACE-Complete?

texts:
I want to show that $A_\mathrm{LBA}$ is PSPACE-Compelte.

Say we proved it is in PSPACE. Now for PSPACE-HARD:

I had an idea, which was very similar to some solution i found on the web- say we have a TM M which decides some language A in PSPACE. Then given an x in A we can simulate M on x to determine the number of steps M makes.

Suppose the above simulation is defined as another TM M' and k steps are needed for M to run x.

Build a TM M'' which simulates M on "x, $space^{\mathrm{k}}$" - the word x concatenated with k spaces. return (M'', "x, $space^{\mathrm{k}}$")

What i don't understand - the input is only x and its length is |x| so how do we know that simulating M on x is poly-time(x) ? we don't know the size of the description of M, which must be fed to the single-tape LBA M''.

How come all the solutions i've encountered don't even mention that the size of the description of M might not be poly-time(x) ? then we have that the mere writing of M on M''s tape might be more than poly-time(x). (?)

No relation is given between |x| and |M| (the decider for A) because the input is only the word x...


texts: Defunctionalization and known arity function calls by pointer

texts:
Defunctionalization is nice for higher order functions where it is completely necessary to avoid runtime support, but in some cases it's favourable to use function pointers instead (since they don't generate huge code bloat for certain scenarios, i.e.):

data Foo a = Foo (a -> Int)

Under what conditions is it safe to implement higher order calls using function pointers instead of reducing them to huge switch tables of static calls?

My initial thought is that it has something to do with known arity.


texts:
The following question is in my homework:

  Is the statement $f(n) = O(g(n))$ true, when $f(n) = n/2 + 4$ and $g(n) = \sqrt{n} + 2\log_2 n + 3$?

I understand how $f(n)$ is the upper bound of $g(n)$. However, I am unsure how to prove it mathematically.


texts: Context-free grammar for $ \{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, l \geq \min(n,m)\}$

texts:
I know that $L = \{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, (l ≥ n) ∨ (l ≥ m)\}$ is a context-free language, because I know the context-free grammar, i.e.
$$
S \rightarrow AbZ \mid XBc \\
A \rightarrow aAb \mid X \\
B \rightarrow aBc \mid Y \\
X \rightarrow aX \mid a \\
Y \rightarrow bY \mid b \\
Z \rightarrow cZ \mid c
$$
I have a bit of difficulties understanding this construction. Can you explain step-by-step how it has been created? The rules?


texts:
I have a 20-dimensional dataset, with a large amount of data points. I would like to have each dimension discretized into bins. Per bin, I would like to be able to access two neighbours per dimension (i.e. +1 and -1 per dimension). Basically I want to be able to easily access 2*d (where d is the dimensionality) neighbours. For lower dimensions, this would be quite easy to do using a multidimensional array (i.e. for point data[0][1][2] I would access its neighbours data[0][1][3] and data[0][1][1] for the third dimension). However, when this approach is scaled up to higher dimensions, memory becomes an issue.

What kind of data structures would be suitable to use, where the most important criterium is the quick and easy access to its +1 and -1 neighbours?


texts: Intuition behind min cut in a flow network? Whether it's baseball elimination or project selection

texts:
I was wondering if someone can give me a general definition of a min-cut besides it being the max flow of a network.

For example, in the baseball elimination problem, if we wanted to find out if team z is eliminated, the min cut represents the team(s) that will beat team z out of the 1st place if the edges aren't full saturated. If the edges are fully saturated, then min-cut is everything except t, and team z still has a chance.

For the project selection, the min cut contains the projects you should do to maximize your return.

How do people figure out that min-cut can be applied to these problems? What is it about min-cut that gives it such power?

Thank you!


texts: Q: Calculating a MPI cluster throughtput from hardware latencies

texts:
Since i don't have a CS background in my career,
Built up an openmpi compute platform which succesfully computes from a variable number of available nodes. call this whole, a mpi cluster having N^2 4-Core-CPU + 16-OpenCL-1.1-compute-cores with a reasonable compute power each node.

I have no experience in parallel optimizations of algorithms thus i've processed diferent segments of a  in 'distances' from a norm (semi-random parameters with a regular metrics).
Current online setup is 2-node each 4*2600Mhz + 16*1440Mhz for solver and a network bandwidth of 1 Gigabit/s per node switched at 1Gb/s.
1. How would one integrate a computation time from a series of latency values delivered from each node such as the sum of all hardware latencies involved.
2. Do i need a quadratic time solver feeded with latencies to get a 'deviation' or something like that? many thanks.


texts: Good introduction to Turing's work and complexity theory?

texts:
I'm currently an undergrad whose been amazed by what Turing has done for the world. I know there are plenty of other amazing individuals, but Turing's work specifically has always sounded the most interesting to me and I'm finally at the point where I can understand some of it. So my question is, where do I really begin to dive into his work? I have yet to take an official theory course, but I'm determined enough to go through important works that will help me get where I need. I'm currently reading his 1936 thesis and I find it mostly understandable, but I want to go deeper into the mathematics behind it all.

On a similar note, I think what I overall am interested in is complexity theory. I have some experience with basic abstract algebra, and some mathematical maturity. Can anyone list some books/papers to read, some introductions and some deeper, that can help me fully understand the implications of some topics, i.e. P=NP? How T.M.s were and are currently being used as foundational tools to prove and disprove ideas? I realize these are vague questions, but I want people to suggest books/papers that have been most influential to them that are related to these topics (or any other influential reads that one might have).

If I said anything incorrectly please feel free to correct me!


texts: Hierarchy of complexity classes $\bigcup_{c > 0} \mathrm{Time}(2^{c \log^k n})$, w.r.t. $k$

texts:
This is a true/false question:

  For each integer $k > 1$, define the complexity class $\sf QP_k := \bigcup_{c > 0} Time(2^{c \log^k n})$. Then for all integers $k > 1$, $\sf QP_k \subsetneq QP_{k+1}$.

I have to prove it is true, or I have to give a counter example as to why it is not true.

I am having a lot of difficulty understanding the notation and also how to approach this problem. My understanding is that $c$ is some constant and effectively doesn't matter.

Edit: I guess I am unclear about how c and k work, the c seems like it doesn't matter so  its asking us if there is every a point where from k = 2 to k = infinity if there will ever be a situation in which $2^{c \log^k n}$ = $2^{c \log^{k+1} n}$ for all c and n.

Is this the right interpretation?

I cannot find a single counter example that would make this true for any k, so it must be true. I am not sure how I would go about proving this is true.


texts: Minimally extend a tree such that there are no bridges in the new graph

texts:
We are given an undirected tree on which we should add the minimum number of edges such that there are no bridges in the new graph.

An edge $e$ is a bridge if the graph with that edge removed is no longer connected.

For example, here is a tree with 8 nodes

1 2
2 3
3 4
4 5
3 6
3 7
3 8
At least three edges should be added. For example: (1, 6), (5, 7), (8,4)

In very small graphs we can brute force all possible new edges. However, this is too slow for bigger trees. I tried making some observations but I couldn't find anything that could solve the problem.

This problem is the task "NET" from Baltic Olympiad in Informatics 2015.


texts:
How do we classify formal systems' (propositional logic, first-order logic, second-order logic,  higher-order logic, Hoare logic and type theory) expressivity?

In the same way that grammars (CSG, CFG, ...), languages (CSL, tree-adjoining language, ...) and abstract machines (Turing machine, ...) 'fit' into the Type 0-3 range of the Chomsky hierarchy, can we also classify the formal systems into it?

Or, is there another yardstick for describing the relative expressive power of formal systems?


texts: For regular languages A and B, determine whether B might match early in (A B)

texts:
I have two regular languages A and B, and I want to determine whether there is any pair of strings, a in A and b in B, such that (a b) is a prefix of a string in (A B) and the left-most match of B in (a b) includes one or more characters from a.

Raphael's formulation is good:

  Given two regular language A, B, is there a (non-empty) prefix of a word b in B that is a suffix of a word in A so that the rest of b is a prefix of another word in B?

Example

For example, let's say I have two regular languages, one which describes some properly escaped HTML text, and one which describes an end tag:

A := ([^&<>] | [&] [a-z] [a-z0-9]+ [;])*;
B := "</title";

By inspection, I can tell that there is no string (a b) in (A B) such that the first match of B includes characters from a because "<" is a prefix of B which cannot occur as a suffix of A.

But given a different grammar:

A' := (A | "<![CDATA[" ("]"? ">" | "]"* [^\]>])* "]]>")*;
B' := "</title" ([^>\"] | [\"] [^\"]* [\"])* ">";

then there are strings

a = '<![CDATA[</title "]]>"';
b = '</title>';

where (A B) matches '<![CDATA[</title "]]>"</title>' and the left-most match of B is '</title "]]>"</title>' which includes a non-empty suffix of a : '</title "]]>"'.

Motivation

A in my situation describes the output of an encoder/sanitizer that is derived from a grammar, so an untrusted input is fed to the encoder/sanitizer and I know the output matches A by construction.

B is a limit condition in a larger grammar that describes how parsers determine where a chunk of an embedded language ends so they can hand it off to a parser for the embedded language.

My end goal is to be able to determine when I can optimize away runtime checks that ensure that it is safe to embed a particular encoded string.  For these examples, it would be safe to optimize out the first check, but not the second.

Is this a solved problem?  Does it have a name?  Any pointers appreciated.


texts: Why is this expression (A and ¬A |= C) entailed?

texts:
Hopefully I am posting this in the right place, I am currently in a course of knowledge representation, and I came across an exercise about entailment:
$$A\land\neg A\vDash C\,.$$

I would argue that this expression is not entail, but it is actually entailed, but I don't see how, can you help me figure out why?


texts: Does a function distribute over lists or does it commute with them?

texts:
Assume that we have an operation $f$ such that
$$
f([a_0,\ldots, a_n])= [f(a_0),\ldots,f(a_n)]
$$

Do we say that $f$ distributes over lits or do we say it commutes with lists?
Which one is the correct way of expressing this property?

How about the following?
What do we say for the relation between $f$ and $\vec{a} = a_0,\ldots,a_n$?
$$
f(g(\vec{a})) = g(f(\vec{a})) = g(f(a_0),\ldots,f(a_n))
$$


texts: Why is Computer Architecture in $2^n$ bits?

texts:
I have always wondered why is computer architecture in $2^n$ bits. We have 8 / 16 / 32 / 64-bit microprocessors or for that matter other parts of computer are also in power of 2 bits.

The only logic I could understand from my reasoning is that usually computer design process starts from lower amount of bits. For example : Say I want to design a Full adder to add 16 bit numbers. So I would first design a digital circuit to add 2 bits (one from number A and other form number B). Then I would replicate this circuit 16 times. So this will give me 16-bit full adder.

Is my reasoning correct ? Is there some other reason also ?


texts: What's the accurate definition of a compiler?

texts:
Wikipedia:

In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language).

This implies that the compiler can also convert from a low-level language to a high-level language. But this has also got a specific name decompiler.
So what should be the definition for a compiler? 1) or 2)?

In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language).

A compiler is a computer program that translates computer code written in a high-level programming language into a low-level language.


texts: Maximum Chromatic number of Cayley Graphs with large degree

texts:
It is known that there does not exist a regular graph of order $n$ with clique size greater than $\lceil\frac{n}{2}\rceil$. My question pertains to Cayley graphs with large degree, say $\ge \frac{n}{2}$ and not complete. I think the maximum chromatic number is $\lceil\frac{3n}{5}\rceil$. As an example of a graph attaining the attaining the upper bound, we consider the complete graph with order divisible by $5$ and remove a $2$- factor. The two factor we remove is the disjoint union of $\frac{n}{5}$ $5$-cycles. Then, the chromatic number is $\frac{3n}{5}$.
Are there any Cayley graphs with degree $\ge\frac{n}{2}$, and not complete, such that their chromatic number exceeds $\lceil\frac{3n}{5}\rceil$. And, also, are there other Cayley graphs with chromatic numbers between $\lceil\frac{n}{2}\rceil$ and $\lceil\frac{3n}{5}\rceil$


texts:
Let us say that our definition of a circuit is the one of a boolean circuit from [Vollmer].
He uses directed acyclic graphs to represent circuits where the computation nodes are labeled with some functions which come from a set of possible operations (called basis).

Let us say that we only allow the operation $\land$ for our circuit (i.e. the basis only consists of $\land$). Is $x \land x$ a circuit if $x$ denotes an input gate?  I don't think so, because the input gate $x$ is only allowed to occure once in the graph and then we would need two edges to the $\land$-node, i.e. we would need a multigraph. A way around would be to force a basis to have an identity operation. For instance using the basis $\land, id$ we could of course build the $x \land x$ circuit (this is also the case if we can build the identity operation in any other way, e.g. if we have $\neg$ in our basis) even though we have to increase the size of the circuit by using $id$. It seems very counterintuitive that such a simple circuit is in fact not a circuit over the basis $\land$, so is my reasoning correct?

[Vollmer] Heribert Vollmer, Introduction to Circuit Complexity


texts:
In our operating systems class, the teacher told us about deadlocks prevention methods. One of them is that to select as a victim the process which requires the CPU time or one that requires a lot of resources, and remove this process. The next time the algorithm is called, it may be possible that again the same process becomes the victim. This causes starvation.

I'm confused: if the victim process is terminated, then how can it again become part of the deadlock?


texts: estimating optimal solution for LP with strict inequalities

texts:
I have an LP problem with strict inequalities that cannot be relaxed. I understand that most LP solvers require the problem to not have any strict inequalities as it is impossible to find an optimum for all problems.
However, is there precedent (ex. a paper or package) in allowing strict inequalities and then "stepping" towards the solution via something like gradient decent.
This would allow an estimation of the optimum (especially given the restriction of a convex polytope) with a fairly high degree of accuracy (which can be increased with more steps), which seems like it would be useful in many situations.


texts: How to XOR two binary numbers having different lengths?

texts:
If we have:

x = 1101 and y = 101

How to XORing these numbers?


texts:
I've not been able to find a precise definition of "stack depth" anywhere and have a rather simple question.

When dealing with trees I'm used to the maximum depth (or height) of the tree being the longest simple path between the root node and a leaf. For instance, if we had a longest simple path of length $n$, there would be $n+1$ nodes involved. In this case the height of the tree (or maximum depth) is $n$.

My question is, for "stack depth" and recursion, do we count the initial call to our procedure and all subsequent calls placed on the stack? Or do we exclude the initial call when counting stack depth?


texts: LALAR vs SLR Table for Given SLR Grammar

texts:
i'm so glad that ask my first question on my favorite site.

Infact i ran into multiple choice question in recent exam on Compiler Course.
Suppose T1, T2 is created with SLR(1) and LALR(1) for Grammar G. if G be a SLR(1) Grammar which of the following is TRUE?

a) just T1 has meaning for G.

b) T1 and T2 has not any difference.

c) total Number of non-error element in T1 is lower than T2

d) total Number of error element in T1 is lower than T2

My solution:

we know table size and state of LALAR(1) and SLR(1) is the same. but someone say number of reduced state in LALAR(1) is lower than SLR(1) (free space in LALR(1) is more than SLR1(1) because using lookahead instead of follow) and so (d) is correct. but in answer sheet we see (b) is correct. anyone can describe it for us? which of these is true?


texts: Trying to show if two languages are recognizable or not

texts:
I have two languages that I am trying to prove are recognizable or not:

  Let $$L_1 = \{(\langle M\rangle, w) \mid \text{$M$ is a TM that accepts $w$ and doesn't accept $\varepsilon$}\}$$ where TM is short for "Turing
  Machine", $w$ is a string, and $ε$ is the empty string.

  Is $L_1$ recognizable? Prove your answer is correct.

  Let $$L_2 = \{(\langle M\rangle, w) \mid \text{$M$ is a TM that accepts $w$ and rejects $\varepsilon$} \}$$ Is $L_2$ recognizable? Prove your answer
  is correct.

I've been having trouble with these proofs using mapping reducibility. I know that the language
$$A_\mathrm{TM} = \{\langle M, w \rangle \mid \text{$M$ is a Turing machine that accepts the string $w$}\}$$
is undecidable but recognizable. My approach is to say that
$$L = \{\langle M, \varepsilon\rangle \mid \text{$M$ is a Turing machine that rejects $\varepsilon$} \}$$
is recognizable and, knowing that recognizable languages are closed under intersection, this shows $L$ is also recognizable.

I'm not too sure about the first question, however. Is there a better approach to proving these two languages are recognizable or not?


texts: Decidability of Turing machines that never move their heads past any input string

texts:
$L_1 = \{ \langle M, w\rangle : M \text{ is a TM that never moves its head past the input string } w \}$
  $L_2 = \{ \langle M\rangle : M\text{ is a TM that never moves its head past any input string} \}$

Consider the two languages above. I want to know which ones are decidable.

I know that $L_1$ is decidable, because $M$ has only a finite amount of possible configurations with the input string $w$, so we can create a Turing Machine (TM) for to check 1 step past the number of combinations and decide.

However, for $L_2$, can we do that? I feel like $L_2$ is undecidable, because we can there seems to be no limit to the possible configurations.


texts: What is the Time Complexity of the Matrix Exponential?

texts:
While trying to compute the Matrix Exponential of an nxn array I decided to take advantage of a Python function called scipy.linalg.expm().

According to the documentation, this function adopts the Pade' Approximant to perform a calculation that, otherwise, is said to require a lot of resources and is still a matter of discussion in the mathematics community.

The documentation itself references a work by Al-Mohy and Higham (doi: 10.1137/04061101X), in which I was not able to find any indication regarding the Time Complexity (either T or Theta would work) of this procedure.

Has anyone come across the same problem? What is your suggestion for determining said Time Complexity?


texts: Can CNN be used for "unknown correlated" data?

texts:
Now the title may be misleading, but I don't know how to give it a better name.

My question is if I have data in a 2d matrix and under the assumption that:

-I know for sure that there are correlations between some of the rows and columns, but I am not sure which rows are correlated to each other so I can't pre-order it in a way that the correlated rows and columns are closer to each other.

For example, if I have 100x50 matrix: row_1 .... row_100, if row_1 is correlated to row_100 then my CNN won't capture that for sure but nevertheless, a correlation is present in the matrix.

Is there a way to capture this by CNN?

My idea is to, for eg., create new data by randomly shuffle the rows to:

1- Increase the number of data instances to the CNN (in a way its similar to increasing the image training data by randomly tilting some images).

2- This will increase the chance that the correlated rows will appear closer to each other in few of the newly created instances of data, so it can be captured by the CNN.


texts: proving {$a^ib^jc^k : j = i \lor j = k$} is not regular

texts: i had troubles proving this  is not regular using the pumping lemma {$a^ib^jc^k : j = i \lor j = k$}. Not sure how to approach this anymore, and help would be appreciated


texts:
Given a graph $G(V,E)$ with $n$ vertices labeled $1,2,...n$ and $m$ positively weighted edges $(u,v,w)$ with the condition that $u<v,$ $\forall u,v \in G$, so the graph we are considering is actually a DAG. We need to find an odd path from $1$ to $n$ that have the smallest weight median. i.e when the weights on the path are listed and sorted, the median of that list should be minimal.

Is it possible to solve this problem without enumerating all possible odd paths while maintaining a running median?

I have been trying to solve this problem for a couple of days and got stuck and solutions are not posted on the website.

Problem source: Problem G


texts: Looping through random integers - will it halt with probability 1?

texts:
Say I have a simple program that has the pseudocode like this:

min = 1
max = 100
c = 5
random = randomInt(min,max)
while(c != random):
    random = randomInt(min,max);

Theoretically, from what I understand, I cannot guarantee this will halt. However, is this true for both PRNGs and say, random integers generated using atmospheric noise? Is there a difference? And by convention, can I say this will "almost surely" halt (probability 1), but still cannot guarantee this? I'm still trying to wrap my mind around the edge case of a program with an almost sure chance of halting, and how this is viewed from a computational perspective.