[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