POLYTECHNIC UNIVERSITY

OF THE PHILIPPINES
Computer Engineering
College of Engineering
Mabini Campus, Sta. Mesa

CMPE 30052
Data Structures and Algorithms

Engr. Julius S. Cansino

1
 Data Structures and Algorithms
CMPE 30052

Engr. Julius S. Cansino

ALL RIGHTS RESERVED. No part of this learning module may be

reproduced, used in any form, or by any means graphic, electronic, or
mechanical, including photocopying, recording, or information storage and
retrieval system without written permission from the authors and the
University.

Published and distributed by:

Polytechnic University of the Philippines

Address : 1016 Anonas St., Brgy. 630, Sampaloc, Sta. Mesa, Manila
Website : https://www.pup.edu.ph
Email Address : inquire@pup.edu.ph
Tel. No. : (+63 2) 5335-1PUP (5335-1787) or 5335-1777

2
 The VMPGO

VISION
PUP: The National Polytechnic University

MISSION
Ensuring inclusive and equitable quality education and promoting lifelong
learning opportunities through a re-engineered polytechnic university by committing to:
• provide democratized access to educational opportunities for the holistic
development of individuals with global perspective.
• offer industry-oriented curricula that produce highly-skilled professionals with
managerial and technical capabilities and a strong sense of public service for
nation-building.
• embed a culture of research and innovation.
• continuously develop faculty and employees with the highest level of
professionalism.
• engage public and private institutions and other stakeholders for the attainment
of social development goal.
• establish a strong presence and impact in the international academic community.

PHILOSOPHY
As a state university, the Polytechnic University of the Philippines believes that:
• Education is an instrument for the development of the citizenry and for
the enhancement of nation-building; and,
• That meaningful growth and transformation of the country are best achieved in
an atmosphere of brotherhood, peace, freedom, justice and nationalist-oriented
education imbued with the spirit of humanist internationalism.

3
SHARED VALUES AND PRINCIPLES
1. Integrity and Accountability
2. Nationalism
3. Sense of Service
4. Passion for Learning and Innovation
5. Inclusivity
6. Respect for Human Rights and the Environment
7. Excellence
8. Democracy

GOALS OF THE COLLEGE/CAMPUS

1. Provide quality education through instruction, advance research and extension

services

2. Produce world-class professionals as potential industry leaders and job

providers

3. Develop and produce facilities through the use of adapted technology and
indigenous materials

4. Maintain, upgrade or improve facilities through the applications of engineering

technology

PROGRAM DESCRIPTION

The Database Management System (DBMS) program is designed to provide

students with comprehensive knowledge and practical skills in the field of database
management. This program covers the fundamental concepts, methodologies, and
technologies essential for designing, implementing, and managing modern database
systems. Students will gain a strong foundation in database theory, as well as
hands-on experience with database technologies and tools.

4
COURSE DESCRIPTION

Database Management System (DBMS) introduces students to the principles and

practices of designing, implementing, and administering databases. Topics include
relational database concepts, SQL query language, database design methodologies,
transaction management, concurrency control, and database administration. Students
gain hands-on experience in database design, querying, and administration, preparing
them for roles involving data management in computer engineering.

INSTITUTIONAL LEARNING OUTCOMES (ILOS)

A PUP graduate imbibed:

1. Creative and Critical Thinking
2. Adeptness in the Responsible Use of Technology
3. Strong Service Orientation
4. High Level of Leadership and Organizational Skills
5. Community Engagement
6. Effective Communication
7. Sense of Personal and Professional Ethics
8. Passion to Life-long Learning
9. Sense of National and Global Responsiveness

PROGRAM LEARNING OUTCOMES (PLOS)

1. Employed in the field of Network Engineering or Big Data or Machine Learning or

System Development or other related fields

2. Committed members of professional and other allied organizations engaged in

community development and nation building

3. Involved in continuous training and development in current or emerging trends, and

advancement in their chosen field of specialization

5
COURSE LEARNING OUTCOMES (CLOS)

1. Able to analyze real-world scenarios and design appropriate database schemas

using Entity-Relationship Diagrams (ERDs) and normalization techniques

2. Demonstrate the ability to construct complex SQL queries to retrieve, update, and
manipulate data stored in relational databases

3. Develop a comprehensive understanding of fundamental database management

concepts such as transaction management, concurrency control, and database
security and be able to apply these concepts to design robust and secure database

6
 Preface
In the digital age, the ability to manage and manipulate data effectively is an invaluable skill.
The Database Management Systems (DBMS) instructional material you are about to explore
is designed to provide a thorough introduction to the principles and practices that form the
backbone of data management.

This material is structured to guide students from the basics of database concepts and data
modeling to advanced topics such as transaction processing, data integrity, and distributed
databases. Each chapter is meticulously crafted to build on the previous one, ensuring a
coherent and comprehensive learning experience.

Emphasizing both theory and practice, we have included numerous examples, exercises, and
projects that encourage hands-on learning. These practical components are intended to
reinforce the theoretical knowledge and provide learners with the tools they need to tackle
real-world database challenges.

As educators and professionals in the field, our goal is to demystify the complexities of DBMS
and make this critical subject accessible to all. We trust that this material will serve as a
valuable resource in your educational journey and professional development.

7
 Introduction

This course is divided into ten (10) modules. The modules provide context and

foundational knowledge. Topics include:

• List and list comprehension

• Sorting Algorithm

• Python’s Object-Oriented Programming

• Python’s Exception Handling

• Linked list

• Stacks and its applications

• Queues

• Trees

• Graphs

• Complexities in Algorithms

Activities per module include Laboratory works and Machine Problems for the

students to learn and adapt to the module’s lessons more effectively.

8
 Acknowledgements

This lecture book was accomplished with the help of the following students:

Agsangre, John Mark S. Lofranco, Peewee James D. C.

Amante, Aubrey Gail A. Mamuyac, Vincent Louise B.
Annang, Mary Joy Anne B. Mañebo, Don Rexon L.
Balbalosa, Francine Ruth P. Manucom, Justin Gerick D.
Bataller, Russel Ivan B. Mauricio, Jeorge Alexene A.
Belano, Kristel Shaine A. Morales, Juan Karlo C.
Blanco, Gerard Ian D. Navarrosa, Francis Yvan G.
Blas, Ceasar Lance D. Omadto, Kristen Nicole C.
Burog, Ranei B. Pangilinan, Kenneth Owen C.
Cañarejo, Elijah Joel S. Parcon, Jian Karlo E.
Capistrano, Luis Gabriel P. Punzalan, Khaye Nicole P.
Casanova, Allen Christian C. Regaspi, Marcus Dwayne E.
Climacosa, Jonathan Hope S. Reyes, John Mark S.
De Guzman, Justine Nicole M. Rosero, Ann Catherine B.
De Leon, Joseph M. Rosete, Mark Aaron V.
Deogracias, Marie Claire L. Sabido, Jynoe L.
Diccion, Ras Genry T. Saliente, Bella
Espinas, Aira Ysabelle R. Santos, Jann Jaspher V.
Francisco, Stephanie L. Sta. Ana, Jhemeriz M.
Gubatan, Mary Anne M. Ubaldo, Val Vinson A.
Guevara, Ivan Roswell V. Vasquez, Daniel S.
Guillermo, Antoinette G. Vergel De Dios, Vince Allen C.
Ignacio Jr., Norberto G. Villaruel, Jared Chello T.
Lambon, Aaron Lowell B. Yalung, Joshua A.

9
 Table of Contents
Title Page 1

The VMPGO 3

Preface 7

Table of Contents 10

List of Figures and Tables 11

Introduction to Data Structures and Algorithms 15

a. Linear Data Structures 16

b. Non- Linear Data Structures 19

c. Abstract Data Types 21

d. Algorithm 22

Activity 22

Lesson 1: List and List Comprehension 25

1.1 Lists 25

1.2 List Concatenation 27

1.3 List Comprehension 28

Activity 30

Lesson 2: Sorting Algorithm 32

2.1 Selection Sort 33

2.2 Bubble Sort 35

2.3 Insertion Sort 37

2.4 Merge Sort 39

Activity 43

Lesson 3: Python’s Object-Oriented Programming 45

10
 3.1 Overview of OOP Terminologies 45

3.2 Defining a Class in Python 46

3.3 Class Inheritance 47

3.4 Creating an Object in Python 48

3.5 Constructors in Python 49

3.6 Built- in Class Attributes 50

3.7 Deleting Attributes and Objects 50

Activity 51

Lesson 4: Python’s Exception Handling 55

4.1 What is Exception? 55

4.2 Catching Exceptions in Python 55

4.3 Catching Specific Exceptions in Python (Part I) 57

4.4 Catching Specific Exceptions in Python (Part II) 58

4.5 Raising Exceptions in Python 58

4.6 Try with else Clause in Python 59

4.7 Try- finally 60

4.8 Exception Hierarchy 61

Activity 61

Lesson 5: Linked Lists 65

5.1 What are Linked Lists? 65

5.2 Difference Between Linked Lists and Arrays 66

5.3 Using Linked Lists Instead of Arrays 66

5.4 Linked List Operations 67

Activity 71

Lesson 6: Stacks and its Applications 72

11
 6.1 Stacks 72

6.2 Operation in Stacks 73

6.3 Evaluation of Expression 73

6.4 Reversing Strings 76

6.5 Conversion of Decimal to Other Number System 76

6.6 Backtracking 77

6.7 Parenthesis Matching 77

Activity 78

Lesson 7: Queues 80

7.1 What is Queue? 80

7.2 Steps of Enqueue Operation 81

7.3 Steps of Dequeue Operation 81

7.4 Basic Features of Queue 81

7.5 Auxiliary Queue Functions 81

7.6 Different Types of Queues 81

7.7 Applications of Queue 82

7.8 Implementation of Queue Data Structure using Array 83

Activity 84

Lesson 8: Trees 85

8.1 Overview of Tree Terminologies 85

8.2 Binary Tree Data Structure 86

8.3 Types of Binary Tree 87

8.4 Binary Tree Traversals 88

8.5 Arithmetic Expression Tree 92

8.6 Binary Search Tree Implementation in Python 96

12
 8.7 Applications of Tree Data Structure 98

Activity 99

Lesson 9: Graphs 101

9.1 Vocabulary and Definitions 102

9.2 The Graph Abstract Data Type 104

9.3 Adjacency Matrix 104

9.4 Adjacency List 106

9.5 Graph Implementation in Python 106

Activity 112

Lesson 10: Complexities in Algorithm 114

10.1 Properties of Algorithm 114

10.2 Various Steps in Developing Algorithms 115

10.3 Efficiency of an Algorithm 116

10.4 What is Complexity in Algorithms 116

10.5 Types of Complexities in Algorithms 117

10.6 What is Big- O Notations 119

10.7 Time Complexities Application Samples 120

10.8 Space Complexities Application Samples 127

Summary 128

Activity 128

13
 APPENDICES

List of Figures

Lesson 5: Linked Lists

Figure 5.1.1 64
Figure 5.4.1 67
Figure 5.4.2 67
Figure 5.4.3 68
Figure 5.4.4 68
Figure 5.4.5 69
Figure 5.4.6 69

Lesson 7: Queues
Figure 7.1.1 79

Lesson 9: Graphs
Figure 9.A 101
Figure 9.1.1 102
Figure 9.3.1 104
Figure 9.4.1 105

14
 INTRODUCTION TO DATA STRUCTURES AND ALGORITHM

LEARNING OBJECTIVES
✓ To introduce the concept of data structures and its importance.
✓ To learn the difference between linear and non-linear data structure.

✓ To understand Abstract Data Types (ADTs), abstraction, and encapsulation.

INTRODUCTION
What is Data Structure and its function?
• A data structure is a specialized format for processing, organizing, retrieving and
storing data in order to facilitate the access and modifications.
• A data structure may be selected or designed to store data for the purpose of
working on it with various algorithms in Computer Programming.
• Each data structure contains information about the data values, relationships
between the data and functions that can be applied to the data.
• It is a representation of data and the operations allowed on the data.
Fundamental Data Structures

Fundamental Data Structures

15
Operations in Data Structure
• Deletion
➢ removal of a data element from a data structure if it is found.
• Insertion
➢ addition of a new data element in a data structure.
• Searching
➢ involves searching for the specified data element in a data structure.
• Traversal
➢ processing all the data elements present in it.
• Sorting
➢ arranging data elements of a data structure in a specified order.
• Merging
➢ combining elements of two similar data structures to form a new data
structure of the same type.

A. LINEAR DATA STRUCTURES

A Linear Data Structure have data elements arranged in a chronological manner
and each element is linked to preceding and following element. Some examples of linear
data structures are List, Queue, Stacks, Array, etc.

Examples of Linear Data Structures:

1. Array
An array consists of data elements of a same data type. For example, you need
to store the names of 100 people, with array you can create a string type that can store
100 names.

16
2. Stack

Stack is a linear structure that uses LIFO (Last In-First Out) rule in which the last
data added will be removed first. A push operation adds a data element in the list while a
pop operation deletes an element from the list.

3. Queue
Queue is a data structure that uses the FIFO (First In-First Out) rule in which the
first element that was added will be remove first. There are two terms used in queue, front
end, and rear. The insertion operation performed at the back end is known as enqueue,
and dequeue is the deletion operation that is performed at the front end.

4. Linked list

17
 A Linked list is a collection of nodes that are made up of two parts.

Example A.1
Arrays:
1. Define the size of the array
as N
2. Create a list of N elements
where every element is zero
3. Now you can access each
element of the list using its
index ranging from [0, N-1]

Example A.2
Queues:
1. Define the sequence of elements
of the queue.
2. Create an empty list object as
variable Q and append the
elements in a sequence using
Q.append(val) method, this
operation is also called enqueuing.
3. For removing the elements use the
Q.pop(0) method of the created
object of the list which will remove
the element of the zeroth index,
this operation is also called
Dequeuing.

18
Example A.3
Stacks:
1. Define the sequence of
elements of the stack.
2. Create an empty list object as
variable S and append the
elements in a sequence using
S.append(val) method, this
operation is also called
pushing.
3. For popping the elements use
the S.pop() method of the
created object of the list which
will remove the element of the
last index.

B. NON-LINEAR DATA STRUCTURES

A non-linear data structure does not follow a sequential order, and the elements
may be connected to multiple elements as well. Even so, the elements are still sorted and
may have hierarchical relationships with each other. This kind of data structure is not
usually traversed in a single run, but in terms of the usage of memory, non-linear data
structure ensures an efficient utilization. The two common kinds of non-linear data
structure are the trees and graphs.

Examples of Non-Linear Data Structure:

1. Trees
A tree is an example of a non-linear data structure. As shown on the figure
on the right, it follows a hierarchical order. The tree has a root node, parent node,
child node, and the leaf node.
2. Graphs
A graph is also an example of non-linear data structure. It is composed of
nodes and edges which could be connected with the other elements.

19
Example B.1

Visual Representation of a Tree

Example B.2

Visual Representation of a Graph

Important differences between Linear Data Structures and Non-Linear Data Structures.

20
C. ABSTRACT DATA TYPES
Abstract Data Types (ADTs) are types of data whose behavior is specified by a set of
value and a set of operations. Process called abstraction and encapsulation make ADTs
beneficial.
• Abstraction refers to the organizing of solutions to a problem into well-defined
entities by defining their data and operations. It includes the replacement of low-
level details with a simpler, higher-level idea.
• Encapsulation hides the implementation and only provides well-defined
interface. It includes the building of walls or boundaries around the module’s
implementation so that the module will be only in-charge for its internal behavior
and will be independent to bugs in other parts of the system.

There are two parts to each ADT:

1. Public or External part is consisting of:
• the conceptual picture or the user’s view of what the object looks like and
how the structure is organized; and
• the conceptual operations that show what the user can do to the data.

2. Private or Internal part is comprised of:

• the representation of the data or how the structure is actually organized in
memory; and
• the implementation of the operations or the actual code.

There are main operations that can be defined for every collection ADT:
• add data,
• remove data, and
• access data.

Aside from these, ADT collections can also be defined to:

• check if the collection is empty;
• make the collection empty; and
• output a subset of the collection.

21
Each of these operations is executed by one or more subroutines during the
implementation. The data structures used in the implementations can be in the language
type primitive/built-
in or user-defined.

D. ALGORITHM
Algorithm is a well-ordered collection of unambiguous and effectively computable
operations that, when executed produces a result and halts in a finite amount of time. To
analyze an algorithm the most important factors is to calculate resources needed for
running the algorithm.

ACTIVITY
1. A collection of nodes that are made up of two parts.
a. Queues
b. Stacks
c. Trees
d. Linked List

2. It is a finite set of instructions and logic that is written in sequential order, to

accomplish a certain task.
a. List
b. Algorithm
c. Linear Data Structure
d. Non-Linear Data Structure

3. It consists of data elements of a same data type.

a. Tree
b. Queue
c. Array
d. Encapsulation

4. It is a data structure that uses the FIFO (First In-First Out) rule.
a. Queue

22
 b. Stacks
c. Linked List
d. Algorithm

5. What part of an ADT is created using encapsulation?

a. External
b. Private
c. Public
d. Data Structures

6. How are data structures implemented in ADTs?

a. through primitive language
b. through user-defined functions
c. through adding a data
d. both a and b

7. It is a specialized format for processing, organizing, retrieving, and storing data

in order to facilitate the access and modifications.
a. Linear Data Structures
b. Arrays
c. Data Structure
d. Non-Linear Data Structure

8. It is an operation of removing of a data element from a data structure if it is

found.
a. Deletion
b. Insertion
c. Merging
d. Sorting

9. It is an operation of adding a new data element in a data structure.

a. Deletion
b. Insertion

23
 c. Searching
d. Sorting
10. It is an operation of combining elements of two similar data structures to form
a new data structure of the same type.
a. Deletion
b. Insertion
c. Merging
d. Sorting

24
 MODULE 1
MODULE 1
List and List Comprehension

INTRODUCTION
What comes to your mind when you hear the word “collection”? Collection is a
group of anything that may or may not share distinct characteristics. The arrangement of
elements does not have a specific order or pattern. When a collection begins to follow a
specific order, then it becomes a sequence.
A sequence is a collection of objects that contains multiple items of data arranged
in a particular manner. In Python, sequence of elements can be stored inside a list.

LEARNING OBJECTIVES
✓ To understand and be familiar with lists and list comprehension

✓ To apply different methods of lists

✓ To apply and practice list comprehension

1.1 | LISTS
A list is a type of sequence that contains elements and data. Unlike arrays, lists are
flexible in storing different data types, may it be an integer or a string. In Python, the
elements inside a list are enclosed in square brackets while being separated by a comma.
They also have a definite count, and elements can be located indexing the list. There are
many methods that can be applied while working with lists.

To create a list, simply assign a variable to an empty square bracket or use the list
function. To check for its contents, you may print the list. The index of a list starts with 0.
Index refers to the position of a certain element in the list, and we can apply it by using
the index() method. We can individually access the items in the list using indexing.
Meanwhile, we can locate the end of a list through negative indexes.
List slicing is used to get a sublist or a specific portion of items from a list. Said portion
can be anywhere for the list. The operator “:” is the most commonly used to get a range
of elements in a list. Syntax in Python is as follows:

25
Example 1.1.1

Output:

These are other methods to be used in working around with lists:

append() Adding an element at the end of the list

extend() Copies the elements of one list to another

insert() Takes two arguments; inserts an element on a specified position

remove() Removes the specified element from the list

pop() Removes an item based on the given index as argument

clear() Takes out all the elements on the list

count() Counts how many times an element is listed on the list

sort() Arranges the elements in a chronological order

reverse() Reverses the elements position on the list

To traverse and check for the items on the list, we can use in and not in operator. This
will return a Boolean value whether or not the item has been found.

26
1.2 | LIST CONCATENATION
List concatenation is used when we have number of different lists of elements that needs
to be processed in a similar manner. There are three methods to concatenate a list:
Method #1: Using the “Naive Method”
Steps:
1. Transverse the second list
2. Append each element to the first list.

Example 1.2.1

Output:

Method #2: Using the “+” Operator (the conventional method)

Steps:
1. Add the two names of the list.

Example 1.2.2

Output:

Method #3: Using list comprehension

Steps:
1. Create a one-line expression to the loop method discussed above.

27
Example 1.2.3

Output:

1.3 | LIST COMPREHENSION

List comprehension allows a much shorter way of creating lists with elements. It is
made up of square brackets that indicates the list, and the expressions or conditions
inside. For and if clauses are usually the expressions executed.

Example 1.3.1
Two ways in creating a list

Example 1.3.2
Indexing through the list

28
Example 1.3.3
Other methods in Lists:

29
ACTIVITY
1. What are the two ways in creating a list? Choose those that apply.
a. using copy() method
b. assigning a variable to square brackets
c. using list() function
d. print(list)

2. What is the method that removes an item based on the index provided?
a. remove()
b. copy()
c. clear()
d. pop()

3. What is the concise way of creating a list by using expressions?

a. List Comprehension
b. extend() method
c. using square brackets
d. list() function

4. What will be the output of the code:

a. 1
b. 1, 1, 1
c. [1, 1, 1]

5. What is the element of list[-2] given the list below?

a. Monday
b. Thursday
c. Sunday

30
6. What do you call the operation that can get a sublist or a portion of the original
list?
a. Indexing
b. Concatenating
c. Slicing
d. Copying

7. What is the conventional way of concatenating lists?

a. Using list comprehension
b. Using the “+” operator
c. Using the Naïve Method

8. What will be the output of the following snippet:

a. [10,15,10]
b. [15,20]
c. [10,15]

9. What will be the output of the snippet in number 8, when

will be printed?
a. [10,15,20]
b. [15,20]
c. [10,15]

10. What will be the output of this list comprehension code

a. [1, 8, 27, 64, 125]

b. [1, 8, 27, 64]
c. [0, 1, 8, 27, 64]

31
 MODULE 2
MODULE 2
Sorting Algorithm

INTRODUCTION
Sorting is one of the most thoroughly studied algorithms in computer science, it
refers to arranging data in a particular format and it is a basic building block that many
other algorithms are built upon. It is also used to represent data in more readable formats.

A Sorting Algorithm specifies the way to arrange data in a particular order, it is

used to rearrange a given array or list elements according to a comparison operator on
the elements, which is used to decide the new order of element in the respective data
structure.

Here are some of the implementations of sorting in python: selection sort, bubble sort,
insertion sort, and merge sort.

There are adaptive and non-adaptive sorting algorithms. An algorithm is adaptive

if takes advantage of already 'sorted' elements in the list that is to be sorted and if the
source list has some element already sorted while sorting, adaptive algorithms will take
this into account and will try not to re-order them. On the other hand, non-adaptive
algorithm is one which does not consider the elements which are already sorted, they just
force every single element to be re- ordered to confirm their sorting.

LEARNING OBJECTIVES
✓ Students should be able to define what is sorting algorithm

✓ Visualize and learn how to sort in ascending and descending order using
Selection Sort
✓ Understand and apply Selection Sort in programming in Python

Some terms that are helpful to know in sorting algorithms:

1. Increasing Order
• The successive element is greater than the previous one

32
 Example:
2 4 6 8 10 are in increasing order because every next element is
greater than the previous one

2. Decreasing Order
• The successive element is less than the current one
Example:
9 7 5 3 1 are in decreasing order, because every next element is less
than the previous one

2.1 | SELECTION SORT

The sorting algorithm that sorts an array by repeatedly finding the minimum element (for
ascending order) from unsorted part and putting it at the beginning or by finding the
maximum element (for descending order) from unsorted part and putting it at the
beginning is the Selection Sort. The algorithm maintains two subarrays in each array:
the sorted subarray and the unsorted remaining subarray.

In every iteration of selection sort, the minimum element (considering ascending order)
or maximum element (considering descending order) from the unsorted subarray is
picked and moved to the sorted subarray.

The algorithm for an unsorted list to be arranged in ascending order is as follows:

1. Start by finding the minimum value in a given list and move it to a sorted list
2. Repeat the process for each of the remaining elements in the unsorted list
3. Next element entering the sorted list is compared with the existing elements and
placed at its correct position

To arrange elements in descending order, start by finding the maximum value instead of
the minimum value.

An example for an implementation of Selection Sort in a python program is as follows:

33
Example 2.1.1
Sort the list [15, 10, 5, 3] in ascending order using Selection Sort.

Start by finding for the minimum value, which is 3, and move it to a sorted array [3]. In the
next step, the minimum value is 5 in the remaining elements of unsorted array, so we
moved it to the sorted array [3, 5]. In the third step, the minimum value is 10 in the
remaining elements of unsorted array, so we moved it to the sorted array [3, 5, 10]. In the
last step, the minimum value left in the unsorted array is 15, so we moved it to the sorted
array [3, 5, 10, 15].

Example 2.1.2
Sort the list [24, 7, 18, 26, 33, 29] in descending order using Selection Sort.

Start by finding the maximum value, which is 33, and move it to a sorted array [33]. In the
next step, the maximum value is 29 in the remaining elements of unsorted array, so we
moved it to the sorted array [33, 29]. In the third step, the maximum value is 26 in the
remaining elements of unsorted array, so we moved it to the sorted array [33, 29, 26]. In
the fourth step, the maximum value is 24 in the remaining elements of unsorted array, so
we moved it to the sorted array [33, 29, 26, 24]. In fifth step, the maximum value is 18 in
34
the remaining elements of unsorted array, so we moved it to the sorted array [33, 29, 26,
24, 18]. The only left element in the unsorted array is 7, so moving it to the sorted array
gives us [33, 29, 26, 24, 18, 7].

2.2 | BUBBLE SORT

The Bubble Sort is considered to be the simplest sorting algorithm that works by
repeatedly swapping succeeding elements if they are in the wrong order.

LEARNING OBJECTIVES
✓ To learn how to use Bubble Sort in sorting sets of numbers

✓ To know when to use Bubble Sort as a sorting algorithm

✓ To implement Bubble Sort in Python code

The algorithm for sorting a list in ascending order using Bubble Sort follows:
1. Compare the values of the first element and the element succeeding it and swap
their positions if the first element is greater.
2. Repeat this process through the second element until the (n + 1)th to the last
element with n being the number of iterations done to the list including the current
one as the last n – 1 element(s) is/are already in place.
3. Check if the list has already been sorted.
4. If not, repeat steps 1 – 3 until the list is sorted.

Arranging elements in descending order is also possible for this sorting algorithm. The
elements would only be swapped if the former element is less than the latter element.

Converting the algorithm above to Python code:

35
Example 2.2.1

Using Bubble Sort, sort a list containing [5, 12, 8, 3, 9] in ascending order.

First Iteration:

Second Iteration:

Third Iteration:

Example 2.2.2

In descending order, use Bubble Sort to sort [5, 18, 16, 7, 12]

First Iteration:

36
Second Iteration:

Example 2.2.3

Sort [8, 19, 20, 16, 1] in ascending order using Bubble Sort.

First Iteration:

Second Iteration:

Third Iteration:

Fourth Iteration:

2.3 | INSERTION SORT

Insertion sort includes splitting a list into two, one for the sorted elements, and the other
for the unsorted elements. This sorting algorithm iterates the unsorted list from left to right
and “inserts” them into the sorted list, until the unsorted list is depleted, and all that
remains is the sorted list.

37
LEARNING OBJECTIVES
✓ Learn how to use Insertion Sort to arrange in ascending and descending order.

✓ Learn how to code Insertion Sort in Python.

✓ Learn how to visualize Insertion Sort.

The algorithm for an unsorted list to be arranged in ascending order is as follows:

1. Iterate from the second element to the final element.

2. Compare the current element to the previous element.
3. If the current element is smaller, compare it to the elements before the previous
elements. Repeat until there are no more smaller elements to compare with.
4. Move all greater elements one space higher to make space for the current
element to take its new position.

To arrange elements in descending order, simply change the comparison from requiring
a lesser previous element to a greater previous element in value.

The Python 3.x code for Insertion sort is as follows:

Example 2.3.1

Sort the list [7, 4, 5, 3, 10] in ascending order using Insertion Sort

38
Green is the current element, and yellow is the element that has the smallest value in the
sorted list that can be compared as greater than the current element. If there are no yellow
cells in the row, the position of the current element does not move in relation to the highest
value of the sorted list, however, they are inserted at the end of the sorted list.

Example 2.3.2

Sort the list [7, 4, 5, 3, 10] in descending order using Insertion Sort.

Green is the current element, and yellow is the element that has the greatest value in the
sorted list that can be compared as lesser than the current element. If there are no yellow
cells in the row, the position of the current element does not move in relation to the lowest
value of the sorted list, however, they are inserted at the end of the sorted list.

2.4 | MERGE SORT

Merge sort is a sorting technique based on divide and conquer technique. With worst-
case time complexity being Ο(n log n), it is one of the most respected algorithms. Merge
sort first divides the array into equal halves and then combines them in a sorted manner.

39
Merge sort keeps on dividing the list into equal halves until it can no more be divided. By
definition, if it is only one element in the list, it is sorted. Then, merge sort combines the
smaller sorted lists keeping the new list sorted too.

LEARNING OBJECTIVES
✓ Learn how to use Merge Sort to arrange in ascending order.

✓ Learn how to code Merge Sort in Python.

✓ Learn how to visualize Merge Sort.

The algorithm for an unsorted list to be arranged in ascending order is as follows:

1. If it is only one element in the list it is already sorted, return.

2. Divide the list recursively into two halves until it can no more be divided.
3. Merge the smaller lists into new list in sorted order.

40
41
Example 2.4.1

Sort the list [14, 33, 27, 10, 35,19,42,44] in ascending order using Merge Sort.

Merge sort first divides the whole array iteratively into equal halves unless the atomic
values are achieved. We see here that an array of 8 items is divided into two arrays of
size 4.

This does not change the sequence of appearance of items in the original. Now we divide
these two arrays into halves.

We further divide these arrays and we achieve atomic value which can no more be
divided.

42
Now, we combine them in exactly the same manner as they were broken down. Please
note the color codes given to these lists.

We first compare the element for each list and then combine them into another list in a
sorted manner. We see that 14 and 33 are in sorted positions. We compare 27 and 10
and in the target list of 2 values we put 10 first, followed by 27. We change the order of
19 and 35 whereas 42 and 44 are placed sequentially.

In the next iteration of the combining phase, we compare lists of two data values, and
merge them into a list of found data values placing all in a sorted order.

After the final merging, the list should look like this −

ACTIVITY
1. Using Selection Sort, arrange the following values [3, 1, 7, 9, 15, 4] in ascending
order.
2. Using Selection Sort, arrange the following values [6, 2, 10, 18, 13, 5] in
descending order.

3. Write a python program that implements Selection Sort (consider ascending

order) where:
• The user must be prompted to enter a list of numbers
• The sorted list must be displayed

43
4. Using Bubble Sort, sort the following lists in ascending and descending order.
1. [5, 8, 1, 6, 3]
2. [12, 48, 23, 58, 16]
3. [158, 867, 254, 579, 957]

5. Arrange the values [23, 43, 22, 34, 32, 24] in ascending order visualized using
Insertion Sort.

6. Arrange the values [23, 43, 22, 34, 32, 24] in descending order visualized using
Insertion Sort.

7. Create a program that takes x amount of integers and arranges them in

descending order using Insertion sort. Output each iteration and the final output.

8. Arrange the values [23, 43, 22, 34, 32, 24] in ascending order visualized using
Merge Sort.

9. Arrange the values [33, 53, 12, 4, 72, 1] in ascending order visualized using
Merge Sort.

10. Create a program that takes x number of integers and arranges them in
ascending order using merge sort. Output each iteration and the final output.

44
 MODULE 3
MODULE 3
Python’s Object - Oriented Programming

INTRODUCTION

Python has been an object-oriented programming language since it existed. Unlike

procedure-oriented programming, where the main emphasis is on functions, object-

oriented programming stresses on objects. Because of python being an object-oriented

language, making and using classes and objects are uncomplicated.

LEARNING OBJECTIVES

✓ Understand the differences between class and object.

✓ Know how to define a class in Python.

✓ Create an Object in Python.

✓ Know how constructors are used in Python.

3.1 | OVERVIEW OF OOP TERMINOLOGIES

Class – we could use class as a sketch, blueprint, or prototype of a house. These

contain all the important details, parts of the house (floors, doors, windows, etc.) which

are used in building the house. The house is the object. In python, it is known as the user-

defined prototype for an object that defines a set of attributes that characterize any object

of the class.

Inheritance – this is the process where the characteristics of a class are

transferred and derived to other classes.

Instantiation – this is the term used when the process of creating an instance of

a class (object).

45
 Object – this is defined as a collection of data (variables) and methods (functions)

which act on those data. Like what the meaning of class above tells, the class is the

blueprint of the object. In python, it is a unique instance of a data structure which is defined

by its class. It compromises both data members which are the class variables and

instance variables and the methods.

Example: Calculator, Electric Fan, A book, Shoes, etc.

3.2 | DEFINING A CLASS IN PYTHON

In the creation of a class, a new local namespace is also created where all its

attributes are defined. A namespace is a collection of currently defined symbolic names

along with information about the object that each name references. Attributes may be a

data or a function. It is like a dictionary where in the keys are the object names and the

values are the objects themselves.

46
Example 3.2.1

• empCount is a class variable whose value is shared among all instances of a

class. It can be accessed as Employee.empCount from inside the class or outside
the class.
• The __init__() method, is a special method which is a constructor or initialization
method called when the user creates a new instance of this class.
• Declaring other class methods with the similarity of declaring other functions but
the first argument to be written to each method is self.
Defining a class could create a new class object with the same name as the class. The
new class object will give access to the user to the different attributes and to instantiate
new object of that class.
3.3 | CLASS INHERITANCE
To lessen the workload of the user, you can use your pre existing class to create a new
class by listing the parent class in parentheses after the new class name.
The new class or we could call child class inherits the attributes which are inside the pre
existing class or the parent class. The child class could also do override data members
and methods from the parent class.
This is the syntax when doing class inheritance:

47
3.4 | CREATING AN OBJECT IN PYTHON
Class objects could be used in accessing different attributes. It could also be used in
creating new object instances of that class, this process is called instantiation.

In this case, the new object instance we created named Lora which we could use to
access the attributes of objects using the object name prefix.
The use of attributes could be through a data or a method. The methods used of an object
are the corresponding functions of that class.
In the example below, Person.greet is used as a function object in other term it is called
attribute of class which means that Person.greet will be a method object.

The Output will be:

48
The self parameter in the function definition is inside the class but the method was called
as harry.greet without the use of any argument and it still worked.
It still worked because whenever the object calls its method, the object itself is passed as
the first argument. So, harry.greet() translates into Person.greet(Lora).
Essentially, a method that is called with a list of n arguments is the same as calling the
corresponding function with an argument list that is created by inserting the object of the
method before inserting the first argument.
The function’s first argument in the class must be the object itself. This is normally called
self.
3.5 | CONSTRUCTORS IN PYTHON
The functions in a class which starts with double or two underscores (__) are called
special functions because of the meaning they have.
One constructor which is mostly used is the __init__ function. When a new object of that
class is instantiated, this special function is used.
These constructors are used in Object – Oriented Programming (OOP) to initialize all the
variables.
Example 3.5.1

49
The output will be:

The example above shows a new class which used the functions, __init__() to initialize
the variables (defaults to zero) and get_data() to display the number properly.
The new attribute, attr was also created for the object num2 and read it as well. This
attribute was created for num2 and does not affect the object num1.
3.6 | BUILT – IN CLASS ATTRIBUTES
In every Python class there are built-in class attributes which could be accessed by the
user using the dot operator which is also used in any other attributes. Here are some of
those built-in attributes:

• __dict__ - An attribute which is a dictionary containing the class’s namespace.

• __doct__ - This attribute is used for accessing the class documentation string,
none if undefined.
• __name__ - This is the attribute for the class name.
• __module__ - This attribute is the module name that the class is defined. When
used in interactive mode, it is also used as “__main__”.
• __base__ - An attribute which is for an empty tuple containing the base classes
where the order is based on their occurrence in the base class list.

3.7 | DELETING ATTRIBUTES AND OBJECTS

Using the ‘del’ statement, any attribute in a class can be deleted anytime.

50
Example 3.7.1

Also, by using the del statement, we could delete the object itself.

When we do the c1 = ComplexNumber (4,5), we have created a new instance object

named c1.
Using ‘del c1’ the name c1 is deleted from the namespace. However, the object c1 =
ComplexNumber (4,5) continues to exist in the memory but when there is no name bound
to it, it will be automatically destroyed. This process in python is called garbage collection.

ACTIVITY

Answer the following questions:

1. In Python, a class is ________ for a concrete object.

a) A nuisance
b) An instance
c) A blueprint
51
 d) A distraction

2. Object and class attributes are accessed using ___ notation in Python.
a.) Dot
b.) Def
c.) __init__
d.) Class

3. In Python, a function within a class definition is called a:

a.) A class function
b.) A factory
c.) A method
d.) An operation

4. What will be the output of the following code snipet?

a.) AttributeError: ‘JackRussellTerrier’ object has no attribute ‘walk’

b.) *walking*

c.) Arff!
d.) Woof!

52
5. What is the output of the following code snippet?

a.) CanineError: Dog malfunction

b.) Arff!
c.) *walking*
d.) Woof!

6. What is the output of the following code snippet?

a.) canineError: Tail curvature exceeded

b.) *walking*
c.) Woof!
d.) Arff!

7. What you get when you tell Python to create a class.

a.) Object

53
 b.) Class
c.) Instance
d.) Inheritance

8. How do you define a function inside a class?

a.) Dot
b.) def
c.) class
d.) object
9. The concept that one class can inherit traits from another class, much like you
and your parents.
a.) Instance
b.) Inheritance
c.) Instantaneous
d.) Insect

10. Could be used as a data or a method.

a.) Function
b.) Method
c.) Instance
d.) Attributes

54
 MODULE 4
MODULE 4
Python’s Exception Handling

INTRODUCTION
4. 1 | WHAT IS EXCEPTION?
An exception is an occurrence that happens during the execution of a program that
interrupts the usual flow of instructions provided by the program. In general, an exception
occurs when a Python script faces a condition that it cannot cope with. A Python object
that contains an error is an exception. If a Python script raises an exception, it must either
handle the exception immediately or otherwise it terminates and quits.
In our programming experience so far, we have encountered several kinds of run-time
exceptions, such as division by zero, accessing a list with an out-of-range index, and
attempting to convert a non-number to an integer. To this point, all our run-time exceptions
have terminated the running program. Python offers a standard mechanism called
exception handling that assists programmers to deal with these kinds of run-time
exceptions and many more. Instead of always ending the execution of the program, as it
happens, an operating program may sense the problem and probably execute code to fix
the problem or minimize it in other ways. In Python, this chapter discusses handling
exceptions.

LEARNING OBJECTIVES
✓ Define what is Exception handling using Python.
✓ Learn how to apply Exceptions in Python.

✓ To be able to apply different functions of Exception handling in Python.

4.2 | CATCHING EXCEPTIONS IN PYTHON

Exceptions can be managed in Python by using try statement. The critical operation which
can raise an exception is placed inside the try clause. The code that handles the
exceptions is written in the except clause. Once we have identified the exception, we may
then select what operations to run. A basic example is here.’

55
Example 4.2.1

Output

In this program, we loop through the values of the randomList list. As previously
mentioned, the portion that can cause an exception is placed inside the try block. If no
exception occurs, the except block is skipped and normal flow continues (for last value).
But if any exception
occurs, it is caught by the except block (first and second values). Here, we print the name
of the exception using the exc_info() function inside sys module. We can see that a
causes ValueError and 0 causes ZeroDivisionError. Since every exception in Python
inherits from the base Exception class, we can also perform the above task in the
following way:

56
Example 4.2.2

4.3 | CATCHING SPECIFIC EXCEPTIONS IN PYTHON

In the above example, we did not mention any specific exception in the except clause.
This is not a wise programming technique, since all exceptions will be detected, and any
case treated in the same manner. We can specify which exceptions an except clause
should catch. A try clause can have any number of except clauses to handle different
exceptions, however, only one will be executed in case an exception occurs. We can use
a tuple of values to specify multiple exceptions in an except clause. Here is an example
pseudo code.

57
Example 4.3.1

4.4 | CATCHING SPECIFIC EXCEPTIONS IN PYTHON

While it is often tempting to catch every Exception. In most cases it is bad practice. It
might catch more than intended, such as SystemExit, KeyboardInterrupt and
MemoryError - each of which should generally be handled differently than usual system
or logic errors. It also means there is no clear understanding for what the internal code
may do wrong and how to recover properly from that condition. If you are catching every
error, you will not know what error occurred or how to fix it. This is more commonly
referred to as 'bug masking' and should be avoided. Let your program crash instead of
silently failing or even worse, failing at deeper level of execution. (Imagine it is a
transactional system) Usually, these constructs are used at the very outer level of the
program and will log the details of the error so that the bug can
be fixed, or the error can be handled more specifically.

4.5 | RAISING EXCEPTIONS IN PYTHON

In Python programming, exceptions are raised when errors occur at runtime. We can also
manually raise exceptions using the raise keyword. We can optionally pass values to the
exception to clarify why that exception was raised.

58
4.6 | TRY WITH ELSE CLAUSE IN PYTHON
In some situations, you might want to run a certain block of code if the code block inside
try ran without any errors. For these cases, you can use the optional else keyword with
the try statement.

Note: Exceptions in the else clause are not handled by the preceding except clauses.

Example 4.6.1

59
Output

4.7 | TRY-FINALLY
The try statement in Python can have an optional finally clause. This clause is executed
no matter what and is generally used to release external resources. For example, we may
be connected to a remote data center through the network or working with a file or a
Graphical User Interface (GUI). In all these circumstances, we must clean up the resource
before the program comes to a halt whether it successfully ran or not. These actions
(closing a file, GUI or disconnecting from network) are performed in the finally clause to
guarantee the execution.

This type of construct makes sure that the file is closed even if an exception occurs during
the program execution

60
4.8 | EXCEPTION HIERARCHY
Exception handling occurs based on an exception hierarchy, determined by the
inheritance structure of the exception classes. For example, IOError and OSError are
both subclasses of EnvironmentError. Code that catches an IOError will not catch an
OSError. However, code that catches an EnvironmentError will catch both IOErrors and
OSErrors.

ACTIVITY
1. How many except statements can a try-except block have?
a) zero
b) one
c) more than one
d) more than zero

2. What will be the output of the following Python code?

61
 a) NameError
b) ValueError
c) IndexError
d) TypeError

3. When will the else part of try-except-else be executed?

a) always
b) when an exception occurs
c) when no exception occurs
d) when an exception occurs in to except block

4. The following Python code will result in an error if the input value is entered as
-5.

a) True
b) False

5. What will be the output of the following Python code?

a) No output
b) after f?
c) error
d) after f

6. Which of the following is not an exception handling keyword in Python?

a) try
b) except
c) accept
d) finally

62
7. Compare the following two Python codes shown below and state the output if
the input entered in each case is -6?

a) ValueError, NameError
b) AttributeError, ValueError
c) NameError, TypeError
d) TypeError, ValueError

8. What will be the output of the following Python code?

a) 1
b) 2
c) 3
d) error, there is more than one return statement in a single try-finally block

9. What will be the output of the following Python code?

63
 a) someError has occurred
b) someError has not occurred
c) invalid code
d) none of the mentioned

10. What happens when ‘1’ == 1 is executed?

a) we get a True
b) we get a False
c) an TypeError occurs
d) a ValueError occurs

64
 MODULE 5
MODULE 5
Linked Lists

INTRODUCTION
5.1 | WHAT ARE LINKED LISTS?
Linked lists are a sequence of data elements, which are connected together via
links. Each data element contains a connection to another data element in the form of a
pointer. Python does not have linked lists in its standard library. However, one may
implement the concept of linked lists using the concept of nodes.

LEARNING OBJECTIVES
✓ Define what are Linked Lists.
✓ Identify the differences between Linked Lists and Array.

✓ Determine the advantages and drawbacks of using Linked Lists.

✓Learn how to insert or delete a node/ element in a Linked List.

Figure 5.1.1 The elements in Linked Lists are linked using pointers

Basic Operations
Following are the basic operations supported by a list.
●Insertion − add an element at the beginning of the list.
●Deletion − delete an element at the beginning of the list.
●Display − displaying complete list.
●Search − search an element using a given key.
●Delete − delete an element using a given key.

65
5.2 | DIFFERENCE BETWEEN LINKED LISTS AND ARRAYS
Like arrays, Linked List is a linear data structure. However, elements in a linked
list are not stored at a contiguous location (a single memory space).

Major Differences between Linked Lists and Arrays

●Size. Since data can only be stored in contiguous blocks of memory in an array, its size
cannot be altered at runtime due to risk of overwriting other data. In a linked list however,
each node points to the next one such that data can exist at scattered (non-contiguous)
addresses; this allows for a dynamic size which can change at runtime.
●Memory Allocation. For arrays at compile time and at runtime for linked lists.
●Memory Efficiency. For the same number of elements, linked lists use more memory
as a reference to the next node is also stored along with the data. However, size flexibility
in linked lists may make them use less memory overall; this is useful when there is
uncertainty about size or there are large variations in the size of data elements; memory
equivalent to the upper limit on the size has to be allocated (even if not all of it is being
used) while using arrays, whereas linked lists can increase their sizes step-by-step
proportionately to the amount of data.
●Execution Time: Any element in an array can be directly accessed with its index; in the
case of a linked list however, all the previous elements must be traversed to reach any
element. Also, better cache locality in arrays (due to contiguous memory allocation) can
significantly improve performance. As a result, some operations (such as modifying a
certain element) are faster in arrays, while some others (such as inserting or deleting an
element in the data) are faster in linked lists.

5.3 | USING LINKED LISTS INSTEAD OF ARRAYS

Arrays may be used to store linear data of similar types, but arrays have the
following limitations:
●The size of the arrays is fixed. We must know the upper limit on the number of elements
in advance. Also, generally, the allocated memory is equal to the upper limit irrespective
of the usage.
●Inserting a new element in an array of elements is expensive because the room has to
be created for the new elements and to create room existing elements have to be shifted.
Advantages over Arrays

66
●Dynamic size
●Ease of insertion or deletion

Drawbacks
●Random access is not allowed. We have to access elements sequentially starting from
the first node. cannot do binary search with linked lists efficiently with its default
implementation.
●Extra memory space for a pointer is required with each element of the list.
●Not cache friendly. Since array elements are contiguous locations, there is locality of
reference which is not there in case of linked lists.

5.4 | Linked List Operations

Inserting at the end of the Linked List
Inserting an element to the end of a Linked List involves pointing the next pointer
of the current last node of the linked list to the new data node. The current last node of
the linked list becomes the second last data node and the new node becomes the last
node of the linked list.

67
 Figure 5.4.1 How to insert an element to the back end of a Linked List using
Python

When the above code is executed, it produces the following result:

Figure 5.4.2 Result after using the code in Figure 5.4.1 to insert an element at the
rear of the list

Inserting in between two Data Nodes

This involves changing the pointer of a specific node to point to the new node. That
is possible by passing in both the new node and the existing node after which the new
node will be inserted. We define an additional class which will change the next pointer of
the new node to the next pointer of the middle node. Then assign the new node to the
next pointer of the middle node.

68
 Figure 5.4.3 How to insert an element between two nodes using Python

Figure 5.4.4 Output of Figure 5.4.3

Removing an Item from a Linked List

We can remove an existing node using the key for that node. In the below program
we locate the previous node of the node which is to be deleted. Then point the next pointer
of this node to the next node of the node to be deleted.

69
Figure 5.4.5. Code which removes a node in a Linked List

Figure 5.4.6. Output of Figure 5.4.5

70
ACTIVITY
1. Explain linked list.
2. Explain Insertion and Deletion.
3. Which of the following points is/are true about Linked List data structure when it is
compared with an array?
A. Arrays have better cache locality that can make them better in terms of
performance.
B. It is easy to insert and delete elements in Linked List.
C. Random access is not allowed in a typical implementation of Linked List.
D. The size of the array must be pre-decided, linked lists can change their size
any time.
E. All of the above
4. Which of the following sorting algorithms can be used to sort a random linked list
with minimum time complexity?
A. Insertion Sort
B. Quick Sort
C. Heap Sort
D. Merge Sort

71
 MODULE 6
MODULE 6
Stacks and Its Application

INTRODUCTION
Stacking is a process in which objects are arranged in a neat or orderly pile. In real
life, the process of stacking or creating a stack is always applied to almost any
arrangement of objects, from the simplest such as clothes and books, to the most complex
such as virtual objects such as data.

LEARNING OBJECTIVES
✓ To understand the Stack data structure in Python.

✓ To know how Stacks in Python is constructed.

✓ To understand how data moves in Stacks in Python.

✓ To learn about conversion of infix to postfix expression.

6.1 | STACKS
In the field of computer science, the application of stack is one of the important
and very essential ways in creating data structures. The collected data is to be piled in
order in which the addition/insertion and the deletion of a data item can only be done at
one end or also called the top of the stack. To achieve that way of only inserting and
deleting an item from the top of the stack, the last-in-first-out process is done meaning
the last item element that was added will also be the first item element to be removed.

A stack is a data structure which serves as a collection of elements that are

inserted and deleted according to the LIFO (“LAST IN FIRST OUT”) principle and
performs two principle operations, push (insertion) and pop (deletion).

A LIFO structure where elements are inserted and deleted from the same end. It
is a simple memory mechanism where elements are implemented as an array or linked
list.
A stack is a limited access data structure - elements can be added and removed
from the stack only at the top. push adds an item to the top of the stack, pop removes the

72
item from the top. A helpful analogy is to think of a stack of books; you can remove only
the top book, also you can add a new book on the top.

6.2 | OPERATIONS IN STACKS

There are two operations that can be done in a stack: the push operation and the
pop operation.
●Push – is the process of adding an element into the stack. The most recent element to
be pushed is considered as the element in the top and in which the number of elements
in the stack is incremented by one. A stack overflow error happens if the stack is already
full.
●Pop – is the process of removing an element from the stack. The top element in the
stack will be removed and the number of elements in the stack will be decremented by
one. A stack underflow error happens if the pop operation is done in an empty stack.

Figure 6.2.1. This illustration represents how data moves inside a stack using the
operation Push and Pop. You can also observe the LIFO principle is being applied
since the first number.

6.3 | EVALUATION OF EXPRESSION

●Conversion of infix to postfix expression.
●Computation to postfix. (reverse polish)
In this, the arithmetic operation which is a high-level programming language is
converted into machine language. This is because machines can understand only binary

73
 language (0 and 1). It assumes that an arithmetic operation can take place in two
operands only like A+B, C*D, F/E etc. But the arithmetic expression may contain more
than one operator and many operands like A+(B+C-(D/E^F)*G)*H). These complex
expressions can be converted and can be executed in two operands and an operator
form.

●Infix Expression
In Infix, the operator is preceded and succeeded by an operand.
Example: A+B
●Postfix Expression
In Postfix, the operator is succeeded by both the operands.
Example: AB+

During conversions when several operators occur in an expression, each part is

evaluated and resolved in a particular order called as operator precedence.

^ Exponential

*, / Multiplication, Division

+, - Addition, Subtraction

Example 6.3.1.
Conversion of infix to postfix expression:
●A+(B+C*D)+E → ABCD*+*E+

74
Solution:

Example 6.3.2.
Computation to postfix expression:
●2 3 4 + * 5 * → 70

Solution:

75
6.4 | REVERSING STRINGS
It is one of the simple applications of stack, where characters of string are pushed
onto the stack one by one as the string is read from left to right. Once all characters are
pushed, they are popped out. Since the last character pushed in is the first to be popped
out. Subsequent pop operation results in reversal of strings.
Time Complexity: O (n) where n is the number of characters in stack.

Example 6.4.1.

6.5 | CONVERSION OF DECIMAL TO OTHER NUMBER SYSTEM

Here, the given decimal number is divided by the base (2 or 8 or 16) repeatedly
and the corresponding elements are pushed onto the stack. Then the elements are
popped out of the stack to give the required results.

76
 Figure 6.5.1

6.6 | BACKTRACKING
It is a general algorithm to find solutions to some computational problems. Let us
consider a simple example of a maze. There are several points from starting to
destination. If a random path is chosen, suppose it is wrong there must be a way to reach
the beginning of a point. With stacks, we remember the point where we reached by
pushing that point to stack. In case of a wrong path, pop the last point from the stack and
thus return to the last point and continue to find the right path.

6.7 | PARENTHESIS MATCHING

Given a parenthesized expression, it tests whether the given expression is
parenthesized or not. An opening parenthesis is always pushed on the stack. It is not
removed until a right parenthesis is encountered. If it is encountered, it pops out of the
stack.

77
ACTIVITY
1. It is the procedure of arranging objects or data in an orderly manner.
a. Array c. Stacking
b. Queue-ing d. Sorting
2. What insert and delete principle does the Stacks use?
a. Last in, First out c. First in, Last out
b. Last in, Last out d. First in, First out
3. Which method inserts an element?
a. Pop c. Insert
b. Push d. Append
4. Which method looks at the top element?
a. Push c. isEmpty
b. Pop d. peak

5. Which method removes an element?

a. Push c. Delete
b. Pop d. isEmpty
6. In a stack, if a user tries to remove an element from an empty stack it is called
_________.

78
 a. Overflow c. Empty
b. Underflow d. Crash

7. What is the value of the postfix expression 6 3 2 4 + - *?

a. 40 c. -18
b. 74 d. 1
8. Convert the infix expression into postfix. (A + B) + C / D * E ^ A / B
a. A B + C D / E A ^ * B / + c. A B C D E A B + / * ^
b. A + B C / D E *A ^ B / d. A B + C / D E * A ^ B / +
9. An opening parenthesis is always pushed on the stack.
a. True
b. False
10. During parenthesizing the expression, the operands associated with operators
having higher precedence are first parenthesized.
a. True
b. False

79
 MODULE 7
MODULE 7
Queues

INTRODUCTION
7.1 | WHAT IS QUEUE?
Queue is an abstract data type or a linear data structure, just like stack data
structure, in which the first element is inserted from one end called the REAR(also called
tail), and the removal of the existing element takes place from the other end called
FRONT(also called head). This makes the queue a FIFO (First in First Out) data structure,
which means that element inserted first will be removed first. Which is exactly how the
queue system works in the real world. If you go to a ticket counter to buy movie tickets,
and you are first in the queue, then you will be the first one to get the tickets. The same
case goes for the Queue data structure. Data inserted first, will leave the queue first.

LEARNING OBJECTIVES
✓ To learn about queues in Python.
✓ To know the basic operations, steps, functions and applications of queue.

✓ To learn how to implement queue data structure.

The process to add an element into the queue is called Enqueue and the process
of removal of an element from the queue is called Dequeue.

Figure 7.1.1. Enqueue and Dequeue Operation

80
7.2 | STEPS OF ENQUEUE OPERATION
1. Check if the queue is full or not.
2. If the queue is full, then print an overflow error and exit the program.
3. If the queue is not full, then increment the rear pointer to point to the next empty
space.
4. Add a data element to the queue location, where the rear is pointing.
5. Return success.

7.3 | STEPS OF DEQUEUE OPERATION

1. Check if the queue is empty or not.
2. If the queue is empty, then print an underflow error and exit the program.
3. If the queue is not empty, access the data where the front is pointing.
4. Increment front pointer to point to the next available data element.
5. Return success.

7.4 | BASIC FEATURES OF QUEUE

1. Like stack, queue is also an ordered list of elements of similar data types.
2. Queue is a FIFO (First in First Out) structure.
3. Once a new element is inserted into the Queue, all the elements inserted before the
new element in the queue must be removed, to remove the new element.

7.5 | AUXILIARY QUEUE FUNCTIONS

1. peek() function is often used to return the value of the first element without dequeuing
it.
2. isfull() function is used to check if the queue is full.
3. isempty() function is used to check if the queue is full.
In Python we can add items into a queue using the append() function and we can
also remove items from a queue using the pop() function.

7.6 | DIFFERENT TYPES OF QUEUES

1. Circular Queue – Circular queue is a linear data structure in which the operations
are performed based on FIFO (First in First Out) principle and the last position is
connected back to the first position to make a circle.

81
2. Input Restricted Queue – in this type of Queue, the input can be taken from one
side only (rear) and deletion of elements can be done from both sides (front and rear).
This kind of Queue does not follow FIFO (First in First Out) principle. This queue is used
in the cases where the consumption of the data needs to be FIFO order but and if there
is a need to remove the recently inserted data for some reasons, such cases can be
irrelevant data, performance issues, etc.
3. Output Restricted Queue – In this type of Queue, the input can be taken from both
sides (rear and front) and the deletion of the element can be done from only one side
(front). This queue is used in the case where the inputs have some priority order to be
executed and the input can be placed even in the first place so that it is executed first.
4. Double ended Queue (Dequeue) – Double Ended Queue is also a Queue data
structure in which the insertion and deletion are performed at both the ends (front
and rear). That means, we can insert at both front and rear positions and can delete
from both front and rear positions.
5. Priority Queue – A priority queue is a special type of queue in which each element is
associated with a priority. There are two types of Priority Queues these are:
1. Ascending Priority Queue – Element can be inserted arbitrarily but only
the smallest element can be removed. For example, suppose there is an array
having elements 8, 4, 16 in the same order. So, while inserting the elements,
the insertion will be in the same sequence but while deleting the order will be
4, 8, 16.
2. Descending priority Queue – Elements can be inserted arbitrarily but only the
largest element can be removed first from the given Queue. For example,
suppose there is an array having elements 2, 1, 4 in the same order. So, while
inserting the elements, the insertion will be in the same sequence but while
deleting, the order will be 4, 2, 1.

7.7 | APPLICATIONS OF QUEUE

Queue, as the name suggests is used whenever we need to manage any group of
objects in an order in which the first one coming in, also gets out first while the others wait
for their turn, like in the following scenarios:
1. Serving requests on a single shared resource, like a printer, CPU task
scheduling etc.

82
 2. In real life scenarios, Call Center phone systems use Queues to hold people
calling them in an order, until a service representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the
same order as they arrive i.e First come first served.
7.8 | IMPLEMENTATION OF QUEUE DATA STRUCTURE USING ARRAY
Queue can be implemented using an Array, Stack or Linked List. The easiest way
of implementing a queue is by using an Array. Initially the head (FRONT) and the tail
(REAR) of the queue points at the first index of the array (starting the index of array from
0). As we add elements to the queue, the tail keeps on moving ahead, always pointing to
the position where the next element will be inserted, while the head remains at the first
index.
Example 7.8.1.

83
ACTIVITY
1. Given a circular array-based queue Q capable of holding 7 objects. Show the final
contents of the array after the following code is executed:

Final Answer:

0 1 2 3 4 5 6

2. Given a 5-element queue Q (from front to back: 1, 3, 5, 7, 9), and an empty stack S,
remove the elements one-by-one from Q and insert them into S, then remove them one-
by-one from S and re-insert them into Q. The queue now looks like? (from front to back)

84
 MODULE 8
MODULE 8
Trees

INTRODUCTION
Tree is a kind of a nonlinear data structure where each node in it contains data
and a number of pointers to other nodes in the structure such that no loops exist.
Compared to a real-life tree, it has a root, branches, and leaves. A tree with no any node
is called an empty tree and a singular-node tree for a tree with one node only (that node
is the root node). In programming, there are two main classification of tree data structure.
First one is the General Tree and the other one is the Binary Tree. A General Tree is a
tree where in each node could have zero (0) or more children. On the other hand, a Binary
Tree is a tree where in each node could have no more than two (2) children. However, in
this learning material, we will focus on Binary trees.

LEARNING OBJECTIVES
✓ To understand the Tree data structure in Python.
✓ To learn about Binary Tree data structure.

✓ To learn about different Binary Tree traversal schemes.

✓ To understand Arithmetic Expression Tree in Python.

✓ To know how to implement Binary Search Tree in Python.

✓ To find out different applications of Tree data structure.

8.1 | OVERVIEW OF TREE TERMINOLOGIES

➤ Root: is the node on top of a tree. There is only one root for every tree.
➤ Edge: is the connection between one node to another.

➤ Path: is a sequence of nodes and edges connecting a node with a descendant.

➤ Child/Children Node/s: is/are the node/s below a given node connected by the
respective downward edge.
➤ Parent Node: is the node which acts as a predecessor of any node in the tree.

➤ Leaf Node: is the node that does not have a child node.
➤ Sibling Nodes: are the nodes that come from the same parent node.

85
➤ Ancestor Node: is the node which is connected to all lower-level nodes.
➤ Descendant Node: is the inverse relationship of ancestor nodes. It is the child of the
child node.
➤ Level: is the number of edges from one node to the root node. (Note: The level of the
root node is zero (0))
➤ Height of the Tree: is the number of nodes on the longest path from root to a leaf.

➤ Degree: is the number of nodes connected to a particular parent node.

8.2 | BINARY TREE DATA STRUCTURE

A binary tree in data structure is a tree where in each node could have at most 2
children nodes (namely left and right child nodes). The smaller value items will always be
inserted at the left and the bigger ones will be inserted at the right. The children of the
root node would become the ancestor node of the subtrees. The right subtree contains
all the items with bigger value while the left subtree contains the items with smaller value.

Figure 8.2.1 Example of a Binary Tree

The figure shown above is an example of a binary tree. The following are the
description of the shown binary tree:
• Root Node: 25
• Leaf nodes or the leaves: 5, 12, 22, 28, 38, and 48
• Node 25: Level 0
• Nodes 20 and 36: Level 1
• Nodes 10, 22, 30 and 40: Level 2
• Nodes 5, 12, 28, 38 and 48: Level 3
86
• Height of the tree: 4

8.3 | TYPES OF BINARY TREE

There are two main types of a binary tree, the Complete Binary Tree and Full
Binary Tree. In a complete binary tree, every level, except to the possibly last, is
completely filled, and all nodes in the last level are as far left as possible. On the other
hand, in a full binary tree, every node has either zero (0) or two (2) children nodes.

Figure 8.3.1 Two Main Types of Binary Tree

Example 8.3.2
Given this following set of numbers: 40, 10, 65, 88, 70, 21, 140, 29, 13, 1, 67
Construct the corresponding binary tree.

87
8.4 | BINARY TREE TRAVERSALS
Unlike other data structures which only have one logical way to traverse them,
trees can be traversed in three (3) different orders:
1. Inorder Traversal
2. Preorder Traversal
3. Postorder Traversal
A. In-order Traversal
In the case of Binary Search Trees (BST), Inorder Traversal firstly explores the left
subtree, followed by the root, and lastly, the right subtree. In short, we will follow this
scheme:
Left – Root – Right
B. Pre-order Traversal
In the case of Binary Search Trees (BST), Preorder Traversal firstly explores the
root, followed by the left subtree, and lastly, the right subtree. In short, we will follow this
scheme:
Root – Left – Right
C. Post-order Traversal
In the case of Binary Search Trees (BST), Inorder Traversal firstly explores the left
subtree, followed by the right subtree, and lastly, the root. In short, we will follow this
scheme:
Left – Right – Root

88
Example 8.4.1

In-order Traversal: 1 3 4 6 7 8 10 13 14
1. Starting from the left subtree: 3 1 6 4 7
2. 1 is the left element of the 3 1 6 4 7 left subtree >>> 1 _ _ _ _ _ _ _ _
3. 3 is the root node of the 3 1 6 4 7 left subtree >>> 1 3 _ _ _ _ _ _ _
4. 6 4 7 right subtree is the right element of the 3 1 6 4 7 left subtree.
5. From 6 4 7 right subtree, 4 is the left element >>> 1 3 4 _ _ _ _ _ _
6. From 6 4 7 right subtree, 6 is the root node >>> 1 3 4 6 _ _ _ _ _
7. From 6 4 7 right subtree, 7 is the right element >>> 1 3 4 6 7 _ _ _ _
8. 8 is the root node of 3 1 6 4 7 left and 10 14 13 right subtree >>> 1 3 4 6 7 8 _ _ _
9. From 10 14 13 right subtree, there is neither left element nor left subtree.
10. 10 is the root node >>> 1 3 4 6 7 8 10 _ _
11. 14 13 right subtree is the right element of the 10 14 13 right subtree.
12. From 14 13 right subtree, 13 is the left element >>> 1 3 4 6 7 8 10 13 _
13. From 14 13 right subtree, 14 is the root node >>> 1 3 4 6 7 8 10 13 14
14. In-order Traversal: 1 3 4 6 7 8 10 13 14

89
Example 8.4.2

Pre-order Traversal: 8 3 1 4 16 10 9 13 30 24 32

1. 8 is the root node of the whole tree >>> 8 _ _ _ _ _ _ _ _ _ _

2. 1 3 4 left subtree is the left element of 8 root nodes.
3. From 1 3 4 left subtree, 3 is the root node >>> 8 3 _ _ _ _ _ _ _ _ _
4. From 1 3 4 left subtree, 1 is the left & 4 is the right element >>> 8 3 1 4 _ _ _ _ _ _ _
5. 16 10 30 9 13 24 32 right subtree is the right element of 8 root nodes.
6. From 16 10 30 9 13 24 32 right subtree, 16 is the root >>> 8 3 1 4 16 _ _ _ _ _ _
7. From 16 10 30 9 13 24 32 right subtree, 9 10 13 left subtree is the left element.
8. From 9 10 13 left subtree, 10 is the root node >>> 8 3 1 4 16 10 _ _ _ _ _
9. From 9 10 13 left subtree, 9 is the left element >>> 8 3 1 4 16 10 9 _ _ _ _
10. From 9 10 13 left subtree, 13 is the right element >>> 8 3 1 4 16 10 9 13 _ _ _
11. From 16 10 30 9 13 24 32 right subtree, 24 30 32 right subtree is the right element.
12. From 24 30 32 right subtree, 30 is the root node >>> 8 3 1 4 16 10 9 13 30 _ _
13. From 24 30 32 right subtree, 24 is the left element >>> 8 3 1 4 16 10 9 13 30 24 _
14. From 24 30 32 right subtree, 32 is the right element >>> 8 3 1 4 16 10 9 13 30 24 32
15. Pre-order Traversal: 8 3 1 4 16 10 9 13 30 24 32

90
Example 8.4.3

Post-order Traversal: 7 17 27 22 15 45 75 60 30

1. 7 15 17 27 22 left subtree is the left element of the 30 root node.

2. From 7 15 17 27 22 left subtree, 7 is the left element >>> 7 _ _ _ _ _ _ _ _
3. From 7 15 17 27 22 left subtree, 17 22 27 right subtree is the right element.
4. From 17 22 27 right subtree, 17 is the left element >>> 7 17 _ _ _ _ _ _ _
5. From 17 22 27 right subtree, 27 is the right element >>> 7 17 27 _ _ _ _ _ _
6. From 17 22 27 right subtree, 22 is the root node >>> 7 17 27 22 _ _ _ _ _
7. From 7 15 17 27 22 left subtree. 15 is the root node >>> 7 17 27 22 15 _ _ _ _
8. 45 60 75 right subtree is the right element of the 30 root node.
9. From 45 60 75 right subtree, 45 is the left element >>> 7 17 27 22 15 45 _ _ _
10. From 45 60 75 right subtree, 75 is the right element >>> 7 17 27 22 15 45 75 _ _
11. From 45 60 75 right subtree, 60 is the root node >>> 7 17 27 22 15 45 75 60 _
12. 30 is the root node of 7 15 17 27 22 left subtree and 45 60 75 right subtree.
13. Post-order Traversal: 7 17 27 22 15 45 75 60 30

91
8.5 | ARITHMETIC EXPRESSION TREE
The arithmetic expression tree is a binary tree where all internal nodes correspond
to the operator and all external nodes correspond to the operand. When the given
arithmetic expression tree was traversed in in-order, the output will be an in-fix
expression. When the given arithmetic expression tree was traversed in post-order, the
output will be a post-fix expression. Lastly, when the given arithmetic expression tree was
traversed in pre-order, the output will be a pre-fix expression.

Example 8.5.1
The arithmetic expression tree of: 3 + [(a + 5) * b]

In-order Traversal (In-fix expression): 3 + [(a + 5) * b]

Post-order Traversal (Post-fix expression): 3 a 5 + b * +
Pre-order Traversal (Pre-fix expression): + 3 * + a 5 b

A. In-order Traversal (In-fix expression):

1. From (3 + * + b a 5) tree, 3 is the left element of + root node >>> 3 _ _ _ _ _ _
2. From (3 + * + b a 5) tree, + is the root node >>> 3 + _ _ _ _ _
3. From (3 + * + b a 5) tree, (* + b a 5) right subtree is right element of root node +.
4. From (* + b a 5) right subtree, (+ a 5) left subtree is the of the * root node.
5. From (+ a 5 left) subtree, a is the left element >>> 3 + a _ _ _ _
6. From (+ a 5 left) subtree, + is the root node >>> 3 + a + _ _ _
7. From (+ a 5 left) subtree, 5 is the right element >>> 3 + a + 5 _ _
8. From (* + b a 5) right subtree, * is the root node >>> 3 + a + 5 * _
9. From (* + b a 5) right subtree, b is the right element >>> 3 + a + 5 * b
92
10. Since (* + b a 5) right subtree, put it inside a parenthesis >>> 3 +(a + 5 * b)
11. Since (+ a 5) left subtree, put it inside a parenthesis >>> 3 + ((a + 5) * b)
12. Fix the enclosure of the elements. >>> 3 + [(a + 5) * b]
13. In-order Traversal (In-fix expression): 3 + [(a + 5) * b]
B. Post-order Traversal (Post-fix expression):
1. From (3 + * + b a 5) tree, 3 is the left element of the + root node >>> 3 _ _ _ _ _ _
2. From (3 + * + b a 5) tree, (* + b a 5) right subtree is right element of root node +.
3. From (* + b a 5+ right subtree, (+ a 5) left subtree is the of the * root node.
4. From (+ a 5) left subtree, a is the left element >>> 3 a _ _ _ _ _
5. From (+ a 5 left) subtree, 5 is the right element >>> 3 a 5 _ _ _ _
6. From (+ a 5 left) subtree, + is the root node >>> 3 a 5 + _ _ _
7. From (* + b a 5) right subtree, b is the right element >>> 3 a 5 + b _ _
8. From (* + b a 5) right subtree, * is the root node >>> 3 a 5 + b * _
9. From (3 + * + b a 5) tree, + is the root node >>> 3 a 5 + b * +
10. Post-order Traversal (Post-fix expression): 3 a 5 + b * +
C. Pre-order Traversal (Pre-fix expression):
1. From (3 + * + b a 5) tree, + is the root node >>> + _ _ _ _ _ _
2. From (3 + * + b a 5) tree, 3 is the left element of + root node >>> + 3 _ _ _ _ _
3. From (3 + * + b a 5) tree, (* + b a 5) right subtree is right element of root node +.
4. From (* + b a 5) right subtree, * is the root node >>> + 3 * _ _ _ _
5. From (* + b a 5) right subtree, (+ a 5) left subtree is the of the * root node.
6. From (+ a 5) left subtree, + is the root node >>> + 3 * + _ _ _
7. From (+ a 5) left subtree, a is the left element >>> + 3 * + a _ _
8. From (+ a 5) left subtree, 5 is the right element >>> + 3 * + a 5 _
9. From (* + b a 5) right subtree, b is the right element >>> + 3 * + a 5 b
10. Pre-order Traversal (Pre-fix expression): + 3 * + a 5 b

Example 8.5.2
The arithmetic expression tree of: [x * (y – 2)] / [6 / (z + 1)]

93
 In-order Traversal (In-fix expression): [x * (y – 2)] / [6 / (z + 1)]
Post-order Traversal (Post-fix expression): x y 2 - * 6 z 1 + / /
Pre-order Traversal (Pre-fix expression): / * x – y 2 / 6 + z 1

A. In-order Traversal (In-fix expression):

1. From (/ * x – y 2 / 6 + z 1) tree, (* x – y 2) left subtree is the left element of / root.
2. From (* x – y 2) left subtree, x is the left element of * root >>> x _ _ _ _ _ _ _ _ _ _
3. From (* x – y 2) left subtree, * is the root node >>> x * _ _ _ _ _ _ _ _ _
4. From (* x – y 2) left subtree, (– y 2) right subtree is the right element of * root.
5. From (– y 2) right subtree, y is the left element of – root >>> x * y _ _ _ _ _ _ _ _
6. From (– y 2) right subtree, – is the root node >>> x * y – _ _ _ _ _ _ _
7. From (– y 2) right subtree, 2 is the right element of – root >>> x * y – 2 _ _ _ _ _ _
8. From (/ * x – y 2 / 6 + z 1) tree, / is the root node >>> x * y – 2 / _ _ _ _ _
9. From (/ * x – y 2 / 6 + z 1) tree, (/ 6 + z 1) right subtree is the right element of / root.
10. From (/ 6 + z 1) right subtree, 6 is the left element of / root >>> x * y – 2 / 6 _ _ _ _
11. From (/ 6 + z 1) right subtree, / is the root node >>> x * y – 2 / 6 / _ _ _
12. From (/ 6 + z 1) right subtree, (+ z 1) rights subtree is the right element of / root.
13. From (+ z 1) right subtree, z is the left element of + root >>> x * y – 2 / 6 / z _ _
14. From (+ z 1) right subtree, + is the root node >>> x * y – 2 / 6 / z + _
15. From (+ z 1) right subtree, 1 is the right element >>> x * y – 2 / 6 / z + 1
16. Since (* x – y 2) left subtree, put it inside a parenthesis >>> (x * y – 2) / 6 / z + 1
17. Since (– y 2) right subtree, put it inside a parenthesis >>> (x * (y – 2)) / 6 / z + 1
18. Since (/ 6 + z 1) right subtree, put it inside parenthesis >>> (x * (y – 2)) / (6 / z + 1)

94
19. Since (+ z 1) right subtree, put it inside a parenthesis >>> (x * (y – 2)) / (6 / (z + 1))
20. Fix the enclosure of the elements. >>> [x * (y – 2)] / [6 / (z + 1)]
21. In-order Traversal (In-fix expression): [x * (y – 2)] / [6 / (z + 1)]
B. Post-order Traversal (Post-fix expression):
1. From (/ * x – y 2 / 6 + z 1) tree, (* x – y 2) left subtree is the left element of / root.
2. From (* x – y 2) left subtree, x is the left element of * root >>> x _ _ _ _ _ _ _ _ _ _
3. From (* x – y 2) left subtree, (– y 2) right subtree is the right element of * root.
4. From (– y 2) right subtree, y is the left element of – root >>> x y _ _ _ _ _ _ _ _ _
5. From (– y 2) right subtree, 2 is the right element of – root >>> x y 2 _ _ _ _ _ _ _ _
6. From (– y 2) right subtree, – is the root node >>> x y 2 – _ _ _ _ _ _ _
7. From (* x – y 2) left subtree, * is the root node >>> x y 2 – * _ _ _ _ _ _
8. From (/ * x – y 2 / 6 + z 1) tree, (/ 6 + z 1) right subtree is the right element of / root.
9. From (/ 6 + z 1) right subtree, 6 is left element of / root >>> x y 2 – * 6 _ _ _ _ _
10. From (/ 6 + z 1) right subtree, (+ z 1) right subtree is the right element of / root.
11. From (+ z 1) right subtree, z is the left element of + root >>> x y 2 – * 6 z _ _ _ _
12. From (+ z 1) right subtree, 1 is the right element >>> x y 2 – * 6 z 1 _ _ _
13. From (+ z 1) right subtree, + is the root node >>> x y 2 – * 6 z 1 + _ _
14. From (/ 6 + z 1) right subtree, / is the root node >>> x y 2 – * 6 z 1 + / _
15. From (/ * x – y 2 / 6 + z 1) tree, / is the root node >>> x y 2 – * 6 z 1 + / /
16. Post-order Traversal (Post-fix expression): x y 2 - * 6 z 1 + / /
C. Pre-order Traversal (Pre-fix expression):
1. From (/ * x – y 2 / 6 + z 1) tree, / is the root node >>> / _ _ _ _ _ _ _ _ _ _
2. From (/ * x – y 2 / 6 + z 1) tree, (* x – y 2) left subtree is the left element of / root.
3. From (* x – y 2) left subtree, * is the root node >> / * _ _ _ _ _ _ _ _ _
4. From (* x – y 2) left subtree, x is the left element of * root >> / * x _ _ _ _ _ _ _ _
5. From (* x – y 2) left subtree, (– y 2) right subtree is the right element of * root.
6. From (– y 2) right subtree, – is the root node >>> / * x – _ _ _ _ _ _ _
7. From (– y 2) right subtree, y is the left element of – root >>> / * x – y _ _ _ _ _ _
8. From (– y 2) right subtree, 2 is the right element of – root >>> / * x – y 2 _ _ _ _ _
9. From (/ * x – y 2 / 6 + z 1) tree, (/ 6 + z 1) right subtree is the right element of / root.
10. From (/ 6 + z 1) right subtree, / is the root node >>> / * x – y 2 / _ _ _ _
11. From (/ 6 + z 1) right subtree, 6 is left element of / root >>> / * x – y 2 / 6 _ _ _
12. From (/ 6 + z 1) right subtree, (+ z 1) right subtree is the right element of / root.

95
13. From (+ z 1) right subtree, + is the root node >>> / * x – y 2 / 6 + _ _
14. From (+ z 1) right subtree, z is the left element of + root >>> / * x – y 2 / 6 + z _
15. From (+ z 1) right subtree, 1 is the right element >>> / * x – y 2 / 6 + z 1
16. Pre-order Traversal (Pre-fix expression): / * x – y 2 / 6 + z 1

8.6 | BINARY SEARCH TREE IMPLEMENTATION IN PYTHON

The binary search tree is a node-based binary tree data structure which has the
following properties:
• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s
key.
• The left and right subtree each must also be a binary search tree.
• There must be no duplicate nodes.

Example 8.6.1
The following is a sample Python program which demonstrates how to insert data
in a Binary Search Tree, and how to traverse that tree in pre-order, post-order, and in-
order.
Source Code

96
97
8.7 | APPLICATIONS OF TREE DATA STRUCTURE
The following are some of the applications of tree data structure:
• Manipulate hierarchical data.
• Make information easy to search (see tree traversal).
• Manipulate sorted lists of data.
• As a workflow for compositing digital images for visual effects.
• Router algorithms or the networks to find the best path on the Internet.
• Form of a multi-stage decision-making (see business chess).
• Getting data from API via token-based authentication.

98
ACTIVITY
1. How many root/s is/are there in every tree?
a. 2 c. 1
b. Depends on the type of the tree d. 0
2. It is the node which acts as a child of a child node.
a. Child Node c. Sibling Node
b. Leaf Node d. Descendant Node
3. It is a node-based binary tree data structure.
a. Binary Search Tree c. Complete Binary Tree
b. Full Binary Tree d. Binary Select Tree
4. The _____________ of a node contains only nodes with keys greater than the
node’s key.
a. Left subtree c. Right subtree
b. Binary Tree d. Duplicate Node
5. Which of the following code snippets performs in-order traversal?
a. public void inorder(Tree root) c. public void inorder(Tree root)
{ {
System.out.println(root.data); inorder(root.right);
inorder(root.left); inorder(root.left);
inorder(root.right); System.out.println(root.data);
} }

b. public void inorder(Tree root) d. public void inorder(Tree root)

{ {
System.out.println(root.data); inorder(root.left);
inorder(root.right); System.out.println(root.data);
inorder(root.left); inorder(root.right);
} }
6. In the Arithmetic Expression Tree, all internal nodes correspond to ________.
a. Operand c. Child
b. Operator d. Ancestor

99
For number 7-9:

7. Obtain the Post-order Traversal of the given arithmetic expression tree.

a. [3 + (2 * 9)] – (6 / 4) c. 2 9 * 3 + - 6 4 /
b. - + 3 * 2 9 / 6 4 d. 3 2 9 * + 6 4 / -
8. Obtain the Pre-order Traversal of the given arithmetic expression tree.
a. [3 + (2 * 9)] – (6 / 4) c. 2 9 * 3 + - 6 4 /
b. - + 3 * 2 9 / 6 4 d. 3 2 9 * + 6 4 / -
9. Obtain the In-order Traversal of the given arithmetic expression tree.
a. [3 + (2 * 9)] – (6 / 4) c. 2 9 * 3 + - 6 4 /
b. - + 3 * 2 9 / 6 4 d. 3 2 9 * + 6 4 / -
10. A binary search tree contains values 7, 8, 13, 26, 35, 40, 70, 75. Which one of
the following is a valid post-order sequence of the tree provided the pre-order
sequence is 35, 13, 7, 8, 26, 70, 40 and 75?
a. 8, 7, 26, 13, 40, 75, 70, 35 c. 26, 13, 7, 8, 70, 75, 40, 35
b. 7, 8, 13, 26, 35, 40, 70, 75 d. 7, 8, 26, 13, 75, 40, 70, 35

100
 MODULE 9
MODULE 9
Graphs

INTRODUCTION
In this chapter we will study graphs. Graphs are a more general structure than the
trees we studied in the last chapter; in fact, you can think of a tree as a special kind of
graph. Graphs can be used to represent many interesting things about our world,
including systems of roads, airline flights from city to city, how the Internet is connected,
or even the sequence of classes you must take to complete a major in computer science.
We will see in this chapter that once we have a good representation for a problem, we
can use some standard graph algorithms to solve what otherwise might seem to be a very
difficult problem.

While it is relatively easy for humans to look at a road map and understand the
relationships between different places, a computer has no such knowledge. However, we
can also think of a road map as a graph. When we do so we can have our computer do
interesting things for us. If you have ever used one of the Internet map sites, you know
that a computer can find the shortest, quickest, or easiest path from one place to another.

As a student, you may wonder about the courses you must take in order to get a
major. A graph is a good way to represent the prerequisites and other interdependencies
among courses. Figure 1 shows another graph. This one represents the courses and the
order in which they must be taken to complete a major in computer science.

LEARNING OBJECTIVES
✓ To learn what a graph is and how it is used.
✓ To implement the graph abstract data type using multiple internal
representations.
✓ To see how graphs can be used to solve a wide variety of problems.

101
 Figure A. Prerequisites for a Computer Science Major

9.1 | VOCABULARY AND DEFINITIONS

Now that we have looked at some examples of graphs, we will more formally define
a graph and its components. We already know some of these terms from our discussion
of trees.
• Vertex
- A vertex (also called a “node”) is a fundamental part of a graph. It can have
a name, which we will call the “key.” A vertex may also have additional information. We
will call this additional information the “payload.
• Edge
- An edge (also called an “arc”) is another fundamental part of a graph. An
edge connects two vertices to show that there is a relationship between them. Edges may
be one-way or two-way. If the edges in a graph are all one-way, we say that the graph is
a directed graph, or a digraph. The class prerequisites graph shown above is clearly a
digraph since you must take some classes before others.
• Weight
- Edges may be weighted to show that there is a cost to go from one vertex to
another. For example, in a graph of roads that connect one city to another, the weight on
the edge might represent the distance between the two cities.

Detailed Explanation:

102
 Figure 9.1.1 A Simple example of a Directed Graph

The example graph in Figure 9.1.1 helps illustrate two other key graph terms:
• Path
- A path in a graph is a sequence of vertices that are connected by edges. Formally
we would define a path as w1, w2, ..., wn such that (wi, wi +1) ∈ E for all 1 ≤ i ≤ n−1. The
unweighted path length is the number of edges in the path, specifically n−1.
- The weighted path length is the sum of the weights of all the edges in the path.
- For example in Figure 9.2 the path from V3 to V1 is the sequence of vertices
(V3,V4,V0,V1). The edges are {(v3, v4,7), (v4, v0,1), (v0, v1,5)}.
• Cycle
- A cycle in a directed graph is a path that starts and ends at the same vertex.
For example, in Figure 9.2 the path (V5, V2, V3, V5) is a cycle.

103
 - A graph with no cycles is called an acyclic graph.
- A directed graph with no cycles is called a directed acyclic graph or a DAG.
We will see that we can solve several important problems if the problem can
be represented as a DAG.

9.2 | THE GRAPH ABSTRACT DATA TYPE

The graph abstract data type (ADT) is defined as follows:
• Graph() creates a new, empty graph.
• addVertex(vert) adds an instance of Vertex to the graph.
• addEdge(fromVert, toVert) Adds a new, directed edge to the graph that connects
two vertices.
• addEdge(fromVert, toVert, weight) Adds a new, weighted, directed edge to the
graph that connects two vertices.
• getVertex(vertKey) finds the vertex in the graph named vertKey.
• getVertices() returns the list of all vertices in the graph.
• in returns True for a statement of the form vertex in graph, if the given vertex is in
the graph, False otherwise.

Beginning with the formal definition for a graph there are several ways we can
implement the graph ADT in Python. We will see that there are trade-offs in using different
representations to implement the ADT described above. There are two well-known
implementations of a graph, the adjacency matrix and the adjacency list. We will explain
both of these options, and then implement one as a Python class.

9.3 | ADJACENCY MATRIX

One of the easiest ways to implement a graph is to use a two-dimensional matrix.
In this matrix implementation, each of the rows and columns represent a vertex in the
graph. The value that is stored in the cell at the intersection of row v and column w
indicates if there is an edge from vertex v to vertex w. When two vertices are connected
by an edge, we say that they are adjacent. Figure 9.3 illustrates the adjacency matrix for
the graph in Figure 9.2. A value in a cell represents the weight of the edge from vertex v
to vertex w.

104
 Figure 9.3.1 An Adjacency Matrix Representation for a Graph

The advantage of the adjacency matrix is that it is simple, and for small graphs it
is easy to see which nodes are connected to other nodes. However, notice that most of
the cells in the matrix are empty. Because most of the cells are empty, we say that this
matrix is “sparse.” A matrix is not a very efficient way to store sparse data. In fact, in
Python you must go out of your way to even create a matrix structure like the one in Figure
9.3.

The adjacency matrix is a good implementation for a graph when the number of
edges is large. But what do we mean by large? How many edges would be needed to fill
the matrix? Since there is one row and one column for every vertex in the graph, the
number of edges required to fill the matrix is | V | 2 . A matrix is full when every vertex is
connected to every other vertex. There are few real problems that approach this sort of
connectivity. The problems we will look at in this chapter all involve graphs that are
sparsely connected.

105
9.4 | ADJACENCY LIST
A more space-efficient way to implement a sparsely connected graph is to use an
adjacency list. In an adjacency list implementation, we keep a master list of all the vertices
in the Graph object and then each vertex object in the graph maintains a list of the other
vertices that it is connected to. In our implementation of the Vertex class we will use a
dictionary rather than a list where the dictionary keys are the vertices, and the values are
the weights. Figure 9.4 illustrates the adjacency list representation for the graph in Figure
9.2.

Figure 9.4.1. An Adjacency List Representation of a Graph

The advantage of the adjacency list implementation is that it allows us to compactly

represent a sparse graph. The adjacency list also allows us to easily find all the links that
are directly connected to a particular vertex.

9.5 | GRAPH IMPLEMENTATION IN PYTHON

The advantage of the adjacency list implementation is that it allows us to compactly
represent a sparse graph. The adjacency list also allows us to easily find all the links that
are directly connected to a particular vertex.

106
Example 9.5.1
Using dictionaries, it is easy to implement the adjacency list in Python. In our
implementation of the Graph abstract data type we will create two classes (see Listing 1
and Listing 2), Graph, which holds the master list of vertices, and Vertex, which will
represent each vertex in the graph.

Each Vertex uses a dictionary to keep track of the vertices to which it is connected,
and the weight of each edge. This dictionary is called connectedTo. The listing below
shows the code for the Vertex class. The constructor simply initializes the id, which will
typically be a string, and the connectedTo dictionary. The addNeighbor method is used
to add a connection from this vertex to another. The getConnections method returns all
of the vertices in the adjacency list, as represented by the connectedTo instance
variable. The getWeight method returns the weight of the edge from this vertex to the
vertex passed as a parameter.

Listing Explanation:
The Graph class, shown in the next listing, contains a dictionary that maps vertex
names to vertex objects. In Figure 9.4, this dictionary object is represented by the shaded

107
gray box. Graph also provides methods for adding vertices to a graph and connecting
one vertex to another.

The getVertices method returns the names of all of the vertices in the graph. In
addition, we have implemented the __iter__ method to make it easy to iterate over all the
vertex objects in a particular graph. Together, the two methods allow you to iterate over
the vertices in a graph by name, or by the objects themselves.

Using the Graph and Vertex classes just defined, the following Python session
creates the graph in Figure 9.2.

108
Steps to reproduce:
First, we create six vertices numbered 0 through 5. Then we display the vertex
dictionary. Notice that for each key 0 through 5 we have created an instance of a Vertex.
Next, we add the edges that connect the vertices together. Finally, a nested loop verifies
that each edge in the graph is properly stored. You should check the output of the edge
list at the end of this session against Figure 9.2.

Example 9.5.1

Example 9.5.2
In this example, we will see how to implement graphs in Python using dictionary
data structure in Python. The keys of the dictionary used are the nodes of our graph and
the corresponding values are lists with each node, which are connected by an edge.
This simple graph has six nodes (a-f) and five arcs:
109
a -> c
b -> c
b -> e
c -> a
c -> b
c -> d
c -> e
d -> c
e -> c
e -> b
It can be represented by the following Python data structure. This is a dictionary
whose keys are the nodes of the graph. For each key, the corresponding value is a list
containing the nodes that are connected by a direct arc from this node.

Python representation:

Graphical representation of the graph:

Python function to generate a graph:

110
Python program for validation of a graph:

Example 9.5.2 OUTPUT

111
ACTIVITY
1. Which of the following statements for a simple graph is correct?
a) Every path is a trail.
b) Every trail is a path.
c) Every trail is a path as well as every path is a trail.
d) Path and trail have no relation.
2. In a simple graph, the number of edges is equal to twice the sum of the degrees of
the vertices.
a) True
b) False
3. Which of the following properties does a simple graph not hold?
a) Must be connected
b) Must be unweighted
c) Must have no loops or multiple edges
d) Must have no multiple edges
4. For a given graph G having v vertices and e edges which is connected and has no
cycles, which of the following statements is true?
a) v=e c) v + 1 = e
b) v = e+1 d) v = e-1
5. In a simple graph, the number of edges is equal to twice the sum of the degrees of
the vertices.
a) True
b) False
6. What is the number of edges present in a complete graph having n vertices?
a) (n*(n+1))/2 c) n
b) (n*(n-1))/2 d) Information given is insufficient
7. Which of the following is true?
a) A graph may contain no edges and many vertices.
b) A graph may contain many edges and no vertices.
c) A graph may contain no edges and no vertices.
d) A graph may contain no vertices and many edges.
112
8. If a simple graph G, contains n vertices and m edges, the number of edges in the
Graph G'(Complement of G) is ___________
a) (n*n-n-2*m)/2 c) (n*n-n-2*m)/2
b) (n*n+n+2*m)/2 d) (n*n-n+2*m)/2
9. The given Graph is regular.

a) True
b) False

10. For the given graph(G), which of the following statements is true?

a) G is a complete graph.
b) G is not a connected graph.
c) The vertex connectivity of the graph is 2.
d) The edge connectivity of the graph is 1.

113
 MODULE 10
MODULE 10

Complexities in Algorithm

10.1 | PROPERTIES OF ALGORITHM

Algorithms generally share a set of properties.
● Correctness
An algorithm must produce the correct output values for all legal input instances of
the problem.
● Input
To solve the computational problem and generate some output, an algorithm must
supply zero or some finite input values externally for a specified set. In order to
produce the output, the input data is transformed during the computation.
● Output
After applying some operation on the given set of input values, the algorithm
produces some infinite or finite set of outputs. The output values are the solution. The
output can be anything from data returned to the calling algorithm, the message
displayed, the calculation printed, and it is possible that there is no output.
● Finiteness
If steps such that an algorithm must be a well-defined, ordered series of
instructions, the algorithm must be terminated after performing the finite number.
● Definiteness
In order for the operation to be done without any doubt, each step of an algorithm
must be explicit and unambiguous. For instance, the same symbol should not be used in
the algorithm to indicate both multiplication and division in two different locations.
● Effectiveness
Each step must be properly executed by the algorithm and hence time tends to be
more important in measuring the effectiveness of an algorithm in a finite amount of time
where the notion that considers minimization of the used space. The space and other
resources taken up by the algorithm also play a critical role in the algorithm's
effectiveness. After converting the algorithm into a computer program, it is when
effectiveness is accurately calculated.
● Multiple availability

114
 Several algorithms for solving the same problem may exist - with different
properties. Same algorithm may be represented in different ways showing the flexibility
of the algorithm.

LEARNING OBJECTIVES
✓ Define what is Complexities in Algorithms.

✓ Learn how to apply different types of Complexities of Algorithms in Python.

✓ To give ideas of what are the two types of complexities in algorithms.

✓ To know the purpose of algorithmic complexity is to quantify how performance

will be impacted as the size of the input changes, not the resources required for
each unit of input data.
✓ To visually see the complexity of the source code for an algorithm, including
length, constant time, linear time, quadratic time, exponentiation time,
factorial time and linear space complexities.
✓ To understand the uses of Time and Space Complexities in real world
examples.

10.2 | VARIOUS STEPS IN DEVELOPING ALGORITHM

Devising the Algorithm
It is a strategy for solving a problem. It is important to describe each step of an
algorithm clearly and unambiguous expressions can be used. In a less formal
language than a programming language such as pseudo code—is being used to
define the algorithm.
Validating the Algorithm
The process of checking the algorithm's correctness. By providing the necessary
input, using the algorithm and having the required output in a finite amount of time, a
person must be able to execute any step using paper and pencil.
Expressing the Algorithm
In a programming language, to execute the algorithm— after a finite number of
operations, the algorithm used should terminate.

115
10.3 | EFFICIENCY OF AN ALGORITHM
● What any programmer hopes to be able to do is to write successful programs, but
what sort of programs are effective? The question contributes to the notion of program
generalization.
● A property of an algorithm that refers to the amount of computing resources utilized by
the algorithm is algorithmic efficiency. To evaluate the system efficiency, an algorithm
must be evaluated, and the performance of an algorithm should be calculated depending
on the use of multiple resources.
● In addition, algorithms are applications. An algorithm is a concept that a program is
based upon. Three aspects should fulfill an algorithm:
-It should be independent of the programming language in which the idea is realized
-Every programmer having enough knowledge and experience should understand it.
-It should be applicable to inputs of all sizes.
● Algorithm efficiency denotes the pace at which a problem of size n is solved by an
algorithm.
● It is calculated by the sum of resources, time and space that it consumes. We would
like to minimize resource consumption for optimum algorithm performance. It is not
possible to compare important resources such as time and space complexity directly, so
time and space complexity should be taken into consideration for algorithmic efficiency.
● The times refers to the number of steps the algorithm executes while the space refers
to the number of unit memory storage it requires.
● The complexities of an algorithm are calculated by measuring the time taken and
space needed for the algorithm to be completed.
● One parameter is the input size, denoted by n, used to define the problem example.
● The input size n is the number of registers needed to hold the input (data segment size).

10.4 | WHAT IS COMPLEXITY IN ALGORITHM

● Complexity of algorithms is a metric that evaluates the order of the count of operations
performed as a function relative to the size of the input data by a given algorithm.
Algorithm complexity is a rough estimate of the number of steps taken for an algorithm to
be executed.
● Algorithmic complexity is a measure of how long, given an input of size n, it will take an
algorithm to complete. If an algorithm needs to scale, even for large values of n, it can

116
measure the outcome within a finite and reasonable time limit. For this cause, complexity
is asymptotically measured as infinity approaches n. Although complexity is typically in
regards to time, complexity is often evaluated in terms of space, which corresponds to
the memory requirements of the algorithm.

10.5 | TYPES OF COMPLEXITIES IN ALGORITHM

There are two types of complexities namely, Time, and Space Complexities.
1. Time Complexity
An algorithm's time complexity is the amount of time (or number of steps) taken by
a program to complete its task (to execute a particular algorithm). The method in which
an algorithm involves the number of steps varies with the scale of the issue it solves.

The complexity of time relies on a variety of factors, such as hardware, operating

systems, processors, etc. However, when evaluating the algorithm, we do not consider
any of these variables. We can only consider the execution time of an algorithm. The time
taken for an algorithm is comprised of two times; compilation time, and run time.

Compilation time is the time needed for an algorithm to be compiled. Your program
has called for syntax and semantic errors in the programs before compiling it, and
connects it to the standard libraries.

a. Worst Case: For a given problem, to achieve a desired outcome, it is the longest
time that an algorithm can use for all instances of size n.
b. Average Case: The algorithm would use the average time for a given problem to
achieve a desired outcome for all instances of size n.
c. Best Case: The algorithm would use the shortest time for a given problem to obtain a
desired outcome for all instances of size n.

Real world example that varies the efficiency of computation time:

-sorting a deck of playing cards (using merge sort)
-checking if you have everything on your shopping list in your trolley
-determining if a number is odd or even
-finding a word in the dictionary

117
-counting the stars in the universe
2. Space Complexity
The total amount of memory space that an algorithm/program requires, plus the
execution space of input values. So, it is enough to measure the space occupied by the
variables used in an algorithm/program to find space-complexity.

The way in which the amount of storage space is required by an algorithm varies with the
size of the problem to be solved. The space occupied by the program is generally by the
following:

The space for the computer code and the space used by the variables in the program
share a set amount of memory.

The variable amount of memory that the element variable occupies, the size of which
depends on the problem being resolved. Based on whether iterative or recursive
processes are used by the code, this space increases or decreases.

The usage of memory is not under the programmer's control, since a program totally
reliant on the compiler to allocate this memory.

But the memory space taken but the variables is in the control of a programmer. More the
number of variables used, more will be space taken by them in the memory, but the
memory space is taken, but a programmer's influence is over the
program’s variable. The higher the number of variables used, the more memory space
they can take up.

Space complexity is normally expressed as an order of magnitude, eg 𝑂(𝑛 2 ) means

that if the size of the problem n doubles then four times as much working storage will
be needed.

For determining the amount of memory used by the algorithm, three distinct
spaces are considered:

118
Instruction space is the amount of memory used to save the compiled version of
instructions. We consider this space as a fixed space for some value n. Normally, this
value is overlooked, but note that it is there. The instruction space is independent of the
size of the problem.

Data space is the space in memory that is used to store the data structures, amount
of space used by the variables and constants.. Memory allocated and other elements
of data. The data space is connected to the problem's scale.

Environment space is the space in the memory that is used for each function call on the
run time stack. This is connected to the run time stack and contains the previous function's
return address. As any object on the stack has a return value and a pointer on it, the
memory that each method uses on the stack is a constant. Often it is possible to call an
algorithm within another algorithm. The current variables are moved onto the system
stack in such a case, where they wait for further execution and then the call is made to
the inside algorithm.

Real world example that varies the of usage of space:

- Answering long math equations on a ¼ sheet of paper.
- Using all various colors to fit in a wall mural

10.6 | WHAT IS BIG-O NOTATIONS

The most common metric for the measurement of time complexity is the Big O
notation. In comparison to the number of steps needed to achieve it, it defines the
execution time of a task. The Big O notation is written in the form of O(n), where O
stands for "order of magnitude" and n represents the complexities of a task to which
we measure. One of several algorithms, each with differing complexity and scalability
over time, can be used to manage a task.

The general step wise procedure for Big-O runtime analysis is as follows:
-Figure out what the input is and what n represents.
-Express the maximum number of operations the algorithm performs in terms of n.
-Eliminate all excluding the highest order terms.

119
-Remove all the constant factors.
3. Constant Complexity O(1)
It has the least complexity where the constant time of a constant task would not
change no matter what the input value is. Consider a feature in an array that prints a
value. Regardless of the importance of which element you ask the function to print, only
one move is needed. So we can assume that the function is running at O(1) time; it does
not increase its run-time. Its magnitude order is always 1.
4. Linear Complexity: O(n)
The running time of a linear task can vary depending on its input value. If you ask
a function to print all the elements in a 10-element array, it will take fewer steps than a
10,000 element array to complete. This is said to run at O(n); its runtime increases at a
magnitude equal to n.
5. Exponential: O(2^N)
There are a number of steps needed for a quadratic task equal to the square of its
input value. A function that takes an array and N as it is an input value where N is the
array's number of values. using a nested loop, all of which use N as their limit condition,
and I ask the function to print the contents of the array, the function will print N rounds for
a total of N^2 print steps, each round printing N rows.
6. Logarithmic: O(log(N))
O(log(n)) is more complex than O(1), The time is reduced at an inversely
proportional magnitude to N instead of increasing the time it takes to execute each
corresponding step. Only half of a progressively smaller data set per step is analyzed by
a logarithmic algorithm that conducts a binary search. The algorithm begins by looking
for half of the entire data set, an ascending ordered set of numbers. If the number is not
identified, it discards the just-checked set and then looks for half of the remaining number
set.

10.7 | TIME COMPLEXITIES APPLICATION SAMPLES

1. Constant Time Complexity— O(1) (read as O of 1)
-An algorithm/code where the efficiency of execution is not impacted by the
size of the input.
OBSERVE AND LEARN!!

120
 We are finding the first and the last element of the list directly by accessing the list
index. The size of the list does not have an impact on the operational efficiency of the
logic.

2. Linear Time Complexity— O(n) (read as O of n)

An algorithm/code where the operational execution time increases linearly with the
increase in the size of the input.
LET US OBSERVE AND LEARN!!
Now, we are adding all the elements of a list by traversing from its first element till
its last element. Hence, the longer the input (list), the more time it will take to execute this
code. The operational execution time increases linearly with the increase in the size of
the input.

121
3. Quadratic Time Complexity— O(n2) (read as O of n squared)
An algorithm/code where, for each of its input, another O(n) complexity code is to
be executed. In such cases, usually, the input is traversed twice or the code has nested
loops that traverse twice of n times.
OBSERVE AND LEARN!!
We are adding all the elements of N*N matrix. Here we traverse twice N times to
reach every single element. Thus, this contains two O(n) executions, making it an O(n2)
operational execution time.

122
4. Exponentiation Time Complexity O(2n) (read as O of 2 raised to n)
-An algorithm/code where the operational time increases in exponentiations as the
input increases. The nature of these algorithms is such that every increase in the size of
input causes a huge increase in operational complexity, being low initially and then
drastically increased with the increase in the input size.
OBSERVE AND LEARN!!
We are calling the Fibonacci fun function recursively to calculate the sum of
Fibonacci numbers up to its input parameter. The complexity of execution increases in
exponentiation fashion as we call the function recursively with every increase in the size
of the input to generate the Fibonacci series.

The below table indicates the number of recursive calls per input series. As you can see
at each step the operational complexity increases almost exponentially.

123
5. Logarithmic Time Complexity O(log n) (read as O of log n)
An algorithm/code where with every iteration, the size of the relevant input
keeps on reducing. In such cases with every iteration, the relevant input keeps on
becoming smaller and smaller.
OBSERVE AND LEARN!!
Below is the code of binary search. Here, with every iteration, the search is
narrowed down to half the size of input than the size of the input in its previous iteration
as depicted in the below table.

124
6. Quasilinear Time Complexity O(n log n) (read as O of n log n)
An algorithm/code where every iteration further has a Logarithmic O(log n)
complexity.
OBSERVE AND LEARN!!
Now, we are traversing through an array and for every array item, we are calling a
binary search function that has O(log n) complexity. Thus, this code possesses a log n
complexity that has to be executed n times. Hence it has O(n log n) time complexity.

125
7. Factorial Time Complexity O(n!) (read as — O of n factorial)
-An algorithm/code where the operational execution complexity increases
factorially with the increase in the input size is said to have a Factorial Time complexity.
OBSERVE AND LEARN!!
The code below aims to find factorial of a number recursively has Factorial time
complexity as the operational execution increases exponentially as the size of input
increases. The solution to those problem statements where permutation is involved would
in most cases possess Factorial time complexity.

126
10.8 | SPACE COMPLEXITIES APPLICATION SAMPLES

As we can see in the above expression, variables a, b, c and z are all integer
types, hence they will take up 4 bytes each, so total memory requirement will be (4(4) +
4) = 20 bytes, this additional 4 bytes is for return value. And because this space
requirement is fixed for the above example, hence it is called Constant Space Complexity.

Example 10.8.1

● In the above code, 4*n bytes of space is required for the array a[] elements.
● 4 bytes each for x, n, i and the return value.

Hence the total memory requirement will be (4n + 12), which is increasing linearly
with the increase in the input value n, hence it is called Linear Space Complexity.
Similarly, we can have quadratic and other complex space complexity as well, as
the complexity of an algorithm increases.
But we should always focus on writing algorithm code in such a way that we keep
the space complexity minimum.

127
SUMMARY
Measurement of algorithm complexity should be part of the method of design. The
software developer must provide an accessible way to grasp the complexity of an
algorithm in simple terms and come up with feasible and effective ways to simplify it where
possible in order to calculate how complicated an algorithm is and to be able to spot the
necessary sections of the composition of the algorithm in order to overcome anomalies
in algorithm design and review. Without discussing the word "algorithm complexity" we
will not speak about the performance of algorithms and data structures because both are
inherently related. We consider time complexity and space complexity mainly when
evaluating an algorithm. An algorithm's time complexity quantifies the amount of time an
algorithm takes to run as a function of the input's length. Similarly, an algorithm's space
complexity quantifies the amount of space or memory an algorithm requires to run as a
function of the length of the input. It is necessary to calculate the number of operations or
steps that the algorithm will take when attempting to describe the performance of an
algorithm in terms of execution time, irrespective of some individual program or machine,
it is where the Big-O Notation is bestowed. If each of these steps is assumed to be a
simple unit of computation, then the execution time for an algorithm can be expressed as
the number of steps needed to solve the problem. It can be a difficult problem to settle on
an effective simple computation unit which would depend on how the algorithm is applied.

ACTIVITY
1. What is the worst case time complexity of a linear search algorithm?
a. O(1) c. O(log n)
b. O(n) d. O (n2)
2. An algorithm is
a. a piece of code to be executed
b. a loosely written code to make final code
c. a step by step procedure to solve problem
d. all of the above
3. What is the worst case run-time complexity of a binary search algorithm?
a. O(n2) c. O(n3)
b. O(nlog n) d. O (n)

128
4. Program with the highest run-time complexity is
a. Tower of Hanoi c. Prime Numbers
b. Fibonacci Sequence d. None of the Above
5. The two main measures for the efficiency of an algorithm are:
a. Processor and Memory c. Time and Space
b. Complexity and Capacity d. Data and Space

129