Received: from csa.bu.edu (csa [128.197.12.3]) by cs.bu.edu (8.12.2/8.12.2) with ESMTP id hA63f1Ll019173 for <cs320@cs.bu.edu>; Wed, 5 Nov 2003 22:41:01 -0500 (EST) Received: from localhost (japeter@localhost) by csa.bu.edu (8.10.1/8.10.1) with ESMTP id hA63ew627689 for <cs320@cs.bu.edu>; Wed, 5 Nov 2003 22:40:58 -0500 (EST) X-Authentication-Warning: csa.bu.edu: japeter owned process doing -bs Date: Wed, 5 Nov 2003 22:40:58 -0500 (EST) From: John Peterson <japeter@cs.bu.edu> X-Sender: japeter@csa.bu.edu To: cs320@cs.bu.edu Subject: Tons of Questions about Problem 6 In-Reply-To: <Pine.SOL.4.20.0311052141400.13903-100000@csa.bu.edu> Message-ID: <Pine.SOL.4.20.0311052211270.21294-100000@csa.bu.edu> Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Length: 1878 Status: RO X-Mozilla-Status: 8009 X-Mozilla-Status2: 00000000 X-UIDL: 3fa9987300000015
Problem 6 seems to be ambiguous. Isn't the whole point of using trees
instead of lists because they're more efficient? balanced binary
trees provide logarithmic time for all three functions. If efficient
search, insert, and delete are so important, why use lists at
all? Just how efficient do we need to make insert and delete?
Futhermore to implement a binary search, we're going to need a
sorted list, we'll probably want to use merge sort for this, is this
in the standard library? We'll also need a list size or list length
function, is this in the library too? Where can I examine the standard
library for that matter. It seems to be chalk full of useful
functions. Or aren't we suppose to use them?
Also, about structures, can they have helper functions that are not
declared in the signature? Can they have multiple signatures (like Java
can have multiple interfaces). If neither, are we allowed to change
the signature for DICTIONARY, or are we not allowed helper functions?
hmmmm.. did I miss anything?
John
On Wed, 5 Nov 2003, Christopher Selin wrote:
> It is my understanding that lookup, looks for a key (which is a string) and
> returns the item corresponding to that key, if it finds it. If we're
> looking up a string, why would we need to use the nth function?
>
> On Wed, 5 Nov 2003, Rui Shi@cs.bu.edu wrote:
>
> > Hi, all,
> >
> > I realilze that in problem 6, the professor ask us to implement lookup etc. functions using binary search.
> >
> > You may need following functions:
> >
> > List.nth : 'a list * int -> 'a
> >
> > which take a list and an index n, return the nth element in the list. nth (ls, 0) is the first element of ls.
> >
> > Also need to note that we should use
> >
> > String.compare (a, b) to compare 2 strings, read the text book.
> >
> > Sorry for late reminder.
> >
> > TF
> >
> >
> >
> >
> >
>
>
This archive was generated by hypermail 2b29 : Fri Jan 21 2005 - 12:17:03 EST