Received: from acsn03.bu.edu (acsn03.bu.edu [128.197.159.63]) by cs.bu.edu (8.12.2/8.12.2) with ESMTP id hA64ZvLl029324 for <cs320@cs.bu.edu>; Wed, 5 Nov 2003 23:35:57 -0500 (EST) Received: from BPATTON (bays200-0b01-dhcp154.bu.edu [168.122.253.154]) by acsn03.bu.edu ((8.9.3p2.buoit.v1.3)/BU_Server-1.3) with SMTP id XAA41570 for <cs320@cs.bu.edu>; Wed, 5 Nov 2003 23:35:26 -0500 Message-ID: <001901c3a41f$6292dfc0$9afd7aa8@BPATTON> From: "Brian Patton" <bjp@bu.edu> To: "cs320 Course Account" <cs320@cs.bu.edu> References: <Pine.SOL.4.20.0311052211270.21294-100000@csa.bu.edu> Subject: Re: Tons of Questions about Problem 6 Date: Wed, 5 Nov 2003 23:35:19 -0500 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2800.1158 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1165 X-Score-Level: -0.6 Content-Length: 3041 Status: RO X-Mozilla-Status: 8018 X-Mozilla-Status2: 00000000 X-UIDL: 3fa998730000001d
I'll go at a couple of these questions...
I don't think we'll need to change the signature for dictionary - just
change "type 'a t = (string * 'a) tree" to "type 'a t = (string * 'a) list"
in the Dict structure.
I agree that it seems wiser to implement the dictionary using a tree because
even by using List.drop, List.take, etc. we are still doing a linear search
through the front half or back half of the list... The bottom line is that
we can only really achieve logn time on a tree. We tried in 112 to do
binary search on a linked list and decided it wasn't possible - that was a
disadvantage when compared to trees. Still, we can make it _look_ faster by
using the take and drop functions...
There is no delete, is there? I hope not.
Anyway, that's my contribution - it would be nice to know what the functions
in the library are, and get to use them when they would help.
-Brian
----- Original Message -----
From: "John Peterson" <japeter@cs.bu.edu>
To: <cs320@cs.bu.edu>
Sent: Wednesday, November 5, 2003 10:40 PM
Subject: Tons of Questions about Problem 6
>
> 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