Computer Science I
Computer Science I CMPU 101
Popular in Course
Popular in ComputerScienence
CHEM 2311 P1
verified elite notetaker
This 37 page Class Notes was uploaded by Reuben Rohan on Wednesday October 28, 2015. The Class Notes belongs to CMPU 101 at Vassar College taught by Marc Smith in Fall. Since its upload, it has received 14 views. For similar materials see /class/230535/cmpu-101-vassar-college in ComputerScienence at Vassar College.
Reviews for Computer Science I
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/28/15
Chapter 10 FloatingPoint Datatypes CMPU101 ProblemSolving and Abstraction Marc Smith Vassar College Spring 2007 FloatingPoint Datatypes type bits from to float 32 34x1038 34x1038 double 64 18 x 10308 18 x 10308 Java assumes that floatingpoint literals are doubles doubles have more range and precision than floats We39ll use only doubles ProglOOl Read a double amp Print Its Square SystemoutprintquotEnter a double quot double x kbnextDouble SystemoutprintnquotThe square of quot x 39 is quot x x 3939 FloatingPoint Numbers decimal points 473 314159 00825 scientific notation 6023 x 1023 91 x 103931 FloatingPoint Datatypes IEEE Standard for Binary FloatingPoint Arithmetic IEEE 754 For the curious http z en wikipedia orglwiki IEEE754 This material will be covered thoroughly in CMPU224 Computer Organization Prog1002 double x 13 13 Systemoutprintnx quot without a formatquot Systemoutprintfquotf in format fnquotx Systemoutprintfquot60f in format 60fnquotx Systemoutprintfquot61f in format 61fnquotx Systemoutprintfquot62f in format 62fnquotx Systemoutprintfquot63f in format 63fnquotx Systemoutprintfquot64f in format 64fnquotx Systemoutprintfquot65f in format 65fnquotx Systemoutprintfquot66f in format 66fnquotx Output prints as 1 6900000000000002 17 Arith metic r t double operator double a double int operator int 6 int MixedMode Arithmetic double operatorint a double int operator double a double Shortcuts double x 75 x 33 x Stringformatquot63f3913 13 a v 1590quot Some Examples 20 3 5 0666667 5 3166667 Methods from Class Mat h Mathabsdouble Mathsqrtdouble Mathsindouble Mathpowdoubledouble Converting ints to doubles inti 3 double d i Approximate Equality public static boolean almostEquaI double x double y return Mathabsxy lt 1e10 Driver SystemoutprintquotnEnter the radius for a circle quot Circle c new CirclekbnextDouble Systemoutprintfquotradius is 64fnquotcgetRadius Systemoutprintfquotarea is 64fnquotcgetArea Converting doubles to ints double d 25 int i d forbidden possible loss of precision int i int d Progl 003 Class Circle class Circle private double radius public Circle double radius thisradius radius public double getRadiuso return radius V 34 V public double getAreao return MathP radius radius ll end Circle SystemoutprintquotnEnter a new radius for the circle quot csetRadiuskbnextDoubIe Systemoutprintfquotradius is 64fnquotcgetRadius Systemoutprintfquotarea is 64fnquotcgetArea lnClass Exercise add public boolean isBiggerCircle Converting strings to doubles Double parseDoubleString public void grow radius 11 public void shrink radius 09 Converting doubles to strings Rough double x String s x For greater control StringformatcontroString value Chapter 14 Arrays CMPU101 ProblemSolving and Abstraction Marc Smi h Vassar College Spring 2007 Plan Basic operations on arrays Class Mystring represents a String as an array of char Reimplement Section using an array of Students instead of a file of students Position Numbering in an Array 0 1 2 length1 This is the same numbering scheme we used for Strings Strings are notjust arrays of char Strings are objects so we can send them messages Collections In Chapter 13 we saw many algorithms used on les Now we39ll apply these algorithms to arrays Arrays Arrays may contain either objects or primitive datatypes Within an array all of the elements are the same type homogeneous Arrays like objects must be instantiated with a new but arrays are not objects When an array is created its length is fixed If we know the name of an array we can get its length Declaring and Allocating Memory for an Array of 3 ints Declaration int 1a a is an array of ints Allocation creates space for 3 consecutive integers a new int3 Note By default a has length 3 an array contains Combined declaration and allocation 3quot zer s quotCe int a new int3 allocated Array Field length a length evaluates to 3 Positions are numbered 0 1 2 Note that length is a field not a methodit s not length This is because arrays are not objects Using Array Elements o Systemoutprintlna1 Anny L systemoutprimlMam Including the position inside 15 for int i 0 i lt 3 i hardcoded termination cond Systemoutprintlnai forint i 0 i lt alength i mum batter39 Systemoutprintlnai ArraylndexOutOfBoundsExceptlon in a new in 5 No negative indices are allowed and position 10 does not exist in am 7 array a a102 Initializing Arrays Initializing aO 7 pronounced a sub zero a1 3 a sub one a2 9 a sub two Using Array Elements Systemoutprintln5a2 1 a2 2a2 a2 aO a1 a new in 5 a is now pointing to a completely new array of five elements An Array of 10 ints Construct an array of ints length 10 where each element is the square of its subscript Print the elements of the array separated by spaces Compute and print the sum of the elements of the array Desired output 49162536496481 sum 285 Solution int a new int10 forinti 0 i lt alength i ai i forinti 0 i lt alength i Systemoutprintai quot quot Systemoutprintln i sum ai Systemoutprintlnquotsum quot sum Shortcut Array lnitializers in a 7 3 9 allocates and specific initialization in a new int3 a0 7 a1 3 a2 9 Read ints From a File into an Array Three ways of doing it Read the file twice Grow the array as needed Maintain a partiallyfilled array read the details in the chapter OBO Errors OffByOne for int i 0 ilt alength i Perfect for int i 1 ilt alength i Misses aO for int i 0 ilt alength i Illegally references aalength generates ArraylndexOutOfBoundsException Arrays of Length 0 in a new intO is perfectly legal a length evaluates to 0 Progl 4 O 4 Arrays amp Array Elements as formal parameters public static void f int a a0 Changes the value of the first cell of an array passed in public static void g int a a new int5 Inside the method a points to a new array On return the passed array argument matching a is unchanged Passing arrays as arguments is like passing objects as arguments public static void square in a for inti 0 ilt alength i alil alilalil On return every position of a has been changed Progl 4 O 6 Class MyString Represent a String as an array of char class MyString private char a Primitive types are passbyvalue public static void h int n n1339 Inside the method I has value 13 On return the passed integer is unchanged from what it was at the time of the call to h Prog14 05 returning arrays public static in growBy1 int a int result new in alength 1 for inti 0 ilt alength i resul i ai return result MyString constructor public MyString String s l thisa new charslength for int i 0 i lt slength i thisai scharAti Alternate MyString constructor MyString char a Constructs a MyString from a full array of char public MyString char a l thisa a public int length return alength public String toString String result for int i 0 ilt alength i result ai return result MyString char a int used Constructs a MyString from an unfilled array of char public MyString char a int used l thisa new charused forinti0iltusedi thisai ai public static MyString read Scanner sc String s scnextLine return new MyStrings Overloading the read method avoids passing null as an argument public static MyString read PrintStream psScanner sc psprintln Please enter a Stringquot String s scnextLine return new MyStrings Typical Driver Scanner kb new ScannerSystemin MyString s MyStringreadSystemoutkb Systemoutprintln You entered the MyString quotquot s quotquotquot Systemoutprintln quotIts length is quot slength Taxonomy of MyString Methods Prototypes boolean isPaIindromeO int containsHowManychar char charAtint MyString trim MyString concatMyString String toString public boolean equals MyString that chara1 thisa char a2 thata if a1 length a2length return false forint i 0 i lt a1length i if a1i a2i return false return true indeXOf public int indexOf char c l for inti 0 ilt alength i ifalil0l return i return 1 Progl407 public boolean equals MyString that if thislength thatlength return false for int i 0 i lt thislength i if thisai thatai eturn fals return true public MyString concat MyString that char a1 thisa char a2 thata int n1 a1length int n2 a2length char newA new chadn1n2 forinti0iltn1i newAi a1i Prog1408 forinti0iltn2i newAn1i a2i return new MyStringnewA lastlndexof public int lastlndexOf char c forintialength1igt0i ifalil0l return i return 1 lastlndexof Another Way public int lastlndexOf char c int result 1 for inti 0 ilt alength i ifai CH result i return result contains Another Way public boolean contains char c return thisindexOfc Mystring Receiver Mystring Parameter Same Length MyString replacecharchar MyString replaceCharAtlndexintchar MyString reverse Progl4ll Extra credit explain the title of this slide contains public boolean contains char c l for inti 0 ilt alength i ifali0 return true return false howMany public int howMany char c int result 0 for inti 0 ilt alength i ifai CH result return result public MyString replace char c1 char c2 char result new charalength for int i 0 ilt alength i if ai c1resul11i c2 else resultii ai return new MyStringresult public MyString reverse public MyString replaceCharAtIndex int n char c char result new charalength for int i 0 ilt alength i if i nresu11i c else resuti ai return new MyStringresult int n thisalength char result new charn forinti0iltni resul i thisani1i return new MyStringresult Reversing in Place public void reverse Progl412 public MyString addCharAtFront char c int n thisalength for m 39 0 i 39lt 2 i 39 char newA new chaqn1 chartemp thisai neWAIOl i 6 I thisai thisan1i f r 39 t 39 0 v 395 v 39 thisan 1 i temp newAi1 thisai int n thisalength return new MyStringnewA Progl4l3 deleteSpaces V1 1 Of 2 public MyString addCharAtRear char c int n thisalength char newA new chaqn1 forinti0iltn39 public MyString deleteSpaces newAi thisai int n 0 ifthisai 39 39 n newA c MyStringnewA for int i 0 i lt thisalength i l l return new char newA new charn int next how does this work Progl4l3 deleteSpaces V1 2 Of 2 for int i 0 i lt thisalength i ifthisai 39 39 newAnext thisai next return new MyStringnewA Progl4 15 deleteSpaces V3 public MyString deleteSpacesO char newA new cha for int i 0 ilt alength i if ai 39 char newerA new charnewAength1 for intj 0 j lt newAlength j werA wAj newerAnewA length ai newA newerA return new MyStringnewA Progl4l3 deleteSpaces V2 public MyString deleteSpacesO char newA new charthisalength int next inti i ltthisalength i if thisai 39 39 newAnext thisai next return new MyStringn ewAnext Progl416 deleteSpaces V4 public MyString deleteSpacesO String result for int i 0 i lt thisalength i if thisai 39 result thisai return new MyStringresult char Literals Chapter 9 In single quotes 39a or 39A39 or 39139 or39 char Escape sequences CMPU101 ProblemSolving and Abstraction Marc Smith i i Vassar College t tab Spring 2007 n new line i i i i char Size in Bits Don39t Confuse chars with Strings English requires only 7 bits 39a39 is a char quot3quot is a String ASCII uses 8 bits 256 chars Unicode uses 16 bitschar 65536 characters Covers all known languages String Methods Involving chars chars amp Strings char charAtint String s c int indexOfchar int astndexOfchar 39s39 quotpinquot a quotspinquot quotpinquot S i quotpinsquot Comparing chars with Relational Operators and I are obvious 39a39 lt 39b39 etc Every language has a collating sequence boolean isDigitchar Method 2 return 1 quot0123456789quotindexOfc Don39t grab random methods from the API boolean isDigitchar Method 1 return 39039 n 39139 H c 39239 boolean isDigitchar Method 3 return 39039 lt c ampamp c lt 39939 nClass Exercises public static boolean isVowel char public static boolean beginsWithVowel String public static boolean isLetter char public static boolean isConsonant char hasa Relationship Chapter 16 class Student Inheritance amp Class Hierarchies Private String name private Date dateOfBirth CMPU101 ProblemSolving and Abstraction Marc S 39 mlth a Student hasa String for its name Vassar COllege a student hasa Date for its dateOfBirth Spring 2007 In UML Terms isa Relationship student a Student ISa Person String name Every student object is also a Person object Date dateOfBirth Class student inherits data amp methods from Class Person UML for inheritance Terminology for Inheritance Person name inherits all elds of parent class child class Pars dateofBlrth and de nes ad res s superclass subclass more ofits base class derived class quotWquot No Person does Student not inherit anything from ma or ent 9133 clas sList transcript dvisor Syntax for Inheritance class Student extends Person Inheritance Issues What methods and variables of the superclass do we want the subclass to see What if the subclass wants to add a method orvariable with the same name as a method or variable of the superclass Extend PrintStream to inherit methods rLi PrintstreamFileOutputStream void printLJ void printf J void println J BetterPS BetterPSString BettezPS inherits mahods printquot print and println froszintStzeam M Inheritance Pro motes Software Reuse Start with a class A which is almost what we want Create subclass B that extends A and add additional capabilities to B Prog1602 Extends PrintStream to reduce typing in instantiation Current Code PrintStream ps new PrintStream new FileOutputStream new Filequotfooquot psprintlnquotheloquot Desired Code BetterPS bps new BetterPSquotfooquot bpsprintlnquotheoquot Extend PrintStream Use super to call superclass constructor class BetterPS extends PrintStream public BetterPS String filename throws Exception super new FileOutputStream new File filename Why not just modify existing code Code eg for PrintStream may not be available to us Existing code may be difficult to understand Our changes may break the existing code Progl603 Item item new Itemquotsoupquot129 Item item2 new Taxableltemquottissuequot189 Systemoutprintfquotitem1 costs 62fn item1getCost Systemoutprintfquotitem1 costs 62fnquot item2getCost Superclass constructor public Item String name double netCost thisname name this netCost netCost public double getCost return this netCost Overriding superclass methods String name double netCost Taxalfleite39 double getCost overrldes getCost double getCost Protected Visibility class Item protected String name protected double netCost public visible to all classes protected visible to this class and all of its subclasses private visible only in this class Subclass constructor uses super keyword class Taxableltem extends Item public Taxableltem String name double netCost supernamenetCost cas superclass constructor public double getCost overrides superclass method return thisnetCost 10 00825 declaring subclass variables and overriding superclass method Person String name Personstring String toString Student String major Studentstringstring String toString superclass Notice how method tostring occurs in both classes Superclass Person class Person protected String name protected means visible to subclasses public Person String name thisname name public String toString return thisname Progl605 name is private in superclass class Person private String name private variables can t be accessed by subclass public String toString return thisname Prog1604 Person bill new Personquotbiquot Student sue new Studentquotsue physicsquot Systemoutprintnbi Systemoutprintnsue Subclass Student class Student extends Person private String major ll not a eld in superclass Person public Student String name String major supername ll rst invokes superclass s constructor thismajor major then initializes new eld public String toString overrides superclass s method return thisname quot quot thismajor quotquot Invoking overridden methods in a superclass class Student extends Person private String major public String toString return supertoString quot quot thismajor quotquot supertoString invokes the toString method of the parent class h m Person Shadowing an Instance Variable Prog 1606 String data String data B void message Prog 1606 class B extends A class B extends A private String data ll private data shadows superclass data M public B Think of it like this B tring eld data eclipses A s super String eld data or that As data eld is hiding in the shadow of B s data eld thisdata quotB39s dataquot public void message SystemoutprintlnquotB has data quot this data 39 lto explicitly refer to superclass data use superdata ystemoutprintlnquotB has superdata quot superdata Overriding vs Overloading Don39t confuse overriding with overloading Overriding occurs when a subclass declares a method with the same prototype as a method in the superclass Overloading occurs when a single class contains methods with the same name but different signatures Prog 1606 class A class A protected String data II public A thisdata quotA39s dataquot II Object The Top of All Hierarchies Methods defined in the Object class and overridden in most subclasses public String toString public boolean equalsObject Single vs Multiple Inheritance Truck Boat Am phibiousVehicle Single vs Multiple Inheritance Plane Boat SeaPlane Single vs Multiple Inheritance Java only allows singe inheritance Interfaces can be used to achieve the effects of multiple inheritance The final Modifier Depending on the context Makes a variable constant Prevents a method from being overridden in a subclass Makes a class nonextendable it can39t have subclasses Single vs Multiple Inheritance Car Truck Minivan Inheritance amp Interface Are Orthogonal class A extends B implements C where B is a class from which A inherits variables and methods C is an interface with which A has made a contract Orthogonal When de ning a new class you may use either both or neither of inheritance and inter ces Suppose we want to crEte this hierarchy of class m Animal Hierarchy class Animal class Dog extends Animal class Cat extends Animal class Human extends Animal class Mime extends Human Each has public void speak Animal animals new AnimalMAX animals0 new Dog animals1 new Cato animals2 new Human animals3 new Dog animals4 new Mime animals5 new Cato animals6 new Animal forinti0iltMAX i animalsispeak An array ofAnimal objects may contain objects that are instances of any class that extends class Animal directly or indirec ly eg Mime extends Human which extends Animal Progl610 abstract class Animal abstract public void speak Any class which extends Animal will contain a concrete speak method or will be itselfabstract Animal Systemoutprintlnquot generic animal noise 7quot Dog Systemoutprintlnquotwoofquot Cat Systemoutprintlnquotmeowquot Human Systemoutprintlnquothelloquot Mime Systemoutprintln Abstract Classes Animal Too generic Animal should really be a placeholderfor all fields and behaviors that are shared by subclasses should be at the top of the hierarchy Let s make Animal an abstract class Abstract classes are not instantiable types Prohibited You can39t instantiate an abstract class it has no instances it39s only a placeholder in the class hierarchy But like an interface you can use an abstract class as a type for declaration of variables Stnngtusmngo Employee String ssn String tusmngo double pay Stnngtu smngo mmmmmw gamma double pay Su pose we want to create this hierarchy of class foran organization Here Person would most likely be abstract because it is too general to be an actual part of an organizat onal hierarchy Persons in an Organization Hourly They are paid at an hourlyRate UnionMembers They are paid at an hourIyRate but they are paid timeandahalf for hours worked over 40 hoursweek Persons in an Organization double total 00 Systemoutprintn forinti0iltMAXi total pe rsonnei pay Systemoutprintfquottota 72fquottotal Persons in an Organization Volunteer They get thanked they don39t get money Salaried Paid the same amount each week regardless of how many hours they work Each class has a pay method Persons in an Organization Person personnel new PersonMAX 11111111quot1200 personnel2 new HourlyquotAmber 222222222quot personnel3 new UnionMemberquotDiegoquotquot333333333quot10 personnel4 new VolunteerquotTanyquot personnel0 new VolunteerquotBill 1 m a o z z 1 u z m E n E Equot E amp n m Hourlypersonnel2addHours10 Hourlypersonnel3addHours41 NOTE To call a method particular to he Hourly class an object declared as a Person must be cast as an Hourly this is dangerous in practice and must be done with great care how do you know whether an element within an array of Person objects Is really an Hourly object Abstract Person abstract class Person private String name II public Person String name thisname name II public String toString return this name II abstract public double pay not implemented here II Vo luntee r class Volunteer extends Person public Volunteer String name supername public double pay System outprintlnquotThank quot supertoString 39 return 00 Salaried Employee class Salaried extends Employee private double weeklySalary public Salaried String name String ssn double weeklySalary supernamessn thisweeklySalary weeklySalary public double payo System outprintfquotPay 72fto snquot thisweeklySalary er toStringO return thisweeklySalary Unbn Class UrllorlMernber extends Hourly l publlc UrllorlMernber Strlrlg rlarne Strlrlg ssn double nourlyRate 5uperrlarney ssny nourlyRate tnis noursWorked o o l publlc double pay double mount tnis noursWorked tnis nourlyRate it tnis noursWorked gt 40 amount o 5 tnis noursWorked e 40 tnis nourlyRate l system out prlrltf Pay 7 2t includes oyertime to s n x amount upertoStrlrlgO tnis noursWorked 0 0 return amount Employee abstract class Employee extends Person protected String ssn it public Employee String name String ssn supername thisssn ssn u public String toString return supertoString quot quot thisssn quotquot Hourly Employee class Hourly extends Employee t protected double nourlyRate protected double noursWorked publlc Hourly Strlrlg narne Strlrlg ssny double nourlyRate supernamessn tnis nourlyRate tnis noursWorked nourlyRate 0 0 m publlc yoid addHours Hm publlc double pay double nourslltnis noursWorked noursl uble amount sWorked tnis nourlyRate system out prlrltf Pay 7 2tto s n tnis amount supertoStrlrlgO tnis noursvvor ed 0 0 return arn m l Previously Chapter 13 Our programs have worked with sequentially processing a fixed number of items Loops amp FIles Eg Read and print the first three lines in afile Sum the first ve numbers in a file CMPU101 ProblemSolving and Abstraction Marc Smi Vassar College Spring 2007 Chapter 13 Loops Programs work with a variable number of items Read amp print all the lines in a file Read print amp sum aIthe numbers in a file for when we know in advance how many times to loop while when we don39t The number 0f Iteratlons depends on the data39 Looping is often done with collections of data 3 Characteristics of Collections Some Collections Where stored Disk vs memory string Homogeneous vs heterogeneous file memm i ml Duplicates allowed array ls order of elements important vector Access Random vs just from the front linked list These couections are data structuresquot set the subject of CMPU 102 Patte rn Looping allows us to answer questions such as Given a file of ints how many are negative We can vary the collection but the pattern remains the same Vary the Datatype andor Criterion Given a file of ints how many are negative Given a file of ints how many are positive Given a file of strings how many are the empty string Given a file of strings how many are purely upper case Given a file of Complex how many are 0 Given a file of students how many got As Given a file of students how many failed Files as Collections Not random access Read from top to bottom from first line to last line Contain strings that we can convert to objects or read as ints using neXtInt Vary the Type of the Collection Given a le of ints how many are negative Given an array of ints how many are negative Given a set of ints how many are negative Given a tree of ints how many are negative Algorithm All variants of a pattern use the same algorithm Loop until done with data while cond stmt Normally we intend that cond false eventuall causing execution to continue w th the code after the loop else true Prog1301 ReadProcess Loop Given a file of strings print the Strings to the monitor String s while schasNext Note that the empty s scnextLine by hasta Systemoutprintlns Count the Number of Lines in a File Progl303 Here we don t int count 0 care about the while schasNext content of the string because we re not saving s as it is read We re just countin lines String s scnextLine count Other Accumulations Given a file of ints compute the sum compute the sum of the odd ints compute the sum of the squares of the ints compute the sum of the squares of the odd ints while loop with condition schasNext 1 Are we at the end of the file 2 If so then exit 3 Otherwise 4 Read Read a String from the file 5 Process Print that String 6 Go to Step 1 Progl304 of Odds of Evens int nOdd 0 int nEven 0 while schasNext In this case the file could have int n SCnethntO each number on if n2 0 nEven a new line or else nOdd many numbers on the same line Progl305 Given a file of ints compute the sum int sum 0 while schasNext int n scnextnt sum n Progl306 Given a file of ints compute the product int product 1 while schasNext l int n scnextlnt product n Progl307 Given a file of ints compute both the sum and the product int sum 0 int product 1 while schasNext int n scnextlnt sum n produc n 21 Progl309 Average of a File of ints int count 0 int sum 0 Note how the average is computed without using integer division int n scnextlnt mll39tip39yihg by 3 cou same as casting as a sum n dOUb39e while schasNext SystemoutprintlnquotThe average is quot 10 sumcount Accumulating Particular ltems Given a file of ints compute the sum of the odd ints int sum 0 while schasNext l int n scnextlnt if n2 0 l sum n Progl308 int sumE 0 the sum of the even ints int sumO 0 the sum of the odd ints while schasNext l int n scnextlnt if n2 0 SumE n This solves Given a file of ints else compute the sum of the even ints sumo n and the sum of the odd ints 22 Progl310 Average Reading the File Twice Scanner sc new Scannernew Filefilename int count 0 while schasNext l int n scnextlnt count scclose Progl310 Average cont Reading the File Again sc new Scannernew Filefilename int sum 039 Closing the file before while schasNext l creating a new file Scanner resets the int n SCnethntO Scanner to the top sum n line of the file SystemoutprintlnquotThe average is quot 10 sumcount Ancient Geek Proverb Change the implementation but don t change the interface In Chapter 14 we39ll change the implementation to an array of students but we won39t change the interface Section as in a course section at college A collection of Students In this chapter it s implemented as a le of Students Chapter 8 boolean CMPU101 ProblemSolving and Abstraction Marc Smith Vassar College Spring 2007 boolean Literals true false Systemout printlntrue boolean b false Systemoutprintlnb ProgOBOl SystemoutprintquotnEnter int 1 quot int i1 kbnextlnt SystemoutprintquotEnter int 2 quot int i2 kbnextlnt Systemoutprintlnquotni1 i2 quot i1 i2 Systemoutprintlnquotni1 lt i2 quot i1 lt i2 Up Until Now George Boole 18151864 logic true false Order of presentation literals relational operators logical operators Relational Operators lt less than lt less than or equal equal not equal gt greaterthan or equal gt greaterthan Watch Out for Precedence Suppose 11 is 17 and i2 is 99 Systemoutprintlnquotni1 Systemout printlnquotni1 Error is clone before and or not 252 Logical Operators These are defined by truth tabes Logical Or x y ll Y true true true true false true false true true false false false Operators We39ve Learned aIiLhmcLic operators relational opcmtors logical opcmtols Logical And X y x u y true true true true false false false true false false false false Logical Negation true false false true Precedence Equality and Objects they refer to the same object equals the corresponding slots are equal Predicates These are methods which return a boolean value We39ve seen boolean equalsString lnClass Exercise Add to class Rectangle public boolean isSquare public boolean isThin public boolean hasAreaGreaterThanRectange String s1 quothelloquot String s2 s1 String s3 quothequotconcatquotoquot 51 52 true 51 53 39 false 51equa1552 392 true 51equa1553 39 true ProgO 8 0 4 Integer Odd or Even SystemoutprintquotnEnter an int quot int n kbnextnt SystemoutprintlnquotEven quot 0 n2 SystemoutprintlnquotOdd quot 0 n2 static Predicates public static isEven int n return 0 n2 public static boolean isUpperCase String s return sequalsstoUpperCase Predicates for Later public static boolean isPrime int n public static boolean isPalindrome String s ShortCircuiting Also known as lazy evaluation Java only evaluates what it has to evaluate false ampamp booeanEXpresson booeanEXpresson is not evaluated true booeanEXpresson booeanEXpresson is not evaluated Mathematical Recursive Definitions Factorial 1 8 0 1 Recursive functions are characterized by nl n n 1 I 1 A base case Va ue w en recursion stops 39 39 2 A recursive operation The function calls itsef Recu rs IO n one base case The recursive operaton must bring the one recursive Step value closer to the base case CMPU101 ProblemSolving and Abstraction Marc Smith Vassar College Spring 2007 2 Fibonacci Numbers Recursive Methods fib0 1 A recursive method is one that calls itself either directly or fib1 1 indirectly fibn fibn 2 fibn1 Like recursive functions they have at least one base case 1 1 2 3 5 8 13 21 34 55 89 and at least one recursive expression two base cases one recursive step 3 4 Properties of Recursive Methods Closed Forms 1 The subproblems must have the same form as the 30 1 Recursiver deflned functions contain larger problem selfreferentialquot expressions Sn2Sn 11 2 There must be one or more instances that can be solved without recursion These are known as the base cases 50 1 SUI 2m1 1 s1 3 3 All recursive calls must make progress towards a 32 7 Closed forlns are formulae that base case so that the computation will halt S315 requ39re quot recurs39 3quot5 Infinite Recursion Prog1801 private static void f f Stack overflow occurs javaIangStackOverFowError when a Program runs out of space to keep track of method calls at Prog1801fProg1801java17 at Prog1801fProg1801java17 at Prog1801fProg1801java17 at Prog1801fProg1801java17 at Prog1801fProg1801java17 Stack Overflow 1 2 Your Mileage May Vary 3 Run Prog1802 on your computer system amp note how far you get before 4 observing a StackOverFlow error 5 16636 16637 16638 16639 HandTracing public static int a int X int y 2139 5 1 1a15 if x 0 return y base case 1 1 1 a0 5 return 1 ax1y recursive call 1 1 1 1 6 1 7 acursion 8 bottoms outquot at the call a05 What does method a mpute Counting Stack Depth Prog1802 class Prog1802 private static int depth 0 private static void f depth Systemoutprintndepth f0 For each invocation off Java has to remember the parameters of this invocation if any the return address where to resume execution after completing this particular invocation If f takes more parameters the stack will overflow sooner sumlnts public static int sumlnts int x t if x 0 return 0 base case int total sumlntsx1 recursive call return total x sumlnts4 MM Witt 3M WEN 3m WW 01 2 3 4 10 12 publie statie int sumlnts int x isPaIindrome public static boolean isPalindrome String s if slength 0 return true 2 base cases if slength 1 return true if scharAt0 scharAtslength 1 return false return isPaIindromessubstring1sength1 radar a ada a d a true ABBA a BB 6 a true x a true reader a eade 6 ad a false Making Java Trace For Us Prog1805 private static int b int n int indent for int i o i lt indent i Systemoutprintquot quot Systemoutprintlnquotgt bquot n quotquoti int result if n 0n1 result 1 else result bn2indent2 bn1indent2 for int i 0 i lt indent i Systemoutprintquot quot Systemoutprintlnquotlt bquot n quot retums quot result return result Tail Recursion return value of each recursive call is immediately returned no work remains to be done after recursive cas In this case the partial result recursive call as a return sumlntsHeIpern O parameter private statie int sumlntsHeIperint 11 int aee if x 0 return aee base ease aee aee 11 return sumlntsHeIperwel aee HandTracing ANALYSIS Compute the value of a particular call to a recursive function SYNTHESIS Play with examples until the recursive code becomes obvious Ggtjava Progl805 4 77gt flb4 77gt flb2 77gt flb0 ltii f1b0 returns 1 77gt flbl f1bl returns l lt f1b2 returns 2 77gt flb3 77gt flbl ltii f1bl returns 1 77gt flb2 77gt f1 O lt f1b0 returns 1 77gt flbl W f1 1 returns l lt f1b2 returns 2 lt f1b3 returns 3 lt f1b4 returns 5 m 5 When to Use Recursion When it makes the code easier to read without sacrificing speed Recursion in the Past Theory of computation What problems can amp can39t be solved Recursion in the Present Compiling Natural Language Processing NLP Artificial Intelligence Al Data structures trees and linked lists Computer graphics fractals Distributed amp parallel processing
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'