UNIT I ABSTRACT DATA TYPES

Data Structures
A data structure is a specialized format for organizing, processing, retrieving and storing data.
There are several basic and advanced types of data structures, all designed to arrange data to
suit a specific purpose. Data structures make it easy for users to access and work with the
data they need in appropriate ways. Most importantly, data structures frame the organization
of information so that machines and humans can better understand it.

Algorithm

An Algorithm is step by step set of instruction to process the data for a specific purpose. So,
an algorithm utilises various data structures in a logical way to solve a specific computing
problem.

From the data structure point of view, following are some important categories of algorithms
−
 Search − Algorithm to search an item in a data structure.
 Sort − Algorithm to sort items in a certain order.
 Insert − Algorithm to insert item in a data structure.
 Update − Algorithm to update an existing item in a data structure.
 Delete − Algorithm to delete an existing item from a data structure.

Characteristics of an Algorithm

Not all procedures can be called an algorithm. An algorithm should have the following
characteristics −
 Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or
phases), and their inputs/outputs should be clear and must lead to only one meaning.
 Input − An algorithm should have 0 or more well-defined inputs.
 Output − An algorithm should have 1 or more well-defined outputs, and should
match the desired output.
 Finiteness − Algorithms must terminate after a finite number of steps.
 Feasibility − Should be feasible with the available resources.
 Independent − An algorithm should have step-by-step directions, which should be
independent of any programming code.

How to Write an Algorithm?

There are no well-defined standards for writing algorithms. Rather, it is problem and resource
dependent. Algorithms are never written to support a particular programming code.
As we know that all programming languages share basic code constructs like loops (do, for,
while), flow-control (if-else), etc. These common constructs can be used to write an
algorithm.

1
We write algorithms in a step-by-step manner, but it is not always the case. Algorithm
writing is a process and is executed after the problem domain is well-defined. That is, we
should know the problem domain, for which we are designing a solution.
Example
Let's try to learn algorithm-writing by using an example.
 Problem − Design an algorithm to add two numbers and display the result.
step 1 − START
step 2 − declare three integers a, b & c
step 3 − define values of a & b
step 4 − add values of a & b
step 5 − store output of step 4 to c
step 6 − print c
step 7 − STOP
Algorithms tell the programmers how to code the program. Alternatively, the algorithm can
be written as −
step 1 − START ADD
step 2 − get values of a & b
step 3 − c ← a + b
step 4 − display c
step 5 − STOP

General Data Structures

The various data structures in computer science are divided broadly into two categories
Liner Data Structures
These are the data structures which store the data elements in a sequential manner.
 Array − It is a sequential arrangement of data elements paired with the index of the
data element.
 Linked List − Each data element contains a link to another element along with the
data present in it.
 Stack − It is a data structure which follows only to specific order of operation.
LIFO(last in First Out) or FILO(First in Last Out).
 Queue − It is similar to Stack but the order of operation is only FIFO(First In First
Out).
 Matrix − It is two dimensional data structure in which the data element is referred by
a pair of indices.

2
Non-Liner Data Structures
These are the data structures in which there is no sequential linking of data elements. Any
pair or group of data elements can be linked to each other and can be accessed without a strict
sequence.
 Binary Tree − It is a data structure where each data element can be connected to
maximum two other data elements and it starts with a root node.
 Heap − It is a special case of Tree data structure where the data in the parent node is
either strictly greater than/ equal to the child nodes or strictly less than it’s child
nodes.
 Hash Table − It is a data structure which is made of arrays associated with each other
using a hash function. It retrieves values using keys rather than index from a data
element.
 Graph − It is an arrangement of vertices and nodes where some of the nodes are
connected to each other through links.

Python Specific Data Structures

These data structures are specific to python language and they give greater flexibility in
storing different types of data and faster processing in python environment.
 List − It is similar to array with the exception that the data elements can be of
different data types. You can have both numeric and string data in a python list.
 Tuple − Tuples are similar to lists but they are immutable which means the values in
a tuple cannot be modified they can only be read.
 Dictionary − The dictionary contains Key-value pairs as its data elements.
Python - Arrays
Array is a container which can hold a fix number of items and these items should be of the
same type. Most of the data structures make use of arrays to implement their algorithms.
Following are the important terms to understand the concept of Array are as follows −
 Element − Each item stored in an array is called an element.
 Index − Each location of an element in an array has a numerical index, which is used
to identify the element.

Array Representation

Arrays can be declared in various ways in different languages. Below is an illustration.

3
As per the above illustration, following are the important points to be considered −
 Index starts with 0.
 Array length is 10, which means it can store 10 elements.
 Each element can be accessed via its index. For example, we can fetch an element at
index 6 as 9.

Basic Operations

The basic operations supported by an array are as stated below −

 Traverse − print all the array elements one by one.
 Insertion − Adds an element at the given index.
 Deletion − Deletes an element at the given index.
 Search − Searches an element using the given index or by the value.
 Update − Updates an element at the given index.
Array is created in Python by importing array module to the python program. Then, the array
is declared as shown below −

Typecode are the codes that are used to define the type of value the array will hold. Some
common typecodes used are as follows –

4
Output

Accessing Array Element

We can access each element of an array using the index of the element. The below code
shows how to access an array element.
Example

Output

Insertion Operation

5
Insert operation is to insert one or more data elements into an array. Based on the
requirement, a new element can be added at the beginning, end, or any given index of array.
Example
Here, we add a data element at the middle of the array using the python in-built insert()
method.

Deletion Operation

Deletion refers to removing an existing element from the array and re-organizing all elements
of an array.
Example
Here, we remove a data element at the middle of the array using the python in-built remove()
method.

6
Output

Search Operation

You can perform a search for an array element based on its value or its index.
Example
Here, we search a data element using the python in-built index() method.

Output

Update Operation

Update operation refers to updating an existing element from the array at a given index.
Example
Here, we simply reassign a new value to the desired index we want to update.

7
Output

Python - Lists
The list is a most versatile datatype available in Python which can be written as a list of
comma-separated values (items) between square brackets. Important thing about a list is that
items in a list need not be of the same type.
Creating a list is as simple as putting different comma-separated values between square
brackets.

Similar to string indices, list indices start at 0, and lists can be sliced, concatenated and so on.

Accessing Values

To access values in lists, use the square brackets for slicing along with the index or indices to
obtain value available at that index.

Updating Lists

8
You can update single or multiple elements of lists by giving the slice on the left-hand side of
the assignment operator, and you can add to elements in a list with the append() method.

OUTPUT

Delete List Elements

To remove a list element, you can use either the del statement if you know exactly which
element(s) you are deleting or the remove() method if we do not know.

Output

9
Basic List Operations

Lists respond to the + and * operators much like strings; they mean concatenation and
repetition here too, except that the result is a new list, not a string.

Python - Tuples
A tuple is a sequence of immutable Python objects. Tuples are sequences, just like lists. The
differences between tuples and lists are, the tuples cannot be changed unlike lists and tuples
use parentheses, whereas lists use square brackets.
Creating a tuple is as simple as putting different comma-separated values. Optionally you can
put these comma-separated values between parentheses also.

The empty tuple is written as two parentheses containing nothing −

tup1 = ();
To write a tuple containing a single value you have to include a comma, even though there is
only one value −
tup1 = (50,);

Accessing Values in Tuples

To access values in tuple, use the square brackets for slicing along with the index or indices
to obtain value available at that index.

10
Updating Tuples

Tuples are immutable which means you cannot update or change the values of tuple
elements. You are able to take portions of existing tuples to create new tuples as the
following example demonstrates −

Delete Tuple Elements

Removing individual tuple elements is not possible. There is, of course, nothing wrong with
putting together another tuple with the undesired elements discarded.
To explicitly remove an entire tuple, just use the del statement.
11
Output

Basic Tuples Operations

Tuples respond to the + and * operators much like strings; they mean concatenation and
repetition here too, except that the result is a new tuple, not a string.

Python - Dictionary
In Dictionary each key is separated from its value by a colon (:), the items are separated by
commas, and the whole thing is enclosed in curly braces. An empty dictionary without any
items is written with just two curly braces, like this − {}.
Keys are unique within a dictionary while values may not be. The values of a dictionary can
be of any type, but the keys must be of an immutable data type such as strings, numbers, or
tuples.

12
Accessing Values in Dictionary

To access dictionary elements, you can use the familiar square brackets along with the key to
obtain its value.
Example

Output

Updating Dictionary

You can update a dictionary by adding a new entry or a key-value pair, modifying an existing
entry, or deleting an existing entry as shown below in the simple example

Delete Dictionary Elements

13
You can either remove individual dictionary elements or clear the entire contents of a
dictionary. You can also delete entire dictionary in a single operation.
Example
To explicitly remove an entire dictionary, just use the del statement. A simple example is as
mentioned below −

Properties of Dictionary Keys

Dictionary values have no restrictions. They can be any arbitrary Python object, either
standard objects or user-defined objects. However, same is not true for the keys.
There are two important points to remember about dictionary keys −
 More than one entry per key not allowed. Which means no duplicate key is allowed.
When duplicate keys encountered during assignment, the last assignment wins.

14
 Python - 2-D Array
Two dimensional array is an array within an array. It is an array of arrays. In this type of
array the position of an data element is referred by two indices instead of one. So it represents
a table with rows an dcolumns of data.
In the below example of a two dimensional array, observer that each array element itself is
also an array.
Consider the example of recording temperatures 4 times a day, every day. Some times the
recording instrument may be faulty and we fail to record data.

Accessing Values

The data elements in two dimesnional arrays can be accessed using two indices. One index
referring to the main or parent array and another index referring to the position of the data
element in the inner array.If we mention only one index then the entire inner array is printed
for that index position.

15
Example

Output

Inserting Values

We can insert new data elements at specific position by using the insert() method and
specifying the index.
Example

Output

Updating Values

We can update the entire inner array or some specific data elements of the inner array by
reassigning the values using the array index.

16
Example

Output

Deleting the Values

We can delete the entire inner array or some specific data elements of the inner array by
reassigning the values using the del() method with index.

Output

17
Time Complexity

Time Complexity of an algorithm is the representation of the amount of time required by the
algorithm to execute to completion.

Space Complexity

Space complexity of an algorithm represents the amount of memory space needed the
algorithm in its life cycle.

Abstract Data Types

Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set
of values and a set of operations. The definition of ADT only mentions what operations are
to be performed but not how these operations will be implemented. It does not specify how
data will be organized in memory and what algorithms will be used for implementing the
operations. It is called “abstract” because it gives an implementation-independent view.

Python OOPs Concepts

Like other general-purpose programming languages, Python is also an object-oriented
language since its beginning. It allows us to develop applications using an Object-Oriented
approach. In Python, we can easily create and use classes and objects.

An object-oriented paradigm is to design the program using classes and objects. The object is
related to real-world entities such as book, house, pencil, etc. The oops concept focuses on
writing the reusable code. It is a widespread technique to solve the problem by creating
objects.

Major principles of object-oriented programming system are given below.

o Class
o Object
18
 o Method
o Inheritance
o Polymorphism
o Data Abstraction
o Encapsulation

Class

The class can be defined as a collection of objects. It is a logical entity that has some specific
attributes and methods. For example: if you have an employee class, then it should contain an
attribute and method, i.e. an email id, name, age, salary, etc.

Object

The object is an entity that has state and behavior. It may be any real-world object like the
mouse, keyboard, chair, table, pen, etc.

Everything in Python is an object, and almost everything has attributes and methods. All
functions have a built-in attribute __doc__, which returns the docstring defined in the
function source code.

When we define a class, it needs to create an object to allocate the memory. Consider the
following example.

In the above example, we have created the class named car, and it has two attributes
modelname and year. We have created a c1 object to access the class attribute. The c1 object
will allocate memory for these values.

19
Example program for both class and objects

Method

The method is a function that is associated with an object. In Python, a method is not unique
to class instances. Any object type can have methods.

Inheritance

Inheritance is the most important aspect of object-oriented programming, which simulates the
real-world concept of inheritance. It specifies that the child object acquires all the properties
and behaviors of the parent object.

By using inheritance, we can create a class which uses all the properties and behavior of
another class. The new class is known as a derived class or child class, and the one whose
properties are acquired is known as a base class or parent class.

It provides the re-usability of the code.

Polymorphism

Polymorphism contains two words "poly" and "morphs". Poly means many, and morph
means shape. By polymorphism, we understand that one task can be performed in different
ways. For example - you have a class animal, and all animals speak. But they speak
differently. Here, the "speak" behavior is polymorphic in a sense and depends on the animal.
So, the abstract "animal" concept does not actually "speak", but specific animals (like dogs
and cats) have a concrete implementation of the action "speak".

Encapsulation

20
Encapsulation is also an essential aspect of object-oriented programming. It is used to restrict
access to methods and variables. In encapsulation, code and data are wrapped together within
a single unit from being modified by accident.

Data Abstraction

Data abstraction and encapsulation both are often used as synonyms. Both are nearly
synonyms because data abstraction is achieved through encapsulation.

Abstraction is used to hide internal details and show only functionalities. Abstracting
something means to give names to things so that the name captures the core of what a
function or a whole program does.

Object-oriented vs. Procedure-oriented Programming languages

The difference between object-oriented and procedure-oriented programming is given below:

Python Class and Objects

Class

The class can be defined as a collection of objects. It is a logical entity that has some specific
attributes and methods. For example: if you have an employee class, then it should contain an
attribute and method, i.e. an email id, name, age, salary, etc.

21
Suppose a class is a prototype of a building. A building contains all the details about the
floor, rooms, doors, windows, etc. we can make as many buildings as we want, based on
these details. Hence, the building can be seen as a class, and we can create as many objects of
this class.

On the other hand, the object is the instance of a class. The process of creating an object can
be called instantiation.

Creating classes in Python

In Python, a class can be created by using the keyword class, followed by the class name. The
syntax to create a class is given below.

In Python, we must notice that each class is associated with a documentation string which can
be accessed by using <class-name>.__doc__. A class contains a statement suite including
fields, constructor, function, etc. definition.

Consider the following example to create a class Employee which contains two fields as
Employee id, and name.

The class also contains a function display(), which is used to display the information of
the Employee.

22
Here, the self is used as a reference variable, which refers to the current class object. It is
always the first argument in the function definition. However, using self is optional in the
function call.

The self-parameter

The self-parameter refers to the current instance of the class and accesses the class variables.
We can use anything instead of self, but it must be the first parameter of any function which
belongs to the class.

Creating an instance of the class

A class needs to be instantiated if we want to use the class attributes in another class or
method. A class can be instantiated by calling the class using the class name.

The syntax to create the instance of the class is given below.

The following example creates the instance of the class Employee defined in the above
example.

23
In the above code, we have created the Employee class which has two attributes named id
and name and assigned value to them. We can observe we have passed the self as parameter
in display function. It is used to refer to the same class attribute.

We have created a new instance object named emp. By using it, we can access the attributes
of the class.

Delete the Object

We can delete the properties of the object or object itself by using the del keyword. Consider
the following example.

24
It will through the Attribute error because we have deleted the object emp.

Python Inheritance
Inheritance provides code reusability to the program because we can use an existing class to
create a new class instead of creating it from scratch.

In inheritance, the child class acquires the properties and can access all the data members and
functions defined in the parent class. A child class can also provide its specific
implementation to the functions of the parent class.

Single Inheritance:

In python, a derived class can inherit base class by just mentioning the base in the bracket
after the derived class name. Consider the following syntax to inherit a base class into the
derived class.

25
A class can inherit multiple classes by mentioning all of them inside the bracket. Consider the
following syntax.

Example

26
Python Multi-Level inheritance

Multi-Level inheritance is possible in python like other object-oriented languages. Multi-

level inheritance is archived when a derived class inherits another derived class. There is no
limit on the number of levels up to which, the multi-level inheritance is archived in python.

27
The syntax of multi-level inheritance is given below.

28
Example: 1

Another Example:

29
Python Multiple inheritance

Python provides us the flexibility to inherit multiple base classes in the child class.

Example

30
Another Example:

31
Hierarchical Inheritance

If multiple derived classes are created from the same base, this kind of Inheritance is known
as hierarchical inheritance. In this instance, we have two base classes as a parent (base) class
as well as two children (derived) classes.

Example

Example:
32
Multilevel inheritance

Multilevel inheritance, the features that are part of the original class, as well as the class that
is derived from it, are passed on to the new class. It is similar to a relationship involving
grandparents and children.

Example:

33
Another Example:

34
 Polymorphism
What is polymorphism?

Polymorphism refers to having multiple forms. Polymorphism is a programming term that

refers to the use of the same function name, but with different signatures, for multiple types.

Example of in-built polymorphic functions:

Output:

Examples of user-defined polymorphic functions:

Polymorphism with Class Methods

For loops that iterate through multiple objects are created. Next, call the methods without
caring about what class each object belongs to. These methods are assumed to exist in every
class.
35
Example:

Encapsulation
Encapsulation is one of the most fundamental concepts in object-oriented programming
(OOP). This is the concept of wrapping data and methods that work with data in one unit.
This prevents data modification accidentally by limiting access to variables and methods. An
object's method can change a variable's value to prevent accidental changes. These variables
are called private variables.

Protected Members

Protected members in C++ and Java are members of a class that can only be accessed within
the class but cannot be accessed by anyone outside it. This can be done in Python by
following the convention and prefixing the name with a single underscore.

36
The protected variable can be accessed from the class and in the derived classes (it can also
be modified in the derived classes), but it is customary to not access it out of the class body.

The __init__ method, which is a constructor, runs when an object of a type is instantiated.

Example:

Another Example

37
Private Members

Private members are the same as protected members. The difference is that class members
who have been declared private should not be accessed by anyone outside the class or any
base classes. Python does not have Private instance variable variables that can be accessed
outside of a class.

However, to define a private member, prefix the member's name with a double
underscore "__".

Python's private and secured members can be accessed from outside the class using Python
name mangling.

Example:

38
 Abstraction
Abstraction is used to hide the internal functionality of the function from the users. The users
only interact with the basic implementation of the function, but inner working is hidden. User
is familiar with that "what function does" but they don't know "how it does."

In simple words, we all use the smartphone and very much familiar with its functions such as
camera, voice-recorder, call-dialing, etc., but we don't know how these operations are
happening in the background. Let's take another example - When we use the TV remote to
increase the volume. We don't know how pressing a key increases the volume of the TV. We
only know to press the "+" button to increase the volume.

Why Abstraction is Important?

39
In Python, an abstraction is used to hide the irrelevant data/class in order to reduce the
complexity. It also enhances the application efficiency.

Abstraction classes in Python

In Python, abstraction can be achieved by using abstract classes and interfaces.

A class that consists of one or more abstract method is called the abstract class. Abstract
methods do not contain their implementation. Abstract class can be inherited by the subclass
and abstract method gets its definition in the subclass. Abstraction classes are meant to be the
blueprint of the other class. An abstract class can be useful when we are designing large
functions. An abstract class is also helpful to provide the standard interface for different
implementations of components. Python provides the abc module to use the abstraction in the
Python program. Let's see the following syntax.

Abstract Base Classes

An abstract base class is the common application program of the interface for a set of
subclasses. It can be used by the third-party, which will provide the implementations such as
with plugins. It is also beneficial when we work with the large code-base hard to remember
all the classes.

Working of the Abstract Classes

Unlike the other high-level language, Python doesn't provide the abstract class itself. We
need to import the abc module, which provides the base for defining Abstract Base classes
(ABC). The ABC works by decorating methods of the base class as abstract. It registers
concrete classes as the implementation of the abstract base. We use
the @abstractmethod decorator to define an abstract method or if we don't provide the
definition to the method, it automatically becomes the abstract method. Let's understand the
following example.

Example -

40
Output:

Explanation -

In the above code, we have imported the abc module to create the abstract base class. We
created the Car class that inherited the ABC class and defined an abstract method named
mileage(). We have then inherited the base class from the three different subclasses and
implemented the abstract method differently. We created the objects to call the abstract
method.

Example –

41
 o An Abstract class can contain the both method normal and abstract method.

o An Abstract cannot be instantiated; we cannot create objects for the abstract class.

Python Constructor
A constructor is a special type of method (function) which is used to initialize the instance
members of the class.

In C++ or Java, the constructor has the same name as its class, but it treats constructor
differently in Python. It is used to create an object.

42
Constructors can be of two types.

1. Parameterized Constructor

2. Non-parameterized Constructor

Constructor definition is executed when we create the object of this class. Constructors also
verify that there are enough resources for the object to perform any start-up task.

Creating the constructor in python

In Python, the method the __init__() simulates the constructor of the class. This method is
called when the class is instantiated. It accepts the self-keyword as a first argument which
allows accessing the attributes or method of the class.

We can pass any number of arguments at the time of creating the class object, depending
upon the __init__() definition. It is mostly used to initialize the class attributes. Every class
must have a constructor, even if it simply relies on the default constructor.

Consider the following example to initialize the Employee class attributes.

43
Counting the number of objects of a class

The constructor is called automatically when we create the object of the class. Consider the
following example.

Python Non-Parameterized Constructor

The non-parameterized constructor uses when we do not want to manipulate the value or the
constructor that has only self as an argument. Consider the following example.

Example:
44
Another Example:

Python Parameterized Constructor

The parameterized constructor has multiple parameters along with the self. Consider the
following example.

45
Example:

Another Example:

46
Python Default Constructor

When we do not include the constructor in the class or forget to declare it, then that becomes
the default constructor. It does not perform any task but initializes the objects. Consider the
following example.

More than One Constructor in Single class

47
In the above code, the object st called the second constructor whereas both have the same
configuration. The first method is not accessible by the st object. Internally, the object of the
class will always call the last constructor if the class has multiple constructors.

Python built-in class functions

Example

48
Built-in class attributes

Along with the other attributes, a Python class also contains some built-in class attributes
which provide information about the class.

The built-in class attributes are given in the below table.

49
 NAMESPACE
WHAT IS NAMESPACE?

A namespace is a way of providing the unique name for each object in Python.

Everything in Python is an object, i.e., a variable or a method. In other words, it is a

collection of the defined symbolic names along with the information about the object that
each name references.

A namespace can be understood as a dictionary where a name represents a key and objects
are values.

EXAMPLE:

A namespace is like a surname. A "Peter" name might be difficult to find in the class if there
are multiple "Peter," but when we particularly ask for "Peter Warner" or "Peter Cummins,". It
might be rare to find the same name and surname in a class for multiple students.

The namespace helps the Python interpreter to understand what exact method or variable is
trying to point out in the code. So its name gives more information - Name (which means
name, a unique identifier) + Space (related to scope).

In Python, there are four types of namespaces which are given below.

o Built-in
o Global
o Enclosing
o Local

The Built-in Namespace

As its name suggests, it contains pre-defined names of all of Python's built-in objects already
available in Python.

50
The built-in namespace creates by the Python interpreter when its starts up. These are
terminated when Python interpreter terminates.

The Global Namespace

The global namespace consists of any names in Python at any level of the main program. It is
created when the main body executes and remains in existence until the interpreter
terminates.

The Python interpreter creates a global namespace for any module that our Python loads with
the import statement. To get more information, visit our Python Module.

The Local and Enclosing Namespaces

The function uses the local namespaces; the Python interpreter creates a new namespace
when the function is executed. The local namespaces remain in existence until the function
terminates. The function can also consist of another function.

Example –

def f():
print('Initiate f()')

def g():
print('Initiate g()')
print('End g()')
return

g()

print('Initiate f()')
return
f()

In the above example, the function g() is defined within the body of f(). Inside the f() we
called the g() and called the main f() function. Let's understand the working of the above
function -

o When we calls f(), Python creates a new namespace for f().

o Similarly, the f() calls g(), g() gets its own separate namespace.
o Here the g() is a local namespace created for f() is the enclosing namespace.

Each of these namespace is terminated when the function is terminated.

Scope of the Object/Variable

The scope is term which defines the coding region from a particular Python object is
accessible. Every object/variable has its scope where we can access that particular variable in
the program. For example - A variable in a function can only access inside the function.

51
Example -

def scope_func():
print("Inside scope_func")
def scope_inner_func():
var = 20
print("Inside inner function, value of var:",var)
scope_inner_func()
print("Try printing var from outer function: ",var)
scope_func()

Python Namespace Dictionaries

Python implements global and local namespaces as dictionaries. Python comes with
the globals() and locals() methods that allow us to access global and local namespace
dictionaries.

The globals() Method

The globals() method returns a reference to the current global namespace dictionary. We can
use it to access the objects in the global namespace.

Example -

>>> type(globals())
<class 'dict'>
>>> globals()
{'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <class '_frozen
_importlib.BuiltinImporter'>, '__spec__': None, '__annotations__': {}, '__builtins__': <modul
e 'builtins' (built-in)>}

As we can see that, there are many built-in entries in globals() method. It may be differ
according to your operating system and Python version. Now let's define the global variable
and observe the differences.

52
>>> a = 20
>>> globals()
{'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <class '_froze
n_importlib.BuiltinImporter'>, '__spec__': None, '__annotations__': {}, '__builtins__': <modu
le 'builtins' (built-in)>, 'a': 20}

After the assignment of a = 20, a new global variable assigned to the global namespace
dictionary. We can access the values as we access in the dictionaries. Let's see the below
example.

>>> a = 20
>>> globals()
{'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <class '_froze
n_importlib.BuiltinImporter'>, '__spec__': None, '__annotations__': {}, '__builtins__': <modu
le 'builtins' (built-in)>, 'a': 20}
>>> a
20
>>> globals()['a']
20

{'a': 10, 'b': 20, 'str1': 'Hello'} We can modify the dictionary value using the globals()
function.

>>> globals()['a'] = 100

>>> a
100

Now the new value of a will be appeared in the global dictionaries.

The locals() Function

Python also provides the locals() method similar to globals() but accesses objects in the local
namespace instead.

Example -

>>> def func(a, b):

... str1 = "Hello"
... loc = locals()
... print(loc)
...
>>> func(10, 20)

53
 Shallow Copy and Deep Copy

Copy in Python
The copies are helpful when a user wants to make changes without modifying the original
object at the same time. A user also prefers to create a copy to work with mutable objects.

Example -

list1 = [[1, 2, 3], [4, 5, 6], [7, 8, 'a']]

list2 = list1

list2[1][2] = 4

print('Old List:', list1)

print('ID of Old List:', id(list1))

print('New List:', list2)

print('ID of New List:', id(list2))

In the above output, we can see that both variable list1 and list2 share the same id
1909447368968.

If we make any changes in any value in list1 or list2, the change will reflect in both.

Types of Copies in Python

The main motive is to create a copy of Python object that we can modify the copy without
changing the original data. In Python, there are two methods to create copies.

o Shallow Copy
o Deep Copy

The copy Module

The copy module is used to create the shallow copy and deep copy.

54
Shallow Copy

A shallow copy is a copy of an object that stores the reference of the original elements. It
creates the new collection object and then occupying it with reference to the child objects
found in the original.

It makes copies of the nested objects' reference and doesn't create a copy of the nested
objects. So if we make any changes to the copy of the object will reflect in the original object.
We will use the copy() function to implement it.

Example -

# importing "copy" for copy operations

import copy

# initializing list 1
list1 = [1, 7, [3,5], 8]

# using copy to shallow copy

list2 = copy.copy(list1)

# original elements of list

print ("The original elements before shallow copying")
for i in range(0,len(list1)):
print (list1[i],end=" ")

print("\r")

# adding and element to new list

list2[2][0] = 10

# checking if change is reflected

print ("The original elements after shallow copying")
for i in range(0,len( list1)):
print (list1[i],end=" ")

55
In the above code, we made chance in the list1 that reflected in the other list.

Example - 2

import copy

list1 = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]
list2 = copy.copy(list1)

list1.append([13, 14,15])

print("Old list:", list1)

print("New list:", list2)

In the above code, we have created a shallow copy of list1. The newly created list2 contains
the reference of the original nested object stored in list1. We have then appended the [13, 14,
15] into the old list and sublist not copied in the new list.

Deep Copy in Python

A deep copy is a process where we create a new object and add copy elements recursively.
We will use the deecopy() method which present in copy module. The independent copy is
created of original object and its entire object.

Example -

import copy
x = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
z = copy.deepcopy(xs)
print(x)
prin(z)

56
In the above output, we can see that z is a clone of x that we have created using
the deecopy() method. If we make change to one of child won't affect the original object.

Both objects are fully independent in the deep copy. The list x was cloned recursively,
including all of its child objects.

import copy
x = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
z = copy.deepcopy(x)

x[2][2] = 'Hello'
print(x)

Example - 2:

import copy

list1 = [0, [1, 2], [3,5], 4]

# using deepcopy to deep copy

list2 = copy.deepcopy(list1)

# original elements of list

print ("The original list: ")
for i in range(0,len(list1)):
print (list1[i],end=" ")

print("\r")

# adding and element to new list

list2[1][0] = 8

# Change is reflected in l2
print ("The new list after deep copying: ")
for i in range(0,len( list1)):
print (list2[i],end=" ")

print("\r")

# Change is NOT reflected in original list

# as it is a deep copy
print ("The original elements:")
for i in range(0,len( list1)):
print (list1[i],end=" ")

57
Copying Arbitrary Python Objects

We can also copy the arbitrary Python objects including custom classes using copy method.
The copy.copy() and copy.deepcopy() method can be used to duplicate any objects.

Example -

import copy
class Func_New:
def __init__(self, x, y):
self.x = x
self.y = y

def __repr__(self):
return 'Func_new(%r, %r)' % (self.x, self.y)

a = Func_New(50, 56)
b = copy.copy(a)

print(a)
print(b)

print(a is b)
print(b is a)

58
In the above code, we have created a user define class named Func_new and we defined
the __repr__() to inspect objects. Next, we created the shallow copy using the copy module.
We instantiated the class and check whether the both original and its shallow copy.

The compound objects are the main difference between the shallow and deep copy. The
objects that contain other objects, such as a list or class instance, are called list or class
instances.

o A shallow copy creates a new compound object and then adds a reference to the
object found in the original.
o A deep copy creates a new compound object and then adds a reference to the object
found in the original.
o We can copy arbitrary objects (including custom classes) with the copy module.

Algorithm
An algorithm is a process or a set of rules required to perform calculations or some other
problem-solving operations especially by a computer.

It contains the finite set of instructions which are being carried in a specific order to perform
the specific task.

It is not the complete program or code; it is just a solution (logic) of a problem, which can be
represented either as an informal description using a Flowchart or Pseudocode.

Characteristics of an Algorithm

The following are the characteristics of an algorithm:

o Input: An algorithm has some input values. We can pass 0 or some input value to an
algorithm.
o Output: We will get 1 or more output at the end of an algorithm.
o Unambiguity: An algorithm should be unambiguous which means that the
instructions in an algorithm should be clear and simple.
o Finiteness: An algorithm should have finiteness. Here, finiteness means that the
algorithm should contain a limited number of instructions, i.e., the instructions should
be countable.
o Effectiveness: An algorithm should be effective as each instruction in an algorithm
affects the overall process.
o Language independent: An algorithm must be language-independent so that the
instructions in an algorithm can be implemented in any of the languages with the
same output.

59
Dataflow of an Algorithm
o Problem: A problem can be a real-world problem or any instance from the real-world
problem for which we need to create a program or the set of instructions. The set of
instructions is known as an algorithm.
o Algorithm: An algorithm will be designed for a problem which is a step by step
procedure.
o Input: After designing an algorithm, the required and the desired inputs are provided
to the algorithm.
o Processing unit: The input will be given to the processing unit, and the processing
unit will produce the desired output.
o Output: The output is the outcome or the result of the program.

Why do we need Algorithms?

We need algorithms because of the following reasons:

o Scalability: It helps us to understand the scalability. When we have a big real-world

problem, we need to scale it down into small-small steps to easily analyze the
problem.
o Performance: The real-world is not easily broken down into smaller steps. If the
problem can be easily broken into smaller steps means that the problem is feasible.

Factors of an Algorithm

The following are the factors that we need to consider for designing an algorithm:

o Modularity: If any problem is given and we can break that problem into small-small
modules or small-small steps, which is a basic definition of an algorithm, it means
that this feature has been perfectly designed for the algorithm.
o Correctness: The correctness of an algorithm is defined as when the given inputs
produce the desired output, which means that the algorithm has been designed
algorithm. The analysis of an algorithm has been done correctly.
o Maintainability: Here, maintainability means that the algorithm should be designed
in a very simple structured way so that when we redefine the algorithm, no major
change will be done in the algorithm.
o Functionality: It considers various logical steps to solve the real-world problem.
o Robustness: Robustness means that how an algorithm can clearly define our problem.
o User-friendly: If the algorithm is not user-friendly, then the designer will not be able
to explain it to the programmer.
o Simplicity: If the algorithm is simple then it is easy to understand.

60
 o Extensibility: If any other algorithm designer or programmer wants to use your
algorithm then it should be extensible.

Issues of Algorithms

The following are the issues that come while designing an algorithm:

o How to design algorithms: As we know that an algorithm is a step-by-step procedure

so we must follow some steps to design an algorithm.
o How to analyze algorithm efficiency

The major categories of algorithms are given below:

o Sort: Algorithm developed for sorting the items in a certain order.

o Search: Algorithm developed for searching the items inside a data structure.
o Delete: Algorithm developed for deleting the existing element from the data structure.
o Insert: Algorithm developed for inserting an item inside a data structure.
o Update: Algorithm developed for updating the existing element inside a data
structure.

Algorithm Analysis

The algorithm can be analyzed in two levels, i.e., first is before creating the algorithm, and
second is after creating the algorithm. The following are the two analysis of an algorithm:

o Priori Analysis: Here, priori analysis is the theoretical analysis of an algorithm which
is done before implementing the algorithm. Various factors can be considered before
implementing the algorithm like processor speed, which has no effect on the
implementation part.
o Posterior Analysis: Here, posterior analysis is a practical analysis of an algorithm. The
practical analysis is achieved by implementing the algorithm using any programming
language. This analysis basically evaluate that how much running time and space
taken by the algorithm.

Algorithm Complexity

The performance of the algorithm can be measured in two factors:

o Time complexity: The time complexity of an algorithm is the amount of time

required to complete the execution. The time complexity of an algorithm is denoted
by the big O notation. Here, big O notation is the asymptotic notation to represent the
time complexity. The time complexity is mainly calculated by counting the number of
steps to finish the execution.

61
 Example:

sum=0;
for i=1 to n
sum=sum+i;
return sum;

In the above code, the time complexity of the loop statement will be atleast n, and if the value
of n increases, then the time complexity also increases. While the complexity of the code, i.e.,
return sum will be constant as its value is not dependent on the value of n and will provide
the result in one step only. We generally consider the worst-time complexity as it is the
maximum time taken for any given input size.

o Space complexity: An algorithm's space complexity is the amount of space required

to solve a problem and produce an output. Similar to the time complexity, space
complexity is also expressed in big O notation.

For an algorithm, the space is required for the following purposes:

1. To store program instructions

2. To store constant values
3. To store variable values
4. To track the function calls, jumping statements, etc.

Auxiliary space: The extra space required by the algorithm, excluding the input size, is
known as an auxiliary space. The space complexity considers both the spaces, i.e.,
auxiliary space, and space used by the input.

So,

Space complexity = Auxiliary space + Input size.

Asymptotic Notations

Asymptotic notations are the mathematical notations used to describe the running time of an
algorithm when the input tends towards a particular value or a limiting value.

Asymptotic notations are mathematical tools to represent the time complexity of

algorithms for asymptotic analysis.

Asymptotic Notations

Following are the commonly used asymptotic notations to calculate the running time
complexity of an algorithm.
 Ο Notation

62
  Ω Notation
 θ Notation

Big Oh Notation, Ο
 The big O notation measures the upper bound on the running time of an algorithm.
 Big O time complexity describes the worst case
f(n)<=c*g(n)
The notation Ο(n) is the formal way to express the upper bound of an algorithm's running
time. It measures the worst case time complexity or the longest amount of time an algorithm
can possibly take to complete.

For example, for a function f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }

Example:

f(n)=2n+8, g(n)=7n

Step1:
If n=0,then
f(0)=2(0)+8
=0+8
f(0)=8

g(0)=7(0)
=0
g(0)=0

f(0)>g(0)
f(n)>g(n)

condition failed.

Step2:

63
If n=1,then
f(1)=2(1)+8
=2+8
f(1)=10
g(1)=7(1)
=7
g(1)=7

f(1)>g(1)
f(n)>g(n)

Step3:
If n=2,then
f(2)=2(2)+8
=4+8
f(2)=12

g(2)=7(2)
g(2)=14
f(2)<g(2)
f(n)<g(n)
Condition Satisfied when n>2

f(n)<=c*g(n) satisfies

Omega Notation, Ω
The big Omega measures the lower bound on the running time of an algorithm.

Big Omega time complexity describes the best case.

f(n)>=c*g(n)

The notation Ω(n) is the formal way to express the lower bound of an algorithm's running
time. It measures the best case time complexity or the best amount of time an algorithm can
possibly take to complete.

64
For example, for a function f(n)
Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }

Example:

f(n)=2n+8, g(n)=3n

Step1:
If n=0,then
f(0)=2(0)+8
=0+8
f(0)=8

g(0)=3(0)
=0
g(0)=0

f(0)>g(0)

f(n)>g(n)
Condition Satisfied when n>0

f(n)€Ώg(n)
f(n)>=c*g(n)

Theta Notation, θ
The big Theta measures the time between the upper and the lower bound of an algorithm.
Big Theta describes the time complexity within the bounds of the best and worst case.
c1.g(n) <= f(n) <= c2.g(n)

The notation θ(n) is the formal way to express both the lower bound and the upper bound of
an algorithm's running time. It is represented as follows

Example:
C1(g(n))<=f(n)<=c2(g(n))

65
Big oh=> 2n+8<7n when n>2
Omega=> 2n+8>3n when n>0
3n<=2n+8<=7n when n>2
f(n)€Ɵ(g(n))

DIVIDE AND CONQUER

It divide the problem into atleast two or more smaller problems, and then it will try to solve
each of those problems individually.

66
A typical Divide and Conquer algorithm solves a problem using following three steps:
Divide: This involves dividing the problem into smaller sub-problems.
Conquer: Solve sub-problems by calling recursively until solved.
Combine: Combine the sub-problems to get the final solution of the whole problem.
Standard algorithms that follow Divide and Conquer algorithm
Merge Sort is also a sorting algorithm. The algorithm divides the array into two halves,
recursively sorts them, and finally merges the two sorted halves
Merge Sort Working Process:

The recursive algorithm continuously splits the array in half until it cannot be further
divided. This means that if the array becomes empty or has only one element left, the
dividing will stop, i.e. it is the base case to stop the recursion. If the array has multiple
elements, split the array into halves and recursively invoke the merge sort on each of the
halves. Finally, when both halves are sorted, the merge operation is applied. Merge
operation is the process of taking two smaller sorted arrays and combining them to
eventually make a larger one.

Algorithm for merge sort:

67
step 1: start
step 2: declare array and left, right, mid variable
step 3: perform merge function.
if left > right
return
mid= (left+right)/2
mergesort(array, left, mid)
mergesort(array, mid+1, right)
merge(array, left, mid, right)
step 4: Stop

Fundamental of Divide & Conquer Strategy:

There are two fundamental of Divide & Conquer Strategy:

1. Relational Formula
2. Stopping Condition

68
1. Relational Formula: It is the formula that we generate from the given technique. After
generation of Formula we apply D&C Strategy, i.e. we break the problem recursively & solve
the broken subproblems.

2. Stopping Condition: When we break the problem using Divide & Conquer Strategy, then
we need to know that for how much time, we need to apply divide & Conquer. So the
condition where the need to stop our recursion steps of D&C is called as Stopping Condition.

Applications of Divide and Conquer Approach:

Following algorithms are based on the concept of the Divide and Conquer Technique:

1. Binary Search: The binary search algorithm is a searching algorithm, which is also
called a half-interval search or logarithmic search. It works by comparing the target
value with the middle element existing in a sorted array. After making the
comparison, if the value differs, then the half that cannot contain the target will
eventually eliminate, followed by continuing the search on the other half. We will
again consider the middle element and compare it with the target value. The process
keeps on repeating until the target value is met. If we found the other half to be empty
after ending the search, then it can be concluded that the target is not present in the
array.
2. Quicksort: It is the most efficient sorting algorithm, which is also known as partition-
exchange sort. It starts by selecting a pivot value from an array followed by dividing
the rest of the array elements into two sub-arrays. The partition is made by comparing
each of the elements with the pivot value. It compares whether the element holds a
greater value or lesser value than the pivot and then sort the arrays recursively.
3. Merge Sort: It is a sorting algorithm that sorts an array by making comparisons. It
starts by dividing an array into sub-array and then recursively sorts each of them.
After the sorting is done, it merges them back.
4. Closest Pair of Points: It is a problem of computational geometry. This algorithm
emphasizes finding out the closest pair of points in a metric space, given n points,
such that the distance between the pair of points should be minimal.
5. Strassen's Algorithm: It is an algorithm for matrix multiplication, which is named
after Volker Strassen. It has proven to be much faster than the traditional algorithm
when works on large matrices.
6. Cooley-Tukey Fast Fourier Transform (FFT) algorithm: The Fast Fourier
Transform algorithm is named after J. W. Cooley and John Turkey. It follows the
Divide and Conquer Approach and imposes a complexity of O(nlogn).
7. Karatsuba algorithm for fast multiplication: It is one of the fastest multiplication
algorithms of the traditional time, invented by Anatoly Karatsuba in late 1960 and got
published in 1962. It multiplies two n-digit numbers in such a way by reducing it to at
most single-digit.

Advantages of Divide and Conquer

o Divide and Conquer tend to successfully solve one of the biggest problems, such as
the Tower of Hanoi, a mathematical puzzle. It is challenging to solve complicated
problems for which you have no basic idea, but with the help of the divide and
conquer approach, it has lessened the effort as it works on dividing the main problem

69
 into two halves and then solve them recursively. This algorithm is much faster than
other algorithms.
o It efficiently uses cache memory without occupying much space because it solves
simple subproblems within the cache memory instead of accessing the slower main
memory.
o It is more proficient than that of its counterpart Brute Force technique.
o Since these algorithms inhibit parallelism, it does not involve any modification and is
handled by systems incorporating parallel processing.

Disadvantages of Divide and Conquer

o Since most of its algorithms are designed by incorporating recursion, so it necessitates

high memory management.
o An explicit stack may overuse the space.
o It may even crash the system if the recursion is performed rigorously greater than the
stack present in the CPU.

Recursion

 The process in which a function calls itself directly or indirectly is called

recursion

and the corresponding function is called a recursive function.

 Using a recursive algorithm, certain problems can be solved quite easily.

Examples

 Towers of Hanoi (TOH),

 Inorder/Preorder/Postorder Tree Traversals,
 DFS of Graph

Towers of Hanoi

Tower of Hanoi is a mathematical puzzle where we have three rods (A, B, and C)
and N disks.

Rules

 Only one disk can be moved at a time.

70
  Each move consists of taking the upper disk from one of the stacks and
placing it on

top of another stack i.e. a disk can only be moved if it is the uppermost disk on a
stack.

 No disk may be placed on top of a smaller disk.

Tower of Hanoi using Recursion:

Example program:

71
 Analyzing Recursive Algorithm
Need of Recursion
Recursion is an amazing technique with the help of which we can reduce the length of our
code and make it easier to read and write. It has certain advantages over the iteration
technique which will be discussed later. A task that can be defined with its similar subtask,
recursion is one of the best solutions for it. For example; The Factorial of a number.

72
Properties of Recursion:
 Performing the same operations multiple times with different inputs.
 In every step, we try smaller inputs to make the problem smaller.
 Base condition is needed to stop the recursion otherwise infinite loop will occur.
A Mathematical Interpretation
Let us consider a problem that a programmer has to determine the sum of first n natural
numbers, there are several ways of doing that but the simplest approach is simply to
add the numbers starting from 1 to n. So the function simply looks like this,
approach(1) – Simply adding one by one
f(n) = 1 + 2 + 3 +……..+ n
but there is another mathematical approach of representing this,
approach(2) – Recursive adding
f(n) = 1 n=1
f(n) = n + f(n-1) n>1
There is a simple difference between the approach (1) and approach(2) and that is
in approach(2) the function “ f( ) ” itself is being called inside the function, so this
phenomenon is named recursion, and the function containing recursion is called
recursive function, at the end, this is a great tool in the hand of the programmers to
code some problems in a lot easier and efficient way.
How are recursive functions stored in memory?
Recursion uses more memory, because the recursive function adds to the stack with
each recursive call, and keeps the values there until the call is finished. The recursive
function uses LIFO (LAST IN FIRST OUT) Structure just like the stack data structure.
What is the base condition in recursion?
In the recursive program, the solution to the base case is provided and the solution to
the bigger problem is expressed in terms of smaller problems.

int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}
In the above example, the base case for n < = 1 is defined and the larger value of a
number can be solved by converting to a smaller one till the base case is reached.
How a particular problem is solved using recursion?
The idea is to represent a problem in terms of one or more smaller problems, and add
one or more base conditions that stop the recursion. For example, we compute factorial
n if we know the factorial of (n-1). The base case for factorial would be n = 0. We
return 1 when n = 0.

73
Why Stack Overflow error occurs in recursion?
If the base case is not reached or not defined, then the stack overflow problem may
arise. Let us take an example to understand this.
int fact(int n)
{
// wrong base case (it may cause
// stack overflow).
if (n == 100)
return 1;

else
return n*fact(n-1);
}
If fact(10) is called, it will call fact(9), fact(8), fact(7), and so on but the number will
never reach 100. So, the base case is not reached. If the memory is exhausted by these
functions on the stack, it will cause a stack overflow error.
What is the difference between direct and indirect recursion?
A function fun is called direct recursive if it calls the same function fun. A function fun
is called indirect recursive if it calls another function say fun_new and fun_new calls
fun directly or indirectly. The difference between direct and indirect recursion has been
illustrated in Table 1.
// An example of direct recursion
void directRecFun()
{
// Some code....

directRecFun();

// Some code...
}

// An example of indirect recursion

void indirectRecFun1()
{
// Some code...

indirectRecFun2();

// Some code...
}
void indirectRecFun2()
{
// Some code...

74
 indirectRecFun1();

// Some code...
}

Example factorial program for recursion:

Time Complexity: O(2n)

Auxiliary Space: O(n)

Recursion VS Iteration

75