CIS3020:Notes 4

From BluWiki

Back to CIS3020

VARIABLES

• Variable: An identifier than can be given a value
  • Associated with primitive types

• Reference Variable: A variable whose value is a reference
  • Associated with instances of a class

• Most programmer refer to both as variables
• There is a fundamental difference in how they are used internally

String Methods

*Method		Return Val		Arguments		
*toUpperCase	ref. to String obj.	none
*toLowerCase	ref. to String obj.	none
*length		a number		none
*trim		ref. to String obj.	none
*concat		ref. to String obj.	ref. to String obj. (add Strings together)
*substring	ref. to String obj.	a number (position to start reading the String from)
*substring	ref. to String obj.	two numbers (pos. to start and pos. to end)

BOUND VARIABLES

Given two methods:

public int test( int x )	public int square( int x )
{ body1; }			{ body2; }

The two X's are NOT the same. These are formal paramenters of their respective methods. The method definitions BIND them.

• A variable is said to be BOUND in an expression if the meaning of the expression is unchanged when the variable is

consistently renamed throughout the expression

• In other words, replace either x with some other name like p throughout its entire method and the definition of the method

remains the same!

Scope (of a name)

That portion of a program in which there is a binding for a particular name

FREE name - A variable or method name is said to be FREE in an expression if it is NOT bound

public boolean goodEnough( double guess, double x ) {
	return (abs(square(guess) -x) < 0.001);
}

• Who is bound? goodEnough, guess, x
• Who is free? abs, square

LINEAR RECURSION

• Suppose I would like to know how many people are in row 2
• Rather than counting each student, I will let them count themselves
• Each student will:

- Give a count of 1 if no one is to their left
- Will ask the person to their left for a count, then will give an answer one larager than that value

TAIL RECURSION

• where all the calculations are done as the recursion progresses.

ORDERS OF GROWTH

• An Important consideration in the comparison of different solutions to problems is the complexity of the algorithms used
• This complexity is measured on two important quantities:
  • The space requirements (Space Complexity) to represents all values used in the algorithm
  • The time requirements (Time Complexity) needed to perform all of the needed calculations

THE BIG - O...RGASM

• Informal definition:
• If function Est(n) times some integer constant, m, dominates function Time(n), then we say:
  • Time(n) = O( Est(N) )

Algebraic Identites for Big-O

Assume c denotes a constant and that f and g are arbitrary functions

1. c * f = O(f) -- you can drop constant multipliers
   • 17n = O(N) ... "Of order n"
   • 25n^2 = O(N^2) ... "of order n^2"
   • 99 = O(1) ... "of order 1"
2. f+g = O(f), so long as f dominates g
   • n^2 + 3= O(N^2)
   • n^5 + n^3 + n = O(N^5)
3. f*g = O(f) * O(g)
   • n^3m^2 = O(N^3)*O(M^2)

Important Order Relationships

For the following assume that k and c are positive constants and that n os a variable

• n^n dominates n!
• n! dominates c^n
• c^n dominates k^n, so long as c>k
• k^n dominates n^c, so long as k>1
• n^c dominates n^k, so long as c> k
• n^2 dominates n*log(n)
• n*log(n) dominates n
• n dominates log(n)
• log(n) dominates 1

Special Big-O Complexities

• O(1) Constant complexity
• O(N) linear complexity
• O(N^k) polynomial
• O(k^n) exponential

Stay below exponentials! Way too much calculation