Lecture 40

Announcements

Partner Evaluations are available if you wish to use them; see collab's announcements page.

The final exam will be given on Tuesday 6 May from 7–10pm. The location will depend on the numeral in your computing ID; see the bottom of the course schedule for details.

The exam will target 1½ times the length of the previous exams, but you will have 180 minutes (approximately 3½ as much time as previous tests) in which to take it.

Final Test Review Sheet

Test Topics

Cumulative
- Any topic that was fair game for Test 1 is fair game for the final.
- Any topic that was fair game for Test 2 is fair game for the final.
- More than half of the points will be for new material not covered by either previous test.
General Points
- There will be questions involving coding; problem solving will be involved.
- You should be able to read code and interpret what it is doing.
- You will be asked to implement and entire class.
Not on the test
- You do not have to know what to import to get access to various classes.
- You do not have to know when to use throws.
- You do not have to know particular room-counting algorithms, how to make the particular fractals we mentioned in class, or the details of other in-class or in-lab examples.
- L-systems will not be on the test.
Classes
- public and private.
- static and non-static for both methods and fields.
- How to implement an entire class.
- Using classes you write as parameters, return types, and field types.
- Classes that refer to one another.
- how to write toString (but not how to write equals).
Algorithms
- Different ways code can be good (simple, versatile, quick to write, fast when run, etc).
- How linear and binary searches work.
- How to code linear search, either for a particular value or for the biggest/smallest/closest to a taget value/etc.
Recursion
- Given a recursive method, tell us what it does.
- Write a recursive method given a description of what it should do.
- The three parts of recursion and how to identify recursive methods that are lacking each part.
- Recursive Turtle drawings: given code, what will it draw? Given a rule, what does the code look like?

Studying for the Test

Practice coding without using Eclipse.
You'll be writing code on paper. This feels different than writing it in Eclipse. You don't want to be surprised by how different it feels. Practice writing code by hand.

A few small syntax errors is OK. But if you are really off we will take off points. Try to write correct code

You will never need to add import statements, but you might need to write class declaration, method declaration, etc.

Try re-solving the homework problems on paper without looking at your code or textbook.

You can find more sample problems in Programming Challenges in the textbook; try, for example, chapter 8's problems 1, 3, 5, 6, 8, and 10; and chapter 15's problems 1–9.
More practice.
codingbat.com has lots of methods you can practice with. Their recursion sets will be particularly useful.
Read programs.
We'll show you code and ask you what it does. You won't be able to have Java run it. Practice thinking through code without running it. Drawing memory pictures can be very helpful, but memory sketches will not be on the test directly.
Review the Lecture Notes.
Not everything in the book is equally important, and some of what we covered is not in the book (algorithms, for example). Review the lecture notes to see what we emphasized. If you are confused by some point, check the podcast.
Study Groups.
There is benefit in getting 3–5 people together and coding on a whiteboard.

From 1pm Lecture

Do the rooms apply to late exams?
    No
How to use static methods
    static: Math.pow, Math.sqrt, HW5.readCSV, ___.main
    non-static (instance): keyboard.nextInt(), bird.flap(), ...
    use: ClassName.methodName(arguments)
When do you use this.
    "rule": this. before an instance field or method of this object
    Rule: only in non-static methods
What should we avoid when writing classes that use classes
    infinite recursion
    data inconsistency

Linear search, binary search

    1 32 4 631 8 0 168 432 68 4132 476 5168 432 1
    0 1  2 3   4 5 6   7   8  9    10  11   12  13
Linear:
    check list[0], then list[1], then list[2], ... until it finds it
Binary (look for 432):
    check [0,13] : list[6] = 168
    check [7,13] : list[10] = 476
    check [7,9]  : list[8] = 68
    check [9,9]  : list[9] = 4132
    check [9,8]  : fail  

public static int binarySearch(int[] list, int goal, int start, int end) {
} 

Walk through a fractal example
    code to picture
    
public static void fractal(Turtle t, int n) {
    if(n == 0) {
        t.forward(10);
    } else {
        fractal(t, n-1);
        t.left(90);
        fractal(t, n-1);
        t.right(90);
        fractal(t, n-1);
    }
}

public static void fractal(Turtle t, int n) {
    if(n == 0) {
        t.forward(10);
    } else {
        t.right(25);
        fractal(t, n-1);
        t.left(90+25);
        t.forward(5);
        t.right(90+25);
        fractal(t, n-1);
        t.left(25);
    }
}

Lab 13: Buckets
    public static String buckets(String str) {
        /* Bucket the first and last half of the input 
         * and add brackets around the result. Round 
         * "half" down: the first half of a string with 
         * 3 characters has 1 character in it, the second 
         * half has 2 characters in it.
         */
        // get the first half
        if (str.length() == 1) {
            return "["+str+"]";
        }
        int middle = str.length() / 2;
        String firstHalf = str.substring(0, middle);
        // recursively bucket it
        firstHalf = buckets(firstHalf);
        // get the second half
        String secondHalf = str.substring(middle, str.length());
        // recursively bucket it
        secondHalf = buckets(secondHalf);
        // put the buckets halves together
        String joined = firstHalf + secondHalf;
        // inside of []
        return "[" + joined + "]";
    }

From 3pm Lecture

See an example static method
	main, every method from HW5 & 4
	Hw5.readCSV, Math.pow
Non-static (instance)
	keyboard.nextInt, bird.flap

When classes refer to each other, when ClassName.method vs object.method?
	ClassName.method for static methods
	objectName.method for non-static

How does tick in Jumper.java work?
	well

class writing in general -- process
	1. Make a UML class diagram
	2. Turn that diagram into java code (no method bodies yet)
	3. Flesh out one method
	4. Test it so far
	5. Return to step 3
Write a stopwatch class
	Make a stopwatch class that keeps track of minutes and seconds
	and has a tick method that goes to the next second
	and a reset method that resets it to 00:00
----------------------
   StopWatch
----------------------
seconds : int
minutes : int
onness : boolean
----------------------
reset() : void
tick() : void
setOnness(boolean) : void
StopWatch()
----------------------

public class StopWatch {

	private int seconds; 
	private int minutes;
	private boolean onness;
	
	public StopWatch() {
		this.minutes = 0;
		this.seconds = 0;
		this.onness = false;
	}
	
	
	public void reset() {
		if (this.onness) {
			this.minutes = 0;
			this.seconds = 0;
		}
	}
	public void tick() {
		if (this.onness) {
			this.seconds += 1;
			if (this.seconds >= 60) {
				this.seconds -= 60;
				this.minutes += 1;
			}
		}
	}
	public void setOnness(boolean on) {
		this.onness = on;
	}
	
	public String toString() {
		return this.minutes +" min and " + this.seconds + " sec";
	}
}



Examples of recursive turtle drawing
	From rule image to code
	From code to picture

public static void fractal(Turtle t, int n) {
	if (n == 0) {
		t.forward(29);
	} else {
		t.right(90);
		fractal(t, n-1);
		t.left(90);
		fractal(t, n-1);
		t.left(90);
		t.forward(29);
		t.right(90);
		fractal(t, n-1);
	}
}