MIT Python Course All Class Slide
MIT Python Course All Class Slide
1
TODAY
Course info
What is computation
Python basics
Mathematical operations
Python variables and types
NOTE: slides and code files up before each lecture
Highly encourage you to download them before class
Take notes and run code files when I do
Do the in-class “You try it” breaks
Class will not be recorded
Class will be live-Zoomed for those sick/quarantine
6.100L Lecture 1
WHY COME TO CLASS?
6.100L Lecture 1
OFFICE
PSETS
HOURS
OPTIONAL
PIAZZA (practice)
PROBLEM
SOLVING MANDATORY
FINGER
PRACTICE
EXERCISES
LECTURES
KNOWLEDGE PROGRAMMING
OF CONCEPTS SKILL
RECITATION
EXAMS
6.100L Lecture 1
LET’S GOOOOO!
6
TYPES of KNOWLEDGE
6.100L Lecture 1
NUMERICAL EXAMPLE
6.100L Lecture 1
NUMERICAL EXAMPLE
6.100L Lecture 1
NUMERICAL EXAMPLE
10
6.100L Lecture 1
WE HAVE an ALGORITHM
11
6.100L Lecture 1
ALGORITHMS are RECIPES /
RECIPES are ALGORITHMS
Bake cake from a box
1) Mix dry ingredients
2) Add eggs and milk
3) Pour mixture in a pan
4) Bake at 350F for 5 minutes
5) Stick a toothpick in the cake
6a) If toothpick does not come out clean, repeat step 4 and 5
6b) Otherwise, take pan out of the oven
7) Eat
12
6.100L Lecture 1
COMPUTERS are MACHINES that
EXECUTE ALGORITHMS
Two things computers do:
Performs simple operations
100s of billions per second!
Remembers results
100s of gigabytes of storage!
What kinds of calculations?
Built-in to the machine, e.g., +
Ones that you define as the programmer
The BIG IDEA here?
13
6.100L Lecture 1
A COMPUTER WILL ONLY DO
WHAT YOU TELL IT TO DO
14
6.100L Lecture 1
COMPUTERS are MACHINES that
EXECUTE ALGORITHMS
Fixed program computer
Fixed set of algorithms
What we had until 1940’s
Stored program computer
Machine stores and executes instructions
Key insight: Programs are no different from other kinds of data
15
6.100L Lecture 1
STORED PROGRAM COMPUTER
16
6.100L Lecture 1
MEMORY
CONTROL ARITHMETIC
UNIT LOGIC UNIT
program counter do primitive ops
INPUT OUTPUT
17
6.100L Lecture 1
3456 3 7889 5
3457 4 7890 2
3458
3459 True
7891
7892 MEMORY
3460 7893
3461 False 7894
INPUT OUTPUT
18
6.100L Lecture 1
3456 3 7889 5
3457 4 7890 2
3458
3459 True
7891
7892 MEMORY
3460 7893
3461 False 7894
INPUT OUTPUT
19
6.100L Lecture 1
3456 3 7889 5
3457 4 7890 2
3458
3459
7
True
7891
7892 MEMORY
3460 7893
3461 False 7894
INPUT OUTPUT
20
6.100L Lecture 1
3456 3 7889 5
3457 4 7890 2
3458
3459
7
True
7891
7892 MEMORY
3460 7893
3461 False 7894
INPUT OUTPUT
21
6.100L Lecture 1
3456 3 7889 5
3457 4 7890 2
3458
3459
7
True
7891
7892
7
MEMORY
3460 7893
3461 False 7894
INPUT OUTPUT
22
6.100L Lecture 1
3456 3 7889 5
3457 4 7890 2
3458
3459
7
True
7891
7892
7
MEMORY
3460 7893
3461 False 7894
INPUT OUTPUT
23
6.100L Lecture 1
3456 3 7889 5
3457 4 7890 2
3458
3459
7
True
7891
7892
7
MEMORY
3460 7893
3461 False 7894
INPUT OUTPUT
True
24
6.100L Lecture 1
BASIC PRIMITIVES
6.100L Lecture 1
ASPECTS of LANGUAGES
Primitive constructs
English: words
Programming language: numbers, strings, simple operators
26
6.100L Lecture 1
ASPECTS of LANGUAGES
Syntax
English: "cat dog boy" not syntactically valid
"cat hugs boy" syntactically valid
Programming language: "hi"5 not syntactically valid
"hi"*5 syntactically valid
27
6.100L Lecture 1
ASPECTS of LANGUAGES
28
6.100L Lecture 1
ASPECTS of LANGUAGES
29
6.100L Lecture 1
WHERE THINGS GO WRONG
Syntactic errors
Common and easily caught
Static semantic errors
Some languages check for these before running
program
Can cause unpredictable behavior
No linguistic errors, but different meaning
than what programmer intended
Program crashes, stops running
Program runs forever
Program gives an answer, but it’s wrong!
30
6.100L Lecture 1
PYTHON PROGRAMS
31
6.100L Lecture 1
PROGRAMMING ENVIRONMENT:
ANACONDA
Code Editor
Shell / Console
32
6.100L Lecture 1
OBJECTS
33
6.100L Lecture 1
OBJECTS
34
6.100L Lecture 1
SCALAR OBJECTS
>>> type(5)
int
>>> type(3.0)
float
35
6.100L Lecture 1
int float
0, 1, 2, …
0.0, …, 0.21, …
300, 301 …
1.0, …, 3.14, …
-1, -2, -3, …
-1.22, …, -500.0 , …
-400, -401, …
bool NoneType
True
False None
36
6.100L Lecture 1
YOU TRY IT!
In your console, find the type of:
1234
8.99
9.0
True
False
37
6.100L Lecture 1
TYPE CONVERSIONS (CASTING)
38
6.100L Lecture 1
YOU TRY IT!
In your console, find the type of:
float(123)
round(7.9)
float(round(7.2))
int(7.2)
int(7.9)
39
6.100L Lecture 1
EXPRESSIONS
40
6.100L Lecture 1
BIG IDEA
Replace complex
expressions by ONE value
Work systematically to evaluate the expression.
41
6.100L Lecture 1
EXAMPLES
>>> 3+2
5
>>> (4+2)*6-1
35
>>> type((4+2)*6-1)
int
>>> float((4+2)*6-1)
35.0
42
6.100L Lecture 1
YOU TRY IT!
In your console, find the values of the following expressions:
(13-4) / (12*12)
type(4*3)
type(4.0*3)
int(1/2)
43
6.100L Lecture 1
OPERATORS on int and float
44
6.100L Lecture 1
SIMPLE OPERATIONS
**
45
6.100L Lecture 1
SO MANY OBJECTS, what to do
with them?!
temp = 100.4
a= 2
go = True
b= -0.3
x= 123 flag = False
n= 17
small = 0.001
46
6.100L Lecture 1
VARIABLES
CS variables
Is bound to one single value at a given time a = b + 1
Can be bound to an expression
(but expressions evaluate to one value!) m = 10
F = m*9.98
47
6.100L Lecture 1
BINDING VARIABLES to VALUES
pi = 355/113
Step 1: Compute the value on the right hand side (the VALUE)
Value stored in computer memory
Step 2: Store it (bind it) to the left hand side (the VARIABLE)
Retrieve value associated with name by invoking the name
(typing it out)
48
6.100L Lecture 1
YOU TRY IT!
Which of these are allowed in Python? Type them in the
console to check.
x = 6
6 = x
x*y = 3+4
xy = 3+4
49
6.100L Lecture 1
ABSTRACTING EXPRESSIONS
6.100L Lecture 1
WHAT IS BEST CODE STYLE?
#do calculations
a = 355/113 *(2.2**2)
c = 355/113 *(2.2*2)
p = 355/113
r = 2.2
#multiply p with r squared
a = p*(r**2)
#multiply p with r times 2
c = p*(r*2)
6.100L Lecture 1
CHANGE BINDINGS
52
6.100L Lecture 1
BIG IDEA
Lines are evaluated one
after the other
No skipping around, yet.
We’ll see how lines can be skipped/repeated later.
53
6.100L Lecture 1
YOU TRY IT!
These 3 lines are executed in order. What are the values of
meters and feet variables at each line in the code?
meters = 100
feet = 3.2808 * meters
meters = 200
ANSWER:
Let’s use PythonTutor to figure out what is going on
Follow along with this Python Tutor LINK
Where did we tell Python to (re)calculate feet?
54
6.100L Lecture 1
YOU TRY IT!
Swap values of x and y without binding the numbers directly.
Debug (aka fix) this code.
x = 1 1
y = 2 x
2
y
y = x
x = y
Python Tutor to the rescue?
ANSWER:
1
x
2
y
temp
55
6.100L Lecture 1
SUMMARY
Objects
Objects in memory have types.
Types tell Python what operations you can do with the objects.
Expressions evaluate to one value and involve objects and operations.
Variables bind names to objects.
= sign is an assignment, for ex. var = type(5*4)
Programs
Programs only do what you tell them to do.
Lines of code are executed in order.
Good variable names and comments help you read code later.
56
6.100L Lecture 1
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
57
STRINGS, INPUT/OUTPUT,
and BRANCHING
(download slides and .py files to follow along)
6.100L Lecture 2
Ana Bell
1
pi = 3.14 3.14
RECAP radius = 2.2
pi
2.2
area = pi*(radius**2)
radius
area 3.2
radius = radius+1
15.1976
var = type(5*4) var int
Objects
Objects in memory have types.
Types tell Python what operations you can do with the objects.
Expressions evaluate to one value and involve objects and operations.
Variables bind names to objects.
= sign is an assignment, for ex. var = type(5*4)
Programs
Programs only do what you tell them to do.
Lines of code are executed in order.
Good variable names and comments help you read code later.
2
6.100L Lecture 2 2
STRINGS
6.100L Lecture 2 3
STRINGS
silly = a * 3 c "memyself"
d "me myself"
silly "mememe"
6.100L Lecture 2 4
YOU TRY IT!
What’s the value of s1 and s2?
b = ":"
c = ")"
s1 = b + 2*c
f = "a"
g = " b"
h = "3"
s2 = (f+g)*int(h)
6.100L Lecture 2 5
STRING OPERATIONS
s = "abc"
len(s) evaluates to 3
chars = len(s)
6.100L Lecture 2 7
SLICING to get
ONE CHARACTER IN A STRING
Square brackets used to perform indexing
into a string to get the value at a certain
index/position
s = "abc"
index:
index:
0 1 2 indexing always starts at 0
-3 -2 -1 index of last element is len(s) - 1 or -1
s[0] evaluates to "a"
s[1] evaluates to "b"
s[2] evaluates to "c"
s[3] trying to index out of
bounds, error
s[-1] evaluates to "c"
s[-2] evaluates to "b"
s[-3] evaluates to "a"
7
6.100L Lecture 2 8
SLICING to get a SUBSTRING
6.100L Lecture 2 9
SLICING EXAMPLES
s = "abcdefgh"
index: 0 1 2 3 4 5 6 7
index: -8 -7 -6 -5 -4 -3 -2 -1
6.100L Lecture 2 10
YOU TRY IT!
s = "ABC d3f ghi"
s[3:len(s)-1]
s[4:0:-1]
s[6:3]
10
6.100L Lecture 2 11
IMMUTABLE STRINGS
"bar"
s
11
6.100L Lecture 2 12
BIG IDEA
If you are wondering
“what happens if”…
Just try it out in the console!
12
6.100L Lecture 2 13
INPUT/OUTPUT
13
6.100L Lecture 2 14
PRINTING
6.100L Lecture 2 15
INPUT
x = input(s)
Prints the value of the string s
User types in something and hits enter
That value is assigned to the variable x
Binds that value to a variable
text = input("Type anything: ")
print(5*text)
SHELL:
Type anything:
15
6.100L Lecture 2 17
INPUT
x = input(s)
Prints the value of the string s
User types in something and hits enter
That value is assigned to the variable x
Binds that value to a variable
text = input("Type anything: ")
print(5*text)
SHELL:
16
6.100L Lecture 2 18
INPUT
x = input(s)
Prints the value of the string s
User types in something and hits enter
That value is assigned to the variable x
Binds that value to a variable
text = input("Type anything: ")
print(5*text)
SHELL:
17
6.100L Lecture 2 19
INPUT
x = input(s)
Prints the value of the string s
User types in something and hits enter
That value is assigned to the variable x
Binds that value to a variable
text = input("Type anything: ")
print(5*text)
SHELL:
18
6.100L Lecture 2 20
INPUT
x = input(s)
Prints the value of the string s
User types in something and hits enter
That value is assigned to the variable x
Binds that value to a variable
text = input("Type anything: ")
print(5*text)
SHELL:
19
6.100L Lecture 2 21
INPUT
input always returns an str, must cast if working with numbers
num1 = input("Type a number: ")
print(5*num1)
num2 = int(input("Type a number: "))
print(5*num2)
SHELL:
num1 "3"
Type a number: 3
20
6.100L Lecture 2 22
INPUT
input always returns an str, must cast if working with numbers
num1 = input("Type a number: ")
print(5*num1)
num2 = int(input("Type a number: "))
print(5*num2)
SHELL:
num1 "3"
Type a number: 3
33333
21
6.100L Lecture 2 23
INPUT
input always returns an str, must cast if working with numbers
num1 = input("Type a number: ")
print(5*num1)
num2 = int(input("Type a number: "))
print(5*num2)
SHELL:
num1 "3"
Type a number: 3
33333
Type a number: 3
22
6.100L Lecture 2 24
INPUT
input always returns an str, must cast if working with numbers
num1 = input("Type a number: ")
print(5*num1)
num2 = int(input("Type a number: "))
print(5*num2)
SHELL:
num1 "3"
Type a number: 3
33333
num2 3
Type a number: 3
23
6.100L Lecture 2 25
INPUT
input always returns an str, must cast if working with numbers
num1 = input("Type a number: ")
print(5*num1)
num2 = int(input("Type a number: "))
print(5*num2)
SHELL:
num1 "3"
Type a number: 3
33333
num2 3
Type a number: 3
15
24
6.100L Lecture 2 26
YOU TRY IT!
Write a program that
Asks the user for a verb
Prints “I can _ better than you” where you replace _ with the verb.
Then prints the verb 5 times in a row separated by spaces.
For example, if the user enters run, you print:
I can run better than you!
run run run run run
25
6.100L Lecture 2 27
AN IMPORTANT ALGORITHM:
NEWTON’S METHOD
Finds roots of a polynomial
E.g., find g such that f(g, x) = g3 – x = 0
Algorithm uses successive approximation
𝑓𝑓(𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔)
next_guess = guess -
𝑓𝑓′ (𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔)
Partial code of algorithm that gets input and finds next guess
6.100L Lecture 2 29
F-STRINGS
6.100L Lecture 2 30
BIG IDEA
Expressions can be
placed anywhere.
Python evaluates them!
28
6.100L Lecture 2 32
CONDITIONS for
BRANCHING
29
6.100L Lecture 2 33
BINDING VARIABLES and VALUES
variable = value
Change the stored value of variable to value
Nothing for us to solve, computer just does the action
some_expression == other_expression
A test for equality
No binding is happening
Expressions are replaced by values and computer just does the
comparison
Replaces the entire line with True or False
30
6.100L Lecture 2 34
COMPARISON OPERATORS
i > j
i >= j
i < j
i <= j
i == j equality test, True if i is the same as j
i != j inequality test, True if i not the same as j
31
6.100L Lecture 2 35
LOGICAL OPERATORS on bool
A B A and B A or B
True True True True
True False False True
False True False True
False False False False
32
6.100L Lecture 2 36
COMPARISON EXAMPLE
pset_time = 15
sleep_time = 8
print(sleep_time > pset_time)
derive = True
drink = False
both = drink and derive
print(both)
pset_time 15
sleep_time 8
derive True
drink False
both False
33
6.100L Lecture 2 37
YOU TRY IT!
Write a program that
Saves a secret number in a variable.
Asks the user for a number guess.
Prints a bool False or True depending on whether the guess
matches the secret.
34
6.100L Lecture 2 38
WHY bool?
35
6.100L Lecture 2 40
INTERESTING ALGORITHMS
INVOLVE DECISIONS
It’s midnight
Free
food
email
36
6.100L Lecture 2 41
If right clear, If right blocked, If right and If right , front,
go right go forward front blocked, left blocked,
go left go back
37
6.100L Lecture 2 42
BRANCHING IN PYTHON
if <condition>:
<code>
<code>
...
<rest of program>
sion>
<expression>
...
else:
<expression>
<expression>
...
<rest of program>
6.100L Lecture 2 43
BRANCHING IN PYTHON
if <condition>:
<code>
<code>
...
<rest of program>
if <condition>:
<code>
<code>
...
else:
<code>
<code>
...
<rest of program>
6.100L Lecture 2 44
BRANCHING IN PYTHON
if <condition>: if <condition>:
<code> <code>
<code> <code>
... ...
<rest of program>
elif <condition>:
<code>
if <condition>: <code>
<code> ...
<code> elif <condition>:
... <code>
else: <code>
<code> ...
<code> <rest of program>
...
<rest of program>
6.100L Lecture 2 45
BRANCHING IN PYTHON
if <condition>: if <condition>: if <condition>:
<code> <code> <code>
<code> <code> <code>
... ... ...
<rest of program>
elif <condition>: elif <condition>:
<code> <code>
if <condition>: <code> <code>
<code> ... ...
<code> elif <condition>: else:
... <code> <code>
else: <code> <code>
<code> ... ...
<code> <rest of program> <rest of program>
...
<rest of program>
6.100L Lecture 2 46
BRANCHING EXAMPLE
pset_time = ???
sleep_time = ???
if (pset_time + sleep_time) > 24:
print("impossible!")
elif (pset_time + sleep_time) >= 24:
print("full schedule!")
else:
leftover = abs(24-pset_time-sleep_time)
print(leftover,"h of free time!")
print("end of day")
42
6.100L Lecture 2 47
YOU TRY IT!
Semantic structure matches visual structure
Fix this buggy code (hint, it has bad indentation)!
x = int(input("Enter a number for x: "))
y = int(input("Enter a different number for y: "))
if x == y:
print(x,"is the same as",y)
print("These are equal!")
43
6.100L Lecture 2 48
INDENTATION and NESTED
BRANCHING
Matters in Python
How you denote blocks of code
x = float(input("Enter a number for x: ")) 5 5 0
y = float(input("Enter a number for y: ")) 5 0 0
if x == y: True False True
print("x and y are equal") <- <-
if y != 0: True False
print("therefore, x / y is", x/y) <-
elif x < y: False
print("x is smaller")
else:
print("y is smaller") <-
print("thanks!") <- <- <-
44
6.100L Lecture 2 50
BIG IDEA
Practice will help you
build a mental model of
how to trace the code
Indentation does a lot of the work for you!
45
6.100L Lecture 2 51
YOU TRY IT!
What does this code print with
y=2
y = 20
y = 11
What if if x <= y: becomes elif x <= y: ?
answer = ''
x = 11
if x == y:
answer = answer + 'M'
if x >= y:
answer = answer + 'i'
else:
answer = answer + 'T'
print(answer)
46
6.100L Lecture 2 52
YOU TRY IT!
Write a program that
Saves a secret number.
Asks the user for a number guess.
Prints whether the guess is too low, too high, or the same as the secret.
47
6.100L Lecture 2 53
BIG IDEA
Debug early,
debug often.
Write a little and test a little.
Don’t write a complete program at once. It introduces too many errors.
Use the Python Tutor to step through code when you see something
unexpected!
48
6.100L Lecture 2 55
SUMMARY
6.100L Lecture 2 56
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
50
ITERATION
(download slides and .py files to follow along)
6.100L Lecture 3
Ana Bell
1
LAST LECTURE RECAP
6.100L Lecture 3
BRANCHING RECAP
if <condition>: if <condition>: if <condition>:
< code > < code > < code >
< code > < code > < code >
... ... ...
elif <condition>: elif <condition>:
if <condition>: < code > < code >
< code > < code > < code >
< code > ... ...
... elif <condition>: else:
else: < code > < code >
< code > < code > < code >
< code > ... ...
...
6.100L Lecture 3
If you keep going right, you are
stuck in the same spot forever
To exit, take a chance and go
Zelda, Lost Woods tricks you the opposite way
© Nintendo. All rights reserved. This content is excluded from our Creative
Commons license. For more information, see https://ocw.mit.edu/help/faq-fair-use/
if <exit right>:
<set background to woods_background>
if <exit right>:
<set background to woods_background>
if <exit right>:
<set background to woods_background>
and so on and on and on...
else:
<set background to exit_background>
else:
<set background to exit_background>
else:
<set background to exit_background>
4
6.100L Lecture 3
If you keep going right, you are
stuck in the same spot forever
To exit, take a chance and go
Zelda, Lost Woods tricks you the opposite way
© Nintendo. All rights reserved. This content is excluded from our Creative
Commons license. For more information, see https://ocw.mit.edu/help/faq-fair-use/
while <exit_right>:
<set background to woods_background>
<ask user which way to go>
<set background to exit_background>
6.100L Lecture 3
while LOOPS
6.100L Lecture 3
BINGE ALL EPISODES OF ONE SHOW
6.100L Lecture 3
CONTROL FLOW: while LOOPS
while <condition>:
<code>
<code>
...
<condition> evaluates to a Boolean
If <condition> is True, execute all the steps inside the
while code block
Check <condition> again
Repeat until <condition> is False
If <condition> is never False, then will loop forever!!
8
6.100L Lecture 3
while LOOP EXAMPLE
"left"
PROGRAM:
where = input("You're in the Lost Forest. Go left or right? ")
while where == "right":
where = input("You're in the Lost Forest. Go left or right? ")
print("You got out of the Lost Forest!")
6.100L Lecture 3
YOU TRY IT!
What is printed when you type "RIGHT"?
10
6.100L Lecture 3
while LOOP EXAMPLE
11
6.100L Lecture 3
while LOOP EXAMPLE
To terminate:
Hit CTRL-c or CMD-c in the shell
Click the red square in the shell
12
6.100L Lecture 3
YOU TRY IT!
Run this code and stop the infinite loop in your IDE
while True:
print("noooooo")
13
6.100L Lecture 3
BIG IDEA
while loops can repeat
code inside indefinitely!
Sometimes they need your intervention to end the program.
14
6.100L Lecture 3
YOU TRY IT!
Expand this code to show a sad face when the user entered the
while loop more than 2 times.
Hint: use a variable as a counter
where = input("Go left or right? ")
while where == "right":
where = input("Go left or right? ")
print("You got out!")
15
6.100L Lecture 3
CONTROL FLOW: while LOOPS
n = 0
while n < 5:
print(n)
n = n+1
16
6.100L Lecture 3
A COMMON PATTERN
Find 4!
i is our loop variable
factorial keeps track of the product
x = 4
i = 1
factorial = 1
while i <= x:
factorial *= i
i += 1
print(f'{x} factorial is {factorial}')
6.100L Lecture 3
for LOOPS
18
6.100L Lecture 3
ARE YOU STILL WATCHING?
Netflix while falling asleep
(it plays only 4 episodes if
you’re not paying attention)
6.100L Lecture 3
CONTROL FLOW:
while and for LOOPS
6.100L Lecture 3
STRUCTURE of for LOOPS
6.100L Lecture 3
A COMMON SEQUENCE of VALUES
for n in range(5):
print(n)
6.100L Lecture 3
A COMMON SEQUENCE of VALUES
2
for n in range(5): 3
print(n)
4
6.100L Lecture 3
range
24
6.100L Lecture 3
YOU TRY IT!
What do these print?
for i in range(1,4,1):
print(i)
for j in range(1,4,2):
print(j*2)
for me in range(4,0,-1):
print("$"*me)
25
6.100L Lecture 3
RUNNING SUM
mysum = 0 i 0
for i in range(10):
mysum += i
print(mysum)
mysum 0
26
6.100L Lecture 3
RUNNING SUM
mysum = 0 i 0
for i in range(10): 1
mysum += i
print(mysum)
mysum 0
1
27
6.100L Lecture 3
RUNNING SUM
mysum = 0 i 0
for i in range(10): 1
mysum += i 2
print(mysum)
mysum 1
3
28
6.100L Lecture 3
RUNNING SUM
mysum = 0 i 0
for i in range(10): 1
mysum += i 2
print(mysum) 3
mysum 3
6
29
6.100L Lecture 3
RUNNING SUM
mysum = 0 i 0
for i in range(10): 1
mysum += i 2
print(mysum)
…
3
mysum 36
45
30
6.100L Lecture 3
YOU TRY IT!
Fix this code to use variables start and end in the range, to get
the total sum between and including those values.
For example, if start=3 and end=5 then the sum should be 12.
mysum = 0
start = ??
end = ??
for i in range(start, end):
mysum += i
print(mysum)
31
6.100L Lecture 3
for LOOPS and range
x = 4
factorial = 1
for i in range(1, x+1, 1):
factorial *= i
print(f'{x} factorial is {factorial}')
32
6.100L Lecture 3
BIG IDEA
for loops only repeat
for however long the
sequence is
The loop variables takes on these values in order.
33
6.100L Lecture 3
SUMMARY
Looping mechanisms
while and for loops
Lots of syntax today, be sure to get lots of practice!
While loops
Loop as long as a condition is true
Need to make sure you don’t enter an infinite loop
For loops
Can loop over ranges of numbers
Can loop over elements of a string
Will soon see many other things are easy to loop over
34
6.100L Lecture 3
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
35
LOOPS OVER STRINGS,
GUESS-and-CHECK,
BINARY
(download slides and .py files to follow along)
6.100L Lecture 4
Ana Bell
1
LAST TIME
Looping mechanisms
while and for loops
While loops
Loop as long as a condition is true
Need to make sure you don’t enter an infinite loop
For loops
Loop variable takes on values in a sequence, one at a time
Can loop over ranges of numbers
Will soon see many other things are easy to loop over
6.100L Lecture 4
break STATEMENT
while <condition_1>:
while <condition_2>:
<expression_a>
break
<expression_b>
<expression_c>
3
6.100L Lecture 4
break STATEMENT
mysum = 0
for i in range(5, 11, 2):
mysum += i
if mysum == 5:
break
mysum += 1
print(mysum)
6.100L Lecture 4
YOU TRY IT!
Write code that loops a for loop over some range and prints
how many even numbers are in that range. Try it with:
range(5)
range(10)
range(2,9,3)
range(-4,6,2)
range(5,6)
6.100L Lecture 4
STRINGS and LOOPS
for char in s:
if char == 'i' or char == 'u':
print("There is an i or u")
for char in s:
if char in 'iu':
print("There is an i or u")
6
6.100L Lecture 4
BIG IDEA
The sequence of values
in a for loop isn’t
limited to numbers
6.100L Lecture 4
ROBOT CHEERLEADERS
6.100L Lecture 4
YOU TRY IT!
Assume you are given a string of lowercase letters in variable s.
Count how many unique letters there are in the string. For
example, if
s = "abca"
Then your code prints 3.
HINT:
Go through each character in s.
Keep track of ones you’ve seen in a string variable.
Add characters from s to the seen string variable if they are not already a character in
that seen variable.
6.100L Lecture 4
SUMMARY SO FAR
10
6.100L Lecture 4
THAT IS ALL YOU NEED TO
IMPLEMENT ALGORITHMS
11
6.100L Lecture 4
GUESS-and-CHECK
12
6.100L Lecture 4
GUESS-and-CHECK
done
13
6.100L Lecture 4
GUESS-and-CHECK
SQUARE ROOT
Basic idea:
Given an int, call it x, want to see if there is another int which is its
square root
Start with a guess and check if it is the right answer
0 1 2 3 4 5 6 7 8 9 10
14
6.100L Lecture 4
GUESS-and-CHECK
SQUARE ROOT
Basic idea:
Given an int, call it x, want to see if there is another int which is its
square root
Start with a guess and check if it is the right answer
To be systematic, start with guess = 0, then 1, then 2, etc
15
6.100L Lecture 4
GUESS-and-CHECK
SQUARE ROOT
Basic idea:
Given an int, call it x, want to see if there is another int which is its
square root
Start with a guess and check if it is the right answer
To be systematic, start with guess = 0, then 1, then 2, etc
If x is a perfect square, we will eventually find its root and can
stop (look at guess squared)
0 1 2 3 4 5 6 7 8 9 10
16
6.100L Lecture 4
GUESS-and-CHECK
SQUARE ROOT
Basic idea:
Given an int, call it x, want to see if there is another int which is its
square root
Start with a guess and check if it is the right answer
To be systematic, start with guess = 0, then 1, then 2, etc
But what if x is not a perfect square?
Need to know when to stop
Use algebra – if guess squared is bigger than x, then can stop
0 1 2 3 4 517 6 7 8 9 10
6.100L Lecture 4
GUESS-and-CHECK
SQUARE ROOT with while loop
guess = 0
x = int(input("Enter an integer: "))
while guess**2 < x:
guess = guess + 1
if guess**2 == x:
print("Square root of", x, "is", guess)
else:
print(x, "is not a perfect square")
18
6.100L Lecture 4
GUESS-and-CHECK
SQUARE ROOT
Does this work for any integer value of x?
What if x is negative?
while loop immediately terminates
Could check for negative input, and handle differently
x guess?
-2 -1 0 1 2 3 4 5 6 7 8
19
6.100L Lecture 4
GUESS-and-CHECK
SQUARE ROOT with while loop
guess = 0
neg_flag = False
x = int(input("Enter a positive integer: "))
if x < 0:
neg_flag = True
while guess**2 < x:
guess = guess + 1
if guess**2 == x:
print("Square root of", x, "is", guess)
else:
print(x, "is not a perfect square")
if neg_flag:
print("Just checking... did you mean", -x, "?")
20
6.100L Lecture 4
BIG IDEA
Guess-and-check can’t
test an infinite number
of values
You have to stop at some point!
21
6.100L Lecture 4
GUESS-and-CHECK COMPARED
while LOOP for LOOP
Initial guess Nothing here
6.100L Lecture 4
YOU TRY IT!
Hardcode a number as a secret number.
Write a program that checks through all the numbers from 1 to
10 and prints the secret value if it’s in that range. If it’s not
found, it doesn’t print anything.
23
6.100L Lecture 4
YOU TRY IT!
Compare the two codes that:
Hardcode a number as a secret number.
Checks through all the numbers from 1 to 10 and prints the secret value if
it’s in that range.
If it’s not found, it doesn’t print anything. If it’s not found, prints that it didn’t find it.
Answer: Answer:
secret = 7 secret = 7
found = False
for i in range(1,11): for i in range(1,11):
if i == secret: if i == secret:
print("yes, it's", i) print("yes, it's", i)
found = True
if not found:
print("not found")
24
6.100L Lecture 4
BIG IDEA
Booleans can be used as
signals that something
happened
We call them Boolean flags.
25
6.100L Lecture 4
while LOOP or for LOOP?
26
6.100L Lecture 4
GUESS-and-CHECK CUBE ROOT:
POSITIVE CUBES
cube = int(input("Enter an integer: "))
27
6.100L Lecture 4
GUESS-and-CHECK CUBE ROOT:
POSITIVE and NEGATIVE CUBES
cube = int(input("Enter an integer: "))
28
6.100L Lecture 4
GUESS-and-CHECK CUBE ROOT:
JUST a LITTLE FASTER
cube = int(input("Enter an integer: "))
for guess in range(abs(cube)+1):
if guess**3 >= abs(cube):
break
if guess**3 != abs(cube):
print(cube, "is not a perfect cube")
else:
if cube < 0:
guess = -guess
print("Cube root of "+str(cube)+" is "+str(guess))
29
6.100L Lecture 4
ANOTHER EXAMPLE
6.100L Lecture 4
GUESS-and-CHECK
with WORD PROBLEMS
31
6.100L Lecture 4
EXAMPLE WITH BIGGER
NUMBERS
6.100L Lecture 4
MORE EFFICIENT SOLUTION
33
6.100L Lecture 4
BIG IDEA
You can apply
computation to many
problems!
34
6.100L Lecture 4
BINARY NUMBERS
35
6.100L Lecture 4
NUMBERS in PYTHON
int
integers, like the ones you learned about in elementary school
float
reals, like the ones you learned about in middle school
36
6.100L Lecture 4
OUR MOTIVATION - keep this in
mind for the next few slides
x = 0
for i in range(10):
x += 0.1
print(x == 1)
print(x, '==', 10*0.1)
37
6.100L Lecture 4
BIG IDEA
Operations on some
floats introduces a very
small error.
The small error can have a big effect if operations are done
many times!
38
6.100L Lecture 4
A CLOSER LOOK AT FLOATS
39
6.100L Lecture 4
FLOATING POINT
REPRESENTATION
Depends on computer hardware, not programming language
implementation
Key things to understand
Numbers (and everything else) are represented as a sequence of bits (0
or 1).
When we write numbers down, the notation uses base 10.
0.1 stands for the rational number 1/10
This produces cognitive dissonance – and it will influence how we write
code
40
6.100L Lecture 4
WHY BINARY?
HARDWARE IMPLEMENTATION
Easy to implement in hardware—build components that can be
in one of two states
Computer hardware is built around methods that can efficiently
store information as 0’s or 1’s and do arithmetic with this rep
a voltage is “high” or “low” a magnetic spin is “up” or “down”
Fine for integer arithmetic, but what about numbers with
fractional parts (floats)?
41
6.100L Lecture 4
BINARY NUMBERS
42
6.100L Lecture 4
CONVERTING DECIMAL INTEGER
TO BINARY
We input integers in decimal, computer needs to convert to
binary
Consider example of
x = 1910 = 1*24 + 0*23 + 0*22 + 1*21 + 1*20 = 10011
If we take remainder of x relative to 2 (x%2), that gives us
the last binary bit
If we then integer divide x by 2 (x//2), all the bits get
shifted right
x//2 = 1*23 + 0*22 + 0*21 + 1*20 = 1001
Keep doing successive divisions; now remainder gets next bit,
and so on
Let’s convert to binary form
43
6.100L Lecture 4
DOING THIS in PYTHON for Python Tutor LINK
POSITIVE NUMBERS
result = ''
if num == 0:
result = '0'
while num > 0:
result = str(num%2) + result
num = num//2
44
6.100L Lecture 4
DOING this in PYTHON and
HANDLING NEGATIVE NUMBERS
if num < 0:
is_neg = True
num = abs(num)
else:
is_neg = False
result = ''
if num == 0:
result = '0'
while num > 0:
result = str(num%2) + result
num = num//2
if is_neg:
result = '-' + result
45
6.100L Lecture 4
SUMMARY
46
6.100L Lecture 4
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
47
FLOATS and
APPROXIMATION
METHODS
(download slides and .py files to follow along)
6.100L Lecture 5
Ana Bell
1
OUR MOTIVATION FROM LAST
LECTURE
x = 0
for i in range(10):
x += 0.1
print(x == 1)
print(x, '==', 10*0.1)
6.100L Lecture 5
INTEGERS
6.100L Lecture 4
FRACTIONS
6.100L Lecture 5
FRACTIONS
6.100L Lecture 5
WHAT ABOUT FRACTIONS?
6.100L Lecture 5
BUT…
6.100L Lecture 5
TRACE THROUGH THIS ON YOUR OWN
Python Tutor LINK
x =0.625
p = 0
while ((2**p)*x)%1 != 0:
print('Remainder = ' + str((2**p)*x - int((2**p)*x)))
p += 1
num = int(x*(2**p))
result = ''
if num == 0:
result = '0'
while num > 0:
result = str(num%2) + result
num = num//2
print('The binary representation of the decimal ' + str(x) + ' is ' + str(result))
8
6.100L Lecture 4
WHY is this a PROBLEM?
6.100L Lecture 5
THE POINT?
10
6.100L Lecture 5
FLOATS
11
6.100L Lecture 5
STORING FLOATING POINT NUMBERS
#.#
Floating point is a pair of integers
Significant digits and base 2 exponent
(1, 1) 1*21 102 2.0
(1, -1) 1*2-1 0.12 0.5
(125, -2) 125*2-2 11111.012 31.25
125 is 1111101 then move the decimal point over 2
12
6.100L Lecture 5
USE A FINITE SET OF BITS TO REPRESENT A
POTENTIALLY INFINITE SET OF BITS
The maximum number of significant digits governs the
precision with which numbers can be represented
Most modern computers use 32 bits to represent significant
digits
If a number is represented with more than 32 bits in binary, the
number will be rounded
Error will be at the 32nd bit
Error will only be on order of 2*10-10
13
6.100L Lecture 5
SURPRISING RESULTS!
x = 0 x = 0
for i in range(10): for i in range(10):
x += 0.125 x += 0.1
print(x == 1.25) print(x == 1)
14
6.100L Lecture 5
MORAL of the STORY
15
6.100L Lecture 5
APPROXIMATION
METHODS
16
6.100L Lecture 5
LAST LECTURE
17
6.100L Lecture 5
BETTER than GUESS-and-CHECK
18
6.100L Lecture 5
EFFECT of APPROXIMATION on
our ALGORITHMS?
19
6.100L Lecture 5
APPROXIMATE sqrt(x)
Good
guess? enough
x
-2 -1 0 1 2 3 4 5 6 7 8
20
6.100L Lecture 5
FINDING ROOTS
21
6.100L Lecture 5
APPROXIMATION
22
6.100L Lecture 5
APPROXIMATION ALGORITHM
-2 -1 0 1 2 3 4 5 6 7 8
23
epsilon epsilon
6.100L Lecture 5
APPROXIMATION ALGORITHM
-2 -1 0 1 2 3 4 5 6 7 8
24 epsilon epsilon
6.100L Lecture 5
BIG IDEA
Approximation is like
guess-and-check
except…
1) We increment by some small amount
2) We stop when close enough (exact is not possible)
25
6.100L Lecture 5
IMPLEMENTATION
x = 36
epsilon = 0.01
num_guesses = 0
guess = 0.0
increment = 0.0001
26
6.100L Lecture 5
OBSERVATIONS with DIFFERENT
VALUES for x
For x = 36
Didn’t find 6
Took about 60,000 guesses
Let’s try:
24
2
12345
54321
27
6.100L Lecture 5
x = 54321
epsilon = 0.01
numGuesses = 0
guess = 0.0
increment = 0.0001
6.100L Lecture 5
WE OVERSHOT the EPSILON!
x = 54321
epsilon epsilon
29
6.100L Lecture 5
SOME OBSERVATIONS
30
6.100L Lecture 5
LET’S FIX IT
x = 54321
epsilon = 0.01
numGuesses = 0
guess = 0.0
increment = 0.0001
while abs(guess**2 - x) >= epsilon and guess**2 <= x:
guess += increment
numGuesses += 1
print('numGuesses =', numGuesses)
if abs(guess**2 - x) >= epsilon:
print('Failed on square root of', x)
else:
print(guess, 'is close to square root of', x)
31
6.100L Lecture 5
BIG IDEA
It’s possible to overshoot
the epsilon, so you need
another end condition
32
6.100L Lecture 5
SOME OBSERVATIONS
33
6.100L Lecture 5
BIG IDEA
Be careful when
comparing floats.
34
6.100L Lecture 5
LESSONS LEARNED in
APPROXIMATION
Can’t use == to check an exit condition
Need to be careful that looping mechanism doesn’t jump over
exit test and loop forever
Tradeoff exists between efficiency of algorithm and accuracy of
result
Need to think about how close an answer we want when
setting parameters of algorithm
To get a good answer, this method can be painfully slow.
Is there a faster way that still gets good answers?
YES! We will see it next lecture….
35
6.100L Lecture 5
SUMMARY
36
6.100L Lecture 5
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
37
FLOATS and
APPROXIMATION
METHODS
(download slides and .py files to follow along)
6.100L Lecture 5
Ana Bell
1
OUR MOTIVATION FROM LAST
LECTURE
x = 0
for i in range(10):
x += 0.1
print(x == 1)
print(x, '==', 10*0.1)
6.100L Lecture 5
INTEGERS
6.100L Lecture 4
FRACTIONS
6.100L Lecture 5
FRACTIONS
6.100L Lecture 5
WHAT ABOUT FRACTIONS?
6.100L Lecture 5
BUT…
6.100L Lecture 5
TRACE THROUGH THIS ON YOUR OWN
Python Tutor LINK
x =0.625
p = 0
while ((2**p)*x)%1 != 0:
print('Remainder = ' + str((2**p)*x - int((2**p)*x)))
p += 1
num = int(x*(2**p))
result = ''
if num == 0:
result = '0'
while num > 0:
result = str(num%2) + result
num = num//2
print('The binary representation of the decimal ' + str(x) + ' is ' + str(result))
8
6.100L Lecture 4
WHY is this a PROBLEM?
6.100L Lecture 5
THE POINT?
10
6.100L Lecture 5
FLOATS
11
6.100L Lecture 5
STORING FLOATING POINT NUMBERS
#.#
Floating point is a pair of integers
Significant digits and base 2 exponent
(1, 1) 1*21 102 2.0
(1, -1) 1*2-1 0.12 0.5
(125, -2) 125*2-2 11111.012 31.25
125 is 1111101 then move the decimal point over 2
12
6.100L Lecture 5
USE A FINITE SET OF BITS TO REPRESENT A
POTENTIALLY INFINITE SET OF BITS
The maximum number of significant digits governs the
precision with which numbers can be represented
Most modern computers use 32 bits to represent significant
digits
If a number is represented with more than 32 bits in binary, the
number will be rounded
Error will be at the 32nd bit
Error will only be on order of 2*10-10
13
6.100L Lecture 5
SURPRISING RESULTS!
x = 0 x = 0
for i in range(10): for i in range(10):
x += 0.125 x += 0.1
print(x == 1.25) print(x == 1)
14
6.100L Lecture 5
MORAL of the STORY
15
6.100L Lecture 5
APPROXIMATION
METHODS
16
6.100L Lecture 5
LAST LECTURE
17
6.100L Lecture 5
BETTER than GUESS-and-CHECK
18
6.100L Lecture 5
EFFECT of APPROXIMATION on
our ALGORITHMS?
19
6.100L Lecture 5
APPROXIMATE sqrt(x)
Good
guess? enough
x
-2 -1 0 1 2 3 4 5 6 7 8
20
6.100L Lecture 5
FINDING ROOTS
21
6.100L Lecture 5
APPROXIMATION
22
6.100L Lecture 5
APPROXIMATION ALGORITHM
-2 -1 0 1 2 3 4 5 6 7 8
23
epsilon epsilon
6.100L Lecture 5
APPROXIMATION ALGORITHM
-2 -1 0 1 2 3 4 5 6 7 8
24 epsilon epsilon
6.100L Lecture 5
BIG IDEA
Approximation is like
guess-and-check
except…
1) We increment by some small amount
2) We stop when close enough (exact is not possible)
25
6.100L Lecture 5
IMPLEMENTATION
x = 36
epsilon = 0.01
num_guesses = 0
guess = 0.0
increment = 0.0001
26
6.100L Lecture 5
OBSERVATIONS with DIFFERENT
VALUES for x
For x = 36
Didn’t find 6
Took about 60,000 guesses
Let’s try:
24
2
12345
54321
27
6.100L Lecture 5
x = 54321
epsilon = 0.01
numGuesses = 0
guess = 0.0
increment = 0.0001
6.100L Lecture 5
WE OVERSHOT the EPSILON!
x = 54321
epsilon epsilon
29
6.100L Lecture 5
SOME OBSERVATIONS
30
6.100L Lecture 5
LET’S FIX IT
x = 54321
epsilon = 0.01
numGuesses = 0
guess = 0.0
increment = 0.0001
while abs(guess**2 - x) >= epsilon and guess**2 <= x:
guess += increment
numGuesses += 1
print('numGuesses =', numGuesses)
if abs(guess**2 - x) >= epsilon:
print('Failed on square root of', x)
else:
print(guess, 'is close to square root of', x)
31
6.100L Lecture 5
BIG IDEA
It’s possible to overshoot
the epsilon, so you need
another end condition
32
6.100L Lecture 5
SOME OBSERVATIONS
33
6.100L Lecture 5
BIG IDEA
Be careful when
comparing floats.
34
6.100L Lecture 5
LESSONS LEARNED in
APPROXIMATION
Can’t use == to check an exit condition
Need to be careful that looping mechanism doesn’t jump over
exit test and loop forever
Tradeoff exists between efficiency of algorithm and accuracy of
result
Need to think about how close an answer we want when
setting parameters of algorithm
To get a good answer, this method can be painfully slow.
Is there a faster way that still gets good answers?
YES! We will see it next lecture….
35
6.100L Lecture 5
SUMMARY
36
6.100L Lecture 5
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
37
BISECTION SEARCH
(download slides and .py files to follow along)
6.100L Lecture 6
Ana Bell
1
LAST LECTURE
6.100L Lecture 6
RECAP: SQUARE ROOT FINDING:
STOPPING CONDITION with a BIG INCREMENT (0.01)
x = 54321
epsilon epsilon
6.100L Lecture 6
RECAP of APPROXIMATION METHOD TO
FIND A “close enough” SQUARE ROOT
x = 54321
epsilon = 0.01
num_guesses = 0
guess = 0.0
increment = 0.0001
while abs(guess**2 - x) >= epsilon and guess**2 <= x:
guess += increment
num_guesses += 1
print('num_guesses =', num_guesses)
if abs(guess**2 - x) >= epsilon:
print('Failed on square root of', x)
else:
print(guess, 'is close to square root of', x)
6.100L Lecture 6
BISECTION SEARCH
6.100L Lecture 6
CHANCE to WIN BIG BUCKS
Suppose I attach a hundred dollar bill to a particular page in the text book,
448 pages long
If you can guess page in 8 or fewer guesses, you get big bucks
If you fail, you get an F
Would you want to play?
Now suppose on each guess I told you whether you were correct, or too low
or too high
Would you want to play in this case?
6.100L Lecture 6
BISECTION SEARCH
6.100L Lecture 6
LOG GROWTH is BETTER
6.100L Lecture 6
AN ANALOGY
6.100L Lecture 6
BISECTION SEARCH for SQUARE
ROOT
Suppose we know that the answer lies between 0 and x
Rather than exhaustively trying things starting at 0, suppose
instead we pick a number in the middle of this range
0 x
g
10
6.100L Lecture 6
BISECTION SEARCH for SQUARE
ROOT
If not close enough, is guess too big or too small?
If g**2 > x, then know g is too big; so now search
0 x
new g g
11
6.100L Lecture 6
BISECTION SEARCH for SQUARE
ROOT
And if, for example, this new g is such that g**2 < x, then know
too small; so now search
0 x
new g next g g
12
6.100L Lecture 6
BISECTION SEARCH for SQUARE
ROOT
And if, for example, this next g is such that g**2 < x, then know
too small; so now search
0 x
next g g
latest g
At each stage, reduce range of values to search by half
13
6.100L Lecture 6
BIG IDEA
Bisection search takes advantage
of properties of the problem.
1) The search space has an order
2) We can tell whether the guess was too low or too high
14
6.100L Lecture 6
YOU TRY IT!
You are guessing a 4 digit pin code. The only feedback the
phone tells you is whether your guess is correct or not. Can you
use bisection search to quickly and correctly guess the code?
15
6.100L Lecture 6
YOU TRY IT!
You are playing an EXTREME guessing game to guess a number
EXACTLY. A friend has a decimal number between 0 and 10 (to
any precision) in mind. The feedback on your guess is whether
it is correct, too high, or too low. Can you use bisection search
to quickly and correctly guess the number?
16
6.100L Lecture 6
SLOW SQUARE ROOT USING
APPROXIMATION METHODS
x = 54321
epsilon = 0.01
num_guesses = 0
guess = 0.0
increment = 0.00001
while abs(guess**2 - x) >= epsilon and guess**2 <= x:
guess += increment
num_guesses += 1
print('num_guesses =', num_guesses)
if abs(guess**2 - x) >= epsilon:
print('Failed on square root of', x)
else:
print(guess, 'is close to square root of', x)
17
6.100L Lecture 6
FAST SQUARE ROOT
x = 54321
epsilon = 0.01
num_guesses = 0
num_guesses += 1
print('num_guesses =', num_guesses)
print(guess, 'is close to square root of', x)
18
6.100L Lecture 6
FAST SQUARE ROOT
x = 54321
epsilon = 0.01
num_guesses = 0
low = 0
high = x
guess = (high + low)/2.0
while abs(guess**2 - x) >= epsilon:
num_guesses += 1
print('num_guesses =', num_guesses)
print(guess, 'is close to square root of', x)
19
6.100L Lecture 6
FAST SQUARE ROOT
x = 54321
epsilon = 0.01
num_guesses = 0
low = 0
high = x
guess = (high + low)/2.0
while abs(guess**2 - x) >= epsilon:
if guess**2 < x :
else:
num_guesses += 1
print('num_guesses =', num_guesses)
print(guess, 'is close to square root of', x)
20
6.100L Lecture 6
FAST SQUARE ROOT
x = 54321
epsilon = 0.01
num_guesses = 0
low = 0
high = x
guess = (high + low)/2.0
while abs(guess**2 - x) >= epsilon:
if guess**2 < x :
low = guess
else:
num_guesses += 1
print('num_guesses =', num_guesses)
print(guess, 'is close to square root of', x)
21
6.100L Lecture 6
FAST SQUARE ROOT
x = 54321
epsilon = 0.01
num_guesses = 0
low = 0
high = x
guess = (high + low)/2.0
while abs(guess**2 - x) >= epsilon:
if guess**2 < x :
low = guess
else:
high = guess
num_guesses += 1
print('num_guesses =', num_guesses)
print(guess, 'is close to square root of', x)
22
6.100L Lecture 6
FAST SQUARE ROOT
Python Tutor LINK
x = 54321
epsilon = 0.01
num_guesses = 0
low = 0
high = x
guess = (high + low)/2.0
while abs(guess**2 - x) >= epsilon:
if guess**2 < x :
low = guess
else:
high = guess
guess = (high + low)/2.0
num_guesses += 1
print('num_guesses =', num_guesses)
print(guess, 'is close to square root of', x)
23
6.100L Lecture 6
LOG GROWTH is BETTER
Brute force search for root of 54321 took over 23M guesses
With bisection search, reduced to 30 guesses!
We’ll spend more time on this later, but we say the brute force
method is linear in size of problem, because number to steps
grows linearly as we increase problem size
Bisection search is logarithmic in size of problem, because
number of steps grows logarithmically with problem size
search space
first guess: N/2
second guess: N/4
kth guess: N/2k
guess converges on the order of log2N steps
24
6.100L Lecture 6
WHY?
6.100L Lecture 6
DOES IT ALWAYS WORK?
26
6.100L Lecture 6
You Try It: BISECTION SEARCH –
SQUARE ROOT with 0 < x < 1
x = 0.5
epsilon = 0.01
if x >= 1:
low = 1.0
high = x
else:
low = x
high = 1.0
guess = (high + low)/2
29
6.100L Lecture 6
YOU TRY IT!
Write code to do bisection search to find the cube root of
positive cubes within some epsilon. Start with:
cube = 27
epsilon = 0.01
low = 0
high = cube
30
6.100L Lecture 6
NEWTON-RAPHSON
6.100L Lecture 6
INTUITION - LINK
32
6.100L Lecture 6
NEWTON-RAPHSON ROOT FINDER
33
6.100L Lecture 6
NEWTON-RAPHSON ROOT FINDER
epsilon = 0.01
k = 24.0
guess = k/2.0
num_guesses = 0
6.100L Lecture 6
ITERATIVE ALGORITHMS
35
6.100L Lecture 6
SUMMARY
36
6.100L Lecture 6
DECOMPOSITION and
ABSTRACTION
37
6.100L Lecture 6
LEARNING to CREATE CODE
But in fact, we’ve taught you nothing about two of the most
important concepts in programming…
38
6.s061 Lecture 7
DECOMPOSITION and
ABSTRACTION
Decomposition
How to divide a program into self-contained parts that can be
combined to solve the current problem
39
6.s061 Lecture 7
DECOMPOSITION and
ABSTRACTION
Abstraction
How to ignore unnecessary detail
40
6.s061 Lecture 7
DECOMPOSITION and
ABSTRACTION
Decomposition:
Ideally parts can be reused by other programs
Self-contained means parts should complete computation using only
inputs provided to them and “basic” operations
a = 3.14*2.2*2.2 pi = 3.14
r = 2.2
area = pi*r**2
Abstraction:
Used to separate what something does, from how it actually does it
Creating parts and abstracting away details allows us to write complex
code while suppressing details, so that we are not overwhelmed by
that complexity
# calculate the area of a circle
41
6.s061 Lecture 7
BIG IDEA
Make code easy to
create
modify
maintain
understand
42
6.s061 Lecture 7
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
43
DECOMPOSITION,
ABSTRACTION, FUNCTIONS
(download slides and .py files to follow along)
6.100L Lecture 7
Ana Bell
1
AN EXAMPLE: the SMARTPHONE
6.100L Lecture 7
AN EXAMPLE: the SMARTPHONE
ABSTRACTION
User doesn’t know the details of how it
works
We don’t need to know how something works in
order to know how to use it
User does know the interface
Device converts a sequence of screen touches and
sounds into expected useful functionality
Know relationship between input and output
6.100L Lecture 7
ABSTRACTION ENABLES
DECOMPOSITION
100’s of distinct parts
Designed and made by different
companies
Do not communicate with each other,
other than specifications for components
May use same subparts as others
Each component maker has to know
how its component interfaces to other
components
Each component maker can solve sub-
problems independent of other parts,
so long as they provide specified inputs
True for hardware and for software 4
6.100L Lecture 7
BIG IDEA
Apply
abstraction (black box) and
decomposition (split into self-contained parts)
to programming!
6.100L Lecture 7
SUPPRESS DETAILS with
ABSTRACTION
In programming, want to think of piece of code as black box
Hide tedious coding details from the user
Reuse black box at different parts in the code (no copy/pasting!)
Coder creates details, and designs interface
User does not need or want to see details
6.100L Lecture 7
SUPPRESS DETAILS with
ABSTRACTION
Coder achieves abstraction with a function (or procedure)
You’ve already been using functions!
A function lets us capture code within a black box
Once we create function, it will produce an output from inputs, while
hiding details of how it does the computation
max(1,4)
abs(-3)
len("mom's spaghetti")
6.100L Lecture 7
SUPPRESS DETAILS with
ABSTRACTION
A function has specifications, captured using docstrings
Think of a docstring as “contract” between coder and user:
If user provides input that satisfies stated conditions, function will
produce output according to specs, including indicated side effects
Not typically enforced in Python (we’ll see assertions later), but user
relies on coder’s work satisfying the contract
abs(-3)
6.100L Lecture 7
CREATE STRUCTURE with
DECOMPOSITION
Given the idea of black box abstraction, use it to divide code
into modules that are:
Self-contained
Intended to be reusable
Modules are used to:
Break up code into logical pieces
Keep code organized
Keep code coherent (readable and understandable)
In this lecture, achieve decomposition with functions
In a few lectures, achieve decomposition with classes
Decomposition relies on abstraction to enable construction of
complex modules from simpler ones
9
6.100L Lecture 7
FUNCTIONS
10
6.100L Lecture 7
FUNCTIONS
11
6.100L Lecture 7
FUNCTION CHARACTERISTICS
Has a name
(think: variable bound to a function object)
Has (formal) parameters (0 or more)
The inputs
Has a docstring (optional but recommended)
A comment delineated by """ (triple quotes) that provides a
specification for the function – contract relating output to input
Has a body, a set of instructions to execute when function is
called
Returns something
Keyword return
12
6.100L Lecture 7
HOW to WRITE a FUNCTION
def is_even( i ):
"""
Input: i, a positive int
Returns True if i is even, otherwise False
"""
if i%2 == 0:
return True
else:
return False
13
6.100L Lecture 7
HOW TO THINK ABOUT WRITING
A FUNCTION
What is the problem?
Given an int, call it i, want to know if it is even
Use this to write the function name and specs
def is_even( i ):
"""
Input: i, a positive int
Returns True if i is even, otherwise False
"""
14
6.100L Lecture 7
HOW TO THINK ABOUT WRITING
A FUNCTION
How to solve the problem?
Can check that remainder when divided by 2 is 0
Think about what value you need to give back
def is_even( i ):
"""
Input: i, a positive int
Returns True if i is even, otherwise False
"""
if i%2 == 0:
return True
else:
return False
15
6.100L Lecture 7
HOW TO THINK ABOUT WRITING
A FUNCTION
Can you make the code cleaner?
i%2 is a Boolean that evaluates to True/False already
def is_even( i ):
"""
Input: i, a positive int
Returns True if i is even, otherwise False
"""
return i%2 == 0
16
6.100L Lecture 7
BIG IDEA
At this point, all we’ve
done is make a function
object
17
6.100L Lecture 7
HOW TO CALL (INVOKE) A
FUNCTION
is_even(3)
is_even(8)
That’s all!
18
6.100L Lecture 7
HOW TO CALL (INVOKE) A
FUNCTION
is_even(3)
is_even(8)
That’s all!
19
6.100L Lecture 7
ALL TOGETHER IN A FILE
def is_even( i ):
return i%2 == 0
is_even(3)
20
6.100L Lecture 7
WHAT HAPPENS when you CALL a
FUNCTION?
Python replaces:
formal parameters in function def with values from function call
i replaced with 3
def is_even( i ):
return i%2 == 0
is_even(3)
21
6.100L Lecture 7
WHAT HAPPENS when you CALL a
FUNCTION?
Python replaces:
formal parameters in function def with values from function call
i replaced with 3
Python executes expressions in the body of the function
return 3%2 == 0
def is_even( i ):
return i%2 == 0
is_even(3)
22
6.100L Lecture 7
WHAT HAPPENS when you CALL a
FUNCTION?
Python replaces:
formal parameters in function def with values from function call
i replaced with 3
def is_even( i ):
return i%2 == 0
is_even(3)
print(is_even(3))
23
6.100L Lecture 7
BIG IDEA
A function’s code
only runs when you
call (aka invoke) the function
24
6.100L Lecture 7
YOU TRY IT!
Write code that satisfies the following specs
def div_by(n, d):
""" n and d are ints > 0
Returns True if d divides n evenly and False otherwise """
25
6.100L Lecture 7
ZOOMING OUT
(no functions)
a = 3 Program Scope
b = 4 3
a
c = a+b
b 4
c 7
26
6.100L Lecture 7
ZOOMING OUT
a = is_even(3)
b = is_even(10)
c = is_even(123456)
This is me telling my black box to do
something
27
6.100L Lecture 7
ZOOMING OUT
a = is_even(3)
b = is_even(10)
c = is_even(123456)
One function call
28
6.100L Lecture 7
ZOOMING OUT
b True
a = is_even(3)
b = is_even(10)
c = is_even(123456)
6.100L Lecture 7
ZOOMING OUT
b True
a = is_even(3)
b = is_even(10) c True
c = is_even(123456)
6.100L Lecture 7
INSERTING FUNCTIONS IN CODE
for i in range(1,10):
if is_even(i):
print(i, "even")
else:
print(i, "odd")
31
6.100L Lecture 7
ANOTHER EXAMPLE
32
6.100L Lecture 7
BIG IDEA
Don’t write code right
away!
33
6.100L Lecture 7
PAPER FIRST
34
6.100L Lecture 7
SIMPLE TEST CASE
2 3 4
a b 35
6.100L Lecture 7
MORE COMPLEX TEST CASE
2 3 4 5 6 7
a b 36
6.100L Lecture 7
2 3 4
SOLVE SIMILAR PROBLEM
a b
37
6.100L Lecture 7
2 3 4
CHOOSE BIG-PICTURE STRUCTURE
a b
38
6.100L Lecture 7
WRITE the LOOP 2 3 4
(for adding all numbers)
a b
39
6.100L Lecture 7
DO the SUMMING 2 3 4
(for adding all numbers)
a b
40
6.100L Lecture 7
INITIALIZE the SUM 2 3 4
(for adding all numbers)
a b
41
6.100L Lecture 7
TEST! 2 3 4
(for adding all numbers)
a b
print(sum_odd(2,4))
print(sum_odd(2,4))
42
6.100L Lecture 7
WEIRD RESULTS… 2 3 4
(for adding all numbers)
a b
print(sum_odd(2,4))
print(sum_odd(2,4)) 9
5
43
6.100L Lecture 7
DEBUG! aka ADD PRINT STATEMENTS 2 3 4
(for adding all numbers)
a b
6.100L Lecture 7
FIX for LOOP END INDEX 2 3 4
(for adding all numbers)
a b
6.100L Lecture 7
2 3 4
ADD IN THE ODD PART!
a b
6.100L Lecture 7
BIG IDEA
Solve a simpler problem
first.
Add functionality to the code later.
47
6.100L Lecture 7
TRY IT ON ANOTHER 2 3 4 5 6 7
EXAMPLE
a b
6.100L Lecture 7
PYTHON TUTOR
49
6.100L Lecture 7
BIG IDEA
Test code often.
Use prints to debug.
50
6.100L Lecture 7
YOU TRY IT!
Write code that satisfies the following specs
def is_palindrome(s):
""" s is a string
Returns True if s is a palindrome and False otherwise
"""
For example:
If s = "222" returns True
If s = "2222" returns True
If s = "abc" returns False
51
6.100L Lecture 7
SUMMARY
52
6.100L Lecture 7
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
53
FUNCTIONS as OBJECTS
(download slides and .py files to follow along)
6.100L Lecture 8
Ana Bell
1
FUNCTION FROM LAST LECTURE
def is_even( i ):
"""
Input: i, a positive int
Returns True if i is even and False otherwise
"""
return i%2 == 0
6.100L Lecture 8
WHAT IF THERE IS
NO return KEYWORD
def is_even( i ):
"""
Input: i, a positive int
Does not return anything
"""
i%2 == 0
6.100L Lecture 8
def is_even( i ):
"""
Input: i, a positive int
Does not return anything
"""
i%2 == 0
return None
6.100L Lecture 8
YOU TRY IT!
What is printed if you run this code as a file?
def add(x,y):
return x+y
def mult(x,y):
print(x*y)
add(1,2)
print(add(2,3))
mult(3,4)
print(mult(4,5))
6.100L Lecture 8
return vs. print
6.100L Lecture 8
YOU TRY IT!
Fix the code that tries to write this function
def is_triangular(n):
""" n is an int > 0
Returns True if n is triangular, i.e. equals a continued
summation of natural numbers (1+2+3+...+k), False otherwise """
total = 0
for i in range(n):
total += i
if total == n:
print(True)
print(False)
6.100L Lecture 8
FUNCTIONS SUPPORT
MODULARITY
Here is our bisection square root method as a function
def bisection_root(x):
epsilon = 0.01
low = 0
Initialize variables
high = x
ans = (high + low)/2.0
guess not close enough
while abs(ans**2 - x) >= epsilon:
if ans**2 < x:
iterate update low or high,
low = ans depends on guess too
else: small or too large
high = ans
ans = (high + low)/2.0 new value for guess
# print(ans, 'is close to the root of', x)
return ans return result
6.100L Lecture 8
FUNCTIONS SUPPORT
MODULARITY
Call it with different values
print(bisection_root(4))
print(bisection_root(123))
6.100L Lecture 8
YOU TRY IT!
Write a function that satisfies the following specs
def count_nums_with_sqrt_close_to (n, epsilon):
""" n is an int > 2
epsilon is a positive number < 1
Returns how many integers have a square root within epsilon of n """
10
6.100L Lecture 8
ZOOMING OUT
11
6.100L Lecture 8
ZOOMING OUT
12
6.100L Lecture 8
ZOOMING OUT
15
13
6.100L Lecture 8
FUNCTION SCOPE
14
6.100L Lecture 8
UNDERSTANDING FUNCTION
CALLS
15
6.100L Lecture 8
ENVIRONMENTS
Global environment
Where user interacts with Python interpreter
Where the program starts out
Invoking a function creates a new environment (frame/scope)
16
6.100L Lecture 8
VARIABLE SCOPE
xy = 3
z = f( y
x )
17
6.100L Lecture 8
VARIABLE SCOPE
after evaluating def
x = 3
z = f( x )
18
6.100L Lecture 8
VARIABLE SCOPE
after exec 1st assignment
6.100L Lecture 8
VARIABLE SCOPE
after f invoked
6.100L Lecture 8
VARIABLE SCOPE
after f invoked
6.100L Lecture 8
VARIABLE SCOPE
eval body of f in f’s scope
6.100L Lecture 8
VARIABLE SCOPE
during return
6.100L Lecture 8
VARIABLE SCOPE
after exec 2nd assignment
6.100L Lecture 8
BIG IDEA
You need to know what
expression you are executing
to know the scope you are in.
25
6.100L Lecture 8
ANOTHER SCOPE EXAMPLE
26
6.100L Lecture 8
FUNCTIONS as
ARGUMENTS
27
6.100L Lecture 8
HIGHER ORDER PROCEDURES
28
6.100L Lecture 8
OBJECTS IN A PROGRAM
function
my_func object with
some code
is_even
pi = 22/7
a False
my_func = is_even
b True
a = is_even(3)
b = my_func(4)
29
6.100L Lecture 8
BIG IDEA
Everything in Python is
an object.
30
6.100L Lecture 8
FUNCTION AS A PARAMETER
def add(a,b):
return a+b
def div(a,b):
if b != 0:
return a/b
print("Denominator was 0.")
print(calc(add, 2, 3))
31
6.100L Lecture 8
STEP THROUGH THE CODE
res
32
6.100L Lecture 8
CREATE calc SCOPE
res
33
6.100L Lecture 8
MATCH FORMAL PARAMS in calc
res
34
6.100L Lecture 8
FIRST (and only) LINE IN calc
res
35
6.100L Lecture 8
CREATE SCOPE OF add
res
36
6.100L Lecture 8
MATCH FORMAL PARAMS IN add
res
37
6.100L Lecture 8
EXECUTE LINE OF add
res
returns 5
38
6.100L Lecture 8
REPLACE FUNC CALL WITH RETURN
res
39
6.100L Lecture 8
EXECUTE LINE OF calc
res
returns 5
40
6.100L Lecture 8
REPLACE FUNC CALL WITH RETURN
res 5
41
6.100L Lecture 8
YOU TRY IT!
Do a similar trace with the function call
def calc(op, x, y):
return op(x,y)
def div(a,b):
if b != 0:
return a/b
print("Denom was 0.")
res = calc(div,2,0)
42
6.100L Lecture 8
ANOTHER EXAMPLE:
FUNCTIONS AS PARAMS
def func_a():
print('inside func_a')
def func_b(y):
print('inside func_b')
return y
def func_c(f, z):
print('inside func_c')
return f(z)
print(func_a())
print(5 + func_b(2))
print(func_c(func_b, 3))
43
6.100L Lecture 8
FUNCTIONS AS PARAMETERS
print('inside func_c')
return f(z)
print(func_a())
print(5 + func_b(2))
print(func_c(func_b, 3))
44
6.100L Lecture 8
FUNCTIONS AS PARAMETERS
6.100L Lecture 8
FUNCTIONS AS PARAMETERS
Global scope
def func_a(): Some
func_a
print('inside func_a') code
def func_b(y): Some
func_b code
print('inside func_b')
return y Some
def func_c(f, z): func_c code
print('inside func_c')
return f(z)
print(func_a())
print(5 + func_b(2))
print(func_c(func_b, 3))
46
6.100L Lecture 8
FUNCTIONS AS PARAMETERS
6.100L Lecture 8
FUNCTIONS AS PARAMETERS
6.100L Lecture 8
FUNCTIONS AS PARAMETERS
6.100L Lecture 8
FUNCTIONS AS PARAMETERS
Global scope
def func_a(): Some
func_a
print('inside func_a') code
def func_b(y): Some
func_b code
print('inside func_b')
return y Some
func_c code
def func_c(f, z):
print('inside func_c') None
return f(z)
print(func_a()) 7
print(5 + func_b(2))
print(func_c(func_b, 3))
50
6.100L Lecture 8
FUNCTIONS AS PARAMETERS
6.100L Lecture 8
FUNCTIONS AS PARAMETERS
6.100L Lecture 8
FUNCTIONS AS PARAMETERS
54
6.100L Lecture 8
SUMMARY
55
6.100L Lecture 8
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
56
LAMBDA FUNCTIONS,
TUPLES and LISTS
(download slides and .py files to follow along)
6.100L Lecture 9
Ana Bell
1
FROM LAST TIME
def apply(criteria,n):
"""
* criteria: function that takes in a number and returns a bool
* n: an int
Returns how many ints from 0 to n (inclusive) match the
criteria (i.e. return True when run with criteria) """
count = 0
for i in range(n+1):
if criteria(i):
count += 1
return count
def is_even(x):
return x%2==0
print(apply(is_even,10))
6.100L Lecture 9
ANONYMOUS FUNCTIONS
lambda x: x%2 == 0
Body of lambda
parameter Note no return keyword
6.100L Lecture 9
ANONYMOUS FUNCTIONS
apply( is_even , 10 )
6.100L Lecture 9
YOU TRY IT!
What does this print?
6.100L Lecture 9
YOU TRY IT!
What does this print?
Global environment
6.100L Lecture 9
YOU TRY IT!
What does this print?
6.100L Lecture 9
YOU TRY IT!
What does this print?
6.100L Lecture 9
YOU TRY IT!
What does this print?
lambda x: x**2
environment
x 3
9
6.100L Lecture 9
YOU TRY IT!
What does this print?
lambda x: x**2
environment
x 3
10
Returns 9
6.100L Lecture 9
YOU TRY IT!
What does this print?
11
6.100L Lecture 9
YOU TRY IT!
What does this print?
12
6.100L Lecture 9
TUPLES
13
6.100L Lecture 9
A NEW DATA TYPE
14
6.100L Lecture 9
TUPLES
t = (2, "mit", 3)
t[0] evaluates to 2
(2,"mit",3) + (5,6)evaluates to a new tuple(2,"mit",3,5,6)
t[1:2] slice tuple, evaluates to ("mit",)
t[1:3] slice tuple, evaluates to ("mit",3)
len(t) evaluates to 3
max((3,5,0)) evaluates 5
t[1] = 4 gives error, can’t modify object
15
6.100L Lecture 9
INDICES AND SLICING
seq = (2,'a',4,(1,2))
index: 0 1 2 3
print(len(seq)) 4
print(seq[3]) (1,2)
print(seq[-1]) (1,2)
print(seq[3][0]) 1
print(seq[4]) error
print(seq[1]) 'a'
print(seq[-2:] (4,(1,2))
print(seq[1:4:2] ('a',(1,2))
print(seq[:-1]) (2,'a',4)
print(seq[1:3]) ('a',4)
for e in seq: 2
print(e) a
4
(1,2) 16
6.100L Lecture 9
TUPLES
17
6.100L Lecture 9
TUPLES
both = quotient_and_remainder(10,3)
18
6.100L Lecture 9
BIG IDEA
Returning
one object (a tuple)
allows you to return
multiple values (tuple elements)
19
6.100L Lecture 9
YOU TRY IT!
Write a function that meets these specs:
Hint: remember how to check if a character is in a string?
def char_counts(s):
""" s is a string of lowercase chars
Return a tuple where the first element is the
number of vowels in s and the second element
is the number of consonants in s """
20
6.100L Lecture 9
VARIABLE NUMBER of
ARGUMENTS
6.100L Lecture 9
LISTS
22
6.100L Lecture 9
LISTS
23
6.100L Lecture 9
INDICES and ORDERING
a_list = []
L = [2, 'a', 4, [1,2]]
[1,2]+[3,4] evaluates to [1,2,3,4]
len(L) evaluates to 4
L[0] evaluates to 2
L[2]+1 evaluates to 5
L[3] evaluates to [1,2], another list!
L[4] gives an error
i = 2
L[i-1] evaluates to 'a' since L[1]='a'
max([3,5,0]) evaluates 5
24
6.100L Lecture 9
ITERATING OVER a LIST
total = 0 total = 0
for i in range(len(L)): for i in L:
total += L[i] total += i
print(total) print(total)
Notice
• list elements are indexed 0 to len(L)-1
and range(n) goes from 0 to n-1
25
6.100L Lecture 9
ITERATING OVER a LIST
def list_sum(L):
total = 0 total = 0
for i in L: for i in L:
# i is 8 then 3 then 5
total += i total += i
print(total) return total
6.100L Lecture 9
LISTS SUPPORT ITERATION
27
6.100L Lecture 9
YOU TRY IT!
Write a function that meets these specs:
def sum_and_prod(L):
""" L is a list of numbers
Return a tuple where the first value is the
sum of all elements in L and the second value
is the product of all elements in L """
28
6.100L Lecture 9
SUMMARY
6.100L Lecture 9
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
30
LISTS, MUTABILITY
(download slides and .py files to follow along)
6.100L Lecture 10
Ana Bell
1
INDICES and ORDERING in LISTS
a_list = []
L = [2, 'a', 4, [1,2]]
len(L) evaluates to 4
L[0] evaluates to 2
L[3] evaluates to [1,2], another list!
[2,'a'] + [5,6] evaluates to [2,'a',5,6]
max([3,5,0]) evaluates to 5
L[1:3] evaluates to ['a', 4]
for e in L loop variable becomes each element in L
L[3] = 10 mutates L to [2,'a',4,10]
2
6.100L Lecture 10
MUTABILITY
[2,4,3]
[2,5,3]
L
3
6.100L Lecture 10
MUTABILITY
Compare
Making L by mutating an element vs.
Making t by creating a new object
L = [2, 4, 3]
L[1] = 5 L [2,5,3]
[2,4,3]
t = (2, 4, 3) t x (2,4,3)
t = (2, 5, 3) (2,5,3)
6.100L Lecture 10
OPERATION ON LISTS – append
[2,1,3]
[2,1,3,5]
L
6.100L Lecture 10
5
OPERATION ON LISTS – append
[2,1,3]
[2,1,3,5]
L
6.100L Lecture 10
6
OPERATION ON LISTS – append
[2,1,3,5,5]
[2,1,3]
L
6.100L Lecture 10
7
OPERATION ON LISTS – append
[2,1,3,5,5]
[2,1,3]
None
L
6.100L Lecture 10
8
OPERATION ON LISTS – append
L
6.100L Lecture 10
9
YOU TRY IT!
What is the value of L1, L2, L3 and L at the end?
L1 = ['re']
L2 = ['mi']
L3 = ['do']
L4 = L1 + L2
L3.append(L4)
L = L1.append(L3)
10
6.100L Lecture 10
BIG IDEA
Some functions mutate
the list and don’t return
anything.
We use these functions for their side effect.
11
6.100L Lecture 10
OPERATION ON LISTS: append
L = [2,1,3]
L.append(5)
6.100L Lecture 10
YOU TRY IT!
Write a function that meets these specs:
def make_ordered_list(n):
""" n is a positive int
Returns a list containing all ints in order
from 0 to n (inclusive)
"""
13
6.100L Lecture 10
YOU TRY IT!
Write a function that meets the specification.
def remove_elem(L, e):
"""
L is a list
Returns a new list with elements in the same order as L
but without any elements equal to e.
"""
L = [1,2,2,2]
print(remove_elem(L, 2)) # prints [1]
14
6.100L Lecture 10
STRINGS to LISTS
15
6.100L Lecture 10
LISTS to STRINGS
16
6.100L Lecture 10
YOU TRY IT!
Write a function that meets these specs:
def count_words(sen):
""" sen is a string representing a sentence
Returns how many words are in s (i.e. a word is a
a sequence of characters between spaces. """
17
6.100L Lecture 10
A FEW INTERESTING LIST
OPERATIONS
Add an element to end of list with L.append(element)
mutates the list
sort()
L = [4,2,7]
L.sort()
Mutates L
reverse()
L = [4,2,7]
L.reverse()
Mutates L
sorted()
L = [4,2,7]
L_new = sorted(L)
Returns a sorted version of L (no mutation!)
18
6.100L Lecture 10
MUTABILITY
L=[9,6,0,3]
L.append(5)
a = sorted(L) returns a new sorted list, does not mutate L
[9,6,0,3,5]
[9,6,0,3]
19
6.100L Lecture 10
MUTABILITY
L=[9,6,0,3]
L.append(5)
a = sorted(L) returns a new sorted list, does not mutate L
[9,6,0,3,5]
L
[0,3,5,6,9]
a
20
6.100L Lecture 10
MUTABILITY
L=[9,6,0,3]
L.append(5)
a = sorted(L) returns a new sorted list, does not mutate L
None
b
[0,3,5,6,9]
[9,6,0,3,5]
L
[0,3,5,6,9]
a
21
6.100L Lecture 10
MUTABILITY
L=[9,6,0,3]
L.append(5)
a = sorted(L) returns a new sorted list, does not mutate L
None
b
[9,6,5,3,0]
[0,3,5,6,9]
L
[0,3,5,6,9]
a
22
6.100L Lecture 10
YOU TRY IT!
Write a function that meets these specs:
def sort_words(sen):
""" sen is a string representing a sentence
Returns a list containing all the words in sen but
sorted in alphabetical order. """
23
6.100L Lecture 10
BIG IDEA
Functions with side
effects mutate inputs.
You can write your own!
24
6.100L Lecture 10
LISTS SUPPORT ITERATION
def square_list(L):
for elem in L:
# ?? How to do L[index] = the square ??
# ?? elem is an element in L, not the index :(
6.100L Lecture 10
LISTS SUPPORT ITERATION
def square_list(L):
for i in range(len(L)):
L[i] = L[i]**2
Note, no return!
26
6.100L Lecture 10
TRACE the CODE with an
EXAMPLE
Example: square every element of a list, mutating original list
def square_list(L):
for i in range(len(L)):
L[i] = L[i]**2
Suppose L is [2,3,4]
i is 0: L is mutated to [4, 3, 4]
i is 1: L is mutated to [4, 9, 4]
i is 2: L is mutated to [4, 9, 16]
27
6.100L Lecture 10
TRACE the CODE with an
EXAMPLE
Example: square every element of a list, mutating original list
def square_list(L):
for i in range(len(L)):
L[i] = L[i]**2
Lin = [2,3,4]
print("before fcn call:",Lin) # prints [2,3,4]
square_list(Lin)
print("after fcn call:",Lin) # prints [4,9,16]
28
6.100L Lecture 10
BIG IDEA
Functions that mutate
the input likely…..
Iterate over len(L) not L.
Return None, so the function call does not need to be saved.
29
6.100L Lecture 10
MUTATION
30
6.100L Lecture 10
TRICKY EXAMPLES OVERVIEW
TRICKY EXAMPLE 1:
A loop iterates over indices of L and mutates L each time (adds more
elements).
TRICKY EXAMPLE 2:
A loop iterates over L’s elements directly and mutates L each time (adds
more elements).
TRICKY EXAMPLE 3:
A loop iterates over L’s elements directly but reassigns L to a new
object each time
TRICKY EXAMPLE 4 (next time):
A loop iterates over L’s elements directly and mutates L by removing
elements.
31
6.100L Lecture 10
TRICKY EXAMPLE 1: append
6.100L Lecture 10
TRICKY EXAMPLE 1: append
L = [1,2,3,4]
for i in range(len(L)):
[1,2,3,4,0,1,2]
[1,2,3,4,0]
[1,2,3,4]
[1,2,3,4,0,1]
[1,2,3,4,0,1,2,3]
L.append(i)
print(L) L
(0,1,2,3)
i
1st time: L is [1, 2, 3, 4, 0]
2nd time: L is [1, 2, 3, 4, 0, 1]
3rd time: L is [1, 2, 3, 4, 0, 1, 2]
4th time: L is [1, 2, 3, 4, 0, 1, 2, 3]
33
6.100L Lecture 10
TRICKY EXAMPLE 2: append
for e in L: 1
3
0
2
L
L.append(i)
i
i += 1
print(L) 1st time: L is [1, 2, 3, 4, 0]
2nd time: L is [1, 2, 3, 4, 0, 1]
In previous example, L was accessed at
onset to create a range iterable; in this 3rd time: L is [1, 2, 3, 4, 0, 1, 2]
example, the loop is directly accessing 4th time: L is [1, 2, 3, 4, 0, 1, 2, 3]
indices into L NEVER STOPS!
34
6.100L Lecture 10
COMBINING LISTS
L1 [2,1,3]
L2 [4,5,6]
L3 [2,1,3,4,5,6]
35
6.100L Lecture 10
COMBINING LISTS
L1 [2,1,3]
[2,1,3,0,6]
L2 [4,5,6]
L3 [2,1,3,4,5,6]
36
6.100L Lecture 10
COMBINING LISTS
L1 [2,1,3]
[2,1,3,0,6]
L2 [4,5,6]
[4,5,6,[1,2],[3,4]]
L3 [2,1,3,4,5,6]
37
6.100L Lecture 10
TRICKY EXAMPLE 3: combining
6.100L Lecture 10
TRICKY EXAMPLE 3: combining
e
L = [1,2,3,4]
for e in L: [1,2,3,4]
[1,2,3,4,1,2,3,4]
L = L + L L
print(L)
39
6.100L Lecture 10
TRICKY EXAMPLE 3: combining
e
L = [1,2,3,4]
for e in L: [1,2,3,4]
[1,2,3,4,1,2,3,4]
L = L + L L
[1,2,3,4,1,2,3,4,
1,2,3,4,1,2,3,4]
print(L)
40
6.100L Lecture 10
TRICKY EXAMPLE 3: combining
e
L = [1,2,3,4]
for e in L: [1,2,3,4]
[1,2,3,4,1,2,3,4]
L = L + L L
[1,2,3,4,1,2,3,4,
1,2,3,4,1,2,3,4]
print(L)
[1,2,3,4,1,2,3,4,
1,2,3,4,1,2,3,4,
1st time: new L is [1, 2, 3, 4, 1, 2, 3, 4] 1,2,3,4,1,2,3,4,
1,2,3,4,1,2,3,4,]
2nd time: new L is [1, 2, 3, 4, 1, 2, 3, 4,
1, 2, 3, 4, 1, 2, 3, 4 ]
3rd time: new L is [1, 2, 3, 4, 1, 2, 3, 4,
1, 2, 3, 4, 1, 2, 3, 4 ,
1, 2, 3, 4, 1, 2, 3, 4,
1, 2, 3, 4, 1, 2, 3, 4] 41
6.100L Lecture 10
TRICKY EXAMPLE 3: combining
e
L = [1,2,3,4]
for e in L: [1,2,3,4]
[1,2,3,4,1,2,3,4]
L = L + L L
[1,2,3,4,1,2,3,4,
1,2,3,4,1,2,3,4]
print(L)
[1,2,3,4,1,2,3,4,
4th time: new L is [1, 2, 3, 4, 1, 2, 3, 4, 1,2,3,4,1,2,3,4,
1, 2, 3, 4, 1, 2, 3, 4 , 1,2,3,4,1,2,3,4,
1,2,3,4,1,2,3,4,]
1, 2, 3, 4, 1, 2, 3, 4,
1, 2, 3, 4, 1, 2, 3, 4 [1,2,3,4,1,2,3,4,
1,2,3,4,1,2,3,4,
1, 2, 3, 4, 1, 2, 3, 4, 1,2,3,4,1,2,3,4,
1, 2, 3, 4, 1, 2, 3, 4 , 1,2,3,4,1,2,3,4,
1,2,3,4,1,2,3,4,
1, 2, 3, 4, 1, 2, 3, 4, 1,2,3,4,1,2,3,4,
1, 2, 3, 4, 1, 2, 3, 4 ] 42
1,2,3,4,1,2,3,4,
1,2,3,4,1,2,3,4,]
6.100L Lecture 10
EMPTY OUT A LIST AND CHECKING
THAT IT’S THE SAME OBJECT
You can mutate a list to remove all its elements
This does not make a new empty list!
Use L.clear()
How to check that it’s the same object in memory?
Use the id() function
Try this in the console
>>> L = [4,5,6] >>> L = [4,5,6]
>>> id(L) >>> id(L)
>>> L.append(8) >>> L.append(8)
>>> id(L) >>> id(L)
>>> L.clear() >>> L = []
>>> id(L) >>> id(L)
43
6.100L Lecture 10
SUMMARY
44
6.100L Lecture 10
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
45
ALIASING,
CLONING
(download slides and .py files to follow along)
6.100L Lecture 11
Ana Bell
1
MAKING A COPY OF THE LIST
Loriginal [4,5,6]
Lnew [4,5,6]
6.100L Lecture 11
YOU TRY IT!
Write a function that meets the specification.
Hint. Make a copy to save the elements. The use L.clear() to
empty out the list and repopulate it with the ones you’re
keeping.
def remove_all(L, e):
"""
L is a list
Mutates L to remove all elements in L that are equal to e
Returns None
"""
L = [1,2,2,2]
remove_all(L, 2)
print(L) # prints [1]
6.100L Lecture 11
OPERATION ON LISTS: remove
6.100L Lecture 11
EXERCISE WITH REMOVE INSTEAD
OF COPY AND CLEAR
Rewrite the code to remove e as long as we still had it in the list
It works well!
6.100L Lecture 11
EXERCISE WITH REMOVE INSTEAD
OF COPY AND CLEAR
What if the code was this:
L = [1,2,2,2]
remove_all(L, 2)
print(L) # should print [1]
6.100L Lecture 11
EXERCISE WITH REMOVE INSTEAD
OF COPY AND CLEAR
L = [1,2,2,2]
remove_all(L, 2) L [1,2,2,2]
print(L) # should print [1]
6.100L Lecture 11
EXERCISE WITH REMOVE INSTEAD
OF COPY AND CLEAR
L = [1,2,2,2]
remove_all(L, 2) L [1,2,2,2]
print(L) # should print [1]
6.100L Lecture 11
EXERCISE WITH REMOVE INSTEAD
OF COPY AND CLEAR
L = [1,2,2,2]
remove_all(L, 2) L [1,2,2,2]
[1,2,2]
print(L) # should print [1]
6.100L Lecture 11
EXERCISE WITH REMOVE INSTEAD
OF COPY AND CLEAR
L = [1,2,2,2]
remove_all(L, 2) L [1,2,2]
print(L) # should print [1]
10
6.100L Lecture 11
EXERCISE WITH REMOVE INSTEAD
OF COPY AND CLEAR
It’s not correct! We removed items as we iterated over the list!
L = [1,2,2,2]
remove_all(L, 2) L [1,2]
[1,2,2]
print(L) # should print [1]
11
6.100L Lecture 11
TRICKY EXAMPLES OVERVIEW
TRICKY EXAMPLE 1:
A loop iterates over indices of L and mutates L each time (adds more
elements).
TRICKY EXAMPLE 2:
A loop iterates over L’s elements directly and mutates L each time (adds
more elements).
TRICKY EXAMPLE 3:
A loop iterates over L’s elements directly but reassigns L to a new
object each time
TRICKY EXAMPLE 4:
A loop iterates over L’s elements directly and mutates L by removing
elements.
12
6.100L Lecture 11
TRICKY EXAMPLE 4
PYTHON TUTOR LINK to see step-by-step
6.100L Lecture 11
MUTATION AND ITERATION WITHOUT CLONE
e
L1 = [10, 20, 30, 40]
L2 = [10, 20, 50, 60]
remove_dups(L1, L2)
L1 [10,20,30,40]
L2 [10,20,50,60]
14
6.100L Lecture 11
MUTATION AND ITERATION WITHOUT CLONE
e
L1 = [10, 20, 30, 40]
L2 = [10, 20, 50, 60]
remove_dups(L1, L2)
L1 [20,30,40]
L2 [10,20,50,60]
15
6.100L Lecture 11
MUTATION AND ITERATION WITHOUT CLONE
e
L1 = [10, 20, 30, 40]
L2 = [10, 20, 50, 60]
remove_dups(L1, L2)
L1 [20,30,40]
L2 [10,20,50,60]
16
6.100L Lecture 11
MUTATION AND ITERATION WITHOUT CLONE
e
L1 = [10, 20, 30, 40]
L2 = [10, 20, 50, 60]
remove_dups(L1, L2)
L1 [20,30,40]
L2 [10,20,50,60]
17
6.100L Lecture 11
MUTATION AND ITERATION WITH CLONE
L1_copy = L1[:]
6.100L Lecture 11
def remove_dups(L1, L2):
L1_copy = L1[:]
for e in L1_copy:
if e in L2:
L1.remove(e)
e
L1 = [10, 20, 30, 40]
L2 = [10, 20, 50, 60]
remove_dups(L1, L2)
L1_copy [10,20,30,40]
L1 [10,20,30,40]
L2 [10,20,50,60]
19
6.100L Lecture 11
def remove_dups(L1, L2):
L1_copy = L1[:]
for e in L1_copy:
if e in L2:
L1.remove(e)
e
L1 = [10, 20, 30, 40]
L2 = [10, 20, 50, 60]
remove_dups(L1, L2)
L1_copy [10,20,30,40]
L1 [20,30,40]
L2 [10,20,50,60]
20
6.100L Lecture 11
def remove_dups(L1, L2):
L1_copy = L1[:]
for e in L1_copy:
if e in L2:
L1.remove(e)
e
L1 = [10, 20, 30, 40]
L2 = [10, 20, 50, 60]
remove_dups(L1, L2)
L1_copy [10,20,30,40]
L1 [20,30,40]
L2 [10,20,50,60]
21
6.100L Lecture 11
def remove_dups(L1, L2):
L1_copy = L1[:]
for e in L1_copy:
if e in L2:
L1.remove(e)
e
L1 = [10, 20, 30, 40]
L2 = [10, 20, 50, 60]
remove_dups(L1, L2)
L1_copy [10,20,30,40]
L1 [30,40]
L2 [10,20,50,60]
22
6.100L Lecture 11
def remove_dups(L1, L2):
L1_copy = L1[:]
for e in L1_copy:
if e in L2:
L1.remove(e)
e
L1 = [10, 20, 30, 40]
L2 = [10, 20, 50, 60]
remove_dups(L1, L2)
L1_copy [10,20,30,40]
L1 [30,40]
L2 [10,20,50,60]
23
6.100L Lecture 11
def remove_dups(L1, L2):
L1_copy = L1[:]
for e in L1_copy:
if e in L2:
L1.remove(e)
e
L1 = [10, 20, 30, 40]
L2 = [10, 20, 50, 60]
remove_dups(L1, L2)
L1_copy [10,20,30,40]
L1 [30,40]
L2 [10,20,50,60]
24
6.100L Lecture 11
ALIASING
… all the aliases refer to the old attribute and all the new ones
The Hub small tech-savvy snowy
25
6.100L Lecture 11
MUTATION AND ITERATION WITH ALIAS
L1_copy = L1
6.100L Lecture 11
def remove_dups(L1, L2):
L1_copy = L1
for e in L1_copy:
if e in L2:
L1.remove(e)
e
L1 = [10, 20, 30, 40]
L2 = [10, 20, 50, 60]
remove_dups(L1, L2) L1_copy
L1 [20,30,40]
[10,20,30,40]
L2 [10,20,50,60]
27
6.100L Lecture 11
BIG IDEA
When you pass a list as a
parameter to a function,
you are making an alias.
The actual parameter (from the function call) is an alias for
the formal parameter (from the function definition).
28
6.100L Lecture 11
def remove_dups(L1, L2):
L1_copy = L1
for e in L1_copy:
if e in L2:
L1.remove(e)
e
La = [10, 20, 30, 40]
Lb = [10, 20, 50, 60]
remove_dups(La, Lb) L1_copy
print(La) La [20,30,40]
[10,20,30,40]
L1
Lb [10,20,50,60]
L2
29
6.100L Lecture 11
ALIASES,
SHALLOW COPIES, AND
DEEP COPIES WITH
MUTABLE ELEMENTS
30
6.100L Lecture 11
CONTROL COPYING
new_list[2][1] = 6
print("New list:", new_list) New list: [[1,2],[3,4],[5,6]]
print("Old list:", old_list) Old list: [[1,2],[3,4],[5,6]]
So mutating one object changes the other
[ , , ]
new_list
31
6.100L Lecture 11
CONTROL COPYING
6.100L Lecture 11
old_list = [[1,2],[3,4],[5,6]]
new_list = copy.copy(old_list)
[ , , ]
old_list
[1,2] [3,4] [5,6]
new_list 6.0001 LECTURE 5
[ , , ]
33
6.100L Lecture 11
CONTROL COPYING
old_list.append([7,8])
print("New list:", new_list)
print("Old list:", old_list)
34
6.100L Lecture 11
old_list = [[1,2],[3,4],[5,6]]
new_list = copy.copy(old_list)
old_list.append([7,8])
print("New list:", new_list)
New list: [[1,2],[3,4],[5,6]]
print("Old list:", old_list)
Old list: [[1,2],[3,4],[5,6],[7,8]]
[[ ,, ,, ], ]
old_list
[1,2] [3,4] [5,6] [7,8]
new_list 6.0001 LECTURE 5
35
[ , , ]
6.100L Lecture 11
CONTROL COPYING
old_list.append([7,8])
old_list[1][1] = 9
print("New list:", new_list)
print("Old list:", old_list)
36
6.100L Lecture 11
old_list = [[1,2],[3,4],[5,6]]
new_list = copy.copy(old_list)
old_list.append([7,8])
old_list[1][1] = 9
print("New list:", new_list) New list: [[1,2],[3,9],[5,6]]
print("Old list:", old_list) Old list: [[1,2],[3,9],[5,6],[7,8]]
[[ ,, ,, ], ]
old_list
[1,2] [3,4]
[3,9] [5,6] [7,8]
new_list 6.0001 LECTURE 5
[
37
, , ]
6.100L Lecture 11
CONTROL COPYING
old_list.append([7,8])
old_list[1][1] = 9
print("New list:", new_list)
print("Old list:", old_list)
38
6.100L Lecture 11
old_list = [[1,2],[3,4],[5,6]]
new_list = copy.deepcopy(old_list)
old_list.append([7,8])
old_list[1][1] = 9
print("New list:", new_list) New list: [[1,2],[3,4],[5,6]]
print("Old list:", old_list) Old list: [[1,2],[3,9],[5,6],[7,8]]
[ , , ]
, ]
[39 , , ]
6.100L Lecture 11
LISTS in MEMORY
Separate the idea of the object vs. the name we give an object
A list is an object in memory
Variable name points to object
Lists are mutable and behave differently than immutable types
Using equal sign between mutable objects creates aliases
Both variables point to the same object in memory
Any variable pointing to that object is affected by mutation of object,
even if mutation is by referencing another name
If you want a copy, you explicitly tell Python to make a copy
Key phrase to keep in mind when working with lists is side
effects, especially when dealing with aliases – two names
pointing to the same structure in memory
Python Tutor is your best friend to help sort this out!
http://www.pythontutor.com/ 40
6.100L Lecture 11
WHY LISTS and TUPLES?
41
6.100L Lecture 11
AT HOME TRACING
EXAMPLES SHOWCASING
ALIASING AND CLONING
42
6.100L Lecture 11
ALIASES
43
6.100L Lecture 11
ALIASES
44
6.100L Lecture 11
CLONING A LIST
45
6.100L Lecture 11
CLONING A LIST
46
6.100L Lecture 11
CLONING A LIST
47
6.100L Lecture 11
LISTS OF LISTS
OF LISTS OF….
Can have nested lists
Side effects still
possible after mutation
48
6.100L Lecture 11
LISTS OF LISTS
OF LISTS OF….
Can have nested lists
Side effects still
possible after mutation
49
6.100L Lecture 11
LISTS OF LISTS
OF LISTS OF….
Can have nested lists
Side effects still
possible after mutation
50
6.100L Lecture 11
LISTS OF LISTS
OF LISTS OF….
Can have nested lists
Side effects still
possible after mutation
51
6.100L Lecture 11
LISTS OF LISTS
OF LISTS OF….
Can have nested lists
Side effects still
possible after mutation
52
6.100L Lecture 11
LISTS OF LISTS
OF LISTS OF….
Can have nested lists
Side effects still
possible after mutation
53
6.100L Lecture 11
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
54
LIST COMPREHENSION,
FUNCTIONS AS OBJECTS,
TESTING, DEBUGGING
(download slides and .py files to follow along)
6.100L Lecture 12
Ana Bell
1
LIST COMPREHENSIONS
6.100L Lecture 12
LIST COMPREHENSIONS
6.100L Lecture 12
LIST COMPREHENSIONS
def f(L):
Lnew = []
for e in L: Lnew = [e**2 for e in L]
Lnew.append(e**2)
return Lnew
6.100L Lecture 12
LIST COMPREHENSIONS
def f(L):
Lnew = []
for e in L: Lnew = [e**2 for e in L]
Lnew.append(e**2)
return Lnew
def f(L):
Lnew = []
for e in L:
if e%2==0:
Lnew.append(e**2)
return Lnew
5
6.100L Lecture 12
LIST COMPREHENSIONS
def f(L):
Lnew = []
for e in L: Lnew = [e**2 for e in L]
Lnew.append(e**2)
return Lnew
def f(L):
Lnew = []
for e in L:
if e%2==0:
Lnew.append(e**2) Lnew = [e**2 for e in L if e%2==0]
return Lnew
6
6.100L Lecture 12
LIST COMPREHENSIONS
def f(L):
Lnew = []
for e in L: Lnew = [e**2 for e in L]
Lnew.append(e**2)
return Lnew
def f(L):
Lnew = []
for e in L:
if e%2==0:
Lnew.append(e**2) Lnew = [e**2 for e in L if e%2==0]
return Lnew
7
6.100L Lecture 12
LIST COMPREHENSIONS
def f(L):
Lnew = []
for e in L: Lnew = [e**2 for e in L]
Lnew.append(e**2)
return Lnew
def f(L):
Lnew = []
for e in L:
if e%2==0:
Lnew.append(e**2) Lnew = [e**2 for e in L if e%2==0]
return Lnew
8
6.100L Lecture 12
LIST COMPREHENSIONS
6.100L Lecture 12
YOU TRY IT!
What is the value returned by this expression?
Step1: what are all values in the sequence
Step2: which subset of values does the condition filter out?
Step3: apply the function to those values
10
6.100L Lecture 12
FUNCTIONS: DEFAULT
PARAMETERS
11
6.100L Lecture 12
SQUARE ROOT with BISECTION
def bisection_root(x):
epsilon = 0.01
low = 0
high = x
guess = (high + low)/2.0
while abs(guess**2 - x) >= epsilon:
if guess**2 < x:
low = guess
else:
high = guess
guess = (high + low)/2.0
return guess
print(bisection_root(123))
12
6.100L Lecture 12
ANOTHER PARAMETER
13
6.100L Lecture 12
epsilon as a PARAMETER
print(bisection_root(123, 0.01))
14
6.100L Lecture 12
KEYWORD PARAMETERS &
DEFAULT VALUES
def bisection_root(x, epsilon)can be improved
We added epsilon as an argument to the function
Most of the time we want some standard value, 0.01
Sometimes, we may want to use some other value
Use a keyword parameter aka a default parameter
15
6.100L Lecture 12
Epsilon as a KEYWORD
PARAMETER
def bisection_root(x, epsilon=0.01):
low = 0
high = x
guess = (high + low)/2.0
while abs(guess**2 - x) >= epsilon:
if guess**2 < x:
low = guess
else:
high = guess
guess = (high + low)/2.0
return guess
print(bisection_root(123))
print(bisection_root(123, 0.5))
16
6.100L Lecture 12
RULES for KEYWORD PARAMETERS
17
6.100L Lecture 12
FUNCTIONS RETURNING
FUNCTIONS
18
6.100L Lecture 12
OBJECTS IN A PROGRAM
function
my_func object
named
is_even is_even
pi = 22/7
a False
my_func = is_even
b True
a = is_even(3)
b = my_func(4)
19
6.100L Lecture 12
FUNCTIONS CAN RETURN
FUNCTIONS
def make_prod(a):
def g(b):
return a*b
return g
20
6.100L Lecture 12
SCOPE DETAILS FOR WAY 1
def make_prod(a):
def g(b):
return a*b
return g
val = make_prod(2)(3)
print(val)
21
6.100L Lecture 12
SCOPE DETAILS FOR WAY 1
val = make_prod(2)(3)
print(val)
22
6.100L Lecture 12
SCOPE DETAILS FOR WAY 1 NOTE: definition
of g is done
within scope of
make_prod, so
binding of g is
def make_prod(a): Global scope make_prod within that
scope frame/scope
def g(b):
make_prod Some Since g is bound
return a*b a 2 in this frame,
code
cannot access it
return g by evaluation in
Some global frame
g
code g can only be
val = make_prod(2)(3) accessed within
call to
print(val) make_prod, and
each call will
create a new,
internal g
23
6.100L Lecture 12
SCOPE DETAILS FOR WAY 1
25
6.100L Lecture 12
SCOPE DETAILS FOR WAY 1
def make_prod(a):
def g(b):
return a*b
return g
doubler = make_prod(2)
val = doubler(3)
print(val)
27
6.100L Lecture 12
SCOPE DETAILS FOR WAY 2
28
6.100L Lecture 12
SCOPE DETAILS FOR WAY 2
29
6.100L Lecture 12
SCOPE DETAILS FOR WAY 2
Returns value
30
6.100L Lecture 12
WHY BOTHER RETURNING
FUNCTIONS?
Code can be rewritten without returning function objects
Good software design
Embracing ideas of decomposition, abstraction
Another tool to structure code
Interrupting execution
Example of control flow
A way to achieve partial execution and use result somewhere else
before finishing the full evaluation
31
6.100L Lecture 12
TESTING and
DEBUGGING
32
6.100L Lecture 12
DEFENSIVE PROGRAMMING
• Write specifications for functions
• Modularize programs
• Check conditions on inputs/outputs (assertions)
TESTING/VALIDATION DEBUGGING
• Compare input/output • Study events leading up
pairs to specification to an error
• “It’s not working!” • “Why is it not working?”
• “How can I break my • “How can I fix my
program?” program?”
33
6.100L Lecture 12
SET YOURSELF UP FOR EASY
TESTING AND DEBUGGING
34
6.100L Lecture 12
WHEN ARE YOU READY TO TEST?
35
6.100L Lecture 12
CLASSES OF TESTS
Unit testing
• Validate each piece of program
• Testing each function separately
Regression testing
• Add test for bugs as you find them
• Catch reintroduced errors that were previously
fixed
Integration testing
• Does overall program work?
• Tend to rush to do this
36
6.100L Lecture 12
TESTING APPROACHES
6.100L Lecture 12
BLACK BOX TESTING
38
6.100L Lecture 12
BLACK BOX TESTING
CASE x eps
boundary 0 0.0001
perfect square 25 0.0001
less than 1 0.05 0.0001
irrational square root 2 0.0001
extremes 2 1.0/2.0**64.0
extremes 1.0/2.0**64.0 1.0/2.0**64.0
extremes 2.0**64.0 1.0/2.0**64.0
extremes 1.0/2.0**64.0 2.0**64.0
extremes 2.0**64.0 39 2.0**64.0
6.100L Lecture 12
GLASS BOX TESTING
40
6.100L Lecture 12
GLASS BOX TESTING
def abs(x):
""" Assumes x is an int
Returns x if x>=0 and –x otherwise """
if x < -1:
return –x
else:
return x
Aa path-complete test suite could miss a bug
Path-complete test suite: 2 and -2
But abs(-1) incorrectly returns -1
Should still test boundary cases
41
6.100L Lecture 12
DEBUGGING
Once you have discovered that your code does not run
properly, you want to:
Isolate the bug(s)
Eradicate the bug(s)
Retest until code runs correctly for all cases
Steep learning curve
Goal is to have a bug-free program
Tools
• Built in to IDLE and Anaconda
• Python Tutor
• print statement
• Use your brain, be systematic in your hunt
42
6.100L Lecture 12
ERROR MESSAGES – EASY
6.100L Lecture 12
LOGIC ERRORS - HARD
44
6.100L Lecture 12
DEBUGGING STEPS
45
6.100L Lecture 12
PRINT STATEMENTS
46
6.100L Lecture 12
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
47
EXCEPTIONS,
ASSERTIONS
(download slides and .py files to follow along)
6.100L Lecture 13
Ana Bell
1
EXCEPTIONS
2
UNEXPECTED
CONDITIONS
6.100L Lecture 13
HANDLING EXCEPTIONS
6.100L Lecture 13
EXAMPLE with CODE YOU MIGHT
HAVE ALREADY SEEN
A function that sums digits in a string
CODE YOU’VE SEEN CODE WITH EXCEPTIONS
def sum_digits(s): def sum_digits(s):
""" s is a non-empty string """ s is a non-empty string
containing digits. containing digits.
Returns sum of all chars that Returns sum of all chars that
are digits """ are digits """
total = 0 total = 0
for char in s: for char in s:
if char in '0123456789': try:
val = int(char) val = int(char)
total += val total += val
return total except:
print("can't convert", char)
return total
5
6.100L Lecture 13
USER INPUT CAN LEAD TO
EXCEPTIONS
6.100L Lecture 13
HANDLING SPECIFIC EXCEPTIONS
6.100L Lecture 13
OTHER BLOCKS ASSOCIATED WITH
A TRY BLOCK
else:
• Body of this is executed when execution of associated try body
completes with no exceptions
finally:
• Body of this is always executed after try, else and except clauses,
even if they raised another error or executed a break, continue or
return
• Useful for clean-up code that should be run no matter what else
happened (e.g. close a file)
Nice to know these exist, but we don’t really use these in this
class
6.100L Lecture 13
WHAT TO DO WITH EXCEPTIONS?
6.100L Lecture 13
EXAMPLE with SOMETHING
YOU’VE ALREADY SEEN
A function that sums digits in a string
Execution stopping means a bad result is not propagated
def sum_digits(s):
""" s is a non-empty string containing digits.
Returns sum of all chars that are digits """
total = 0
for char in s:
try:
val = int(char)
total += val
except:
raise ValueError("string contained a character")
return total
10
6.100L Lecture 13
YOU TRY IT!
def pairwise_div(Lnum, Ldenom):
""" Lnum and Ldenom are non-empty lists of equal lengths containing numbers
# For example:
L1 = [4,5,6]
L2 = [1,2,3]
# print(pairwise_div(L1, L2)) # prints [4.0,2.5,2.0]
L1 = [4,5,6]
L2 = [1,0,3]
# print(pairwise_div(L1, L2)) # raises a ValueError
11
6.100L Lecture 13
ASSERTIONS
12
6.100L Lecture 13
ASSERTIONS: DEFENSIVE
PROGRAMMING TOOL
Want to be sure that assumptions on state of computation are as
expected
Use an assert statement to raise an AssertionError
exception if assumptions not met
assert <statement that should be true>, "message if not true"
An example of good defensive programming
Assertions don’t allow a programmer to control response to unexpected
conditions
Ensure that execution halts whenever an expected condition is not met
Typically used to check inputs to functions, but can be used anywhere
Can be used to check outputs of a function to avoid propagating bad
values
Can make it easier to locate a source of a bug
13
6.100L Lecture 13
EXAMPLE with SOMETHING
YOU’VE ALREADY SEEN
A function that sums digits in a NON-EMPTY string
Execution stopping means a bad result is not propagated
def sum_digits(s):
""" s is a non-empty string containing digits.
Returns sum of all chars that are digits """
assert len(s) != 0, "s is empty"
total = 0
for char in s:
try:
val = int(char)
total += val
except:
raise ValueError("string contained a character")
14
6.100L Lecture 13
YOU TRY IT!
def pairwise_div(Lnum, Ldenom):
""" Lnum and Ldenom are non-empty lists of equal lengths
containing numbers
Returns a new list whose elements are the pairwise
division of an element in Lnum by an element in Ldenom.
Raise a ValueError if Ldenom contains 0. """
# add an assert line here
15
6.100L Lecture 13
ANOTHER EXAMPLE
16
6.100L Lecture 13
LONGER EXAMPLE OF
EXCEPTIONS and ASSERTIONS
17
6.100L Lecture 13
EXAMPLE [[['peter', 'parker'], [80.0, 70.0, 85.0]],
CODE [['bruce', 'wayne'], [100.0, 80.0, 74.0]]]
def get_stats(class_list):
new_stats = []
for stu in class_list:
new_stats.append([stu[0], stu[1], avg(stu[1])])
return new_stats
def avg(grades):
return sum(grades)/len(grades)
18
6.100L Lecture 13
ERROR IF NO GRADE FOR A
STUDENT
19
6.100L Lecture 13
OPTION 1: FLAG THE ERROR BY
PRINTING A MESSAGE
6.100L Lecture 13
OPTION 2: CHANGE THE POLICY
6.100L Lecture 13
OPTION 3: HALT EXECUTION IF
ASSERT IS NOT MET
def avg(grades):
assert len(grades) != 0, 'no grades data'
return sum(grades)/len(grades)
22
6.100L Lecture 13
ASSERTIONS vs. EXCEPTIONS
6.100L Lecture 13
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
24
DICTIONARIES
(download slides and .py files to follow along)
6.100L Lecture 14
Ana Bell
1
HOW TO STORE
STUDENT INFO
Suppose we want to store and use grade information for
a set of students
Could store using separate lists for each kind of
information
names = ['Ana', 'John', 'Matt', 'Katy']
grades = ['A+' , 'B' , 'A' , 'A' ]
microquizzes = ...
psets = ...
Info stored across lists at same index, each index refers to
information for a different person
Indirectly access information by finding location in lists
corresponding to a person, then extract
2
6.100L Lecture 14
HOW TO ACCESS
STUDENT INFO
def get_grade(student, name_list, grade_list):
i = name_list.index(student)
grade = grade_list[i]
return (student, grade)
6.100L Lecture 14
HOW TO STORE AND
ACCESS STUDENT INFO
Alternative might be to use a list of lists
eric = ['eric', ['ps', [8, 4, 5]], ['mq', [6, 7]]]
ana = ['ana', ['ps', [10, 10, 10]], ['mq', [9, 10]]]
john = ['john', ['ps', [7, 6, 5]], ['mq', [8, 5]]]
6.100L Lecture 14
A BETTER AND CLEANER WAY –
A DICTIONARY
Nice to use one data structure, no separate lists
Nice to index item of interest directly
A Python dictionary has entries that map a key:value
A list A dictionary
0 Elem 1 Key 1 Val 1
… … … …
6.100L Lecture 14
BIG IDEA
Dict value refers to the
value associated with a
key.
This terminology is may sometimes be confused with the
regular value of some variable.
6.100L Lecture 14
A PYTHON DICTIONARY
my_dict = {}
d = {4:16}
grades = {'Ana':'B', 'Matt':'A', 'John':'B', 'Katy':'A'}
6.100L Lecture 14
DICTIONARY LOOKUP
6.100L Lecture 14
YOU TRY IT!
Write a function according to this spec
def find_grades(grades, students):
""" grades is a dict mapping student names (str) to grades (str)
students is a list of student names
Returns a list containing the grades for students (in same order) """
# for example
6.100L Lecture 14
BIG IDEA
Getting a dict value is
just a matter of indexing
with a key.
No. Need. To. Loop
10
6.100L Lecture 14
'Ana' 'B'
DICTIONARY 'Matt' 'A'
OPERATIONS 'John' 'B'
'Katy' 'A'
'Grace' 'A'
'C'
Add an entry
grades['Grace'] = 'A'
Change entry
grades['Grace'] = 'C'
Delete entry
del(grades['Ana'])
11
6.100L Lecture 14
'Ana' 'B'
DICTIONARY 'Matt' 'A'
OPERATIONS 'John' 'B'
'Katy' 'A'
12
6.100L Lecture 14
YOU TRY IT!
Write a function according to these specs
def find_in_L(Ld, k):
""" Ld is a list of dicts
k is an int
Returns True if k is a key in any dicts of Ld and False otherwise """
# for example
d1 = {1:2, 3:4, 5:6}
d2 = {2:4, 4:6}
d3 = {1:1, 3:9, 4:16, 5:25}
13
6.100L Lecture 14
'Ana' 'B'
DICTIONARY 'Matt' 'A'
OPERATIONS
'John' 'B'
'Katy' 'A'
Can iterate over dictionaries but
assume there is no guaranteed order
grades = {'Ana':'B', 'Matt':'A', 'John':'B', 'Katy':'A'}
14
6.100L Lecture 14
'Ana' 'B'
DICTIONARY OPERATIONS
most useful way to iterate over 'Matt' 'A'
dict entries (both keys and vals!) 'John' 'B'
'Katy' 'A'
Can iterate over dictionaries but
assume there is no guaranteed order
grades = {'Ana':'B', 'Matt':'A', 'John':'B', 'Katy':'A'}
list(grades.items())
returns [('Ana', 'B'), ('Matt', 'A'), ('John', 'B'), ('Katy', 'A')]
6.100L Lecture 14
YOU TRY IT!
Write a function that meets this spec
def count_matches(d):
""" d is a dict
Returns how many entries in d have the key equal to its value """
# for example
d = {1:2, 3:4, 5:6}
print(count_matches(d)) # prints 0
d = {1:2, 'a':'a', 5:5}
print(count_matches(d)) # prints 2
16
6.100L Lecture 14
DICTIONARY KEYS & VALUES
6.100L Lecture 14
WHY IMMUTABLE/HASHABLE
KEYS?
A dictionary is stored in memory in a special way
Next slides show an example
18
6.100L Lecture 14
Hash function:
1) Sum the letters Memory block (like a list)
2) Take mod 16 (to fit in a memory
block with 16 entries) 0 Ana: C
1
1 + 14 + 1 = 16
16%16 = 0 2
3 Eric: A
Ana C 4
5 + 18 + 9 + 3 = 35
35%16 = 3
5 [K,a,t,e]: B
6
Eric A 7
10 + 15 + 8 + 14 = 47 8
47%16 = 15
9
John B 10
11
12
13
11 + 1 + 20 + 5 = 37 14
37%16 = 5 15 John: B
[K, a, t, e] B 19
6.100L Lecture 14
Hash function:
1) Sum the letters Memory block (like a list)
2) Take mod 16 (to fit in a memory
block with 16 entries) 0 Ana: C
1
Kate changes her name to Cate. Same 2
person, different name. Look up her 3 Eric: A
grade? 4
5 [K,a,t,e]: B
6
7
8
9
10
11
12
13 ??? Not here!
3 + 1 + 20 + 5 = 29 14
29%16 = 13 15 John: B
[C, a, t, e] 20
6.100L Lecture 14
A PYTHON DICTIONARY for
STUDENT GRADES
21
6.100L Lecture 14
A PYTHON DICTIONARY for
STUDENT GRADES
22
6.100L Lecture 14
A PYTHON DICTIONARY for
STUDENT GRADES
23
6.100L Lecture 14
A PYTHON DICTIONARY for
STUDENT GRADES
6.100L Lecture 14
YOU TRY IT!
my_d ={'Ana':{'mq':[10], 'ps':[10,10]},
'Bob':{'ps':[7,8], 'mq':[8]},
'Eric':{'mq':[3], 'ps':[0]} }
Given the dict my_d, and the outline of a function to compute an average, which line should
be inserted where indicated so that get_average(my_d, 'mq') computes average
for all 'mq' entries? i.e. find average of all mq scores for all students.
6.100L Lecture 14
list vs dict
26
6.100L Lecture 14
EXAMPLE: FIND MOST COMMON
WORDS IN A SONG’S LYRICS
6.100L Lecture 14
CREATING A DICTIONARY
Python Tutor LINK
song = "RAH RAH AH AH AH ROM MAH RO MAH MAH"
def generate_word_dict(song):
song_words = song.lower()
words_list = song_words.split()
word_dict = {}
for w in words_list:
if w in word_dict:
word_dict[w] += 1
else:
word_dict[w] = 1
return word_dict
28
6.100L Lecture 14
USING THE DICTIONARY
Python Tutor LINK
word_dict = {'rah':2, 'ah':3, 'rom':1, 'mah':3, 'ro':1}
def find_frequent_word(word_dict):
words = []
highest = max(word_dict.values())
for k,v in word_dict.items():
if v == highest:
words.append(k)
return (words, highest)
29
6.100L Lecture 14
FIND WORDS WITH FREQUENCY
GREATER THAN x=1
Repeat the next few steps as long as the highest frequency is
greater than x
Find highest frequency
30
6.100L Lecture 14
FIND WORDS WITH FREQUENCY
GREATER THAN x=1
Use function find_frequent_word to get words with the
biggest frequency
31
6.100L Lecture 14
FIND WORDS WITH FREQUENCY
GREATER THAN x=1
Remove the entries corresponding to these words from
dictionary by mutation
freq_list = [(['ah','mah'],3)]
32
6.100L Lecture 14
FIND WORDS WITH FREQUENCY
GREATER THAN x=1
Find highest frequency in the mutated dict
freq_list = [(['ah','mah'],3)]
33
6.100L Lecture 14
FIND WORDS WITH FREQUENCY
GREATER THAN x=1
Use function find_frequent_word to get words with that
frequency
freq_list = [(['ah','mah'],3)]
34
6.100L Lecture 14
FIND WORDS WITH FREQUENCY
GREATER THAN x=1
Remove the entries corresponding to these words from
dictionary by mutation
35
6.100L Lecture 14
FIND WORDS WITH FREQUENCY
GREATER THAN x=1
The highest frequency is now smaller than x=2, so stop
36
6.100L Lecture 14
LEVERAGING DICT PROPERTIES
Python Tutor LINK
word_freq_tuple = find_frequent_word(word_dict)
freq_list.append(word_freq_tuple)
for word in word_freq_tuple[0]:
del(word_dict[word])
return freq_list
37
6.100L Lecture 14
SOME OBSERVATIONS
6.100L Lecture 14
SUMMARY
39
6.100L Lecture 14
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
40
RECURSION
(download slides and .py files to follow along)
6.100L Lecture 15
Ana Bell
1
ITERATIVE ALGORITHMS
SO FAR
Looping constructs (while and for loops) lead to
iterative algorithms
Can capture computation in a set of state variables that
update, based on a set of rules, on each iteration through
loop
What is changing each time through loop, and how?
How do I keep track of number of times through loop?
When can I stop?
Where is the result when I stop?
6.100L Lecture 15
MULTIPLICATION
6.100L Lecture 15
MULTIPLICATION
THINK in TERMS of ITERATION
Can you make this iterative?
Define a*b as a+a+a+a... b times
Write a function
6.100L Lecture 15
MULTIPLICATION –
ANOTHER ITERATIVE SOLUTION
Capture state by i i i i i
An iteration number (i) starts at b result: 0 result:
result: 2a result:
a result: 3a 4a
Update i i-1 and stop when 0
rules
A current value of computation (result) starts at 0
result result + a
6.100L Lecture 15
MULTIPLICATION
NOTICE the RECURSIVE PATTERNS
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4 is 5+5*3
But this is 5+5+5*2
And this is 5+5+5+5*1
6.100L Lecture 15
MULTIPLICATION
FIND SMALLER VERSIONS of the PROBLEM
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4
= 5+( 5*3 )
= 5+(5+( 5*2 ))
= 5+(5+(5+(5*1)))
6.100L Lecture 15
MULTIPLICATION
FIND SMALLER VERSIONS of the PROBLEM
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4
= 5+( 5*3 )
= 5+(5+( 5*2 ))
= 5+(5+(5+(5*1)))
6.100L Lecture 15
MULTIPLICATION
FIND SMALLER VERSIONS of the PROBLEM
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4
= 5+( 5*3 )
= 5+(5+( 5*2 ))
= 5+(5+(5+(5*1)))
6.100L Lecture 15
MULTIPLICATION
REACHED the END
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4
= 5+( 5*3 )
= 5+(5+( 5*2 ))
= 5+(5+(5+(5*1)))
10
6.100L Lecture 15
MULTIPLICATION
BUILD the RESULT BACK UP
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4
= 5+( 5*3 )
= 5+(5+( 5*2 ))
= 5+(5+(5+( 5 )))
11
6.100L Lecture 15
MULTIPLICATION
BUILD the RESULT BACK UP
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4
= 5+( 5*3 )
= 5+(5+( 10 ))
= 5+(5+(5+( 5 )))
12
6.100L Lecture 15
MULTIPLICATION
BUILD the RESULT BACK UP
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4
= 5+( 15 )
= 5+(5+( 10 ))
= 5+(5+(5+( 5 )))
13
6.100L Lecture 15
MULTIPLICATION –
RECURSIVE and BASE STEPS
14
6.100L Lecture 15
MULTIPLICATION –
RECURSIVE and BASE STEPS
15
6.100L Lecture 15
MULTIPLICATION – RECURSIVE
CODE Python Tutor LINK
Recursive step
• If b != 1, a*b = a + a*(b-1)
Base case
• If b = 1, a*b = a
16
6.100L Lecture 15
REAL LIFE EXAMPLE
Student requests a regrade: ONLY ONE function call
Iterative:
Student asks the prof then the TA then the LA then the grader
one-by-one until one or more regrade the exam/parts
Student iterates through everyone and keeps track of the new score
Meme girl © source unknown. Woman image ©
BC niversal. Willy Wonka © Warner
Bros. ntertainment nc. Still from Bridesmaids ©
niversal Studios. Still from Cocoon ©
niversal Studios. All rights reserved. This
content is excluded from our Creative Commons
license. For more information, see https://
ocw.mit.edu/help/faq-fair-use/
17
6.100L Lecture 15
REAL LIFE EXAMPLE
Student requests a regrade: MANY function calls
Here
you go
Recursive:
1) Student request(a function call to
regrade!): Here
Asks the prof to regrade you go
Regrade
Prof asks a TA to regrade
please?
TA asks an LA to regrade
LA asks a grader to regrade Here
you go
2) Relay the results (functions return Regrade
results to their callers): please?
Grader tells the grade to the LA
Here
LA tells the grade to the TA
you go
TA tells the grade to the prof Regrade
Prof tells the grade to the student please?
Meme girl © source unknown. Woman image © BC niversal. Willy Wonka
© Warner Bros. ntertainment nc. Still from Bridesmaids © niversal
Studios. Still from Cocoon © niversal Studios. All rights reserved. This 18
content is excluded from our Creative Commons license. For more information,
see https://ocw.mit.edu/help/faq-fair-use/ 6.100L Lecture 15
BIG IDEA
“Earlier” function calls
are waiting on results
before completing.
19
6.100L Lecture 15
WHAT IS RECURSION?
Algorithmically: a way to design solutions to problems by
divide-and-conquer or decrease-and-conquer
Reduce a problem to simpler versions of the same problem or to
problem that can be solved directly
Semantically: a programming technique where a function
calls itself
In programming, goal is to
NOT have infinite recursion
Must have 1 or more base cases
that are easy to solve directly
Must solve the same problem on
some other input with the goal of
simplifying the larger input
problem, ending at base case
20
6.100L Lecture 15
YOU TRY IT!
Complete the function that calculates np for variables n and p
21
6.100L Lecture 15
FACTORIAL
n! = n*(n-1)*(n-2)*(n-3)* … * 1
22
6.100L Lecture 15
def fact(n):
RECURSIVE if n == 1:
FUNCTION return 1
else:
SCOPE return n*fact(n-1)
EXAMPLE print(fact(4))
Global scope fact scope fact scope fact scope fact scope
(call w/ n=4) (call w/ n=3) (call w/ n=2) (call w/ n=1)
fact Some n n n n
4 3 2 1
code
23
6.100L Lecture 15
BIG IDEA
In recursion, each
function call is
completely separate.
Separate scope/environments.
Separate variable names.
Fully I-N-D-E-P-E-N-D-E-N-T
24
6.100L Lecture 15
SOME OBSERVATIONS
Python Tutor LINK for factorial
25
6.100L Lecture 15
ITERATION vs. RECURSION
26
6.100L Lecture 15
WHEN to USE RECURSION?
SO FAR WE SAW VERY SIMPLE CODE
6.100L Lecture 15
SUMMARY
Recursion is a
Programming method
Way to divide and conquer
A function calls itself
A problem is broken down into a base case and a recursive step
A base case
Something you know
You’ll eventually reach this case (if not, you have infinite recursion)
A recursive step
The same problem
Just slightly different in a way that will eventually reach the base case
28
6.100L Lecture 15
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
29
PYTHON CLASSES
(download slides and .py files to follow along)
6.100L Lecture 17
Ana Bell
1
OBJECTS
6.100L Lecture 17
OBJECT ORIENTED
PROGRAMMING (OOP)
6.100L Lecture 17
WHAT ARE OBJECTS?
6.100L Lecture 17
EXAMPLE:
[1,2,3,4] has type list
6.100L Lecture 17
REAL-LIFE EXAMPLES
6.100L Lecture 17
ADVANTAGES OF OOP
6.100L Lecture 17
BIG IDEA
You write the class so you
make the design decisions.
You decide what data represents the class.
You decide what operations a user can do with the class.
6.100L Lecture 17
Implementing the class Using the class
6.100L Lecture 17
A PARALLEL with FUNCTIONS
10
6.100L Lecture 17
COORDINATE TYPE
DESIGN DECISIONS
Can create instances of a Decide what data elements
Coordinate object constitute an object
• In a 2D plane
• A coordinate is defined by
(3 , 4) an x and y value
11
6.100L Lecture 17
Implementing the class Using the class
class Coordinate(object):
#define attributes here
6.100L Lecture 17
WHAT ARE ATTRIBUTES?
13
6.100L Lecture 17
Implementing the class Using the class
6.100L Lecture 17
Image © source unknown. All rights
reserved. This content is excluded from
our Creative Commons license. For more
information, see https://ocw.mit.edu/
WHAT is self? help/faq-fair-use/
ROOM EXAMPLE
Think of the class definition as a Now when you create ONE instance
blueprint with placeholders for (name it living_room), self becomes
actual items this actual object
self has a chair living_room has a blue chair
self has a coffee table living_room has a black table
self has a sofa living_room has a white sofa
Can make many instances using
the same blueprint
15
6.100L Lecture 17
BIG IDEA
When defining a class,
we don’t have an actual
tangible object here.
It’s only a definition.
16
6.100L Lecture 17
Implementing the class Using the class
6.100L Lecture 17
VISUALIZING INSTANCES
18
6.100L Lecture 17
VISUALIZING INSTANCES:
in memory
Make another instance using
a variable
a = 0 Type: Coordinate
c x: 3
orig = Coordinate(a,a) y: 4
orig.x a 0
19
6.100L Lecture 17
VISUALIZING INSTANCES:
draw it
class Coordinate(object):
def __init__(self, xval, yval):
self.x = xval
self.y = yval
(3 , 4)
c
c = Coordinate(3,4)
origin = Coordinate(0,0)
print(c.x)
print(origin.x)
(0 , 0)
origin
20
6.100L Lecture 17
WHAT IS A METHOD?
Procedural attribute
Think of it like a function that works only with this class
Python always passes the object as the first argument
Convention is to use self as the name of the first argument of all
methods
21
6.100L Lecture 17
Implementing the class Using the class
DEFINE A METHOD
FOR THE Coordinate CLASS
class Coordinate(object):
def __init__(self, xval, yval):
self.x = xval
self.y = yval
def distance(self, other):
x_diff_sq = (self.x-other.x)**2
y_diff_sq = (self.y-other.y)**2
return (x_diff_sq + y_diff_sq)**0.5
Other than self and dot notation, methods behave just
like functions (take params, do operations, return)
22
6.100L Lecture 17
HOW TO CALL A METHOD?
Familiar?
my_list.append(4)
my_list.sort()
23
6.100L Lecture 17
Implementing the class Using the class
6.100L Lecture 17
VISUALIZING INVOCATION
25
6.100L Lecture 17
VISUALIZING INVOCATION
6.100L Lecture 17
Implementing the class Using the class
27
6.100L Lecture 17
BIG IDEA
The . operator accesses
either data attributes or
methods.
Data attributes are defined with self.something
Methods are functions defined inside the class with self as the first parameter.
28
6.100L Lecture 17
THE POWER OF OOP
29
6.100L Lecture 17
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
30
MORE PYTHON CLASS
METHODS
(download slides and .py files to follow along)
6.100L Lecture 18
Ana Bell
1
IMPLEMENTING USING
THE CLASS vs THE CLASS
6.100L Lecture 18
RECALL THE COORDINATE CLASS
class Coordinate(object):
""" A coordinate made up of an x and y value """
def __init__(self, x, y):
""" Sets the x and y values """
self.x = x
self.y = y
def distance(self, other):
""" Returns euclidean dist between two Coord obj """
x_diff_sq = (self.x-other.x)**2
y_diff_sq = (self.y-other.y)**2
return (x_diff_sq + y_diff_sq)**0.5
6.100L Lecture 18
ADDING METHODS TO THE
COORDINATE CLASS
Methods are functions that only work with objects of this type
class Coordinate(object):
""" A coordinate made up of an x and y value """
def __init__(self, x, y):
""" Sets the x and y values """
self.x = x
self.y = y
def distance(self, other):
""" Returns euclidean dist between two Coord obj """
x_diff_sq = (self.x-other.x)**2
y_diff_sq = (self.y-other.y)**2
return (x_diff_sq + y_diff_sq)**0.5
def to_origin(self):
""" always sets self.x and self.y to 0,0 """
self.x = 0
self.y = 0
4
6.100L Lecture 18
MAKING COORDINATE INSTANCES
c = Coordinate(3,4)
origin = Coordinate(0,0)
c.to_origin()
print(c.x, c.y)
5
6.100L Lecture 18
CLASS DEFINITION INSTANCE
OF AN OBJECT TYPE vs OF A CLASS
6.100L Lecture 18
USING CLASSES TO BUILD OTHER
CLASSES
Example: use Coordinates to build Circles
Our implementation will use 2 data attributes
Coordinate object representing the center
int object representing the radius
radius
Center
coordinate
6.100L Lecture 18
CIRCLE CLASS:
DEFINITION and INSTANCES
class Circle(object):
def __init__(self, center, radius):
self.center = center
self.radius = radius
center = Coordinate(2, 2)
my_circle = Circle(center, 2)
6.100L Lecture 18
YOU TRY IT!
Add code to the init method to check that the type of center is
a Coordinate obj and the type of radius is an int. If either are
not these types, raise a ValueError.
6.100L Lecture 18
CIRCLE CLASS:
DEFINITION and INSTANCES
class Circle(object):
def __init__(self, center, radius):
self.center = center
self.radius = radius
def is_inside(self, point):
""" Returns True if point is in self, False otherwise """
return point.distance(self.center) < self.radius
center = Coordinate(2, 2)
my_circle = Circle(center, 2)
p = Coordinate(1,1)
print(my_circle.is_inside(p))
10
6.100L Lecture 18
YOU TRY IT!
Are these two methods in the Circle class functionally equivalent?
class Circle(object):
def __init__(self, center, radius):
self.center = center
self.radius = radius
11
6.100L Lecture 18
EXAMPLE:
FRACTIONS
12
6.100L Lecture 18
NEED TO CREATE INSTANCES
class SimpleFraction(object):
def __init__(self, n, d):
self.num = n
self.denom = d
13
6.100L Lecture 18
MULTIPLY FRACTIONS
class SimpleFraction(object):
def __init__(self, n, d):
self.num = n
self.denom = d
def times(self, oth):
top = self.num*oth.num
bottom = self.denom*oth.denom
return top/bottom
14
6.100L Lecture 18
ADD FRACTIONS
class SimpleFraction(object):
def __init__(self, n, d):
self.num = n
self.denom = d
………
def plus(self, oth):
top = self.num*oth.denom + self.denom*oth.num
bottom = self.denom*oth.denom
return top/bottom
15
6.100L Lecture 18
LET’S TRY IT OUT
f1 = SimpleFraction(3, 4)
f2 = SimpleFraction(1, 4)
print(f1.num) 3
print(f1.denom) 4
print(f1.plus(f2)) 1.0
print(f1.times(f2)) 0.1875
16
6.100L Lecture 18
YOU TRY IT!
Add two methods to invert fraction object according to the specs below:
class SimpleFraction(object):
""" A number represented as a fraction """
def __init__(self, num, denom):
self.num = num
self.denom = denom
def get_inverse(self):
""" Returns a float representing 1/self """
pass
def invert(self):
""" Sets self's num to denom and vice versa.
Returns None. """
pass
# Example:
f1 = SimpleFraction(3,4)
print(f1.get_inverse()) # prints 1.33333333 (note this one returns value)
f1.invert() # acts on data attributes internally, no return
print(f1.num, f1.denom) # prints 4 3
17
6.100L Lecture 18
LET’S TRY IT OUT WITH MORE
THINGS
f1 = SimpleFraction(3, 4)
f2 = SimpleFraction(1, 4)
print(f1.num) 3
print(f1.denom) 4
print(f1.plus(f2)) 1.0
print(f1.times(f2)) 0.1875
18
6.100L Lecture 18
SPECIAL OPERATORS IMPLEMENTED
WITH DUNDER METHODS
19
6.100L Lecture 18
SPECIAL OPERATORS IMPLEMENTED
WITH DUNDER METHODS
6.100L Lecture 18
PRINTING OUR OWN
DATA TYPES
21
6.100L Lecture 18
PRINT REPRESENTATION OF AN
OBJECT
>>> c = Coordinate(3,4)
>>> print(c)
<__main__.Coordinate object at 0x7fa918510488>
>>> print(c)
<3,4>
22
6.100L Lecture 18
DEFINING YOUR OWN PRINT
METHOD
class Coordinate(object):
def __init__(self, xval, yval):
self.x = xval
self.y = yval
def distance(self, other):
x_diff_sq = (self.x-other.x)**2
y_diff_sq = (self.y-other.y)**2
return (x_diff_sq + y_diff_sq)**0.5
def __str__(self):
return "<"+str(self.x)+","+str(self.y)+">"
23
6.100L Lecture 18
WRAPPING YOUR HEAD AROUND
TYPES AND CLASSES
24
6.100L Lecture 18
EXAMPLE: FRACTIONS WITH
DUNDER METHODS
25
6.100L Lecture 18
CREATE & PRINT INSTANCES
class Fraction(object):
def __init__(self, n, d):
self.num = n
self.denom = d
def __str__(self):
return str(self.num) + "/" + str(self.denom)
26
6.100L Lecture 18
LET’S TRY IT OUT
f1 = Fraction(3, 4)
f2 = Fraction(1, 4)
f3 = Fraction(5, 1)
print(f1) 3/4
print(f2) 1/4
print(f3) 5/1
Ok, but looks weird!
27
6.100L Lecture 18
YOU TRY IT!
Modify the str method to represent the Fraction as just the
numerator, when the denominator is 1. Otherwise its
representation is the numerator then a / then the denominator.
class Fraction(object):
def __init__(self, num, denom):
self.num = num
self.denom = denom
def __str__(self):
return str(self.num) + "/" + str(self.denom)
# Example:
a = Fraction(1,4)
b = Fraction(3,1)
print(a) # prints 1/4
print(b) # prints 3
28
6.100L Lecture 18
IMPLEMENTING
+-*/
float()
29
6.100L Lecture 18
COMPARING METHOD vs.
DUNDER METHOD
30
6.100L Lecture 18
LETS TRY IT OUT
a = Fraction(1,4)
b = Fraction(3,4)
print(a) 1/4
c = a * b
print(c) 3/16
31
6.100L Lecture 18
CLASSES CAN HIDE DETAILS
32
6.100L Lecture 18
BIG IDEA
Special operations we’ve
been using are just
methods behind the
scenes.
Things like:
print, len
+, *, -, /, <, >, <=, >=, ==, !=
[]
and many others!
33
6.100L Lecture 18
CAN KEEP BOTH OPTIONS BY ADDING
A METHOD TO CAST TO A float
class Fraction(object):
def __init__(self, n, d):
self.num = n
self.denom = d
………
def __float__(self):
return self.num/self.denom
c = a * b
print(c) 3/16
print(float(c)) 0.1875
34
6.100L Lecture 18
LETS TRY IT OUT SOME MORE
a = Fraction(1,4)
b = Fraction(2,3)
c = a * b
print(c) 2/12
35
6.100L Lecture 18
ADD A METHOD
class Fraction(object):
………
def reduce(self):
def gcd(n, d):
while d != 0:
(d, n) = (n%d, d)
return n
if self.denom == 0:
return None
elif self.denom == 1:
return self.num
else:
greatest_common_divisor = gcd(self.num, self.denom)
top = int(self.num/greatest_common_divisor)
bottom = int(self.denom/greatest_common_divisor)
return Fraction(top, bottom)
c = a*b
print(c) 2/12
print(c.reduce()) 1/6 36
6.100L Lecture 18
WE HAVE SOME IMPROVEMENTS TO MAKE
class Fraction(object):
…………
def reduce(self):
def gcd(n, d):
while d != 0:
(d, n) = (n%d, d)
return n
if self.denom == 0:
return None
elif self.denom == 1:
s
return self.num
else:
greatest_common_divisor = gcd(self.num, self.denom)
top = int(self.num/greatest_common_divisor)
bottom = int(self.denom/greatest_common_divisor)
return Fraction(top, bottom)
37
6.100L Lecture 18
CHECK THE TYPES, THEY’RE DIFFERENT
a = Fraction(4,1)
b = Fraction(3,9)
ar = a.reduce() 4
br = b.reduce() 1/3
38
6.100L Lecture 18
YOU TRY IT!
Modify the code to return a Fraction object when denominator
is 1
class Fraction(object):
def reduce(self):
def gcd(n, d):
while d != 0:
(d, n) = (n%d, d)
return n
if self.denom == 0:
return None
elif self.denom == 1:
return self.num
else:
greatest_common_divisor = gcd(self.num, self.denom)
top = int(self.num/greatest_common_divisor)
bottom = int(self.denom/greatest_common_divisor)
return Fraction(top, bottom)
# Example:
f1 = Fraction(5,1)
print(f1.reduce()) # prints 5/1
39
not 5
6.100L Lecture 18
WHY OOP and BUNDLING THE
DATA IN THIS WAY?
Code is organized and modular
Code is easy to maintain
It’s easy to build upon objects to make more complex objects
40
6.100L Lecture 18
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
41
INHERITANCE
(download slides and .py files to follow along)
6.100L Lecture 19
Ana Bell
1
WHY USE OOP AND
CLASSES OF OBJECTS?
Mimic real life
Group different objects part of the same type
Data attributes
How can you represent your object with data?
What it is
for a coordinate: x and y values
for an animal: age
Procedural attributes (behavior/operations/methods)
How can someone interact with the object?
What it does
for a coordinate: find distance between two
for an animal: print how long it’s been alive
6.100L Lecture 19
HOW TO DEFINE A CLASS (RECAP)
class Animal(object):
def __init__(self, age):
self.age = age
self.name = None
myanimal = Animal(3)
6.100L Lecture 19
GETTER AND SETTER METHODS
class Animal(object):
def __init__(self, age):
self.age = age
self.name = None
def __str__(self):
return "animal:"+str(self.name)+":"+str(self.age)
6.100L Lecture 19
GETTER AND SETTER METHODS
class Animal(object):
def __init__(self, age):
self.age = age
self.name = None
def __str__(self):
return "animal:"+str(self.name)+":"+str(self.age)
def get_age(self):
return self.age
def get_name(self):
return self.name
def set_age(self, newage):
self.age = newage
def set_name(self, newname=""):
self.name = newname
6.100L Lecture 19
AN INSTANCE and
DOT NOTATION (RECAP)
Instantiation creates an instance of an object
a = Animal(3)
Dot notation used to access attributes (data and methods)
though it is better to use getters and setters to access data
attributes
a.age
a.get_age()
6.100L Lecture 19
INFORMATION HIDING
6.100L Lecture 19
CHANGING INTERNAL REPRESENTATION
class Animal(object):
def __init__(self, age):
self.years = age
self.name = None
def __str__(self):
return "animal:"+str(self.name)+":"+str(self.age)
def get_age(self):
return self.years
def set_age(self, newage):
self.years = newage
a.get_age() # works
a.age # error
6.100L Lecture 19
PYTHON NOT GREAT AT
INFORMATION HIDING
11
6.100L Lecture 19
USE OUR NEW CLASS
def animal_dict(L):
""" L is a list
Returns a dict, d, mappping an int to an Animal object.
A key in d is all non-negative ints, n, in L. A value
corresponding to a key is an Animal object with n as its age. """
d = {}
for n in L:
if type(n) == int and n >= 0:
d[n] = Animal(n)
return d
L = [2,5,'a',-5,0]
12
6.100L Lecture 19
USE OUR NEW CLASS
L = [2,5,'a',-5,0]
animals = animal_dict(L)
print(animals)
13
6.100L Lecture 19
USE OUR NEW CLASS
def animal_dict(L):
""" L is a list
Returns a dict, d, mappping an int to an Animal object.
A key in d is all non-negative ints n L. A value corresponding
to a key is an Animal object with n as its age. """
d = {}
for n in L:
if type(n) == int and n >= 0:
d[n] = Animal(n)
return d
L = [2,5,'a',-5,0]
animals = animal_dict(L)
for n,a in animals.items():
print(f'key {n} with val {a}')
14
6.100L Lecture 19
YOU TRY IT!
Write a function that meets this spec.
def make_animals(L1, L2):
""" L1 is a list of ints and L2 is a list of str
L1 and L2 have the same length
Creates a list of Animals the same length as L1 and L2.
An animal object at index i has the age and name
corresponding to the same index in L1 and L2, respectively. """
#For example:
L1 = [2,5,1]
L2 = ["blobfish", "crazyant", "parafox"]
animals = make_animals(L1, L2)
print(animals) # note this prints a list of animal objects
for i in animals: # this loop prints the individual animals
print(i)
15
6.100L Lecture 19
BIG IDEA
Access data attributes
(stuff defined by self.xxx)
16
6.100L Lecture 19
HIERARCHIES
Parent class
(superclass) Animal
Child class
(subclass)
• Inherits all data and
behaviors of parent Person Cat Rabbit
class
• Add more info
• Add more behavior
• Override behavior Student
18
6.100L Lecture 19
INHERITANCE:
PARENT CLASS
class Animal(object):
def __init__(self, age):
self.age = age
self.name = None
def get_age(self):
return self.age
def get_name(self):
return self.name
def set_age(self, newage):
self.age = newage
def set_name(self, newname=""):
self.name = newname
def __str__(self):
return "animal:"+str(self.name)+":"+str(self.age)
19
6.100L Lecture 19
SUBCLASS CAT
20
6.100L Lecture 19
INHERITANCE:
SUBCLASS
class Cat(Animal):
def speak(self):
print("meow")
def __str__(self):
return "cat:"+str(self.name)+":"+str(self.age)
6.100L Lecture 19
WHICH METHOD
TO USE?
22
6.100L Lecture 19
SUBCLASS PERSON
23
6.100L Lecture 19
class Person(Animal):
def __init__(self, name, age):
Animal.__init__(self, age)
self.set_name(name)
self.friends = []
def get_friends(self):
return self.friends.copy()
def add_friend(self, fname):
if fname not in self.friends:
self.friends.append(fname)
def speak(self):
print("hello")
def age_diff(self, other):
diff = self.age - other.age
print(abs(diff), "year difference")
def __str__(self):
return "person:"+str(self.name)+":"+str(self.age)
24
6.100L Lecture 19
YOU TRY IT!
Write a function according to this spec.
def make_pets(d):
""" d is a dict mapping a Person obj to a Cat obj
Prints, on each line, the name of a person, a colon, and the
name of that person's cat """
pass
p1 = Person("ana", 86)
p2 = Person("james", 7)
c1 = Cat(1)
c1.set_name("furball")
c2 = Cat(1)
c2.set_name("fluffsphere")
d = {p1:c1, p2:c2}
make_pets(d) # prints ana:furball
# james:fluffsphere
25
6.100L Lecture 19
BIG IDEA
A subclass can
use a parent’s attributes,
override a parent’s attributes, or
define new attributes.
Attributes are either data or methods.
26
6.100L Lecture 19
SUBCLASS STUDENT
27
6.100L Lecture 19
import random
class Student(Person):
def __init__(self, name, age, major=None):
Person.__init__(self, name, age)
self.major = major
def change_major(self, major):
self.major = major
def speak(self):
r = random.random()
if r < 0.25:
print("i have homework")
elif 0.25 <= r < 0.5:
print("i need sleep")
elif 0.5 <= r < 0.75:
print("i should eat")
else:
print("i'm still zooming")
def __str__(self):
return "student:"+str(self.name)+":"+str(self.age)+":"+str(self.major)
28
6.100L Lecture 19
SUBCLASS RABBIT
29
6.100L Lecture 19
CLASS VARIABLES AND THE Rabbit
SUBCLASS
6.100L Lecture 19
RECALL THE __init__ OF Rabbit
Rabbit.tag 1
2
Age: 8
r1 Parent1: None
Parent2: None
r1 = Rabbit(8) Rid: 1
31
6.100L Lecture 19
RECALL THE __init__ OF Rabbit
Rabbit.tag 1
3
2
Age: 8
r1 Parent1: None
Parent2: None
r1 = Rabbit(8) Rid: 1
r2 = Rabbit(6)
Age: 6
r2 Parent1: None
Parent2: None
Rid: 2
32
6.100L Lecture 19
RECALL THE __init__ OF Rabbit
Rabbit.tag 1
3
2
4
Age: 8
r1 Parent1: None
Parent2: None
r1 = Rabbit(8) Rid: 1
r2 = Rabbit(6)
Age: 6
r3 = Rabbit(10) r2 Parent1: None
Parent2: None
Rid: 2
Age: 10
r3 Parent1: None
Parent2: None
Rid: 3
33
6.100L Lecture 19
Rabbit GETTER METHODS
class Rabbit(Animal):
tag = 1
def __init__(self, age, parent1=None, parent2=None):
Animal.__init__(self, age)
self.parent1 = parent1
self.parent2 = parent2
self.rid = Rabbit.tag
Rabbit.tag += 1
def get_rid(self):
return str(self.rid).zfill(5)
def get_parent1(self):
return self.parent1
def get_parent2(self):
return self.parent2
34
6.100L Lecture 19
WORKING WITH YOUR OWN
TYPES
35
6.100L Lecture 19
RECALL THE __init__ OF Rabbit
Rabbit.tag 1
3
2
4
5
Age: 8
r1 Parent1: None
Parent2: None
Rid: 1
r1 = Rabbit(8) Age: 6
r2 = Rabbit(6) r2 Parent1: None
r3 = Rabbit(10) Parent2: None
Rid: 2
r4 = r1 + r2 Age: 10
r3 Parent1: None
Parent2: None
Rid: 3
Age: 0
Parent1: obj bound to r1
r4 Parent2: obj bound to r2
36
Rid: 4
6.100L Lecture 19
SPECIAL METHOD TO COMPARE TWO
Rabbits
Decide that two rabbits are equal if they have the same two
parents
def __eq__(self, other):
parents_same = (self.p1.rid == oth.p1.rid and self.p2.rid == oth.p2.rid)
parents_opp = (self.p2.rid == oth.p1.rid and self.p1.rid == oth.p2.rid)
return parents_same or parents_opp
Compare ids of parents since ids are unique (due to class var)
Note you can’t compare objects directly
For ex. with self.parent1 == other.parent1
This calls the __eq__ method over and over until call it on None and
gives an AttributeError when it tries to do None.parent1
37
6.100L Lecture 19
BIG IDEA
Class variables are
shared between all
instances.
If one instance changes it, it’s changed for every instance.
38
6.100L Lecture 19
OBJECT ORIENTED
PROGRAMMING
Create your own collections of data
Organize information
Division of work
Access information in a consistent manner
39
6.100L Lecture 19
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
40
FITNESS TRACKER
OBJECT ORIENTED
PROGRAMMING EXAMPLE
(download slides and .py files to follow along)
6.100L Lecture 20
Ana Bell
1
IMPLEMENTING USING
THE CLASS vs THE CLASS
6.100L Lecture 20
Thanks to Sam Madden for this OOP
example (his slides have been modified)
Workout Tracker Example
Different kinds3 of workouts Apple Watch and fitness tracker screens © Apple. Fitbit © Fitbit Inc.
Garmin watch © Garmin. All rights reserved. This content is excluded
from our Creative Commons license. For more information, see
6.100L Lecture 20 https://ocw.mit.edu/help/faq-fair-use/
Fitness Tracker
© Apple. All rights reserved. This content is
excluded from our Creative Commons license. Different types of workouts
For more information, see
https://ocw.mit.edu/help/faq-fair-use/
Common properties:
Icon Kind
Date Start Time
End Time Calories
Heart Rate Distance
Swimming Specific:
Swimming Pace
Stroke Type
100 yd Splits
Running Specific:
Cadence
Running Pace
Mile Splits
Elevation
4
6.100L Lecture 20
GROUPS OF OBJECTS HAVE
ATTRIBUTES (RECAP)
Data attributes
• How can you represent your object with data?
• What it is
• for a coordinate: x and y values
• for a workout: start time, end time, calories
Functional attributes (behavior/operations/methods)
• How can someone interact with the object?
• What it does
• for a coordinate: find distance between two
• for a workout: display an information card
6.100L Lecture 20
DEFINE A SIMPLE CLASS (RECAP)
class Workout(object):
def __init__(self, start, end, calories):
self.start = start
self.end = end
self.calories = calories
self.icon = '😓😓'
self.kind = 'Workout'
6
GETTER AND SETTER METHODS (RECAP)
class Workout(object):
def __init__(self, start, end, calories):
self.start = start
self.end = end
self.calories = calories
self.icon = '😓😓'
self.kind = 'Workout'
def get_calories(self):
return self.calories
def get_start(self):
return self.start
def get_end(self):
return self.end
def set_calories(self, calories):
self.calories = calories
def set_start(self, start):
self.start = start
def set_end(self, end):
self.end = end
6.100L Lecture 20
Demo
Instance State
Class State Dictionary
Dictionary Accessed via
“self” keyword
8
6.100L Lecture 20
AN INSTANCE and
DOT NOTATION (RECAP)
my_workout.calories
my_workout.get_calories()
6.100L Lecture 20
WHY INFORMATION HIDING?
Keep the interface of your class as simple as possible
Use getters & setters, not attributes
i.e., get_calories() method NOT calories attribute
Prevents bugs due to changes in implementation
May seem inconsequential in small programs, but for
large programs complex interfaces increase the potential
for bugs
If you are writing a class for others to use, you are
committing to maintaining its interface!
10
6.100L Lecture 20
CHANGING THE CLASS
IMPLEMENTATION
11
6.100L Lecture 20
Demo
def get_calories(self):
if (calories == None):
return Workout.cal_per_hr*(self.end-self.start).total_seconds()/3600
else:
return self.calories
12
6.100L Lecture 20
ASIDE: datetime OBJECTS
OTHER PYTON LIBRARIES
Takes the string representing the date and time and converts it
to a datetime object
from dateutil import parser
start = '9/30/2021 1:35 PM'
end = '9/30/2021 1:45 PM'
start_date = parser.parse(start)
end_date = parser.parse(end)
type(start_date)
13
6.100L Lecture 20
CLASS VARIABLES LIVE IN CLASS
STATE DICTIONARY
get_calories()
my_workout start
Workout get_start()
an instance
Class get_end() end
set_calories() calories
set_start()
icon
set_end()
__init__() kind
cal_per_hr
Instance State
Class State Dictionary
Dictionary Accessed via
“self” keyword
14
6.100L Lecture 20
CLASS VARIABLES
Associate a class variable with all instances of a class
Warning: if an instance changes the class variable, it’s
changed for all instances
class Workout:
cal_per_hr = 200
def __init__(self, start, end, calories):
…
print(Workout.cal_per_hr)
print(w.cal_per_hr)
Workout.cal_per_hr = 250
print(w.cal_per_hr)
15
6.100L Lecture 20
YOU TRY IT!
Write lines of code to create two Workout objects.
One Workout object saved as variable w_one,
from Jan 1 2021 at 3:30 PM until 4 PM.
You want to estimate the calories from this workout.
Print the number of calories for w_one.
Another Workout object saved as w_two,
from Jan 1 2021 at 3:35 PM until 4 PM.
You know you burned 300 calories for this workout.
Print the number of calories for w_two.
16
6.100L Lecture 20
NEXT UP: CLASS HIERARCHIES
17
6.100L Lecture 20
HIERARCHIES Workout
Parent class
(superclass)
Outdoor Indoor
Child class Workout Workout
(subclass)
• Inherits all data and
behaviors of parent
class
• Add more info Running Swimming
• Add more behavior
• Override behavior
Treadmill Weights
18
6.100L Lecture 20
Fitness Tracker
© Apple. All rights reserved. This content is
excluded from our Creative Commons license. Different kinds of workouts
For more information, see
https://ocw.mit.edu/help/faq-fair-use/
Common properties:
Icon Kind
Date Start
Time
End Time Calories
Heart Rate Distance
Swimming Specific:
Swimming Pace
Stroke Type
100 yd Splits
Running Specific:
Cadence
Running Pace
Mile Splits
Elevation
19
6.100L Lecture 20
INHERITANCE:
PARENT CLASS
class Workout(object):
cal_per_hr = 200
def __init__(self, start, end, calories=None):
…
Everything is an object
Class object implements basic operations in Python, e.g.,
binding variables
20
6.100L Lecture 20
INHERITANCE:
SUBCLASS
class RunWorkout(Workout):
def get_elev(self):
return self.elev
def set_elev(self, e):
self.elev = e
6.100L Lecture 20
Demo
INHERITANCE REPRESENTATION
IN MEMORY
get_calories()
Workout get_start()
Class get_end()
start
RunWorkout
set_calories() instance end
set_start()
set_end() calories
__init__() icon
elev
RunWorkout get_elev()
Class
set_elev()
Accessed via
“self” keyword
22
6.100L Lecture 20
WHY USE INHERITENCE?
Improve clarity
Commonalities are explicit in parent class
Differences are explicit in subclass
Reuse code
Enhance modularity
Can pass subclasses to any method that uses parent
23
6.100L Lecture 20
SUBCLASSES REUSE PARENT CODE
return retstr
24
6.100L Lecture 20
Demo
w=Workout(…)
rw=RunWorkout(…)
sw=SwimWorkout(…)
print(w)
print(rw)
print(sw)
25
6.100L Lecture 20
WHERE CAN I USE AN INSTANCE
OF A CLASS?
26
6.100L Lecture 20
Demo
6.100L Lecture 20
YOU TRY IT!
For each line creating on object below, tell me:
What is the calories val through get_calories()
What is the elevation val through get_elev()
28
6.100L Lecture 20
Demo
OVERRIDING SUPERCLASSES
def get_calories(self):
if (self.route_gps_points != None):
dist = 0
lastP = self.routeGpsPoints[0]
for p in self.routeGpsPoints[1:]:
dist += gpsDistance(lastP,p)
lastP = p
return dist * RunWorkout.cals_per_km
else:
return super().get_calories()
29
6.100L Lecture 20
OVERRIDDEN METHODS IN
MEMORY
get_calories()
Workout get_start()
Class get_end()
start
RunWorkout
set_calories() instance end
set_start()
set_end() calories
__init__() icon
elev
RunWorkout get_elev()
Class set_elev()
get_calories() Accessed via
cals_per_km “self” keyword
30
6.100L Lecture 20
WHICH METHOD
WILL BE CALLED?
get_calories()
• Overriding: subclass methods
with same name as superclass Workout
31
6.100L Lecture 20
Demo
class Workout(object):
……
def __eq__(self, other):
return type(self) == type(other) and \
self.startDate == other.startDate and \
self.endDate == other.endDate and \
self.kind == other.kind and \
self.get_calories() == other.get_calories()
class RunWorkout(Workout):
……
def __eq__(self,other):
return super().__eq__(other) and self.elev == other.elev
32
6.100L Lecture 20
OBJECT ORIENTED DESIGN:
MORE ART THAN SCIENCE
OOP is a powerful tool for modularizing your code and grouping state
and functions together
BUT
It’s possible to overdo it
New OOP programmers often create elaborate class hierarchies
Not necessarily a good idea
Think about the users of your code
Will your decomposition make sense to them?
Because the function that is invoked is implicit in the class hierarchy, it can
sometimes be difficult to reason about control flow
The Internet is full of opinions OOP and “good software design” – you
have to develop your own taste through experience!
33
6.100L Lecture 20
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
34
TIMING PROGRAMS,
COUNTING OPERATIONS
(download slides and .py files to follow along)
6.100L Lecture 21
Ana Bell
1
WRITING EFFICIENT PROGRAMS
6.100L Lecture 21
EFFICIENCY IS IMPORTANT
6.100L Lecture 21
EVALUATING PROGRAMS
6.100L Lecture 21
ASIDE on MODULES
Call functions from inside the module using the module’s name
and dot notation
math.sin(math.pi/2)
6.100L
6.0001Lecture
LECTURE 921
TIMING
6.100L Lecture 21
TIMING A PROGRAM
tstart = time.time()
Start clock
c_to_f(37)
Call function
dt = time.time() - tstart
Stop clock
print(dt, "s,")
6.100L Lecture 21
TIMNG c_to_f
6.100L Lecture 21
TIMING mysum
6.100L Lecture 21
TIMING square
10
6.100L Lecture 21
TIMING PROGRAMS IS
INCONSISTENT
6.100L
6.0001Lecture
LECTURE 821
COUNTING
12
6.100L Lecture 21
COUNTING c_to_f 3 ops
def c_to_f(c):
OPERATIONS return c*9.0/5 + 32
6.100L Lecture 21
COUNTING c_to_f
14
6.100L Lecture 21
COUNTING mysum
15
6.100L Lecture 21
COUNTING square
16
6.100L Lecture 21
COUNTING OPERATIONS IS
INDEPENDENT OF COMPUTER
VARIATIONS, BUT …
GOAL: to evaluate different algorithms
Running “time” should vary between algorithms
Running “time” should not vary between implementations
Running “time” should not vary between computers
Running “time” should not vary between languages
Running “time” is should be predictable for small inputs
No real definition of which operations to count
6.100L
6.0001Lecture
LECTURE 821
… STILL NEED A BETTER WAY
18
6.100L Lecture 21
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
19
BIG OH and THETA
(download slides and .py files to follow along)
6.100L Lecture 22
Ana Bell
1
TIMING
6.100L Lecture 22
TIMING A PROGRAM
6.100L
6.0001Lecture
LECTURE 822
EXAMPLE: convert_to_km, compound
def convert_to_km(m):
return m * 1.609
6.100L
6.0001Lecture
LECTURE 922
CREATING AN INPUT LIST
L_N = [1]
for i in range(7):
L_N.append(L_N[-1]*10)
for N in L_N:
t = time.perf_counter()
km = convert_to_km(N)
dt = time.perf_counter()-t
print(f"convert_to_km({N}) took {dt} seconds ({1/dt}/sec)")
6.100L
6.0001Lecture
LECTURE 922
RUN IT!
convert_to_km OBSERVATIONS
6.100L Lecture 22
MEASURE TIME:
compound with a variable number of months
6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: sum over L Observation 1: Size of the input is
now the length of the list, not
how big the element numbers are.
def sum_of(L):
total = 0.0 Observation 2: average time
for elt in L: seems to increase by 10 as size of
total = total + elt argument increases by 10
return total
Observation 3: relationship
L_N = [1] between size and time only
for i in range(7): predictable for large sizes
L_N.append(L_N[-1]*10)
Observation 4: Time seems
for N in L_N: comparable to computation of
L = list(range(N)) compound
t = time.perf_counter()
s = sum_of(L)
dt = time.perf_counter()-t
print(f"sum_of({N}) took {dt} seconds ({1/dt}/sec)")
6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: find element in a list
# search each element one-by-one
def is_in(L, x):
for elt in L:
if elt==x:
return True
return False
6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: find element in a list
10
9/28/20 6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: find element in a list
11
9/28/20 6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: find element in a list
12
9/28/20 6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: find element in a list
9/28/20 6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: find element in a list
6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: diameter function
L=[(cos(0), sin(0)),
(cos(1), sin(1)),
(cos(2), sin(2)), ... ] #example numbers
def diameter(L):
farthest_dist = 0
for i in range(len(L)):
for j in range(i+1, len(L)):
p1 = L[i]
p2 = L[j]
dist = math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)
if dist > farthest_dist:
farthest_dist = dist
return farthest_dist
16
6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: diameter function
def diameter(L):
farthest_dist = 0
for i in range(len(L)):
for j in range(i+1, len(L)):
p1 = L[i]
p2 = L[j]
dist = math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)
if dist > farthest_dist:
farthest_dist = dist
return farthest_dist
17
6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: diameter function
def diameter(L):
farthest_dist = 0
for i in range(len(L)):
for j in range(i+1, len(L)):
p1 = L[i]
p2 = L[j]
dist = math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)
if dist > farthest_dist:
farthest_dist = dist
return farthest_dist
18
6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: diameter function
def diameter(L):
farthest_dist = 0
for i in range(len(L)):
for j in range(i+1, len(L)):
p1 = L[i]
p2 = L[j]
dist = math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)
if dist > farthest_dist:
farthest_dist = dist
return farthest_dist
19
6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: diameter function
def diameter(L):
farthest_dist = 0
for i in range(len(L)):
for j in range(i+1, len(L)):
p1 = L[i]
p2 = L[j]
dist = math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)
if dist > farthest_dist:
farthest_dist = dist
return farthest_dist
20
6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: diameter function
def diameter(L):
farthest_dist = 0
for i in range(len(L)):
for j in range(i+1, len(L)):
p1 = L[i]
p2 = L[j]
dist = math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)
if dist > farthest_dist:
farthest_dist = dist
return farthest_dist
21
6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: diameter function
def diameter(L):
farthest_dist = 0
for i in range(len(L)):
for j in range(i+1, len(L)):
p1 = L[i]
p2 = L[j]
dist = math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)
if dist > farthest_dist:
farthest_dist = dist
return farthest_dist
22
6.100L
6.0001Lecture
LECTURE 922
MEASURE TIME: diameter function
def diameter(L):
farthest_dist = 0
for i in range(len(L)):
for j in range(i+1, len(L)):
p1 = L[i]
p2 = L[j]
dist = math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)
if dist > farthest_dist:
farthest_dist = dist
return farthest_dist
6.100L
6.0001Lecture
LECTURE 922
PLOT OF INPUT SIZE vs. TIME TO RUN
is_in
binary_search
linear logarithmic
diameter
quadratic
24
6.100L Lecture 22
TWO DIFFERENT MACHINES
My old laptop My old desktop
Observation 1: even for the same code, the actual machine may affect speed.
Observation 2: Looking only at the relative increase in run time from a prev run,
if input is n times as big, the run time is approx. n times as long.
25
DON’T GET ME WRONG!
6.100L
6.0001Lecture
LECTURE 922
COUNTING
27
6.100L Lecture 22
COUNT OPERATIONS
convert_to_km 2 ops
Assume these steps take def convert_to_km(m):
constant time: return m * 1.609
• Mathematical operations
• Comparisons
sum_of 1+len(L)*3+1 = 3*len(L)+2 ops
• Assignments def sum_of(L):
• Accessing objects in total = 0
memory for i in L:
Count number of these total += i
operations executed as return total
function of size of input
28
6.100L
6.0001Lecture
LECTURE 822
COUNT OPERATIONS: is_in
29
6.100L
6.0001Lecture
LECTURE 922
COUNT OPERATIONS: is_in
30
6.100L
6.0001Lecture
LECTURE 922
COUNT OPERATIONS:
binary search
6.100L
6.0001Lecture
LECTURE 922
COUNT OPERATIONS
is_in testing
Observation 1: number of
for 1 element, is_in used 9 operations
operations for is_in increases by
for 10 element, is_in used 37 operations
10 as size increases by 10
for 100 element, is_in used 307 operations
for 1000 element, is_in used 3007 operations
for 10000 element, is_in used 30007 operations
for 100000 element, is_in used 300007 operations
for 1000000 element, is_in used 3000007 operations
binary_search testing
for 1 element, binary search used 15 operations Observation 2: but number
for 10 element, binary search used 85 operations of operations for binary
for 100 element, binary search used 148 operations search grows much more
for 1000 element, binary search used 211 operations slowly. Unclear at what rate.
for 10000 element, binary search used 295 operations
for 100000 element, binary search used 358 operations
for 1000000 element, binary search used
32
421 operations
10/5/20 6.100L
6.0001Lecture
LECTURE 922
PLOT OF INPUT SIZE vs. OPERATION COUNT
33
6.100L Lecture 22
PROBLEMS WITH TIMING AND COUNTING
6.100L Lecture 22
EFFICIENCY IN TERMS OF INPUT: BIG-PICTURE
RECALL mysum (one loop) and square (nested loops)
mysum(x)
What happened to the program efficiency as x increased?
10 times bigger x meant the program
Took approx. 10 times as long to run
Did approx. 10 times as many ops
Express it in an “order of” way vs. the input variable: efficiency = Order of x
square(x)
What happened to the program efficiency as x increased?
2 times bigger x meant the program
Took approx. 4 times as long to run
Did approx. 4 times as many ops
10 times bigger x meant the program
Took approx. 100 times as long to run
Did approx. 100 times as many ops
Express it in an “order of” way vs. the input variable: efficiency = Order of x2
35
6.100L Lecture 22
ORDER of GROWTH
36
6.100L Lecture 22
ORDERS OF GROWTH
It’s a notation
Evaluates programs when input is very big
Expresses the growth of program’s run time
Puts an upper bound on growth
Do not need to be precise: “order of” not “exact” growth
37
6.100L Lecture 22
A BETTER WAY
A GENERALIZED WAY WITH APPROXIMATIONS
6.100L Lecture 22
WHICH INPUT TO USE TO MEASURE EFFICIENCY
Could be an integer
-- convert_to_km(x)
Could be length of list
-- list_sum(L)
You decide when multiple parameters to a function
-- is_in(L, e)
Might be different depending on which input you consider
39
6.100L
6.0001Lecture
LECTURE 822
DIFFERENT INPUTS CHANGE HOW
THE PROGRAM RUNS
40
6.100L
6.0001Lecture
LECTURE 822
DIFFERENT INPUTS CHANGE HOW
THE PROGRAM RUNS
41
6.100L
6.0001Lecture
LECTURE 822
DIFFERENT INPUTS CHANGE HOW
THE PROGRAM RUNS
6.100L
6.0001Lecture
LECTURE 822
ASYMPTOTIC GROWTH
6.100L
6.0001Lecture
LECTURE 822
BIG O Definition
3𝑥𝑥 2 + 20𝑥𝑥 + 1 = 𝑂𝑂(𝑥𝑥 2 )
Crossover
f(x) = O(g(x)) means that g(x) times
some constant eventually always
exceeds f(x)
Eventually means above some
threshold value of x
4𝑥𝑥 2 > 3𝑥𝑥 2 + 20𝑥𝑥 + 1∀𝑥𝑥 > 20.04
44
6.100L Lecture 22
BIG O FORMALLY
A big Oh bound is an upper bound on the growth of some function
𝑓𝑓(𝑥𝑥) = 𝑂𝑂(𝒈𝒈(𝒙𝒙)) means there exist
constants 𝒄𝒄𝟎𝟎 , 𝒙𝒙𝟎𝟎 for which 𝒄𝒄𝟎𝟎 𝒈𝒈(𝒙𝒙) ≥ 𝒇𝒇(𝒙𝒙) for all 𝑥𝑥 > 𝒙𝒙𝟎𝟎
Example: 𝑓𝑓(𝑥𝑥) = 3𝑥𝑥 2 + 20𝑥𝑥 + 1
Crossover at
x=20.04 orange > blue
for all x > 20.04)
These lines
will never
cross again
0 <= x <= 30 45
0 <= x <= 100
6.100L Lecture 22
BIG Θ Definition 3𝑥𝑥 2 − 20𝑥𝑥 − 1 = 𝜃𝜃(𝑥𝑥 2 )
A big Θ bound is a lower and upper bound on the growth of some function
Suppose 𝑓𝑓(𝑥𝑥) = 3𝑥𝑥 2 − 20𝑥𝑥 − 1
𝒇𝒇(𝒙𝒙) = Θ(𝒈𝒈(𝒙𝒙)) means:
there exist constants 𝒄𝒄𝟎𝟎 , 𝑥𝑥0 for which 𝒄𝒄𝟎𝟎 𝒈𝒈(𝒙𝒙) ≥ 𝒇𝒇(𝒙𝒙) for all 𝑥𝑥 > 𝒙𝒙𝟎𝟎
and constants 𝒄𝒄𝟏𝟏 , 𝑥𝑥1 for which 𝒄𝒄𝟏𝟏 𝒈𝒈(𝒙𝒙) ≤ 𝒇𝒇(𝒙𝒙) for all 𝑥𝑥 > 𝒙𝒙𝟏𝟏
Example, 𝒇𝒇(𝒙𝒙) = Θ(𝒙𝒙𝟐𝟐 ) because 𝟒𝟒𝒙𝒙𝟐𝟐 > 𝟑𝟑𝒙𝒙𝟐𝟐 − 𝟐𝟐𝟎𝟎𝒙𝒙 − 𝟏𝟏 ∀𝑥𝑥 ≥ 𝟎𝟎 (𝒄𝒄𝟎𝟎 = 𝟒𝟒, 𝒙𝒙𝟎𝟎 = 𝟎𝟎)
and 𝟐𝟐𝒙𝒙𝟐𝟐 < 𝟑𝟑𝒙𝒙𝟐𝟐 − 𝟐𝟐𝟎𝟎𝒙𝒙 − 𝟏𝟏 ∀𝑥𝑥 ≥ 𝟐𝟐𝟏𝟏 (𝒄𝒄𝟏𝟏 = 𝟐𝟐, 𝒙𝒙𝟏𝟏 = 𝟐𝟐𝟎𝟎. 𝟎𝟎𝟒𝟒)
46
𝒇𝒇 𝒙𝒙 = 𝜣𝜣 𝒙𝒙𝟐𝟐
≠ Θ 𝑥𝑥 3 ≠ Θ 2𝑥𝑥 and anything higher order because they
upper bound but not lower bound it
47
6.100L Lecture 22
SIMPLIFICATION EXAMPLES
Θ(n2) : n2 + 2n + 2
Θ(x2) : 3x2 + 100000x + 31000
Θ(a) : log(a) + a + 4
48
6.100L
6.0001Lecture
LECTURE 822
BIG IDEA
Express Theta in terms of
the input.
Don’t just use n all the time!
49
6.100L Lecture 22
YOU TRY IT!
Θ(x) : 1000*log(x) + x
Θ(n3) : n2log(n) + n3
Θ(y) : log(y) + 0.000001y
Θ(2b) : 2b + 1000a2 + 100*b2 + 0.0001a3
Θ(a3)
Θ(2b+a3)
All could be ok, depends on the input we care about
50
6.100L Lecture 22
USING Θ TO EVALUATE YOUR
ALGORITHM
def fact_iter(n):
"""assumes n an int >= 0"""
answer = 1
while n > 1:
answer *= n
n -= 1
return answer
Number of steps: 5n + 2
Worst case asymptotic complexity: Θ(n)
Ignore additive constants
2 doesn’t matter when n is big
Ignore multiplicative constants
5 doesn’t matter if just want to know how increasing n changes time
needed
51
6.100L
6.0001Lecture
LECTURE 822
COMBINING COMPLEXITY CLASSES
LOOPS IN SERIES
Analyze statements inside functions to get order of growth
Apply some rules, focus on dominant term
6.100L
6.0001Lecture
LECTURE 822
COMBINING COMPLEXITY CLASSES
NESTED LOOPS
Analyze statements inside functions to get order of growth
Apply some rules, focus on dominant term
6.100L
6.0001Lecture
LECTURE 822
ANALYZE COMPLEXITY
def f(x):
answer = 1
for i in range(x): Outer loop is Θ(x)
for j in range(i,x): Inner loop is Θ(x)
answer += 2 Everything else is Θ(1)
return answer
54
6.100L Lecture 22
YOU TRY IT!
What is the Theta complexity of this program? Careful to
describe in terms of input
(hint: what matters with a list, size of elems of length?)
def f(L):
Lnew = []
for i in L:
Lnew.append(i**2)
return Lnew
ANSWER:
Loop: Θ(len(L))
f is Θ(len(L))
55
6.100L Lecture 22
YOU TRY IT!
What is the Theta complexity of this program?
def f(L, L1, L2):
""" L, L1, L2 are the same length """
inL1 = False
for i in range(len(L)):
if L[i] == L1[i]:
inL1 = True
inL2 = False
for i in range(len(L)):
if L[i] == L2[i]:
inL2 = True
return inL1 and inL2
ANSWER:
Loop: Θ(len(L)) + Θ(len(L))
f is Θ(len(L)) or Θ(len(L1)) or Θ(len(L2))
56
6.100L Lecture 22
COMPLEXITY CLASSES
6.100L
6.0001Lecture
LECTURE 822
COMPLEXITY GROWTH
6.100L Lecture 22
SUMMARY
6.100L Lecture 22
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
60
COMPLEXITY CLASSES
EXAMPLES
(download slides and .py files to follow along)
6.100L Lecture 23
Ana Bell
1
THETA
6.100L Lecture 23
WHERE DOES THE FUNCTION
COME FROM?
Given code, start with the input parameters. What are they?
Come up with the equation relating input to number of ops.
f = 1 + len(L1)*5 + 1 + len(L2)*5 + 2 = 5*len(L1) + 5*len(L2) + 3
If lengths are the same, f = 10*len(L) + 3
6.100L Lecture 23
WHERE DOES THE FUNCTION
COME FROM?
A quicker way: no need to come up with the exact formula.
Look for loops and anything that repeats wrt the input
parameters. Everything else is constant.
6.100L Lecture 23
COMPLEXITY CLASSES
n is the input
We want to design algorithms that are as
close to top of this hierarchy as possible
6.100L
6.0001Lecture
LECTURE 823
CONSTANT COMPLEXITY
6
CONSTANT COMPLEXITY
6.100L Lecture 23
CONSTANT COMPLEXITY:
EXAMPLE 1
6.100L Lecture 23
CONSTANT COMPLEXITY: EXAMPLE 2
def convert_to_km(m):
return m*1.609
6.100L
6.0001Lecture
LECTURE 923
CONSTANT COMPLEXITY: EXAMPLE 3
def loop(x):
y = 100
total = 0
for i in range(y):
total += x
return total
10
6.100L Lecture 23
LINEAR COMPLEXITY
11
LINEAR COMPLEXITY
12
6.100L Lecture 23
COMPLEXITY EXAMPLE 0
(with a twist)
Multiply x by y
def mul(x, y):
tot = 0
for i in range(y):
tot += x
return tot
13
6.100L
6.0001Lecture
LECTURE 923
BIG IDEA
Be careful about what
the inputs are.
14
6.100L Lecture 23
LINEAR COMPLEXITY: EXAMPLE 1
15
6.100L Lecture 23
LINEAR COMPLEXITY: EXAMPLE 2
6.100L Lecture 23
FUNNY THING ABOUT FACTORIAL
AND PYTHON
6.100L
6.0001Lecture
LECTURE 923
LINEAR COMPLEXITY: EXAMPLE 3
def fact_recur(n):
""" assume n >= 0 """
if n <= 1:
return 1
else:
return n*fact_recur(n – 1)
6.100L Lecture1023
6.0001 LECTURE
LINEAR COMPLEXITY: EXAMPLE 4
def compound(invest, interest, n_months):
total=0 Θ(n_months)
for i in range(n_months):
total = total * interest + invest Θ(1)
return total
Θ(1)*Θ(n_months) = Θ(n_months)
Θ(n) where n=n_months
If I was being thorough, then need to account for assignment
and return statements:
Θ(1) + 4*Θ(n) + Θ(1) = Θ(1 + 4*n + 1) = Θ(n) where n=n_months
19
6.100L
6.0001Lecture
LECTURE 923
COMPLEXITY OF
ITERATIVE FIBONACCI
def fib_iter(n):
Θ(1)+ Θ(1)+ Θ(n)*Θ (1)+ Θ(1)
if n == 0:
return 0 Θ(n)
elif n == 1:
return 1
else:
fib_i = 0
fib_ii = 1
for i in range(n-1):
tmp = fib_i
fib_i = fib_ii
fib_ii = tmp + fib_ii
return fib_ii
20
6.100L Lecture 23
POLYNOMIAL
COMPLEXITY
21
POLYNOMIAL COMPLEXITY
(OFTEN QUADRATIC)
Most common polynomial algorithms are quadratic, i.e.,
complexity grows with square of size of input
Commonly occurs when we have nested loops or recursive
function calls
22
6.100L Lecture 23
QUADRATIC COMPLEXITY:
EXAMPLE 1
def g(n):
""" assume n >= 0 """
x = 0
for i in range(n):
for j in range(n):
x += 1
return x
6.100L Lecture 23
QUADRATIC
COMPLEXITY: EXAMPLE 2
6.100L
6.0001Lecture
LECTURE 923
QUADRATIC
COMPLEXITY: EXAMPLE 2
25
6.100L
6.0001Lecture
LECTURE 923
QUADRATIC COMPLEXITY: EXAMPLE 3
6.100L
6.0001Lecture
LECTURE 923
QUADRATIC
COMPLEXITY: EXAMPLE 3
Overall Θ(len(L1)*len(L2))
27
6.100L
6.0001Lecture
LECTURE 923
DIAMETER COMPLEXITY
def diameter(L):
farthest_dist = 0
for i in range(len(L)):
for j in range(i+1, len(L)):
p1 = L[i]
p2 = L[j]
dist = math.sqrt( (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2 )
if dist > farthest_dist:
farthest_dist = dist
return farthest_dist
Θ(len(L)2)
28
6.100L
6.0001Lecture
LECTURE 923
YOU TRY IT!
def all_digits(nums):
""" nums is a list of numbers """
digits = [0,1,2,3,4,5,6,7,8,9]
for i in nums:
isin = False
for j in digits:
if i == j:
isin = True
break
if not isin:
return False
return True
ANSWER:
What’s the input?
Outer for loop is Θ(nums).
Inner for loop is Θ(1).
Overall: Θ(len(nums))
29
6.100L Lecture 23
YOU TRY IT!
Asymptotic complexity of f? And if L1,L2,L3 are same length?
def f(L1, L2, L3):
for e1 in L1:
for e2 in L2:
if e1 in L3 and e2 in L3 :
return True
return False
ANSWER:
Θ(len(L1))* Θ(len(L2))* Θ(len(L3)+len(L3))
Overall: Θ(len(L1)*len(L2)*len(L3))
Overall if lists equal length: Θ(len(L1)**3)
30
6.100L Lecture 23
EXPONENTIAL
COMPLEXITY
31
EXPONENTIAL COMPLEXITY
Recursive functions
where have more than
one recursive call for
each size of problem
Fibonacci
Many important
problems are inherently
exponential
Unfortunate, as cost can
be high
Will lead us to consider
approximate solutions 230 ~= 1 million
more quickly 2100 > # cycles than all the computers
in the world working for all of recorded history
32
could complete
6.100L Lecture 23
COMPLEXITY OF
RECURSIVE FIBONACCI
def fib_recur(n):
""" assumes n an int >= 0 """
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib_recur(n-1) + fib_recur(n-2)
Worst case:
Θ(2n)
33
6.100L Lecture 23
COMPLEXITY OF RECURSIVE
FIBONACCI
Fib(6)
Fib(5) Fib(4)
Fib(2) Fib(1)
6.100L Lecture 23
EXPONENTIAL COMPLEXITY: GENERATE SUBSETS
Input is [1, 2, 3]
Output is all combinations of elements of all lengths
[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
def gen_subsets(L):
if len(L) == 0:
return [[]]
extra = L[-1:]
smaller = gen_subsets(L[:-1])
new = []
for small in smaller:
new.append(small+extra)
return smaller+new
35
6.100L Lecture 23
VISUALIZING the ALGORITHM
[1,2,3]
[1,2]
[1]
def gen_subsets(L):
if len(L) == 0:
[] return [[]]
extra = L[-1:]
smaller = gen_subsets(L[:-1])
new = []
for small in smaller:
new.append(small+extra)
return smaller+new
36
6.100L Lecture 23
VISUALIZING the ALGORITHM
[1,2,3]
[1,2]
[1]
6.100L Lecture 23
VISUALIZING the ALGORITHM
[1,2,3]
[1,2]
[[],[1]]
[1]
6.100L Lecture 23
VISUALIZING the ALGORITHM
[1,2,3]
[[],[1],[2],[1,2]]
[1,2]
[[],[1]]
[1]
6.100L Lecture 23
VISUALIZING the ALGORITHM
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
[1,2,3]
[[],[1],[2],[1,2]]
[1,2]
[[],[1]]
[1]
6.100L Lecture 23
VISUALIZING the ALGORITHM
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
[1,2,3]
[1,2]
[[],[1]]
[1]
6.100L Lecture 23
EXPONENTIAL COMPLEXITY
GENERATE SUBSETS
def gen_subsets(L):
if len(L) == 0:
return [[]] Assuming append is
extra = L[-1:] constant time
smaller = gen_subsets(L[:-1])
new = []
Time to make sublists
for small in smaller: includes time to solve
new.append(small+extra) smaller problem, and
return smaller+new time needed to make a
copy of all elements in
smaller problem
42
6.100L Lecture 23
EXPONENTIAL COMPLEXITY
GENERATE SUBSETS
43
6.100L Lecture 23
LOGARITHMIC
COMPLEXITY
44
TRICKY COMPLEXITY
def digit_add(n):
""" assume n an int >= 0 """
answer = 0
s = str(n)
for c in s[::-1]:
answer += int(c)
return answer
4 2 7 1 1
45
6.100L Lecture 23
TRICKY COMPLEXITY
def digit_add(n):
""" assume n an int >= 0 """
answer = 0
s = str(n)
for c in s[::-1]:
answer += int(c)
return answer
4 2 7 7 1
46
6.100L Lecture 23
TRICKY COMPLEXITY
def digit_add(n):
""" assume n an int >= 0 """
answer = 0
s = str(n)
for c in s[::-1]:
answer += int(c)
return answer
4 2 2 7 1
47
6.100L Lecture 23
TRICKY COMPLEXITY
def digit_add(n):
""" assume n an int >= 0 """
answer = 0
s = str(n)
for c in s[::-1]:
answer += int(c)
return answer
4 4 2 7 1
48
6.100L Lecture 23
TRICKY COMPLEXITY
def digit_add(n):
""" assume n an int >= 0 """
answer = 0
s = str(n)
for c in s[::-1]:
answer += int(c)
return answer
6.100L Lecture 23
LOGARITHMIC COMPLEXITY
50
6.100L Lecture 23
LIST AND DICTIONARIES
6.100L Lecture 23
SEARCHING
ALGORITHMS
52
SEARCHING ALGORITHMS
Linear search
• Brute force search
• List does not have to be sorted
• Bisection search
• List MUST be sorted to give correct answer
• Will see two different implementations of the algorithm
53
6.100L Lecture 23
LINEAR SEARCH
ON UNSORTED LIST
6.100L Lecture 23
LINEAR SEARCH
ON UNSORTED LIST
for i in range(len(L)):
if e == L[i]:
return True
return False
6.100L Lecture 23
LINEAR SEARCH
ON SORTED LIST
56
6.100L Lecture 23
BISECTION SEARCH FOR AN
ELEMENT IN A SORTED LIST
57
6.100L Lecture 23
BISECTION SEARCH COMPLEXITY
ANALYSIS
Finish looking
through list when
1 = n/2i
So… relationship
between original
… length of list and
how many times
we divide the list:
i = log n
…
Complexity is
Θ(log n) where n
is len(L)
58
6.100L Lecture 23
BIG IDEA
Two different
implementations have
two different Θ values.
59
6.100L Lecture 23
BISECTION SEARCH
IMPLEMENTATION 1
def bisect_search1(L, e):
if L == []:
return False
elif len(L) == 1:
return L[0] == e
else:
half = len(L)//2
if L[half] > e:
return bisect_search1( L[:half], e)
else:
return bisect_search1( L[half:], e)
60
6.100L Lecture 23
COMPLEXITY OF bisect_search1
(where n is len(L))
6.100L Lecture 23
BISECTION SEARCH ALTERNATE
IMPLEMENTATION
Reduce size of
problem by factor
of 2 each step
Keep track of low
and high indices
…
to search list
Avoid copying list
… Complexity of
recursion is
Θ(log n) where n
is len(L)
62
6.100L Lecture 23
BISECTION SEARCH
IMPLEMENTATION 2
6.100L Lecture 23
COMPLEXITY OF bisect_search2
and helper (where n is len(L))
64
6.100L Lecture 23
WHEN TO SORT FIRST
AND THEN SEARCH?
65
6.100L Lecture 23
SEARCHING A SORTED LIST
-- n is len(L)
66
6.100L Lecture 23
AMORTIZED COST
-- n is len(L)
Why bother sorting first?
Sort a list once then do many searches
67
6.100L Lecture 23
COMPLEXITY CLASSES SUMMARY
Given a function f:
Only look at items in terms of the input
Look at loops
Are they in terms of the input to f?
Are there nested loops?
Look at recursive calls
How deep does the function call stack go?
Look at built-in functions
Any of them depend on the input?
68
9/28/20 6.100L
6.0001Lecture
LECTURE 923
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
69
SORTING ALGORITHMS
(download slides and .py files to follow along)
6.100L Lecture 24
Ana Bell
1
SEARCHING A SORTED LIST
-- n is len(L)
6.100L Lecture 24
AMORTIZED COST
-- n is len(L)
Why bother sorting first?
Sort a list once then do many searches
AMORTIZE cost of the sort over many searches
6.100L Lecture 24
SORTING ALGORITHMS
4
BOGO/RANDOM/MONKEY SORT
aka bogosort,
stupidsort, slowsort,
randomsort,
shotgunsort
To sort a deck of cards
• throw them in the air
• pick them up
• are they sorted?
• repeat if not sorted
6.100L Lecture 24
COMPLEXITY OF BOGO SORT
def bogo_sort(L):
while not is_sorted(L):
random.shuffle(L)
6.100L Lecture 24
BUBBLE SORT
Compare consecutive
pairs of elements
Swap elements in pair
such that smaller is first
When reach end of list,
start over again
Stop when no more
swaps have been made
6.100L Lecture 24
COMPLEXITY OF BUBBLE SORT
def bubble_sort(L):
did_swap = True
while did_swap:
did_swap = False
for j in range(1, len(L)):
if L[j-1] > L[j]:
did_swap = True
L[j],L[j-1] = L[j-1],L[j]
Inner for loop is for doing the comparisons
Outer while loop is for doing multiple passes until no
more swaps
Θ(n2) where n is len(L)
to do len(L)-1 comparisons and len(L)-1 passes
8
6.100L Lecture 24
SELECTION SORT
First step
• Extract minimum element
• Swap it with element at index 0
Second step
• In remaining sublist, extract minimum element
• Swap it with the element at index 1
Keep the left portion of the list sorted
• At ith step, first i elements in list are sorted
• All other elements are bigger than first i elements
6.100L Lecture 24
COMPLEXITY OF SELECTION SORT
def selection_sort(L):
for i in range(len(L)):
for j in range(i, len(L)):
if L[j] < L[i]:
L[i], L[j] = L[j], L[i]
6.100L Lecture 24
VARIATION ON SELECTION SORT:
don’t swap every time
11
6.100L Lecture 24
MERGE SORT
12
6.100L Lecture1024
6.0001 LECTURE
MERGE SORT
unsorted unsorted
13
6.100L Lecture 24
MERGE SORT
unsorted unsorted
14
6.100L Lecture 24
MERGE SORT
unsorted unsorted
merge merge
15
6.100L Lecture 24
MERGE SORT
sorted sorted
merge
16
6.100L Lecture 24
MERGE SORT
sorted
17
6.100L Lecture 24
MERGE SORT DEMO
6.100L Lecture1024
6.0001 LECTURE
CLOSER LOOK AT THE
MERGE STEP (EXAMPLE)
[1,2,3,4,5,12,17,18,19,20] 19
6.100L Lecture 24
MERGING SUBLISTS STEP
6.100L Lecture 24
COMPLEXITY OF
MERGING STEP
21
6.100L Lecture1024
6.0001 LECTURE
FULL MERGE SORT ALGORITHM
-- RECURSIVE
def merge_sort(L):
if len(L) < 2:
return L[:]
else:
middle = len(L)//2
left = merge_sort(L[:middle])
right = merge_sort(L[middle:])
return merge(left, right)
Divide list successively into halves
Depth-first such that conquer smallest pieces down one
branch first before moving to larger pieces
22
6.100L Lecture 24
84165920
Merge
1468 &0259
01245689
8416 5920
Merge Merge
48 &16 59 &02
1468 0259
84 16 59 20
8 4 1 6 5 9 2 0
6.100L Lecture 24
COMPLEXITY OF MERGE SORT
Each level
At first recursion level
• n/2 elements in each list, 2 lists
• One merge Θ(n) + Θ(n) = Θ(n) where n is len(L)
At second recursion level
• n/4 elements in each list, 4 lists
• Two merges Θ(n) where n is len(L)
And so on…
Dividing list in half with each recursive call gives our levels
• Θ(log n) where n is len(L)
• Like bisection search: 1 = n/2i tells us how many splits to get to one element
Each recursion level does Θ(n) work and there are Θ(log n) levels,
where n is len(L)
Overall complexity is 𝚯𝚯(n log n) where n is len(L)
24
6.100L Lecture 24
SORTING SUMMARY
-- n is len(L)
Bogo sort
• Randomness, unbounded Θ()
Bubble sort
• Θ(n2)
Selection sort
• Θ(n2)
• Guaranteed the first i elements were sorted
Merge sort
• Θ(n log n)
𝚯𝚯(n log n) is the fastest a sort can be
25
6.100L Lecture 24
COMPLEXITY SUMMARY
10/6/20 6.100L
6.0001Lecture
LECTURE 924
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
27
PLOTTING
(download slides and .py files to follow along)
6.100L Lecture 25
Ana Bell
1
WHY PLOTTING?
6.100L Lecture 25
MATPLOTLIB
6.100L Lecture 25
A SIMPLE EXAMPLE
6.100L Lecture 25
PLOTTING THE DATA
To generate a plot:
plt.plot(<x values>, <y values>)
Arguments are lists (or sequences) of numbers
Lists must be of the same length
Generates a sequence of <x, y> values on a Cartesian grid
Plotted in order, then connected with lines
Can change iPython console to generate plots in a new
window through Preferences
Inline in the console
In a new window
6.100L Lecture 25
EXAMPLE
Note how
matplotlib
automatically
fits plot within
frame
6.100L Lecture 25
ORDER OF POINTS MATTERS
Suppose I create a set of values for n and for n2, but in arbitrary
order
Python plots using the order of the points and connecting
consecutive points
6.100L Lecture 25
UNORDERED EXAMPLE
6.100L Lecture 25
SCATTER PLOT DOES NOT CONNECT DATA POINTS
6.100L Lecture 25
SHOWING ALL DATA ON ONE PLOT
10
6.100L Lecture 25
PRODUCING MULTIPLE PLOTS
Creates a new display with that name if one does not already exist
If a display with that name exists, reopens it for additional processing
11
6.100L Lecture 25
EXAMPLE CODE
12
6.100L Lecture 25
DISPLAY OF quad
13
6.100L Lecture 25
DISPLAY OF cube
14
6.100L Lecture 25
DISPLAY OF lin
15
6.100L Lecture 25
DISPLAY OF expo
Note how
matplotlib
automatically
scales to fit both
plots within frame
16
6.100L Lecture 25
A “REAL” EXAMPLE
matplotlib has
automatically
selected x and y
scales to best fit data
17
6.100L Lecture 25
A “REAL” EXAMPLE
18
6.100L Lecture 25
A “REAL” EXAMPLE
19
6.100L Lecture 25
A “REAL” EXAMPLE
20
6.100L Lecture 25
A “REAL” EXAMPLE
21
6.100L Lecture 25
ADDING GRID LINES
22
6.100L Lecture 25
LET’S ADD ANOTHER CITY
23
6.100L Lecture 25
BUT WHERE AM I?
24
6.100L Lecture 25
LET’S ADD ANOTHER CITY
25
6.100L Lecture 25
PLOT WITH TWO CURVES
Note: Python
picked different
colors for each
plot; we could
specify if we
wanted
26
6.100L Lecture 25
CONTROLLING PARAMETERS
27
6.100L Lecture 25
CONTROLLING COLOR AND STYLE
28
6.100L Lecture 25
CONTROLLING COLOR AND STYLE
29
6.100L Lecture 25
USING KEYWORDS
30
6.100L Lecture 25
CONTROLLING COLOR AND STYLE
31
6.100L Lecture 25
LINE, COLOR, MARKER OPTIONS
Line Style
- solid line
-- dashed line
-. dash dot line
: dotted line
Color Options (plus many more)
b blue
g green
r red
c cyan
m magenta
y yellow
yellow
k black
w white
white
Marker Options (plus many more)
. point
o circle
v triangle down
^ triangle up
32
* star
6.100L Lecture 25
CONTROLLING COLOR AND STYLE
33
6.100L Lecture 25
WITH MARKERS
34
6.100L Lecture 25
CONTROLLING LINE WIDTH
35
6.100L Lecture 25
MANY OTHER OPTIONS
36
6.100L Lecture 25
PLOTS WITHIN PLOTS
37
6.100L Lecture 25
AND THE PLOT THICKENS
Y scales are
different!
38
6.100L Lecture 25
PLOTS WITHIN PLOTS
39
6.100L Lecture 25
AND THE PLOT THICKENS
40
6.100L Lecture 25
LOTS OF SUBPLOTS
41
6.100L Lecture 25
AND THE PLOT THICKENS
42
6.100L Lecture 25
US POPULATION
EXAMPLE
43
6.100L Lecture 25
A MORE INTERESTING EXAMPLE
44
6.100L Lecture 25
THE INPUT FILE
USPopulation.txt
...
45
6.100L Lecture 25
PLOTTING THE DATA
46
6.100L Lecture 25
POPULATION GROWTH
Visualizing data
can expose things
not easily seen in
raw data
47
6.100L Lecture 25
CHANGING THE SCALING
48
6.100L Lecture 25
POPULATION GROWTH
49
6.100L Lecture 25
WHICH DO YOU FIND MORE INFORMATIVE?
50
6.100L Lecture 25
COUNTRY POPULATION
EXAMPLE
51
6.100L Lecture 25
THE DATA FILE
countryPops.txt
Interested in
analyzing the
population numbers.
Don’t care about
rank, country, or year.
...
52
6.100L Lecture 25
LOADING AND
PLOTTING THE DATA
53
6.100L Lecture 25
POPULATION SIZES
54
6.100L Lecture 25
STRANGE INVESTIGATION: FIRST DIGITS
55
6.100L Lecture 25
FREQUENCY OF EACH DIGIT
Benford’s Law
1
𝑃𝑃 𝑑𝑑 = 𝑙𝑙𝑙𝑙𝑙𝑙10 (1+ )
𝑑𝑑
56
6.100L Lecture 25
COMPARING CITIES
EXAMPLE
57
6.100L Lecture 25
AN EXTENDED EXAMPLE
58
6.100L Lecture 25
THE DATA FILE
temperatures.csv
...
59
6.100L Lecture 25
temperatures.csv
CITY,TEMP,DATE
EXTRACTING DATA SEATTLE,3.1,19610101
SEATTLE,0.55,19610102
SEATTLE,0,19610103
This will return a list of temperatures (in F) and a SEATTLE,4.45,19610104
corresponding list of dates for a specific city
This will calculate the average temp over every day for 55 years, for every city.
Compute
average
temperature
61
6.100L Lecture 25
AND THE TEMPERATURE IS …
Detroit, Chicago,
Boston
62
6.100L Lecture 25
BUT MORE INTERESTING TO LOOK
AT CHANGE OVER TIME
For one city, calculate the average temperature over each year.
Check that
entry is for
right year
Previous
code
Get temp
data for
year
63
6.100L Lecture 25
BUT MORE INTERESTING TO LOOK
AT CHANGE OVER TIME
Pick some cities to plot 55 temps (avg temp over each year)
64
6.100L Lecture 25
BABY IT’S COLD OUTSIDE!
65
6.100L Lecture 25
BUT WHAT IS VARIATION?
high, low, avg temps by year
66
6.100L Lecture 25
BUT WHAT IS VARIATION?
high, low, avg temps by year
67
6.100L Lecture 25
SOME CITY EXAMPLES
68
6.100L Lecture 25
USE SAME Y RANGE FOR ALL PLOTS
Fix the
display
range for
y axis
69
6.100L Lecture 25
BETTER CITY COMPARISON
70
6.100L Lecture 25
HOW MANY DAYS AT A TEMP in 1961?
Set up a list of 100 elements, making a histogram-like structure.
• Index 0 stores how many days had a temp of 0
• Index 1 stores how many days had a temp of 1
…
• Index 99 stores how many days had a temp of 99.
Create a list of
temperatures for a
specific year
Count number of
days of a
particular year for
which a specific
temperature was
the daily average
71
6.100L Lecture 25
HOW MANY DAYS AT A TEMP IN 1961?
72
6.100L Lecture 25
SAN DIEGO IS BORING?
Plot two distributions, one for 1961 and one for 2015
74
6.100L Lecture 25
OVERLAY BAR CHARTS
75
6.100L Lecture 25
OR CAN PLOT SEPARATELY
76
6.100L Lecture 25
CAN CONTROL LOTS OF OTHER THINGS
6.100L Lecture 25
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
78
LIST ACCESS, HASHING,
SIMULATIONS,
& WRAP-UP!
(download slides and .py files to follow along)
6.100L Lecture 26
Ana Bell
1
TODAY
6.100L Lecture 26
LISTS
6.100L Lecture 26
COMPLEXITY OF SOME PYTHON OPERATIONS
▪ Lists: n is len(L)
• access θ(1)
• store θ(1)
• length θ(1)
• append θ(1)
• == θ(n)
• delete θ(n)
• copy θ(n)
• reverse θ(n)
• iteration θ(n)
• in list θ(n)
6.100L Lecture 26
CONSTANT TIME LIST ACCESS
1234 … 5295
actual value
6.100L Lecture 26
CONSTANT TIME LIST ACCESS
If list is heterogeneous
Can’t store values directly (don’t all fit in 32 bits)
Use indirection to reference other objects
Store pointers to values (not value itself)
Still use consecutive set of memory locations
Still set aside 4*len(L) bytes
Still add 32*i to first location and +1 to access that location in memory
Still constant time complexity
…
value stored is pointer to
pointer to a list 5295 actual object in memory
6
6.100L Lecture 26
NAÏVE IMPLEMENTATION OF dict
6.100L Lecture 26
COMPLEXITY OF SOME PYTHON OPERATIONS
Dictionaries: n is len(d)
▪ Lists: n is len(L)
worst case (very rare)
• access θ(1)
• length θ(n)
• store θ(1)
• access θ(n)
• length θ(1)
• store θ(n)
• append θ(1)
• delete θ(n)
• == θ(n)
• iteration θ(n)
• delete θ(n)
• copy θ(n) average case
• reverse θ(n) • access θ(1)
• iteration θ(n) • store θ(1)
• in list θ(n) • delete θ(1)
• in θ(1)
• iteration θ(n)
8
6.100L Lecture 26
HASHING
6.100L Lecture 26
DICTIONARY IMPLEMENTATION
10
6.100L Lecture 26
QUERYING THE HASH FUNCTION
11
6.100L Lecture 26
HASH TABLE
12
6.100L Lecture 26
NAMES TO INDICES
1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976
2160
13
6.100L Lecture 26
A BETTER IDEA: ALLOW COLLISIONS
14
6.100L Lecture 26
Hash function:
1) Sum the letters Hash table (like a list)
2) Take mod 16 (to fit in a hash
table with 16 entries) 0 Ana: C Eve: B
1
1 + 14 + 1 = 16
16%16 = 0 2
3 Eric: A
Ana C 4
5 + 18 + 9 + 3 = 35
35%16 = 3
5
6
Eric A 7
10 + 15 + 8 + 14 = 47
47%16 = 15
8
9
John B 10
5 + 22 + 5 = 32 11
32%16 = 0
12
Eve B 13
14
15 John: B
15
6.100L Lecture 26
PROPERTIES OF A GOOD HASH
FUNCTION
6.100L Lecture 26
Hash function:
1) Sum the letters Hash table (like a list)
2) Take mod 16 (to fit in a memory
block with 16 entries) 0 Ana: C Eve: B
1
1 + 14 + 1 = 16
16%16 = 0 2
3 Eric: A
Ana C 4
5 + 18 + 9 + 3 = 35
35%16 = 3
5 [K,a,t,e]: B
6
Eric A 7
10 + 15 + 8 + 14 = 47
47%16 = 15
8
9
John B 10
5 + 22 + 5 = 32 11
32%16 = 0
12
Eve B 13
11 + 1 + 20 + 5 = 37 14
37%16 = 5 15 John: B
[K, a, t, e] B 17
6.100L Lecture 26
Hash function:
1) Sum the letters Hash table (like a list)
2) Take mod 16 (to fit in a memory
block with 16 entries) 0 Ana: C Eve: B
1
Kate changes her name to Cate. Same 2
person, different name. Look up her 3 Eric: A
grade? 4
5 [K,a,t,e]: B
6
7
8
9
10
11
12
13 ??? Not here!
3 + 1 + 20 + 5 = 29 14
29%16 = 13 15 John: B
[C, a, t, e] 18
6.100L Lecture 26
COMPLEXITY OF SOME PYTHON OPERATIONS
Dictionaries: n is len(d)
worst case (very rare)
• length θ(n)
• access θ(n)
• store θ(n)
• delete θ(n)
• iteration θ(n)
average case
• access θ(1)
• store θ(1)
• delete θ(1)
• in θ(1)
• iteration θ(n)
19
6.100L Lecture 26
SIMULATIONS
20
6.100L Lecture 26
TOPIC USEFUL FOR MANY
DOMAINS
21
6.100L Lecture 26
ROLLING A DICE
6.100L Lecture 26
THE SIMULATION CODE
def prob_dice(side):
dice = ['.',':',':.','::','::.',':::']
Nsims = 10000
count = 0
for i in range(Nsims):
roll = random.choice(dice)
if roll == side:
count += 1
print(count/Nsims)
prob_dice('.')
prob_dice('::')
23
6.100L Lecture 26
THAT’S AN EASY SIMULATION
24
6.100L Lecture 26
NEW QUESTION
NOT AS EASY MATHEMATICALLY
Observe an event and want to calculate something about it
Roll a dice 7 times, what’s the prob to get a :: at least 3 times out of 7
rolls?
Using computation, design an experiment of that event
Make a list representing die faces and randomly choose one 7 times in a
row
Face counter increments when you choose :: (keep track of this number)
Repeat the experiment K many times (simulate it!)
Repeat the prev step 10000 times.
How? Wrap the simulation in a loop!
Keep track of the outcome of your event
Count how many times out of 10000 the :: face counter >= 3
After K repetitions, report the value of interest
Divide the outcome count by 10000
25
6.100L Lecture 26
EASY TWEAK TO
EXISTING CODE
def prob_dice_atleast(Nrolls, n_at_least):
dice = ['.',':',':.','::','::.',':::']
Nsims = 10000
how_many_matched = []
for i in range(Nsims):
matched = 0
for i in range(Nrolls):
roll = random.choice(dice)
if roll == '::':
matched += 1
how_many_matched.append(matched)
count = 0
for i in how_many_matched:
if i >= n_at_least:
count += 1
print(count/len(how_many_matched))
prob_dice_atleast(7, 3)
prob_dice_atleast(1, 1)
26
6.100L Lecture 26
REAL WORLD QUESTION
VERY COMMON EXAMPLE OF HOW
USEFUL SIMULATIONS CAN BE
Water runs through a faucet somewhere
between 1 gallons per minute and
3 gallons per minute
What’s the time it takes to fill a 600 gallon pool?
Intuition?
It’s not 300 minutes (600/2)
It’s not 400 minutes (600/1 + 600/3)/2
In code:
Grab a bunch of random values between 1 and 3
Simulate the time it takes to fill a 600 gallon pool with each
randomly chose value
Print the average time it takes to fill the pool over all these
randomly chosen values
27
6.100L Lecture 26
def fill_pool(size):
flow_rate = []
fill_time = []
Npoints = 10000
for i in range(Npoints):
r = 1+2*random.random()
flow_rate.append(r)
fill_time.append(size/r)
fill_pool(600)
28
6.100L Lecture 26
PLOTTING RANDOM FILL RATES AND
CORRESPONDING TIME IT TAKES TO FILL
29
6.100L Lecture 26
PLOTTING RANDOM FILL RATES AND
CORRESPONDING TIME IT TAKES TO FILL
Random values for fill rate (sorted) Time to fill (sorted) using formula
pool_size/rate
30
6.100L Lecture 26
RESULTS
6.100L Lecture 26
WRAP-UP of 6.100L
THANK YOU FOR BEING IN THIS CLASS!
32
6.100L Lecture 26
WHAT DID YOU LEARN?
Python syntax
Flow of control
Loops, branching, exceptions
Data structures
Tuples, lists, dictionaries
Organization, decomposition, abstraction
Functions
Classes
Algorithms
Binary/bisection
Computational complexity
Big Theta notation
Searching and sorting
33
6.100L Lecture 26
YOUR EXPERIENCE
6.100L Lecture 26
WHAT’S NEXT
35
WHAT’S NEXT
6.101 fundamentals of
programming (Python)
Implementing efficient algorithms
Debugging
36
6.100L Lecture 26
WHAT’S NEXT
37
6.100L Lecture 26
WHAT’S NEXT
Other classes
(ML, algorithms, etc.)
38
6.100L Lecture 26
IT’S EASY TO FORGET WITHOUT PRACTICE!
HAPPY CODING!
39
6.100L Lecture 26
MITOpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
40