﻿﻿ CS 1110/1111: Introduction to Programming

# 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

### 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 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) {
return sum;
}
Digit addTens(Digit a, Digit b, Digit c) {
}```

`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 arbitrary numbers represented as lists of digits

• Adding two arbitrary numbers, either or both of which might be negative