[PRL] Re: [plt-internal] cisco router problem

[Shriram Krishnamurthi]

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