Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

2019-01-30

posted Jan 30, 2019, 6:24 AM by Konstantinovich Samuel   [ updated Jan 30, 2019, 9:33 AM ]
Goal: More Recursion

Homework:
1. Write the sqrt method explained below (recursively).
2. On codingbat, in your profile/preferences
Everyone:
  -share with konstans@stuy.edu (even if you did it last semester)
  -Adjust your "name" to be   PD.LAST.FIRST  (exactly like what follows)
    e.g.
        3.Rahman.Bobby
        5.Queen.Stephen
        9.Takahashi.Keiko

Do Now:
0. Take seats
1. ALWAYS: notebooks out.

Consider a function meant to revers a string:
    public static String reverse(String s){}
Answer the following in your notes:
2. What is a good base case?
3. What would you do if there is more letter than that? [include the recursive call to part of the problem]
4. Answer 2 again to see a pattern.
5. AFTER you have 2-4, write the method.



Consider the following method headers:

public static int sumArray( int[] data)

Can you make these recursive?
Remember you cannot split an array.

What if they were ArrayLists?





Newton's Square Root Approximation

There is an algorithm to calculate the square root:

1.Guess any number for the sqrt of n. (like n/2, or even 1)
n = 100
guess = 1

2 Make a better guess this way: 
guess =  ( n / guess + guess) / 2

             = 50.5

3 do it again and again until you get close enough.
[test accuracy by squaring the guess, NOT by using another sqrt method!!!]
guess = 26.24009900990099
guess = 15.025530119986813
guess = 10.840434673026925
guess = 10.032578510960604
guess = 10.000052895642693
...
Notice how fast this converges on the correct value (10).

Same if you try to calculate sqrt(2)
It converges:
guess = 1         (2/1+1)/2 = 1.5
guess = 1.5       (2/1.5 + 1.5)/2  = 1.4167
guess = 1.4167  etc.
guess = 1.4142.

This can be done with a while loop until your guess squared is close to n by a % difference of some threshhold. (0.001% is not bad which is 0.00001)

Write and TEST the method:
/*  
 *@param n any non-negative value you want to take the sqrt of
 *@return the approximate sqrt of n within a tolerance of 0.001%
 */
public static double sqrt(double n){}

This method and several others will be collected as a single submission.




Extra:
Need to study longer? (You are doing it wrong)
Let me end with a link to a video about how to study for less time and get more out of it. Even if you only watch the first 5-10 minutes you will be much smarter.
You can watch as little or as much of this video as you want, I won't ever check... but you won't increase your GPA either.  If  this video helps you do better please let me know!
This pairs nicely with every article about sleeping more to remember things better...

Extra:
Need to study longer? (You are doing it wrong)
Let me end with a link to a video about how to study for less time and get more out of it. Even if you only watch the first 5-10 minutes you will be much smarter.
You can watch as little or as much of this video as you want, I won't ever check... but you won't increase your GPA either.  If  this video helps you do better please let me know!
This pairs nicely with every article about sleeping more to remember things better...
Comments