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. Then, we discussed functions, short circuit evaluation and analyzed the efficiency of the functions we saw. Finally, we talked about binary numbers (with some theory) and base conversions.
Code for printing several outputs in one cell (not part of the recitation):
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
accessing list items in constant time (given an index)
x = 10
lst = [300, x, "name", True, print, [50, 49], 3.14]
len(lst)
7
lst[0]
300
lst[len(lst) - 1]
3.14
lst
[300, 10, 'name', True, <function print>, [50, 49], 3.14]
lst[-2][1]
49
lst[-2][1] = 490
lst
[300, 10, 'name', True, <function print>, [50, 490], 3.14]
lst[4]
lst[4]("name")
<function print>
name
#empty list
empty_lst = []
len(empty_lst)
empty_lst[0]
0
--------------------------------------------------------------------------- IndexError Traceback (most recent call last) <ipython-input-10-71919d0c3d2f> in <module>() 2 empty_lst = [] 3 len(empty_lst) ----> 4 empty_lst[0] IndexError: list index out of range
List slicing creates a new list in memory. Slicing takes time that is proportional to the size of the generated slice.
lst = [x, 1, 2, 3, "name", print, True, [3.14, 2.5]]
lst[3: 8: 2]
[3, <function print>, [3.14, 2.5]]
Operator + generates a new list in memory whose items are items of two concatenated lists
lst1 = [1, 2, 3]
lst2 = [10, 20, 30]
lst_new = lst1 + lst2
lst_new
lst1
lst2
[1, 2, 3, 10, 20, 30]
[1, 2, 3]
[10, 20, 30]
How to extend an existing list?
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!!
lst1
Bad coding:
[1, 2, 3, 10, 20, 30, 10, 20, 30]
Good coding:
[1, 2, 3, 10, 20, 30]
[1, 2, 3, 10, 20, 30, 10]
[1, 2, 3, 10, 20, 30, 10, [10, 20, 30]]
[1, 2, 3, 10, 20, 30]
lst = [10, -40.5, 6]
sum(lst)
-24.5
lst = [10, -40.5, 6]
slst = sorted(lst)
print(slst)
print(lst)
lst.sort()
print(lst)
[-40.5, 6, 10] [10, -40.5, 6] [-40.5, 6, 10]
Using while loop
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
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
lst = [1, 2, 3, 4, "hi", "bye", 100]
for item in lst:
print(item)
1 2 3 4 hi bye 100
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 = grades + [grade] #BAD CODING!!
grades.append(grade)
#grades.extend([grade])
#grades += [grade]
s = sum(grades)
avg = s / count
for gr in grades:
if gr > avg:
above += 1
print(above, "grades are above the average", avg)
How many grades? 5 enter a grade: 89 enter a grade: 34 enter a grade: 84 enter a grade: 56 enter a grade: 100 3 grades are above the average 72.6
lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
lst1 = [x for x in lst if x % 3 == 0]
lst1
[0, 3, 6, 9]
lst2 = [x**2 for x in lst if x % 3 == 0]
lst2
[0, 9, 36, 81]
lst3 = ["!" for x in lst if 2*x > 10]
lst3
['!', '!', '!', '!']
lst4 = [1 for x in lst]
lst4
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
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 = grades + [grade] #BAD CODING!!
grades.append(grade)
#grades.extend([grade])
#grades += [grade]
s = sum(grades)
avg = s / count
#for gr in grades:
# if gr > avg:
# above += 1
above = len([1 for gr in grades if gr > avg])
print(above, "grades are above the average", avg)
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)
print(x)
z = max2(x, -4)
y = max2(10)
30
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-26-8388edf3d5a0> in <module>() 13 print(x) 14 z = max2(x, -4) ---> 15 y = max2(10) TypeError: max2() missing 1 required positional argument: 'b'
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
def max3_v2(a, b, c):
#max_ab = max2(a, b)
#total_max = max2(max_ab, c)
#return total_max
return max2(max2(a, b), c)
x = True or 3/0
x
y = 3/0 or True
y
True
--------------------------------------------------------------------------- ZeroDivisionError Traceback (most recent call last) <ipython-input-27-80e3f1397e6d> in <module>() 1 x = True or 3/0 2 x ----> 3 y = 3/0 or True 4 y ZeroDivisionError: division by zero
We use decimal numbers, that is, numbers in base 10. These numbers are represented using 10 digits (0-9). Binary numbers (in base 2) use two possible digits: 0-1. In general, a number in base $b$ will be represented using $b$ possible digits.
Let $x_{base 2} = a_{n-1} ... a_1 a_0$ be a binary number in base 2 with $n$ digits. The following formula returns its decimal representation: $$x_{base 10} = \sum_{0 \le k \le n-1} a_k \cdot 2^k$$
Question 1: Let $N$ be a decimal positive integer, which has $n$ bits in its binary representation. What are the possible values of $N$ (as a function of the number of bits $n$)
Question 2: Let $N$ be a decimal positive integer. How many bits ($n$) are required for representing $N$ in binary (as a function of $N$)?
Converting from decimal to binary is done by integer division and modulo operations. We saw an algorithm for converting from decimal to a general base $b$.
bin(10)
type(bin(10))
hex(161)
int("345")
int("1101", 2)
int("a1", 16)
int("a1", 2)
'0b1010'
str
'0xa1'
345
13
161
--------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-3-45b2071e6420> in <module>() 5 int("1101", 2) 6 int("a1", 16) ----> 7 int("a1", 2) ValueError: invalid literal for int() with base 2: 'a1'