UNIT-2

UNIT-2 TOPICS

 Handling exceptions,
 Exceptions as a control flow

mechanism,
 Assertions, Abstract Data Types and

Classes,
 Inheritance,

 Encapsulation and information hiding,

 Search Algorithms, Sorting

Algorithms,
 Hashtables
ERRORS IN A PYTHON PROGRAM

 1. Compile time errors – usually the easiest to

spot, compile time errors occur when you make
a mistake.

 Not ending an if statement with the colon is an

example of an compile time error, as is
misspelling a Python keyword (e.g.
using whille instead of while).

 Syntax error usually appear at compile time

and are reported by the interpreter.
 Runtime errors:
 Runtime error refers to an error that takes place

while executing a program.

 As opposed to the compilation errors that occur

during a program compilation, runtime errors
occur only during the execution of the program.

 Runtime errors imply bugs in the program or

issues that the developers had expected but were
unable to correct.

 For example, insufficient memory can often

trigger a runtime error.
 Logical errors –

 also called semantic errors, logical errors

cause the program to behave incorrectly, but
they do not usually crash the program.

 Unlike a program with syntax errors, a program

with logic errors can be run, but it does not
operate as intended.
 WHAT IS EXCEPTION?
 An exception is an event, which occurs during the
execution of a program that disrupts the normal flow
of the program's instructions.
 Python has many built-in exceptions which forces

your program to output an error when something in

it goes wrong.
 In general, when a Python script encounters a

situation that it cannot cope with, it raises an

exception.
 An exception is a Python object that represents an

error.
 When a Python script raises an exception, it must

either handle the exception immediately otherwise it

terminates and quits.
 HANDLING AN EXCEPTION
 If you have some suspicious code that may raise an
exception, you can defend your program by placing
the suspicious code in a try: block. After the try:
block, include an except: statement, followed by a
block of code which handles the problem as smartly
as possible.
 If an error is encountered, a try block code execution

is stopped and transferred down to the except block.

 In addition to using an except block after the try

block, you can also use the finally block.

 The code in the finally block will be executed

regardless of whether an exception occurs.

 Raising an exception breaks current code execution

and returns the exception back until it is handled.

 RAISING AN EXCEPTIONS

 You can raise exceptions in several ways by using

the raise statement. The general syntax for the
raise statement is as follows.
 Syntax
 raise [Exception as args [, traceback]]]
 Here, Exception is the type of exception (for
example, NameError) and argument is a value for
the exception argument. The argument is
optional; if not supplied, the exception argument
is None.
 The final argument, traceback, is also optional

(and rarely used in practice), and if present, is

the traceback object used for the exception
 ASSERTION
 The assert statement is intended for
debugging statements.
 It can be seen as an abbreviated notation for a

conditional raise statement, i.e. an exception

is only raised, if a certain condition is not True.
 Without using the assert statement,

 Sysntax:

 assert <some_test>, <message>

 The line above can be "read" as: If

<some_test> evaluates to False, an

exception is raised and <message> will
be output.
>>> x = 5
>>> y = 3
>>> assert x < y, "x has to be smaller than y"
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AssertionError: x has to be smaller than y
 CLASS & OBJECT IN PYTHON
 A class in python is the blueprint from which specific
objects are created.
 It lets you structure your software in a particular way.
 Classes allow us to logically group our data and
function in a way that it is easy to reuse and a
way to build upon if need to be.
 In the first image (A), it represents a blueprint of a house
that can be considered as Class. With the same
blueprint, we can create several houses and these can
be considered as Objects.
 In Class, attributes can be defined into two parts:
 OBJECT
 An object is an instance of a class.
 It is a collection of attributes (variables) and methods.
 We use the object of a class to perform actions.
 Every object has the following property.
 Identity: Every object must be uniquely identified.
 State: An object has an attribute that represents a state of
an object, and it also reflects the property of an object.
 Behavior: An object has methods that represent its
behavior.
 Object creation is divided into two parts in Object
Creation and Object initialization
 Internally, the __new__ is the method that creates the
object
 And, using the __init__() method we can implement
constructor to initialize the object.
 Syntax
 <object-name> = <class-name>(<arguments>)
CREATE A CLASS IN PYTHON
 The name of the class immediately follows the keyword class
followed by a colon as follows −
class class_name:
'''This is a docstring. I have created a new
class'''
<statement 1>
<statement 2>
.
.
<statement N>

 The class has a documentation string, which can be

accessed via ClassName.__doc__.
 class_name: It is the name of the class
 Docstring: It is the first string inside the class and has a
brief description of the class. Although not mandatory, this is
highly recommended.
 statements: Attributes and methods
 EXAMPLE OF CLASS & OBJECT
class Student:
# class variables
college_name = "MCA"

# constructor
def __init__(self, name, age):
# instance variables
[Link] = name
[Link] = age

s1 = Student("Rj", 12)
# access instance variables
print('Student:', [Link], [Link])

# access class variable

print("College name:", Student.college_name)

# Modify instance variables

[Link] = 'Raviraj'
[Link] = 14
print('Student:', [Link], [Link])

# Modify class variables

Student.college_name = "Infotech"
print('college name:', Student.college_name)
THE SELF PARAMETER
 The self parameter is a reference to the
current instance of the class, and is used to
access variables that belongs to the class.
 It does not have to be named self , you can call it

whatever you like, but it has to be the first

parameter of any function in the class.

class Person:
def __init__(self, name, age):
[Link] = name
[Link] = age

def myfunc(abc):
print("Hello my name is " + [Link])

p1 = Person("Raviraj", 36)
[Link]()
CONSTRUCTOR IN PYTHON
 A constructor is a special method used to
create and initialize an object of a class. This
method is defined in the class.

 The constructor is executed automatically at the

time of object creation.

 The primary use of a constructor is to declare

and initialize data member / instance
variables of a class.

 The constructor contains a collection of statements

(i.e., instructions) that executes at the time of object
creation to initialize the attributes of an object.
CONSTRUCTOR IN PYTHON
 In Python, Object creation is divided into two parts
in Object Creation and Object initialization

 Internally, the __new__ is the method that creates

the object

 And, using the __init__() method we can

implement constructor to initialize the object.
SYNTAX OF A CONSTRUCTOR
 def __init__(self):
# body of the constructor
 Where,

 def: The keyword is used to define function.

 __init__() Method: It is a reserved method. This

method gets called as soon as an object of a class is
instantiated.
 self: The first argument self refers to the current
object. It binds the instance to the __init__() method.
It’s usually named self to follow the naming
convention.
 The __init__() method arguments are optional. We can
define a constructor with any number of arguments.
EXAMPLE OF CONSTRUCTOR
class Student:
# constructor
# initialize instance variable
def __init__(self, name):
print('Inside Constructor')
[Link] = name
print('All variables initialized')

# instance Method
def show(self):
print('Hello, my name is', [Link])

# create object using constructor

s1 = Student(‘Raviraj')
[Link]()
NOTES FOR CONSTRUCTOR
 For every object, the constructor will be executed
only once. For example, if we create four objects,
the constructor is called four times.

 In Python, every class has a constructor, but it’s

not required to define it explicitly. Defining
constructors in class is optional.

 Python will provide a default constructor if no

constructor is defined.
TYPES OF CONSTRUCTORS
 In Python, we have the following three types of
constructors.
 DefaultConstructor
 Non-parametrized constructor
 Parameterized constructor
DEFAULT CONSTRUCTOR
 If you do not implement any constructor in your
class or forget to declare it, the Python inserts a
default constructor into your code on your behalf.

 This constructor is known as the default constructor.

 It does not perform any task but initializes the objects.

It is an empty constructor without a body.

 The default constructor is not present in the source py

file. It is inserted into the code during compilation if not
exists.

 If you implement your constructor, then the default

constructor will not be added.
DEFAULT CONSTRUCTOR EXAMPLE
class Employee:

def display(self):
print('Inside Display')

emp = Employee()
[Link]()
NON-PARAMETRIZED CONSTRUCTOR

 A constructor without any arguments is called

a non-parameterized constructor.

 This type of constructor is used to initialize each

object with default values.

 This constructor doesn’t accept the arguments

during object creation.

 Instead, it initializes every object with the same

set of values.
NON-PARAMETRIZED CONSTRUCTOR
EXMAPLE
class Company:

# no-argument constructor
def __init__(self):
[Link] = “Sankul"
[Link] = "Amreli"

# a method for printing data members

def show(self):
print('Name:', [Link], 'Address:', [Link])

# creating object of the class

cmp = Company()

# calling the instance method using the object

[Link]()
PARAMETERIZED CONSTRUCTOR
 A constructor with defined parameters or
arguments is called a parameterized
constructor.

 We can pass different values to each object at

the time of creation using a parameterized
constructor.

 The first parameter to constructor is self that is

a reference to the being constructed, and the rest of
the arguments are provided by the programmer.

 A parameterized constructor can have any

number of arguments.
PARAMETERIZED CONSTRUCTOR
EXAMPLE

class Employee:
# parameterized constructor
def __init__(self, name, age, salary):
[Link] = name
[Link] = age
[Link] = salary

# display object
def show(self):
print([Link], [Link], [Link])

# creating object of the Employee class

emma = Employee('Emma', 23, 7500)
[Link]()

kelly = Employee('Kelly', 25, 8500)

[Link]()
CONSTRUCTOR WITH DEFAULT
VALUES

class Student:
# constructor with default values age and classroom
def __init__(self, name, age=12, classroom=7):
[Link] = name
[Link] = age
[Link] = classroom

# display Student
def show(self):
print([Link], [Link], [Link])

# creating object of the Student class

s1 = Student(‘sankul')
[Link]()

s2 = Student(‘BCA', 13)
[Link]()
 Instead of using the normal statements to access
attributes, you can use the following functions −
 The getattr(obj, name[, default]) : to access the

attribute of object.
 The hasattr(obj,name) : to check if an attribute

exists or not.
 The setattr(obj,name,value) : to set an attribute.

If attribute does not exist, then it would be created.

 The delattr(obj, name) : to delete an attribute.

 hasattr(emp1, 'age') # Returns true if 'age'

attribute exists
 getattr(emp1, 'age') # Returns value of 'age'
attribute
 setattr(emp1, 'age', 8) # Set attribute 'age' at 8
 delattr(empl, 'age') # Delete attribute 'age'
 BUILT-IN CLASS ATTRIBUTES
 Every Python class keeps following built-in
attributes and they can be accessed using dot
operator like any other attribute:
 __dict__: Dictionary containing the class's

namespace.
 __doc__: Class documentation string or none, if

undefined.
 __name__: Class name.

 __module__: Module name in which the class is

defined. This attribute is "__main__" in interactive

mode.
 __bases__: A possibly empty tuple containing the

base classes, in the order of their occurrence in the

base class list.
 NAMESPACES
 A namespace is a collection of names.
 Every entity in python is considered an object.
 We give some names to every object like variable, class,
and function for identification. Often these names are
known as identifiers in python.
 So, the name is nothing but the identifier.
 All these names and where we use value are stored in the
main memory at a unique location.
 This location is known as space. So the location
allocated to an object name and its value is known
as python namespaces.
 Python also maintains its namespace that is known as a
python dictionary.
 All namespaces in python are like dictionaries in
which names are considered as keys, and dictionary
values are the actual values associated with those names.
 So, a namespace is a practical approach to define the
scope, and it helps to avoid name conflicts.
 PYTHON NAMESPACE EXAMPLE
 File directories in a computer system are the best
example of namespaces. Files may have the same
names but different data and are stored at various
locations.
 The telephone directory is a good real-time

example for the namespace.

 If we try to search a phone number of a person

named Shubham, there are multiple entries, and it

will be difficult to find the right one. But if we know
the surname of Shubham, we can see the correct
number.
 In this case, a person's name is a name or identifier in

python, and space depends on the person’s location.

 globals() --> global namespaces

 dir(__builtins__) --> builtin namespaces

BUILT-IN NAMESPACE

 When we run the Python interpreter without creating

any user-defined function, class, or module.

 Some functions like input(), print(), type() are always

present. These are built-in python namespaces.

name=input("Enter your name:") #input() is built-in

function
print(name) #print() is built-in
function
In the above code we are using input() and print() without creating any
function or without accessing any module.
GLOBAL NAMESPACE

 When we create a module, it creates its namespaces,

and these are called global namespaces.

 The global namespace can access built-in namespaces.

x=10 #variable declared in a global namespace with the

global scope of variable in python
def f1(): #function definition
print(x) #variable accessed inside the function
f1()

In the code given above, the variable x is declared in a global

namespace and has a global scope of variable in python.
LOCAL NAMESPACE
 When we create a function, it creates its
namespaces, and these are called local
namespaces.
 A local namespace can access global as well as built-
in namespaces.
def f1(): #function definition
print("function start ")
def f2():
var = 10 # local scope of variable in python
print("local function, value of var:",var)
f2()
print("Try printing var from outer function: ",var) #Error
f1()

In the code given above, the variable var is declared in a local namespace
and has a local scope of variable in python.
CREATE NAMESPACE

• In the above example, we have used a built-in namespace i.e. print()

which is accessed by global and local namespace.
• Also, we have created global namespace x and local namespace y.
SCOPE OF VARIABLE IN PYTHON
ACCESS MODIFIERS IN PYTHON
 Encapsulation can be achieved by declaring the data
members and methods of a class either as private or
protected.
 But In Python, we don’t have direct access modifiers

like public, private, and protected.

 We can achieve this by using

single underscore and double underscores.

 Access modifiers limit access to the variables and

methods of a class.
 Python provides three types of access modifiers

private, public, and protected.

 Public Member: Accessible anywhere from otside
oclass.
 Private Member: Accessible within the class
 Protected Member: Accessible within the class and its
sub-classes
DATA HIDING USING ACCESS MODIFIERS
PUBLIC MEMBER
 Public data members are accessible within and outside of a class. All
member variables of the class are by default public.

class Employee:
# constructor
def __init__(self, name, salary):
# public data members
[Link] = name
[Link] = salary

# public instance methods

def show(self):
# accessing public data member
print("Name: ", [Link], 'Salary:', [Link])

# creating object of a class

emp = Employee(‘Raviraj’, 10000)

# accessing public data members

print("Name: ", [Link], 'Salary:', [Link])

# calling public method of the class

[Link]()
PRIVATE MEMBER
 We can protect variables in the class by marking them private.
 To define a private variable add two underscores as a
prefix at the start of a variable name.
 Private members are accessible only within the class, and we
can’t access them directly from the class objects.
class Employee:
# constructor
def __init__(self, name, salary):
# public data member
[Link] = name
# private member
self.__salary = salary

# creating object of a class

emp = Employee('Jessa', 10000)

# accessing private data members

print('Salary:', emp.__salary) AttributeError: 'Employee' object has no attribute
'__salary'
 We can access private members from outside of a
class using the following two approaches
 Createpublic method to access private members
 Use name mangling
PUBLIC METHOD TO ACCESS PRIVATE
MEMBERS
class Employee:
# constructor
def __init__(self, name, salary):
# public data member
[Link] = name
# private member
self.__salary = salary

# public instance methods

def show(self):
# private members are accessible from a class
print("Name: ", [Link], 'Salary:', self.__salary)

# creating object of a class

emp = Employee('Jessa', 10000)

# calling public method of the class

[Link]()
NAME MANGLING TO ACCESS PRIVATE
MEMBERS
class Employee:
# constructor
def __init__(self, name, salary):
# public data member
[Link] = name
# private member
self.__salary = salary

# creating object of a class

emp = Employee('Jessa', 10000)

print('Name:', [Link])
# direct access to private member using name mangling
print('Salary:', emp._Employee__salary)
PROTECTED MEMBER
 Protected members are accessible within the class
and also available to its sub-classes. To define a
protected member, prefix the member name with a
single underscore _.

 Protected data members are used when you

implement inheritance and want to allow data
members access to only child classes.
# base class
class Company:
def __init__(self):
# Protected member
self._project = "NLP"

# child class
class Employee(Company):
def __init__(self, name):
[Link] = name
Company.__init__(self)

def show(self):
print("Employee name :", [Link])
# Accessing protected member in child class
print("Working on project :", self._project)

c = Employee("Jessa")
[Link]()

# Direct access protected data member

print('Project:', c._project)
 Information Hiding and conditional logic
for setting an object attributes
 TYPES OF METHODS
 Class methods
 A class method is one that belongs to the class as a
whole. It doesn't require an instance. Instead, the class
will automatically be sent as the first argument. A class
method is declared with the @classmethod decorator.

class Foo(object):
@classmethod
def hello(cls):
print("hello from %s" % cls.__name__)
[Link]()
-> "Hello from Foo"
Foo().hello()
-> "Hello from Foo"
INSTANCE METHODS
 On the other hand, an instance
method requires an instance in order to call it,
and requires no decorator.
 This is by far the most common type of method.

 Example

class Foo(object):
def hello(self):
print("hello from %s" %
self.__class__.__name__)
f=Foo()
[Link]()
 STATIC METHODS
 A static method is similar to a class method, but
won't get the class object as an automatic
parameter.
 It is created by using the @staticmethod decorator.

 Example

class Foo(object):
@staticmethod
def hello():
print("hello from %s" % cls.__name__)

[Link]()
CLASS METHOD VS STATIC METHOD
 A class method takes cls as first parameter while a
static method needs no specific parameters.

 A class method can access or modify class state

while a static method can’t access or modify it.

 In general, static methods know nothing about class

state. They are utility type methods that take some
parameters and work upon those parameters. On
the other hand class methods must have class as
parameter.

 We use @classmethod decorator in python to create

a class method and we use @staticmethod decorator
to create a static method in python.
 INHERITANCE
 Inheritance is used to specify that one class will get
most or all of its features from its parent class.

 It is a feature of Object Oriented Programming.

 It is a very powerful feature which facilitates users to
create a new class with a few or more modification to
an existing class.
 The new class is called child class or derived
class and the main class from which it inherits
the properties is called base class or parent
class.
 The child class or derived class inherits the features
from the parent class, adding new features to it.
 It facilitates re-usability of code.
 TYPES OF INHERITANCE
 There are five types of inheritance in python programming:
 Single inheritance
 In single inheritance, a child class inherits from a single-parent
class.
 Multiple Inheritance
 In multiple inheritance, one child class can inherit from multiple
parent classes.
 Multilevel Inheritance
 In multilevel inheritance, a class inherits from a child class or
derived class. Suppose three classes A, B, C. A is the superclass, B
is the child class of A, C is the child class of B. In other words, we
can say a chain of classes is called multilevel inheritance.
 Hierarchical Inheritance
 In Hierarchical inheritance, more than one child class is derived from a
single parent class. In other words, we can say one parent class and
multiple child classes.
 Hybrid Inheritance
 When inheritance is consists of multiple types or a combination of
different inheritance is called hybrid inheritance.
HYBRID INHERITANCE
class
DerivedClassName(BaseClassName):
<statement-1>
.
.
.
<statement-N>
POLYMORPHISM
 Polymorphism in Latin word which made up of
‘ploy’
means many and ‘morphs’ means forms.

 From the Greek , Polymorphism means

many(poly)
shapes (morph).

 This is something similar to a word having several

different meanings depending on the context.

 Generally, polymorphism means that a method or

function is able to handle with different types of
input.
 In
OOP , Polymorphism is the characteristic of
being able to assign a different meaning to a
particular symbol or operator in different
contexts specifically to allow an entity such
as a variable, a function or an object to have
more than one form.

 Thereare two kinds of Polymorphism.

 Overloading :
 Two or more methods with different signatures
 Overriding:
 Replacing an inherited method with another
having the same signature
 METHOD OVERLOADING
 In Python you can define a method in such a way
that there are multiple ways to call it.
 Given a single method or function, we can specify

the number of parameters ourself.

 Depending on the function definition, it can be

called with zero, one, two or more parameters.

 This is known as method overloading.

 Like other languages (for example method

overloading in C++) do, python does not

supports method overloading.
 We may overload the methods but can only use

the latest defined method.

 METHOD OVERRIDING
 In inheritance, all members available in the parent
class are by default available in the child class.

 If the child class does not satisfy with parent

class implementation, then the child class is
allowed to redefine that method by extending
additional functions in the child class. This concept
is called method overriding.

 When a child class method has the same name,

same parameters, and same return type as a
method in its superclass, then the method in the
child is said to override the method in the parent
class.
METHOD OVERRIDING
 ISSUBCLASS() AND ISINSTANCE()
FUNCTION

 isinstance(object, classinfo)
 Check if object is an instance of class classinfo or a tuple
of classes.
 issubclass(class, classinfo)
 Check if class is a subclass of another class classinfo or
a tuple of classes.
THE SUPER() METHOD

 In Python, super() built-in has two major use

cases:
 Allowsus to avoid using base class explicitly
 Working with Multiple Inheritance

 The super() builtin returns a proxy object

that allows you to refer parent class by
'super'.

 super() with Single Inheritance

 super() with Multiple Inheritance
ABSTRACT DATA TYPE
 Abstract Data Type(ADT) is a data type, where only
behavior is defined but not implementation.
 abstract data types are the entities that are definitions of data
and operations but do not have implementation details.
 In this case, we know the data that we are storing and the
operations that can be performed on the data, but we don't
know about the implementation details.
 The reason for not having implementation details is that every
programming language has a different implementation
strategy.
 for example; C data structure is implemented using
structures while a C++ data structure is implemented using
objects and classes.
 For example, a List is an abstract data type that is
implemented using a dynamic array and linked list. A queue
is implemented using linked list-based queue, array-based
queue, and stack-based queue. A Map is implemented using
Tree map, hash map, or hash table.
 ABSTRACT DATA TYPE MODEL

 Abstraction: It is a technique of hiding the internal details

from the user and only showing the necessary details to the user.
 Encapsulation: It is a technique of combining the data and

the member function in a single unit is known as

encapsulation.
 The above figure shows the ADT model. There are
two types of models in the ADT model, i.e., the
public function and the private function.

 The ADT model also contains the data structures

that we are using in a program.

 In this model, first encapsulation is performed, i.e.,

all the data is wrapped in a single unit, i.e., ADT.

 Then, the abstraction is performed means showing

the operations that can be performed on the data
structure and what are the data structures that we
are using in a program.
 Real life example:
 book is Abstract (Telephone Book is an implementation)
ENCAPSULATION AND INFORMATION HIDING
 Encapsulation is seen as the bundling of
data with the methods that operate on
that data.
 Information hiding on the other hand is the
principle that some internal information or
data is "hidden", so that it can't be
accidentally changed.
 Data encapsulation via methods doesn't
necessarily mean that the data is hidden.
You might be capable of accessing and
seeing the data anyway, but using the
methods is recommended.
 Finally, data abstraction is present, if both
data hiding and data encapsulation is
used.
 Encapsulation is often accomplished by providing
two kinds of methods for attributes:

 The methods for retrieving or accessing the values

of attributes are called getter methods.

 Getter methods do not change the values of

attributes, they just return the values.

 The methods used for changing the values of

attributes are called setter methods.
 SEARCH ALGORITHMS
 Searching is also a common and well-studied task.
This task can be described formally as follows:
 Given a list of values, a function that compares two

values and a desired value, find the position of the

desired value in the list.
 We will look at two algorithms that perform this task:

 linear
search, which simply checks the values in
sequence until the desired value is found.

 binary search, which requires a sorted input list, and

checks for the value in the middle of the list,
repeatedly discarding the half of the list which contains
values which are definitely either all larger or all smaller
than the desired value
 LINEAR SEARCH
 Linear search is the most basic kind of search
method.
 It involves checking each element of the list in turn,

until the desired element is found.

 For example, suppose that we want to find the

number 3.8 in the following list:

 We start with the first element, and perform a
comparison to see if its value is the value that we
want.
 In this case, 1.5 is not equal to 3.8, so we move

onto the next element:

 We perform another comparison, and see
that 2.7 is also not equal to 3.8, so we move
onto the next element:
 We perform another comparison and determine that we
have found the correct element. Now we can end the
search and return the position of the element (index 2).
 We had to use a total of 3 comparisons when searching

through this list of 4 elements.

 How many comparisons we need to perform

depends on the total length of the list, but also

whether the element we are looking for is near the
beginning or near the end of the list. In the worst-case
scenario, if our element is the last element of the list, we
will have to search through the entire list to find it.
 If we search the same list many times, assuming that all

elements are equally likely to be searched for, we will on

average have to search through half of the list each
time. The cost (in comparisons) of performing linear
search thus scales linearly with the length of the list.
ASSIGNMENT
 Write a function which implements linear
search. It should take a list and an element
as a parameter, and return the position of
the element in the list. If the element is not
in the list, the function should raise an
exception. If the element is in the list
multiple times, the function should return the
first position.
 BINARY SEARCH
 Binary search is a more efficient search algorithm
which relies on the elements in the list being sorted.
 We apply the same search process to progressively

smaller sub-lists of the original list, starting with the

whole list and approximately halving the search area
every time.
 We first check the middle element in the list.

 If it is the value we want, we can stop.

 If it is higher than the value we want, we

repeat the search process with the portion of

the list before the middle element.
 If it is lower than the value we want, we

repeat the search process with the portion of

the list after the middle element.
 For example, suppose that we want to find
the value 3.8 in the following list of 7
elements:
 First we compare the element in the middle

of the list to our value. 7.2 is bigger than

3.8, so we need to check the first half of the
list next.
 Now the first half of the list is our new list to
search. We compare the element in the
middle of this list to our value. 2.7
is smaller than 3.8, so we need to search
the second half of this sublist next.
 The second half of the last sub-list is just a
single element, which is also the middle
element. We compare this element to our
value, and it is the element that we want.
 We have performed 3 comparisons in total when
searching this list of 7 items.
 The number of comparisons we need to perform

scales with the size of the list, but much more

slowly than for linear search – if we are searching
a list of length N, the maximum number of
comparisons that we will have to perform is log2N.
ASSIGNMENT
 Write a function which implements
binary search. You may assume that the
input list will be sorted. Hint: this
function is often written recursively.
 SORTING ALGORITHMS

 Given a list of values and a function that compares

two values, order the values in the list from
smallest to largest.

 The values might be integers, or strings or even

other kinds of objects.
 We will examine two algorithms:
 Selection sort, which relies on repeated selection of
the next smallest item
 Merge sort, which relies on repeated merging of
sections of the list that are already sorted
 SELECTION SORT
 Selection sort is a sorting algorithm that picks the
smallest element from an unsorted list and sets it
at the top of the unsorted list in each iteration.

 The selection sort algorithm is an in-place

comparison-based method that divides the input
array into two sections: a sorted array on the
left and an unsorted array on the right.
 Steps
 Assign the minimum value to array index 0.
 Search Smallest element input in an array.
 Swap with value at the location of minimum value.
 Increment minimum value to point next element.
 Repeat until the array is sorted.
 ALGORITHM

1. Create a function Selection_Sort that takes an

array as an argument
2. Create a loop with a loop variable i that counts
from 0 to the length of the array – 1
3. Declare smallest with the initial value i
4. Create an inner loop with a loop variable j that
counts from i + 1 up to the length of the array
– 1.
5. if the elements at index j are smaller than
the element at index smallest, then set
smallest equal to j
6. swap the elements at indexes i and smallest
7. Print the sorted list
 MERGE SORT
 We now turn our attention to using a divide and conquer
strategy as a way to improve the performance of sorting
algorithms.
 The first algorithm we will study is the merge sort.
 Merge sort is a recursive algorithm that continually
splits a list in half.
 If the list is empty or has one item, it is sorted by definition
(the base case).
 If the list has more than one item, we split the list and
recursively invoke a merge sort on both halves.
 Once the two halves are sorted, the fundamental operation,
called a merge, is performed.
 Merging is the process of taking two smaller sorted lists and
combining them together into a single, sorted, new list. Figure
10 shows our familiar example list as it is being split by
mergeSort. Figure 11 shows the simple lists, now sorted, as
they are merged back together.
 The algorithm for merge sort may be written as this list of steps:
 Create a temporary storage list which is the same size as the list to
be sorted.
 Start by treating each element of the list as a sorted one-element
sub-section of the original list.
 Move through all the sorted sub-sections, merging adjacent pairs as
follows:
 Use two variables to point to the indices of the smallest
uncopied items in the two sorted sub-sections, and a third
variable to point to the index of the start of the temporary
storage.
 Copy the smaller of the two indexed items into the indicated
position in the temporary storage. Increment the index of the
sub-section from which the item was copied, and the index into
temporary storage.
 If all the items in one sub-section have been copied, copy the
items remaining in the other sub-section to the back of the list in
temporary storage. Otherwise return to step 3 ii.
 Copy the sorted list in temporary storage back over the section
of the original list which was occupied by the two sub-sections
that have just been merged.
 If only a single sorted sub-section remains,
the entire list is sorted and we are done.
Otherwise return to the start of step 3.
BUBBLE SORT
 Bubble Sort is a sorting algorithm used to sort list
items in ascending order by comparing two adjacent
values.
 If the first value is higher than second value, the first
value takes the second value position, while second
value takes the first value position.
 If the first value is lower than the second value, then
no swapping is done.

 This process is repeated until all the values in a list

have been compared and swapped if necessary.
 Each iteration is usually called a pass.
 The number of passes in a bubble sort is equal to the
number of elements in a list minus one.
IMPLEMENTING THE BUBBLE SORT
ALGORITHM
 We will breakdown the implementation into three (3)
steps, namely the problem, the solution, and the
algorithm that we can use to write code for any
language.
 The problem

 A list of items is given in random order, and we

would like to arrange the items in an orderly manner

 Consider the following list:
 [21,6,9,33,3]
 The solution
 Iterate
through the list comparing two adjacent elements
and swapping them if the first value is higher than the
second value.
 The result should be as follows:
 [3,6,9,21,33]
 The steps involved in the performance of a
Bubble Sort algorithm in Python are:
 The first and second elements in the list are compared
and swapped by the sorting program in case they are in
the wrong order.
 The second and third elements in the list are compared
and swapped by the sorting program in case they are in
the wrong order.
 The process continues until the last element present in
the list is compared and swapped in the same fashion.
 All the steps are iterated until the entire list gets sorted.
WHAT IS A HASH TABLE IN PYTHON?
 Hash tables are a form of data structure in which a
hash function is used to produce the address or
index value of a piece of data.

 Since the index value acts as a key for the data

value, you can access the data faster.

 In other words, a hash table contains key-value pairs,

but the key is created using a hashing function.

 As a result, a data element’s search and insertion

functions become considerably faster, since the key
values themselves become the index of the array
that holds the data.
 The dictionary data type in Python is used to
implement hash tables.
 The dictionary’s keys meet the following criteria:
 The dictionary’s keys are hashable, which means they’re
created using a hashing function that produces a unique
result for each unique value sent to it.
 In a dictionary, the order of data elements is not fixed.
# Declare a dictionary
dict = {'Name': 'Srija', 'Age': 15,'Loc': 'Hyd'}

#Access the dictionary with its key

print "dict['Name']: ", dict['Name']
print "dict['Age']: ", dict['Age']

# Declare a dictionary
dict = {'Name': 'Srija', 'Age': 15,'Loc': 'Hyd'}
dict['Age'] = 16; # Update existing entry
dict['School'] = 'DAV PUBLIC School'; # Add new entry
print "dict['Age']: ", dict['Age']
print "dict['School']: ", dict['School']

dict = {'Name': 'Srija', 'Age': 15,'Loc': 'Hyd'}

del dict['Name']; # remove entry with key 'Name'
[Link](); # remove all entries in dict
del dict ; # delete entire dictionary
 [Link]
objects/