Recitation 2¶

We tested if a positive integer (or a range of integers) satisfies the Collatz conjecture (using "while" and "for" loops). We discussed the basics of lists, the efficiency of list operations and how to efficiently concatenate a list to another. We also demonstrated list comprehension. Finally, we discussed functions, short circuit evaluation and analyzed the efficiency of the functions we saw.

Takeaways:¶

1. Lists can be a highly modular and useful data structure. Make sure that you understand their functionality and also their limits (figuratively and literally).
2. Avoid using the + operator for extending a given list. Use += or list.extend() instead.
3. Functions can be used in one another (max2 in max3_v3) and can be composed together.
4. When analyzing a function's performance, think about the input that will cause the largest amount of work and then measure how many operations the function does.
5. Using short circuit evaluation, if e.g. you have a long "and" condition, place the part that is most easy to compute first since if it is false, all other parts of the condition will not be computed.

Code for printing several outputs in one cell (not part of the recitation):

In [13]:
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"


Collatz Conjecture¶

The Collatz Conjecture, from Wikipedia:

Start with any positive integer $n$. Each term in the Collatz sequence is obtained from the previous term as follows:

• If the previous term is even, the next term is one half the previous term: $n \to n // 2$
• If the previous term is odd, the next term is 3 times the previous term plus 1: $n \to 3\cdot n + 1$

The conjecture is that no matter what value of $n$ we start with, the sequence will always reach 1.

Check conjecture for a single number:¶

In [1]:
orig_num = int(input("Enter a positive integer to apply Collatz algorithm: "))
num = orig_num

while num > 1:
print(num, end=" ")
if num % 2 == 0:
num = num // 2
else:
num = 3*num + 1

print(num)
print(orig_num, "is OK!")


Enter a positive integer to apply Collatz algorithm: 7
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
7 is OK!


Check conjecture for a range of numbers:¶

In [2]:
limit = int(input("Check Collatz algorithm for 1 ... "))

orig_num = 1
while orig_num <= limit:
num = orig_num

while num > 1:
print(num, end=" ")
if num % 2 == 0:
num = num // 2
else:
num = 3*num + 1

print(num)
print(orig_num, "is OK!")

orig_num += 1

Check Collatz algorithm for 1 ... 8
1
1 is OK!
2 1
2 is OK!
3 10 5 16 8 4 2 1
3 is OK!
4 2 1
4 is OK!
5 16 8 4 2 1
5 is OK!
6 3 10 5 16 8 4 2 1
6 is OK!
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
7 is OK!
8 4 2 1
8 is OK!


range examples¶

In [63]:
for i in range(10):
print(i)


0
1
2
3
4
5
6
7
8
9

In [64]:
for i in range(1, 7, 2):
print(i)

1
3
5

In [71]:
for i in range(7, 1, -2):
print(i)

7
5
3


Check conjecture for a range of numbers (using "for")¶

In [72]:
limit = int(input("Check Collatz algorithm for 1 ... "))

for orig_num in range(1, limit + 1):
num = orig_num

while num > 1:
print(num, end=" ")
if num % 2 == 0:
num = num // 2
else:
num = 3*num + 1

print(num)
print(orig_num, "is OK!")


Check Collatz algorithm for 1 ... 4
1
1 is OK!
2 1
2 is OK!
3 10 5 16 8 4 2 1
3 is OK!
4 2 1
4 is OK!


Lists - Basics¶

A Python list is a collection of ordered elements. The elements can be of different types, they can include repetitions and they can even include lists.

Python allows us to check how many elements a list contains using the $len(lst)$ function, and access an element at index $i$ using the command $lst[i]$

In [9]:
x = 10
lst = [x, 1, 2, 3, "name", print, True, [3.14, 2.5]]
len(lst)
lst[4]
lst[5]
lst[5]("hello")
#lst[100]
lst[-1]
lst[-1][0]
lst[1] = 1000
lst
lst[8] = 40

hello

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-9-3054f173fc04> in <module>
10 lst[1] = 1000
11 lst
---> 12 lst[8] = 40
13

IndexError: list assignment index out of range
In [10]:
empty_lst = []
len(empty_lst)
empty_lst[0]

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-10-12a587872310> in <module>
1 empty_lst = []
2 len(empty_lst)
----> 3 empty_lst[0]

IndexError: list index out of range
In [11]:
lst = [x, 1, 2, 3, "name", print, True, [3.14, 2.5]]
lst[3: 8: 2]

Out[11]:
[3, <function print>, [3.14, 2.5]]
In [15]:
lst1 = [1, 2, 3]
lst2 = [10, 20, 30]

lst_new = lst1 + lst2
lst_new
lst1
lst2

lst1 = lst1 + lst2
lst1

print("Good coding:")
lst1 = [1, 2, 3]
lst2 = [10, 20, 30]
lst1.extend(lst2)
lst1
lst1.append(10)
lst1
lst1.append(lst2)
lst1

lst1 = [1,2,3]
lst2 = [10,20,30]
lst1 += lst2 #invokes extend!!

Out[15]:
[1, 2, 3, 10, 20, 30]
Out[15]:
[1, 2, 3]
Out[15]:
[10, 20, 30]
Bad coding:

Out[15]:
[1, 2, 3, 10, 20, 30]
Good coding:

Out[15]:
[1, 2, 3, 10, 20, 30]
Out[15]:
[1, 2, 3, 10, 20, 30, 10]
Out[15]:
[1, 2, 3, 10, 20, 30, 10, [10, 20, 30]]

Common List functions¶

We've seen the $len(\cdot)$ function, and in a sense, the indexing call $lst[i]$ is also a function. What other builtin functions does Python supply for lists?

In [85]:
lst = [10, -40.5, 6]
sum(lst)

Out[85]:
-24.5
In [86]:
lst = [10, -40.5, 6]
slst = sorted(lst)
slst
lst

lst.sort()
lst

Out[86]:
[-40.5, 6, 10]
Out[86]:
[10, -40.5, 6]
Out[86]:
[-40.5, 6, 10]

Iterating over lists¶

Using while loop

In [16]:
lst = [1, 2, 3, 4, "hi", "bye", 100]
i = 0
while i < len(lst):
print(lst[i])
i += 1

1
2
3
4
hi
bye
100


Using for loop with range

In [17]:
lst = [1, 2, 3, 4, "hi", "bye", 100]
for i in range(len(lst)):
print(lst[i])


1
2
3
4
hi
bye
100


Using for loop over elements

In [18]:
lst = [1, 2, 3, 4, "hi", "bye", 100]
for item in lst:
print(item)

1
2
3
4
hi
bye
100


Exercise: given grades, how many are there above average?¶

solution 1: using loops¶

In [87]:
count = int(input("How many grades? "))
above = 0

for i in range(count):

avg = s/count

above += 1

print(above, "grades are above the average", avg)

How many grades? 4
3 grades are above the average 60.125


list comprehension example:¶

In [22]:
lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

lst1 = [x for x in lst if x % 3 == 0]
lst1
lst2 = [x**2 for x in lst if x % 3 == 0]
lst2
lst3 = ["!" for x in lst if 2*x > 10]
lst3
lst4 = [1 for x in lst]
lst4

Out[22]:
[0, 3, 6, 9]
Out[22]:
[0, 9, 36, 81]
Out[22]:
['!', '!', '!', '!']
Out[22]:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

A list comprehension command has the following structure:

lst = [x for y in object if cond]

And is equivalent to the following piece of code:

In [19]:
lst = []
for y in object:
if cond:
lst.append(x)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-19-96fff830a03e> in <module>
1 lst = []
----> 2 for y in object:
3     if cond:
4         lst.append(x)

TypeError: 'type' object is not iterable

Solution 2: using list comprehension¶

In [90]:
count = int(input("How many grades? "))
above = 0

#try to replace this loop by list comprehension exp
for i in range(count):

avg = s/count

print(above, "grades are above the average", avg)

How many grades? 3
1 grades are above the average 56.666666666666664


Functions: max2, max3¶

In [52]:
def max2(a,b):
'''
max2(float,float)  ---> float
return the maximum od a and b
'''
if a>=b:
return a
#else:
#    return b
return b

x = max2(10,30)
x
y = max2(10)

Out[52]:
30
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-52-54b0c2131972> in <module>()
11 x = max2(10,30)
12 x
---> 13 y = max2(10)

TypeError: max2() missing 1 required positional argument: 'b'

max3¶

at most 4 comparisons¶

In [23]:
def max3_v1(a,b,c):
if a >= b and a >= c:
return a
elif b >= a and b >= c:
return b
else:
return c


at most 2 comparisons¶

In [ ]:
def max3_v2(a,b,c):
if a>=b:
if a>=c:
return a
else:
return c
else:
if b>=c:
return b
else:
return c


at most 2 comparisons¶

In [3]:
def max3_v3(a,b,c):
##    max_ab = max2(a,b)
##    total_max = max2(max_ab,c)
return max2(max2(a,b), c)


Collatz over range, with functions¶

In [4]:
def collatz(orig_num):
num = orig_num

while num > 1:
print(num, end=" ")
if num%2 == 0:
num = num//2
else:
num = 3*num+1

print(num)
print(orig_num, "is OK!")

def collatz_range(limit):
for num in range(1, limit + 1):
collatz(num)

collatz_range(6)


1
1 is OK!
2 1
2 is OK!
3 10 5 16 8 4 2 1
3 is OK!
4 2 1
4 is OK!
5 16 8 4 2 1
5 is OK!
6 3 10 5 16 8 4 2 1
6 is OK!


Short circuit evaluation¶

In [27]:
x = True or 3/0
x

x = 3/0 or True
x

Out[27]:
True
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-27-4e64ba0c63fd> in <module>
2 x
3
----> 4 x = 3/0 or True
5 x

ZeroDivisionError: division by zero
In [26]:
x = False and 3/0
x

x = True and 3/0
x

Out[26]:
False
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-26-e936951d6351> in <module>
2 x
3
----> 4 x = True and 3/0
5 x

ZeroDivisionError: division by zero
In [ ]: