texts: Does data entropy depend on the arrangement of the characters in a file?

texts: From what I understand data entropy controls the limit of data compression and it depends on the probability of the characters in the file. Assuming that we have a file of size 256 bytes containing 256 different symbols and we made a bigger file consisting of many copies of that file, And because the small file has the maximum entropy a file of its size can have, the big file will also have that high entropy (because all characters have the same probability). Although that file has high entropy it still can be compressed to a very smaller size. What did I misunderstand here?


texts: Reduction from set cover problem to vertex cover problem

texts: Although the reduction from vertex cover problem to set cover problem is quite simple, I did not find anywhere the reduction in the opposite direction. From the similarity in the type of problems, I guess this reduction should be simple too. However, despite trying for some time, I could not develop this. So, any ideas how this reduction can be done?


texts: Why would we want a self-hosting compiler?

texts: I understand that a self-hosting compiler is a compiler which can compile the code of the language that it is written in into different language but I don't understand why we would want to do that. What are the benefits (and drawbacks) of a compiler which is self-hosting?


texts: In two sets, identify set of pairs with maximal sum of connections

texts:
Given two sets of items

$A = { a_1, .., a_N }, B = { b_1, .., b_M },$

and assuming a connection weight $w{_i}_j \ge 0$ between any possible pair $(a_i, b_j)$ that contains one item of each set, how can I identify the set of pairs $S$ that maximizes the sum of all involved weights: $\sum_{S}w{_i}_j$, under the condition that any $a_i$ and any $b_j$ occurs maximally once in the new set?

Example: With $A = [a_1, a_2], B = [b_1, b_2, b_3]$, and

$w$'s from $a_1$ to $B$: $[5, 2, 1]$

$w$'s from $a_2$ to $B$: $[1, 0.2, 0.4]$

the solution is to use the pairs: $(a_1, b_1), (a_2, b_3)$ which result in the highest possible sum $5.4$, and $b_2$ is left over.

Also, is there a way to approximate the sum e.g. not optimizing further for those $w{_i}_j < threshold$?

I'm sure this problem has a name, but I'm not able to figure it out.


texts: Find shortest path in undirected graph that goes through all vertices and returns to starting vertex

texts:
I have an undirected weighted graph like this one

My task is to find the fastest path (with least weight) that goes from specified vertex goes through all vertices and returns to the starting vertex without repeating a vertex.

Graph
1 3 time 5
3 2 time 5
2 4 time 5
4 1 time 5
4 3 time 4
1 2 time 5

Starting vertex 3
Path 1: 3->1->4->2->3
Path 2: 3->2->1->4->3
Time 1 and 2: 5+5+5+5=20

Path 3: 3->1->2->4->3
Path 4: 3->4->2->1->3
Time 3 and 4: 5+5+5+4=19 -> fastest

Is there a fastest way than DFS to solve the problem?


texts: What is the optimal solution of the 1962 Procter and Gamble's TSP Contest?

texts:
In 1962, you could win a prize of \$ 10 000 (about \$ 80 000 in today's money) if you found the solution to an Euclidean travelling salesman problem defined on 33 cities.

http://www.math.uwaterloo.ca/tsp/history/pictorial/car54.html

Looking at the picture, the problem seems pretty easy. However I failed to find more detailed resources on the problem.

Does anybody know some more details, such as the exact distances and an optimal solution?


texts: k disjoint triangles with graph splitting to two distinct groups

texts:
Please note that this question is different than this question.
The $k$-disjoint triangles problem is as follows:

Input: A graph $G=(V,E)$ and an integer $k\in \mathbb{N}$
Output: Are there $k$ vertex-disjoint triangles in $G$?

An FPT algorithm is presented here (starting from slide 60). The algorithm uses color-coding and relies on dynamic programming to determine if a solution is highlighted (each vertex in the solution group is colored with a distinct color). The running time of the algorithm is $O^{*}((2e)^{3k})$.
Now, Let's assume that we get a group $X \subseteq V$ of vertices, and the problem changes: Are there $k$ vertex-disjoint triangles in $G$ where one vertex is from $X$ and the other two are from $V \setminus X$?
I need to find an algorithm whose running time is $O^{*}((2e)^{2k})$. I tried coloring all vertices from $X$ in a single color, but I couldn't find a way to avoid the duplicate choices of vertices from $X$. I also try to color each vertex from $X$ in a distinct color that is different from the colors of $V\setminus X$ but the running time is higher.
Can you propose a coloring method that will highlight a possible solution within the required complexity? Should I try something else?


texts: Recurrence relation for time complexity $T(n) = T(n-1) + n^2$

texts:
I'm looking for a $\Theta$ approximation of
$$T(n) = T(n-1) + cn^{2}$$

This is what I have so far:

$$
\begin{align*}
T(n-1)& = T(n-2) + c(n-1)^2\\
T(n) &= T(n-2) + c(n-1) + cn^2\\[1ex]
T(n-2) &= T(n-3) + c(n-2)^2\\
T(n) & = T(n-3) + c(n-2)^2 + c(n-1)^2 + cn^2 \\[1ex]
T(n-3) &= T(n-4) + c(n-3)^2 \\
T(n) &= T(n-4) + c(n-3)^2 + c(n-2)^2 + c(n-1)^2 + cn^2
\end{align*}
$$

So, at this point I was going to generalize and substitute $k$ into the equation.

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

Now, I start to bring the base case of 1 into the picture. On a couple of previous, more simple problems, I was able to set my generalized k equation equal to 1 and then solve for $k$. Then put $k$ back into the equation to get my ultimate answer.

But I am totally stuck on the $(n-k+1)^2$ part. I mean, should I actually foil all this out? I did it and got $k^2-2kn-2k+n^2 +2n +1 = 1$. At this point I'm thinking I totally must have done something wrong since I've never see this in previous problems.

Could anyone offer me some help with how to solve this one? I would greatly appreciate it. I also tried another approach where I tried to set $n-k = 0$ from the last part of the equation and got that $k = n$. I plugged n back into the equation towards the end and ultimately got $n^2$ as an answer. I have no clue if this is right or not.

I am in an algorithms analysis class and we started doing recurrence relations and I'm not 100% sure if I am doing this problem correct. I get to a point where I am just stuck and don't know what to do. Maybe I'm doing this wrong, who knows. The question doesn't care about upper or lower bounds, it just wants a theta.


texts:
I am studying for my algorithms final and came across the following problem:

Find three languages $L_1 \subset L_2 \subset L_3$ over the same alphabet such that $L_2 \in P$ and $L_1,L_3$ are undecidable.

I am having trouble coming up with an example of three such languages. My first thought was to use a form of the halting problem for both $L_1$ and $L_3$ since that is pretty much the only undecidable language I know and am familiar with. I was thinking of perhaps coming up with something of the form
\begin{align*}
L_1 &= \{M \mid \text{$M$ is a Turing machine that starts with 00 and halts}\}\\
L_2 &= \{M \mid \text{$M$ is a Turing machine that starts with a 00}\}\\
L_3 &= ?
\end{align*}
but this doesn't seem to be working.  Any ideas are appreciated!


texts: Why do Θ-bounds not survive taking differences?

texts:
$f_1$, $f_2$, $g_1$, and $g_2$ are functions such that:

$$f_1 = \Theta(f_2)$$
$$g_1 = \Theta(g_2)$$

I was able to prove that:

$$\frac{f_1}{g_1} = \Theta\biggl(\frac{f_2}{g_2}\biggr)$$

But I can't understand why the following statment is not necessarily true:

$$f_1 - g_1 = \Theta(f_2 - g_2)$$


texts: Is Monotone 3-SAT with exactly 3 distinct variables untractable?

texts:
I have given the following SAT variation:

Given a formula F in CNF where each clause C has exactly 3 distinct literals and for each C in F either all literals are positive or all literals are negated. Example:

$F= (x_1\vee x_2 \vee x_4) \wedge (\neg x_2\vee \neg x_3 \vee \neg x_4) \wedge (x_3\vee x_4 \vee x_5)$

Is this variation of SAT tractable?

My findings so far:
I suspect the problem is NP-complete and therefore not tractable. Thus I would like to perform a poly-reduction from 3-SAT to the variation described above.
An arbitrary 3-SAT formula can be converted to monotone 3-SAT.
Take following example:
$C_1=(x_1\vee x_2 \vee \neg x_3)$ and define $z_3$ by $\neg x_3 \leftrightarrow z_3$ and  $x_3 \leftrightarrow \neg z_3$ which is equivalent to $(x_3\vee z_3)\wedge(\neg x_3 \vee \neg z_3)$.
From that we get the monotone form of $C_1$ by
$(x_1\vee x_2 \vee \neg x_3) \leftrightarrow (x_1\vee x_2 \vee  z_3)\wedge (x_3\vee z_3)\wedge(\neg x_3 \vee \neg z_3)$
By applying this transformation to all clauses I get a monotone 3-SAT formula which is equally satisfiable.
My reduction produces additional 2 clauses with 2 literals for each non-monotone clause, but how do I get only monotone clauses with exactly 3 distinct literals?


texts: probability matrix from digraph adjacency matrix

texts: All I have in hand is a adjacency matrix of a digraph with equal weight on every edge, is there a very simple way to convert this to a state change probability matrix?


texts: On the time complexity of finding independent sets in hypergraphs

texts:
I am interested in the complexity of the following problems:

(a) Finding an independent set of a fixed size in an arbitrary hypergraph
(b) Finding an independent set of maximum size in an arbitrary hypergraph

It is well known that the analogues of (a)  and (b) (say (a') and (b')) for graphs are NP-complete and NP-hard, respectively. However, I am having trouble finding references for the complexity of (a) and (b). In fact, all of the papers I've been able to find on these two problems (for hypergraphs) just cite the fact that (a') and (b') are NP-complete and NP-hard, as if these results trivially generalize to (a) and (b). Is this actually the case? If not, can anyone provide references that prove the complexity of (a) and (b)?


texts: Finite substitution and regular closure properties

texts:
I'm not sure if I get the following definition right:

1.Def: A map $\varphi: \Sigma^{*} \rightarrow 2^{\Delta^{*}}$ is called Substitution iff:

$\forall u,v \in \Sigma^{*}: \varphi(uv)=\varphi(u) \varphi(v)$
$\varphi(\epsilon)=\{\epsilon\}$

My assumption: every string in $\Sigma^{*}$ with the size $>0$ maps to a Language from $\Delta^{*}$.

such as:

$\Sigma := \{a, b\}$, $\Delta:=\{0,1\}$

$\varphi(a) = \{01^{i}0 |i \in \mathbb N \}$, $\varphi(b) = \{w\in \Delta^{*} ||w|_{0} \neq |w|_{1}\}$

$\varphi(ab) = \varphi(a)\varphi(b)=\{01^{i}0w |i \in \mathbb N \land w \in \Delta^{*} |w|_{0} \neq |w|_{1}\}$

example strings: 001, 000, 0101, 01011, 010100, ...

My first question: Is this assumption and example right?

2.Def: $\varphi$ is finitie iff $\varphi(a)$ $\forall a \in \Sigma$ is a finite subset of $\Delta^{*}$

My assumption: $\Delta^{*}$ is every possible string over the alphabet $\Delta$ and an finite subset would be a limited set $X \subseteq \Delta^{*}$  $|X| < \infty$

I would now implie that my first example is not a finite substitution, because a and b are not mapping to finite sets.

an example could be:

$\varphi(a) = \{10^{i}1 | i \in \{1,...,100\}\}$, $\varphi(b) = \{\epsilon\}$

$\varphi(bba) = \varphi(b)\varphi(b)\varphi(a) = \{\epsilon\}\{\epsilon\}\{10^{i}1 | i \in \{1,...,100\}\}=\{10^{i}1 | i \in \{1,...,100\}\}$

now I can implie that the class $REG$ is closed under finite substitution, because a concatenation of finite sets is finite and every finite set is regular.

My second question: Is this my assumption about finite substitution and the closure propierty right?


texts: Computational Complexity of a special case of Integer Programming

texts:
Integer Linear Programming (ILP) is NP-complete. However, there are special instances that can be solved in polynomial time. I am curious about the following integer program (IP) with equations and inequalities in $y_i, c_i, x \in \mathbb Z$ of the following form:

$$\begin{align*}
A_i + B_i y_i+ c_i &= x \\
c_i^2 &> 0\\
c_i^2 &< B_i^2\\
y_i &\geq 0
\end{align*}$$

where $A_i, B_i \in \mathbb N^+$ are given. I wasn't able to find much on this special case. Anyone please?


texts: Given the following code, array A and 2 indexes, find out by using substitution technique the $\Theta$

texts:
While setting left=0, right=n-1 and A an array of n numbers, find out the running time complexity in terms of $\Theta$. Firstly find out the recurrence and then evaluate it by using the substitution technique. (MergeSort is a regular mergesort between the given 2 indexes, and Merge is of linear time complexity as the number of numbers in fields left and left+p, left+p and left+2p, left+2p and right.)

The code:

void Sort(int A[], int left, int right)
{
int p;

 if(left<right)
 {
  p=(right-left+2)/3;
  Sort(A,left,left+p-1);
  Sort(A,left+p,left+2p-1);
  MergeSort(A,left+2p,right);
  Merge3(A,left,left+p,left+2p,right);
 }
}

This is what I did:

Firstly let's notice the internal work of Sort is MergeSort and Merge3. because mergeSort gets $n-1-2\frac{n-1+2}{3}$ numbers to sort, the complexity of it would be $\Theta(n\log n)$. Because Merge3 is linear to the amount of numbers in its fields, then the time complexity would be the amount of numbers in array A. Thus, it's $\Theta(n)$. So finally, the "extra work" is of time complexity $\Theta(n+n\log n)=\Theta(n\log n)$
Let's notice there are two recursive calls to Sort. First one is for function Sort with left+p-1-left range of numbers. so the size of the range is $\frac{n-2}{3}+1$. Thus it's a recursive call of type $T(\frac{n+1}{3})$. Same for second call of Sort
So finally in TOTAL we get the recurrence $T(n)=2T(\frac{n+1}{3})+\Theta(n\log n)$

My Question is if it's correct? because it seems to be too complicated to evaluate the time complexity of this recursive function. I wouldn't ask if I got for example $T(n)=2T(\frac{n}{3})+\Theta(n\log n)$ instead. because the $n+1$ in the numerator makes it really hard to evaluate.


texts: How does this algorithm for verifying if a string is $0^n1^n$ work?

texts:
I have found an efficient algorithm for verifying if a string $\omega$ is of the form $0^n1^n$, where $n \in \mathbb{N}$.

Scan across $\omega$. If a 1 appears before a 0, then reject.
Repeat so long as some 0s and some 1s remain on the tape.

Scan across $\omega$. If the total number of 0s and 1s remaining is odd, reject.
Scan across $\omega$. Cross out every other 0 starting with the first 0.
Scan across $\omega$. Cross out every other 1 starting with the first 1.

If no 0s and 1s remain in $\omega$, accept. Otherwise, reject.

I generally see how this algorithm is efficient. It gets rid of half of all 1s and 0s every iteration. How does it work though? Why must we reject if the total number of 0s and 1s remaining in $\omega$ is odd?


texts: Assign resources that each have a certain amount of work they can provide to tasks that require a certain amount of work

texts:
I'm attempting to do a hobby automation project and have come to a roadblock. I have a certain problem I need to solve, but can't think of the solution nor what the name for the problem would be.

Say we have n tasks where each task requires $x_i$ amount of work to be done and m resources where each resource can provide $y_j$ work. The total amount of work required will equal the the total amount of work the resources can provide, i.e. $\sum_{i=1}^{n} y_i = \sum_{j=1}^{m}x_j$. For all j from 1 to m, $y_j \in \left \{1, 2, 6, 12, 24\right \}$ and each $x_i = a*1 +b *2 + c*6+d*12+e*24$. I was looking at task assignment problems, but those seemed to be a bit overkill since they were concerned with optimization where I'm just simply trying to slot the correct blocks in the right place so that I don't have tasks that are given too few or too many resources.

My current guess is that you can iterate over each task, and give it the largest resource available that doesn't go over the amount of work that is left for the task to be completed. It's almost analagous to filling a jar with different sized rocks; the best way is to start with the largest rocks and then go down in size from there, so that the smaller rocks fill in the space between the larger ones. Am I not taking something into consideration that complicates this problem further? I'm sorry if this is an obvious one, but I'm a hobbyist programmer and couldn't think of the name of the problem or of a good set of keywords to google. The closest I could find is task assignment so far.


texts:
I have been reading this tutorial on time complexity, and I am a bit puzzled on its explanation of big $O$ notation. It writes:

$O(g(n)) = $ { $f(n)$ : there exist positive constants $c$ and $n_0$ such that $0 \leq f(n) \leq c*g(n)$ for all $n > n_0$.

The way I understand it, $c*g(n)$ denotes $c$ multiplied by $g(n)$. If this is the case, then how does the above expression specify time, and not just that $c*g(n)$ is greater than $f(n)$? Or am I incorrect, and this is some notation I don't understand? My understanding of time complexity is very rudimentary, so forgive me if this is just a stupid mistake on my part.


texts: Prove the language L of all palindromes over {0,1} is in NP

texts: Wouldn't this language be in P, since it is a context free language. And every context free language is a member of P? Or would it be otherwise?


texts: Explaination for Variation of Boyer-Moore Majority voting algorithm

texts:
Boyer-Moore's majority vote algorithms can be used to determine the majority element in a linear time and constant space.

The intuition behind finding the majority element is understandable as it has to be greater than the count of other elements in the input sequence if a majority element exists.

However, there is a variation of this algorithm to find the elements occurring more than [n / 3] where n is the length of the sequence.

The algorithm goes like this.

  Start with two empty candidate slots and two counters set to 0.
  for each item:

  if it is equal to either candidate, increment the corresponding count
  else if there is an empty slot (i.e. a slot with count 0), put it in that
  slot and set the count to 1
  else reduce both counters by 1

I can understand there will be at most (n /3) - 1 entries so we keep two containers and their counts.

But I'm not sure why the last reduce both by 1 is pivotal to this algorithm. I would be very helpful if you explain the intuition behind this.

Code of the above algorithm

vector<int> majorityElement(vector<int>& nums) {
    int cnt1=0, cnt2=0;
    int a,b;
    for(int n: nums){
        if (cnt1 == 0 || n == a){
            cnt1++;
            a = n;
        }
        else if (cnt2 == 0 || n==b){
            cnt2++;
            b = n;
        }
        else{ // This part
            cnt1--;
            cnt2--;
        }
    }
    cnt1=cnt2=0;
    for(int n: nums){
        if (n==a) cnt1++;
        else if (n==b) cnt2++;
    }
    vector<int> result;
    if (cnt1 > nums.size()/3) result.push_back(a);
    if (cnt2 > nums.size()/3) result.push_back(b);
    return result;
}

Algorithm and code source


texts: Deciding between two algorithms with similar runtime in two parameters

texts:
Let's say I have a problem which depends on two variables, $m$ and $n$.  I also have two algorithms for solving the problem.  How do I decide which algorithm to use?

For example, say I have an array of unique numbers $A$, not necessarily sorted, and a second sorted array $B$.  I want to create a third array $C$ which contains how many times each number in $A$ appears in $B$.

Algorithm 1 runs in time $O(m \lg n)$ and algorithm 2 in $O(m \lg m + n)$.

It seems to me I would need to divide into three cases:

$n=\Theta(m)$
$n\gg m$
$m \gg n$

How would I generally proceed from here?


texts:
Given a collection C of sets, there are a number of proposed algorithms for building the subset partial order, e.g. this paper.
But is there any work on algorithms that return the [components of such collection, that is the weakly connected components of the DAG that represents the subset relation?

Input: C, a set of sets of elements.
Output: P, a partitioning of C, that is a set of sets of sets of elements such that all sets in a partition are connected by the subset relation and no sets from different partitions are connected.

Regarding Input and Output, this problem is really simple and has many potential applications, but I have not been able to find any research that is looking for optimal solutions.
Of course, you can build the partial order by above methods and then use a union-find structure to compute the components, but aren't there any shortcuts for the described problem? In particular it would be good to skip the explicit computation of all edges.
Also if memory would be taken into account, that would be great.
Any ideas?
I am currently looking into the following approach:

Compute the relationships between all the sets in C and their minimal elements in C as in this paper
Compute the connected components of this reduced poset in linear time

So in this context, I am looking for a simple algorithm for finding the minimal elements in a poset that exploits the fact that the partial order is the subset partial order, which will probably allow for shortcuts compared to any given partial order, i.e. see this paper.


texts:
I'm trying to implement a Inventory Routing Problem with Branch-and-Cut. But I'm facing with an issue regarding subtour elimination. (http://www.danflash.com/files/irp.pdf)

The paper describes the constraint like this:
$$\sum_{i \in S} \sum_{j \in S, j<i} y^t_{ij} \le \sum_{i \in S} z_{it} -z_{kt} \quad S \subseteq M \quad t \in T \quad \text{for some} \ k \in S$$
And some page further I've found this: $k=arg max_j\{z_{jt}\}$ but no idea how to interpret this.

Where $y^t_{ij}$ is $1$ when the edge is used from $i$ to $j$ at time $t$. And $z_{it}$ is $1$ when vertex $i$ is visited at time $t$.

What is the exact definition of $S$? The set of all subtours or one specific subtour? Let say $M = \{1, 2, ...,7\}$ and $M' = \{0, 1, ..., 7\}$ ($M'$ with supplier/depot).

And the solution I get contains the following subtours: $0,1,3,0$ and $2,4,5,2$ and $6,7,6$

Know how would a pseudo code look like to implement this? And what is $k$?

My current solution look like this (implemented in C# with Gurobi solver). But I'm not sure if this should be implemented as a lazy constraint in the callback or adding the constraint after model.Optimize() if a subtour exists and call model.Optimize() again.

I did an implementation but I guess it's not worth to post it before I really understand the equation.


texts: Persistent data structures representing a directed graph's paths

texts:
Are there any standard persistent data structures that facilitate the following?

tabulating, for each arc in a rooted, oriented, acyclic multigraph, the set of root-emanating paths containing the arc
keeping accurate tallies of path collections as arcs are added to and removed from the graph

My research to this point suggests two broad possibilities:

a comonad-like Erwig-style graph decomposition where each edge (or node instead perhaps) points to its collection of coincident root-emanating paths (or some decomposition thereof)
a radix-tree-like data structure, with root-emanating paths as its keys

However, although the first idea as a roughly conceived strategy seems interesting, I'm not sure whether such an approach is even possible. And the second strategy seems to require an accompanying method for identifying all paths/keys that contain any arc marked for deletion, and so its usefulness may be limited by the efficiency of this secondary indexing scheme.

Might either of the two ideas above suggest a practical means to use some persistent data structure for tabulating a graph's paths? Or if not, are there any unrelated, yet canonical data structures for this purpose?


texts: Graph optimization problem with multiple objectives/constraints

texts:
Let's assume that we have a directed acyclic graph $G = (V, E)$, non-negative vertex weight functions $w_a(v)$ and $w_b(v)$, and a non-negative edge weight function $t(u,v)$. We want to divide vertices in two subsets $V_a$ and $V_b$, such that $V_a \cap V_b = \emptyset$ and $V_a \cup V_b = V$. The set of edges $E_{ab}$ between the two sets is defined as

$$E_{ab} = \{ (u,v) : (u \in V_a, v \in V_b) \lor (u \in V_b, v \in V_a)\}.$$

A cost function $C$ is defined as follows:

$$C = \sum_{v \in V_a}{w_a(v)} + \sum_{v \in V_b}{w_b(v)} + \sum_{(u,v) \in E_{ab}}{t(u,v)}$$

Define the cost $C_P$ of a path $P$ traversing vertices $v_1, v_2, \dots, v_n$ to be:

$$C_P = \sum_{v \in V_a \land v \in P}{w_a(v)} + \sum_{v \in V_b \land v \in P}{w_b(v)} + \sum_{(v_i, v_{i+1}) \in E_{ab} \land v_i \in P \land v_{i+1} \in P}{t(v_i,v_{i+1})}$$

I know that the problem of finding the subsets $V_a$ and $V_b$ such that the $C$ function is minimized can be reduced to minimum cut, so it's in P.

I've also managed to come up with the solution to find the subsets $V_A,V_B$ with the path with highest possible cost: we can transform the graph $G$ to graph $G'$ in such a way that for every vertex $v$ we create two vertices $v_a$ and $v_b$ with appropriate weights (from $w_a$ and $w_b$ functions respectively), and for every edge $(u,v)$ we create two edges with weight $0$: $(u_a,v_a)$, $(u_b,v_b)$; and two edges with weight $t(u,v)$: $(u_a,v_b)$, $(u_b,v_a)$. In other words, we're creating graph $G'$ that covers every possible path for every division of $V$.

The problem can be reduced to finding the longest path in a graph. The graph $G'$ is still a DAG, so the longest path can be found in polynomial time.

Now, the multi-objective problem that I'm trying to solve is to find subsets $V_a$ and $V_b$ that minimize the cost $C$ but with a constraint that the cost $C_P$ of every possible path is not greater than maximal acceptable cost $c_{max}$. Graph $G = (V, E)$ and all weight functions are given as an input and fixed.

Or the other way around: minimize the maximum cost $C_P$ of every possible paths, but constrain the overall cost $C$ to be not greater than $c_{max}$.

How should I approach this problem? Are there any generic ways to prove complexity of such multi-objective problems?

The best answer that I've found in literature is that "multi-objective optimization problems are generally hard" which is not very helpful.

My real-life application of this problem is to allocate software components on two heterogenous machines (hence two weight functions) connected via network (hence edge weights) and minimize both energy use (the $C$ function is basically the CPU time + transfer time) and the computation time (the path with the highest cost).

Thanks in advance for any help.


texts: what is the time complexity of Leiden Algorithm?

texts:
I am not able to find out the time complexity of the Leiden Algorithm. Can anyone here help me?

https://doi.org/10.1038/s41598-019-41695-z.


texts: Can someone explain in a simple way what "reducible" mean in complexity theory?

texts:
I find the word "reducible" used in complexity theory not very intuitive, and too general taken on a face value.

What does it exactly mean by problem A reducible to B?

Does it mean that A can be reworded into B?
i.e. Finding Vertex Set is actually the same as finding an independent set?
Does it mean that an algorithm that solves problem B will solve A?
i.e. An algorithm that finds longest path will in fact also find the shortest path?
Does it mean that A can be proved to be in the same complexity class
as B?
i.e. A is NP-Hard, B is NPC, then if A is reducible to B, A is in fact NPC?

In other words, A is reducible to B, what can we say about A or B?

As you can see my understanding is quite flaw at the moment, can someone please clarify the application of the word for me maybe even rephrase it into something more intuitive?


texts: Automated geometric theorem-proving using synthetic methods

texts:
This question is about geometric theorem proving and is inspired by this  Math.SE  post.  Currently, Euclidean-geometric theorem provers, as referred to in the post, use coordinate geometry to convert a geometry problem into a set of algebraic equations.

  Why haven't people developed a theorem prover that uses synthetic reasoning ?

By 'synthetic' I mean reasoning from axioms. I feel that synthetic reasoning would be more insightful than solving a large number of equations; yet, am unsure about how well it yields to implementation. Can you offer more insight? What would be the benefits and drawbacks of such a prover?

Also,I felt that my question would be more appropriate here than on Math.SE.


texts: Does an algorithm exist for solving the change-making problem using a finite coin library of known size?

texts:
I'm currently working on implementing an algorithm to solve a real-world problem I'm encountering in a lab, but with little background in algorithms, I'm struggling to create an ideal solution.

I work in a protein lab and using a mass spectrometer I can get the mass of a protein of interest. Each protein is made up of a string of building blocks called amino acids, and each amino acid has a known mass. Additionally, each amino acid can posses one of about a dozen modification which can alter it's mass by a known amount, positively or negatively.

Using the total mass of the protein alone, I'm looking for a way to identify all possible combinations of amino acids and modifications that could potentially sum up to that protein's mass.

As an example, say we know the following:

Protein mass: 12 Da
Amino acid masses:

A: 3 Da
B: 6 Da
C: 10 Da

Modification masses:

a: +2 Da

With this information, we can decompose the peptides mass into the sums of the following combinations (I may have missed some):

AAAA
AAB
BB
Ca

Obviously order of the building blocks can't be inferred from the mass alone, but the atomic makeup should be.

I've attempted to solve the problem by looking at it as a type of change-making problem, and implemented my first solution using the algorithm outlined by Bocker and Liptak in the following paper:

https://bio.informatik.uni-jena.de/bib2html/downloads/2005/BoeckerLiptak_EfficientMassDecomposition_ACMSAC_2005.pdf

The issue is that this algorithm calculates every possible combination of amino acids and modifications that sums to the peptide mass, which for larger peptides results in billions if not trillions of combinations over a runtime of hours if not days.

Bocker and Liptak use an infinite set of values to sum to the target peptide mass, whereas I believe that I can drastically shorten the runtime if I can use a finite library size. Say I know that I protein I'm analyzing normally has 3 As, 2 Bs, and 5 Cs, the idea I have is to restrict the calculations to only those combinations that involve the same number of amino acids plus or minus X. The number of modifications would be tied to the number of amino acids on a one to one basis.

Is there an algorithm for this sort of calculation? Please feel free to ask me to clarify anything because I know that it's a complicated problem.

Best!


texts: What was Robert Floyd's algorithm for inserting brackets?

texts:
In page 71 of Mathematics for Computer Science (page 77 in the pdf) it says that "The Turing award (the “Nobel Prize” of computer science) was ultimately bestowed on Robert Floyd, for, among other things, being discoverer of a simple program that would insert the brackets properly [into an arithmetic expression]."

What was this algorithm?

Based on the page for Floyd's award, it looks like the algorithm can be found in this paper.


texts: Pushdown Automata: How can I recognize a ratio threshold between two symbols in a string?

texts:
I'm trying to design a pushdown automata where there are two symbols in the alphabet and the accept state is when there is >= 60% of symbol A.

I'm trying to think in terms of what to save on the stack. The problem of telling when there are 50% or more is trivial. You can just pop and push As and Bs on the stack to track which one has the majority. If an A is on the stack at the end, you're solid. however, in this problem we see that an A can be on the stack in the end and still not meet the criteria because it could be a ratio of 6 As to 5 Bs, which is under 60%.


texts: Pseudocode for checking if two arrays contain the same elements?

texts:
I'm not so much confused as to write the actual code as I am to write the pseudocode.

To determine if two arrays of the same size contain the same elements, I know you would need two for loops, then compare one element in the first array to each element in the second array, and repeat this for each element in the first array, stopping the loops if there are no elements that match. But is there a faster way to do this? If not, how would I go about putting the for loops into pseudocode?


texts: Why sizeof(int) and sizeof(int *) takes different value in a system? I mean generally size of integer is 4 B, but size of integer pointer is 8 B. But why they cannot take same value, although their return type is same?


texts: Finding the shortest tour of a Pyramidal traveling salesman problem

texts:
We have a directed graph $G=(V,A)$ with $V=\{1,2,...,n\}$ where for each $(i,j)$ the distance $l(i,j)\in A$ is known. We want to find a pyramidal tour that has minimal length and that includes all points exactly once.
A tour is pyramidal if it is of the form: $(n\rightarrow 1 \rightarrow n)$ such that all points in $n\rightarrow 1 $ are decreasing and all points in $1\rightarrow n$ are increasing (example: $(6,5,4,2,1,3,6)$.
I want to find a solution to this problem using Dynamic Programming where $f(i,j)$ is the length of the shortest pyramidal path $(i\rightarrow 1 \rightarrow j)$.
My solution is the following:

$f(i,j)=\begin{Bmatrix} min_{1\leq k<i}(f(k,1)+l(i,k)),\text{when } j=1
\\ min_{1\leq r<j}(f(1,r)+l(r,i)),\text{when } i=1
\\ min_{\begin{matrix} 1\leq k<i \\1\leq r<j,\end{matrix} }(f(k,r)+l(i,k)+l(r,j),\text{when } j>1, i>1
 \end{Bmatrix}$

Assuming that $f(1,1)=0$ we find the shortest possible tour by compution $f(n,n)$ is this correct?


texts: Probability of terminating in a state in a probabilistic algorithm

texts:
Suppose i have a circular array of $n$ elements.
At time $t=0$ i am in position 0 of the array. The algorithm moves left or right with probability $p=1/2$ (since the array is circular when it moves left from 0 it goes to position $n$).
When i visited all the positions at least once the algorithm returns the position it terminated into.
Launching the algorithms many times shows that it stops with the same probability in any of the n positions (except for zero obviously).
How do i demonstrate that the probability of ending up in each state is uniform?
My understanding is that this process is explained by a doubly stochastic Markov chain, but is there a theorem i can quote about this specific case?


texts: Reusing variable in converting grammar to Chomsky Normal Form

texts:
I'm not sure if reusing variable is allowed in CNF.

For example, I have this grammar not in CNF. So I have to convert it to CNF.

1. S->abAB|abB|abA|ab
2. A->bAa|ba
3. B->BAa|bAa|ba|Ba|Aa|a

For conversion, I'm using a convention where new variables and terminals are in the form

(V1,V2,V3,...,Vk) for k > 0
Ti where i are terminals (a,b,c,...,z)

Introduce new terminals for each terminal in the grammar
S->(Ta)(Tb)AB|(Ta)(Tb)B|(Ta)(Tb)A|(Ta)(Tb)
A->(Tb)A(Ta)|(Tb)(Ta)
B->BA(Ta)|(Tb)A(Ta)|(Tb)(Ta)|B(Ta)|A(Ta)|a
Ta->a
Tb->b

For the purpose of my question, I'm only focusing only on B productions due to the repetition of A(Ta).

...
B->BV1|(Tb)V2|(Tb)(Ta)|B(Ta)|A(Ta)|a
V1->A(Ta)
V2->A(Ta)
...

See V1 and V2, they have the same right-hand side that is A(Ta).


texts: Are today's massive parallel processing units able to run cellular automata efficiently?

texts:
I wonder whether the massively parallel computation units provided in graphic cards nowadays (one that is programmable in OpenCL, for example) are good enough to simulate 1D cellular automata (or maybe 2D cellular automata?) efficiently.

If we choose whatever finite grid would fit inside the memory of the chip, can we expect one transition of a cellular automaton defined on this grid to be computed in (quasi)constant time?

I assume 2D cellular automata would require more bandwidth for communication between the different parts of the chips than 1D automata.

I'd also be interested by the same question in the case of FPGA programming or custom chips.


texts: Minimum number of cuts to divide a rectangle

texts:
We're given a big rectangle, and a list of small rectangles contained inside it, with their vertex coordinates.

We want a list of  the minimum number of lines defined by a pair of points (x,y) that cut up the big rectangle into the small ones.

For example for this case:

The minimum number of cuts would be 7, and they are represented in the following picture.

Any idea to achieve this? (The rectangles are not always touching the borders.)


texts:
Looking for some tutorials / references that discuss Breadth First Search that takes into consideration the cost of paths, but could not find much information.

Could someone refer a tutorial?


texts: Does amortized complexity always equal to worst case complexity divided by n?

texts:
Is it true that given any operation that takes O(f(n)) amount of time, we do this n times in a process, then the amortized cost is O(f(n))/n?

I'm confused because this statement is so simple and applicable, I don't see the need for accounting method or potential method if we can just divide the worst case operation i.e. enlarging a dynamic array or multipop by the times we want the operation to be perfornmed


texts: Can I have 2 free adjacent nodes in the fit algorithm for data management

texts: so I know we can have 2 busy adjacent nodes for the fit algo since there'll always be free memory available, but what about when it comes to 2 free adjacent nodes? Is it possible to have 2 adjacent free nodes and why? Thanks


texts:
How do I present the complement using set notation?

I guess it has to be shows with universal set - {aa,bb} but I do not know how to represent the universal set in terms of set notation. Since, the strings of the universal set can be anything over alphabets {a,b}. So, how to represent it?
I guess something like this might work if we are going from outside to inside {{{a,b}*}*}.
Any help is appreciated.


texts:
I ask this question with regards to a grammar in Chosmky Normal Form. The definition states that the rules must be of the following forms:

A $\rightarrow$ BC
A $\rightarrow$ a
S $\rightarrow$ $\epsilon$

And A,B and C are non-terminal symbols, B and C are different from S and a is a terminal symbol. The definition also states that the last rule can only be present if the language of the grammar accepts the empty string (source). Now if $\epsilon$ is a terminal symbol, than this is a contradiction as the second rule can be transformed to S $\rightarrow$ $\epsilon$, seeing as A must not be different from S. This leads me to conclude that $\epsilon$ is not a terminal symbol, is this correct?


texts:
I want such data-structure, which can:

add element at the end of the array in $O(log (n))$.
find out the minimum value in the sub-segment in $O(1)$


texts: Reading process memory of computer A on computer B?

texts: So I was wondering if there is a way of reading process memory of one device on another. So lets say a process is running on computer A, I then use some form of connection lan, pcie etc. Once the two computers are connected. Would it be any way possible to then, say open something like cheat engine and read process memory of PC A on PC B in real time. Has something like this been done before/is possible?


texts: Optimization of modular exponentiation using fft

texts: My math prof said it is trivial to optimize a modular exponentiation (a^b mod c) problem for large values using fft, but I can't figure out how to do this. I looked it up and found a few papers on it (namely [1], [2], and [3]), but 2 of them use Montgomery multiplication, although in different ways, and the third one uses a completely different algorithm to the best of my understanding. I didn't fully understand the papers and can't find anything else on this subject outside these 3 papers. How would one do this?


texts: Hardness of mixed 3-SAT and 2-SAT formula

texts:
It is well known that 3-SAT is $\sf NP$-complete , but 2-SAT is in $\sf P$. Let there be a formula with $n-1$ clauses with 2 literals each and only 1 clause with 3 literals.

We can solve this case in polynomial time, separating and solving in a brute force manner the 3 literal clause and then for each satisfying assignment try to solve the rest $n-1$ 2-literal clauses. This method can work till $O(\log n)$ clauses with 3 literals.
If we consider a more general case with e.g $\frac{n}{2}$ clauses with 2 literals and  $\frac{n}{2}$ clauses with 3 literals does the problem remain $\sf NP$-complete?

It is a bit confusing because we have a subproblem approximately the same size, implying it is difficult and another one roughly the same size implying it is easy. Is there probably a better method than the one I proposed?


texts: My main concern is whether the genetic programming is an active field of research, with some promising applications in practice. It seems like in field of machine learning, the neural networks are the main buzzword, with mentions in mainstream news today, but I have never heard of similar genetic programming "success story".


texts: Does this "reference" problem have a name?

texts:
I have the following problem which I think is so common that I expect it to have an official name (and standard algorithm of course).
The situation is as follows:
I receive distinct items (A...E in the below sketch) one after the other. Each item has a relation which can generally be termed "descendance" or "family" and is in itself anonymous - the only requirement is that an item can only belong to one family and that it must somehow be possible to distinguish the families. Items keep coming in and are referenced to their own family (like A and B in step 1), but sometimes an item can change the situation for other items already received: see the second step of the sketch: a connection in C points back to A and B and revokes their original descendances and points them to the family of C. Such connections are transitive, which can be seen in step 3: the connection between E and C also converts the descendance of A and B to the new family of E.

The task I need to solve is to keep the descendance relation correct for all items. It may look trivial but the solution that I am looking for should be O(n), n == number of items.
Is there a name (and most likely a different description) of the problem in
literature?


texts: Complexity to generate every combination of every size for a given sequence

texts:
I would like to estimate complexity in space and time of generating every combination of every size for a given sequence.

Exemple :

 seq = [1,2,3]
 combinations = [{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}]

From what i know, for a given sequence of size n and a fixed combination size k, the number of combination generated is ${n}\choose{k}$, so i suppose than complexity in time and space is $O({{n}\choose{k}})$.

What we want is the sum for every value of $k$,
 $O({\sum_{i=1}^n{{n}\choose{i}}})$

I know that for a sum the complexity equals to the most complex element of the sum.

For the binomial coefficient, if n is even, the biggest one will be $n \choose \frac{n}{2}$

So i can put a an upper born as $O(n.{n \choose \frac{n}{2}})$

Is there a more precise way to determine the complexity of this operation ?


texts: Hardness of a problem which is the sum of two NP-Hard problems

texts:
Consider the problem of computing an exponential sum over a certain function $g(x)=f(x)+h(x)$, that is computing
$$\sum_{x}g(x)=\sum_{x}f(x)+\sum_{x}h(x)$$
now if we know that $\sum_{x}f(x)$ and $\sum_{x}h(x)$ are two NP-Hard problems, what can we say about the hardness of $\sum_{x}g(x)$?


texts: Formal Description Of Data Structure For Infinite Sets Of Reals

texts: The paper I'm working on uses sets as implemented in https://docs.sympy.org/latest/modules/sets.html. A set is stored in a data structure as a sequence of intervals with open or closed bounds, so it can represent uncountable and infinite sets. What prior work can I reference for this data structure?


texts: Problem regarding caching. Block offset, Set index and Tag

texts:
I am currently reviewing for my exam in computer architecture. I've run into a question in the old exam sets that I can't really figure out. The question is regarding caches, more specifically block offset, set index and tag. The question is as follows:

The old sets come with solutions. The solution to the problem is as follows:

Unfortunately, it doesn't state how to get there. I'm at a loss here and would really like to understand this. Any help would be appreciated :)


texts: How many number of different binary trees are possible for a given postorder (or preorder) traversal

texts:
I came across the problem:

  What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A,B,C?

Now 3 being small number I was quick to draw all possible binary trees and come at the conclusion that there can be 5 such binary trees for given postorder.

   C        C      C     C       C
  / \      /      /       \       \
 A   B    B      B         B       B
         /        \       /         \
        A          A     A           A

Then I tried to do the same for 4 nodes postorder traversal A,B,C,D. We will need D at the root. Then all A,B,C can be in the right subtree of left subtree. So there will be $2\times 5$ such formations. Let us denote this as follows:

$\underbrace{1}_{\text{root}}:\underbrace{3}_{\text{#nodes in left subtree}}:\underbrace{0}_{\text{#nodes in right subtree}}  = \underbrace{5}_{\text{#tree arrangements}}$

$1:0:3=5$

Now there is another possibility that 2 nodes are in the left subtree and the 3rd one in the right subtree or vice versa. Then,

$1:2:1=2$

$1:1:2=2$

Total $= 14$

For 5 nodes postorder traversal A,B,C,D,E, I can get

$1:4:0=14$

$1:0:4=14$

$1:3:1=5$

$1:1:3=5$

$1:2:2=4$

Total $=42$

Though, I am able to figure out the number of binary trees required for these post orders, I am unable to come up with defining recurrence relation and any closed formula for number of binary trees possible for given post order traversal. Is such recurrence relation and closed formula possible?


texts: Is Context Free Language closed under perfect shuffle?

texts:
Note that this is not shuffle but perfect shuffle, defined as follows:

Let $w = a_{1}a_{2} \ldots a_{n}$ and $x = b_{1}b_{2} \ldots b_{n}$ be two strings of the same length. Then the perfect shuffle of $w$ and $x$ is defined as $a_{1}b_{1}a_{2}b_{2} \ldots a_{n}b_{n}$.

So the question is: are context free languages closed under perfect shuffle?


texts:
I'm studying for my finals in algorithms and reading the part about flow networks. There's a certain section that has me completely stumped and it is as follows:

  Given a graph $G= \langle V_G, E_G \rangle$, we can construct the $H(G)=\langle V_H, E_H\rangle$ as follows:
  $$V_H = V_G\times\{0,1\}$$
  $$E_H = \{((v,0),(v,1))|v\in V_G\}\cup\{((x,1),(y,0))|(x,y)\in E_G\}.$$
  Say that we have a graph $\langle G,u,v\rangle$ where $G$ is some directed graph, which contains vertices $u$ and $v$ then $H(G)$ can be used to find the smallest number of nodes that must be removed from $G$ to separate $u$ to $v$, meaning there will be no simple path from $u$ to $v$.

I really don't understand what's going on here, partly because I can't visualise $H(G)$. I assume we'd get some bipartite graph and maybe apply Edmonds-Karp only because the flow networks sections is succinct and there's not much else in this chapter. Could someone tell/show me what $H(G)$ is doing exactly and why this result is true. Much appreciated.

EDIT:

I've added some images of the what I got for $H(G)$ for some simple graphs. I understand that the function will transform a graph into a bipartite graph. But, how does this graph tell us the minimum number of vertices that have to be removed so there doesn't exists a simple path from $u$ to $v$ in the original graph? I'm perhaps wondering if it is a maximum matching problem in disguise.


texts:
The question in Proof of big-o propositions asked to prove:

  $O(f(n))=O(g(n))\iff\Omega(f(n))=\Omega(g(n))\iff\Theta(f(n))=\Theta(g(n))$

The accepted answer starts the proof with:

  Suppose that $O(f(n))=O(g(n))$. It is easy to check that $g(n)=O(g(n))$ ...  and so $O(f(n))=O(g(n))$ implies that $g(n)=O(f(n))$.

I believe that there is a mistake in quoted part of the answer above.

It claims that $O(f(n))=O(g(n))\tag{1}$

and $g(n)=O(g(n))\tag{2}$

implies

$g(n)=O(f(n))\tag{3}$

Using the interpretation given in "Introduction to Algorithms (CLRS) Edition 3, page 50",  (1) is interpreted as $\forall\Phi(n)\in O(f(n)), \exists\Psi(n)\in O(g(n))$ such that $\Phi(n)=\Psi(n)$.

Additionally, the definition of $O$-notation given in "Introduction to Algorithms (CLRS) Edition 3, page 47" states:

  $O(g(n))=\{f(n):$ there exist positive constants $c$ and $n_0$ such that $0 \leq f(n)\leq c\cdot g(n)$ for all $n\geq n_0\}$

Considering the counter example whereby $f(n)=n$ and $g(n)=n^2$. Then $O(n)=O(n^2)$ and $n^2=O(n^2)$ hold, but $n^2\neq O(n)$, thereby contradicting the assertion given in the accepted answer. Note: "$\neq$" in this case refers to "$\not \in$".

Therefore, I would like to ask if the answer provided is wrong or my interpretation and/or reasoning is wrong.


texts: If L = {xy | |x| = |y|, x=y} is not Context Free, then what about L = {xy | |x| = |y|, x!=y}?

texts:
I know that, when x = y, then it's not Context Free. This is because, the first letter of y cannot be matched with first letter of x, which is at the bottom of the stack.
But, a link of Show that { xy ∣ |x| = |y|, x ≠ y } is context-free claims that, when x!=y, then it's Context Free. But, how can the letters of x and y be matched on stack? Say x=abbb y=bbbb. How can we say first letters don't match?

Not necessarily restricting ourselves to determinism, will it be even possible by the Context-free Language class (Non-deterministic & Deterministic Pushdown Automata), as a whole, to generate L = {xy | |x| = |y|, x!=y}?


texts: why nominal unification is a first-order unification?

texts:
In my understanding, if a unification solves equations of terms that are not higher-order terms, then it is a first-order unification.

If a unification solves equations of terms that are higher-order terms, then it is a higher-order unification. Therefore a unification solves equations of $\lambda$-terms should be a higher-order Unification.

That is what I thought.

Read about unification

the paper nominal unification said that nominal unification is a first order unification, but it is solving equations of $\lambda$-terms.

Why nominal unification is a first-order unification while clearly solving equations of higher-order terms?

Also, that paper shows an example of unification

$$
\lambda a.\lambda b.(b \, M_6) =?= \lambda a.\lambda a.(a \, M_7)
$$

on the right side $\lambda a.\lambda a.(a \, M_7)$, what is that? Why two abstractions have same bound variable $a$ ?

I am confused, could anyone clearify it to me, thanks!


texts:
In the lecture we are told about the very basics about CPU. However after the introductory part I found that there are still some things I don't understand too well or which were not really addressed in detail in the lecture.

When we talk about CPUs and micro commands in lecture, we are mainly looking at the following graphic (or some variation) of it, therefore I would explain below the image, what we have:

The picture in fact shows CPU with all the possible commands on the left. In one tact you submit a signal of 21 bits to your CPU that triggers the respective points the little red arrows are pointing at. (I assume you understand enough to understand the graphic even with no proper knowledge of German. If thats not the case, I include a small dictionary + key below)

I trigger the bits: 0, 2,6, 12 (keeping all others 0) and as a result: The values stored in the registers A and C swap.
But how does this happen without being information lost? I assume all points of the computer receive their bit respective bit value at almost the same time, however how does the CPU guarantee that the value in C is not overwritten before it sends its value to A?
Assume there are some values stored in A and B. Assume further I am evil and I trigger: 2, 5 and 6. What happens? With the currently, given knowledge in the lecture I cannot answer that. Is this even definitely answerable?
Is there a certain meaning to the green triangles? It looks like a NOT-Gate without its small circle or a tri-state buffer. The latter seeming to me the most likeliest.

As always any constructive comment/answer is appreciated. Thank you in advance.

Dictionary for reference:

A, B, C, D and E are registers. Eingabe = Input, vom Speicher = from Memory, zum Speicher = to the memory, Ausgabe = output, Wähle = Choose, Lade = load, Springe = jump, Springe falls = jump, if


texts: Who converts binary/machine code to electrical signals and how?

texts:
I went through lots of blogs and posts but could not exactly figure out how the machine code is converted to electrical signals?

Any software program is compiled to machine code which is nothing but lots of 1s and 0s.
1 means high voltage e.g 5V and 0 means comparatively low voltage e.g. 0V or ground, what's the component which understands that okay I got 1(one) so I need to step up up the voltage to 5V and for 0(zero) I need to step down to lower voltage level and how it does that?


texts: Will the growth of calculation speed of personal computer end after that of classical computer will end?

texts: According to the answer of Andrew Yeats in this link, quantum computer's advantage is so narrow that personal computer is not likely to benefit from the development of quantum computer. I think this is understandable, so will the growth of calculation speed of personal computer end after that of classical computer will end (in 2020~2025)? If so, is there any candidate of new computation model which will replace personal computer in the future?


texts: Implement multi-fragment heuristics for the traveling salesman problem

texts:
I would like to implement the multi-fragment heuristics algorithm for finding a solution to the traveling salesman problem.

The algorithm is described here as follows:

  This seriation method re-organises the $D$ matrix by iteratively placing the smallest distances in matrix $D$ in the $n-1$ cells contiguous to the diagonal.

  This is a greedy approach, with $n-1$ steps.

  At each step, rows $i$ and columns $j$ in $D$ are moved so that the smallest distance is placed in a not yet allocated cell. The smallest distance is not chosen freely. It is constrained by the necessity to keep the already allocated cells in place.

  ...

  This heuristic do not guarantee to find an optimal solution but give quickly a "reasonable good" solution. This solution could be improved by a local search heuristic.

According to the mentioned article, this algorithm was mentioned in a 1992 paper "Fast Algorithms for Geometric Traveling Salesman Problems" by "Bentley", but I couldn't find it on the internet. Moreover, there are almost no other information regarding this algorithm online, except from the usual definition like:

  The multi fragment algorithm works as follows:

  Consider a distance matrix (such as the type at the back of a road atlas of Britain), containing all the distances between all cities on the tour.
  Find the shortest distance and link these two cities together.
  Then, find the second shortest distance, and link these two cities.
  Now, find the next smallest edge whose cities conform to the following criteria:

  Both must have an edge degree ratio <=1 (i.e. neither can already be linked to more than one other city)
  Adding an edge between the cities must not result in a closed tour, which does not already include all the cities on the tour.

  Repeat until all cities end up being connected to two other cities.

I understood the algorithm according to this last article I'm linking to, but I'm not seeing the connection between this last description and the description above.

If the first description is correct, I'm actually not understanding it fully and how could I implement it in practice. For example, suppose we have this simple distance matrix $D$

$$D = \begin{pmatrix} 2& 1 &2 &3\\ 3 &2 &7 &2 \\ 3 &1 &1& 0\\6& 2& 5 &1\end{pmatrix}$$

In the first description, they mention the $n -1$ cells contiguous to the diagonal, but of course we have $2$ of this $n-1$ cells, one in the left triangular matrix (currently from the top to the bottom $3, 1, 5$) and one in the upper one ($1, 7, 0$). Is it ok to choose one arbitrarily?

Then they say:

  At each step, rows $i$ and columns $j$ in $D$ are moved so that the smallest distance is placed in a not yet allocated cell. The smallest distance is not chosen freely. It is constrained by the necessity to keep the already allocated cells in place.

Of course if we move a row or a column in the matrix $D$ and if we number the nodes from $1..N$, then we need to rename the nodes according to the moves.

But actually I'm not fully understanding how these moves could proceed in practice? Any concrete example?

Furthermore, after these moves, what should we do?

I would really appreciate a pseudo-code, if anyone has ever implemented this algorithm.


texts:
For a given classifier h, How is the true error over a distribution D defined?
\begin{align*}
L_D(h) &= \sideset{\mathbb{E}}{}{}_{x,y \sim D} \Pr[h(x) \neq y] \\ &=
\sideset{\mathbb{E}}{}{}_{x,y \sim D}
\begin{cases}
\Pr[y \neq 0|x] & \text{if } h(x) = 0, \\
\Pr[y \neq 1|x] & \text{if } h(x) = 1.
\end{cases}
\end{align*}

I saw these two formulae here Showing that Bayes classifier is optimal Are these two equivalent?


texts: Find two contiguous subarrays with the greatest difference

texts:
Here's an interview question I've seen on a few sites. People claim that an O(n) solution is possible, but I've been racking my brain these last 2 days and I couldn't come up with a solution, nor find one anywhere on the web.

Given an array of integers, find two disjoint, contiguous subarrays such that the absolute difference between the sum of the items in each subarray is as big as possible.

Example input: (2, -1, -2, 1, -4, 2, 8)

Example output: ((1, 4), (5, 6))

The output above is the indices of these two subarrays: ((-1, -2, 1, -4,), (2, 8))

I've been trying to reduce this problem to the Maximum subarray problem but with no success.


texts: Proving that $\{0^nw1^n\mid n\geq 0, w\in\{0,1\}\}$ is irregular

texts: How can I prove that the language $L = \{0^nw1^n\mid n\geq0,w\in\{0,1\}\}$ is irregular? I've tried the pumping lemma but that seems not to work.


texts:
Suppose I have a recurrence like $T(n)=2T(n/4)+\log(n)$ with $a=2, b=4$ and $f(n)=\log(n)$.

That should be case 1 of the Master theorem because $n^{1/2}>\log(n)$. There is also a lambda in case 1: $f(n)=O(n^{(1/2)-\lambda})$. Is this correct? And how can I find this lambda?


texts: Space complexity of string indices: O(1) or O(log|S|)?

texts:
Say you have a string S and wish to store indices of it, e.g. letter at index 3 of "toast" is 'a'. Seems that people generally consider an index as taking O(1) space to store*. But doesn't it take O(log(|S|)) space?

If we use binary bits...

length 4 string => index must be at least 2 bits
length 8 string => index must be at least 3 bits
length n string => index must be at least log(n) bits

*An example of where I'm seeing O(1) suggested: educational sources state that a suffix tree has O(|S|) space complexity, where S is the input string, because there are O(|S|) nodes in the tree, and each node is just an index in the input string. This implies that each index takes O(1) space, but this seems untrue to me. Seems like the tree takes O(|S| log(|S|)) space.

*More examples: Many basic data structures (hash tables, BSTs, etc) use memory pointers (equivalent to string indices), and everyone considers these pointers fixed-size.


texts:
Is the following a context-free language?
$$L = \{a^n w w^R a^n \mid n \geq 0, w \in \{a,b\}^*\}$$

I think no because the number of $w$'s is not equal.

Somebody please guide me.


texts: Induction / (machine learning) of Resource Grammars for Grammatical Framework?

texts: Grammatical Framework is based in Abstract Categorial Grammars. It is known that Combinatory Categorial Grammars have grammar induction/learning capabilities see e.g. https://link.springer.com/article/10.1007/s11168-007-9026-2 and there are also works about statistical learning in Cornell Semanatic Parser framework. But what about abstract CG generally and GF specifically - can GF resource grammars be machine learned/induced - are there works about this? Google gives nothing, but Google is not reliable with such searches.


texts:
On a distributed system, there are more than 50 machines than continuously read from a database which tasks they have to process.
There is no criteria based on which a certain machine chooses which task to process, leading to problems like unbalanced-task machines and low-quality completed tasks (the quality of a processed task depends on which machine processed it).
Goal is to "decouple" this architecture, introducing a new "entity" in the middle that serves as a task distributor. This way, we'd jump from this current architecture:
Database of tasks <- Machines randomly read tasks to be processed from database

to something like this:
Database of tasks <- TASK DISTRIBUTOR -> Machine receives task from task distributor

The main purpose of this new task distributor would be:
a) To minimize idle time in machines (to act as a load-balancer).
b) For every task, enroute them to the machine that best fits some criteria based on task requirements. For example, machines of type "A" are best suited to process tasks of type "1" than machines of type "B", so there must be an attempt to enroute tasks of type "1" as much as possible to machines of type "A" (if all machines of type "A" are too busy, tasks of type "1" can be sent to machines of type "B").
So my question is: is there any algorithm/heuristic/academia research that tackles the proposed scenario?
EDIT: I now particularize my problem (too general described above)
The tasks to be assigned are URLs and the machines have to download the HTML pages returned after processing the request for these URLs (distributed Web Crawler).
It might happen that a machine is more suitable than others to process requests of a particular website, because there are several factors that influence here: IP location of the machine, VPN provider it has configured, etc. Depending on this machine configuration, the URL that has been processed can return a navigation cancelled result (the URL could not be processed properly).
I want to minimize this number of "navigation cancelled" requests as well as keeping the distributed system as load-balanced as possible.


texts: Where am I wrong?: "countability" and "recursive enumerability"

texts:
I have a a few fundamental doubts in recursive enumerability and countability and below, I have written what I understand them to be with proofs. But there are contradictions at the end. What is wrong with the statements/proofs i have made?

Countability (C=Countable): A set $X$ is C when a bijection exists between the set of natural numbers and the set $X$

Recursive Enumerability (RE= Recursively Enumerable): Say set $S'$ is a subset of another set $S$. When there exists a turing machine with alphabet $A$ (where $S$ is a subset of $A^*$) which halts if the input to it belongs to the set $S'$ and does not halt if the input belongs to $S-S'$ then I say that the set $S'$ is recursively enumerable (given the fact that inputs comes only from the set $S$ and not from $A^*-S$ hence the latter will not concern us.) I have referred to the book "Elements of the theory of Computation" by Papadimitrou for this definition, though the introduction of an alphabet A is my own addition to make things more firm

Now I will prove 2 statements:

if a set $X$ is RE then it is C
if a set $X$ is C then it is RE

Hence proving 3. RE iff C

I will prove 2 first.

I can write a Turing Machine $M$ which when asked to check if an element $x$ belongs to $X$ or not will follow the algorithm:

There exists a mapping from the set of natural numbers to $X$ call it $f$. $M$ can search for $x$ (like a linear search algorithm running on $X$) starting from $f(1)$ going to $f(2)$... and it keeps going till it finds $x$. By this method, $M$ terminates iff $x$ belongs to $X$.

The behaviour above proves that $X$ is RE

Now I prove 1- Given a Turing Machine $M$ exists which halts iff $x$ belongs to $X$

I can construct a bijective map from the set of naturals to $X$ as follows: To map $x$ (given it belongs to $X$) , we run it as input against $M$. I take the concatenation of all configurations (Configuration=tape head position+tape content+state) of $M$ which it goes through from the starting of a computation to the end and decode that string as a natural number. It will be unique.

Hence 1. is proven and so is 3.

But then I find certain resources on the internet which tell me that enumerability and recursive enumerability are different things. How is it possible? Furthermore- We know that the power set of a countably infinite set is uncountably infinite. If $X$ was countably infinite, it would be RE (see 2.). Now we know that the subset of a set which is C is also C. Hence all subsets of $X$ would be C hence they would be RE. Now there would be an uncountable number of RE sets.

Now for each RE set, we can write a turing machine (with appropriate halting behaviour) which can be encoded as a natural number implying that the "set of all RE sets" must be C. This contradicts the conclusion of the previous paragraph.

Where exactly am I wrong?
Thankyou in advance!


texts: How to represent a map data structure mathematically

texts:
Wondering how to represent a map object such as the following mathematically:

var foo = {
  a: 10,
  b: 'bar',
  c: true
}

You could say that it was a function like this:

foo(x, y, z)

where $x$ is an integer, $y$ is a string, and $z$ is a boolean. But the question then is how to say the names of the keys a, b, c. Something like:

foo(label(x, a), label(y, b), label(z, c))

But then wondering about how type theory deals with this, so I' a bit confused. Wondering how computer science would model this data structure using mathematical notation. Maybe:

$$
\begin{align*}
foo = \left\{
  \begin{array}{r@{}l}
& a = x \\
& b = y \\
& c = z
  \end{array}
  \right\}
\end{align*}
$$


texts: Why $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ doesn't refute the lower bound $O(n^{3-\delta})$?

texts:
I have a simple quesiton:

  It is conjectured that All Pairs Shortest Path (APSP) has no $O(n^{3-\delta)}$-time algorithm for any $\delta >0$ by SETH.

also

  there is a result that says APSP can be solved in time $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ by Ryan Williams.

But, this improvement doesn't refute the conjectures.

So, what I did is as following: I compare between $\lim_{n -> \infty} \frac{( \frac{n^3}{2^{\sqrt{\log n}}})}{n^{3-\delta} } = 0 $ So, $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ is better than the other one, so why it doesn't mean that we refute the conjecture.

When I have this function: $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$, I didn't know how to compare it with other since Big Omega is only on part of it, how to compare in general with other function when you have this one?

Thanks in advance!


texts:
I'm coming to Computer Science from Mathematics and am familiar with the idea of building classes of objects using Propositional Logic. Namely, start with some universe of objects, define some proposition $P \left( x \right)$, and then iterate over the universe of objects, applying $P \left( x \right)$ to each; keep the objects for which $P \left( x \right)$ is true; exclude each object for which $P \left( x \right)$ is false.
So, when we define a class of objects called $\mathbb{NP}$ (as in P vs NP), I really need to see a formal definition of the proposition used to build that class--as well as a formal definition of the universe of objects we're starting with.
Defining the Universe of Discourse, $\mathbb{U}$
My understanding is that, for the question of $\mathbb{P}$ vs $\mathbb{NP}$, our universe of discourse is all decision problems that are satisfiable. Namely, problems that can be implemented in boolean logic, return a boolean result, and that someone somewhere at some point has found a finite sequence of inputs that cause the implementation to return $TRUE$.
In spite of Russell's Paradox, let us define our universe of discourse as the set $\mathbb{U}$.
Defining $\mathbb{NP}$
$\mathbb{NP}$ is a subset of $\mathbb{U}$. Namely, it is the set of all objects in $\mathbb{U}$ for which the following proposition returns $TRUE$:

This object can be written as a decision problem that returns a boolean value, that decision problem can take any amount of time to resolve, and--as long as the decision problem resolves--given a sequence of inputs that cause the decision problem to resolve to $TRUE$, we can verify the correctness of that resolution in polynomial time.

So, in defining $\mathbb{NP}$, we are really applying our class-defining proposition $P \left( x \right)$ to objects that are compositions of four other objects: namely, a decision problem, a sequence of inputs, an output, and an algorithm for verifying the output is indeed determined by the inputs.
Furthermore, the only object in that composition whose run time we care about is the verifier: the decision problem can run in any amount of time--so long as it resolves. But the verifier needs to return in polynomial time, $O \left( n^{ O \left( 1 \right) } \right)$.
Furthermore, the $\mathbb{N}$ in $\mathbb{NP}$ stands for "nondeterministic". That word is meant to describe the following, further clause in our proposition for defining $\mathbb{NP}$:

If we are given no known solution to the decision problem being examined, we should be able in polynomial time to do the following:

Randomly choose values from the decision problem's input space.
Plug those values into the verifier.
Repeat until we find a sequence of inputs that both satisfy the decision problem and cause the verifier to return $TRUE$.

Is my understanding of the proposition used to define $\mathbb{NP}$ correct?


texts:
Given two strings, A and B, of the same length $n$, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.

I've tried bruteforce, and this can be achieved in $O(n^2)$. I'm looking for any kind of optimization that is faster than $O(n^2)$. I'm not familiar with backtracking and DP. So, can anyone throw some light?


texts: Understanding trap and dead state in automata

texts:
Well, this sounds somewhat basic definitions, but I feel they needs to be clearly defined.

In book by Hopcroft et. al., there is an excerpt:

  ...a dead state, that is, a nonaccepting state that goes to itself on every possible input symbol...

In book by Peter Linz, there is an excerpt:

  ...the automaton finds itself in state $q_2$, with the transition $\delta(q_2,0)$ undefined. We call such a situation a dead configuration...

The same book have following excerpt too:

  ... the dfa goes into state $q_2$, from which it can never escape. The state $q_2$ is a trap state.

So I want to know if following facts are correct:

Trap state is one from which we cannot escape, that is, it has either no transitions defined or transitions for all symbols goes to itself.
I feel, definition on this page for dead state is more correct:

  Once the machine enters a dead state, there is no way for it to reach an accepting state.

So a trap state can be final or non final, since both can have either no transitions defined or have transitions for every symbol happening to itself.
Earlier I felt:

  A final state cannot be a dead state, as we can read $\epsilon$ and stay in the same state, which is final state.

But this, seems incorrect, as epsilon moves are not allowed in DFAs.
Thus trap state is always a dead state.
It does not makes sense to have non-trap dead state. I mean it makes no sense to show outgoing transition from dead state, if that transition does not lead to some final state further on its path. Thus dead state is always a trap state. Right?
As I write these points and think, now, I feel both concepts are one and the same and I am unnecessarily getting confused.
This page also has following statement:

  Techincally, this automaton is not a DFA, because it lacks transitions on most symbols from each of its states.

then it says:

  ...add a transition to the dead state from each other state $q$, on all input symbols for which $q$ has no other transition. The result will be a DFA in the strict sense.

I feel DFA (regardless of any attribute attached to it: strict or non strict) can have dead state as it does not eliminates its "deterministic" nature. Right?


texts: Show that RP is closed under concatenation

texts:
I'm trying to prove the following problem:

  Show that $RP$ is closed under concatenation

Now, let's say that the two languages are $L_{1}$ and $L_{2}$ (both in $RP$). Then I accept a word iff the TM of $L_{1}$ accepted the first part of the word (with a probability $\geq\frac{1}{2}$), and the TM of $L_{2}$ accepted the second part of the word (with a probability $\geq\frac{1}{2}$).

But then each word in the language $L_{1} \circ L_{2}$ would be accept with a probability of $\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4}$, so the language $L_{1} \circ L_{2}$ will not be in $RP$.

So what is the correct proof to the problem?


texts: Is Rectilinear Steiner Tree still NP-complete when points have integral coordinates?

texts: Garey proved that the Rectilinear Steiner Tree problem is (strongly) NP-hard. I wonder if it is still true when we retrict the points to have integral coordinates and lie on a square of side lenght n^O(1) where n denotes the number of points.


texts:
I asked the following question on math.se but it wasn't really answered so moved it over here as I feel it's more relevant.
I saw the question below on an old stack exchange question when looking to understand NP-completeness. At first, I thought I understood it so I gave it a go but ended up more confused than before (I'm a maths student and computational complexity is my first foray into CS and I'm struggling to get to grips with it).
Question is as below:

Given as inputs integers $a, b$ and $c(i,j)$ for each $i,j \leq a$, decide if there is a permutation $\tau$ of $\{1,2,\dots,a\}$ such that
$$
c(\tau(a),\tau(1))+\sum_{i=1}^{a-1}c((\tau(i),\tau(i+1))\leq b
$$
Prove this problem is NP-complete. Hint: find a reduction from the Hamiltonian circuit decision problem (given a graph, decide whether it contains a Hamiltonian circuit).

It seems very similar to the decision version of TSP (where given a set of cities with the distances between each pair of cities, and a length $k$, does there exist a circuit connecting all cities of length less than $k$).
I've read the proof for NP-completeness of TSP and I feel like I understand the reduction from Hamiltonian circuit decision problem to TSP, but I can't get it to translate into a reduction from HC to this problem.
My understanding to compare this to TSP, is that $a$ is the number of cities, each $c(i,j)$ represents the distance between city $i$ and $j$.
My (fairly poor) attempt at this reduction is as follows;
The problem is clearly in NP as we can non-deterministically "guess" a permutation and calculate the given sum and verify that it's at most $b$ in polynomial time.
Then, given a graph $G=\langle V,E\rangle$ where there are $a$ vertices, say $1,2,\ldots,a$, and $b$ edges of length $c(i,j)$, where $i \neq j$ and $i,j\leq a$, construct the completion of $G'$ of $G$ and a weight function that assigns any edge of $G'$ a 1 if the edge is present in $G$ and 2 if not. This can be computed in polynomial time.
Then if $G$ contains a Hamiltonian circuit (consisting of $b$ edges), this path has weight at most $b$ in $G'$ and so the sum of the lengths of this path is at most $b$ and so the permutation corresponding to the order of this path satisfies the original decision problem for these numbers $a,b$ and $c(i,j)$.
Conversely, if given the numbers $a,b$ and $c(i,j)$ and a permutation $\tau$ that satisfy the problem the associated graph G contains a path starting at $\tau(a)$ and finishing at $\tau(b)$. Thus G has a Hamiltonian circuit.
Thus HC reduces to this problem and hence it is NP-hard and so NP-complete.
I can tell it's wrong but I'm not sure how to properly describe a function relating to Hamiltonian circuits and lengths into weights in $G'$.
Any advice and or pointers would be much appreciated.


texts: Results on the languages recognized by undirected DFAs

texts:
For my Bachelor's thesis, I consider the class of languages recognized by symmetrical DFAs, that is, deterministic (complete) finite automata satisfying the following condition:

Let $A$ be a complete DFA over the alphabet $\Sigma$. If, for every $a\in \Sigma$ and every transition $u \stackrel{a}{\longrightarrow}v$ in $A$, there is a transition $v \stackrel{a}{\longrightarrow}u$ in $A$, we call $A$ a symmetrical DFA (SDFA). If $A$ is not complete, we call it a partial SDFA. We can regard an SDFA as an undirected, labeled graph in a natural way.

I could find an algebraic characterization of the class of languages recognized by (complete as well as partial) SDFAs and deduce some closure properties. However, neither me nor my supervisor are aware of previous results concerning this particular class of regular languages (barring results like Reingold's $\mathsf{SL = L}$ which might seem related).

Motivated by a comment that J.-E. Pin passed on a related question I asked, my question is now:

  Are there results concerning these automata?


texts:
What is the complexity of the problem of computing the cardinality of the union of many (finite) and small sets?

What is both the time and space complexity of the naive algorithm that does this computation?

An inefficient recursive algorithm to do this task is:

Where

This results in Θ(2n) exponential blow up time complexity and this is incredibly bad!

Another iterative algorithm to compute the cardinality is:

This formula was taken from this proof wiki webpage, although it doesn't show any proof, but only the formula itself.

But I don't know how to analysis it's both time and space complexity.

EDIT: It appears that the iterative algorithm, unlike the recursive algorithm, iterates over all the different subsets of {S1, ... , Sn} in order to compute the cardinality of the union of all sets from S1 to Sn, but the number of subsets of {S1, ... , Sn} is 2n, so the time complexity of the iterative algorithm is same as the time complexity of the recursive algorithm, i.e. the time complexity of the iterative algorithm is also Θ(2n) exponential time blow up as the time complexity of the recursive algorithm.

Does exist polynomial both time and space algorithm to compute this?

I tried to google an answer to this question for hours, but I didn't find it anywhere.


texts:
To begin with: what I know of computer science is what friends have told me and what I've read on Wikipedia. Please correct me if I'm using some term wrongly, or if there is something I can clarify.

Let's say I have a directed graph. I want my computer to look at it, and see whether x > y, y > x, or if the relationship between x and y is unknown.

Linear graph

If the graph looks kind of like this it's an easy task:

Just let a = 4, b = 3, c = 2, and d = 1. I can evaluate if a > c by comparing 4 and 2, and the result will be correct.

Tree graph

Now it gets interesting.

Here we have a tree graph. This kind of hierarchical data is discussed by Bill Karwin in these slides, which outlines four different ways of storing hierarchical data in a relational database. You can see a summary table on slide 69. Of these, the "nested sets" model looks like the one I'd prefer.

Directed acyclic graph (DAG)

Now, what if we have a directed acyclic graph?

All of the models described by Bill Karwin above work only if each node has at most one parent. In this graph, and more complex variants of it, any given node can have any number of parents (and any number of children).

My question is: how can I store a DAG in a normal relational database (such as MySQL) so that I can query the database for the relationship between two given nodes?


texts: When inserting into a binary tree, is there a universal agreed upon place to insert then new node to minimize complexity?

texts:
Do programmers (in real life), always insert at the top node or somewhere else? Because in my text book CLRS it is not made very clear, so the insertion process can take a best case of O(1), if you insert it just at the right place, or a worst case when you have to rebalance the entire tree.

So in practice is there a place that all new nodes are inserted?


texts: complexity of outputting the union of a collection of subsets of a set

texts:
This question concerns the time complexity of outputting the unions of subsets of a given set.

Given $m$ subsets of an $k$-element set, can the union of those sets be computed in linear time with respect to $m+k$?  Or $(m+k)p(\log (m+k))$, where $p(x)$ is some polynomial?  Or at least known is there a  subquadratic  algorithm (with respect to $m+k$)?

Any direction on this would be much appreciated.


texts: Can the pre-order traversal of two different trees be the same even though they are different?

texts:
This question pretty much explains that they can, but does not show any examples of there being two different trees with the same pre-order traversal.

It is also mentioned that the in-order traversal of two different trees can be the same though they are structurally different. Is there an example of this?


texts:
I'm new to build parse trees and I'm really unsure if I'm doing this right. So I have this example Grammar (S->Sa, S->aSa, S->a) and the word I'm parsing is simply aaaa.

My solution would look like

Is this right and is this the only possible parse tree?


texts: 'Texas Hold Em Poker' Agent Heuristics to help decide whether to fold or bet?

texts:
I am designing a poker agent with different heuristics to decide whether to raise, fold or pass (in Texas holdem poker). I am planning to have 4 heuristics with the agent biased to one of them.

The poker game will consist of 10 agents playing against each other.

I have two heuristics now:

bluff - Agent would keep betting until all others fold
odds>pot odds - https://www.youtube.com/watch?v=1wux3avg1CM&feature=relmfu

I need to know what other heuristics a poker agent can use to make a decision.


texts: Proof that language is not regular. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$

texts:
I'm trying to proof that the following language is not regular using pumping lemma.
$L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$

I started by stating that:

$|w\bar{w}| = 2p = |xyz|$

Because of Pumping Lemma the following has to be true:

$1 \leq |y| \leq |xy| \leq p$

Because $|xy| \leq p$ and $|w|=|\bar{w}|$ have to be true, $\bar{w}$ has to be completly in $z$. I now tried somehow to manipulate the first half, so that it always evaluates to a contradiction, but I am stuck.


texts: Can a deterministic language be accepted by a deterministic Push Down Automaton?

texts:
I have a question that asks me to show that the PDA of the language L is not deterministic, but that the language is nevertheless deterministic. I was under the assumption that any deterministic language contains a PDA that is deterministic.

The language in question is: $L = \{w \in \{a,b\}^* : n_a(w) = n_b(w)\}$


texts: How does automated verification of systems with infinitely many states work?

texts:
I need some help with basic definitions and intuition to understand why and how it's possible to verify systems with infinitely many states.

For example, if I consider an x86 computer, and assuming the CPU architecture is a large and finite state machine, it will have infinitely ($\aleph_0$) many possible states (sequences) it can run, so how can systems with infinitely many states be theoretically verified at all?


texts: Can't wrap my head around on building a suffix table for Boyer Moore

texts:
My resources were the following video, as well as this video.
Basically, in one of the videos they state that the good suffix table for the pattern "ABCBAB" is the following:

k
suffix
d2

1
B
2

2
AB
4

3
BAB
4

4
CBAB
4

5
BCBAB
4

and for "DRIDI":

k
suffix
d2

1
I
2

2
DI
5

3
IDI
5

4
RIDI
5

If all of the above is correct, I can't understand why in the first table, for k = 5, we have d2 = 4 (because we match the A with the suffix "BCBAB"?), where as in the second table for k = 4, we cannot do the same (match D with the D inside the suffix "RIDI"), hence why the value for d2 is the length of the pattern, i.e 5 and not 3.
What's going on here?


texts: What does an = sign with an x beneath it mean?

texts:
I am studying for a test in Logic right now, and saw the symbol $\underset{x}{=}$, which is used like this: $I \underset{x}{=} I'$.

I've seen it in the solutions of questions like this one:

  Prove that $\lnot \exists E \mathrel{=\!\!\!|} \forall x \lnot E$.

The theme is 'Satisfiability'. There is an exercise in which I need to prove equivalence. I know that there exists a law that says the following:

Let $M$ be a model and $I$ an assignment.
We can say that $(M, I)$ satisfies a formula $A$, and write $(M, I) \vDash A$ if:

$$(M,I) \vDash \exists x\,A$$

iff there is an assignment $I'$ that is different from $I$ at most by $x$, so that

$$(M,I') \vDash A\,.$$

Does the sign that I mentioned above mean "different from (something) at most by $x$"? Or is there a different sign for this?

Please excuse me if I used the wrong terms. I study in a different language.


texts:
I am confused in finding RAW dependencies whether we have to find only in adjacent instructions or non-adjacent also.

consider the following assembly code

I1: ADD R1 , R2, R2;

I2: ADD R3, R2, R1;

I3: SUB R4, R1 , R5;

I4: ADD R3, R3, R4;

FIND THE NUMBER OF READ AFTER WRITE(RAW) DEPENDENCIES IN THE Above Code.

I am getting 2 dependency  I2-I1 and I4-I3.


texts:
Here is the question:

Show that $L = \{0^m1^n : m > 1, n > 1, n < m \}$ is not regular.

I am not sure what superscripts mean in this situation? Does it mean something like this:

$0^5 = 00000$ or $1^7 = 1111111$.


texts: Computer Networks: Does integrity depend on confidentiality?

texts:
I'm taking the course computer networks and we currently had our second lecture. We got the following question:

  What are the differences between integrity and confidentiality of a message? Is confidentiality possible without integrity? What about integrity without confidentiality? Explain.

From what I understand the main difference between confidentiality and integrity is that "confidentiality" should prevent from spying on the message / intruders. And "integrity" is to ensure that the original message hasn't been altered in any way (modification/deletion/insertion).

What I'm unsure about: Does confidentiality mean that a possible interuder can't decode the ciphertext, or does this mean he can't even intercept the cipher?

To the two questions about the dependecies of integrity and confidentiality:
At first I thought: If an intruder can't intercept the message (break confidentiality), there's no way he can alter the message in any way (break integrity). But the more I think about that, the less certain I become. Especially when I think about deletion of a message.

Thanks a lot in advance for clearing things up.

  P.S: I hope "confidentiality" and "integrity" are the right terms in English. We learned "Vertraulichkeit" & "Integrität" in German.


texts: Are all finitely recursive context free languages parseable with a regexp?

texts:
Let's say I have a context free language. It can be recognised by a pushdown automaton. Chances are it can't be parsed with a regular expression, as regular expressions are not as powerful as pushdown automata.

Now, let's put an additional constraint on the language: the maximum recursion amount must be finite.

Because the stack size has an upper bound in this case, my understanding is that there are finite number of stack configurations reachable. This means I could number them 0, 1, 2, 3, ..., N. So, I should be able to create a deterministic finite automaton (DFA) with states 0, 1, 2, 3, ..., N that recognises the same language that the pushdown automaton recognises.

Now, if I'm able to create an equivalent DFA, doesn't it mean that there exists a regular expression that can parse the context-free language with maximum recursion amount?

So, my theory is that all context-free languages that have a maximum recursion amount can be parsed with regular expressions. Is this theory correct? Of course, the theory says nothing about the complexity of the regular expression, it just says such a regular expression should exist.

So, in other words: if your stack memory is limited, a regexp can do the job of a HTML/XML parser!

In principle, isn't it true that computers with finite memory are actually DFAs and not Turning machines?


texts:
Consider the situation, when you're given M byte arrays of size N, and you need to check if all of them have unique content (so there are no two arrays that have the same sequence of bytes). What would be the best option to check this condition?
From my point of view, there are several approaches available for this problem (the examples provided below are relevant for Go programming language ecosystem):
Compare hash sums
Take some fast non-cryptographic hash (like murmur3) and compute hash sum from the every array. Store every sum in a set and find duplicates.  Provided that hash is O(N), the whole operation should be O(M*N):
func unique(arrays [][]byte) bool {
   set := newSet()
   for _, array := range arrays {
       sum := hash(array)
       dump := hex(sum)
       if set.contains(dump) {
            return false
       }
       set.add(dump)
   }
   return true
}

Compare arrays bytewise
In Go there is [bytes.Equal][2] function written in pure assembly which can utilize platform-dependent optimizations. So it's possible to iterate over the arrays and check equality pairwise for O(M^2*N):
func unique(arrays [][]byte) bool {
    for i := 0; i < len(arrays); i++ {
        for j := i + 1; j < len(arrays); j++ {
            if result := bytes.Equal(arrays[i], arrays[j]); result {
                return false
            }
        }
    }
    return true
}

Despite the fact that this algorithm has worse computational complexity, it may run faster due to above-mentioned optimizations.
String(?) algorithm

Take ith byte from every array
Compare bytes;
If all are unique, return true;
If there are repeating values, repeat step #1 for (i+1)th bytes for only those arrays which had equal ith bytes.

This should be also O(M*N), because in the worst case one would have to completely compare all arrays. But it seems like this approach will bring too much overhead (I mean state of algorithm between iterations etc.)
Please share your opinion about the optimal way to solve this problem.


texts: Big O notation for Average case in Linear search

texts:
Average case complexity for linear search is (n+1)/2 i.e, half the size of input n.
The average case efficiency of an algorithm can be obtained by finding the average number of comparisons as given below:
Minimum number of comparisons = 1
Maximum number of comparisons = n
If the element not found then maximum number of comparison = n
Therefore, average number of comparisons = (n + 1)/2
Hence the average case efficiency will be expressed as O (n).(I've seen this in many websites...)
Here, how can we say it as O(n) in big O notation or terminology. It should be O(n/2), I suppose. Kindly clarify me


texts:
I have a problem that I was able to conceptualize as following:
Problem
We have a set of n people. And m subsets representing their ethnicity like White, Hispanic, Asian etc. Given any combination of these people, I want to check if it is a diverse group.
A diverse group is a group that satisfies several requirements, each requirement is of the form "at least $k_i$ persons in the group belong to subset $S_i$". Here is the tricky part, one person can only be used to satisfy one requirement. As in, you can't use him/her for multiple requirements.
Example:
Given:
At least two people from Hispanic= {a,b,c}
At least two people from African={a,d,e}
Is the group {a,c,d} a diverse group?
The group {a,c,d} is not diverse because you cant count a as Hispanic and African. But, the group {a,c,d,e} is diverse because we have two Hispanics a and c and two African d and e.
Attempt:
I think this is an instance of the Assignment problem. The jobs are the ethnicity and we can put as many ethnicity as the requirement dictate. For example, if we need two Hispanic, then we put two Hispanic jobs. However there only some people are able to do a particular job. Is there a name for such a problem? any algorithms somewhere in the internet? If not how would the implementation look like?
This is my attempt so far:
I will construct a bipartite graph with the set of people $P$ on one hand and the set of ethnicity on the other $S$. We will put an edge between a person $p_i$ and an ethnicity $S_i$ if he/she belongs to the ethnicity.
Now, we will modify the graph, for every ethnicity $S_i$ duplicate it $k_i$ times ($S_{i,1}, S_{i,2}, ... , S_{i,k_i}$). And add new edges accordingly. Find the maximum matching M of this graph.
Now, merge the $S_{i,j}$s into one $S_i$ and there you have a diverse group. However, a maximum matching is only a possible solution to to the problem. And my problem is a decision problem, I want to check if a given group is a solution or not.


texts: Maximum sum difference between two sorted array elements under one condition

texts:
We're given two arrays $A$ and $B$ with size $N$ and $M$ respectively. We want to find a set $P = \{(a_1, b_1), \dots, (a_s,b_s)\}$ such that

for each $i\in\{1, \dots, s\}$, $a_i\in A$, $b_i\in B$ and $a_i>b_i$ and $a_i,b_i$ musn't be chosen before;
$\sum_{i=1}^s (a_i-b_i)$ is maximized.

A natural approach is to sort array $A$ in descending order and $B$ in ascending order, initialize $i$ and $j$ to $1$, then iterate: while $A[i] > B[j]$ add $A[i] - B[j]$. How we can prove that this solution works?


texts: In the shor's quantum circuit, what is the transformation of the modular operating gates?

texts:
I know different parts of this circuit, just I have a problem with that part that I circled in picture.
I want to know the function of that part.
If you have useful information about it, please share it with me.
Thank you so much.


texts: Relation between Lattice and Boolean Algebra

texts: In discrete math, I have read that lattice is a generalized form of boolean lattice. But those places where boolean algebra is mentioned, they don't tell about lattices (digital logic, binary,...). Whether the meet and join is same as and and or in boolean logic? If we are thinking in terms of lattices how you define 1 and 0 = 0? We consider only a two element lattice?


texts: Can the isomorphic graph problem be solved in deterministic polynomial time?

texts:
Here is a recent homework problem of mine:

  Call graphs G and H isomorphic if the nodes of G may be reordered so
  that it is identical to H. Let ISO = {⟨G,H⟩| G and H are isomorphic
  graphs}. Show that ISO ∈ NP.

In order to solve this problem, I created a non-deterministic Turing machine that did the following:

Check if each graph has the same number of nodes
Non-deterministically arrange the edges of G in a permutation that matches H
Verify that each edge in the permutation of G matches the corresponding edge in H

As far as I know, this approach is acceptable for solving this problem with non-determinism.

My question is this: if we can compare the edges in the permutation of G against H, why can't we simply check to see if each edge in the original list of edges in G (a maximum of $n^2$ nodes) has a matching edge in H (which also has a maximum of $n^2$ nodes) for a total big O of O($n^4$)?  If this is possible, does that mean that this problem is in P?


texts:
I am using a sensing board able to detect magnetic signals between the board and a display.

I have a set of objects that are represented (each of them) by a unique set of points (magnets) with a particular shape. For example: object #1 is made by three points that form an equilateral triangle with side length 1cm; object #2 is made by three points that form a right triangle with sides 3cm, 4cm, 5cm; object #3 is made by three aligned points with distance 2cm; and so on. I can have a multiplicity of objects with unique patterns.

Now I have a list of points with the coordinates w.r.t. the Cartesian plane, and I need to match them referring to the patterns I got from the objects. I also know that every point must be matched, therefore I can minimize the overlapping errors. In practice, every point in the set can belong to maximum one object, and at the same time also it must belong to an object of the initial set.

Any idea on how to do that in an efficient way?


texts: Polynomial space complexity with exponential size witnesses

texts:
Define the complexity class $C$ to be the class of all languages that can be verified by a TM that has:

Input tape: Read only, move in both directions.
Witness tape: Read only, move only in one direction.
Work tape: Read-Write, move in both directions.

The machine itself is deterministic (the guesses are the value of the witness tape). The space complexity is the size of the work tape, and is polynomial. We say the machine
accepts an input if and only if there exists a setting for the witness tape, with which the
machine accepts.

Prove: $C = \mathrm{PSPACE}$

Well, it's obvious that $\mathrm{PSPACE} \subset C$ since any TM $M$ can be converted into a TM $M'$ that simply ignores its witness tape and runs in the same space complexity as $M$.

However, I'm struggling with the other direction. The problem is that the witness can be exponential in the input and I can't see how we can enumerate over all witnesses using only polynomial space.

edit: I had a mistake, the witness tape can only be read in one direction.