Chapter 4: Algorithms

(AP Computer Science Standard: III Program Analysis)

 Essential Question: How does an algorithm compare to a mathematical model in physics or engineering?

What is an Algorithm
1. Define the term algorithm.
2. Correctly use recursion. Read the Barron's book write up on recursion. Click here for a simple example of recursion. Relevance: If you can do recursions you can learn to do anything in Comp Sci.
• Must call itself within the method
• Must alter one or more of its arguments each time it calls itself.
• Must have a means of stopping itself based on the modified argument(s)

• Stores calculated values in a stack and evaluates them after the recursion stops.

Programming Assignment: Write a program that inputs an integer n using command line input and uses it to calculate n factorial using recursion.

Programming Assignment: Write an application that finds and outputs Pi using recursion and the following series: Click here for 3 examples of recursion.

(Pi 2)/6 = 1 + 1/22 + 1/32 + ... + 1/n2

Input the number of times the recursion should run using command line input.

1. Determine the number of iterations a given recursion will have.
2. Define list in abstract terms. an abstract data structure that implements an ordered collection of values, where the same value may occur more than once. The simplest form of list is an array.
• items numbered
• method for accessing the i th item is defined
1. Define traversal. The process of visiting (examining and/or updating) each node or item in a list.
2. Compare sequential to binary search. Note: O(----) as shown below is called big O notation and indicates how run time will increase for as the amount of data items = n increases.
• sequential: examines each item in a list in order until it finds the one it's searching for. O(n) run time increases proportional to the number of items searched = n.
• binary: list must be sorted. Uses a divide and conquer technique (20 questions). O(log n) run time increases proportional to the logrithm of the number of items searched = n.
 n 2 3 4 5 6 7 8 9 10 log n 0.3 0.48 0.6 0.7 0.78 0.85 0.9 0.95 1

Read Chap. 4; Algorithms Should Mind Your Business, How To Think: Algorithmic Thinking, Read the Recursion section of the Barron's book. Read and study yet another Mr. Rogers' recursion example.

Homefun (summative/formative assessment):
1) Exercises 1,  7, 9,
2) Based on the reading assignments, write a 1/2 to one page paper explaining what algorithmic thinking is and how it differs from mathematical thinking.
Programming Assignment: Exercise 10

Summative Assessment: Test Chap 4 Objectives 1- 6

Relevance: Prior to the second half of the 21st century, the mathematical model particularly in physics was king as a method of predicting outcomes and solving problems. However, there are many problems which can only be solved with algorithms especially in the less mathematical sciences. Even in physics algorithms are required for solving chaos related problems.

 Essential Question: What's the difference between style and syntax?

Chap. 5: Java Syntax and Style

(AP Computer Science Standard: II Program Implementation, III Program Analysis)

1. Correctly use the three forms of comments:

• // Single line comment

• /* One or more lines of comments*/

1. Identify reserved words (p. 107).

2. Correctly use the naming conventions for classes, methods, and fields.

• Capitalize the first letter of classes but not methods or fields.

• The first character must be a letter & have no spaces in it.

• Names can include letters, numbers or the underscore_.

• Names should be descriptive.

• Method names = verbs, field = nouns

• Constants use all capitals.

1. Correctly indent programs.

Homefun (summative/formative assessment):
Read Chap. 5; Princeton professor foresees computer science revolution
Exercises 3, 4, 5, 7, 8, 10

Programming Assignment: Lab 5.6

Relevance: A program won't run without proper syntax. Proper style makes the code readable so that it can be modified and maintained.

 Essential Question: Why did you learn to find remainders in grade school instead of going straight to long division ?

Chapter 6: Data Types, Variables, and Arithmetic

(AP Computer Science Standard: II Program Implementation, III Program Analysis)

1. Understand the meaning and use of the equal sign in Java.

• Can have only one field or variable on the left side

• Means "replaced by", not equals

1. Correctly declare fields and local variables.

2. Correctly initialize fields, local variable, and parameters.

3. State the default values used for initializing fields.

• numeric types: 0

• objects: null

1. State the default value used for initializing local variables. (there isn't one)

2. State the eight types of primitive data types and their sizes in bytes. (p. 129)

3. Explain why the largest size of an integer or long variable can be a major issue. The size is finite and if the size is exceeded the program will not work.

 Data Type Max size int slightly over 2.1 x 10 9 long slightly over 9.2  x 10 18 double 1.8 x 10 308
1. Explain the limitations of precision on floating point data types and why these limitations can produce round-off errors. Unlike a short, integer, or long, a floating point number is not exact. It has a limited number of significant figures. Repetitive calculations can produce significant rounding errors.

2. State the primitive data types which do not have a true zero and explain why this can be a problem. double and float

3. Correctly Use:

• literal constant - letters in single quotes and numbers

• symbolic constant - declared and initialized using final

• escape sequences (p.131, \n newline, \t tab, \\ slash, etc.)

1. Understand the term scope (p. 133). Note: the concept of scope is incredibly important to programming in Java. You must consider it whenever you create a variable. As a matter of style, variables should be declared at the top limit of their scope.

• inside the { } of a class

• inside the { } of a method

• inside the { } of a loop, if, else statement, or any other set of {}

1. Correctly convert numbers and objects into strings and explain why objects need special attention. (An object may have multiple variables or fields of different data types associated with them, hence the output has to be defined in order to understand how it should be done.)

• Concatenate to an empty string. Example: System.out.print ("" + 6);

• Use toString method for converting objects to strings (This method outputs the class name and memory location. To output something more meaningful it has to be overridden.)

Homefun (summative/formative assessment): read Sections 6.1 to 6.5; Exercises 1- 7 p.146-147

1. Use literal constants as either int or doubles (Example: int: 2, double: 2.0).

2. Correctly use the order of operation for arithmetic.

1. parentheses

2. division, multiplication, modulus

3. Perform division using integers and doubles.

Note: integer division truncates the decimal portion of a number. It does NOT round numbers. Mixed division of integers and doubles upgrades the answer to a double (this is called autoboxing).

Examples:
division of integers: 1 / 2       yields 0
division of doubles: 1.0 / 2.0 yields 0.5
mixed division:         1 / 2.0    yields 0.5,  1.0 / 2    yields 0.5

1. Truncate and round numbers using integer division.

Examples:
1/2 rounded to nearest whole number
((1*10) / 2 + 5) / 10  yields 1

y/x  rounded to nearest whole number
((y*10) / x + 5) / 10
1. Cast variables.

Example:
int a, b;
double c;
c = (double) a / (double) b;
1. Correctly use various arithmetic operators including:

• modulus (%) returns remainder: 1 = 5 % 2

• compound assignment operators (/=, +=, -=, *=, %=)

• increment/decrement (y++, ++y, y--, --y)

 Modulus Examples 1 = 1 % 3 2 = 2 % 3 0 = 3 % 3 1 = 4 % 3 2 = 5 % 3 0 = 6 % 3

Homefun (summative/formative assessment): Read Sections 6.6 to 6.10; Exercises 8, 10, 11 p.147-148

Programming Assignment: Lab 6.10, Exercises 12, 13 p.148

Programming Assignment: Write a program which uses command line input to input a single dimension in centimeters. Use this dimension to calculate and output the surface area and volume of a cube, sphere, and cylinder along with the correct units. The radius and height of the cylinder are equal to the dimension. Use a separate method for each calculation.

Relevance: Handling massive numbers of transactions involving money without losing anything to rounding errors is a major issue for international finance and businesses.

 Essential Question: How does a progressive income tax system work and is it a good idea?

Note: with a progressive income tax, when a higher rate is triggered the taxpayer only pays the higher rate on income above the amount that triggers the higher rate.

Tax code program:

Input: Using the command line input income in dollars. (This needs to be changed to cents inside the program.)

Output:

• Taxable income in dollars

• Tax due in dollars (round tenths of cents upward)

• Nominal tax rate in % of income

NTR = (taxDue) / (income) *100

Description: The program will round any tenths of a cent upward. "If" statements are not allowed. The program will use only algorithms to calculate taxes. It will use the following progressive tax table:

 Income (\$) Tax Rate Comments 0 to 19,999.99 00 % This part of income is never taxed 20,000 to 29,999.99 25 % Only income above \$19,999.99 is taxed at 25% 30,000 + 35 % Only Income above \$29,999.99 is taxed at 35%. Note this is an additional 10% above the 25% tax that kicks in at \$29,999.99.

 Homefun (summative/formative assessment):

Summative Assessment: Test Chap 5 & 6 Objectives 1-22