From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.8 required=5.0 tests=BAYES_00,PLING_QUERY autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: a07f3367d7,7d1a02b763945274 X-Google-Attributes: gida07f3367d7,public,usenet X-Google-NewGroupId: yes X-Google-Language: ENGLISH,ASCII-7-bit X-Received: by 10.66.85.229 with SMTP id k5mr2036615paz.18.1358654516242; Sat, 19 Jan 2013 20:01:56 -0800 (PST) Path: 6ni6558pbd.1!nntp.google.com!npeer03.iad.highwinds-media.com!peer01.am1!peering.am1!npeer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!nrc-news.nrc.ca!News.Dal.Ca!news.litech.org!news.kjsl.com!newsfeed-00.mathworks.com!nntp.TheWorld.com!.POSTED!not-for-mail From: Robert A Duff Newsgroups: comp.lang.ada Subject: Re: Algorithms Homework Help?!?! Date: Wed, 16 Jan 2013 17:27:48 -0500 Organization: The World Public Access UNIX, Brookline, MA Message-ID: References: <183f4095-ac19-4396-a910-ba9cadfb958b@googlegroups.com> NNTP-Posting-Host: shell01.theworld.com Mime-Version: 1.0 X-Trace: pcls6.std.com 1358375268 27100 192.74.137.71 (16 Jan 2013 22:27:48 GMT) X-Complaints-To: abuse@TheWorld.com NNTP-Posting-Date: Wed, 16 Jan 2013 22:27:48 +0000 (UTC) User-Agent: Gnus/5.1008 (Gnus v5.10.8) Emacs/21.3 (irix) Cancel-Lock: sha1:Ek9jwDHayW6rkMxEinKlv59cfbU= X-Received-Bytes: 3230 Content-Type: text/plain; charset=us-ascii Date: 2013-01-16T17:27:48-05:00 List-Id: Adam Beneschan writes: > When I studied computer science, binary search was something covered > in, I think, one of the first-year introductory courses. Algorithmic > analysis was an upper-division course, which I think I took in my > third year. So I don't think this would work. If this is (as I > suspect) an introductory course, the students may not yet even know > what O-notation is, let alone know what the expected running time for > algorithms is. (OK, you've given them the hint that binary search is > O(log N); but if they don't know what the run time is for other > algorithms, it won't help them if you say "You don't have to use > binary search; you can use some other algorithm that runs in O(log N) > time".) Good point. I don't actually remember when I learned to program a binary search, nor when I learned O-notation. It seems like I've always known these things (and I've always known how to read, and I've always been happily married to my wife). ;-) Of course I knew how to do a binary search long before I knew how to program one -- it's more-or-less how one found things in a dictionary before google. It's interesting that when programming a binary search, people often write infinite loops and similar silly mistakes, but when doing it by hand, those mistakes don't occur. > On top of that, I don't think this homework assignment can be done > with an O(log N) algorithm. ... Oh, OK. I didn't look at it carefully. It just struck me that in the real world, customers don't say "Please solve this problem with a binary search"; they say "Please solve it fast enough", possibly with a vague or precise notion of "fast enough". > Anyway, I'd tend to agree that it seems odd to *require* binary > search, especially since off the top of my head it doesn't seem > appropriate for this particular problem. But classroom problems do > have to be contrived, sometimes. True. - Bob