driller for theory

[wood]

Indeed. CFG intersect CFG does not necessarily lead to a CFG. However, CFG intersect regular language = CFG.

Wood

[AlbaLed]

What about CFL intersect Reg. Lang, and CFL intersect CFG?

[AlbaLed]

Q15) On average, how many exchanges are performed by insertion sort on n elements? How about selection sort? How about bubble sort?

According to Sedgewick (and I’m not sure I trust the answer for bubble)
Bubble: O(n*n/2)

Nonevent here is what I get for bubble, maybe you can trust me, forget Sedgewick

elements in bubble (smallest elem on top)
x
x1

probability of that x1 will bubble over x is 1/2

x
x1
x2
x3

probability of that x1 will bubble over x is 1/2, 
probability that x2 will bubble 1 spot  = 1/2, (if x2 < x1, x2 bubles 1 spot)
probability that x2 will bubble 2 spots = 1/2, (if x2 < x,  x2 bubles 2 spots)
probability that x3 will bubble 1 spot  = 1/2, (if x3 < x2, x3 bubles 1 spot)
probability that x3 will bubble 2 spots = 1/2, (if x3 < x1, x3 bubles 2 spots)
probability that x3 will bubble 3 spots = 1/2, (if x3 < x,  x3 bubles 3 spot)
.............
Now we can see a trend develeping 
1/2 + 2/2 +3/2 + 4/2 ...................

if we do a summation we get sum(k=1 to n-1)[x/2] =
= 1/2 * sum(k=1 to n-1)(k)
= 1/2(n-1)(n-2) = O(n*n/4)

[nonevent99]

Originally posted by AlbaLed

Q15) On average, how many exchanges are performed by insertion sort on n elements? How about selection sort? How about bubble sort?

According to Sedgewick (and I’m not sure I trust the answer for bubble)
Bubble: O(n*n/2)

Nonevent here is what I get for bubble, maybe you can trust me, forget Sedgewick

elements in bubble (smallest elem on top)
x
x1

probability of that x1 will bubble over x is 1/2

x
x1
x2
x3

probability of that x1 will bubble over x is 1/2, 
probability that x2 will bubble 1 spot  = 1/2, (if x2 < x1, x2 bubles 1 spot)
probability that x2 will bubble 2 spots = 1/2, (if x2 < x,  x2 bubles 2 spots)
probability that x3 will bubble 1 spot  = 1/2, (if x3 < x2, x3 bubles 1 spot)
probability that x3 will bubble 2 spots = 1/2, (if x3 < x1, x3 bubles 2 spots)
probability that x3 will bubble 3 spots = 1/2, (if x3 < x,  x3 bubles 3 spot)
.............
Now we can see a trend develeping 
1/2 + 2/2 +3/2 + 4/2 ...................

if we do a summation we get sum(k=1 to n-1)[x/2] =
= 1/2 * sum(k=1 to n-1)(k)
= 1/2(n-1)(n-2) = O(n*n/2)

I do trust you, Alba, but that last line of your derivation confuses me. Doesn't the sum of (k=1 to n-1) equal (n-1)(n-2)/2?

Then S = sum(k=1 to n-1)[x/2]
= 1/2 * sum(k=1 to n-1)(k)
= 1/2(n-1)(n-2)/2 = n*n/4

Moreover, if I experimentally attempt to verify that the answer is n*n/4 using an applet such as

http://www.eca.com.ve/cs/it_page/Sor...ble%20sort.htm

it invariably comes back as something very close to n*n/4 rather than n*n/2.

Finally, the usual bubble sort typically has n*(n-1)/2 =approx n*n/2 comparisons. I would expect that half of the comparisons would lead to swaps. That yields n*n/4.

These are the reasons I'm skeptical of Sedgewick. It just doesn't appeal to my gut. What's your take?

[wood]

That's true nonevent99. Looks like O(n*n/2) is a thigh upper bound for the worst case scenario. Your link shows that worst case (10 elements and 45 swaps). But in average, you'll get O(n*n/4) as you pointed out.

Wood

[AlbaLed]

I meant n*n/4 typo, checlk the time when I posted it, my eyes were ready to pop out into the keyboard at that time

[nonevent99]

Oh, good. It makes sense that the average should be n*n/4 or so, and the worst case n*n/2 or so.

Thanks, guys. You are a big comfort.

[CalmLogic]

*** bump ***

[ethanph]

Q3) How about {ww% : w is in {0,1}*}, % meaning "reverse"
PDA, S-> e | 1S1 | 0S0
(Thanks for the correction, Wood)

I check our notes in my class, WW% cannot be recognizable by any DPA. I think if we can figure out the CFL, it doesn't means it can be recognizable by DPA. NPDA can recognize some CFL that PDA cannot. Am I right?

[blah321]

That's right.. DPDA can keep pushing onto the stack, but doesn't know when to start popping (when the reverse of the string starts). But an NPDA guesses correctly.