cs1001.py , Tel Aviv University, Spring 2019

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

print("Bad coding:")
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

grades = []
for i in range(count):
    grade = float(input("enter a grade: "))
    #grades[i] = grade #wrong
    #grades.append(grade)
    #grades.extend([grade])
    grades += [grade] #invokes extend
    #grades = grades + [grade] #bad coding!
    
s = sum(grades)
avg = s/count

for grade in grades:
    if grade > avg:
        above += 1

print(above, "grades are above the average", avg)
How many grades? 4
enter a grade: 10
enter a grade: 78
enter a grade: 60.5
enter a grade: 92
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

grades = []
#try to replace this loop by list comprehension exp
for i in range(count):
    grade = float(input("enter a grade: "))
    #grades[i] = grade #wrong
    #grades.append(grade)
    #grades.extend([grade])
    grades += [grade] #invokes extend
    #grades = grades + [grade] #bad coding!
    
s = sum(grades)
avg = s/count


above = len([grade for grade in grades if grade > avg])

print(above, "grades are above the average", avg)
How many grades? 3
enter a grade: 100
enter a grade: 50
enter a grade: 20
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 total_max
    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 [ ]: