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.224.218.2 with SMTP id ho2mr1685699qab.8.1358371169006; Wed, 16 Jan 2013 13:19:29 -0800 (PST) X-Received: by 10.49.116.139 with SMTP id jw11mr715081qeb.12.1358371168907; Wed, 16 Jan 2013 13:19:28 -0800 (PST) Path: k2ni11qap.0!nntp.google.com!p13no836957qai.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Wed, 16 Jan 2013 13:19:28 -0800 (PST) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=66.126.103.122; posting-account=duW0ogkAAABjRdnxgLGXDfna0Gc6XqmQ NNTP-Posting-Host: 66.126.103.122 References: User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <183f4095-ac19-4396-a910-ba9cadfb958b@googlegroups.com> Subject: Re: Algorithms Homework Help?!?! From: Adam Beneschan Injection-Date: Wed, 16 Jan 2013 21:19:29 +0000 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Date: 2013-01-16T13:19:28-08:00 List-Id: On Wednesday, January 16, 2013 11:47:37 AM UTC-8, Robert A Duff wrote: >=20 > > Then do my binary search based on this helper function(Posted below).= =20 > > --This problem MUST include Binary Search in some way. >=20 > That seems like an odd requirement. Taken literally, it would mean > you could do a binary search on some unrelated data structure, > throw away the result, and then solve the real problem some other > (slower) way. But that's probably not what your teacher meant. ;-) >=20 > If I were the teacher, I'd say: >=20 > The program must run in O(log N) time, where N is .... > Note: binary search is an O(log N) algorithm. When I studied computer science, binary search was something covered in, I = think, one of the first-year introductory courses. Algorithmic analysis wa= s an upper-division course, which I think I took in my third year. So I do= n't think this would work. If this is (as I suspect) an introductory cours= e, the students may not yet even know what O-notation is, let alone know wh= at 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 t= ime 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".) On top of that, I don't think this homework assignment can be done with an = O(log N) algorithm. It takes an input array that isn't required to be sort= ed, so there has to be some part of the program that iterates through the e= ntire array. In the OP's first program, he put his binary search in a whil= e loop, and the expected number of iterations would be O(log N) [I'm not su= re what N is]; but his loop called a function that scanned through the arra= y, so the actual time is O(N log N) or O(M log N) or something. I haven't = studied the problem in depth to figure out what the best running time is. = It's probably independent of the largest value in the array, while I think = the binary search the OP came up with started with an interval based on the= largest value in the array, and successively divided it in half to find th= e answer. Anyway, I'd tend to agree that it seems odd to *require* binary search, esp= ecially since off the top of my head it doesn't seem appropriate for this p= articular problem. But classroom problems do have to be contrived, sometim= es. =20 -- Adam