[PRL] Re: [plt-internal] cisco router problem
Shriram Krishnamurthi
sk at cs.brown.edu
Wed Jan 14 16:12:14 EST 2004
I didn't know you needed to give students concrete problems. Any
other pedagogic insights you want to share before reading my message?
Shriram
Matthias Felleisen wrote:
> 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