ACOL106: Data Structures

(Recap: Python Module 1)

This sequence of Jupyter notebooks is meant to help the students recap the material taught in ACOL100. We will revisit some of the key concepts of Python programming while focusing on those that will be important for Data Structures. This is mainly the first chapter of the prescribed textbook. Much of the material here is copied from the textbook. The advantage of the Jupyter notebook is that it gives you an opportunity to experiment with the code while you are trying to pick up the concepts. Such experimentation and engagement make it much easier to pick up the concepts.

1. Python interpreter

Python is an interpreted language, which means there is a software known as the "Python interpreter" that executes the programming instructions from the user interactively, one instruction at a time. A user can either interact with the Python interpreter instruction-by-instruction OR give a sequence of instructions to the interpreter to process together. The Jupyter notebook has a Python interpreter running in the background (recall starting the jupyterlab program from the terminal to get this notebook started), and you can interact with it using the code segments such as the one given below. Let us test this interpreter by asking it to execute the following simple instruction to print "Hello World". You can click on the code segment below and run it to see the result. Alternatively, if you are using this notebook in the HTML format, then you can copy the code in the code segments on this notebook, paste them as commands on a separate terminal on which you have the Python interpreter running, and see the results there.

print('Hello World')

Hello World

We can also give a sequence of commands such as given below:

print('Hello World')
print('Hello Python')
for i in range(5):
    print('Within iteration', i, 'of the loop')

Hello World
Hello Python
Within iteration 0 of the loop
Within iteration 1 of the loop
Within iteration 2 of the loop
Within iteration 3 of the loop
Within iteration 4 of the loop

Questions:

1. There are programming languages (e.g., C) that are "compiled", where all the programming instructions are converted to machine code and then executed instead of a line-by-line conversion as in an interpreted language. What could be the advantages/disadvantages of an interpreted language over a compiled language.

2. Python objects

Python is an object-oriented language, and classes form the basis of all data types. Even data types required for basic computations, such as integers, floating-point numbers, and strings, have built-in classes defined for them, and we need to know these to be able to do even basic data processing.

• Class for integers: int
• Class for floating point numbers: float
• Class for strings: str

2.1 Assignment

The most basic data processing instruction in any language is the assignment statement, where a value is "assigned" to an identifier. A simple example from the book is given below.

temperature = 98.6

Here temperature is an identifier. This identifier references (or gets associated with) a float object that has the value 98.6. The diagram below captures this notion.

There are rules for what could be a valid identifier, and students should look this up. In short, most combinations of letters, numerals, and underscores that do not start with a numeral should be a valid identifier.

An interesting property of the Python programming language is that we do not need to define the "type" of an identifier before assigning an object to it. In other languages, such as Java or C++, we must first define the type of an identifier before assignment. For example, a similar assignment statement in Java will be float temperature = 98.6. This is because Python is a dynamically typed language. This means that the same identifier can be used to reference a different type of object. For example, see the code below.

temperature = 98.6
print("The temperature identifier is of type", type(temperature))
temperature = 'Hello World'
print("The temperature identifier is of type", type(temperature))

The temperature identifier is of type <class 'float'>
The temperature identifier is of type <class 'str'>

One can establish an alias by assigning a second identifier to an existing object using an assignment statement as given below:

temperature = 98.6
original = temperature
print("Original", original)

Original 98.6

The assignment statement original = temperature makes the identifier original reference the same object as referenced by temperature. The diagram below captures this notion.

There is always an identifer to the left of '=' of an assignment statement. To the right of '=', we could have an expression (which includes values such as 98.6 or another identifier). The object that the identifier on the left references depends on how the expression on the right gets evaluated. There are certain rules related to expression evaluation, that we will see soon. Let us see an example to get started:

temperature = 98.6
original = temperature
temperature = temperature + 5

What do you think is the result of the above sequence of instructions? Do identifiers temperature and original reference the same object storing value 103.6 at the end of these instructions? This crucially depends on how the expression temperature + 5 is evaluated. It turns out, the value 98.6 associated with the object referenced by temperature is added to the value 5, and a new object is created to store the result 103.6. This new object is assigned to the identifier to the left of '=', which is temperature. So, after these lines temperature references a float object with value 103.6, whereas original continues to reference the object with value 98.6. See diagram below. Add print statements in the code segment above to check for yourself.

2.2 Creating and using objects

Since objects and classes are at the core of programming in Python, it is important to have a familiarity with the key concepts to be able to start with basic programming. The full power of object-oriented programming is a separate topic, which we will recap soon. As you must have seen in the ACOL100 course, classes help to encapsulate data and define actions on the data so that a programmer who intends to use the code need not know the details of the inner workings within the class. An object is an instantiation of a class. For example, suppose there is a Student class that is designed to store grades and perform data processing on the grades of a student. We can instantiate an object for every student in the class. To instantiate an object of a class, we invoke the constructor of the class. For example, the Student class may have a constructor that takes as input the name of the student. Then, we can instantiate an object as s1 = Student("Ragesh"). Python's built-in classes (i.e., classes that are pre-defined within Python) support what is known as a literal form for instantiating. The assignment statement we saw earlier: temperature = 98.6 is an example of instantiating a float object using this literal form.

Classes have member functions that are known as methods that are invoked on a specific instance of the class using the dot operator ('.'). For example, the Student may have a method to calculate the CGPA of the student, which can be invoked using the statement s1.calculateCGPA(). Some methods can change the state of the corresponding object (on which the method is called), which are called mutators. Others may only provide access to the state and do not change the state. These are called accessors.

2.3 Python's built-in classes

To start doing basic programming, we must know the basic built-in classes of Python related to various types of data. One of the key concepts when dealing with Python objects is mutability of classes. A class is said to be immutable if the value of any object of the class cannot change after instantiation. For example, float is an immutable object. Classes where the value of the object is allowed to change after instantiation are known as mutable classes. We look at some of the basic built-in classes in Python below.

The bool class:

This is an immutable class for manipulating Boolean data. There are two literal forms: True and False. There is also a default constructor bool() that instantiates to False. There is also bool(val). When val is a number, then bool(val) instantiates to False when val is 0, and True, otherwise. When val is a string, then bool(val) instantiates to False when val is an empty string, and True, otherwise. See some examples below.

x = True
y = False
z = bool("")
t = bool(90)
print("x, y, z, t: ", x, y, z, t)

x, y, z, t:  True False False True

The int class

This class is for manipulating integer values with arbitrary magnitude (note that this is unlike in other languages, such as C, C++, where there are different data types for different precisions). The literal forms are values, such as -1, 23, 456785. There is a constructor int() that instantiates to 0. There is also a constructor int(val). When val is a float, then the instantiation is to the truncated value of val. For example, int(3.14) is instantiated to 3 and int(-4.14) is instantiated to 3. When val is a string, then the instantiation is to the integer value of the string. See some examples below.

x = 3
y = int()
z = int(3.14)
t = int(-4.14)
r = int('14326')
print("x, y, z, t, r: ", x, y, z, t, r)

x, y, z, t, r:  3 0 3 -4 14326

The float class

This is to support operations on floating point numbers (Python supports 64-bit precision adhering to the IEEE 754 standard). Literal forms include simply the values, such as 98.6. Another literal form is 6.022e23 that represents the number 6.022x10²³. Other constructor examples include float() that instantiates to 0.0, float(2) that instantiates to 2.0, float('3.14') that instantiates to 3.14. See some examples below.

x = 2.0
y = 6.022e23
z = float('3.14')
t = float(2)
r = float()
print("x, y, z, t, r: ", x, y, z, t, r)

x, y, z, t, r:  2.0 6.022e+23 3.14 2.0 0.0

The list class

A list is a mutable class meant to store a sequence of references to arbitrary objects. They are zero-indexed and array-based sequences. The literal form involves using '[]' as delimiters. Some of the examples below should be sufficient to understand the options for constructing a list.

L1 = ['red', 'green', 'blue']
L2 = [] #an empty list
L3 = [1, 3.14, 'red', True]
L4 = [L1, L2, L3]
print(L1, L2, L3, L4)
print(L4[1])
L4[1] = ['T', 'E', 'S', 'T']
print(L4[1])

#The list() constructor instantiates to an empty list
L5 = list() 
print(L5)

#The list(val) constructor can be given any input of iterable type, such as string, list, dictionary, etc. 
L6 = list("Testing lists")
print(L6)

['red', 'green', 'blue'] [] [1, 3.14, 'red', True] [['red', 'green', 'blue'], [], [1, 3.14, 'red', True]]
[]
['T', 'E', 'S', 'T']
[]
['T', 'e', 's', 't', 'i', 'n', 'g', ' ', 'l', 'i', 's', 't', 's']

The tuple class

This is an immutable version of lists. The literal form uses '()' as delimiters. The examples below should be sufficient to understand the constructions.

T0 = () #an empty tuple
T1 = (2,) #This is a special representation for a tuple with one element since (2) would also represent the number 2

T2 = (2, 3, 'red')
print(T2[1])
# Try executing T2[1] = 4 to check that tuples are immutable

# A tuple of tuples
T4 = (T0, T1, T2)
print(T4)

3
((), (2,), (2, 3, 'red'))

The str class

Python’s str class is specifically designed to efficiently represent an immutable sequence of characters, based upon the Unicode international character set. The examples below should be self-explanatory:

S = '' #An empty string
print(S)
S = "" #Another empty string
print(S)
S = "Hello"
print(S)
S = 'Hello'
print(S)
S = "Don't worry"
print(S)
S = 'Don\'t worry' # A backslash is used to differentiate the delimiters from characters within the string
print(S)
S = "A newline\nexample"
print(S)
S = """A multiline
example using triple \""""
print(S)

Hello
Hello
Don't worry
Don't worry
A newline
example
A multiline
example using triple "

The set class

Python’s set class represents the mathematical notion of a set, namely a collection of elements, without duplicates, and without an inherent order to those elements. Note that only instances of immutable types can be added to a Python set. Python uses curly braces { and } as delimiters for a set. Examples below are self-explanatory:

S = set() #This instantiates to the empty set. Note that {} does not represent the empty set
print(S)
S = {1, 2, 3, 'red', 2, 1}
print(S)

# For an iterable parameter as input, the set is initialized with the elements of the input
S = set("Hellooooooo")
print(S)

# One can create more complex sets
S1 = {(2, 3), False, 2.13, (2,)}
print(S1)
# On the other hand, one cannot create a set containing another set or a list, since sets and lists are mutable
# Try creating a set such as S1 = {S, 1, 2} OR S1 = {[1, 2], 1, 2} to check.

set()
{1, 2, 3, 'red'}
{'H', 'o', 'l', 'e'}
{(2, 3), False, 2.13, (2,)}

The dict class

Python’s dict class represents a dictionary, or mapping, from a set of distinct keys to associated values. For example, a dictionary might map from unique course ID numbers to larger records (such as the instructor’s name and prerequisite). Python implements a dict using an almost identical approach to that of a set, but with storage of the associated values. This also means that the dict class is mutable. The literal form includes the use of '{}' as delimiters. See examples below:

D1 = {} #An empty dictionary
print(D1)

D2 = {'ACOL100': 'Venkata', 'ACOL106': 'Ragesh'}
print(D2)
D2 = {'ACOL100': ('Venkata', 'None'), 'ACOL106': ('Ragesh', 'ACOL100')}
print(D2)

D3 = dict([('ACOL100', ('Venkata', 'None')), ('ACOL106', ('Ragesh', 'ACOL100'))])
print(D3)

{}
{'ACOL100': 'Venkata', 'ACOL106': 'Ragesh'}
{'ACOL100': ('Venkata', 'None'), 'ACOL106': ('Ragesh', 'ACOL100')}
{'ACOL100': ('Venkata', 'None'), 'ACOL106': ('Ragesh', 'ACOL100')}

3. Expressions, operators, and precedence

Existing values/objects can be combined into larger syntactic expressions using a variety of special symbols and keywords known as operators. The meaning of an operator depends on the type of its operands. For example, when a and b are numbers, the syntax a+b indicates addition, while if a and b are strings, the operator indicates concatenation. In this section, we describe Python’s operators in various contexts of the built-in types.

The logical operators

The following operators are supported on Boolean values: (i) Logical negation: not, (ii) Logical AND: and, (iii) Logical OR: or. See some examples below:

if(not False):
    print("Hello 1")
a = True
b = False
if(a or (not b)):
    print("Hello 2")

if(a or b):
    print("Hello 3")

if(b and a):
    print("Hello 4")

Hello 1
Hello 2
Hello 3

The equality operators

Python supports the following operators to test two notions of equality: (i) Same identity: is, (ii) Different identity: is not, (iii) Equivalent: ==, (iv) Not Equivalent: !=. The expression a is b evaluates to True, precisely when identifiers a and b are aliases for the same object. The expression a == b tests a more general notion of equivalence. If identifiers a and b refer to the same object, then a == b should also evaluate to True. Yet a == b also evaluates to True when the identifiers refer to different objects that happen to have values that are deemed equivalent. The precise notion of equivalence depends on the data type. For example, two strings are considered equivalent if they match character for character. Two sets are equivalent if they have the same contents, irrespective of order. In most programming situations, the equivalence tests == and != are the appropriate operators; use of is and is not should be reserved for situations in which it is necessary to detect true aliasing. Here are a few examples to test our understanding.

A = [1, 2, 3]
B = A
if(B is A):
    print("Hello 1")
if(B == A):
    print("Hello 2")

C = [1, 2, 3]
D = [1, 2, 3]
if(C is D):
    print("Hello 3")
if(C == D):
    print("Hello 4")

Hello 1
Hello 2
Hello 4

The comparison operators

The standard comparison operators <, <=, >, >= are defined on numeric and string types. These operators have expected behaviour for numeric types, and are defined lexicographically and case-sensitively for strings. See a few examples below:

print("Ragesh" < "ragesh")

True

The arithmetic operators

Python supports the following arithmetic operators on numeric types: (i) + addition, (ii)− subtraction, (iii) * multiplication, (iv) / true division, (v) // integer division, (vi) % the modulo operator. There are a few subtle points regarding these operations that students should pick up from the book. See a few examples below:

print(27//4)
print(27%4)
print(-27//4)
print(27//-4)
print(8.2//3.14)
print(8.2%3.14)

6
3
-7
-7
2.0
1.919999999999999

The bitwise operators

Python provides the following bitwise operators for integers: (i) ∼ bitwise complement (prefix unary operator), (ii) & bitwise, (iii) | bitwise or, (iv) ˆ bitwise exclusive-or, (v) << shift bits left, filling in with zeros, (vi) >> shift bits right, filling in with sign bit. See a few examples below that you can further experiment with:

# The bit representation of 13 is 1101. So the bit representation of 13>>2 should be 11 (i.e., 3 in decimal)
print(13>>2) 

print(13<<1)
print(12 & 9)
print(12 | 9)
print(12 ^ 5)

3
26
8
13
9

The sequence operators

Each of Python’s built-in sequence types (str, tuple, and list) support the following operator syntaxes:

• s[j]: element at index j
• s[start:stop]: slice including indices [start,stop)
• s[start:stop:step]: slice including indices start, start + step, start + 2 step, . . . , up to but not equalling or stop
• s + t: concatenation of sequences
• k*s: shorthand for s + s + s + ... (k times)
• val in s: containment check
• val not in s: non-containment check

Python uses a slicing notation to describe subsequences of a sequence. Slices are described as half-open intervals, with a start index that is included, and a stop index that is excluded. For example, the syntax data[3:8] denotes a subsequence including the five indices: 3,4,5,6,7. An optional “step” value, possibly negative, can be indicated as a third parameter of the slice. If a start index or stop index is omitted in the slicing notation, it is presumed to designate the respective extreme of the original sequence.

Because lists are mutable, the syntax s[j] = val can be used to replace an element at a given index. Lists also support a syntax, del s[j], that removes the designated element from the list. Slice notation can also be used to replace or delete a sublist.

The notation val in s can be used for any of the sequences to see if there is an element equivalent to val in the sequence. For strings, this syntax can be used to check for a single character or for a larger substring, as with "amp" in "example". All sequences define comparison operations based on lexicographic order, performing an element-by-element comparison until the first difference is found. For example, [5, 6, 9] < [5, 7] because of the entries at index 1. Therefore, the following operations are supported by sequence types:

• s == t: equivalent (element by element)
• s != t: not equivalent
• s < t: lexicographically less than
• s <= t: lexicographically less than or equal to
• s > t: lexicographically greater than
• s >= t: lexicographically greater than or equal to

Let's experiment with allt he sequence operators below:

L = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N']
print(L[0])
print(L[1:5])
print(L[1:10:2])
S = ['O', 'P', 'Q', 'R']
print(L+S)
print(L)
print(S)
print(2*S)
if('G' in L):
    print("Hello 1")
if('G' in S):
    print("Hello 2")

# Delete an element of the list 
print(S)
del S[2]
print(S)
S[1] = 'Z'
print(S)

if(L != S):
    print("Hello 3")
    
if(L < S):
    print("Hello 4")

A
['B', 'C', 'D', 'E']
['B', 'D', 'F', 'H', 'J']
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R']
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N']
['O', 'P', 'Q', 'R']
['O', 'P', 'Q', 'R', 'O', 'P', 'Q', 'R']
Hello 1
['O', 'P', 'Q', 'R']
['O', 'P', 'R']
['O', 'Z', 'R']
Hello 3
Hello 4

Operators for sets

Sets support the following operators:

• key in s: containment check
• key not in s: non-containment check
• s1 == s2: s1 is equivalent to s2
• s1 != s2: s1 is not equivalent to s2
• s1 <= s2: s1 is subset of s2
• s1 < s2: s1 is proper subset of s2
• s1 >= s2: s1 is superset of s2
• s1 > s2: s1 is proper superset of s2
• s1 | s2: the union of s1 and s2
• s1 & s2: the intersection of s1 and s2
• s1− s2: the set of elements in s1 but not s2
• s1 ˆ s2: the set of elements in precisely one of s1 or s2

Let's experiment with these operators below:

s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9}
x = 2
if(x in s1):
    print("Hello 1")
s2 = {6, 7, 8, 9, 10, 11, 12}
if(s1 == s2):
    print("Hello 2")

if(s1 <= s2):
    print("Hello 3")

if(s1 <= s1|s2):
    print("Hello 4")

print(s1 - s2)
print(s2 - s1)
print(s1 ^ s2)

Hello 1
Hello 4
{1, 2, 3, 4, 5}
{10, 11, 12}
{1, 2, 3, 4, 5, 10, 11, 12}

Operators for dictionaries

The supported operators are as follows:

• d[key]: value associated with given key
• d[key] = value: set (or reset) the value associated with given key
• del d[key]: remove key and its associated value from dictionary
• key in d: containment check
• key not in d: non-containment check
• d1 == d2: d1 is equivalent to d2
• d1 != d2: d1 is not equivalent to d2

Let's experiment:

d = {'sample1': ('green', 'solid'), 'sample2': ('yellow', 'liquid'), 'sample3': ('red', 'gas')}
print(d['sample2'])
d['sample3'] = ('blue', 'solid')
print(d['sample3'])

s = 'sample1'
if(s in d):
    print(d[s])

d1 = {'sample1': ('green', 'solid'), 'sample2': ('yellow', 'liquid'), 'sample3': ('red', 'gas')}
if(d == d1):
    print("Hello 1")

d2 = {'sample1': ('green', 'solid'), 'sample2': ('yellow', 'liquid'), 'sample3': ('blue', 'solid')}
if(d == d2):
    print("Hello 2")

('yellow', 'liquid')
('blue', 'solid')
('green', 'solid')
Hello 2

Extended assignment operator

Students who have been exposed to programming languages such as Java, C++ must be used to assignment statements such as count+=1 for incrementing the value of variable count by 1. This is the short way to write count = count + 1. However, in Python count = count + 1 has a different interpretation. Here, count + 1 creates a new object with value one more than the value in the object referenced by count. This new object is assigned the identifier count. The reason is that the int class is immutable, so its value cannot be changed by 1. In cases where the class is mutable, += has a different effect as exhibited by the example below.

alpha = [1, 2, 3]
beta = alpha # an alias for alpha
beta += [4, 5] # extends the original list with two more elements
beta = beta + [6, 7]  # reassigns beta to a new list [1, 2, 3, 4, 5, 6, 7]
print(alpha) # will be [1, 2, 3, 4, 5]
print(beta)

[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6, 7]

Compound Expressions and Operator Precedence

Programming languages must have clear rules for the order in which compound expressions, such as 5 + 2*3, are evaluated. The formal order of precedence for operators in Python is given in the Table below. Operators in a category with higher precedence will be evaluated before those with lower precedence, unless the expression is otherwise parenthesized. Therefore, we see that Python gives precedence to multiplication over addition, and therefore evaluates the expression 5 + 2*3 as 5 + (2*3), with value 11, but the parenthesized expression (5 + 2) * 3 evaluates to value 21. Operators within a category are typically evaluated from left-to-right, thus 5 − 2 + 3 has a value of 6. Exceptions to this rule include that unary operators and exponentiation are evaluated from right to left.

Python allows a chained assignment, such as x = y = 0, to assign multiple identifiers to the rightmost value. Python also allows the chaining of comparison operators. For example, the expression 1 <= x + y <= 10 is evaluated as the compound (1 <= x + y) and (x + y <= 10), but without computing the intermediate value x + y twice.

Some experiments are given below. You should run more experiments.

print(2**-10+1 < 3+5*6/100+20)
print(2 * 3 + 5 & 10 + 2)

True
8

4. Module Endnote

In this module, we have learnt basic elements of Python programming, including instantiating and working with Python's built-in classes. We have also learnt the use of operators and expressions to process a bunch of objects. Is this sufficient to start writing interesting Python programs? Yes, we can write some very basic programs using expressions and operators to do "calculator-like" computations. However, it would be worth waiting to learn a few more concepts, such as conditionals and loops, to exploit the full power of programming. This is known as control flow, and we start the discussion in the next module.