MCD4710 Workbook July 22, 2020 Contents Preface 3 I Programming Fundamentals 4 1 Expressions 5 1.1 Numerical Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Boolean Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Control Flow 9 2.1 Conditionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.1 While-Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.2 For-Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.3 Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3 Sequences 20 3.1 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3 Range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4 Functions 24 5 Code Traces 31 6 Recursion 32 II Data Structures 36 7 Tables and Matrices 37 7.1 Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 7.2 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 8 Graphs 45 8.1 Paths, cycles, and connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 8.2 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 8.3 Graph Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 9 Stacks and Queues 52 III Algorithm Analysis 53 10 Invariants 54 10.1 Finding Loop Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 1 11 Computational Complexity 59 11.1 Big-Oh Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 11.2 Computational Complexity of Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 IV Additional Resources 67 12 Practice Exam Questions 68 12.1 Discussion of Theoretical Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 12.2 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 12.3 Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 13 Solutions to Practice Exam Questions 72 13.1 Solutions: Discussion of Theoretical Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 13.2 Solutions: Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 13.3 Solutions: Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 2 Preface This workbook is an additional learning resource for FIT1045 and FIT1053. This is our first semester offering a workbook, so the workbook will grow as the semester progresses. This workbook is not sufficient for the unit. You must also complete lectures, workshops, and tutorials. The workbook will be useful in tutorials during time dedicated to self-directed-learning; as a tool for identifying any gaps in your knowledge; and for providing materials with which to practice. You can use the workbook as much or as little as is useful for you. The questions in this workbook reflect the questions you can expect to see on the in-semester tests, and the final exam. The difficulty of the questions can be understood like so: 1. Clarify questions allow you to identify any misunderstandings you may have with the fundamental tools you will learn. These are very simple questions. If you can do the practice questions, there is no need to do these questions. 2. Practice questions allow you to practice the kinds of questions you will see in your tests and exam. Some will be knowledge-based, some will be problem solving. If you can do all the practice questions, you will be fully prepared for the content of the tests and exam. Always start with the practice questions, and if you cannot do them switch to clarify; if they are too easy switch to challenge. 3. Challenge questions allow you to practice questions that are more difficult than most of the questions you will see in your tests and exam. It can be difficult to problem-solve under test conditions, so practicing on questions that are more difficult than what you might expect to see can be useful. Some questions on the final exam will be similar to challenge level questions. Solutions will not be provided for Challenege questions. 4. Extension questions are questions that contain non-assessable content. They may contain a taster of material that will be taught in later units, or they may show you something cool you can do with the tool you are being taught. If you are ever confused by a workbook question, feel free to ask about it in your tutorial, on Moodle, or at a consult. Enjoy! 3 Part I Programming Fundamentals 4 1 | Expressions 1.1 Numerical Expressions Clarify What do each of these numerical expressions yield 1. 9+5 2. 7/2 3. 3**2 4. 10%3 5. 4/2 6. -9%2 7. -10%-4 8. 8//4 9. 14//5 10. 9.5//3 11. 6//3.0 12. 9.5%2 13. 8.0%3 14. 2**2**3 15. 4-3*2 16. 13/(5%3) Practice What do each of these numerical expressions yield Make sure you understand when the expression yields a float and when it yields an integer. 1. 10/(5%2) 2. 4+11%6//2**2 3. 2**(9%3+2)+12//(5.5-7.5) 4. 1*2**(3%2+2)+14//5 5. 3*2**2**(5//7+1) 6. 3+2*3**(10//5)-7 7. 7*-4**4 8. -8%-6//3 9. 3*3/-4 10. -1//-5*-8 11. 5**1-4 12. -2-7%4 13. 1+0%7-9%1 14. -8*6//2%2+-1 15. 6*8*4/-6//-4 16. 8+4+2*-3/-3 17. -9+-1%-7–8%-4 18. 9/1-7//7%9 19. 4–8*-4-5%-9 20. -8/-7*-7//-5*-9 21. 0-5-4%6//-2 22. -6%8+2+-8//-2 23. -6/8//8%8/4 24. 7–4//-4**6*9 25. -5+-2**-3**-9**2 26. -4**4%-1**2//8 27. 7**-10//2**-10/6 28. -4+2**2**3–9 29. -1**7//4*-2**4 30. -5+4+-3//-1*2 31. -2%4**3-2**9 32. -4–2+8**-7*0 5 Test 1 Test 2 Exam Challenge What do each of these numerical expressions yield 1. int(False or True)*2**2**(14//5*2%3+2)+2 Answers Write the expression in the Python shell and compare output. 6 1.2 Boolean Expressions When answering the following questions, keep in mind Python operator precedence given in the lectures, or found in the Python documentation.1 It can be helpful to think of operators with higher precedence as having brackets around them. For example, to think of False or not True and True as being False or ((not True) and True). Also keep in mind the behavior of the boolean operators given in the lectures, or found in the Python documen- tation.2 Finally, be aware of when type coercion occurs. Clarify What do each of these function calls return or boolean expressions yield 3 1. bool(3) 2. bool(”) 3. bool([0]) 4. bool(‘cat’) 5. not ‘dog’ 6. not [] What do each of these boolean expressions yield Assume each expression is self-contained and identify which will result in a NameError. Boolean operators 1. True or False 2. True and False 3. False or False 4. not True or True 5. not (True or True) 6. not not True Booleans – with short-circuiting 1. x or True 2. True or x 3. False and x 4. False or x 5. True and False or x 6. False and True or True or x Comparison operators 1. 7 <= 3 2. 2 > 2 3. 1 != 0 4. 10 < 5 < 20 5. 3 > 2 < 20 6. 2 == 2 > -4 Comparisons – with booleans 1. True == 1 2. False < 3 3. False >= 0 4. True == 6 5. True == (not not 6)4 6. False == [] Practice What do each of these boolean expressions yield Assume each expression is self-contained and identify which will result in a NameError. 1. ” or not 0 2. False or False and True or True or x 3. True or False or 2 4. 5 or True and False 5. 3>7 or 9>=15 and 4<5 or not 10==4 6. not [] and 2<2 and 'cat'or 7>4<12 1Operator precedence at url: http://docs.python.org/3/reference/expressions.html#operator-precedence 2Boolean Operator behavior at url: http://docs.python.org/3/library/stdtypes.html#boolean-operations-and-or-not. 3Truth value testing at url: http://docs.python.org/3/library/stdtypes.html#truth 4Note that == has higher precedence than not, which means brackets must be used to avoid a SyntaxError. 7 Test 1 Test 2 Exam 7. 'word'or range(1,2) or -6>=8 or -3<=-3 8. -3<=-3 or ''and -4==-1 or -4==-1 9. [] and 'word'or range(1,2) and [''] 10. -6>=8 and 0 and -3<=-3 or 'word' 11. '' and -4==-1 or -5 or range(0) 12. 2<0 and None and None or 2<0 13. not(-4>-1 or not [”] or not ‘w’or ‘word’) 14. ‘0’ and 4 or range(0) or -5 15. 0 and 3==4 or range(0) or ” 16. None and ”and 2<0 and range(1,2) 17. range(3,1) or None or [] or 'word'or '' 18. None and range(1,2) or None or -5 and -4==-1 19. 2<0 or [''] and [] or range(5,3) and 'word' 20. not([''] and -5 or -4==-1) or ''and 'word' 21. -3<=-3 and ''or -5 and '0'or range(-3, -9) 22. '0' or -4==-1 or not ('word'or 2<0 and None) 23. '' or 7 and -4==-1 and -6>=8 or [] 24. 0 and not ‘word’or ‘string’or ‘0’and -4==-1 Answers Write the expression in the Python shell and compare output. 8 2 | Control Flow 2.1 Conditionals Clarify Code trace What is the value of x after the code sequence is executed 1. x = 5 if x < 10: x = 'small' 2. x = True if x: x = 'Yay!' else: x = 'No....' 3. x = 'dog' if x == 'cat': x = 'meow' elif x == 'dog': x = 'woof' else: x = 'animal sound' 4. x = 6 if x > 10: x = ‘big’ elif x < 5: x = 'small' 5. x = 25 if x < 10: x = 'cold' elif x > 25: x = ‘hot’ elif x < 25: x = 'average ' else: x = 'perfect ' 6. x = -10 if x < 0: x = x * -1 7. a = 5 b = 8 x = 0 if a < b: x = b else: x = a 8. x = 25 if x%2 == 0: x = x // 2 if x%3 == 0: x = x // 3 if x%5 == 0: x = x // 5 Coding Write a control sequence that ... 1. sets x to the smaller of two numbers, a and b. 9 Test 1 Test 2 Exam 2. sets x to the largest of three numbers, a, b, and c. 3. sets parity to even or odd, based on the value of num. 4. sets opt to 'different', 'pair', or 'triple', based on the value of a, b, and c. 5. sets message to 'Wear {option}' based on the value of temp. The value option should be 'a jacket' if the temperature is cold, and 'sunscreen' if the temperature is hot. You may decide what temperature is hot, and what is cold. Practice Write a control sequence that ... 1. sets shape to 'triangle' or 'not triangle' given the lengths of three lines.1 2. sets type to 'equilateral', 'isosceles', or 'scalene', given the lengths of the three sides of a triangle, x, y, and z. 3. sets rounded to the decimal num rounded to the nearest integer. Follow the IEEE rounding rule ‘round to nearest, ties to even’ (i.e. if rounding x.5, round to the nearest even integer).2 4. sorts a list of three numbers.3 Answers Clarify Code trace 1. x == 'small' 2. x == 'Yay!' 3. x == 'woof' 4. x == 6 5. x == 'perfect' 6. x == 10 7. x == 8 8. x == 5 Coding 1. a = b = x = a if b < a: x = b 2. a = b = c = x = a if x < b: x = b if x < c: x = c 3. num = parity = None if num%2 == 0: parity = 'even' else: parity = 'odd' 1For three lines to make a triangle, every line must be shorter than the sum of the remaining two. 2For more information on the IEEE rounding rules, see here: http://en.wikipedia.org/wiki/IEEE_754 3Attempt after completing section Lists. 10 4. a = b = c = opt = ‘different ‘ if a == b or b == c or a == c: opt = ‘pair’ if a == b and b == c: opt = ‘triple ‘ 5. #15 or lower is cold; above 15 is hot temp = message = ‘Wear ‘ if temp <= 15: message = message + 'a jacket ' else: message = message + 'sunscreen ' Practice Note that there are many potential implementations. The answers given here are just an example of a possible implementation. 2. x = y = z = type = None if x == y and y == z: type = 'equilateral ' elif x==y or y==z or x==z: type = 'isosceles ' else: type = 'scalene ' 4. lst = [ , , ] a = lst [0] b = lst [1] c = lst [2] #correct position of a if a > b or a > c: if a > b and a > c: lst [2] = a else: lst [1] = a #correct position of b if b < a and b < c: lst [0] = b elif: if b > a and b > c: lst [2] = b #correct position of c if c < a or c < b: if c < a and c < b: lst [0] = c else: lst [1] = c 11 2.2 Loops 2.2.1 While-Loops All questions are Clarify. For Practice and higher, go to the Loops subsection. Fill in the blanks Fill in the blanks, _, so that each loop creates a list of the numbers 1 to 10. 1. x = _ lst = [] while x <= 10: lst = lst + [x] x = x + 1 2. x = 1 lst = [] while True: lst = lst + [_] x = x _ _ if x == _ : _ 3. x = 2 lst = [] while x < _: lst = lst + [x//2] x = x + _ 4. x = _ lst = [] while True: if x > _: break x = x _ _ lst = lst + [x] Coding Write a while-loop that … 1. … adds all the numbers from 1 to 100 (inclusive) and stores the total in the variable x. 2. … adds all even numbers from 1 to 50 (inclusive) and stores the total in the variable x. 3. … creates the list lst = [1,2,3,4,5,6,7,8,9]. 4. … creates the list lst = [10, 8, 6, 4, 2, 0]. 5. … creates the list lst = [1,1,1,1,1,1,1,1,1]. Use the length of the list in the while condition. 6. … creates the list lst = [1,1,1,1,1,1,1,1,1]. Use a counter. 7. … creates the list lst = [1,2,3,4,5,6,7,8,9]. Use a break statement. 8. … creates the list lst = [2,2,2,2,2,2,2,2,2]. Use a break statement. 2.2.2 For-Loops All questions are Clarify. For Practice and higher, go to the Loops subsection. This section should be done after you have completed the Range subsection. Fix the problem Identify the problem with the given loop and implement a corrected version. 1. #should add the numbers 1 to 10 total = 0 for num in range(2, 10): total = total + num 12 Test 1 Test 2 Exam 2. #should create the string n=’12345′ n = ” lst = [1,2,3,4,5] for i in range(len(lst )): n = n + str(i) 3. #should double each number in lst lst = [1,2,3,4,5] for n in lst: n = n*2 4. #should replace all ‘o’s with ‘a’s b = ‘bonono ‘ for i in range (1,6,2): b[i] = ‘a’ Coding Write a for-loop that … 1. … adds all the numbers from 1 to 100 (inclusive) and stores the total in the variable x. 2. … adds all even numbers from 1 to 50 (inclusive) and stores the total in the variable x. 3. … triples all the numbers in the given list lst. 4. … creates a list containing ten 5s. 5. … creates a list of all the even numbers that are greater than 1 and less than 100. 6. … takes a string word and creates a new string identical word but with all ‘a’s removed. 2.2.3 Loops Clarify Choose What kind of loop would you use for the following scenarios 1. Halving a number until it is smaller than 100. 2. Doubling every number in a list. 3. Summing an infinite series to estimate an irrational number. 4. Summing every digit in a string. 5. Count the frequency of a character in a string. 6. Asks for input from the user, and keeps asking until input is valid. Coding Write a while-loop with the same behaviour as the given for-loop. 1. total = 0 for num in range(55, 105, 5): total = total + num 2. x = 100 for num in range(-1, -10, -1): x = x + num 3. lst = [1, 2, 3, 4, 5, 6] total = 0 for num in lst: total = total + num 4. lst = [‘a’, ‘b’, ‘a’, ‘a’, ‘b’, ‘a’] for i in range(len(lst )): if lst[i] == ‘b’: lst[i] = ‘aa’ 13 Write a for-loop with the same behaviour as the given while-loop: 1. total = 0 num = 20 while num < 42: total = total + num num = num + 2 2. total = 0 num = 25 while num <= 100: total = total + num num = num + 25 3. lst = [2, 4, 3, 5, 2, 2, 3] i = 0 while i < len(lst): lst[i] = lst[i] // 2 i = i + 1 4. lst = ['P', 'y', 't', 'h', 'o', 'n'] word = '' i = 0 while i < len(lst): word = word + lst[i] i = i + 1 Practice Write loops with the following behaviours: 1. Generates a list containing the first 64 powers of 2. 2. Generates a list containing all the powers of 2 that are less than 1,000,000. 3. Generates a list containing the first 100 numbers of the Fibonacci sequence. I.e. [0,1,1,2,3,...].4 4. Determines whether a given list of numbers is in ascending order. 5. Finds the factorial of the given number.5 6. Finds the greatest common divisor of two given numbers. 7. Finds the lowest common multiple of two given numbers. 8. Finds the sum of all numbers in a given string. Assume numbers are positive integers. For example, '4 and 20 blackbirds' sums to 24. 9. Finds the sum of all digits in a given number. 10. Finds the mean of a list of numbers. 11. Generates the reverse of a given string. Do not use string slicing or the function reversed(). 12. Determines whether a given string is a palindrome. Do not use string slicing or the function reversed(). 13. Generates a list of all factors of a given number. 14. Generates the complement of a given binary number. For example, the complement of '110101' is '001010'. Challenge Write loops with the following behaviours: 1. Generates a list containing all the perfect numbers between 1 and 1000. I.e. it should return this list: [6, 28, 496]. A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For example, the divisors of 6 are 1, 2, 3, and 1 + 2 + 3 = 6.6 2. Generates a list of the first 100 primes. 4Read about Fibonacci numbers here: http://en.wikipedia.org/wiki/Fibonacci_number 5Read about factorials here: http://en.wikipedia.org/wiki/Factorial 6Read about perfect numbers here: http://en.wikipedia.org/wiki/Perfect_number 14 3. Checks whether the given number num is a happy number. A happy number is a number where repeatedly calculating the sum of the squares of the number’s digits leads to 1. For example, if num=28 then when the loop terminates is_happy = True; if num=22 then when the loop terminates is_happy = False.7 4. Generates a list containing all permutations of a given string. For example, ‘cat’ would generate [‘cat’, ‘cta’, ‘act’, ‘atc’, ‘tca’, ‘tac’]. 7Let s0 be our number. Let the sum of the squares of the digits of s0 be s1. Let the sum of the squares of the digits of s1 be s2. Let the sum of the squares of the digits of sn be sn+1. A number x0 is happy if there exists an n whereby xn = 1. For instance, 28 is happy as: 22 + 82 =68 62 + 82 =100 12 + 02 + 02 =1 Whereas 22 is unhappy as: 22 + 22 =8 82 =16 … and 16 is a known unhappy number. The following numbers are known unhappy numbers: 0, 4, 16, 20, 37, 42, 58, 89, or 145. Read more about happy numbers here: http://mathworld.wolfram.com/HappyNumber.html. Note that the description given here is a limited definition of happy numbers and not accurate if you are a number theory mathematician. 15 Answers While-loops Fill in the blanks 1. x = 1 lst = [] while x <= 10: lst = lst + [x] x = x + 1 2. x = 1 lst = [] while True: lst = lst + [x] x = x + 1 if x == 10: break 3. x = 2 lst = [] while x < 21: lst = lst + [x//2] x = x + 2 4. x = 0 lst = [] while True: if x > 9: break x = x + 1 lst = lst + [x] Coding 2. x = 0 num = 1 while num <= 50: if num%2 == 0: x = x + num num = num + 1 4. lst = [] num = 10 while num >= 0: lst = lst + [num] num = num – 2 6. lst = [] counter = 0 while counter < 9: lst = lst + [1] counter = counter + 1 8. lst = [] while True: if len(lst) == 9: break lst = lst + [2] For-loops Fix the problem 1. #should add the numbers 1 to 10 total = 0 for num in range(1, 11): total = total + num 2. #should create the string n='12345' n = '' lst = [1,2,3,4,5] for i in range(len(lst )): n = n + str(lst[i]) #alternative implementation n = '' lst = [1,2,3,4,5] for num in lst: n = n + str(num) 16 3. #should double each number in lst lst = [1,2,3,4,5] for i in range(len(lst )): lst[i] = lst[i]*2 4. #should replace all 'o's with 'a's b = 'bonono ' ban = '' for char in b: if char == 'o': ban = ban + 'a' else: ban = ban + char Coding 1. x = 0 for num in range(1, 101): x = x + num 2. x = 0 for num in range(0, 51, 2): x = x + num 3. lst = for i in range(len(lst )): lst[i] = lst[i]*3 4. lst = [] for _ in range (10): lst = lst + [5] 5. lst = [] for num in range(2, 100, 2): lst = lst + [num] 6. word = new = '' for char in word: if word != 'a': new = new + char Loops Clarify 1. As there is a condition to be met, should use a while-loop. 2. This can be done with a while-loop or for-loop. A for-loop will likely be simpler to implement. 3. Usually when estimating an irrational number, the intention is to get within a certain level of error. This means there is a condition to be met, so should use a while-loop. 4. This can be done with a while-loop or for-loop. A for-loop will likely be simpler to implement. 5. This can be done with a while-loop or for-loop. A for-loop will likely be simpler to implement. 6. As there is a condition to be met, should use a while-loop. For-loops to while-loops 1. total = 0 num = 55 while num <= 100: total = total + num num = num + 5 2. x = 100 num = -1 while num > -10: x = x + num num = num -1 17 3. lst = [1, 2, 3, 4, 5, 6] total = 0 i = 0 while i < len(lst): total = total + lst[i] i = i + 1 4. lst = ['a', 'b', 'a', 'a', 'b', 'a'] i = 0 while i < len(lst): if lst[i] == 'b': lst[i] = 'aa' i = i + 1 While-loops to for-loops 1. total = 0 for num in range(20, 42, 2): total = total + num 2. total = 0 for num in range(25, 125, 25): total = total + num 3. lst = [2, 4, 3, 5, 2, 2, 3] for i in range(len(lst )): lst[i] = lst[i] // 2 4. lst = ['P', 'y', 't', 'h', 'o', 'n'] word = '' for letter in lst: word = word + letter Practice Note that there are many potential implementations. The answers given here are just an example of a possible implementation. 2. lst = [] index = 0 while 2** index < 1000000: lst = lst + [2** index] index = index + 1 4. lst = in_order = True for i in range(len(lst)-1): if lst[i] > lst[i+1]: in_order = False 6. big_num = small_num = while small_num != 0: remainder = big_num % small_num big_num = small_num small_num = remainder gcd = big_num 8. string = numbers = [‘0′,’1′,’2′,’3′,’4’, ‘5’,’6′,’7′,’8′,’9′] i = 0 sum = 0 while i < len(string ): if string[i] in numbers: j = i while j < len(string) and string[j] in numbers: j = j+1 num = string[i:j] sum = sum + int(num) i = j i = i+1 10. sum = 0 for num in lst: sum = sum + num mean = sum/len(lst) 12. string = palindrome = True for i in range(len(string )//2): if string[i] != string[-(i+1)]: palindrome = False 18 14. binary = complement = '' for digit in binary: if digit == '0': complement = complement + '1' else: complement = complement + '0' 19 3 | Sequences Summary of sequence operations: Operator/Function Result Type x in seq whether x is contained in seq Boolean x not in seq whether x is not contained in seq Boolean len(seq) number of elements contained in seq integer seq[i] the ith element of seq varies seq[a:b] the sub-sequence of seq from the ath element (inclusive) to the bth element (exclusive) same as seq 3.1 Strings Summary of useful string methods:1 Operation Description str.count(sub) Returns the number of times substring sub is in string str str.find(sub) Returns the lowest index sub is in str, or 1 if not in str str.format(*args) Formats the string str str.index(sub) Returns the lowest index sub is in str, throws error if not in str str.join(iter) Returns a string which is the concatenation of the strings in iter. Strings in iter are joined by str. str.lower() Returns a copy of str with all cased characters in lower case str.split(sep) Returns a list of the words in str, using sep as the delimiter string str.strip() Removes all white space from beginning and end of str str.upper() Returns a copy of str with all cased characters in upper case Clarify Basic Operators What do each of these expressions yield Ensure you include all information. 1. 'I have '+ str(2) + 'cats.' 2. len('animals') 3. 'ing' in 'Coding is fun!' 4. 'Coding is fun!'[0] 5. 'Coding is fun!'[10:13] 6. len('Python') 7. 'FIT1045'[:3] 8. 'Hello, world.'[3:5] + 'magic'[-3:len('magic')] 1For all string methods, see here: http://docs.python.org/3.8/library/stdtypes.html#string-methods 20 Test 1 Test 2 Exam String Methods What do each of these expressions yield Ensure you include all information. 1. ‘antelopes, ants, and alpacas are all animals’.count(‘an’) 2. ‘Python’.find(‘y’) 3. ‘Hello’.find(‘y’) 4. ‘ and ‘.join([‘lions’,’tigers’,’bears’]) 5. ‘Learn Python in FIT1045’.lower() 6. ‘Do you know methods ‘.split() 7. ‘1+3+5=2’.split(‘+’) 8. ‘ Clean up… ‘.strip() Practice Evaluate What do each of these expressions yield Ensure you include all information. Which expressions throw errors or do not behave as they ought, and how can they be fixed 1. ‘One wonders on a pond’.lower().count(‘on’) 2. len(‘FIT1045,FIT1008,FIT2004,FIT3155’.split(‘,’)[2]) 3. ‘and’.join(‘7 + 9 + 4’.split(‘+’)) 4. ‘oar’.upper().join(‘fat rat sat with bat and goat at math’.split(‘at’)[2:5]) 5. ‘{} {}s’.format(‘Emit’.lower()[::-1], ‘Drawer’.lower()[::-1]) 6. ‘na’*8 + ‘batman’.upper() 7. ‘This question is number {}’.format(‘5 + 2’.split()[0] + ‘5 + 2’.split()[-1]) 8. ‘There are ‘+ 3+7 + ‘movies with Ironman.’ Code In the following questions the only strings you can use are those you are given. Write an expression that … 1. … evaluates to ‘python’ given the string string = ‘Students in FIT1045 code in Python.’ 2. … evaluates to ‘saidallinonebreath’ given the string string = ‘Said all in one breath!’ 3. … replaces all es in a string with os, given e=’e’ and o=’o’. Assume the string is string. 4. … evaluates to the given string, but with the words in reverse order. Assume the string is string. E.g. ‘This is weird.’ becomes ‘weird. is This’ Answers Write the expression in the Python shell and compare output. 21 3.2 Lists Summary of useful string methods:2 Operation Description lst.append(x) Appends item x to list lst lst.extend(iter) Extends list lst by adding all items from iterable iter lst.count(x) Returns the number of times item x is in list lst lst.insert(k,x) Inserts item x at index k in list lst lst.pop() Returns the last item in list lst and removes it from the list lst.remove(x) Removes the first occurrence of item x in list lst lst.reverse() Reverses all the items in list lst Clarify Basic Operators What do each of these expressions yield Ensure you include all information. 1. `I have ‘+ 2 + ` cats’ List Methods What do each of these expressions yield Ensure you include all information. Practice Evaluate What do each of these expressions yield Ensure you include all information. Which expressions throw errors or do not behave as they ought, and how can they be fixed 1. `I have ‘+ 2 + ` cats’ Code Answers Write the expression in the Python shell and compare output. 2For all string methods, see here: http://docs.python.org/3.8/library/stdtypes.html#string-methods 22 Test 1 Test 2 Exam 3.3 Range Clarify Evaluate What sequence of numbers is equivalent to the given ranges 1. range(6) 2. range(2,5) 3. range(4,10) 4. range(-3,5) 5. range(4,2) 6. range(2,8,2) 7. range(1,10,2) 8. range(25,5,-3) 9. range(-2,-20,-4) 10. range(10,-10,-5) 11. range(-14,-2,-3) 12. range(-4,15,6) Coding Express each of the following as a range. 1. [11,12,13,14,15] 2. [9,8,7,6,5,4] 3. [-2,-4,-6,-8,-10] 4. [-5,-4,-3,-2,-1,0,1,2,3,4,5] 5. [0,1,2,3,4,5,6,7,8,9] 6. [0,10,20,30,40,50,60,70,80] 7. [0,-4,-8,-12,-16,-20,-24] 8. -15,-10,-5,0,5,10,15,20 Practice What do each of these expressions yield 1. len(range(2,8)) 2. 3 in range(-2,5) 3. range(-7,-2)[4] 4. range(4,20)[2:5] 5. range(12,18)[-2] 6. len(range(25,-5,-4)) 7. list(range(-4,-18,-3)[2:8]) 8. list(range(3,9)[-2:-5:-1]) 9. list(range(10,20)[-5:7]) 10. list(range(5,20,3)[-4:4]) 11. len(range(17,-5,-6)) 12. 18 in range(10,20,-2) 13. list(range(0,75,5)[2:-1:3]) 14. list(range(10,60,4)[-2:1:-4] 15. range(3,12,4)[2] 16. len(range(2,-7,5)) Challenge What do each of these expressions yield 1. range(0,9,2)[:] 2. range(-2,20,5)[1:4] 3. range(3,18,2)[::2] 4. range(1,33,6)[1::2] 5. range(2,20)[-2:-10:-1] 6. range(-4,15,4)[-1:-5:-1] 7. range(-5,20,3)[-8:5:2] 8. range(100,50,-7)[1:-3:3] Answers Write the expression in the Python shell and compare output. 23 Test 1 Test 2 Exam 4 | Functions Clarify Fill in the blanks 1. #should return the sum of two numbers def sum(x, y): _ x + y 2. #should return the given string concatenated with itself _ double_string(_): _ my_string + my_string 3. #should return the sound the animal makes _ animal_sound(_): if animal == ‘cat’: _ ‘meow’ _ ‘unknown animal ‘ 4. #should return whether the number is even _ is_even(_): _ num%2 == 0 Exiting Early Rewrite the following functions to use multiple return statements, and fewer elif and else statements. 1. def factors(num): statement = ” if num%2 == 0: statement = ‘2 is the smallest non -1 factor ‘ elif num%3 == 0: statement = ‘3 is the smallest non -1 factor ‘ else: statement = ‘neither 2 nor 3 are factors ‘ return statement 2. def contains_even(lst): contains = False for num in lst: if num%2 == 0: contains = True return contains 24 Test 1 Test 2 Exam 3. def scissors_paper_rock(player1 , player2 ): result = None if player1 == player2: result = ‘Noone wins’ elif (player1 == ‘scissors ‘ and player2 == ‘paper’ or player1 == ‘paper’ and player2 == ‘rock’ or player1 == ‘rock’ and player2 == ‘scissors ‘): result = ‘Player1 wins’ else: result = ‘Player2 wins’ return result 4. def find_mode(x, y, z): mode = None if x==y or x==z: mode = x elif y==z: mode = y else: mode = (x, y, z) return mode Print vs. Return Identify which of the following code blocks will throw errors. 1. def sum(x, y): print(x + y) result = sum(2, 8) double = result *2 2. def letter_in_word(word , letter ): in_word = letter in word return in_word result = letter_in_word(‘apple’, ‘p’) print(‘Letter p in word apple: ‘ + str(result )) 3. def divide(x, y): print(x/y) result = divide (6,3) print(‘6/3 is shown above.’) 4. def double_string(string ): print(string *2) my_string = ‘phone’ result = double_string(my_string) print(my_string + ‘ doubled is ‘ + result) 25 Variable arguments Identify which of the following code blocks will throw errors. 1. def sum(*nums): total = 0 for n in nums: total = total + n return total sum(3, 7, 2) 2. def multiply(start_val , *nums): for n in nums: start_val = start_val * n return start_val multiply (10, 2, 2, 3) 3. def divide(numer , denom , *nums): total = numer/denom for n in nums: total = total / n return total divide (5) 4. def subtract (*nums): total = 0 for n in nums: total = total – n return total subtract () Sequence Unpacking Identify which of the following code blocks will throw errors. 1. def find_range(lst): minimum = min(lst) maximum = max(lst) return minimum , maximum my_min , my_max = find_range ([2, 2, 7, 1, 3, 9, 3]) 2. def move_point_up(x, y, z): return x+1, y, z x, y, z = move_point_up (2, 3, 1) 3. def move_point_right(x, y, z): return x, y+1, z new_point = move_point_right (2, 3, 1) 26 4. def move_point_down(x, y, z): return x-1, y, z x, y = move_point_down (2, 3, 1) 5. def move_point_left(x, y): return x, y-1 x, y, z = move_point_left (2, 3) 6. def move_point_left(x, y): return x, y-1 x, y, z = move_point_left (2, 3) Coding Write a function that … 1. … takes integers x and y as input, where x2. … takes integers x and y as input, and returns the minimum integer (if they are the same size, than both are the minimum). 3. … takes as input a list lst containing only 0s and 1s, and returns True if there are more 1s than 0s, else returns False. 4. … takes as input a list lst containing only numbers, and returns the list with all numbers inside it doubled. 5. … takes as input a list lst containing exactly five numbers, and returns True if there are three or more identical numbers in a row, else returns False. 6. … takes as input a string word, and returns a new string identical to word but with all vowels removed (a,e,i,o,u). Practice Write a function that … 1. … takes as input three integers, date, month, year, and returns True if the three integers make a valid date, else returns False. 2. … takes as input a list numbers containing exactly five numbers, and returns an integer that is the maximum number of identical numbers in a row. 3. … takes as input a list numbers containing only numbers, and an integer n, and returns the sum of every nth number in numbers. Keep an eye on this section. It will likely grow over the semester. 27 Answers Clarify Fill in the blanks 1. #should return the sum of two numbers def sum(x, y): return x + y 2. #should return the given string concatenated with itself def double_strin
