PYTHON
PYTHON
sorted sub-list
Step 6 − Repeat until list is sorted
Step 4 − Shift all the elements in the sorted
sub-list that is greater than the value to be
sorted
Assume 44 is a sorted
44 16 83 07 67 21 34 45 10
list of 1 item
16 44 83 07 67 21 34 45 10 inserted 16
16 44 83 07 67 21 34 45 10 inserted 83
07 16 44 83 67 21 34 45 10 inserted 07
07 16 44 67 83 21 34 45 10 inserted 67
07 16 21 44 67 83 34 45 10 inserted 21
07 16 21 34 44 67 83 45 10 inserted 34
07 16 21 34 44 45 67 83 10 inserted 45
07 10 16 21 34 44 45 67 83 inserted 10
At the end of the pass the insertion algorithm will try to check the results of
sort algorithm gives the sorted output in the previously solved sub-problems. The
ascending order as shown below: solutions of overlapped sub-problems are
combined in order to get the better solution.
07 10 16 21 34 44 45 67 83
Steps to do Dynamic programming
4.6. Dynamic programming
• The given problem will be divided into
smaller overlapping sub-problems.
Dynamic programming is an
algorithmic design method that can be • An optimum solution for the given
used when the solution to a problem can problem can be achieved by using result
be viewed as the result of a sequence of of smaller sub-problem.
decisions. Dynamic programming approach
• Dynamic algorithms uses Memoization.
is similar to divide and conquer. The given
problem is divided into smaller and yet
smaller possible sub-problems. Note
Memoization or memoisation
Dynamic programming is used
is an optimization technique used
whenever problems can be divided into
primarily to speed up computer
similar sub-problems. so that their results
programs by storing the results of
can be re-used to complete the process.
previous function calls and returning
Dynamic programming approaches are
the cached result when the same inputs
used to find the solution in optimized way.
occur again.
For every inner sub problem, dynamic
41 Algorithmic Strategies
Points to remember:
• An algorithm is a finite set of instructions to accomplish a particular task.
• Algorithm consists of step-step-by instructions that are required to accomplish a task
and helps the programmer to develop the program.
• Program is an expression of algorithm in a programming language.
• Algorithm analysis deals with the execution or running time of various operations
involved.
• Space complexity of an algorithm is the amount of memory required to run to its
completion.
• Big Oh is often used to describe the worst-case of an algorithm.
• Big Omega is used to describe the lower bound which is best way to solve the space
complexity.
• The Time complexity of an algorithm is given by the number of steps taken by the
algorithm to complete the process.
• The efficiency of an algorithm is defined as the number of computational resources
used by the algorithm.
Evaluation
Part - I
43 Algorithmic Strategies
Part - II
1. What is an Algorithm?
2. Write the phases of performance evaluation of an algorithm.
3. What is Insertion sort?
4. What is Sorting?
5. What is searching? Write its types.
Part - III
Part - IV
Reference Books
Web References
www.wickipedia.org
1. Create an algorithm for grading systems of your class student’s Quarterly examination
marks by satisfying all necessary conditions.
45 Algorithmic Strategies
This is the question that is fretting The above statistical data has
the minds of teachers and students. maintained its grip with Python scoring
The present book is organized in 100 and C++ language stands second
such a way that even a novice reader can nipping at its heels with a 99.7 score.
grasp and work on python programming. Python being popular is used by a number
Testimonies of tech giants like Google, Instagram,
Pinterest, Yahoo, Disney, IBM, Nokia etc.
• "Python has been an important part
1. Python 100.0
of Google since the beginning and
2. C++ 99.7
remains so as the system grows and 3. Java 97.5
evolves. Today dozens of Google 4. C 96.7
engineers use Python, and we're 5. C# 89.4
looking for more people with skills 6. PHP 84.9
in this language." -- Peter Norvig, 7. R 82.8
director of search quality at Google, 8. JavaScript 82.6
Inc. 9. Go 76.4
10. Assembly 74.1
• "Python is fast enough for our
site and allows us to produce Many businesses are advised to choose
maintainable features in record times, Python for the following reasons:-
with a minimum of developers," • Easy syntax and readability
-- Cuong Do, Software Architect, • High level scripting language with
YouTube.com oops
• famous for enormous functions, add-
Python’s popularity has seen on modules, libraries, frameworks and
a steady and unflagging growth over tool-kits.
the recent years. Today, familiarity • Built-in functions supports scientific
with Python is an advantage for every computing.
programmer, as Python has infiltrated With the advent of computers,
every niche and has useful roles to play in there have been significant changes in the
any software solution. way we work in almost all the fields. The
Python has experienced an computerization has helped to improve
productivity and accelerate decision
impressive growth as compared to the
making in every organization. Even for
other languages. The IEEE Spectrum individuals, be it engineers, doctors,
magazine published by the Institute chartered accountants or homemakers, the
of Electrical & Electronics Engineers, style of working has changed drastically.
New York, ranks Python as the top language So as we go, let us accept the change and
for 2018, for the second consecutive year. move towards a brighter day ahead.
Learning Objectives
5.1 Introduction
47
(Or)
b = 350 a = 100
b = 350
c = a+b
c = a+b
print ("The Sum=", c) print ("The Sum=", c)
a=100
b=350
c=a+b
print ("The Sum=", c)
(2) If your code has any error, it will be shown in red color in the IDLE window, and Python
describes the type of error occurred. To correct the errors, go back to Script editor, make
corrections, save the file using Ctrl + S or File → Save and execute it again.
(3) For all error free code, the output will appear in the IDLE window of Python as shown in
Figure 5.8
Output
A program needs to interact with the user to accomplish the desired task; this can be
achieved using Input-Output functions. The input() function helps to enter data at run time
by the user and the output function print() is used to display the result of the program on the
screen after execution.
5.4.1 The print() function
In Python, the print() function is used to display result on the screen. The syntax for
print() is as follows:
Example
print (“string to be displayed as output ” )
print (variable )
print (“String to be displayed as output ”, variable)
print (“String1 ”, variable, “String 2”, variable, “String 3” ……)
Example
>>> print (“Welcome to Python Programming”)
Welcome to Python Programming
>>> x = 5
>>> y = 6
>>> z = x + y
>>> print (z)
11
>>> print (“The sum = ”, z)
The sum = 11
>>> print (“The sum of ”, x, “ and ”, y, “ is ”, z)
The sum of 5 and 6 is 11
The print ( ) evaluates the expression before printing it on the monitor. The print
() displays an entire statement which is specified within print ( ). Comma ( , ) is used as a
separator in print ( ) to print more than one item.
>>> city=input()
Rajarajan
>>> print (“I am from”, city)
I am from Rajarajan
Note that in example-2, the input( ) is not having any prompt string, thus the user will
not know what is to be typed as input. If the user inputs irrelevant data as given in the above
example, then the output will be unexpected. So, to make your program more interactive,
provide prompt string with input( ).
The input ( ) accepts all data as string but not as numbers. If a numerical value is
entered, the input values should be explicitly converted into numeric data type. The int( )
function is used to convert string data as integer data explicitly. We will learn about more such
functions in later chapters.
Example 3:
x = int (input(“Enter Number 1: ”))
y = int (input(“Enter Number 2: ”))
print (“The sum = ”, x+y)
Output:
Enter Number 1: 34
Enter Number 2: 56
The sum = 90
5.6 Indentation
Python uses whitespace such as spaces and tabs to define program blocks whereas
other languages like C, C++, java use curly braces { } to indicate blocks of codes for class,
functions or body of the loops and block of selection command. The number of whitespaces
(spaces and tabs) in the indentation is not fixed, but all statements within the block must be
indented with same amount spaces.
5.7 Tokens
Python breaks each logical line into a sequence of elementary lexical components
known as Tokens. The normal token types are
1) Identifiers,
2) Keywords,
3) Operators,
4) Delimiters and
5) Literals.
Whitespace separation is necessary between tokens.
5.7.1. Identifiers
An Identifier is a name used to identify a variable, function, class, module or object.
5.7.2. Keywords
Keywords are special words used by Python interpreter to recognize the structure of
program. As these words have specific meaning for interpreter, they cannot be used for any
other purpose.
Table 5.1 Python’s Keywords
as elif if or yield
5.7.3 Operators
In computer programming languages operators are special symbols which represent
computations, conditional matching etc. The value of an operator used is called operands.
Operators are categorized as Arithmetic, Relational, Logical, Assignment etc. Value and
variables when used with operator are known as operands.
(i) Arithmetic operators
An arithmetic operator is a mathematical operator that takes two operands and performs
a calculation on them. They are used for simple arithmetic. Most computer languages contain a
set of such operators that can be used within equations to perform different types of sequential
calculations.
XII Std Computer Science 56