About Schedule Software

Sep 16: Intro to OO programming and Java

• What's this course about?
• Administrative stuff
• Java basics

Code discussed in lecture

• Counter.java

What's this course about?

"Problem solving via object oriented programming." Examples of problems from your experience? In this class: process images, search social networks, play games, compress files, identify clusters in data sets, solve puzzles like Sudoku, play the Kevin Bacon game on a movie database....

While those are fun (I hope), the goal of the course is to develop expertise in core programming techniques useful throughout computer science, including representation, abstraction, recursion and modularity, and concurrency. One of the most important themes in this course is abstraction:

• Identify a pattern or interaction (computational or otherwise).
• Give it a name.
• Define its interface (i.e., describe inputs/outputs and their relationships to each other)

Proper abstraction allows us to treat complex ideas as "black boxes" so that we can reason about their behavior without knowing their exact contents. For instance, we can abstract the notion of square root, giving a black box into which we feed a number and from which we receive that number's square root. We don't care what's inside the black box, as long as it preserves the input/output relationship; we could use Newton's method or another algorithm, a look-up table, or some combination.

The same analogy applies to standard interchangeable parts (a big revolution in military and industrial technology). Lots of different pieces, but with standard connections and cables, so you can hook them up as you please. Similarly with computers — USB ports, video output, headphone mini-jacks, etc.

In order to define our abstractions, we need to have a kind of notation for describing them. Ideally, we want a notation that can be read by the computer as well as by humans. In this class we will use the object-oriented (OO) language Java. Simula, a simulation language, was the first OO language. The idea is to express a simulation (or other problem) in terms of interacting objects. Sometimes those objects model things in the world, like the wildebeests that stampeded in The Lion King. It would be too complex to try to control them all directly, so they created an object for each wildebeest that contained rules for how to interact with other wildebeests and with the environment. They started them up and let them interact. They thus simulated wildebeest behavior and interaction and put it onto film.

Often objects are more abstact. But they usually have:

• Some data or information that they "know".
• Some actions that they can perform when asked (methods), usually involving the data that they hold.

Objects are a good way to perform abstraction. If the data is private (which is usually the case in Java), the only way to interact with it is through the methods. The methods become an interface between the data and the world. The exact way that the data is stored becomes invisible to the outside world, so it can be changed without breaking anything.

This ability is important, because as we will see there are often a number of different data structures that can be used to represent the data, each with its advantages and drawbacks. In this class we will spend a lot of time looking at:

• Abstract Data Types (ADTs). In spite of the name, these are collections of operations. Some, like lists, sets, dictionaries, maps, stacks, queues, priority queues, graphs, etc. have become somewhat standardized because they are widely applicable. We will look at a number of these abstractions.
• Data structures. These are concrete ways of representing data. Some examples are arrays, linked lists, binary search trees, and hash tables. We will look at all of these. We will see that an array can be used to implement most of the ADTs listed above, but for some (e.g. sets) they are much slower than other choices. We will look at the tradeoffs of choosing one data structure or another to implement each ADT.

Talk about Parnass's paper where he introduced the idea of an Abstract Data Type in the 1970s.

Administrative stuff

See http://www.cs.dartmouth.edu/~cs10/ for

• Who, when, where
• Requirements: homeworks (short assignments, problem sets), exams
• Collaboration policies (please follow the honor code)
• Schedule
• Java info

Note that SA-0 is out, just to take care of the preliminaries.

Lecture notes are there to help you, to keep you from having to write down and type in a lot of stuff that we go over in class. However, they aren't necessarily complete, and they're also simple, sometimes terse, not necessarily grammatical, etc. They're my working notes, and are not intended to take the place of the lectures or the readings. That being said, additions, corrections, and suggestions are welcome.

Java basics

You all know a programming language. For most of you it is Python. For some of you it is Java or C. Learning a second programming language is much easier than learning a second natural language like English. The first hundred pages in the book go over what we will use in Java rather formally with a lot of detail. The on-line text introduces Java in a more conversational, interactive way.

Lectures are an awful way to communicate detail. I expect you to read these sections and come to me or course staff with questions. In lecture I will try to give you a framework on which to hang the details, and a way of approaching and thinking about the language.

Dr. Java and Eclipse

We will introduce you to two systems for programming in Java. Dr. Java has an Interaction window, which lets you type Java statements and expressions and see the results immediately, sort of what most of you are used to from Python. It is great for experimentation. Eclipse is a much more powerful IDE, and supplies all sorts of help like code completion (you type a variable name and a dot and it shows you all of the variables and methods in the object referred to by that variable, with templates describing the parameters of methods) and refactoring (reorganizing your code - e.g renaming a variable, where only the references in the current scope are changed). But if you want to run a command you have to write a program to do it.

I will start using Dr. Java to demonstrate things interactively, but will move to Eclipse for more complicated programs. You may use either for any assignment.

A quick look at a Java class

We will start by skimming a Java class. The class that we will look at is Counter . An object of this class represents a counter that starts at 0. Each time the method tick() is called, one is added to the counter. When the counter reaches a pre-defined limit it "wraps," going back to 0. Such an object could be used as part of a digital timer or digital clock class.

The code for this class is here: Counter.java. We will do a quick overview - class declaration, variable declarations, method declarations, return types, parameters. Note in particular that blocks of statements are defined via curly braces {}, not indentation (like Python).