[PRL] Re: [plt-internal] cisco router problem
Matthias Felleisen
matthias at ccs.neu.edu
Wed Jan 14 16:07:43 EST 2004
No. "Stories" are better with students here and other regular places.
Real stories that they can do on their own.
Naturally, at a place where everyone is brilliant you don't need
stories to motivate performance problems you won't need this. Just
showing them the history of algorithmics, starting with MIX
is enough.
-- Matthias
On Wednesday, January 14, 2004, at 04:06 PM, Shriram Krishnamurthi
wrote:
> I suppose the entire history of algorithmics isn't enough as a source
> of examples? (-:
>
> Shriram
>
> Matthias Felleisen wrote:
>
>> Close. The reason I am pushing him is to get a cute little example for
>> 212 students. Here is something you can design. Let's stress. Hah,
>> it's too slow, and it's not Java's fault. How can we do better?
>>
>> If we can find four or five more things like this, 212's O stuff
>> becomes more interesting and accessible to students.
>>
>> -- Matthias
>>
>>
>> On Wednesday, January 14, 2004, at 03:27 PM, Mitchell Wand wrote:
>>
>>> I'm assuming the following is a reasonable abstraction of the
>>> problem:
>>>
>>> Given two long lists of integers (possibly with duplicates), one much
>>> longer than the other, find their intersection.
>>>
>>> Doing intersection (or DB join) is usually a n^2 problem.
>>>
>>> Some standard solutions:
>>>
>>> 1. Read the big list once and the smaller list many times. I'm
>>> guessing he's already thought of this.
>>>
>>> 2. Keep the lists sorted. That way it turns into a O(n) problem.
>>> If
>>> you have to sort the lists, that makes it O(n log n).
>>>
>>> 3. Preprocess the smaller list once to get a hashtable of possible
>>> hits. That way you only scan through the small list for big-list
>>> elements
>>>
>>> 4. Indices are Good Things. (Generalization of #3).
>>>
>>> --Mitch
More information about the PRL
mailing list