is AVL tree is better than heap for sorting purpose? for sorting n elements what is better to use AVL tree or heap data structure and why? Can someone explain in brief?

Both of them will work, and both of them support insertions${}^1$ and deletion${}^2$ of the minimum element in $O(\log n)$ worst-case time (where $n$ is the number of elements currently in the data structure).
It really depends what you mean by "better". An AVL tree will have the additional binary-search-tree property that the heaps do not have, and this allows to quickly support other operations (in addition to returning the ones above). For example you can quickly search for any element in the tree (both for its value and its rank).
Indeed, the typical use of AVL trees is to implement a dictionary.
Since there isn't really any reason to use an AVL tree for sorting (they are a bit more complex to implement than an heap), you could stick with an heap. See also: heapsort.

${}^1$ Notice that constructing an AVL tree of $n$ elements by repeated insertions takes $O(n \log n)$ time. You can also construct an heap by repeated insertions in $O(n \log n)$ time but, since the arrangement of the elements in an heap is more relaxed than a BST, this can actually be improved to $O(n)$. For the purpose of sorting this doesn't really matter since its complexity will be subsumed by the one of the subsequent $n$ deletions.
${}^2$ Deletions are not really necessary if an AVL tree is used. Since an AVL tree is a BST, it suffices to return the elements in the same order as they are considered by a symmetric traversal of the tree.


Find two numbers in sorted array whose product is close to N Given a sorted array of numbers, is there a good algorithm for finding two numbers in that array whose product is as close as possible to a given number N?

I know that there is a good O(n) (?) algorithm for the related problem of finding two numbers that sum to a given number N. You begin with ptr1 at the start of the array and ptr2 at the end, and if *ptr1 + *ptr2 > N you decrement ptr2, else increment ptr1.

But for multiplication, it feels possible this method could "miss" the optimal solution by overshooting it somehow? Is there a good way to solve the multiplication variant in something that isn't just O(n^2)?

This answer is compilation of above comments but this include reasoning why this algorithm works.

1. find(A, val)
2.    start = 1
3.    end = A.length
4.    minn = (start,end)                //minn is pair used to store answer
5.    minnErr =   |A[start]*A[end]-val|        //minnErr is difference between best
                                  //pair of values seen so far and targate value.
6.    while(start < end)
7.        if (|A[start]*A[end]-val| < minnErr) //if this pair of values is
                                                      //even better than remember it.
8.            minnErr = |A[start]*A[end]-val|
9.            minn = (start, end)

10.       if A[start]*A[end] > val:              // here
11.           end = end - 1
12.       elif A[start]*A[end] < val:
13.           start = start + 1
14.       else:
15.              break
16. return minn

Algorithm works as follows:

here answer is pair of indices of element of array which has product closest to target
value.

We keep two pointers $start$ and $end$. Which are initialized to $1$ and $array\space size$ respectively.
Now in every iteration we compare $A[start] * A[end]$ with $minnErr$.
If current pair have better solution than we record it.
If $A[start]*A[end] < val$ than we increase $start$ by $1$.
Now note that all $(i,j): i< start, j\le end$ can never be solution because for any
such $(i,j)$ we have $A[i]*A[j] \le A[start]*A[end] < val$.
if $A[start]*A[end] > val$ than we decrease $end$ by $1$.
Now here(considering decremented value of $end$) all $(i,j): i\ge start, j>end$ can never be solution because for any such
$(i,j)$ we have $A[i]*A[j] \ge A[start]*A[end] > val$.
if $A[start]*A[end] = val$ than we stop here as this is best solution.

credits:  @G. Bach, @greybeard


Algorithms for generating brick walls I'm not sure which StackExchange community is the correct place to ask this so I'm trying this one.

I want to write a code that generates random brick wall type textures. Similarly to what, for example, this commercial software does: http://www.vizpark.com/shop/walls-and-tiles/ .

So far I've thought at least three types of brick wall textures I would like to generate:
1) Periodic and user-defined pattern with one or more predefined brick types (bricks can be different shape an size). This is the simplest case.
2) Completely random pattern with predefined brick types
3) Completely random pattern with random sized bricks.

This is pretty much a mathematical problem that could be rephrased as: what is the way to fill a predefined area with certain shapes (either random or predefined) without leaving gaps?

I would assume that people have thought about this type or problems before, but I don't know how to search for it. I'm not looking for a conclusive answer, but would appreciate links to articles, etc. discussing different variations of this or related problems.

I would like to comment this, but reputation...

What you are looking for is a Tessellation.

  A tessellation of a flat surface is the tiling of a plane using one or more geometric shapes, called tiles, with no overlaps and no gaps.

For example, the Penrose Tiling, the Pithagorean Tiling, Domino Tiling or Polyomino Tiling.


"Unrolling" a recurrence relation int function(int n)
{
   int i;

   if (n <= 0) {
       return 0;
   } else {
       i = random(n - 1);
       return function(i) + function(n - 1 - i);
   }
}

Consider the recursive algorithm above, where the random(int n) spends one unit of time to return a random integer which is evenly distributed within the range [0,n]. If the average processing time is T(n), what is the value of T(6)T(6)?

(Assume that all instructions other than the random cost a negligible amount of time.)

This question was on Brilliant and I was following along their solution

              T(n)=T(i)+T(n−1−i)+1
              T(n)=T(0)+T(n−1)+1
              T(n)=T(1)+T(n−2)+1
                    ....
              T(n)=T(n−2)+T(1)+1
              T(n)=T(n−1)+T(0)+1

       nT(n)=2(T(0)+T(1)+....+T(n−2)+T(n−1))+n..........(1)
       (n−1)T(n−1)=2(T(0)+T(1)+...+T(n−2))+n−1).........(2)

Subtract 1 from 2

            nT(n)−(n−1)T(n−1)=2T(n−1)+1

$\frac{T(n)}{n+1}$ = $\frac{T(n-1)}{n}$ + $\frac{1}{n(n+1)}$.   They mention this is a telescoping sequence.

They say T(0) = 0 and then get

$\frac{T(n)}{n+1}$ = $\frac{1}{(1)(2)}$ + $\frac{1}{(2)(3)}$ + ... + $\frac{1}{n(n+1)}$ = $\frac{n}{n+1}$.  I do not understand how they got to this equation from the previous.

Let $S(n) = T(n)/(n+1)$. Notice that $S(0) = 0$ and $S(n) = S(n-1) + 1/n(n-1)$. Thus
$$
S(n) = \frac{1}{n(n+1)} + S(n-1) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + S(n-2) = \cdots
$$
Continuing in this way, for any $i \geq 0$ we get
$$
S(n) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + \cdots + \frac{1}{(i+1)(i+2)} + S(i).
$$
In particular, for $i = 0$ we get
$$
S(n) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + \cdots + \frac{1}{(1)(2)}.
$$

Alternatively, you can prove by induction that $S(n) = n/(n+1)$. This clearly holds for $n = 0$. Assuming it holds for $n-1$, we prove it for $n$:
$$
S(n) = \frac{1}{n(n+1)} + S(n-1) = \frac{1}{n(n+1)} + \frac{n-1}{n} = \frac{1+(n-1)(n+1)}{n(n+1)} = \frac{n^2}{n(n+1)} = \frac{n}{n+1}.
$$

Alternatively, we can prove directly that $T(n) = n$ by induction. This clearly holds for $n = 0$. Assuming it holds for $n-1$, we prove it for $n$:
$$
T(n) = \frac{n+1}{n} T(n-1) + \frac{n+1}{n(n+1)} = \frac{n+1}{n} \cdot (n-1) + \frac{1}{n} = \frac{(n+1)(n-1)+1}{n} = \frac{n^2}{n} = n.
$$


Smallest possible integer not obtained from sumset Given a number N, and some set $A=\{a, 1\le a\le N\}$, and let $B=\{\text{every integer} \in [1,N]\}$, and $C=B\setminus A$ (Set C has all values from B not in A)

What is the best way of finding the smallest number ($S$) that can't be obtained from the sum of any subset of C?

i.e.
if $A=\emptyset$, the smallest number $S= 1+\sum_1^Nx$,
but if $A\ne \emptyset,\ S\leq 1+ \sum_1^Nx-\sum_{i=0}^na_i$,
However if $N=10,A=\{2\}$, then $S=2$, and that is something that I'm not sure how to get efficiently.

I can obviously bruteforce the solution, but I can't find a better way, and I don't know how these kinds of problems are called so that I could Google them.

One possible way is computing the product
$$ \prod_{a \in C} (1+x^a). $$
This is a polynomial $p(x)$.  The coefficient of $x^j$ will be non-zero if and only if $j$ can be represented as the sum of some subset of $C$.  Therefore, given $p(x)$, you can read off the set of all numbers that are obtainable as the sum of some subset, and then find the smallest that isn't obtainable (i.e., the smallest integer $j$ such that $x^j$ has coefficient $0$ in $p(x)$).

As a bonus, you'll also get the number of possible representations of each number which is representable.

The running time is polynomial in $N$, and doubtless you can optimize the degree of the polynomial. (This is dynamic programming in disguise.)

If you're after an algorithm polynomial in the input length (the input can be either $A$ or $C$), that's a different question.  The problem is that the input can be very small; though perhaps such inputs can be handled separately.


Tips for understanding the Pumping Lemma for Context-Free Languages I'm having a hard time wrapping the idea in my head. Can anyone explain this as different from Sipser's perspective?

(I saw one discussion in reddit but it's for regular languages)
https://www.reddit.com/r/compsci/comments/1pnjrp/the_pumping_lemma/

One way of looking at the pumping lemma is in terms of the pumping game, a two-player game parametrized by an infinite language $L$. The two players are the Prover and Challenger, and the game goes as follows:

Prover picks an integer $n$.
Challenger picks a word $w \in L$ of length at least $n$.
Prover chooses a decomposition $w = xyz$ such that $|xy| \leq n$ and $|y| \ge 1$.
Challenger chooses an integer $i$.
If $xy^iz \in L$ then Prover wins, otherwise Challenger wins.

The pumping lemma states that:

  If $L$ is regular then Prover has a winning strategy.

The pumping lemma is often used in the contrapositive:

  If Challenger has a winning strategy then $L$ is not regular.

Here is an example: we will show that Challenger has a winning strategy for the language $L = \{a^nb^n : n \geq 0\}$.

In response to Prover's choice of $n$, Challenger chooses the word $w = a^n b^n$. In response to Prover's choice of a decomposition $w = xyz$ such that $|xy| \leq n$ and $|y| \geq 1$, Challenger chooses $i=0$. Then $xy^iz = a^{n-|y|}b^n \notin L$, and so Challenger wins.


Using DCEL to represent "simple geometric objects" Many algorithms in computational geometry assume to have as input a complex data structure to represent a geometric object. The most common I know is the Doubly connected edge list, but there're also the halfdge data structure, winged edge etc... I was wondering if such data structure is also used to represent simple object. I know for example there's no need to represent a vertex or a line segment using a DCEL, however in practical implementations this would probably make the interface reusable, and therefore the whole algorithm implemented (unless we want to use some wrapper but I'm assuming I'm not).

So my question is, how can both points and segments be represented using a DCEL?

I would initialize the half_edge_incident field to be NIL and I would keep the  list_< HalfEdge* >  empty, same as the list< Face* >?

For the segment case I would just have two vertices entries not empty, two half edges entries not empty, the faces list would be empty.

Does this representation work?

First of all, while being generic is nice from an user perspective, it is usually the best idea to use the simplest structure that you require from an algorithmic perspective. The proper solution to this problem is simply to offer the user a single interface (or 'wrapper', as you call it).

(Another problem is that unnecessary abstraction is potentially unbounded. Why use a plane when $\mathbb{R}^n$ is more general? Why use that when an abstract metric space is more general, etc.)

Now, for your specific construction:

  For the segment case I would just have two vertices entries not empty, two half edges entries not empty, the faces list would be empty.

The problem with this construction is that a lot of fields are empty that I would expect to be filled. Why do some edges have no face, why do some edges have no successor? Both these cases do not occur in a DCEL, so to make this particular structure work you must already define a generalisation of a DCEL that allows for empty fields. Most importantly, you are trying to store something that is not a subdivision of the plane in a DCEL, which is designed to store precisely that!

If you really want to store 'simple geometric objects' in the plane, using a trapezoidal decomposition seems like a decent idea, as it can reasonably store both segments and polygons. (It is even possible to store both a trapezoidal decomposition and a DCEL for the same data) However, this all depends on the actual application, since some operations are more efficient with a DCEL or other structures.

If you insist on storing segments in a DCEL, an approach is to represent a segment by a pair of edges (so 4 half-edges), where one of the 'faces' is the space surrounding the segment and the other the face 'inside' the segment (with 0 area).


Why do we pop the dollar symbol when it's already present in the stack in PDA? Could anyone tell the reason for popping the top of stack(dollar symbol) as said in this lecture(p.54) when there's already dollar symbol in the stack.

I would like to know if we could replace the transition given here(p.54) of the form

A,$ $\to$ 0$

with

A,$\epsilon \to$ 0.

The "end-of-stack" symbol (often $\$$) is necessary for the automaton to know when there are no more stack symbols. Therefore, when we reach $\$$ we have two options:

Remove the $\$$ and terminate¹.
Put it back there for later, maybe adding additional symbols.

Ergo, as long as you do not want to terminate you have to keep putting $\$$ back when you find it.

Why does it have ot be like that, you ask? In the definition I know, PDAs always "take out"² the top-most symbol. So the creator of the PDA has no choice but to deal with the $\$$ once it is on the top of the stack.

But why define it like that, you ask? If PDAs were allowed to not consume the topmost stack symbol they'd be inherently nondeterministic. And since you gain nothing by this choice -- doing nothing with the stack is trivial to simulate by just putting the symbol you read back -- there is no reason to introduce this source of nondeterminism.

Depending on the definition, termination is defined by empty stack or you have to switch into a final state. The definitions are equivalent.
Remember that it's an declarative, not an algorithmic definition!


What does it mean by saying "Asymptotically more efficient"? What does it mean when we say that an algorithm $X$ is asymptotically more efficient than $Y$ ?

$X$ will be a better choice for all inputs.
$X$ will be a better choice for all inputs except small inputs.
$X$ will be a better choice for all inputs except large inputs.
$Y$ will be a better choice for small inputs.

The link for this question is here .

http://quiz.geeksforgeeks.org/algorithms-analysis-of-algorithms-question-16/

I thought that an algorithm more asymptotically efficient should work for all inputs, but I am not getting the reason behind "It works for all inputs except small ones".

First off, both algorithms "work" for all inputs.  The question is about performance.

The answers to that question are kind of crappy.  One way to say one algorithm is asymptotically more efficient than another is if there is some (problem-specific) input size such that for any larger input size the more efficient algorithm will take fewer "computational steps", usually by some abstract measure, e.g. number of comparisons.

The idea of the answers is that an asymptotically more efficient algorithm may still require more steps before that input size.  It can be the case that the asymptotically more efficient algorithm requires fewer steps for all inputs, but it doesn't need to be the case and in practice usually isn't.  So a better wording of the "correct" answer would be "$X$ will be a better choice for all inputs except possibly small inputs".

The wording still isn't that great though.  First off, many more factors go into deciding what algorithm is a "better choice", but I'll give them that the intent is clear enough in this case.  The real issue is "small" and "large".  One of my favorite papers is The Fastest and Shortest Algorithm for All Well-Defined Problems. This paper describes an algorithm which given any specification of a function and a proof that it can be computed in polynomial time will compute that function in optimal time complexity within a factor of $5$ plus an additive term.  For example, if I provided it an implementation of bubble sort as the function specification and the simple proof that it was $O(n^2)$, it would produce a sorting algorithm that was $O(n\lg n)$.  In fact, it would produce an algorithm that was $5cn\lg n + o(n\lg n)$ where $c$ was the constant factor of the asymptotically* optimal algorithm. This is amazing.  There's just one problem: the constant term – hidden in the $o(n\lg n)$ in this example – renders the algorithm almost certainly completely infeasible for virtually any real problem.  What do I mean by "completely infeasible"? I mean the heat death of the universe will happen many times over before that algorithm completes.  Nevertheless, for suitably "large" inputs it will be faster than bubble sort.  My point is it's almost certainly not physically possible to write down by any means a "suitably large" input, let alone compute on it.

At any rate, how I would word the correct answer would be: "$X$ requires fewer steps than $Y$ on sufficiently large inputs".  This is still a bit vague as there are multiple notions of "step" that could apply and an algorithm could be asymptotically more efficient by one metric and less efficient by another.  This wording avoids the value judgement of "better choice"; there are many reasons to choose asymptotically less efficient algorithms or even less efficient algorithms when constant factors/terms are specified such as cache-efficiency or implementation simplicity.

* There is a subtlety here. The asymptotically optimal algorithm may have a worse constant factor, $c$, than an asymptotically non-optimal algorithm. I think it will have the best value of $c$ for any asymptotically optimal algorithm, but it's conceivable that to squeeze out a slight gain in asymptotic efficiency, massive complexity is added that significantly increases the constant factor.


How to understand pushdown automata intuitively? What is an intuitive way of understanding what a push down automaton is capable of computing?

Intuitively, a pushdown automaton uses a stack and using a stack we can do a depth first traversal of a parse tree. It means that we can accept strings which are in context free languages by using stack of a pushdown automaton (left-most derivation). This is not a rigorous proof that languages of pushdown automata are context free. For proofs you must see various textbooks on the subject.


Computing modular exponent given order I want to compute $g^{mn}$ mod $n^2$ where $n=pq$ and I know that $g$ has order $kn$ mod $n^2$ where $m<k$. Is there any clever way of doing it utilizing the order? I have tried other methods of computing $g^{mn}$ directly.

My question stems from an implementation of the Paillier cryptosystem that I'm working on. Right now, I'm following the original paper "Public-key cryptosystems based on composite degree residuosity classes", scheme 3 with the recommendation of generating $g$ using DSA. I have looked at different methods of computing modular exponentiation directly such as square and multiply, k-ary, window sliding, etc.  I want an algorithm for computing $g^{mn} \bmod n^2$ that does not rely upon knowledge of the factorization of $n$.

There's a small chance you might be able to get a speed-up by using properties of arithmetic modulo $n^2$, depending on how $g$ was chosen.

Suppose $g=a(1+bn)$.  Then note that, by the binomial theorem,

$$g^x = a^x (1+bn)^x = a^x \sum_i {x \choose i} (bn)^i  = a^x (1 + bx n + n^2 \times \text{stuff})$$

so we see that

$$g^x = a^x (1 + bx n) \pmod{n^2}$$

Thus if you can compute $a^x \bmod n^2$ efficiently, you can compute $g^x \bmod n^2$ with just a tiny bit more work.  Here you want to take $x=mn$.  The simplification is that now $g$ can always be expressed in the form $g=a(1+bn)$ where $0 \le a < n$.

What can we say about $a$?  Well, for one thing we know that $g^{kn}=1 \pmod{n^2}$, so it follows that $a^{kn}=1 \pmod{n^2}$.  Thus, the order of $a$ modulo $n^2$ has to be a divisor of $kn$.

If the order of $a$ is exactly $kn$, we haven't gotten anywhere.

But if the order of $a$ is a strict divisor of $kn$, we can get some speedup.  We first reduce $mn$ modulo the order of $a$, then compute $a^{mn} \bmod n^2$, and finally use the relationship above to get the value of $g^{mn} \bmod n^2$.  (For instance, if you get lucky, it is possible that the order of $a$ might be $k$, and then you'll get a non-trivial speedup.)

Whether this yields a speedup in practice will depend on the value of $g$ and how $g$ was chosen; since that wasn't specified in your question, it's not possible to evaluate whether this is likely to help in practice, but it might.


Pseudo Code optimization Summary:

I am struggling with the Pseudo code for an that algorithm assigns "least filled slot first" to a tasks on multi-core chip.

Detail

So far I have written following:

What I do not like here is:

In while loop I am removing one by one elements of $R$ (which is a row vector with $m$ elements). This means the complexity of $m^2$, however I could have sorted $R$ outside the loop and then just removed the head every time that would reduce the complexity to $m\log m + m$ for this part. But in that case the index $j$ will get jumbled up and not usable in the rest of the part. Is there an elegant Pseudo-code way of saying "store the indices before sorting for later use"?
Any other stylistic suggestions that make it easier to read while still reducing the "implementation complexity" ?

In general, I know its a trade-off between readability vs complexity. Generally, the main purpose of presenting an algorithm is to make it readable and leave the implementation details to the implementer. But just to be pedantic ..

Thanks.

I think it would be perfectly reasonable and normal to present the pseudocode as is, and to mention in the accompanying text that if you sort $R$ in advance, you can implement this algorithm in $O(m \log m)$ time.  I think it's pretty clear how to implement the selection step, and you don't need to write out all the indices to explain.


Are registers stack, per core or per application based? I am doing a study on I found on youtube called OpenSecurityTraining: Introductory Intel x86. From what I understand there are registers like EAX, ECD, EDX, ect... and each have a purpose and hold/move information in memory.

Are these registers per stack/application? Meaning, each application will have it's own EAX, EDX, ect... that it uses to hold or move data in and out of memory?

Each processor has it's own registers. each process has it's own values to the registers which getting stored/reload during context-switch.


Is there a polynomial time algorithm to tell if an NFA over an unary alphabet is universal? Given an Nondeterministic Finite State Automaton with $n$ states over an unary alphabet, is there some algorithm to check if the automata is universal in time polynomial in the number of states?

I would not expect this would work over an alphabet of size two or more, since it is PSPACE-complete to check whether a regular expression is universal. However, since regular languages over unary alphabets have nice characterizations, I would expect there would be some way to check the universality of an NFA over an unary alphabet.

Determining whether a unary NFA is universal is coNP-complete, as proved by Stockmeyer and Meyer, Word Problems Requiring Exponential Time. See Gruber and Holzer, Computational Complexity of NFA Minimization for
Finite and Unary Languages, for more results in this vein.


TQBF PSPACE-COMPLETE : Why this algorithm is exponential but Savitch's not? So this is a question pertaining to the proof for $PSPACE-COMPLETE$ (for TQBF for example). The idea is to first prove the $L$ $is$  $PSPACE$(easy part) and next is to prove $PSPACE-COMPLETE$. The latter requires demonstrating an algorithm which computes the L in polynomial space. This is usually achieved by having recursive calls such that is re-used.

In TBQF proof, the equation $\phi_{i+1}(A,B)$= $\exists Z [\phi_{i+1}(A,Z)
 \land \phi_{i+1}(Z,B) ]$ ($Z$ is mid-point )is default recursive relation for computing TBQF truth. In any standard proof, it is said that $\phi_{i+1}(A,B)$ is computed two times and for $m$ nodes, this formula explodes hence, other recursive-relation should be used to bound.

However in Savitch's proof, the recursive relation is $Path(a,b,t)$ = $Path(a,mid,t-1)$ AND $Path(mid,b,t-1)$ accepts then ACCEPT. In proof, it is stated that this relation reuses-spaces.

My Question is Why in TBQF relation space explodes while in Path, it is reused? Both of these relations looks more or less same to me because both refers to i-1 instances and will need space to store them?.

In the proof of the $\textit{PSPACE-}$completeness of TQBF, we need to construct a formula of some specific type. The recursive midpoint algorithm is easy to implement (and Savitch's Theorem requires finding the $\textit{algorithm}$), while the same idea, if performed in a similar manner, results in an exponential formula (and the completeness proof requires the $\textit{formula}$).

More generally, suppose there's some language $\textit{L}$, an optimal algorithm $A$ deciding $L$, and the smallest formula (maybe quantified) $\varphi$, s.t. $\varphi(x) = 1 \Leftrightarrow x \in L$. For me, it's not very clear why $A\in \textit{PSPACE}$ would imply that  $\varphi$ is small (I only see it as a consequence of the $\textit{PSPACE}-$completeness theorem)


Boolean Algebra : Using identities, prove x(x + y) = x Example: Prove the ABSORPTION LAW:
$$
x(x + y) = x
$$

$
Solution: \\
x(x + y) \\
= (x + 0)(x + y) \;\;\;\;\; Identity \;Law \\
= x + (0 · y) \;\;\;\;\;\;\;\;\;\;\; Distributive \;Law \\
= x + y · 0 \;\;\;\;\;\;\;\;\;\;\;\;\;\; Commutative \;Law \\
= x + 0 \; \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;Domination \;Law \\
= x \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; Identity \;Law \\
$

I was given an example here and shown one method of solving it. I was told there was an alternative solution to it and I was curious about it.

This is one method of proving the problem.

The alternative method suggested solving the same expression in the order of:

DISTRIBUTIVE LAW, IDEMPOTENT LAW, DISTRIBUTIVE LAW, DOMINANCE LAW, and IDENTITY LAW.

When I try, I get stuck here:

$
Solution: \\
x(x + y) \\
= (x · x) + (x · y) \;\;\;\;\; Distributive \;Law \\
= x + (x · y) \;\;\;\;\;\;\;\;\;\;\;\;\; Idempotent \;Law \\
= (x + x)(x + y) \;\;\;\;\;\; Distributive \;Law \\
$

I've been stuck on where I can prove it using the dominance law, unless I can extend this with an identity law proof. My first time in a while, please excuse.

Solution:
$$ \begin{align}x(x+y)
&= (x\cdot x)+(x\cdot y) \quad\text{[Distributive Law]} \\
&= x + (x\cdot y) \quad\text{[Idempotent Law]} \\
&= x \cdot (1+y) \quad\text{[Distributive Law]}\\
&= x \cdot 1 \quad\text{[Property of 1]} \\
&= x \quad\text{[Property of 1]}
\end{align}$$


Proof (by contradiction) of the emptiness problem I fail to understand the proof of the Emptiness Problem

$E_{TM} = \{\langle M \rangle | M $ is a TM and $L(M) = \emptyset\}$

1) Use the description of $M$ and $w$ to construct $M_1$, which on Input $x$ behaves as follows:

If $x \neq w$, reject
If $x = w$, run $M$ on input $w$ and accept if $M$ does

2) Run $R$ on input $\langle M_1\rangle$

3) If $R$ accepts, reject; if $R$ rejects, accept

I do understand the basic idea of a reduction and in particular the reduction of $A_{TM}$ to $Halt_{TM}$, however,

I do not see how $E_{TM}$ could be used as a subroutine to solve $A_{TM}$. The whole construction of $M_1$ confuses me a lot. To me it looks like $M_1$ is just like a filter that rejects everything except $w$
But why does $M_1$ even have to check if $x$ equals $w$? As soon as $S$ is fed with a particular pair $\langle M,w\rangle$, $x$ will be equal to $w$, no? how can it be anything different than $w$?

$M_1$ rejects everything, including $w$, unless $M$ accepts it (crucial). $M_1$ will then be a machine that always rejects, if and only if $M$ rejects $w$.
The white box treats $M$ and $w$ as constants. They are still something that $S$ received as input, and we know that.
$R$ is a hypothetical machine that decides if its input is a machine that always rejects.
$S$ will receive unknown $\langle M,w \rangle$ as its input. Should $R$ work as intended, then $S$ in fact solves the general problem of deciding if $M$ accepts $w$, which is exactly $A_{TM}$.
It has been proven that $A_{TM}$ is not decidable.

Therefore,

$R$ cannot exist.
Our reference question has more information on the subject. You may find particularly interesting to see how this kind of proof can be generalized (look for Rice's theorem).


Calculate how much segements the system can handle I am a bit lost calculating how much segments will the system handle in a memory segmented system (without virtual memory). The problem says that the system has a word length of 32 bits and the address are 6 hexadecimal numbers, 3 of them are the segment identifier. We have a segment size of 4KiB

I tought this:

If the address are of 24 bits wide, we could address $2^{24}$ bytes of data and our segment size is $2^{12}$ bytes. So divide them and we have the maximum number of segments our system can handle.

But I was told this isn't the way to solve this problem. Here is the way it's supposedly correct:

We have $2^{24}$ address in our system, with a length of 32 bits so we have $2 ^ {29}$ bits of addressable memory, $2 ^{16}$ KiB of addressable memory. So dividing between our segment size we have $2^{14}$ segments.

But I don't find this answer correct, because if it says that the 3 hex digits identifies the segment we have 12 bits to identify every segment, with a maximum of $2^{12}$ segments, so I don't know how the second solution manage to add 4 times more segments than my solution.

So what answer is correct?

Thanks

I think neither of those is a good solution, but yours is better than the one you were given.

Here's how I'd reason through it: there are 3 hex digits to represent the segment identifier.  That's 12 bits for the segment identifier.  12 bits can identify up to $2^{12}$ possibilities.  So the system can have at most $2^{12}$ possible segments.  The rest of the information is irrelevant.


Is $O$ contained in $\Theta$? So I have this question to prove a statement:

$O(n)\subset\Theta(n)$...

I don't need to know how to prove it, just that in my mind this makes no sense and I think it should rather be that $\Theta(n)\subset O(n)$.

My understanding is that $O(n)$ is the set of all functions who do no worse than $n$ while $\Theta(n)$ is the set of all functions that do no better and no worse than n.

Using this, I can think of the example of a constant function say $g(n)=c$. This function will surely be an element of $O(n)$ as it will do no worse than $n$ as $n$ approaches a sufficiently large number.

However, the same function $g$ would not be an element of $\Theta(n)$ as g does do better than $n$ for large $n$... Then since $g  \in  O(n)$ and $g \not\in \Theta(n)$, then $O(n)\not\in\Theta(n)$

So is the question perhaps wrong ? I've learnt it is dangerous to make that assumption and usually I have missed something, I just can't see what it might be in this case.

Any thoughts ?
Thanks a lot..

At the suggestion of Raphael, I have turned a previous comment into this answer.

It is not true that $O(f(n)) \subset \Theta(f(n))$. In fact, $\Theta(f(n)) = O(f(n)) \cap \Omega(f(n))$, by definition. So we have $\Theta(f(n)) \subset O(f(n))$.


context free grammar of given language I wonder how can I find out what is context-free grammar of the following language?

$$
L_4 = \{w_1\#w_2 \mid w_1,w_2 \in \Sigma^*, w_1 \neq w_2^R \}
$$

Assume $\Sigma = \{a,b\}$. We want to generate a word $w_1\#w_2$ is such that $w_1 \ne w_2^R$. There are two obvious possibilities:

$|w_1| = |w_2|$: In these words, there has to be at least one pair of positions equidistance from $\#$ such that the letters in these positions are different. Using the non-terminal $S_1$, we will generate the part of $w$ till we reach the first such pair; then we transition to non-terminal $S_2$ which will generate the opposite letters at that pair of position and move to the non-terminal $S_3$. From $S_3$, we are free to generate whatever we want. This will make sure that we have at least such pair of opposite letters, and hence $w_1 \ne w_2^R$.
We can generate such words using following grammar:
\begin{align}
S_1   &\rightarrow aS_1a|bS_1b|S_2\\
S_2  &\rightarrow aS_3b|bS_3a\\
S_3 &\rightarrow aS_3a| bS_3b| aS_3b | bS_3a|\#
\end{align}
$|w_1| \ne |w_2|$: In this case, with the non-terminal $P_1$ we will generate any word with equal number of letters on both side of $P_1$, and then we will move to either the non-terminal $P_2$ or $P_3$. With $P_2$ (or $P_3$) we will generate more letters either on the left side (or the right side) of $\#$. In the end, this will make sure that $|w_1| \ne |w_2|$.
We can generate such words using the following grammar:

\begin{align}
P_1   &\rightarrow aP_1a| bP_1b| aP_1b | bP_1a| P_2 |P_3 \\
P_2  &\rightarrow aP_2|bP_2|a\# | b\#\\
P_3 &\rightarrow  P_3a|P_3b|\#a | \#b\\
\end{align}

For the given language, the grammar would be: $S \rightarrow S_1|P_1$.


Context-free grammar for all words not of the form w#w I was asked to define a CFG for the complement of $\{w\#w \mid w \in \{0,1\}^*\}$ and I'm struggling to define it. I think it is quite similar to defining a CFG for the complement of $\{ww \mid w \in \{0,1\}^*\}$, but  I'm finding that the '#' really messes things up. Is the language even context-free?

If a word is not of the form $w\#w$ then one of the following must happen:

It contains no $\#$.
It contains more than one $\#$.
It is of the form $x\#y$, where $x,y \in \{0,1\}^*$ and $x \neq y$, in which case one of the following must happen:

$|x| > |y|$ or $|x| < |y|$.
$x_i = 0$ and $y_i = 1$ for some $i$, or vice versa.

The only case which is non-trivial to handle is the last one, in which case we have a word of the form
$$
x_1 0 x_2 \# y_1 1 y_2,
$$
where $|x_1| = |y_1|$. We can split this into
$$
x_1 \;\; 0x_2\# \;\; y_1 \;\; 1y_2,
$$
where $|x_1| = |y_1|$. This should make it clear how to construct a CFG for such words.

Altogether, we obtain the following grammar:
\begin{align}
&S \to A \mid B \mid C \mid D \mid E \mid F \\
&A \to 0A \mid 1A \mid \epsilon \\
&B \to A\#B \mid A\#A\#A \\
&C \to A0G \mid A1G \\
&D \to G0A \mid G1A \\
&G \to 0G0 \mid 0G1 \mid 1G0 \mid 1G1 \mid \# \\
&E \to E_11A \\
&E_1 \to 0E_10 \mid 0E_11 \mid 1E_10 \mid 1E_11 \mid 0A\# \\
&F \to F_10A \\
&F_1 \to 0F_10 \mid 0F_11 \mid 1F_10 \mid 1F_11 \mid 1A\# \\
\end{align}
In this grammar:

$A$ generates words without $\#$
$B$ generates words with more than one $\#$
$C$ generates words of the form $x\#y$ with $|x| > |y|$
$D$ generates words of the form $x\#y$ with $|x| < |y|$
$E$ generates words of the form $x_10x_2\#y_11y_2$ with $|x_1|=|y_1|$
$F$ generates words of the form $x_11x_2\#y_10y_2$ with $|x_1|=|y_1|$
$G$ generates words of the form $x\#y$ with $|x| = |y|$


Shortest traverse path in a matrix given the start point $(i,j)$ Given a $m\times n$ matrix and a starting position $(i,j)$, how can we find the shortest path to go through all the elements at least once if we can only move by a single unit (i.e. up, right, left or down) at a time?
Currently all I could think of was moving to the nearest corner and then traversing from there, but that would not be the shortest path unless the start position is already a corner. And unfortunately I couldn't find anything similar to this problem.

If either $m=1$ or $n=1$, the starting position will determine how many elements will need to be revisited - head to the nearest end and the back to the other. The following cases consider $m,n>1$.
If either $m$ or $n$ is even, there is a simple traverse starting from any element (and which will conclude on an adjacent element), without revisiting any element.
Consider a $2\times n$ matrix. Then there is a loop traverse that runs one way along one row and back along the other row:

Now for a $2k\times n$ matrix you can stack these loops and jump from loop to loop as required:

(there is no requirement to stagger the loop jumps - that is purely choice). The same idea applies if it is $n$ rather than $m$ that is even.
When $m$ and $n$ are both odd, you do not have a convenient loop path. If for your starting square, $i$ and $j$ are opposite parity - one odd, one even - you cannot avoid one revisit of a cell. A checkerboard colouring argument shows that easily. I believe that otherwise you can complete a path without a revisit, provided you avoiding leaving "dead end" elements until inevitable.


Conversion of ambiguous left recursive grammar to LL(1) I have been strugling with this LL(1) transformation for far longer than expected and am getting quite desperate. We are given a grammar $ G = \left\{V_N, V_T, S, \Phi \right\}$, with the non-terminal set $V_N = \left\{S\right\}$, terminal set $V_T = \left\{\underline{o}, \underline{l}, \underline{r}, \underline{i}\right\}$, start symbol $ S $ and the production rules in $\Phi$:

$$ \begin{equation}\begin{split} S \rightarrow & \ S \underline{o} S \\ S \rightarrow & \ S \underline{l} S \underline{r} \\ S \rightarrow & \ \underline{i}\end{split}\end{equation}$$

I have tried the standard tricks like left factoring, left recursion removing, which lead to an infinite transformation loop. Trying to fix first and follow set clashes also did not help. Here are some results after applying the transformations:

$$ \begin{equation}\begin{split} S \rightarrow & \ \underline{i} A & \ \ \ \ \ \ \ \ \ \ \ S \rightarrow & \ S A \\ A \rightarrow & \ \underline{o} S A & \ \ \ \ \ \ \ \ \ \ \ S \rightarrow & \ \underline{i} \\ A \rightarrow & \ \underline{l} S \underline{r} A & \ \ \ \ \ \ \ \ \ \ \ A \rightarrow & \ \underline{o} S \\ A \rightarrow & \ \epsilon & \ \ \ \ \ \ \ \ \ \ \ A \rightarrow & \ \underline{l} S \underline{r} \end{split}\end{equation} $$

However I go about the problem, I cannot seem to get even close to eliminating the double entries in my LL(1) table.

I don't want to do your homework, but the two insights that appear to solve it for me are:

What the first rules

$S \rightarrow SoS$

$S \rightarrow SlSr$

say is that whatever else $S$ can be rewritten to (which, in this case, is just $i$) can be followed by any number of occurrences of $oS$ and $lSr$ arbitrarily often.

If we introduce a nonterminal for that (the part that follows the $i$), left-factorized rules for it follow immediately.


Subset sum NP-Completness I know that the subset sum problem is NP-Complete because I can reduce a known NP-Complete problem to subset sum.

However, since subset sum can be solved by dynamic programming, I was not completely convinced that it is NP-Complete. I then realized that the dynamic programming solution in fact tries all possible combinations and because of this, is in fact the same as a brute force approach. Is this a valid insight into why subset sum is NP-Complete?

tries all possible combinations and because of this, is in fact the same as a brute force approach

You don't share the specific algorithm you have in mind, but I think you are wrong. Trying all splittings at every level of the recursion is not the same as trying all solutions.

  since subset sum can be solved by dynamic programming, I was not completely convinced that it is NP-Complete

Again, you don't share the specific algorithm, but it probably has pseudo-polynomial running time. So no, there is no contradiction; "dynamic programming" does not equal "polynomial time" let alone "fast".


Type checking on assignment I want to develop an interpreter. In the language, you have values and variables and types. The literals (the values) belong to some basic type. The subtypes can constrain the range of values. The spec says that making assignment, we ensure that the value assigned is assignable to the target (variable) range. Is it worth do the check on every assignment or ensure statically? How do you ensure it statically?

In the current implementation, I see that a type is attached to every value object. Are there are better approaches?

It depends on how the language is defined.

Language might be statically typed (like e.g. C, Java, Haskell, ...) or dynamically typed (like e.g. Python, Common Lisp, ...). In a statically typed language every expression has associated value and the semantic analyser checks whether the types match just after when the expressions are parsed.

In a statically typed language if you have variable a defined to contain integer and variable b defined to contain integer between 0 and 10, assignment b = a is not valid at compile. Of course such language needs a way of saying "please check whether the value will fit and set it if it does and do that if it does not". Usually via some kind of type cast that throws an exception, but might be anything.

In a dynamically typed language expressions don't have any type specified and whether the value can be assigned is always checked at runtime when specific type is needed.

Combination is possible where expressions may have associated type and if they don't, they are considered to be of universal "any" type and runtime check is omitted if it is possible to statically ensure the value will fit.

Then there are strongly typed languages (e.g. Java, Python, Haskell, ...) and weakly typed languages (C, C++, Pascal). In a strongly typed language each value has associated type and this type may be checked at runtime if needed. On the other hand in weakly typed languages the value is just a bit pattern and gets interpreted according to the static type of the expression. Note that dynamically typed languages are strongly typed as their values carry their type around with them.

Since your language has variable types, it is at least partially statically typed. So you can do some static type checking. If you have assignment of variable that can hold positive numbers to variable that can only hold negative numbers, you can reject such statement straight away without waiting for the actual values, because the ranges are disjoint (the types are incompatible).

If the type on the right hand is a subtype of the one on left hand (the range is smaller), you know the statement will always be ok. You don't need to do a check at runtime.

If the types have some overlap, but the type on right hand is not a subtype, i.e. may have values that don't fit in the variable on the left side, you may either require explicit check or you may automatically inject a check that will yield error or exception if at runtime the actual value does not fit. Which you do depends on the specification of the language.

Last for constants you handle them as special case of the subtype rule. A constant 42 is an integer in range [42, 42]. This is a subtype of all ranges that can contain 42 and you can do the check at compile-time.


Precomputation for partial products in monoids Suppose I have a sequence of elements $a_1,\ldots,a_n$ in a group and I want to compute, for varying $1\leq i\leq j\leq n$, the product $b_{i,j}:=\Pi_{i\leq k\leq j}a_k$. Then I can do a precomputation of all $b_{1,j}$ and later determine each needed $b_{i,j}$ as $(b_{1,i-1})^{-1}b_{1,j}$.

The cost is $O(n)$ group operations and $O(n)$ additional time for the precomputation, and $O(1)$ operations and $O(1)$ additional time for each access. Clearly optimal. So far so good.

Now what if I don't have inverses (that is I have a monoid instead of a group)?
The best I can come up with is a binary-tree like precomputed data structure. The cost of access would increase to $O(\log n)$. Can that be improved?

As you say, with $O(n)$ precomputation you can arrange that each access takes $O(\log n)$ time.  You build a binary tree over the elements, and annotate each internal node with the product of the leaves under it.  This takes $O(n)$ precomputation and $O(n)$ storage.

If you are willing to do more precomputation, you can reduce the access time.  In particular, with $O(n \log n)$ precomputation and $O(n \log n)$ storage, you can arrange that each access runs in $O(1)$ time.  The idea is outlined below.

Notationally, we will let $b_{i,j}$ denote the product $a_i a_{i+1} \cdots a_j$, as you define in your question.

First, precompute the products $b_{i,n/2-1}$ for $i=1,2,\dots,n/2-1$ and the products $b_{n/2,j}$ for $j=n/2,\dots,n-1,n$.  This can be done with a $O(n)$ precomputation.  This will let you compute any product $b_{i,j}$ in $O(1)$ time if we have $i < n/2 \le n/2$, i.e., if the range $[i,j]$ spans the midpoint.

We still need a way to handle ranges that don't span the midpoint.  We'll handle that recursively.  Basically, take the sequence $a_1,\dots,a_{n/2-1}$ and recursively build a data structure for it (e.g., find its midpoint $a_{n/4}$, etc.).  Also, recursively build a data structure for $a_{n/2},\dots,a_n$.  This will let us compute all products $b_{i,j}$ where $j<n/2$ or $i\ge n/2$, i.e., where the range $[i,j]$ doesn't span the midpoint.  This covers all the cases.

How much time does the precomputation take?  If $T(n)$ denotes the time for the entire precomputation, it satisfies the recurrence

$$T(n) = 2 T(n/2) + O(n),$$

which solves to $T(n) = O(n \log n)$.  Similarly, we can see that the amount of storage needed is also $O(n \log n)$.  Finally, this data structure will let you compute any product $b_{i,j}$ in $O(1)$ time.

(I'll let you figure out how to compute $b_{i,j}$ from this data structure in $O(1)$ time.  It can be done with some clever bit-shifting tricks.  It may help to think about the data structure in terms of the big-endian binary representation of the indices.  For each index $i$, we compute $b_{i,i'}$ where $i,i'$ share a common prefix and then $i'$ is all ones after the common prefix; and we compute $b_{j',j}$ where $j',j$ share a common prefix and then $j'$ is all zeros after the common prefix.  Given $i,j$, we can find the longest common prefix of $i,j$, then express as the product $b_{i,j} = b_{i,i'} b_{j',j}$, look up the values of $b_{i,i'}$ and $b_{j',j}$, and compute the product.  All of these can be done in $O(1)$ time by placing the precomputed values in an array in the correct order.)


Is there an optimization algorithm that could help match the maximum number clients to servers with constraints? How do you go about solving the following problem that tries to match the greatest number of clients with servers with constraints? I'm trying to identify an algorithm or simulation that could help me solve this problem as optimally as possible.
Assume you are given a 2d map of servers and clients randomly scattered. Each server can handle a certain radius of clients but never two clients that are near each other (this is the constraint). While it makes sense for a server to handle all the clients near it, some clients may need to be handled by another server nearby. Picking which of those clients should be handled by another server (potentially farther but still in reach) such that the maximum number of clients can be handled is the objective.
Not all clients necessarily can be handled, but the problem should be able to match the most number of clients with servers possible, and the constraint must be upheld.

The problem is NP-hard.  Consider the following special case: there is only one server, and its radius is infinite (or very large). Then your problem becomes the problem of finding an independent set in a planar graph.  That problem is known to be NP-hard.  Since a special case of your problem is NP-hard, then your problem must be at least as hard in the general case.
There are many ways to deal with NP-hard problems.  Probably one reasonable approach is to formulate your problem as integer linear programming, and then solve with an off-the-shelf ILP solver.  Another approach is to formulate it as an instance of SAT (with a pseudoboolean constraint/cardinality constraint for counting the number of clients that are serviced), and solve with an off-the-shelf SAT solver, like Z3 (which has good support for pseudoboolean constraints).


Leader Election: Every bit-reversal ring is $\frac{1}{2}$-symmetric I have a proof that I need help with. Like the title says, the theorem is that every bit-reversal ring is $\frac{1}{2}$-symmetric. The theorem is for Leader Election algorithm in synchronous ring. The things I know follow:
Bit reversal ring is defined as follows: We assign to each process $i$ the integer from ${0,\ldots, n-1}$ whose $k$ bit representation is the reverse of the $k$ bit representation of $i$. $n$ is also a power of two, $n=2^{k}$.
Two segments $U$ and $V$ are order equivalent if they are the same length $k$, and for all $i$ and $j$ such that $1 \leq i,j \leq k$ we have that $u_{i} \leq u_{j}$ if and only if $v_{i} \leq v_{j}$.
Ring $R$ is $c$-symmetric if for every segment $S$ of $R$ there are at least $\lfloor \frac{cn}{l} \rfloor$ segments that are order equivalent to $S$, including $S$ itself, where $l$ is length of the segment, and this holds for every $\sqrt{n} \leq l \leq n$.
So after plugging all I know into formulas I get that $\lfloor \frac{2^{k-1}}{l} \rfloor$ is formula for number of segments and $l$ is such that $2^{\frac{k}{2}} \leq l \leq 2^{k}$.
Any hint or piece of information would be much appreciated! Thank you.

We will prove your formula for all $\ell$, with a bound of $\lceil \frac{n/2}{\ell} \rceil$. We can assume that $\ell < n/2$, since otherwise $\lceil \frac{n/2}{\ell} \rceil = 1$, and there is nothing to prove. Also, if $n = 1$ then the result is trivial, so we can assume that $n \geq 2$.
The relative order of elements in the interval of length $n/2$ starting at $i$ is the same as the relative order of elements in the ring of length $n/2$, when read from position $i$. For example, here are all intervals of length $4$ in the ring of length $8$, and the corresponding intervals in the ring of length $4$:
\begin{align}
&0,4,2,6 & 0,2,1,3 \\
&4,2,6,1 & 2,1,3,0 \\
&2,6,1,5 & 1,3,0,2 \\
&6,1,5,3 & 3,0,2,1 \\
&1,5,3,7 & 0,2,1,3 \\
&5,3,7,0 & 2,1,3,0 \\
&3,7,0,4 & 1,3,0,2 \\
&7,0,4,2 & 3,0,2,1
\end{align}
To see this, note first that each interval on the left doesn't contain a pair of elements which differ only in their LSB. Therefore, we can ignore the LSB of all elements on the left. One way to do it is to divide all elements on the left by two. This results in the intervals on the right.
This property immediately implies a similar property for all intervals of length $\ell \leq n/2$: the relative order of elements in the interval of length $\ell$ starting at $i$ is the same as the relative order of elements in the interval of length $\ell$ starting at $i \bmod (n/2)$ in the ring of length $n/2$. This implies (by induction) that an interval of length $\ell \leq n/2$ has at least this many order-equivalent intervals: $2\lceil \frac{n/4}{\ell} \rceil \geq \lceil \frac{n/2}{\ell} \rceil$.


Confused between turing-completeness and universal approximation - are they related? I am trying to de-knot a point of confusion in my mind regarding "turing-completeness" and the "universal approximation theorem".

The context here is deep neural nets: So, consider two types of networks: a recurrent neural net, (RNN), and a feedforward net, say a pure convolutional neural net (CNN).

I understand that the RNN is turing complete. I also know that a CNN is a universal approximator, but is NOT turing complete.

What I am trying to understand is the link between universal approximation, and turing-completeness: Is there a link? Why is a CNN a universal approximator but NOT turing complete? Does a machine being turing-complete automatically make it a universal approximator? Trying to uncouple the two concepts.

Thanks!

A CNN can approximate a function on a fixed number of input variables, say $n$ of them.  The set of functions on $n$ input variables isn't "Turing-complete".  For instance, a boolean function $f:\{0,1\}^n \to \{0,1\}$ is always computable, as it can be computed by a program that just hardcodes the truth-table of $f$; and the set of such functions is not "Turing-complete".

Complication: CNN's actually approximate continuous functions $f:\mathbb{R}^n \to \mathbb{R}$... but a similar point remains (at least if the input is bounded).

Turing-completeness isn't really connected to universal approximation.  For one thing: Turing-completeness talks about languages, which are subsets of $\{0,1\}^*$ and thus refers to discrete entities.  Universal approximations talks about functions $f:\mathbb{R}^n \to \mathbb{R}$, and thus refers to continuous entities.

To qualify for "universal approximation", it's enough to be able to approximate all functions of $n$ variables (for each function, there exists a neural network that approximates it), so it talks about functions on inputs of bounded length.  Turing-completeness requires the ability to compute all computable functions, which is a set of functions that has no fixed upper limit on the number of variables, i.e., it is a set of functions on inputs of unbounded length.  Universal approximation could thus, in some sense, be considered "weaker" than Turing-completeness (though strictly speaking they are incomparable; neither implies the other).


Given two sequences of the same size, how many longest common subsequences can they have? For simplicity assume that both have the same size N.

the lengh of this subsequence can be at most N, so maybe it's

max(C(N,1), C(N,2), ... , C(N,N))?

I understand the question as follows:

Given $n$. How many different longest common consecutive subsequences might two strings of length $n$ have at most?

If this is your question, than consider for example the string $a_1a_2...a_n$ with $a_i\ne a_j$ for $i\ne j$ and the reverse string $a_na_{n-1}...a_1$. The longest common subsequences of those strings are all subsequences of length $1$ $(a_1,a_2,...,a_n)$. Therefore, in your unrestricted question, the maximal number of different longest common subsequences of two strings of length $n$ is equal to the the maximal number of different subsequences with same length, which is $n$ for subsequences of length $1$.

If you restrict the question to strings over a given alphabet of fixed size, lets say $k$, the answer is much more difficult.


The same outgoing and incoming degree in graph I have an undirected graph with $n$ vertices and $m$ edges. How to determinate in $poly (n, m)$, is it possible (and how is it necessary) to orient all the edges so that each vertex has the same outgoing and
incoming degree.

If such an orientation is possible, then all degrees are even. Conversely, if all degrees are even then the graph is Eulerian. Orient the edges according to an Eulerian circuit.


Context-free grammar for complement of $\{ab \mid b=\mathrm{complement}(a)\}$ I want to construct a context-free grammar for
$$L=\Sigma^*-\{ab \mid b=\mathrm{complement} (a)  , a,b \in \{0, 1\}^*\}$$
and prove the correctness of answer. The complement of a string is obtained by switching $0$s and $1$s. For example, $\mathrm{complement}(001) = 110$.
I'm trying to decompose the language but I'm not sure about the different cases I should consider. For example, I know that $L$ contains all strings with odd length. But what else do I have to consider? Also, I can't make sure that the language of constructed grammar equals the given language, so a proof is needed.

As you have noticed, you can decompose between words of odd length and words of even length. Since the odd part is quite easy, I will focus on the even one, that is $L = \{uv \mid u, v\in \{0,1\}^*\wedge u\neq \mathrm{complement}(v)\}$.
Given $u, v\in\{0,1\}^*, |u|=|v|$, if we write $u = u_1…u_k$ and $v = v_1…v_k$, then $uv \in L$ if and only if $k \geq 1$ and $\exists i \in [\![1,k]\!], u_i = v_i$. In that case, we can write $uv = wu_ixv_iy$ where $|w| = u_1…u_{i-1}$ and $y = v_{i+1}…v_k$. We also have $|x| = k-i + i -1= k-1$, so $x$ can be written as $x = zt$ with $|z| = i-1 = |w|$ and $|t| = k-i = |y|$.
We will now write a grammar to generate these words. Let's define:

$S\to AA\mid BB$
$A \to 0 \mid 0A0 \mid 0A1 \mid 1A0 \mid 1A1$
$B\to 1\mid 0B0\mid 0B1 \mid 1B0 \mid 1B1$

It is clear that $A$ rules will generate a word $w0x$ with $|w| = |x|$. That means that $AA$ will generate $w0zt0y$, with $|w| = |z|$ and $|t| = |y|$. The same thing can be done with $BB$.
(This answer was greatly inspired by this one.)


Bellman Ford for directed graph G finds shortest paths within one iteration Given directed graph G, vertex s, and all v∈V(G) are 1 edge distant from vertex s.

Is it possible to find a specific edges order (from E(G)) such that a single iteration of Bellman Ford pass over these edges in this order finds all the shortest paths (in weight) from vertex s to all vertices?

I couldn't find a counterexample for that, and it seems correct. But I have no idea how to prove it - would appreciate any hint and direction....

If there's no negative cycle, this is true even without the constraint that all $v\in V(G)\backslash\{s\}$ are one edge distant from vertex $s$.

  Lemma. There exists a shortest path $e(v,1)e(v,2)\ldots$ (where $e(v,1),e(v,2),\ldots \in E(G)$) from $s$ to $v$ for each $v\in V(G)\backslash \{s\}$, such that for each $v_1,v_2\in V(G)\backslash \{s\}$, if there exists $i_1,i_2,j_1,j_2$ such that $e(v_1,i_1)=e(v_2,i_2)$, $e(v_1,j_1)=e(v_2,j_2)$ and $i_1<j_1$, then $i_2<j_2$.

Proof. Suppose there are such shortest paths corresponding to $v_1,\ldots,v_k$. Fix these paths and consider any shortest path $e(v_{k+1},1)e(v_{k+1},2)\ldots$ from $s$ to $v_{k+1}$. Let $i$ be the largest index such that $e(v_{k+1},i)$ appears in those fixed shortest paths corresponding to $v_1,\ldots,v_k$. Say $e(v_{k+1},i)=e(v,j)$ for some $v\in\{v_1,\ldots,v_k\}$ and some index $j$. Now consider the new path from $s$ to $v_{k+1}$: $e(v,1)\ldots e(v, j) e(v_{k+1},i+1)\ldots$ Note $e(v,1)\ldots e(v, j)$ must be a shortest path from $s$ to the vertex to which $e(v,j)$ points (otherwise $e(v,1)e(v,2)\ldots$ is not the shortest path from $s$ to $v$), the new path is no longer than $e(v_{k+1},1)e(v_{k+1},2)\ldots$ Now regarding this new path as the shortest path corresoponding to $v_{k+1}$, we have proved there are shortest paths corresponding to $v_1,\ldots,v_{k+1}$ satisfying the conditions in the lemma. Furthermore, the lemma is proved by mathematical induction. $\blacksquare$

Due to the lemma, there exists a total order of edges that is consistent with the order of edges in each shortest path selected by the lemma. Apply the first iteration of Bellman-Ford algorithm according to this total order and consider a vertex $v\in V(G)\backslash \{s\}$. Recall that $e(v,1)\ldots e(v, j)$ must be a shortest path from $s$ to the vertex to which $e(v,j)$ points, so after dealing with $e(v,1)$, the minimum distance from $s$ to the vertex to which $e(v,1)$ points is computed correctly, and after dealing with $e(v,2)$, the minimum distance from $s$ to the vertex to which $e(v,2)$ points is computed correctly, and so on. Finally we can conclude the minimum distance from $s$ to $v$ is computed correctly. As a conclusion, one iteration corresponding to this total order is sufficient.


How to go about working the average case run time of this trivial algorithm (and other algorithms)? This is a similar algorithm to one I used in a previous question, but I'm trying to illustrate a different problem here.

for (int i = 0; i < numbers.length - 1; i++) {
    for (int j = i + 1; j < numbers.length; j++) {
        if (numbers[i] + numbers[j] == 10) {
            System.out.println(i+" and "+j+" add up to 10!");
            return;
        }
    }
}
System.out.println("None of these numbers add up to 10!");
return;

Basically, I realised, that I have a decent understanding of how to work out the best case run time here. I.e. the first two numbers which are fed in, add up to 10, and therefore our best-case runtime is constant time. Also, I understand that in the worst-case, none of the numbers we provide add up to 10, so we must then iterate through all loops, giving us a quadratic runtime. However, in the slides I was going through (for this particular course) I noticed that I had missed this:

Average case

• Presume that we've just randomly given
integers between 1 and 9 as input in
numbers to our previous example

• Exercise: Work out the average running time

I realise I don't have the first clue as to how to go about calculating average case run-time. I'm not asking for the answer to: "what is the average-case runtime for this algorithm?", what I need to know is, how do you work something like this out?

Here's an elaboration of The Unfun Cat's answer. For convenience, let the numbers be $v_1,\ldots,v_n$. Whatever the value of $v_1$ is, for $i>1$ we have $\Pr[v_i = 10-v_1] = 1/9$. Therefore, the number of iterations of the second loop is roughly distributed geometrically $G(1/9)$, so we expect it to run about $9$ times. A complication is that $n$ is not infinite, but this doesn't have a great effect on the running time.

Given $n$, the probability that the outer loop doesn't terminate on the first iteration is $(8/9)^{n-1}$. If it does, then the expected number of (inner-loop) iterations is less than $9$. Otherwise, it is at most $\binom{n}{2}$. Therefore the running time is $O(9 + \binom{n}{2}(8/9)^{n-1}) = O(1)$, using $n^2 = O((9/8)^n)$.


Underlying codes for Niederreiter cryptosystems Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$.

The minimum distance $d$ is given by

$d := min\lbrace k \text{ such that there are $k$ linearly dependant columns in $H$}\rbrace$

Encryption in this case is done by encoding messages $m$ of weight less than $d/2$.

Now keeping Niederreiter systems in mind, my question is, since $m$ is over $\mathbb{F}_2$, it makes sense to consider linearly dependence over $\mathbb{F}_2$ rather than $\mathbb{F}_{2^n}$. In other words, is it okay to consider code as a code over $F_{2}$ with alphabet extension or do we  have to consider it as codes over $\mathbb{F}_{2^n}$.

According to Sendrier, Niederreiter systems are only known to be secure when used with Goppa codes. All other families of codes which have been tried have been broken. You are suggesting a code superficially related to the Goppa code but probably having very different properties. Hence it is likely to be insecure (or perhaps useless for other reasons, such as low rate or low distance).

More generally, cryptosystems are surprisingly brittle. I would leave them to the experts.


Writing a grammar for lambda calculus I'm trying to write a context-free grammar (to be feeded to lark) for parsing lambda calculus expressions. Basic version of it, as presented by most sources, looks like:

expr: variable | "(" expr ")" | application | abstraction
abstraction: "λ" variable "." expr
application: expr expr

I'd like the grammar to unambiguously parse expressions taking advantage of the notational conventions mentioned here on Wikipedia.
While I'm able to modify the grammar to follow most of them, I got stuck with implementing this one: "The body of an abstraction extends as far right as possible".

For example, there are two parse trees for λx.x λa.a - it can be both an application of two abstractions ( (λx.x)(λa.a) ) or an abstraction with an application in its body ( λx.(x(λa.a)) ).
If the abstraction was greedy as it should be, only the second one would be correct.

Is it possible to write a grammar that would force (i.e., make it the only choice) greedy interpretation of abstractions? If so, how to do it?

As @chi wrote, one good solution would be to enforce parenthesis around both applications and abstractions.

Because I want to be as close to "handwritten" lambda calculus (so I'd like to eliminate parenthesis as much as possible), I tried another approach, which eventually worked. I blocked applications from having abstractions (not parenthesised abstractions, just abstractions) on their left side, so that λx.x M will never parse to
(λx.x)M. This will force the greedy parsing of abstractions - λx.(xM), exactly as I want.

The grammar doing that might look like this:

atom: "(" expression ")" | variable
expr: atom | abstraction | application
abstraction: "λ" variable "." expr
application: atom | application (atom | abstraction)


P vs NP characterization confusion I know that $P \subseteq NP$, but for a problem in $P$, e.g. MST in a graph, is it a correct statement to say that:
The MST problem belongs in NP-Class.
(I mean, i think it is correct, but could someone classify that as wrong because he would expect P instead of NP?)

The statement is correct for exactly the reason you started with: $\mathsf P$ is a subset of $\mathsf{NP}$ which means that every problem in $\mathsf P$ is also in $\mathsf{NP}$. You can also go through the definitions and find that a deterministic TM running in polynomial time is merely a special kind of nondeterministic TM running in polynomial time and take it from there.
However, while being true, the statement "MST is in $\mathsf{NP}$" holds less value than the statement "MST is in $\mathsf P$" as complexity theory is, at large, concerned with lower bounds. A decent analogy in my opinion would be that the statement $\pi \geq 3$ is stronger than the statement $\pi \geq 0$ eventhough both are true.


Why does a polytime hitting set generator derandomize RP? I am reading Goldreich, Vadhan, Wigderson: Simplified Derandomization of BPP Using a Hitting Set Generator and trying to understand the result that polytime hitting set generators (HSGs) would not only imply $\mathsf{RP = P}$ but $\mathsf{BPP = P}$ as well, but I can't even conceptualize why the former holds.
The paper states that

Having such a generator that runs in polynomial time enables a trivial deterministic
simulation of an RP algorithm by using each of the generator’s outputs as the random pad
of the given algorithm.

Every paper or lecture notes I've found on the topic of HSGs and $\mathsf{BPP}$ derandomization also mentions that $\mathsf{RP}$ derandomization is trivial using an HSG, simply by trying all elements of the hitting set as random pads.
I am confused as to why this is the case. At least one element of a hitting set must be accepted by circuits that accept over half of their inputs. However, RP circuits don't necessarily accept over half their inputs; rather, if $x \in L$, only then will the circuit accept over half the time. I assume that fact is related to why a hitting set must contain a valid $\mathsf{RP}$ random pad, but I do not understand exactly how.
So, my question is: how do the circuits in the definition of an HSG relate exactly to $\mathsf{RP}$ circuits? i.e. how do the elements of the hitting set - which are to be the random pads across all inputs - relate to the randomness of RP algorithms when such algorithms accept over half the time only when $x \in L$?

The point is that instead of checking what happens for all possible random strings, you can reduce the search to the output of the generator.
Let $M(x,r)$ be some RP machine for a language $L$, i.e. if $x\in L$ at least two thirds of the $r$'s lead to acceptance, and if $x\notin L$ there is no $r$ for which $M(x,r)$ accepts. Now, Given input $x$, construct a circuit $C_x(r)=M(x,r)$ and execute the generator $G\left(p(|x|),|C_x|\right)$, where $p(n)$ is the number of random bits used by $M$ on a length $n$ input. This yields a set $R$ of polynomially many strings, now simply check whether or not $C_x(r)$ accepts at least one element from $R$. This doesn't straightforwardly generalizes to BPP since in that case it might be the case that $x\notin L$ but $C_x(r)$ accepts some strings from $R$.


How many combination of “n” bits are there in terms of n? How many combination of "n" bits are there in terms of n? And if this is derived, Given 4 bits for representing negative and positive numbers, what is the largest positive number that can be represented?

Each bit can be either 0 or 1, so you have two choices per bit. That gives you 2^n combinations. E.g. n=1 implies 2^1=2 states, n=2 implies 2^2=4 states. You could arrive at this by 1) making a lexicographic list of all the combinations or 2) using a formula from combinatorics.

Your second question seems to address representing integers with binary numbers. You must first settle on an encoding scheme before that question can be answered. A popular encoding scheme is two's complement. The maximum positive integer represented in 4-bit two's complement is 0111, which is 7.


Turing machine state transition diagram vs finite state machine state transition diagram If you were given a state transition diagram could you tell, just by looking at the diagram, if the diagram represented a DTM or a DFA (especially if it was unlabeled, just a directed graph)? Would there be any difference between the diagram representing the deterministic Turing machine and the diagram representing the deterministic finite automata, or is the difference between them in the context that surrounds the diagram and in the labeling ie. one can read and write to the tape while the other can only read?

Summary : you may still be able to tell them apart , but not necessarily
First refere to the formal definition to a Turing machine from Wikipedia
Now consider the transition function δ :

First , δ does not allow transitions from accepting states , so in a state diagram of a TM you expect some state to have no transitions from it , unlike a DFA where every state must have transitions out of it , other definitions of TMs allow transitions from final states , but have accept/reject states taking effect immediately , and so you don't expect these states to have transitions

δ is a partial function , thus you don't need to define a transition for each state and each symbol , unlike DFAs which require a transition from each on each symbol (refer to Wikipedia under complete and incomplete) , so in a DFA you have all states having equal number of transitions/arrows from them but not necessarily in a Turing machine

Arguments :

1 would be nullified if TM and DFA have no final states to begin with
2 can also be nullified should we choose to provide transition from all states on all symbols for a TM , or go for the less common alternative definition for the DFA in Wikipedia and then not all states need to have equal number of transitions


Is it possble to store a counter that could reach $\lfloor \frac{N}{x}\rfloor$ using $\lceil\log_2(N+1)\rceil$ - $\lfloor\log_2 x\rfloor$ bits? Let $x,N$ be positive integers.

I'd like to store a counter which could reach value of $\left\lfloor \frac{N}{x}\right\rfloor$ (i.e. could take any value in $0,1,\ldots,\frac{N}{x}$) using  $$\lceil\log_2(N+1)\rceil - \lfloor\log_2 x\rfloor$$

bits.

Equivalently, does the following hold:
$$\log\left\lfloor \frac{N}{x} + 1\right\rfloor \leq \lceil\log_2(N+1)\rceil - \lfloor\log_2 x\rfloor$$

Obviously, this holds for $x=1$, what about general $x$?

This is indeed possible.

First, notice that for storing $\left\lfloor\frac{N}{x}+1\right\rfloor$ values ($0,1,2,\ldots,\left\lfloor\frac{N}{x}\right\rfloor$), you need $\left\lceil\log\left\lfloor\frac{N}{x}+1\right\rfloor\right\rceil$ bits (which might be larger than $\log\left\lfloor\frac{N}{x}+1\right\rfloor$). This won't stop us though :).

We first notice that for every $$\forall 1<x,N\in\mathbb N:\left\lfloor\frac{N}{x}+1\right\rfloor\leq\left\lceil\frac{N+1}{x}\right\rceil$$
To see this, consider the case where $\frac{N}{x}\in \mathbb N$, and thus $$\left\lfloor\frac{N}{x}+1\right\rfloor = \frac{N}{x}+1=\frac{N}{x}+\left\lceil\frac{1}{x}\right\rceil=\left\lceil\frac{N+1}{x}\right\rceil$$ Otherwise, when $\frac{N}{x}\not \in \mathbb N$:$$\left\lfloor\frac{N}{x}+1\right\rfloor =\left\lceil\frac{N}{x}\right\rceil\leq\left\lceil\frac{N+1}{x}\right\rceil$$

Another useful inequality is $\forall r\geq 1:\log\left\lceil r\right\rceil\leq\left\lceil\log r\right\rceil$.

To see this, let $k\in \mathbb N$ such that $2^{k-1}<r\leq2^{k}$.

Now $k-1<\log r\leq k$, and therefore $\left\lceil\log r\right\rceil =k$. Now $\log\left\lceil r\right\rceil\leq k=\left\lceil\log r\right\rceil$.

Finally, we conclude that:
$$\left\lceil\log\left\lfloor\frac{N}{x}+1\right\rfloor\right\rceil\leq\left\lceil\log\left\lceil\frac{N+1}{x}\right\rceil\right\rceil\leq\left\lceil\left\lceil\log\frac{N+1}{x}\right\rceil\right\rceil$$
$$=\left\lceil\log(N+1)-\log(x)\right\rceil$$
$$\leq\left\lceil\log(N+1)\right\rceil-\left\lfloor\log(x)\right\rfloor$$


Create a DFA and a NFA where the word includes (two) consecutive zeroes I have chosen an example task to see if I understood DFA and NFA correctly.

So let's say we have that task:

  Given alphabet $\Sigma = \{0,1\}$ and the language $L = \{w \mid w \text{ includes two consecutive zeroes}\}$. Create a DFA and a NFA for the language with as
  less as possible states.

The following description is just a rough one (there are much more attitudes a DFA / NFA has). Please tell me if it's correct anyway because these are the ones I'm not sure about.

For this example, each state of the DFA needs at least two outgoing arrows. So each state needs at least one outgoing arrow $0$ and one outgoing arrow $1$ because we have $\Sigma = \{0,1\}$. We do not really need to care about incoming arrows, there can be any number of incoming arrows.

For the NFA, however, we do not need to care how many outgoing / incoming arrows we use for each state.

So here I made a DFA and a NFA where the words include two consecutive zeroes. Did I do it correctly?

The difference of DFA and NFA is in the transition map (or "outgoing arrows" as you describe) and has nothing to do with "incoming arrows". Namely, if $\Sigma$ is the input alphabet then the transition function of the DFA must be uniquely defined for each state and input symbol pair

$$\delta(q,a) = p, \text { for } q,p \in Q, a\in \Sigma$$

In case of the NFA the transition function maps each pair $(q,a)$ to a subset of states $Q$
$$\delta(q,a) = Q' = \{p_1, p_2, \dots, p_n\}, \text { for } Q' \subseteq Q, a\in \Sigma$$

In simply words, for DFA for each input symbol a state must have exactly one outgoing arrow, but in the case NFA for each input symbol a state may have more than one outgoing arrows or no outgoing arrow.

In your example $\Sigma=\{0,1\}$ and thus the DFA must have exactly two outgoing arrows for each state, but the NFA may have no outgoing arrow or up to $|Q|$ outgoing arrows.


Is it possible for a maximum weight edge of a cycle being included in MST? Let C be a cycle in a simple connected weighted undirected graph. Let "e" be an edge of maximum weight on C
Which of the following is TRUE?

(A) No minimum weight spanning tree contains e.
(B) There exists a minimum-weight spanning tree not containing e.
(C) no shortest path, between any two vertices, can contain e.
(D) None

This was a question for which I gave the answer A because I thought using Kruskal's algo & since the maximum weight edge is lying on the cycle, we will always have an opportunity to select an edge with lesser weight.

The answer to the question in the title, "is it possible for a maximum weight edge of a cycle being included in MST?", is "not necessarily".

The correct answer to the multiple-choice question is (B).

A counterexample to (A): Let $G$ be an triangle with weight $1$, $1$ and $1$. Let $e$ be any edge of $G$.

The answer by raindrop says (A) is correct. However, he/she also points out that "A possible exception is if multiple edges have the same maximum weight, e.g. there are multiple maximum edges on $C$ which qualify to be labeled $e$. In that case, a minimum weight spanning tree may contain $e$". Let me repeat the condition about $e$ in OP's post is Let "$e$" be an edge of maximum weight on $C$. The article "an" in "an edge" does indicate that possibility. Since we are in math or computer science, one counterexample or one exception is enough to prove the fallacy of a statement.

Proof of (B): Let $m$ be an MST of $G$. If $e$ is not in $m$, we are done. Now suppose $e$ is in $m$. If we remove $e$ from $m$ (but do not remove $e$'s vertices), $m$ will be split into two trees, which we name $m_1$ and $m_2$. As a cycle that connect $m_1$ and $m_2$ by $e$, $C$ must also connect $m_1$ and $m_2$ at another edge, which we name $e'$. Then $m_1$ together with $m_2$ and $e'$ is an MST of $G$ that does not contain $e$.

A counterexample to (C): Let $G$ be an triangle with weight 1, 1 and 1. Let $e$ be any edge of $G$. The shortest path between $e$'s two vertices contains one edge, $e$ itself.

(D) is wrong since (B) is correct.


Help with Linear recurrence relation with balanced partition In my slides for my algorithms class, I have a method of finding complexity of recursive functions called Recurrence Relation with "partizione bilanciata" which means "balanced partition".

My course is in Italian and looking online in English I could not find any trace of this method, I know of the recursive tree, induction and master theorem.

Has anyone an idea of how this is called in English? I don't like studying in Italian and I do not understand those pdfs.

I'm attaching some images of the formulas.

What exactly "balanced partition" mean, does it have something to do with for example Quick Sort, when you choose a middle pivot and the partitions are equal in size, which means it's balanced ?

Is it the same as master theorem written maybe in a different way?
I can see the form of the recurrence relation is different than the master theorem:

The master theorem has $f(n)$ instead of $cn^\beta$.

Looks like I learned it by myself in a different way than my teacher teaches it, and that is why I never heard of "balanced partition".

Apparently it means that a problem is divided in more sub problems (kind of like quick sort as I said), and when we have this condition where T(n/b) and b>=2, we use the "balanced partition" method.

I learned it in a different way, by getting Theta as f(n) and looking for p and k, where Theta(n^k * log^p(n)) , after that I have different cases, like in the following picture, my teacher teaches in a different way and that is why i got confused, because in English there is no "balanced partition" therm.


What is the metadata in microblogging platform? I'm reading papers regarding microblog credibility perception of non-text cues.

Tweeting is believing? Understanding microblog credibility perceptions
by Morris et al., 2012
Microblog Credibility Perceptions: Comparing the United States and China
by Yang et al., 2013

However, Yang et al.[2013] refer to some cues, such as location, number of followers, is a reply as metadata. Metadata is defined as 'data about data', but such cues seem normal data to me.

Examples of cues mentioned:

author location
contains URL
number of followers
is a retweet

Now I'm confused what exactly does metadata include in microblogs, and what is the difference between metadata and normal data in microblogs.

For example:
the number of followers - it's a non-text data. But is it a data or metadata?

Metadata is an infamously ill-defined term.  Roughly speaking, it's trying to get at a distinction along the following lines: data is the "content" you care about; metadata is other information that is secondary or exists primarily for technical reasons (e.g., addressing information, tags, technical data to facilitate storage or communication).

A classical analogy is postal mail.  The contents of the letter is considered "data".  The addresses on the envelope might be considered "metadata".

Of course, it's just bits, so at some level it's all data.  But when we talk about the data/metadata distinction, we're usually trying to draw a distinction between the main content that users care about, vs secondary information used to enable the system to work.

Again, the term "metadata" is vague, ambiguous, and ill-defined.  Don't expect a precise technical definition of the term.  Instead, if you plan to use this term in communication  and its precise meaning is important, then make sure to state clearly what you mean by metadata and what you do/don't consider to be metadata.

See also https://freedom-to-tinker.com/2008/10/20/what-your-mailman-knows-part-1-2/ and https://freedom-to-tinker.com/2008/10/23/abandoning-envelope-analogy-what-your-mailman-knows-part-2/ for discussion about the use of the term "metadata" in the  privacy context.


Worst run-time for 3 nested loop Suppose we need to find a tight asymptotic bound on the worst case run time of the following program

t = 0;
for i = 0 to n-1 do
  for j = i+1 to n-1 do
    for k = j+1 to n-1 do
      t++;

I can't for the life of me figure out what the run-time would be. I have a feeling it would have n! in there somewhere, but I can't seem to wrap my head around it. All help is appreciated

I suggest you slightly modify your program, as follows:

int i, j, k, t = 0;
for (i = 0; i <= n - 1; i++)
  for (j = i + 1; j <= n - 1; j++)
    for (k = j + 1; k <= n - 1; k++)
      t++;

Now run this program for various values of $n$ and print the corresponding values of $t$, which is your runtime $T(n)$. Make a guess at the growth rate of $T(n)$ based on this. Try to prove your guess.

Another idea is to try to understand what happens when you have only one loop, then two nested loops, and then all three nested loops. The first case in particular is pretty easy.


Prove the languages |L| = 2 and |L| $\not=$ 2 to be non-Turing recognizable or non-recursively enumerable I am trying to prove the non-recursively enumerable property of two languages.

$L_2 = \{\langle M \rangle: |L\langle M \rangle| = 2\}$ and
$L_{\not=2} = \{\langle M \rangle: |L\langle M \rangle| \not= 2\}$.

My idea is to use the following two properties:

If A $\leq_m$ B and A is not Turing recognizable then B is not Turing-recognizable.
A $\leq_m$ B if and only if $A^c \leq_m B^c$.

For language $L_{2}$,
If I can show that $A_{TM}$ is mapping reducible to $L_{\not=2}$, according to property 2 we could get that $\overline{A_{TM}}$(the complement of $A_{TM}$) is mapping reducible to $L_{2}$, and for the fact that $\overline{A_{TM}}$ is not Turing recognizable, we could get that $L_{=2}$ is not Turing recognizable.

For language $L_{\not=2}$,
If I can show that $\overline{A_{TM}}$ is also mapping reducible to $L_{\not=2}$, and for the fact that $\overline{A_{TM}}$ is not Turing recognizable, we could get that $L_{\not=2}$ is not Turing recognizable.

However, I don't know how to prove the mapping reducible relationships between them. Or my direction could be totally wrong.

Could somebody give me the hints or possible solutions?

If I can show that $A_{TM}$ is mapping reducible to $L_{=2}$, ...

That is a nice idea. Given $\langle M, w \rangle$, can you construct a TM $M_1$ that accepts only one word, the word $w$ if and only if $M$ accepts $w$?

Then, can you change $M_1$ so that it accepts another word that is different from $w$?

You can also show that $A_{TM}$ is mapping reducible to $L_{\not=2}$ by creating a TM $M_3$ which accepts 2 words if $M$ does not accepts $w$ and 3 words otherwise.


What are Markov chains? I'm currently reading some papers about Markov chain lumping and I'm failing to see the difference between a Markov chain and a plain directed weighted graph.

For example in the article Optimal state-space lumping in Markov chains they provide the following definition of a CTMC (continuous time Markov chain):

  We consider a finite CTMC $(\mathcal{S}, Q)$ with state space
  $\mathcal{S} = \{x_1, x_2, \ldots, x_n\}$ by a transition rate matrix
  $Q: \mathcal{S} \times \mathcal{S} \to \mathbb{R}^+$.

They don't mention the Markov property at all, and, in fact, if the weight on the edges represents a probability I believe the Markov property trivially holds since the probability depends only on the current state of the chain and not the path that lead to it.

In an other article On Relational Properties of Lumpability Markov chains are defined similarly:

  A Markov chain $M$ will be represented as a triplet $(S, P, \pi)$
  where $S$ is the finite set of states of $M$, $P$ the transition
  probability matrix indicating the probability of getting from one
  state to another, and $\pi$ is the initial probability distribution
  representing the likelyhood for the system to start in a certain
  state.

Again, no mention of past or future or independence.

There's a third paper Simple O(m logn) Time Markov Chain Lumping where they not only never state that the weights on the edges are probabilities, but they even say:

  In many applications, the values $W(s, s')$ are non-negative. We do
  not make this assumption, however, because there are also applications
  where $W(s, s)$ is deliberately chosen as $-W(s, S \setminus \{s\})$,
  making it usually negative.

Moreover, it's stated that lumping should be a way to reduce the number of states while maintaining the Markov property (by aggregating "equivalent" state into a bigger state). Yet, to me, it looks like it's simply summing probabilities and it shouldn't even guarantee that the resulting peobabilities of the transitions to/from the aggregated states are in the range $[0,1]$. What does the lumping actually preserve then?

So, there are two possibilities that I see:

I didn't understand what a Markov chain is, or
The use of the term Markov chain in those papers is bogus

Could someone clarify the situation?

It really looks like there are different communities using that term and they mean widely different things. From these 3 articles that I'm considering it looks like the Markov property is either trivial or useless, while looking at a different kind of papers it looks fundamental.

A Continuous-time Markov Chain can be represented as a directed graph with constant non-negative edge weights.  An equivalent representation of the constant edge-weights of a directed graph with $N$ nodes is as an $N \times N$ matrix.  The Markov property (that the future states depend only on the current state) is implicit in the constant edge weights (or constant entries in the matrix).  Implicit means implied by.  Mathematicians use it as a euphemism meaning, "you should prove it yourself."

But the first paper defines a notation consistent with a Continuous-time Markov Chain, sometimes called a Markov Process, while the second paper defines a notation consistent with a Discrete-time Markov Chain.  They say

  $P$ is the transition probability matrix indicating the probability of getting from one state to another, and $\pi$ is the initial probability distribution representing the likelihood for the system to start in a certain state. [emphasis added]

They are assuming that the matrix is constant over time (thus implying the Markov property).  Implicit in the term probability is the fact that each constant is in range $[0,1]$, that the entries in every column of $P$ sum to $1$, and that the sum of the entries in $\pi$ sum to $1$.

I can't read the third paper, it is paywalled.  If the entries in every column of the matrix are required to sum to 1 then they are probabilities and they are talking about Discrete-time Markov Chains.  If the entries in every column can sum to an arbitrary number then the entries represent rates not probabilities and they are talking about Continuous-time Markov Chains.

Continuous-time Markov Chains are not the same as Discrete-time Markov Chains.  In a Continuous-time Markov Chain the edge weights do not represent probabilities, but rather transition rates.  The edge weights must be non-negative, but can be arbitrarily large, and the weights of the out-edges can sum to any non-negative number.  The sum is not required to be $1$.

With both Continous-time and Discrete-time Markov Chains the Markov property is implied by the constant edge weights (or equivalently the constant entries in the transition matrix.)


Why does the proof of undecidability of $A_{TM}$ require the universal TM to take input $\langle M,\langle M\rangle\rangle$? I've read a proof explaining why $A_{\mathrm{TM}}$ is undecidable, and I don't seem to understand why we need to give the opposite of $H$ function $D$ itself as input.

Here's the copy-paste of that proof (link: https://courses.cs.washington.edu/courses/cse322/04au/Lect10.pdf):

$A_{\mathrm{TM}} = \{\langle M,w\rangle\mid M\text{ is a TM that accepts }w\}$ is
undecidable! Proof (by contradiction):

Assume $A_{\mathrm{TM}}$ is decidable  there’s a decider $H$, $L(H)$ = $A_{\mathrm{TM}}$.
$H$ on $\langle M,w\rangle = \mathrm{ACC}$ if $M$ accepts $w$
$\mathrm{REJ}$ if $M$ rejects $w$ (halts in $q_{\mathrm{REJ}}$
or loops on $w$).
Construct new TM $D$: On input $\langle M\rangle$:
Simulate $H$ on $\langle M,\langle M\rangle\rangle$ (here, $w = \langle M\rangle$).
If $H$ accepts, then reject input $\langle M\rangle$;
If $H$ rejects, then accept input $\langle M\rangle$.
What happens when $D$ gets $\langle D\rangle$ as input?
$D$ rejects $\langle D\rangle$ if $H$ accepts $\langle D,\langle D\rangle\rangle$ if $D$ accepts $\langle D\rangle$;
$D$ accepts $\langle D\rangle$ if $H$ rejects $\langle D,\langle D\rangle\rangle$ if $D$ rejects $\langle D\rangle$.
Either way: Contradiction! $D$ cannot exist, so $H$ cannot exist.
Therefore, $A_{\mathrm{TM}}$ is not a decidable language.

So, I don't understand why we need to give $H$ the input of $\langle D,\langle D\rangle\rangle$, why not give it the input of $\langle D,w\rangle$? And give $D$ the same input, isn't that the same thing? Or what's the logic behind the second $\langle D\rangle$? For some reason it's very confusing for me. Thanks.

Why not give it the input of $\langle D,w\rangle$?

What's $w$? The machine $D$ is given some input, which it interprets as the coding of a Turing machine $M$. It's not given any $w$: only $\langle M\rangle$.

Imagine instead that you're given a function $f$ which is defined as $f(x)=x^x$. I ask you to calculate $f(10)$ and your question is a bit like asking, "Why does it have to be $10^{10}$?  Why can't it be $10^y$?"


Computational complexity lecture/videos/exercise I have basic background (at the level of Sipser's book),
but am looking to brush it up and get to the more advanced part via self-study.
I have two Computational Complexity books (Arora and Barak and Papadimitriou's).

I am looking for good lectures (online), exercises etc., possibly coursera style,
for a faster progress with the material.
Any recommendations would be greatly appreciated.

Thanks

Coursera has materials on Automata by Ullman. You can always "preview" that material. Also for a more complete reference on a first course, may I suggest Gusfield's Lectures (available in iTunesU)

For more advanced treatment, Tim Gowers has few online lectures on Computational Complexity and Quantum Computation

Also, the AB book is really good. you may want to stick with that.

If you want more advanced materials, looking into the proceedings of STOC or FOCS from the previous years, might be insightful.


Choosing which workers (limited number) to use in a binary assignment problem? First of all, I am not completely sure whether this problem belong to the category of assignment problems so feel free to correct me in this case.

The problem:

We are given a set of $m$ workers $A = \{ a_1, a_2,...a_m \}$ and a set of $n$ tasks $T = \{ t_1, t_2,...,t_n \}$. Each worker either can or cannot perform any given task and there is no cost associated with a task. The set of tasks that can be performed by a single worker $a_i$ is $T_{a_i} \subset T$. The set of tasks that can be performed by a subset of $s$ workers is given by the union of the tasks each individual worker can perform $\bigcup_{i=1}^{s} T_{a_i}$ (not necessarily the first $s$ workers).

The problem is to select $s$ workers such that the number of task that can be performed is maximized, i.e. maximize the number of elements in $\bigcup_{i=1}^{s} T_{a_i}$.

I couldn't find which category of problems this belong to, let alone any solutions. Any help in this matter would be greatly appreciated!

Your problem is known as maximum coverage.


How to apply the pumping lemma for CFGs to languages that contain the empty string The pumping lemma states that if we can split a string w (taken from a context-free language L) as uvxyz with conditions |vy|>=1 |vxy|<=p |w|>=p for some p then $uv^ixy^iz$ is in L for any i.

However, some context-free languages include the empty string, which has length 0. How can we possibly split the empty string to satisfy the condition |vy|>=1?

For instance, the following language $\{0^n1^n0^n1^n|n>=0 \} $ contains the empty string but is not context-free, so how can I ensure a string taken from it can we split as uvxyz with |vy|>=1?

Thanks!

The pumping lemma requires the word $w$ you start with to be large enough — larger than the pumping lemma constant $p$.

However, this doesn't really answer your question, which is how to ensure that the string given to the pumping lemma is not empty. Here you are very lucky — you are the one choosing the string! The pumping lemma only states that whatever string $w$ you choose from the language (as long as it is long enough), it can be decomposed as $w = uvxyz$ so that $uv^ixy^iz$ is in the language for all $i \geq 0$, $vy \neq \epsilon$, and $|vxy| \leq p$.


MAX-2-XOR-SAT: Why does the special case work? I'm a new user so I cannot respond directly to this post here.

I'm confused about the answers to the question, namely that MAX-2-XOR-SAT is in $P$ iff each clause is of the form $(x_i \oplus \neg x_j)$ (or is it $(x_i \oplus x_j)$? There were two different answers). Couldn't you make a simple substitution $\neg x_i \rightarrow y_i$ such that this is always the case, so that you can get the special case always? For example, you could convert, $(x_1 \oplus \neg x_2) \wedge (x_1 \oplus x_3)$, to $(x_1 \oplus y_2) \wedge (x_1 \oplus x_3)$.

Forgive me if there is something obvious I am missing...I'm new to this field.

Thank you!

EDIT

To clear up confusion, I'm asking if a substitution is made for all clauses with a matching variable. Take for example,

$$(x_1 \oplus x_2) \land (\neg x_1) \land (x_1 \oplus \neg x_3)$$

By substituting $\neg x_3 \rightarrow y_3$ we get:

$$(x_1 \oplus x_2) \land (\neg x_1) \land (x_1 \oplus y_3)$$

Where each 2-clause is of the form $(x_i \oplus x_j)$. It seems that in this case it still remains in $P$. Which raises a new question, how do single clauses affect the complexity of the solution?

No, you can't make a substitution like that.  The resulting formula isn't equivalent to the original formula.

Consider

$$(x_1 \oplus x_2) \land (x_1 \oplus \neg x_2).$$

This formula is not satisfiable.  However, if we apply your substitution, we end up with the formula

$$(x_1 \oplus x_2) \land (x_1 \oplus y_2).$$

The resulting formula now has 6 variables and is satisfiable.  For example, you can set $x_1=\text{True}$, $x_2=\text{False}$, $y_2=\text{False}$.

The problem is that your substitution doesn't ensure that $y_i = \neg x_i$, so it doesn't preserve satisfiability.  (If you wanted to preserve satisfiability, you could do that by making your substitution and then adding clauses of the form $(y_i \oplus x_i)$ ... but while that would preserve satisfiability, it wouldn't preserve the maximum number of clauses that can be simultaneously satisfied, so it still wouldn't help for solving MAX-2-XOR-SAT.)


Can agent be autonomous without having consciousness? My intuition is that 1) self-awareness (modeled through epistemic modal logics); 2) goal reasoning (e.g. https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12292) and 3) consciousness (e.g. Integrated Information Theory) are the necessary and sufficient features for agent to be truly autonomous. Especially - consciousness is the key feature of autonomy. So - can truly autonomous (human-level autonomy) agent exist without consciousness?

Of course, I am thinking about autonomy not ultimate freedom. E.g. every agent can be autonomous but it will be bounded by 1) scarcity of resources; 2) ultimate goals and values which will be inscribed into agent by the humans.

Here is a glimpse.

Concerning agents you're trying to elaborate here,I would like to give you some insights of these following key aspects,which might help in your future research nor knowledge;

Consciousness
Here an agent is capable of understanding its own existence nor selfawareness.
Intelligence
An agent is capable solving problem based reasoning with no help from third-party knowledge.
Autonomous
An agent has the ability to solve problems basing on the third-party knowledge for instance,self driving car does its own problem solving basing on the existing knowledge it discovers from the environment.

  Therefore,for any agent to be autonomous,it doesn't mean its selfaware
  or conscious,otherwise. For your information,do further reading on the
  above three terminologies.