2015-02-04 + HW01

posted Feb 3, 2015, 2:27 PM by Samuel Konstantinovich   [ updated Feb 8, 2015, 6:41 PM ]
Goal: Basic Recursion + Getting stuff done!

Lab + Homework:
Due Sunday 11:59pm.
I will grade and post results Saturday morning. 
Submit before then if you want a chance to re-do for full credit. No late submissions will be graded.
I will re-grade and post results Monday morning. 

Make a new github repo for this semester's homework. 
You will make a new folder on the TOP LEVEL OF YOUR REPO* for each homework starting with a 2 digit homework number. *Do not make a folder and put all of your homework assignments into it. The repo IS your "folder".
Submit your repo here:  http://goo.gl/forms/qKj3hlXpcY

These are examples of directory names for this homework: 
Good       //simple

OK!         //added a capital letter but its fine

Meh...     //reference to the goal on the board, but not a great name 

Bad!       //Reference to a song, while awesome if you make cool esoteric references, it is a terrible name for your homework folder. 

You are writing a class called Recursion for grading purposes this must be exact.
IMPORTANT NOTE: The methods will NOT be static. I will instantiate a Recursion object to test your code.  

1.1 You are adding a method to return your name: format: "Last,First" as it appears on your school documentation.
public String name();

1.2 You are solving 3 problems recursively:

The following three methods (1.21, 1.22, and 1.23) will throw an IllegalArgumentException when n < 0. 

1.21 factorial    public int fact(int n);

Calculate n!  (That is you must calculate n factorial, I am not exclaiming  how exciting n is...)

This is one of the most basic recursion examples. 

1.22 fibonacci*    public int fib(int n);

Calculate the n'th fibonacci number. Starting with 
fib(0) = 0, 
fib(1) = 1, 

Which starts to look like this: 0 1 1 2 3 5 8 13 21 34...

You must use the relationship:  the N'th fib number  = sum of the previous two fib numbers.

*Optionally, you can make a helper function to do this using tail recursion. This is not required. 

1.23 sqrt**   public double sqrt(double n);

Now to think a little:
There is a formula to calculate square root
Guess any number for the sqrt of n. (like n/2, or even 1)

n = 100
guess = 1

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

guess = 50.5

(then do it again, then do it again)
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).

** You MUST make a helper function, because you have to keep track of both n, and your guess in the recursion. This means that you need a function with two parameters, even though the sqrt function only takes 1 parameter.

1.3 Make your code compliant with this interface so that when I test it, you will be sure that it works properly. This is a great way to test if you followed directions. 

//if you ignored any directions above(including the 1st part about non-static)
//Then this will cause tons of errors for you!
public interface hw1{
public String name();
public int fact(int n);
public int fib(int n);
public double sqrt(double n);

2. 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...