Untitled
Untitled
Untitled
Your feedback plays a critical role in the evolution of our products and you
can contact us - reachus@pearson.com. We look forward to it.
PYTHON PROGRAMMING: A MODULAR
APPROACH
Sheetal Taneja
Department of Computer Science
Dyal Singh College
University of Delhi
Delhi, India
and
Naveen Kumar
Department of Computer Science
University of Delhi
Delhi, India
Contents
Foreword
Preface
About the Authors
1. Python Programming: An Introduction
1.1IDLE – An Interpreter for Python
1.2 Python Strings
1.3 Relational Operators
1.4 Logical Operators
1.5 Bitwise Operators
1.6 Variables and Assignment Statements
Assignment Statement
Shorthand Notation
1.7 Keywords
1.8 Script Mode
Summary
Exercises
2. Functions
2.1 Built-in Functions
input Function
eval Function
Composition
print Function
type Function
round Function
Type Conversion
min and max Functions
pow Function
Random Number Generation
Functions from math Module
Complete List of Built-in Functions
2.2 Function Definition and Call
Fruitful Functions vs Void Functions
Function help
Default Parameter Values
Keyword Arguments
2.3 Importing User-defined Module
2.4 Assert Statement
2.5 Command Line Arguments
Summary
Exercises
3. Control Structures
3.1 if Conditional Statement
General Form of if Conditional Statement
Conditional Expression
General Form of if-else Conditional Statement
General Form of if-elif-else Conditional Statement
Nested if-elif-else Conditional Statement
3.2 Iteration (for and while Statements)
3.2.1 for Loop
General Format of for Statement
3.2.2 while Loop
General Format of while Statement
Infinite Loops
3.2.3 while Statement vs. for Statement
3.2.4 Example: To Print Some Pictures
3.2.5 Nested Loops
3.2.6 break, continue, and pass Statements
3.2.7 Example: To Compute sin(x)
3.2.8 else Statement
Summary
Exercises
4. Debugging
4.1 Testing
An Example: Finding Maximum of Three Numbers
4.2 Debugging
Summary
Exercises
5. Scope
5.1 Objects and Object ids
5.2 Scope of Objects and Names
5.2.1 Namespaces
5.2.2 Scope
LEGB Rule
Summary
Exercises
6. Strings
6.1 Strings
6.1.1 Slicing
6.1.2 Membership
6.1.3 Built-in Functions on Strings
Function count
Functions find and rfind
Functions capitalize, title, lower, upper, and swapcase
Functions islower, isupper, and istitle
Function replace
Functions strip, lstrip, and rstrip
Functions split and partition
Function join
Functions isspace, isalpha, isdigit, and isalnum
Function startswith and endswith
Functions encode and decode
List of Functions
6.2 String Processing Examples
6.2.1 Counting the Number of Matching Characters in a Pair of Strings
6.2.2 Counting the Number of Common Characters in a Pair of Strings
6.2.3 Reversing a String
6.3 Pattern Matching
6.3.1 Some Important Definitions
Summary
Exercises
7. Mutable and Immutable Objects
7.1 Lists
7.1.1 Summary of List Operations
7.1.2 Function list
7.1.3 Functions append, extend, count, remove, index,
pop,and insert
7.1.4 Function insert
7.1.5 Function reverse
7.1.6 Functions sort and reverse
7.1.7 List Functions
7.1.8 List Comprehension
7.1.9 Lists as Arguments
7.1.10 Copying List Objects
7.1.11 map, reduce, and filter Operations on a Sequence
7.2 Sets
7.2.1 Set Functions add, update, remove, pop, and clear
7.2.2 Set Functions union, intersection, difference, and symmetric_difference
7.2.3 Function copy
7.2.4 Subset and Superset Test
7.2.5 List of Functions
7.2.6 Finding Common Factors
7.2.7 Union and Intersection Operation on Lists
7.3 Tuples
7.3.1 Summary of Tuple Operations
7.3.2 Functions tuple and zip
7.3.3 Functions count and index
7.4 Dictionary
7.4.1 Dictionary Operations
7.4.2 Deletion
7.4.3 Function get
7.4.4 Function update
7.4.5 Function copy
7.4.6 List of Functions
7.4.7 Inverted Dictionary
Summary
Exercises
8. Recursion
8.1 Recursive Solutions for Problems on Numeric Data
8.1.1 Factorial
Iterative Approach
Recursive Approach
8.1.2 Fibonacci Sequence
Iterative Approach
Recursive Approach
8.2 Recursive Solutions for Problems on Strings
8.2.1 Length of a String
8.2.2 Reversing a String
8.2.3 Palindrome
8.3 Recursive Solutions for Problems on Lists
8.3.1 Flatten a List
8.3.2 Copy
8.3.3 Deep Copy
8.3.4 Permutation
8.4 Problem of Tower of Hanoi
Summary
Exercises
9. Files and Exceptions
9.1 File Handling
9.2 Writing Structures to a File
9.3 Errors and Exceptions
9.4 Handling Exceptions Using try…except
9.5 File Processing Example
Summary
Exercises
10. Classes I
10.1 Classes and Objects
10.2 Person: An Example of Class
10.2.1 Destructor
10.3 Class as Abstract Data Type
10.4 Date Class
Summary
Exercises
11. Classes II
11.1 Polymorphism
11.1.1 Operator Overloading
Comparing Dates
11.1.2 Function Overloading
11.2 Encapsulation, Data Hiding, and Data Abstraction
11.3 Modifier and Accessor Methods
11.4 Static Method
11.5 Adding Methods Dynamically
11.6 Composition
11.7 Inheritance
11.7.1 Single Inheritance
Scope Rule
Extending Scope of int Class Using a User Defined Class
11.7.2 Hierarchical Inheritance
11.7.3 Multiple Inheritance
11.7.4 Abstract Methods
11.7.5 Attribute Resolution Order for Inheritance
11.8 Built-in Functions for Classes
Summary
Exercises
12. List Manipulation
12.1 Sorting
12.1.1 Selection Sort
12.1.2 Bubble Sort
12.1.3 Insertion Sort
12.2 Searching
12.2.1 Linear Search
12.2.2 Binary Search
12.3 A Case Study
12.3.1 Operations for Class Section
Complete Script
12.4 More on Sorting
12.4.1 Merge Sort
12.4.2 Quick Sort
Summary
Exercises
13. Data Structures I: Stack and Queues
13.1 Stacks
13.1.1 Evaluating Arithmetic Expressions
13.1.2 Conversion of Infix Expression to Postfix Expression
13.2 Queues
Summary
Exercises
14. Data Structures II: Linked Lists
14.1 Introduction
14.2 Insertion and Deletion at the Beginning of a Linked List
14.3 Deleting a Node with a Particular Value from a Linked List
14.4 Traversing a Linked List
14.5 Maintaining Sorted Linked List While Inserting
14.6 Stack Implementation Using Linked List
14.7 Queue Implementation Using Linked List
Summary
Exercises
15. Data Structures III: Binary Search Trees
15.1 Definitions and Notations
15.2 Binary Search Tree
15.3 Traversal of Binary Search Trees
15.3.1 Inorder Traversal
15.3.2 Preorder Traversal
15.3.3 Postorder Traversal
15.3.4 Height of a Binary Tree
15.4 Building Binary Search Tree
Summary
Exercises
16. More on Recursion
16.1 Pattern within a Pattern
16.2 Generalized Eight Queens Problem
16.3 Knight's Tour Problem
16.4 Stable Marriage Problem
16.5 Fractal (Hilbert Curve and Sierpinski Triangle)
16.6 Sudoku
16.7 Guidelines on Using Recursion
Summary
Exercises
17. Graphics
17.1 2D Graphics
17.1.1 Point and Line
Axis, Title, and Label
Plotting Multiple Functions in the Same Figure
Multiple Plots
Saving Figure
17.1.2 Histogram and Pi Chart
17.1.3 Sine and Cosine Curves
17.1.4 Graphical Objects: Circle, Ellipse, Rectangle, Polygon,
and Arrow
Circle
Ellipse
Rectangle
Polygon
Arrow
17.2 3D Objects
Box
Sphere
Ring
Cylinder
Arrow
Cone
Curve
17.3 Animation – Bouncing Ball
Summary
Exercises
18. Applications of Python
18.1 Collecting Information from Twitter
Open Authentication
An Example – Collecting User Information
Collecting Followers, Friends, and Tweets of a User
Collecting Tweets Having Specific Words
18.2 Sharing Data Using Sockets
Client-Server Communication on the Same Machine – A Simple Example
An Echo Server
Accessing Web Data (Downloading a Pdf File)
18.3 Managing Databases Using Structured Query Language (SQL)
18.3.1 Database Concepts
18.3.2 Creating Database and Tables
18.3.3 Inserting Data into Table
18.3.4 Retrieving Data from Table
18.3.5 Updating Data in a Table
18.3.6 Deleting Data from Table/Deleting Table
18.4 Developing Mobile Application for Android
18.4.1 A Simple Application Containing Registration Interface
18.4.2 Tic-Tac-Toe Game
18.4.3 Running Kivy Applications on Android
18.5 Integrating Java with Python
18.5.1 Accessing Java Collections and Arrays in Python
18.5.2 Converting Python Collections to Java Collections
18.5.3 Invoking a Parameterized Java Method from Python
18.5.4 Invoking Parameterized Python Method from Java
18.6 Python Chat Application Using Kivy and Socket Programming
Summary
Exercises
Index
Colour Illustrations
Foreword
Prof. S K Gupta
Department of Computer Science and Engineering
Indian Institute of Technology Delhi
New Delhi, India
Preface
ACKNOWLEDGEMENTS
We are grateful to Hitarth, first-year undergraduate student at Dyal Singh
College of University of Delhi, for going through the entire book with great
care and suggesting dozens of subtle corrections and modifications. We are
thankful to Arpit of Amazon Inc. for his help in identifying the suitable level
of abstraction in several chapters of the book. We are also grateful to Prof. S
K Gupta, IIT Delhi, Mr. Suraj Prakash, Director Training, Bal Bharati group
of institutions, Dr Anamika Gupta of SS College of Business Studies, Dr
Sharanjeet Kaur of Acharya Narendra Dev College, Mr. Ashok Jain of Sugal
Infotech, and our former students Abhishek, Ajay, Kanika, Mitul and Sunil,
for their comments on various sections of the book.
We are grateful to the entire Pearson team, especially Ms. Neha Goomer
and Mr. M. Balakrishnan who were readily available for any help during the
preparation of the book. Ms. Neha’s suggestion to include margin notes in
the book has significantly improved the readability of the book. Last but not
the least, we would like to express our gratitude to our family members for
their support and patience.
Sheetal Taneja
Naveen Kumar
About the Authors
CHAPTER OUTLINE
1.1 IDLE – An Interpreter for Python
1.2 Python Strings
1.3 Relational Operators
1.4 Logical Operators
1.5 Bitwise Operators
1.6 Variables and Assignment Statements
1.7 Keywords
1.8 Script Mode
Ever since the language was developed, it is becoming popular day by day
amongst the programmers. Various versions of Python have been released
till date ranging from version 1.0. This book uses Python 3.6. Python is used
in various application areas such as the web, gaming, scientific and numeric
computing, text processing, and network programming.
Python shell displays the prompt >>> to indicate that it is waiting for a user command
Python shell may also be used as a calculator, for example, when we type 18
+ 5 followed by enter, Python shell outputs the value of the expression, i.e.
23, as shown below:
>>> 18 + 5
23
The exponentiation operator (**) yields raise to the power operation, i.e. a .
b
>>> 3 ** 2
>>> 6 / 3 / 2
1.0
>>> 2 ** 3 ** 2
512
>>> 10 * -5
-50
while the parentheses have the highest precedence, addition and subtraction are at the lowest
level
An error occurs when the input expression is not correctly formed. For
example, the expression 7 + 3(4 + 5) generates an error because the
operator between 3 and ( is missing:
>>> 7 + 3(4 + 5)
7 + 3(4 + 5)
'Hello World'
Hello World
>>> """Hello
What's
happening"""
"Hello\nWhat's\nhappening"
>>> print("""Hello
What's
happening""")
Hello
What's
happening
a Python string may be enclosed within single, double, or triple quotes
Note that enclosing quote marks are used only to specify a string, and they
do not form part of the string. When we print a string using the print
instruction, the value of the string, i.e. the sequence of characters within
quotes is printed. Also, note that, within a string, \n denotes the beginning of
a new line. When a string having \n is printed, everything after \n
(excluding \n) is printed on the next line. In this section, we shall study
basic operations on strings. Let us begin with the concatenation operator (+),
which is used to produce a string by concatenating two strings; for example,
the expression 'hello ' + '!!' yields the string 'hello !!'. Similarly,
the expression 'how' + ' are' + ' you?' yields 'how are you?' (=
('how' + ' are') + ' you') as shown below:
'hello !!'
>>> 'hello' * 5
'hellohellohellohellohello'
Relational operators are used for comparing two expressions and yield True
or False. In an expression involving both arithmetic and relational
operators, the arithmetic operators have higher precedence than the
relational operators. In Table 1.2, we give a list of relational operators
Python 3 does not allow string values to be compared with numeric values
The logical operators not, and, and or are applied to logical operands
True and False, also called Boolean values, and yield either True or
False. The operator not is a unary operator, i.e. it requires only one
operand. The expressions not True and not False yield False and True,
respectively. An expression involving two Boolean operands and the and
operator yields True if both the operands are True, and False otherwise.
Similarly, an expression involving two Boolean operands and the or
operator yields True if at least one operand is True, and False otherwise.
This is shown in Table 1.3.
False
i.e. False
parentheses have the highest precedence while logical operators have the lowest precedence
Variables provide a means to name values so that they can be used and
manipulated later on. Indeed, a program essentially carries out variable
manipulations to achieve the desired objective. For example, variables
english, maths, and commerce may be used to deal with the marks obtained
in these subjects, and the variables totalMarks and percentage may be
used to deal with aggregate marks and the overall percentage of marks,
respectively. If a student has obtained 57 marks in english, this may be
expressed in Python using the following statement:
>> english = 57
assignment statement
57
in Python, variables are often called names
>>> commerce = 62
In this example, we assume that maximum mark in each subject is 100. Total
marks in these three subjects and overall percentage can be computed using
another sequence of statements:
>>> totalMarks = english + maths + commerce
>>> percentage
61.0
Assignment Statement
As discussed above, values are assigned to variables using an assignment
statement. The syntax for assignment statement is as follows:
variable = expression
totalMarks
TOTAL_MARKS
>>> age = 24
>>> Age
Age
Python is case-sensitive.
age and Age are different names
>>> b = a
>>> a = 7
more than one variable may refer to the same object
Shorthand Notation
By now, we have seen several examples of assignment statements. The
following assignment statement updates value of the variable a by adding 5
to the existing value.
>> a = a + 5
a shorthand notation
>>> a = a ** (b + c)
can be written as follows, respectively:
>>> a += b + c
>>> a **= b + c
is equivalent to
a <operator>= b
Thus, we can specify more variables than one on the left side of an
assignment statement, and the corresponding number of expressions, like
<expr1>, <expr2>, ..., <exprK>, on the right side. Formally, the syntax
for an assignment statement may be described as follows:
<name1>, <name2>, ..., <nameK> = <expr1>, <expr2>, ..., <exprK>
This notation can be used to enhance the readability of the program. We may
also assign a common value to multiple variables, for example, the
assignment statement
>>> totalMarks = count = 0
assigning same value to multiple variables in a single statement
>>> count = 0
Suppose we wish to swap values of two variables, say, num1 and num2. For
this purpose, we use a variable temp as follows:
>>> num1, num2 = 10, 20
20 10
we save the value of the variable num1 in the variable temp, so that the same
can be assigned to the variable num2 in the following assignment statement.
A variable that is used to hold the value of another variable temporarily is
often called temporary variable.
1.7 KEYWORDS
Keywords are the reserved words that are already defined by the Python for
specific uses. They cannot be used for any other purpose. Hence, make sure
that none of the names used in a program should match any of the keywords.
The list of the keywords in Python 3.6 is given in Fig. 1.4.
keywords have special meaning
So far, we have done all work using Python shell, an interactive environment
of IDLE. The definitions of objects, names, etc., exist only during an IDLE
session. When we exit an IDLE session, and start another IDLE session, we
must redo all computations. This is not a convenient mode of operation for
most of the computational tasks. Python provides another way of working
called script mode. All the instructions necessary for a task are stored in a
file often called a source file script, program, source code, or a module.
Python requires that such a file must have extension .py or .pyw. To create
a script, Python IDLE provides a New Window option in the File menu. On
clicking the New Window option, a Python Editor window opens, where we
can write a sequence of instructions, collectively called a program or a
script. A script can be saved using the Save As option in the File menu. It
may be executed in shell by selecting Run Module option in the Run menu.
As a trivial example, the script readNshow in Fig. 1.5 takes two numbers
from the user and outputs these numbers. On executing the first line of the
script, the system waits for the user to enter a number which is assigned to
the variable number1. On executing the second line of the script, the system
waits for the user to enter another number which is assigned to the variable
number2. The values of variables number1 and number2 are displayed on
executing the third line of the script.
The problem with the above script is that as we have developed it just
now, we remember that the program requires two numbers as the input.
However, if we wish to use it a month later, we may forget what inputs are
required by the program, and we will need to examine the program again
before running it. Surely, we would like to avoid this effort. A good
programming practice is to display to the user what data is to be entered.
The modified script readNshowWell (Fig. 1.6) achieves this by displaying a
message to the user as the system waits for user input.
SUMMARY
10. A variable is a name that refers to a value. We may also say that a variable associates a name with a
data object such as number, character, string, or Boolean.
11. Values are assigned to variables using assignment statement. The syntax for assignment statement is
as follows:
variable = expression
where expression may yield any value such as numeric, string, or Boolean.
12. In an assignment statement, the expression on the right-hand side of the equal to operator (=) is
evaluated and the value so obtained is assigned to the variable on the left-hand side of the = operator.
13. A variable name must begin with a letter or _ (underscore character). It may contain any number of
letters, digits or underscore characters. No other character apart from these is allowed.
14. Python is case-sensitive. Thus, age and Age are different variables.
15. The shorthand notation for a = a <operator> b is
a <operator>= b
16. In Python, multiple assignment statements can be specified in a single line as follows:
<name1>, <name2>, ... = <expression1>, <expression2>, ...
17. A keyword is a reserved word that is already defined by Python for a specific use. Keywords cannot
be used for any other purpose. The list of the Python keywords is given below:
EXERCISES
1.
2.
3.
11. How does the effect of the following two statements differ?
1. x += x + 10
2. x = x + 10
CHAPTER 2
FUNCTIONS
CHAPTER OUTLINE
2.1 Built-in Functions
2.2 Function Definition and Call
2.3 Importing User-defined Module
2.4 assert Statement
2.5 Command Line Arguments
In this chapter, we will learn how simple statements can be put together in
the form of functions to do useful tasks. We can easily deal with problems
whose solutions can be written in the form of small Python programs. As a
problem becomes complex, the program also increases in size and
complexity, and it is impossible for a programmer to keep track of the data
and control statements in the whole program. Indeed, experience has shown
that the most programmers cannot keep track of more than ten statements or
so at a time. Therefore, we cannot apply the crude method of attacking the
whole problem at the same time. Instead, we opt for a more systematic way
of problem solving by dividing the given problem into several sub-problems,
finding their individual solutions in the form of functions (also called sub-
programs) and integrating them to form the final program. If necessary, the
sub-problems may be further divided into still smaller problems, and the
process of dividing a problem into a set of problems of smaller size can be
continued up to any appropriate level. Later on, solutions of the small
problems are merged to form programs aimed at solving the complex
problem. This approach to problem solving is called stepwise refinement
method or modular approach.
input Function
The function input enables us to accept an input string from the user
without evaluating its value. The function input continues to read input text
from the user until it encounters a newline, for example:
>>> name
'Alok'
The variable name now refers to the string value 'Alok' entered by the user.
Making use of a function is called calling the function, or invoking the
function. In the above statement, the string 'Enter a name: ' specified
within the parentheses is called an argument. So, we say that the function
input has been called with the argument 'Enter a number: '. Further, we
say that the function returns the string entered by the user ('Alok') which is
subsequently assigned to the variable name.
eval Function
The function eval is used to evaluate the value of a string, for example:
evaluating a string
>>> eval('15')
15
>>> eval('15+10')
25
Composition
nested calls: output of inner function serves as input argument to outer function
>>> n1
234
>>> n2
38.0
Note that the inputs 234 and 12.0 + 13.0 * 2 were correctly evaluated as
int and float values respectively.
print Function
Recall from the previous chapter that the following statement enables us to
produce the output in Python. On execution of the statement:
print('hello')
the system will output hello:
>>> print('hello')
hello
2 567 234
hello Raman 2 + 2 = 4
Note that when several values are included in a call to the print function
separated by commas, they are displayed on the same line, separated by
single spaces between them. It is important to point out that after printing the
values of the expressions included as arguments while invoking the print
function, the print control moves to the beginning of the next line. Thus, the
output of a sequence of print function calls appears on separate lines. In the
next example, the output of a single call to the print function is displayed
on two lines:
>>> print('hello', name, '\n2 + 2 =', 2 + 2)
hello Raman
2 + 2 = 4
The backslash character \ has a special meaning. The character sequence \n
serves as a line feed character and transfers the print control to the beginning
of the next line. The character sequences like \n and \t are called escape
sequences. Next, we give an example of the escape sequence \t which is
interpreted as a tab character:
hello Raman 2 + 2 = 4
type Function
Values or objects in Python are classified into types or classes, for example,
12 is an integer, 12.5 is a floating point number, and 'hello' is a string.
Python function type tells us the type of a value, for example:
determining data type
<class 'type'>
round Function
The round function rounds a number up to specific number of decimal
places, for example:
89.62 90 90.0
34.1 -35
When calling the function round, the first argument is used to specify the
value to be rounded, and the second argument is used to specify the number
of decimal digits desired after rounding. In a call to function round, if the
second argument is missing, the system rounds the value of first argument to
an integer, for example, round(89.635) yields 90.
Type Conversion
Let the variables costPrice and profit denote cost price and desired profit
for a grocery item in a shop. We wish to compute the selling price for the
item (Fig. 2.1).
Enter profit: 5
Note that the input function considers all inputs as strings. Therefore, the
value of sellingPrice shown above as 505 is the concatenation of the input
values of costPrice and profit, i.e., '50' and '5', respectively. To
convert the input strings to equivalent integers, we need to use the function
int explicitly (Fig. 2.2):
Enter profit: 5
Selling Price: 55
We may also use float function if we wish to take decimal value as input
from the user. The function str can be used to convert a numeric value to a
str value. Next, we give some examples, illustrating the use of some
functions for type conversion:
conversion from int to str
>>> str(123)
'123'
>>> float(123)
123.0
>>> int(123.0)
123
>>> str(123.45)
'123.45'
>>> float('123.45')
123.45
>>> int('123.45')
int('123.45')
Note that last example yields an error since function int cannot be used for
converting a string containing decimal value to its integer equivalent. We
already know that the eval function converts the value of the argument to
the appropriate type, for example:
>>> eval('50+5')
55
95.6
59
'you'
'Sir'
Note that the integer and floating point values are compatible for
comparison. However, numeric values cannot be compared with string
values.
pow Function
The function pow(a, b)computes a . Thus, given the side of a cube, if we
b
computing power
else:
The if-else statement used here will be discussed in detail in the next
chapter. In the case of multiple players, using the above approach for
deciding who will play the first turn will make the program complex. The
random module provides another function randint that randomly chooses an
integer in the specified range; for example, randint(1,n) will randomly
generate a number in the range 1 to n (both 1 and n included).
name of the module, followed by the separator dot, should precede function name
>>> math.ceil(3.4)
>>> math.floor(3.7)
>>> math.fabs(-3)
3.0
>>> math.exp(2)
7.38905609893065
>>> math.log(32, 2)
5.0
>>> math.log10(100)
2.0
>>> math.pow(3, 3)
27.0
>>> math.sqrt(65)
8.06225774829855
>>> math.cos(math.pi)
-1.0
>>> math.sin(math.pi/2)
1.0
>>> math.tan(math.pi/4)
0.9999999999999999
>>> math.acos(1)
0.0
>>> math.asin(1)
1.5707963267948966
>>> math.atan(1)
0.7853981633974483
>>> math.degrees(math.pi)
180.0
>>> math.radians(180)
3.141592653589793
Note that the name of a function in a module is preceded by the name of the
module and the separator '.'.
>>> help(math.cos)
cos(...)
cos(x)
print a triangle
print a square
If we replace the above outline with Python code, our job would be done.
We call this script picture and store it in the file picture.py as per Python
convention (Fig. 2.4).
In Fig. 2.4 (and elsewhere in the book), line numbers are not part of
Python program but used only for the purpose of explanation. In this
program, line number 2 begins with # (hash). This line is a comment. A
comment is a non-executable text in the program that is not processed by the
system. Comments are ignored by the Python interpreter as if they are not
present. They are placed to make the intent of Python code clear to the
reader. In general, if # appears anywhere in a line in the Python program,
rest of the line is ignored by the system. For example:
multi-line comment
statements
syntax for function definition
Having developed the function main in the script picture, we would like
to execute it. To do this, we need to invoke the function main. This can be
done by performing the following two steps:
We can eliminate the need to call function main explicitly from the shell, by
including in the script picture, the following call to function main:
if __name__=='__main__':
main()
The revised script is shown in Fig. 2.5. Every Python module has a built-in
variable called __name__ containing the name of the module. When the
module itself is being run as the script, this variable __name__ is assigned the
string '__main__' designating it to be a __main__ module. The __main__
module, i.e. script picture in this case (Fig. 2.5), comprises:
built-in variable __name__
you may read this paragraph casually for now, and come back to it later when you have some
experience in programming
Fig. 2.5 Program to print a triangle followed by square (picture.py)
The script in Fig. 2.6 works as follows: Python makes a note of the
definition of functions triangle, square, and main as it sees their
definitions. As described above, on the execution of the if statement (line
22), the control is transferred to the function main (line 15). Line 16 being a
comment, is ignored by Python. In line 17, the function triangle is called,
and the body of function triangle gets executed. As the main function calls
the function triangle, it is said to be the caller function, and the function
triangle that is called is said to be the callee function or called function.
function main serves as a caller function for the called functions triangle and square
Fig. 2.6 Program to print a triangle followed by square (picture1.py)
Again, line 2 of the function triangle being a comment, Python ignores it.
Next, lines 3–6 are executed in sequence. On completing execution of the
function triangle, the control is transferred to the statement immediately
following the one that called the function triangle, i.e. at line 18 that prints
a blank line. In line 20, we call the function square. On execution of the
body of function square, the control returns to main function (line 21). As
there are no more statements to be executed in the main, the control now
moves to the line following the statement that invoked the main function,
i.e., call to print function at line 24 in the global frame, which now
executes, and the program comes to an end.
triangle
square
Unlike the scripts picture (Fig. 2.5) and picture1 (Fig. 2.6), often, the
caller and the called functions need to share some information between
themselves. To demonstrate this, we develop a program to print the area of a
rectangle that takes length and breadth of the rectangle as inputs from the
user.
Fig. 2.7 The script shows that function triangle is not being invoked
output: area
computations:
Line 1 of the function definition includes the name of the function (i.e.,
areaRectangle). The names length and breadth within parenthesis in the
function are called parameters. Lines 2–6 constitute a docstring describing
the function. Line 3 describes the overall objective of the function. Line 4
describes each of the inputs to the function and the type of value it takes.
Line 5 indicates that the function would return the area of a rectangle to the
calling function. Area of the rectangle is computed in line 7. Finally, line 8 is
a return statement that returns the area computed in line 7 to the caller
function main. In general, the return statement returns the value of the
expression following the keyword return to the caller function. If there is
no return statement in a function, the function returns the value None to the
caller function on the execution of the last statement of the function. The
value being returned may be assigned to a variable.
return statement returns the value of expression following the return keyword in the absence
of the return statement, default value None is returned
In Fig. 2.9, we give the complete script to compute the area of a rectangle
that takes length and breadth of the rectangle as inputs from the user. The
variables and expressions whose values are passed to the called function are
called arguments. At the point of call to function areaRectangle in line 19,
values of arguments lengthRect and breadthRect are passed to parameters
length and breadth, respectively. These values are used inside the function
areaRectangle, for computing area. While the parameters length and
breadth are called formal parameters, or dummy arguments, lengthRect
and breadthRect used for invoking the function areaRectangle are called
actual parameters, or arguments. The arguments in call to the function must
appear in the same order as that of parameters in the function definition.
Area of rectangle is 20
End of program
Figure 2.10 shows how the values of the arguments lengthRect and
breadthRect are passed to the parameters length and breadth at the point
of call to function areaRectangle. The figure showing the correspondence
between arguments and parameters is sometimes called a memory map.
Function help
Recall that function help can be used to provide a description of built in
functions. Function help can also be used to provide description of the
function defined by user. All one needs to do is to add a multi-line comment.
Function help works by retrieving the contents specified using multi-line
comments. For example, consider the function given in Fig. 2.12.
areaRectangle(length, breadth)
function help retrieves first multi-line comment from the function definition
If there are more than one multi-line comments, only the first multi-line
comment is displayed.
function call uses default value if value for a parameter is not provided
>>> areaRectangle(5,2)
10
Keyword Arguments
In the programs developed so far, the order of arguments always matched
the parameters in the function definition. However, Python allows us to
specify arguments in an arbitrary order in a function call, by including the
parameter names along with arguments. The arguments specified as
parameter_name = value
are known as keyword arguments. For example, in the following call to the
function areaRectangle, the order of arguments is different from the one in
the function definition.
areaRect = areaRectangle(breadth = 2,
length = 5)
return a + b + c + d + e + f + g + h
62
Recall from Section 2.1 that to access functions such as floor, ceil, and
log given in Table 2.1, we need to import math module that includes the
definitions of these functions. Similarly, to access a function from a user-
defined module (also known as program or script that may comprise
functions, classes, and variables), we need to import it from that module. To
ensure that the module is accessible to the script, we are currently working
on, we append to the system's path, the path to the folder containing the
module. Once this is done, we can import the module by using an instruction
like:
import name-of-the-module
Once this is done, we can access all the functions defined in it by using the
following notation: module name, followed by a dot, followed by the
function name as shown in line 14 in Fig. 2.14.
Fig. 2.14 Program to find area of floor (floorArea.py)
Length: 500
Width: 400
200000
2.4 ASSERT STATEMENT
assert condition
Fig. 2.15 Program to find percentage (percent.py)
in <module>
main()
in main
AssertionError
Let us now revisit the program to find area of the rectangle. So far, we have
executed the Python programs in Python IDLE. However, we may choose to
run the Python script from the command line interface. For example, the
script area (Fig. 2.9) may be run from the command prompt by executing
the following steps:
F:\PythonCode\Ch02>python area.py
So far, we have been taking inputs from the user in an interactive manner.
However, we may also take the inputs as command line arguments while
executing a script from the command prompt as follows:
F:\PythonCode\Ch02>python area1.py 20 10
End of program
usually whitespace(s) are used for separating the command line arguments from each other
python area1.py 20 10
command line arguments length and breadth that follow the script name
(area1.py) are stored in argv[1] and argv[2] respectively.
Fig. 2.16 Program to compute area of rectangle using command line inputs (area1.py)
SUMMARY
1. Functions provide a systematic way of problem solving by dividing the given problem into several
sub-problems and finding their individual solutions.
2. Built-in functions are predefined functions that are provided by the Python environment.
input function enables us to accept an input string from the user without evaluating its value.
print function enables us to produce output in Python.
eval function is used to evaluate the value of a string.
type function tells us the type of value.
round function rounds a number up to a specified number of decimal places.
int function can be used to convert a value to its corresponding integer.
str function can be used to convert a value to its corresponding string.
max and min functions are used for finding maximum and minimum out of several values,
respectively.
pow function is used to find some power of a number.
random function of the module random is used for generating a random number in the range
[0,1).
randint(1,n) function of the module random is used for generating a random number in the
range [1, n].
math module contains several mathematical functions such as log, ceil, and sin.
3. A comment is a non-executable text in the program that is ignored by the Python interpreter as if is
not present. The comments are used to make the intent of Python code clear to the reader. A single-
line comment starts with character #, whereas a multi-line comment may be specified using docstring.
4. The code following colon must be indented i.e. shifted to the right.
5. The variables that appear in function definition enclosed in parentheses immediately following the
name of the function are called formal parameters or dummy parameters. When the function is called,
they are replaced by the values called arguments. The arguments in call to the function must appear in
the same order as that of the parameters in the function definition.
6. A user-defined module is also known as program or script that may comprise functions, classes, and
variables.
7. The function parameters may be assigned initial values, called default values. All non-default
parameters must appear before the default parameters.
8. Python allows us to specify arguments in an arbitrary order in a function call, by including the
parameter names along with arguments. An argument specified as
parameter_name = value
is known as keyword argument.
9. import statement is used for importing a module that may be user-defined or built-in.
10. assert statement is used for error checking. If the condition specified in an assert statement fails to
hold, Python responds with an assertion error.
EXERCISES
1. What will be the output produced by each of the following function calls:
math.ceil(65.65) math.ceil(65.47)
math.fabs(-67.58) math.fabs(3)
math.exp(2.7) math.log(45,2)
math.log10(1000) math.pow(4,1/2)
math.sqrt(121) math.radians(30)
math.degrees(math.pi/2)
2. Give the range in which value of variable x may lie on execution of the following statements:
import random
x = random.random() + 5
3. Evaluate the following expressions using Python shell. Assume that ASCII coding scheme is used for
character data.
2.
5. Consider the following function:
def nMultiple(a = 0, num = 1):
return a * num
What will be the output produced when the following calls are made:
1. nMultiple(5)
2. nMultiple(5, 6)
3. nMultiple(num = 7)
4. nMultiple(num = 6, a = 5)
5. nMultiple(5, num = 6)
6. Study the program segments given below. Give the output produced, if any.
1. def test(a, b):
a = a+b
b = a-b
a = a-b
print('a = ', a)
print('b = ', b)
test(5,8)
2. def func():
pass
a = func()
print(a)
7. Write a function areaTriangle that takes the lengths of three sides: side1, side2, and side3 of the
triangle as the input parameters and returns the area of the triangle as the output. Also, assert that
sum of the length of any two sides is greater than the third side. Write a function main that accepts
inputs from the user interactively and computes the area of the triangle using the function
areaTriangle.
8. Create the following scripts importedModule (Fig. 2.17) and mainModule (Fig. 2.18) in the working
directory, execute the script mainModule and justify the output.
Fig. 2.17 (importedModule.py)
9. Rewrite the code in question 7 so that it takes inputs as command line arguments.
!
This section may be skipped on first reading without loss of continuity.
CHAPTER 3
CONTROL STRUCTURES
CHAPTER OUTLINE
3.1 if Conditional Statement
3.2 Iteration (for and while Statements)
The functions that we have developed so far had the property that each
instruction in a function was executed exactly once. Further, the instructions
in these functions were executed in the order in which they appeared in the
functions. Such functions are called straight line functions. However, real
life problems would usually require non-sequential and repetitive execution
of instructions. Python provides various control structures for this purpose.
In this chapter, we will study the following control structures with suitable
examples: if, for, and while.
control structures are used for non-sequential and repetitive execution of instructions
Suppose a teacher grades the students on a scale of 100 marks. To pass the
examination, a student must secure pass marks (say, 40). Before announcing
the results, the teacher decides to moderate the results by giving maximum
of two grace marks. Thus, if the student has scored 38 or 39 marks, he or she
would be declared to have scored 40 marks. Let us see how script moderate
(Fig. 3.1) achieves this.
First, we set passMarks equal to 40 in the function main (Fig. 3.1). The
next statement prompts the user to enter the marks obtained by a student. As
marks entered by the user is of type str, we transform it to an integer
quantity intMarks using the function int. In line 23, we invoke the function
moderate defined in lines 1–12 with the arguments intMarks and
passMarks. Inside the function moderate (line 10), we check whether the
value of the input parameter marks is less than passMarks by one or two
using the condition marks == passMarks-1 or marks == passMarks-2.
The assignment statement in line 11 gets executed only if the condition
evaluates to True. Next, the function moderate returns marks (possibly
modified) to the main function. The value returned by the function moderate
is assigned to the variable moderatedMarks (line 23). Finally, we print
moderatedMarks in line 24. If we run the script in Fig. 3.1, the system
responds by asking the marks and displays moderatedMarks.
Fig. 3.1 Program to moderate the results by giving maximum of two grace marks (moderate.py)
marks to be updated to passMarks based on a condition
>>>
Enter marks: 38
Moderated marks: 40
>>>
Enter marks: 39
Moderated marks: 40
>>>
Enter marks: 40
Moderated marks: 40
statements following if clause are executed only if the condition in the clause evaluates to
True
flow-diagram of if statement
Fig. 3.3 Flow diagram of if statement
Fig. 3.4 Program to authenticate user and allow access to system (authenticate.py)
The function main in Fig. 3.4 prompts the user to enter the password,
which is stored in the variable password. Next, the function
authenticateUser beginning line 1 is called in line 22 with the argument
password. Inside the function authenticateUser, the value of this input
parameter is matched against the password 'magic' (already known to the
system), using the condition password == 'magic' (line 7). The assignment
statement in line 8 gets executed only if the condition holds True. Similarly,
if the condition specified in line 9 holds True, the assignment statement in
line number 10 gets executed. String value returned by the function
authenticateUser (line 11) is assigned to the variable message in line 22.
Finally, we print a message indicating whether the user is authorized to use
the system in line 23.
password validation
If we run the script in Fig. 3.4, the system responds by asking for the
password and displays a suitable message indicating successful or
unsuccessful login attempt.
LOGIN SYSTEM
==============================
Password mismatch !!
LOGIN SYSTEM
==============================
Login Successful !!
Welcome to system.
You must have noted in the previous program that there were two if
statements for checking the correctness and incorrectness of the password
entered by a user. However, it is obvious that if password is not correct, it
must be incorrect. Indeed, Python provides an if-else statement to handle
such situations. Let us have a look at the modified script given in Fig. 3.6.
Fig. 3.6 Program to authenticate user and allow access to system (authenticate.py)
If the condition in line 7 holds True, the statement in line number 8 (body
of if statement) gets executed. If the condition in line 7 fails to hold, control
is transferred to the assignment statement in line 10 (body of the else part).
In Fig. 3.7, we illustrate the if-else statement with the help of a flowchart.
Conditional Expression
Python allows us to write conditional expressions of the form given below:
use of if-else conditional statement to validate the password entered by the user
If the condition holds True, the conditional expression yields the value of
expression1, otherwise, it yields the value of expression2. For example,
the following piece of code
if password == 'magic':
else:
may be replaced by
message = ' Login Successful !!\n ' if password == 'magic' else
' Password mismatch !!\n '
When there is more than one way of doing a thing, one should prefer the one
which enhances the readability of the program. As you might have noted
that the use of an if-else statement is more readable as compared to a
conditional expression. Although a conditional expression happens to be
more concise, we discourage the use of conditional expressions for the
beginners.
else:
The script grade (Fig. 3.9) takes marks of a student as input from the user
and assigns a grade on the bases of marks obtained using if-elif-else
statement. In Fig. 3.10, we illustrate the if-elif-else statement with the
help of a flowchart.
Fig. 3.9 Program to assign grade on the basis of marks obtained (grade.py)
else:
Maximum number is 89
We can simplify the above program using nested function approach (Fig.
3.13). We define a function max2 that takes two numbers as an input and
computes their maximum. Next, we make use of max2 to define the function
max3 that finds the maximum of three numbers. We say that the function
max2 is nested within the function max3. The functions max2 and max3 are
known as inner function and outer function, respectively.
Suppose we wish to read and add 100 numbers. Using the method discussed
so far, we will have to include 100 statements for reading and an equal
number of statements for addition. If the numbers to be read and added were
10,000 instead of 100, we can well imagine the gigantic appearance of the
program that would run into well over a hundred pages. Surely, we cannot
think of doing that. The process of repetitive execution of a statement or a
sequence of statements is called a loop. Using loops, we need to write only
once the sequence of statements to be repeatedly executed. Execution of a
sequence of statements in a loop is known as an iteration of the loop.
iteration of a loop
In the function summation (script sum, Fig. 3.14), the variable total is
initialized to zero. Next, for loop is executed. The function call range(1,n
+ 1) produces a sequence of numbers from 1 to n. This sequence of numbers
is used to keep count of the iterations. In general,
total += count
Next, we develop a program to read and add the marks entered by the user
in n subjects, and subsequently use the total marks so obtained to compute
the overall percentage of marks (Fig. 3.15). The number of subjects n is
taken as the input from the user. The variable totalMarks is initialized to
zero in line 8 before the for loop. The sequence of statements at lines 11,
12, and 13 forms the body of the loop and is executed n times, once for each
value of i. We say that the loop iterates for each value of i in the sequence
1, 2, …, n. Once the execution of the loop completes, percentage is
computed.
Fig. 3.15 Program to compute percentage (percentage.py)
On executing the script percentage (Fig. 3.15), Python prompts the user
to enter the number of subjects and the marks, and responds by displaying
the percentage.
Number of subjects: 5
Enter marks
Subject 1: 75
Subject 2: 80
Subject 3: 85
Subject 4: 90
Subject 5: 95
<block S of statements>
Here, variable refers to the control variable used for counting, which is set
in the beginning to the first value in a sequence of values (e.g., range(10),
'abcdef'). Subsequently, in each iteration of the loop, the value of the
control variable is replaced by the successor value in the sequence. The
process of executing the sequence S and replacing the current value of
control variable by its successor in sequence is repeated until the entire
sequence is exhaused.
4 * 2 = 8
4 * 3 = 12
4 * 4 = 16
4 * 5 = 20
4 * 6 = 24
4 * 7 = 28
4 * 8 = 32
4 * 9 = 36
4 * 10 = 40
By now you must have noted that Python output is aligned on the left-hand
side, for example:
>>> print(7)
>>> print(100)
100
However, the numeric output looks good, if aligned on the right-hand side.
For this purpose, we need to specify how many places we would like to
reserve for printing a value, for example, the format string '%5d' may be
used to indicate that at least five positions are to be reserved for an integer
value.
>>> '%5d'% 45
' 45'
45
12345
Enter a number: 2
Enter a number: 18
Enter a number: 15
Enter a number: 15
Enter a number:
Infinite Loops
Sometimes we want a while loop to continue indefinitely until an enabling
event takes place, for example, the screen of a laptop may remain off until a
key is pressed. For this purpose, we make use of a while loop based on a
condition that always evaluates to True. Such a loop is known as an infinite
loop, for example:
import time
while True:
try:
print('Loop processing....')
time.sleep(1)
except KeyboardInterrupt:
in the absence of a keyboard interrupt, the while loop will execute infinitely.
total += count
total += count
count += 1
Note that for computing the sum of first few natural numbers, the use of for
loop is more elegant and easy as compared to the while loop. Out of several
control structures which may be used at a place, it is the discretion of the
programmer to choose the simple and elegant one.
We note that in the first row, one '*' is to be output, in the second row two
'*'s are to be output, and so on. So, in general, the ith row will have i
'*'s. With these remarks, we modify the outline of the code given above:
print('*' * i)
for loop for printing a right triangle
Let nSpaces denotes the number of leading spaces in a row. We note that
there are no leading spaces in the first row. So, we set
nSpaces = 0
For every subsequent row, the number of leading spaces nSpaces increases
by one in each row. Next, let nStars denote the number of stars to be printed
in a row. We note that in the first row, the number of stars to be printed is 2
* nRows – 1. So, we set
nStars = 2 * nRows - 1
We also note that the number of stars to be printed decreases by two for
every subsequent row. With these remarks, we modify the outline of the
above piece of code as follows:
nSpaces = 0
nStars = 2 * nRows - 1
nStars -= 2
nSpaces += 1
In light of the above discussion, we give the complete script in Fig. 3.23:
Fig. 3.23 Program to print right triangle and inverted triangle (triangle.py)
In the above script, the figures right triangle and inverted triangle
comprise '*' only. However, we may make the above program more general
by printing the figures made using a character provided by the user. For this
purpose, the function rightTriangle may be modified as follows (Fig.
3.24):
Fig. 3.24 Function rightTriangle
In order that the output of the program appears nicely, we would like that
each number be printed using at least the number of positions specified in
the format string. This may be done as follows (5 digits are reserved for each
number which is left padded with spaces):
>>> for i in range(1,4):
print('{0: >5}'.format(i*9))
18
27
Also, we would like that the output of several calls to print function may be
printed on the same line. For this purpose, we we need to use empty string
('') in place of the default newline. This can be achieved using keyword
argument end. For example,
>>> for i in range(1,4):
print('{0: >5}'.format(i*9), end = '')
9 18 27
using empty string as the terminator in print function by changing the default value of
keyword argument end
print('{0: >5}'.format(i*9))
is equivalent to:
>>> for i in range(1,4):
Next, to print one row of a multiple of all numbers i.e. multiples of num in
the range (1, nTables+1), we may iterate over num using a for loop as
follows:
for num in range(1, nTables + 1):
print('{0: >2}'.format(num),'*',\
'{0: >2}'.format(multiple),'=', \
'{0: >3}'.format(num*multiple),'\t',
end = '')
print()
Note the use of the keyword argument end in the print function under the
for loop, as we want the output of the entire loop to appear on the same line.
Finally, when the for loop completes, invoking the print function moves
the control to the next line for printing the next row of the multiplication
table. The character backslash (\) used at the end of second and third line is a
line continuation character that can be used for wrapping long lines i.e. if we
wish to extend a statement over multiple lines. The complete script to print
multiplication table is shown in Fig. 3.27.
use continue statement to transfer the control to next iteration of the loop
INVALID MARKS !!
INVALID MARKS !!
Number of Subjects: 4
Percentage: 72.5
In the above series, the first term is x/1. The second term can be computed
by multiplying the first term by -x /(2*3). Similarly, the third term in the
2
on. In general, we can obtain a new term of the series by multiplying the
previous term by -x and dividing this product by the product of the next two
2
x/1*(-x2)/(2*3) = -x3/3!
-x3/3!*(-x2)/(4*5) = x5/5!
To code the above idea, we set multBy equal to -x and initialize nxtInSeq
2
Since the given series is an infinite one, and we can do only finite
computations on a computer, we need to decide when to stop. We keep on
adding more terms until the absolute value of term becomes smaller than a
predefined value, say, epsilon. In Fig. 3.32, we present the complete
function mySine that computes sine(x) as sum of the above series.
Fig. 3.32 Function mySine (sine.py)
SUMMARY
1. Control statements (also called control structures) are used to control the flow of program execution
by allowing non-sequential or repetitive execution of instructions. Python supports if, for, and
while control structures. In a control statement, the Python code following the colon (:) is indented.
2. if statement allows non-sequential execution depending upon whether the condition is satisfied.
The general form of if conditional statement is as follows:
if < condition >:
< Sequence S of statements to be executed >
EXERCISES
1. Write an assignment statement using a single conditional expression for the following if-else code:
if marks >=70:
remarks = 'good'
else:
remarks = 'Average'
2. Study the program segments given below. In each case, give the output produced, if any.
1. total = 0
count = 20
while count > 5:
total += count
count -= 1
print(total)
2. total = 0
N = 5
for i in range(1, N+1):
for j in range(1, i+1):
total += 1
print(total)
3. total = 0
N = 10
for i in range(1, N+1):
for j in range(1, N+1):
total += 1
print(total)
4. total = 0
N = 5
for i in range(1, N+1):
for j in range(1, i+1):
total += 1
total -=1
print(total)
5. total = 0
N = 5
for i in range(1, N+1):
for j in range(1, N+1):
total += i
print(total)
6. total = 0
N = 5
for i in range(1, N+1):
for j in range(1, i+1):
total += j
print(total)
7. total = 0
N = 5
for i in range(1, N+1):
for j in range(1, N+1):
total += i + j
print(total)
8. total = 0
N = 5
for i in range(1, N+1):
for j in range(1, i+1):
for k in range(1, j+1):
total += 1
print(total)
9. number = 72958476
a, b = 0, 0
while (number > 0):
digit = number % 10
if (digit % 2!= 0):
a += digit
else:
b += digit
number /= 10
print(a, b)
3. Write a function to determine whether a given natural number is a perfect number. A natural number is
said to be a perfect number if it is the sum of its divisors. For example, 6 is a perfect number because
6=1+2+3, but 15 is not a perfect number because 15≠1+3+5.
4. Write a function that takes two numbers as input parameters and returns their least common multiple.
5. Write a function that takes two numbers as input parameters and returns their greatest common
divisor.
6. Write a function that accepts as an input parameter the number of rows to be printed and prints a
figure like:
7. Write a function that finds the sum of the n terms of the following series:
1. 1 – x /2! + x /4! – x /6! + … x /n!
2 4 6 n
2.
8. Write a function that returns True or False depending on whether the given number is a palindrome.
9. Write a function that returns the sum of digits of a number, passed to it as an argument.
10. Write a program that prints Armstrong numbers in the range 1 to 1000. An Armstrong number is a
number whose sum of the cubes of the digits is equal to the number itself. For example, 370 = 33 + 73
+ 03.
11. Write a function that takes two numbers as input parameters and returns True or False depending on
whether they are co-primes. Two numbers are said to be co-prime if they do not have any common
divisor other than one.
12. Write a function sqrt that takes a non-negative number as an input and computes its square root. We
can solve this problem iteratively. You will recall from high school mathematics that to find the square
root of a number, say 2, we need to solve the equation f(x) = x2 – 2 = 0. To begin with, choose two
numbers a and b so that f(a)<0 and f(b)>0. Now, for the equation f(x) = x2 – 2 = 0, f(1)<0 and
f(2)>0. So, the root of the equation must lie in the interval [a,b] (i.e. [1,2]). We find the midpoint,
say, mid of the interval [a,b]. If f(a)<0 and f(mid)>0, we know that the root of the equation f(x)=0
lies in the interval [a,mid]. However, in the other case, (f(mid)<0 and f(mid)>0), the root of the
equation f(x)=0 must lie in the interval [mid,b]. Thus, for the next iteration, we have reduced the
search interval for the root of the equation to half, i.e. from [a,b] to [a,mid] or [mid,b]. Proceeding
in this way, we find a good approximation to the root of the equation when the length of the search
interval becomes sufficiently small, say, 0.01. The following table depicts the steps for computing
square root approximation for the number 2.
13. Write a function to multiply two non-negative numbers by repeated addition, for example, 7*5 = 7 +
7 + 7+ 7 + 7.
CHAPTER 4
DEBUGGING
CHAPTER OUTLINE
4.1 Testing
4.2 Debugging
When a program fails to yield the desirable result, we say that it contains a
bug. The bug could be an error such as division by zero, invalid type
conversion, using a variable not defined, wrong initialization, or some other
unintended operation being performed. The process of discovering the bugs
and making the program bug-free is called debugging. In this chapter, we
discuss some debugging techniques.
4.1 TESTING
We test this script on various permutations of the inputs: 10, 20, 30,
namely:
1. 30, 20, 10
2. 30, 10, 20
3. 20, 10, 30
4. 20, 30, 10
5. 10, 30, 20
6. 10, 20, 30
Fig. 4.1 Program to find the maximum of three numbers (max3.py)
It so turns out that the result obtained is correct for all input permutations,
except for the permutations 20, 10, and 30:
>>>
Maximum number is 0
Thus, a bug persists in the program that needs to be detected and removed.
4.2 DEBUGGING
There are various Python debugging tools such as pdb, pudb, pydb, and
pydbgr. In this section, we will discuss Python's built-in debugger pdb,
which is an interactive tool that helps in examining the code execution step
by step. It allows us to stop the execution of a program at a chosen
instruction called a break point, and evaluate the various expressions in the
current context. The debugger also allows us to examine the current vicinity
of the code, as well as the status of various objects in the current function
being executed which collectively constitute the stack frame corresponding
to that function.
>>> pdb.run('max3.main()')
> <string>(1)<module>()->None
(Pdb)
Python debugger uses the prompt (Pdb) to indicate that the program is
executing in the debugging mode. Another way to execute a program in
debugging mode is by including the following two lines in the script:
import pdb
pdb.set_trace()
Note that including above two lines at the beginning of the program in Fig.
4.1 will increase every line number by two. By invoking the function
set_trace() at the very beginning, the program would run in debugging
mode right from the first instruction to be executed. However, since we
know that the bug exists in the function max3, we may invoke set_trace()
within the function body. Before proceeding further, let us have a look at
debugging commands (Table 4.1).
Execution of the program in Fig. 4.1 in debugging mode for the inputs 20,
10, and 30 is shown in Figs. 4.2 (a), (b1), and (b2).
Fig. 4.2(a) Execution of program max3.py
In Fig. 4.2 (a), line 2 (beginning with greater than sign) shows the script
being executed. Line 3 begins with an arrow and marks the next line to be
executed. Now, Python enters into debugging mode (line 4), and we see the
Pdb prompt. Command h displays all the available commands (lines 4–20).
Command h s displays the description of the step command (lines 24–28).
Command w has been used to inspect the current position in the stack frame
and it displays the stack trace with the statement to be executed next at the
bottom (lines 29–38). Command l (line 39) lists 11 lines in the vicinity of
the current statement (lines 40–50). Next, to execute lines of code, we use s
command. Execution of s command in line 51 yields the definition of
function max3 for future use. Similarly, execution of s command in line 54
yields the definition of function main for future use. Now, line 56 shows that
the step to be executed next is the if statement in the script. On execution of
s command (line 57), the conditional expression yields True, and the
control moves to the next statement that invokes the function main (line 59).
Execution of s command (line 60) moves the control to the beginning of the
function main (line 63):
def main():
Now execution of s command moves the control to the next statement (line
66).
n1 = int(input('Enter first number: '))
At this stage, when s command is executed (line 67), the control steps into
the function input. But we are not interested in the detailed execution of
this function. Instead, we would like to execute the function input as a
single unit. So, we need to move one level up in the stack frame. For this
purpose, we execute the command u (line 72). Subsequently, we execute
command n to execute the current line as a single unit. Thus, user inputs are
entered on the execution of n commands (lines 75–86). At this stage, we
display (n1, n2, n3) (lines 87–88). As we move to the execution of the
function max3, we show the details in a separate figure (Fig. 4.2 (b1)).
n: execute the current statement/function completely and move the control to the next
statement
Fig. 4.2 (b1) Execution of program max3.py
In Fig. 4.2 (b1), using l command in line 1, we inspect the next statement to
be executed. The arrow in line 7 marks the next line to be executed in the
code, i.e. line 28. To completely execute the function max3 with the input
numbers, we use the command n. Now, the control moves to line 29 in the
script. On executing the command n once more, the value of maximum is
displayed which being 0 (line 25) is incorrect. Note that main function is
now completely executed and the control returns to the point following line
32 in the script which invoked the function main. Now we have reached the
end of the script as indicated by the response of the debugger:
f:\pythoncode\ch04\max3.py(32)<module>()->None
Although we know that a bug exists in the function max3, we have still
not found it. To find the bug, we need to step into the function max3 instead
of executing it completely in one go using command n. This has been
shown in Fig. 4.2 (b2). At line 13, on the execution of the command s, the
control transfers to the statement:
def max3(n1, n2, n3):
n2 = 10
n3 = 30
SUMMARY
1. Debugging is the process of examining the source code from the point of determining bugs and
eliminating them to make the program bug-free.
2. Python debugger pdb is an interactive debugger for debugging Python programs. The module pdb
contains the class pdb. The debugger helps in debugging the code step by step, allows setting of
breakpoints, printing some lines in the vicinity of the current line of the code, supports evaluating and
printing the result of evaluating an expression in the current context, and examining the stack frame
3. Function set_trace of module pdb is used to tell the starting point of debugging when the program is
normally run. By mentioning this statement in the very beginning, we intend to specify that the
program should start running in debugging mode from the starting point of its execution.
4. Python debugger pdb supports the following commands:
Command Explanation
h or help In the absence of any argument, it lists all the available commands. With an argument, it prints the description about that command.
w or where Prints the stack trace (sequence of function calls currently in execution, most recent function call being at the beginning). Also shows the
statement to be executed next.
u or up Moves to the stack frame one level up in the stack trace.
d or down Moves to the stack frame one level down in the stack trace.
s or step Executes the current statement and moves the control to either next statement or the function that is being invoked in current statement.
n or next Executes the current statement and moves the control to the next statement. Unlike step command, if a function is being invoked in the
current statement, the invoked function gets executed completely.
r or return Continue execution until the current function returns.
j(ump) lineno Jumps to the given line number for the next statement to be executed.
l or list List 11 lines in the vicinity of the current statement.
b or break Sets the breakpoint at the line specified (name of file optional). If the argument func specifying function name is provided, breakpoint is set
[[file:]line|func[,cond]] at the first executable statement of the function. The second argument may be used to denote a condition which must evaluate to True for
setting the breakpoint.
tbreak Similar to break command. However, breakpoints being set are automatically removed once they are reached.
[[file:]line|func[,cond]]
cl or clear Clears the specified breakpoint. In the absence of any argument, is clears all the breakpoints.
[[file:]line|func[,cond]]
c or continue Continue execution until the breakpoint is reached.
a or args Prints the argument list of the current function along with their values.
p or print(expression) Prints the value of the specified expression in the current context.
q or quit Quits from the Python debugger.
EXERCISES
1. Consider the following Python code intended to compute the sum of n natural numbers. During
testing, it was found that sum printed by program always excludes the last number. Debug the script
(Fig. 4.4) using the debugger discussed in the chapter.
2. Consider the following Python code (Fig. 4.5) intended to print inverse right triangle for given number
of rows nRows. For example, for nRows = 5, the following inverted triangle should be printed:
*****
****
***
**
*
During testing, it was found that program does not produce even the single
line of output. Debug the following script (Fig. 4.5) using the debugger
discussed in the chapter.
3. Consider the Python script given in Fig. 4.6 intended to compute the percentage. During testing, it was
found that percentage computed was not accurate rather rounded to lower bound integer value. Debug
the script (Fig. 4.6) using the debugger discussed in the chapter.
4. Consider the Python script in Fig. 4.7, intended to determine whether the given year is a leap year.
During testing, it was found that an year such as 1800 or 2100, despite being non-leap year, was also
displayed as a leap-year. Debug the function isLeapYear (Fig. 4.7) using the debugger discussed in
the chapter.
Fig. 4.5 Program to print inverse right triangle
Fig. 4.7 Program to determine whether the given year is a leap year
5. Consider the Python script (Fig. 4.8), intended to find HCF. During testing, it was found that program
yields an error for numbers having no common factor other than 1. Debug the script (Fig. 4.8) using
the debugger discussed in the chapter.
CHAPTER OUTLINE
5.1 Objects and Object IDs
5.2 Scope of Objects and Names
In this chapter, we will review the objects and their mapping to names, the
scope of names and parameter passing mechanisms in Python. Recall that in
Python, the terms name and variable are used as synonyms.
a = 5 id(a): 10538176
b = 5 id(b): 10538176
a = 7 id(a): 10538240
b = 5 id(b): 10538176
Recall that when the script objectId is executed, Python makes a note of the
definition of the function main in the global frame. Next, on encountering
the if statement, Python checks whether the name of the current module is
__main__. This being true, the expression __ name__ == '__main__'
evaluates as True, and the function main gets invoked. Next, the statements
in the main function are executed in a sequence. Line 2 being a comment is
ignored by Python. Execution of line 3 creates an int object 5 and assigns it
the name a. This object has a unique object id but can have multiple names
as the execution of the script proceeds. For example, execution of the
statement
b = 3 + 2
in line 5 does not generate a new object, it only associates the name b to the
int object 5 created earlier. Now, a and b have the same object id. However,
execution of line 7 creates an int object 7 and associates it with the name a.
The name b continues to be associated with int object 5 created earlier. It is
important to emphasize that different object ids may be generated when a
script is executed again.
It comes as good news that there are some open source tools available
online that can be used to visualize the execution of Python code. For
example, the following link
http://www.pythontutor.com/visualize.html#mode=display
opens a user interface for visualizing Python code. Figure 5.2 shows this
interface. We select the language Python 3.6 and copy the code in Fig. 5.1 in
the box.
Fig. 5.2 Python tutor interface
We can see the line numbers appearing on the left of each line of code. If we
want to discuss our code with a friend, we can start a shared session by
clicking on the icon Start shared session. This would open a chat box and
generate a link that we can send to our friend. Once he/she copies it in the
browser, we are ready for an interactive session, and each of us can see
actions performed by the other person. For our discussion in this section, we
have chosen the following options:
shared session
Once we have learned to use the visualizer, we can play with other options.
Finally, to visualize the execution of code, we click the icon Visualize
Execution, and a bar showing the progress of program execution appears.
Clicking somewhere on this bar would execute a fraction of the code.
Alternatively, we can use the forward and back buttons. To begin with, we
prefer the latter option. Anytime, we want to modify the code, we can click
on Edit code.
visualize execution
46078432
>>> print(id(2.4))
47619216
>>> print(id(2.4))
47619024
>>> print(id(2.4))
46078432
>>> print(id(2.4))
47619024
>>> print(id(2.4))
47619216
Note that the first three instructions create new objects. However,
subsequent instructions sometimes used the objects created earlier. The del
operator makes a name (i.e. the association between the name and the
object) undefined, for example, examine, the following sequence of
statements:
>>> a = 5
>>> b = 5
10538176 10538176
>>> del a
>>> print(a)
print(a)
>>> print(b)
5
>>> del b
>>> print(b)
print(b)
The first statement creates an int object 5 and binds it to name a. The
second statement does not create a new object. Instead, it binds the same
object to name b and thus creates another reference to int object a. Figure
5.8 illustrates this.
Fig. 5.8 Visualization in Python tutor
del a
b = 5
Step 1 of 5
It means that we are about to execute the first of the five steps in the script.
These five steps are as follows:
<Input Box>
Next, clicking <Forward> executes the call to the function percent and the
visualizer shows the function percent among frames (Fig. 5.16). Note that
the parameters marks and maxMarks are mapped to float objects created
earlier. Next, clicking <Forward>, moves the line pointer to line 7. Another
click executes it and creates the float object percentage having value
90.0. In the visualizer, execution of return statement at line 8 requires two
clicks. On first click, Python creates a return value i.e. the float object (to be
returned to the main function) 90.0 which was created earlier as shown in
Fig. 5.17. The second click returns the value 90.0 from the function percent
by associating it with the variable percentage of function main (line 15).
This completes the execution of line 15 (Fig. 5.18). Now, the control moves
to line 16. Note that the variable percentage of the function main now maps
to the float object 90.0 (Return value returned by function percent).
Further, since we had opted to show exited frames, visualizer is still showing
the lightly highlighted frame for the function percent. Next click shows the
output on execution of line 16 in <Print output> box (Fig. 5.19) and moves
the line pointer to line 17. It also shows return value None associated with
the function main() as it does not return any value. A further click brings us
to the end of the program. The final response of the visualizer is shown in
Fig. 5.20.
5.2.1 Namespaces
As the term suggests, a namespace is a space that holds some names. A
namespace defines a mapping of names to the associated objects. In Python,
a module, class, or function defines a namespace. Names that appear in
global frame (usually outside of the definition of classes, functions, and
objects) are called global names and collectively they define the namespace
called global namespace. The names introduced in a class or function are
said to be local to it. The region in a script in which a name is accessible is
called its scope. Thus, the scope of a name is resolved in the context of the
namespace in which it is defined. For example, each of the functions f1 and
f2 defined in a script may have the name x. Indeed, the variable x defined
in function f1 may refer to an object of type different from that of the object
associated with variable x in the function f2. A namespace maps names to
objects. Being an object-oriented language, definitions of functions and
classes are also examples of objects.
global names: usually appear outside of the definition of all classes, functions, and objects
5.2.2 Scope
LEGB Rule
The scope rules for names in Python are often summarized as LEGB rule.
LEGB stands for local, enclosing, global, and built in. All names defined
within the body of a function are local to it. Function parameters are also
considered local. If a name is not locally found, Python recursively searches
for its definition in an enclosing scope. Names defined in the Python script
but usually outside of any function or class definition are called global.
Python defines some built-in names such as len and abs, which can be
accessed from anywhere in a program.
If a name is not defined locally in function f, but is defined in a function g, that encloses it,
then it is accessible in the function f. If the name being accessed is not defined in the function
g that immediately encloses f, then Python looks for it in a function that encloses g, and so on.
If a name is not defined in any enclosing function, Python looks for it outside of all functions
and if found, it is accessible in function f.
We will illustrate the notion of scope and namespaces with the help of
several examples.
Example 5.1
On executing the script scope1 (Fig. 5.21), Python responds with the
following output:
global a: 4
Example 5.2
On executing the script scope2 (Fig. 5.22), Python responds with the
following output:
global a: 4.2
Note that the name a introduced in line 3 in the function f is local to it and
has associated value 5. Thus defining the value of name a in the function f,
does not affect the value of the global name a.
Example 5.3
On executing the script scope3 (Fig. 5.23), Python responds with the
following output:
inside function g, b: 5
Example 5.4
On executing the script scope4 (Fig. 5.24), Python responds with the
following output:
in outer function g, a =
f()
in f
Example 5.5
On executing the script scope5 (Fig. 5.25), Python responds with the
following output:
in <module>
f()
in f
g()
b = a
Example 5.6
On executing the script scope6 (Fig. 5.26), Python responds with the
following output:
inside f, before calling g, a = 5
after calling f, a = 4
Example 5.7
On executing the script scope7 (Fig. 5.27), Python responds with the
following output:
In this example, in line 4, we tell Python that the variable a used in the scope
of function g is from the global scope by using the keyword global. Thus,
the assignment statement in line 5 modifies the global variable a, the new
value being 4. However, in line 8, as the variable a is locally available, no
attempt is made to search it in the global scope. The value 5 is assigned to
local variable a. Of course, this assignment of value 5 to local variable in
function f does not affect the value of global variable which remains
unaltered i.e. 4.
Fig. 5.27 Program to illustrate scope of variables (scope7.py)
Example 5.8
On executing the script scope8 (Fig. 5.28), Python responds with the
following output:
>>>
global f
inner f
global f
inner f
Traceback (most recent call last):
in <module>
main()
in main
h()
in h
fprime()
In this example, we demonstrate that the same rules apply to resolve the
names of function objects and numeric objects. On execution of line 18,
id(f) is printed for the global function f. Next, the function f is assigned to
the name fprime. On invoking the function f, line 2 is executed. During
execution of function g, the execution of line 6 prints the id(f) for the
global function f. Subsequently, the global function f is redefined in the
function g, and the execution of line 9 prints the id of this modified function
f. However, it does not affect the definition of function fprime. Thus,
execution of line 23 invokes the function fprime, thereby, line 2 is executed
SUMMARY
1. Python visualizer is an online tool for visualizing the execution of Python code.
2. A namespace defines a mapping of names to the associated objects.
3. Names that appear in global frame outside of the definition of classes, functions, and objects are called
global names, and collectively they define the namespace called global namespace.
4. The names introduced in a class, or function are said to be local to it.
5. The region in a script in which a name is accessible is called its scope.
6. The scope rules for names in Python are often summarized as LEGB rule. LEGB stands for local,
enclosing, global and built in.
7. If a name is not locally defined, Python recursively searches for its definition in an enclosing scope.
8. Python defines some built-in names such as len and abs which can be accessed from anywhere in a
program.
EXERCISES
1. Study the program segments given below. Give the output produced, if any.
1. globalVar = 10
def test():
localVar = 20
print('Inside function test : globalVar =',
globalVar)
print('Inside function test : localVar =',
localVar)
test()
print('Outside function test : globalVar =',
globalVar)
print('Outside function test : localVar =',
localVar)
2. globalVar = 10
def test():
localVar = 20
globalVar = 30
print('Inside function test : globalVar =',
globalVar)
print('Inside function test : localVar =',
localVar)
test()
print('Outside function test : globalVar =',
globalVar)
3. globalVar = 10
def test():
global globalVar
localVar = 20
globalVar = 30
print('Inside function test : globalVar =',
globalVar)
print('Inside function test : localVar =',
localVar)
test()
print('Outside function test : globalVar =',
globalVar)
4. def test1():
test1.a = 10
def test2():
test1.a = 8
print('Inside function test2: ', test1.a)
test2()
print('Outside function test2 ', test1.a)
test1()
5. a = 4
def f():
a = 5
def g():
nonlocal a
a = 10
print('inside function g,', 'a = ', a)
def h():
nonlocal a
a = 20
print('inside function h,', 'a = ', a)
h()
g()
print('inside function f,', 'a = ', a)
f()
6. x = 2
def test():
x = x + 1
print(x)
print(x)
7. x = 2
def test():
global x
x = x + 1
print(x)
print(x)
CHAPTER 6
STRING
CHAPTER OUTLINE
6.1 Strings
6.2 String Processing Examples
6.3 Pattern Matching
Elementary forms of data such as numeric and Boolean are called scalar data
types. Several applications require more complex forms of data. For
example, the name of a person, or an SMS may be expressed in the form of a
string. We have already been dealing with strings. In this chapter, we shall
discuss more about strings
6.1 STRINGS
10
Individual characters within a string are accessed using a technique known
as indexing. In Fig. 6.1, we illustrate the notion of indexing with the help of
the string 'Hello Gita'.
Note that the indices start with 0 (index for accessing the first character
from the left) and end with one less than the length of the string (index for
accessing the last character). The following instructions illustrate how to
access individual characters in a string via indices. An index is specified
within the sqaure brackets, for example:
>>> message[0]
'H'
>>> message[6]
'G'
>>> message[index]
'a'
The expression message[0] yields character 'H' since 'H' is stored at index
0. Similarly, the value of len(message) being 10, when index is set equal to
len(message)-1, message[index] yields the last character of the string
message at index 9, i.e. 'a'. Sometimes it is more convenient to access the
elements of a string from the right end. For this purpose, Python provides
negative indices. The negative indices range from - (length of the string) to
-1. For the string message, the negative indices would range from -10 to -1.
Thus, the entire range of valid indices would be {-10, -9, …, -1, 0, 1,
…, 9}. Consequently, message[-1] would yield 'a' and message[-index]
would yield 'e':
negative indexes: used to access the string from the right end
>>> message[-1]
'a'
>>> message[-index]
'e'
If we try to access an index which is not in the valid index range of a string,
IndexError will be generated:
>>> message[15]
message[15]
message[6] = 'S'
'Computer Science'
>>> 'Hi' * 3
'HiHiHi'
'C'
' sir'
6.1.1 Slicing
Sometimes, we need to retrieve a substring, also called a slice, from a string.
This can be done by specifying an index range. For example, to extract the
substring comprising the character sequence having indices from start to
end-1, we specify the range in the form start:end as illustrated below:
>>> message[0:5]
'Hello'
>>> message[-10:-5]
'Hello'
If the value of start or end is not specified, Python assumes 0 as the default
value of start, and length of the string as the default value of end, for
example:
>>> message[:5]
'Hello'
>>> message[5:]
' Sita'
>>> message[:]
'Hello Sita'
'Hello Sita'
>>> message[:15]
'Hello Sita'
>>> message[15:]
''
'Hello Sita'
'ta'
>>> message[6:None]
'Sita'
'HloSt'
>>> message[0:len(message):3]
'HlSa'
6.1.2 Membership
Python also allows us to check for membership of the individual characters
or substrings in strings using in operator. Thus, the expression s in str1
yields True or False depending on whether s is a substring of str1, for
example:
True
True
False
>>> helloSpaced
'h e l l o'
>>> 'Encyclopedia'.count('c')
>>> vowelCount = 0
vowelCount += 'Encyclopedia'.count(ch)
>>> vowelCount
The system responds with 4 as the value of the vowelCount, even though the
number of vowels in the search string 'Encyclopedia' is 5. As the character
'E' was not included in the string vowels, it was not included in counting
too. To include the count of uppercase vowels also, we just need to include
vowels in uppercase also in the string vowels:
vowels = 'AEIOUaeiou'
>>> colors.find('red')
To find the last occurrence of a string, we use the function rfind that scans
the string in reversed order from the right end of the string to the beginning:
>>> colors.rfind('red')
23
If the function find fails to find the desired substring, it returns -1:
>>> colors.find('orange')
-1
'Python is a language'
Python function title can be used to capitalize the first letter of each word
in a string and change the remaining letters to lowercase (if not already so):
>>> 'python IS a PROGRAMMING Language'.title()
'Python Is A Programming Language'
Python functions lower and upper are used to convert all letters in a string
to lowercase and uppercase, respectively. Suppose we want to check for the
equivalence of a pair of email ids. Since email ids are not casesensitive, we
convert both email ids to either uppercase or lowercase before testing for
equality:
>>> emailId1 = 'geek@gmail.com'
False
True
True
>>> 'python'.islower()
True
>>> 'Python'.isupper()
False
True
False
>>> '123'.istitle()
False
True
Function replace
The function replace allows to replace part of a string by another string. It
takes two arguments as inputs. The first argument is used to specify the
substring that is to be replaced. The second argument is used to specify the
string that replaces the first string. For example:
>>> colors.split(',')
['Red', ' Green', ' Blue', ' Orange', ' Yellow', ' Cyan']
Function join
Python function join returns a string comprising elements of a sequence
separated by the specified delimiter. For example,
'I am ok'
"' > I > ' > , > > ' > a > m > ' > , > > ' > o > k > '"
In the first example, the sequence comprises three elements, namely, 'I',
'am', and 'ok', which are combined to form the string 'I > am > ok'.
In the second example, we use space as a delimiter instead of >. In the third
example, each character in the string "'I > am > ok'" is an element of the
sequence of characters in "'I > am > ok'".
>>> name.isalpha()
True
>>> name.isalpha()
False
Note that the blank character is not an alphabet. Similarly, to check the
validity of a mobile number, we may want it to be a string of length 10
comprising of digits only. This can be achieved using functions isdigit and
len:
== 10
True
True
>>> password.isalnum()
True
>>> password.isalnum()
False
>>> name.endswith('Talwar')
True
Similarly, to find whether a person's name begins with Dr. we can use the
function startswith as follows:
>>> name = 'Dr. Vihan Garg'
True
False
>>> str1
b'\xff\xfe\x00\x00m\x00\x00\x00e\x00\x00\x00s\x00\x00\x00s\x00\x
00\x00a\x00\x00\x00g\x00\x00\x00e\x00\x00\x00'
>>> str1.decode('utf32')
'message'
One may also use alternative coding schemes such as utf8 and utf16.
List of Functions
The functions described above are listed in Table 6.1. Note that the original
string S remains unchanged in each case.
Fig. 6.2 Program to find number of matched characters in two strings (matchChar.py)
As we do not wish to distinguish among alphabets based on the case
(lower or upper), we convert the input arguments to lowercase. To keep a
count of the matched characters, we initialize the variable count to 0. The
outer loop works by picking up a character ch1 from temp1 and comparing it
against every character ch2 in temp2 in the nested loop. For each matched
pair, the variable count is incremented by one. At the end of the function,
the value of count is returned. Let us examine an example:
16
Note that the first 'R' in string 'Ram Rahim' matches 'R' in 'SAMARTH
RAHI' at indices 4 and 8, first 'a' in string 'Ram Rahim' matches 'A' in
'SAMARTH RAHI' at indices 1, 3, and 9, first 'm' in string 'Ram Rahim'
matches 'M' in 'SAMARTH RAHI' at index 2, first space character ' ' in
string 'Ram Rahim' matches ' ' in 'SAMARTH RAHI' in at index 7, the
second 'R' in string 'Ram Rahim' again matches 'R' in 'SAMARTH RAHI' at
indices 4 and 8, and so on.
Language: It is the set of strings (words) defined over the alphabet ∑ that
conforms to some predefined pattern, or rule(s). In this section, we discuss a
class of languages called regular languages. A regular language is described
by a regular expression, described below. We shall use the terms regular
expression and pattern interchangeably.
empty language
If r and s are regular expressions, r|s is also a regular expression and
denotes the language L(r|s) = L(r) U L(s). The operator | is called the
union operator. Thus, the regular expression 0|1 denotes the language
L(0|1) = L(0) U L(1) = {0} U {1} = {0,1}.
The regular expression rs denotes the language L(rs) = L(r) L(s), i.e.,
the language formed by concatenating every string of the language L(r) by
every string of language L(s). The regular expression (0|1)1 denotes the
language L((0|1)1) = L((0|1))L(1) = {0,1} {1} = {01,11}. It is easy
to see that the regular expressions 1(0|1) and (0|1)1 denote different
languages. Thus, concatenation is not commutative. Concatenation has
higher precedence than the union operator |. Thus, the regular expression
0|11 would denote the language L(0|11) = L(0) U L(11) = {0} U {11}
= {0,11}.
module re deals with pattern matching search(): used for pattern matching
>>> match.group()
'ram@gmail'
When several substrings of a given string match the regular expression, the
function group returns the first substring matching the regular expression.
However, if we wish to retrieve list of all substrings matching the regular
expression, we may use the function finditer:
retrieving all substrings matching a regular expression
print(i.group())
ram@gmail.com
pranav.gupta@cs.iitd.ac.in
nik@yahoo.com
raman@gmail.com
Note that the null string matches the pattern r'(a(b|c))*'. Next, let us find
all words ending with 'ing' in a string. Again, we can use the function
finditer for this purpose.
print(i.group())
Walking
thinking
coming
>>> len(words)
13
Note that findall returns a list of matched patterns within the parenthesis
only if the entire regular expression matches.
Next, given a snippet of Python code, we wish to extract all the single line
comments contained in it. As a single line comment begins with # and
terminates with an end of line character, it can be represented using the
regular expression #.*.
extracting comments
"""
"""
a = 5 #number1
b = 5 #number2
c = a + b
'''
print(i.group())
#number1
#number2
print(i.group())
"""
"""
Aiysha,Renuka,Robin
Sneha,Ravi''')
SUMMARY
8. A regular expression defines a pattern. It is used for extracting sequences of characters in a string that
match the pattern. A regular expression involves symbols such as symbols from the alphabet of the
language, null string, parenthesis, * (star), and + (plus).
9. We need to import the re module for working with regular expressions.
10. The function search of the Python module re is used for matching a regular expression in a given
string. It searches for the first location of a match and returns the matchObject instance matching the
regular expression, and None otherwise.
EXERCISES
1. Write a function that takes a string as a parameter and returns a string with every successive repetitive
character replaced with a star(*). For example, 'balloon' is returned as 'bal*o*n'.
2. Write a function that takes two strings and returns True if they are anagrams and False otherwise. A
pair of strings is anagrams if the letters in one word can be arranged to form the second one.
3. Write a function that takes a sentence as an input parameter and displays the number of words in the
sentence.
4. Write a function that takes a sentence as an input parameter and replaces the first letter of every word
with the corresponding uppercase letter and rest of the letters in the word by corresponding letters in
lowercase without using built-in function.
5. Write a function that takes a string as an input and determines the count of the number of words
without using regular expression.
6. What will be the output on executing each of the statements, following the assignment statement:
address = 'B-6, Lodhi road, Delhi'
1. len(address)
2. address[17:-1]
3. address[-len(address): len(address)]
4. address[:-12] + address[-12:]
5. address.find('delhi')
6. address.swapcase()
7. address.split(',')
8. address.isalpha()
7. Examine the following string:
greeting = 'Good Morning. Have a Good Day!!'
What will be the output for the following function calls:
1. greeting.count('Good')
2. greeting.find('a')
3. greeting.rfind('a')
4. greeting.capitalize()
5. greeting.lower()
6. greeting.upper()
7. greeting.swapcase()
8. greeting.istitle()
9. greeting.replace('Good', 'Sweet')
10. greeting.strip()
11. greeting.split()
12. greeting.partition('.')
13. greeting.startswith('good')
14. greeting.endswith('!!')
8. Determine the patterns extracted by the following regular expressions.
1. string1 = 'Python Programming Language'
1. match1 = re.search('......m?', string1)
print(match1.group())
2. match2 = re.search('......m{1,2}', string1)
print(match2.group())
3. match3 = re.search('.*Language$', string1)
print(match3.group())
4. match4 = re.search('\w*\s\w*', string1)
print(match4.group())
5. match5 = re.search('.*', string1)
print(match5.group())
2. string2 = 'Car Number DL5645'
1. match1 = re.search('\w\w?\d{1,4}', string2)
print(match1.group())
2. match2 = re.search('.*5', string2)
print(match2.group())
3. match3 = re.search('.*5?', string2)
print(match3.group())
4. match4 = re.search('\d{3}', string2)
print(match4.group())
5. match5 = re.search('^C.*5$', string2)
print(match5.group())
3. string3 = 'cdcccdcddd343344aabb'
CHAPTER OUTLINE
7.1 Lists
7.2 Sets
7.3 Tuples
7.4 Dictionary
Elementary forms of data such as numeric and Boolean are called scalar data
types. Several applications require more complex forms of data, for
example, the name of a person, coordinates of a point, a set of objects, or a
list of personal records of individuals. In the previous chapter, we discussed
about strings (type str – an immutable structure). In this chapter, we will
discuss some other mutable and immutable objects, namely, lists, tuples,
sets, and dictionaries.
7.1 LISTS
Note that the elements of a list are enclosed in square brackets, separated by
commas. Elements of a list are arranged in a sequence beginning index 0,
just like characters in a string. In Fig. 7.1, we show the representation of the
list subjects as in PythonTutor.
indexing in a list
To understand the lists better, let us invoke the function id that returns
object identifier for the list object subjects:
>>> id(subjects)
57135752
>>> id(temporary)
57135752
Note that each of the names subjects and temporary is associated with the
same list object having object id 57135752. PythonTutor representation of
the lists subjects and temporary, at this point, is shown in Fig. 7.2.
>>> print(temporary)
>>> print(subjects)
57135752 57135752
As each of the two names temporary and subjects refers to the same list,
on modifying the component temporary[0] of the list temporary, the
change is reflected in subjects[0] as shown as shown in Fig. 7.3.
>>> subjectCodes[1]
['English', 85]
>>> print(subjectCodes[1][0],subjectCodes[1][1])
English 85
Often times, we need to take a list as an input from the user. For this
purpose, we use the function input for taking the input from the user, and
subsequently apply the function eval for transforming the raw string to a
list:
>>> details
print(name)
Ram
Shyam
Gita
Sita
As another example, given a list of marks in a subject, let us find the number
of students who have obtained marks >= 75.
>>> marksList = [78, 32, 89, 99, 56]
>>> count = 0
count += 1
>>> count
>>> list(vowels)
append: The function append insert the object passed to it at the end of the
list, for example:
>>> a.append(35)
>>> a
>>> a.extend([35,40])
>>> a
>>> a.extend('abc')
>>> a
count: The function count returns the count of the number of times the
object passed as an argument appears in the list, for example:
>>> a = [10, 20, 30, 10, 50, 20, 60, 20, 30, 55]
>>> a.count(20)
pop: The function pop returns the element from the list whose index is
passed as an argument, while removing it from the list, for example:
>>> a = [10, 20, 30, 10, 50, 20, 60, 20, 30, 55]
>>> a.pop(3)
10
>>> a.pop(3)
50
>>> a
remove: The function remove takes the value to be removed from the list as
an argument, and removes the first occurrence of that value from the list, for
example:
>>> a.remove(20)
>>> a
Next, suppose we have two lists, names – the list of the names of students
and rollNums – the list of corresponding roll numbers:
>>> names = ['Ram', 'Shyam', 'Sita', 'Gita', 'Sita']
>>> rollNums.pop(names.index('Shyam'))
>>> names.remove('Shyam')
deleting an object
>>> a
>>> del a
>>> a
Note that on execution of statement del a, name a no more refers to the list
object. Informally, we may say that the object a has been deleted or a has
been deleted.
>>> names
>>> names.reverse()
>>> names
['Anya', 'Sita', 'Sita', 'Ram']
>>> names.sort()
>>> names
If we wish to sort the list of names in descending order, we may use the
argument reverse = True while invoking the function sort:
use keyword argument reverse = True for sorting the elements of a list in descending order
>>> names
>>> names
>>> end = 10
cubes.append(i ** 3)
>>> cubes
Alternatively, a simple one line statement can be used for achieving the
same task.
shorthand notation for creating a list of cubes
>>> tall
>>> s2 = [3, 5]
>>> crossProduct
[['a', 3], ['a', 5], ['b', 3], ['b', 5], ['c', 3], ['c', 5]]
7.1.9 Lists as Arguments
Let us examine the script in Fig. 7.4. The function listUpdate updates the
list a (line 10) by replacing the object a[i] by value. The main function
invokes the function listUpdate with the arguments lst, 1, and 15
corresponding to the formal parameters a, i, and value. As arguments are
passed by reference, during execution of the function listUpdate, an access
to the formal parameter a means access to the list lst created in the main
function. Consequently, when we update the list a in the function
listUpdate, it results in the corresponding update of the list lst, as
visualized in PythonTutor (Fig. 7.5). Thus, the value at index 1 of the list
lst gets updated to the value 15.
assigning a list to another name does not create another copy of the list, instead it creates
another reference
As the names list1 and list2 refer to the same list object (Fig. 7.6), any
changes made in the list will relate to both the names list1 and list2, for
example (Fig. 7.7):
Fig. 7.6 list1 and list2 refer to the same list
Fig. 7.7 list1 and list2 refer to the same list
>>> list1[1] = 22
>>> list1
>>> list2
copy(): to create a copy of the list elements excluding the nested objects
Note that the copy function creates a new copy list3 of the list1.
Consequently, on modifying list1[1], list3[1] remains unaltered:
>>> list1[1] = 25
>>> list1
>>> list3
[10, 20, [30, 40]]
However, the copy function creates a shallow copy i.e. it does not create
copies of the nested objects. Thus, the two lists share the same nested
objects. Thus, list1[2] and list3[2] refer to the same nested list [30,
40]. Next, let us modify list1[2][0] in sub-list list1[2] of list list1 to
value 35.
>>> list1[2][0] = 35
>>> list1
>>> list3
As discussed above, since list1[2] and list3[2] refer to the same sub-list
at index 2 (Fig. 7.9), when we modify the list list1[2], the modification is
also visible in the list list3[2].
Fig. 7.9 list1 and list3 refer to the different lists
If we wish to create a copy of a list object so that the nested objects (at all
levels) get copied to new objects, we use the function deepcopy of the copy
module:
deepcopy(): to create a copy of a list including copies of the nested objects at all level
>>> import copy
Note that list1 and list4 are distinct objects (Fig. 7.10), having the nested
lists list1[2] and list4[2] as distinct objects. Thus, modifying the value
of list1[2][0] to 35 does not affect the object list4[2] [0] of list4
which remains unaltered as shown in Fig. 7.11.
>>> list1[2][0] = 35
>>> list1
>>> list4
lambda expression: used to define the expression to be be evaluated using the arguments
>>> cube(3)
27
Similarly, the function sum2Cubes may be used to compute the sum of cubes
of two numbers:
lambda expression to compute the sum of cubes of two numbers
>>> sum2Cubes(2, 3)
35
Next, suppose we wish to compute the cubes of all values in the list lst. The
following statements use the map function to map every value in the list lst
to its cube. Since the function map returns a map object, we have used the
function list to convert it to list.
[1, 2, 3, 4, 5]
Suppose we wish to compute the sum of cubes of all elements in a list. Note
that adding elements of the list is a repetitive procedure of adding two
elements at a time. The function reduce, available in functools module,
may be used for this purpose. It takes two arguments: a function, and a
iterable object, and applies the function on the iterable object to produce a
single value:
>>> sumCubes
225
Thus, in the above example, we are able to compute the sum of all the
elements of the list lstCubes. In a parallel environment, the sum may be
computed by adding two values at a time, and then summing over the sums
obtained in the first step, and so on. Thus, the sum of the elements of the list
[1, 2, 3, 4, 5, 6, 7, 8] may be computed as (((1+2) + (3+4)) + ((5+6) +
(7+8))).
Next, we compute the sum of cubes of only those elements in the list
lstCubes that are even. Thus, we need to filter the even elements from the
list lstCubes and before applying the function reduce. Python provides the
function filter that takes a function and a iterable object as the input
parameters and returns only those elements from the iterable object for
which function returns True. In the following statement, the filter function
returns an iterable object of even elements of the list lstCubes, which is
assigned to variable evenCubes. Since the function filter returns a filter
object, we have used the function list to convert it to list.
>>> evenCubes
[8, 64]
>>> sumEvenCubes
72
>>> sumEvenCubes
72
The functions map, reduce, and filter are often used to exploit the
parallelism of the system to distribute computation to several processors.
However, details of the parallel programming are beyond the scope of the
book.
7.2 SETS
set: a comma separated unordered sequence of values enclosed within curly braces
>>> {1,2,3}
{1, 2, 3}
>>> vowels
>>> vehicles
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
set type does not support indexing, slicing, + operator, and * operator
e a o u i
The functions min, max, sum, and len work for sets in the same manner as
defined for lists.
>>> min(digits)
>>> max(digits)
>>> sum(digits)
45
>>> len(vehicles)
True
>>> vehicles.add('Bus')
>>> vehicles
>>> vehicles
duplicate elimination
>>> heavyVehicles.remove('Crane')
>>> heavyVehicles
{'Bus', 'Truck'}
>>> heavyVehicles.remove('Car')
heavyVehicles.remove('Car')
KeyError: 'Car'
>>> heavyVehicles.pop()
'Bus'
To remove all the elements of a set, without deleting the set object, we use
the clear function:
>>> heavyVehicles.clear()
>>> heavyVehicles
set()
>>> eatables
Alternatively, we may use the union operator | for achieving the same result:
>>> eatables = fruits | vegetables
>>> eatables
Next, to determine those eatables which are both fruits and vegetables,
we take intersection of sets fruits and vegetables using either the function
intersection or the intersection operator & as follows:
intersection of two sets
>>> fruitsAndVegetables
>>> fruitsAndVegetables
Next, we find the fruits which are not vegetables by taking difference of
the two sets, either using the function difference or using the difference
operator:
set difference
>>> onlyFruits
{'Orange', 'Apple'}
>>> onlyFruits
{'Orange', 'Apple'}
>>> onlyVegetables
{'Cauliflower', 'Potato'}
>>> onlyVegetables
{'Cauliflower', 'Potato'}
Next, to determine eatables which are either only fruits or only
vegetables, we may take union of the sets onlyFruits and
onlyVegetables:
>>> fruitsXORVegs
symmetric difference
>>> fruitsXORVegs
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
{2}
{1, 3}
The function set.difference works by taking the union of all sets except
the first one and subtracting the union from the first set.
>>> digits
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> digits2
{0, 1, 2, 3, 7, 8, 9}
>>> isSubset
True
>>> isSuperset
True
The functions issubset and issuperset can also be used for the same
purpose.
A list of individuals who like either basketball or badminton, i.e. union of lists lst1 | lst2.
A list of people who like both basketball and badminton, i.e., the intersection of lists lst1 &
lst2.
A list of individuals who like basketball but not badminton, i.e. the difference lst1 - lst2.
Although Python does not support such operators on lists, we can convert lists into sets, apply
the necessary operations on sets, and finally convert the sets back into lists. It is important to
emphasize that a list should be converted to sets only when the order of elements in the list is
not important. Also, transforming a list into the set will remove repeating elements. In Fig.
7.12, we define the functions union, intersection, and difference for lists.
Fig. 7.12 Functions to find union, intersection, and difference of lists (lists.py)
7.3 TUPLES
>>> type(t1)
<class 'tuple'>
>>> (2)
>>> (2,)
(2,)
(2, 4, 6)
t1[1] = 3
>>> t1[2][1] = 5
>>> t1
>>> tuple(vowels)
>>> tuple([4,10,20])
>>> tuple(range(5))
(0, 1, 2, 3, 4)
The function zip is used to produces a zip object (iterable object), whose ith
element is a tuple containing ith element from each iterable object passed as
argument to the zip function. We have applied list function to convert the
zip object to a list of tuples. For example,
producing a list of tuples containing corresponding element from each iterable object
>>> fruitColor
>>> fruitColorQuantity
>>> age.count(18)
The function index is used to find the index of the first occurrence of a
particular element in a tuple, for example:
>>> age.index(18)
7.4 DICTIONARY
Unlike lists, tuples, and strings, a dictionary is an unordered sequence of
key-value pairs. Indices in a dictionary can be of any immutable type and are
called keys. Beginning with an empty dictionary, we create a dictionary of
month_number-month_name pairs as follows:
dictionary: a comma separated unordered sequence of key-value pairs enclosed in curly braces
>>> month = {}
>>> month
>>> type(month)
<class 'dict'>
>>> price['potato']
20
>>> price['carrot']
20
>>> price.keys()
>>> price.values()
>>> price.items()
Membership operation in, and functions min, max and sum apply only to the
keys in a dictionary. Thus, applying these operations on the dictionary
winter is equivalent to applying them on winter.keys() as shown below:
7.4.2 Deletion
We may remove a key-value pair from a dictionary using del operator, for
example:
>>> winter
To remove all the key–value pairs in a dictionary, we use the clear function.
Note that while assigning an empty dictionary {} creates a new object, the
function clear removes all key-value pairs from an existing dictionary:
clear(): to remove all key-value pairs
>>> months.clear()
({}, {})
Note that as the names winter and months refer to the same dictionary
object, on applying clear function to months, the dictionary winter also
becomes empty.
>>> passwords.get('Ram',-1)
'ak@607'
The first parameter is used to specify the key and the second parameter is
used to specify the value to be returned in case the key is not found in the
dictionary. In case, the second parameter is not specified, the system returns
None, for example:
get() returns second argument if the key is not present in the dictionary
>>> print(passwords.get('Raman'))
None
>>> passwords.update(morePasswords)
>>> passwords
(54782832, 54781104)
We conclude this section with a sample run of the program invDict (Fig.
7.13).
>>>
Inverted Dictionary:
SUMMARY
1. The list is a non-scalar type. It is an ordered sequence of values specified within square brackets.
Values in a list may be of any type such as str, int, float, or list.
2. Indexing is used for accessing elements of a list.
3. Unlike strings, lists are mutable, i.e. one may modify individual elements of a list.
4. A list of lists is called a two-dimensional list.
5. The following table lists operations that can be applied on the list:
>>> list1 = ['Red', 'Green']
>>> list2 = [10, 20, 30]
Operation Example
Multiplication operator * >>> list2 * 2
[10, 20, 30, 10, 20, 30]
Concatenation operator + >>> list1 = list1 + ['Blue']
>>> list1
['Red', 'Green', 'Blue']
Length operator len >>> len(list1)
3
Indexing >>> list2[-1]
30
Slicing >>> list2[0:2]
Syntax: start:end:inc [10, 20]
>>> list2[0:3:2]
[10, 30]
Function min >>> min(list2)
10
Function max >>> max(list1)
'Red'
Function sum >>> sum(list2)
(not defined on strings) 60
Membership operator in >>> 40 in list2
False
6. The following table lists some important built-in functions that can be applied to lists:
Function Explanation
L.append(e) Inserts the element e at the end of the list L .
L.extend(L2) Inserts the items in the sequence L2 at the end of the elements of the list L .
L.remove(e) Removes the first occurrence of the element e from the list L .
L.pop(i) Removes the element at index i from the list L .
L.count(e) Returns count of occurrences of object e in the list L .
L.index(e) Returns index of the first occurrence of the object e, if present in the list L .
L.insert(i,e) Inserts element e at index i in the list L .
L.sort() Sorts the elements of the list L .
L.reverse() Reverses the order of elements in the list L .
7. Comprehension provides an easy shorthand notation for creating lists, sets, and dictionaries. For
example, the expression [x**3 for x in range(1, end)] creates a list containing cube of each
element in the range (1, end).
8. Assignment of a list to another variable does not create a new list. Instead, the new variable references
the existing list that appears on the right-hand side of the = operator.
9. To create another instance of an object of types such as list, set, and dict, we need to import the
copy module and invoke the function copy.copy(). However, to create a copy of a list object, so that
embedded objects (at all levels) get copied, the function deepcopy of the copy module should be used.
10. The function map is used for transforming every value in a given iterable object by applying a
function to it.
11. The function filter that takes a function and a iterable object as the input parameters and returns only
those elements from the iterable object for which the function returns True.
12. The function reduce, available in functools module takes two arguments: a function, and an iterable
object, and applies the function on the iterable object to produce a single value.
13. A set is an unordered collection of objects without any duplicates. An object of type set may be
created by enclosing within curly brackets the elements of the set. A set object may also be created by
applying the set function to a list, string or tuple.
14. The following table lists some important built-in functions that can be applied to sets:
Function Description
S.add(e) Adds the element e to the set S.
S1.update(L1) Adds the items in object L1 to the set S1.
S.remove(e) Removes the element e from the set S.
S.pop() Removes an element from the set S.
S.clear() Removes all elements from the set S.
S.copy() Creates a copy of the set S.
S1.union(S2) Returns union of sets S1 and S2.
S1.intersection(S2) Returns a set containing elements common in the sets S1 and S2.
S1.difference(S2) Returns a set containing elements in the set S1 but not in the set S2.
S 1 . symmetric_difference(S2 Returns a set containing elements which are in one of the two sets S1 and S2, but not in both.
15. The operators <=, ==, and >= may be used to check whether a given set is a subset, equal, or superset
of another set.
16. A tuple is a non-scalar type. It is an ordered sequence of elements. Unlike lists, tuples are immutable,
i.e. elements of a tuple cannot be overwritten.
17. A tuple with a single element is also known as singleton tuple. Python allows values contained in a
tuple to be of varied types.
18. If a component of a tuple contains an object that itself is modifiable, that object can be modified.
19. The following table lists operations that can be applied on tuples:
>>> t1 = ('Monday', 'Tuesday')
>>> t2 = (10, 20, 30)
Operation Example
Multiplication operator * >>> t1 * 2
('Monday', 'Tuesday', 'Monday', 'Tuesday')
Concatenation operator + >>> t3 = t1 + ('Wednesday',)
>>> t3
('Monday', 'Tuesday', 'Wednesday')
Length operator len >>> len(t1)
2
Indexing >>> t2[-2]
20
Slicing >>> t1[1:2]
Syntax: start:end:inc 'Tuesday'
Function min >>> min(t2)
10
Function max >>> max(t2)
30
Function sum >>> sum(t2)
(not defined on strings) 60
Membership operator in >>> 'Friday' in t1
False
23. A dictionary is a non-scalar type. It is an unordered collection of key-value pairs. A dictionary may
be specified by including the key-value pairs within curly braces. A key and its associated value are
colon-separated. Each key uniquely identifies the value associated with it, and also, acts as an index.
As keys in a dictionary are immutable, lists cannot be used as keys.
24. The following table lists the operations that can be applied on the dictionary of digit–name pairs:
digits = {0:'Zero', 1:'One', 2:'Two', 3:'Three', 4:'Four',
5:'Five', 6:'Six', 7:'Seven', 8:'Eight', 9:'Nine'}
25. A key-value pair can be removed from a dictionary using del operator.
26. The following table lists some of the built-in functions that can be applied on the type dict:
Function Description
D.items() Return an object comprising of tuples of key-value pairs present in dictionary D. .
D.keys() Return an object comprising of all keys of dictionary D .
D.values() Return an object comprising of all values of dictionary D.
D.clear() Removes all key–value pairs from dictionary D .
D.get(key,default) For the specified key, the function returns the associated value. Returns the default value in case of absence of key in dictionary D .
D.copy() Creates a shallow copy of dictionary D .
D1.update(D2) Adds the key–value pairs of dictionary D2 in dictionary D1 .
EXERCISES
1. Write a function that takes a list of values as input parameter and returns another list without any
duplicates.
2. Write a function that takes a list of numbers as input from the user and produces the corresponding
cumulative list where each element in the list at index i is the sum of elements at index j <= i.
3. Write a program that takes a sentence as input from the user and computes the frequency of each
letter. Use a variable of dictionary type to maintain the count.
4. Identify the output produced when the following functions are invoked.
1. def func():
l1 = list()
l2 = list()
for i in range(0,5):
l1.append(i)
l2.append(i+3)
print(l1)
print(l2)
2. def func():
l1 = list()
l2 = list()
for i in range(0,5):
l1.append(i)
l2.append(i+3)
l1, l2 = l2, l1
print(l1)
print(l2)
5. Determine the output of the following code snippets:
1. c = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
result = 0
for i in range(0, 10):
if (c[i]%2 == 0):
result += c[i]
print(result)
2. c = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
result = 0
for i in range(0, 10):
if (c[i]%2 != 0):
result += c[i]
print(result)
3. subject = 'computer'
subject = list(subject)
ch = subject[0]
for i in range(0, len(subject)-1):
subject[i] = subject[i+1]
subject[len(subject)-1]=ch
print(''.join(subject))
4. quantity = [15, 30, 12, 34, 56, 99]
total = 0
for i in range(0, len(quantity)):
if (quantity[i] > 15):
total += quantity[i]
print(total)
5. x = [1, 2, 4, 6, 9, 10, 14, 15, 17]
for i in range(0, len(x)):
if (x[i]%2 == 0):
x[i] = 4*i
elif (x[i]%3 == 0):
x[i] = 9*i
else:
x[i] *= 2
print(x)
6. Write a function that takes n as an input and creates a list of n lists such that ith list contains first five
multiples of i.
7. Write a function that takes a number as an input parameter and returns the correspond text in words,
for example, on input 452, the function should return 'Four Five Two'. Use a dictionary for mapping
digits to their string representation.
8. Given the following inputs, indicate in each case (a) to (x), whether the statements will execute
successfully. If, so, give what will be the outcome of execution? Also give the output of print
statements (where applicable):
address = 'B-6, Lodhi road, Delhi'
list1 = [1, 2, 3]
list2 = ['a', 1, 'z', 26, 'd', 4]
tuple1 = ('a', 'e', 'i', 'o', 'u')
tuple2 = ([2,4,6,8], [3,6,9], [4,8], 5)
dict1 = {'apple': 'red', 'mango': 'yellow', 'orange': 'orange'}
dict2 = {'X': ['eng', 'hindi', 'maths', 'science'], 'XII':
['english', 'physics', 'chemistry', 'maths']}
1. list1[3] = 4
2. print(list1 * 2)
3. print(min(list2))
4. print(max(list1))
5. print(list(address))
6. list2.extend(['e', 5])
print(list2)
7. list2.append(['e', 5])
print(list2)
8. names = ['rohan', 'mohan', 'gita']
names.sort(key= len)
print(names)
9. list3 = [(x * 2) for x in range(1, 11)]
print(list3)
10. del list3[1:]
print(list3)
11. list4 = [ x+y for x in range(1,5) for y in range(1,5)]
print(list4)
12. tuple2[3] = 6
13. tuple2.append(5)
14. t1 = tuple2 +(5)
15. ','.join(tuple1)
16. list(zip(['apple', 'orange'], ('red', 'orange')))
17. dict2['XII']
18. dict2['XII'].append('computer science'), dict2
19. 'red' in dict1
20. list(dict1.items())
21. list(dict2.keys())
22. dict2.get('XI', 'None')
23. dict1.update({'kiwi':'green'}) print(dict1)
9. Consider the following three sets, namely vehicles, heavyVehicles, and lightVehicles:
>>>vehicles = {'Bicycle', 'Scooter', 'Car', 'Bike', 'Truck',
'Bus', 'Rickshaw'}
>>> heavyVehicles = {'Truck', 'Bus'}
>>> lightVehicles = {'Rickshaw', 'Scooter', 'Bike', 'Bicycle'}
Determine the output on executing the following statements:
1. lytVehicles = vehicles – heavyVehicles
print(lytVehicles)
2. hvyVehicles = vehicles – lightVehicles
print(hvyVehicles)
3. averageWeightVehicles = lytVehicles & hvyVehicles
print(averageWeightVehicles)
4. transport = lightVehicles | heavyVehicles
print(transport)
5. transport.add('Car')
print(transport)
6. for i in vehicles:
print(i)
7. len(vehicles)
8. min(vehicles)
9. set.union(vehicles, lightVehicles, heavyVehicles)
!
This section may be skipped on first reading without loss of continuity
CHAPTER 8
RECURTION
CHAPTER OUTLINE
8.1 Recursive Solutions for Problems on Numeric Data
8.2 Recursive Solutions for Problems on Strings
8.3 Recursive Solutions for Problems on Lists
8.4 Problem of Tower of Hanoi
8.1.1 Factorial
Suppose we wish to find the factorial of a non-negative number n. To do
this, we have to multiply numbers 1 to n:
n! = n * (n-1) * (n-2) * (n-3) * … * 2 * 1
Iterative Approach
Factorial of a number n can be computed by using a loop that iterates over
elements in the range(1, n + 1). An iterative function for computing the
factorial of a number is given in Fig. 8.1.
Fig. 8.1 Program to compute factorial of a number (factorial1.py)
Recursive Approach
Next, we rewrite the function factorial to compute factorial of a number
using recursive approach. Recall that n! = n * (n-1) * (n-2) * (n-3) *
… * 2 * 1. Alternatively, we may write the definition of n! as
or equivalently as
factorial(n) = 1 if n==0 or 1
= n * factorial(n-1) if n > 1
= 3 * (2 * factorial(1))
= 3 * (2 * 1))
= 3 * 2
= 6
Figure 8.3 shows stack frames created and exited during the execution of
the script in Fig. 8.2. Note that the exited frames (border lines as well as the
content) are shown in light grey color. To begin with, when Python
encounters the definitions of factorial and main functions in the program,
an entry is created for factorial and main functions in the global frame
(Fig. 8.3(a)). When the condition if __name__=='__main__' evaluates to
True, the function main is invoked and a new frame is created. On entering 3
as the input value for n (line 19), the variable binding for it is created (Fig.
8.3(b)). On invoking the function factorial (line 20, Fig. 8.2) with the
argument 3, a new frame is created containing a binding for the input
parameter n (Fig. 8.3(c)). Further, since the value of n is greater than l,
during execution of line 11, a recursive call is made to the function
factorial with 2 as the input argument. This creates another stack frame as
shown in Fig. 8.3(d). Note that the parameter n is now bound to value 2.
This recursive call further invokes function factorial with input argument
l (Fig. 8.3(e)). In this frame, the parameter n is bound to value 1. As the
value associated with variable n is now 1, the condition in line 8 becomes
True. So, this instance of function call creates the returns value 1 (Fig.
8.3(f)). On completion of the execution of this instance of the function
factorial, the frame for the function call that has just terminated is
removed from the stack, and the control is returned to the previous frame
(Fig. 8.3(g)) at the point of call (line 11), i.e. frame for function factorial,
where parameter n is bound to value 2. This instance of function call now
creates the returns value 2 as shown in Fig. 8.3(g). The function returns
value 2 on execution of line 11. This value 2 is returned in line 11 (variable n
is now bound to value 3, Fig. 8.3(h)). This instance of function call now
creates the returns value 6 as shown in Fig. 8.3(h). Execution of line 11
returns value 6 to the main function (Fig. 8.3(i)). In the main function, the
just returned value 6 gets bound to the variable result (Fig. 8.3(i)). When
the main function completes, it returns value None associated with it (Fig.
8.3(j)), and the control is returned to the global frame from the frame main
function (Fig. 8.3(k)).
Note that the stack is growing in the downward direction. The value of
any variable can be found in the current state of the program by looking at
the most recent stack frame (highlighted frame in the visualizer).
Fig. 8.3 Recursive calls to function factorial
'''
'''
assert n >= 0
if n == 0 or n == 1:
return 1
return n * factorial(n-1)
0, 1, 1, 2, 3, 5, 8, 13, 21, …
Suppose, we want to find out the nth term in the Fibonacci sequence. It may
be computed as follows:
Iterative Approach
In this section, we develop a function to compute the nth term of the
Fibonacci sequence. If the value of n is 1 or 2, the function just needs to
return 0 or 1, respectively. However, if n>2, the nth term is computed using a
loop with iterator i that iterates over elements in the range (3, n+1), and
for each element in the range(3,n+1), the new value is computed by taking
the sum of the previous two terms that we call secondLast and last.
Iterative function for finding the nth term of the Fibonacci sequence is given
in Fig. 8.4.
Fig. 8.4 Program to determine nth Fibonacci term (fibo1.py)
Recursive Approach
In this section, we compute nth Fibonacci term using recursive approach. As
mentioned earlier, nth term in the Fibonacci sequence may be computed as
follows:
These problems of sizes smaller than that of the original problem can be
further expressed in terms of problems of even smaller sizes, and so on until
we reach a problem of size 1 or 2 – a trivial problem to solve. For example,
4th term of Fibonacci sequence may be computed as follows:
fibo(4) = fibo(3) + fibo(2)
= (1 + fibo(1)) + fibo(2)
= (1 + 0) + fibo(2)
= 1 + fibo(2)
= 1 + 1
= 2
In light of the above discussion, we present a recursive function to compute
nth term in the Fibonacci sequence (Fig. 8.5).
Note that during each call to function Fibonacci, a new stack frame will
be allocated, and variable bindings will be created, allocating storage space
for new values. Also, the program remembers the point of call to the
function, so as to return control back to the point of call when the function
completes. Suppose we wish to determine 4th Fibonacci term. Determining
4th Fibonacci number involves computing 3rd and 2nd Fibonacci terms.
Figures 8.6(a) and (b) show the contents of the run-time stack as visualized
in Python Tutor for computation of the 3rd and 2nd Fibonacci terms.
Subsequently, 4th term is computed using these two values as shown in Fig.
8.6(c).
Fig. 8.5 Program to determine nth term in the Fibonacci sequence (fiboRecur.py)
= 1 + (1 + length('ro'))
= 1 + (1 + (1 + length('o')))
= 1 + (1 + (1 + (1 + length(''))))
= 1 + (1 + (1 + (1 + 0)))
= 1 + (1 + (1 + 1))
= 1 + (1 + 2)
= 1 + 3
= 4
Fig. 8.7 Program to determine length of the string (lenStr.py)
Figure 8.8 gives stack frames created and exited on the execution of the
script lenStr with 'Zero' as an input value for str1, as visualized in Python
Tutor.
8.2.2 Reversing a String
A string is said to be a reversed string of another string if the first character
in the reversed string is the last character of the given string, the second
character in the reversed string is the second last character of the given
string, and so on. To reverse a given string, the trivial base case is the case
when the string is an empty string, in which case, the reverse of the given
string is the empty string itself. However, if the string is non-empty, reversed
string can be obtained as the last character of the string concatenated with
the reverse of string obtained from the original string by dropping the last
character:
= 'o' + 'reZ'
= 'oreZ'
Fig. 8.8 Recursive calls to function length
Fig. 8.9 Program to reverse the string (reverse.py)
In Fig. 8.10, we present stack frames created and exited on the execution
of script reverse in Python Tutor on the input string 'Zero'.
8.2.3 Palindrome
A string is said to be a palindrome if the reverse of a string is equal to the
string itself. Next, we examine how to check whether a given string is a
palindrome. A string can be tested for being palindrome by comparing the
characters in the string from the two extreme ends. Thus, we compare the
character at index 0 with the character at index −1, the character at index 1
with the character at index −2, and so on, till we reach the middle of the
string. In case, a mismatch is found on the way, given string is not a
palindrome, and we return False; otherwise, it is a palindrome, and we
return True. This approach can be easily expressed using recursion. The
trivial base case is the case where the string is an empty string and as such a
palindrome. However, if the string is non-empty, a string can be declared as
palindrome if the following two conditions hold:
= True
To create the flattened list, say lst2, for a given list lst1, we initialize list
lst2 as an empty list and append the data values in the list lst1 to the list
lst2, one by one. The overall approach to flatten a list can be summarized
as follows:
for every element i in list lst1
if i is not a list
otherwise,
flatten list i
Let us examine the recursive program to flatten the list [1, [2, 3]]. As
Python Tutor does not support the eval function, we will fix the value of the
variable lst1 in the program to be [1, [2, 3]]. This style of programming
where values of the variables or parameters cannot be changed without
modifying the program is called hard-coding and is strongly discouraged for
all practical purposes. Anyway, while executing the program in Fig. 8.13 in
the Python Tutor, we replace line 20 in Fig. 8.13 by the assignment
statement:
lst1 = [1, [2, 3]]
8.3.2 Copy
In this section, we develop a function for creating a copy of a list. As
mentioned earlier, simply assigning a list object to another name does not
create a copy of the list; instead, both the names refer to the same list object.
So, to create a copy of a source list, say lst1, we begin with an empty
destination list, say lst2, and append every element of list lst1 to list lst2
recursively. The trivial base case is the case when the list lst1 is an empty
list, implying that the destination list lst2 will also be empty. However, if
the list lst1 is non-empty, a copy of a list can be created by appending the
first element of list lst1 to list lst2, and invoking the copy function for the
remaining list lst1 (i.e., excluding the first element). This way of copying a
sequence is also known as shallow copy. Thus, a problem of size n has been
expressed in terms of a problem of size (n – 1). Based on this discussion,
we present the complete program that accepts a list from the user, creates a
copy of the list and prints it (Fig. 8.15).
copying a list
Fig. 8.15 Program to create copy of a list (copy.py)
Let us examine the recursive function to create a copy of the list [1, [2,
3]]. As discussed before, a new stack frame will be allocated, and the
variable bindings will be created, allocating storage space for new values.
Also, the program remembers the point of call of the function, so as to return
control back to the point of call when the function completes. Figure 8.16
shows the stack frames created and exited on execution of the script as
visualized in Python Tutor with [1, [2, 3]] being the value of the list
lst1.
8.3.4 Permutation
An arrangement of the elements of a list is called a permutation. For
example, the list [1, 2, 3] will have the following six permutations:
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
Fig. 8.17 Program to create deep copy of a list (deepCopy.py)
In this section, we will develop a function to generate all permutations of a
list. In general, a list with n elements will have n! permutations.
insert 3 at pos
print perm
remove 3 from perm at pos (To get back the original permutation
[1,2])
In this section, we will discuss how to use recursion to solve the problem of
Tower of Hanoi. First, let us describe the problem. There are three poles
numbered 1, 2, and 3. In the first pole, n disks have been inserted. These
disks are placed one above the other in a decreasing order of the diameter.
The problem is to transfer all the disks from pole 1 to pole 3 using pole 2 as
a spare pole, moving one disk at a time, and always keeping in mind that a
disk with larger diameter is not to be placed over a disk with smaller
diameter. See Fig. 8.21 for the case n = 3.
Fig. 8.20 Generating the first permutation using function permute
Fig. 8.21 Tower of Hanoi for n = 3
Before solving the problem in general, let us consider some simple cases.
n = 1
The solution is trivial. Just move the disk from pole 1 to pole 3.
n = 2
Move the smaller disk at pole 1 to the spare pole 2. Now, the bigger disk at
pole 1 can be moved to pole 3. Finally, move the smaller disk from the spare
pole 2 to pole 3. This completes the task.
n = 3
Two disks in pole 2 are yet to be transferred to pole 3 using pole 1, which
is currently empty as the spare pole. Since each disk in pole 2 is of a smaller
diameter than the disk in pole 3, any of them can be shifted to pole 3. The
following steps will achieve the transfer of two disks from pole 2 to pole 3.
Move a disk from pole 2 to pole 1
SUMMARY
1. Python allows a function to call itself, possibly with new parameter values. This technique is called
recursion.
2. Recursion is a technique, which aims to solve a problem by providing a solution in terms of the
smaller version(s) of the same problem. A recursive function definition comprises two parts. The first
part is the base part which is the simplest version of the problem, often termed stopping or termination
criterion. The second part is the inductive part which is the recursive part of the problem that reduces
the complexity of the problem by defining a simpler version of the original problem itself.
3. Factorial of a number can be recursively expressed as follows:
EXERCISES
1. Write a recursive function that multiplies two positive numbers a and b, and returns the result.
Multiplication is to be achieved as a + a + a (b times).
2. Write a recursive function that takes number n as an input parameter and prints n-digit strictly
increasing numbers.
3. Write a recursive function that generates all binary strings of n-bit length.
4. Write a recursive function that takes two strings as input parameters and prints all interleaving strings
of the given two strings preserving their order of occurrence. For example, interleaving of strings
‘AB’ and ‘CD’ will generate the strings: ‘ABCD’, ‘ACBD’, ‘ACDB’, ‘CDAB’, ‘CADB’ and
‘CABD’.
5. Write a recursive function that inserts the element x at every kth position in the given list, and returns
the modified list. For example, if we wish to insert element 50 at every 3rd position (counting 0, 1, 2,
3) in the list [1, 2, 3, 4, 5, 6, 7], the output list will be [1, 2, 3, 50, 4, 5, 6, 50, 7].
6. Write a recursive function that deletes every kth element, and returns the modified list. For example, if
we wish to delete every 3rd element from the list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], the output list will be
[1, 2, 4, 5, 7, 8, 10, 11].
7. Write a recursive function that recursively removes adjacent duplicates from a given list, and returns
the modified list. For example, removing adjacent duplicates recursively from the list [1, 2, 4, 4, 5, 7,
7, 7, 8, 8, 9, 7] will yield list [1, 2, 5, 9, 7].
8. Write a recursive function that takes two numbers as input parameters and computes their greatest
common divisor.
9. In Fig. 8.17, after line 25, include the following statement, execute the code again and justify the
output:
lst2 = deepCopy(lst1)
CHAPTER 9
FILES AND EXCEPTIONS
CHAPER OUTLINE
9.1 File Handling
9.2 Writing Structures to a File
9.3 Errors and Exceptions
9.4 Handling Exceptions using try…except
9.5 File Processing Example
Programs that we have developed so far take data from the user in an
interactive manner. Such data remain in memory only during the lifetime of
the program. Often we want to store data permanently, in the form of files
that usually reside on disks, so that it is available as and when required. For
example, for login application, we would like to validate the user name and
password entered by a user against the names and passwords of valid users
stored permanently in a file. By default, Python provides a standard input
file and a standard output file to deal with the transitory data. The standard
input file is read from the keyboard, and the standard output file is displayed
on the screen. Apart from these standard input/output files, we can also
create files on disks that store data permanently for subsequent use. In this
chapter, we will study file handling in detail. Moreover, programs
necessarily have to deal with exception situations like unavailability of a file
we want to read from or an error like division by zero. Therefore, in this
chapter, we will also discuss how to deal with such situations smoothly.
opening a non-existent file in w or a mode creates a new file with the given name
f = open(file_name, access_mode)
By default, the system creates a file in the default working directory. Instead
of this relative path name, absolute (full) path name such as
F:\PythonCode\Ch09 could also be specified. The functions read and write
are used for reading from and writing into the file respectively. To use
read/write function, we use the following notation: name of the file object,
followed by the dot operator (.), followed by the name of the function. For
example, in the following statement, we use write() function to write some
text in the file PYTHON.
>>> f.write('''Python:
130
Note that apart from writing the given data into a file, the function write
also returns the number of characters written into the file (130 in the above
example). Since the file is opened in write mode, Python disallows read
operation on it by flagging an error as shown below:
>>> f.read()
f.read()
>>> f.close()
The function close also saves a file, which was opened for writing. Once a
file is closed, it cannot be read or written any further unless it is opened
again and an attempt to access the file results in an I/O (input/output) error:
To read the contents of the file f, we open the file again, but this time in read
mode. Once the file has been opened in read mode, its contents can be read
using read function:
>>> f = open('PYTHON', 'r')
>>> f.read()
>>> f.close()
>>> print(f.read())
Python:
>>> f.close()
As seen above, the read() function retrieves the contents of the entire file.
More often, we need to read data in smaller chunks. As an alternative, we
can read a fixed number of bytes from the file by specifying the number of
bytes as the argument to read function. For example, reading only first 4
bytes will return Pyth as output.
>>> f = open('PYTHON','r')
>>> f.tell()
0
>>> f.read(4)
'Pyth'
>>> f.tell()
We have used the function tell to know the current position while reading
the file object f. Initially, the current position of file object f is set at 0, i.e.,
position of the first byte. A subsequent read operation will read the file f
from the current position of the file object.
>>> f.read(4)
'on:\n'
>>> f.tell()
Note that so far we have read only eight bytes from the input file. However,
the function f.tell() shows 9 as the current position in the file. This is
because the end of line character '\n' is stored by WINDOWS operating
system as a pair of characters, namely, carriage return character (CR) to
transfer control to beginning of line and line feed character (LF) to transfer
control to the next line. However, if we are using a linux/UNIX®1 based
systems, the function tell would return the position 8 as shown below:
>>> f.tell()
>>> f.read(4)
'on:\n'
>>> f.tell()
Another way of reading from a file is reading one line at a time, Python
function readline() is used for this purpose:
>>> f.readline()
Note that the readline function reads a stream of bytes beginning the
current position until a newline character is encountered. On reading a
sequence of four bytes from the file twice, the current file position was set at
the beginning of the second line. That is why, on invoking the function
readline, the system returns the second line of text. Once we are done with
reading this line, the next read operation will take place beginning the next
line.
>>> f.readline()
>>> f.readline()
''
Note that, when all the contents of a file have been read, a further read
operation on it will return a null string. One way to read from a particular
position in a file is to use the function seek(). For example, for reading
from the beginning of the file, we may invoke the seek function with the
argument 0 as shown below:
reading the file that has been read entirely returns a null string
>>> f.seek(0)
0
The function seek returns the new absolute position. The function
readlines()returns all the remaining lines of the file in the form of a list:
>>> f.readlines()
As each string in the list returned by the function readlines comprises one
line, it terminates with the newline character. Just like the readlines
function discussed above, the function writelines takes a list of lines to be
written in the file as an argument.
>>> f.writelines(description)
>>> f.close()
>>> f.read()
>>> f.close()
Suppose if we wish to copy the contents of a text file, say, PYTHON in another
file PythonCopy. For this purpose, we open the source file PYTHON in read
mode and the output file PythonCopy (yet to be created) in write mode, read
the data from the file PYTHON, and write it into the file PythonCopy as
follows:
>>> f1 = open('PYTHON', 'r')
>>> f2.write(data)
55
>>> f1.close()
>>> f2.close()
Note that if an application requires the file to be opened in both read and
write mode, 'r+' mode can be used while opening it. If we wish to put the
new content at the end of previously existing contents in a file, we need to
open the file in append ('a') mode as shown below:
use r+ mode for opening a file both for reading and writing
31
44
>>> f.close()
>>> f.read()
To ensure that the contents written to a file have been saved on the disk, it
must be closed. While we are still working on a file, its contents may be
saved anytime using the flush function.
>>> print('Hello)
Indentation error
In contrast to a syntax error, an exception occurs because of some mistake
in the program that the system cannot detect before executing the code as
there is nothing wrong in terms of the syntax, but leads to a situation during
the program execution that the system cannot handle. For example, opening
a non-existent file for reading, attempting to access value of a variable
without assigning a value to it, and dividing a number by zero. These errors
disrupt the flow of the program at a run-time by terminating the execution at
the point of occurrence of the error. We have noticed that whenever an
exception occurs, a Traceback object is displayed which includes error
name, its description, and the point of occurrence of the error such as line
number. Now we describe some commonly encountered exceptions:
1. NameError
This exception occurs whenever a name that appears in a statement is not
found globally. For example, in the following statement, we intend to take
marks as an input from the user. For doing so, we intended to use function
input but instead typed Input. Python being case-sensitive fails to
recognize the function input and the system responds with the error
message NameError: name 'Input' is not defined. This message
begins with the name of the exception. Note that the following Traceback
object describes that error occurred in line 1 in Python shell, in the most
recent call:
Note that the above error could not have been detected as a syntax error as
it is perfectly fine to define a function Input as shown below:
>>> def Input():
return input('Enter your marks: ')
>>> marks = Input()
Enter your marks: 78
>>> marks
'78'
2. TypeError
This exception occurs when an operation or function is applied to an object
of inappropriate type. For example, the expression 'sum of 2 and 3 is '
+ 5 involves adding a number to a string which is not a valid operation
resulting in an exception.
3. ValueError
This exception occurs whenever an inappropriate argument value, even
though of correct type, is used in a function call, for example:
>>> int('Hello')
Traceback (most recent call last):
File "<pyshell#5>", line 1, in <module>
int('Hello')
ValueError: invalid literal for int() with base 10: 'Hello'
Note that in the above example, the function int has been invoked with a
valid type of argument, i.e. str, but its value, i.e., 'Hello', cannot be
converted to an integer. Hence the ValueError.
4. ZeroDivisionError
This exception occurs when we try to perform numeric division in which
the denominator happens to be zero, for example:
>>> 78/(2+3-5)
Traceback (most recent call last):
File "<pyshell#13>", line 1, in <module>
78/(2+3-5)
ZeroDivisionError: division by zero
5. OSError
This exception occurs whenever there is a system related error such as disk
full or an error related to input/output, for example, opening a non-existent
file for reading or reading a file opened in write mode:
>>> f = open('passwordFile.txt')
Traceback (most recent call last):
File "<pyshell#9>", line 1, in <module>
f = open('passwordFile.txt')
FileNotFoundError: [Errno 2] No such file or directory:
'passwordFile.txt'
6. IndexError
This exception occurs whenever we try to access an index that is out of a
valid range. For example, let us name the list of colors ['red', 'green',
'blue'], as colors. Now the valid range of indexes for colors is [-3,
-2, -1, 0, 1, 2] and the valid index range of indexes for the string
colors[2] is [-4, -3, -2, -1, 0, 1, 2, 3]. Accessing an index outside
a valid range will cause IndexError exception to occur:
Whereas a try block comprises statements that have the potential to raise
an exception, except block describes the action to be taken when an
exception is raised. In the except clause, we may specify a list of exceptions
and the common action to be taken on occurrence of any of these exceptions.
Alternatively, a specific action may be provided for each of the exceptions
separately. We can also specify a finally block in the try…except clause,
which is executed irrespective of whether an exception is raised.
Note that as IOError exception raised in line 8 had been handled (lines 9–
10), the program did not terminate abruptly and continued smoothly to
execute line 11 after the exception was handled.
We can access the description of the Traceback notice directly. For this
purpose, the name of the exception such as IOError is followed by the
keyword as, which is followed by a user-defined name such as err in the
except clause (Fig. 9.3). So, when IOError exception is raised during
execution of the open function (line 9), the exception information is assigned
to the variable err and the message [Errno 2] No such file or
directory: 'Temporary_File' is displayed (line 11). It is also possible to
track the exception raised by Python using the expression sys.exc_info(),
which yield the details of the exception as a tuple comprising the type of
exception, and description of the exception, a reference to the exception
object, for example, on executing the script try_except2 (Fig. 9.3), the
system responds as follows:
In the script pricePerUnit1 (Fig. 9.4), we wish to compute the price per
unit weight of an item. For this purpose, we define a function main that takes
price and weight as inputs and computes the price per unit. Note that
ValueError and TypeError exceptions may be raised while converting an
argument to a float value (lines 12 and 14) and ZeroDivisionError
exception may be raised while dividing price by weight (line 16). For
handling these exceptions, we include all of them in the except clause (line
17). An optional else clause (line 20) may also be specified in the try…
except clause, which will be executed only if no exception is raised.
Fig. 9.4 Program to compute price per unit weight of an item (pricePerUnit1.py)
On executing the script pricePerUnit1 (Fig. 9.4), the system prompts the
user to enter values of price and weight:
> >>
When we enter the inputs -20 and 0, each of the assert statement (line 15)
and division operation (line 16) can raise exceptions. However, as the
assert statement is encountered before the division operation, in the try…
except clause, AssertionError exception is raised. As none of the
exceptions specified in lines 17, 19, and 21 matches the AssertionError
exception, the empty except block (lines 23–24) got executed. Thus, line 16
got skipped.
If there is no handler for the exception raised in try block, search for handler takes place in
outer try...except block
Fig. 9.6 Program to compute price per unit weight of an item (pricePerUnit3.py)
>>>
Bye
main()
Fig. 9.7 To illustrate the use of raise and finally clauses (raiseFinally1.py)
> >>
Bye
4001,Nitin Negi,75
4002,Kishalaya Sen,98
4003,Kunal Dua,80
4004,Prashant Sharma,60
4005,Saurav Sharma,88
As we need to ensure throughout the program that the file operations are
being performed smoothly without any errors, we must perform checks on
error conditions. The revised pseudocode is shown in Fig. 9.10.
check for possible exceptions
The complete script is given in Fig. 9.11. When we execute the program in
Fig. 9.11 and enter 3 as value of addPercent, the system outputs the
contents of the file moderatedMarks as follows:
4001,Nitin Negi,78.0
4002,Kishalaya Sen,100
4003,Kunal Dua,83.0
4004,Prashant Sharma,63.0
4005,Saurav Sharma,91.0
Fig. 9.11 Program to compute moderated marks (moderatedMarks.py)
1001,Vinay Kumar,30
1002,Rohit Sen,35
1003,Vinita Sharma,28
1004,Bijoy Dutta,35
1001,245
1002,0
1003,0
1004,240
To compute the monthly wages of all employees, we need to read the files
employeeMaster and empMonthly and produce a third file monthlyWages
containing monthly wages of the employees. We describe this task in the
form of a pseudocode (Fig. 9.12).
Fig. 9.12 Pseudocode to compute contents for file monthlyWages
The complete script is given in Fig. 9.14. Instead of invoking the exit
function in line 13, we could have executed a return statement to return the
control to main function and ask the user to enter the name of the file again.
On the execution of the program in Fig. 9.14, the system creates an output
file monthlyWages with the following content:
1001,7350
1002,0
1003,0
1004,8400
Fig. 9.13 Pseudocode to compute contents for file monthlyWages
Fig. 9.14 Program to generate salary (salaryGen.py)
In the above program, we assume that the information about each employee
in empMaster is available in empMonthly. Suppose, the file empMonthly does
not contain an entry for employees for whom hrlyWorked is equal to 0.
Sample data in this file is shown below:
1001,245
1004,240
The complete script is given in Fig. 9.16. On the execution of the above
program, the system outputs the contents of the file monthlyWages as
follows:
1001,7350
1002,0
1003,0
1004,8400
Fig. 9.16 Program to generate salary (salaryGen.py)
SUMMARY
EXERCISES
1. Write a function that takes two file names, file1 and file2 as input. The function should read the
contents of the file file1 line by line and should write them to another file file2 after adding a
newline at the end of each line.
2. Write a function that reads a file file1 and displays the number of words and the number of vowels in
the file.
3. Write a function that takes data to be stored in the file file1 as interactive input from the user until he
responds with nothing as input. Each line (or paragraph) taken as input from the user should be
capitalized, and stored in the file file1.
4. Write a function that reads the file file1 and copies only alternative lines to another file file2.
Alternative lines copied should be the odd numbered lines. Handle all exceptions that can be raised.
5. Write a function that takes two files of equal size as input from the user. The first file contains weights
of items and the second file contains corresponding prices. Create another file that should contain
price per unit weight for each item.
6. Write a function that reads the contents of the file Poem.txt and counts the number of alphabets, blank
spaces, lowercase letters and uppercase letters, the number of words starting with a vowel, and the
number of occurrences of word 'beautiful' in the file.
7. What will be the output produced on executing function inverse1 when the following input is entered
as the value of variable num:
(a)5 (b)0 (c)2.0 (d)x (e)None
def inverse1():
try:
num = input('Enter the number: ')
num = float(num)
inverse = 1.0 / num
except ValueError:
print('ValueError')
except TypeError:
print('TypeError')
except ZeroDivisionError:
print('ZeroDivisionError')
except:
print('Any other Error')
else:
print(inverse)
finally:
print('Function inverse completed')
8. Examine the following function percentage:
def percentage(marks, total):
try:
percent = (marks / total) * 100
except ValueError:
print('ValueError')
except TypeError:
print('TypeError')
except ZeroDivisionError:
print('ZeroDivisionError')
except:
print('Any other Error')
else:
print(percent)
finally:
print('Function percentage completed')
Determine the output for the following function calls:
1. percentage(150.0, 200.0)
2. percentage(150.0, 0.0)
3. percentage('150.0', '200.0')
9. Identify two exceptions that may be raised while executing the following statement:
result = a + b
10. What will be the output for the following code snippets if the file being opened does not exist:
1. try:
f = open('file1.txt', 'r')
except IOError:
print('Problem with Input Output...\n')
else:
print('No Problem with Input Output...\n')
2. try:
f = open('file1.txt', 'w')
except IOError:
print('Problem with Input Output...\n')
else:
print('No Problem with Input Output...\n')
1
UNIX® is a registered trademark of The Open Group
CHAPTER 10
CLASSES I
CHAPER OUTLINE
10.1 Classes and Objects
10.2 Person: An Example of Class
10.3 Class as Abstract Data Type
10.4 Date Class
class: logical grouping of related data and methods that operate on them
Variables used so far took values of types (also called classes) string
(str), integer (int), floating point (float), Boolean (bool), list, tuple, or
dictionary (dict). As these classes are already available in Python, they are
called built-in classes. Python also allows us to define new classes (i.e.,
types), called user-defined classes. Data and methods associated with a class
are collectively known as class attributes.
class attributes: data and methods associated with a class
We begin our study of classes with the built-in class str. The strings 'Raman',
'CBSE', and 'Jan 11 2014' are instances of class str. The following
assignment statement assigns the object 'Raman' of class str to the variable
name:
A class would usually have several functions (called methods in the context
of classes), which can act on objects of the class. We have already seen
several methods that can be applied to objects of the class str. For example,
the method lower returns an str object that has all uppercase letters in the
given string object replaced by lowercase letters:
>>> name.lower()
'raman'
Here, the method lower defined in class str has been invoked for the object
name. To specify an attribute of a class (or class instance), we write the
name of the class (or class instance) followed by a dot, followed by the
name of that attribute. In the above example, name – an instance of class str
is followed by a dot (.), followed by lower() – the attribute of interest. The
method lower may also be invoked as follows:
>>> str.lower(name)
'raman'
In this format, we specify the name of the class (str), followed by the dot
operator (.), followed by the name of the method (lower), followed by an
object (name). The object name being an argument is enclosed in
parentheses.
In this section, we shall discuss the concept of class with the help of an
example. To keep the matter simple, we shall describe a person using three
attributes, viz., name, DOB (date of birth), and address, each of which takes
values of type str. In Fig. 10.1, we define the class Person that describes a
person with the above-mentioned attributes name, DOB, and address.
class ClassName:
classBody
Execution of statements in lines 14, 15, and 16 sets data members name,
DOB, and address of the object p1 equal to parameter values 'Amir', '24-
10-1990', and '38/4, IIT Delhi 110016' respectively with which the
method __init__ was invoked. Execution of the assignment statement in line
17 increments the class variable count, which now holds value 1. Note that
all instances of a class Person share this attributes. A reference to count may
be made using either the class name or a specific object of the class Person.
a class attribute can be referenced using the name of the class or an object of the class
Note that while creating an object (such as p1) of class Person, although
we mention only three arguments to be used by method __init__, in effect
four arguments are used for initializing an instance of Person. By default,
Python passes object itself (such as p1) as the first argument to the method
__init__. In the formal parameter list for the method __init__, it appears by
the name self. Although being a formal parameter, any other name (like
me) would do equally well, there is a strong convention to use self as the
first parameter. Indeed, when we execute the statement:
by default, the object itself is passed as the first parameter to the method __init__
object attributes: data members and methods associated with an instance of a class
Fig. 10.2 Python Tutor visualization of objects p1 and p2, and class attributes
To execute the script person and generate some objects, let us include the
following two statements in the script:
p1 = Person('Amir','24-10-1990','38/4, IIT Delhi 110016')
It is important to know that whereas each instance of a class has its copy
of data members, the class variables and methods are shared. In summary,
operations supported by classes may be categorized as follows:
For the system-defined classes like int, str, list, and tuple, Python
provides built-in method attribute __str__ that transforms internal
representation of the object to a printable string as illustrated below:
True
True
>>> int.__str__(7)
'7'
>>> print(int.__str__(7))
The method hasattr(obj, attr ) returns True if instance obj contains the
attribute attr, and False otherwise. Note that the method __str__ when
applied to int object 7 indeed returns equivalent str value '7'. Thus, the
statement
print(7)
print(str(7))
__str__ method is automatically invoked when print function is invoked to print an object
p1.__str__()
and
print(p1.__str__())
DOB:24-10-1990
Execution of the following statement also yields the same output as shown
above:
>>> print(p1)
>>> p1.setDOB('24-10-1991')
>>> print(p1)
Name:Amir
DOB:24-10-1991
10.2.1 Destructor
When an object is no more required, we use the del statement. However, an
object may be referenced by multiple names. Execution of the del statement
reduces the reference count by one. When the reference count becomes zero,
the __del__ method is invoked. Next, we define the __del__ method for the
class Person. As the number of Person objects reduces by one on execution
of the destructor, we decrement Person.count by one (line 9, Fig. 10.3).
>>> p3 = p2
>>> print(Person.count)
>>> del p1
Deleted !!
>>> print(p1)
print(p1)
>>> print(Person.count)
>>> del p2
>>> print(Person.count)
>>> del p3
Deleted !!
>>> print(Person.count)
the method __del__ is invoked before destroying the instance object, when all the references to
the given instance have been removed
Note that we created two Person objects p1 and p2. Name p3 refers to the
same object as p2 and is just another reference for the object p2 created
earlier, and the reference count of the object p2 as well as that of p3 is 2.
Execution of the instruction del p1 invokes __del__ method defined in the
class Person, the object p1 gets deleted, Person.count gets decremented by
one, and the message 'Deleted !!' is printed. However, the instruction del
p2 does not delete the object p2 as the name p3 still refers to it. It only
dissociates the name p2 from the object.
The execution of the first statement in the main function (line 16) prints
the directory of class Person as shown in Fig. 10.5 (lines 1–8). Note that
directory contains the docstring __doc__, the class variable count, and the
list of methods of the class, but does not contain the data attributes of the
class as they belong to the class objects and not directly to the class. Also,
note that the directory includes some attributes that we have not discussed.
These are system defined attributes. Once you are of comfortable with the
basic concepts of classes, you can experiment with them. As expected, use
of print function in line 17 prints the docstring:
directory of a class
The class Person describes a person
associated with the class Person (lines 9–10, Fig. 10.5). In line 18 (Fig.
10.4), we print the name of the module that contains the class Person (lines
11–12, Fig. 10.5). In line 22 (Fig. 10.4), we create an object p1 of the class
Person.
Fig. 10.4 Using class Person (personEx.py)
Fig. 10.5 Output of the script personEx (Fig. 10.4)
In line 23 (Fig. 10.4), we print the value of class variable count (lines 13–
14, Fig. 10.5). Here, we would like to mention that to access data attributes
of a class directly outside of the class definition is in violation of the
abstraction principle and it is best avoided. In line 24 (Fig. 10.4), we invoke
the method getCount for the object p1 that fetches the class variable count
(lines 15–16, Fig. 10.5). This is consistent with the abstraction principle as
we are making use of the function getCount to retrieve the value of count.
In lines 25–26 (Fig. 10.4), we print the values of p1.__doc__ and
p1.__module__ (lines 17–20, Fig. 10.5). Note that p1.getCount(),
p1.__doc__, and p1.__module__ yield the same values as Person.count,
Person.__doc__, and Person.__module__, respectively, because p1 is an
object of class Person. In line 27 (Fig. 10.4), we print the object p1 (see Fig.
10.5, lines 21–24). The print function invokes the method
Person.__str__() for the object p1. More explicitly, we may invoke the
__str__ method defined in class Person as follows:
while Person.count can also be accessed using p1.count, but assigning a value to p1.count
would not change the value of corresponding class variable, instead it will create a new data
attribute for the object p1
>>> print(p1.__str__())
Name:Amir
DOB:24-10-1991
The above statement invokes the method __str__ of the object p1. Here, the
object p1 that corresponds to the formal parameter self is passed to the
method __str__ implicitly. In the following call to the print function, the
call to method __str__ of class Person is even more explicit and matches
the syntactic description of __str__(self). However, in practice, this form
is rarely used.
>>> print(Person.__str__(p1))
Name:Amir
DOB:24-10-1991
In line 28 (Fig. 10.4), we print the directory of the object p1 (lines 25–33,
Fig. 10.5). Note that in addition to attributes of the class Person that
automatically get associated with the object p1, the directory for object p1
also contains its data attributes: name, DOB, and address.
__dict__ attribute
We often need to deal with date and time in our programs. Although Python
provides a built-in class for this purpose, in this section, we shall discuss
how to develop our class to deal with dates. We know that the date
comprises the day, month, and year. In the script date (Fig. 10.6), we define
the class MyDate. In this example we have struggled to ensure that the class
MyDate creates an instance of a valid date only. However, you may skip the
details of validating the date on first reading.
Fig. 10.6 Definition and use of class MyDate(date.py)
The execution of line 77 (Fig. 10.6) creates an object named today and
initializes it to date 03-09-2014 by invoking the constructor of the class
MyDate as MyDate(3,9,2014). Execution of the lines 20, 25, and 30 in the
constructor achieves the desired initialization of the data members day,
month, and year of the object today of the class MyDate. Execution of the
statement in line 79 creates the object defaultDate. Since no arguments are
provided while creating the object defaultDate, the method __init__ uses
the default parameter values 01, 01, and 2000 for initializing the instance
variables day, month, and year, respectively. So, on executing line 80,
Python will print:
default date
01-01-2000
Note that day, month, and year provided while invoking the constructor of
the class MyDate may be invalid. For example, the following statement
attempts to create an object of the class MyDate by initializing the instance
variables day, month, and year as 30, 02, and 2012, respectively:
>>> feb30 = MyDate(30, 2, 2012)
validating date
SUMMARY
1. A class is a template that provides a logical grouping of data and methods that operate on them.
Instances of a class are called objects.
2. Data members and methods associated with an instance of a class are called attributes of the object.
The set of attributes that are associated with an object forms its namespace. To use an attribute of a
class (or class instance), we specify the name of the class (or class instance) followed by a dot
operator, followed by the name of that attribute.
3. A class definition begins with the keyword class followed by the name of the class, and a colon. By
convention, the first letter of the class name is capitalized.
4. Functions defined in a class are called methods. By default, Python passes the object itself as the first
parameter to the method.
5. Special methods begin and end with a double underscore.
6. The __init__ method is used to initialize an instance of a class.
7. When we want to delete an object using del statement, Python special method __del__, if defined, is
invoked for the object.
8. Operations supported by classes may be categorized as follows:
Instantiation: It refers to the creation of an object, i.e. an instance of the class.
Attribute references: Methods and data members of an object of a class are accessed using the
notation: name of the object, followed by dot operator, followed by the member name.
9. Python provides a built-in method attribute __str__ for transforming the internal representation of the
object to a printable string. When the print function is executed to print an object, Python invokes the
method __str__ of the corresponding class to obtain a string representation of the object.
10. Python built-in data member __doc__ stores docstring of the class.
11. Python built-in data member __dict__ is a dictionary comprising key–value pairs. A key may either
be a data member or a method, and the corresponding value would be the value of the data members
or the reference associated with the class method.
12. Class attributes are shared among all instances of the class.
EXERCISES
1. Define a class Rectangle. The class should contain sides: length and breadth of the rectangle as the
data members. It should support the following methods:
1. __init__ for initializing the data members: length and breadth.
2. setLength for updating the length of the rectangle.
3. setBreadth for updating breadth of the rectangle.
4. getLength for retrieving the length of the rectangle.
5. getBreadth for retrieving the breadth of the rectangle.
6. area to find the area of the rectangle.
7. perimeter for finding perimeter of the rectangle.
2. Define the following methods for MyDate class:
1. addDays – To add n days to the date.
2. addMonths – To add n months to date.
3. addYears – To add n years to date.
4. weekday – To return weekday of the date.
5. diffDates – To find difference between two dates in terms of the years, months, and days.
6. futureDate – To find a future date after a given number of days, months, and years.
7. pastDate – To find a date in the past before a given number of days, months, and years.
3. Define a class Student that keeps track of academic record of students in a school. The class should
contain the following data members:
rollNum – Roll number of student
name – Name of student
marksList – List of marks in five subjects
stream – A: Arts, C: Commerce, S: Science
percentage – Percentage computed using marks
grade – Grade in each subject computed using marks
division – Division computed on the basis of overall percentage
The class should support the following methods:
1. __init__ for initializing the data members.
2. setMarks to take marks for five subjects as an input from the user.
3. getStream for accessing the stream of the student.
4. percentage for computing the overall percentage for the student.
5. gradeGen that generates grades for each student in each course on the basis of the marks
obtained. Criteria for computing the grade is as follows:
Marks Grade
>= 90 A
<90 and >=80 B
<80 and >=65 C
<65 and >=40 D
<40 E
6. division for computing division on the basis of the following criteria based on overall percentage of marks scored:
Percentage Division
>= 60 I
<60 and >=50 II
<50 and >=35 III
4. Define a class Bank that keeps track of bank customers. The class should contain the following data
members:
name – Name of the customer
accountNum – Account Number
type – Account Type (Savings or Current)
amount – amount deposited in the bank account
interest – Interest earned by the customer
The class should support the following methods:
1. __init__ for initializing the data members.
2. deposit for depositing money in the account.
3. withdrawal for withdrawing money from the account.
4. findInterest that determines the interest on the basis of amount in the account:
Fig. 10.7 Program to method to compute the date on the following day of a given date
CHAPTER 11
CLASSES II
CHAPER OUTLINE
11.1 Polymorphism
11.2 Encapsulation, Data Hiding, and Data Abstraction
11.3 Modifier and Accessor Methods
11.4 Static Method
11.5 Adding Methods Dynamically
11.6 Composition
11.7 Inheritance
11.8 Built-in Functions for Classes
We have already studied user-defined data types in the form of classes. The
classes lie at the heart of a programming methodology called object-oriented
paradigm or Object-oriented Programming (OOP). It includes several
concepts like polymorphism, encapsulation, data hiding, data abstraction,
and inheritance. In this chapter, we shall study these concepts.
object-oriented programming
11.1 POLYMORPHISM
overloading + operator
Fig. 11.1 Use of special methods
(5,7)
Comparing Dates
In addition to the special methods discussed above, Python also provides
special methods such as __eq__, __lt__, __le__, __gt__, and __ge__ for
overloading comparison operators ==, <, <=, >, and >= respectively.
Suppose we wish to compare two dates. Let us define two objects of MyDate
class and compare them as follows:
>>> date1 = MyDate(31,12,2014)
>>> id(date1)
49078096
>>> id(date2)
10775792
False
Note that in spite of two dates being same, the comparison yields False as
the result. It is so because the default implementation of
__eq__ method compares ids of the two objects. So, we define our own
implementation of the equality operator == for the class MyDate (Fig. 11.4)
that would consider two dates to be equal if and only if they agree on each of
the day, month, and year components. In line 10 (Fig. 11.4) we invoke the
built-in function isinstance to check whether the second object received as
a parameter is an object of MyDate class. If the condition holds True, it
returns the result of the comparison. Otherwise, it displays the message
'Type Mismatch' and the program terminates. The method __ne__
corresponding to the operator != may be developed on similar lines. Next,
we illustrate the use of the method __eq__
True
False
Fig. 11.4 Class methods __eq__
Next, we present the implementation of __lt__ method for the MyDate class
(see Fig. 11.5). This method may be used to sort a list of objects of type
Date.
>>> dates.sort()
print(date)
31-10-2014
17-12-2014
31-12-2014
Fig. 11.5 Date class methods __lt__
When we invoke the sort function with a list of objects of type Date, it
makes use of the method __lt__ defined for the Date class.
function overloading: different functions having the same name but different number and type
of parameters
def area(radius):
# Computes the area of circle
return areaCirc
return areaRect
out of all the definitions in a scope having the same function name, Python retains the most
recent definition
>>> area(4)
area(4)
>>> area(4, 5)
20
'''
Inputs:
'''
if b == None:
areaCirc = 3.14 * a * a
return areaCirc
else:
areaRect = a * b
return areaRect
Thus, when the function area is invoked with two arguments, it computes
the area of the rectangle, and when it is invoked with only one argument, it
computes the area of the circle.
encapsulation: grouping together related data and its associated functions under one name
abstraction: representing essential features of the real world, hiding lower level details
today = MyDate(31,1,2014)
today.day = 15
Note that setting attribute day of the object today is a violation of the
principle of data abstraction, which states that the data attributes of the
instance variables should only be accessed by the methods of the class.
Python allows us to prevent accidental access to the data and method
attributes from outside the class via the notion of private members. We can
tell Python that an attribute is a private attribute by prefixing the attribute
name by at least two consecutive underscore characters. Further, the
attribute name should not have more than one underscore character at the
end. This technique of restricting access to private members from outside the
class is known as name mangling. For example, in the class MyDate, to
indicate that the attributes day, month, and year are private members of the
class, we would prefix each of these attribute names by two consecutive
underscore characters __, thus replacing the attribute names day, month, and
year by __day, __month, and __year, respectively. Now, these attributes are
not directly accessible from outside the class, and an attempt to access them
will result in error. For example, an attempt to access today.__day from
outside the scope of the class MyDate generates an error message indicating
that no attribute with name __day exists:
accessing data and method attributes outside the class is a violation of the principle of
abstraction
>>> print(today.__day)
print(today.__day)
However, access to this attribute within the class will continue to be allowed
using notation self.__day. The restriction on the use of private variables
from outside the scope of the class may be bypassed using the syntax:
<instance>._<className><attributeName>
The methods in the class definition that modify the value of one or more
arguments are known as modifiers. For example, the methods setAddress
and setName in the class Person are modifiers since they change the values
of the data attributes address and name respectively associated with
parameter self. However, methods such as getAddress and getName of the
class MyDate only access (do not modify) the data attributes address and
name of the object self. Such methods are known as accessors.
In the methods discussed so far, the object that invokes the method is passed
as the first implicit argument (self). These methods are called instance
methods. An instance method typically defines operations on the data
members of an instance of a class. However, there are situations when we
want to define a method for a class to modify the class data members. Such a
method does not require a class object to be passed as the first parameter and
is called a static method. A static method is invoked as an attribute of a
class. It is usually invoked as className.staticMethodName.
instance methods: invoked for the particular instance of the class,which is passed as the first
argument (corresponding to self)
static methods: used for modifying class data members and do not require passing object as the
first parameter
>>> Person.getPersonCount()
Once all the methods of the class have been defined, one may realize the
need to add another method to the class or a particular instance of the class.
Python allows us to add methods dynamically to a class using the syntax:
<className>.<newMethodName> = <existingFunctionName>
For the sake of an illustration, we define a class Student having only the
constructor method __init__ (Fig. 11.7). The script also includes the
methods percentage and result. However, these methods do not belong to
the class Student. The following instruction will add the method
percentage to the class.
The method percentage can now be invoked like any other method of the
class Student as shown below:
>>> s1 = Student('Amey', 47, 450)
>>> print(s1.percentage())
90.0
<instance>.<newMethodName>=MethodType(<existingFunctionName>,
<instance>)
Now we are ready to add the method result to the instance s1 of the class
Student.
>>> s1.result()
'pass'
Invoking this method from a class instance to which we have not added the
result method will lead to an error:
>>> s2.percentage()
98.0
>>> s2.result()
s2.result()
11.6 COMPOSITION
In this section, we will refine the class Person, introduced in the last chapter,
that comprised the instance attributes name, DOB, and address in addition to
the class attribute personCount. While creating objects of class Person, we
used string objects such as '24-10-1990' as values of the date of birth (DOB).
In the last chapter, we also defined MyDate class comprising three
components day, month, and year. To use this representation of the date in
the class Person, we only need to import the MyDate class in the script, and
there is no change in the description of class Person (Fig. 11.8).
>>> print(p1)
Name:Rajat Mittal
DOB:24-10-1990
Address:B-23,Malviya Nagar,Delhi
Note that data attribute dob of object p1 is of type MyDate. Here, we have
used an object of another class MyDate as an attribute of the class Person.
The process of using objects of the other classes as attribute values is called
object composition. It is important to observe that we have already used this
concept subconsciously. While creating objects of class Person earlier, we
used objects of system-defined class str as values of attributes name, DOB,
and address. We could have, equally well, used the object
MyDate(24,10,1990)directly as an argument, while invoking the the
constructor, instead of first creating it as dob, as shown below:
using objects of other classes as attributes
11.7 INHERITANCE
>>> dir(object)
It is interesting to note that various types such as int, list, tuple, and
dict have some common methods such as __eq__, __lt__, and __str__.
These types have derived these common methods (attributes) from the
object class. The object class serves as the base class of each of these
classes.
Details of the class Employee appear in Fig. 11.11. As the Employee class
is a derived class of the base class Person, we import the base class Person
from module person (stored as person.py in the current directory). Next,
we must tell Python that the class Employee is a derived class of base class
Person. We do this by enclosing the name of base class Person in
parenthesis following the name of derived class Employee (line 3, Fig.
11.11). Based on the assumption that the Employee ids begin with 1001, the
class attribute nextId is initialized as 1001 and is incremented by the
constructor method whenever an instance of class Employee is created.
Fig. 11.11 Class Employee (employee.py)
As the Employee class is a derived class of the base class Person, all the
data and method attributes defined in the Person class become available to
the Employee class. Recall that we had defined the methods __init__,
__str__, and __del__ in the class Person. However, we need to redefine
these methods in the derived class Employee. When an object of a derived
class makes a call to a method that is also defined in the base class, Python
invokes the method of derived class. Thus, the derived class methods
override the base class methods, and this process is known as method
overriding.
The constructor for the Employee class, needs to initialize the variables of
the Person class as well as the new variables introduced in the Employee
class. Recall that we say that Employee is a Person. Therefore, to initialize
an object of class Employee, we invoke the constructor of class Person that
initializes the Person class variables for an object of the Employee class. For
this purpose, we pass self (self refers to an object of Employee class) as an
argument while invoking the Person class constructor. To be more specific,
invoking the constructor of the Person class in the Employee class
constructor does not create a new instance of the Person class, instead it
only initializes the variables of the Person class for the Employee class
object.
'B-23,Malviya Nagar,Delhi')
>>> print(Person.personCount)
>>> print(Employee.employeeCount)
>>> print(Person.personCount)
Deleted!!
>>> print(Employee.employeeCount)
>>> print(Person.personCount)
or
or
super().__del__()
Scope Rule
To access an instance attribute, Python will first look for it in the instance's
namespace, then in the class namespace, and then in the superclass
namespace recursively going up in the hierarchy. We illustrate this in Fig.
11.12.
ob2:
dir(A):
dir(ob1):
dir(B):
dir(ob2):
The values of data attributes of the objects ob1 and ob2 can be read from the
namespaces of these objects (Fig. 11.13).
Fig. 11.13 Representation of class A, class B, object ob1, and object ob2
In the expression 'ob1:\n' + str(ob1), when the __str__ method is
invoked, it uses the values of data attributes x, y, and w directly from the
namespace of object ob1. The data attribute ob1.z is also accessible as it is
defined as a class variable of the class A of which ob1 is an object.
According to scope rule, an attribute is first searched in object's namespace.
Therefore, in the expression 'ob2:\n' + str(ob2), when the __str__
method is invoked, it uses the values of data members x and v directly from
the namespace of the object ob2 and the variables x and v are bound to
values 6 and 50, respectively. The attribute y is an instance attribute
inherited from the parent class A and is bound to value 10. Similarly, the
attribute w is an instance attribute inherited from the superclass A and is
bound to value 100. However, for accessing z, Python first searches in object
ob2's namespace, then in its class B's namespace, and finally in superclass A's
namespace, where it is found and gets bound to value 30.
We may obtain the name(s) of the class(es) from which a class inherits
properties as follows:
>>> str.__bases__
(<class 'object'>,)
>>> B.__bases__
(<class '__main__.A'>,)
>>> B.__bases__[0]
<class '__main__.A'>
Note that class B inherits from only one class, i.e. A. Therefore, tuple
B.__bases__ contains only one class, i.e. <class '__main__.A'>. Given an
object, its class name may be obtained as shown below:
>>> 'Python'.__class__.__name__
'str'
Next, we illustrate the use of MyInt class to display the number of digits in
an integer:
>>> n1 = MyInt(3456)
>>> n2 = MyInt(-18)
>>> len(n1)
4
>>> len(n2)
>>> len(MyInt(0))
Note that the methods of the int class such as __add__, __sub__, __mult__,
and __div__ can still be applied to objects of type MyInt as it inherits all the
attributes of the int class. The following examples illustrate this:
>>> n1 + n2
3438
>>> n1 - n2
3474
multilevel inheritance
hierarchical inheritance
As another example of class inheritance, the two classes Clerk and Manager
may be derived from single base class Employee (Fig. 11.16). Whereas the
Clerk class has an additional class attribute clerkCount, the Manager class
has two additional attributes: a class attribute managerCount and an instance
attribute managerialPay. The complete definition of these classes is given in
Fig. 11.17. Note that class Manager defines method getSalary that overrides
the superclass method getSalary and computes the manager's salary by
adding managerialPay to an employee's Salary.
>>> print(clerk1)
Name:Arun
DOB:05-06-1930
Id:1001
Salary:20000
Date of Joining:05-06-1950
Fig. 11.17 Classes Clerk and Manager
Since there is no __str__ method in the class Clerk, to print the object
clerk1, __str__ method of the superclass Employee is invoked. Also,
because Arun is the first employee, Id 1001 is assigned to him. Next, we
create an object of class Manager:
>>> print(manager1)
Name:Rehman
DOB:05-06-1970
Id:1002
Salary:52000
Date of Joining:05-06-1990
ManagerialPay:2000
As the class Manager has its own __str__ method (lines 70–78), it will be
invoked to print manager1. As Manager is an employee, the method __str__
of Manager class concatenates
'\nManagerialPay:'+str(self.managerialPay)to
Employee.__str__(self) to return string representation of an object of the
class Manager. Next, let us print salary (basicSalary + managerialPay) of
manager1:
>>> print(manager1.getSalary())
52000
the class Appointment derives properties from two classes: MyDate and MyTime
>>> print(currentTime)
23:50:30
15-7-2014, 10:00:00
abstract methods and abstract classes identify functionality that should be implemented by all
the subclasses
__metaclass__ = ABCMeta
>>> rectangle.area()
450
>>> rectangle.perimeter()
90
>>> circle.area()
78.5
>>> circle.perimeter()
31.4
new-style classes
then the class C would inherit from classes B1 and B2 in the order B2 and B1.
Fig. 11.22 Inheritance in new-style classes (newStyleClasses.py)
In Fig. 11.23, the order of resolution would be the object c1 of class C,
class C, class B1, class B2, class A, class object. On executing the script in
Fig. 11.22, value 50 is printed. When the print function is executed in the
main function (line 21), Python invokes pre-defined method __str__ where
it needs to reference variable test. Since test is not an instance variable of
the object c1, the search is made in class C, subsequently followed by a
search in superclass B1, and finally in B2 where it is found.
Fig. 11.23 Inheritance hierarchy for classes in Fig. 11.22
For determining the order in which methods of classes will be accessed,
Python provides the attriibute __mro__ which stands for method resolution
order. It returns a list ordered by the classes in which search for methods is
to take place. For example:
>>> C.__mro__
>>> B2.__mro__
>>> B1.__mro__
>>> A.__mro__
Python provides several built-in functions that deal with classes and their
instances. For example, to find whether a class is a subclass of another class,
one may use the function issubclass that takes two arguments: sub and
super:
issubclass()
issubclass(sub, super)
The function issubclass returns True if sub is the subclass of class super,
and False otherwise. For example:
>>> issubclass(Appointment, MyDate)
True
To find whether the instance obj is an object of class class1, we use the
function isinstance:
isinstance()
isinstance(obj, class1)
True
True
False
>>>
hasattr()
This function returns True if instance obj contains an attribute attr, and
False otherwise, for example:
False
The functions getattr and setattr may be used to retrieve and set
respectively, the value val of an attribute attr of an instance obj, as
illustrated below:
getattr(obj, attr)
15
>>> print(meetStaff)
23-07-2014, 10:00:00
delattr()
delattr(obj, attr)
>>> print(meetStaff)
print(appointment1)
if self.day <= 9:
SUMMARY
1. Write a class Point having x and y coordinates as data members. Write another class LineSegment
that derives the class Point Also, list appropriate methods.
2. Define the method __ne__ for the class MyDate.
3. Define the method __sub__ (Fig. 11.24) for the class MyDate.
4. Define a class ComplexNumbers. Write operations for addition, subtraction, and multiplication, using
the notion of operator overloading.
5. Examine the following class Shape:
class Shape:
def __init__(self, shapeType, x, y):
self.shapeType = shapeType
self.length = x
self.width = y
def computeArea():
pass
CHAPTER OUTLINE
12.1 Sorting
12.2 Searching
12.3 A Case Study
12.4 More on Sorting
12.1 SORTING
Suppose we need to arrange a list of names in lexicographic order, i.e., as
they appear in a dictionary. Examine the sample data that appears in the list
names (Fig. 12.1).
Fig. 12.1 The list of names and the corresponding indexes at which they appear
We have already seen that the strings can be compared using relational
operators <, <=, >, >=, ==, and !=. So, we shall frequently use the terms such
as less, less than equal to, greater, greater than equal to, equal to, not equal
to, least, smallest, largest, maximum in the context of strings.
The attribute or property of data that forms the basis of sorting is called
the key. There are several techniques of sorting the data such as selection
sort, bubble sort, insertion sort, heap sort, merge sort, and quick sort, which
can be studied for their relative efficiency. However, in this chapter, we shall
discuss only first three techniques. Without any loss of generality, we
discuss how to sort the data in ascending order. The other case of sorting in
descending order follows similarly. We just need to change the <, <=
operators to >, >= operators, respectively and vice versa.
Now that the smallest name 'Anya' is at the proper position (index 0), we
only have to sort the names in the updated list from index 1 to 5. For this
purpose, we need to find the index of the second smallest name in the list
(i.e. the smallest name in the index range 1 to 5). In Fig. 12.4, we illustrate
this process.
Fig. 12.4 Steps in the selection sort method for second iteration (i = 1)
Since name 'Maya' at index 4 is the smallest name across the indexes
ranging from 1 to 5, we swap name at index 4 with the name at index 1. The
modified list at the end of the second iteration is shown in Fig. 12.5.
Fig. 12.5 Modified data at the end of second iteration (i = 2)
In the third iteration, we have to sort names in the updated list from index
2 to 5. Since the smallest name in the remaining unsorted list is at minIndex
2, there will be no change in the relative position of entries in the third
iteration. At the end of the fourth iteration, names at indexes 3 and 4 will be
swapped, and the modified list is shown in Fig. 12.6.
if the ith smallest element is already at its position in an iteration, there will be no change in
relative position of entries
In the fifth iteration, we begin the search for the smallest name from the
index 4. Since the name at index 5 is smaller than the name at index 4, the
names at indexes 4 and 5 will be swapped, and the modified list is shown in
Fig. 12.7.
Now that five names (at indexes 0, …, 4) have been placed in order, the
last name at index 5 is automatically in order. In this manner, we have been
able to sort a list of names (Fig. 12.7).
Using the above ideas, we give the complete script selectionSort (Fig.
12.9).
Fig. 12.9 Program for selection sort (selectionSort.py)
Sorted List
the function selectionSort works equally well on numeric and string data
Fig. 12.10 List of names and the corresponding indexes at which they appear
Fig. 12.11 Steps in the first iteration of bubble sort (i = 0). The curved double-headed arrows mark
the list elements being swapped
The modified list, thus modified, at the end of the first iteration is shown in
Fig. 12.12:
Fig. 12.12 Modified list at the end of first iteration (i = 0)
Note that at the end of the first iteration, the smallest name moves to the first
position (index 0). Similarly in the second iteration, above procedure will be
performed on names in the index range 1 to 5 and at the end of it, the second
smallest name will move to index 1 as shown in Fig. 12.13.
Fig. 12.13 Steps in the second iteration of bubble sort. The curved double-headed arrows mark the list
elements being swapped
The modified list after the second iteration is shown in Fig. 12.14.
Fig. 12.14 Modified list at the end of second iteration (i=1)
In the third iteration, we consider the names in the index range 2 to 5 and the
modified list at the end of the third iteration is shown in Fig. 12.15.
In the fourth iteration, we consider the names in the index range 3 to 5 and
the modified list at the end of the fourth iteration is shown in Fig. 12.16.
In the fifth iteration, we consider the names in the index range 4 to 5. As the
names at indexes 4 to 5 are already in sorted order, the list at the end of the
fifth iteration will be the same as the list at the end of the fourth iteration
(Fig. 12.16). Thus, at the end of the fifth iteration, all the six names have
been arranged in order. Based on the preceding discussion, we present the
complete script for the bubble sort method (Fig. 12.17).
324
Fig. 12.17 Program for bubble sort (bubbleSort.py)
Sample runs of the script bubbleSort are shown as follows:
Enter the list: ['Vijaya', 'Sanvi', 'Ruby', 'Zafar', 'Maya',
'Anya']
Sorted List
Sorted List
Next, let us apply bubble sort algorithm on the list in Fig. 12.18. The
modified list at the end of the first, second, and third iteration is shown in
Figs. 12.19, 12.20, and 12.21, respectively.
Fig. 12.18 List of names and the corresponding indexes at which they appear
Note that when we apply bubble sort on the list in Fig. 12.18, the list gets
sorted at the end of the second iteration and no data is swapped in the third
iteration. Indeed, if no data is swapped in an iteration, we conclude that the
list has already been sorted. As such, the control should break out of the
loop, instead of unnecessarily proceeding with the remaining iterations.
Based on this observation, we modify the script bubbleSort (see Fig.
12.22).
if no swapping takes place in an iteration in bubble sort, we conclude that the list is now sorted,
and skip rest of the iterations
Fig. 12.22 Program for bubble sort (bubbleSort1.py)
maintain two divisions of the list: sorted part and unsorted part.
in each iteration, insert first value from the unsorted part into the sorted part
In this example, the left sorted part (grey portion) comprises elements at
indices 0, 1, 2, 3, and the right unsorted part (white portion) comprises the
elements at indices 4 and 5. As of now, the lengths of the sorted and
unsorted parts are 4 and 2, respectively. So, at the end of the next iteration,
lengths of sorted and unsorted parts will be 5 and 1, respectively. Our task in
this iteration is to insert the element lst[4] at the correct position. As
'Maya' < 'Zafar', we shift 'Zafar' one position right, but before we do so,
we must save 'Maya' in a temporary variable, say, temp. The modified list is
shown in Fig. 12.24.
temp = 'Maya'
Fig. 12.24 List of names and the corresponding indexes
Next, we compare the value of the variable temp, i.e. 'Maya' with lst[2],
i.e., 'Vijaya'. As 'Maya' < 'Vijaya', we shift 'Vijaya' one position right.
The modified list is shown in Fig. 12.25.
Next, we compare the value of the variable temp, i.e. 'Maya' with lst[1],
i.e. 'Sanvi'. As 'Maya' < 'Sanvi', we shift 'Sanvi' one position right. The
modified list is shown in Fig. 12.26.
Next, we compare, 'Maya' with lst[0], i.e. 'Anya'. As 'Maya' > 'Anya',
we do not need to shift 'Anya', and 'Maya' can now be placed at index 1.
The modified list is shown in Fig. 12.27.
Fig. 12.27 List of names and the corresponding indexes
Recall that the element 'Maya' to be inserted in the list sorted up to index
3 was at index 4. The following code achieves the desired effect of shifting
'Maya' to its correct position at index 1:
i = 4
temp = lst[i]
j = i - 1
lst[j + 1] = lst[j]
j = j-1
lst[j + 1] = temp
code to insert value at index 4 at correct position in the list (sorted up to index 3)
Once again, we use the following list to illustrate insertion sort (Fig.
12.28):
initially, the sorted list comprise value at index 0, followed by remaining indexes to be part of
unsorted list
As shown in Fig. 12.29, in the first iteration, 'Vijaya' is shifted towards the
right by one position and 'Sanvi' (that appeared at index1 earlier) is
inserted at index 0. Thus, 'Sanvi' now belongs to the sorted part of the list.
Similarly, in the second iteration, names at indices 0 and 1 are shifted
towards the right and the name 'Anya' is placed at index 0 in the left part.
This process is continued till the fifth iteration when the right partition
becomes empty and the left partition contains the sorted list. On the basis of
the foregoing discussion, we present the complete program for insertion sort
(Fig. 12.30).
Fig. 12.29 Steps in insertion sort on the list in Fig. 12.28
Fig. 12.30 Program for insertion sort (insertionSort.py)
Sorted List
12.2 SEARCHING
In this section, we shall discuss how to find out whether a data value appears
in a list. For example, given a list of names of students in a class, we wish to
find whether a particular name appears in the list. In the following sections,
we discuss two techniques for searching a value in a list, namely, linear
search, and binary search. While the former technique scans the list from the
beginning till the data value is found or the list is exhausted, the latter
technique is considerably more efficient in terms of time complexity but
works for sorted lists only.
linear search: sequential search that scans the list from the beginning till the required data value
is found or the list is exhausted
Fig. 12.31 List of names of students
To search for the name 'Shubham' in the list, we look for this value
starting at index 0. After iterating over values at the indexes 0, 1, 2, and 3,
when the value at index 4 is compared to the target value 'Shubham', we
find that it matches the target value, and the search terminates successfully.
However, if we were searching for 'Sarthak', the entire list is exhausted
without finding a match. So, we conclude that the name 'Sarthak' is not in
the list. The complete script for linear search appears in Fig. 12.32.
Fig. 12.32 Program for linear search (linearSearch.py)
On executing the script in Fig. 12.32, Python prompts the user for the list
and the value to be searched and will display the appropriate message
indicating presence or absence of the value, for example:
Enter a list: ['Reena', 'Stuti', 'Monika', 'Deepika']
First, we examine the middle name of the list, if it matches the name that
we are looking for, we stop. If we do not find the name at the middle
position, we will only have to search on the left or right side of the middle
name depending on whether the name at the middle position is greater or
smaller than the name we are looking for. Based on this idea, we present the
binarySearch function in Fig. 12.33.
332
Fig. 12.33 Function for binary search
Now we study the last example in detail (Fig. 12.35). In this example, we
used binary search to look for the name 'Shubham' in the list ['Gaurav',
'Nitin', 'Rashmi', 'Shilpi', 'Shubham', 'Shweta']:
In the first iteration, the variables low and high are initialized to 0 to 5,
respectively. When the name to be searched is compared against the name at
index mid (=2), the name 'Shubham' is found to be greater than 'Rashmi'.
Now the value of low is set to 3 so that the search can be continued in the
index range 3 to 5. In the second iteration, taking 3 as low and 5 as high, the
name 'Shubham' is compared with the name at index mid (=4). Since the
name 'Shubham' is found at index 4, search terminates by exiting the loop.
The search process has been illustrated in Fig. 12.36.
Fig. 12.36 Steps for binary search for data given in Fig. 12.35
Note that binary search on the above-sorted list took only two steps.
However, if the same sorted list were to be searched for the name 'Shubham'
using linear search, it would have taken five steps. To see how fast binary
search works, we only have to observe that every time search fails, the
search interval is reduced to half. Thus, in the worst case, we would require
no more than (log N) + 1 steps.
2
In this section, we will discuss how to prepare a merit list of students who
took an examination. For each student, we store information about roll
number, name, and marks obtained. Sample data is shown in Table 12.1.
Let us introduce another class Section (Fig. 12.38) having data attribute
records that store information about students in the form of a list of
Student objects. In this class, we define various methods for operations on
the list records. As we have not yet discussed the implementation of these
methods, we use pass statement as the body of the function.
Fig. 12.37 Class Student (student.py)
337
Fig. 12.38 Class Section (section.py)
We will use an object of class Section, to store the sample data in Table
12.1 as list records (Fig. 12.39):
1. __init__()
The __init__ method (Fig. 12.41) initializes an instance of the Section
class by initializing its list records (of the Student class) as an empty list.
2. readList(self, source)
The readList method (Fig. 12.42) accepts the name of the source file
containing Student objects as an input parameter and appends the Student
objects read from the source file to the list records of the Section
instance at hand.
reading the Student objects for list records from source file
Fig. 12.42 Method readList
3. writeList(self, destination)
The writeList method (Fig. 12.43) accepts the name of the destination
file as an input parameter and writes to it one by one the Student objects in
the list records of the Section instance at hand.
5. isSorted(self)
If the list records is arranged in ascending order of the values of the key
rollNo, the method isSorted (Fig. 12.45) returns True, otherwise it
returns False.
checking whether the Student objects are sorted with respect to roll numbers in list records
6. binarySearch(self, rollNo)
The binarySearch method (Fig. 12.46) is applicable if the list records is
already sorted. It accepts rollNo as an input parameter. The Student
objects are searched for the given rollNo in the list records using the
binary search procedure described in the previous section. If a Student
object with the given rollNo is found in the list records, the method
returns the index of the matched object, otherwise it returns None.
7. linearSearch(self, rollNo)
The linearSearch method (Fig. 12.47) is used if the list records is not
sorted. It accepts rollNo as an input parameter. The Student objects are
searched sequentially in the list records for the given rollNo in the list
records using the linear search procedure described in the previous section.
If a Student object with the given rollNo is found in the list records, the
method returns the index of the matched object, otherwise it returns None.
searching for the roll number of a student in the unsorted list records
8. insertionSort(self)
In the previous section, we discussed three techniques of sorting a list of
objects. Now, we make use of the insertion sort technique (Fig. 12.48) to
sort the list records of Student objects, based on rollNo.
sorting list records of Student objects based on roll number using insertion sort
Fig. 12.48 Method insertionSort
9. delete(self, rollNo)
The delete method (Fig. 12.49) accepts rollNo as the input parameter. It
searches the entire list records sequentially for the Student object having
the given rollNo. If the desired Student object is found, it is removed from
the list records and the method returns the message 'Record deleted
successfully' to indicate successful termination. However, if the desired
Student object having the given rollNo is not found, the method returns
the message 'Record not found'.
deleting a Student instance with the given roll number from the list records
11. __str__(self)
The method __str__ (Fig. 12.51) of class Section constructs the string
representation for an instance of the class. It traverses the list records
invoking __str__ function for each Student object.
1. Invoke the function textToObject (line 14) from the module impExpObject for converting the student
information in a text file to a file of Student objects. In future, we may use this file of Student objects
instead of the text file. The data in the text file appears in the following format:
1,Amit,36
5,Kriti,50
4,Alok,50
2,Umang,27
3,Shweta,85
working of the script for processing student data
2. Create an instance section of the Section class and initialize its list records of Student instances
from the file created in step 1 (lines 16–18). This list of records is unsorted as of now.
3. Search for a student in the section using linear search (lines 20–26).
4. Sort the Student objects in the section based on rollNo and write in a file. In future, we may use the
sorted file (lines 28–30).
5. Read the sorted file created in step 4 to create an instance section of the Section class and use binary
search to look for a rollNo (lines 32–42).
6. Read the sorted file created in step 4 to create a text file for viewing it using a text editor (line 44).
Fig. 12.52 Program for processing student data (listManipulation.py)
Next, we show the working of the above script (Fig. 12.52) with the help
of an example:
Enter source file name: student.txt
3 found at index 4
6 not found
Suppose we wish to sort the student data on the basis of the particular key
attribute. For this purpose, we develop method insertionSort (Fig. 12.53)
that takes the choice as an input parameter and sorts the student data based
on the value of attributes rollNo, name, or marks depending upon 1, 2, or 3
as the user choice respectively. This method uses the method key to retrieve
the value of the key attribute based on the user choice. Recall that the
method insertionSort is a member of class Section. Also, the method key
should be included as a member of the class Student.
Fig. 12.53 Methods insertionSort and key
quick sort uses a pivot element for partitioning the list around it
SUMMARY
1. The process of arranging data in ascending/descending order is called sorting. The attribute that forms
the basis of sorting is called key.
2. In selection sort, to begin with, we find the smallest value in the list, and interchange this entry with
the first entry in the list. Next, we find the entry with the smallest value out of the remaining entries,
and interchange it with the second value in the list, and proceed in this manner. If there are n values,
only (n − 1) values need to be placed in order because when (n − 1) values have been put in the proper
place, then the nth value would automatically be in order.
3. In bubble sort, in each pass, we compare values in adjacent positions and interchange them, if they are
out of order. Suppose we have a list of n values. To begin with, the nth and (n − 1)th values are
compared and interchanged if found out of order; then (n − 1)th and (n − 2)th values are compared and
interchanged if found out of order, and so on. Observe that in the first pass the smallest value will
move to the front of the list at index 0; on subsequent passes, it will be ignored. After n − 1 iterations,
the list will be completely sorted and the algorithm will halt.
4. In insertion sort, the list is logically divided into two parts. Whereas the left part is the sorted part, the
right part is unsorted part comprising the elements yet to be arranged in sorted order. In each iteration,
we increase the length of the sorted part by one in the following manner: insert the first element from
the unsorted part in the sorted part at the correcft position. To find the correct position of the value to
be inserted, we compare it with values in sorted part and shift each value to the right by one position,
until the correct position is found.
5. Searching is the task of finding whether a data value appears in a list.
6. In linear search of a data value in a list, we scan the list from the beginning till the data value is found,
or the list is exhausted. This technique is known as linear search as the order of search is linear or
sequential in nature.
7. Binary search is used in case the list to be searched is already sorted. For searching a data value in this
list, we proceed as follows: first, we examine the middle element of the list, if it is equal to the data
value that we are looking for, we will stop. If we do not find the element at the middle position, we
will only have to search on the left or the right of the middle element depending on whether the data
value at the middle position is greater or smaller than the data value we are looking for.
8. Merge sort and quick sort methods make significantly less number of comparisons as compared to
selection sort, insertion sort, and bubble sort methods.
EXERCISES
1. Develop a program to sort the employee data on the basis of pay of the employees using (i) selection
sort, (ii) bubble sort algorithm, and (iii) insertion sort. Consider a list L containing objects of class
Employee having empNum, name, and salary.
2. Write the recursive version of linear search and binary search algorithms, discussed in the text.
3. Rewrite selection sort, bubble sort and insertion sort functions using recursion.
4. For the list shown below, show the values of the indexes low, high, and mid at each step of the binary
search method discussed in the text when we are searching for the key:
1. 15
2. 25
3. 55
4. 40
5. 22
5. Write a function leftCirculate that takes a list as an input and left circulates the values in the list so
that in the final list, each value is left shifted by one position and leftmost value in the original list
now appears as the rightmost value. For example, on execution of the function on the list [1, 2, 3,
4, 5] it would be transformed to the list [2, 3, 4, 5, 1]. Modify the function to include a numeric
argument to specify the number of positions by which left rotation is to be carried out.
6. Write a program that defines a class Card which can be used to instantiate cards with a particular rank
and suit. Create another class DeckOfCards for maintaining a sorted list of cards using a method
sortedInsert that takes an object of class Card as an input parameter and inserts it at the suitable
position in the sorted list.
!
This section may be skipped without loss of continuity.
CHAPTER 13
DATA STRUCTURES I: STACK AND QUEUES
CHAPTER OUTLINE
13.1 Stacks
13.2 Queues
In this chapter, we will be concerned with the first meaning of the term
data. Further, Oxford Dictionary defines structure as an arrangement of and
relations between the parts of something, a building or other object
constructed from several parts. The terms such as construction, form,
formation, shape, combination, conformation, pattern, and mold are used as
synonyms for structure. Thus, the phrase data structure refers to
construction, formation, shape, combination, conformation, pattern, mold, or
structure made from simple forms of data. In this chapter, we shall study the
data structures stacks and queues, and methods to implement them using
lists in Python.
dictionary meaning of structure
data structures
13.1 STACKS
In a stack, objects are stored one over the other, and these objects leave in
the reverse order of their arrival. For example, in a restaurant, the waiter puts
the used plate one above the other. The cleaner takes a plate from the top,
cleans it, and puts it onto another stack, from which the plate placed on top
can be picked up for eating. Note that the used plate that is placed last is
cleaned first and the plate that is cleaned last is taken first for eating. This is
called Last In First Out (LIFO) arrangement. We observe another example
of Last In First Out arrangement in the library, where the readers stack used
books one above other. Subsequently, a staff member in the library picks up
books one by one from the top of the stack and places them in appropriate
shelves.
push: Place (push) a new element on top of the stack. The push operation is also called insertion of an
element in a stack.
pop: Remove (pop) top element from the stack. The pop operation is also called deletion of an element
from a stack.
The easiest way to represent a stack is using a list. As stack operations push
and pop relate to the top element of the stack, we need to keep track of the
top element of the stack. Remember, it is only the top element which is
accessible. At any point in time, insertion or removal of an object takes
place at the top of the stack. For example, beginning with an empty stack,
we perform the following operations in a sequence.
insertion and deletion of elements take place from top of the stack
1. push 5
2. push 10
3. pop
4. push 20
5. push 25
6. push 30
7. pop
8. pop
9. pop
10. pop
11. pop
In Fig. 13.1, we show the stack, in the form of a list, on execution of each of
the above operations. Note that in step 11, we tried to pop an element from
the stack when it was already empty. When an attempt is made to pop from
an empty stack, it is called underflow condition.
In light of the above discussion, we define the class Stack (Fig. 13.2).
The following operations are often required to be performed on a stack:
check if the stack is empty, push an object, pop an object, retrieve value at
the top of the stack without removing it from the stack, find the number of
elements in the stack, print contents of the stack. Note that we do not discuss
an operation to test whether the stack is full as append operation in a list is
limited only by the physical storage available to the program.
stack operations
stack underflow
In Fig. 13.2, we present the above-mentioned stack operations using inbuilt
list operations append and pop. The constructor for the class Stack defines
an empty list – values – to store the data objects that would be pushed on
the stack. Next, we describe each of the above-mentioned operations for the
class Stack.
use of list operations append and pop for implementing stack operations
Fig. 13.2 Class Stack (stack.py)
1. Is Stack Empty
The method isEmpty determines whether the stack is empty by checking
whether the length of the list values is zero, i.e. whether
len(self.values) == 0. The method returns True if the stack is empty,
and False otherwise.
2. Push an Object
The method push takes the element to be pushed as an input parameter and
puts it at the end of the list values by invoking the method append.
3. Pop an Object
The method pop first checks whether the stack is empty by invoking the
method isEmpty. If the stack is not empty, the object at the top of the stack
(i.e, the element that was pushed on the stack last) is popped and returned.
Otherwise, the message 'Stack Underflow' is displayed and None is
returned indicating empty stack.
4. Retrieve Value at the Top of Stack
The method top returns value at the top of the stack if the stack is not
empty. Otherwise, None is returned indicating empty stack. The stack
contents remain unchanged.
5. Find the Number of Elements in the Stack
The method size returns the number of elements in the stack by returning
the length of the list values. For the purpose of demonstration, we have
provided this method to return number of elements in the stack, even
though stack operations do not require this method.
6. Print Contents of the Stack
The method __str__ produces a string representation of the entire stack by
concatenating the string representation of each value in the list values. The
string representation is used to print the contents of the stack. For the
purpose of demonstration, we have provided this method to display the
contents of the entire stack, even though stack operations do not require this
method.
a + (b + c) * (k + (d + e) * (f + g * h))
Next, we show the evaluation of the above expression (Fig. 13.4). Note that
in order to evaluate the expression correctly, we need to keep track of
precedence of operators and matching parentheses. In this process, we have
to scan parts of the expression several times. An alternative form of
expressions, called postfix form removes this difficulty.
Fig. 13.4 Evaluation of expression a+(b+c)*(k +(d+e)*(f+g*h))
Postfix form: In the postfix form, the operator appears after the operands.
For example, the infix expression a + b would be written as a b + in the
postfix form. Now, as a b + is the postfix expression for a + b, the postfix
expression for (a + b) + c would be a b + c +. Before we get into the
details of converting expressions from infix to postfix form, we discuss the
evaluation of postfix form expressions. To evaluate a postfix form
expression, we make use of a stack and scan the postfix expression from left
to right, applying the following rules:
If the character currently being scanned is an operator, and precedence (operator currently scanned) >
precedence (operator on top of the stack), push it on the stack
If the character currently being scanned is an operator, and precedence (operator currently scanned)
<= precedence (operator on top of the stack), pop off and append to the output string, each operator
having precedence higher than or equal to the precedence of the operator currently being scanned,
until an operator having lower precedence is encountered on top of the stack, or the stack becomes
empty. Now, push the operator being scanned currently on the stack.
If the character being scanned is an operand, append it to the output string.
If the end of the input string is reached, pop off all the operators one by one and append to the output
string.
push: if operator currently scanned is '(', or the top of the stack is '(', or precedence (operator
currently scanned) > precedence (operator on top of the stack)
pop: if operator currently scanned == ')', then pop off all the operators up to and including the first
'(' encountered in the stack. If the character currently being scanned is an operator other than a
parenthesis, and precedence (operator currently scanned) <= precedence (operator on top of the stack),
pop off and append to the output string, each operator having precedence higher than or equal to the
precedence of the operator currently being scanned, one by one, until '(' or an operator having lower
precedence is encountered on top of the stack, or the stack becomes empty. Now, push the operator
being scanned currently on the stack.
If the character being scanned is an operand, concatenate it to the output string.
If the end of the input string is reached, pop off all operators one by one. Concatenate the operators to
output string as they are popped off.
Note that a right parenthesis would never be pushed on the stack. Since ')'
terminates a sub-expression, on encountering ')', we pop off all operators
up to the matching '(', that is, the first '(' encountered on the stack. As the
role of '(' is now over, it can also be popped out of the stack. However, it is
not appended to the output string as postfix form expressions do not use
parentheses. We put together above ideas in the form of the function
postfix (Fig. 13.7). Note that we have considered expressions involving
+,-,*, /, (,) and single digit operands only.
On executing the script in Fig. 13.7, it outputs the postfix expression for a
given infix expression:
Enter the expression in infix notation: ((7-5)*6+4) 75-6*4+
Fig. 13.7 Program to find postfix expression for the given infix expression (postfix.py)
13.2 QUEUES
A queue is a data structure that behaves in First In First Out (FIFO) manner,
i.e. objects leave in the same order in which they arrive. All insertions occur
at one end called rear end, and all deletions occur at another end called
front end. Insertion and deletion operations are also known as enqueue and
dequeue operations respectively.
queue: first in, first out
use of list operations append and pop(0) for implementing queue operations
Fig. 13.9 Class Queue (queue.py)
The constructor of class Queue introduces the list values for storing the
queue objects. Initially, the list values is an empty list. We define the
following Queue operations:
1. isEmpty: The method isEmpty returns True if the length of the list values is zero, and False
otherwise.
2. enqueue: It takes the element to be inserted in the queue as an input argument and adds the element
at the rear end of the list values by invoking the method append.
3. dequeue: The method dequeue first checks whether the queue is empty by invoking the method
isEmpty. If the queue is empty, the message 'Queue Underflow' is displayed and None is returned
indicating underflow. If the queue is not empty, the value from the front end of the list values is
deleted using the method pop and returned.
4. front: If the queue is not empty, the method front returns the value at the front end (index zero in
the list values), without deleting it from the queue. Otherwise, it returns None indicating empty queue.
5. size: The method size returns the number of elements in the queue by returning the length of the list
values. For the purpose of demonstration, we have provided this method to return the number of
elements in the queue, even though queue operations do not require this method.
6. __str__: The method __str__ produces a string representation of the entire queue by concatenating
the string representation of each value in the list values. For the purpose of demonstration, we have
provided this method to display the contents of the entire queue, even though queue operations do not
require this method.
SUMMARY
1. The stack is a data structure in which objects are stored one over the other, and these objects leave in
the reverse order of their arrival. Such an arrangement of objects is called Last In First Out (LIFO)
arrangement.
2. A stack is characterized by the following operations:
push: Place (push) a new element on top of the stack. The push operation is also called insertion
of an element.
pop: Remove (pop) top element from the stack. The pop operation is also called deletion of an
element.
3. Popping an element from the stack when it is empty results in an underflow condition.
4. Python’s built-in list methods append and pop are typically used for implementing a stack.
5. A queue is a data structure that behaves in First In First Out (FIFO) manner i.e. objects leave in the
same order in which they arrive. All insertions take place at one end called rear end, and all deletions
occur at another end called front end. Insertion and deletion operations are also known as enqueue
and dequeue operations respectively.
6. When a queue is empty, dequeue operation on it results in an underflow condition.
7. Python provides inbuilt list operations append and pop for implementing a queue.
EXERCISES
1. Imagine that Python list does not support methods append and pop. Examine the script in Fig. 13.11
and define your implementation of push and pop operation of the stack by filling up the code.
Fig. 13.11 Class Stack(stackDefined.py)
2. Imagine that Python list does not support methods append and pop. Examine the script in Fig. 13.12
and define your own implementation of enqueue and dequeue operation on a queue by filling up the
missing code:
Fig. 13.12 Class Queue(queueDefined.py)
3. The queue implementation defined in question 2 does not utilize the storage space effectively since if
front points to index j and rear points to index i >= j, empty space at indexes 0 to i-1 cannot be
utilized as shown in Fig. 13.13.
6. Rewrite the code in exercise 2 so that whenever there is a queue overflow scenario, all the elements in
the queue are shifted (if possible) so that the front element is at index 0.
7. Write a program to reverse a string using stacks.
8. Evaluate the following postfix expression. Show the status of the stack on the execution of each
operation.
1. 99/52*9-+
2. 25*94/5-+
3. 526*93/-*
4. 51+31-*
5. 687+*82/-
6. 152-*25*+
7. 55+93-*3/
8. 651+21-+*
9. 836+27-9+*/
9. Convert the following infix expression to its equivalent postfix expression, showing the stack contents
at each step.
1. 8+6/(5-3)*2
2. (8–3-1)*6/2+8/4
3. 8+(9–9/3–4*7)–5
4. 7+6–7/2–7*4–3
CHAPTER 14
DATA STRUCTURES II: LINKED LIST
CHAPTER OUTLINE
14.1 Introduction
14.2 Insertion and Deletion at the Beginning of a Linked List
14.3 Deleting a Node with a Particular Value from a Linked List
14.4 Traversing a Linked List
14.5 Maintaining Sorted Linked List while Inserting
14.6 Stack Implementation Using Linked List
14.7 Queue Implementation Using Linked List
14.1 INTRODUCTION
Next, we describe a class Node for dealing with nodes of a linked list in a
program. An instance of this class comprises two members, namely, data
and next. We define the method __init__ (Fig. 14.3) for the class Node that
creates an instance of a node of the linked list. In this method, self refers to
the Node object being created, self.data refers to the object value, being
passed as an argument (an instance of class int in Fig. 14.1), and self.next
refers to an instance of the class Node. Note that when we create a node
object, by default, next is assigned the value None. Now, we show a more
accurate representation of the linked list in Fig. 14.1 (Fig. 14.2). However,
for reasons of brevity and simplicity of the figures, we will continue to use
the representation of the linked list shown in Fig. 14.1.
Now let us examine the script linkedList1 (Fig. 14.4) that creates the
linked list shown in Fig. 14.1. In Fig. 14.5, we show the run-time stack as
the execution of the code proceeds in Python Tutor. Since Python Tutor does
not allow us to import user defined modules, in order to execute the script in
Python Tutor, import statement should be replaced by the complete
definition of the class.
when a name refers to a node, we say: it is a reference to the node or it points to the node
Fig. 14.4 Linked list creation (linkedList1.py)
lst refers to the first node of the linked list. We may also say that lst refers to the linked list.
lst.data refers to the data attribute of the first node (i.e., int object 20) and lst.next refers
to the next attribute of the first node (i.e., second node).
As lst.next refers to the second node, lst.next.data refers to the data attribute of the
second node (i.e., int object 15)and lst.next.next refers to the next attribute of the second
node (i.e. third node).
As lst.next.next refers to the third node, lst.next.next.data refers to the data attribute of
the third node (i.e., int object 25) and lst.next.next.next refers to the next attribute of the
third node (i.e., object. None).
Fig. 14.5 Creation of a linked list lst
In lines 11 to 17 we print data values and node instances. On executing
theses lines, Python produced the following output:
lst: <node.Node object at 0x0305BD90>
lst.data: 20
lst.next.data: 15
lst.next.next.data: 25
lst.next.next.next: None
You must have noted that the above method of accessing nodes of a linked
list as a sequence of next links (e.g., lst.next.next.next) beginning the
first node is not just cumbersome, but also unworkable for linked lists
having several nodes. As an alternative, we typically introduce, a variable
current that keeps track of the node with which we are currently dealing.
We insert a new node in the linked list by assigning the new node to
current.next. In the script linkedCubes (Fig. 14.6), we use this method to
create a linked list of cubes of four numbers beginning 1.
Execution of line 9 creates the node lst having the data attribute lst.data
equal to 1 (Fig. 14.7(a)). On execution of line 10, both current and lst
refer to this node (Fig. 14.7(b)). Every time line 12 is executed, a new node
is created with data attribute i**3 and assigned to current.next. Thus the
new node gets inserted in the linked list. Subsequently, in line 13, current is
assigned current.next to make the node just inserted the current node for
the next iteration. Thus, a new node is always inserted after the node that
was inserted last in the linked list. The linked list on insertion of each of the
nodes having data values 8, 27, and 64, respectively, is shown in Fig.
14.7(c), 14.7(d), and 14.7(e), respectively.
In this section, we will discuss linked lists in some more detail. We develop
a class LinkedList (Fig. 14.8) that provides the following functionality:
Fig. 14.7 Linked list lst visualization
create an empty linked list,
insert a node at the beginning of linked list
delete a node from the beginning of linked list.
This class makes use of the Node class discussed earlier. We introduce a
variable head to refer to the first node of the linked list. As the linked list is
initially empty, head is initialized to be None in the constructor method (line
10).
When the option 1 is chosen, the user is asked to enter the value for the node
to be inserted in the linked list. We demonstrate the linked list operations for
the following sequence of choices:
Choice value
1 25
1 15
1 20
2
3
On entering choice 1 and value 25, the method insertBegin is invoked
with the argument 25. It inserts a node having value 25 at the beginning of
the linked list. For this purpose, it first checks whether linked list is empty,
i.e., head contains None as the associated value. As the linked list is, indeed,
currently empty, it invokes the constructor of the Node class with the
argument 25 (Fig. 14.8, line 21) to create a node having 25 as the value of
data and None as the value of the next link. This node instance is referred to
via head of the linked list (Fig. 14.10(b)).
Next, we wish to insert another node having data value 15 in the linked
list. However, the linked list is non-empty now. Again, we invoke the
method insertBegin with the argument 15. Execution of line 23 (Fig. 14.8)
creates a node instance named temp having 15 as the value of data and None
as the value of the next link (Fig. 14.10(c)). On execution of line 24, the
node instance temp gets added to the linked list by assigning the value of
head of the linked list lst to the next link of temp (Fig. 14.10(d)). Note,
however, that we still need to update head to point to the beginning of the
modified list. Execution of line 25 (Fig. 14.8) achieves this (Fig. 14.10(e)).
In Fig. 14.10(f), we see a compact representation of the same linked list on
exit from the function insertBegin as visualized in Python Tutor. To add
another node having value 20 at the beginning of the linked list, we invoke
the method insertBegin with the argument 20. On execution of the method
insertBegin, the final linked and its compact representation are shown in
Fig. 14.10(g) and Fig. 14.10(h), respectively.
Fig. 14.10 Insertion at the beginning of the linked list
Next, we wish to delete a node from the beginning of the linked list. On
entering choice 2, method delBegin is invoked. It first checks whether
linked list is empty, i.e. whether the value of head is None. If the linked list is
empty, the method displays the message 'Empty List' and returns the
control to the main function (lines 36–37, Fig. 14.8). However, the linked list
lst is non-empty as it contains three nodes. To delete the first node, we first
save a reference to it as temp and refer to its data as value (lines 39–40: Fig.
14.8, Fig. 14.11(a)). On execution of line 41 (Fig. 14.8), head of the linked
list is updated to point to the second node, which now becomes the first node
of the linked list (Fig. 14.11(b)). On the execution of line 42, the node
pointed by temp is deleted using del (Fig. 14.11(c)). Finally, on the
execution of line 43, method delBegin exits while returning value (20) (Fig.
14.11(d)).
deleting a node somewhere in the middle: traverse the list to search for target value
if a node having the target value is not found, display 'Value not Found!!'.
Fig. 14.13 Deletion of a particular value from the linked list
Next, we define the string representation for a linked list. Consider a linked
list lst with three nodes having successive data values 20, 15, and 25. We
define the string representation of this linked list to be the string: '20->15-
>25' as shown below:
>>> print(lst)
20->15->25
As first step, the method insertSort checks whether linked list is empty
i.e. whether head has the value None (line 21). If the linked list is currently
empty, it invokes the constructor for the Node class with the argument value
(line 22) to create a node having value as data and None as the value of the
next link. The attribute head of the linked list now refers to this node
instance (line 22). If the linked list is not empty and the value to be inserted
is smaller than the value of the data of the first node, execution of lines 24–
26 creates a new node and inserts it at the beginning of the linked list and the
modified list remains in ascending order of data values. Otherwise, we need
to find the proper position for inserting the new node with given value.
To illustrate the process of inserting a node (not the first node) having a
given value of data, we consider a linked list, having three nodes
comprising data 1, 3, and 5 (Fig. 14.17(a)). Suppose we wish to insert a
node having data value 4 in the linked list. As usual, the variable current is
used to keep track of the node with which we are currently dealing. Initially,
it is set to point to the first node, i.e. head of the linked list (line 28). We use
another variable prev to keep track of the node previous to the current
node. Initially, it is set to None (line 29 (Fig. 14.15), Fig. 14.17(b)).
Execution of while loop (lines 30–34) causes traversal of the linked list until
the control reaches the node before which the new node is to be inserted (i.e.
current.data >value) (Fig. 14.17(c) and Fig. 14.17 (d)), or end of the
linked list is reached. Execution of line 35 invokes the constructor for the
Node class with the argument 4 to create a node temp having 4 as the value of
data and None as the value of the next link (Fig. 14.17(e)). Execution of line
36 updates the next link of node instance pointed by prev to point to the
new node (being referred to as temp) (Fig. 14.17(f)). Further, on execution of
line 37, the next link of the temp node instance is updated to refer to the
node instance current (Fig. 14.17(g)). In Fig. 14.17(h), we see a compact
representation of the same linked list on exit from the function insertSort.
Fig. 14.15 Class LinkedList (linkedListSorted.py)
Fig. 14.16 Class LinkedList (linkedListSortedMain.py)
Fig. 14.17 Sorted linked list lst
variable current: keeps track of the current node of interest
variable prev: provides a link/reference to the node before the current node
As we always push the new node on the stack as the top node, we must
insert it at the beginning of the linked list. Similarly, we pop off a node from
the stack by deleting the node at the beginning of the linked list. In the script
linkedStackMain (Fig. 14.19), we present the main function for
demonstrating various operations of the class LinkedStack.
Fig. 14.19 main function using operations of class LinkedStack (linkedStackMain.py)
SUMMARY
1. A linked list comprises objects, called nodes, each of which contains a link to the next object (node).
Thus, next link defines the relationship of a node to the next node.
2. In Python, all names reference objects, i.e. instances of classes.
3. A linked list may require the following functionality:
Creating an empty linked list
Inserting a node at the beginning of the linked list
Deleting a node from the beginning of the linked list
Deleting a node with particular value from the linked list
Inserting a node in sorted linked list
4. In the stack implementation of linked list, push and pop operations are analogous to the following
operations in a linked list: insertion at the beginning and deletion from the beginning.
5. In queue implementation using linked list, the method enqueue inserts at the rear end of the linked
queue and the method dequeue deletes from the front end of the linked queue.
EXERCISES
1. Write a method insertEnd for the class LinkedList that takes a value as an input and adds a node
having that value at the end of the linked list.
2. Write a method delEnd for the class LinkedList that deletes the last node of the linked list and returns
the value of the data attribute of the last node.
3. Write a function that takes two sorted linked lists as input parameters and returns the merged, sorted
list.
4. Write a method findVal for the class LinkedList that takes n as an input parameter and returns value
of the data attribute of the nth node starting from the beginning.
5. Write an iterative method reverse for the class LinkedList that reverses the given linked list.
6. Write a recursive method reverDisplay for the class LinkedList that displays the data values of the
linked list from the right end.
7. Write a method divideList for the class LinkedList. The method should create and return a tuple
comprising two linked lists, one comprising nodes at even positions and another comprising nodes at
odd positions.
8. A variant of the linked list is known as doubly linked list or two-way linked list (Fig. 14.22)
comprising the following node structure having two links (next and prev) for traversing in both
directions.
Fig. 14.22 Doubly linked list
class Node:
def __init__(self, value):
'''
Objective: To initialize an object of class Node
Input Parameter:
self (implicit parameter) - object of type Node
Return Value: None
'''
self.data = value
self.next = None
self.prev = None
CHAPTER OUTLINE
15.1 Definitions and Notations
15.2 Binary Search Tree
15.3 Traversal of Binary Search Trees
15.4 Building Binary Search Tree
no two nodes may have the same child node, however, multiple nodes may have the same
parent node
root: A
internal nodes: A, B, D, F
leaves: E, C, H, G
Now, we describe some terminology in the context of the tree shown in Fig.
15.1:
1. Leaf: A leaf node is a node which has no children. In the figure, the nodes E, C, H, and G are leaves.
2. Internal node: A node which is not a leaf node is called internal node or a non-leaf node. In the
figure, the nodes A, B, D, and F are internal nodes.
3. Path and Path Length: If n ,1 n2, …, nk is a sequence of nodes in a tree such that ni is the parent of
ni+1 for 1 <= i <= k-1, the sequence is called a path of length k-1 from n1 to nk. In the figure, A, D, G
is a path of length 2.
tree terminology
4. Height: The length of the longest path from the root to a leaf in a tree defines the height of the tree.
For example, in Fig. 15.1, A, D, F, H is the longest path, and thus the height of the tree is three. Also,
we define height of an empty tree to be zero.
5. Level: Level of a node is the number of edges on the path from the root to the node. For example,
nodes A, D, F, and H are at levels 0, 1, 2, and 3, respectively.
6. Ancestor/Descendant: If there is a path from node n 1 to node n2, we say that n1 is an ancestor of node
n2 and n2 is a descendant of node n1. Thus, if node n1 is an ancestor of node n2, then n1 is either parent
of n2 or parent of an ancestor of node n2. Also, by definition, a node is an ancestor as well as
descendant of itself. For example, the node D is an ancestor of each of the nodes D, F, G, and H. Note
that node D being parent of each of the nodes F and G, is an ancestor of each of the nodes F and G.
Similarly, the node F being parent of the node H is an ancestor of node H. Also, the node D being an
ancestor of node F, which in turn is an ancestor of node H, is an ancestor of node H. Similarly, the
nodes D, F, G, and H are descendants of the node D.
7. Siblings: Children of the same node are siblings to each other. For example, B, C, and D being children
of A, are siblings. Similarly, F and G are siblings.
8. Subtree: A subtree of a tree is a tree that comprises a node of the tree together with all its
descendants, for example in Fig. 15.1, the tree comprising the nodes D, F, G, and H is subtree of the tree
having root A.
A binary tree is a particular type of tree whose nodes have two or fewer
children. In a binary tree, the child nodes of a node are called the left-child
and right-child. A binary tree may be an empty tree, comprising no nodes at
all, or may comprise a root node along with other nodes which may be
organized as a left binary subtree and a right binary subtree of the root node.
The left and right binary subtrees may also be empty (as per the definition of
binary tree). For example, in Fig. 15.2(a), binary tree having the node
labelled 6 as the root (also called binary tree rooted at node 6) has two
subtrees—a binary tree rooted at 10 and another binary tree rooted at 23. The
binary tree rooted at 10 has a left-child—the binary tree rooted at 15. We say
that the binary tree rooted at 10 does not have a right-child, or that the right-
child is an empty tree. The node labeled 15 is a leaf node as its left-child as
well as the right-child is an empty tree. Similarly, the nodes labelled 30 and
20 are leaves.
binary tree: empty tree or a tree with root node having a left binary subtree and a right binary
subtree
strictly binary tree: binary tree in which every non-leaf node has non-empty left and right
subtree
There are some special types of binary tree like strictly binary tree (Fig.
15.2(b)) and complete binary tree (Fig. 15.2(c)). A strictly binary tree is a
binary tree in which every non-leaf node has non-empty left and right
subtree. Thus, each node in a strictly binary tree has either two children or
none. A complete binary tree is a binary tree that is full on all levels except
the lowest level which is filled in from left to right.
complete binary tree: a binary tree that is full on all levels except the lowest level which is
filled in from left to right
Fig. 15.2 Binary Tree
A binary tree is called a binary search tree if for any node n of the binary
tree, every node in its left subtree has value smaller or equal to that of the
node n, and every node in its right subtree has value larger than that of node
n. For example, in the following binary search tree (Fig. 15.3), the root node
has value 15. Note that values 10 and 6 in the left subtree of the root are
smaller than 15, and values 23, 20, and 30 in the right subtree of the root are
larger than 15. Similarly, value 6 in the left subtree of binary search tree
rooted at 10 is less than 10. Further, values 20 and 30 in the left and right
subtree, respectively of the binary search tree rooted at 23 are smaller and
larger than 23, respectively. In the rest of this chapter, we will focus only on
the binary search trees.
binary search tree: binary tree in which, for every node n, every node in its left subtree has
value smaller or equal to it and every node in its right subtree have value larger than it
Fig. 15.3 Binary search tree
Now let us examine the script BSTree (Fig. 15.5) that creates the binary
search tree bst shown in Fig. 15.3. Execution of line 8 (Fig. 15.5) creates a
node instance comprising data (int object 15), left link (object None) and
right link (object None) (Fig. 15.6(a)). This node instance is named as bst.
Execution of line 9 creates a node instance comprising data (int object 23),
left link (object None) and right link (object None) (Fig. 15.6(b)). Now,
the name bst.right which referred to None on the execution of line 8, refers
to the new node just created. Thus, execution of line 9 defines the right-child
of the root node. Similarly, execution of lines 10 and 11 defines the right
child and the left child of the binary search tree having the root with data 23
(Figs. 15.6(c) and 15.6(d)) by creating node instances with int objects 30
and 20, respectively. Further, execution of line 12 defines left-child of the
root node (Fig. 15.6(e)). It creates a node instance comprising data (int
object 10), left link (object None), and right link (object None). Now,
bst.left which referred to None on execution of line 8, refers to the new
node just created. Finally, execution of line 13 defines the left-child of this
node having data (int object 6) (Fig. 15.6(f)).
Fig. 15.4 Class Node of binary search tree (bNode.py)
Fig. 15.5 Creating a binary search tree (BSTree.py)
Note that an empty binary tree can be constructed by assigning None to bst.
Fig. 15.6 Visualization of building a binary search tree
In Fig. 15.7, we describe the function inorder for inorder traversal of the
binary tree. On invoking the function inorder with the argument bst–
binary search tree instance constructed above, the nodes will be visited in
the following order of data values:
>>> inorder(bst)
6 10 15 20 23 30
Note that when we traverse the nodes of a binary search tree in inorder, the
data values appear in ascending order.
traversing binary search tree in inorder yields nodes in ascending order of their values
Given the root node object, the function first traverses the left subtree,
then the root, and then the right subtree. We illustrate the execution of
function inorder using Python Tutor (Fig. 15.8). On invoking the function
with argument bst, root points to the node having data (=15) as shown in
Fig. 15.8(a). Since root is not None, on execution of line 3, the function
inorder is invoked with the left-child of the root node, i.e. node having data
(=10), which now becomes new root node for this new function call (Fig.
15.8(b)). It further invokes the function recursively (line 3) with left-child
node having data (=6). Being a leaf node, the root is not None (Fig.
15.8(c)). So the function inorder is invoked with the argument root.left
(= None). Now that root is None (Fig. 15.8(d)), the function terminates, and
the control is returned to line 4 of the previous function call (Fig. 15.8(e)),
and value 6 is printed. On execution of line 5, the function inorder is
invoked with the argument root.right (= None). As the root is None (Fig.
15.8(f)), the function terminates, and the control returns to the previous call.
The traversal of the binary tree having root label 6 is now complete (Fig.
15.8(g)). So, the control returns to the previous call (root labeled 10, line 4).
Now the left subtree of this subtree (root labeled 10) has already been
traversed (Fig. 15.8(h)). On execution of line 4, root.data (=10) is printed.
On execution of line 5, the function inorder is invoked with the right-child
(None) as the argument (Fig. 15.8(i)). The right-child of the root (labeled
10) being an empty tree, the control immediately returns to the previous call
of the function inorder (root labeled 10, see Fig. 15.8(j)). As this call to
function inorder is now complete, the control is transferred to the previous
call of the function inorder (root labeled 15, Fig. 15.8(k)). Line 4 is now
executed and the root label (= 15) is printed. Next, on execution of line 5,
the function inorder is invoked with the right-child (root labeled 23) as the
argument. Continuing in this manner, 20, 23, and 30 get printed.
Fig. 15.8 Inorder Traversal
In Fig. 15.9, we present the function preorder for preorder traversal of the
binary tree. On invoking the function preorder with bst as the argument,
we get the data values in preorder traversal:
>>> preorder(bst)
15 10 6 23 20 30
6 10 20 30 23 15
height of the tree is one more than the maximum of the heights of left and right subtree
>>> height(bst)
2
Fig. 15.11 Function height (bTree.py)
a new node should be carefully inserted in a binary search tree, so that it still remains a binary
search tree
in a binary search tree, the new node is always inserted as a leaf node
parent and child node: to keep track of nodes while traversing the binary search tree for
locating position of insertion for new node
Fig. 15.13 Insertion of value 12 in binary search tree
Since value 12 (data value for the new node to be inserted) is less than
the value of child node, i.e. value (=12) <=child.data (=15), child is
updated to point to the left node of child node (i.e., child = child.left)
on execution of line 28 (Fig. 15.12, Fig. 15.13(d)). Since child is not None
(child.data =10), another iteration of the while loop begins and execution
of line 26 updates parent (parent = child). Again, value 12 is compared
with the data value (10) at child node, and since 12 > 10, child is updated
to point to the right-child of the child node (i.e., child = child.right) on
execution of line 30 (Fig. 15.12, Fig. 15.13(e)). As child.right is None,
child becomes None on execution of line 30 (Fig. 15.12). This leads to
termination of the while loop.
Thus, we have found the place where the new node is to be inserted. Now,
the condition value (=12) <=parent.data (=10) is False. So, execution of
line 34 (Fig. 15.12) creates a node instance by invoking the constructor for
the Node class with the argument value (=12). As usual, the constructor
assigns the value None to left and right links of the node being created.
The parent–child relationship is established by assigning the new node (data
=12) to parent.right (line 34 (Fig. 15.12), Fig. 15.13(f)). Finally, in Fig.
15.13(g), we see the compact representation of binary search tree after
insertion of the node with value 12.
compare the value of new node to be inserted as child node with parent node and assign it as
left or right child accordingly
SUMMARY
1. A tree is a hierarchical structure. It is a collection of elements called nodes along with a relation called
parenthood that defines a hierarchical structure on nodes.
2. The root node is a node which does not have any parent node.
3. A leaf node is a node which has no children.
4. A node which is not a leaf node is called internal node or a non-leaf node.
5. If n , n , …, n is a sequence of nodes in a tree such that n is the parent of n
1 2 k i i+1 for 1 <= i <= k-1,
the sequence is called a path of length k-1 from n1 to nk.
6. The number of edges on the longest path from the root to a leaf in a tree defines the height of the tree.
7. The level of a node is the number of edges on the path from the root to the node.
8. n is an ancestor of node n if n is either parent of n or parent of an ancestor of node n .
1 2 1 2 2
1. Given inorder and preorder traversal, write a method that constructs a binary tree.
2. Write a method delVal for class binSearchTree that deletes a node having a given value from the
binary search tree.
3. Write a method levelOrderTraversal for the class binSearchTree that traverses binary search tree
level by level.
4. Write a method count for the class binSearchTree that counts and returns the number of nodes in a
binary search tree.
5. Write a method countLeaves for the class binSearchTree that returns the number of leaf nodes in a
binary search tree.
6. Write a method countNonLeaves for the class binSearchTree that returns the number of non-leaf
nodes in a binary search tree.
7. Write a method delLeaves for the class binSearchTree that deletes all the nodes that are currently the
leaf nodes of a binary search tree.
8. Write a method mirrorBST for the class binSearchTree that creates and returns mirror image of a
binary search tree.
9. Write a method copyBST for the class binSearchTree that creates and returns a copy of a binary
search tree.
10. Write a method minVal for the class binSearchTree that finds and returns the minimum value in a
binary search tree.
11. Write a method ancestor for the class binSearchTree that finds and returns the first common
ancestor of a pair of nodes in the binary search tree.
CHAPTER 16
MORE ON RECURSION
CHAPTER OUTLINE
16.1 Pattern Within a Pattern
16.2 Generalized Eight Queens Problem
16.3 Knight's Tour Problem
16.4 Stable Marriage Problem
16.5 Fractal (Hilbert Curve and Sierpinski Triangle)
16.6 Suduko
16.7 Guidelines on Using Recursion
The script square (Fig. 16.1) creates a square of the desired size. When we
enter 20 as the size of the square, the square would appear as shown in Fig.
16.2.
Fig. 16.1 Program to plot a square (square.py)
Fig. 16.2 Square
Next, let us print squares within squares. Evidently, recursion would be our
natural choice to design such a function. However, before we develop the
recursive function, we need to do some housekeeping. In the script
squareRecur, we develop a separate function squareWrapper to do the
housekeeping work related to the main function square (Fig. 16.3). Such a
function is called a wrapper function. It accepts the size of the square as a
parameter, initializes the vectors x and y, invokes the recursive function
square, prints the title of the figure, fixes the axes, invokes the function
grid() to plot the grid, and finally invokes the method show() to show the
result. For every call to the function square, we decrease the size of the
square by two, thus, causing the square to shrink inwards. Finally, we
terminate the function square when the difference between adjacent
coordinates is less than one. When we enter 20 as the size of the square, the
square would appear as shown in Fig. 16.4.
squareWrapper: wrapper function for housekeeping work
in every recursive call to the function square, decrease square size by two
Fig. 16.3 Program to recursively plot square within a square (squareRecur.py)
Fig. 16.4 Squares within squares
The eight queens problem is the problem of placing eight queens on the
chessboard so that none can attach each other. A queen is attackable if
another queen lies in the same row, same column, or same diagonal (either
direction). In this problem, we need to find a solution in the form of a
placement of queens on the 8 × 8 chessboard so that each of the eight queens
is non-attackable (i.e. safe). We may begin as follows: initially, place a
queen at any place in the first row, and then successively choose the position
of the next queen on the subsequent rows in such a manner that chosen
square is unguarded, i.e. not attackable by any other queen. As we follow the
procedure just described, it is possible that we may get stuck on the way, as
there may be a row for which no position is a safe position. If this happens,
we backtrack one or more steps as required, to try another alternative.
place eight queens on the chessboard so that no one can attack any one
class Queens: used to modify and keep track of the current chessboard configuration
n = boardSize
print configuration
else
solveFrom(configuration)
1. __init__
This method creates an instance of class Queens and initializes the data
members boardSize, count (number of queens), and board.
2. getBoardSize
This method returns the size of the chess board.
3. __str__
This method returns string representation of object of type Queens.
4. unguarded
This method returns True, if the current chessboard square is unguarded,
and False otherwise. It checks whether a queen is guarding the current
square. As all the rows of the board having row number greater than the
row number of the current square are vacant (not yet occupied by a queen),
we only need to check whether a queen in the rows above the current
square is guarding the current square. This is accomplished by checking
upper parts of the column, left diagonal, and the right diagonal for the
current square. This approach is summarized below:
Execution of the script nQueens (Fig. 16.5) for 4-queens problem yields the
following chessboard configurations resulted as the output:
Enter board size: 4
4 -Queens Problem
Solution No. 1
- Q - -
- - - Q
Q - - -
- - Q -
Solution No. 2
- - Q -
Q - - -
- - - Q
- Q - -
Knight's tour: traversing the entire chessboard, without stepping over any square more than
once
two steps vertically upwards or downwards, followed by one step right or left
two steps horizontally right or left, followed by one step vertically upwards, or downwards
Thus, the knight may, possibly, jump to one of the eight square positions
described above. For example, in a 5 × 5 chessboard, if the knight is placed
at the centre, there are eight potential moves (Fig. 16.6). Obviously, the
number of choices for making a move is limited by a horse position on the
chessboard, for example, a horse placed on any of the four corners of the
chessboard has only two choices.
Note that the class Knight contains several data members and methods for
keeping track of the current chessboard configuration and carrying out
moves of the knight (Fig. 16.7). The data member board represents the
chessboard configuration of size boardSize. It keeps track of the history of
successive moves. It is initialized with value 0 to mark all chessboard
squares as untraversed.
Fig. 16.6 Possible moves of a knight
if board[x,y] == 0
else if board[x,y] =i
In summary, the class Knight supports the following methods for solving
Knight's Tour problem.
1. __init__
This method creates an instance of class Knight and initializes the data
members boardSize, moveNum (number of moves taken by the knight),
solNum (keeps track of the number of solutions explored), moves (stores all
possible moves possible from the current position), and board.
2. getBoardSize
This method returns the size of the chessboard.
3. __str__
This method returns a string representation of the object of type Knight.
4. possible
This method returns True or False depending on whether the move to a
given position in the chessboard is possible. It works in the following
manner:
if the position is a valid position on chessboard i.e. x and y
lie in the valid index range [0, boardSize-1], and the current
chessboard square is not traversed before
Return True to indicate that this move is possible
else
Return False to reject the move
5. add
The method assumes that the current chessboard square has not yet been
traversed by the knight. It places the knight at the given chessboard position
by marking it traversed, i.e. assigning it the current move number and
incrementing the moveNum by 1 to denote the number of moves taken so far.
7. moveFurther
This method determines next sequence of moves if the current
configuration is not yet complete. It works in the following manner:
if a solution to Knight's tour is found
print configuration
else
for every possible candidate move p from the current
position(x,y)
place the knight on square p of the current configuration.
try the next sequence of moves.
remove the knight from square p of current configuration.
8. isSolved
This method determines whether the current chessboard configuration is
complete, i.e. all the squares have been traversed. It works in the following
manner:
Determine the number of total moves in the current chessboard
configuration.
If the total number of moves equals boardSize*boardSize
return True
else
return False
Solution Number: 1
1 6 15 10 21
14 9 20 5 16
19 2 7 22 11
8 13 24 17 4
25 18 3 12 23
Solution Number: 2
1 6 11 18 21
12 17 20 5 10
7 2 15 22 19
16 13 24 9 4
25 8 3 14 23
Solution Number: 3
1 6 11 16 21
12 15 20 5 10
7 2 13 22 17
14 19 24 9 4
25 8 3 18 23
Solution Number: 4
1 6 17 12 21
16 11 20 5 18
7 2 9 22 13
10 15 24 19 4
25 8 3 14 23
Solution Number: 5
1 12 17 6 21
18 5 20 11 16
13 2 9 22 7
4 19 24 15 10
25 14 3 8 23
Solution Number: 6
1 16 11 6 21
10 5 20 15 12
17 2 13 22 7
4 9 24 19 14
25 18 3 8 23
Solution Number: 7
1 18 11 6 21
10 5 20 17 12
19 2 15 22 7
4 9 24 13 16
25 14 3 8 23
Solution Number: 8
1 10 15 6 21
16 5 20 9 14
11 2 7 22 19
4 17 24 13 8
25 12 3 18 23
Solution Number: 9
1 16 5 10 21
6 11 20 15 4
19 2 17 22 9
12 7 24 3 14
25 18 13 8 23
Solution Number: 10
1 12 5 18 21
6 17 20 13 4
11 2 9 22 19
16 7 24 3 14
25 10 15 8 23
In this problem, we deal with two groups of equal number of persons, one of
the men and the other of women. Each man gives his relative preference for
every woman from best to worst, and each woman gives her relative
preference for every man. Based on their preferences, we are required to find
a pairing between men and women. Further, the pairing should be stable in
the following sense: there are no two people of the opposite sex who would
both prefer to have each other than their current partners. For example, let M
= {m1, m2} and W = {w1, w2} be two sets of men and women,
respectively. Let us suppose m1 and m2 have an identical list of ordered
preferences of women [w1, w2], i.e. each of them prefers w1 over w2.
Further, let us suppose w1 and w2 also have an identical list of ordered
preferences of men [m1, m2], i.e. each of them prefers m1 over m2. Next,
suppose we do the following matching {{m1, w2}, {m2, w1}}. This
matching is not stable because m1 and w1 prefer each other over the
partners assigned to them. However, the matching {{m1, w1}, {m2, w2}} is
stable because there are no two persons of opposite sex that would prefer
each other over the partners assigned to them, for example, although m2
prefers w1 over w2, but w1 does not prefer m2 over m1.
notion of a stable marriage
The goal is to determine n pairs of <m, w> so that each pair represents a
stable marriage, i.e. there is no pair <m, w> of persons who would prefer
each other to their assigned partners. In other words, a pair <m, w> is
considered to be stable if the following two conditions hold:
1. Every women candidate who is preferred by man m to his current assignment w prefers her current
partner over the man m.
2. Every man candidate who is preferred by woman w to her current assignment m prefers his current
partner over the woman w.
engagedMen and engagedWomen: used to keep track of engaged men and women at any point in
time
else
Note that if for a given man m, if none of the women not yet engaged yields a
stable pairing, the control returns to the previous call and the matching for
the man m-1 is undone to try another alternative. This backtracking may
proceed up to man m = 1. Finally, the man m would be paired. Whenever all
the men have been matched, a stable marriage solution is printed.
1. __init__
This method creates an instance of class StableMarriage and initializes the
data members count, menPref, womenPref, freeWomen, engagedMen and
engagedWomen.
2. __str__
This method returns a string representation of the object of type
StableMarriage.
3. isStable
This method returns True or False depending on whether the pairing of
given man and woman under consideration indicates a stable marriage. It
works in the following manner:
1. For man m, all other women candidate who are preferred by man m to his current
assignment w, are already married and prefer their current partners over man m.
2. For woman w, all other men candidate who are preferred by woman w to her current
assignment m, are either yet not engaged or prefer their current partners over
woman w. (Candidate men who are not engaged yet are not considered till now).
4. free
This method sets free an engaged pair of man and woman. It achieves this
by adding the given woman to the list freeWomen who are not engaged. It
also updates dictionaries engagedMen and engagedWomen to reflect that they
are no longer engaged.
5. engage
This method engages the given man and woman by pairing them. It
achieves this by removing the given woman from the list freeWomen. It also
updates dictionaries engagedMen and engagedWomen to reflect that they are
engaged.
6. findMatching
This method finds stable matching for the given man.
Stable pairings:
{1: 2, 2: 3, 3: 1}
{1: 1, 2: 2, 3: 3}
{1: 3, 2: 1, 3: 2}
stable pairings
fractal: curve or a geometric figure which comprises a recursive pattern that repeats itself
turtle module: provides turtle graphics for drawing various shapes and pictures
1. forward(): Used for moving the turtle forward by a given distance in the direction of the turtle.
2. Backward(): Used for moving the turtle backward by a given distance in the direction of the turtle.
3. left(): Used for rotating the turtle in the left direction by a specified angle.
4. right(): Used for rotating the turtle in the right direction by a specified angle.
5. goto(): Used for moving the turtle to the location specified (x,y coordinates).
6. penup(): Used to specify no drawing while moving.
7. pendown(): Used to specify drawing while moving.
8. fillcolor(): Used to specify the colour to be filled in the shape. Colour specified could either be a
string or a tuple (r,g,b).
9. begin_fill(): Used just before drawing the shape to be filled.
10. end_fill(): Used to fill the shape drawn after last call to begin_fill().
11. done(): Completes the turtle graphics work.
Let us examine the Sierpinski Triangle first. The simplest Sierpinski triangle
is a triangle subdivided into nested equilateral triangles formed by bisecting
sides of the triangle having the central triangle removed. This results in an
outer triangle with three upward facing equilateral triangles on top, bottom
left and bottom right side with one downward facing triangle that is removed
from the centre. Each of the triangles facing upward may further contain
three nested equilateral triangles depending upon the level of depth.
Sierpinski triangles of levels 1, 2 and 3 are shown in Fig. 16.9. Next, we
describe the approach used for drawing Sierpinski triangle:
The triangle drawn as the part of the first statement in Sierpinski triangle can
be created using the following steps:
1. Specify the color to be filled in the closed object to be created, using fillcolor method.
2. Position the turtle to one of the end points of the triangle in pen-up mode so that there is no drawing
while moving.
3. Invoke method begin_fill before drawing the shape to be filled.
4. After successful positioning, create a triangle by traversing all its endpoints in the pen-down mode.
5. Invoke method end_fill after drawing the shape to be filled.
We may also set the speed of the turtle using function speed. Next, we
develop a program for drawing Hilbert curve. A Hilbert curve is a curve that
is formed by connecting a sequence of U-shaped curves oriented in different
directions. These U-shaped curves are placed at a certain step size distance
apart. Level 1 Hilbert curve is a simple U-curve that is formed by moving
down step size, then moving right step size, followed by moving up step size
as shown in Fig. 16.11. Level 2 Hilbert curve is formed by orienting level 1
Hilbert curve in different directions and connecting them. Thus, in general,
Hilbert curve of level n can be formed by orienting the Hilbert curve at level
n − 1 in different directions and connecting them.
Hilbert curve: curve formed by connecting a sequence of U-shaped curves oriented in different
directions
Let us examine Hilbert curve at level 1. Since turtle initially points towards
the right, the following steps will draw a simple U curve.
Next, let us examine level 2 Hilbert curve. Again, assuming that initially
turtle points towards the right, the following steps may be used to draw a
level 2 Hilbert curve:
Thus, Hilbert curve of any level n greater than zero with given degree y can
be drawn using the following steps:
16.6 SUDOKU
challenge: assign digits 1 to 9 without repetition in each of the blocks of size 3 × 3 within the 9
× 9 grid
else,
find a target index (i,j) on the grid with value 0.
On executing the script sudoku (Fig. 16.14) with the following input,
Enter the list (0 for missing values): [[5, 3, 0, 0, 7, 0, 0, 0,
0], [6, 0, 0, 1, 9, 5, 0, 0, 0], [0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3], [4, 0, 0, 8, 0, 3, 0, 0, 1], [7, 0,
0, 0, 2, 0, 0, 0, 6], [0, 6, 0, 0, 0, 0, 2, 8, 0], [0, 0, 0, 4,
1, 9, 0, 0, 5], [0, 0, 0, 0, 8, 0, 0, 7, 9]]
[6, 7, 2, 1, 9, 5, 3, 4, 8]
[1, 9, 8, 3, 4, 2, 5, 6, 7]
[8, 5, 9, 7, 6, 1, 4, 2, 3]
[4, 2, 6, 8, 5, 3, 7, 9, 1]
[7, 1, 3, 9, 2, 4, 8, 5, 6]
[9, 6, 1, 5, 3, 7, 2, 8, 4]
[2, 8, 7, 4, 1, 9, 6, 3, 5]
[3, 4, 5, 2, 8, 6, 1, 7, 9]
SUMMARY
EXERCISES
3. Write a recursive function for Tug of war problem. The function should take a list of n integers and
should divide the elements into two lists of n/2 sizes so that the absolute difference between the sum
of elements of the two lists is the minimum possible.
4. Write a recursive function that draws order n Koch fractal curve (Fig. 16.15).
5. Write a program to solve Stable Matching Problem. Given, n (even) individuals and their ordered
preference list for their room partner, the problem is to divide them into n/2 stable pairs based on their
preferences. Further, the pairing should be stable in the following sense: there are no two persons (not
forming a pair) both of whom would prefer each other than their current partners.
6. Write a program that takes a matrix (list of lists) of 0’s and 1’s as an input from the user and invokes a
recursive function which returns the maximum length of connected cells having value 1. The two cells
are said to be connected if they are adjacent to each other, horizontally, vertically, or diagonally.
CHAPTER 17
GRAPHICS
CHAPTER OUTLINE
17.1 2D Graphics
17.2 3D Graphics
17.3 Animation – Bouncing Ball
17.1 2D GRAPHICS
python get-pip.py
pyplot module: contains functions for plotting figures and setting various properties
plt.plot(3, 2)
plt.show()
plotting a point
The function show is used for displaying the figure. Once the function show
is executed, the system waits for us to have a look at the graph, and
execution of other instructions is blocked until the graphical window is
closed. Hence, the function show is called a blocking function. When we
wish to continue the execution of other statements, without closing the
window manually, we specify block = False as an argument while
invoking the function show. Note that the first line introduces plt as an
alternative name of the module matplotlib.pyplot.
Fig. 17.1 Function plot(3, 2) to display point (3, 2) (see page 583 for the colour image)
Let us plot the point (3, 2) as a circular red-colored point (Fig. 17.2) as
follows:
plt.plot(3, 2, 'ro')
interactive buttons on the bottom panel for manipulating current view of the figure
Fig. 17.2 Point (3, 2) (see page 583 for the colour image)
Note that Fig. 17.2 has several interactive buttons on the bottom panel that
help in manipulating the current view of the figure. The first button is called
the home button and is used to reset original view of the figure. The fourth
button is used for controlling the axis by panning the axis with the left
button of mouse and zooming with the right button of the mouse. We may
also zoom in the rectangular portion of the current view of the figure using
the fifth button. In the case of multiple sub-plots, we may configure them
with the sixth button. At any point in time, we may revert to previous view
or next view using second and third button respectively. The seventh button
is used for saving the figure in the desired directory.
At times, we may be interested in plotting several points on the graph. For
example, suppose we wish to plot five points: (2,3), (4,5), (6,7), (8,9),
(10,11). We construct two lists: x and y — the list x comprising x-
coordinates of all the points, and the list y comprising y-coordinates of the
corresponding points. As each point comprises an x-coordinate and a y-
coordinate, both lists have the same length. Now we are ready to call the
plot function with arguments x, y, and 'ro'. The resulting graph is shown
in Fig. 17.3.
import matplotlib.pyplot as plt
x = [2, 4, 6, 8, 10]
y = [3, 5, 7, 9, 11]
plt.plot(x,y, 'ro')
plt.show()
Note that the system displays a solid line in blue color. These are default
options for line style and color. Thus, default format string is 'b-'. We may
choose any of the four line styles that appear in Table 17.3. Color options
have already been described in Table 17.1.
Next, we display a line comprising dashes and asterisks (in red color) (Fig.
17.5).
x = [2, 4, 6, 8, 10]
y = [3, 5, 7, 9, 11]
plt.plot(x, y, 'r*--')
plt.show()
The function plot supports several properties that may be set as per the user
preferences such as markerfacecolor, markersize (decimal value),
markeredgecolor, markeredgewidth (decimal value), linestyle and
linewidth (decimal value). For example, to set the width of the line as 2.2
and size of the marker as 10.5, we use the following call to plot function
(Fig. 17.7):
Fig. 17.6 Solid line joining points defined by vectors [0, 1, 2, 3, 4] and y (see page 583 for the colour
image)
For example, we redraw Fig. 17.7 by setting the axis parameters (Fig. 17.8):
x = [2, 4, 6, 8, 10]
y = [3, 5, 7, 9, 11]
plt.show()
Fig. 17.8 Line joining points specified by vectors x and y (see page 584 for the colour image)
To make the graph easy to understand, we label the axes and assign a title to
the graph. Functions xlabel, ylabel, and title may be used for this
purpose, as illustrated below:
plt.xlabel('X')
plt.ylabel('X * X')
plt.title('X vs X * X')
displaying a grid
.
plot (Xn, Yn, LineSpecn)
Fig. 17.9 Line joining points specified by vectors x and y (see page 584 for the colour image)
For example, let us plot functions f(x) = x2 and f(x) = x3 in the same figure in
the interval [a,b] in steps of step. When we display more than one graph in
the same figure, we need a mechanism to distinguish between them. For this
purpose, we make use of different colors, width, and style, or a combination
of these as illustrated in the function plotFunctions (Fig. 17.10). In the
script plotLines1, we have chosen colors red and blue for plotting the
functions x**2 and x**3 respectively. Legends associated with different plot
functions are specified using the keyword label while invoking the plot
function (lines 13 and 14). Finally, we invoke function legend for displaying
the legends for the two functions being plotted (line 15).
keyword label is used for specifying legend
Fig. 17.10 Program to plot functions f(x) = x2 and f(x) = x3 on the graph (plotLines1.py)
On executing the script plotLines1 (Fig. 17.10), the user is asked to enter
the range parameters and the step size:
Enter first element of the range: 2.5
On entering the range parameters 2.5 and 4.5, Python responds with Fig.
17.11.
Multiple Plots
Suppose we wish to plot several functions, each in a separate graph, but in
the same figure. The function subplot described below may be used for this
purpose.
Fig. 17.11 Functions f(x) = x2 and f(x) = x3 plotted in the interval [2.5, 4.5] in steps of 0.1 (see page
584 for the colour image)
The function takes three arguments, the number of rows, the number of
columns, and the figure number. Instead of a comma-separated sequence of
parameters, we may specify an ordered sequence of these values, for
example, we may use either of the function calls subplot(1, 2, 1) and
subplot(121). In the script plotLines2 (Fig. 17.12), we plot six functions
f(x) = x, f(x) = x , f(x) = x , f(x) = x , f(x) = x , and f(x) = x
2 3 4 5 6
as six different graphs (two rows and three columns) but in the same figure
(Fig. 17.13). Note that the call to the function plot in line 20 plots the graph
in the subplot mentioned in line 19. On executing the script plotLines2
(Fig. 17.12), Python prompts the user to enter the list x to be plotted:
Fig. 17.12 Program to plot six functions on different subgraphs in the same figure (plotLines2.py)
On providing the input range(1,15), Python outputs Fig. 17.13. All the list
sequences that are provided to functions of matlplotlib.pyplot are
internally converted to numpy arrays (homogeneous multidimensional
arrays). Also, to add sufficient spacing between subplots so that they do not
overlap, function tight_layout has been invoked in line 61.
future reference, thus, avoiding the need to re-run the code every time such a
figure is needed. To save a graph in the current directory, we use the
function savefig, for example,
x = range(0,5)
y = [i**2 for i in x]
plt.savefig('xSquare')
Fig. 17.13 Six functions plotted on different subgraphs in same figure (see page 585 for the colour
image)
By default, the method hist assumes the maximum number of bins to be 10.
If we wish to have more than 10 bins, we need to set the number of bins to
the desired value explicitly, say n, using keyword argument bins = n along
with input data. Also, as the bins of the histogram are not centred around
values (Fig. 17.15), we may prefer to specify the range (boundaries) for each
bin of the histogram. For example, the following statement defines the bins
with boundaries 0.5, 1.5, 2.5, 3.5, 4.5, 5.5, and 6.5 which creates six bins as
[0.5,1.5), [1.5,2.5), [2.5,3.5), [3.5,4.5), [4.5,5.5), and [5.5,6.5].
Fig. 17.14 Program to plot histogram (histogram.py)
Fig. 17.15 Histogram (see page 585 for the colour image)
range(0,max(data)+2)])
pie(): to create a pie chart for the given sequence of data node
autopct: keyword argument to specify the percent area covered by each wedge
On executing the script piechart (Fig. 17.17), Python prompted with
following inputs and displayed pie chart as shown in Fig. 17.18.
Fig. 17.20 Sine and cosine curve (see page 586 for the colour image)
17.1.4 Graphical Objects: Circle, Ellipse, Rectangle, Polygon, and Arrow
To support the classes such as Rectangle, Circle, Ellipse,
RegularPolygon, Polygon, CirclePolygon, Rectangle, Arrow, and
FancyArrow, matplotlib library provides patches module. Consequently,
the graphical shapes such as rectangle, circle, ellipse, regular polygon,
polygon, circle polygon, rectangle, arrow, and fancy arrow are called
patches. All these classes are sub-classes of the class Patch which further
inherits from the class Artist of the module artist.
Circle
Creating an instance of the class Circle requires a tuple (x, y) denoting the
centre of the circle and an optional value for the parameter radius (default
5). Further, we may set different properties of the class Patch while
instantiating the class Circle. In the script circle (Fig. 17.21), we draw a
circle on the plot area. The circle is centred at (0, 0) and has the user-
specified radius. Further, facecolor, edgecolor, linestyle, and
linewidth have been set to green, red, dotted, and 2.2, respectively.
Fig. 17.22 Circle (see page 586 for the colour image)
Ellipse
Creating an instance of the Ellipse class takes width and height as the
required attributes and an optional value for the parameter angle (default
0.0) denoting rotation in degrees (anti-clockwise). As usual, we may set
different properties of the class Patch while instantiating the class Ellipse.
In the script ellipse (Fig. 17.23), we draw an ellipse on the plot area. The
ellipse is centred at (0, 0) and has user-specified width and height. Further,
fc, ec, linestyle, and lw have been set to cyan, red, dashed, and 2.2,
respectively.
Fig. 17.24 Ellipse (see page 586 for the colour image)
Rectangle
For creating an instance of Rectangle class, we specify width and height as
the required attributes. We may also specify the optional parameter angle
(default 0.0) denoting rotation in degrees (anti-clockwise). In the script
rectangle (Fig. 17.25), we draw a rectangle on the plot area. The rectangle
is centred at (0, 0) with user-specified length and breadth. As usual, we set
some of the properties of the class Patch while instantiating the class
Rectangle. Default values are used for other properties.
Fig. 17.26 Rectangle (see page 587 for the colour image)
Polygon
Creating an instance of Polygon class requires a list (vector) of points. Each
point in the list denotes one of the endpoints of the line segments of the
polygon. As usual, we may set different properties of the class Patch while
instantiating the class Polygon. In the script polygon (Fig. 17.27), we draw a
polygon on the plot area that joins the user-specified points having ec,
linestyle, and lw set to red, dashdot, and 4, respectively.
On executing the script polygon (Fig. 17.27), Python prompts the user to
enter the list of endpoints of a polygon. On entering the input [[2.5,4],
[2,6], [4,8], [6,6], [5.5,4]], a polygon is displayed (Fig. 17.28).
Enter the points: [[2.5,4], [2,6], [4,8], [6,6], [5.5,4]]
Arrow
Creating an instance of Arrow class requires attributes x, y, dx, and dy.
Whereas (x, y) denotes the starting point (base) of the arrow, and (dx, dy)
defines the the position of the head of the arrow relative to its base. As
usual, we may set different properties of the class Patch while instantiating
the class Arrow. In the script arrow (Fig. 17.29), we draw an arrow that
begins from a user specified position (x, y) having coordinates of head of
the arrow as (x + dx, y + dy). We set the fill property to False so that
the arrow is not filled with any color. Also, we set the hatch property to
value 'O' so that the arrow is filled with Os.
17.2 3D OBJECTS
Box
A box may be drawn by creating an instance of class box. While creating an
instance of box class, we may specify attributes listed in Table 17.6.
box: the class used to create a box
Sphere
A sphere may be drawn by creating an instance of the class sphere as shown
below:
sphere()
Fig. 17.32 Sphere (see page 587 for the colour image)
materials.rough)
Ring
A ring can be drawn by creating an instance of the class ring. While creating
an instance of ring class, we may specify attributes listed in Table 17.8.
ring(axis=(0.5,0,0.9), radius=0.5,\
thickness=0.15)
Fig. 17.33 Ring (see page 587 for the colour image)
Cylinder
Graphical object cylinder can be drawn by creating an instance of the class
cylinder. While creating an instance of cylinder class, we may specify
attributes listed in Table 17.9.
cylinder: the class used to draw a cylinder
Fig. 17.34 Cylinder (see page 587 for the colour image)
Arrow
An arrow can be drawn by creating an instance of the class arrow. While
creating an instance of arrow class, we may specify attributes listed in Table
17.10.
up = (0,10,20))
Fig. 17.35 Arrow (see page 588 for the colour image)
Cone
A cone can be drawn by creating an instance of the class cone. While
creating an instance of cone class, we may specify attributes listed in Table
17.11.
cone(pos=(0,-2,0), axis=(0,4,0),radius=2)
Fig. 17.36 Cone (see page 588 for the colour image)
Curve
An object curve can be drawn by creating an instance of the class curve.
While creating an instance of curve class, we may specify attributes listed in
Table 17.12.
curve(pos=[(-2,-2,0),(-2,0,1),(0,0,0), (3,0,0),\
In lines 2 and 4 (Fig. 17.38), we create a base ground using a box object
and a ball using sphere object and define their attributes. The center point
of the visual display window is positioned at (0, 5, 5) (lines 6). The ball is
projected with an initial velocity 10 unit/sec in the direction of y-axis, and
the coefficient of restitution is 0.9 (line 7 and 8). Change in time dt is set to
0.01 sec (line 9). The while loop produces a bouncing ball animation.
Function rate defines a maximum number of loops per second. The position
of the bouncing ball in each iteration is updated using current velocity and
time. If the current position of the ball is less than the radius of the ball, it
touches the floor. In this case, the velocity of the ball is negated changing the
direction of motion and its position is set to coordinates (0,1,0). Also,
velocity is updated using the formula v = u + a*t. Note that bouncing ball
animation lasts until the position of the ball becomes static i.e. there is no
change in the position of the ball in successive iterations (line 17). Also, we
may set the visual display window to full-screen by using the following
command immediately after importing the module visual:
scene.fullscreen = True
Fig. 17.38 Program to create a bouncing ball (bouncingBall.py)
Fig. 17.39 Snapshots of bouncing ball (see page 588 for the colour image)
SUMMARY
1. Python library matplotlib provides several methods that facilitate us to draw graphical objects
including point, line, circle, rectangle, oval, and polygon. The library also supports objects like
graphs, histograms, bar charts, pie charts, scatter plots, and error charts.
2. pyplot module of matplotlib contains several functions for plotting, and modifying or setting
various properties such as the layout of the plot area, labels, and attributes of the figure.
3. The function plot of pyplot module may used for plotting as follows:
plot (x, y, LineSpecification)
4. The function show of pyplot module is used for displaying the figure.
5. The function axis of pyplot module is used for setting axis parameters x , x , y and y .
min max min max
6. The functions title, xlabel, and ylabel of pyplot module are used for setting title and labelling
axes.
7. The function subplot of pyplot module is used for plotting several functions, each in a separate
graph, but in the same figure. The function takes three arguments, the number of rows, the number of
columns, and the figure number.
8. The function savefig of pyplot module is used to save a graph.
9. The function hist of pyplot module is used for plotting a histogram for the given data set.
10. The function pie of pyplot module is used for creating a pie chart for a given sequence of data.
11. In matplotlib terminology, the graphical shapes such as a circle, rectangle, polygon, and ellipse are
known as patches. The module patch supports classes such as Rectangle, Circle, Ellipse,
RegularPolygon, Polygon, CirclePolygon, Rectangle, Arrow, and FancyArrow.
12. Visual Python has visual module that supports 3D graphics and animation. It contains several classes
such box, sphere, cone, cylinder, arrow, ring, pyramid, ellipsoid, and helix that facilitate us to
draw various 3D graphical objects.
EXERCISES
1. Write a program that plots graphs corresponding to the following equations by taking suitable lists as
an input from the user:
1. y = 3x2 + 4x + 2 (y vs. x)
2. v = u + at (v vs. t)
3. F = ma (F vs. m)
2. Write a program that plots the following functions in the range 0° to 360° in the same figure:
1. tan
2. cot
3. sec
4. cosec
3. Write a program that illustrates superposition of two waves of the same amplitude.
4. Write a program that shows the moving car.
5. Write a program that shows the motion of a rocket.
CHAPTER 18
APPLICATIONS OF PHYTHON
CHAPTER OUTLINE
18.1 Collecting Information from Twitter
18.2 Sharing Data Using Sockets
18.3 Managing Database Using Structured Query Language
18.4 Developing Mobile Application for Android
18.5 Integrating Java with Python
18.6 Python Chat Application Using Kivy and Socket Programming
Python has emerged as a preferred choice for programming in almost every application area
Often we are interested to know the current trend, i.e., to find the ongoing
activity about an event, place, or person. Twitter is one such source of
information about almost everything happening in the world. Indeed, Twitter
has emerged as a popular social networking site, and people use it to air their
views and increase their awareness. Because of the millions of active users
sharing the latest updates, a lot of interesting data can be collected from
Twitter. Twitter can also be used to retrieve information about the tweets,
connections, or followers of a user, or topics trending on Twitter.
In this section, we will build a simple crawler that searches and collects
Twitter data in real time. So we will be using streaming APIs. An API
request on Twitter is first authenticated using Open Authentication (OAuth).
OAuth allows the users to connect to Twitter and send authorized Twitter
API request. Every registered application (consumer) of Twitter is assigned
a Consumer Key (API Key) and Consumer Secret ( API Secret) using which
the applications can authenticate themselves. Twitter verifies the user’s
identity and assigns PIN (OAuth verifier) that will be required by the
application to request Access Token and Access Secret to be used in an
application for invoking API calls. The Access Token and Access Secret pair
uniquely identify a user.
For Open Authentication, we need to follow the steps given in Fig. 18.1.
get-pip.py>
python get-pip.py
installing pip
Alternatively, we may open and execute the script get-pip.py from Python
IDLE. Also, the environment path for system variable should be updated to
include C:\Python27\Scripts.
Open Authentication
Accessing Twitter data requires open authentication of the application. In the
script TwitterOAuth (Fig. 18.2), we aim at authorizing a Python application
to access Twitter. The function OAuthVerifier is used for doing so. It first
initializes the variables consumerKey, consumerSecret, accessToken, and
accessSecret (lines 9, 10, 12, and 13). Execution of line 11 creates an
OAuthHandler object for using API key and API secret. The accessToken
and accessSecret are set for this object using the method
set_access_token. The authentication handler, that we just obtained, can be
passed as a parameter to class API of the tweepy module (a wrapper for API
as provided by Twitter). An object of this class (api) can be used for
retrieving user information such as his/her followers, friends, and tweets.
Note that the keys used in the program are only for illustration purpose;
however, the user is expected to generate the keys himself and replace them
appropriately in the given code.
The user method me (line 32) of the api returns authenticated user
information. Another user method get_user returns information about the
particular user, whose id/screen name is taken as input in line 35. We define
a function getUserStatistics for accessing and printing the user
information. Table 18.1 lists variables associated with user object that may
be accessed for information.
Table 18.1 Variables associated with user object
On executing the script TwitterUserInfo1 (Fig. 18.3), Python responds
with the following output:
>>>
ID: 727494459118653446
Location: India
No. of followers: 3
No. of friends: 34
No. of favorite tweets: 0
ID: 135421739
No. of friends: 79
Followers:
PeaceAlwaysPARI
ikindlebook
gauravparashari
followers
Friends:
gvanrossum
iamsrk_sharukh
DataSciFact
CompSciFact
Delhi_U
htTweets
ndtv
timesofindia
EconomicTimes
msdhoni
BeingSalmanKhan
SrBachchan
imVkohli
sachin_rt
PythonHub
PythonStack
pycoders
pythoncoders
djangoproject
ThePSF
friends
Tweets:
tweets
Often two processes need to communicate with each other for sharing data.
These processes may reside either on the same machine or on different
machines connected to a network. The two processes involved in this
interprocess communication are typically the client and the server
applications. The client application requests data and the server application
responds by fulfilling the request. The client-server architecture allows two
remote entities to communicate. For this purpose, HTTP is often used in
Internet applications as shown in Fig. 18.7.
sharing data across applications: processes need to communicate with each other
The first two parameters specify the domain, i.e., family of the protocol,
such as AF_INET, AF_INET6, and AF_UNIX, and the type of socket to be
created such as stream socket (SOCK_STREAM) for connection-oriented
protocol and datagram socket (SOCK_DGRAM) for the connectionless protocol.
The third parameter is a default parameter, which specifies a particular
variant of protocol within given domain and socket type. The socket object
mySock created above is a unique socket identifier which is used for
communicating with other process.
Table 18.2 Server socket methods associated with socket object mySock
Table 18.3 Client socket methods associated with socket object mySock
1. SERVER: On creating the socket, the server must bind it to the particular port number on the local
address, specifying the application that will listen to the incoming client requests. The method bind of
the socket class takes a tuple comprising local address as the first parameter, and port number as the
second parameter. Here, hostname and IP address are used as aliases. Since all ports below 1024 are
reserved, we may use a port number between 1025 and 65535, both included. We may identify the
ports already in use by executing the command (at command prompt): netstat –a.
2. SERVER: Once the server is bound to a socket, it must be ready to service requests from the client.
The server listens for incoming connections from the clients using the method listen. This method
takes the maximum number of connections allowed to be queued as the input parameter.
listen(): listens for incoming connections from the client on the socket
3. SERVER: The server waits in a loop indefinitely until the client connects to the port to which server
has bound itself. While listening on the socket, if a connection request from a client arrives, the server
needs to accept it. The method accept gets the pending connection from the connection queue, and
returns (i) the socket object for the client to be used for data transfer (ii) the address of the client
(destination IP address and port number).
4. CLIENT: Once the socket is created at the client end, we may use it to establish the connection
between the client (our Python program) and the application running on the server by specifying the
host name and the port number. The method connect of the socket module is used for this purpose. It
requires a tuple comprising the name of the host and the destination port number listening to a client
request.
5. Now the client and the server may exchange the data using send and recv methods. Since the client
and server can understand a bytes-like object, we use encode function to covert a string into bytes
object. By default, encode function uses utf-8 encoding scheme. Subsequently, the encoded bytes
object is converted to a string using decode function.
send() and recv(): to send and receive bytes-like object to and from the socket
6. Finally, the client and the server close the socket using the close method.
F:\PythonCode\Ch18>python client.py
F:\PythonCode\Ch18>
Note that an unused port is randomly chosen for the client process.
An Echo Server
Next, we develop an echo application, in which the server program (Fig.
18.12) echoes the data sent by a client application (Fig. 18.11) running on a
different system. So, in this case, the client invokes send method to send the
data to the server. Subsequently, the server receives the data using recv
method. The data received is echoed back to the client using send method.
The client then receives it using recv method. The procedure continues as
long as client provides the input data to be sent to echo server. Since the
client and the server reside on two different systems in the network, client
and server host names will be different.
Hello
I love Python
F:\PythonCode\Ch18>
http://marvin.cs.uidaho.edu/Teaching/CS515/pythonTutorial.pdf
The data received from this socket can be written to another pdf file on the
system. The data will be received and written to the file as long as the entire
content of the file is not transferred (Fig. 18.13). Note that we open the new
file PythonGuidoVanRossum.pdf in 'wb' (write, binary) mode (line 10) since
pdf files are binary files.
conn = sqlite3.connect('COLLEGE.db')
cur = conn.cursor()
conn.close()
The method execute of the cursor object is used for executing SQL
commands. However, the method can be used for executing only one SQL
command at a time. If one wishes to execute multiple SQL commands, the
method executescript may be used. The method execute allows the use of
several parameters discussed in subsequent sections.
.
table_constraints]
);
Since each student has a unique roll number, no two students can have the
same value of the attribute RollNum. So, RollNum must be unique across all
tuples of STUDENT table. As we would like to use RollNum to identify a
student uniquely, this attribute cannot be NULL. So, we apply column
constraints UNIQUE and NOT NULL to the attribute RollNum. The attribute
RollNum has been declared primary key of the table in the last line of CREATE
TABLE command. Also, RollNum being the primary key, column constraints
UNIQUE and NOT NULL automatically hold for it, and thus, do not need to be
mentioned explicitly.
If the primary key comprises a single attribute, we may include the phrase
PRIMARY KEY while defining the attribute in the CREATE command, as shown
below:
CREATE TABLE STUDENT(
);
SQLite does not enforce strict type requirement. To ensure strict type
conformity, CHECK constraint must be associated with an attribute.
);
Given the name of a table and associated attribute values in the form a tuple,
INSERT command inserts a tuple in the table. The order of values within the
tuple should correspond to the order of the attributes of the table. The
character and date type values should be enclosed in single quotes. When the
value of an attribute is not known/missing/not applicable for a tuple, we use
the NULL value. For example, suppose we wish to insert information about a
Student having RollNum 1, Name Hiten, and Percentage 89. To do this,
we may use the following INSERT command:
INSERT INTO STUDENT
In the script SQLCommands (Fig. 18.16), we insert five rows in the table
STUDENT.
Fig. 18.16 Inserting data in STUDENT table (SQLCommands.py)
In sqlite3, commit method associated with the object connect is used for
forcefully saving the current state of the database, thus making the changes
permanent. For example, in the script SQLCommands (Fig. 18.16), commit
method is executed after inserting the five tuples in the table. This ensures
that the tuples just inserted in the table STUDENT of the database become
immediately visible to other connections to this database.
Next, we present another format for inserting a tuple into a table using a
question mark. For example, we may add a tuple in the table STUDENT using
the question mark as a placeholder for the data being provided as the second
argument to method execute:
FROM relation_list;
FROM STUDENT;
In the above command, first line comprising of keyword SELECT along with
a list of attributes RollNum, Name, Percentage is called SELECT clause, and
the second line is called FROM clause. On executing the above command,
SQL will respond with the relation given in Table 18.6.
FROM STUDENT;
*: wild card character, used in an SQL command as a substitute for all the attributes occurring
in the relation(s)
Next, suppose that we wish to list only roll numbers and names of the
students in the college. For this purpose, we need to specify in the SELECT
clause, the relevant attributes RollNum and Name of the relation STUDENT, as
shown below:
SELECT RollNum, Name
FROM STUDENT;
Next, suppose we wish to retrieve information about students who have
secured percentage more than 80. WHERE clause in an SQL query facilitates
retrieval of only those tuples which satisfy a condition such as Percentage
> 80. Thus, the following SQL query would retrieve the desired
information:
SELECT *
FROM STUDENT
FROM relation_list
WHERE condition_list;
The result returned by an SQL query may be accessed using the method
fetchall that returns a list of tuples (line 6, Fig. 18.17). Alternatively, we
may retrieve the data from the database row by row by iterating through the
cursor object as shown below:
print(row)
The method execute also allows the use of named placeholders for SQL
literals. For example, the query
cur.execute('SELECT * FROM STUDENT WHERE Percentage > 80;')
In the above query, the method execute makes use of the name value as a
placeholder for the actual data 80 that appears as the second argument.
UPDATE relation
SET attribute-value_pairs
[WHERE condition_list1];
In the UPDATE command, SET clause may take any number of comma-
separated attributes and their updated values. In a Python program, the
following statements can be used for updating data:
cur.execute('UPDATE STUDENT \
[WHERE condition_list1];
Suppose a student with roll number 3 has left the college. We may delete the
information about that student using the following SQL command:
DELETE FROM STUDENT
WHERE RollNum = 3;
The command
DELETE FROM STUDENT;
deleting entire data from the table
will delete the entire data from the table STUDENT. If we wish to delete the
table itself along with all its tuples, we may use the DROP TABLE command.
For example, the following SQL command will delete the entire table
STUDENT:
In this section, we will study how Python can be used for creating
applications for android. For illustrating this, we will develop the popular
two-player game Tic-Tac-Toe, also known as the game of Xs and Os. In this
game, the player who successfully places three consecutive symbols
horizontally, vertically or diagonally wins the game. For developing the
game, we will first create a cross-platform application of the game that can
be executed on the Android device. Before developing this game, we will
create a registration interface for the user.
kivy installation
Finally, for installing kivy package, download the nightly wheel from the
link https://kivy.org/downloads/appveyor/kivy/Kivy-1.9.2.dev0-cp36-
cp36m-win32.whl and install it using the following command (the file just
downloaded from kivy.org should be available in the working directory and
needs to be moved to working directory, if downloaded in a different folder):
python -m pip install Kivy-1.9.2.dev0-cp36-cp36m-win32.whl
On executing the script main (Fig. 18.19), Python responds with the
following output shown in Fig. 18.20. Left window of the figure displays the
button when the application starts. Right window displays the button when it
is pressed.
Another approach for using widgets and their definitions is to use separate
files for specifying them (Fig. 18.21). Note that the widget definition is
stored in a separate file having .kv as a suffix. The .kv file is named after
the main app class containing build method. While name of a class may
include uppercase letters, to name the .kv file, we use the same name as that
of the class, but in lowercase letters and drop the suffix App, if included in
the name of the class. The file contains the colon-separated properties and
their values for each widget. Also, the root widget is enclosed in angular
brackets followed by a colon.
On executing the script in Fig. 18.23, Python responds with the output given
in Fig. 18.24. Left window (Fig. 18.24(a)) displays a user interface for
registration, and the right window (Fig. 18.24 (b)) shows popup window
which appears when Register button is clicked.
Fig. 18.24 Output of program 18.23
a user click invokes the method action which sets the symbol on the grid and checks for the
winner
title=<Application Title>
author=<Your Name>
orientation=<portrait|landscape>
Next, go to Kivy Launcher and choose the project you wish to execute.
We will make use of py4j for invoking Java functionality from Python. It
can be installed by executing the following command from command line:
for communication to take place, Java program must be compiled and executed before the
Python program
The script hello.py (Fig. 18.30) uses the Java program that we discussed
above. For this purpose, we need to create an instance of the class
JavaGateway available in the module py4j.java_gateway. The first two
lines of the Python script hello achieve this. When we invoke JavaGateway
(line 2), Python tries to connect with JVM of Java program already running
and returns an instance. We can access the entry point object using the
member entry_point (line 3). This object now enables us to use Java
functionality in the Python program (line 4). However, if no JVM is waiting
for a connection, an error message Py4JNetworkError is displayed.
Fig. 18.30 Python applications that uses a method of java program (hello.py)
On running the script hello (Fig. 18.30), Python outputs Hello. If the error
message address already in use appear while running the Java program, we
need to explicitly specify a new port number (between 1025 and 65535) in
each of the Java and Python programs. For example, in the Java program
HelloClass (Fig. 18.29), we may replace line 10 by:
and in the Python script hello (Fig. 18.30), we replace line 2 by:
gateway =
JavaGateway(gateway_parameters=GatewayParameters(port=25539))
@echo off
batch file
Note that the second and third commands in the above sequence, i.e.,
java -jar <CompletePath>\DemoProject.jar
and
Python <CompletePath>\hello.py
gateway = JavaGateway()
intArray = gateway.new_array(gateway.jvm.int,2)
intArray[0] = 0
intArray[1] = 1
print(value)
On executing the above Python code (after starting Java Gateway Server),
Python responds with the following output:
0
Similarly, we can also create a Java list using the gateway object.
Subsequently, we may add elements to that list, either by using append
method of Python list or by using add method of Java as shown below:
creating a Java list in Python
Python responds with the following output on the execution of above piece
of code:
['red', 3]
use of convert method of List-Converter class for converting Python list to Java list
Fig. 18.31 Sorting python list using Java method sort (SortPythonList1.py)
Note that javaList obtained from pythonList is sorted using Java method
sort (line 7). Python responds with the following output on the execution of
the program SortPythonList1.py (Fig. 18.31):
[2, 3, 1] [1, 2, 3]
Fig. 18.33 Java Program which modifies elements of the list received as parameter
(ListManipulation.java)
To make methods of the class ListManipulation accessible in a Python
program, it must be compiled and executed before execution of Python
program. Examine the Python script in Fig. 18.34 that uses this Java
program. In lines 2 and 3, we have created an instance of class JavaGateway
available in module py4j.java_gateway. Entry point object is used for
accessing Update method by passing pythonList as an input argument. Note
that the input argument is not converted to Java compatible type explicitly.
Instead, we have set gateway parameter auto_convert which automatically
achieves this.
Fig. 18.34 Python applications that uses the method Update from Java program (ListManipulation.py)
As shown in the program List (Fig. 18.36), object lst passed via Python
program is received as object op in Java method ListOperation of class
List (line 5). Note that, for every Python method, an interface method
should be defined in Java. In Fig. 18.37, we have defined an interface
ListManipulationInterface which declares the method Update.
On running the Java program followed by Python script, Java responds with
the following output:
Updated List:
2 4 6
In this section, we will build a chat application that allows two parties to
communicate with each other via type and send chat interface. We have used
kivy library to create a chat interface, one for each communicating party.
The interface comprises a textbox named ChatBox where chat logs are
displayed, an entry text box named EntryBox to type a message to be sent,
and a button named SendButton to send the message. Note that each widget
can be assigned a name identifier using id property and referenced in the
program using dictionary ids maintained by the root widget that comprises
all widgets having an id attribute. We present the widget definitions in the
file chatappinterface.kv file (Fig. 18.38).
In the scripts host (Fig. 18.39) and client (Fig. 18.40), we have defined the
respective chat application. The host program will initiate the
communication by listening to request, and the client will connect to the host
waiting for a connection and communicate with it. A message typed by
either party will be displayed in its own ChatBox as well as the ChatBox of
another communicating party. Thus, we need to perform the two tasks for
each application: the first task takes the user input through EntryBox and
displays it in his/her own ChatBox, and the second task sends the input to
the connected party. Further, the chat application running at each end should
be ready to receive a message sent by another party for displaying it in the
ChatBox. Former functionality is performed by the clickAction method
associated with the widget SendButton. The latter functionality is performed
by getHostConnected and getClientConnected methods of the host and the
client respectively. For this purpose, we create a separate thread by using the
method start_new_thread of the module _thread which takes the method
to be executed as the first parameter and a list of arguments to be sent to the
method as the second parameter.
the chat applications at the two ends send and receive messages at their own pace
Fig. 18.39 Host application (host.py)
Fig. 18.40 Client application (client.py)
In Fig. 18.41, we show the output of a sample chat session when the host
application is run, followed by the client application.
SUMMARY
EXERCISES
1. Write a program that takes a user handler as an input and extracts all tweets posted by him.
2. Write a program that extracts all tweets tweeted in the past five days regarding India’s economy. Use
the appropriate list of search words.
3. Write a socket programming application for transferring files across the networks.
4. Write a program that provides functionality for managing information about the college in the
database COLLEGE. The database should contain relations for storing information about entities such
as students, teachers, courses, and departments.
5. Develop a kivy application for Tic-Tac-Toe game with a grid of size 4 × 4.
6. Develop a kivy paint application that provides a paint palette containing basic 12 colours along with
the paint area and a brush for painting.
7. Develop a kivy application for the pong game. The pong game is a table tennis game where the player
who scores 11 points first by hitting the ball wins the game.
Index
A
abc module, 303
ABCMeta, 303
Abstract Base Classes (ABCs), 303
Abstract class, 303
Abstract data type, 259
Abstract methods, 303
Abstraction, 279
Accessing Web Data, 539
Accessor methods, 280
Accessors, 280
Activation record, 191
Actual parameters, 33
Adding methods dynamically, 282
Aliasing, 151
Alphabet, 137
Animation: bouncing ball, 517
Append, 359
Application programming interfaces (API), 522
Argument, 20, 33
Arithmetic operators, 5
ASCII values, 6
Assert statement, 39
Assignment statements, 9, 10
Association, 10
Attribute resolution order, 307
Attributes, 541
B
Base class, 285
Binary search tree, 419
building, 431
traversal of, 422
Binary search, 331
Binary tree, 418
height of a, 430
Binding, 10
Bits, 8
Bitwise operators, 8
Blocking function, 484
Boolean (bool), 250
Boolean values, 6
Break point, 87
break statement, 72
Bubble sort, 320
Build, 551
Built-in classes, 250
boolean (bool), 250
dictionary (dict), 250
floating point (float), 250
integer (int), 250
list, 250
string (str), 250
tuple, 250
Built-in function, 20, 27
Built-in functions for classes, 309
Built-in functions on strings, 127
C
Called function, 30
Callee function, 30
Caller function, 30
Calling the function, 20
Cardinality, 541
Chat applications, 571
Child class, 285
Class attributes, 250
Class constructor, 253
Class initializer, 253
Class node, 385
Classes, 250
Command line arguments, 41–42
Complete binary tree, 418
Composition, 20, 284
Conditional expression, 51
Continue statement, 72
Control structures, 46–80
Control structures, 78
Converting python collections to Java collections, 566
Create table, 543
Creating a linked list of cubes, 388
D
Data, 279, 357
Data definition language (DDL), 541, 542
Data hiding, 279
Data manipulation language (DML), 542
Data structures, 357
Database
concepts, 541
creating, 542
loading the, 545
populating the, 545
Database management system (DBMS), 540
Date class, 265
Debugging, 85–95
commands, 88–89
Deep copy, 210
Default values, 37
Degree, 541
Deletion, 177
Dependencies, 550
Dequeue, 369, 412
Derived class, 285
Destructor, 257
Developing mobile application for android, 550
Dict, 250
Dictionary, 175
inverted, 179
operations, 177
Docstring, 4
Domain, 543
E
Echo server, 537
else statement, 77
Empty except clause, 232
Empty language, 138
Encapsulation, 279
Enqueue, 369, 409
Entity, 541
Errors, 227
exceptions, 228
indentation error, 228
indentation, 228
IndexError, 230
NameError, 228
OSError, 230
syntax, 227
TypeError, 229
ValueError, 229
ZeroDivisionError, 229
Escape sequences, 22
eval function, 20
Exceptions, 228
Extracting comments, 144
F
File, 221
handling, 221
Finding common factors, 171
Floating point (float), 250
Floating point numbers, 2
for loop, 58
Formal parameters, 33
Fractal, 471
Front, 372
Front end, 369
Fruitful function, 36
Function parameters, 33
Function(s), 19–42
append, 154
axis, 489
built-in, 20, 27
called, 30
callee, 30
caller, 30
calling the, 20
composition, 20
comprehension, 157
copy, 170, 179
count, 127, 154, 175
decode, 132
definition and call, 27–38
dump, 226
encode, 132
endswith, 132
eval, 20
extend, 154
filter, 164
find, 128
from math module, 25
fruitful, 36
functions, 157
get, 178
help, 37
index, 154, 175
input, 20
insert, 154, 156
invoking the, 20
isalnum, 131
isalpha, 131
isdigit, 131
islower, 129
isspace, 131
istitle, 129
isupper, 129
join, 131
list, 154
load, 227
lstrip, 130
map, 164
max, 24
min, 24
nested, 56
overloading, 277
partition, 130
pop, 154
pow, 24
print, 21
readline, 224
recursive, 188
reduce, 164
remove, 154,
replace, 130
reverse, 156
rfind, 128
round, 22
rstrip, 130
seek, 225
show, 484
sort, 156
split, 130
startswith, 132
strip, 130
superset test
tuple, 174
type, 22
update, 178
wrapper, 438
writelines, 225
zip, 174
G
Game of Xs and Os, 550
Global frame, 29
Global names, 114
Graphical package, 445
Graphics, 483–519
2D, 483
3D, 509
animation, 517–519
arrow (2D), 508
arrow (3D), 514
box, 510
circle, 502
cone, 515
cosine curve, 500
curve, 516
cylinder, 513
ellipse, 504
histogram, 496
pie chart, 498
polygon, 506
rectangle, 505
ring, 512
sine curve, 500
sphere, 510
H
Handler, 235
Hard-coding, 205
hasattr, 309
Hierarchical inheritance, 295
Hilbert curve, 471
Home button, 486
I
Idle, 1
If conditional statement, 46
If-elif-else conditional statement, 55
If-else conditional statement, 52
Importing user-defined module, 38–39
Indentation error, 228
Indentation, 29
IndexError, 230
Infinite loops, 64
Infix expression, 363
Infix form, 363
Inheritance, 285
hierarchical, 295
multilevel, 295
multiple, 299
single, 286
inner function, 57
Inorder traversal, 423
input function, 20
Insertion sort, 326
Instance method, 280
Integer (int), 250
Intersection operation on list, 171
Inverted dictionary, 179
Invoiking the function, 20
isEmpty, 361
isSubclass, 309
Iteration, 57
Iteration of the loop, 58
J
Javabridge, 563
Jpype, 563
K
Key, 316, 541
Keyword arguments, 38
Keywords, 13
Kivy, 550
application, 562
installation, 550
python chat application using, 570
L
Language, 137
empty, 138
null, 138
regular, 137
Last in first out (LIFO) arrangement, 358
Left binary subtree, 418
Left-child relationship, 419
LEGB Rule, 114
Linear search, 330
Linked list, 384
insertion and deletion at the beginning of, 388
maintaining sorted, 400
operations, 392
stack implementation using, 405–409
string representation of a, 399
traversing a, 399
list, 250
List manipulation, 315–354
List objects; copying, 159
Lists, 150–152
as argument, 158
intersection operation on, 171
two-dimensional, 152
union operation on, 171
Loading the database, 545
Logical operators, 6
Loop, 58
for, 58
infinite, 64
iteration of the, 58
nested, 69
while, 63
M
Master data, 240
Matplotlib, 445, 484
max function, 24
Membership, 127
Memory map, 34
Metadata, 542
Method overriding, 289
min function, 24
Modifier, 280
Modular approach, 19
Module, 14
Modulus, 2
Multilevel inheritance, 295
Multiple inheritance, 299
Multiple plots, 492
N
Name mangling, 279
NameError, 228
Names, 10
Namespaces, 114
Nested function, 56
Nested if-elif-else conditional statement, 55
Nested loops, 69
Nesting, 55
New-style classes, 306
Node(s), 384
deleting, 396
internal, 417
keep track of, 397
root, 416
value of the, 416
Null language, 138
Null string, 137
O
Object attributes, 255
Object composition, 284
Object-oriented programming (OOP), 272
Objects, 2, 250
Open authentication (OAuth), 522
Operands, 2
Operator overloading, 272, 273
Operator, 2
arithmetic, 5
bitwise, 8
logical, 6
relational, 5
OSError, 230
Outer function, 57
P
Parameters, 33
actual, 33
formal, 33
function, 33
Parent class, 285
Pass statement, 72
Patches, 502
Pattern matching, 137
Pattern within a pattern, 445
Pickling, 226
Pivot element, 351
Plotting a point, 484
Polymorphism, 272
Pop, 358, 361
Populating the database, 545
Postfix form, 363
Postorder traversal, 430
pow function, 24
Preorder traversal, 429
print function, 21
Problem of Tower of Hanoi, 214–218
Problems
eight queens, 448
Knight’s Tour, 455
stable marriage, 464
Program, 14
Properties, 551
Pseudocode, 32
push, 358, 361
Py4j, 563
Pyjnius, 563
Pyplot module, 484
Python, 1
applications of, 521–576
arrays in, 565
code, 1
editor, 1
errors, 227
integrating java with, 563
shell, 2
strings, 4, 125
style, 10
tutor, 101
visual, 509
PythonCopy, 225
Python tutor interface, 101
Pythonic style, 10
Pythonic way, 10
Q
Queue, 369
Queue operations, 372
R
raise keyword, 236
Random number generation, 24–25
Rear end, 369
Recursion, 188–218
Recursive function, 188
Recursive solutions for problems on lists, 204
copying a list, 209
deep copy, 210
flatten a list, 204
permutation, 211
Recursive solutions for problems on numeric data, 188–197
factorial, 188
fibonacci sequence, 194
Recursive solutions for problems on strings, 197–204
length of a string, 197
palindrome, 201
reversing a string, 199
Recusion, 481
Regular languages, 137
Relation, 541
Relational operators, 5
Retrieving all matching patterns, 144
Reversing a string, 136
Right binary subtree, 418
Right-child relationship, 419
Root node, 416
Round function, 22
S
Saving figure, 495
Scalar data types, 123, 150
Scope rule, 290
Scope, 100–120
Script mode, 14
Searching, 315, 329
Selection sort, 316
set functions, 167, 171
add, 167
clear, 167
difference, 168
intersection, 168
pop, 167
remove, 167
symmetric_difference, 168
union, 168
update, 167
Sets, 166
Shallow copy, 210
Shared session, 102
Sharing data across applications, 532
Sharing data using sockets, 532
Short-circuit evaluation, 7
Shorthand notation, 11
Sierpinski Triangle, 471
Single inheritance, 286
Singleton tuple, 173
Size, 361, 373
Slice, 125
Slicing, 125–126
socket, 533
Socket programming, 570
Sort
bubble, 320
insertion, 326
merge, 349
quick, 351
Sorting, 315
Source code, 14
Source file script, 14
SQLite database, 540
Stack frame, 191
Stack, 357
deletion of an element from a, 358
insertion of an element in a, 358
Static method, 280
Stepwise refinement method, 19
Stepwise refinement process, 32
Straight line functions, 46
Stream, 530
streamListener, 530
Strictly binary tree, 418
String (str), 250
String, 137
null, 137
Strings, 123–147
reversing, 136
Structured query language (SQL), 541
Sub, 285
Sub-programs, 19
Subset, 170
Sudoku puzzle, 477
Super class, 285
Superset test, 170
Symbols used in regular expressions, 139–140
Syntax error, 227
T
Table(s)
creating, 542
deleting, 549
inserting data into, 545
retrieving data from, 546
updating data in a, 548
Temporary variable, 13
Testing, 85
Tic-Tac-Toe game, 558
Top, 361
Transaction data, 240
Transmission Control Protocol/Internet Protocol (TCP/IP), 533
Tree, 416
ancestor/descendant, 417
height, 417
internal node, 417
leaf, 417
level, 417
path and path length, 417
siblings, 418
subtree, 418
try…except clause, 230
Tuple, 172, 250, 541
Tweet update, 530
Twitter, 521
collecting followers, friends, and tweets of a user, 526
collecting tweets having specific words, 530
collecting information from, 521
data analysis, 522
open authentication, 523
Two-dimensional list, 152
Type conversion, 23
type function, 22
TypeError, 229
U
uixmodule, 551
Underflow condition, 358
Underflow, 370
Unhandled exceptions, 230
Union operation on list, 171
Union operator, 138
Unpickling, 226
Update command, 548
User-defined classes, 250
V
Value of the node, 416
ValueError, 229
Values, 2
Variable current, 402
Variables, 9
Visualize execution, 102
Void function, 36
W
Web Data; Accessing, 539
Wedges, 498
Where clause, 547
while loop, 63
Widgets, 551
Wrapper function, 438, 447
Writing structures to a file, 226
Z
ZeroDivisionError, 229
Colour Illustrations
Plate 1 Function plot(3, 2)to display point (3, 2)(see page 485)
Plate 2 Point (3, 2) (see page 486)
Plate 5 Dashed line joining points (star marker) specified by vector x and y (see page 488)
Plate 6 Solid line joining points defined by vectors [0, 1, 2, 3, 4] and y (see page 489)
Plate 7 Line joining points specified by vectors x and y (see page 489)
Plate 8 Line joining points specified by vectors x and y (see page 490)
Plate 9 Line joining points specified by vectors x and y (see page 491)
Plate 10 Functions f(x) = x2 and f(x) = x3 plotted in the interval [2.5, 4.5] in steps of 0.1 (see page
493)
Plate 11 Six functions plotted on different subgraphs in same figure (see page 496)
Plate 12 Histogram (see page 497)