UNIT I ALGORITHMIC PROBLEM SOLVING

Algorithms, building blocks of algorithms (statements, state, control flow, functions), notation (pseudo code,
flow chart, programming language), algorithmic problem solving, simple strategies for
developing algorithms (iteration, recursion). Illustrative problems: find minimum in a list, insert a card in a list
of sorted cards, guess an integer number in a range, Towers of Hanoi.

PROBLEM SOLVING

Problem solving is the process of transforming the description of a problem into the solution
of that problem.

The problem solving strategy goes through the following stages.

Analysis

Design

Development

Testing

Implementation

Analysis - In this stage we should find what the problem should do.

Design - The way or method of how our problem is solved.

Development - The method found in design is then coded here in a given programming
language.

Testing -Here we verify that the program written is working correctly.

Implementation – Finally the program is ready to use.

GE8151 - PROBLEM SOLVING AND PYTHON PROGRAMMING AAMEC - KOVILVENNI

Alogrithm:

o Algorithm is a set of rules for solving a problem in finite number of

steps.

o An algorithm defined as a finite sequence of explicit instructions.

o Algorithm can have steps that repeat (iterate) or require decisions (logic
and comparison) until the task is completed.

Properties of Algorithm:

a. There must be no ambiguity in any instruction.

b. There should not be any uncertainty about which instruction is to be
executed next.
c. The algorithm should conclude after a finite number of steps.
d. An algorithm cannot be open-ended.
e. The algorithm must be general enough to deal with any contingency.

Example:

Step 1: Start

Step 2: Read height and width of a rectangle

Step 3: Find area of rectangle by multiplying height with width and store
the

result in area.

Step 4: Display area

Step 5: Stop

Building blocks of an Algorithm

An algorithm is a sequence of simple steps that can be followed to solve a

problem. The steps must be organized in a logical and clear manner.

Algorithm can be designed using the following basic methods:

(i) Statements
(ii) Sequential control
(iii) Selection or Conditional
(iv) Repetition or Iteration
(v) Functions

GE8151 - PROBLEM SOLVING AND PYTHON PROGRAMMING AAMEC - KOVILVENNI

 (i) Statements

The algorithm is part of the blueprint or plan for the computer program.

It is an effective procedure for solving a problem.

An algorithm is a series of specific steps (statements).

Example: Algorithm statements

1. Description of the problem: To find sum of two numbers

2. Variable requirements: Two variables for addition and one for storing
the result.
3. Parameters: Read 1st number and Read 2nd number
4. Execution: adding 1st number and 2nd number and store it in 3rd variable
5. Conclusion: Displaying the result is in 3rd variable.

(ii) Sequential control:

The steps of an algorithm are carried out in a sequential manner, where

each step is executed exactly once.

Example for sequential control:

1. Read temperature in Fahrenheit

2. Apply conversion formula : Celsius = (5/9) * (Fahrenheit – 32)
3. Display result in Celsius.

(iii) Selection or Conditional Control

In selection control only one of a number of alternative steps is executed

based on the given condition

Example for Selection or Conditional control

Eligibility for voting

1. Read the age of a person

2. If (age >= 18) print “eligible for voting”
Else print “not eligible for voting”

GE8151 - PROBLEM SOLVING AND PYTHON PROGRAMMING AAMEC - KOVILVENNI

 (iv) Repetition or Iteration

In repetition one or more steps are performed repeatedly.

One or more instruction may executed several times, depending on some condition

Example of repetition or iteration

Compute and print the average of ten numbers

1. Total = 0, Average = 0
2. FOR 1 to 10
3. Read number
4. Total = Total + number
5. END FOR
6. Average = Total / 10
7. Print Average

(v) Functions
A function is self contained block.
It is used to perform specific task
Larger programs are subdivided into smaller one by the use of functions (Modular
programming)
Functions are also named as methods, subroutines or procedures.

Example:
1. Read A,B
2. add(A,B) //Calling function add
3. sub(A,B) // calling function sub
1. add(X,Y), Z=X+Y, print Z // called function
2. sub(X,Y), Z=X-Y, print Z // called function

Notation:

A notation is system of characters, expression, graphics or symbols

used in problem solving to represent technical facts, created to facilitate the best result
for a problem.

GE8151 - PROBLEM SOLVING AND PYTHON PROGRAMMING AAMEC - KOVILVENNI

The various notations that are used in problem solving are pseudo code, flowcharts,
and programming languages.
Flowchart

A flowchart is a pictorial representation of an algorithm in which the steps are drawn in the
form of different shapes of boxes and the logical flow indicated by interconnecting arrows.

Boxes represent operations and the arrows represent the sequence.

Flowchart Symbols

ADVANTAGES OF USING FLOWCHARTS

1. Communication: Flowcharts are better way of communicating the logic of a system to all
concerned.

2. Effective analysis: With the help of flowchart, problem can be analysed in more effective
way.

3. Proper documentation: Program flowcharts serve as a good program documentation,

which is needed for various purposes.

4. Efficient Coding: The flowcharts act as a guide or blueprint during the systems analysis
and program development phase.

5. Proper Debugging: The flowchart helps in debugging process.

GE8151 - PROBLEM SOLVING AND PYTHON PROGRAMMING AAMEC - KOVILVENNI

6. Efficient Program Maintenance: The maintenance of operating program becomes easy
with the help of flowchart. It helps the programmer to put efforts more efficiently on that part

LIMITATIONS OF USING FLOWCHARTS

1. Complex logic: Sometimes, the program logic is quite complicated. In that case,
flowchart becomes complex and clumsy.

2. Alterations and Modifications: If alterations are required the flowchart may require re-
drawing completely.

3. Reproduction: As the flowchart symbols cannot be typed, reproduction of flowchart

becomes a problem.

4. The essentials of what is done can easily be lost in the technical details of how it is done.

Examples START

Sample flowchart

READ HEIGHT AND

WIDTH

AREA = HEIGHT * WIDTH

PRINT AREA

STOP

Pseudocode- (pseudo-imitation, Code- instruction)

Set of instructions that mimic programming language instructions.

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

Pseudocode uses plain English statements also known as PDL(Program Design Language).

The goal of writing pseudocode is to provide a high-level description of an algorithm, which

facilitates analyzis and eventual coding, but at the same time suppresses many of the details
that are insignificant.

GE8151 - PROBLEM SOLVING AND PYTHON PROGRAMMING AAMEC - KOVILVENNI

Some keywords:

Input: READ, OBTAIN, GET, and PROMPT

Output: PRINT, DISPLAY, and SHOW

Compute: COMPUTE, CALCULATE, and DETERMINE

Initialize: SET and INITIALIZE

Add One: INCREMENT

Example:

Calculate the area of a rectangle

PROMPT the user to enter the height of the rectangle

PROMPT the user to enter the width of the rectangle

COMPUTE the area by multiplying the height with width

DISPLAY the area

STOP
Pseudocode Guidelines

a) Should be written in simple English.

b) Steps must be understandable
c) It should be concise
d) Each instruction should be written in separate line.
e) Capitalize keywords, such as READ, PRINT, and so on
f) Each set of instructions is written from top to bottom, with only one entry
and one exit.
g) It should allow for easy transition from design to coding in programming
language.

Benefits of pseudocode

a) Language independent. It allows the developer to express design in plain

natural language.
b) It is easier to develop a program from a pseudocode than with a flowchart.
c) It is easy to translate pseudocode into a programming language.
d) It is compact and does not tend to run over many pages. Its simple structure
and readability make it easier to modify.

GE8151 - PROBLEM SOLVING AND PYTHON PROGRAMMING AAMEC - KOVILVENNI

 Limitations of pseudocode

a) It does not provide visual representation of the program’s logic

b) Programmers use their own style of writing. There are no accepted standards.
c) It cannot be compiled nor executed.

PROGRAMMING LANGUAGES
Computer programming languages are used to communicate instructions to the computer.
They are based on certain syntactic and semantic rules, which define the meaning of each of the
programming language construct.

They are divided into following categories:

1. Interpreted programming languages
2. Functional programming languages
3. Compiled programming languages
4. Procedural programming languages
5. Scripting programming languages
6. Markup programming languages
7. Logic based programming languages
8. Concurrent programming languages
9. Object oriented programming languages

1. INTERPRETED PROGRAMMING LANGUAGES

 An interpreted language is a programming language for which most of its implementation
executes instructions directly.
 The interpreter executes programs directly, translating each statement into sequence of one or
more sub-routines.

Example: BASIC, LISP, PASCAL, PERL, PYTHON

PYTHON:
It is a high level programming language, interpreted, interactive and object oriented
scripting language. Python is designed to be highly readable. It uses English keywords
frequently where as other languages use punctuation, and it as few syntactical constructions.
2. FUNCTIONAL PROGRAMMING LANGUAGES
 Functional programming language defines every computation as a mathematical
evaluation.
 Many of the functional programming languages are bound to mathematical
calculation.

Example: CLEAN, CURRY, F#

8

GE8151 - PROBLEM SOLVING AND PYTHON PROGRAMMING AAMEC - KOVILVENNI

3. COMPILED PROGRAMMING LANGUAGES
Compiled language is a programming language whose implementations are typically compilers and
not interpreters.

Example: C, C++, JAVA, VISUAL BASIC

4. PROCEDURAL PROGRAMMING LANGUAGES
 Procedural (Imperative) programming language implies specified in the steps that the
programs should take to reach to an intended state.
 It makes the programs structured and easily traceable for program flow.

Example: MATLAB, HYPER TALK, MODULA-2

5. SCRIPTING PROGRAMMING LANGUAGES
Scripting programming language are programming languages that control an application.
Script can execute independent of any other application.

Example: PHP, VBSCRIPT, APPLE SCRIPT, WINDOWS POWERSHELL

6. MARKUP PROGRAMMING LANGUAGES
A markup language is an artificial language that uses annotations to text that define how the text is to
be displayed.

Example: SGML, HTML, XML, XHTML

7. LOGIC BASED PROGRAMMING LANGUAGES
 Logic programming is a type of programming paradigm which is largely based on formal
logic.
 Any program written in logical programming language is a set of sentences in logical form,
expressing facts and rules about some problem domain.

Example: ALF, Fril, prolog.

8. CONCURRENT PROGRAMMING LANGUAGES

 Concurrent programming is a computer programming technique that provides for the
execution of operations concurrently, either within a single computer, or across a number of
systems.
 In the later case, the term distributed computing is used.

Example: ABCL, CONCURRENT PASCAL, E

9. OBJECT ORIENTED PROGRAMMING LANGUAGES
Object oriented programming language is a programming paradigm based on the concept of
“objects”, which may contain data, in the form of fields, often known as attributes and code, in the
form of procedures, often known as methods.

Example: AGORA, BETA, LAVA, MOTO.

GE8151 - PROBLEM SOLVING AND PYTHON PROGRAMMING AAMEC - KOVILVENNI

 ALGORITHMIC PROBLEM SOLVING
INTRODUCTION
Algorithmic problem solving is about the formulation and finding solution to problems..

UNDERSTANDING THE PROBLEM

o Understanding the given problem is very important before solving the problem.
o Understand the problem and clarify the doubts before going into next stage.
o Correct algorithm should work for all possible inputs.
o In this stage analyze what are all the inputs, required data, analyze who is going to use
this system and what is the desired output.
ASCERTAINING THE CAPABILITIES OF A COMPUTATIONAL DEVICE
o The second step is to find out the capabilities of a machine.
o The instructions are executed one after another, one operation at a time,
o Depending on the capability of machine, algorithm is classified as
(i) Sequential algorithm (ii) Parallel algorithm

10

GE8151 - PROBLEM SOLVING AND PYTHON PROGRAMMING AAMEC - KOVILVENNI

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.
There are three issues to choose an approximation algorithm.
1. There are certain problems like extracting square roots, solving non-linear equations which
cannot be solved exactly.
2. If the problem is complicated, it slows the operations. E.g. traveling salesman problem.
3. This algorithm can be a part of a more sophisticated algorithm that solves a problem
exactly.
DECIDING ON 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.
1. They provide guidance for designing for new problems.
2. Algorithms are the cornerstones of computer science.
Algorithm design techniques make it possible to classify algorithms according to an
underlying design idea; therefore, they can serve as a natural way to both categorize and study
algorithms.
METHODS OF SPECIFYING AN ALGORITHM
o Flowcharts and pseudo code are used for specifying an algorithm.
o Flowchart is a pictorial representation of algorithm.
o A Pseudocode, which is a mixture of a natural language and programming language
like
constructs.
PROVING AN ALGORITHM'S CORRECTNESS
o Correctness has to be proved for every algorithm.
o To prove that the algorithm gives the required result for every legitimate input in a
finite amount of time.
o A technique used for proving correctness by mathematical induction because an
algorithm’s iterations provide a natural sequence of steps needed for such proofs.
ANALYSING AN ALGORITHM
11

GE8151 - PROBLEM SOLVING AND PYTHON PROGRAMMING AAMEC - KOVILVENNI

 There are two kinds of algorithm efficiency: time and space efficiency. Time efficiency
indicates how fast the algorithm runs; space efficiency indicates how much extra memory the
algorithm needs. Another desirable characteristic is simplicity. Simper algorithms are easier to
understand and program, the resulting programs will be easier to debug.

CODING AN ALGORITHM
o Programming the algorithm by using some programming language.
o Validity is done through testing and debugging.
o Inputs should fall within a range and hence require no verification. The analysis has to
be done in various sets of inputs.
o A good algorithm is a result of repeated effort and work.
o The program's stopping or terminating condition has to be set.
o Another important issue is the question of whether or not every problem can be solved
by an algorithm.
o And the last, is to avoid the ambiguity which arises for a complicated algorithm.
Simple strategies for developing algorithms
An Iterative algorithm will use looping statements such as for loop, while loop or do-while loop to
repeat the same steps.

Recursive algorithm, a function calls itself again and again till the base condition(stopping
condition) is satisfied.

An Iterative algorithm will be faster than the Recursive algorithm because of overheads like calling
functions and registering stacks repeatedly. Many times the recursive algorithms are not efficient as
they take more space and time.

Recursive algorithms are mostly used to solve complicated problems when their application is easy
and effective.
For example Tower of Hannoi algorithm is made easy by recursion while iterations are widely used,
efficient and popular.

Difference between Recursive algorithm and Iterative algorithm

 Recursive algorithm:

o In recursive algorithm, the function calls itself until the condition is met.
o It is slower than iteration.
o It uses more memory than iteration.
o Recursion is like a selection structure, and which makes code smaller and clean.
o Tracing the code will be more difficult in the case large programs.

 Iterative algorithm:

o Iterative algorithm is a repetition process until the condition fails.

o Here code may be longer but it is faster than recursive.
12

GE8151 - PROBLEM SOLVING AND PYTHON PROGRAMMING AAMEC - KOVILVENNI

 o It consumes less memory.
o If the loop condition is always true in such cases it will be an infinite loop.

13

GE8151 - PROBLEM SOLVING AND PYTHON PROGRAMMING AAMEC - KOVILVENNI