Sections A and B Notes and sample code

-->

Date	Topics	Code Examples	To do

This document is updated frequently, so remember to refresh your browser. How to import the code examples below into an Eclipse project.

Week 14 (November 16 - November 20)
Monday	Exceptions Reporting errors: the `throw` statement Handling errors: `try/catch` blocks Declaring errors: the `throws` clause (required for "checked" exception types only) The Exception class hierarchy; "checked" vs "unchecked" exceptions The "unchecked" exceptions are subtypes of RuntimeException "checked" exceptions must be caught, or declared with `throws`, in order for the code to compile An exception may occur in a method call that is farther up the call stack than the code containing the try/catch block The exception "propagates" down the stack until a matching catch block is found catch blocks are specific to the type of exception In general, avoid catching an exception unless you can actually do something about it e.g., `catch (Exception e){...}` is almost always a bad idea	ExceptionTest.java ExceptionHandlingExample.java	zyBook Sections 10.1 - 10.4
Wednesday	"Unwinding" the call stack to find the first matching `catch` block Cleanup: `try/catch/finally` and `try/finally` Code in a `finally` block is guaranteed to be executed before the stack frame disappears, whether or not an exception occured `finally` blocks are commonly used to ensure that files are closed or other OS resources are released in case of an exception Exception handling in real life: using Sockets	CallStackExample.java SimpleServer.java SimpleClient.java
Friday	More fun with sockets (realistic examples using try/catch and try/catch/finally) Example: tracing some exception-handling code Reviewing polymorphism	SimpleHttpServer.java SimpleHttpClient.java WhatDoesThisDo.java Animals.java Here is the class hierarchy for the Animals example.

Week 13 (November 9 - November 13)
Monday	An `interface` is a purely abstract list of methods (no method bodies) A class can declare that it `implements` an interface, which means it must provide implementations for all the declared methods Creates a subtype relationship between the implementing class and the interface A class can only extend one other class, but may implement many interfaces You can think of an interface as a representation of a set of capabilities Example: The Zoo can hold any kind of object, provided it has the capabilities represented by the Creature interface (returning its species, making noise) Example: Our graphing calculator can plot any kind of function, provided it has the capability of returning a y-value for a given x We say that `GraphingCalculator` is loosely coupled to the main method and the concrete function types when we create new function types, we don't have to modify the GraphingCalculator Example: Factoring the common code from `SineFunction`, `CosineFunction`, and `TangentFunction` into an abstract superclass `AnyTrigFunction`	ZooTest.java graphing_calculator.zip (This is a complete Eclipse project you can import; alternatively you can create a new project and drag the packages into the src folder. There are main() methods to run in `bad.GCMain` and in `good.GCMain`.)	zyBook Sections 9.11 - 9.12
Wednesday	Understanding the String `compareTo` method and the Java `Comparable` interface The Java `Arrays.sort` method can sort any type of object as long as it implements the `Comparable` interface We say that a component A is tightly coupled to component B if making a change in A forces you to make changes in B Interfaces are used to "decouple" components For Arrays.sort, it cannot be tightly coupled to the classes being sorted When the code was written, it would be impossible for the programmer to predict all the types of objects (such as our Contact type) that might need to be sorted Another example: The Swing GUI framework can invoke any event handler in our code, provided that it implements the `ActionListener` interface Another example: In lab 2, the plotter is tightly coupled to the RabbitModel class When making a new kind of model, we had to modify the RabbitModel class itself Better: have the plotter refer to an interface representing the capabilities it needs to plot the model (`getPopulation`, `simulateYear`, and `reset`) Using the `Comparator` interface Interfaces vs abstract classes The main purpose of inheritance is to reuse code The main purpose of an interface is to reduce coupling Use an abstract class when you specifically need a partial implementation that can be extended by subclasses Use an interface when you don't need a shared implementation Interfaces are much more flexible, since a class can implement many interfaces without constraining its inheritance hierarchy	ContactSorter.java Contact.java PhoneContact.java TextContact.java EmailContact.java FirstSwingExample.java ComparatorExample.java	zyBook Section 9.13
Friday	Case study: redesigning the graphing calculator so that function types can report their own parameters and descriptions Defining a Descriptor type for a parameter and string description Adding additional capabilities to the SVFunction interface Creating an abstract class for the common code among the function types Options for subclasses to initialize the data in the abstract class Constructors Additional protected methods Don't drink too much Kool-Aid Inheritance isn't always the right solution is-a vs has-a relationships A Car is a Vehicle (suggests inheritance) A Car has a SteeringWheel (suggests composition) Composition is often more flexible and gives you better control	graphing_calc_better.zip See the `ugly.GraphingCalculator` for example using explicit type-checking with `instanceof` and downcasts. See the `better` package for a redesigned solution using an interface to describe the function parameters. Here are some notes on our redesign of GraphingCalculator. Here is the class diagram for the SVFunction hierarchy. NoDupListWithInheritance.java NoDupListWithComposition.java

Week 12 (November 2 - November 6)
Monday	Introduction to inheritance Extending a class (the `extends` keyword) to create a subclass or derived class The subclass inherits the attributes and methods of the superclass However, private instance variables or methods are still inaccessible Use the `protected` access modifier to allow subclasses to use or override a method without making it public `protected` is rarely used for variables, since that would break encapsulation A subclass can re-implement a method from the superclass, called overriding The class `java.lang.Object` is a superclass for every Java class No multiple inheritance: Every class except Object has exactly one "parent" class (immediate superclass)	InheritanceTest.java	zyBook Sections 9.1 - 9.4
Wednesday	Inheritance, continued When a subclass is constructed, the first thing that happens is that a superclass constructor is called If the superclass has a default constructor (no arguments), the compiler can do this automatically More often, the programmer has to explicitly invoke a superclass constructor using the `super` keyword Polymorphism: a variable declared with type T can refer, at runtime, to an object that is a subtype of T Every variable is associated with two types: The declared type is the type in the variable declaration never changes is what the compiler sees The runtime type is the type of the object that the variable actually refers to may change from moment to moment as the code executes cannot be seen by the compiler The code that actually executes when a method is called depends on the runtime type The VM starts at the runtime type, and searches up the class hierarchy until a matching method is found This mechanism is called dynamic binding or dynamic dispatch, since it happens dynamically as the code executes	ConstructorTest.java InheritanceTest2.java	zyBook Sections 9.5 - 9.7
Friday	Downcasting an object The compiler sees only the declared type of a variable It is possible to insert a downcast to allow the compiler to treat a variable as though it had a different declared type A cast doesn't change the type of an object (which cannot change) A cast may fail at runtime with `ClassCastException` if runtime type is incompatible with the cast Can check the runtime type before a cast using the `instanceof` operator or `getClass` Explicit type-checking like this is needed only rarely in well-designed OO code One place you do need it is when overriding the `equals()` method of Object Abstract classes An `abstract` method has no body If a class contains one or more `abstract` methods, then it must be declared `abstract` as well Abstract classes cannot be instantiated An abstract class usually has protected constructors, since only subclasses can call them An abstract class is a partial implementation that needs to be extended Use an abstract class for code that is common to two or more subclasses when it doesn't make sense for those classes to extend each other Neither `Cat extends Dog` nor `Dog extends Cat` makes any sense Instead, `Cat` and `Dog` can extend an abstract class `Pet` with the common code More about superclass constructors: Never re-declare instance variables in a subclass Use the superclass constructor to initialize them Use the public API methods to access them Add `protected` accessors if needed	InheritanceTest3.java	zyBook Sections 9.8 - 9.9

Week 11 (October 26 - October 30)
Monday	Tail recursion is when the recursive call is the very last thing that happens in the method Local variables in the call stack will never be used again, so... ...it is easy to replace the recursion with a loop that just updates the local variables See the nonrecursive version of binary search When not to use recursion Calculating fibonacci numbers recursively requires the same previous values to be recalculated over and over again Dynamic programming is the technique of converting a recursive algorithm to an iterative one by building up a table of previously calculated values Introduction to sorting In practice, we use the built in library methods (such as `Arrays.sort` or `Collections.sort`) Sorting algorithms continued to be actively studied because they are good examples of algorithm design and analysis Two examples of easy but inefficient sorting algorithms Selection sort Insertion sort	BinarySearch.java FibonacciTest.java SelectionSort.java InsertionSort.java	zyBook Sections 6.19, 6.20, 8.10
Wednesday	Using a divide-and-conquer strategy for sorting Implementing a merge algorithm The merge sort algorithm Introduction to algorithm analysis Running time of selection sort is proportional to n², where n is the size of the array Running time of merge sort is proportional to n log n	MergeSort1.java MergeSort2.java	zyBook Section 8.11
Friday	No class

Week 10 (October 19 - October 23)
Monday	Recursion is when a method calls itself. Every method call has its own local variables Local variables live in an activation frame on the call stack The frame includes a "return address", where to resume execution when the method returns Thinking recursively Reduce the problem to a smaller instance Identify a base case Believe that it will work Our initial examples of recursion are simple problems that we could easily solve with loops... ...however, it turns out to be a powerful problem-solving technique for many problems that are very difficult to solve with loops Infinite recursion and `StackOverflowError` Using extra parameters in `PalindromeChecker` to keep track of the start and end of the substring	Step through the `countUp` method in the debugger (or pythontutor) to visualize the frames in the call stack. CountUp.java RecursionExamples.java PalindromeChecker.java InfiniteRecursion.java JimGoesUpStairs.java	zyBook Sections 8.1, 8.2, 8.3, 8.8
Wednesday	Some problems that are very hard to write with loops are very simple using recursion Towers of Hanoi Listing permutations Searching a file hierarchy	TowersOfHanoi.java Permutations.java FileListerExamples.java	zyBook Sections 8.4 - 8.7
Friday	More file hierarchy examples - using an extra parameter to keep track of "depth" Recursion with arrays The divide-and-conquer strategy Split the problem into two parts Solve each part (usually using recursion) Combine the parts into a solution	FileListerExamples.java ArraySum.java ArraySumVerbose.java BinarySearch.java

Week 9 (October 12 - October 16)
Monday	The class `ArrayList` Generic type parameters in Java classes Using an ArrayList for reading input Comparing arrays and ArrayLists Wrapper classes for primitive types, autoboxing	ArrayListExample.java FindMedian.java FairDieCheckerWithArrayList.java	zyBook Sections 6.14 - 6.16
Wednesday	How an ArrayList works behind the scenes it's a partially filled array when no more room, a new backing array is created that is twice as big More examples of array modification Returning a new array vs modifying a given array Doing deletions while iterating is tricky In some cases (e.g. moving even numbers to front) the modification can be done "in place" (without creating a temporary array) Shifting even numbers to front, odd numbers to end: to avoid clobbering all the odd numbers, can use an auxiliary ArrayList to store them	IntList.java IntListTest.java ArrayRemoveOddNumbers.java	zyBook Sections 6.10 - 6.13
Friday	Two-dimensional arrays The first index is always the row! In Java, a 2D array is really an array of arrays Each element is one row (a 1D array) The number of rows is `arr.length` The number of columns is `arr[0].length` Making a copy of an array shallow copy - copy array values only deep copy - make copies of the objects they refer too as well (an assignment never makes a copy of anything in Java) Methods such as `Arrays.copyOf` always make a shallow copy To make a deep copy, you generally have to use a constructor to make a duplicate of each object in the array Don't use `Arrays.copyOf` for 2D arrays!	ArrayExamples2D.java ArrayCopy2DArray.java	zyBook Section 6.7

Week 8 (October 5 - October 9)
Monday	Reading text files is just like reading input from a string or any other input stream 1. Opening a file means asking the operating system to find the device and start buffering the data Two ways to open a file Construct a Scanner from a `File` object representing the path to your file, or Create a `FileInputStream` object using the path to your file (and then construct a Scanner from it) 2. Method that opens file needs the declaration `throws FileNotFoundException` (or `throws IOException`) 3. Remember to close the Scanner when working with files! A `File` object isn't actually a file, but is a Java object with methods for working with file names and paths An exception like `FileNotFoundException` that requires the `throws` declaration is called a "checked" exception the declaration says, in effect, "this method might cause this type of exception to occur" Finding files A program always has a working directory For Java programs run within Eclipse, the working directory is always the project directory To open a file that is not in the working directory, use a relative path or absolute path to the file Text files are usually organized into lines ended by one of the platform-dependent line termination characters To read a file line by line, use the scanner methods `hasNextLine()` and `nextLine()`	LoopToReadFile.java FileTest.java ReadFileLineByLine.java (For the examples above you'll need a text file in the project directory containing some data to read, e.g. nums.txt and scores.txt)	zyBook Sections 7.1 - 7.4
Wednesday	Arrays! An array is a sequence of elements that can be accessed by index (like characters in a string) Can be of any Java type Fixed in length (but length can be computed during runtime) Mutable Arrays are objects and are created with the `new` keyword A newly created array has default values for all elements (zeros or nulls) There are no useful built-in methods, use the `.length` attribute to get the length The `Arrays` class has many static methods for working with arrays, such as `toString` and `sort`	ArrayExamples.java ArrayExamplesWithLoops.java	zyBook Sections 6.1, 6.2, 6.3, 6.8
Friday	Why we can't write a method to swap two ints Primitives are always passed to a method by value Objects are always passed to a method by reference A non-primitive method parameter is always an alias, and the object it refers to can be modified by the method However, modifying the parameter itself has no effect outside the method Copying arrays of objects A shallow copy makes a new array and copies over the references A deep copy makes a new array and creates a copy of each object that the references point to Java methods such as `Arrays.copyOf` only make a shallow copy Using an array as a collection of related variables	ArrayCopyExample.java ArrayDeepCopy.java FairDieChecker.java	zyBook Sections 6.4, 6.5, 6.6, 6.9

Week 7 (September 28 - October 2)
Monday	The `for` statement Initialization, condition, and the "update" step are all moved onto one line You can see at a glance how the loop is being controlled and how many times it will execute Scope of variables declared within a block Hand-tracing a loop The idea of a "search" problem Once you find something, don't un-find it! Ask yourself: do I need to examine all the data, or can I stop once I see what I'm looking for? Using a `return` statement to exit a loop Using the debugger to diagnose an exception	ForLoopExamples.java	zyBook Sections 5.3, 5.4, 5.5
Wednesday	Recap: when writing a loop Am I iterating over a fixed sequence or range of values (use a for-loop) or is the number of iterations difficult to bound (use a while-loop) Do I need to examine all the input, or can I stop when I find what I'm looking for (this is a "search" type of problem, potentially use an early exit) Exiting a loop early using the `break` statement unconditional jump to end of loop not evil, but use sparingly harder to analyze loop because early exit bypasses loop condition The `continue` statement unconditional jump to beginning of loop mostly evil, try to avoid, difficult to use correctly may, or may not, bypass the "update" step of the loop Using the debugger to break into an infinite loop Using a Scanner to parse a string The methods `hasNext`, `hasNextInt`, etc A loop to read input almost always has the form while there is still another item in the input stream get the item do something with it	MoreLoopExamples.java ContinueStatementExample.java LoopToParseString.java	zyBook Sections 5.6, 5.8
Friday	Reading input from the console Can't detect end of input using `hasNext` or `hasNextInt`, because the method won't return until something is entered! Need a recognizable "sentinel" value for console input Nested loops The `break` statement with nested loops	LoopToParseConsoleInput.java NestedLoopExamples.java	zyBook Sections 5.6, 5.7

Week 6 (September 21 - 25)
Monday	Using an "early return" from a conditional Boolean operators, continued De Morgan's Laws Short-circuiting	LeapYearCalculator.java	zyBook Sections 4.6, 4.7, 4.8
Wednesday	Loops! The `while` statement Identifying initialization, condition, and body of a loop While-loops vs. for-loops Use `for`-loops when counting with an index or iterating over a fixed sequence of items Use `while`-loops when the number of iterations is unknown or difficult to compute	WhileLoopExamples.java GuessingGameWithLoop.java GuessingGameWithLoopMain.java	zyBook Section 5.1
Friday	No class

Week 5 (September 14 - 18)
Monday	Conditional statements in Java Condition must be a `boolean` expression Relational operators for comparing numbers Problem-solving strategy: Do an example by hand Write down the basic logic in pseudocode	Order.java OrderTest.java MaxOfThree.java	zyBook Section 4.1
Wednesday	Nested conditionals, con't Using helper methods to simplify code "procedural decomposition" again Use `if...else if...else if...else....` for mutually exclusive actions Use sequential `if` statements when you want all conditions to be checked When to use `else` vs. `else if` at the end The `switch` statement	GuessingGame.java GuessingGameMain.java GradeCalculator.java SwitchExample.java	zyBook Sections 4.2 and 4.3
Friday	Using `==` for objects only tests for identity, not "sameness". When to use `==` (or `!=`) For integer and char types Checking whether an object reference is `null` For `enum` types (we'll see them later on) Use `Math.abs(d1 - d2) < ERR` to test whether two `double` values are the "same" Use `.equals()` for Strings or `.equalsIgnoreCase()`, or `.startsWith()`, or `.endsWith()`, or `.contains()` Using `==` or `!=` for booleans is almost always redundant! `if (isResident == true) {...}` should be written `if (isResident) {...}` `if (isResident == false) {...}` should be written `if (!isResident) {...}` The boolean operators `&&` (and), `\|\|` (or), and `!` (not)	FloatingPointEqualsTest.java OrderUI.java GradeCalculatorWithInputCheck.java	zyBook Sections 4.4, 4.5, 4.6

Week 4 (September 7 - 11)
Monday	Client view: the public API Developer view: instance variables, method implementations (private) Encapsulation: data and implementation details are hidden from clients Clients only depend on the public API Incremental development, con't Start with simple, concrete examples that you can do on paper (or on your fingers) The steps of a simple example show you how to write the code You can use your examples for test cases too An object can have instance variables that are also objects ...remember to initialize them! A `NullPointerException` is thrown when you try to invoke a method on an object reference that is `null` This is usually caused by forgetting to initialize something in your constructor Introducing the JUnit framework for unit tests	Car.java CarTest.java GasTank.java GasTankTestJUnit.java	zyBook Section 3.7
Wednesday	Guidelines for instance variables: Instance variables store the "permanent" state of an object. Use local variables for temporary values within methods. Avoid redundant instance variables Make sure every instance variable is documented and initialized in the constructor All instance variables should have consistent and correct values at the end of each method Accessor methods should never modify instance variables Avoid shadowing (don't name a local variable the same as an instance variable) Don't use the `static` keyword when defining instance variables (we use `static` for constants, and sometimes for methods, but almost never for variables)	BadSimpleRectangle.java BadSimpleRectangleTest.java BadCar1.java BadCar1Test.java BadCar2.java BadCar2Test.java BadCar3.java BadCar3Test.java
Friday	The `this` keyword is usually redundant can be used to distinguish between an instance variable and a local variable with the same name (See the first constructor for GasTank2.java) can be used to call one constructor from another (See the second constructor for GasTank2.java) can add clarity to a method that interacts with another method of the same type (See the `stealFrom` method of GasTank2.java) The `static` keyword In general, a static attribute is associated with the class, rather than with instances of the class A method may be declared `static` if it does not refer to any instance variables (result is just calculated from arguments) Example: utility methods such as `Math.max` We usually declare constants to be `static final` Using `static` for variables is usually a mistake (See BadCashRegister.java.) The `final` keyword A final variable's value can't change Final instance variables must be initialized in the constructor	GasTank2.java BadCashRegister.java BadCashRegisterTest.java	zyBook Section 3.8 and 3.10

Week 3 (August 31 - September 4)
Monday	Constructing objects Strings are unusual in Java because They do not have to be constructed using the `new` keyword They are immutable Exploring a simple class - `java.awt.Rectangle` In the code `Rectangle r = new Rectangle(10, 20),` the `new` keyword: Allocates a blank chunk of memory Runs the constructor code to initialize it Returns a reference to it Implementing our own class! Instance variables represent the object's state (also called fields, attributes, or member variables) Constructors initialize the instance variables Methods provide the operations we want Mutator vs accessor methods Accessor methods return information about the object's state (but do not modify it) Mutator methods modify the object's state (and usually return `void`) A method can be both, but it's rare (Example: the Scanner methods such as `next`, `nextInt`, etc.) A class with no mutator methods is called immutable (Example: the class String)	RectangleTest.java SimpleRectangle.java SimpleRectangleTest.java	zyBook sections 3.1 - 3.3
Wednesday	Recap: a typical class definition has Instance variables - the object's state Constructors - initialize the instance variables Methods - the operations we want Methods are usually either Accessors - return information about the object's state (without modifying anything) Mutators - modify the object's state (usually return void) Instance variables vs. local variables An instance variable is declared outside of all methods and represents a "permanent" part of the object's state A local variable is declared within a method and is used for temporary calculations within that method Typical steps for defining a class Design the public API Write stubs for the methods and constructors, and document them Write some unit tests or usage examples Start thinking about instance variables Look at the accessor methods for inspiration Make sure each instance variable is initialized in the constructors Write the method bodies Create further tests Steps 4 - 6 may need to be iterated many times Always start with simple test cases or usage examples before writing too much code!	CashRegister.java CashRegisterTest.java	zyBook sections 3.3, 3.4, and 3.9
Friday	Encapsulation: An object's data and implementation details are hidden from clients In particular, we almost always make instance variables `private` Why encapsulation? Code needs to evolve for bug fixes, performance improvements, feature requests Example: adding a method `getTaxableSubtotal` to our CashRegister, we eliminated the `subtotal` instance variable If instance variables are accessible to clients, we can no longer guarantee correctness and consistency of the internal data Example: the tax added should always be consistent with the taxable items entered; if clients can access the `tax` instance variable, they could (accidentally or maliciously) make the tax inconsistent with the taxable items Unlike local variables, instance variables have default values Numeric variables (including `char`) default to zero Boolean variables default to false Object variables default to `null` Instance variables can also be initialied inline using field initializers, if the value does not depend on the constructor parameters	GasTank.java GasTankTest.java	zyBook sections 3.5, 3.6, 3.11

Week 2 (August 24 - 28)
Monday	More about floating point numbers Rounding vs casting Using `Integer.parseInt` to convert String to number Mathematical methods (functions) from the class `Math` Calling methods Parameters are the variables appearing in the method declaration Arguments are the values you pass in when calling the method (can be any expression of compatible type) Arguments must match parameters in number, order, and type A method is overloaded if it has multiple versions with different parameters This is how Java gets the effect of "optional" method arguments	FPTest.java	zyBook sections 2.6 - 2.8
Wednesday	Defining constants as `public (or private) static final` Avoid embedding mysterious literal values in code Instance methods vs static methods A static method is one whose result depends ONLY on the method's arguments Invoked using the class name, as in `Math.sqrt(25)` An instance method is one whose result depends on the method's arguments AND on the internal state of the "target" object Invoked using an object reference (the "target"), as in `name.charAt(3)`, where `name` is a String variable Experimenting with String methods Using a Scanner to parse strings Void vs non-void methods Some methods are defined to return a value to the caller, such as `Math.sqrt` or the String `charAt` method Some methods are defined to produce a "side-effect" (change the state of the world somehow), such as `System.out.println` These methods are declared with a return type of `void` Defining our own static methods	StringTest.java OurMethods.java OurMethodsTest.java	zyBook sections 2.9 - 2.12
Friday	Developing methods incrementally Start with simple, concrete examples Create method stubs for your API Write a simple description for each one Write a few test cases Test early, test often! Use helper methods* to reduce duplicated code*	Solver.java SolverTest.java	zyBook sections 2.9 - 2.12

Week 1 (August 17 - 21)
Monday	Introduction Who should take Com S 227? Syllabus overview Powerpoint slides from first day		Log in to Canvas! Read the syllabus! Check out the zyBook! Read section 1.1 Try Piazza!
Wednesday	Syllabus overview, con't Role of the compiler and the Java Virtual Machine (Java runtime) A first Java program	Greeter.java	zyBook sections 1.2 - 1.5
Friday	Introduction to Eclipse A class is a definition for a type of object In our "Hello, World" example, the class itself serves no purpose except as a container for the `main` method This is not typical of Java classes! Primitive types vs object types Picturing variables: stack frames and the heap Visualizing code execution with Pythontutor Arithmetic operators Integer division and the mod operator `%`	Change.java	zyBook sections 2.1 - 2.5