texts: Parity check and magnitude comparison in Residue Number Systems

texts:
Let

$\{m_1,...,m_t\}$ be a set of relatively coprime integers
$M=\prod_{i=1}^tm_i$ the range of this system
$X$ an integer such that $X \in [0,M-1]$

This forms a Residue Number System and every integer $X$ can be uniquely represented in RNS format as
$(x_1,\dots,x_t)$, where $x_i = X\bmod m_i, \forall i\in[0,t]$.

One can add,subtract,multiply efficiently in RNS by adding,subtracting,multiplying modulo $m_i$ in parallel the corresponding RNS digits as in

$X\otimes Y=(x_1,\dots,x_t)\otimes(y_1,\cdots,y_t)=(x_1 \otimes y_1,\cdots,x_t \otimes y_t)$, where $\otimes=(+,-,\times) \bmod m_i$

There are various operations though that are not efficient in RNS, like parity check or magnitude comparison. I've encountered an interesting algorithm for parity check directly in RNS and I would like to take advantage of it to perform sign detection (in fact checking whether the result of $X-Y$ is negative or not). The idea comes from another topic where I quote exactly the part I don't understand:

"...one can compute $X-Y$ and if it underflows, the parity will be unexpected. That is, if $p(X)=X \bmod 2$,   $p(X)\in\{0,1\}$ is the parity function, then $p(X−Y) \equiv p(X)+p(Y) \bmod 2$. However, if it underflows, it will wrap around to $M−1$. Therefore if the parity is off after $X−Y$, you know that $Y>X$".

What is meant by "parity if off?" How can I check an underflow by just checking the parities?


texts:
Let the language be : $$ L = \{ w \in \{a,b\}^* : \#_a(w) = \#_b(w)\}. $$
Now the PDA that I've designed for this language and seen at many other places is :

Let the PDA be denoted by M such that,
M = ({q0,q1}, {a,b}, {z0, a,b}, q0, delta, z0, q1)

Transitions for accepting L:
delta(q0, a, z0) = (q0, az0)
delta(q0, a, a)  = (q0, aa)
delta(q0, b, z0) = (q0, bz0)
delta(q0, b, b)  = (q0, bb)
delta(q0, a, b)  = (q0, epsilon)
delta(q0, b, a)  = (q0, epsilon)
delta(q0, epsilon, z0) = (q1, z0)

Now, if a PDA has to be termed as DPDA, then it should follow the following 2 properties strictly :

 1. delta(q, a, b) will contain atmost 1 element
 2. if delta(q, epsilon, b) != empty_set
      then, for every input symbol c on state q,
            delta(q, c, b) == empty_set should hold true

Source : An Introduction To Formal Languages And Automata 6th Edition, Peter Linz

But the above mentioned PDA contains the following 2 transitions that violate the second condition:

delta(q0, epsilon, z0) = (q1, z0)
delta(q0, a, z0) = (q0, az0)
delta(q0, b, z0) = (q0, bz0)

Issue : According to my understanding of DPDA, this PDA should be a NPDA. But at few places I've seen this PDA marked as DPDA, which I feel is wrong. So can you help me clear this doubt?


texts: Why do we need the valid-invalid bit in a page table?

texts:
I'm reading about memory management in Operating System Concepts, by A. Silberschatz. The author says:

  [...] the user process by definition is unable to access memory it does not own.
  It has no way of addressing memory outside of its page table, and the table
  includes only those pages that the process owns.

Then, the author explains the need of having a valid-invalid bit:

  One additional bit is generally attached to each entry in the page table: a valid–invalid bit. When this bit is set to valid, the associated page is in the process’s logical address space and is thus a legal (or valid) page. When the bit is set to invalid, the page is not in the process’s logical address space.

Why do we also need a valid-invalid bit, if a process is by definition able to access only memory addresses stored in its own page table?

The two quoted sentences appear to be contradictory, in my opinion. There must be something I am missing here.

This exact same question has been already asked a few times;
however, none of the answers clarified my doubt. Source:

What’s the purpose of having valid-invalid bits in page table?
Valid-invalid bit in a process page table
What is the need for valid/invalid bit in paged memory technique?

The answers that other users have given don’t explain why the validity bit is needed to protect address spaces. The page table of a process contains only those pages that are valid for that process (i.e., that the process actually owns), so why do we need to replicate a security feature that is already present thanks to the way the page table is implemented?


texts: How does the OS determine the CPU burst time of a process?

texts:
This question is related to OS. After having solved many problems in CPU scheduling I was wondering how does the CPU know the burst time of all the processes in the main memory before executing them?

Selecting a process among a pool of processes using some scheduling algorithm is done based on CPU burst of each process(SJF,SRTF etc). And I'm aware of the predictor formula. And yet I'm trying to get the whole picture as clearly as possible.
How does that equation help choose which process is to be executed next?


texts: Are entities in a many-to-many relation related individually?

texts:
I know in some many-to-many relationships, an entity is related to other entities on an individual basis. But is this always the case?

For example, in the Authorship relationship between authors and books. An author can write many books, and a book can have many authors. In each such connection, an author is individually connected to the book he/she authors, and vice versa, a book is individually connected to its authors.

However, in some cases, a group of things relate to another group of things. The relationship seems to be between the groups of entities rather than individual entities.

For example in the picture below, one road is drawn as two segments i1 i2 in one map, and three segments j1, j2, j3 in the other map. In a sense, the two groups of segments form a one-to-one correspondence.

But does this situation constitutes a many-to-many correspondence in relational database theory?

If yes, this is weird, because unlike the authorship relationship, i1 seems to have nothing to do with j3 individually.

If not a many-to-many relationship, what is this kind of correspondence in relational database theory called? And how do we translate this to physical table design?


texts:
I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated!

  Suppose we are given a matrix $\{-1, 0, 1\}^{n\ \times\ k} $, for example,

  $$\begin{bmatrix}
    1 & 0 & 1 & 0  & -1 \\
    -1 & 0 & 0 & 0  & 1 \\
    0 & 1 & 1 & 0 & -1 \\
    -1 & -1 & 0 & 1  & 1 \\
    1 & 0 & 0 & 0  & -1
    \end{bmatrix}$$

  Without trying every single permutation, find an ordering of columns $c_i$ that maximises the number of rows for which the first non-zero element is $1$.

For the example above, one such ordering (it's not unique!) is $(c_3, c_4, c_1, c_2, c_5)$, i.e.,

$$\begin{bmatrix}
    1 & 0 & 1 & 0  & -1 \\
    0 & 0 & -1 & 0  & 1 \\
    1 & 0 & 0 & 1 & -1 \\
    0 & 1 & 1 & -1  & 1 \\
    0 & 0 & 1 & 0  & -1
  \end{bmatrix}$$

Here, for $4$ out of $5$ rows the first non-zero element is $1$.


texts: How to demonstrate that a language is regular for k?

texts:
I sort of need an explanation on how can I demonstrate that a language formed by strings that are multiples of k, is a regular language

I really dont know how


texts: Generating uniformly random bits from a stream of arbitrarily biased bits

texts: Say we have a function called GenBiasedBit. This function returns 1 with probability p (where p is an unknown real number between 0 and 1 exclusive) and returns 0 with probability 1 − p. How could I write a Las Vegas algorithm (called GenUnbiasedBit) that returns 1 or 0 with equal (nonzero) probability, using calls from GenBiasedBit as a source of randomness? I'm not really sure how to approach this problem. Since 1 and 0 must be generated with equal chance, I'm assuming they must both have a 50/50 chance of being selected. Since this is a Las Vegas algorithm, I'm not sure how to guarantee that its output is correct, if we don't know the probability of GenBiasedBit generating a 1 or 0.


texts: How would a neural network deal with an arbitrary length output?

texts:
I've been looking into Recurrent Neural Networks, but I don't understand what the architecture of a neural network would look like when the output length is not necessarily fixed.

It seems like most networks I've read descriptions of require the output length to be equal to the input length or at least a fixed size. But how would you do something like convert a word to the string of corresponding phonemes?

The string of phonemes might be longer or shorter than the original word. I know you could sequence in the input characters using 8 input nodes (bitcode of the character) in a recurrent network, provided there's a loop in the network, but is this a common pattern for the output stream as well? Can you let the network provide provide something like a 'stop codon'?

I suppose a lot of practical networks, like those that do speech synthesis should have an output that is not fixed in length. How do people deal with that?


texts: How to construct a network flow problem?

texts:
I have the optimization problem given below

max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$

s.t

$\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad   \forall i$

$\quad 2)\quad x_{ij} \in {0,1}$

$\quad 3)\ \ \sum_{j=1}^{M} x_{ij}R_{ij} \geq R^b_{i} \quad   \forall i$

$\quad 4)\ \ \sum_{i=1}^{N} x_{ij}R_{ij} \leq R^u_{j} \quad   \forall j$

$\quad 5)\ \ \sum_{i=1}^{N} x_{ij}\leq N_{eq} \quad   \forall j$

The parameters $N, M, R_{ij},R^b_{i},R^u_{j}, N_{eq}$ are given.

It is clear the problem is binary LP. I would like to construct a network flow problem.

I will set up a network flow problem as follows. There will be four layers.
The first layer is a single node we call the source. The second layer consists of $N$ nodes. The third layer has $M$ nodes. The final layer is one node we call the sink. For each edge, we give a lower bound , upper bound and and a profit, say, $[lb,ub,p]$. One arc enters the source node and we label it as $[N,N,0]$. We label each arc from the source node to each edge in the second layer as $[1,1,0]$. We also label each arc from a node $i$ in the second layer to a node $j$ in the third layer as $[0,1,R_{ij}]$. Arcs from each node in the third layer to the sink node are labeled by $[0,N_{eq},0]$.

Note that this construction does not consider constraint (3) and (4). To consider constraint (3), arcs that does not satisfy $R_{ij}\geq R^b_{i}$ are labeled as $[0,0,R_{ij}]$, not $[0,1,R_{ij}]$ as mentioned above because we want to force its variable $x_{ij}$ to be zero.

My questions are:

Q1: If we ignore constraint (4), is the network flow problem correct?.

Q2: Considering constraint (4), how can I reconstruct the network flow problem?.

Thanks,


texts: Can we do everything in imperative languages with a functional language if it does not allow for a 'state'?

texts:
I was reading Structure and Interpretation of Computer Programs (SICP), MIT. What I have understood is that in pure functional programming language, there is no such thing as a local state. SICP, pg 230 says:

"Programming without any use of assignments, as we did throughout the last two chapters of this book, is accordingly known as functional programming."

I come from a imperative programming background, and I can't seem to comprehend how to design a  program that models a real world system (like a simple bank or a library management software) without the idea of state.

If functional programming does not have the idea of a state, how do we do this?


texts: Is there a name for algorithms which detect nearly-similar structures?

texts:
I'm interested in how you might detect similarities in tree structures. For example, in these three JSON documents;

(a)   { name="foo", length=23 }
(b)   { name="boo", length=99, redundant=true }
(c)   { quux="baz", a=44, b=66, c=99 }

it's obvious to the human eye that (a) and (b) are more similar, in content and structure, than (a) and (c). However, I don't know of heuristics I might use to quantify that similarity.

I'm sure such algorithms exist -- they might exist, say, in code that detects similarities in parse trees or abstract syntax trees, to detect duplicate code structures -- but I've no idea how to search for more information because I don't know what to look for.

Is there a name for this kind of algorithm, where you're looking to be able to calculate 'near-ness' between different trees, graphs, or sets?

(Aside: I've just found out about the Levenshtein Distance so maybe there is a common technique like 'print out your data structures as strings and calculate distances between the printed strings' but I'm very new to the concept.)


texts: Complexity class (P/NP) variants of Hamiltonian paths problems

texts:
I know that the following problems related to Hamiltonian paths in graph are NP-complete:

Undirected Hamiltonian circuit:
Given an undirected graph, does it has a cycle that passes through
each node exactly once?
Undirected Hamiltonian path:
Given an undirected graph, does it has a path that passes through each node exactly once?
Directed Hamiltonian circuit:
Given a directed graph, does it has a directed cycle that passes through each node exactly once?

But then my textbook says following problems are NP-Hard but not NP-complete:

Problem A: Finding a Hamiltonian circuit in a graph with number of vertices $|V|$ divisible by 3
Problem B: Determining if Hamiltonian circuit exists in the graphs as given problem A.

Why is this so?


texts: Which non-regular languages are in $AC^0$?

texts: For example, I know that the non-regular language $a^nb^n$ is in $AC^0$. I would like to know more examples like this.


texts: How to efficiently compute the most isolated point?

texts:
Given a finite set $S$ of points in $\mathbb R^d$, how can we efficiently compute a "most isolated point" $x\in S$?

We define a "most isolated point" $x$ by

$$x = \arg\max_{p \in S} \min_{q \in S \setminus \{p\}} d(p,q)$$

(I used the $x=\arg\min$ notation even though it is not necessarily unique. Here $d$ denotes the euclidean distance.)
So in other words we're looking for a point with the largest distance to the closest neighbour.

A naive algorithm would be computing all pairwise distances, finding the neighbour with the least distance for every point and then finding the maximum of these. This is takes $O(n^2)$ operations, but can we do better than that?


texts: Pumping lemma for L = {a^i b^j c^k: i < j < k}

texts:
I had a question regarding a specific proof I found online that I had some concerns with, I have quoted it below.

  Show that the language L = {a^i b^j c^k: i < j < k} is not a context-free
  language.

Solution:  If L were context free, then the pumping lemma should hold.
Let z = a^n b^{n+1} c^{n+2}.  Given this string and knowing that |z| >= n,
we want to define z as uvwxy such that |vwx| <= n, |vx| >= 1.
Because |vwx| <= n, there are five possible descriptions of uvwxy:

   1.  vwx is a^p for some p<=n, p>=1
   2.  vwx is a^p b^q for some p+q<=n, p+q>=1
   3.  vwx is b^p for some p<=n, p>=1
   4.  vwx is b^p c^q for some p+q<=n, p+q>=1
   5.  vwx is c^q for some i<=n, i>=1

   Note that because |vwx| <= n, vwx cannot contain both "a"s and "c".
   For all of these cases, u v^i w x^i y, i>=0, should be in the language.

   In case 1, if i=2 we will be adding an a to the string, making the
   number of "a"s n+1 and thus the string is not in the language.  The
   same argument holds for case 3 in which the number of "b"s will be
   equal to the number of "c"s.  A similar argument holds in case 5.
   In case 5 if i=0 then the number of "c"s will be less than or equal to
   the number of "b"s.

   In case 2, when i=2 either the number of "a"s will be greater than the
   number of "b"s or the number of "b"s will be greater than the number of
   "c"s (depending on the distribution of v and x).

   In case 4, when i=0 either the number of "b"s will be less than or equal
   to number of "a"s or the number of "c"s will be less than or equal to
   the number of "b"s (depending on the distribution of v and x).

Now my issue comes with the wording of some of these cases. Such as with case 3 where they say "The
   same argument holds for case 3 in which the number of "b"s will be
   equal to the number of "c"s." My issue is depending on the distribution of V and X is there no possibility that there would be more b's than c's in the language. I know that if there were more b's than c's in the string the pumping lemma would be contradicted. But I just wanted to confirm my intuition that based on the distribution of v and x there is a possibility that there would more b's than c's left in the string.

I also feel the same way about Case 2: where depending the distribution of v and x could there not be an equal number of a's to b's?

Thank you in advance I really appreciate the help!


texts:
Consider a recurrence of the form

$T(n) = a T(n/b) + f(n)$

Master theorem's regularity condition excludes some cases (for example, when $f(n)$ is oscillating).

Suppose, however, that $f(n)$ is always less than or equal to a function $g(n)$ that does not violate the regularity condition, so that the master theorem is applicable if $g(n)$ is used instead of $f(n)$.
Consider then the following recurrence:

$T'(n) = a T'(n/b) + g(n)$

and assume that the master theorem gives the solution $T'(n)=\Theta(g(n))$.

My doubt is this: can I then safely conclude that $T(n)=O(g(n))$?

In other words, can I be sure that the solution of a recurrence with a term replaced by its upper bound is an upper bound of the solution of the original occurrence? After all, the recurrence establishes a relationship between $T(n)$ and $T(n/b)$ but says nothing about what happens between $n/b$ and $n$ (and $f(n)$ here is oscillating...).


texts: Determining if my artificial neural network needs additional layers

texts:
I have implemented a neural network for load forecasting in Microsoft Excel. My structure is very simplistic and involves only 1 hidden layer and 4 neurons. (See picture)

I trained my network with a very large set of data and the predictions are as decent as could be expected. However, when I go to try and predict the "future" using recent data, the network is only in the ball-park, not very close at all. Here is a plot of the actual numbers versus the forecast ones.

From looking at this chart, can it be determined if I need another layer or more neurons??


texts: How to map points in high-dimensional space into dense grid in lower-dimensional space?

texts:
A formal description of the problem:

Given a set $P$ of $n^k$ points in $d$ dimensional space, what algorithm can I use to find a mapping between them and points on a $n \times n \times n...$ grid in $k$ dimensional space so that points that are close together in $P$ map to points that are likely to be close together on the grid?

An example of the problem:

Suppose I want to create a 4096 by 4096 image with every possible color that can be stored as a 24-bit RGB value (8 bits per color channel). $P$ is the set of all points in RGB colorspace when using 8 bits per channel, and the grid I'm mapping it to is the image. How can I do this so similar colors end up close together?

I came up with a solution involving a genetic algorithm: it swaps pixels, then compares how similar they are to the other pixels in that region. This solution, however, is very computationally intensive, and requires a lot of time to produce good results. Below is an image generated using the genetic algorithm.

The genetic algorithm I coded has already been heavily optimized at all levels. It's coded in C++; rather than swapping a single pixel it analyzes groups of 64 randomly selected pixels and uses the Hungarian Algorithm to find the optimal way to swap all pixels in the group; the fitness function has been written to allow multiple pixels to be tested at one location with each pixel adding practically no additional computational cost; I've been able to parallelize it too. The above picture is the result of 5 minutes of work. After a few hours of computation it produces this:

Although I'm hoping to find a faster and more elegant way to go about solving this problem.

Using the image analogy, the metric I'm using to calculate fitness is pretty simple. The fitness of the total image is the sum for every pixel of the color distance squared divided by the image distance squared to all the other pixels. To calculate color distance, just treat the color as a vector in 3-dimensional space (red is x, green is y, blue is z) and find the euclidean distance. The image distance is just the distance between two pixels in the image. If $g$ is the function that maps points in $P$ onto the grid, then the fitness is:

$$\sum_{p \in P} \sum_{q\in P \mid q \neq p} \frac{\left\lVert p-q\right\rVert^2}{\left\lVert g(p)-g(q)\right\rVert^2}$$

(In the image example, $g(p)$ returns the x and y coordinates of the pixel with the color whose red, green, and blue channels match $p$)

This function is very expensive to calculate, however there are a number of optimizations that can be made to speed up the calculation a lot, and in general it's not important to calculate the actual fitness; just the change in fitness that would result from swapping some group of pixels (which makes the computation a lot faster). If someone knows of a better metric to use please let me know!


texts: On submultisets of given cardinality and bound that sum to $0$

texts:
Given multiset of integers $a_1,\dots,a_{m}$ where $|a_i|\leq\log^cm$  for some $c\in\Bbb R^+$. Is it $\mathsf{NP}$-complete to decide if there is a cardinality $\lceil m^\alpha\rceil$ submultiset for some $\alpha\in(0,1)$ whose sum is $0$?

How many submultisets of such cardinality can we expect to have vanishing sum?


texts:
I am asked to find

Prove that the following languages are regular languages:
(a) $\{a^nb^ma^k \mid n\geq3,m\geq1,k\geq1\}$
(b) $\{a^n \mid n\neq3 \text{ and } n\not\equiv2 \mod7\}$
(c) $\{a^nb \mid n\geq2\}\cup\{ab^m \mid m≥3\}$

I have a vague understanding of pumping lemma, and how to prove a language is not regular, but was hoping that someone could walk through (a) with me to give me a better understanding and allow me to do the rest on my own.


texts: Why is Church-Rosser so important for basing programming languages on lamdba-calculus?

texts:
So, I know Church-Rosser has 2 thesis:

CR1: If $ E_1 \leftrightarrow E_2 $, then there exists an Expression E so $ E_1  \rightarrow E $ and $ E_2 \rightarrow E $

CR2: If $ E \rightarrow N $ (with N in normalform), then there exists a reduction row in normalorder (first reduce the left most ouuter most index) from E to N

from CR1 we learn that no expression can be converted to 2 different normalforms, so there is only one result for each function

from CR2 we learn that reduction in normalorder always finds the result (if their is one (no loop))

But i don't understand why these two are so important for basing a programming language on lambda-calculus. So my question is why are they?


texts: Why LL(1) grammar generate all regular languages?

texts:
I came across following:

  Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages.

I tried to get that.

Definition: Right linear grammar (RLG)
In right linear grammar, all productions are of one of the following forms: $A\rightarrow t^*V$  or $A\rightarrow t^*$, where $A$ and $V$ are non terminals and $t$ is terminal.

Definition: LL(1) grammar

A grammar $G$ is $LL(1)$ grammar if and only if whenever $A→α|β$ are two distinct productions of $G$, the following conditions hold:

For no terminal $a$ do both $α$ and $β$ derive strings beginning with $a$.
At most one of $α$ and $β$ can derive the empty string.
If $β⇒^*ϵ$, then $α$ does not derive any string beginning with a terminal FOLLOW(A). Likewise, if $α⇒^*ϵ$, then $β$ does not derive any string beginning with a terminal in FOLLOW(A). ($β⇒^*ϵ$ means $B$ derives $\epsilon$)

(Q1.) How definition of RLG ensures condition 1 in the definition of LL(1) grammar.

This answer says:

  All regular languages have LL(1) grammars. To obtain such a grammar, take any DFA for the regular language (perhaps by doing the subset construction on the NFA obtained from the regular expression), then convert it to a right-recursive regular grammar. This grammar is then LL(1), because any pair of productions for the same nonterminal either start with different symbols, or one produces ε and has $ as a lookahead token.

(Q2.) I read somewhere "eliminating left recursion from given grammar does not necessarily make it LL(1)". Then how turning grammar to right recursive will ensure its LL(1) (as stated in above quoted answer)?

(Q3). I didnt get the significance of "one produces ε and has $ as a lookahead token" in above quoted answer.

(Q4.) First quote in this question says right linear grammar is LL(1). How is it so?

(Q5.) This answer says "all regular languages have a LR(0) grammar", I guess its incorrect as LR(0) are DCFLs with prefix property which are not superset of regular languages. Am I right with this?


texts: For example, I have one program that requires $O(i)$ time complexity, and a second program requires $O(j)$ time complexity. Would the total time complexity be $O(i+j)$? And why?


texts: Given a binary tree of leaves with weights, find minimum weights for internal nodes (such that sum(weighti-weightj) is minimized for (i,j)∈E(T))

texts:
So this is a question within a bigger question for which I've reduced to this so far:

If I have a tree (phylogenetic) with known weights for leaves, how would I find the weights for all internal nodes such that the sum of the differences between the weights of two endpoints of edges is minimized?

I.e. Given a tree $T$ with $n$ leaves with weights $D_1,\ldots,D_n$ respectively. Assign;

a weight $D_u$ to each internal node $u = n+1,\ldots,2n-1$ such that
$\sum_{(u,v) \in E(T)} (D_u-D_v)$ is minimized.

If it helps, it might be similar to the Sankoff algorithm or so. Thanks!


texts: How to prove computational completeness of a variant of P system

texts:
I have read a lot of books on membrane computing (P system), of which the computational completeness of several variants are already under investigation. My goal is to design my own variant and prove its computational completeness.

I also know that in order to prove computational completeness many research papers normally prove the equivalence of their variants of P system with variants of formal languages (e.g. context-free, context sensitive languages, Turing machines etc.), those of which are already known to be computationally complete.

My question is how exactly can I prove equivalence of a variant of P system with a formal language?


texts:
Given the following method written in Java:
private void collatz(List<Integer> values) {
     int size = values.size();
     if (size == 0 ||
              values.get(size=1) <= 1) {
              return;
     } else {
        int last = values.get(size = 1);
        if (last%2 == 0) {
           values.add(last/2);
        } else {
           values.add(3*last+1) ;
        }
        collatz(values);
   }
}

My textbook gives the following CFG for the code:

Where each vertex describes the corresponding line of code.  Why is this correct? What I don't understand is the edge between the vertex $13$ and the end vertex, shouldn't this edge be from $13$ to $2$ instead, since we're recursively calling the function? Would really appreciate your input.


texts: Are there any good examples of promise problems that are NP complete?


texts: Mapping reducibility from recursive to recursively enumerable language

texts:
I want to find out whether, assuming a language $L_1$ being mapping reducible (i.e., $L_1$ maps to $L_2$ and the complement of $L_1$ maps to the complement of $L_2$) to a language $L_2$ and $L_2$ being recursively enumerable, $L_1$ is recursive or not.

I tried creating a recursive Turing machine for $L_1$ by using the recursively enumerable machine of $L_2$, but if the input belongs to the complement of $L_1$, its mapping will also be in the complement of $L_2$ and we cannot say anything about it.

So I tried proving by contradiction instead: Assuming $L_1$ is recursive, show that our assumption that $L_2$ is recursively enumerable is wrong. However, this will require an inverse mapping.
Alternatively, we could also try assuming $L_1$ is recursive and show that such a mapping cannot exist, but I can't think of any approach to it.

Can someone help me?

Mapping reducibility of two languages $L_1$ and $L_2$ is defined as a function which, when given a string in $L_1$, gives as output a string in $L_2$ and, when given as input a string in $L_1$ complement, gives as output a string in $L_2$ complement.


texts:
Studying for a test in a computer science class and cannot figure out the answer to this question.  Any help would be appreciated!

Although the picture shows a directed graph, please treat it as an undirected graph, ignoring all the edge orientations.


texts: Given G(V,E) a graph that has 2 connected components, what is the diamter of this graph?


texts: I have a question concerning the use of the Ford-Fulkerson algorithm. Since a minimum cost flow problem is a linear programming problem, it has a dual problem. That dual would be to maximize a certain function. Considering this, is it possible to apply the Ford-Fulkerson algorithm to that dual in order to solve the minimum cost flow problem?


texts: Which one should I report as total network I/O bytes among Sum(InBound) or Sum(InBound + OutBound)?

texts:
I have a set of experiments with distributed environments.

I am planning to present a total network I/O bytes usage of the system for each run.

Which one should I report as total network I/O bytes among Sum(InBound Traffic) or Sum(InBound Traffic + OutBound Traffic)?

For example, say there are two machines A and B in my cluster server.

A sends 10 bytes to B.

B sends 15 bytes to A.

What is the total network I/O bytes? Is it 25 or 50 bytes?


texts: Why does merge sort run in $O(n^2)$ time?

texts:
I have been learning about Big O, Big Omega, and Big Theta. I have been reading many SO questions and answers to get a better understanding of the notations. From my understanding, it seems that Big O is the upper bound running time/space of the algorithm, Big Omega is the lower bound running time/space of the algorithm and Big Theta is like the in between of the two.

This particular answer on SO stumbled me with the following statement

  For example, merge sort worst case is both ${\cal O}(n\log n$) and $\Omega(n\log n)$ -
  and thus is also $\Theta(n\log n)$, but it is also ${\cal O}(n^2)$, since $n^2$ is
  asymptotically "bigger" than it. However, it is NOT $\Theta(n^2)$, Since
  the algorithm is not $\Omega(n^2)$

I thought merge sort is ${\cal O}(n\log n)$ but it seems it is also ${\cal O}(n^2)$ because $n^2$ is asymptotically bigger than it. Can someone explain this to me?


texts:
In all books about this topic, I read that there is a rule of thumb is that 80% of the process execution time is lower than time slice. But how do I calculate this value? I looked at every article possible and I found like nothing. Can someone help me understand this topic?

I know that there is a topic with this question click here. I have the exact same problem, but the answer from there isn't clear to me.

Thanks in advance.


texts: Passing arrays vs functions as arguments in SMT?

texts:
In SAT Modulo Theories (SMT), with the theory of uninterpreted functions, all functions are first order, that is, they don't take functions as arguments or return functions.

In the theory of arrays, however, functions can take arrays as arguments, and return arrays as values.

However, my understanding is that arrays in SMT are just syntactic sugar for functions. That is, an array $a$ indexed by $I$ with elements of type $T$ is just modeled as a function $f: I \to T$. Lookup is just a function call, and extending an array $a[i] := e$ produces the array described by the function $f'(x) = ite(i=x, e, f(x)) $, where $ite$ is an if-then-else operator.

Is there something fundamentally different between arrays and functions that allows them to be passed as arguments? Or is the limitation that functions are first-order an artificial one?


texts: Reducing the vertex cover problem to a variation of the vertex cover problem

texts:
The following variation on the vertex cover problem was given:

  Given is an instance of graph $G = (V, E)$. Does $G$ have a vertex cover of size at most $\frac{|V|}{4}$?

I was asked to prove that this problem is also $\mathsf{NP}$-hard. I am pretty sure that this can be done by using Karp-reduction from the original vertex cover problem to this variation.

That means that I would need some transformation function $f$ that would transform an instance of the vertex cover problem, $I = (V, E, k)$, to an instance of the above described problem, $f(I) = (V', E')$.

I am not sure how to come up with the proper transformation function, but this is what I think have figured out:

Let $V = \{v_1, v_2, ..., v_n\}$.
Let $V' = V \cup V^+$, where $V^+ = \{v_{n+1}, v_{n+2}, ..., v_{4n}\}$, because this would mean that the total size $|V'| = 4 \cdot |V|$.
Let $E' = E \cup E^+$, where $E^+ = \{\{v_i, v_j\} \mid v_i \in V, v_j \in V^+, j \in \{n +i, 2n+i, 3n+i\}\}$. Basically, this means that each vertex in $V$ is connected to three different vertices in $V^+$ such that all vertices in $V^+$ are connected to exactly one vertex in $V$.

However, I am having a hard time proving the correctness of this reduction. I think I messed up the generation of $E'$, which would make the transformation function wrong. Anyone have an idea what the actual transformation function could be?


texts: Generating a recursive descent parser for grammar having Kleene star

texts:
From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar:
\begin{align}
&E \to E+T \mid T \\
&T \to T\cdot F \mid F \\
&F \to F^* \mid a \mid b
\end{align}
I actually changed this to:
\begin{align}
&E \to TE' \\
&T \to +TE' \mid \epsilon \\
&T \to F\cdot T' \\
&T \to \cdot FT' \mid \epsilon \\
&F \to aF' \mid bF' \\
&F' \to ^*F' \mid \epsilon
\end{align}
This is done using the left-recursion elimination formula.
But then I have a doubt about whether it is correct or not, because the last $F$ transition cannot now generate $abb$, which it was able to generate. And if it is still able to do that, I would love to know, how?
Another transition that I tried for $F$ was:
\begin{align}
&F \to G^* \mid G \\
&G \to a \mid b
\end{align}
This was done to remove the left recursion without using any formula.
But then I realized that it made the last transition nondeterministic.
Then I tried changing it by using the left-recursion elimination formula on $F \to G^* \mid G$, making it:
\begin{align}
&F \to GF' \\
&F' \to ^*F' \mid \epsilon \\
&G \to a \mid b
\end{align}
And now I am all confused!


texts: Computing critical pairs, confluence and Normal terms

texts:
Down below is a Term rewriting system where I am trying to find the critical pairs, decide if it is confluent and find the Normal terms. I think it's difficult to understand all these concepts and I am just mixing everything up, I think.

Problem

Consider the $TRS$
\begin{equation}
\begin{split}
(R_1)\quad x\cdot (y + z)&\rightarrow x\cdot y+x\cdot z\\
(R_2)\quad(y + z)\cdot x &\rightarrow y\cdot x+z\cdot x\\
(R_3)\quad\text{ }\text{ }\text{ }(x\cdot y)\cdot z&\rightarrow x\cdot (y\cdot z)\\
(R_4)\quad(x+y)+z&\rightarrow x + (y+z)?
\end{split}
\end{equation}

What are the critical pairs?
Is it Confluent?
What are the normal terms?

Solution

Let us start with the critical pairs:

Critical Pair:

To find the critical pairs we will, as a start, compute
$$(\alpha+\beta)\cdot (y+z)\to_{R_1} (\alpha+\beta)\cdot y + (\alpha + \beta)\cdot z$$
$$(\alpha+\beta)\cdot (y+z)\to_{R_2} \alpha\cdot (y+z)+\beta\cdot (y+z)$$

Now, we found a critical pair $C_1=((\alpha+\beta)\cdot y + (\alpha + \beta)\cdot z,\alpha\cdot (y+z)+\beta\cdot (y+z))$.
So, to find a critical pair We take an expression and apply two different rules and see where we end up? If that's the case I would continue as this:

$$((\alpha+\beta)\cdot y)\cdot z\to_{R_2} (\alpha\cdot y+\beta\cdot y)\cdot z$$
$$((\alpha+\beta)\cdot y)\cdot z\to_{R_3} (\alpha+\beta)\cdot (y\cdot z)$$

So the next critical pair would be $C_2=((\alpha\cdot y+\beta\cdot y)\cdot z,(\alpha+\beta)\cdot (y\cdot z))$. Or should I reduce them as much as possible and that will be my critical pairs? Perhaps I should do both? How do I know if I have found all my critical pairs? I don't even know what I am allowed to do.
  $\text{ }$ :(

I mean, can I do something like this?

$((\alpha_1+\alpha_2)+\alpha_3)\cdot (x+y)$. And this would give me other critical pairs?

Confluent:

Since by starting with $R_1$ and then apply $R_2$ doesn't yield the same term as when we start with $R_2$ and then apply $R_1$ (when we found the first critical pair), thus, the TRS cannot be confluent. Is this a correct interpretation? It shouldn't matter in which order I apply the rules, it should still end up with the same result.

Normal Form:

$$(\alpha+\beta)\cdot (y+z)\to_{R_1} (\alpha+\beta)\cdot y + (\alpha + \beta)\cdot z\to_{R_2} (\alpha\cdot y+\beta\cdot y)+(\alpha\cdot z+\beta\cdot z)\to_{R_4} \alpha\cdot y+(\beta\cdot y+(\alpha\cdot z+\beta\cdot z))$$

So perhaps $N_F=\alpha\cdot y+(\beta\cdot y+(\alpha\cdot z+\beta\cdot z))$ is a normal form (term?) of $(\alpha+\beta)\cdot (y+z)$, since $N_F$ can't be reduced any further.

I really hope someone can help me with this problem. I have been thinking about this for a week now and I cannot get my head around it.

Thanks :)

The book I am using:

"Term Rewriting and All That" by Franz Baader and Tobias Nipkow


texts: Why does converting a NDTM to a a DTM result in a higher time complexity?

texts:
I feel like I am really close to understanding the difference between P vs NP, and I think it comes down to this. The confusion stems from the fact that both P and NP problems are done in polynomial time, but P problems are only polynomial with a DTM (deterministic Turing machine) and NP problems are only polynomial with a NDTM (non-deterministic Turing machine).
Because of the Church-Turing thesis, we know we can construct a DTM that accepts the same problems as a NDTM. This means we can construct a DTM that solves the NP problems.
This is the big question I have: Is the reason why (we think) P != NP because this DTM will be more complex (in terms of time complexity) than the NDTM?
Of course some NP problems are P, so those done with a NDTM and DTM will both have the same complexity (in fact the DTM is also a NDTM) but what about problems that are NP-complete? Those can be done by a NDTM in polynomial time, but will the DTM for that problem always be more complex and by how much?
My understanding for that last question is that the DTM will always be more complex (if P != NP) and it will actually have an exponential time complexity and this is because the DTM will essentially be doing a breadth-first search of the configuration tree of the NDTM.
So my final question, assuming my understanding so far is correct, is why is the breadth-first search of the configuration tree going to take exponential time? e.g. if the problem was done in O(n^2) time by the NDTM, why would doing the breadth-first search for finding the solution in the configuration tree take O(a^n) (for some a > 1)?
Thanks.


texts: What is the purpose of the SKI combinator calculus(or even lambda calculus)? What are some real life examples of its use?

texts: I understand what it is, but I don't see how it is any use for algorithms or anything. Maybe I am missing something. I need someone to give me an example of how it can be used so I can understand it better.


texts: Polynomial time verification of Graph Isomorphism problem

texts:
Using guess and check method, for two given graphs with the same number of nodes, a NTM selects a permutation of the node set and then checks if the edges are preserved.
The nondeterministic selection of a permutation of the nodes is done in polynomial time.
How is the choice of a function done in polynomial time? This is not clear to me.


texts: How to compute all inequivalent (under Aut(P)) nonnegative integer weight assignments (with fixed sum) to the vertices of a finite poset P?

texts:
Let $P$ be a poset on $n$ points, $\text{Aut}(P)$ its automorphism group, and $a_1,a_2,\dots,a_k$ the lengths of the orbits under $\text{Aut}(P)$.
Goal: An algorithm to generate a member from each equivalence class (under $\text{Aut}(P)$) of assignments of nonnegative integer weights to the vertices of $P$ such that the weights sum to $m.$
Partial result: My current algorithm works for $m+n\leq5$ and only misses a tiny fraction of weight assignments for larger values of $m+n.$ For example, for $m+n=6,7,8$ just $1,7,57$ out of $400,2490,18980$ are missed, respectively.
For $m+n=6$ it only fails to distinguish between these two inequivalent weight assignments (black $=0,$ red $=1)$:

The algorithm: Let $C_{i,j}$ and $P_{i,j}$ be the sets of compositions and partitions, respectively, of $i$ with $j$ nonnegative parts. We assign all compositions in $C_{m,k}$ to the set of orbits (one part per orbit) and to each such composition $c_1+c_2+\dots+c_k,$ all possible combinations of partitions $p_{i,1}+\dots+p_{i,a_i}\in P_{c_i,a_i}$ (one part per vertex) for $1\leq i\leq k.$
Since $\text{Aut}(P)=\{(1), (0\ 1)(2\ 3)\}$ for the poset $P$ in the diagram above, its orbits are $\{0,1\}$ and $\{2,3\}.$ Our algorithm fails to recognize it matters whether we select vertex $2$ or $3$ to go with vertex $0,$ assuming $0$ was selected from $\{0,1\}$ under the composition $1+1$ of $m$ and its only possible combination of subpartitions, namely, $1+0$ for each orbit.
The theme gets repeated as we increase $n$:

Most if not all (I haven't checked) of the missing weight assignments for $m+n\leq8$ can be obtained by symmetrically removing edges and vertices from these two posets. Note that the one on the right is self-dual.
The backstory: A year and a half ago I posted this message to Brendan McKay's nauty mailing list asking about the availability of nonhomeomorphic finite topologies online. As per his reply, McKay generously sent me files containing all transitive digraphs on up to 9 points, from which I was able to easily—using his detailed and easy-to-follow instructions—produce all nonhomeomorphic topologies on up to $9$ points (available here).
Unfortunately, he did not mention how to construct the digraphs and I didn't ask. His and Brinkmann's paper Counting Unlabelled Topologies and Transitive Relations enumerates them (see the proof of Theorem 2.1) but it doesn't show how to construct them as far as I can tell. The insufficient, so-close-yet-so-far algorithm above was inferred from McKay's digraphs. Maybe the vertices need to be partitioned (colored); that would refine the orbits, which at least seems to be on the right track.
Closing remarks: An MSE cross-post appears here. My overall goal is to add cardinalities $10$ and $11$ to my collection of nonhomeomorphic topologies. The latter file will be approximately 10 GB uncompressed in adjacency matrix format. I might also post a brief note on my ResearchGate page describing the method of construction.


texts: Cache strategies, what reference article could I study?

texts:
So as to optimize an application, I must implement data caching: not to recompute some data - those heavy on cpu but that don't change often.

When playing with the idea, I imagined something like the way win32/MFC manages the windows screen i.e.:

While a part is valid, it is not repainted.
When a rectangle or a region is invalidated, this part is repainted during the next painting session - launched by the OS.

I was imagining a way to validate and invalidate my cached value, so as to recompute only what is necessary when it is necessary.

Then I read this wikipedia page about Cache Algorithms, and none of the listed algorithm was using the technique I explained above. So I feel ill at ease, and I need to read some work about caching.

Do you know of some resources that I could rely on before I start implementing my own cache process ?


texts: Possibility to prove that a function in big-theta is in big-O and little-o

texts:
I understand that many similar questions of this sort have been asked, but in this case, the solution does not appear to be provable - or is it?

Question: If $f(n) = \Theta (g(n))$ and $g(n) = o(h(n))$ then $f(n) = O(h(n))$

Current solution:

$f(n) = \Theta (g(n))$ implies that $c_1 . g(n) \le f(n) \le c_2 . g(n)$ for $c_1, c_2 \in \mathbb{N}$ and $\forall n \ge k_1$ Call this equation $1$.

$g(n) = o(h(n))$ implies that $g(n) < c_3 . h(n) $ for $c_3 \in \mathbb{N}$ and $\forall n \ge k_1$ Call this equation $2$.

Multiply $2$ by $c_2$.

$c_2 . g(n) < c_2 . c_3 . h(n)$ Call this equation $3$.

From $1$ and $3$ it can be inferred that:

$f(n) \le c_2 . g(n) < c_2 . c_3 . h(n)$

Which means that $f(n) \not\le c_4 . h(n)$ (where $c_4 = c_2 . c_3$) and therefore $f(n) \not = O(h(n))$. Is this way of approaching the problem correct, or is it - as my intuition tells me - I've missed something entirely obvious?


texts: What are the current fastest algorithms for basic mathematical operations?

texts:
In other words, what algorithms have been demonstrated to have the fastest big O notation time/asymptotic complexity for, assuming two real numbers $x$ and $y$:

$x + y$
$x \times y$
$\frac xy$
$x-y$
$x^y$


texts: PHPMyadmin is stated as a 3 tier database architecture.How is  this possible,Isn't it a 2 tier architecture.What are the real world examples of 1-tier and 2-tier architecture.


texts: Is it possible to solve this problem in less than n^2 time without using additional space?

texts:
Here's the problem:

Given an array array containing integers, maximize array[i] + array [j] + |i - j| where i and j both range from 0 to length -1. i and j potentially could be the same.

Upon reasoning, I concluded that it is not possible. Am I wrong?


texts: Assigning all nodes in a tree a parent and children

texts:
If one was given a tree in the form of a list of $A,B$ (not implying which one is the parent) pairs implying that node $A$ and $B$ were connected by an edge, how could a root node be determined and each node be assigned children and a parent such that by recursing up through its parent, its parents parent and so on the eventually one will eventually hit the root  e.g.

Could be represented as
4,1 4,2 4,3 4,5 6,5

and a possible solution could be

1: parent:4, children: None
 2: parent:4, children: None
 3: parent:4, children: None
 4: parent:None, children:1,2,3,5
 5: parent:4, children: 6
 6: parent:5, children: None

where 4 is the root.


texts:
Proving that L is not regular by showing that $\equiv_L$ has infinite index.
$\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0}
My ideas:
theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has finite index
We show: $\equiv_L$ has infinte equivalence classes.
$a^{3^i}$ $\not\equiv$ $a^{3^{i+k}}$, $k>0$
-> equivalence classes: [a], [aaa], [$a^3$]...
Every $a^{3^i}$ is a different equivalence class.
Therefore $\equiv_L$ has an infinite amount of equivalence classes $\rightarrow$ L is not regular. qed.

How to show that the classes are different?


texts: How to build a heap better than Incremental and In-place method using decision tree?

texts:
For an array A = [a1, a2, a3, a4] of distinct numbers, I have built heap using binary decision tree by Incremental and In-place method.

Incremental method:

In-place method:

Is there a way to build heap using decision tree for inputs of size 4 that uses fewer decisions in the worst-case, compared to above methods?

Notes on heap: https://drive.google.com/open?id=0By6GDPYLwp2cY3lfbEVWNHlrSlE
Incremental method - page 36, In-place method - page 48.


texts: Lower bounds of calculating a function of a set

texts:
Having a set $A$ of $n$ elements, let's say I want to calculate a function $f(A)$ that is sensitive to all parts of the input, i.e. depends on very member of $A$ (i.e. it is possible to change any member of $A$ to something else to obtain a new input $A'$ s.t. value of $f$ on $A$ and $A'$ are different).

For example, $f$ could be the sum or the average.

Is there a result that proves that, under some conditions, the time necessary to a deterministic Turing machine to compute $f$ will be $\Omega(n)$?


texts:
$$ L = \{a^ib^jc^k \mid i,j,k > 0 \text{ and } i+k>j\} $$

I say it's not regular. Proof by pumping lemma:
Find a string $xy^iz$ that is not in $L$ (respecting the constraints).
Let $w=x^py^pz^p$.

Let $i=2$.
$x^p(y^py^p)z^p$ is not in $L$.

Thus $L$ is not regular.

Is this proof correct?


texts: Limit repetitions in randomized list with each unique element occurring n times

texts:
I have a set of 3 elements and need to generate a randomized sequence containing each element n times with the condition that one element can only occur m times in a row.

So with elements [0,1,2] n = 4 and m = 3:
[1, 2, 0, 0, 0, 1, 1, 2, 2, 2, 0, 1] valid
[1, 2, 0, 0, 0, 0, 1, 2, 2, 2, 1, 1] invalid

The only solutions I found were to add all elements n times to a list and then shuffle until the condition is satisfied or generate the whole search space and then randomly sample from the correct solutions. Both seem possibly slow and memory intensive.
Could just be looking for the wrong terms, this has to be documented somewhere.

I came up with this approach, but am not sure about correctness.

E: set of elements e
n: of each element in sequence
m: maximum repetitions of one element
S = [] # empty sequence
while |S| < |E| * n:
    R = shuffled list containing each e m times
    for m:
        if s+r satisfies condition:
            S <- s+r # Extend s with r
        else:
            rotate r by one element
return the first |E| * n elements of S

It seems to produce correct results, but is it ok to sample and then rotate the subsequences R like that?
Would the time complexity be just O(|E| * n * m)?

Here is my python implementation:

def generate_sequence(e, n, m):
# Final sequence
s = []
# Extend s by n * len(elements) each iteration
for _ in range(n//m+1):
    r = list(e) * m
    random.shuffle(r)
    for _ in range(len(r)):
        # List of all windows of size m+1 where at least one element is from s or r.
        windows = filter(lambda x: len(x) == m + 1,
                         [s[-i:] + r[:(m + 1 - i)] for i in range(1, m + 1)])
        # check if any window contains an invalid sequence
        if not all(len(set(window)) > 1 for window in windows):
            # rotate r one to right
            r = [r[-1]] + r[:-1]
        else:
            # Valid s+r
            s.extend(r)
            break
return s[:len(list(e)) * n]


texts:
Given a directed graph $G$, edge weights for each edge, source vertex $s$ and $d[v]$ for each vertex in the graph (the distance from $s$ to $v$), I need to find an algorithm that builds the shortest paths graph.

I was thinking of going on edges by BFS, but then how can I know which edge should be in the tree and how to check that the $d[v]$ for each vertex is true?


texts: Using bloom filters for high speed pattern matching in combination with Aho Corasick

texts: I am implementing a new system for pattern matching in Intrusion Detection Systems for streaming data (network packets). I understand that bloom filters also produce false positives. Is there anyway for me to mark patterns that are false positives and then feed them to Aho Corasick as a verification system? I was hoping I could get comments on my approach or any suggestions on other data structures and algorithms I should be looking at?


texts: Proof that G is a Tree After DFS and BFS form the same tree T

texts:
Let G be a connected, undirected graph containing some vertex s. let's say  that  BFS  and  DFS  are  both  run  on  G starting  at  s and  that  the  breadth  first  search  and  depth
first search trees produced are the same.  Show that G is a tree.

Would this be good enough?

In order to show that G is a tree  Let us denote the tree produced by BFS and DFS be T.
Assume that G is not a tree, which means there must be an edge (u, v) ∈ G and such that (u, v) $\not\in $ T. ( G has more edges than T)

In such case, as the DFS tree forming, there will be a backedge.  That implies there is a cycle in G . That is because if v is discovered  first by DFS,  DFS must also find V later before finishing explore v.

On the other hand,  as the BFS tree forming, u and v can only differ by one level, which means there is not cycle.

With the fact that BFS and DFS tree are the same tree, it implies that one of u and v is an ancestor of the other and they can only differ by  one level. Therefore, all edges connecting T are the same as connecting G and G is a tree.


texts:
In a question I've been given a 5x5 matrix that I'm told represents a weighted graph, and no other information. Here is an example:

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

My question is, how does this represent a weighted graph? I think that each number at position [i,j] in the matrix represents the length between the nodes i and j in the graph, am I correct? Is this the most likely representation or are there other ways that I am not aware of?


texts: What is the difference between cyber security ontologies and scenario ontologies in this system?

texts:
I have been reading the paper Towards a Cognitive System for Decision Support in Cyber Operations. And I have been trying to understand the role of two ontologies proposed here, cyber security ontologies and scenario ontologies.

I have asked a question on CGS SE, What are the practical uses of ontologies? and the role of the ACT-R architecture in this system have become clear to some extent, but the question about the ontologies is that:

Does the cyber security ontologies make the ideas in the TENA's Repo understandable for ACT-R or the ideas that are in the repo has to be represented by an ontology called cyber security ontologies in order to be understandable for the ACT-R architecture?

The Cognitive System realized in the TENA framework:

Questions raising from this Figure can be:

What is the difference between the cyber security ontologies and the scenario ontologies?
What kind of knowledge the scenario ontologies represent?
And of course what is the reason that the scenario ontologies are connected to Event data management module instead of TENA's Repo?

ACT-R Architecture:

TENA Architecture:


texts: Massively parallel unconstrained minimization; f is a black box

texts:
My objective function, f, is complicated and embodies several disparate constraints I want my simulation to optimize simultaneously. So I can't really even assume it's continuous; it is probably close, in that small changes in the parameter space won't produce big shifts in f, but the gradient, etc. will be undefined all over the place.  Also I'm interested in solutions that won't require me to derive the gradient, hessian, etc. every time I make a change to the model.

In my corner, I've got a Tesla K20X.  I know that any reasonable N-dimensional grid around the region of likely minima will contain numerous cells that will be nowhere close to optimal.  That is, the error of most combinations of the N free parameters will be essentially infinite.

So far I've just been using a standard unconstrained search function (Matlab's fminsearch) on the CPU from numerous different starting points.  This takes too long, and I'm worried about local minima (which will always be a concern, but perhaps less so with a better approach).  Aside from just implementing that on the GPU (each thread doing its own fminsearch, which seems wasteful), I've thought of a kind of divide-and-conquer approach--evaluate the model at a relatively coarse N-dimensional grid of points in parameter space, throw out those cells with the most error, refine the grid, re-evaluate keeping the total number of evaluations about the same, and keep iterating until the error falls below threshold/won't shrink any more.  What else is there?  My searching has mainly come up with algorithms that expect you to do some math on the equations, but for the models I eventually plan to run (input-driven dynamical systems with dozens of state variables) this looks to be infeasible.


texts:
Logic gates are an abstract device which can be implemented with electromagnetic relays, vacuum tubes, or transistors.  These implemenations have been successful in computing in part because of various properties of chainability, durability, and size beyond their basic binary stability.  They also work well because electricity is the energy source which can rather easily be shipped around.

I've seen adders built out of wood, marbles, and gravity.  I've seen "lab on a chip" capilary-action-driven prototypes.  I've seen all kinds of specialty mechanical calculators (Curta, slide rule).  I've seen domino trails as single-use logic gates.

I'm interested in other illustrative computing devices that aren't necessarily convenient, durable, or fast, but which exploit properties of everyday materials to perform computation and which are directly visible.  The dominoes trails are close, but are a little too complicated to reset.

Magneto-mechanical arrangements?  Water in pipes/troughs?  More general marble contraptions?

PS.  Here's a new one.  Mechanical CPU Clock


texts: Prove or disprove that $NL$ is closed under polynomial many-one reductions

texts:
If $B \in NL$ and there exists a Karp reduction (polynomial-time many-one reduction) from $A$ to $B$, then $A \in NL$.
  Prove that the above claim is correct, incorrect, or equivalent to an open question.

Trying to solve this, I was pretty sure that the statement is either incorrect, or at least equivalent to an open question. My reasoning was that the statement is correct if the reduction is promised to be a log-space reduction (uses only $log \ n$ space). Removing this demand seems to be too much, but I wasn't able to prove this.

I was then told that this statement is equivalent to the open question $NL = P$. I thought of this, and tried proving that if the statement is correct, then one can define a Karp reduction from any $L \in P$ to a language in $NL$, therefore proving $L \in NL$ and $P \subseteq NL$. However I couldn't find such a reduction.
The only reduction I could think of that could help would be to transform the operations of a deterministic polynomial Turing machine $M_L$ to a configurations graph (a directed graph with an edge $(u,v)$ iff there exist two consecutive configurations $u, v$ in $M_L$. However, this reduction would take exponential $2^{p(n)}$ time, and not polynomial.

Any contribution would be appreciated.


texts:
In an example of the application of MapReduce provided by University of Utah, it says that Map() function emits <"hello", 1> every time it sees hello where the reduce function counts the number of instances "hello" occurs

My question is if this is the case, why isn't reduce doing <"hello", {1,1,1,1,1,1,1,1,1,1,1,1...}>, where each 1 is an instance Map() emits a key,value pair? In the example it wrote something like <"hello", (3,5,2,7)>, what does it mean?

Also, why do you need MapReduce to do this? I can just use an linked list on my computer.

Thanks


texts: When is conditional Kolmogorov complexity zero?

texts:
It seems intuitive that conditional Kolmogorov complexity is only zero when the bitstrings are the same, and otherwise is greater than 0.  I.e. if $b_1 = b_2$, then $K(b_1|b_2) = 0$, otherwise $K(b_1|b_2) > 0$.

However, if that is the case, then we could break a long bitstring into many smaller, different bitstrings, and then use conditional Kolmogorov complexity to establish a lower bound on the long bitstring's Kolmogorov complexity.

E.g., original bitstring is $\mathcal{B}$.  It is broken into different, smaller bitstrings $b_1,b_2,\ldots,b_n$.  We then use conditional Kolmogorov complexity to establish a lower bound on $K(\mathcal{B})$, in the following way,

\begin{align*}
K(\mathcal{B}) &= K(b_1,b_2,\ldots,b_n) \\
&= K(b_1) + K(b_2|b_1) + \ldots + K(b_n|b_1,b_2,\ldots,b_{n-1}) +
 O(log(K(b_1,b_2,\ldots,b_n)))\\
&\geq n.
\end{align*}

The equality is not strict, there are errors involved, which may invalidate the argument.

As the bitstring length grows, we can continue to grow the lower bound $n$ arbitrarily large, since there are a greater number of distinct smaller bitstrings that can be used to construct the large bitstring.  This appears to violate Chaitin's incompleteness theorem, which states with a fixed axiomatic system there is a limit $\mathcal{L}$ above which we cannot prove $K(\mathcal{B}) > \mathcal{L}$.

What am I missing here?


texts: Binary string satisfying several constraints

texts:
I'm trying to solve this problem, but without success.

Problem: You're given a binary string where some of the bits are replaced by ?. You're also given several intervals [$l_i$, $r_i$] ($l_i < r_i$). Find a binary string S with ? replaced by 0 or 1, such that in each interval [$l$, $r$], s[$l..r$] includes both 0 and 1.
Example:
Given the string 00?11 and the interval [2, 3], the string 00111 satisfies the requirements, as S[2..3]=01 include both 0 and 1.
However, the string 00?11 and the intervals [2, 3] and [3, 4] cannot be solved, as the ? would have to be both 0 and 1.
The bounds are |S|,Q<=1e5

I tried using greedy, but it's giving wrong answer for this case: 0??0, [1, 3], [2, 3] and [3, 4], as the greedy algorithm would try 0??0 -> 01?0 -> 0100 -> fail, yet there exists a solution (0010).
I tried removing completely overlapping intervals (such as [1, 3] and [2, 3]), but there're other cases I found that fails. What would be a correct solution?
Thanks.


texts:
Consider a system that indexes documents based on vector space model and a simple query, such as qwe asd. When searching we assign weights to both words qwe and asd based on how often they appear in the index. The idea being that if word exists in larger number of documents then it should have smaller impact on relevance. This works well because for each word we usually store statistics: number of occurrences of a given word in the whole index and number of occurrences of a given word in each document (possibly after normalization).

Now consider another query: "qwe asd" zxcrty. We have two parts here: a phrase and a simple word. For the word we have the above mentioned statistics, but for the phrase we do not. This poses a question: how to rank documents against phrase searches? If we find a one document that contains the phrase (qwe asd) and another that contains the single word (zxcrty) which one should be ranked higher?

I somehow doubt that there is one and ultimate solution to this question but would like to know about what approaches are used in existing search engines, whether other models solve the issue and other information that can be useful in analysing the problem.


texts:
Problem: Given an undirected, weighted, complete graph $G = (V, E, w, c)$. $w$ is the time weight function on edges, $w:E \to \mathbb{N}^{+}$; $w(e)$ represents the time it takes to travel along edge $e$. $c$ is the time deadline function on vertices, $c:V \to \mathbb{N}^{+}$.
Given a source vertex $s$, the question is whether there exists a tour $p: v_{0} = s \to^{e_{0}} v_{1} \to^{e^{1}} v_{2} \to \cdots \to v_{i} \to^{e_{i}} \to \cdots$ such that

$\{ v_{i} \}$ is a multi-set. That is, $p$ is not necessarily a simple path.
$\{ v_{i} \}$ contains all vertices, i.e., $V \subseteq \{ v_{i} \}$.
For each vertex $v \in V$, suppose that it first appears in $p$ as $v_{i}$, then we require that
$$\sum_{n=0}^{n=i-1} w(e_{n}) \le c(v).$$

Background: A courier needs to deliver goods to the places represented by $V$. Each  consignee has specified a deadline. The question is whether there is a tour satisfying all these deadlines.

I guess that this problem is NP-hard, and it reminds me of the scheduling problems with deadlines. However, I cannot find a suitable one for the reduction. Any ideas? (Other reductions for NP-hardness or algorithms are also appreciated.)


texts: Why this pattern matching fails in Agda?

texts:
Consider function wa'' (need natural number definition, either in stdlib or Agda.Builtin.Nat):

postulate comm : ∀ m n -> m + n ≡ n + m

wa'' : ∀ m n -> wa (m + n) ≡ wa (n + m)
wa'' m n with comm n m
...        | refl = { }0

The pattern matching on comm n m with refl fails. But if I add one more match:

wa'' : ∀ m n -> wa (m + n) ≡ wa (n + m)
wa'' m n with (n + m) | comm n m
...        | .(m + n) | refl = { }0

This code works. Is there any semantics-level difference between these two code snippets?


texts: is advice function and an oracle the same thing?

texts:
In the context of P/poly complexity class, an advice function is mentioned.
How is the advice function different than an oracle(/certificate)?
https://en.wikipedia.org/wiki/Advice_(complexity)
https://en.wikipedia.org/wiki/P/poly


texts: can't quit understand one step of the recurrence time complexity calculation

texts:
I solved the question T(n) = T(sqrt(n)) + 1 but can't quit understand one step of the solution
I don't understand the transition in (1).
how did we conclude that T(m) = T(m/2) + 1 from the previous step that m is in the power?


texts:
Let us define two languages of Turing machines.
$$
EQ_{TM} = \{<M_1,M_2> : L(M_1) = L(M_2)\}
$$
$$
ALL_{TM} = \{<M> : L(M) = \Sigma^*\}
$$
It is easy to show that neither of the languages are in $RE \cup coRE$, and also it is easy to construct a reduction $ALL_{TM} \leq EQ_{TM}$.

I suspect that there is no reduction in the other direction, but I don't know how to prove it. Is there some sort of hierarchy of undecidable/non-recognizable languages that proves it?


texts: What is the branching factor for nondeterministic games?

texts:
Given a nondeterministic game how could one know the branching factor of it? Is it the number of all possible outcomes?

I have an example game in which you have some cards. The goal is to get rid of all of them. At the start of the game you get 7 random cards. There is a draw pile from which you take cards if you can't (or don't want to) play a card. You can't see the cards in that pile and they are in random order. The amount of card types in the simple version is equal to 52. If I understand correctly that means that the branching factor is at least 52 for every move plus 52 times the number of cards of the player (player's don't know other's cards). Is my thinking correct? It seems to be too big (416 at the start of the game (52 + 52*7) from the perspective of another player and 59 (52 + 7) from the player's own perspective, when Go has "only" 250) but I'm not expert in this.


texts: Running Build-Heap Algorithm on given numbers

texts:
I don't fully understand this build-heap function. Lets assume we have array 3, 4, 5, 13, 16, 32.

It seems like we swap the parent when it is less than the current A[j] but which number does the loop start with? Maybe somebody can go through 2-3 loops and show how the array changes after 1st loop, 2nd loop, 3rd loop. Much appreciated. Oh, also, what would be the runtime?

for i=2 to n
    j = i
    while (j>1) and A[parent(j)]<A[j] do
        swap A(parent(j)] and A[j]
        j = parent(j)


texts: Maximize cost in graph with variable costs

texts:
Consider the following problem. A prisoner eats once a day, he can either have a low, or a high calorie dish. In order to be allowed to eat the high calorie dish, he must not have eaten the previous day. The prisoner knows the calories of each dish for the full week, and wishes to maximize his calorie intake for the week.

I modeled the problem into a bidirected cyclic graph:
l[n], h[n] are the two known arrays of costs and k the number of steps taken through the graph. (The cost to the H node at the kth step is h[k]). L represents eating the low nutrient dish, while H the high one. If you want to get to H you must pass from - first and amass no cost. The costs represent the nutrients gained when moving to each node. (They could be rewards on the nodes instead). S is the start node. The goal is to maximize the cost, given the number of maximum steps n.

I'm looking for a general direction. Does it belong to a known family of problems? If yes, how do you solve them efficiently? Dynamic programming, knapsack or some known modification of a graph traversal algorithm? Is considering it a graph problem wrong, or not particulartly helpful? Sorry for the barrage of questions.


texts: Why doesn't Dijkstra's use a shortest-path first search?

texts:
When using BFS search on an unweighted graph to find the single-source shortest paths, no relaxation step is required because a breadth-first search guarantees that when we first make it to a node, we have found the shortest path to it.

However, my understanding is that Dijkstra's algorithm has no such guarantee because the neighbours of each node are checked in no specific order. Therefore, we need a relaxation step to update the shortest path of each node if we later find a shorter path.

Instead of choosing a random neighbour, why not always follow the neighbour with the shortest path? I think that would guarantee we have always found the shortest path and no relaxation step is required. I implemented this in Python and it seems to work. Am I missing something?

from heapq import heappop, heappush

def shortest_path_lengths(graph, source):
    dist = {}
    q = [(0, source)]
    while q:
        source_to_v1_dist, v1 = heappop(q)
        if v1 in dist:
            continue
        dist[v1] = source_to_v1_dist
        for v2, v1_to_v2_dist in graph[v1].items():
            if v2 not in dist:  # check it hasn't been visited already
                heappush(q, (source_to_v1_dist + v1_to_v2_dist, v2))
    return dist

graph = {
    'a': {'b': 3, 'c': 5},
    'b': {'c': 1},
    'c': {'d': 4},
    'd': {},
}
print(shortest_path_lengths(graph, 'a'))


texts: How to label a video for supervised learning?

texts:
I have just started discovering the machine learning world! I found many tutorials showing how to deal with different types of data. I walked through some tensorFlow tutorials and I think they have very good way for showing how the (x, y) pair for supervised learning is "formed".

I was not able to find a way for representing the (x, y) pair for a video though. Are there any resources that can help me get started with labeling video sequences?


texts: Why Is KD-Tree-based Nearest Neighbor Exponential in K?

texts:
I've read in many papers on higher-dimensional nearest neighbor search that KD-Trees are exponential in K, but I can't seem to determine why.

What I'm looking for is a solid runtime-complexity analysis which explains this aspect of the problem.


texts:
A classic application of divide and conquer is to solve the following problem:

Given an array $a[1\dots n]$ of distinct, comparable elements, count the number of inversion pairs in the array: pairs $(i,j)$ such that $a[i] \gt a[j]$ and $i \lt j$.

One approach to this is to do a Merge Sort, but also counting of the number of inversion pairs in the sub-problems. During the merge step, we count the number of inversion pairs that span across the (two) sub-problems and add to the counts of the sub-problems.

While this is good, and gives an $O(n\log n)$ time algorithm, this messes up array.

If we have the additional constraint that the array is read-only, then we can make a copy and deal with the copy, or use an additional data-structure like an order statistics balanced binary tree to do the counting, both of which use $\Theta(n)$ space.

The current question is to try and better the space, while not affecting the run time. i.e.

  Is there an $O(n\log n)$ time algorithm to count the number of
  inversion pairs, which works on a read-only array and uses sub-linear
  (i.e. $o(n)$) space?

Assume a uniform cost RAM model and that the elements take $O(1)$ space and comparison between them is $O(1)$.

A reference will do, but an explanation will be better :-)

I tried searching the web, but could not find any positive/negative answer for this. I suppose this is just a curiosity.


texts: How to classify a 3D "Knapsack" problem where the only limitation is space, i.e. there is no weight constraint?

texts:
The problem is defined as: pack a 3D space with a given list of 3 types of cuboids which are each assigned a value, trying to either completely fill the space or to achieve the highest total value of the packing.
When researching knapsack problems all of the different variations I came across
had a weight constraint and most didn't consider geometrical 3D space as a constraint. So my question is: is my problem considered a knapsack problem and/or is there a different term for these kind of problems which I could look into further?


texts: Non-recursivity of language of TMs which have equivalent TMs of smaller and larger description length

texts:
Prove that the language

$$ L=\{\langle M \rangle \mid \exists M_1, M_2 : L(M_1)=L(M_2)=L(M) \text{ and } |\langle M_1 \rangle| < |\langle M \rangle| < |\langle M_2\rangle| \}$$

is not recursive.


texts: Understanding Martin Farach's suffix tree algorithm

texts:
I feel stuck at this point. I have spent several days trying to get my head around the algorithm, but both resources I have [1] [2] seems to skip over whatever details that would make me comfortable trying to explain/implement it. I'm going to hope that someone here knows Farachs suffix tree algorithm, but I'll link to the paper below.

I get the individual mechanisms of the algorithm, but I don't understand how to put it all together. By starting at the first step:

(1) Creating the odd tree requires sorting every character pair of the string, but the example used, namely g = 121112212221 yields the "sorted" list l = (1,2),(1,1),(1,2),(2,1),(2,2),(2,1), and then taking the ranks of l yields. g' = 2,1,2,3,4,3. I can't see how l is sorted, or why it would help to sort it.

(2) Farach mentions that the suffix tree for g' needs to be computed recursively. Is this the only step of the algorithm that needs recursion?

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.4336&rep=rep1&type=pdf

[2] https://www.amazon.com/Computing-Patterns-Strings-William-Smyth/dp/0201398397


texts:
I'm afraid this may be opinion-based and not apt here, but...
Mathematicians often talk about "mathematical beauty", i.e. Gauss' proof of the Fundamental Theorem of Algebra, Euler's Formula, etc.
What's beautiful in Computer Science?
Things like the Church-Turing thesis or Curry-Howard correspondence are cool, but I'm not sure they are the same kind of "beauty" as mathematicians commonly prescribe.
Is it because CS is often an engineering field (despite its theories), and doesn't share the same notion of "beauty"?


texts: Arithmetic problems known to be in TC^{i+1} but not known to be in TC^i

texts: Is there an arithmetic problem that is known to be in $TC^{i+1}$ but not known in $TC^i$ for any $i\geq0$? Concrete examples for $i=0$ would be of most utility however any arithmetic example is fine.


texts: An efficient algorithm to decide if a triangulation is 3-colourable

texts:
I don't know how to start with the following exercise:

  Design an efficient algorithm to decide whether a given triangulation with $n $ points is $3$-colourable.
  The triangulation is given by a sorted edge list, where every edge is given by the indices of its two end points. Further, for every edge there are given the indices of the points with which the edge forms a triangle in the triangulation (two indices for interior edges and one index for edges on the boundary of the convex hull). Give proof for the correctnesss of your algortihm.

Below is an example.

I've heard about the BFS and DFS algorithms in lecture, but I don't see how I could apply this here. I'd be thankful for any help.


texts: is it necessary to cover all the verticies in eular path?

texts:
I was going through graph theory and came across the term Euler path or some people prefer Euler trail as vertices can repeat.

According to the definition from wiki (https://en.wikipedia.org/wiki/Eulerian_path), Euler path is defined as under

  In graph theory, a Eulerian trail (or Eulerian path) is a trail in a graph which visits every edge exactly once.

Following are the conditions for Euler path,

  An undirected graph (G) has a Eulerian path if and only if every vertex has even degree except 2 vertices which will have odd degree, and all of its vertices with nonzero degree belong to a single connected component.

So as per the definition, I need to cover all edges in a connected graph with non zero degrees.

The same information is stated here at geeks for geeks(https://www.geeksforgeeks.org/eulerian-path-and-circuit/).

so if I need to only consider vertices with non zero degrees then graph (G)can be disconnected?

Note: These are the other information I collected from the wiki page

1)Finite connected graph (with vertices of even degree except 2 or 0 with the odd degree) will have a Euler path.
2)But Euler path can also be present in the disconnected graph as shown in the following picture

3) Doubt does following graph have Euler path,

My answer ,No as all vertices are not in same connected component.


texts:
I'm studying computer architecture and I'm doing an experiment.
Does LRU make sense in a direct mapping cache? I'm quite confused.
Thank you.


texts: Basic question about branches and pipelines

texts: In which stage ( on an ideal 5-stage pipeline ) are branches and hazards handled? How much is the branch penalty for a branch hazard or data hazard. Is there different stages to find data hazards or branch hazards ( meaning for example branch hazards occurs on the 2th stage in the pipeline) or are all hazards detected at a specific stage?


texts: Understanding state table for turing machine

texts: I'm having trouble understanding state tables for turing machines where the state table shown in the above image is supposed to show the change from the top turing machine to the bottom such that an extra 1 was added at index 5. I don't see how when S0 reads 1 (at start, index 1) and shifts the head right it then reads 0 and then writes 1, as when it shifts right shouldn't the head be at index 2 and read 1? And if the head was at index 2 then the finish at S2 would be at index 2 as well (since it shifts left and then right again)?


texts: Constructing a NFA that accept complement of language L of another NFA

texts: if given a language $L$ recognized by NFA $N_0$ over an alphabet $\Sigma$. Is it possible to find a general way of constructing an NFA $N_1$ that accept $L^C$ such that $L^C= \{w \in \Sigma^{*} |\mid w \notin L \}$?


texts: Find the minimum sum of distances between sets of points to a straight line in a plane

texts:
Given $n$ dots on a plane, such as: n couples ($x_i$,$y_i$)
I would like to find a line parallel to y-axis ( $x=b$ ), such that the sum of all of the point's distances from that line will be minimal
In order to do that, I need to write an alogrithem with a linear run-time ( $O(n)$ )

MY METHOD I relate only for the $x$ values of each point as an
element in an Array called $A$ So I used the Select(A,left, right, p) & Partition Alogorithm in order to find the median of
medians of the array

pseudo-code:
Select(A,left,right,p)
 n<-right-left+1
 if n=1 then
  return A[left]
 m<-⌈n/5⌉
 let B array with length m
 for i <-1 to m
  B[i]=medianOf5(A,left,right,x)
 x<-Select(B,1,m, ⌈m/2⌉)
 q <- partition(A,left,right,x)
 k <-q-left+1
 if p<k then
  return Select(A,left,q,p)
 if p>k
  return Select(A,q,right,p)

But, using median of medians seems unnecessary
If so, is there an easier way to that? if not ( or if yes for that matter ) was my way correct?


texts: Proving regularity via equivalence classes

texts:
Given two regular languages $L_1$ and $L_2$, we define a new language

$$L=\{w_1w_2\mid \text{ there exist two words } x,y \text{ such that } xw_1\in L_1, w_2y\in L2\}$$

How do I show that $L$ is regular with equivalence classes?

My assignment allows the use of closure properties that all regular languages hold, but I cannot use $\text{rank} (L)$, as in show a limit to the number of equivalence class.

Can someone lead me in the right direction?


texts: Algorithm to determine tournament winners given matrix

texts:
I am given an $n\times n$ matrix, $M$, that denotes the outcome of a series of races between $n$ contestants. Each contestant $i$ races against every other contestant $j$ and we say $M_{i,j}=1$ if $i$ beat $j$ (note $M_{i,j}=1\Leftrightarrow M_{j,i}=0$.) We then say that racer $i$ placed in the tournament if they lost at most $10$ races. I am supposed to define an algorithm that is linear in the number of queries made to matrix that returns all of the racers who placed (i.e. lost at most $10$ races.)

In order to reach this algorithm I have noted that the number of placers is bounded by $n=22$. We can thus define an algorithm that will reduce the problem to some case with under $22$ possible candidates and it is possible to brute force from there. I am, however, having trouble reducing the problem to only $22$ contestants. I have tried applying a dynamic programming approach by keeping track of how many races each contestant has won or lost and traversing the matrix diagonally (exploiting the fact that it is symmetric along the diagonal if you invert the values) and thus eventually eliminating $n-22$ of the contestants. I am having trouble showing whether this is indeed linear or, if it is not, how else I may further reduce the problem. Any help would be greatly appreciated, thanks!


texts: Algorithm for producing array of objects according to the given distribution

texts:
I have a set of objects, and each object has (let's say) a color. Given a distribution such as:

red : 50%
green : 30%
blue : 20%

I need to produce an N-length array of objects with a color distribution as close to this as possible. It is possible that the length of the original
list is smaller than N, so duplicates may be required.

Is there an efficient algorithm that might be suited for this kind of task? I imagine there is, but I'm lacking the terminology to find it.


texts: Minimum distance between start and end by going through must visit points in a maze

texts:
So, suppose i have a maze, which has a start point and an end point, marked with Orange and red respectively and my goal is to find the minimum distance between them. The blocked path is represented by black colour and the open path is represented by white colour . However there are two modification done in this.

There are some cells which are must visit, marked in grey colour.
Any cell can be visited any number of times(even the start, finish and must visit points)

for ex-
  █=Black, ░=white, G=grey, R=Red, O=orange

         ██████                 █████
         ██G███                 █░GG█
MAZE1 => █O░GR█     MAZE2  =>   █O███
         ██G███                 █░░R█
         ██████                 █████

Here in this case ans will be

MAZE1 => M[2][1] => [2][2] => [1][2] => [2][2] => [3][2] => [2][2] => [2][3] => [2][4]  = 7
MAZE2 => M[1][1] => [1][2] => [2][2] => [3][2] => [3][3] => [3][2] => [2][2]            = 6

As you can see, the nodes appear multiple times

First i thought of using recursion technique (backtracking) but couldn't come to an algorithm. and

So i thought of using this way.

I will keep track of all the coordinates of  must visit points, start and end points
Find the distance between each node(like in selection sort we compare each and every term, just like that, we get the minimum distance between each node (using BFS))
Then apply some minimum distance algorithm. I thought of TSP but it says nodes must be visited exactly once.Here it can be multiple times. I found chinese postman problem, but don't know if it can be applied here. Floyd warshall algorithm is there but it doesn't include every point

How should i proceed, any idea?


texts: Equivalence of states between two "quasi-deterministic" strongly connected Büchi automata accepting the same $\omega$-language

texts:
Hope someone can point me to the right direction to solve this problem.

Premise.
I call quasi-deterministic Büchi automaton (qDBA) a Büchi automaton $B = \langle S, \Sigma, S_0, \delta, F \rangle$, where $S$ is the set of states, $\Sigma$ the alphabet of transition labels, $S_0 \subseteq S$ the set of initial states, $\delta: S \times \Sigma \rightarrow S$ a partial transition function, and $F \subseteq S$ the set of accepting states. That is, a Büchi automaton where the only place of nondeterminism is in the initial state, while the transition function is deterministic.
An $\omega$-word is accepted by $B$ iff any of the infinite runs induced by the word on $B$ passes infinitely many times through some states of $F$.

Given a qDBA $B$ and a state $s \in S$, let $B/s = \langle S, \Sigma, s, \delta, F \rangle$ denote the deterministic Büchi automaton accepting all the $\omega$-words inducing runs of $B$ starting from $s$ (where $s$ may also be a non-initial state in B). Two states $s_1$ of the qDBA $B_1$ and $s_2$ of the qDBA $B_2$ are equivalent iff the language of the $\omega$-words accepted by $B_1/s_1$ is the same as the one accepted by $B_2/s_2$.

Finally, I say that $B$ is strongly connected if for any two states $s_1$ and $s_2$ there is a finite path connecting $s_1$ to $s_2$ and vice versa.

Question. Let $B_1 = \langle S_1, \Sigma, S_{0,1}, \delta_1, F_1 \rangle$ and $B_2 = \langle S_2, \Sigma, S_{0,2}, \delta_2, F_2 \rangle$ be two strongly connected qDBAs accepting the same $\omega$-language, $L(B_1) = L(B_2) = L$. I want to prove that for every state $s_1 \in S_1$ there exists at least one state $s_2 \in S_2$ equivalent to $s_1$.

Does this property hold in general? I tried to construct counterexamples to this property, but in every case I could think of, in order to falsify the conclusion, I always needed either to drop the assumption that $\delta_2$ was a deterministic transition function, or that $B_2$ was strongly connected.

I have a strong sense this property should hold. It might even be trivial, but maybe I am using the wrong vocabulary and I cannot find this result.

My intuition so far. Suppose there are two $\omega$-words $w'$ and $w''$ accepted by $B_1/s_1$. Since $B_1$ is strongly connected, one can construct accepted words by starting with the first symbols of $w'$, then taking a path back to $s_1$, then continuing with some symbols from $w''$, then back to $s_1$, and again following $w'$ in any combination. Since $B_2$ also accepts all of these combinations but has a finite number of states, the runs corresponding to these words must eventually reach some state $s_2$ from which both $w'$ and $w''$ are possible continuations of the runs. This must hold for every set of words accepted by $B_1/s_1$. But I am not able to turn this (possibly wrong) reasoning in general, formal terms. Could you please help me do so, if possible?


texts: Expectation Maximization Algorithm for simple naive Bayesian network

texts:
I am trying to understand the following network
A has two children - B & C (aka common cause)

All the variables are binary and can be either 0 or 1.
In data values are missing only for some records. Only values that are missing are values A.

How does the Expectation step looks like in this example? Is it P(A|B,C) and then calculating the counts for P(A = 0| B = 0, C=0) ? I am confused with this.

How does the Maximization step looks like in this example?


texts: Bits needed to send parameters of perfect hash functions

texts:
Suppose that there is a server that has $n$ files. The server is used to construct a perfect hash function for those files and then the computed parameters will be sent to a user. These parameters will be used by the user to compute the hash of a certain file in order to find its position between files on the main server. The question is that how many bits are needed to be transmitted between the server and the user? Is that in order of $O(n)$?
Can anybody suggest a specific algorithm with its parameters and communication cost?


texts: How does the induction proof work in this example?

texts:
Refer to answer 1.1 of this file: http://www.dei.unipd.it/~geppo/AA/DOCS/NPC.pdf

From my understanding and this thread, https://math.stackexchange.com/a/928412, we need 3 steps for that proof.
The first case is trivial and true. Now we have assumed the same for i and going to prove that it is true for i+1. I'm unable to clearly see how they have made that deduction in this answer.


texts:
Suppose we have the function below:

def func(n):
    for i in range(n):
        for j in range(n - i):
            for k in range(n - j):
                if i + j + k == 0:
                    break
            if i + j == 0:
                break
        if i == 0:
            break
    return n + 1

We have three nested for-loops and the total number of elements evaluated appears to be: (n)(n-1)(n-2). However, this cannot be correct, as I know the time complexity of this function is not O(n^3). What is the proper way to evaluate the time complexity of this function?


texts: Confused with an Instruction Cycle question

texts:
Here's the question

The content of PC in the basic computer architecture (given below) is 3AF. The content of AC is 7EC3. The content of memory at address 3AF is A32E. The content of memory at address 32E is 09AC. The content of memory at 9AC is 8B9F. The next two contents of PC are 3B0 and 3B1. The content of memory at address 3B0 is 1340 and the content of memory at 3340 is 10B0. The content of memory at address 3B1 is 3345. Identify each register values mentioned in the question and update according to the sequence of PC value.

I am able to run up till the part where it says

the content of memory at 1340 is 10B0

After first instruction executes, that is 3AF, a memory reference instruction is executed which in the end puts 8B9Fh in DR and AC. Here's the execution:
Clock   Operations                                   Result
T0      AR <- PC                                     AR = 3AFh
T1      IR <- M[AR], PC <- PC + 1                    IR = A32Eh, PC = 3B0h
T2      D <- IR(12-14), AR <- IR(0-11), I <- IR(15)  D = 010b, I = 1b, AR = 32Eh
T3      AR <- M[AR]                                  AR = 9ACh
D2T4    DR <- M[AR]                                  DR = 8B9Fh
D2T5    AC <- DR, SC <- 0                            AC = 8B9Fh

Now at the second instruction, the  confusion begins. I think the Question may be wrong. Here's the execution:
Clock   Operations                                   Result
T0      AR <- PC                                     AR = 3B0h
T1      IR <- M[AR], PC <- PC + 1                    IR = 1340h, PC = 3B1h
T2      D <- IR(12-14), AR <- IR(0-11), I <- IR(15)  D = 001b, I = 0b, AR = 340h
T3      Nothing
D1T4    DR <- M[AR]                                  DR = M[340]??? Here's the problem

The question says "the content of memory at 1340 is 10B0". However, we can't possibly store 1340 in a 12 bit AR. I will provide further details if the question is unclear, please comment below.


texts: In complexity theory, does polynomial time refer to the big-O notation?

texts:
When we are discussing the run time of an algorithm, are we referring to big-O notation or are we saying that the runtime is the same for all cases?

For example; algorithm X runs in polynomial time.


texts: Compact, reversible mapping from set partitions of length k to integers

texts:
Given a set $S$ of length $n$, I'm looking to map all the $k$-length partitions of $S$ onto the set of integers such that these integers are as close to 0 as possible. Ideally the range would be $\left[0, {n \brace k}\right)$.

Ideally this mapping and its inverse would be easy to compute.


texts: Recursive complexity with change of variable

texts:
I face a problem with computing a complexity.
I have this equality : $P(u) = (\sqrt{u}+1)P(\sqrt{u}) + \theta(\sqrt{u})$

And I want to prove that $P(u) = O(u)$

This is how I process :

I put $m = \lg\lg u \implies P(u) = P(2^{2^{m}}) = (2^{2^{m-1}}+1)P(2^{2^{m-1}}) + \theta(2^{2^{m-1}})$

Now, I consider $S(m)$ that is : $S(m) = P(2^{2^{m}}) = mS(m-1) + \theta(m-1)$

And here I have a problem. I obtain a factorial complexity and I don't know how to integrate $\lg$ to prove the equality $P(u) = O(u)$

Some advice ?


texts: Check-digit algorithm that includes characters?

texts:
I have a data set that uses a very simple modulo 10 checksum algorithm which ignores alphabetic characters entirely.  Which wasn't a big deal, as the few  alphabetic characters present weren't critical.

Changes to the data format are upcoming, including characters which will now be critical to the interpretation of the data.  So I'd like to propose a new checksum algorithm that can detect errors in those characters.  And something more powerful then modulo 10 wouldn't hurt either.

I've been looking at the Luhn, Verhoeff and Damm and a few other check digit algorithms, but they all only handle digits, not characters.  Is there anything out there that does both digits and characters [A-Z.+-] ?  I'd rather implement something existing and proven rather then roll my own.  I think the check 'digit' could reasonable be any character from the alphabet in use [A-B.+-], not just [0-9]

Thanks!


texts: Does an algorithm exist that transforms any connected graph, cyclic or not, into tree form?

texts:
I developed an algorithm that transforms any simple connected graph, cyclic or not, into a tree.
The resulting tree is syntax-preserving, in a sense that it allows to reconstruct the original input graph and only the original input graph. In other words, the constructed tree preserves adjacency information, while resolving cycles.
Moreover, I assume that with the constructed tree allowing to reconstruct only the original input graph, no other graph that is structurally different can exist that would result in an identical tree form.

I did some research on algorithms that transform graphs into tree form, but I was unable to find another algorithm that would work for any simple connected graph like described above.
However, I am pretty such there must exist something.

So maybe one more experienced in graph theory can help me out.
It would be highly appreciated.

Alex


texts: How can I reduce a product of transpositions?

texts:
I'm looking for an algorithm to solve the following task:

Input: a set $T$ of transpositions; a permutation $\pi$ expressed as a product of transpositions from $T$
Desired output: express $\pi$ as the shortest possible product of transpositions from $T$.

In other words, the output should be a list of transpositions $\tau_1,\dots,\tau_k$ such that $\pi = \tau_1 \circ \dots \circ \tau_k$, $\tau_1,\dots,\tau_k \in T$, and $k$ is as small as possible.

Is there an algorithm for this that will be efficient in practice?

For example, if I were given (2,3)(0,3)(0,3)(2,6)(2,3)(2,6)(0,3) = (0623), I could reduce it to (2,6)(2,3)(0,3) = (0623).

I have come up with a few methods, based on the following properties:

The product of identical transpositions cancel. For example, (1,2)(1,2)(2,3) = (2,3).
Any product of the form (x,y)(y,z)(x,y) is equal to (y,z)(x,y)(y,z).
Any transpositions which share no elements commute. That is, (u,v)(x,y)=(x,y)(u,v).

I have three methods, based on these three properties:

One simple method is simply finding instances of (1). In the first example, (0,3)(0,3) appears as a product, so I may remove those transpositions.
Another method is finding instances of (x,y)(y,z)(x,y)(y,z), since this is equal to (y,z)(x,y)(y,z)(y,z) = (y,z)(x,y).
A third method is to recognize if identical transpositions are separated by disjoint transpositions. For example, (0,3)(2,6)(0,3) = (0,3)(0,3)(2,6) = (2,6).

Are there any other methods I am missing here?

I will explain some of the context in which this problem appears. Consider a graph G with labelled vertices. On each vertex lies a pebble, $p_i$. A transposition in the given product corresponds to selecting an edge in G and swapping the pebbles that are incident to that edge.

Therefore, a product of transpositions corresponds to a process of exchanging pebbles of edges, and the end result is a permutation of the pebbles on G which is described by the permutation given by the product of transpositions.

Hence, this process of boiling down a product of transpositions is an attempt to reduce the number of exchanges needed to achieve any permutation of pebbles on a graph G.


texts: Communication complexity of string matching

texts:
let us consider Alice and Bob communicate over channel bit by bit. They have one string over $\{0,1\}^{*}$. Let $x$ (uniformly at random) be the string that Bob have and $y$ be the string that Alice have.  They want to check whether there strings are same or not.

On simple algorithm is exchange $n$ bits one by one. We want to solve this problem with few bits exchanged between Alice and Bob.

My Idea : We will randomly select $k = O(\log {n})$ many bits and exchange only these bits. In this probability of error is going to be less than $1/2^{k}$ (because probability of making error for one bit is 1/2) and as each time we are randomly selecting the bits overall probability of error will be less than $\frac{1}{2^{k}}$.

Question : Is my solution optimal one to solve the problem described above?