ACM Programming Team

The first practice contest for the York Programming Team is today from 12:30 to 3:00pm in room 1006 of CSE.

The 2010 ACM-ICPC World Finals will be held in Harbin, China.

A Hairy Problem

Estimate the number of hairs on an adult human head.

Solution Outline

Assuming that a human head is approximately spherical:

1. Estimate the diameter of an adult human head.
2. Estimate the fraction of the head surface area covered by hair.
3. Estimate the density of hair (number of hairs per square centimeter).

Worked Solution

Several Internet sources state that the average number of hairs on a human head is on the order of 100000.

A Java Implementation

Solving small problems like estimating the number of hairs on a human head is easy to do in Java. The solution involves only a few numeric variables and some simple arithmetic.

Start jEdit if you have not already done so.

Step 1: Declare a Class

In 1020, your programs will always consist of a single file. The file will define a Java class. For now, you can think of a class as being the smallest building block of a Java program.

You need to give the class a name to declare a class. The name (or identifier) should be descriptive of the problem you are trying to solve. We will use the name HairsOnHead for our solution. Type the following into jEdit:

public class HairsOnHead
{

}

Save the file with the name HairsOnHead.java in your working folder.

• the line public class HairsOnHead is called the class header
• the two matched braces enclose the class body
  • in general, braces group blocks of code
• class names should always start with a capital letter
  • capitalize each word of a multiword name
• identifiers should always begin with a letter
• the Java language is case sensitive; HairsOnHead is a different identifier than Hairsonhead
• the Java language is freeform in that you can add whitespace (space, tab, or carriage return) in most places
  • but follow the style guidelines for the course
• keep your code neatly formatted; notice how the opening brace { and closing brace } line up vertically with the p
• the file name must be the class name followed by .java

Step 2: Add a main Method

Every Java program starts executing in a method called main. A method is simply a group of Java statements that have been collected into one unit that can be re-used over and over again. In 1020, the only method that you will have to create is the main method; however, you will use methods that other programmers have created.

Add the main method to the HairsOnHead class as shown below:

public class HairsOnHead
{
   public static void main(String[] args)
   {

   }
}

Save the file.

• the signature of the main method shown above is the one that is most commonly used
  • you should memorize the fragment of code above; when you write a program in 1020 you should start with the same fragment of code (changing the class name to something more appropriate)
• the method declaration is indented by 3 spaces inside of the class body
• much of the above code may not make any sense to you at this point; that's ok because the explanation for most of it is beyond the scope of this course

Step 3: Declare a diameter Variable

Recall that our worked solution used a variable to describe the diameter of a human head. The diameter is a numeric value. Let's assume that we're only interested in integer values for the diameter.

In Java, we must declare a variable before we can use it. Declaring a variable means specifying its type and its name. For integer numeric values we can use the type called int.

Declare a variable of type int named diameter by typing in the following code:

public class HairsOnHead
{
   public static void main(String[] args)
   {
      int diameter;
   }
}

• a type defines what values a variable can take and the operations that can be performed with the variable
• Java is strongly typed, meaning every variable must have a type before it is used
• the variable declaration is indented by 3 spaces inside of the method body
• the semi-colon is important; it indicates the end of a Java statement

What Does int diameter; Mean?

The statement int diameter; indicates that we want to associate the name diameter with a chunk of memory that holds an int value. A variable is the chunk of memory that is reserved for it.

A simple model of computer memory is a column of identical boxes numbered sequentially starting at zero.

Each box holds a fixed amount called a byte of memory. It requires 4 bytes to hold an int in Java.

The statement int diameter; reserves a block of 4 bytes and labels the block with the identifier diameter.

Step 4: Assign a Value to diameter

Now that we have declared a variable named diameter we need to assign it a value. Because the type of diameter is int, we can only assign it integer values.

In Java, the equals symbol = is used to assign values to a variable. The symbol = is called the assignment operator. Update your code to assign a value to diameter:

public class HairsOnHead
{
   public static void main(String[] args)
   {
      int diameter;
      diameter = 17;
   }
}

• IMPORTANT! the statement diameter = 17; means "the variable named diameter is assigned the value of 17"
  • DO NOT get into the habit of saying or thinking "the variable named diameter equals 17"
• names of variables should begin with a lowercase letter
• the number 17 is called an int literal
  • a literal is the source code representation of a fixed value; literals are represented directly in your code without requiring computation

What Does diameter = 17; Mean?

The statement diameter = 17; means that you want to assign the value of 17 to the block of memory (the variable) with the identifier diameter.

We say that the variable at address 100 has the type int, the name diameter, and the value 17. The Java compiler keeps track of all of this information inside of its symbol table.

Step 5: Declare and Assign a fractionCovered Variable

Now we need a variable that describes the fraction of a head that is covered by hair; this is a real-valued numeric variable. In Java, a suitable type for representing real-valued numeric quantities is called double.

If you know the value of a variable when you want to declare the variable, you can declare and assign a value to the variable in one statement. Declare and assign the value of 0.5 to a variable of type double named fractionCovered as shown below:

public class HairsOnHead
{
   public static void main(String[] args)
   {
      int diameter;
      diameter = 17;
      double fractionCovered = 0.5;
   }
}

• IMPORTANT! the statement double fractionCovered = 0.5; means "the variable of type double named fractionCovered is assigned the value of 0.5"
  • DO NOT get into the habit of saying or thinking "fractionCovered equals 0.5"
• the number 0.5 is a double literal; the following are also double literals with the value of 0.5
  • 0.5d
  • 5e-1 or 5.e-1 or 5.0e-1 (Java notation for 5 × 10^-1)
  • 5E-1 or 5.E-1 or 5.0E-1 (Java notation for 5 × 10^-1)

Step 6: Declare and Assign an areaCovered Variable

We can now calculate the area of a head that is covered by hair. The calculation requires the multiplication of some variables we have already declared and assigned. We will declare a variable to hold the value of the calculated area.

In Java, multiplying variables of type int and double is done using the * symbol. Declare and assign a variable of type double named areaCovered as shown below:

public class HairsOnHead
{
   public static void main(String[] args)
   {
      int diameter;
      diameter = 17;
      double fractionCovered = 0.5;
      double areaCovered = fractionCovered * 3.1415 * diameter * diameter;
   }
}

• when assigning the value to areaCovered the value on the right-hand-side (RHS) of the assignment operator is evaluated first
  • that is, the value of fractionCovered * 3.1415 * diameter * diameter is evaluated first and then assigned to areaCovered
• notice that we can use the value of a previously declared and assigned variable just by using the name of the variable
• notice that the value of π is not built into the Java language; we had to use the inexact literal 3.1415 instead

Steps 6—8: Complete the Solution

You have now seen all of the techniques you need to complete the solution. Complete the solution as shown below:

public class HairsOnHead
{
   public static void main(String[] args)
   {
      int diameter;
      diameter = 17;
      double fractionCovered = 0.5;
      double areaCovered = fractionCovered * 3.1415 * diameter * diameter;
      int linearDensity = 15;
      int areaDensity = linearDensity * linearDensity;
      double numberOfHairs = areaCovered * areaDensity;
   }
}

• the number of hairs is an integer value but we used a variable of type double to hold the result; you will see the reason for doing so in Day 03

The Memory Diagram for our Solution

Each variable of type double requires 8 bytes of memory. The complete memory diagram for our main method is shown below:

Step 9: Print the Result

Our program is correct the way it is currently written, but we cannot see the answer to the problem. Java provides a way to send output to a console window. Output the answer by adding the code as shown below:

public class HairsOnHead
{
   public static void main(String[] args)
   {
      int diameter;
      diameter = 17;
      double fractionCovered = 0.5;
      double areaCovered = fractionCovered * 3.1415 * diameter * diameter;
      int linearDensity = 15;
      int areaDensity = linearDensity * linearDensity;
      double numberOfHairs = areaCovered * areaDensity;
      System.out.print("The number of hairs on a human head is ");
      System.out.println(numberOfHairs);
   }
}

Save the file.

• we look at input and output in greater detail in Week 02 and beyond

Step 10: Compiling the Program

You must compile your program before it can be run. The Java compiler translates your source code program into instructions that the Java virtual machine can understand.

To compile your program, start the Command Prompt program.

Make sure your source code file is in the folder by typing dir followed by the Enter key.

Compile your program using the Java compiler by typing javac HairsOnHead.java followed by the Enter key.

Step 11: Run the Program

Run your program using the Java program launcher by typing java HairsOnHead followed by the Enter key.

Your Turn

Write a Java program to solve the following problem:

Suppose that 100000 people are tested for an uncommon disease that afflicts approximately 1 in every 5000 people. The medical test is not perfect. There is a 95% chance that the test will come back positive if the person actually has the disease. There is a 1% chance that the test will come back positive if the person does not have the disease.

What percentage of people who test positive for the disease actually have the disease?

Self Check

1. Can you create, compile, and run a simple Java program (a program with only a main method?
2. Do you understand the concepts listed in the Summary of Key Concepts on page 35 of textbook (concepts 3—10)?
3. Can you answer the Review Questions on page 36 of the textbook (questions 4, 6, 11, 12, 15, and 16)?
4. Can you do Exercises 1.9, 1.14, and 1.15 in the textbook?

To Do For Next Lecture

1. Get a CSE account if you don't have one yet. It takes 20 minutes or so to activate your account so try to do it before your lab on Monday.
2. Read up to and including Section 1.3.2 in the textbook.