[racket] [Racket]27.3.5, 27.3.6 htdp

From: Ken Hegeland (hegek87 at yahoo.com)
Date: Fri Nov 19 14:21:58 EST 2010

Hi, Im sorry if I appear to be coming here a lot, just having trouble with the algorithm section more than any others.


I believe I completed find-root-linear, which to me seems like just testing if a number in the table is a root of some function, if it is I return the the position in the table.
I also think that a table can really be considered a list, and this whole problem can be thought of as finding some item in a list. Linear is basically natural recursion with numbers, if the first item in a list is what you are looking for, return appropriate position of the item in list. So, that being said, I feel I understood the linear part, and I am struggling with how to complete the divide-and-conquer method, find-root-discrete.

The goal seems simple, divide the list in half, check the middle number to see if it is a root, and then go somewhere from there. if the middle number is a root, return mid. if it's less than root, recurse with mid and (sub1 n), finally, if it's greater than root, recurse with mid and 0. so with length 10, and table '( -5 -4 -3 0 3 4 5 7 8 9) it would find the midpoint as (/ 10 2) or 5, determine the 5th item as 3. since 3 is greater than 0, it would do midpoint of 5 and 0, which is 2.5, I used floor to drop it to 2, 2 is -4, which is less than 0, so now it should find the midpoint of the number 2, and the n, which is now 5, which produces 3.5, or 3, which gets you -3, and it continues until it finds 0. Just this example I tried to explain leaves me with a couple of questions. 
First of which, if the list is counted '((f 0)(f 1)(f 2)...(f(sub1 n))), I will already encounter a problem I believe, because mid uses the number n, 10. There are 10 items in the list, but the 5th item in the list is (f 4), so would it return (- n 1) when it finds the root?

My next question, I am having trouble determining how exactly to determines an upper mid, and lower mid, I was thinking of 2 local mid definitions, one to do (/ n 2), and another do do(/(+ mid n)2), is this an idea which is going in the correct direction?

I am also playing around with the idea of creating a function that consumes an value to search for, a list, a lower bound, and an upper bound, and trying to create a working function to abstract.

While I was struggling with this I decided to take a moment and read a bit ahead and see what the next exercise is, and again, I'm having some trouble. My real point of trouble is that I don't exactly understand what function integration is. I tried googling it, and it seems to be calculus type math, which I have never experienced. Is it safe to say function integration is just finding the area under some function? So, the goal of this is to split it into many small rectangles, and add up the numbers? I feel like that can't be it, because with dividing it by midpoints, you can eventually make all rectangles L=(f x) W=1, which would make the areas equal to (f x), so it would seem to be easier to just add every number.
(+ (f 0) (f 1) (f 2) (f 3) (f 4)....(f(- n 1)))

Anyway, thanks as usual for any help.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20101119/bf99ccca/attachment.html>

Posted on the users mailing list.