lec2.pdf

Extended Introduction to Computer Science CS1001.py Chapter A Acquaintance with Python Lecture 2 (cont.) Michal Kleinbort, Elhanan Borenstein School of Computer Science Tel-Aviv University...

Extended Introduction to Computer Science CS1001.py Chapter A Acquaintance with Python Lecture 2 (cont.) Michal Kleinbort, Elhanan Borenstein School of Computer Science Tel-Aviv University Spring Semester 2024 http://tau-cs1001-py.wikidot.com * Slides based on a course designed by Prof. Benny Chor  Last Time Programing (high level) language → machine code IDLE Python basics: ▪ Types (int, float, str) ▪ Variables ▪ operators ▪ Conditionals 2  This Lecture More on variables, types and operators – Type bool (Boolean) – Logical operators (and, or, not) – Comparison operators (=, ==, !=) Loops (while, for) Collections – (Type str) – Type range – Type list 3  ‫* ‪Comic Relief‬‬ ‫* אנו מזמינים אתכם לשלוח לנו הצעות לתמונות שיופיעו על שקפים אלו לאורך הסמסטר‬ ‫‪4‬‬  Boolean Type Boolean values are either true or false. Note that Python’s True and False are capitalized, while in most other programming languages they are not. George Boole 1815-1864 The standard logical operators and, or, not can be applied to them and generate complex Boolean expressions from “atomic” ones. 5  Boolean Type and Logical Operators >>> a = True >>> b = True Binary ops >>> c = False >>> a and b True >>> a and c False >>> a or c True >>> a or False True >>> not a False Unary op 6  More on Boolean Type We could settle with only and and not: not (a or b) is equivalent to (not a) and (not b) You may have seen this equivalence in the Discrete Math course (De Morgan rules): A∨𝐵 ≡𝐴∧𝐵 Similarly, we could settle with or and not. In fact, either combination is universal, meaning that it is enough to represent any logical operator of 1 or more variables (you may prove this claim in the “computer 7 structure” course)  Exclusive Or (XOR) Python does not have a built-in Boolean xor (exclusive or) operator, which is a highly useful operator: >>> a = True >>> b = True >>> c = False a xor b >>> (a and (not b)) or ((not a) and b) False >>> (a and (not c)) or ((not a) and c) a xor c True 8  Exclusive Or (XOR) >>> (a and (not b)) or ((not a) and b) False >>> (a and (not c)) or ((not a) and c) True It is annoying and time consuming to write and rewrite the same expression with different variables. We will address this issue when we discuss functions (in the next lecture). Then we will be able to write: >>> xor(a, b) Not a built-in Python command. False We will implement it soon 9  Comparison Operators Comparing numbers is important in many contexts. Python’s comparison operators are intended for that: they operate on two numbers and return a Boolean value, indicating equality, inequality, or a size comparison. >>> 5 == 5 True >>> 6 != 6 False 6≠6 >>> 3 > 2 True >>> 4 < 3 False >>> 3 >= 2 True Shortcut for 3>2 or 3==2 >>> 4 >> 19.1 > 7 True >>> 14.0 == 14 ??? Check it! Don’t be lazy! 11  Comparing Booleans What about comparing Booleans? Well, instead of guessing, let us try: >>> True > True False >>> True > False True Given these examples, how do >>> False > 2.17 False you think the interpreter >>> 4 + True “views” True and False? 5 >>> False * 2 0 >>> True + False 1 Python “views” True as 1 and False as 0. >>> True == 1 and False == 0 True Yet, we strongly recommend you do not use True and False in arithmetic contexts 12  What Else Can We Compare? >>> "0" == 0 False >>> "0" > 0 Traceback (most recent call last): File "", line 1, in "0">0 TypeError: unorderable types: str() > int() Fair enough. What about comparing strings to strings? 13  Comparing Strings What about comparing strings to strings? >>> "Amir" >= "Amir" True >>> "Amir" > "Amir" False Any hypotheses on how Python >>> "Michal" > "Amir" compares strings? True >>> "Amir" > "Michal" False >>> "Amirrrrrrrrrr" > "Michal" False >>> "cat" > "bat" True >>> "cat" > "cut" False >>> "cat" > "car" 14 True  Lexicographical (alphabetical) order Assumption: the set of alphabet (characters allowed) is totally ordered. This means that any 2 single characters can be compared. This assumption holds in Python (more details in the here future, but if you are curious, look here) Given 2 strings over some totally ordered alphabet 𝑆 = 𝑠0 𝑠1 ⋅ ⋅ ⋅ 𝑠𝑛−1 and 𝑇 = 𝑡0 𝑡1 ⋅ ⋅ ⋅ 𝑡𝑚−1 𝑆 < 𝑇 if and only if there exists some 𝑖 ≥ 0 such that (1) for every 0 ≤ 𝑗 < 𝑖 we have 𝑠𝑗 = 𝑡𝑗 and 15 (2) either 𝑠𝑖 < 𝑡𝑖 or 𝑖 = 𝑛 < 𝑚.  ‫* ‪Comic Relief‬‬ ‫‪ What to do after class:‬‬ ‫* אנו מזמינים אתכם לשלוח לנו הצעות לתמונות שיופיעו על שקפים אלו לאורך הסמסטר‬ ‫‪16‬‬  Loops and Iteration “Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an ‘iteration,’ and the results of one iteration are used as the starting point for the next iteration.” (from Wikipedia) 17  Our Example It is very common to have a portion of a program where we wish to iterate the same operation, possibly with different arguments. For example, >>> 1+2+3+4+5+6+7+8+9+10 55 If we just want to add the numbers from 1 to 10, the piece of code above may be adequate. But suppose that instead, we wish to increase the summation limit to 100, 1000, or even 10**8. We obviously ought to have a more efficient method to express such iterated addition. We want to iterate over the integers in the range [1,100], [1,1000], or [1,108], repeatedly, adding the next element to the partially computed sum. 18  Wait a Minute… Do you know young Carl Friedrich Gauss from Wikipedia (1777 – 1855)? At the age of six, he allegedly figured out how to efficiently compute this sum, which is an arithmetic series. 𝑛 𝑛+1 Gauss' observation was that 1 + 2 +⋅⋅⋅ +𝑛 = 2. We are not going to use it, though, and simply let the computer chew its way through the iteration. 19  while Loops n = 10**8 i = 1 loop s = 0 condition while i>> sum(range(1,n+1)) 5000000050000000 29  Comparing Solution’s Efficiency Young Gauss' observation enabled him to calculate the sum 1 + 2 +⋅⋅⋅ +100 very fast. 𝑛 𝑛+1 1 + 2 +⋅⋅⋅ +𝑛 = 2 In modern terminology, we could say that his method, requiring only one addition, one multiplication and one division, is much more computationally efficient than our method, requiring exactly 𝑛 − 1 addition operations. We will define these notions in a precise manner in one of the next lectures, on complexity. 30  Comparing Solution’s Efficiency >>> n = 10**8 >>> sum(range(1,n+1)) 5000000050000000 Computing this sum takes almost 108 additions. Even without measuring it, the time taken for the computation to complete is noticeable. >>> n*(n+1)//2 5000000050000000 Computing this sum “the Gauss way” requires only 3 arithmetic operations and is noticeably faster. Good algorithms often succeed to tackle problems in non- obvious ways, and dramatically improve their efficiency. 31  ‫* ‪Comic Relief‬‬ ‫‪http://www.devtopics.com/wp-content/uploads/2008/05/comic.jpg‬‬ ‫* אנו מזמינים אתכם לשלוח לנו הצעות לתמונות שיופיעו על שקפים אלו לאורך הסמסטר‬ ‫‪32‬‬  Type list str in Python is a sequence (ordered collection) of characters range in Python is a sequence (ordered collection) of integers list in Python is a sequence (ordered collection) of elements (of any type) The simplest way to create a list in Python is to enclose its elements in square brackets: >>> my_list = [2, 3005, 50, 746, 11111] >>> my_list [2, 3005, 50, 746, 11111] 33  Lists (and strings) are Indexable Elements of lists and strings can be accessed via their position, or index. This is called direct access (aka “random access”) In this respect, lists are similar to arrays in other programming languages (yet they differ in other aspects) Indices in Python start with 0, not with 1 >>> my_list = [2, 3005, 50, 746, 11111] >>> my_list 2 >>> my_list 11111 >>> my_list Traceback (most recent call last): File "", line 1, in my list 34 IndexError: list index out of range  len() Quite often, the length is a useful quantity to have. len returns the length (number of elements) of a collection >>> len("abcd") 4 >>> my_list = [2, 3005, 50, 746, 11111] >>> len(my_list) 5 >>> len([]) 0 >>> len([1,2,3] + ["a", "b"]) List concatenation 5 Collections in Python store and maintain their length, so applying len() to them involves merely a single memory read 35 operation, thus is efficient  Iterating over Lists and Strings Recall that for loops allow simple iteration over collections: for x in collection: do something with x for ch in "abc": for x in [55, -6, 7, 8]: print(ch) print(x) a 55 b -6 c 7 8 36  Iteration using range for x in sequence: do something with x L = [11, 12, 13] for k in L: print(k) for i in range(len(sequence)): do something with sequence[i] L = [11, 12, 13] for i in range(len(L)): print(L[i]) 37  Slicing Lists and Strings Slicing allows creating a new list (or string) from an existing one, where the new list (string) is composed of an ordered subset of the original one Slicing merely provides a convenient shorthand for a loop Slicing has many parameters and options. You should neither be overwhelmed by this, nor are you expected to digest and memorize all options right away. You should know the options exist and how to look them up. 39  Slicing – examples >>> num_list = [11,12,13,14,15,16,17,18,19,20] >>> len(num_list) 10 >>> num_list[1:5] slicing ]12,13,14,15[ >>> num_list[0:10:2] slicing an arithmetic progression ]11,13,15,17,19[ >>> num_list[::2] shorthand for previous slicing ]11,13,15,17,19[ >>> num_list[::-1] reversing the list ]20,19,18,17,16,15,14,13,12,11[ 40  Slicing - examples (cont.) >>> num_list[10::-1] same as before ]20,19,18,17,16,15,14,13,12,11[ >>> num_list[-1::-1] index -1 refers to last element ]20,19,18,17,16,15,14,13,12,11[ >>> num_list[-1:-11:-1] and -11 here is one before first ]20,19,18,17,16,15,14,13,12,11[ >>> num_list[8:3:-2] arithmetic progression with δ = -2 ]19,17,15[ >>> num_list[3:8:-2] outcome is an empty list, NOT an error [] >>> num_list slicing did NOT change original list [11,12,13,14,15,16,17,18,19,20] 41  They Slice Strings Too, Don't They? >>> len("Rye Bread") 9 >>> "Rye Bread"[0:9] everything 'Rye Bread' >>> "Rye Bread"[:] shorthand for previous 'Rye Bread' >>> "Rye Bread"[:4] first 4 characters 'Rye ' >>> "Rye Bread"[4:] everything but first 4 characters 'Bread' >>> "Rye Bread"[:4] + "Rye Bread"[4:] concatenate prefix+suffix 'Rye Bread' 42  Sliced Strings (cont.) >>> "Rye Bread"[0:9:2] every second char, starting from first 'ReBed' >>> "Rye Bread"[0::2] shorthand for previous 'ReBed' >>> "Rye Bread"[:9:2] shorthand for previous previous 'ReBed' >>> "Rye Bread"[::2] shorthand for previous previous previous 'ReBed' >>> "Rye Bread"[9::-1] everything, backwards 'daerB eyR' >>> "Rye Bread"[::-1] shorthand for previous 'daerB eyR' 43  Lists and Strings – Summary Both lists and strings are examples for sequences (ordered collections) in python Both can be indexed, sliced and iterated over More collections (ordered and unordered) coming soon 44  Iterating over Lists: Example L = [1,2,3,4] What would happen if we initialized product to 0 instead of 1? product = 1 for k in L: product = product * k print(product) ??? “same as”: for i in range(len(L)): product = product * L[i] 45  Ways to Generate Lists 1) Explicit: [1, 11, 21, 31] 2) Via loop: L = [] for i in range(40): if i%10 == 1: L = L + [i] 3) Slicing an existing list L = [1,11,21,31,41,51,61] L = L[0:4] 4) Direct casting of other sequences: L = list(range(1,40,10)) 5) List comprehension: L = [i for i in range(40) if i%10==1] 46  List Comprehension In mathematics, concise notations are often used to express various constructs, such as sequences or sets. For example, 𝑛2 1 ≤ 𝑛 < 10 ∧ 𝑛 𝑖𝑠 𝑜𝑑𝑑} is the set of squares of odd numbers that are smaller than 10 (the numbers, not the squares). This set is {1, 9, 25, 49, 81} Python supports a mechanism called list comprehension, which enables syntactically concise ways to create lists. For example: >>> [n**2 for n in range(1,10) if n%2 == 1] [1, 9, 25, 49, 81] Syntax: [expression for variable in collection if condition] 47  List Comprehension (cont.) List comprehension is a powerful tool, allowing the succinct, powerful creation of new lists from other collections. >>> staff = [“elhanan", "michal", "matan", "sapir", "dror", "ron“, "amit"] >>> L = [st for st in staff if st=="m"] >>> L ["michal", "matan"] >>> [st.replace("m","M") for st in staff if st=="m"] ["Michal", "Matan"] >>> print(staff) ["elhanan", "michal", "matan", "sapir", "dror", "ron", "amit"] (the original list is unchanged) 48  Lecture 2 - Highlights Conditional statements (if-elif-else) allow splitting the program’s flow into paths Don't forget to #document your code Boolean values are either True or False Logical operators: and, or, not. Comparison operators: == != < > = Logical and comparison expressions evaluate to Boolean values In Python strings are compared lexicographically Loops allow repeating a set of operations multiple times (“iterations”) while loops - as long as some condition holds for loops - over a given collection of elements (e.g., list, string, range) Python’s list is an array of elements – Similar to strings, lists support indexing, iteration, slicing, len() 49