Topics/Material/Reading for Week 3

This week is based on Lesson 3 of the Udacity course CS101 "Introduction to Computer Science". It would be best if you sign up and watch these lectures.

We will cover:

Read Section 4.1 "Strings" of "Knights Programming".

Read Subsection 3.1.2 "Strings" of The Python Tutorial.

Read Section 4.2 "Lists" of "Knights Programming".

Read Subsection 3.1.3 "Lists" of The Python Tutorial.

Structured Data

String List
sequence of characters sequence of anything 
s='hallo'
 
p=['h','a','l','l','o']
 
s[0] # => 'h'
 
p[0] # => 'h'
 
s[2:4] # => 'll'
 
p[2:4] # => ['l','l']
 
# <list> -> [<Expression>,<Expression>,...]
[]
[3]
[1,2,3]

Lists - Programming Quiz

# Given the variable
days_in_month=[31,28,31,30,31,30,31,31,30,31,30,31]
# define a procedure, how_many_days, that takes as 
# input a number representing a month, and outputs
# the number of days in that month

Lists - Solution to Programming Quiz

# Given the variable
days_in_month=[31,28,31,30,31,30,31,31,30,31,30,31]
# define a procedure, how_many_days, that takes as 
# input a number representing a month, and outputs
# the number of days in that month

def how_many_days(month):
    return days_in_month[month - 1]

Nested Lists

mixed_up = ['apple',3,'oranges',28,[1,4,['alpha','beta']]]

Nested Lists - Programming Quiz

# Given the variable countries defined as:
#             Name    Capital  Populations (millions)
countries = [['China','Beijing',1350],
             ['India','Delhi',1210],
             ['Romania','Bucharest',21],
             ['United States','Washington',307]]

# Write code to print out the capital of India
# by accessing the array.

Nested Lists - Solution to Programming Quiz

# Given the variable countries defined as:
#             Name    Capital  Populations (millions)
countries = [['China','Beijing',1350],
             ['India','Delhi',1210],
             ['Romania','Bucharest',21],
             ['United States','Washington',307]]

# Write code to print out the capital of India
# by accessing the array.

print(countries[1][1])

Nested Lists - Programming Quiz

# Given the variable countries defined as:
#             Name    Capital  Populations (millions)
countries = [['China','Beijing',1350],
             ['India','Delhi',1210],
             ['Romania','Bucharest',21],
             ['United States','Washington',307]]

# What multiple of the population of the USA is the population 
# of China?

Nested Lists - Solution to Programming Quiz

# Given the variable countries defined as:
#             Name    Capital  Populations (millions)
countries = [['China','Beijing',1350],
             ['India','Delhi',1210],
             ['Romania','Bucharest',21],
             ['United States','Washington',307]]

# What multiple of the population of the USA is the population 
# of China?

print(countries[0][2] / countries[3][2])

Mutation - Strings are Immutalbe

s='Hello' # step 1
s='Yello' # step 2
s=s+'w'   # step 3

 step 1           
 s----->'Hello'

Mutation - Strings are Immutalbe

s='Hello' # step 1
s='Yello' # step 2
s=s+'w'   # step 3

 step 2
 s--+    'Hello'  
    |             
    +--> 'Yello'  
                  
                  

# Note: whenever a string is assigned to s, a new string is created

Mutation - Strings are Immutalbe

s='Hello' # step 1
s='Yello' # step 2
s=s+'w'   # step 3

 step 3
 s--+    'Hello'
    |
    |    'Yello'
    |
    +--> 'Yellow'

# Note: whenever a string is assigned to s, a new string is created

Mutation - Lists Are Mutable

p=['H','e','l','l','o'] # step 1
p[0]='Y'                # step 2
p.append('w')           # step 3

# step 1
       0   1   2   3   4   5
       +---+---+---+---+---+
p ---> |'H'|'e'|'l'|'l'|'o'|
       +---+---+---+---+---+

Mutation - Lists Are Mutable

p=['H','e','l','l','o'] # step 1
p[0]='Y'                # step 2
p.append('w')           # step 3

# step 2
       0   1   2   3   4   5
       +---+---+---+---+---+
p ---> |'Y'|'e'|'l'|'l'|'o'|
       +---+---+---+---+---+

# Note: no new list is created; the old list is changed ("mutated")

Mutation - Lists Are Mutable

p=['H','e','l','l','o'] # step 1
p[0]='Y'                # step 2
p.append('w')           # step 3

# step 3
       0   1   2   3   4   5   6
       +---+---+---+---+---+---+
p ---> |'Y'|'e'|'l'|'l'|'o'|'w'|
       +---+---+---+---+---+---+

# Note: no new list is created; the old list is changed ("mutated")

Yello Mutation - Lists Are Mutable

p=['H','e','l','l','o'] # step 1
p[0]='Y'                # step 2
q=p                     # step 3
q[4]='!'                # step 4

# step 1
         0   1   2   3   4   5
         +---+---+---+---+---+
p -----> |'H'|'e'|'l'|'l'|'o'|
         +---+---+---+---+---+

Yello Mutation - Lists Are Mutable

p=['H','e','l','l','o'] # step 1
p[0]='Y'                # step 2
q=p                     # step 3
q[4]='!'                # step 4

# step 2
         0   1   2   3   4   5
         +---+---+---+---+---+
p -----> |'Y'|'e'|'l'|'l'|'o'|
         +---+---+---+---+---+

Yello Mutation - Lists Are Mutable

p=['H','e','l','l','o'] # step 1
p[0]='Y'                # step 2
q=p                     # step 3
q[4]='!'                # step 4

# step 3
         0   1   2   3   4   5
         +---+---+---+---+---+
p --+--> |'Y'|'e'|'l'|'l'|'o'|
    |    +---+---+---+---+---+
    | 
q --+

# Note: both p and q point refer to the same object, whose value is the string 'Yello'

Yello Mutation - Lists Are Mutable

p=['H','e','l','l','o'] # step 1
p[0]='Y'                # step 2
q=p                     # step 3
q[4]='!'                # step 4

# step 4
         0   1   2   3   4   5
         +---+---+---+---+---+
p --+--> |'Y'|'e'|'l'|'l'|'!'|
    |    +---+---+---+---+---+
    | 
q --+

# Note: both p and q refer to the same object, which has changed its value to the string 'Yell!'

Strings vs. Lists

s='Hello'
s[0]='Y'
# 'str' object does not support item assignment

p=['H','e','l','l','o'] 
q=p
p[0]='Y'

print(p) # => Yello 
         # not surprising 

print(q) # => Yello
         # this could appear surprising because we did not use q directly

Aliasing

Different ways of refering to the same object.

Aliasing - Quiz

# What is the value of agent[2] after the
# following code runs:

spy=[0,0,7]
agent=spy
spy[2]=agent[2]+1

Aliasing - Solution to Quiz

# What is the value of agent[2] after the
# following code runs:

spy=[0,0,7]
agent=spy
spy[2]=agent[2]+1

print(agent[2]) # => 8

Lists - Programming Quiz

# Define a procedure, replace_spy,
# that takes as its input a list of
# three numbers, and modifies the
# value of the third element in the
# input list to be one more than its
# previous value.

# For instance:
spy = [0,0,7]
replace_spy(spy)
print(spy)       # => [0,0,8]

Lists - Solution to Programming Quiz

# Define a procedure, replace_spy,
# that takes as its input a list of
# three numbers, and modifies the
# value of the third element in the
# input list to be one more than its
# previous value.

def replace_spy(p):
    p[2] = p[2] + 1 # no return value

spy=[0,0,7]
replace_spy(spy)
print(spy)          # => [0,0,8]

Passing Lists (Mutable) and Integers (Immutable) to Functions

def replace_spy(p):
    p[2] = p[2] + 1 # no return value

spy=[0,0,7]
replace_spy(spy)
print(spy)          # => [0,0,8]

# compare this to 
def inc(n):
    n = n + 1       # also no return value

a=3
inc(a)
print(a)            # => 3

Cloning Lists - Programming Quiz

def replace_spy(p):
# How can you create a true clone q of p so q does not change when p is changed?
# The following obviously does not work.

p = [1,2,3]
q = p
p.append(4)

p # => [1,2,3,4]
q # => [1,2,3,4]

# How can you create a true clone q of p so q does not change when p is changed?

Cloning Lists - Programming Quiz

def replace_spy(p):
# How can you create a true clone q of p so q does not change when p is changed?

p = [1,2,3]
q = p[:]
p.append(4)

p # => [1,2,3,4]
q # => [1,2,3]

# another possibility would be 
q = p + []

List Operations

# <list>.append(<element>)
#
# <list> + <list>
#
# len(<list>)

a = [1,2,3]
a.append(4)
b = [5,6]
c = a + b
c      # => [1,2,3,4,5,6]
len(c) # => 6

List Operations - Programming Quiz + Mutation Example

# What is output after running:
p=[1,2]
q=[3,4]
p.append(q)
print(len(p))
print(p)
q[1]=5
print(p)

List Operations - Solution to Programming Quiz

# What is output after running:
p=[1,2]
q=[3,4]
p.append(q)
print(len(p)) # => 3 
print(p)      # => [1,2,[3,4]]

# mutation again !

q[1]=5 
print(p)      # => [1,2,[3,5]]

Loops on Lists - Programming Quiz

# while <test>:
#     <Block>

def print_all_elements(p):
    i = 0
    while # fill in the correct test condition:
        print(p[i])
        i = i + 1

Loops on Lists - Solution to Programming Quiz

# while <test>:
#     <Block>

def print_all_elements(p):
    i = 0
    while i < len(p):
        print(p[i])
        i = i + 1

For Loops

# for <name> in <list>:
#     <Block>

def print_all_elements(p):
    for e in p:
        print(e)

For Loops - Programming Quiz

# Define a procedure, sum_list,
# that takes as its input a
# list of numbers, and returns
# the sum of all the elements in
# the input list.

def sum_list(p):

For Loops - Solution to Programming Quiz

# Define a procedure, sum_list, that takes as its input a
# list of numbers, and returns the sum of all the elements in the input list.

def sum_list(p):
    sum = 0 
    for e in p:
        sum = sum + e
    return sum

Find Element in List - Programming Quiz

# Define a procedure, find_element, that takes as its inputs a list
# and a value of any type, and returns the index of the first element 
# in the input list that matches the value.

# If there is no matching element,
# return -1.

def find_element(list, target):

Find Element in List - Solution to Programming Quiz Using While Loop

# Define a procedure, find_element, that takes as its inputs a list
# and a value of any type, and returns the index of the first element 
# in the input list that matches the value.

# If there is no matching element,
# return -1.

def find_element(list, target):
    pos = 0
    while pos < len(list):
        if list[pos] == target:
            return pos
        pos = pos + 1
    return -1

print(find_element([1,2,3],3))               # => 2

print find_element(['alpha','beta'],'gamma') # => -1

Find Element in List - Solution to Programming Quiz Using For Loop

# Define a procedure, find_element, that takes as its inputs a list
# and a value of any type, and returns the index of the first element 
# in the input list that matches the value.

# If there is no matching element,
# return -1.

def find_element(list, target):
    pos = 0
    for e in list:
        if e == target:
            return pos
        pos = pos + 1
    return -1

print(find_element([1,2,3],3))               # => 2

print find_element(['alpha','beta'],'gamma') # => -1

Index

# <list>.index(<value>)
# if <value> is in the <list>, returns

# the first position where <value> is 
# found in <list>.
# Otherwise, produces an error.

p = [0,1,2]
print(p.index(2)) # => 2
p = [0,1,2,2,2]
print(p.index(2)) # => 2 always give the first position
print(p.index(3)) # => 3 is not in list

Find Element in List - Programming Quiz

# Define a procedure, find_element, that takes as its inputs a list
# and a value of any type, and returns the index of the first element 
# in the input list that matches the value.

# If there is no matching element,
# return -1.

def find_element(list, target):

Find Element in List - Solution Programming Quiz Using Index

# Define a procedure, find_element, that takes as its inputs a list
# and a value of any type, and returns the index of the first element 
# in the input list that matches the value.

# If there is no matching element,
# return -1.

def find_element(list, target):
    if target not in list:
        return -1
    return list.index(target)

# alternative solution

def find_element(list, target):
    if target in list:
        return list.index(target)
    else:
        return -1

Union - Programming Quiz

# Define a procedure, union,
# that takes as inputs two lists.
# It should modify the first input
# list to be the set union of the two
# lists. You may assume the first list
# is a set, that is, it contains no 
# repeated elements.

def union(first, second):

Union - Solution to Programming Quiz

# Define a procedure, union,
# that takes as inputs two lists.
# It should modify the first input
# list to be the set union of the two
# lists. You may assume the first list
# is a set, that is, it contains no 
# repeated elements.

def union(first, second):
    for e in second:
        if e not in first:
            first.append(e)
    return first

a = [1,2,3]
b = [2,4,6]
union(a,b)
print a # => [1,2,3,4,6]
print b # => [2,4,6]

Pop

# <list>.pop() -> <element>
#
# mutates the list by removing and returning its last element

Pop - Quiz

# Assume p refers to a list with two elements. 
# Which of these code fragments does not change the final value of p:

# 1                   # 3
p.append(3)           x = pop()
p.pop()               p.append(x)

# 2                   # 4
x=p.pop()             x = p.pop()
y=p.pop()             y = p.pop()
p.append(x)           p.append(y)
p.append(y)           p.append(x)

Pop - Solution Quiz

# Assume p refers to a list with two elements. 
# Which of these code fragments does not change the final value of p:

# 1                   # 3
p.append(3)           x = pop()
p.pop()               p.append(x)

# 2                   # 4
x=p.pop()             x = p.pop()
y=p.pop()             y = p.pop()
p.append(x)           p.append(y)
p.append(y)           p.append(x)

# Solution: #1, #3, #4