Mr. Gilmore's Course Pages

Welcome to SJP's AP CS A class website!

April 12: Visualizing Sorting

This year, you will be responsible for three sorting techniques. In order of complexity they are insertion sort, selection sort, and merge sort. The links below offer some excellent visual help in understanding how each sorting technique works.

There's sound and animation with most, so be sure your sound is on.

1. Insertion Sort with a deck of playing cards
2. Insertion Sort with integers
3. Selection Sort with a deck of playing cards
4. Selection Sort with integers
5. One page with tons of animations of different sort algorithms.

You can run multiple ones at once to see a speed comparison and also see the code driving the sorting. One warning: the initial data set matters a lot when comparing sorting. Is the array already partially sorted? Or not? Is the array small? Or huge. Some algorithms will be slower on small data sets, but as the data set grows in size, the time taken grows very slowly. They offer an advantage on big data sets. One task you have as you move through these tutorials and your reading is to set in your mind which of the three algorithms we're looking at is good in which circumstances.

March 25: Exam Coming Up and Extra Credit

The next exam will be on Monday, March 29. It will be all multiple choice; 50% of the examination will be on Gridworld; 50% will be questions that simply rely on your accumulated knowledge of Java, though you can expect a somewhat high concentration of class and program design questions.

Those interested in extra credit can solve the following Gridworld problem. It is worth 50 points and is due no later than Monday BEFORE the bell rings. As we all know, one peril we face in the modern world is zombies. Your task here is to simulate this peril, showing how long a Human population lasts in the presence of zombies. You need to create a Human class and a ZombieRunner class. Populate the world with Humans and with one Human who has been transformed into a zombie. We can recognize zombiefied Humans because they have turned into festering masses of decaying flesh with serious black fungal growth. Since they represent a danger, we will represent them by having them appear red. Non-zombie Humans can come in a variety of colors, but not red.

A Human's usual behavior is wandering around enjoying him or herself. They move randomly like Critters. But once zombiefied this changes. They turn red and if non-zombiefied Humans (one or more) are immediately adjacent to them, a zombie chooses one randomly and attacks, converting it into a zombie. Upon being attacked, a Human changes to the color red, waits 20 calls of its act method without moving, and then begins acting as a zombie. If a zombie is not adjacent to a Human and has passed its initialization phase of 20 turns, it begins to move randomly like a Critter until it finds itself next to a non-zombie. But, it moves very slowly-- only 30% of the time we'll say. For extra extra credit (10 points), make it so that a normal Human can "see" a zombie two moves away and move away from it. Add a comment explaining how this changes the results of the simulation.

March 22: Thinking About Critters

When faced with a task like writing a QuickCrabCritter class, begin by considering the Critter's desired behavior. What is it supposed to do? Write down for yourself a clear explanation of this behavior, and make that explantion the comment at the top of the class.

Now consider how that behavior is the same as that of a CrabCritter and how it differs. Your QuickCrab class will extend CrabCritter. What behavior is the same? Is it interested in the same actors (that is, actors in the same locations) as is a CrabCritter? If so, leave getActors alone -- the QuickCrab does the right thing. If not, override getActors so that QuickCrab chooses the right actors to pass on to processActors. Repeat this procedure for each of the methods that characterizes a Critter -- that is, for each of the methods that Critter's act() method calls. Override only those that must implement different behavior. Usually, there's remarkably little code to write. The work is not typing! The work is thinking carefully about which methods to override and then writing a few -- very few -- lines of code to implement the behavior you want.

Begin the coding of a method by writing a series of one line comments about what you want to do. Until you have a clear series of actions you need to implement, writing code is absurd. It's like exiting an airplane before it's landed. It's like scheduling the playoffs before the regular season. It's like -- well, I was going to make a political comment about elections but I'll stop instead. You get the idea. Until you have a clear series of steps that lead to the solution you want, writing code makes no sense.

March 19: Short Handwritten Explanation of Exceptions

For each of the following, explain what programming error would cause the exception. I expect two or three sentences of explanation per exception, so an example of a specific problem might help for each.

1. NullPointerException,
2. ArrayIndexOutOfBoundsException,
3. ArithmeticException,
4. ClassCastException,
5. IllegalArgumentException.

March 18, 2010: Don't Ignore Previously Written Code

As you work through these problems, don't ignore source code that you have already written for previous problems. Sometimes all you need to do is tweak it. That's fine if it's your own code. Also feel free to use ANY source code in the Gridworld code distribution itself. Copy and modify a method if you want. For example, the class AbstractGrid contains implementation code for getNeighbors, a method required by the Grid interface and accessible to the class BoundedGrid which extends AbstractGrid. So take that code and modify it if you want for BlusterCritter. (I'm not suggesting that's the best alternative; but it's one alternative).

March 11, 2010: Knight's Tour (as a Critter)

The Knight's Tour is a classic chess problem. Wikipedia notes that it is mentioned as early as the 9th century "in the highly stylized Sanskrit poem Kavyalankara written by the 9th century Kashmiri poet Rudrata, which discusses the art of poetry, especially with relation to theater (Natyashastra). As was often the practice in ornate Sanskrit poetry, the syllabic patterns of this poem elucidate a completely different motif, in this case an open knight's tour on a half-chessboard."

A knight's tour consists of moving the knight exactly 63 times so that it ends up having visited all 64 squares of a chess board exactly once. A human might take quite a while to hit on a successful tour -- if he or she is not careful, the knight will end up blocked in corner with nowhere to go. A computer could simply try a tour, back up when blocked and try again, and repeat this pattern until by brute force it finds a path. This could take a computer entire seconds -- they're fast -- whereas it might take a person months of continuous effort. However, there is an algorithm that lets a programmer ensure that the problem is solved extremely quickly -- in what computer scientists call "linear time". This means that it takes 63 moves on a board of 64 squares, and 99 moves on a board of 100 squares, and 999 moves on a board of 1000 squares, etc.

Below is a slow-moving animation of a linear algorithm that I implemented using Gridworld Critter as a base class. The algorithm is known as Warnsdorff’s algorithm -- I didn't know that when I first had to solve this problem and it was a fun moment when I hit on the solution, implemented it, and saw my program zip to a solution immediately. The principle behind Warnsdorff's algorithm helps in solving many analytical reasoning problems. My use of it also raises an interesting question: will the solution work for all possible starting positions on the board. How could we answer this question?

The animation is slow moving because I'd like you to take the time to guess the next move at least a few times. And because I was taxing my processor with other tasks while taping the run. As we saw in class, the animation could be (almost) lightning fast. Remember that a Critter object:

1. gets Actors (here, numbers in the squares already visited)
2. processes Actors (here we could do fun stuff with changing number colors)
3. gets possible move locations (where can a knight move?)
4. selects a move location (this is the algorithm's critical step)
5. makes the move

So I simply extended Critter and overrode the necessary methods. After we examine the code in class, I'm going to have you modify processActors to do something more than the current code does.

March 10, 2010: Battling Bugs and Chomping Critters

Some Gridworld videos from YouTube....

February 2, 2010: Interfaces and Polymorphism

The concept of an interface is the most complex idea we've yet encountered. But, in fact, there's not much to them. They're simple and powerful. We need to understand

1. what they are
2. how to use them

What is an Interface

In Java programming, we use the word interface in two different ways. In the general way, the interface of any class is the public methods that we can call to manipulate objects of that class. So, part of the interface of the String class is the method substring(int from). The parts of a class we cannot see and directly manipulate are what we refer to as a "black box." A black box does stuff for us, but we don't know how. In fact, the way substring(int from) works is also a black box -- we just know how to call it.

Chapter 9 in Java Concepts deals with a second meaning of the word interface. In this case, an interface is quite simply a contract. An interface file is typed up just like a class file, but the methods just consist of method signatures WITH NO BODIES. Anyone who writes an actual class that implements our interface MUST implement all the methods specifed in the interface file. That's the contract. In addition, we can add some data members, but they are all by default public, final, and static -- but data members of an interface are unusual.

Here's a sample interface:

public interface SoundMaker
{
String makeSound();
}

So, any class which implements the SoundMaker interface MUST have a method (public) called makeSound() taking no arguments and returning a String. It's up to the creator of the class to decide what the implementation is.

Here's a complete sample class implementing SoundMaker:

public class SilentAnimal implements SoundMaker
{
public String makeSound()
{
return ""; }
}

Here is another complete class implementing the same interface. Of course, a class can have methods in addition to those specified in the interface.

public class Cow implements SoundMaker
{
public String makeSound()
{
return "mooooooooooooooooooooooo"; }

public String generateMethane()
{
return "generated a quantity of methane";
}
}

How Do We Use Interfaces?

Suppose we own a pet store. We might want to represent each of our species of animals by a class. To avoid redundant code, we'd probably implement a class Animal and then have subclasses for Cat, Dog, Ferret, etc. But let's ignore inheritance for the moment. We could use interfaces in this context instead. Animal could be the interface, and each species could be represented by a class that implements the Animal interface. Then we could have one massive ArrayList containing Animal objects. The actual types could be Cat, Dog, Ferret, etc., but since they're all Animal objects we can iterate through the ArrayList and call any Animal method we want on each object and nothing will break because the ArrayList contains objects of classes that implement the Animal interface and thus each object in the list will be able to execute any method of class Animal.

January 22, 2010: Final Extra Credit of Quarter 2

Any or all JavaBat String-3 problems can be done for extra credit of 6 points apiece.

On a completely unrelated note, I hope to trade in my Honda Civic for one of these when they become available.

January 5, 2010: Assignments in JB

The following String problems from JavaBat will be due this week. It might help to review the basic String operations covered in the textbook or to look through the String API in the online Java API. Remember that long, convoluted code is almost always a sign that you're missing some simpler strategy. Also, get ahead when time permits. The String 2 problems are harder, and I'll be adding some String 3 ones soon.:
Wed: (all from String 1) firstHalf, nonStart, theEnd, endsLy,middleThree, lastChars, seeColor, extraFront, startWord. Thur: (all from String 2)  doubleChar, countCode, bobThere, repeatEnd Fri: (all from String 2) prefixAgain, sameStarChar, plusOut, catDog

December 12, 2009: Long Term Extra Credit Options

When we return from Christmas break, we'll turn our attention to JavaBat problems involving Strings and loops. Since some of you want extra credit options, I'll offer a batch of JavaBat problems. The one proviso is that you agree not to discuss the problems with anyone else; I'm trusting that the work you do is your own. This trust is critical. If you violate it, then I can't offer extra credit.

The following String-1 JavaBat problems are extra credit (7 points apiece): makeAbba, extraEnd,withoutEnd,left2, withoutEnd2, nTwice, hasBad, conCat, frontAgain, without2, withoutx. They're the middle column problems.

The following String-2 problems are extra credit (7 points apiece): countHi, endOther,xyBalance,repeatFront,xyzMiddle, zipZap, wordEnds (again, the middle column).

In addition, all the Logic-2 puzzles can be done for the same 7 points apiece of extra credit.

I'll check the extra credit problems on January 5, 2010.

December 8, 2009: Decisions and Loops: Exercises

So far our exercises have been drawn from Horstmann's Java Concepts and each required you to write an entire class (in fact, usually two) to run your program. For chapters 5 and 6 we'll alter that pattern and focus on

• pen and paper exercises emphasizing proper use of booleans, and
• JavaBat exercises which require you to write a short method accomplishing a specific task.

Task one will be to register at www.javabat.com with a username that MUST be your SJP email. Under preferences set your last name, first name. Then under the preferences teacher share section, share your results with me by entering my SJP email address bgilmore@stjohnsprep.org

Carefully check to see which exercises are due; get ahead when you can, because you never know when you might get stuck on a problem. Any problem that has (due start) after it is due at the moment the bell rings to start class. Any problem that has (due 20) after it is due during class and I guarantee you will have at least 20 minutes of class time to work on it. If another number appears, that's the number of minutes I guarantee.

For those curious how JavaBat works, I'd guess that the author Nick Parlente used something called JUnit, a testing framework developed by one of the guys behind Extreme Programming. JUnit allows a programmer to create tests for each method, supplying inputs for the arguments a method might take and listing what the expected outcome is. The whole suite of tests can then be run at the press of a button in an IDE (Integrated Development Environment) such as Eclipse and each test reports success (JavaBat's green) or failure (JavaBat's red). An AP student at another school created a neat tool called JamTester that uses JUnit to a similar end. Do a web search to learn more.

Testing is important in all areas of engineering. Ever wonder how safe a Smart ForTwo is?

In the software engineering world, Extreme Programming (XP) and other "agile" development processes emphasize the importance of testing. The following is a Google Tech Talk, one revelation of which is that Google uses XP a lot, though many of the people there struggle to do it well. It's aimed at software professionals, so it might be a bit too technical in some ways, but take a look if you're curious about Google and life as a professional software engineer.

December 4, 2009: Extra Credit Options

Now that we've completed chapters 1-4 and had our exam, it's worth considering what we know. We can create objects from pre-existing classes in the Java libraries. We can write simple classes of our own to serve as blueprints for creating objects. We know a good bit about the Math class and its available methods, and can do substring operations on Strings. We're also familiar with datatypes (ints, doubles, etc.) and operations on them such as integer division. That's not exhaustive, but it's fairly complete.

Looming ahead are chapters on decisions (if/else) and loops (while) that will recap some of what we did with JKarel and move us into more complete mastery of boolean expressions.

For those in need of further developing their understanding of the material to date and in need of some multiple choice AP practice, I'll offer the following extra credit opportunities after school in room S014 from 2:35 to 3:00. If you cannot make any (or multiple) times and want an opportunity, talk to me about scheduling one:

• Monday, December 7
• Tuesday, December 8
• Monday, December 9
• Tuesday, December 10

Remember, when learning to do multiple choice AP questions, speed is not everything. Accuracy THEN speed is a good rule to follow. Speed before accuracy leads to problems.

November 15, 2009: Site with EText

I have set up the online site that allows you to read an electronic copy of the texbook. You can access the site at http://edugen.wiley.com/edugen/class/cls145212/ . As the year progresses, we will learn to use some of the tools at the site, including those that allow you to electronically submit your homework and receive instant feeback. We will not, however, be using all the available tools there since they're a bit clunky and user-unfriendly.

November 10, 2009: Java Concepts Chapter 3

What are the key lessons from chapter 3?

• In an object oriented program, a program typically consists of a number of related objects which together accomplish the job.
• The design for an object is specified in a class file, a Java source code file ending in .java created in any text editor.
• A class file has three sections in it, which we will arrange in the following order:
  1. the private instance fields
  2. the constructors (which initialize the instance fields)
  3. the public methods of the class (which specify what objects of the class can DO)
• Using public methods to access private instance fields might seem unnecessarily indirect, but it has several advantages.
  • we can later change the data type of an instance field as we wish and as long as we modify the method that accesses it, users of the class will never know the difference. This is called encapsulation. We've already seen that representing a bank balance in pennies rather than dollars has an advantage given what we know so far.
  • we can carefully error check in accessor methods to prevent stupid or malicious things from happening (e.g. a user trying to withdraw a cat from a bank account -- stupid -- or a user trying to withdraw -1000 from a bank account -- malicious but tempting.

October 15, 2009: Java Concepts Chapter 2

What are the key lessons from chapter 2?

• Java is an object oriented language. We write programs by "instantiating" objects (creating them) and then "invoking" methods (calling built-in functions). A program is composed of a bunch of interacting objects. As a result, it's easier to debug a program and reuse parts we've created. Of course, it's also a bit more difficult to keep track of the parts. But on balance, using an object oriented language results in better, more reliable code.
• A line of code to create an object is of the form:
  Rectangle mySquare = new Rectangle(1,1,1,1);
  in which Rectangle is the name of the class, mySquare is the name we're going to give to our new object, new is a keyword necessary to create a new object, and Rectangle(1,1,1,1) is the constructor, much like the Robot constructors we saw in JKarel.
• The dot operator is used to invoke a method on an object. So mySquare.getWidth() will invoke the getWidth() method of the mySquare object.
• Methods can be
  • accessor methods (which give us information but do not change the object) -- like getWidth(),
  • mutator methods that change the original object --like translate(), or
  • creator methods that return to us an entirely new object with perhaps new characteristics --like intersection().

October 13, 2009: Java Concepts Chapter 1

What are the key lessons from chapter 1?

• Java is a high level programming language. We write source code (in emacs), compile it into byte code (using javac className.java), and run it (java className). The byte code can be executed on any computer with a Java Virtual Machine (JVM) installed.
• The compiler interprets a program line by line -- even more precisely, token by token where a token is a string of characters surrounded by whitespace (with some exceptions).
• Comments are not compiled. The simplest form of comment begins with a // and anything after that till the end of the line is ignored by the compiler. A multiline comment can begin with /** and will end with */ . Multiline comments in this form can be automatically extracted by the JavaDoc tool to generate nicely formatted documentation in the same style as the Java API.
• Strings are groups of characters -- like words or sentences -- enclosed in quotation marks.
• Since a quotation mark begins and ends a string, we have trouble printing a quotation mark. If we type """ then the second mark ends the quotation and the third one begins a new one which does not end. The compiler will probably say something about an "unenclosed string literal".
• We can inform the compiler that a quotation mark is NOT in fact the beginning or end of a string, but is in fact a quotation mark that we want to print. We do this by "escaping" the quotation mark by putting a backslash in front of it as follows: \" . So now the only trick is printing a backslash.

September 30, 2009

The first reading assignment in Java Concepts is now posted. Be sure to begin reading in time to finish the assignment by the due date. Chapter 1 is an overview of the programming process, computer hardware, and some ethical issues associated with computers. We'll return to these themes througout the year. Get a good grounding now. Chapter 2 will rapidly follow; it will serve as our introduction to the Java programming language. You'll find it stunningly familiar now that you've used JKarel, but there are a few differences.

For those concerned with low grades on an assignment or two, there will be a chance for some extra credit starting with chapter 1 and 2 in Java Concepts.

September 29, 2009

Now that we're drawing to the close of our first unit -- JKarel the Robot -- it's time to take a step back and consider what the essential lessons are.

• Problem solving is best done in phases. Programming is not typing, so don't begin on the keyboard. Understand the problem. Break it into parts. Write comments to yourself about how to solve each part. Then code up a part and test to see if your solution works. Continue till you've done all the parts. See the programmer to the right? Is he programming or having a seizure?
• When coding, write short methods that perform simple, clear tasks and do not cause any side effects. A method longer than a page is a bad, bad idea. Nesting if/else statements more than three deep is a bad, bad idea.
• Format your code according to the standards we've talked about. As you write, align your curly braces correctly. Begin class names with a capital letter. Begin robot object names with a lowercase letter.
• Use sensible names for methods. For example, I saw "hitWall" as the name of a method designed to ensure that a robot doesn't hit a wall. This is obviously a bad, bad idea. "checkIt" is also a terrible name. Check what? Write clear method names, but of course avoiding abominations like anyBeepersInBeeperBag() and instead use something like hasBeepers().
• Back up your work. Save to the network and backup daily to your flash drive, or save to your flash drive and back up daily to the network. I don't care which. But I do care that you do one. I simply won't accept loss of data as an excuse for lateness of an assignment

September 9, 2009

During the year I'll use this page to keep you up to date on what's transpiring in our AP CS A course. I'll add useful resources and commentary on what's essential to gain from each of the chapters in Java Concepts. Homework assignments will be in the left panel on this site. The right panel will have links to sites and resources to help you learn Java.

Bookmark this page so you can quickly access it during the school year.