AD3251 DATA STRUCTURES DESIGN

UNIT I
ABSTRACT DATA TYPES

Abstract Data Types (ADTs) – ADTs and classes – introduction to OOP – classes in
Python – inheritance – namespaces – shallow and deep copying. Introduction to
analysis of algorithms – asymptotic notations – divide & conquer- recursion –
analyzing recursive algorithms.

INTRODUCTION TO DATA STRUCTURES

Data structure is a branch of computer science. The study of data structure helps to understand how
data is organized and how data flow is managed to increase the efficiency of any process or program.
Data structure is the structural representation of logical relationship between data elements.
Definition
Data structure is a way of storing, organizing and retrieving data in a computer, so that it can be used
efficiently. It provides a way to manage large amount of data proficiently.
Need for Data Structures:
 It gives different level of organization of data.
 It tells how data can be stored and accessed.
 It provides a means to manage large amount of data efficiently.
 It provides fast searching and sorting of data.
Classification of Data structures
• Data structures can be classified into two categories.
i) Primitive Data structures
ii) Non-Primitive Data structures
Primitive Data Structures
• Primitive data structures are basic data structures. These can be manipulated or operated
directly by the machine level instructions. Basic data types such as integer, real, character and
Boolean come under this type. Example: int, char, float.
Non-Primitive Data Structures
 Non-primitive data structures are derived from primitive data structures.
 These data structures cannot be operated or manipulated directly by the machine level
instructions.
 They define the group of homogeneous and non-homogenous data items.
 Examples: Array, Lists, Graphs, Trees etc.
1. Linear Data Structures
 A data structure that maintains a linear relationship among the elements is called a linear data
structure.
 Here, the data are arranged in a sequential fashion. But in the memory the arrangement may
not be sequential.
 Examples: Arrays, linked lists, stack and queues.
2. Non-Linear Data Structures
1. A data structure that maintains the data elements in hierarchical order are known as
nonlinear data structure. Thus, they are present at various levels.
2. They are comparatively difficult to implement and understand as compared to the
linear data structures. Examples: Trees and Graphs.

ABSTRACT DATA TYPES (ADTs)

• 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. The process of hiding the nonessential
details and providing only the essentials of problem solving is known as data abstraction.
• Examples: List ADT, Stack ADT, Queue ADT, Trees, Graphs etc.
Advantages of using ADTs
• ADTs give the feel of plug and play interface. So it is easy for the programmer to implement
ADT. For example, to store collection of items, it can be easily put the items in a list. That is,
BirdsList=[‘Parrot’,’Dove’,’Duck’,’Cuckoo’]
• To find number of items in a list, the programmer can use len function without implementing
 the code.
• The ADTs reduces the program developing time. Because the programmer can use the
predefined functions rather than developing the logic and implementing the same.
• The usage of ADTs reduces the chance of logical errors in the code, as the usage of
predefined functions in the ADTs are already bug free.
• ADTs provide well defined interfaces for interacting with the implementing code.
• ADTs increase the understandability and modularity of the code.
ADTs AND CLASSES
A data structure is the implementation for an ADT. In an object-oriented language, an ADT and its
implementation together make up a class. Each operation associated with the ADT is implemented by
a member function or method. The variables that define the space required by a data item are referred
to as data members. An object is an instance of a class that is created and takes up storage during the
execution of a computer program.

INTRODUCTION TO OBJECT ORIENTED PROGRAMMING

Goals:
Software implementations should achieve robustness, adaptability, and reusability.
Robustness
• Every good programmer wants to develop software that is correct, which means that a program
produces the right output for all the anticipated inputs in the program’s application. For example, if
a program is expecting a positive integer and instead is given a negative integer, then the program
should be able to recover gracefully from this error.
Adaptability
• Modern software applications, such as Web browsers and Internet search engines, involve large
programs that are used for many years. Software, therefore, needs to be able to evolve over time in
response to changing conditions in its environment.
 Reusability

• Going hand in hand with adaptability, the software be reusable. That is, the same code should be
usable as a component of different systems in various applications. Developing quality software is
designed in a way that makes it easily reusable in future applications. Such reuse should be done with
care.
Object-Oriented Design Principles
The important principles in object-oriented approach, are as follows
• Modularity
• Abstraction
• Encapsulation
Modularity
• Modern software systems consist of several different components that must interact correctly in order
for the entire system to work properly. Keeping these interactions requires that these different
components be well organized. Modularity refers to an organizing principle in which different
components of software system are divided into separate functional units .

Abstraction
• Abstraction allows dealing with the complexity of the object. Abstraction allows picking out the
relevant details of the object, and ignoring the non-essential details.
• Python supports abstract data types using a mechanism known as an abstract base class (ABC). An
abstract base class cannot be instantiated.
Encapsulation
• It hides the data defined in the class and separates implementation of the class from its interface. The
interaction with the class is through the interface provided by the set of methods defined in the class.
This separation of interface from its implementation allows changes to be made in the class without
affecting its interface.
CLASSES IN PYTHON
• A class serves as the primary means for abstraction in object-oriented programming. In
python everything is an object. Everything is an instance of some class. A class also
serves as a blueprint for its instances.
 The data values stored inside an object are called attributes. The state information for
each instance is represented in the form of attributes (also known as fields, instance
variables, or data members).
 A class provides a set of behaviors in the form of member functions (also known as
methods), with implementations that are common to all instances of that class.
Defining a class
A class is the definition of data and methods for a specific type of object.
Syntax:
class classname:
<statement1>
.
.
.
<statement>

 The class definition begins with the keyword class, followed by the name of the
class, a colon and an indented block of code that serves as the body of the class.
 The body includes definitions for all methods of the class. These methods are
defined as functions, with a special parameter, named self, that is used to identify the
particular instance upon which a member is invoked.
 When a class definition is entered, a new namespace is created, and used as the
local scope. Thus, all assignments to local variables go into this new namespace.
Example:
class customer:
def _ _init_ _(self,name,iden,acno):
self.custName=name
self.custID=iden
self.custAccNo=acno
def display(self):
print("Customer Name = ",self.custName)
print("Customer ID = ",self.custID)
print("Customer Account Number = ",self.custAccNo)
c = customer("Ramesh",10046,327659)
c.display()

The Self Identifier and Self Parameter

In python, the self-identifier places a key role. Self identifies the instance upon
which a method is invoked. While writing function in a class, at least one argument
has to be passed, that is called self-parameter. The self-parameter is a reference to the
class itself and is used to access variables that belongs to the class. In python
programming self is a default variable that contains the memory address of the
instance of current class. So self is used to reuse all the instance variable and instance
methods.
• Example:
self.custName, self.custID, self.custAccNo
 Object Creation:
 An object is the runtime entity used to provide the functionality to the python
class.
 The attributes defined inside the class are accessed only using objects of that
class.
 The user defined functions also accessed by using the object.
Syntax:
object_name = class_name

The dot (.) operator is used to call the functions.

Syntax:
object_name . function_name()

Class variable and Instance variable:

• Class variable is defined in the class and can be used by all the instances of that
class.
 Instance variable is defined in a method and its scope is only with in the object
that defines it.
 Every object of the class has its own copy of that variable. Any change made to
the variable don’t reflect in other objects of that class.
 Instance variables are unique for each instance, while class variables are shared
by all instances
Example:
class Order:
def _ _init_ _(self, coffee_name, price):
self.coffee_name = coffee_name
self.price = price
ram_order = Order("Espresso", 210)
print(ram_order.coffee_name)
print(ram_order.price)
paul_order = Order("Latte", 275)
print(paul_order.coffee_name)
print(paul_order.price)

• In this example, coffee_name and price are the class variables. ram_order and
paul_order are the two instances of this class. Each of these instances has their
own values set for the coffee_name and price instance variables.
• When ram’s order details are printed in the console, the values Espresso and 210
are returned. When Paul’s order details are printed in the console, the
values Latte and 275 are returned.
• This shows that, instance variables can have different values for each instance of
the class, whereas class variables are the same across all instances.
 INHERITANCE
 In object-oriented programming, the existing class is typically described as the base class,
parent class or super class, while the newly defined class is known as the subclass or child
class.
 There are two ways in which a subclass can differentiate itself from its superclass. A subclass
may specialize an existing behavior by providing a new implementation that overrides an
existing method. A subclass may also extend its superclass by providing brand new methods.
 Inheritance is a mechanism through which we can create a class or object based on another
class or object. In other words, the new objects will have all the features or attributes of the
class or object on which they are based. It supports code reusability.
In Python, based upon the number of child and parent classes involved, there are five types of inheritance.
The types of inheritance are listed below:
i. Single inheritance
ii. Multiple Inheritance
iii. Multilevel inheritance
iv. Hierarchical Inheritance
v. Hybrid Inheritance
Single Inheritance
In single inheritance, a child class inherits from a single-parent class. Here is one child class and one
parent class

Example:
# Base class
class Vehicle:
def Vehicle_info(self):
print('Inside Vehicle class')
# Child class
class Car(Vehicle):
def car_info(self):
print('Inside Car class') # Create object of Car
car = Car() # access Vehicle's info using car object
car.Vehicle_info()
car.car_info()
Output:
Inside Vehicle class
Inside Car class
Multiple Inheritance:
In multiple inheritance, one child class can inherit from multiple parent classes. So here is one child class
and multiple parent classes.

class SuperClass1:
# features of SuperClass1

class SuperClass2:
# features of SuperClass2

class MultiDerived(SuperClass1, SuperClass2):

# features of SuperClass1 + SuperClass2 + MultiDerived class

Multilevel Inheritance:
Multilevel Inheritance is a mechanism in object-oriented programming where a class inherits from
another class, which in turn inherits from another class. This process continues until the topmost class is
reached. In this way, inheritance relationships form a hierarchy of classes, with the base class being at the
top, and the derived classes being at the bottom. The derived class inherits the attributes and behavior of
the class it inherits from and can also add new attributes and behavior to those inherited.

Syntax :
class base1 :
body of base class
class derived1( base1) :
body of derived class
class derived2( derived1) :
body of derived class
Example Program:
class Vehicle:
def Vehicle_info(self):
print('Inside Vehicle class')
class Car(Vehicle):
def car_info(self):
print('Inside Car class')
class SportsCar(Car):
def sports_car_info(self):
print('Inside Sports Car class') s_car = SportsCar() s_car.Vehicle_info() s_car.car_info()
s_car.sports_car_info()
Output:
Inside Vehicle class
Inside Car class
Inside Sports Car class
Hierarchical Inheritance:

In Hierarchical inheritance, more than one child class is derived from a single parent class. In other
words, a single base class is inherited by multiple derived classes. In this scenario, each derived class
shares common attributes and methods from the same base class, forming a hierarchy of classes.
Syntax:
class BaseClass:
# Base class attributes and methods

class DerivedClass1(BaseClass):
# Additional attributes and methods specific to DerivedClass1

class DerivedClass2(BaseClass):
# Additional attributes and methods specific to DerivedClass2

Syntax:
class Vehicle:
def info():
print("This is Vehicl` e")
class Car(Vehicle):
def car_info():
print("Car name is BMW”)
class Truck(Vehicle):
def truck_info():
print("Truck name is Ford")
obj1 = Car()
obj1.info()
obj1.car_info()
obj2 = Truck()
obj2.info()
obj2.truck_info()
Output:
This is Vehicle
Car name is BMW
This is Vehicle
Truck name is Ford
 Hybrid Inheritance:
Hybrid inheritance is a blend of multiple inheritance types. In Python, the supported types of
inheritance are single, multiple, multilevel, hierarchical, and hybrid. In hybrid inheritance, classes are
derived from more than one base class, creating a complex inheritance structure.

Syntax:
class BaseClass1:
# Attributes and methods of BaseClass1
class BaseClass2:
# Attributes and methods of BaseClass2
class DerivedClass(BaseClass1, BaseClass2):
# Attributes and methods of DerivedClass
Example:
class Vehicle:
def vehicle_info(self):
print("Inside Vehicle class")
class Car(Vehicle):
def car_info(self):
print("Inside Car class")
class Truck(Vehicle):
def truck_info(self):
print("Inside Truck class")
class SportsCar(Car, Vehicle):
def sports_car_info(self):
print("Inside SportsCar class")
s_car = SportsCar()
s_car.vehicle_info()
s_car.car_info()
s_car.sports_car_info()
Inside Vehicle class
Inside Car class
Inside SportsCar class

Namespaces
 A namespace manages all of the identifiers that are defined in a particular scope, mapping each name
to its associated value. In Python, functions, classes and modules are class objects and so the value
associated with an identifier in a namespace may be a function, class or module.
 A namespace is a collection of currently defined symbolic names along with information about the
object that each name references.
Types:

1) Built-in Namespace
It contains the names of all of Python’s built-in objects. These are available at all times when
Python is running. The Python interpreter creates the built-in namespace when it starts up. This
namespace remains in existence until the interpreter terminates.
Example:
Name=input("Enter your name:") #input() is built-in function
print(Name) #print() is built-in function
2) Global Namespace
It contains any names defined at the level of the main program. Python creates the global
namespace when the main program body starts, and it remains in existence until the interpreter
terminates. The interpreter creates a global namespace for any module that the program loads with
the import statement.

Example:
x=10 # global scope of variable in python
def f1(): #function definition
print(x) #variable accessed inside the function
f1()
3) Local Namespace
In Python, the interpreter creates a new namespace whenever a function executes. That
namespace is local to the function and remains in existence until the function terminates. A local
namespace can access global as well as built-in namespaces.
Example:
def f1(): #function definition
y=20 #Local scope of variable in python
print(y) #variable accessed inside the function
f1()
• The variable ‘y’ is declared in a local namespace and has a local scope of variable in python.

SHALLOW AND DEEP COPYING

• In some applications, it is necessary to subsequently modify either the original or copy in an
independent manner.
 • Consider an application to manage various lists of colors. Each color is represented by an
instance of a presumed color class. warmtones is an identifier denote an existing list of such
colors (e.g., oranges, browns).
Shallow Copy:
A shallow copy creates a new compound object and then references the objects contained in the
original within it. The copying process does not create copies of the child objects themselves. In
the case of shallow copy, a reference of an object is copied into another object. It means that any
changes made to a copy of an object do reflect in the original object. In python, this is implemented
using the “copy()” function.
Syntax:
copy.copy(x)

In this example, the change made in the list did affect another list, indicating the list is shallowly
copied. The shallow copy constructs a new compound object and then (to the extent possible)
inserts references into it to the objects found in the original.
Example:
import copy
li1 = [1, 2, [3,5], 4]
li2 = copy.copy(li1)
print ("The original elements before shallow copying")
for i in range(0,len(li1)):
print (li1[i],end=" ")
print("\r")
li2[2][0] = 7
print ("The original elements after shallow copying")
for i in range(0,len( li1)):
print (li1[i],end=" ")
Output:
The original elements before shallow copying
1 2 [3, 5] 4
The original elements after shallow copying
1 2 [7, 5] 4

In this example, this code demonstrates shallow copying of a list with nested elements
using the ‘copy' module. Initially, it prints the original elements of li1, then performs
shallow copying into li2. Modifying an element in li2 affects the corresponding element
in li1, as both lists share references to the inner lists. This illustrates that shallow copying
creates a new list, but it doesn’t provide complete independence for nested elements.

Deep Copy:
A deep copy creates a new compound object before inserting copies of the items
found in the original into it in a recursive manner. It means first constructing a new
collection object and then recursively populating it with copies of the child objects found
in the original. In the case of deep copy, a copy of the object is copied into another object.
It means that any changes made to a copy of the object do not reflect in the original
object.
Syntax:
copy.deepcopy(x)

In the above example, the change made in the list did not affect other lists, indicating the
list is deeply copied.
Program:
import copy
li1 = [1, 2, [3,5], 4]
li2 = copy.deepcopy(li1)
print ("The original elements before deep copying")
for i in range(0,len(li1)):
print (li1[i],end=" ")
print("\r")
li2[2][0] = 7
print ("The new list of elements after deep copying ")
for i in range(0,len( li1)):
print (li2[i],end=" ")
print("\r")
print ("The original elements after deep copying")
for i in range(0,len( li1)):
print (li1[i],end=" ")
Output:
The original elements before deep copying
1 2 [3, 5] 4
The new list of elements after deep copying
1 2 [7, 5] 4
The original elements after deep copying
1 2 [3, 5] 4

This code illustrates deep copying of a list with nested elements using the copy module. It
initially prints the original elements of li1, then deep copies them to create li2. A
modification to an element in li2 does not affect li1, as demonstrated by the separate
printouts. This highlights how deep copying creates an independent copy, preserving the
original list’s contents even after changes to the copy.

INTRODUCTION TO ANALYSIS OF ALGORITHMS

• To bake a cake, we can get different recipes from the internet. We can find ‘n’ number of
steps for different varieties of cakes. All those different step by step procedure to make a cake
can be called as an algorithm. We can choose a simple, easy and most convenient way to
make a cake.
• Similarly in computer science, multiple algorithms are available for solving the same
problem. The algorithm analysis helps us to determine which algorithm is most efficient in
terms of running time, memory and space consumed. etc.,

Why Analyze an Algorithm?

• The most straightforward reason for analyzing an algorithm is to discover its characteristics in
order to evaluate its suitability for various applications or compare it with other algorithms for
the same application. Moreover, the analysis of an algorithm can help us to understand it
better, and can suggest informed improvements. Algorithms tend to become shorter, simpler,
and more elegant during the analysis process.
• The efficiency of an algorithm can be decided based on
 1. Amount of time required by an algorithm to execute.
2. Amount of storage required by an algorithm.
3. Size of the input set.
Complexities of an Algorithm:
• The complexity of an algorithm computes the amount of time and spaces required by an
algorithm for an input of size (n). The complexity of an algorithm can be two types.
Time Complexity:
Time complexity measures the amount of time required to run an algorithm, as input size of the
algorithm increases.
Space Complexity:
Space complexity measures the total amount of memory that an algorithm or operation needs to run
according to its input size.
Rate of Growth:
• The rate at which the performance of an algorithm increases as a function of input size is
called as rate of growth. The commonly used rate of growth is,
• The relationship between different rates of growth is given as,
 Time complexity Name

1 Constant
log n Logarithmic
n Linear
n log n Linear logarithmic
n2 Quadratic
n3 Cubic
2n Exponential

Asymptotic Analysis
• Asymptotic analysis, gives an idea about the performance of the algorithm based on the input size. It
should not calculate the exact running time, but find the relation between the running time and the
input size. We should follow the running time when the size of the input is increased.
• For the space complexity, the goal is to get the relation or function that how much space in the main
memory is occupied to complete the algorithm.
• Algorithm analysis are broadly classified into three types such as
• Best case analysis: This analysis gives a lower bound on the run-time. It describes the behaviour of
an algorithm under optimal conditions.
 Worst case analysis: This analysis gives the upper bound of the running time of algorithms. In this
case, a maximum number of operations are executed.
• Average case analysis: This analysis gives the region between the upper and lower bound of the
running time of algorithms. In this case, the number of executed operations is not minimum and not
maximum.
ASYMPTOTIC NOTATIONS
Asymptotic notation is one of the most efficient ways to calculate the time complexity of an
algorithm. Asymptotic notations are mathematical tools to represent time complexity of algorithms
for asymptotic analysis. The three asymptotic notations used to represent time complexity of
algorithms are,
The Big O (Big-Oh) Notation
The Big Ω (Big-Omega) Notation
The Big  (Big-Theta) Notation
The Big (O) Notation
Big Oh is an Asymptotic Notation for the worst-case scenario. The Big-O notation defines
asymptotic upper bound of an algorithm, it bounds a function only from above.

It is represented as f(n) = O(g(n)). That is, at higher values of n, the upper bound of f(n) is g(n).

The Mathematical Definition of Big-Oh

f(n) ∈ O(g(n)) if and only if there exist some positive constant c and some non-negative integer n₀
such that, f(n) ≤ c g(n) for all n ≥ n₀, n₀ ≥ 1 and c>0.

The above definition says, in the worst case, let the function f(n) be the algorithm's runtime,
and g(n) be an arbitrary time complexity. Then O(g(n)) says that the function f(n) never grows faster
than g(n) that is f(n)<=g(n) and g(n) is the maximum number of steps that the algorithm can attain.
In the above graph c. g(n) is a function that gives the maximum runtime (upper bound) and f(n) is the
algorithm’s runtime.
The Big Omega () notation:
Big Omega is an Asymptotic Notation for the best-case scenario. Big  notation defines an
asymptotic lower bond.
The Mathematical Definition of Big-Omega
f(n) ∈ Ω(g(n)) if and only if there exist some positive constant c and some non-negative integer n₀
such that, f(n) ≥ c g(n) for all n ≥ n₀, n₀ ≥ 1 and c>0.
The above definition says, in the best case, let the function f(n) be the algorithm’s runtime
and g(n) be an arbitrary time complexity. Then Ω(g(n)) says that the function g(n) never grows more
than f(n) i.e. f(n)>=g(n), g(n) indicates the minimum number of steps that the algorithm will attain. In
the above graph, c.g(n) is a function that gives the minimum runtime (lower bound) and f(n) is the
algorithm’s runtime.
The Big Theta () Notation:
Big Theta is an Asymptotic Notation for the average case, which gives the average growth for a
given function. Theta Notation is always between the lower bound and the upper bound. It provides
an asymptotic average bound for the growth rate of an algorithm. If the upper bound and lower bound
of the function give the same result, then the Θ notation will also have the same rate of growth.
The Mathematical Definition of Big-Theta
f(n) ∈  (g(n)) if and only if there exist some positive constant c₁ and c₂ some non-negative integer n₀
such that, c₁ g(n) ≤ f(n) ≤ c₂ g(n) for all n ≥ n₀, n₀ ≥ 1 and c>0.
The above definition says in the average case, let the function f(n) be the algorithm’s runtime
and g(n) be an arbitrary time complexity. Then  (g(n)) says that the function g(n) encloses the
function f(n) from above and below using c1.g(n) and c2.g(n).
 In the above graph, c1.g(n) and c2.g(n) encloses the function f(n). This  notation gives the realistic
time complexity of an algorithm.
RECURSION
Recursion is a technique by which a function makes one or more calls to itself during execution.
In computing, recursion provides an elegant and powerful alternative for performing repetitive tasks.
When one invocation of the function makes a recursive call, that invocation is suspended until the
recursive call completes.
The factorial function
• The factorial function is a classic mathematical function that has a natural recursive definition.
• The factorial of a positive integer n, is defined as the product of the integers from 1 to n. if n = 0, then n!
is defined as 1.
• For example, 5! = 5 . 4 . 3 . 2 . 1 = 120 and note that 5 ! = 5. (4.3.2.1) = 5. 4!. Generally, for a positive
integer n, we can define n ! = n. (n – 1) !. In this case, n = 0 is the base class. It is defined non recursively is
terms of fixed quantities. n (n-1)! is a recursive case.
Recursive implementation of the factorial function
A recursive implementation of the factorial function is,
def factorial(n):
if n = = 0:
return 1
else:
return n*factorial(n-1)
This function repetition is provided by the repeated recursive invocation of the function. When the
function is invoked, its argument is smaller by one and when a base case is reached, no further recursive
calls are made.

• The execution of a recursive function is illustrated using a recursive trace. Each entry of the trace
 corresponds to a recursive call. Each new recursive function call is indicated by a downward arrow to a
new invocation. When the function returns, an arrow showing this return is drawn and the return value
may be indicated alongside this arrow.
• In python, when a function is called a structure known as an activation record or a frame is created to
store information about the progress of that invocation of the function. This activation record includes a
namespace for storing the function call’s parameters, local variables and information about which
command in the body of the function is currently executing.
• When the execution of a function leads to a nested function call, the execution of the former call is
suspended and its activation record stores the place where the control should continue upon return of the
nested call. That is, there is a different activation record for each active call.
Binary Search:
• When the sequence is unsorted the standard approach for searching a target value is sequential search.
When the sequence is sorted and indexable, then binary search is used to efficiently locate a target value
within a sorted sequence of n elements.
• For any index j, all the values stored at indices 0 to j-1 are less than or equal to the value at index j, and all
the values stored at indices j+1 to n-1 are greater than equal to that at index j. This allows us to quickly
search target value.
• The algorithm maintains two parameters, low and high, such that all the candidate entries have index at
least low and at most high. Initially, low = 0 and high = n−1. Then we compare the target value to the
median candidate, that is, the item data[mid] with index

mid = (low+high)/2.
Consider three cases:
If the target equals data[mid], then we have found the item, and the search terminates successfully.
 If target < data[mid], then we recur on the first half of the sequence, that is, on the interval of
indices from low to mid−1.
 If target > data[mid], then we recur on the second half of the sequence, that is, on the interval
of indices from mid+1 to high.
An unsuccessful search occurs if low > high, as the interval [low, high] is empty. This algorithm is known as
binary search.
Implementation
def binarysearch(data, target, low, high):
if low > high:
return False
else:
mid = (low + high) // 2
if target == data[mid]:
return True
 elif target < data[mid]:
return binarysearch(data, target, low, mid − 1)
else:
return binarysearch(data, target, mid + 1, high)

This binary search algorithm requires O(log n) time. Whereas the sequential search algorithm uses O(n) time.

File Systems:
• File system for a computer has a recursive structure in which directories can be nested arbitrarily deep within
other directories. Recursive algorithms are widely to explore and manage these file systems.
• Modern operating systems define file-system directories in a recursive way. A file system consists of a top-
level directory, consists of files and other directories, which is turn contain files and other directories and so
on.
• The representation of such file system is,
• The file system representation uses recursive algorithms for copying a dictionary, deleting a dictionary etc.
In this example we consider computing the total disk usage for all files and directories nested within a
particular directory.

Tower of Hanoi Puzzle:

• The Tower of Hanoi puzzle consists of a board with three vertical poles and a stack of disks.
The diameter of the disks increases from the top to bottom creating tower structure.
• The illustration of Tower of Hanoi with three disks is shown in Fig.
The objective of tower of hanoi puzzle is to move all the disks from the starting pole to one of the
other two poles to create a new tower, adhering two conditions.
1. Only one disk can be moved at a time.
2. A larger disk can never be placed on top of a smaller disk.
This problem can be solved by recursive operation. Given n disks and three poles are named
source(s) destination (D) and intermediate (I).
 Move the top n – 1 disks from pole S to pole I using pole D.
 Move the remaining disks from pole S to pole D.
 Move the n –1 disks from pole I to pole D using pole S.
 The first and last steps are recursive calls to the same operation but using different poles as
the source, destination and intermediate designations. The second step is a process where
single disk to move. It is a base case.
Step 1 Step 2

Step 3 Step 4

Step 5 Step 6

Step 7

Implementation
def move (n, src, dest, temp):
if n > = 1 :
move (n-1, src, temp, dest)
print (“move %d  %d” % (src, dest))
move (n-1, temp, dest, src)