Basic of python

https://www.poriyaan.in/ Problem Solving and Python Programming https://eee.poriyaan.in/

UNIT I (GE8151 PROBLEM SOLVING AND PYTHON PROGRAMMING)
ALGORITHMIC PROBLEM SOLVING




/
Algorithms are procedural solutions to problems. Algorithmic problem solving is defined as the




in
formulation and solution of problems where solution involves the principles and techniques to




n.
construct the correct algorithms. It means that solving problems that require formulation of an




aa
algorithm for their solution.
Steps in designing and analyzing an algorithm




iy
The steps are




or
i) Understanding the problem
ii) Ascertaining the capabilities of a computational device



.p
iii) Choosing between exact and approximate problem solving
w
iv) Deciding on appropriate data structures.
w
v) Algorithm design techniques
//w

vi) Methods of specifying an algorithm.
vii) Proving an algorithm’s correctness.
viii) Analyzing an algorithm.
s:



ix) Coding an algorithm.
tp




i) Understanding the problem
ht




→Before designing an algorithm, you need to understand the problem completely.
→Read the problem description carefully.
→ Check if it is similar to some standard problems and if a known algorithm exists.
→Ask Questions if you have any doubts and do a few small examples by hand.
→Think about special cases.
→Ask Questions again if needed.

,https://www.poriyaan.in/ https://eee.poriyaan.in/


Understand the problem




/
.in
Decide on: computational




n
means,




aa
Algorithm design techniques




iy
or
.p
Design an algorithm

w
w
Prove correctness
//w
s:



Analyze the algorithm
tp
ht




Code the algorithm




Fig 1: Steps in designing and analyzing an algorithm

ii) Ascertaining the capabilities of a computational Device

The second step is to ascertain the capabilities of a machine.
Sequential algorithms:
→ The essence of von-Neumann machines architecture is captured by RAM; here h
te
instructions are executed one after another, one operation at a time.

,https://www.poriyaan.in/ https://eee.poriyaan.in/

→Algorithms designed to be executed on such machines are called sequential algorithms.
Parallel algorithms:
→ An algorithm which has the capability of executing the operations concurrently




/
in
iscalled parallel algorithms.




n.
→RAM model doesn’t support this.
iii) Choosing between exact and approximate problem solving




aa
→The next decision is to choose between solving the problem exactly or solving ti




iy
approximately.




or
→Based on this, the algorithms are classified as exact and approximation algorithms.
Exact algorithms:



.p
→ The algorithms that can solve the problem exactly are called exact algorithms.
w
Approximate algorithms:
w
→The algorithms that can solve the problem not exactly are called approximate
w

algorithms.
//


→There are three issues to choose an approximation algorithm.
s:



→First, there are certain problems like extracting square roots, solving non-linear
tp




equations which cannot be solved exactly.
ht




→Secondly, if the problem is complicated it slows the operations. E.g. Traveling
salesman problem.
→Third, this algorithm can be a part of a more sophisticated algorithm that solves
aproblem exactly.
iv) Deciding on appropriate data structures

→Data structures play a vital role in designing and analyzing the algorithms.
→Some of the algorithm design techniques also depend on the structuring data specifying
a problem’s instance.
Algorithm + Data structure = Programs
v) Algorithm design techniques

→An algorithm design technique is a general approach to solving problems
algorithmically that is applicable to a variety of problems from different areas of computing.
Download Binils Android App in Playstore Download Photoplex App

, https://www.poriyaan.in/ https://eee.poriyaan.in/
→Learning these techniques is important for two reasons.
i) First, they provide guidance for designing for new problems.
ii) Second, algorithms are the cornerstones of computer science.




/
vi) Methods of specifying an algorithm




in
Once you have designed an algorithm, you need to specify it in some fashion.




n.
There are two options for specifying algorithms.




aa
→ Pseudo code
→ Flowchart




iy
Pseudo code is a mixture of a natural language and programming language. It is more




or
precise.
Flowchart is a method of expressing an algorithm by a collection of connected geometric



.p
shapes containing descriptions of the algorithm’s steps.
w
vii) Proving an algorithm’s correctness
w
→Once an algorithm has been specified, you have to prove its correctness.
w

→You have to prove that the algorithm yields a required result for every legitimate input
//


in a finite amount of time.
s:



→A common technique for proving correctness is to use mathematical induction.
tp




viii) Analyzing an algorithm

→ Our algorithm should possess several qualities.
ht




→ Analysis of algorithms and performance analysis refers to the task of determining how
much computing time and storagean algorithm requires.
→After correctness, the most important quality of an algorithm is Efficiency.
→There are two kinds of algorithm Efficiency.
i) Time efficiency: It indicates how fast the algorithm runs.
ii) Space efficiency: Indicates how much extra memory the algorithm needs.
ix) Coding an algorithm
→ Algorithms are implemented as computer programs.
→ Verification and validation is done for error correction.




Download Binils Android App in Playstore Download Photoplex App