Here are some questions (with my answers) about Problem Set 2:

> RE question 1 part a:
> a)Must the elements of D be integers?  If so, then D must have exactly 2
> non-zero elements in order for DR=0, otherwise DR will never be 0.
> Please correct me if I am wrong, but tell me if I am right.

the elements of D don't have to be integer. If you decide that DR can
never be zero, then in that case Pr[DR=0]=0.

> RE question 1 part b;
> a)  Does the condition on D apply to  this part of the question too?

again, elements of D don't have to be integers (the can be rationals), but
this is not important for the question.

> RE question 1 part c:
> a) I am little confused about Frievald's Technique!  When elements of R
> are randomly chosen from a finite set S, is it better for S to contain 0
> or not to contain 0?  Is it better for S to have only 2 elements or more
> than 2 elements?  Schwartz-Zippel Thm suggests that a larger set is
> better according to my understanding.  Please correct me if I am wrong?

a set S with more elements is better -- 0 doesn't have to be one of them.

> RE question 3:
> a) Is the size of the input for PM(G) the number of edges in G or the
> number of nodes in G (in binary?) ?

the size of G, written |G|, is O(n^2), where n=number of nodes in G, since
by convention G is presented as an adjacency matrix, i.e. a matrix with 
n rows and n columns where the (i,j)-th entry is 1 if (i,j) is an edge in
G, and it is zero otherwise. This is not important for the question, just 
remember that the input size is O(n^2).

> b) May we order the edges of G or group the edges of G? This may be a
> crucial point - I don't know.

They don't have to be in a specific order for the algorithm that I have in
mind.

> RE question 5:
> a) if x is an initial segment of y, then if y=01101 and x=0, then R(x,y)
> = true?

Yes

> b) I am confused as to how x and y appear on the tape: does x appear
> first or y? How many blanks separate x and y? Does the length of x equal
> the length of y?

You can decide the input conventions. For example, you could present <x,y>
as the bits of x, followed by a blank (i.e. by 'b'), followed by the bits
of y. Make sure that your TM takes appropriate steps when y=empty string,
in which case all the squares after x contains b's.

> c) Can you give any hints as to how the TM remembers what it sees?

You can always "remember" by entering states. For example, when you read a
0, and you want to remember that you read a 0, you can enter a state p_0.
If you read a 001, and you want to remember that, you can enter a state
p_001, and so on.

> d)Are we allowed to introduce another symbol for overwriting (instead of
> overwriting with blank symbol b)  so that we know when we are finished
> scanning x because eventually all the symbols of x will be overwritten
> with b's , but then we won't know when to stop looking for x?

Yes, you can design you TM to have any finite set of symbols and states.