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!

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

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

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.

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 amethodWe

definea 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

invokea method by saying, in order,name(value, value, …). This is like sayinggo use that recipe I wrote earlier.When we are done with a method we generally

returnsomething; for example, the last line of a recipe to make a pie crust might bereturn 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 sayand 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.

Copyright © 2014 by Luther Tychonievich. All rights reserved.