Session Start (MSN - ferret:falo): Wed Feb 26 14:40:02 2003
[Wednesday|144003] falo: lo.  Any chance you did those proc prog answers in a text editor?
[Wednesday|144036] ferret: Nope.
[Wednesday|144044] ferret: Hmmm.
[Wednesday|144054] ferret: Which specific questions do you need answers to?
[Wednesday|144109] falo: Sheet 4.  Tute in an hour and just about to start on it :$
[Wednesday|144111] ferret: hang on, toast
[Wednesday|144131] falo: That has to be one of the most random MSN messages I've ever had ....
[Wednesday|144415] ferret: Ok, I'm back.
[Wednesday|144433] ferret: Ok, let's go through the sheet then. :)
[Wednesday|144440] falo: :)
[Wednesday|144501] ferret: You understand what quicksort does in theory?
[Wednesday|144522] falo: Yeppers.  Chooses random point, sorts either side into less than and greater then recurses
[Wednesday|144526] ferret: ok
[Wednesday|144612] ferret: Q1 - If you're sorting something that's been sorted before, this will suck.
[Wednesday|144635] falo: Ah.  'cos then everything greater will go through a number of moves
[Wednesday|144637] falo: I see
[Wednesday|144639] ferret: Q1 part two: 3/4
[Wednesday|144723] falo: Why?
[Wednesday|144739] ferret: Q2:replace the 
 j:= j - 1 ; Swap(lines[i],lines[j])
 with
[Wednesday|144831] ferret: j := j - 1 ; while lines[j]^ > pivot^ do
 j := j - 1 end; Swap(lines[i],lines[j]);
[Wednesday|144957] falo: Cool.  That makes sense
[Wednesday|145003] ferret: Q3: (a): it's difficult to do this question, because it's so blatantly false. 
[Wednesday|145032] falo: Lemme take a quick look.
[Wednesday|145044] ferret: You need to show that their system doesn't change how deep the stack needs to go, it justs 'puts it off'.
[Wednesday|145122] falo: Hmmm.  'cos it's still doing the work, just at a different time.
[Wednesday|145150] ferret: Because with the two recursion calls right next to each other, one is 'deep' and one is shallow. Their 'improved' system does the shallow one first, but the stack size before going into the deep one is the same as that before going into the shallow one.
[Wednesday|145203] ferret: If the stack size isn't the same at these two times, something has fucked up.
[Wednesday|145216] ferret: (b)
[Wednesday|145220] ferret: uh...
[Wednesday|145221] ferret: [b]
[Wednesday|145236] ferret: That's real easy.
[Wednesday|145253] ferret: Replace the if with a while and the recursion line with n:=n-1
[Wednesday|145306] ferret: [c]
[Wednesday|145356] falo: Just apply it?
[Wednesday|145507] ferret: begin
 while b - a > 1 do
 i := Partition(a,b);
 while i - a > 1 do
 i:=Partition(a,i);
 QuickSort(i + 1,b)
 end;
 end;
[Wednesday|145514] ferret: end;
[Wednesday|145524] ferret: [c] part two :D
[Wednesday|145549] ferret: uhh, quite hard
[Wednesday|145603] ferret: Ah, no it isn't.
[Wednesday|145644] ferret: Just use the exact changes they made.
[Wednesday|145714] ferret: Don't even bother to write that down properly, just say implementing it exactly as they suggested will cause the desired improvement (max log(2)(n) stack)
[Wednesday|145803] ferret: Q4: Every single n will be moved in each partition. Exact order n^2
[Wednesday|145821] ferret: Where n is the number of lines...
[Wednesday|145827] falo: Right.
[Wednesday|145837] ferret: And the order refers to the number of swaps, not the number of comparisons.
[Wednesday|145851] ferret: [b]
[Wednesday|145939] ferret: First part: The quicksort will run at normal speed until it ends up with partitions containing all (or mostly) identical lines, then it will become exact order n^2 again.
[Wednesday|150047] ferret: Part two should be obvious... part three answer is no, but I forget why. :D
[Wednesday|150127] falo: I'll work it out before the tute
[Wednesday|150132] ferret: Partially because the pivot won't necessarily be one of the repeat lines, and partially because those items will just be compared again in the next recursion down...
[Wednesday|150144] ferret: Part c is a bitch.
[Wednesday|150205] ferret: Lots of code to right, so wait a minute..
[Wednesday|150208] ferret: write^
[Wednesday|150224] ferret: While I'm doing this, carry on actually writing stuff down or whatever ;)
[Wednesday|150236] falo: Yessir :D
[Wednesday|150900] ferret: procedure Partition(a,b:INTEGER;var i,j:INTEGER)
 var pivot:line; k:INTEGER;
 begin
 i := a + Random.Roll(b - a);
 pivot := lines[i];
 j := i; k := b;
 while j < k do
 if lines[j]^ < pivot^ then
 Swap(lines[i],lines[j]);
 j := j + 1;
 else if lines[j]^ > pivot^ then
 k := k - 1;
 while lines[k]^ > pivot^ do k := k - 1 end;
 Swap(lines[j],lines[k]);
 else j := j + 1
 end;
 end;
 end Partition;
[Wednesday|150904] *** falo209@hotmail.com (Oli - Drunken tutors = teh funny) has joined the conversation.
[Wednesday|150916] ferret: You might need to copy/paste that to get rid of the emoticons :\
[Wednesday|150938] ferret: The Quicksort needs rewriting to, but it's a really minor boring task, don't bother with it.
[Wednesday|150953] falo: OK.  Cheers matey
[Wednesday|151024] falo: You're a life saver.  I'll read it properly before I write it out though.  Don't want him asking questions that I can't answer
[Wednesday|151047] ferret: Ok.
[Wednesday|151111] ferret: I do remember my tutor saying that my code is slightly inefficient in one place, but his version was very complicated.
[Wednesday|151146] falo: OK.  I owe you a pint
[Wednesday|151255] ferret: I don't drink any more ;)
[Wednesday|151510] falo: ... of lemonade
[Wednesday|151532] ferret: ok :D
Session Close (falo): Wed Feb 26 15:17:55 2003


Session Start (MSN - ferret:falo): Tue Mar 04 16:29:11 2003
[Tuesday|162912] *** falo209@hotmail.com (Oli - I must not fear.  Fear is the mindkiller.  Fear is the little death that brings total oblivion.) has joined the conversation.
Session Close (falo): Tue Mar 04 16:29:12 2003