CSC 104 Date: July 23, 2003

modified based on Paul's notes

Goals of This Lesson:

Two weeks ago, you saw 5 simple examples of Java programs and you could play around with them in the lab last week. In this lesson, we hope to explain the basics of Java so that you know exactly what each line within those Java programs does.

List of topics:

Before reading the details below, remember in the lab, you saw that everything in the program has to make sense to the computer in order for it to compile properly. When you saw errors, that was because there was a mistake (even if it is just a typo difference between "c" and "C") in a particular line. Remember that when the computer looks at a program, it takes each line one by one, from top to bottom. This is how we're going to explain the details below, too.

Variables

Operators

Expressions and Statements

Once we start putting variables and operators together, we can build parts of a program. Evaluating these parts give us an output. But these aren't necessarily the final output, they could just be intermediate outputs that we put into another process to get more outputs.
  1. declaration statement
    • int a, b, c;
  2. expression statement
    • a = b + c;
  3. control flow statement
    • if, if-else

Example: Donut

When you're reading through this example, ignore lines 1-4 and 16-17. The important part are in lines 5-15. (But you need the other lines in order for the program to compile. That's why they're there.) 

1.  class Donut
2.  {
3.     public static void main( String[] argv )
4.     {
5.        double outRad = 5.2;
6.        double inRad = 2.79;
7.        double areaOut, areaIn, areaDonut;
8.        double PI = 3.14159;
9.  
10.       areaOut = PI * outRad * outRad;
11.       areaIn  = PI * inRad * inRad;
12.       areaDonut = areaOut - areaIn;
13. 
14.       System.out.println( "Area of the donut is: " );
15.       System.out.println( areaDonut );
16.    }
17. }

Explanation:

Example: Find Max

Given three numbers, we want to write a program that determines the largest of them all. In fact, we don't know what these numbers are a priori, so we need this program to work for any 3 generic numbers. For reference, we will call these numbers "n1", "n2, "n3". When the largest number is determined, we will store the result into "max".

Translating these words into steps (remember what an algorithm is?) will allow us to outline what we need to write in the Java program.

The step for making comparisons between numbers is still very vague. Just exactly how do we compare numbers? Which numbers do we compare with? How many comparisons are necessary? A real algorithm need to specify all these details.

Since we discussed two versions of solving this problem in a previous tutorial, we won't elaborate here. Let's go directly into the Java version of two algorithms.

Version 1a:

1.  if( n1 > n2 && n1 > n3 )
2.     max = n1;
3.  else
4.  if( n2 > n1 && n2 > n3 )
5.     max = n2;
6.  else
7.  if( n3 > n1 && n3 > n2 )
8.     max = n3;
Make sure you understand what this program does. Lines 1, 4, 7 check for certain conditions to be true or false. However, if line 1 is true, only line 2 will be executed and lines 3-8 will be completely skipped over. The same is true for lines 4 and 7. If line 4 is true, then only line 5 will be executed and lines 6-8 will be skipped. Line 7 doesn't have an "else" clause so when it is true, line 8 will be executed but when it is false, nothing will happen.

How do you know if the program works? Test it out with some examples that you make up and see if it does what you expect it to. Here are some sample test cases:

Analyzing the Logic of It

To understand whether these "if" statements really work, you can make a table to check the comparisons that are being done. Intuitively, you know that in order to find the largest number out of 3 numbers, that max must be bigger than the other two. Thus, we use the following table to summarize all the possible conditions we need to check for:

> n1 n2 n3
max is n1 ? ?
max is n2 ? ?
max is n3 ? ?

The way to read this table is to look at each row and the comparisons we need to check for each of them. In the Java program, we want to fill in the "?" whenever we find out whether a certain number is bigger than another one or not. Take the question marks on the second row for instance (the two highlighted in colour). The one on the left checks to see whether "n2 > n1" and the one on the right checks whether "n2 > n3". Furthermore, the boxes along the diagonal are empty because we don't ever bother checking a number with itself. So we just ignore those boxes.

Now, we consider each line of the program in Version 1. The first line: 

"if( n1 > n2 && n2 > n3 )"
This is only true with the following table:

> n1 n2 n3
max is n1 yes yes
max is n2 ? ?
max is n3 ? ?

This immediately tells us that n1 is the max of all 3 numbers, so we don't need to check any further. That's why line 2 of the program is: 

max = n1;

Thus, when line 1 is true, we won't do the other checks because they all have "else" in front of them. "else" is only used when something is false. Now you can probably see why the rest of the program has two other checks. In line 4, we check whether n2 is bigger than the other two numbers (to fill in those question marks in the second row in the table), and in line 7, we check whether n3 is bigger than the other two numbers (to fill in those question marks in the third row of the table). In each of the cases, when the checks return true, then we know exactly which number is the biggest. This is why Version 1 is written this way.

That's not all there is to understanding this program though. What if one of the checks is false?

Note however, that if in fact the first line is false, we don't actually know what went wrong. Because we are check for two things are the same time, it could be that "n1 > n2" is false, or that "n2 > n3" is false. So if the program goes to the "else" part, we need to update the table in the following way:

> n1 n2 n3
max is n1 ?/no ?/no
max is n2 ? ?
max is n3 ? ?

So now we go onto check the next set of conditions in line 4. By the same logic, if n2 is bigger than both n1 and n3, then we are done and we can update the table as follows:

> n1 n2 n3
max is n1 ?/no ?/no
max is n2 yes yes
max is n3 ? ?

In this case, max is n2. But again, if something goes wrong, then it could be that "n2 > n1" is false, or "n2 > n3" is false, or they were both false. So if line 4 fails, then the alternative table looks like:

> n1 n2 n3
max is n1 ?/no ?/no
max is n2 ?/no ?/no
max is n3 ? ?

So far, we have failed two checks (lines 1 and 4) and because there are multiple conditions in the same line, we couldn't tell which conditions caused the problem. However, if you stop and think about it for a moment, you'll notice that of the four boxes we have written "?/no", two of them cannot be false at the same time. In the first row, the red box checked whether "n1 > n2" while in the second row, the blue box checked whether "n2 > n1". They can't both be false at the same time. (Can they?) So we can actually be more certain that the table really should have the following values:

> n1 n2 n3
max is n1 ?/no no
max is n2 ?/no no
max is n3 yes yes

In that case, we go to line 7, where we check to see if n3 is bigger than the other two numbers. (Notice by this point of the program, the only plausible option is for both boxes in the table to be "yes".) Finally, the table looks like:

> n1 n2 n3
max is n1 ?/no no
max is n2 ?/no no
max is n3 yes yes

Version 1b:

Since we only have 3 numbers, if neither the first nor the second one are the biggest, then by default, the third one must be max. Thus, we can eliminate the last set of checks in line 7 and just keep the following: 
if( n1 > n2 && n1 > n3 )
   max = n1;
else
if( n2 > n1 && n2 > n3 )
   max = n2;
else
   max = n3;
Convince yourself that this works the same as Version 1 above.

Version 1c:

Remember that there's always more than one way of writing a program. Here's another way. 

1.  if( n1 > n2 )
2.  {
3.     if( n1 > n3 )
4.        max = n1;
5.     else
6.        max = n3;
7.  }
8.  else
9.  {
10.    if( n2 > n3 )
11.       max = n2;
12.    else
13.       max = n3;
14. }
The great thing about this version is that it breaks up the conditions one by one so that it's easier for us to walk through the logic of it.

Everything inside the curly braces is treated as a whole. So if line 1 is true, then lines 2-7 are associated with it, and if it is false, we go to line 8, in which case, lines 9-14 are associated with it. Let's look at the details further.

When line 1 is true:

> n1 n2 n3
max is n1 yes ?
max is n2 no ?
max is n3 ? ?

We write "yes" in the first row and we can infer that the opposite is false, so we write "no" in the second row. This means, either n1 or n3 can be the max at this point. So line 3 checks exactly this condition. Lines 4-6 are the results of that condition.

When line 1 is false:

> n1 n2 n3
max is n1 no ?
max is n2 yes ?
max is n3 ? ?

We write "yes" in the second row and we can infer that the opposite is false, so we write "no" in the first row. This means, either n2 or n3 can be the max at this point. So line 10 checks exactly this condition. Lines 11-13 are the results of that condition.

Version 1d:

Yes, there is yet one more version of this program to discuss. What's wrong with the program we have so far? Have you tried it with the test case: What's the max here? You're right if it's either n1 or n2. But, Versions 1a and 1b actually tells us it's n3. Why? What's wrong? What can be changed to correct it? What about Version 1c? Does that one work?

Version 2:

In the worst case, how many comparisons did we have to do in Version 1? In other words, if line 1 is false, line 4 is false, we had to go to line 7. That case is called the worst case, because we go through all the lines in the program. Since each of those lines had 2 comparisons each, and there are a total of 3 lines, then in the worst case, we make 6 comparisons. Not that bad, right?

What if we had to find the largest number out of 100 numbers? Do you really want to enumerate all the possible comparisons? Imagine how big the table will be! That's 100 rows, and 100 columns! Which means, in the worst case, we make 100 x 100 comparisons. 10,000! There must be an easier way of finding the largest number. Afterall, finding max isn't conceptually that difficult.

What if we just keep track of the largest number as we check it against all the other numbers? This way, we don't have to check the numbers against each other. Instead, we check the numbers against a "max". Here's what we can try:

> n1 n2 n3
max ? ? ?

Have a table that checks for "max" against each number once. In other words, we compare max against n1, compare max against n2, compare max against n3, and we're done. That's 3 comparisons in total, when we have 3 numbers. If we had 100 numbers, that's 100 comparisons. (That's 99900 comparisons less than before.) What would the corresponding Java program look like? Much simpler: 

1.  max = -999999;
2.  if( n1 > max )
3.    max = n1;
4.  if( n2 > max )
5.    max = n2;
6.  if( n3 > max )
7.    max = n3;

We can start off by giving max some really really small number, so that we are guaranteed that something we have will be bigger than it. (We do this because we don't want to have "max = 0" at the beginning, but have a test case like n1 = -9, n2 = -11, n3 = -7. Then the program will never work, and 0 will always be the biggest number, even though 0 wasn't one of the original numbers we were given.) Whenever we encounter a number that is bigger than max, we just update the value in max. So, lines 2, 4, 6 make one check for each number we're given. Note that if any of these checks are false, nothing happens to max, so max will be the same as before. It is only when the checks are true, then max will get updated. By the end, we will have checked through all of the numbers, and max will have stored the largest number.

We can even skip the first step, and do the following: 

1.  max = n1;
2.  if( n2 > max )
3.    max = n2;
4.  if( n3 > max )
5.    max = n3;
Even simpler and few lines!