Problem Solving And Python Programming

Algorithm – Definition

Algorithm is a step – by – step procedure to solve a problem in a finite number of steps to get the desired output. Algorithm is an ordered set of rules to solve a problem.

Program = Algorithm + Data structures

Algorithm in our daily life

Example : Coffee making

Pour drinking water into electric kettle.
Plug electric kettle and wait for it to boil.
While waiting , prepare coffee cup.
Add instant coffee powder into cup.
Check boiling water.
If water is boiled , unplug kettle and pour water into cup.
If water is not boiled , press the ” on ” switch to continue and wait until boiled.

Characteristics of an Algorithm :

Each and every instruction should be precise and unambiguous.
Algorithm should have finite number of steps.
Algorithm should be written in sequence (step – by – step).
Algorithm should have finite number of inputs.
Ensure that the algorithm terminates.
Results should be obtained only when the algorithm terminate.

Qualities of a good Algorithm:

Time:

The computer system takes some amount of time to execute a program. It is said that lesser time is required for a good Algorithm.

Memory:

The computer system takes some amount of memory storage to execute a program. It is said that lesser memory is required for a good Algorithm.

Accuracy:

More accurate results should be provided by a good Algorithm . Such Algorithm should be suitable.

Sequence:

A good Algorithm should be written in a sequence . The procedure of an Algorithm must form in a sequence.

Understandable:

A good Algorithm should be easily understandable.

Solvable:

A good Algorithm should solve the problem.

Two important factors of an Algorithm:

Time complexity:

The amount of time required by the Algorithm to run to completion is the time complexity of an Algorithm.

Space complexity:

The amount of memory space required by the Algorithm in its life cycle to complete a task.

Key features of an algorithm:

Sequence:

Each instruction is executed in sequence.

Decision:

The result is based on some conditions.

Repeat:

Process is repeated until the condition becomes false.

Steps to develop an algorithm:

An algorithm should be enclosed by two statements start and stop.
To read data from the user input or read statement is used.
To display the output print statement is used.
The arithmetic operations used are;
- + – addition operator
- – – subtraction operator
- * – multiplication operator
- / – division operator
- = – assignment operator
- => – commonly used operator
The relational operators used are;
- > – greater than operator
- < – less than operator
- >= – greater than or equal to operator
- <= – less than or equal to operator
- = – equal to operator

Example:1

Algorithm to find the sum of two numbers.

Start
Read a,b
c=a+b
Print c
Stop

Building blocks of algorithm:

Algorithm:

It is an effective step-by-step procedure to solve a problem.

INPUT————>ALGORITHM—————–>OUTPUT

It can be constructed from building blocks.

Building Blocks:

Instructions / statements
State
Control flow
Functions

Instructions / statements:

Instruction / statements are the steps which solves a particular problem.

Most of the algorithms have the basic parts of statements.

Description of the problem.
Setup
Parameters
Execution
Conclusion

Example: To find the sum of two numbers.

Description of the problem:

To find the sum of two numbers.

Setup:

Two numbers required for addition and one variable is for sorting the result.

Parameters:

Read the first number.
Read the second number.

Execution:

Calculate the sum of two numbers(a,b).

Result=a+b

Conclusion:

The desired output is the sum of two numbers is sorted in the variable ‘result’.

State:

State is defined as the condition of algorithm at a moment in a time.

Algorithm can be in any of the following states.

Start state
Input state
Process state
Output state
Stop state

START———>INPUT————->PROCESS————–>OUTPUT—————>STOP

(states of an algorithm)

Start state:

Start state represents the starting of the program.

Input state:

Input state represents the process of reading the input from the user.

Process state:

Process state represents the process is done in the program.

Example: Addition, subtraction,etc,……….

Output state:

Output state represents the output displayed on the screen.

Stop state:

Stop state represents the ending of the program.

Example: Algorithm to find the sum of two numbers.

Start (START STATE)
Read A,B (INPUT STATE)
C=A+B (PROCESS STATE)
Print C (OUTPUT STATE)
Stop (STOP STATE)

Control flow:

Control flow represents the order of the statement execution and direction of flow of programs.

There are three types of control flow.

Sequential control flow
Selection control flow
Repetition control flow

Sequential control flow:

The step of an algorithm are carried out in a sequential manner.

Example: Temperature conversion.

Start
Read temperature in Fahrenheit f
c=(5/9)*(f-32)
Print c
Stop

Selection control flow:

Only one of the alternative steps is executed based on the condition.

Example: Algorithm to find the biggest among the two numbers.

Start
Read a,b
If a>b then print “a is big”
Else print “b is big”
Stop

Repetition control flow:

One or more steps are performed repeatedly.

This logic is used for producing loops in the program.

The looping process can be performed for one time or multiple times based on the condition.

Example: Algorithm to print numbers from 1 to 10.

Start
Initialize n=0
Increment n=n+1
Print n
If n<=10 then goto step 3
Else goto step 7
Stop

Functions:

A function is a block of organized and reusable code which is used to perform a task or action.

It provides better modularity.

They are also called as routines, methods, procedures etc.

“Add” is a function and it performs addition operation.

Example: Algorithm to find the biggest among N numbers

Start
Read 11, 12, 13,…..1n into array.
Initialize max=11
Read next number 11, do the following
1. If max<11 then
  1. ) max = 11
2. Repeat step “i” until n
Print max
Stop

Advantages of algorithm:

Easy to understand.
Easy to debug.
It is easy for a programmer to convert algorithm into actual program.

Disadvantages of algorithm:

It is time consuming.(An algorithm is developed first, which is then converted into flow chart and then program).
It is difficult to show branching and looping.

Notation:

Pseudo code:

Pseudo code is made up of two words: Pseudo and code.

Pseudo means ‘imitation’ and code refers to instructions written in programming language.

Pseudo code is not a real programming language, but it looks like a programming language.

Pseudo code is also called as “Program Design Language”[PDL].

It is an outline of a program, written in a form that can be easily converted real programming statements.

Pseudo code instructions are written in normal English.

Rules for writing pseudo code:

Write one statement per line.
Capitalize the key words.
End multiline structure.
Keep statements language independent.
Intent to show hierarchy.

Keywords used in pseudo code:

START : BEGIN
INPUT : READ, OBTAIN, GET, INPUT, DEFINE
OUTPUT :OUTPUT, PRINT, DISPLAY, SHOW
COMPUTE : CALCULATE, COMPUTE, ADD, SUBTRACT, INITIALIZE, DETERMINE
INITIALIZE :SET, INITIALIZE
ADD ONE : INCREMENT
STOP : END

Pseudo code guidelines:

Pseudo code statements should be written in simple English.
Each statements should be written in separate line.
The keywords should be capitalized.
Pseudo code should be programing language independent.
The steps must be understandable.
Each set of instructions are written from top to bottom.

Advantages (Benefits):

It can be read and understood easily.
It can be done easily on a word processor.
It can be modified easily.
It occupies less space.
It will not run over many pages.
Converting a pseudo code to a program is simple.

Disadvantages (Limitations):

It is not visual.
We do not get a picture of the design.
There is no standardized style or format.
For a beginner, it is more difficult to follow the logic or write pseudo code.

Example 1: Write a pseudo code to calculate sum of two numbers.

BEGIN

INITIALIZE sum=0, i=1

READ n

FOR i<=n, then

COMPUTE sum=sum+i

CALCULATE i=i+1

END FOR

COMPUTE avg=sum/n

PRINT sum< avg

END

Example 2: Write pseudo code to add two numbers.

BEGIN

SET C=0

READ A,B

ADD C=A+B

PRINT C

END

Flow chart:

Flow chart is a diagrammatic representation of an algorithm.

A flow chart is a picture of the separate steps of a process in sequential order.

Flow chart is made up of boxes, diamonds and other shapes connected by arrows where each shape represents a step in the process.

The arrows show the order of the flow of execution.

Flow charts are used in designing or documenting a process or program.

The logic of the program is communicated in much better way by using a flow chart.

Sl.no	Name of the symbol	Description
1	Start / stop	Represent the start and stop of the program.
2	Input / output	Denoted either an input or output operation.
3	Process	Denotes the process to be carried out.
4	Decision	Represent decision making and branching.
5	Flow lines	Represents the sequence of steps and direction of flow.
6	Connector	Connects remote parts of the flowchart on the same page.
7	Magnetic tape	Stored on magnetic tape.
8	Magnetic disk	I/O from magnetic disk.
9	Delay	Wait.
10	OR	Logical OR.
11	AND	Logical AND.
12	Document	A Document.
13	Sort	Sort in some order.

Guidelines for drawing flowchart:

All necessary requirements should be listed out in logical order.
There should be START and STOP in the flow chart.
The following should be clear, neat and easy to follow.
The direction of flow is from left to right or top to bottom.
Only one flow line should emerge from a process symbol.
Only one flow line should enter a decision symbol but two or three flow line can leave the decision symbol.
Only one flow line is used with terminal symbol.
If the flow chart becomes complex, connector symbols are used to reduce the number of flow lines.
The text within the symbols should be brief.
The validity of flowchart should be tested by passing simple test data.

Advantages:

Better communication
- It is easy for the programmer to explain the logic of program.
Effective analysis
- It is easy to analyze the problem effectively.
Proper documentation
- With the help of flowchart good documentation is done for various purposes.
Efficient coding
- Flowcharts acts as a guide during the system analysis and program development phase.
Efficient debugging
- It helps in debugging process.
Efficient program maintenance
- The maintenance of a program becomes easy with the help of the flowchart.

Disadvantages (limitations):

Complex logic
- Sometimes the logic of the program is quite complicated . In such case flowcharts become complex.
Alternations and modifications
- If alternations are required , the flowchart needs to be redraw completely.
Reproduction
- Reproduction of the flowchart becomes a problem because it cannot be typed.
Cost
- High cost for large applications.

Programming languages:

Programming languages are used to communicate instructions to the computer.Programming languages are written based on syntactic and semantic rules.

Programming languages can be divided into nine major categories.

Interpreted programming language
Functional programming language
Compiled programming language
Procedural programming language
Scripting programming language
Markup programming language
Logic-based programming language
Concurrent programming language
Object-Oriented programming language

Interpreted programming language:

An interpreted programming language is programming language that executes instructions directly, without compiling a program into machine-language instructions.

Example:

BASIC(Beginners All Purpose Symbolic Instruction Code), LISP(List Processing Language), Python.

Functional programming language:

Functional Programming language define every computation as a mathematical evaluation.

They are based on mathematical functions.

They focus on application of functions.

Example:

Clean, curry, F#, Haskell and Q.

Compiled programming language:

Compiled programming language is a programming language which uses compilers to convert the source code into machine code.

Example:

Ada, algol, C, C++, COBOL, Java, Fortran, VB.

Procedural programming language:

A procedural language is a type of computer programming language that specifies a series of well-structured step and procedures within its programming context to compose a program.

These language specify the steps that the program should take to reach to an intended state.

Procedure is a group of statements.

It makes the program structured and helps to reuse the code.

Example:

CLIST, Hypertalk, MATLAB, PL/I.

Scripting programming language:

Scripting programming language are programming language that control applications.

Example:

Applescript, AWK, MAYA, PHP, VBSCRIPT.

Markup programming language:

Markup language is an artificial language that define how the text to be displayed.

Example:

CURL, SGML, HTML, XML, XHTML.

Logic-based programming language:

Logic-based programming language is a type of programming language that is based on logic.

Example:

ALF, Fril, Janus, Leda, Prolog.

Concurrent programming language:

It is a computer programming language that executes the operations concurrently.

Example:

ABCL, Afnix, E, Joule, Limbo.

Object-oriented programming language:

It is a programming language based on concepts of objects.

Objects contain data and functions.

Example:

Agora, Beta, Lava, Moto, Scala, Slate.

Machine language:

In machine language, instructions are in the form of 0’s and 1’s.

Instructions in machine language consists of two parts.

OPCODE
OPERAND

OPCODE:

OPCODE tells the computer what functions are to be performed.

OPERAND:

OPERAND tells the computer where to store the data.

Assembly language:

In assembly language, mnemonic code is assigned to each machine language instruction which is easy to remember and write.

Instruction in assembly language consists of four parts.

LABEL
OPCODE
OPERAND
COMMENT

Fourth generation language:

Fourth generation language are simple which is used to access databases.

Algorithmic programming language:

Algorithms are procedural solutions to problems.

Algorithmic problem solving is defined as the formulation and solution of problems where solution involves the principles and techniques to construct the correct algorithms.

It means that solving problems that formulation of an algorithm for their solution.

Steps in designing and analyzing an algorithm:

The steps are:

Understanding the problem.
Ascertaining the capabilities of a computational device.
Choosing between exact and approximate problem solving.
Deciding on appropriate data structures.
Algorithm design techniques.
Methods of specifying an algorithm.
Proving an algorithm’s correctness.
Analyzing an algorithm.
Coding an algorithm.

Understanding the problem:

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.

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 machine architecture is captured by RAM; here the instructions are executed one after another,one operation at a time.

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 is called parallel algorithms.

RAM model doesn’t support this.

Choosing between exact and approximate problem solving:

The next decision is to choose between solving the problem exactly or solving it approximately.

Based on this, the algorithms are classified as exact and approximation algorithms.

Exact algorithms:

The algorithms that can solve the problem exactly are called exact algorithms.

Approximate algorithms:

The algorithms that can solve the problem not exactly are called approximate algorithms.

There are three issues to choose an approximation algorithm.

First, there are certain problems like extracting square roots, solving non-linear equations which cannot be solved exactly.

Secondly, if the problem is complicated it shows the operations. Example: Traveling salesman problem.

Third, this algorithm can be a part of a more sophisticated algorithm that solves a problem exactly.

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.

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.

Learning these techniques is important for two reasons.

First, they provide guidance for designing for new problems.

Second, algorithms are the cornerstones of computer science.

Methods of specifying an algorithm:

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

There are two options for specifying algorithms:

Pseudo code.

Flow chart.

Pseudo code:

Pseudo code is a mixture of a natural language and programming language.

It is more precise.

Flow chart:

Flo chart is a method of expressing an algorithm by a collection of concerned of connected geometric shapes containing descriptions of the algorithm’s steps.

Proving an algorithm’s correctness:

Once an algorithm has been specified, you have to prove its correctness.

You have to prove that the algorithm yields a required result for every legitimate input in a finite amount of time.

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

Analyzing an algorithm:

Our algorithm should possess several qualities.

Analysis of algorithms and performance analysis refers to the task of determining how much computing time and storage an algorithm requires.

After correctness, the most important quality of an algorithm is Efficiency.

There are two kinds of an algorithm Efficiency

Time efficiency:

Time efficiency indicates how fast the algorithm runs.

Space efficiency:

Space efficiency indicates how much extra memory the algorithm needs.

Coding an algorithm:

Algorithms are implemented as computer programs.

Verification and validation is done for error correction.

Simple strategies for developing algorithms

Iteration and recursion are the simple strategies for developing algorithms.

Iteration:

Iteration is the process of repeating the same set of statements again and again until the condition becomes false.

Iteration is done in two ways:

In iteration loop, the condition is checked at the beginning of the loop. If the condition is true, then the loop will be executed. If the condition is false, the loop will not be executed.
Condition is checked at the bottom of the loop. If the condition is true, loop will be executed. Otherwise the loop will not be executed.

Recursion:

Recursion is a programming technique that has a recursive function that calls itself again and again until the condition is reached.

Syntax:

function():

In the above syntax, function() is a function which calls itself until the condition is reached.

Difference between recursion and iteration:

Sl.No	Recursion	Iteration
1	Function calls itself until the base condition is reached.	Repetition of loop until condition fails.
2	It keeps the code short and simple.	It keeps the code longer.
3	It is slower.	It is faster.
4	It takes more memory.	It takes less memory.
5	Tracing is difficult if any problem.	Tracing is easier if any problem occurs.