CSC151.01 2014F, Class 46: Binary Search ======================================== _Overview_ * Preliminaries. * Admin. * Upcoming Work. * Extra Credit. * Notes on Quiz 11. * Questions. * Preflection. * Details * Algorithms and algorithm design. * Binary search. * A demo: Destructive binary search. * Considering the parameters to binary search. * Lab. Preliminaries ------------- ### Admin * New partners! * My computer is in the shop, which puts me even further behind. I probably won't get you comments on phase 1 of the project, which means that I'll be a little more generous than normal in grading phase 2. Apologies. * If you use the commons, *don't dump tea in the sink* * Schedule will be shifting to accommodate additional discussion today. ### Upcoming Work * Lab writeup: Think about Exercise 4 (don't submit anything) * No reading for tomorrow. * Part two of the project due tomorrow. ### Extra Credit Opportunities #### Academic * CS Extras Tuesday the 25th (tomorrow): Summer Opportunities in CS #### Peer Support * Karan's radio show 11pm Thursday nights on KDIC * Evan's radio show 5pm Friday nights on KDIC * Donna's radio show Sunday midnight on KDIC * Noteworthy and Dance performance, December 4 and 5 in Flanagan * One acts, December 5 and 6 in Roberts ### Notes on Quiz 11 * Pattern: `assoc` returns either an entry (row) or #f. In most cases in which we call `assoc`, we want to do something to the entry or return a default value for #f. * We've encoded that pattern in `lookup-and-process`. * In the case of lookup-color-name we want to turn it into a color * Given an entry of the form `("red" 128 0 0 "reddish")`, to build an IRGB color, extract three components and call `irgb` on them. How would we write this in Scheme? (lambda (val) (irgb-list->irgb (list-take (list-drop VAL 1) 3))) * Problem 2 > (define strnum? (either string? number?)) > (strnum? 'a) #f > (strnum? 3+4i) #t > (all number? (list 1 2 3 4)) #t > (all number? (list 1 2 3 "sam" 4)) #f > (all (lambda (val) (or (number? val) (string? val))) (list 1 2 4 "sam" 5)) #t > (all (either number? string?) (list 1 2 3 4 "sam" 5)) #t > (either number? string?) # ### Project Questions _We're drawing/selecting polygons with turtles. We realize that in order to get it to scale we would have to change the angels of our polygons so that they would no longer follow the (/ 360 sides) formula. What should we do?_ > Note that you would also have to change the length of each side. But both figuring out the angles and figuring out the side length is not reasonable. Hence, I am comfortable as long as your scaling works within the same aspect ratio, even if it does not work with different aspect ratios. (E.g., if the image goes from 100x100 to 200x200 or from 100x200 to 200x400, the turtle portions should scale correctly, but if it goes from 100x100 to 200x100 or 100x200, then the turtle portions do not need to scale correctly.) I'd recommend that you base your side length on either the minimum, maximum, or average of the dimensions of the image. _What about image-compute-pixels?_ > Now called `image-recompute!` (image-recompute! image (lambda (x y) color)) > Also `image-redo!` (image-redo! image (lambda (x y color) newcolor)) > Both should work on only what's selected. _Didn't you promise us code that would select based on a turtle?_ > Yes. And I sent it to you a while ago. ### Questions Preflection ----------- _Two minutes with your partner_ * What were the main points of the reading? * What was confusing? Algorithms and algorithm design ------------------------------- * Look at generalized problems * Not: How do I find a library book, but "given a collection with these characteristics, how do I quickly find something?" * Our question: How do I find something in a vector or list? * One strategy: Use assoc (linear search) * Can we do better? Yes! If we know something about the organization, we can take advantage of it. * Library: Call numbers are in different places and a sign/table tells you where to look * Phone book: Binary search ------------- A demo: Destructive binary search --------------------------------- * If you throw away half and you start with 2000 2000 -> 1000 -> 500 -> 250 -> 125 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1 * A really fast algorithm. We will explore how to implement it in Scheme next class. Binary search in Scheme: Considering the parameters to binary search -------------------------------------------------------------------- Remaining Questions ------------------- _Could you go over `vector-sorted?`? Lab ---