CS112 Assignment 1



Problem 1

public class NewtonRaphson{
	
public static void main(String [] args)
{
	System.out.println("approximate(2, 30, 5, 3) = " + approximate(2, 30, 5, 3));
	System.out.println("approximate(2, 30, 5, 10) = " + approximate(2, 30, 5, 10) + "\n");
	System.out.println("approximate(3, 30, 5, 3) = " + approximate(3, 30, 5, 3) );
	System.out.println("approximate(3, 30, 5, 10) = " + approximate(3, 30, 5, 10) + "\n");
	System.out.println("approximate(4, 30, 5, 3) = " + approximate(4, 30, 5, 3) );
	System.out.println("approximate(4, 30, 5, 10) = " + approximate(4, 30, 5, 10) + "\n");
}

public static float approximate (int k, float n, float x0, int iter)
{
	if(iter == 0)
		return x0;
	
	double x1 = x0 - (Math.pow(x0, k) - n)/(Math.pow(x0, k-1)*k);
	
	return approximate(k, n, (float)x1, iter-1);
}

}


Test Cases: 


approximate(2, 30, 5, 3) = 5.477226
approximate(2, 30, 5, 10) = 5.477226

approximate(3, 30, 5, 3) = 3.1102657
approximate(3, 30, 5, 10) = 3.1072326

approximate(4, 30, 5, 3) = 2.524532
approximate(4, 30, 5, 10) = 2.3403473

_____________________________________

Problem 2

public class Heffalumps {

public static void main(String[] args) {

	int [] counts;

counts = count(0, 1, 5);
System.out.println("0 heffalumps and 1 woozles after 5 generations = " + counts[0] + " heffalumnps " + counts[1] + " woozles \n");

counts = count(1, 2, 3);
System.out.println("1 heffalumps and 2 woozles after 3 generations = " + counts[0] + " heffalumnps " + counts[1] + " woozles \n");

counts = count(3, 4, 5);
System.out.println("3 heffalumps and 4 woozles  after 5 generations = " + counts[0] + " heffalumnps " + counts[1] + " woozles\n");

counts = count(4, 5, 8);
	System.out.println("4 heffalumps and 5 woozles after 8 generations = " + counts[0] + " heffalumnps " + counts[1] + " woozles  \n");

}

	static int [ ] count(int numHeffalumps, int numWoozles, int generations)
	{
		int [] cur_count = {numHeffalumps, numWoozles};
		
		if( generations == 0 )
			return cur_count;
		
		int [] next_count = count (3*numHeffalumps + numWoozles, 2*numHeffalumps + 5 * numWoozles, generations-1);
		
		cur_count[0] += next_count[0];
		cur_count[1] += next_count[1];
		
		return cur_count;
	}

}

Test cases:

0 heffalumps and 1 woozles after 5 generations = 2133 heffalumnps 5934 woozles 

1 heffalumps and 2 woozles after 3 generations = 184 heffalumnps 488 woozles 

3 heffalumps and 4 woozles  after 5 generations = 13536 heffalumnps 36534 woozles

4 heffalumps and 5 woozles after 8 generations = 3233052 heffalumnps 8825445 woozles


___________________________________

Problem 3

public class Wally {
	public static void main(String[] args) {
		System.out.println("numWally in 1 generations");
		System.out.println("recursive " + countWallyRecursive(0, 1, 1));
		System.out.println("iterative " + countWallyIterative(1));
		
		System.out.println("\nnumWally in 5 generations");
		System.out.println("recursive " + countWallyRecursive(0, 1, 5));
		System.out.println("iterative " + countWallyIterative(5));
		
		System.out.println("\nnumWally in 10 generations");
		System.out.println("recursive " + countWallyRecursive(0, 1, 10));
		System.out.println("iterative " + countWallyIterative(10));
	}
	
	// Complexity in both cases is O(num_generations)
	public static int countWallyRecursive(int numMatureWally, int numNewWally, int generations)
	{
		if( generations == 0)
			return numMatureWally + numNewWally;
		
		return countWallyRecursive(numMatureWally+numNewWally, numMatureWally, generations - 1);
	}
	
	public static int countWallyIterative(int generations)
	{
		int numNewWally = 1;
		int numMatureWally = 0;
		
		for (int i = 0; i < generations; i++)
		{
			int temp = numNewWally;
			numNewWally = numMatureWally;
			numMatureWally += temp; 
		}
		
		return numNewWally + numMatureWally; 
	}
}

Test cases:

numWally in 1 generations
recursive 1
iterative 1

numWally in 5 generations
recursive 8
iterative 8

numWally in 10 generations
recursive 89 		
iterative 89

_________________________________________

Problem 4

In order of growth:

1/n	   
2^1000	   
log log n	   
sqrt(log n)	   
(log n)^2	   
n^0.01	   
sqrt(n)	   
3n^0.5	   
2^log n	   
5n	   
n ln 4n	   
2n log n^2	   
6n log n	   
4n^1.5	   
4^log n	   
n^2 log n	   
n^3	   
2^n	   
4^n	   
2^(2^n)	 

Theta of each other: 

sqrt(n), 3n^0.5
2^log n, 5n
n ln 4n, 2n log n^2, 6n log n