Addendum

[Ishaan Joshi]

There are certain problems out there on the internet, regarding the GRE, which seem to have no corresponding solutions, can we use this group to discuss such problem online, time permitting. I will pose a question :

Given a complete graph with n nodes, how many unique paths exist from node x to node y, given that x ! = y ?
let the fun begin.

cheers,

..i[j]
--
What is freedom of expression? Without the freedom to offend, it ceases to exist. - Salman Rushdie

[habiba]

I think it should be = to no. of spanning trees in a complete graph of n nodes. Since each tree will have a unique path from each node to the other so, the number of spanning tree should give the possible number of paths. which for the n node complete graph is n^(n-2).

I will ask around too to confirm. But just thought to throw in the idea.
Habiba
 

[habiba]

i m still struggling with the question and figured out that each of the n spanning trees will have the same path between x & y repeated to i guess it should be n^(n-3) unique paths between x & y nodes. Were there any answer choices available with the question?

[Ishaan Joshi]

Habiba,

  I think this problem can be split as follows :

      Total # paths from x->y = paths with no hop + paths with 1 hop +......+ paths with n-2 hops
                                        = 1 + (n-2) + (n-2)(n-3) + ...+ (n-2)(n-3)..(1)
                                        = = 1 + (n-2) + (n-2)(n-3) + ...+ (n-2)!

  Does anyone know the summation of this value ?
  I just saw the question, not aware of the choices.

cheers,

..i[j]

[AsH]

Ishaan,

I think you've got the answer...though I don't know a formula for that
summation.
So you've got:
1 + (n-2) + (n-2)(n-3) + ... + (n-2)!

Say k = (n-2), so you have:
1 + k + k(k-1) + k(k-1)(k-2) + ... + k!

Divide by k!:

1/k! + 1/(k-1)! + 1/(k-2)! + ... + 1/2! + 1

So we have:
Sum (i=1 to k) of 1/i!

Now there must be a formula for that...I'm going to hunt for it. Does
that look right??

Anushka

p.s: That link you posted before is great.
I hope everyone's studying is going well :P 10 more days!

[AsH]

Having floors/ceilings in formulas confuses me so I hope someone can
tell me how to find the order of growth of the following:

T(n) = T(floor(n/2)) + T(floor(n/4)) + cn

I don't know the solution for this either.

Thanks,
Anushka

[Arun]

I think the solution for this may be theta(n).

Drawing the recurrence tree:
1st level cost: cn
2nd level cost: 3cn/4
3rd level cost: 9cn/16

So, running time is cn + 3cn/4 + 9cn/16 + ..... + etc...

Fraction is monotonically decreasing, so running time will be the
largest term: theta(n).

There is a visual illustration of a similar tree in CLR that I just
saw yesterday.

- Arun

[Ishaan Joshi]

As far as I know, there is implicit rounding in recurrences.
For e.g : T(n/b) is actually T (floor(n/b)), so don't worry if such a thing is mentioned.
             Will a floor instead is a ceil make a difference ?

Your summation foe the unique paths problem is right.

[Anushka]

ok...here's factorial sums:
http://mathworld.wolfram.com/FactorialSums.html

so now what's the answer?

[Ishaan Joshi]

I don't know the answer, but I guess the closest is the one which you gave :
   (k)! * (sum(0 to k)1/k!)
   where k = n-2

I just thought this problem is illustrative of a lot of counting problems.
I will post a few more later in the day.

Do we need to do LL/LR/LALR grammars and their derivations ?

cheers !

[Ishaan Joshi]

Few Questions :

L is an undecidable language (i.e. not recursive). Which of the following statements are correct.

I. L is infinte.
II. L contains a recursive language.
III. L' is undecidable.

a) I only b) I and II c) I and III d) II and III
e) I,II,III


NEXT


47. Let M be a single-tape, deterministic Turing machine with tape alphabet {blank, 0, 1}, and let C denote the (possibly infinite) computation of M starting with a blank tape. The input to each problem below is M, together with a positive integer n. Which of the following problems is (are) decidable?
I. The computation C lasts for at least n steps.
II. The computation C lasts for at least n steps, and M prints a 1 at some point after nth step.
III. M scans at least n distinct tape squares during the computation C.

(A) None (B) III only (C) I and II only (D) I and III only (E) I, II, and III

[habiba]

for the first problem, i think its (b) since its undecidable, so its not accepted by a turing machine and all finite languages are accepted by a TM so L shud be infinite. and 2 is i think right too since recursive is contained in RE. 3rd isnt correct because if a language and its complement are both undecidable then actually they are recursive and not RE. (does it make sense?)

the 2nd quesiton:
my guess is (D) ...i guess i did see this question in some paper.

In the 1st option, we are concerned with only n steps so once the n steps are over we are done. And so is the 3rd. In the 2nd TM can go & on and we never know when is 1 printed.

[Ishaan Joshi]

yep, that's right

L has to be infinite,
L' is definitely undecidable, if it were decidable, then we could just swap accept/reject and make L decidable.
As far as option II, well, I think it asks you whether some subset of L is regular, as in, L constitutes a set of words, is some subset regular ? I think thats easy, anyways.

Second question.. you're right again.

Here are a few more :


S -> A | B
A -> 0B1 | 0
B -> 1A0 | 0
what's true about the language?
I. context-free
II. regular
III. infinite


* I think the answer should be I & III

__________________________________


What is the min number of states required for
converting ANY NFA with N
states to a DFA:
A. N B. N^2 C. 2^N D. 2N E. N!

* A ?

___________________________________

 In a packet delivery system, a packet is
retransmitted when lost, till it
is successfully transmitted. If the probability of
loss is C, and
retransmissions are independent, what is the expected
number of unsuccessful
transmission before a successful transmission:

A. 1/(1-C) B. C/(1-C) C. 1/(1-C)^2 D. C E. 1-C

* B ?



:)


cheers,


..i[j]

[habiba]

Ishan,

For the grammar question, i think I & III are correct. But does anyone has any idea of a quick way to see why this language is not regular. I mean what i understand is that a regular language can be represented as context free, right????? so for a question like this , one can do the a more than 3 minutee for first analyzing the grammar then somehow working out whether u can make DFA/NFA for it etc. which i think is not a quick way to solve this problem. So are there are obvious signs to look for to establish this language is not regular. 

 

2. it is N. 

3.  i think it A 1/(1-C). 

why? because .... C = prob.unsuccessfull transmission  => 1-C = prob. of success. 

So Pr( successfull transmission in the 1 attempt) = 1-C

Pr( successfull transmission in the 2 attempts) = 2*C*(1-C)  

Pr( successfull transmission in the 3 attempts) = 3*C^2*(1-C)

.........

Pr( successfull transmission in the k attempts) = k*C^(k-1)*(1-C)  
  

Now, this can go on to infinity. So we have to sum this series for k 1 to infinity

Summation (1-inifinity) k*C^(k-1)*(1-C) =  (1-C)*Summation (1-inifinity) k*C^(k-1)

=  (1-C)/C*Summation (1-inifinity) k*C^k
This summation part  has a neat sum in calculus , which is C/(1-C)^2

so  now we have,
=  ((1-C)/C)* (C/(1-C)^2)  = 1/(1-C)
............so that makes it the choice A.

I think this is how it shud be, since i saw an almost similar example in a discrete book. But i could be overlooking something.

& plz plz if some one knows an easier way of doing this...do share. This doesnt seem so simple if u have atmost 3 minutes to read understand and solve a question.
 

 

Habiba :)

[Arun]

Given an NFA with N states, I think the equivalent DFA will have 2^N
states. So, the answer is C. See page 55 of Sipser 2nd ed.

- Arun

> > On 04/04/07, habiba <habi...@gmail.com> wrote:
>
> > > for the first problem, i think its (b) since its undecidable, so its not
> > > accepted by a turing machine and all finite languages are accepted by a TM
> > > so L shud be infinite. and 2 is i think right too since recursive is
> > > contained in RE. 3rd isnt correct because if a language and its complement
> > > are both undecidable then actually they are recursive and not RE. (does it
> > > make sense?)
> > > the 2nd quesiton:
> > > my guess is (D) ...i guess i did see this question in some paper.
> > > In the 1st option, we are concerned with only n steps so once the n
> > > steps are over we are done. And so is the 3rd. In the 2nd TM can go & on and
> > > we never know when is 1 printed.
>

[habiba]

Got that,

what i got confused with is that u wud need atleast N states to convert and NFA to DFA , meaning you cannot have any lesser, so that seemed like what the question is asking, and 2^N is the maximum, there would never be any more than that states for converting NFA to DFA. Also, 2^N is a crude upper bound, since it actually counts all possible subsets os N states, but there are many subsets which are not accessible from the start state so the gets thrown away and the resulting DFA is much smaller that 2^N.

But since the question asks for "minimum" in ANY NFA to DFA conversion, so i think you are right it should be 2^N.  N would be the minimum but for some specific NFAs.

Habiba

[habiba]

I am sorry ignore the explanation i gave in the last mail. I think it was confusing...

This is the text from Ullman book (verbatim)

",,,,the DFA in practice has about as many states as an NFA, although it often has more transitions. In the worst case, however, the smallest DFA can have 2^N states while the smallest NFA for the same language has only N states."

 

[Ishaan Joshi]

So I guess the answer is N right ?
Since we're asked the number of states of the "minimal" DFA that can be constructed from an NFA with N states.

ALso, thanks for the connected component explanation !

I'll send a few more questions :)

cheerio,


..i[j]