## Replacing $x,y$ in $f(x,y,z)$ with values from a list

I’m sure there is a simple solution to this using map or apply, but its not occurring to me.

Suppose I have a function $$f(x,y,z)= x+y+z)$$

And I want to evaluate $$f(x,y,1)$$ for $$\{x,y\} ∈ \{\{1,2\},\{3,4\}\}$$

What is the best way to do this?

Examples:

If I use f[x_,y_,z_]:= x+y+z; f[#1,#2,1]&/@ {{1,2},{3,4}}

this will give me things like {{2+#2,3+#2}}.

On the other hand, Apply works on a single element f[#1,#2,1]& @@ {1,2} but not on a list such as {{1,2},{3,4}}. On the list it gives me {f[1,3,1],f[2,4,1]

I am not sure how to go from the case of a single pair to a list of pairs

## Given a plot of a network Graph[] how can the {x,y} screen coordinates be output?

Is there a general way to get the screen or "world" coordinates for every vertex in the graphic output of something like this?

Table[Graph[Table[i \[UndirectedEdge] i + 1, {i, 20}],    GraphLayout -> l,    PlotLabel -> l],  {l, {"CircularEmbedding", "SpiralEmbedding"}}] 

Trying to build an algorithm to generate novel layouts and want to use a large amount of other algorithms for training data.

Posted on Categories cheapest proxies

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

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

## Given a list of strings, find every pair $(x,y)$ where $x$ is a substring of $y$. Possible to do better than $O(n^2)$?

Consider the following algorithmic problem: Given a list of strings $$L = [s_1, s_2, \dots, s_n]$$, we want to know all pairs $$(x,y)$$ where $$x$$ is a substring of $$y$$. A trivial algorithm would be this:

foreach x in L:    foreach y in L:       if x is substring of y:          OUTPUT x,y 

However, this takes $$O(n^2)$$ $$x$$ substring of $$y$$ operations – I am curious to know whether there is a faster algorithm?

Posted on Categories proxies

## Quick calculation for $x^y \bmod 2^d$

I need to calculate $$x^y \bmod 2^d$$ in $$O(d)$$ summations/bitwise operations and $$1$$ multiplication by $$y$$. $$x$$ is restricted to be odd, $$d\geq 3$$.

$$a$$-bit arithmetic (for any $$a$$) is allowed, as this is just a theoretical question.

## Does |xy| ≤ p in the pumping lemma count for all i?

While learning about the pumping lemma, I came across the following question:

Given the language L is $$a^n(0|1)^*$$ with $$c_0 \cdot c_1 = n$$, where $$c_0$$ indicates the amount of zeros present, use the pumping lemma to prove that this language is not regular. Examples of valid words in L are 0, 1, a01, aa001, etc…

In regular english: a word with leading as, followed by any amount of either 0 or 1 characters, where the amount of zeros multiplied by the amount of ones needs to match the amount of as.

My initial attempt was the following:

• Pick w as $$a^p0^p1$$. This obviously holds since $$p \cdot 1 = p$$.
• Split w into xyz as $$x = \epsilon$$, $$y = a^p$$, $$z = 0^p1$$.
• Show that $$xy^2z = a^{2p}0^p1$$ does not hold, since $$p \cdot 1 \ne 2p$$.

However, the answer key instead opts to introduce two new variables $$m \geq 0$$, $$n \gt 0$$, then splits on $$x = a^m$$, $$y = a^n$$, $$z = a^{p-n-m}0^p1$$ (splitting the sequence of a into three parts). Then, they too use $$i = 2$$ to show that $$xy^2z = a^{m}a^{2n}a^{p-n-m}0^p1 = a^{p+n}0^p1$$, which is not a member of the language (since n was more than 0).

As far as I can see, my attempt adheres to the $$|xy| \leq p$$ condition of the pumping lemma: x is empty and $$|y| = p$$. As such, I was under the impression that my answer was correct.

However, the huge increase in complexity of the answer in the answer key leads me to believe that this is not a valid approach. I have the sneaking suspicion this is because my answer actually does violate the $$|xy| \leq p$$ condition.

Is my attempt a correct way to prove that the language is not regular? If not, what misconception/mistake did I make along the way?

## Find PDA for CFL = {x#y | |x| = |y| and x $\neq$ y}

I am studying push down automata. When I read a solution for show that CFL L = {x#y | $$x \neq y$$, $$x,y \in \{0,1\}^*$$}, I could understand L = $$L_1 \cup L_2$$, $$L_1 = \{x\#y\enspace|\enspace|x| \neq |y|\enspace\}$$, $$L_2 = \{x\#y \enspace|\enspace|x| = |y|$$, $$x \neq y\enspace\}$$, and make CFG for $$L_1$$, but I don’t know how to make CFG for $$L_2$$, Since y is not a reverse string of x. How can I know $$i_{th}$$ symbol is different?

Posted on Categories proxiesTags , ,

## Find numbers $x$, $y$ such than $(x,y) = 18$ and $[x,y]= 3780$

Where $$(,)$$ is the greater common divisor and $$[,]$$ the smallest common multiple.

In general how do you solve this kind of problems?

## If $X$ is a vector space endowed with a metric that is NOT norm induced and If $x_n\to x$ and $y_n\to y$, then $x_n+y_n\to x+y$

Let $$X$$ be a real or complex vector space endowed with a metric $$d$$ which is not induced by a norm, that is there exist no norm $$\| \cdot \|$$ on $$X$$ such that $$d(x,y)=\| x-y \|$$. Prove or disprove:

(a) If $$x_n\to x$$ and $$\lambda_n\to \lambda$$ ($$\lambda_n,\lambda$$ are scalars), then $$\lambda_n x_n \to \lambda x$$.

(b) If $$x_n\to x$$ and $$y_n\to y$$, then $$x_n+y_n\to x+y$$.

This is throwing me off just because the vector space is endowed with a metric that is not norm induced, and I am not sure what all that implies. With that said, I think I may be doing this problem naively. Anyway, here are my solutions:

(a) Let $$y\in X$$ be fixed. Then, by the triangle inequality, $$d(\lambda_nx_n,y) \leq d(\lambda_nx_n,\lambda x) + d(\lambda x, y),$$ similarly, $$d(\lambda x,y)\leq d(\lambda x,\lambda_n x_n) + d(\lambda_n x_n , y),$$ which implies that $$d(\lambda x,y) – d(\lambda_n x_n , y) \leq d(\lambda x,\lambda_n x_n),$$ so that as $$n\to\infty$$ we have $$\lambda_n x_n \to \lambda x$$.

(b) We may establish an upper bound via the triangle inequality, so that $$d(x_{n},y_{n}) \leq d(x_{n},x) + d(x,y) + d(y,y_{n}).$$ Again for a lower bound, we use the triangle inequality: $$d(x,y) \leq d(x_{n},x) + d(x_{n},y_{n}) + d(y_{n},y);$$ hence we have that, $$d(x,y) – d(x_{n},x) – d(y_{n},y) \leq d(x_{n},y_{n}).$$ Now as $$n \to \infty$$ we have $$d(x_{n},y_{n}) \to d(x,y).$$

Posted on Categories proxies

## How many pairs $(x,y)$ such that $x+2=y$ have an $x$ or $y$ divisible by 5 and not 3?

Let the set $$S_{n}$$ = {$$(x,y):x,y \in \mathbb{O}$$} such that $$x+2=y$$ and $$y$$ is less than or equal to odd integer $$n$$ and $$\mathbb{O}$$ is set of odd integers > 1.

Let us define the function $$f(n) = |S_{n}|$$ that counts the number of pairs in $$S_{n}$$.

Examples: $$S_{9} =\{(3,5),(5,7),(7,9)\}$$ and $$f(9) = 3$$.

$$S_{13} = \{(3,5), (5,7), (7,9), (9,11),(11,13)\}$$ and $$f(13) = 5$$

$$S_{35} = \{(3,5), (5,7), (7,9), (9,11), (11,13), (13,15), (15,17), (17,19), (19,21), (21,23), (23,25), (25,27), (27,29), (29,31),(31,33),(33,35)\}$$

and $$f(35) = 16$$

It turns out that $$f(n) = ((n-3)/2)$$ for odd integers $$n$$.

Let us define another function $$g(n)$$ that counts the number of pairs $$(x,y)$$ such that either $$x$$ or $$y$$ is divisible by 5 and not divisible by 3, and $$x \neq 5$$ and $$y\neq 5$$.

Example: $$g(35) = 3$$ because there are 3 pairs where $$x$$ or $$y$$ is divisible by 5 and not 3, and $$x$$ or $$y$$ is not equal to 5. They are (23,25), (25,27) and (33,35).

Note, the pairs (3,5) and (5,7) are not included since they contain 5, and the pairs (13,15) and (15,17) are not included because 15 is also divisible by 3.

What is the formula for $$g(n)$$ in terms of $$f(n)$$ ?

What is the formula for $$g(n)$$ in terms of $$f(n)$$ for limit $$n \to\infty$$?