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

Robby Findler robby at cs.uchicago.edu
Wed Jan 14 15:08:15 EST 2004


Uhh... I don't think that the entire history of algorithms would make a
good example for a course in the intro sequence, no... It seems to work
much better when it is a) smaller and b) more concrete.

;)

Robby

At Wed, 14 Jan 2004 16:06:04 -0500, 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