Re: Algorithms Homework Help?!?!

[Adam Beneschan <adam@irvine.com>]

On Wednesday, January 16, 2013 11:47:37 AM UTC-8, Robert A Duff wrote:
> 
> > Then do my binary search based on this helper function(Posted below). 
> > --This problem MUST include Binary Search in some way.
> 
> 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.  ;-)
> 
> If I were the teacher, I'd say:
> 
>     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 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".)

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 sorted, so there has to be some part of the program that iterates through the entire array.  In the OP's first program, he put his binary search in a while loop, and the expected number of iterations would be O(log N) [I'm not sure what N is]; but his loop called a function that scanned through the array, 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 the answer.

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.  

                         -- Adam