1.1
• •
1.2
1. 2. 3. 4.
1.3
• •
1.4
• •
People
Professor Wes Turner (12 noon lecture), Professor Chuck Stewart (2 pm lecture) TAs and programming mentors: see course website
Learning Outcomes
Demonstrate proficiency in the purpose and behavior of basic programming constructs.
Design algorithms and programs to solve small-scale computational programs.
Write, test and debug small-scale programs Demonstrateanunderstandingofthewidespreadapplicationofcomputationalthinkingtoreal-worldproblems.
Textbook
Practical Programming: An Introduction to Computer Science Using Python by Campbell, Gries, Montojo and Wilson
– Available in e-book form
Very important to get the second edition.
– If you bought the first edition from the campus bookstore you can return it and get the second edition. Website and On-Line Resources
Course notes will be posted at
http://www.cs.rpi.edu/academics/courses/fall16/cs1
Piazza will be used for posting homework assignments and labs, and for a public discussion site:
http://piazza.com/rpi/fall2016/csci1100/home
You need to sign up with your rpi.edu account.
CHAPTER ONE
LECTURE 1 — INTRODUCTION
1
CSCI-1100 Course Notes, Release 1
1.5 Other items from the syllabus
• Prof. Stewart’s and Dr. Turner’s office hours; others will be posted on-line
• Lab sections are held Tuesdays and Wednesdays
• Requirements and grading: lecture exercises, labs, homeworks, tests; letter grades • Appealing grades
• Class attendance and participation; lecture notes
• Homework late policy:
– 3 LATE DAYS FOR THE WHOLE SEMESTER
– 2 LATE DAYS ON ANY ONE ASSIGNMENT
• Academic integrity
• Other exceptions: report to me right now or as soon as you know • Notes on schedule:
– Labs start this week!
– No labs during the weeks of October 11-15 (Columbus Day, mid-semester break) and November 21-25
(Thanksgiving).
– Test dates are September 26, October 24, and November 21 all at 6 pm.
* Note that November 21 is the Monday of Thanksgiving week!
– Final exam will be held during finals week. No exceptions! So, don’t make departure plans until the final exam schedule is posted.
1.6 The Magic of Programming
• Cold, harsh logic, and
• Seemingly primitive syntax… • Leading to soaring creativity!
1.7 Types of Problems We Will Study
• Tools used to help you win at Words with Friends
• Image processing and manipulation
• Web searching and crawling
• Programs that work with data from Twitter and Flicker
• Numerical examples, including games and physical simulations • Perhaps even a simple version of (part of) Pokemon Go.
2
Chapter1. Lecture1—Introduction
1.8 Jumping In Quickly with Our First Program — Hello World
• We create a text file called hello.py containing just the two lines of Python code:
• This is done by launching the Wing IDE, which is specific to creating and running Python programs
– IDE stands for ’Integrated Development Environment’
– Two windows will appear — the top being the editor and the bottom being the Python interpreter
• Load the hello.py program
• Run it using the interpreter
• We can also type Python code directly into the interpreter.
1.9 Something a Bit More Interesting
• We are going to emphasize computational thinking throughout the semester, so let’s look at a fun little problem and get started.
• This problem is posed in Think Python and taken from the NPR show Car Talk. If you know the answer, do NOT say it!
Find the one word in the English language that contains three consecutive double letters.
• We will talk through the steps needed to develop and test a Python program to solve this problem.
– The file containing this program will be posted on the course website after class.
• We do not intend that you will understand the details of the program at this time. Rather, this is just an exercise
that illustrates the steps of solving a fun problem computationally.
• On the other hand, it does introduce some elements that will be seeing repeatedly throughout the semester:
– Files
– Functions – Loops
– Logic
– Counting – Output
– Libraries
• In about six weeks, you will understand all parts of this program!
• You can see the code in three_doubles
1.10 Looking Back: What Steps Did We Follow?
1. Developing an understanding of what the problem is really asking. This usually involves playing around with small examples.
CSCI-1100 Course Notes, Release 1
print(‘Hello, World!’)
print(‘This is Python’)
1.8. JumpingInQuicklywithOurFirstProgram—HelloWorld 3
CSCI-1100 Course Notes, Release 1
2. Developing and describing a recipe (an “algorithm”) for solving the problem • Most recipes will involve multiple parts — multiple functional steps
3. Turning this recipe into a program in the formal language of Python, one of many different programming lan- guages.
• English is too imprecise for specification of programs.
4. Running this program using the Python interpreter.
1.11 Programs, Compilers, Interpreters, Abstractions
• Python is an interpreted language — run immediately and interactively by the Python interpreter, which is itself another (very complex) program
• Programs in some other (non-interpreted) languages like C, C++ and Java must be compiled (by a “compiler” — another program) into a new program in machine assembly language and then executed.
• In both cases, we write programs that require other programs to run.
– And, we don’t just need just the compiler or interpreter — we need the file system, the operating system, and the command-line interpreter, each of them complicated, multi-part programs themselves.
• We don’t really think about the details of these programs; we just think of what they do for us.
– This is called an “abstraction”.
– It allows us to think about a problem we are trying to solve without thinking about all the details of all the other systems we are depending on.
– Thinking in terms of abstractions is fundamental to computer science. 1.12 Why Python
• Python has a very simple syntax
– The roles of indentation and blank lines cause the most confusion.
• Intepreted languages provide immediate, useful feedback
• Python has a powerful set of tools — abstractions
• Python is widely used in science, engineering and industry. • Python is good for rapid prototyping
– Sometimes, after a Python program is written and working, the most time-consuming steps are rewritten in either C or C++ and then integrated with the Python code.
1.13 Two Types of Errors in Our Python Programs
• •
•
A syntax error is a mistake in the form of the Python code that will not allow it to run.
A semantic error is a mistake in the “meaning” of the program, causing it to produce incorrect output, even if it
runs. Wewilldemonstratebothtypesoferrorsbydeliberatelyintroducingerrorsinourtripledoubleexampleprogram.
4
Chapter1. Lecture1—Introduction
1.14 Python Versions
• Python, like all programming languages, is continually under development. • We will be using the latest version, which is 3.5.2
1.15 Lab 0 — Tuesday and Wednesday!
By the end of Lab 0, each student will
1. Sign up at the course Piazza web site
https://piazza.com/rpi/fall2016/csci1100/home
2. Go to the course page
http://www.cs.rpi.edu/academics/courses/fall16/cs1/python_environment.html
and follow the instructions to install the Python environment on her/his computer.
• Thereareinstallersfor“native”versionsoftheenvironmentforWindows,MacOSXandLinuxmachines.
3. Create a Dropbox account to store back-up copies “in the cloud” of homework and lab solutions and lab for the course.
• Other cloud-based back-up copies are acceptable.
Students are encouraged to get started before lab, including downloading the environment.
CSCI-1100 Course Notes, Release 1
1.14. PythonVersions 5
45.1 Overview
• Whenafunctioncallsitself,itisknownasarecursivefunction.
• UseofthefunctioncallstackallowsPythontohandlerecursivefunctionscorrectly.
• Examplesincludefactorial,Fibonacci,greatestcommondivisor,flatteningalistoflists,andmergesort.
• We’llthinkabouthowtohand-simulatearecursivefunctionaswellasrulesforwritingrecursivefunctions.
45.2 Our First Example
• ConsiderthefollowingPythonfunction.
• Whatisthetheoutputfromthecall?
blast(5)
45.3 Python’s Call Stack Mechanism
The following mechanism helps us understand what is happening:
• Eachtimethecodemakesafunctioncall,Pythonputsinformationonthe“callstack”,including
– Allvaluesofparametersandlocalvariables
– Thelocationinthecodewherethefunctioncallisbeingmade.
• Pythonthenmakesthefunctioncall,switchingexecutiontothestartofthecalledfunction.
• This function in turn can make additional (potentially recursive) function calls, adding information to the top of the stack each time.
• Whenafunctionends,Pythonlooksatthetopofthestack,and
– restoresthevaluesofthelocalvariablesandparametersofthemostrecentcallingfunction,
CHAPTER
FORTYFIVE LECTURE 24 — RECURSION
def blast(n):
if n > 0:
print(n)
blast(n-1)
else:
print(“Blast off!”)
199
CSCI-1100 Course Notes, Release
– removesthisinformationfromthetopofthestack,
– insertsthereturnedvalueofthecalledfunction(ifany)intheappropriatelocationofthecallingfunc-
tion’s code, and
– continuesexecutionfromthelocationwherethecallwasmade.
45.4 Practice Problems to Illustrate This
What are the outputs of the following?
def rp1( L, i ):
if i < len(L):
print(L[i], end=' ')
rp1( L, i+1 )
else:
print()
def rp2( L, i ):
if i < len(L):
rp2( L, i+1 )
print(L[i], end=' ')
else:
print()
L = [ 2, 3, 5, 7, 11 ]
rp1(L,0)
rp2(L,0)
Note that the entirety of list L is not copied to the top of the stack. Instead, a reference (an alias) to L is placed on the stack.
45.5 Factorial
• Thefactorialfunctionis and
n!=n(n°1)(n°2)···1 0!=1
• Thisisanimprecisedefinitionbecausethe...isnotformallydefined.
• Writingthisrecursivelyhelpstoclearitup:
n!=n·(n°1)!
and
0!=1
The factorial is now defined in terms of itself, but on a smaller number!
• Notehowthisdefinitionnowhasarecursivepartandanon-recursivepart:
– The non-recursive part is called the base case. There must be at least one base case in every recursive function definition.
200
Chapter 45. Lecture 24 — Recursion
45.6 Exploring Factorial
We will:
• WritearecursivePythonfunctiontoimplementn!. • Hand-simulatethecallstackforn=4.
We’ll add output code to the implementation to help visualize the recursive calls in a different way.
45.7 Guidelines for Writing Recursive Functions
1. Define the problem you are trying to solve in terms of smaller / simpler instances of the problem. This includes
(a) Whatneedstohappenbeforemakingarecursivecall?
(b) Whatrecursivecall(s)mustbemade?
(c) Whatneedstohappentocombineorgenerateresultsaftertherecursivecall(orcalls)ends?
2. Definethebasecaseorcases.
3. Makesurethecodeisproceedingtowardthebasecaseineverystep.
45.8 Fibonacci
• TheFibonaccisequencestartswiththevalues0and1.
• Eachnewvalueinthesequenceisobtainedbyaddingthetwopreviousvalues,producing
0,1,1,2,3,5,8,13,21,34,55,... • Recursively, the nth value, fn, of the sequence is defined as
fn = fn°1 + fn°2 • Thisleadsnaturallytoarecursivefunction...
45.9 Dangers of Recursion
• Somerecursivefunctionimplementationscontainwastefulrepeatedcomputation.
• Recursivefunctioncalls—likeanyfunctioncalls—typicallyinvolvehiddenoverheadcosts.
• Often, therefore, a recursive function can (and should) be replaced with a non-recursive, iterative function that is significantly more efficient.
• ThisiseasytodoforbothFactorialandFibonacci,aswewillseeinclass.
CSCI-1100 Course Notes, Release
45.6. Exploring Factorial 201
CSCI-1100 Course Notes, Release
45.10 Why, Then, Do We Study Recursion?
• Manyofourdefinitionsandeven,ourlogicalstructures(suchaslists),areformalizedusingrecursion.
• Sometimesrecursivefunctionsarethefirstoneswecomeupwithandtheeasiesttowrite(atleastafteryou are comfortable with recursion).
– Onlylaterdowewritenon-recursiveversions.
• Sometimesonharderproblemsitisdifficulttoevenwritenon-recursivefunctions!Thelistflatteningprob-
lem below is one such example.
45.11 Advanced Examples
We’ll spend the rest of class on three more advanced examples: 1. Recursivegeometricshapes:theSierpinskitriangle
2. Flatteninganestedlist
3. Arecursiveversionofmergesort
45.12 Recursive Geometric Shapes
• Fractalsareoftendefinedusingrecursion.HowdowedrawaSierpinskitriangleliketheoneshownbelow?
• Wewilllookatthisexampleinclassandattempttodefinetherecursion.
• Toaidus,we’lllookataTkinterPythonprogramthatimplementsthedrawingoftheSierpinskitriangle.
202 Chapter 45. Lecture 24 — Recursion
45.13 Flattening a Nested List
• Supposewewanttotakealistsuchas
v = [[1,5], 6, [[2]], [3, [7, 8, [9,10], [11,12] ]]]
and “flatten” it, converting it to just a list of values with no sublists.
v = [ 1, 5, 6, 2, 3, 7, 8, 9, 10, 11, 12 ]
• This is challenging because we don’t know when we write a function to solve this problem how “deep” the
nesting of sublists goes. The solution should handle arbitrary depths:
– Many,manydatastructures(containers)incomputersciencehavethistypeofnested/recursivestruc- ture: an entry in a list may be another list....
• To solve this problem we will also need to know how to recognize when an entry in a list is another list. For this we need to use the type function in Python. The following example should make this clear:
• Now we are ready to solve the “flattening” problem. We’ll look at two different approaches. In both, the key will be to distinguish between handling elements that are lists (and therefore must be flattened recursively) and elements that are not lists. We’ll start from...
CSCI-1100 Course Notes, Release
>>> v = [ ‘a’, ‘b’, ‘c’]
>>> x = 12
>>> type(v) == list
True
>>> type(v[0]) == list
False
>>> type(x) == int
True
def flatten(L):
if __name__ == “__main__”:
v = [[1,5], 6, [[2]], [3, [7, 8, [9,10], [11,12] ]]]
print(v)
print(flatten(v))
45.14 Final Example: Merge Sort
• Thefundamentalideaofmergesortisrecursive: – Anylistoflength1issorted
– Otherwise:
* Splitthelistinhalf
* Recursivelysorteachhalf
* Mergetheresultingsortedhalves
45.13. Flattening a Nested List 203
CSCI-1100 Course Notes, Release
• WerepeatouruseofthemergefunctionfromLecture20:
def merge(L1,L2):
i1 = 0
i2 = 0
L = []
while i1
>>> print( list(map( len, v)) )
[4, 4, 2, 2]
191
CSCI-1100 Course Notes, Release
• map is an iterator class:
– It produces values in a sequence, one after another, by applying the function (1st argument) to the
values of the second argument.
– Technically,aniteratorclassisonethathasthe__next__methodimplemented(correctly).
– Usinglistgivesusthelistoflengthsofthesublistsexplicitly.
• Tocompletethesolutionweneedtojustapplysum:
Notice that this does not explicitly form an intermediate list.
43.4 Passing Functions as Parameters
• Theaboveexamplepassesthelenfunctionasanargument!
– WealsopassedfunctionsasargumentstoourcallbacksinourGUIprograms
• ThisillustratestheconceptthatPythontreatsfunctionas“first-class”objects-inotherwordsfunctionscan be used just like variables and other data.
– What’spassedasanargumenttomap()isthelocationofthefunctioncode.
• Now suppose we want to find the maximum distance of a list of points from the origin. Here we’ll have to
write a function
43.5 Lambda functions: Anonymous functions
• Wecanavoidtheneedtowriteaseparatefunctionherebywritingananonymousfunctioncalledalambda function.
• Ourfirstexampleisjustsquaringthevaluesofalist
• Now,wecansumthesquaresfrom1ton
• Wecanalsoimplementthedist2Dfunctionanonymously:
• Notice that we did not need to explicitly form a list in each of the preceeding examples. This leads to sub- stantial savings when the list is large!
>>> print sum(map(len,v))
12
def dist2D( p ):
return (p[0]**2 + p[1]**2)**0.5
pts = [ (4.5, 3), (2.1,-1), (6.8,-3), (1.4, 2.9) ]
print(max( map(dist2D,pts) ))
>>> list(map( lambda x: x**2, [ 1, 2, 3, 4 ] ))
[ 1, 4, 9, 16 ]
>>> n = 100
>>> sum( map( lambda x: x**2, range(1,n+1)))
>>> max( map( lambda p: (p[0]**2 + p[1]**2)**0.5, pts) )
7.432361670424818
192 Chapter 43. Lecture 23 — Advanced Python Topics and Functional Programming
• Aside:thenotionofalambdafunctiongoesallthewaybacktotheoriginofcomputerscience
43.6 In-Class Practice Problem:
1. Startingwiththefollowinglistofx,ypointcoordinatetypes,wewillusemap(),alambdafunction,andmax() to find the maximum x coordinate (the 0-th coordinate) in a list of points.
pts = [ (6,-1), (8,4), (7.5,-3), (4.4,12), (7,2) ]
43.7 Lecture Exercises, Problems 1 and 2:
• Atthispointstudentswillbegiventhechancetoworkonthefirsttwolectureexercises.
43.8 Filter: Extract / eliminate values from a list
• Consideradifferentproblem:howtoeliminateallofthenegativevaluesfromalist.Basedonwhatweknow so far, this requires a for loop with append.
• Wecansimplifythisusingthebuilt-inPythonconstructcalledfilter
• Here,
– ThelambdafunctionmustproduceabooleanvalueandifthatvalueisTruethelistitemiskept;oth- erwise it is eliminated.
– The result of filter is an iterator object, just like the result of map is. We convert to a list in order to display the answer.
• Ifwewanttosumupthenon-negativevalues,thenwedon’tneedtoexplicitlygeneratealist:
43.9 Passing Functions to Sort
• Considertheproblemofsortingalistof(x,y)pointsbytheiryvaluesfirstandtheirxvaluesfortiedyvalues, both in decreasing order. For example, given
we’d like the sorted order to be
• ThePythonsortfunction
CSCI-1100 Course Notes, Release
>>> v = [ 1, 9, -4, -8, 10, -3 ]
>>> list(filter( lambda x: x>0, v))
[1, 9, 10]
>>> sum(filter( lambda x: x>0, v))
20
pts = [ (2,5), (12,3), (12,1), (6,5), (14, 10), (12, 10), \
(8,12), (5,3) ]
[(8, 12), (14, 10), (12, 10), (6, 5), (2, 5), (12, 3), \
(5, 3), (12, 1)]
43.6. In-Class Practice Problem: 193
CSCI-1100 Course Notes, Release
>>> sorted( pts, reverse=True )
[(14, 10), (12, 10), (12, 3), (12, 1), (8, 12), (6, 5), \
(5, 3), (2, 5)]
gives the ordering by x value and then by y value. This is not what we want.
• The first step to a solution is to provide a key function to sorted() to pull out the information (the y value in this case) from each tuple to use as the basis for sorting:
This is close but not quite right because the two points with y=5 are out of order.
• Thetrickistosortbyxfirstandthensortbyy!
• This works because sorted() uses what’s known as a stable sort: when two values are “tied” according the sorting criteria (y value in the second sort) their relative ordering (by x value from the first sort) in the final list is preserved.
– Therefore,(6,5)comesearlierthan(2,5),while(12,3)comesearlierthan(5,3)
• Anumberofvariationsonsortingusethis“stablesort”property,butnotallfastsortingalgorithmsarestable.
43.10 Practice Problem
1. Usefiltertoeliminateallwordsthatareshorterthan4lettersfromalistofwords 43.11 List Comprehensions
• InsteadofmapandfiltersomepeoplepreferanotherexampleoffunctionalprogramminginPythoncalled list comprehensions
• Hereisanexampletogeneratealistofthesquaresofthefirstnintegers:
• Theformofthisisanexpressionfollowedbyaforloopstatement.
• Wecangettheeffectoffilterbyaddingaconditionalattheend:
• Here,thevaluesareonlygeneratedintheresultantlistwhentheifconditionpasses.
194 Chapter 43. Lecture 23 — Advanced Python Topics and Functional Programming
>>> sorted( pts, key = lambda p: p[1], reverse=True)
[(8, 12), (14, 10), (12, 10), (2, 5), (6, 5), (12, 3), \
(5, 3), (12, 1)]
>>> by_x = sorted(pts,reverse=True)
>>> by_x
[(14, 10), (12, 10), (12, 3), (12, 1), (8, 12), (6, 5), \
(5, 3), (2, 5)]
>>> sorted( by_x, key = lambda p: p[1], reverse=True)
[(8, 12), (14, 10), (12, 10), (6, 5), (2, 5), (12, 3), \
(5, 3), (12, 1)]
n=8
>>> [ i*i for i in range(1,n+1) ] [1, 4, 9, 16, 25, 36, 49, 64]
>>> v = [ 1, 9, -4, -8, 10, -3 ]
>>> [ x for x in v if x>0 ]
[1, 9, 10]
• We can combine these as well. As a slightly silly example, we can eliminate the negative values and square the positive values
• Wecangetevenmoresophisticatedbynestingforloops.Hereisanexamplewherewegenerateallpairsof numbers between 1 and 4, except for the pairs where the numbers are equal
43.12 Exercises
1. Writealistcomprehensionstatementtogeneratealistofallpairsofoddpositiveintegervalueslessthan10 where the first value is less than the second value.
43.13 Summary and Discussion
• We’ve explored programming that is more compact and at a higher level of abstraction. It can be used to effectively interact with data.
• map and filter each take a function and a sequence (an “iterable”) as arguments and produce an iterator as a result:
– map produces the result of applying the function to each element of the iterable
– filter produces each element of the iterable for which the function returns True
• Bothmapandfilteraremademorecompactbyusinglambdafunctions
• lambda functions can also be used to change the result of sorting
• Astablesortpreservestherelativeorderof“tied”values
• Listcomprehensionscanbeusedinplaceofmapandfilter:
– Somepeoplepreferlistcomprehensionsbecausetheyoftendonotrequirelambdafunctions,but…
– List comprehensions explicitly construct the list of results rather than generating them one-by-one,
which is what map and filter do. This makes them less efficient for large data sets.
• Theseareallexamplesoffunctionalprogramming.
• We’vealsousedtheothermajorprogrammingparadigmsthissemester
– imperativeprogramming
– objectorientedprogramming
• Many modern languages like Python provide tools that allow programming using a combination of
paradigms
CSCI-1100 Course Notes, Release
>>> v = [ 1, 9, -4, -8, 10, -3 ]
>>> [ x*x for x in v if x>0 ]
[1, 81, 100]
>>> [ (i,j) for i in xrange(1,5) for j in xrange(1,5) if i != j ]
[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2),
(3, 4), (4, 1), (4, 2), (4, 3)]
43.12. Exercises 195
35.1 Overview
• Reviewofclasses
• RevisitingourYelpdata:aRestaurantclass. • Techniquesthatwewillsee:
CHAPTER
THIRTYFIVE LECTURE 19 — CLASSES, PART 2
– Callingclassmethodsfromwithintheclass
– Classobjectsstoringotherobjects,suchaslists – Listsofclassobjects
35.2 Review of Classes
We will use our Point2d class solution from Lecture 18 to review the following: • Attributes:
– Thesestorethedataassociatedwitheachclassinstance.
– Theyareusuallydefinedinsidetheclasstocreateacommonsetofattributesacrossallclassinstances. • Initialization:function__init__calledwhentheobjectiscreated.
– Shouldassigninitialvaluestoallattributes • Methods
– Eachincludestheobject,oftenreferredtoasself,asthefirstargument.
– Somechangetheobject,somecreatenewobjects
• Specialmethodsstartandendwithtwounderscores.Pythoninterpretstheiruseinavarietyofdistinctways:
– __str__ is the string conversion function
– __add__, __sub__, etc. become operators
• Eachofthesespecialmethodsbuildsonthe“moreprimitive”methods
157
CSCI-1100 Course Notes, Release
35.3 Larger Example — Restaurant Class
Recall Lab 5 on the Yelp data:
• Readandparseinputlinesthatlooklike:
• Findrestaurantsandprintoutinformationbasedonauserselection • Originalimplementationbasedonalistwasawkward:
– Wehadtoremembertheroleofeachindexofthelist—0wasthename,1wasthelatitude,etc. • Newimplementationhereisbasedonaclass
35.4 Start to a Solution, the Main Code
Let’s look at lec19_restaurants_exercise.py, downloadable as part of the Lecture_19 zip file: • ThisisthecodethatusestheRestaurantclass.
– Westartbyconsideringhowtheclasswillbeusedratherthanhowwewriteit. • Mainfunctiontoinitializearestaurantiscalledconvert_input_to_restaurant
– Parsesarestaurantline
– CreatesandreturnsaRestaurantobject • Functionbuild_restaurant_list
– Openstheinputfile
– Readseachline
– Callsconvert_input_to_restaurant,andappendstheresultingrestauranttothebackofalist
• Maincode:
– Buildstherestaurantlist
– Printsthefirstthreerestaurantsinthelist
– Includescommented-outcodethat
* Getsthenameofacity
* Findstherestaurantwiththehighestaveragerating We will complete this code soon.
35.5 Functionality Needed in the Restaurant Class
• Somefunctionalityisdeterminedbyreadingthecodewehavealreadywritten – Includesbothmethodsandattributes
• Add other functionality by considering the methods that must be in the Restaurant class, including the parameters that must be passed to each method.
The Greek House|42.73|-73.69|27 3rd St+Troy, NY 12180|\
http://www.yelp.com/biz/the-greek-house-troy|Greek|1|5|4|5|4|4|5|5|5|5|5|4
158
Chapter 35. Lecture 19 — Classes, Part 2
• Addattributeslast…
35.6 Turning to the Actual Restaurant Class
Look at Restaurant.py which was distributed with the Lecture_19 files. • The__init__functionspecifiestheattributes.
– Otherattributescouldbeadded,suchastheaveragerating,butinsteadthesearecomputedasneeded by methods.
– Importantly, each class object stores a list of ratings, illustrating the fact that classes can store data structures such as lists, sets, and dictionaries.
• TheRestaurantclasshasmorecomplicatedattributesthanourpreviousobjects – Point2dobject,
– Alistfortheaddressentries
– Alistofscores
• Thereisnothingspecialaboutworkingwiththeseattributesotherthanthey“feel”morecomplicated.
– Justapplywhatyouknowinusingthem – Ourlectureexerciseswillhelp
35.7 In-Class Example
Together we will add the following two methods Restaurant to get our demonstration example to work: 1. Theis_in_citymethod
2. Theaverage_reviewmethod
35.8 Discussion
• WhatisnotintheRestaurantclass?
– Noinputorlineparsing.Usually,wedon’twanttheclasstiedtotheparticularformoftheinput. – Asanalternative,wecouldaddamethodforeachofseveraldifferentformsofinput.
• Oftenitishardtomakethedecisionaboutwhatshouldbeinsideandwhatshouldbeoutsidetheclass.
– Oneexamplethemethodwewrotetotestifrestaurantisinaparticularcity.Asanalternativewecould have written a different method that returns that name of the city and make the comparison outside the class.
• WecouldaddanAddressclass:
– Reuseforobjectsotherthanrestaurants
– Notneededinthis(relatively)shortexample.
– Moreflexiblethanouruseofalistofstringsfromanaddressline.
CSCI-1100 Course Notes, Release
35.6. Turning to the Actual Restaurant Class 159
CSCI-1100 Course Notes, Release
35.9 Summary
• ReviewofthemaincomponentsofaPythonclass: – Attributes
– Methods
– Specialmethodswithnamesstartingandendingwith__
* Initializermethodismostimportant
• ImportantusesofPythonclassesthatwehaveseentoday:
– Classescontainingotherobjectsasattributes
– Listsofclassobjects. • DesignofPythonclasses
– Startbyoutlininghowtheyaretobeused
– Leadstodesignofmethods
– Specificationofattributesandimplementationofmethodscomeslast
160 Chapter 35. Lecture 19 — Classes, Part 2
33.1 Overview
CHAPTER
THIRTYTHREE LECTURE 18 — CLASSES, PART 1
• Defineourowntypesandassociatedfunctions • Encapsulatedataandfunctionality
• Raisethe“levelofabstraction”inourcode
• Makecodeeasiertowriteandtest
• Reusecode
33.2 Potential Examples
In each of these, think about what data you might need to store to represent the “object” and what functionality you might need to apply to the data.
• Date
• Time
• Point
• Rectangle • Student
• Animal
• Molecule
33.3 An Example from Earlier in the Semester
• ThinkabouthowdifficultitwastokeeptrackoftheinformationabouteachrestaurantintheYelpdata. • Youhadto:
– Remembertheindicesof(a)therestaurantname,(b)thelatitudeandlongitude,(c)thetypeofrestau- rant, (d) the address, etc.
– Formaseparatelistinsidethelistfortheratings.
– Writeadditionalfunctionstoexploitthisinformation • Ifweusedaclasstorepresenteachrestaurant:
147
CSCI-1100 Course Notes, Release
– Alloftheinformationabouttherestaurantwouldbestoredandaccessedasnamedattributes
– Informationabouttherestaurantswouldbeaccessedthroughfunctionsthatwewritefortheclass.
33.4 Point2d Class
• Simplest step is to just tell Python that Point2d will exist as a class, deferring the addition of information until later.
• ThePythonreservedwordpasssaysthatthisistheendoftheclassdefinition. – Wewillnotneedthislaterwhenweputinformationintotheclass.
33.5 Attributes
• Classesdonotgetinterestinguntilweputsomethinginthem.
• Thefirstthingwewantisvariablessothatwecanputdataintoaclass.
– InPythonthesevariablesareoftencalledattributes.
– Otherlanguagescallthemmembervariables.
• Wewillseethreedifferentwaystospecifyattributes.
33.6 Assigning Attributes to Each Instance
• Pointshaveanxandaylocation,sowecanwrite,forexample,
• Wehavetodothisforeachclassinstance. • Thisispronetomistakes:
– Couldforgettoassigntheattributes
– Couldaccidentallyusedifferentnamesforwhatisintendedtobethesameattribute. • Exampleofanerror
class Point2d(object):
pass
from math import sqrt
p = Point2d()
p.x = 10
p.y = 5
dist_from_origin = sqrt(p.x**2 + p.y**2)
q = Point2d()
q.x = -5
dist_from_origin = sqrt(q.x**2 + q.y**2) # q.y does not exist
148 Chapter 33. Lecture 18 — Classes, Part 1
CSCI-1100 Course Notes, Release
33.7 Defining the Attributes Inside the Class
• Thesimplestwaytomakesurethatallvariablesthatareinstancesofaclasshavetheappropriateattributes is to define them inside the class.
• Forexample,wecouldredefineourclassas
• AllinstancesofPoint2dnowhavetwoattributes,xandy,andtheyareeachinitializedto0.
• Wenolongerneedthepassbecausethereisnowsomethingintheclass.
33.8 Defining the Attributes Through An Initializer / Constructor
• Westillneedtoinitializexandytovaluesotherthan0:
• Whatwe’dreallyliketodoisinitializethematthetimeweactuallycreatethePoint2dobject: p = Point2d(10,5)
• We do this through a special function called an initializer in Python and a constructor in some other pro- gramming languages.
• Insidetheclassthislookslike
• Ourcodetocreatethepointnowbecomes
p = Point2d(10,5)
• Notes:
– Pythonusesnamesthatstartandendwithtwo’_’toindicatefunctionswithspecialmeanings.More on this later in the lecture.
– Thenameselfisspecialnotationtoindicatethattheobjectitselfispassedtothefunction.
• Ifwe’dliketoinitializethepointto(0,0)withoutpassingthesevaluestotheconstructoreverytimethenwe
can specify default arguments
allowing the initalization
class Point2d(object): x=0
y=0
p = Point2d()
p.x = 10
p.y = 5
class Point2d(object):
def __init__( self, x0, y0 ):
self.x = x0
self.y = y0
class Point2d(object):
def __init__( self, x0=0, y0=0 ):
self.x = x0
self.y = y0
33.7. Defining the Attributes Inside the Class 149
CSCI-1100 Course Notes, Release
p = Point2d()
33.9 Methods — Functions Associated with the Class
• Wecreatefunctionsthatoperateontheclassobjectsinsidetheclassdefinition:
import math
class Point2d(object):
def __init__( self, x0, y0 ):
self.x = x0
self.y = y0
def magnitude(self):
return math.sqrt(self.x**2 + self.y**2)
def dist(self, o):
return math.sqrt( (self.x-o.x)**2 + (self.y-o.y)**2 )
these are called methods
• Thisisusedas
• The method magnitude takes a single argument, which is the Point2d object called self. Let’s examine this:
– The call q.magnitude() appears to have no arguments, but when Python sees this, it turns it into its equivalent:
Point2d.magnitude(q)
which is completely legal Python syntax.
– The name self is not technically special in Python, but it is used by convention to refer to the object that the method is “called upon”. This is q‘ in the call q.magnitude()
• ThemethoddisttakestwoPoint2dobjectsasarguments.Theexamplecall p.dist(q)
becomes
Point2d.dist(p,q)
so now argument p maps to parameter self and argument q maps to parameters o
33.10 Lecture Exercises, Part 1
Our lecture exercises for today will involve adding to the Point2d class and testing it. Make sure you have down- loaded the Point2d.py file from the Piazza site.
p = Point2d(0,4)
q = Point2d(5,10)
leng = q.magnitude()
print(“Magnitude {:.2f}”.format( leng )) print(“Distance is {:.2f}”.format( p.dist(q)))
150 Chapter 33. Lecture 18 — Classes, Part 1
We will allow some time to work on the first lecture exercise.
33.11 Operators and Other Special Functions
• We’dliketowritecodethatusesournewobjectsinthemostintuitivewaypossible.
• Forourpointclass,thisinvolvesuseofoperatorssuchas
• Notice how in each case, we work with the Point2d variables (objects) just like we do with int and float variable (objects).
• Weimplementthesebywritingthespecialfunctions__add__,__sub__,and__neg__
• Forexample,insidethePoint2dclasswemighthave
Very important: this creates a new Point2d object.
• WhenPythonseesp+q,itturnsitintothefunctioncall
Point2d.__add__(p,q)
which is exactly the syntax of the function definition we created.
• Wehavealreadyseenthiswithoperatorsonintegersandstrings.Asexamples,
5+6
is equivalent to
int.__add__(5,6) and
str(13)
is equivalent to
int.__str__(13)
• Implicit in this discussion is the notion that int is in fact a class in Python. The same is true of str and
float and list.
• Notethatwecanalsodefinebooleanoperatorssuchas==and!=throughthespecialfunctions__eq__and
__neq__
33.12 Classes and Modules
• Eachclassshouldgenerallybeputintoitsownmodule,orseveralclosely-relatedclassesshouldbecombined in a single module.
CSCI-1100 Course Notes, Release
p = Point2d(1,2)
q = Point2d(3,5)
r = p+q
s = p-q
t = -s
def __add__(self,other):
return Point2d(self.x + other.x, self.y+other.y)
33.11. Operators and Other Special Functions 151
CSCI-1100 Course Notes, Release
– WearealreadydoingthiswithPoint2d.
• DoingsoisgoodpracticeforlanguageslikeC++andJava,whereclassesareplacedinseparatefiles. • Testingcodecanbeincludedinthemoduleorplacedinaseparatemodule.
• Wewilldemonstratethisinclassandposttheresultonthecoursewebsite.
33.13 More Lecture Exercises
At this point we will stop and take a bit of time to work on the next part of the lecture exercises.
33.14 When to Modify, When to Create New Object
• Somemethods,suchasscale,modifyasinglePoint2dobject
• Othermethods,suchasouroperators,createnewPoint2dobjectswithoutmodifyingexistingones.
• The choice between this is made on a method-by-method basis by thinking about the meaning — the se- mantics — of the behavior of the method.
33.15 Programming Conventions
• Don’tcreateattributesoutsidetheclass.
• Don’tdirectlyaccessorchangeattributesexceptthroughclassmethods.
– LanguageslikeC++andJavahaveconstructionsthatenforcethis.
– InlanguageslikePythonitisnotahard-and-fastrule.
• Class design is often most effective by thinking about the required methods rather than the required at-
tributes.
– Asanexample,werarelythinkabouthowthePythonlistanddictclassesareimplemented.
33.16 Time Example
• Intheremainderofthelecture,wewillworkthroughanextendedexampleofaTimeclass
• Bythis,wemeanthetimeofday,measuredinhours,minutesandseconds.
• We’llbrainstormsomeofthemethodswemightneedtohave.
• We’llthenconsiderseveraldifferentwaystorepresentthetimeinternally:
– Hours,minutesandseconds – Secondsonly
– Militarytime
• Despite potential internal differences, the methods — or at least the way we call them — will remain the same
– Thisisanexampleofthenotionofencapsulation,whichwewilldiscussmoreinLecture19.
152 Chapter 33. Lecture 18 — Classes, Part 1
• Attheendoflecture,theresultingcodewillbepostedandexerciseswillbegeneratedtocompletetheclass definition.
33.17 Summary
• DefinenewtypesinPythonbycreatingclasses
• Classesconsistofattributesandmethods
• Attributesshouldbedefinedandinitializedthroughthespecialmethodcall__init__.Thisisaconstructor • Otherspecialmethodsallowustocreateoperatorsforourclasses.
• WelookedataPoint2dandTimeexample.
CSCI-1100 Course Notes, Release
33.17. Summary 153
31.1 Overview
• Recap
• MoreIMDBexamples:
CHAPTER
THIRTYONE LECTURE 17 — DICTIONARIES, PART 2
– Dictionariesofstring/setpairs
– Convertingdictionarieswithonekeytoanother
– Combininginformationfrommultipledictionaries
• Adifferentviewofdictionaries:storingattribute/valuepairs. • AccessingAPIsandgettingdatabackasadictionary.
31.2 Recap of dictionaries
• Onthesurface,dictionarieslooklikelists,except,youcanhaveanythingforindices(keys),notjustnumbers starting with 0.
• Thefollowingtwostorethesameinformation:
Note that this is a new way for us to initialize a dictionary.
• Youwouldaccesstheminthesameway:
• Youwouldupdatetheminthesameway:
• Butyoucan’textendtheminthesameway.Forexample:
>>> listoption[10] = ‘e’ is illegal, but:
>>> listoption = [‘a’,’b’,’c’]
>>> dictoption = {0:’a’, 1: ‘b’, 2:’c’}
>>> listoption[1]
‘b’
>>> dictoption[1]
‘b’
>>> listoption[1] = ‘d’
>>> dictoption[1] = ‘d’
139
CSCI-1100 Course Notes, Release
>>> dictoption[10] = ‘e’
is perfectly fine. Be sure you can explain why.
• Ofcoursethepowerofadictionaryisthatkeyscanbeanything:
• Thisdictionaryhasstringsaskeysandintegersasvalues.Thevaluescanbeanythingaswell:
• Note that since keys can be anything, to print or iterate through the values in a dictionary. This is actually quite trivial using a dictionary:
>>> d2.keys()
dict_keys([‘Gru’, ‘Margo’])
>>> list(d2.keys())
[‘Gru’, ‘Margo’]
>>> for key in d2: # or, for key in d2.keys(): … print(key, d2[key])
Gru {[123, 456]}
Margo {[456]}
31.3 Copying and Aliasing Dictionaries
• We’lltakeafewminutesinclassforyoutotrytopredicttheoutputofthefollowing:
d = dict()
d[15] = ‘hi’
L = []
L.append(d)
d[20] = ‘bye’
L.append(d.copy())
d[15] = ‘hello’
del d[20]
print(L)
• The result may surprise you, but it reflects the difference between making an alias to an object and making a full copy of an object.
– Analiasisalsosometimesknownasashallowcopy
– Afullcopyisalsosometimesknownasadeepcopy
• Assignmentbetweenlists,betweensets,andbetweendictionariesallinvolvealiasing/shallowcopying!
• Atthispointwewilltakeafewminutesforyoutoworkonthefirstlectureexercise.
31.4 Back to IMDB: Dictionaries Whose Values Are Sets
• In our IMDB data, an individual may be listed more than once for each movie. For example, Tom Hanks is listed six times for Polar Express
140
Chapter 31. Lecture 17 — Dictionaries, Part 2
>>> d = {‘Gru’:3, ‘Margo’:4}
>>> d[‘Gru’]
3
>>> d2 = {‘Gru’: set( [123,456] ), ‘Margo’: set( [456] ) }
>>> d2[‘Gru’]
{456, 123}
• In order to determine who was involved in the most different movies, we need to keep a set of movies for each individual instead of a count.
• WewillmodifyoursolutiontotheIMDBexampletofindoutwhowasinvolvedinthemostdifferentmovies? – Thesolutionwillbepostedonthecoursewebsite.
31.5 Converting to Other Dictionaries: The N Busiest Individuals
• Supposewewanttofindthetop10or25busiestindividualsintheIMDB,basedonthenumberofdifferent movies they are involved in.
• Nowweneedadifferentdictionary:
– Keysareintegersrepresentingthenumberofmovies – Valuesarelistsofactors.
* Whydon’tweneedsetshere?
• Wewillshowhowtoextendourcodetobuildthisdictionaryfromouroriginaldictionary.
• Next, we will need to access the keys from this dictionary in reverse order and print out names of the indi- viduals, stopping when we’ve printed the top N busiest (allowing more in the case of ties).
31.6 More That We Can Do With the IMDB
• Wenowhaveanactorsdictionarywhosekeysareactornamesandwhosevaluesaresetsofmovies.
• Wecanalsoconstructadifferentdictionarywhosekeysaremoviesandwhosevaluesaresetsofactors. • Usingthiswecanfindallsortsofinformation:
– Whatmovieinvolvedthemostpeople?
– HowmanydifferentpeoplehavebeeninmoviesthatincludedMerylStreep? – Solvethe“degreesofKevinBacon”problem:
1. WhohasbeeninamoviewithKevinBacon?Thesepeoplearedegree1.
2. Who is not a degree 1 individual and has been in a movie with a person who was in a movie with Kevin Bacon? These people are degree 2 individuals.
3. Whoisnotadegree1or2individual,andhasbeeninamoviewithadegree2individual(inamovie with a person who has been in a movie with a person who was in a movie with Kevin Bacon)? These people are degree 3 individuals.
4. Etc.
31.7 Attribute / Value Pairs
• We can use dictionaries to construct even more complicated data structures: dictionaries as values, lists of dictionaries, etc.
• Considertheproblemofrepresentingallthehousesarealestatecompanyistryingtosell.
• Wecouldkeepalistwithinformationabouteachproperty,butalistofwhat?
CSCI-1100 Course Notes, Release
31.5. Converting to Other Dictionaries: The N Busiest Individuals 141
CSCI-1100 Course Notes, Release
• We will look at describing each house as a dictionary, with the keys being the “attributes”, and the values being, well, the values of the attributes.
• Examplesincludethelistingreferencenumber,theaddress,thenumberofbedrooms,theprice,whetheror not it has a pool, the style of the house, the age, etc.
– Somepropertieswillnotbeknownandthereforetheywillnotberepresentedinthedictionary.
• We will work through a made-up example in class, producing a list of dictionaries. This list will be called
houses.
• As an exercise you can think about write coding that finds all houses in our house list that have at least 4 bedrooms (attribute is bedrooms, value is an integer), a pool (attribute is pool, value a string describing if the pool is above ground or below), for a price below $300,000 (atttribute is price, value is an int).
• Overall,thisasimplePythonimplementationofthestorageandaccessofinformationinadatabase. 31.8 Accessing APIs
• ManyAPIs(ApplicationProgrammingInterfaces)accessibleontheinternetreturnvaluesthatareJSON(Java Script Object Notation) strings. These are easily loaded into Python objects, often involving dictionaries.
• The best way to understand the dictionary structure returned by an API is to seek documentation. If that fails, you can print the top level keys and values to explore.
• PublicAPIs,whichdonotnotrequireauthentication,areaccessedasfollows:
• AfewexamplesofpublicAPIsare(bothusedinourimagelab):
1. nominatim that gives you a bounding box of geolocation for a given location. Let’s see this for ‘Troy, NY’:
2. panaromio that returns the url for pictures of a given box of geolocations. The following is for ‘Troy, NY’, box obtained from the above call:
• Many sources require authentication with an API key through the oauth2 authentication module. But, the overall method of access remains the same after authentication.
• Onceweunderstandthestructure,wecanwritecodetoextracttheinformationwewant.
import urllib.request
import json
url = “enter your public url here”
f = urllib.request.urlopen(url)
rawcontent = f.read()
content = json.loads(rawcontent.decode(“utf-8”))
url = “http://nominatim.openstreetmap.org/”\
“search?q={} &format=json&polygon_geojson=1&addressdetails=0″\ .format(‘Troy,NY’)
url = “http://www.panoramio.com/map/get_panoramas.php?set=public&”\ “from=0&to=5&minx={}&miny={}&maxx={}&maxy={}&size=medium&mapfilter=true” \ .format(‘-73.8517851′,’42.5684117′,’-73.5317851′,’42.8884117′)
142 Chapter 31. Lecture 17 — Dictionaries, Part 2
CSCI-1100 Course Notes, Release
31.9 Final Example
1. Giventhefollowingdictionaryforhobbiesforpeople:
hobby = {‘Gru’:set([‘Hiking’,’Cooking’]), ‘Edith’:set([‘Hiking’,’Board Games’])} create a new dictionary that lists people for each hobby:
{‘Hiking’: {‘Gru’,’Edith’}, ‘Cooking’:{‘Gru’}, ‘Board Games’:{‘Edith’}}
31.10 Summary
• Dictionariesofsets.
• Dictionarieswherethekeysarenumbers.
• AvarietyofexamplestoextractinformationfromtheIMDBdataset. • Dictionariesasdatabase—storingattribute/valuepairs.
• AccessinginformationfrompublicAPIs
31.11 Additional Dictionary Practice Problems
1. Createadictionarytostorethefavoritecolorsofthefollowingindividuals • Thomasprefersred
• Ashokprefsgreen
• Sandyprefersred
• Alisonprefersorange • Feiprefersgreen
• Natashaprefsblue
Then add some others of your own. Now, write code to change Fei’s preference to green and to remove Sandy’s preference from the dictionary.
2. Usingthedictionaryfromthefirstproblem,writecodetofindwhichcolorismostcommonlypreferred.Use a second dictionary, one that associates strings (representing the colors) with the counts. Output the most common color. If there are ties, output all tied colors.
3. Complete the fast, list solution to the movie counting problem based on sorting, as outlined at the start of the lecture notes.
4. Write a program that uses a dictionary that associates integers (the key) and sets strings (the values) to find the number of movies in each year of the IMDB. Start from Write additional code that uses the years_and_movies dictionary to find the year that has the most movies.
5. Use a dictionary to determine which last names are most common in the IMDB data we have provided. Count individual people not the movies they appear in. For example, ’Hanks, Tom’ counts as one instance of the name ’Hanks” despite the fact that he is in many movies. Assume that the last name ends with the first ’,’ in the actual name. Start this problem by thinking about what the dictionary keys and values should be.
31.9. Final Example 143
CSCI-1100 Course Notes, Release
6. Which two individuals have the most movies in common? To solve this you will need to start from the dic- tionary that associates each individual with the set of movies s/he is involved in. Then you will need double for loops. At first glance this appears that it might be very, very slow, but it can be made much faster by intelligently terminating loops. To illustrate, if you find a pair of individuals with k movies in come then you never have to even consider an individual involved in fewer than k movies!
144 Chapter 31. Lecture 17 — Dictionaries, Part 2
29.1 Overview
CHAPTER
TWENTYNINE LECTURE 16 — DICTIONARIES, PART 1
• MoreonIMDB
• Dictionariesanddictionaryoperations
• Solutionstotheproblemofcountingthemovieseachindividualisinvolvedin. • Otherapplications
29.2 How Many Movies is Each Person Involved In?
• Goals:
– Countmoviesforeachperson.
– Whoisthebusiest?
– Whatmoviesdotwopeoplehaveincommon?
• Bestsolvedwiththenotionofadictionary,butwe’llatleastconsiderhowtousealist.
29.3 List-Based Solution — Straightforward Version
• Coredatastructureisalistoftwo-itemlists,eachgivingaperson’snameandthecountofmovies.
• Forexample,afterreadingthefirstsevenlinesofourshortenedhanks.txtfile,wewouldhavethelist
• Justlikeoursolutionfromthesetslectures,wecanstartfromthefollowingcode:
• Like our list solution for finding all IMDB people, this solution is VERY slow — once again O(N2) (“order of N squared”).
[ [“Hanks, Jim”, 3], [“Hanks, Colin”, 1],
[“Hanks, Bethan”, 1], [“Hanks, Tom”, 2] ]
imdb_file = input(“Enter the name of the IMDB file ==> “).strip()
count_list = []
for line in open(imdb_file, encoding = “ISO-8859-1”):
words = line.strip().split(‘|’)
name = words[0].strip()
131
CSCI-1100 Course Notes, Release
29.4 List-Based Solution — Faster Version Based on Sorting
• WealreadydiscussedasolutionlikethisinLecture15,buthereisareview…
• Appendeachnametotheendofthelistwithoutcheckingifitisalreadythere.
• Afterreadingallofthemovies,sorttheentireresultinglist
– Asaresult,allinstancesofeachnamewillnowbenexttoeachother.
• Gobackthroughthelist,countingtheoccurrenceofeachname
• Thissolutionwillbemuchfasterthanthefirst,butitisalsomoreinvolvedtowritethantheoneweareabout to write using dictionaries
29.5 Introduction to Dictionaries
• Associationbetween“keys”(likewordsinanEnglishdictionary)and“values”(likedefinitionsinanEnglish dictionary). The values can be anything.
• Examples:
>>> heights = dict()
>>> heights = {} # either of these works
>>> heights[‘belgian horse’] = 162.6
>>> heights[‘indian elephant’] = 280.0
>>> heights[‘tiger’] = 91.0
>>> heights[‘lion’] = 97.0
>>> heights
{‘belgian horse’: 162.6, ‘tiger’: 91.0, ‘lion’: 97.0, ‘indian elephant’: 280.0} >>> ‘tiger’ in heights
True
>>> ‘giraffe’ in heights
False
>>> 91.0 in heights
False
>>> list(heights.keys())
[‘belgian horse’, ‘tiger’, ‘lion’, ‘indian elephant’]
>>> sorted(heights.keys())
[‘belgian horse’, ‘indian elephant’, ‘lion’, ‘tiger’]
>>> heights.values()
dict_values([162.6, 91.0, 97.0, 280.0])
>>> list(heights.values())
[97.0, 162.6, 91.0, 280.0]
• Details:
– Twoinitializations;eitherwouldwork.
– Syntaxisverymuchlikethesubscriptingsyntaxforlists,exceptdictionarysubscripting/indexinguses keys instead of integers!
– Thekeys,inthisexample,areanimalspecies(orsubspecies)names;thevaluesarefloats.
– The in method tests only for the presence of the key, like looking up a word in the dictionary without
checking its definition.
– ThekeysareNOTordered.
• Justasinsets,theimplementationuseshashingofkeys.
132 Chapter 29. Lecture 16 — Dictionaries, Part 1
– Conceptually,setsaredictionarieswithoutvalues. 29.6 Lecture Exercise 1
You will have five minutes to work on the first lecture exercise.
29.7 Back to Our IMDB Problem
• Eventhoughourcoverageofdictionarieshasbeenbrief,wealreadyhaveenoughtoolstosolveourproblem of counting movies.
• Onceagainwe’llusethefollowingasastartingpoint
• The solution we give in class will output the counts for the first 100 individuals in alphabetical order. It will be up to you as an exercise to find the most frequently occuring individual.
• Wewillimposeanorderingontheoutputbysortingthekeys.
• We’lltestfirstonoursmallerdatasetandthenagainlateronourlargerones.
29.8 Key Types
• Thusfar,thekeysinourdictionaryhavebeenstrings.
• Keyscanbeany“hashable”type—string,int,float,booleans.
– Lists,setsandotherdictionariescannotbekeys.
• Stringsarebyfarthemostcommonkeytype
• WewillseeanexampleofintegersasthekeytypebytheendoftheLecture17(nextsetof)notes. • Floatandbooleanaregeneralpoorchoices.Canyouthinkwhy?
29.9 Value Types
• Sofar,thevaluesinourdictionarieshavebeenintegersandfloats. • But,anytypecanbethevalues
– boolean – int
– float
– string
– list
29.6. Lecture Exercise 1 133
CSCI-1100 Course Notes, Release
imdb_file = input(“Enter the name of the IMDB file ==> “).strip()
counts = dict()
for line in open(imdb_file, encoding = “ISO-8859-1”):
words = line.strip().split(‘|’)
name = words[0].strip()
CSCI-1100 Course Notes, Release
– tuple
– set
– otherdictionaries
• HereisanexampleusingourIMDBcodeandaset:
• Here is another example where we store the continent and the population for a country instead of just the population:
• Weaccessthevaluesintheentriesusingtwoconsecutivesubscripts.Forexample,
29.10 Removing Values: Sets and Dictionaries
• Foraset:
– discard removes the specified element, and does nothing if it is not there
– remove removes the specified element, but fails (throwing an exception) if it is not there
• Foradictionary,itisthedelfunction.
• Forbothsetsanddictionaries,theclearmethodemptiesthecontainer. • Wewilllookattoyexamplesinclass
29.11 Other Dictionary Methods
• Thefollowingdictionarymethodsareuseful,butnotsomuchastheoneswe’vediscussed.
– get
– pop
– popitem – update
• UsethehelpfunctioninPythontofigureouthowtousethemandtofindotherdictionarymethods.
134 Chapter 29. Lecture 16 — Dictionaries, Part 1
>>> people = dict()
>>> people[‘Hanks, Tom’] = set()
>>> people[‘Hanks, Tom’].add(‘Big’)
>>> people[‘Hanks, Tom’].add(‘Splash’)
>>> people[‘Hanks, Tom’].add(‘Forest Gump’)
>>> print(people[‘Hanks, Tom’])
{‘Forest Gump’, ‘Big’, ‘Splash’}
countries = dict()
countries.clear()
countries[‘Algeria’] = (37100000, ‘Africa’)
countries[‘Canada’] = (34945200, ‘North America’ )
countries[‘Uganda’] = (32939800, ‘Africa’)
countries[‘Morocco’] = (32696600, ‘Africa’)
countries[‘Sudan’] = (30894000, ‘Africa’)
name = “Canada”
print(“The population of {} is {}”.format(name, countries[name][0])) print(“It is in the continent of”, countries[name][1])
29.12 Summary of Dictionaries
• Associate“keys”with“values”
• Feelslikeindexing,exceptweareusingkeysinsteadofintegerindices. • Makescountingandanumberofotheroperationssimpleandfast.
• Keyscanbeany“hashable”value,usuallystrings,sometimesintegers. • Valuescananytypewhatsoever.
29.13 Additional Practice
1. WriteafunctionthattakestheIMDBdictionary—whichassociatesstringsrepresentingnameswithintegers representing the count of movies — and an integer representing a min_count, and removes all individuals from the dictionary involved in fewer than min_count movies.
CSCI-1100 Course Notes, Release
29.12. Summary of Dictionaries 135
27.1 Overview
• Example:findingallindividualslistedintheInternetMovieDatabase(IMDB) • Asolutionbasedonlists
• Setsandsetoperations
• Asolutionbasedonsets.
• Efficiencyandsetrepresentation
Reading is Section 11.1 of Practical Programming.
27.2 Finding All Persons in the IMDB file
• We are given a file extracted from the Internet Movie Database (IMDB) called imdb_data.txt containing, on each line, a person’s name, a movie name, and a year. For example,
Kishiro, Yukito | Battle Angel | 2016
• Goal:
– Findallpersonsnamedinthefile
– Countthenumberofdifferentpersonsnamed. – Askifaparticularpersonisnamedinthefile
• Thechallengeindoingthisisthatmanynamesappearmultipletimes.
• First solution: store names in a list. We’ll start from the following code, posted on the Piazza in
lec15_find_names_start.py, which is part of a Lecture 15 zip file.
and complete the code in class.
• Thechallengeisthatweneedtocheckthatanameisnotalreadyinthelistbeforeaddingit.
• Youmayaccessthedatafilesandthestartingcode.pyfilefromtheResourcespageofthePiazzasite.
CHAPTER
TWENTYSEVEN LECTURE 15 — SETS
imdb_file = input(“Enter the name of the IMDB file ==> “).strip()
name_list = []
for line in open(imdb_file):
words = line.strip().split(‘|’)
name = words[0].strip()
123
CSCI-1100 Course Notes, Release
27.3 How To Test?
• Thefileimdb_data.txthasabout260Kentries.Howwillweknowourresultsarecorrect?
• Evenifwerestrictittomoviesreleasedin2010-2012(thefileimdb_2010-12.txt),westillhave25Kentries! • Weneedtogenerateasmallerfilewithresultswecantestbyhand
– Ihavegeneratedhanks.txtforyouandwilluseittotestourprogrambeforetestingonthelargerfiles. 27.4 What Happens?
• Veryslowonthelargefilesbecauseweneedtoscanthroughthelisttoseeifanameisalreadythere. • We’llwriteafasterimplementationbasedonPythonsets.
• We’llstartwiththebasicsofsets.
27.5 Sets
• APythonsetisanimplementationofthemathematicalnotionofaset:
– Noordertothevalues(andthereforenoindexing)
– Containsnoduplicates
– Containswhatevertypeofvalueswewish;includingvaluesofdifferenttypes.
• Pythonsetmethodsareexactlywhatyouwouldexpect.
– Eachhasafunctioncallsyntaxandmanyhaveoperatorsyntaxinaddition.
27.6 Set Methods
• Initializationcomesfromalist,arange,orfromjustset():
>>> s1 = set()
>>> s1
set([])
>>> s2 = set(range(0,11,2))
>>> s2
set([0, 2, 4, 6, 8, 10])
>>> v = [4, 8, 4, ‘hello’, 32, 64, ‘spam’, 32, 256]
>>> s3 = set(v)
>>> s3
set([32, 64, 4, ‘spam’, 8, 256, ‘hello’])
• Theactualmethodsare
– s.add(x) — add an element if it is not already there
– s.clear() — clear out the set, making it empty
– s1.difference(s2) — create a new set with the values from s1 that are not in s2.
* Pythonalsohasand“operatorsyntax”forthis:
124
Chapter 27. Lecture 15 — Sets
CSCI-1100 Course Notes, Release
s1 – s2
– s1.intersection(s2) — create a new set that contains only the values that are in both sets. Operator
syntax:
s1 & s2
– s1.union(s2) — create a new set that contains values that are in either set. Operator syntax:
s1 | s2
– s1.issubset(2) —- are all elements of s1 also in s2? Operator syntax:
s1 <= s2
– s1.issuperset(s2) — are all elements of s2 also in s1? Operator syntax:
s1 >= s2
– s1.symmetric_difference(s2) — create a new set that contains values that are in s1 or s2 but not
in both. s1 ^ s2
– x in s – evaluates to True if the value associated with x is in set s. • Wewillexploretheintuitionsbehindthesesetoperationsbyconsidering
– s1 to be the set of actors in comedies,
– s2 to be the set of actors in action movies and then consider who is in the sets
27.7 Exercises
1. Setsshouldberelativelyintuitive,soratherthandemotheminclass,we’llworkthroughtheseasanexercise:
s1 – s2
s1 & s2
s1 | s2
s1 ^ s2
>>> s1 = set(range(0,10))
>>> s1
>>> s1.add(6)
>>> s1.add(10)
>>> s2 = set(range(4,20,2))
>>> s2
>>> s1 – s2
27.7. Exercises 125
CSCI-1100 Course Notes, Release
>>> s1 & s2
>>> s1 | s2
>>> s1 <= s2
>>> s3 = set(range(4,20,4))
>>> s3 <= s2
27.8 Back to Our Problem
• We’llmodifyourcodetofindtheactorsintheIMDB.Thecodeisactuallyverysimpleandonlyrequiresafew set operations.
• We’ll
27.9 Side-by-Side Comparison of the Two Solutions
• Neitherthesetnorthelistisordered.Wecanfixthisattheendbysorting.
– Thelistcanbesorteddirectly.
– Thesetmustbeconvertedtoalistfirst.Thefunctionsorteddoesthisforus.
• Whataboutspeed?ThesetversionisMUCHFASTER—tothepointthatthelistversionisessentiallyuseless on a large data set.
– We’llusesometimingstodemonstratethisquantitatively – We’llthenexplorewhyintherestofthislecture.
27.10 Comparison of Running Times for Our Two Solutions
• List-basedsolution:
– Eachtimebeforeanameisadded,thecode—throughthemethodin—scansthroughtheentirelist to decide if it is there.
– Thus,theworkdoneisproportionaltothesizeofthelist.
– The overall running time is therefore roughly proportional to the square of the number of entries in
the list (and the file).
– Letting the mathematical variable N represent the length of the list, we write this more formally as
O(N2), or “the order of N squared” • Set-basedcode
– Forsets,Pythonusesatechniquecalledhashingtorestricttherunningtimeoftheaddmethodsothat it is independent of size of the set.
* ThedetailsofhashingarecoveredinCSCI1200,DataStructures.
126 Chapter 27. Lecture 15 — Sets
– The overall running time is therefore roughly proportional to the length of the set (and number of en- tries in the file).
– WewritethisasO(N).
• Wewilldiscussthistypeofanalysismorelaterinthesemester.
– ItiscoveredinmuchgreaterdetailinDataStructuresandagaininIntro.toAlgorithms. 27.11 Discussion
• Pythonlargelyhidesthedetailsofthecontainers—setandlistinthiscase—andthereforeitishardtoknow which is more efficient and why.
• Forprogramsappliedtosmallproblemsinvolvingsmalldatasets,efficiencyrarelymatters.
• Forlongerprogramsandprogramsthatworkonlargerdatasets,efficiencydoesmatter,sometimestremen- dously. What do we do?
– Insomecases,westillusePythonandchoosethecontainersandoperationsthatmakethecodemost efficient.
– In others, we must switch to programming languages, such as C++, that generate and use compiled code.
27.12 Summary
• SetsinPythonrealizethenotionofamathematicalset,withalltheassociatedoperations.
• Operationscanbeusedasmethodcallsor,inmanycases,operators.
• The combined core operations of finding if a value is in a set and adding it to the set are much faster when using a set than the corresponding operations using a list.
• Wewillcontinuetoseeexamplesofprogrammingwithsetswhenweworkwithdictionaries.
27.13 Extra Practice Problems
1. WritePythoncodethatimplementsthefollowingsetfunctionsusingacombinationofloops,theinopera- tor, and the add function. In each case, s1 and s2 are sets and the function call should return a set.
(a) union(s1,s2)
(b) intersection(s1,s2)
(c) symmetric_difference(s1,s2)
CSCI-1100 Course Notes, Release
27.11. Discussion 127
CHAPTER
TWENTYSIX LECTURE 14 — PROBLEM SOLVING AND DESIGN, PART 1
26.1 Overview
This is the first of our lectures dedicated primarily to problem solving and design rather than on particular pro- gramming constructs and techniques
• Design:
– Choiceofcontainer/datastructure;choiceofalgorithm.
* Atthemoment,wedon’tknowtoomanycontainers,butwewillthinkaboutdifferentwaystouse the one container - lists - we do know about.
– Implementation – Testing
– Debugging
• Wewilldiscusstheseinthecontextofseveralvariationsononeproblem:
– Findingthemodeinasequenceofvalues—thevalue(orvalues)occuringmostoften.
• Thereisnodirectconnecttoachapterinthetext.
• We will start with a completely blank slate so that the whole process unfolds from scratch. This includes looking for other code to adapt.
• Workingthroughproblemslikethisisagoodwaytoreviewwhatwe’velearnedthusfar.
26.2 Problem: Finding the Mode
• Givenaseriesofvalues,findtheonethatoccursmostoften. • Variation1:istherealimited,indexablerangeofvalues?
– Examplesthatareconsistentwiththisvariationincludetestscoresorlettersofthealphabet
– Examplesnotconsistentincludecountingwordsandcountingaminoacids
• Variation2:dowewantjustthemodesordowewanttoknowhowmanytimeseachvalueoccurs? • Variation3:dowewantahistogramwherevaluesaregrouped?
– Example:oceantemperaturemeasurements,pixelintensities,incomevalues.
– Ineachofthesecases,aspecificvalue,thenumberofoccurrencesofaspecificocean,suchas2.314C,
is not really of interest. More important is the number of temperature values in certain ranges.
121
CSCI-1100 Course Notes, Release
26.3 Our Focus: A Sequence of Numbers
• Integers,suchastestscores
• Floats,suchastemperaturemeasurements
26.4 Sequence of Discussion
• Brainstormideasforthebasicapproach.We’llcomewithatleasttwo.
– Wewilldiscussanadditionalapproachwhenwelearnaboutdictionaries.
• Algorithm/implementation • Testing
– Generatetestcases
– Whichtestcaseswegeneratewilldependonthechoiceofalgorithm.Wewillcombinethem. • Debugging:
– Ifwefindafailedtestcase,wewillneedtofindtheerrorandfixit.
– Useacombinationofcarefullyreadingthecode,workingwithadebugger,andgeneratingprintstate-
ments. • Evaluation
– Wecananalyzeusingtheoreticaltoolswewilllearnaaboutlaterorthroughexperimentaltiming 26.5 Discussion of Variations
• Frequencyofoccurrence:
– Whatarethetenmostfrequentlyoccurringvalues?Whatarethetoptenpercentmostfrequentvalues? – Outputtheoccurrencesforeachvalue.
• Clusters/histograms:
– Testscoresineachrangeof10
• Quantiles:bottom25%ofscores,median,top25%
122 Chapter 26. Lecture 14 — Problem Solving and Design, Part 1
CHAPTER
TWENTYTWO LECTURE 12 — CONTOLLING LOOPS
22.1 Restatement of the Basics
• for loops tend to have a fixed number of iterations computed at the start of the loop
• while loops tend to have an indefinite termination, determined by the conditions of the data • MostPythonforloopsareeasilyrewrittenaswhileloops,butnotvice-versa.
– Inotherprogramminglanguages,forandwhilearealmostinterchangeable,atleastinprinciple. 22.2 Overview of Today
• Rangesandcontrolofloopiterations
• Nestedloops
• Listsoflists
• Contollingloopsthroughbreakandcontinue
Reading: Practical Programming, rest of Chapter 9.
22.3 Part 1: Ranges and For Loops— A Review
• Arangeisafunctiontogenerateasequenceofintegers:
outputs the digits 0 through 9 in succession, one per line.
– Rememberthatthisisupthroughandnotincludingtheendvaluespecified!
• Arangeisnotquitealist—insteaditgeneratesvaluesforeachsuccessiveiterationofaforloop. – Fornowwewillconverteachrangetoalistasthebasisforstudyingthem.
• Ifwewanttostartwithsomethingotherthan0,weprovidetwointegervalues
• Withathirdintegervalueswecancreateincrements.Forexample,
for i in range(10):
print(i)
>>> list(range(3,8))
[3, 4, 5, 6, 7]
103
CSCI-1100 Course Notes, Release
>>> list(range(4,20,3))
[4, 7, 10, 13, 16, 19]
starts at 4, increments by 3, stops when 20 is reached or surpassed. • Wecancreatebackwardsincrements
22.4 Using Ranges in For Loops
• We can use the range to generate the sequence of loop variable values in a for loop. Our first example is printing the contents of the planets list
(In this case we don’t need a index variable – we can just iterate over the values in the list.)
• Thevariableiisvariouslyknownastheindexortheloopindexvariableorthesubscript.
• Wewillmodifytheloopinclasstodothefollowing:
– Printtheindicesoftheplanets(startingat1!) – Printtheplanetsbackward.
– Printeveryotherplanet.
22.5 Loops That Do Not Iterate Over All Indices
• Sometimestheloopindexshouldnotgoovertheentirerangeofindices,andweneedtothinkaboutwhere to stop it early, as the next example shows.
• Example: Returning to our example from Lecture 1, we will briefly re-examine our solution to the following problem: Given a string, how can we write a function that decides if it has three consecutive double letters?
• Wehavetothinkcarefullyaboutwheretostartourloopingandwheretostop!
• ReferbacktoLecture10forfurtherexamples
22.6 Part 1 Practice
We will only go over a few of these in class, but you should be sure you can handle all of them
>>> list(range(-1, -10, -1))
[-1, -2, -3, -4, -5, -6, -7, -8, -9]
planets = [ ‘Mercury’, ‘Venus’, ‘Earth’, ‘Mars’, ‘Jupiter’,
‘Saturn’, ‘Uranus’, ‘Neptune’, ‘Pluto’ ]
for i in range(len(planets)):
print(planets[i])
def has_three_doubles(s):
for i in range(0, len(s)-5):
if s[i] == s[i+1] and s[i+2] == s[i+3] and s[i+4] == s[i+5]:
return True
return False
104 Chapter 22. Lecture 12 — Contolling Loops
1. Generate a range for the positive integers less than 100. Use this to calculate the sum of these values, with and without (i.e. use sum) a for loop.
2. Usearangeandaforlooptoprintthepositive,evennumberslessthantheintegervalueassociatedwithn.
3. Supposewewantalistofthesquaresofthedigits0..9.ThefollowingdoesNOTwork
Why not? Write a different for loop that uses indexing into the squares list to accomplish our goal.
4. Thefollowingcodeforfindingoutifawordhastwoconsecutivedoublelettersiswrong.Why?When,specif-
ically, does it fail?
22.7 Part 2: Nested Loops
• Someproblemsrequireiteratingovereither – twodimensionsofdata,or
– allpairsofvaluesfromalist
• Asanexample,hereiscodetoprintalloftheproductsofdigits:
• Howdoesthiswork?
– foreachvalueofithevariableinthefirst,or“outer”,loop,Pythonexecutestheentiresecond,orinner, loop
– Importantly,istaysfixedduringtheentireinnerloop. • Wewilllookatfindingthetwoclosestpointsinalist.
22.8 Example: Finding the Two Closest Points
• Supposewearegivenalistofpointlocationsintwodimensions,whereeachpointisatuple.Forexample,
points = [ (1,5), (13.5, 9), (10, 5), (8, 2), (16,3) ]
• Ourproblemistofindthetwopointsthatareclosesttoeachother.
– We started working on a slightly simpler version of this problem at the end of Lecture 10, but did not have time to complete it.
• Thenaturalideaistocomputethedistancebetweenanytwopointsandfindtheminimum.
CSCI-1100 Course Notes, Release
squares = range(10)
for s in squares:
s = s*s
def has_two_doubles(s):
for i in range(0, len(s)-5):
if s[i] == s[i+1] and s[i+2] == s[i+3]:
return True
return False
digits = range(10)
for i in digits:
for j in digits:
print(“{} x {} = {}”.format(i,j,i*j))
22.7. Part 2: Nested Loops 105
CSCI-1100 Course Notes, Release
– Wecandothiswithandwithoutusingalistofdistances.
• Let’sworkthroughtheapproachtothisandposttheresultonthecoursewebsite.
22.9 Part 3: Lists of Lists
• In programming you often must deal with data much more complicated than a single list. For example, we might have a list of lists, where each list might be temperature (or pH) measurements at one location of a study site:
• Hereiscodetofindthesitewiththemaximumaveragetemperature;notethatnoindicesareused.
• Notes:
– forloopvariablesiteisanaliasforeachsuccessivelistintemps_at_sites
– Aseparatelistiscreatedtostorethecomputedaverages
– Wewillseeinclasshowthiswouldbewrittenwithouttheseparateaverageslist.
22.10 Part 4: Controlling Execution of Loops
• Wecancontrolloopsthroughuseof
– break
– continue
• Weneedtobecarefultoavoidinfiniteloops
22.11 Using a Break
• Wecanterminatealoopimmediatelyuponseeingthe0usingPython’sbreak:
temps_at_sites = [ [ 12.12, 13.25, 11.17, 10.4],
[ 22.1, 29.3, 25.3, 20.2, 26.4, 24.3 ],
[ 18.3, 17.9, 24.3, 27.2, 21.7, 22.2 ],
[ 12.4, 12.5, 12.14, 14.4, 15.2 ] ]
averages = []
for site in temps_at_sites:
avg = sum(site) / len(site)
averages.append(avg)
max_avg = max(averages)
max_index = averages.index(max_avg)
print(“Maximum average of {:.2f} occurs at site {}”.format(max_avg, max_index))
sum = 0
while True:
x = int(input(“Enter an integer to add (0 to end) ==> “))
if x == 0:
break sum += x
106 Chapter 22. Lecture 12 — Contolling Loops
print(sum)
• break sends the flow of control immediately to the first line of code outside the current loop, and
• ThewhileconditionofTrueessentiallymeansthattheonlywaytostoptheloopiswhentheconditionthat triggers the break is met.
22.12 Continue: Skipping the Rest of a Loop Iteration
• Supposewewanttoskipovernegativeentriesinalist.WecandothisbytellingPythontocontinuewhenit the loop variable, taken from the list, is negative:
• Whenitseescontinue,Pythonimmediategoesbacktothe“top”oftheloop,skippingtherestofthecode, and initiates the next iteration of the loop with a new value for item.
• Anyloopthatusesbreakorcontinuecanberewrittenwithouteitherofthese.
– Therefore,wechoosetousethemonlyiftheymakeourcodeclearer.
– A loop with more than one continue or break is rarely well-structured, so if you find that you have written such a loop you should stop and rewrite your code.
• Theexampleabove,whileillustrative,isprobablybetterwithoutthecontinue.
– Usually when we use continue the rest of the loop is relative longer the condition that triggers the
continue it tested at or near the top of the loop. 22.13 Termination of a While Loop
• Whenworkingwithawhilelooponealwaysneedstoensurethattheloopwillterminate!Otherwisewehave an infinite loop.
• Sometimesitiseasytodecideifaloopwillterminate.Sometimesitisnot.
• Doeitherofthefollowingexamplescauseaninfiniteloop?
CSCI-1100 Course Notes, Release
for item in mylist:
if item < 0:
continue
print(item)
import math
x = float(input("Enter a positive number -> “))
while x > 1:
x = math.sqrt(x)
print(x)
import math
x = float(input(“Enter a positive number -> “))
while x >= 1:
x = math.sqrt(x)
print(x)
22.12. Continue: Skipping the Rest of a Loop Iteration 107
CSCI-1100 Course Notes, Release
22.14 Summary
• range is used to generate a sequence of indices in a for loop.
• Nestedforloopsmaybeneededtoiterateovertwodimensionsofdata.
• Listsoflistsmaybeusedtospecifymorecomplexdata.Weprocesstheseusingacombinationofforloops, which may need to be nested, and Python’s built-in functions. Use of Python’s built-in functions, as illus- trated in the example here in these notes, is often preferred.
• Loops (either for or while) may be controlled using continue to skip the rest of a loop iteration and using break to terminate the loop altogether. These should be used sparingly!
108 Chapter 22. Lecture 12 — Contolling Loops
CHAPTER
TWENTY LECTURE 11 — DECISIONS PART 2
20.1 Overview — Logic and Decision Making, part 2
• Programstructure
• Debuggingand“hardening”asimplefunction
• Abitofdesignandabitofarandomwalk
• Moreonlogic-thekeytogettingprogramsright
– Booleanlogic
– Nestedifstatements
– Assigningbooleanvariables
20.2 Part 1: Program Structure
Programming requires four basic skills: 1. Developasolution.
• Startwithsmallsteps,solvethem,andthenaddcomplexity 2. Structureyourcode.
• Moverepeatedcodeintofunctions
• Make your code easy to read and modify. Use meaningful variable names and break complex opera- tions into smaller parts.
• Placevaluesinvariablessotheyareeasytochange.
• Includecommentsforimportantfunctions,butdonotclutteryourcodewithunnecessarycomments. A classic example of a completely unnecessary comment is
x += 1 # increment x
• Documentassumptionsaboutwhatispassedtoafunction.
• Ifyourfunctionismeanttoreturnavalue,makesureitalwaysdoes. 3. Testyourcode.
• Find all possible cases that your program should work for. As programs get larger, this is increasingly hard.
93
CSCI-1100 Course Notes, Release
• If you cannot check for all inputs, then you must then check your code for meaningful inputs: regular (expected inputs) and edge cases (inputs that can break your code).
4. Debugyourcode.
• Neverassumeanuntestedpartofyourcodeisbugfree.
• Learnsyntaxwellsothatyoucanspotandfixsyntaxerrorsfast.
• Semanticerrorsaremuchhardertofindandfix.Youneedstrategiestoisolatewheretheerroris.
• Printoutputbeforeandaftercrucialsteps.
• Lookatwhereyourprogramcrashed.
• Fix the first error first, not the biggest error. The first error may be the cause of bigger errors later in your code.
• Useadebugger.
• Simplify the problem: remove (by commenting out) parts of your code until you no longer have an error. Look at the last code removed for a source of at least part of your errors.
• Testpartsofyourcodeseparatelyandonceyouareconvincedtheyarebugfree,concentrateonother parts.
20.3 Help with debugging
•
• •
•
Considerthefollowingcodetoaddthefirstnintegers:
Doesitwork?Forallinputs?Mightitrunforever?(We’llignorethefactthataforloopwouldbebetterhere.) Howmightwefindsuchanerror?
– Carefulreadingofthecode – Insertprintstatements
– UsetheWingIDEdebugger.
WewillpracticewiththeWingIDEdebuggerinclass,usingittounderstandthebehavioroftheprogram.We will explain the following picture
n = int(input(“Enter a positive integer ==> “)) sum = 0
i=0
while i != n:
sum += i
i += 1
print(‘Sum is’, sum)
94
Chapter 20. Lecture 11 — Decisions Part 2
and note the use of
– Thehand,bugandstopsymbolsonthetopofthedisplay,and – TheDebugI/OandStackDataatthebottomofthedisplay.
• Debuggingbecomescrucialintrackinglogicerrorsaswell.
20.4 Program organization
• Envisionyourcodeashavingtwomainparts:themainbodyandthefunctionsthathelpthemaincode.
• Make sure your functions accomplish one well-defined task. This makes them both easy to test and useful in many places.
• Aswewillseeinanexamplebelow,inPythonitisgoodpracticetoseparatethefunctionsandthemainbody with the following addition to the program structure:
• This will have no apparent effect when a program is run. However, if a program is imported as a module into another program (like the utility code we have been giving you), any code within the above if block is skipped!
• Thisallowsprogramstoworkbothasmodulesandstandalonecode.
• When the primary purpose of your code is to provide functionality as a module, it is best to use the code in the main body to test the module functions.
CSCI-1100 Course Notes, Release
if __name__ == “__main__”
# Put the main body of the program below this line
20.4. Program organization 95
CSCI-1100 Course Notes, Release
20.5 Part 2: Extended Example of a Random Walk
• Manynumericalsimulations,includingmanyvideogames,involverandomevents.
• Pythonincludesamoduletogeneratenumbersatrandom.Forexample,
import random
# Print three numbers randomly generated between 0 and 1.
print(random.random())
print(random.random())
print(random.random())
# Print a random integer in the range 0..5
print(random.randint(0,5))
print(random.randint(0,5))
print(random.randint(0,5))
• We’dliketousethistosimulatea“randomwalk”:
– Hypothetically, a person takes a step forward or backward, completely at random (equally likely to go either way). This can be repeated over and over again until some stopping point is reached.
– Suppose the person is on a platform with N steps and the person starts in the middle, this random forward/backward stepping process is repeated until they fall off (reach step 0 or step N + 1)
* “forward” is represented by an increasing step, while “backward” is represented by a decreasing step
– Howmanystepsdoesittaketofalloff?
• Manyvariationsonthisproblemappearinphysicalsimulations.
• Wecansimulateastepintwoways:
1. Ifrandom.random()returnsavaluelessthan0.5stepbackward;otherwisestepforward.
2. Ifrandom.randint(0,1)returns1thenstepforward;otherwise,stepbackward.
• So,insummary,wewanttostartarandomwalkatpositionN/2andrepeatedlytakeastepforwardorback-
ward based on the output of the random number generator until the walker falls off.
• We will solve this problem together during lecture. We we start by enumerating some of the needed steps and then solving them individually before putting together the whole program.
– Once we see the result we can think of several ways to change things and explore new questions and ideas. Remember, a program is never done!
20.6 Part 3: Review of Boolean Logic
• Invented/discoveredbyGeorgeBooleinthe1840’storeduceclassicallogictoanalgebra – Thiswasacrucialmathematicalstepontheroadtocomputationandcomputers
• Values(inPython)areTrueandFalse • Operators
– Comparisons:<,>,<=,>=,==!= – Logic:and,or,not
96
Chapter 20. Lecture 11 — Decisions Part 2
20.7 Truth Tables
• Asidetorecallthesyntax:and,or,notarelowercase!
• If we have two boolean expressions, which we will refer to as ex1 and ex2, and if we combine their “truth”
values using and we have the following “truth table” to describe the result
• Ifwecombinethetwoexpressionsusingor,wehave
• Finally,usingnotwehave
20.8 DeMorgan’s Laws Relating and, or, not
• Usingex1andex2onceagaintorepresentbooleanexpressions,wehave not (ex1 and ex2) == (not ex1) or (not ex2)
• And,
not (ex1 or ex2) == (not ex1) and (not ex2)
• Also,distributionlaws
• Wecanprovetheseusingtruthtables.
20.9 Why Do We Care?
• Whenwe’vewrittenlogicalexpressionsintoourprograms,itnolongermatterswhatweintended;itmatters what the logic actually does.
• Forcomplicatedbooleanexpressions,wemayneedtoalmostprovethattheyarecorrect
20.10 Part 4: Additional Techniques in Logic and Decision Making
We will examine:
CSCI-1100 Course Notes, Release
ex1
ex2
ex1 and ex2
False
False
False
False
True
False
True
False
False
True
True
True
ex1
ex2
ex1 or ex2
False
False
False
False
True
True
True
False
True
True
True
True
ex1
not ex1
False
True
True
False
ex1 and (ex2 or ex3) == (ex1 and ex2) or (ex1 and ex3)
ex1 or (ex2 and ex3) == (ex1 or ex2) and (ex1 or ex3)
20.7. Truth Tables 97
CSCI-1100 Course Notes, Release
• Short-ciruiting
• Nestedconditionals
• Storingtheresultofbooleanexpressionsinvariables
and then apply them to several problems
20.11 Short-Circuited Boolean Expressions
• Pythononlyevaluatesexpressionsasfarasneededtomakeadecision.
• Therefore,inbooleanexpressionoftheform
ex1 and ex2
ex2 will not be evaluated if ex1 evaluates to False. Think about why.
• Also,inbooleanexpressionoftheform
ex1 or ex2
ex2 will not be evaluated if ex1 evalues to True.
• This“short-circuiting”iscommonacrossmanyprogramminglanguages.
20.12 Nested If Statements
• Wecanplaceifstatementsinsideofotherifstatements.
• Toillustrate,considerthefollowingwhereex1,ex2,ex3andex4areallbooleanexpressions,andblockA,
blockB, blockD and blockE are sections of code.
• Wewillexaminethisexampleinclassandanswerthefollowingquestions: – Underwhatconditionsiseachblockexecuted?
– Isitpossiblethatnoblocksareexecuted?
– Whatistheequivalentnon-nestedif-elif-elsestructure?
20.13 Storing the Result of a Boolean Expression
• Sometimeswestoretheresultofbooleanexpressionsinavariableforlateruse:
if ex1:
if ex2:
blockA
elif ex3:
blockB
elif ex4:
blockD
else: blockE
98 Chapter 20. Lecture 11 — Decisions Part 2
• Weusethisto
– Makecodeclearer
– Avoidrepeatedevaluationofthesameexpression,especiallyiftheexpressionrequiresalotofcompu- tation.
20.14 Examples for Lecture
We will work on the following examples during class, as time permits.
1. Inthefollowingcode,forwhatvaluesofxandydoesthecodeprint1,forwhatvaluesdoesthecodeprint2, and for what values does the code print nothing at all?
The moral of the story is that you should be careful to ensure that your logic and if structures cover the entire range of possibilities!
2. Doctorssometimesassessapatient’sriskofheartdiseaseintermsofacombinationoftheBMI(bodymask index) and age using the following table:
BMI < 22.0 BMI ∏ 22.0
Assuming the values for a patient are stored in variables age and bmi, we can write the following code
We will work out two different ways of printing Low, Medium or High according to the table based on the values of the boolean variables slim and young.
3. Challengeexample:Supposetworectanglesaredeterminedbytheircornerpoints-(x0,y0)and(x1,y1) for one rectangle and (u0,v0) and (u1,v1) for the other. Write a function that takes these four tuples as arguments and returns True when the two rectangles intersect and False otherwise.n
20.15 Summary of Discussion of If Statements and Logic
• Logicisacrucialcomponentofeveryprogram.
• Basicrulesoflogic,includingDeMorgan’slaws,helpustowriteandunderstandbooleanexpressions.
• Itsometimesrequirescareful,precisethinking,evenatthelevelofaproof,toensurelogicalexpressionsand if statement structures are correct.
Age ∑ 45 Low
Age > 45 Medium
CSCI-1100 Course Notes, Release
f = float(raw_input(“Enter a Fahrenheit temperature: “))
is_below_freezing = f < 32.0
if is_below_freezing:
print "Brrr. It is cold"
if x>5 and y<10:
if x<5 or y>2:
if y>3 or z<3:
print 1
else: print 2
Medium
High
slim = bmi < 22.0
young = age <= 45
20.14. Examples for Lecture 99
CSCI-1100 Course Notes, Release
– Many bugs in supposedly-working programs are caused by conditions that the programmers did not fully consider.
• Ifstatementscanbestructuredinmanyways,sometimesnestedseverallevelsdeep.
– Nestingdeeplycanleadtoconfusingcode,however.
– Warning specifically for Python: you can easily change the meaning of your program by accidentally changing indentation. It is very hard to debug these changes.
• Usingvariablestostorebooleanvaluescanmakecodeeasiertounderstandandavoidsrepeatedtests. • Makesureyourlogicandresultingexpressionscovertheuniverseofpossibilities!
100 Chapter 20. Lecture 11 — Decisions Part 2
We will cover the first three of these topics during lecture. The fourth is for your own use: • Listaliasing,listsandfunctions
• Forloopstooperateonlists
• Slicingtocreatecopiesoflistsandtocreatesublists
• Convertingbackandforthbetweenstringsandlists
18.2 List Aliasing
• ConsiderthefollowingexamplePythoncode:
CHAPTER
EIGHTEEN LECTURE 10 — LISTS PART 2
18.1 Topics
>>> L1 = [ ‘RPI’, ‘WPI’, ‘MIT’ ]
>>> L2 = L1
>>> L3 = [ ‘RPI’, ‘WPI’, ‘MIT’ ]
>>> L2.append( ‘RIT’ )
>>> L2[1] = ‘CalTech’
>>> L1
[‘RPI’, ‘CalTech’, ‘MIT’, ‘RIT’]
>>> L2
[‘RPI’, ‘CalTech’, ‘MIT’, ‘RIT’]
>>> L3
[‘RPI’, ‘WPI’, ‘MIT’]
• Surprised?Thisiscausedbythecreationofwhatwecallanaliasincomputerscience:
– L1 and L2 reference the same list – they are aliases of each other and the underlying list – so changes
made using either name change the underlying list
– L3 references a different list that just happens to have the same string values in the same order: there would have been no confusion if the strings in the list had been different.
– We’lluseourmemorymodelforliststounderstandwhatishappeninghere.
• Python uses aliases for reasons of efficiency: lists can be quite long and are frequently changed, so copying
of entire lists is expensive
• Thisistrueforothercontainerdatatypesaswell.
– Assignmentscreateanaliasforimages,lists,tuples,stringsand,aswewillseelater,setsanddictionar- ies
81
CSCI-1100 Course Notes, Release
* Aliases of strings and tuples do not create the same confusion as other containers because they can not be changed once they are created.
• Fortunately,ifwetrulywanttocopyalist,Pythonprovidesacopy()methodforlists.Trythefollowingand see what happens.
18.3 Aliasing and Function Parameters
• Whenavariableispassedtofunctions,acopyofitsvalueiscreatedifthevalueisanumberorabooleans:
L1 = [1,2,3]
L2 = L1.copy()
L1.pop_back()
L2.append( 4 )
print(L1)
print(L2)
def add_two(val1, val2):
val1 += val2
return val1
val1 = 10
val2 = 15
print(val1, val2)
print(add_two(val1,val2))
print(val1, val2)
• Whenalistispassedtofunctions,theparameterbecomesanaliasfortheargumentinthefunctioncall. • Hereisanexampleofafunctionthatreturnsalistcontainingthetwosmallestvaluesinitsinputlist:
def smallest_two(mylist):
mylist.sort()
newlist = []
if len(mylist) > 0:
newlist.append(mylist[0])
if len(mylist) > 1:
newlist.append(mylist[1])
return newlist
values = [35, 34, 20, 40, 60, 30]
print(“Before function:”, values)
print(“Result of function:”, smallest_two(values))
print(“After function:”, values)
• Inclasswewilldiscusswhathappened.
18.4 What Operations Change a List? What Operations Create New Lists?
• Operationsthatchangelistsinclude
– sort,insert,append,pop,remove
82
Chapter 18. Lecture 10 — Lists Part 2
CSCI-1100 Course Notes, Release
• Operationsthatcreatenewlists
– Slicing(discussedbelow),copy(),concatenation(+),replication(*)andlist()
18.5 Part 1 Practice
Students will be given about 5 minutes to work on the first two lecture exercises
18.6 Part 2: For Loops and Operations on List Items
• Although while loops allow us to apply an operation to each entry in a list, Python has a construct called a for loop that is often easier to use for such operations.
• Ourdrivingexamplewillbetheproblemofcapitalizingalistofnames.We’llstartwithasimpleexample:
• Wecanunderstandwhatishappeningbylookingatthispiece-by-piece:
– Thekeywordforsignalsthestartofaloop
– animal is a loop variable that takes on the value of each item in the list (as indicated by the keyword in) in succession
* Thisiscallediteratingoverthevalues/elementsofthelsit
– The:signalsthestartofablockofcodethatisthe“bodyoftheloop”,executedonceinsuccessionfor
each value that animal is assigned
– Thebodyoftheloophereisjustasingle,indentedlineofcode,butinothercases-justasusingwhile
loops – there may be more than one line of code.
– Theendoftheloopbodyisindicatedbyreturningtothesameleveloftheindentationasthefor… line that started the loop.
18.7 Changing the Values in a List
• Whatifwewantedtochangethelist?Wemightconsidercopyingcap_animalsbacktoanimalsattheend of the code sequence.
• Butthisdoesnotworkifwewantedafunctionthatcapitalizedallstringsinalist.
animals = [‘cat’, ‘monkey’, ‘hawk’, ‘tiger’, ‘parrot’]
cap_animals = []
for animal in animals:
cap_animals.append( animal.capitalize() )
print(cap_animals)
def capitalize_list( names ):
cap_names = []
for n in cap_names:
cap_names.append( n.capitalize() )
names = cap_names
animals = [‘cat’, ‘monkey’, ‘hawk’, ‘tiger’, ‘parrot’] capitalize_list(animals)
print(animals) # Make sure you understand the output!!!
18.5. Part 1 Practice 83
CSCI-1100 Course Notes, Release
• Thisdoesnotworkbecausenamesisanaliasforthelistratherthanthelistitself!
• Thefollowingdoesnotworkeitherbecausenisanaliasforthestringinthelist
• So, based on what we know so far to actually change the values in the list we need to use indexing together with a while loop:
• Wecanalsosolvethisusingaforloopandindexing,butforthisweneedarange 18.8 Usingrange
def capitalize_list( names ):
for n in names:
n = n.capitalize()
def capitalize_list( names ): i=0
while i < len(names):
names[i] = names[i].capitalize()
i += 1
•
•
•
•
•
Arange“generates”valuesinasequence,almost-but-not-quitelikealist.
prints the values 0 through 4... Wecanconvertarangetoanactuallist:
Thegeneralformis
range( bi, ei, ii )
where
– bi is the initial value (defaults to 0)
– ei is the ending value (never included in the range!) – ii is the increment, added each time (defaults to 1)
We’lllookatnumberofexamples:
Usingforloopsonlists,weoftenuselen()incombinationwithrangetospecifytheindicesthatshould be used.
Now we have our for loop based solution to capitalizing the names in a list.
Chapter 18. Lecture 10 — Lists Part 2
for i in range(5):
print(i)
>>> x = list(range(5))
>>> print(x)
[0, 1, 2, 3, 4]
list(range(3,10))
list(range(4, 20, 4))
list(range(10, 2, -2))
def capitalize_list( names ):
for i in range(len(names)):
names[i] = names[i].capitalize()
84
• Unlike with a while loop there is no need to write code to compare our index / counter variable i directly against the bound and no need to write code to increment i.
• Thisuseofrangetogenerateanindexlistiscommon
– Whenwewanttochangetheinteger,floatorstringvaluesofalist. – Whenwewanttoworkwithmultiplelistsatonce.
18.9 Part 2 Practice
1. Recallourlist
For the purpose of this exercise only, please pretend the Python sum function does not exist, and then write a short section of Python code that uses a for loop to first compute and then print the sum of the values in the co2_levels list. You do not need to use indexing.
18.10 Using Indices to “Slice” a List and Create a New List
• Recall
• Nowsupposewejustwantthevaluesatindices2,3and4ofthisinanewlist:
• Wegivethefirstindexandonemorethanthelastindexwewant
• If we leave off the first index, 0 is assumed, and if we leave off the second index, the length of the list is assumed.
• Negativeindicesareallowed—theyarejustconvertedtotheirassociatedpositivevalues.Someexamples:
CSCI-1100 Course Notes, Release
co2_levels = [ 320.03, 322.16, 328.07, 333.91, 341.47, \
348.92, 357.29, 363.77, 371.51, 382.47, 392.95 ]
>>> co2_levels = [ 320.03, 322.16, 328.07, 333.91, 341.47,
348.92, 357.29, 363.77, 371.51, 382.47, 392.95 ]
>>> three_values = co2_levels[2:5]
>>> three_values
[328.07, 333.91, 341.47]
>>> co2_levels
[ 320.03, 322.16, 328.07, 333.91, 341.47, 348.92, 357.29, 363.77,
371.51, 382.47, 392.95 ]
>>> L1
[‘cat’, ‘dog’, ‘hawk’, ‘tiger’, ‘parrot’]
>>> L1[1:-1]
[‘dog’, ‘hawk’, ‘tiger’]
>>> L1[1:-2]
[‘dog’, ‘hawk’]
>>> L1[1:-4]
[]
>>> L1[1:0]
[]
>>> L1[1:10]
[‘dog’, ‘hawk’, ‘tiger’, ‘parrot’]
18.9. Part 2 Practice 85
CSCI-1100 Course Notes, Release
18.11 More on List Slicing
• Specifyingindicesforslicingandforarangeareverysimilar:
– Arangeuses()andisagenerator,whileslicingusing[]andisappliedtoalisttocreateanewlist.
• Themostgeneralformofslicinginvolvesthreevalues
L[si:ei:inc]
where
– L is the list
– si is the start index
– ei is the end index
– inc is the increment value
Any of the three values is optional
• We’llworkthroughsomeexamplesinclassto
– Useslicingtocopyanentirelist
– Usenegativeincrementsandgenerateareversedlist – Extractingtheevenindexedvalues
• Note: L[:] returns a copy of the whole list of L. This is the same using method L.copy() or the function list()
>>> L2 = L1[:]
>>> L2[1] = ‘monkey’
>>> L1
[‘cat’, ‘dog’, ‘hawk’, ‘tiger’, ‘parrot’]
>>> L2
[‘cat’, ‘monkey’, ‘hawk’, ‘tiger’, ‘parrot’]
>>> L3 = list(L1)
>>> L3[1] = ‘turtle’
>>> L1
[‘cat’, ‘dog’, ‘hawk’, ‘tiger’, ‘parrot’]
>>> L2
[‘cat’, ‘monkey’, ‘hawk’, ‘tiger’, ‘parrot’]
>>> L3
[‘cat’, ‘turtle’, ‘hawk’, ‘tiger’, ‘parrot’]
18.12 Concatentation and Replication
• Justlikewithstrings,concatenationandreplicationcanbeappliedtolists:
• and
>>> v = [1,2,3]+[4,5]
>>> v
[1,2,3,4,5]
>>> [1]*3
[1,1,1]
86
Chapter 18. Lecture 10 — Lists Part 2
CSCI-1100 Course Notes, Release
18.13 Part 3 Practice
1. Whatistheoutputofthefollowing?
x = [6,5,4,3,2,1] + [7]*2 y=x
x[1] = y[2]
y[2] = x[3]
x[0] = x[1]
print(x)
y.sort()
print(x)
print(y)
2. Writeaslicingcommandtoextractvaluesindexedby1,4,7,10,etcfromalistL0. 18.14 Converting Strings to Lists
• Version1:usethefunctionlisttocreatealistofthecharactersinthestring:
• Version2:usethestringsplitfunction,whichbreaksastringupintoalistofstringsbasedonthecharacter provided as the argument.
– Thedefaultis’’:
– Othercommonsplittingcharactersare’,’,’|’and’\t’
• Wewillplaywiththes=”Helloworld”exampleinclass.
18.15 Converting Lists to Strings
• Whathappenswhenwetypethefollowing?
This is will not concatenate all the strings in the list (assumming they are strings).
• Wecanwriteaforlooptodothis,butPythonprovidessomethingsimplerthatworks:
Can you infer from this the role of the string that the join funciton is applied to?
>>> s = “Hello world”
>>> t = list(s)
>>> print(t)
[‘H’, ‘e’, ‘l’, ‘l’, ‘o’, ‘ ‘, ‘w’, ‘o’, ‘r’, ‘l’, ‘d’]
>>> s = “Hello world”
>>> t = list(s)
>>> s1 = str(t)
>>> L1 = [ ‘No’, ‘one’, ‘expects’, ‘the’, ‘Spanish’, ‘Inquisition’ ]
>>> print(”.join(L1))
NooneexpectstheSpanishInquisition
>>> print(‘ ‘.join(L1))
No one expects the Spanish Inquisition
18.13. Part 3 Practice 87
CSCI-1100 Course Notes, Release
18.16 Indexing and Slicing Strings
• Wecanindexstrings:
• Wecanapplyalloftheslicingoperationstostringstocreatenewstrings:
• Unlikelists,however,wecannotuseindexingtoreplaceindividualcharactersinstrings:
18.17 Part 4 Practice
1. Givenalist
L = [ ‘cat’, ‘dog’, ‘tiger’, ‘lion’ ]
Rewrite L so that it is a list of lists, with household pets in the 0th (sub)list, zoo animals in the first. Using
slicing of L to create this new list and assign L to the result.
2. Howcanyouappendanadditionallistoffarmanimals(e.g.’horse’,’pig’and’cow’)toL?
3. Writecodetoremove’tiger’fromthesublistofzooanimals.
4. Supposeyouhavethestring
>>>s=”cat| dog |mouse|rat” and you’d like to have the list of strings
>>> L = [ “cat”, “dog”, “mouse”, “rat”]
Splitting the list alone does not solve the problem. Instead, you need to use a combination of splitting, and a loop that strips off the extra space characters from each string and appends to the final result. Write this code. It should be at most 4-5 lines of Python.
18.18 Summary
>>> s = “Hello, world!”
>>> print(s[5])
,
>>> print(s[-1])
!
>>> s = “Hello, world!”
>>> s[:len(s):2]
‘Hlo ol!’
>>> s[4] = ‘c’
Traceback (most recent call last):
File “
TypeError: ‘str’ object does not support item assignment
• • •
Assignmentoflistsandpassingoflistsasparameterscreatesaliasesoflistsratherthancopies. Weuseforloopstoiteratethroughalisttoworkoneachentyinthelist.
Weneedtocombineforloopswithindicesgeneratedbyarangeinordertochangethecontentsofalistof integers, floats or strings. These indices are also used to work with multiple lists at once.
88
Chapter 18. Lecture 10 — Lists Part 2
• Concatentation,replicationandslicingcreatenewlists.
• Mostotherlistfunctionsthatmodifyalistdosowithoutcreatinganewlist:insert,sort,append,pop,etc.
• Stringsmaybeindexedandsliced,butindexingmaynotbeusedtochangeastring.
• Conversionofastringtoalistisaccomplishedusingeitherlistorsplit;conversionofalistofstringstoa string uses join.
18.19 Additional Review Exercises: What Does Python Output?
1. WithouttypingintothePythoninterpreter,findtheoutputsfromthefollowingoperations:
2. Whatabouttheseoperations?
CSCI-1100 Course Notes, Release
>>> x = [‘a’,’b’,’c’,’d’, ‘e’]
>>> print(x)
>>> for item in x:
… print(“{} “.format(item)) …
>>> print(x[3])
>>> x[3] = 3
>>> x
>>> len(x)
>>> x[2]=x[1]
>>> x
>>> x[5]
>>> y = x[1:4]
>>> y
>>> x
>>> y = [1, 2, 3]
>>> y.append(‘cat’)
>>> y
>>> y.pop()
>>> y
>>> y.remove(2)
>>> y
>>> y.remove(‘cat’)
>>> z = [‘cat’,’dog’]
>>> z.insert(1,’pig’)
18.19. Additional Review Exercises: What Does Python Output? 89
CSCI-1100 Course Notes, Release
>>> z.insert(0,’ant’)
>>> z
>>> z.sort()
>>> z
>>> z1 = z[1:3]
>>> z1
>>> z
3. Writeafunctionthatreturnsalistcontainingthesmallestandlargestvaluesinthelistthatispassedtoitas an argument without changing the list? Can you think of several ways to do this?
(a) Usingminandmax
(b) Usingsorting(butremember,youcan’tchangetheoriginallist) (c) Usingaforloopthatsearchesforthesmallestandlargestvalues.
90
Chapter 18. Lecture 10 — Lists Part 2
16.1 Overview
• Loops are used to access and modify information stored in lists and are used to repeat computations many times.
• Weconstructloopsusinglogicalconditions:whileloops
• Wewillinvestiagesingleandmultipleloops
Reading: Our coverage of loops is in a different order than that of Practical Programming. A direct reference for reading material is Section 9.6.
16.2 Part 1: The Basics
• Loops allow us to repeat a block of code multiple times. This is the basis for many sophisticated program- ming tasks
• Wewillseetwowaystowriteloops:usingwhileloopsandforloops
• InPython,whileloopsaremoregeneralinPythonbecauseyoucanalwayswriteaforloopusingawhile
loop.
• Wewillstartwithwhileloopsfirstandthenseehowwecansimplifycommontaskswithforloopslater.
16.3 Basics of While
• Ourfirstwhileloopjustcountsnumbersfrom1to9,andprintsthem.
• Generalformofawhileloop:
• Steps
1. Evaluateanycodebeforewhile
CHAPTER
SIXTEEN LECTURE 9 — WHILE LOOPS
i=1
while i<10
print(i)
i += 1 ## if you forget this, your program will never end
while condition:
block
75
CSCI-1100 Course Notes, Release
2. Evaluatethewhileloopcondition:
(a) IfitisTrue,evaluatetheblockofcode,andthenrepeattheevaluationofthecondition. (b) IfitisFalse,endtheloop,andcontinuewiththecodeaftertheloop.
In other words, the cycle of evaluating the condition followed by evaluating the block of code continues until the condition evaluates to False.
• Animportantissuethatissometimeseasytoanswerandsometimesveryhardtoansweristoknowthatyour loop will always terminate.
16.4 Using Loops with Lists
• Often,weuseloopstorepeataspecificoperationoneveryelementofalist.
• Wemustbecarefultocreateanumberthatwillserveastheindexofelementsofalist.Validvaluesare:0up to (not including) the length of list.
co2_levels = [ (2001, 320.03), (2003, 322.16), (2004, 328.07),\
(2006, 323.91), (2008, 341.47), (2009, 348.92),\
(2010, 357.29), (2011, 363.77), (2012, 361.51),\
(2013, 382.47) ]
i=0
while i< len(co2_levels):
print( "Year", co2_levels[i][0], \
"CO2 levels:", co2_levels[i][1])
i += 1
• Let’smakesomeerrorstoseewhathappenstotheloop.
16.5 Part 1 Practice
1. Write a while loop to count down from 10 to 1, printing the values of the loop counting variable i (it could be some other variable name as well).
2. Modifyyourlooptoprintthevaluesinthelistco2_levelsinreverseorder.
16.6 Accumulation of values
• •
•
Often,weuseloopstoaccumulatesometypeofinformationsuchasaddingallthevaluesinalist. Let’schangethelooptoaddnumbersfrom1to9.
(Of course you can and should do this with the sum() function, but guess what that actually does!) Let’susealooptoaddthenumbersinalist.
i=1
total = 0
while i<10
total += i
i += 1
print(total)
76
Chapter 16. Lecture 9 — While Loops
CSCI-1100 Course Notes, Release
– Now,wewillusethenumberstheloopgeneratestoindexalist. – So,theloopmustgeneratenumbersfrom0tolengthofthelist.
co2_levels = [ (2001, 320.03), (2003, 322.16), (2004, 328.07),\
(2006, 323.91), (2008, 341.47), (2009, 348.92),\
(2010, 357.29), (2011, 363.77), (2012, 361.51),\
(2013, 382.47) ]
i=0
sum=0
while i< len(co2_levels):
sum += co2_levels[i][1]
i += 1
print("Total co2_levels is", sum)
• Let’shaveamoreinterestingexample.Beverycarefulnottouseanincorrectindexforthelist.
– CountthenumberofCO2valuesinthelistthataregreaterthan350.
– Calculateandprintthepercentagechangeineachmeasurementyearfromthepreviousmeasurement year.
– DeterminetheyearsinwhichtheCO2levelsdroppedcomparedtothepreviousmeasurement.Output just these years.
16.7 Part 2 Practice
1. Supposewewantedtoprintthefirst,third,fifth,etc.elementsinalist.Writecodetoaccomplishthis.
months=['jan','feb','mar','apr','may','jun','jul','aug','sep','oct','nov','dec']
2. Now,useasimilarloopcodetoprintalittleevergreentree.
3. Trythislater:changeyourlooptoworkforanysizeevergreen.
16.8 Loops that end on other conditions
• Hereisawhilelooptoaddthenon-zeronumbersthattheusertypesin.
*
***
*****
*******
*********
***
***
sum = 0
end_found = False
while not end_found:
x = int( input("Enter an integer to add (0 to end) ==> “))
if x == 0:
end_found = True
else:
16.7. Part 2 Practice 77
CSCI-1100 Course Notes, Release
• Wewillworkthroughthisloopbyhandinclass.
16.9 Multiple nested loops
• Loopsandifstatementscanbothbenested.
• We’vealreadyseenthisforifstatements.
• Here’sanexamplewhereweprinteverypairofvaluesinalist.
• Firstsolution:
L = [2, 21, 12, 8, 5, 31] i=0
while i < len(L):
j=0
while j < len(L):
print(L[i], L[j])
j += 1
i += 1
• Thissolutionprintsthevaluesfromthesamepairofindicestwice-e.g.thepair21,12isprintedoncewhen i=1, j=2 and once when i=2, j=1.
• Howcanwemodifyitsothatweonlyprinteachpaironce?
• Whathastochangeifwedon’twanttoprintwheni==j?
• Finally,wewillmodifytheresultinglooptofindthetwoclosestvaluesinthelist.
16.10 Summary
78
Chapter 16. Lecture 9 — While Loops
• •
• •
•
Loopsareespeciallyusefulforiteratingoveralist,accessingitscontents,andaddingorcountingthevalues from a list. This is done in the sum() and len() functions of Python.
Each loop has a stopping condition — the boolean expression in the while statement. The loop will end when the condition evaluates to True.
Ifthestoppingconditionisneverreached,theloopwillbecome“infinite”.
Often a counter variable is used. It (a) is given an initial value before the loop starts, (b) is incremented (or decremented) once in each loop iteration, and (c) is used to stop the loop when it reaches the index of the end (or beginning) of the list.
Wewilldemonstrateasimplewaytowritethesecommonloopswitha for loop in the next lecture.
sum += x
print(sum)
• Sofarwe’velookedatworkingwithindividualvaluesandvariables.
• Thisiscumbersomeevenforjusttwoorthreevariables.
• Weneedawaytoaggregatemultiplevaluesandrefertothemusingasinglevariable.
• Wehavedonealittlebitofthiswithtuplesandstrings,butnowwearegoingtogetstartedforreal.
This lecture is largely based on Sections 8.1-8.3 of Practical Programming. 14.2 Lists are Sequences of Values
• Gathertogethervaluesthathavecommonmeaning,verymuchliketuplesbutmuchmoreuseful–you’llsee why soon!
• Asafirstexample,herearescoresof7judgesforthefreeskatingpartofafigureskatingcompetition:
scores = [ 59, 61, 63, 63, 68, 64, 58 ]
• Asasecondexample,herearethenamesoftheplanetsinthesolarsystem(includingPluto,fornow):
• Notesonsyntax:
– Beginwith[andendwith]
– Commasseparatetheindividualvalues
– Thespacesbetweenvaluesareoptionalandareusedforclarityhere.
– Anytypeofobjectmaybestoredinalist,andeachlistcanmixdifferenttypes.
14.3 Why bother?
• Gathercommonvaluestogether,providingthemwithacommonname,especiallywhenwedon’tknowhow many values we will have.
• Applyanoperationtothevaluesasagroup.
CHAPTER
FOURTEEN LECTURE 8 — LISTS PART 1
14.1 Overview
planets = [ 'Mercury', 'Venus', 'Earth', 'Mras', 'Jupiter',
'Saturn', 'Neptune', 'Uranus', 'Pluto' ]
67
CSCI-1100 Course Notes, Release
• Applyanoperationtoeachvalueinthegroup. • Examplesofcomputationsonlists:
– Averageandstandarddeviation
– Whichvaluesareaboveandbelowtheaverage – Correctmistakes
– Removevalues(Pluto)
– Lookatdifferences
• Watchforthesethemesthroughoutthenextfewlectures.
14.4 Accessing Individual Values — Indexing
• Noticethatwemadethemistakeintyping’Mras’.Howdowefixthis?We’llstartbylookingatindexing.
• Theline
>>> print(planets[1])
accesses and prints the string at what’s known as index 1 of the list planets. This is similar to tuples!
• Eachitem/valueinthelistisassociatedwithauniqueindex
• IndexinginPython(andmostotherprogramminglanguages)startsat0.
• Thenotationisagaintouse[and]withaninteger(non-negative)toindicatewhichlistitem.
• Whatisthelastindexinplanets?
– Wecanfindthelengthusinglen()andthenfigureouttheanswer. 14.5 A Memory Model for Lists
We’ll draw a memory model in class that illustrates the relationship among • Thenameofthelist
• Theindices
• Thevaluesstoredinthelist
14.6 Practice Problems
We will work on these in class:
1. 2. 3.
Whatistheindexofthefirstvalueinscoresthatisgreaterthan65? WritealineofPythoncodetoprintthisvalueandtoprintthepreviousandnextvaluesofthelist.
Whatistheindexofthemiddlevalueinalistthatisoddlength?Forevenlengthlists,whataretheindicesof the middle two values?
68
Chapter 14. Lecture 8 — Lists Part 1
14.7 Changing Values in the List
• Onceweknowaboutindexing,changingavalueinalistiseasy:
>>> planets[3] = ‘Mars’
• Thismakesitem3ofplanetsnowrefertothestring’Mars’
• Nowwecanchecktheoutput:
>>> print(planets)
to make sure we got it right.
14.8 All Indices Are Not Allowed
• Iftisalist,thentheitemsarestoredatindicesfrom0tolen(t)-1.
• Ifyoutrytoaccessindicesatlen(t)orbeyond,yougetarun-timeerror.We’lltakealookandsee.
• Ifyouaccessnegativeindices,interestingthingshappen:
• Morespecifically,foranylistt,ifiisanindexfrom0tolen(t)-1thent[i]andt[i-len(t)]arethesame spot in the list.
14.9 Functions on Lists: Computing the Average
• Therearemanyfunctions(methods)onlists.Wecanlearnallaboutthemusingthehelpcommand. – Thisisjustlikewedidforstringsandformodules,e.g.
• Interestingly,wecanrunhelpintwoways,one
help(list)
gives us the list methods, and the second
help(planets)
tells us that planets is a list before giving us list methods.
• First,let’sseesomebasicfunctionsonthelistvalues.
• Thebasicfunctionsmax,sumandminmaybeappliedtolistsaswell.
• Thisgivesusasimplewaytocomputetheaverageofourlistofscores.
CSCI-1100 Course Notes, Release
>>> print(planets[-1])
Pluto
>>> import math
>>> help(math)
>>> help(str)
14.7. Changing Values in the List 69
CSCI-1100 Course Notes, Release
>>> print(“Average Scores = {:.2f}”.format( sum(scores) / len(scores) )) Average Scores = 62.29
>>> print(“Max Score =”, max(scores))
Max Score = 68
>>> print(“Min Score =”, min(scores))
Min Score = 58
• Exploring, we will look at what happens when we apply sum, max and min to our list of planet names. Can you explain the result?
14.10 Functions that modify the input: Sorting a list
•
•
Wecanalsosortthevaluesinalistbysortingit.Let’strythefollowing:
Notethatwedidnotassignthevaluereturnedbysorttoanewvariable.Thisisthesecondfunctionwehave learned that modifies the input but returns nothing. (The first one was Image.paste). Try the following and see what happens:
– Ok,whatisthevalueofthevariablenew_scores?Itisunclear.Let’stryinadifferentway.
So,thefunctionreturnsnothing!But,itdoeschangethevalueoftheinputlist.Thisisthefirstsuchfunction we have seen.
It does so because lists are containers, and functions can manipulate what is inside containers. Functions cannot do so for simple types like integer and float.
Ifwewantanewlistthatiswithoutchangingtheoriginallistthenweusethesorted()function:
>>> planets = [ ‘Mercury’, ‘Venus’, ‘Earth’, ‘Mras’, ‘Jupiter’, \
‘Saturn’, ‘Neptune’, ‘Uranus’, ‘Pluto’ ]
>>> planets
[‘Mercury’, ‘Venus’, ‘Earth’, ‘Mras’, ‘Jupiter’, ‘Saturn’, ‘Neptune’, ‘Uranus’, ‘Pluto’]
>>> planets.sort()
>>> planets
[‘Earth’, ‘Jupiter’, ‘Mercury’, ‘Mras’, ‘Neptune’, ‘Pluto’, ‘Saturn’, ‘Uranus’, ‘Venus’]
>>> scores = [ 59, 61, 63, 63, 68, 64, 58 ]
>>> new_scores = scores.sort()
>>> scores
[58, 59, 61, 63, 63, 64, 68]
>>> new_scores
>>>
>>> print(scores)
[58, 59, 61, 63, 63, 64, 68]
>>> print(new_scores)
None
>>>
• • •
>>> scores = [ 59, 61, 63, 63, 68, 64, 58 ]
>>> new_scores = sorted(scores)
>>> scores
[ 59, 61, 63, 63, 68, 64, 58 ]
>>> new_scores
[58, 59, 61, 63, 63, 64, 68]
>>>
70
Chapter 14. Lecture 8 — Lists Part 1
14.11 More Functions: Appending Values, Inserting Values, Deleting
• Now,wewillseemorefunctionsthatcanchangethevalueofalistwithoutreturninganything. • Armedwiththisknowledge,wecanfigureouthowtoaddandremovevaluesfromalist:
– append() – insert() – pop()
– remove()
• Theseoperationsarefundamentaltoany“container”—anobjecttypethatstoresotherobjects. – Listsareourfirstexampleofacontainer
14.12 Lists of Lists
• Notethatlistscancontainanymixtureofvalues,includingotherlists.
• Forexample,in
>>> L = [ ‘Alice’, 3.75, [‘MATH’, ‘CSCI’, ‘PSYC’ ], ‘PA’ ]
– L[0] is the name,
– L[1] is the GPA
– L[2] is a list of courses
– L[2][0] is the 0th course, ’MATH’ – L[3] is a home state abbreviation
• Wewillwritecodetoprintthecourses,tochangethemathcoursetoastatscourse,andtoappendazipcode.
14.13 Additional Practice Problems
1. Writethreedifferentwaysofremovingthelastvalue—’Pluto’—fromthelistofplanets.Twoofthesewill use the method pop.
2. Writecodetoinsert’Asteroidbelt’between’Mars’and’Jupiter’.
14.14 Summary
• Listsaresequencesofvalues,allowingthesevaluestobecollectedandprocessedtogether.
• Individualvaluescanbeaccessedandchangedthroughindexing.
• Functionsandmethodscanbeusedtoreturnimportantpropertiesoflistslikemin(),max(),sum(). • Functionsandmethodscanbealsousedtomodifylists,butnotreturnanything.
CSCI-1100 Course Notes, Release
14.11. More Functions: Appending Values, Inserting Values, Deleting 71
CHAPTER SIX
LECTURE 4 — USING FUNCTIONS AND MODULES
6.1
• •
•
6.2
• •
• •
6.3
•
Reading
Material for this lecture is drawn from Sections 3.1, 6.1 and 7.1-7.3 of Practical Programming. Topics that we will discuss include:
– Python functions for different data types.
– String functions and calling functions on objects – Using modules provided with Python
We will revisit all these concepts several times throughout the semester.
What have we learned so far?
So far, we have learned about three basic data types: integer, float and strings.
We also learned some valuable functions that operate on strings (len) and that convert between data types
(int, str)
The functions that Python provides are called built-in functions.
We will see examples of these functions and experiment with their use in this class.
How about numerical functions?
Many numerical functions also exist. Let us experiment with some of these first. You should make a note of what they do.
– abs()
– pow()
– int()
– float()
>>> name = “Neil Degrasse Tyson” >>> len(name)
19
>>> (name+”! “)*3
‘Neil Degrasse Tyson! Neil Degrasse Tyson! Neil Degrasse Tyson! ‘
27
CSCI-1100 Course Notes, Release
•
6.4
• •
•
– round() – max()
– min()
We will look carefully in class at how these work.
Objects and Methods
All variables in Python are objects. Objects are abstractions:
– Each object defines an organization and structure to the data they store.
– They have operations/functions — we call them methods — that we can apply to access and manipulate
this data.
– We don’t think about how they are implemented; instead we just think about how to use them. This is why they are called abstractions.
Methods associate with objects often use a function call syntax of the form
variable.method(arguments) For example:
This also works on particular values instead of variables:
value.method(arguments) as in
>>> ‘good morning’.find(‘o’, 3)
You can see all the methods that apply to an object type with help as well. Try:
>>> help(str)
String Methods
Here are a few more (of many) string methods:
>>> b = ‘good morning’ >>> b.find(‘o’, 3)
•
6.5
•
>>> name = “Neil Degrasse Tyson” >>> name.lower()
‘neil degrasse tyson’
>>> lowername = name.lower()
>>> lowername.upper()
‘NEIL DEGRASSE TYSON’
>>> lowername.capitalize()
‘Neil degrasse tyson’
>>> lowername.title()
‘Neil Degrasse Tyson’
>>> “abracadabra”.replace(“br”, “dr”)
28
Chapter6. Lecture4—Usingfunctionsandmodules
CSCI-1100 Course Notes, Release
‘adracadadra’
>>> “abracadabra”.replace(“a”, “”) ‘brcdbr’
>>> “Neil Degrasse Tyson”.find(” “) 4
>>> “Neil Degrasse Tyson”.find(“a”) 9
>>> “Neil Degrasse Tyson”.find(“x”) -1
>>> “Monty Python”.count(“o”)
2
>>> “aaabbbfsassassaaaa”.strip(“a”) ‘bbbfsassass’
• As described above, all of these are called in the form of object.method(arguments), where object is either a string variable or a string value.
• Not all functions on objects are called this way. Some are called using more of a function form, while others are called as operators.
– We will see the reason for the differences later in the semester.
• Note of caution: none of these functions change the variable that they are applied to.
6.6 Practice Problems (1)
1. Write code that takes a string in a variable called phrase and prints the string with all vowels removed.
2. Create a string in a variable and assign it to a variable called name. Write code to create a new string that repeats
each letter a in name as many times as a appears in name (assume the word is all lower case). For example,
3. Given a string in a variable called name, switch all letters a and e (only lowercase versions). Assume the variable contains only letters and spaces.
Hint: first replace each ‘a’ with ‘1’.
>>> episode = “Cheese Shop” >>> episode.lower()
‘cheese shop’
>>> len(episode)
11
>>> episode + “!” ‘Cheese Shop!’
>>> name = “amos eaton” ## your code goes here
>>> name ‘aamos eaaton’
>>> name = “Rensselaer Polytechnic Institute” ## your code goes here
6.6. PracticeProblems(1) 29
CSCI-1100 Course Notes, Release
6.7
• •
•
•
•
6.8
• •
6.9
•
• •
String Format Method
The format() method provides a nice way to produce clean looking output. For example, consider the code
Now look at what we can do with the format() method:
Method format() replaces the substrings between { } with values from the argument list.
– {0:.2f}meansargument0,willbeformattedasafloatwith2digitsshowntotherightofthedecimalplace.
* Notice it applies rounding.
– We can leave off the 0, the 1, and the 2 from before the : unless we want to change the order of the output. – We can leave off the :.2f if we want to accept print’s normal formatting on float outputs.
There are many variations on this and we will see quite a few as we progress through the semester.
Built-In Functions
All the functions we have seen so far are built-in to the core Python. It means that these functions are available when you start Python.
Type
>>> help(__builtins__) to see the full list.
Modules
Now we will begin to look at using functions that are not built into the core of Python but rather imported as modules.
Modules are collections of functions and constants that provide additional power to Python programs. Some modules come with Python, but are not loaded automatically. For example the math module.
}’.format(r,
>>> name
‘Ranssalear Polytachnic Instituta’
>>> pi = 3.14159
>>> r = 2.5
>>> h = 10**0.5
>>> volume = pi * r**2 ** h
>>> print(‘A cylinder of radius’, r, ‘and h’, height, ‘has volume’, volume)
A cylinder of radius 2.5 and height 3.1622776601683795 has volume 11472.95913962055
>>> out_string = ‘A cylinder of radius {0:.2f} and height {1:.2f} has volume {2:.2f >>> print(out_string)
A cylinder of radius 2.50 and height 3.16 has volume 11472.96
30
Chapter6. Lecture4—Usingfunctionsandmodules
• Other modules need to be installed first. When we installed software in Lab 0, we installed a library called pillow that has a number of image manipulation modules.
• To use a function in a module, first you must load it into your program using import. Let’s see the math module:
CSCI-1100 Course Notes, Release
>>> import math
>>> math.sqrt(5) 2.2360679774997898 >>> math.trunc(4.5) 4
>>> math.ceil(4.5) 5.0
>>> math.log(1024,2) 10.0
>>> math.pi 3.1415926535897931
• We can get an explanation of what functions and variables are provided in a module using the help function
6.10 Different Ways of Importing
• The way you import a module determines what syntax you need to use the contents of the module in your program.
• We can import only a selection of functions and variables:
• Or we can give a new name to the module within our program:
• Both of these methods help us distinguish between the function sqrt and the data pi defined in the math module from a function with the same name (if we had one) in our program.
• We can also do this (which is NOT recommended!):
>>> from math import *
Now, there is no name difference between the math module functions and ours. Since this leads to confusion
when the same name appears in two different modules it is almost always avoided.
>>> import math >>> help(math)
>>> from math import sqrt,pi >>> pi
3.141592653589793
>>> sqrt(4)
2.0
>>> import math as m >>> m.pi 3.141592653589793 >>> m.sqrt(4)
2.0
6.10. DifferentWaysofImporting 31
CSCI-1100 Course Notes, Release
6.11 Program Structure
• We have now seen several components of a program: import, comments, and our own code, including input, computation and output statements. We will add more components, such as our own functions, as we proceed through the semester.
• You should organize these components in your program files to make it easy to see the flow of program
• We will use the following convention to order the program components:
– an initial comment explaining the purpose of the program, – all import statements,
– then all variables and input commands,
– then all computation,
– finally all output.
6.12 Putting It All Together
• In the rest of this class we will write a program that first asks the user for a name, then asks for the radius and height of a cylinder, and finally prints the area and volume of the cylinder, nicely formatted.
6.13 Practice Problems (2)
1. The math module contains the constant e as well as pi. Write code that prints these values accurate to 3 decimal places and then write code that computes and outputs
⇡e
and
e⇡
2. Write a short program to ask the user to input height values (in cm) three times. After reading these values (as
integers), the program should output the largest, the smallest and the average of the height values.
3. What happens when we type
and then use math.pi?
6.14 Summary
• Python provides many functions that perform useful operations on strings, integers and floats. • Some of these functions are built in while others are organized into modules.
• After a module is imported, the functions in the module can be used by a call of the form:
both accurate to 2 decimal places.
import math math.pi = 3
32 Chapter6. Lecture4—Usingfunctionsandmodules
CSCI-1100 Course Notes, Release
module_name.function_name(arguments) • You can see the details of a function by:
>>> help(module_name.function_name)
• Python has many modules that make it easy to do complicated tasks. If you do not believe it, try typing:
>>> import antigravity
6.14. Summary 33
4.2
•
• •
4.3
• • •
4.4
•
More Than Just Numbers
Much of what we do today with computers revolves around text: – Web pages
– Facebook
– Text messages
These require working with strings.
Strings are our third type, after integers and floats. We’ve already seen the use of strings in output,
Topics for Today
String basics
String operations
Input to and output from your Python programs
Strings — Definition
A string is a sequence of 0 or more characters delimited by single quotes or double quotes.
CHAPTER FOUR
LECTURE 3 — PYTHON STRINGS
4.1 Reading
This material is drawn from Chapter 4 of Practical Programming, 2nd edition.
print(“Hello world”)
x=8
y = 10
print(“Value of x is”, x, “value of y is”, y)
17
CSCI-1100 Course Notes, Release
‘Rensselaer’
“Albany, NY”
‘4 8 15 16 23 42’
”
•
•
•
4.5
• • •
4.6
• •
•
We can print strings:
Strings may be assigned to variables:
Notice that unlike integers and floats there is now a difference between asking the Python function print to output the variable and asking the Python interpreter directly for the value of the variable.
Combining Single and Double Quotes in a String
A string that starts with double quotes must end with double quotes, and therefore we can have single quotes inside.
A string that starts with single quotes must end with single quotes and therefore we can have double quotes inside.
To illustrate this, we will take a look at
Multi-Line Strings
Ordinarily, strings do not extend across multiple lines, causing an error if you try.
But, starting and ending a string “”” or ’’’ tells Python to allow the string to cross multiple lines.
– Any character other than ’’’ (or “””, if that is how the string started) is allowed inside the string. Example,
>>> print(“Hello, world!”) Hello, world!
>>> s = ‘Hello’ >>> t = “Good-bye” >>> print(s)
Hello
>>> t
‘Good-bye’
>>> s = ‘He said, “Hello, World!”‘
>>> t = “Many single quotes here ”””’ and here ”’ but correct.”
>>> s1 = “””This is a multi-line string.”””
>>> s1
‘This\nis a multi-line\nstring.’
>>> print s1 This
is a multi-line string.
>>>
18
Chapter4. Lecture3—PythonStrings
CSCI-1100 Course Notes, Release
•
4.7
• •
•
4.8
•
•
Notice the \n when we ask Python for the value of the string (instead of printing it). This is an escape character, as we will discuss next.
Escape Characters
Inserting a \ in the middle of a string tells Python that the next character will have special meaning (if it is possible for it to have special meaning).
Most importantly:
– \n — end the current line of text and start a new one
– \t — skip to the next “tab stop” in the text. This allows output in columns – \’ — do not interpret the ’ as a string delimiter
– \” — do not interpret the ” as a string delimiter
– \\ — put a true back-slash character into the string
We’ll explore the following strings in class
String Operations — Concatenation
Concatenation: Two (or more) strings may be concatenated to form a new string, either with or without the + operator. We’ll look at
Notice that
is a syntax error but
>>> “Hello” ” World” is not. Can you think why?
String Operations — Replication
You can replicate strings by multiplying them by an integer:
>>> s0 = “*\t*\n**\t**\n***\t***\n”
>>> s1 = “I said, \”This is a valid string.\””
>>> s0 = “Hello”
>>> s1 = “World”
>>> s0 + s1
>>> s0 + ‘ ‘ + s1
>>> ‘Good’ ‘Morning’ ‘America!’ >>> ‘Good ‘ ‘Morning ‘ ‘America!’
>>> s0 = “Hello” >>> s1 = ” World” >>> s0 s1
4.9
•
>>> s = ‘Ha’
>>> print(s * 10) HaHaHaHaHaHaHaHaHaHa
4.7. EscapeCharacters 19
CSCI-1100 Course Notes, Release
• What do you think multiplying a string by a negative integer or 0 does? Try it.
• Many expressions you might try to write involving strings and either ints or floats are illegal Python, including the following:
Think about why
4.10 Practice Problems – Part 1
We will go over these during lecture:
1. Which are valid Python strings:
For those that are not valid, what needs to be fixed? For those that are, what is the output when they are passed to the print function?
2. What is the output?
3. What is the output?
4. Which of the following are legal? For those that are, show what Python outputs when these are typed directly into the interpreter.
>>> ‘Hello’ * 8.1 >>> ‘123’ + 4
>>> s1 = ‘”Hi mom”, I said. “How are you?”‘
>>> s2 = ‘”Hi mom”, I said. ‘”How are you?”
>>> s3 = ‘”Hi mom”, I said. ‘”How are you?”‘
>>> s4 = “””‘Hi mom”, I said. ‘”How are you?”‘”””
>>> s5 = “”I want to be a lion tamer!”‘
>>> s6 = “\”Is this a cheese shop?\”\n\t’Yes’\n\t\”We have all kinds!\””
>>> s = “Cats\tare\n\tgood\tsources\n\t\tof\tinternet\tmemes” >>> s
>>> print(s)
print(‘\\’*4) print(‘\\\n’*3) print(‘Good-bye’)
>>> ‘abc’ ‘def’ >>> ‘abc’ + ‘def’ >>> ‘abc ‘ + ‘def’ >>> x = ‘abc’
>>> y = ‘def’
>>> x+y
>>> x y
>>> s1 = ‘abc’*4 >>> s1
>>> s2 = ‘abc ‘*4 >>> print(s2)
4.11 String Operations — Functions
• Python provides many operations for us to use in the form of functions. We have already seen print(), but now we are going to look at other functions that operate on strings.
20 Chapter4. Lecture3—PythonStrings
CSCI-1100 Course Notes, Release
• You can compute the length of a string with len().
• Here is what happens:
1. Function len is provided with the value of the string associated with variable s
2. len calculates the number of characters in the provided string using its own code, code that is built-in to Python.
3. len returns the calculated value (in this case, 6) and this value is sent to the print function, which actually generates the output.
• We will learn more about using functions in Lectures 4 and 5.
4.12 Example String Functions
• We will look at examples of all of the following during lecture…
• You can convert an integer or float to a string with str().
• You can convert a string that is in the form of an integer to an integer using int()
• You can convert a string that is in the form of a float to a float using, not surprisingly, float()
4.13 The print Function in More Detail
• We already know a bit about how to use print(), but we can learn about more using help()
>>> s = “Hello!” >>> print(len(s))
help(print)
Help on built-in function print in module builtins:
print(…)
print(value, …, sep=’ ‘, end=’\n’, file=sys.stdout, flush=False)
Prints the values to a stream, or to sys.stdout by default.
Optional keyword arguments:
file: a file-like object (stream); defaults to the current sys.stdout. sep: string inserted between values, default a space.
end: string appended after the last value, default a newline.
flush: whether to forcibly flush the stream.
• We will focus on the sep and end and illustrate with examples. 4.14 User Input
• Python programs can ask the user for input using the function called input.
• This waits for the user to type a line of input, which Python reads as a string.
• This string can be converted to an integer or a float (as long as it is properly an int/float). • Here is a toy example
4.12. ExampleStringFunctions 21
CSCI-1100 Course Notes, Release
• We can also insert the string right into the input function call:
• We will use this idea to modify our area and volume calculation so that the user of the program types in the numbers.
– The result is more useful and feels more like a real program (run from the command line). – It will be posted on the course website.
4.15 Practice Problems – Part 2
1. What is the output for this Python program?
2. Which of the following are legal? For those that are, show what Python outputs when these are typed directly into the interpreter.
3. What is the output when the user types the value 64 when running the following Python program?
What happens when you do not have the call to the int function?
4. Write a program that requests an integer from the user as an input and stores in the variable n. The program
should then print n 1’s with 0’s inbetween. For example if the user input the value 4 then the output should be 1010101
4.16 Summary
• Strings represent character sequences — our third Python type
print(len(‘George’))
print(len(‘ Tom ‘))
s = “””Hi
sis!
“””
print(len(s))
>>> ‘abc’ + str(5) >>> ‘abc’ * str(5) >>> ‘abc’ + 5
>>> ‘abc’ * 5
>>> ‘abc’ + 5.0
>>> ‘abc’ + float(5.0) >>> str(3.0) * 3
x = int(input(‘Enter an integer ==> ‘))
y = x // 10
z = y % 10
print(x, ‘,’, y, z, sep=”)
22
Chapter4. Lecture3—PythonStrings
print(“Enter a number”)
x = float(input())
print(“The square of’, x, ‘is’, x*x)
x = input(“Enter a new number “)
x = float(x)
print(“The square of’, x, ‘is’, x*x)
• String operations include addition (concatenate) and replication
• Functions on strings may be used to determine length and to convert back and forth to integers and floats.
• Escape sequences change the meaning of special Python characters or make certain characters have special meaning.
• Some special characters of note: \n for new line, \t for tab. They are each preceded by \
• The print() function offers significant flexibility.
• We can read input using input()
CSCI-1100 Course Notes, Release
4.16. Summary 23
2.1 Overview
CHAPTER TWO
LECTURE 2 — PYTHON AS A CALCULATOR
Most of this is covered in Chapter 2 of both Practical Programming • Part 1:
– Expressions and values – Types
– Precedence
• Part 2:
– Variables and memory
– Errors
– Typing directly in the interpreter vs. running programs; use of print – Documentation and variable names
Throughout we will pay attention to problems and mistakes, both real and potential.
2.2 Aside: Lectures, Note Taking and Exercises
• Lecture notes are outlines.
– Therefore, you should hand-write details as we cover them in class.
• We will create and run examples in class.
– You should write down the shorter ones
– We will post the longer ones on-line, but you should write down as much as you can, especially about the results of running the examples.
2.3 Python As a Calculator
We will start class by using Python as an interactive calculator, working through a number of examples. • The area of a circle.
• The number of minutes in a year.
7
CSCI-1100 Course Notes, Release
• • •
2.4
• •
•
•
2.5
• •
• •
2.6
•
• •
2.7
•
•
The volume of a box.
The volume of the earth in cubic kilometers.
In doing so, we will look at the basic operations of +, -, *, /, and ** (exponentiation).
Whole Number Calculations
Most of the calculations in the foregoing examples involve numbers with fractional values.
Sometimes we want to use whole number of calculations, for example to convert a number of minutes to a number of hours and minutes (less than 60).
In this case, Python offers us different forms of divisions – // is the operator for whole number division
– % is used to find the remainder
For this kind of division, be careful of negative numbers. Can you figure out how they work with // and %?
– This is a case where experimentation with the Python interpreter is crucial. We will encourage you to do this throughout the semester.
Python Types
We have seen what look like real numbers and whole numbers. These are two different types in Python.
A type is a set of possible values — also called a “representation” — and a set of operations on those values.
– Our first examples are the “operators” as +, -, *, / and **
Common Python types we are working with initially include float, int (short for integer) and str (short for
string)
Each value we create will be referred to as an object
float
The float type approximates real numbers. But computers can’t represent all of them because computers only dedicate a finite amount of memory to each.
Limited precision: we’ll look at 2/3, 5/3 and 8/3
Any time integers and floats are mixed and any time we apply division, the result is always a float.
int
The int (integer) type is analogous to whole numbers: { …, -4, -3, -2, -1, 0, 1, 2, 3, 4, …}
Python can represent seemingly arbitrarily large integers, which is not true of other languages like C, C++ and Java
8
Chapter2. Lecture2—PythonasaCalculator
– Using the Python interpreter, we will look at the examples of:
2.8 Precedence
• What is wrong with the computation
>>> 45 – 32 * 5 / 9
as a way of converting 45 degree Fahrenheit to Celsius?
• Largely following the standard rules of algebra, Python applies operations in order of precedence from. Here is a summary of these rules from highest to lowest:
1. ( ) – parentheses
2. ** – the exponentiation operator, ordered right-to-left 3. – – the negation (unary minus) operators, as in -5**2 4. *,/,//,% – ordered left-to-right
5. +,- – ordered left-to-right
• This example also suggests an important question: how do we know we’ve made a mistake – introduced a bug – in our code?
2.9 Part 1 Practice Problems
1. The consider the following evaluations (some of them trivial). Which results are float objects and which are int objects?
2. What is output by the Python interpreter?
3. Write a single line of Python code that calculates the radius of a circle with area 15 units and prints the value. The output should just be the number that your code produces. Your code should include the use of an expression involving division and exponentiation (to compute the square root). Use the value 3.14159 for pi.
CSCI-1100 Course Notes, Release
>>> 1**1**1 >>> 2**2**2 >>> 3**3**3
>>> 9 #1 >>> 9. #2 >>> 9.0 #3 >>> 9 + 3 #4 >>> 9 – 3. #5 >>> 9 / 4 #6 >>> 9 // 4 #7 >>> 9. // 4 #8
>>> 2**3**2
>>> (2**3)**2
>>> -2**3 – 2 * 5
2.8. Precedence 9
CSCI-1100 Course Notes, Release
2.10 Part 2
2.11 Variables and Assignment
• Most calculators have one or several memory keys. Python, and all other programming languages, use “vari- ables” as their memory.
• We’ll start with a simple example of the area of a circle, typed in class. You will notice as we go through this that there is no output until we use the print functions.
• Here is a more extensive example of computing the volume and surface area of a cylinder:
• A variable is a name that has a value “associated” with it. – There are six variables in the above code.
• The value is substituted in for the variable when the variable appears on the right hand side of the =.
• The value is assigned to the variable when the variable name appears on the left hand side of the =.
2.12 More on Variable Assignment
>>> pi = 3.14159
>>> radius = 2
>>> height = 10
>>> base_area = pi * radius ** 2
>>> volume = base_area * height
>>> surface_area = 2 * base_area + 2 * pi * radius * height
>>> print(“volume is”, volume, “, surface area is”, surface_area) volume is 125.6636 , surface area is 150.79632
• •
•
• •
•
The operator = is an assignment of a value (calculated on the right side) to a variable (on the left). In the following..
>>> base_area = pi * radius ** 2
Python
– accesses the values associated with the variables pi and radius,
– squares the value associated with radius and then multiplies the result by the value associated with the variable pi,
– associates the result with the variable base_area
Later, Python accesses the value of base_area when calculating the values to assign to volume and
surface_area.
Thus, the meaning of = in Python is quite different from the meaning of = in mathematics. The statement
>>> base_area * height = volume is not legal Python code. Try it!
It takes a while to get accustomed to the meaning of an assignment statement in Python.
10
Chapter2. Lecture2—PythonasaCalculator
2.13 print
• Consider the line
>>> print(“volume is”, volume, “, surface area is”, surface_area)
• print is a Python “function” that combines strings (between the quotations) and values of variables, sep-
arated by commas, to generate nice output.
• We will play with a number of examples in class to illustrate use of print. As the semester progresses we will learn a lot more about it.
2.14 Variable Names
• Notice that our example variable names include letters and the _ (underscore) character.
• Legal variable names in Python must
– Start with a letter or a _, and
– Be followed by any number of letters, underscores or digits.
Characters that are none of these, including spaces, signal the end of a variable name.
• Capital letters and small letters are different
• We will look at many examples in class.
2.15 Putting Your Code in a File
• So far in today’s lecture we have written our code using the Python Shell.
– This sends your Python statements directly to the interpreter to execute them
• Now we will switch to writing and saving our code in a file and then sending the file to the Python interpreter to be run.
• We will demonstrate using the surface area and volume calculations from earlier in lecture.
• Almost all code that you write for lecture exercises, labs, and homework assignments will be stored in files.
• You will practice in Lab 1 next week.
• Sometimes in class we will still type things directly into the shell. You will know we are doing this when you see >>>
2.16 Syntax and Semantic Errors
• Pythontellsusabouttheerrorswemakeinwritingthenamesofvariablesandinreversingtheleftandrightside of the = operator.
• These are examples of syntax errors — errors in the form of the code.
• Programs with syntax errors will not run; the Python interpreter inspects the code and tells us about these errors
before it tries to execute them. We can then fix the errors and try again
CSCI-1100 Course Notes, Release
2.13. print 11
CSCI-1100 Course Notes, Release
• More difficult to find and fix are semantic errors — errors in the logical meaning of our programs resulting in an incorrect result.
– We have already seen an example of a semantic error. Can you think where?
– Throughout the semester we will discuss strategies for finding and fixing semantic errors.
2.17 Python Keywords
• All variable names that follow the above rules are legal Python names except for a set of “keywords” that have special meaning to Python.
• Keywords allow us to write more complicated operations — involving logic and repetition — than just calculat- ing.
• You can get a list of Python keywords by typing into the shell
• Over the next few lectures, we will soon understand the detailed meaning of the . in the above statement.
2.18 Do Variables Exist Before They Are Assigned a Value?
• Suppose we forgot to assign pi a value? What would happen? – Try it out!
• Variables do not exist until they are assigned a value. • This is a simple form of semantic error.
2.19 Example to Consider
1. Create 2 invalid variable names and 4 valid variable names from the _ character, the digit 0, and the letter a. 2.20 Mixed Operators
•
•
•
Assignments of the form
>>> i = i + 1
are commonly seen in Python. We will take a careful look at what is happening here.
Python contains a short-hand for these:
>>> i += 1
These two statements are exactly equivalent. Other mixed operators include
>>> import keyword
>>> print(keyword.kwlist)
12
Chapter2. Lecture2—PythonasaCalculator
CSCI-1100 Course Notes, Release
-= *= /=
but += is used most commonly for reasons that will gradually become clear over the first half of the semester. 2.21 Terminology: Expressions
• Expressions are formed from combinations values, variables and operators.
• In the examples we’ve seen so far, expressions are on the right-hand side of an assignment statement, as in:
>>> surface_area = 2 * base_area + 2 * pi * radius * height 2.22 Part 2 Practice Problems
1. Which of the following are legal Python variable names?
2. Which of these lines of code contain syntax errors? Once you fix the syntax errors, the program (assume this has been typed into a file and run in the Wing IDE) will still not correctly print the area of a circle with radius 6.5. What two more changes are needed to fixed these errors?
3. Assuming you start with $100 and earn 5% interest each year, how much much will you have at the end of one year, two years and three years? Write Python expressions to calculate these, using variables as appropriate. We will write the solution into a file and run the file using the interpreter.
4. What is the output of the following Python code (when typed into a file and run in the interpreter)? Try to figure it out by hand before typing the statements into a file and running in the Python interpreter.
import
56abc
abc56
car-talk
car_talk
car talk
pi = 21 / 7
area = pi * r * r
r = 6.5
r + 5 = r_new
print(area)
x = 12
y = 7.4
x -= y print(x, y) y = y-x +7 z=1
x *= 2 + z print(x, y) x += x*y print(x, y)
2.21. Terminology: Expressions 13
CSCI-1100 Course Notes, Release
2.23 Summary — Important Points to Remember
• Expressions are formed from combinations values, variables and operators
• Values in Python are one of several different types — integers and floats for now. • Variables are Python’s form of memory
• Python keywords can not be used as variables.
• = is Python’s means of assigning a value to a variable
• Variables do not exist in Python until they are given a value
• Make sure you have the precedence correct in your Python expressions.
14
Chapter2. Lecture2—PythonasaCalculator