Lecture 4

Announcements

Bring laptops to class next lecture

Another quiz is out; I probably won't mention this again for later quizzes.

ACM ice cream social tomorrow

ACM is hosting a casual social event featuring hot chocolate and ice cream this Thursday at 4:30 PM at 4th Floor Rice Hall Lobby. Students should feel free to come talk about UVa's CS major, what's going on with CS in the real world, or just to meet other computing students! We'll also have both of UVa's Google Student Ambassadors there as well, to talk about Google and/or Google products. And hey, if nothing else, free ice cream!

Talking Points

Slides from 001 (3pm) and 002 (1pm)

Algorithm

What is an algorithm?

An algorithm is a set of well-defined steps for performing a task or solving a problem.
—Tony Gaddis, Starting Out with Java, pg. 6

Algorithms are higher-level than code and can be encoded in multiple ways

Generally assumed to be deterministic and finite

Running Example

Consider adding numbers expressed as a list of decimal digits.

We'll assume we already know how to add two single-digit numbers.

We'll build algorithms for how adding many-digit numbers.

Some Java-Like Syntax

We'll learn just a few parts of Java syntax today.

In java, we can name values in variables

Each variable can only hold one type of value: maybe it holds numbers, or text, or pictures, but it only stores one of those types of things.

We make variables by saying type name like Digit x if x is to store a single digit.

= doesn't mean equals, it means should be changed to be:

x = 3 means change x so it stores a 3. 3 = x would mean change 3 so it stores x, which doesn't make sense (bad semantics) and is thus an error.

Something we can do is called a method

We define a method by saying, in order, type name(type name, type name, …) { things to do }. This is like writing a recipe or how-to guide.

We invoke a method by saying, in order, name(value, value, …). This is like saying go use that recipe I wrote earlier.

When we are done with a method we generally return something; for example, the last line of a recipe to make a pie crust might be return theCrust.

Within the list of directions, we separate individual steps with semi-colons.

Getting Started

Assume someone else wrote 2 methods

Digit addOnes(Digit a, Digit b) { ... }
Digit addTens(Digit a, Digit b) { ... }

…such that, e.g., x = addOnes(7,9) would set x to be 6 and y = addTens(3,4) would set y to be 0.

How would we write methods to add three digits together instead of just 2?

Digit addOnes(Digit a, Digit b, Digit c) {
	Digit sum = addOnes(a, b);
	sum = addOnes(sum, c);
	return sum;
}
Digit addTens(Digit a, Digit b, Digit c) {
	Digit carry1 = addTens(a, b);
	Digit sum = addOnes(a, b);
	Digit carry2 = addTens(sum, c);
	return addOnes(carry1, carry2);
}

return is how we say and this is the result.

Building Algorithms

From here we'll build the following algorithms, depending on time:

Adding two 2-digit numbers
Adding two 3-digit numbers
Adding two arbitrary numbers represented as lists of digits
Adding two arbitrary numbers, either or both of which might be negative

Thinking about Algorithms

We left out lots of details that Java needs to know.

Next 2 classes we'll preview most of the Java we'll learn this term; then we'll start in on details of individual parts of the language.

Don't lose sight of the bigger picture: we're just describing algorithms so a computer can understand.