COL100: Introduction to

Computer Science

Lecture 9

Venkata Koppula
Department of CSE, IIT Delhi
So far in the course

1. Basic data types

• Numbers ( int, oat )
No accessible internal structure
• Strings ( sequence of characters )
Can access the i th character of s - s[i]

Can access the substring from i th to j th character - s[i : j]

2. How to compute on numbers, strings

• Operations
on numbers : +, -, *, /, %, **
fl
So far in the course

2. How to compute on numbers, strings

• Operations
on numbers : +, -, *, /, %, **
on strings : +, *
• Storing intermediate computations in variables
• Using conditionals (if … else … )
• Loops (while, for)
Important: convince yourself that your loop is correct, will terminate

In theory, this su ces to solve any computational problem

ffi
 So far in the course

3. How to modularise our code

• via functions

de ne functions that are self-contained

Call them where needed
fi
ffi
The most confusing concept/topic so far?
This (and next) lecture

1. How to store data so that certain operations are faster

• Tuples : very similar to strings
Strings are a sequence of characters, tuples can be sequence of anything
Tuples and strings are non-mutable

• Lists : mutable versions of tuples

Can change any entry,
this is useful in applications that require frequent updates to data
Tuples
Tuples : just like strings

String : sequence of characters

Tuple : sequence of any object

Tuples :
Enclosed in parenthesis ( )
Each element separated by comma ,

t = () # Empty tuple

u = (“Hello”,) # Tuple with one string

# note the comma at the end

v = ("Hello", 5) # Tuple with one string and one integer

Tuples : just like strings

tuples_ nd_output.py

t = ("Hello", 5, "Students")

print("The length of this tuple:", len(t))

print("The first entry is", t[0])

print("The last entry is", t[-1])

print(t) # print the entries, comma separated

Output :

The length of this tuple: 3

The first entry is Hello
The last entry is World
('Hello', 5, ‘Students')
fi
Tuples : just like strings

tuples_ nd_output.py

t = ("Hello", 5, “Students")

print(t[0][0]) # what happens if we print t[1][0]?

print(t[0]*5)

print(t[1]*5)

print(t[3])

Output :

H
HelloHelloHelloHelloHello
25
IndexError
fi
Tuples : just like strings

tuples_ nd_output.py
t = ("Hello", 5, "Students")

u = ("2403", "COL100")

print(t + u)

print(t*2 + u)

print(t[0:1] + u + t[2:3])

print(t[0] + u + t[2])

Output :

('Hello', 5, 'Students', '2403', 'COL100')

('Hello', 5, 'Students', 'Hello', 5, 'Students', '2403', 'COL100')
('Hello', '2403', 'COL100', 'Students')
TypeError
fi
Tuples : just like strings

tuples_ nd_output.py

t = ("Hello", 5, "Students")

u = ("2403", "COL100")

w = t + u

print(len(w))

for s in w: # can iterate over elements in tuple

print(s)

Output :

5
Hello
5
Students
2403
COL100
fi
Tuples : just like strings but more …

Tuple : sequence of any object, including tuples

t = () # Empty tuple

u = ((), ()) # Tuple with two tuples

v = ((“Hello”), “Hello”, 5)
# Tuple with three objects : two strings and one integer
Tuples : just like strings but more …
tuples_ nd_output.py

t = ("Hello", 5, "Students")

u = ("2403", "COL100")

v = (t, u)

print(len(v))

print(v[1][1])

print(v[0][0][0])

Output :

3
COL100
H
fi
Tuples : just like strings but more …
tuples_ nd_output.py

t = ("Hello", 5, "Students")

u = ("2403", "COL100")

v = (t, u)

w = v + u

print(len(w))

print(w)

Output :

4
(('Hello', 5, 'Students'), ('2403', 'COL100'), '2403', 'COL100')
fi
Tuples can be used to return multiple values
Function that takes as input a tuple of integers,
outputs the minimum and maximum
min_max.py

def min_max(t):

if(len(t) == 0):
return None

min = t[0] z = (3, 2, 5, -1, 4, 10, 0)

max = t[0]
(a, b) = min_max(z)
for s in t:
if (s > max): print("min = “, a, “max = ", b)
max = s
if (s < min):
min = s

return (min, max)

Summary of Tuples

• Tuples : very similar to strings

Strings are a sequence of characters,
Tuples can be sequence of anything (including tuples)

Same set of operations as string

Important: Tuples and strings are non-mutable

t = “Hello”
t[0] = “h” # will give an error

u = ((), ()) # Tuple with two tuples

u[0] = (“Hello”,) # will give an error
Summary of Tuples

• Tuples : very similar to strings

Strings are a sequence of characters,
Tuples can be sequence of anything (including tuples)

Same set of operations as string

Important: Tuples and strings are non-mutable

u = ((), ()) # Tuple with two tuples

u = (“Hello”,) + u[1:2] # This will NOT give an error. Why?
Mutable Sequence of Objects: Lists
 Mutables vs Non-Mutables

What happens (internally) when we run the following code:

u = 2
v = 3
z = u + v

Memory: 2

u
 Mutables vs Non-Mutables

What happens (internally) when we run the following code:

u = 2
v = 3
z = u + v

Memory: 2 3

u v
 Mutables vs Non-Mutables

What happens (internally) when we run the following code:

u = 2
v = 3
z = u + v

Memory: 2 3 5

u v z
Mutables vs Non-Mutables

For each of these assignments, Python does the following:

1. Finds a new memory location
2. Puts this value at that memory location
3. ‘Remembers’ the variable to memory location mapping

This memory location can be obtained using id(var_name)

u = 2
v = 3
z = u + v Output

print(id(u)) 4388563576
4388563608
print(id(v)) 4388563672
print(id(z))
 Mutables vs Non-Mutables

Consider the following code, what do you expect the output to be?

u = 2 Output
print(id(u))
4388563576
u = 3 4388563608
print(id(u))

Memory: 2

u
 Mutables vs Non-Mutables

Consider the following code, what do you expect the output to be?

u = 2 Output
print(id(u))
4388563576
u = 3 4388563608
print(id(u))

Memory: 2 3

Integers (and all data-types we’ve seen so far) are non-mutable !

 Mutables vs Non-Mutables

Consider the following code, what do you expect the output to be?

u = 1
v = 2

u = 3

Memory: 1 2

u v

Integers (and all data-types we’ve seen so far) are non-mutable !

 Mutables vs Non-Mutables

Consider the following code, what do you expect the output to be?

u = 1 Once an immutable object

v = 2 loses its variable handle,
Python may free up
u = 3 that memory slot :
garbage collection

Memory: 3 1 2

u v

Integers (and all data-types we’ve seen so far) are non-mutable !

Lists: Mutable objects

Lists :
Enclosed in square brackets [ ]
Each element separated by comma ,

t = [] # Empty list

u = [“Hello”] # List with one string

# note the comma at the end is not needed for lists

v = [“Hello", 5] # List with one string and one integer

Lists: Mutable objects

Lists :
Enclosed in square brackets [ ]
Each element separated by comma ,
Lists are mutable

t = [ “Hello” ]
print(id(t))

t[0] = 5 # List with one integer

print(id(t)) # id remains the same
Lists: Mutable objects

Lists :
Enclosed in square brackets [ ]
Each element separated by comma ,
Lists are mutable

t = [ “Hello” ]
print(id(t))

t = [ 5 ] # List with one integer

print(id(t)) # Does id remain same here?

Id changes every time we have an assignment

Lists: Mutable objects

Adding elements to lists

Adding elements to lists

Lists :
Can use + and * just like tuples and strings

t = [ “Hello” ]
print(id(t))

t = t + [ 5 ] # List with one string and one integer

print(id(t)) # Does id remain same here?

Id changes every time we have an assignment

Adding elements to lists
Lists :
can add element e to list L
using L.append( e )

t = ["hello"]
print("id of t : ", id(t))

t.append(5)
print("t : ", t)

print("id of t after append: ", id(t))

Output

id of t : 4332533696
['hello', 5]
id of t after append: 4332533696
Adding elements to lists
Lists :
can also add a list M to list L
using L.extend( M )

t = ["hello"]
print("id of t : ", id(t))

u = ["world"]
print("id of u : ", id(u))

t.extend(u)
print("t : ", t)
print("id of t after extend: ", id(t))

Output

id of t : 4332533696
['hello', 5]
id of t after append: 4332533696
Adding elements to lists
Lists :
can also add a list M to list L
using L.extend( M )
t = ["hello"]
print("id of t : ", id(t))
Output
t.append(5)
print("t after append: ", t)
id of t : 4377065408
t after append: ['hello', 5]
print("id of t after append: ", id(t))
id of t after append: 4377065408
id of u : 4376906304
u = ["world"]
t after extend: ['hello', 5, 'world']
print("id of u : ", id(u))
u = ['world']
id of u after extend : 4376906304
t.extend(u)
id of t after extend : 4377065408
print("t after extend: ", t)
print("u = ", u)
print("id of u after extend : ", id(u))
print("id of t after extend : ", id(t))
Adding elements to lists
Lists :
can also insert items at any position in L
using L.insert( index, item )

t = [“hello”, “students”]
print("id of t : ", id(t))

t.insert(1, “COL100”)
print("t after insert: ", t)

print("id of t after insert: ", id(t))

Output

id of t : 4377065408
t after insert: ['hello', ‘COL100’, ‘students’]
id of t after append: 4377065408
Removing elements from lists
Removing elements from lists

L.pop( ) : removes the last element in L

L.pop( i ) : removes the element at position i in L

Both these methods modify the list, and also return the element removed

t = [“hello”, “COL100”, “students”]

print("id of t : ", id(t)) Output

id of t : 4377065408
print(t.pop(1)) t after pop: ['hello',‘students’]
print("t after pop: ", t) id of t after pop: 4377065408

print("id of t after pop: ", id(t))

 Other operations on lists

Lots of built-in functions (methods) on lists.

The course objective is not to learn all the existing functions.
Make sure you understand how to use the basic ones.
Sorting a list

Given a list L ,
how to arrange them in increasing/decreasing order?

L.sort( ) : mutates L, sorts elements in increasing order

L.sort( reverse = True ) : mutates L, sorts elements in decreasing order

sorted( L ) : sorts elements in increasing order, does not mutate L (returns a di erent list)
sorted( reverse = True) : sorts elements in increasing order, does not mutate L

ff
Summary of list operations
L.append ( e ) : mutates L, appends e to L, returns None
L.extend( M ) : mutates L, appends list M to L, returns None
L.insert( i, e ) : mutates L, inserts e at position i, returns None

L.pop( ) : mutates L, removes the last element of L and returns it

L.pop( i ) : mutates L, removes element at position i and returns it

L.sort( ) : mutates L, sorts elements in increasing order, returns None

L.sort( reverse = True ) : mutates L, sorts elements in decreasing order, returns None

len( L ) : returns the length of the list

sorted( L ) : sorts elements in increasing order, does not mutate L (returns a di erent list)
sorted( reverse = True) : sorts elements in increasing order, does not mutate L

ff
Computations on lists
Searching in sorted lists

For a list L, element e,

e in L : True if e is an element in L, False otherwise

Our Goal: implement a function search_list( L, e )

that takes as input a list L, element e,
returns True if e is in L, False otherwise
(should not use any built-in functions)
Searching in sorted lists
search_list.py

def search_list(L, e):

left = 0
right = len(L) - 1

while (left <= right):

mid = int((left + right)/2)

if(L[mid] == e):
return True
elif (L[mid] < e):
left = mid + 1
else:
right = mid - 1

return False