CS 10 | Problem solving | Spring 2022 CS 10: Problem Solving via Object Oriented Programming Spring 2022 About Schedule Software Intro [next] What's this course about? Administrative stuff Java setup Our first program Our first (real) class Java notes All the code files for today: Blob.java; Blob0.java; Blob01.java; Blob02.java; BlobDriver.java; BlobDriver2.java; HelloWorld.java Slides from class What's this course about? "Problem solving via object oriented programming." Examples of problems from your experience? In this class we will: process images/video, characterize social networks, play games, compress files, analyze text.... While those are fun (I hope), the goal of the course is to develop expertise in core, widely useful computer science concepts, including representation, abstraction, modularity, recursion, 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 about without knowing their exact content or worrying about the particular implementation. 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 correct input/output relationship; for implementation we could use Newton's method or another algorithm, a look-up table, or some combination. The points is that once the square root routine is written and debugged, we can use it in other tasks without thinking too much about what the square root routine is doing. 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 (are those still a thing?), 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 or Orcs in Lord of the Rings. It would be too complex to try to control each wildebeest or Orc directly, so the movie designers created an object for each creature that contained rules for how to interact with each other and with the environment. The movie designers then gave hundreds of creature objects a geographic starting point, started them up, and let them interact. The designers thus simulated the behavior and interaction of hundreds of creatures without hand-crafting each creature's behavior. Objects can be abstract, but they usually have some common characteristics: Some data or information that they "know". Some actions that they can perform when asked (called methods), usually involving the data that they know. Look back at the examples above — what are the types of data and actions? 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 object's 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 that relies on the object (and in the real world, non-trival code will change over time, guaranteed). 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. ADTs do not specify how they must be implemented, they just specify the operations that can be performed. 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 and how they can be used to solve problems. Data structures. These are concrete ways of implementing ADT operations. 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. Administrative stuff We'll be using Canvas as the main organizational point for the course. Because it's a bit easier for me, and more importantly because they will then persist publicly beyond the term, the actual course notes will be maintained on my own personal web site (as you can see from this page). There will be some cross-referencing within my web site and between Canvas and my web site; hope that goes smoothly enough. Stuff to look at now: Who, when, where Requirements: homeworks (short assignments, problem sets), section meetings (programming drills), exams Collaboration policies Honor code Schedule Software Note that SA-0 is out, just to take care of the preliminaries. In particular, our section meetings will start shortly to help you get up to speed on Java ASAP, so and we need your availability info in order to assign sections. Lecture notes are here 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 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. I will provide source code for the programs we go through in class, but in many cases much of the class will be spent interactively building them up (or tearing them apart). The best way to learn the material is by doing it (that's why we have homeworks!), and I will try to simulate that process as best I can within the time constraints and so forth. Java setup You all know a programming language. For many of you it is Python. For some of you it is Java, or maybe Matlab and C. Learning a new programming language is much easier than learning a new 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. (And the Oracle site has even more.) I have started a Piazza thread encouraging everyone to point to their favorite Java intro sites, as there are a bunch of good ones out there. Lectures are an awful way to communicate such detail, and that's not really the goal of this course either — we want to think mostly about problem solving techniques. I expect you to read the Java details sections and come to me or course staff, or post on Slack, 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, driven by problem-solving applications. At the end of some lectures, I will have a "Java notes" section summarizing some of the key ideas utilized in the examples (without all the gory details). The software page has some references for Java and the IntelliJ programming environment that we will use. TAs help will be available if you have issues, and your section meeting this week will cover some fundamentals too. So for now, let's just use the remaining class time to walk through some simple example applications, to get acquainted with Java programming and IntelliJ. We will develop in IntelliJ, which is a powerful IDE (integrated development enviornment), and supplies all sorts of help like code completion (e.g., 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, unlike a global search-and-replace operation for the variable name). Unlike Python or Matlab and their interpreted environments, if you want to run a command you have to write a whole program to do it. Spend some time playing in IntelliJ. Check out the menus, practice making a few projects, adding code, and running it. We will use IntelliJ a lot this term so the sooner you feel comfortable in this IDE the better. Our first program It's pretty much required to have a "Hello world" program to illustrate a programming language. So here we go: [HelloWorld.java] public class HelloWorld {
/**
* Standard 'Hello World' first program
*
* @author Everyone who has ever written about programming and Tim Pierson too, Dartmouth CS 10, Spring 2020
*/
public static void main(String[] args) {
System.out.println("Hello World!");
}
}
This course will focus on types of data and ways to manipulate them. Here the type of data is a character string, and the manipulation is simply to write it out. This all gets wrapped up in some fairly non-beautiful but standard Java boilerplate that you'll see/write again and again (and IntelliJ helps you write with some shortcut keys). In particular, main defines the program to run, which here is nothing more than printing out the message. It can take some command line arguments, but we'll always ignore that in this course. IntelliJ compiles and runs the program, and directs the output to the console. To create this from scratch yourself, in IntelliJ select menu option "File | New | Class", and give it a name. In this course, I will always leave the Package empty, though you may want to set up packages yourself (a topic we'll briefly discuss later). To save some typing (you'll soon learn that IntelliJ can do lots of coding for you), check the box for generating the method stub for main. To use my version, download it via your browser, and then drag it into IntelliJ. I recommend configuring IntelliJ drag-and-drop options to automatically make a copy (it offers you that option when you first drag, or you can open the Preferences and go to Workspace | Linked Resources). The main program is wrapped up in a class, which is how Java structures almost everything. A class is stored in a file of the same name. But what is a class? This example isn't really much of an illustration, so let's get into that. Our first (real) class The key idea is that a class gives what is essentially a "blueprint" or a template for an entity in a program; the entity is called an object. In the blueprint analogy, the object is like a house specified by the blueprint. Defining a class does not create an object of that class, just as drawing a blueprint does not cause a house to be built (unless you're Harold with a Purple Crayon). A blueprint says that when we build a house, here's what it will be like. Similarly, a class says that when we create an object, here's what it has and what it can do. Today we'll build up a simple Blob class — something that we will eventually expand so that it can move around the screen and grow. (This is just something I made up; don't worry about any formal definition of what a blob is.) We won't actually have it be displayed graphically on the screen today (come back next time...), but let's think about what the template is, and how to handle a blob. For now, a very simple blob has a position and a size. Let's represent the position by x and y coordinates, and the size by a radius (so it'll be just a simple round blob). To be more precise, we also need to give the blueprint for what the coordinates and size are — numbers. In Java: public class Blob {
double x, y; // position
double r; // radius
} Here, x, y, and r are instance variables of the objects of class Blob; i.e., each blob object (instance) has its own coordinates and radius. Python people are used to objects having instance variables (though not declaring them up front like this); C people can think of them kind of like structs (though as we'll see, they're much more powerful). One of the biggest changes for Python programmers in moving to Java is that we have to declare variables and say what type each will hold. It isn't that Python doesn't have types. It's that Python checks them at run time. Java checks them at compile time rather than at run time. By saving all of those run time-checks, Java code is able to run significantly faster than Python code. It's also safer, in that once the compiler is happy, you know that you have the type of thing at run-time that you think you have. You'll get used to have IntelliJ tell you what you need to fix (little red 'x'es); while annoying, it's for your own good! Here, we're saying to use double-precision floating point numbers (double) to store x, y, and r (floating point means it can store a value with a fractional component, e.g., 1.5). Another numeric format is an integer (int), which cannot hold a fractional component (e.g., only 1). So our blueprint looks kind of like this: Blob x [double] y [double] r [double] In order to create a blob from this class blueprint, we use the Java keyword new: public static void main(String[] args) {
Blob bob = new Blob();
} For convenience, this main is directly in the Blob class, though we'll move it out in just a bit. We have to declare that the variable named bob (good or terrible name for a blob?) will reference an object of class Blob. We can then create an instance and have the variable reference it. We could have done those as two separate lines — Blob bob; bob = new Blob(); — but this is more compact and common. It's also safer. Only declaring the type of the variable leaves it empty — new is required to create the object. I guarantee that you will run into errors where you've declared a variable but not created an object. When you get a NullPointerException, remember my promise. The new keyword is then followed by the name of the class and any additional information for initialization within parentheses (here none, but soon some). bob [Blob] x: 0 [double] y: 0 [double] r: 0 [double] Notice that the instance variables in bob are given default values, here 0. (Note that that's the same as 0.0; the point of the double is that it can hold a fractional component, not that there must be one.) But we could change the default, e.g., having the radius default to 5: public class Blob {
double x, y; // position
double r=5; // radius
} We can then act on this instance (within the main): bob.x = 100;
bob.y = 50;
System.out.println("bob is at ("+bob.x+","+bob.y+")"); bob [Blob] x: 100 [double] y: 50 [double] r: 5 [double] Here's a snapshot of all this code, though renamed as "Blob0" because we'll be building up a more fully featured "Blob" shortly, and the filenames/classes have to be unique. Blob0.java It's actually considered bad form to directly modify an object, as that relies on the object's representation never changing. We'll go much more into encapsulation or "information hiding" later, but let's go ahead and take the first step and specify that the instance variables are protected; next time we'll explore further what exactly that means. public class Blob {
protected double x, y; // position
protected double r=5; // radius
} In addition to instance variables, a class defines methods that its objects can do. For example, let's look at how to get and set its size. public void setR(double newR) {
r = newR;
}
public double getR() {
return r;
} The public keyword says that these methods are accessible to anybody. In the setR method, the newR parameter brings in the value passed in the call, and allows the object to store it in its own r instance variable. Note that the instance variable r belongs to whatever the current object is, which is implicit in the method. (Unlike the explicit self in Python, say.) Similarly, in the getR method, the object's r instance variable is returned to the caller. So, down in the main: Blob bob = new Blob();
bob.setR(10);
System.out.println("bob's size is "+bob.getR()); bob [Blob] x: 0 [double] y: 0 [double] r: 10 [double] getR: n/a → double setR: double → n/a Here I've shown the methods associated with the object, and kind of characterized their parameters and return values in a made-up syntax for illustration. ("n/a", or "not applicable" is used to indicate that getR doesn't take any parameters, and likewise that setR doesn't return any values.) The point is that the methods "belong to" the object, and we invoke them on the object, as bob.getR(), etc. For convenience and code safety (instance variables where the default initialization doesn't really suffice) we often provide a constructor to initialize a new object. It has the same name as the class. (This is like __init__ for Python people.) The parameter values are passed to the constructor, where they may be used in initializing the object. public Blob(double initX, double initY, double initR) {
x = initX;
y = initY;
r = initR;
} Note that now we have to pass the values for x, y, and r when we call "new Blob" down in the main method. IntelliJ shows a red "x" because that parameter is required. So we'd have to say, e.g., blob = new Blob(100, 50, 10);. We can have provide multiple constructors as long as they take different parameter lists (in terms of types of parameters). public Blob() {
// Do nothing; everything has its default value
// This constructor is implicit unless you provide an alternative
}
public Blob(double initX, double initY) {
x = initX;
y = initY;
// r has its default value
} Getting and setting instance variables is a fairly standard operation, though often we provide access for just some of them, and maybe only getting or setting but not both. These methods are called "getters" and "setters". They're so standard, IntelliJ will generate them for us automatically with a menu option under "Source", or by select and right click on the instance variable. It's generally considered bad form for other classes to directly access instance variables (it "leaks" details of the implementation); instead, they should go through getters/setters. Let's build this class up just a bit more; see Blob.java. Note that the constructor and setters use a more standard naming convention when a parameter directly corresponds to an instance variable — use the same name, with this to distinguish instance variable from parameter (e.g., this.x = x). There are some more instance variables, defining how a blob will move around and grow. They have custom setters, and no getters (i.e., nobody outside the class can access them). How are they useful? The step method updates the position and radius according to the velocity and growth. The final method for today is contains which uses the formula for a circle to see if a point x2,y2 is within the radius of the center of the blob. This method illustrates three different types of variables: x2 and y2 are parameters, passing values into the method from the caller. E.g., if someone called bob.contains(3,4), then x2 holds 3 and y2 holds 4. x and y are instance variables, holding the state of a particular object. E.g., if bob is at (10,20), then the call bob.contains(3,4) accesses bob's instance variables, so x is 10 and y is 20 dx and dy are local variables, temporarily holding values within the method. In our example, they become 10-3 = 7 and 20-4 = 16, respectively. Following a generally good programming practice, we now separate out the main "driver" program from the class/classes it uses. This allows us to use the same model of the world in different applications and with different ways of interacting with it. (You'll see this notion carried a step further in things like Model-View-Controller for web/GUI programming.) For example, here's one simple driver for Blob: BlobDriver.java. At the end of the program, the objects will look kind of like this: alice [Blob] x: 33 [double] y: 44 [double] dx: 3 [double] dy: 4 [double] r: 5 [double] dr: 0 [double] getX: n/a → double ... bob [Blob] x: 10 [double] y: 20 [double] dx: 0 [double] dy: 0 [double] r: 20 [double] dr: 10 [double] getX: n/a → double ... If the driver program were to have more than just a single straight-line main method, we might want it to actually create a driver object that could hold onto the two candidate objects. public class BlobDriver2 {
private Blob blob1, blob2;
public BlobDriver2(Blob blob1, Blob blob2) {
this.blob1 = blob1;
this.blob2 = blob2;
}
...
} The complete refactoring: BlobDriver2.java. driver [BlobDriver2] blob1: the blob also known as bob [Blob] blob2: the blob also known as alice [Blob] ... Java notes We'll go over these concepts more in the coming few lectures (and the book has more details), but here are some things from the examples, kind of in the order that we build them into the program. class definition Java is organized around classes, which provide a blueprint for how to organize objects (aka "instances") in terms of data and methods. The name of the class (e.g., "Smile") should match the name of the file ("Smile.java"). method definition A method performs an operation for an object. It is defined inside the class, and at its heart include a name, list of parameters (names and types), and return type (before the name), followed by a body, which is a code block to be executed. public static void main(String args[]) This is a special method name and type signature telling Java where to begin execution of the program — it is the main method. We'll be ignoring the args parameter in this course. syntax characters Note that Java uses curly braces, { and }, to mark blocks of code, bodies of classes, etc. Basically wherever we would indent in Python, we also put curly braces in Java (indendation is then optional, but strongly recommended for readability). Each individual statement (not curly braces) is ended with a semicolon. output System.out handles the basic (console-based) output. One method of System.out is named println, and it prints a string and then forces a newline. IntelliJ trick: type "syso" and then hit control-space to complete it to that long phrase, and save some typing. (IntelliJ has a bunch of such shortcuts.) There's also System.err which can be used similarly for error messages. String type A string just holds a bunch of characters. Strings hard-coded in the program are enclosed in double quotes "...". Strings support many operations, including concatenation (gluing together) with +, and many types will "automatically" produce a string representation of themselves in that context. method invocation To ask "object" to perform "method" with "parameters" (comma separated values), we write object.method(parameters); variable declaration Every variable has a type. That's true in any language — it tells the machine how a bunch of 0s and 1s should be interpreted. But in many compiled languages like Java (and C, C++, etc.) that type must be specified in the source code, while in many interpreted languages like Python and Matlab, it is just maintained at run-time. (Some nice languages are able to infer the type at compile time, and kind of have the best of both worlds.) variable assignment The equals sign is used to assign a value (right-hand side) to a variable (left-hand). That can be done at the same time as the variable is declared, and then again later. object creation An instance of a class, an object, is created by the new operator, with the name of the class and any parameters needed to initialize the object. comments Multi-line comments start with /* and end with */; single-line comments are marked with //. Comments beginning with /** are used to automatically generate HTML-based program documentation — javadocs. instance variables / fields These store data specific to an object; they are declared outside any method. local variables These hold values temporarily in a method. parameters These carry values into a method. constructor Creating an object creates its instance variables. Java will initialize these (to 0 for numbers, false for boolean, null for references to objects). However, these are seldom what we want. Java provides a special type of method called a constructor, that has the same name as the class. It called via new, and is reponsible for giving all of the instance variables appropriate values. It can take parameters, too. capitalization By convention, we name our classes so as to start with capital letters and our variables and methods to start with lowercase letters. We capitalize each word (camel-case) in a multi-word name ("BlobDriver"). return This exits a method immediately, and if the method returns a value, specifies what to pass back. Methods that don't return values ("void" type) just have "return" all by itself to return early, or just naturally return at the end of the code block. return type If a method is to return a value, the type of that value is specified. If doesn't return a value, "void" is indicated as the return type. this Refers to the object on which the method is being called. Not typically necessary, as instance variables are implicitly obtained from this, and method calls are implicitly invoked on this. In constructors and setters, it can be helpful to distinguish a parameter that has the same name as the instance variable (e.g., this.x = x where x is the parameter). math Usual mathematical (+, -, etc.) and logical (& &) operators are available. Some math can be combined with assignment, e.g., ++ (increment by 1), += (add rhs to the variable on lhs).
