GE8151 Problem Solving and Python Programming Notes Unit 1 -5

Notes 153 Pages

Anna University

Computer Engineering

Contributed by

Yash Baria

UNIT I
ALGORITHMIC PROBLEM SOLVING
1.1 ALGORITHMS
In computing, we focus on the type of problems categorically known as algorithmic
problems, where their solutions are expressible in the form of algorithms.
The term ‗algorithm‘ was derived from the name of Mohammed al-Khowarizmi, a
Persian mathematician in the ninth century. Al-Khowarizmi → Algorismus (in Latin) →
Algorithm.
An algorithm is a well-defined computational procedure consisting of a set of
instructions that takes some value or set of values, as input, and produces some value or
set of values, as output. In other word, an algorithm is a procedure that accepts data;
manipulate them following the prescribed steps, so as to eventually fill the required unknown
with the desired value(s).
People of different professions have their own form of procedure in their line of work,
and they call it different names. For instance, a cook follows a procedure commonly known
as a recipe that converts the ingredients (input) into some culinary dish (output), after a
certain number of steps.
1.1.1 The Characteristics of a Good Algorithm
 Precision – the steps are precisely stated (defined).
 Uniqueness – results of each step are uniquely defined and only depend on the input
and the result of the preceding steps.
 Finiteness – the algorithm stops after a finite number of instructions are executed.
 Effectiveness – algorithm should be most effective among many different ways to
solve a problem.
 Input – the algorithm receives input.
 Output – the algorithm produces output.
 Generality – the algorithm applies to a set of inputs.
1.2 BUILDING BLOCKS OF ALGORITHM (INSTRUCTIONS, STATE,
CONTROL FLOW, FUNCTIONS)
An algorithm is an effective method that can be expressed within a finite amount of
space and time and in a well-defined formal language for calculating a function. Starting from
an initial state and initial input, the instructions describe a computation that, when executed,
Algorithm
Input
Output
Downloaded from: annauniversityedu.blogspot.com
Page 1
proceeds through a finite number of well-defined successive states, eventually producing
"output" and terminating at a final ending state. The transition from one state to the next is
not necessarily deterministic; that algorithms, known as randomized algorithms.
An instruction is a single operation, that describes a computation. When it executed
it convert one state to other.
Typically, when an algorithm is associated with processing information, data can be
read from an input source, written to an output device and stored for further processing.
Stored data are considered as part of the internal stateof the entity performing the algorithm.
In practice, the state is stored in one or more data structures.
The state of an algorithm is defined as its condition regarding stored data. The stored
data in an algorithm are stored as variables or constants. The state shows its current values or
contents.
Because an algorithm is a precise list of precise steps, the order of computation is
always crucial to the functioning of the algorithm. Instructions are usually assumed to be
listed explicitly, and are described as starting "from the top" and going "down to the bottom",
an idea that is described more formally by flow of control.
In computer science, control flow (or flow of control) is the order in which
individual statements, instructions or function calls of an algorithm are executed or evaluated.
For complex problems our goal is to divide the task into smaller and simpler functions
during algorithm design. So a set of related sequence of steps, part of larger algorithm is
known as functions.
1.2.1 Control Flow
Normally Algorithm has three control flows they are:
 Sequence
 Selection
 Iteration
Sequence: A sequence is a series of steps that occur one after the other, in the same order
every time. Consider a car starting off from a set of lights. Imagine the road in front of the car
is clear for many miles and the driver has no need to slow down or stop. The car will start in
first gear, then move to second, third, fourth and finally fifth. A good driver (who doesn‘t
have to slow down or stop) will move through the gears in this sequence, without skipping
gears.
Selection: A selection is a decision that has to be made. Consider a car approaching a set of
lights. If the lights turn from green to yellow, the driver will have to decide whether to stop or
continue through the intersection. If the driver stops, she will have to wait until the lights are
green again.
Iteration: Iteration is sometimes called repetition, which means a set of steps which are
repeated over and over until some event occurs. Consider the driver at the red light, waiting
Downloaded from: annauniversityedu.blogspot.com
Page 2
for it to turn green. She will check the lights and wait, check and wait. This sequence will be
repeated until the lights turn green.
1.3 NOTATION OF ALGORITHM
There are four different Notation of representing algorithms:
 Step-Form
 Pseudocode
 Flowchart
 Programming Language

1.3.1 Algorithm as Step-Form
It is a step – by – step procedure for solving a task or problem. The steps
must be ordered, unambiguous and finite in number. It is English like representation of logic
which is used to solve the problem.
Some guidelines for writing Step-Form algorithm are as follows:
 Keep in mind that algorithm is a step-by-step process.
 Use begin or start to start the process.
 Include variables and their usage.
 If there are any loops, try to give sub number lists.
 Try to give go back to step number if loop or condition fails.
 Use jump statement to jump from one statement to another.
 Try to avoid unwanted raw data in algorithm.
 Define expressions.
 Use break and stop to terminate the process.
For accomplishing a particular task, different algorithms can be written. The
different algorithms differ in their requirements of time and space. The programmer selects
the best suited algorithm for the given task to be solved.
Let as look at two simple algorithms to find the greatest among three numbers,
as follows:
Algorithm 1.1:
Step 1: Start.
Step 2: Read the three numbers A,B,C.
Step 3: Compare A and B. If A is greater perform step 4 else perform step 5.
Step 4: Compare A and C. If A is greater, output ―A is greater‖ else output ―C is greater‖.
Step 5: Compare B and C. If B is greater, output ―B is greatest‖ else output ―C is greatest‖.
Step 6: Stop.
Algorithm 1.2:
Step 1: Start.
Step 2: Read the three numbers A,B,C.
Downloaded from: annauniversityedu.blogspot.com
Page 3
Step 3: Compare A and B. If A is greater, store Ain MAX, else store B in MAX.
Step 4: Compare MAX and C. If MAX is greater, output ―MAX is greater‖ else output ―C is
greater‖.
Step 5: Stop.
Both the algorithms accomplish same goal, but in different ways. The
programmer selects the algorithm based on the advantages and disadvantages of each
algorithm. For example, the first algorithm has more number of comparisons, whereas in
second algorithm an additional variable MAX is required.
In the Algorithm 1.1, Algorithm 1.2, step 1 and 2 are in sequence logic and step 3, 4,
and 5 are in selection logic. In order to illustrate iteration logic, consider one more example.
Design an algorithm for adding the test scores given as: 26, 49, 98, 87, 62, 75
Algorithm 1.3:
Step 1: Start
Step 2: Sum = 0
Step 3: Get a value
Step 4: sum = sum + value
Step 5: If next value is present, go to step 3. Otherwise, go to step 6
Step 6: Output the sum
Step 7: Stop
In the Algorithm 1.3 step 5 have a go to statement with a back ward step
reference, so it means that iteration logic.

1.3.2 Pseudocode
Pseudocode ("sort of code") is another way of describing algorithms. It is
called "pseudo" code because of its strong resemblance to "real" program code. Pseudocode
is essentially English with some defined rules of structure and some keywords that make
it appear a bit like program code.
Some guidelines for writing pseudocode are as follows.
Note: These are not "strict" guidelines. Any words used that have similar form and function
may be used in an emergency - however, it would be best to stick to the pseudocode words
used here.
 for start and finish BEGIN MAINPROGRAM, END MAINPROGRAM -
this is often abbreviated to BEGIN and END - especially in smaller programs
 for initialization INITIALISATION, END INITIALISATION - this part is
optional, though it makes your program structure clearer
 for subprogram BEGIN SUBPROGRAM, END SUBPROGRAM
 for selection IF, THEN, ELSE, ENDIF
 for multi-way selection CASEWHERE, OTHERWISE, ENDCASE
 for pre-test repetition WHILE, ENDWHILE
Downloaded from: annauniversityedu.blogspot.com
Page 4
 for post-test repetition REPEAT, UNTIL
 Keywords are written in capitals.
 Structural elements come in pairs, eg for every BEGIN there is an END, for
every IF there is an ENDIF, etc.
 Indenting is used to show structure in the algorithm.
 The names of subprograms are underlined. This means that when refining
the solution to a problem, a word in an algorithm can be underlined and a
subprogram developed. This feature is to assist the use of the ‗top-down‘
development concept.
1.3.3 Flowcharts
Flowcharts are a diagrammatic method of representing algorithms. They use
an intuitive scheme of showing operations in boxes connected by lines and arrows that
graphically show the flow of control in an algorithm.
Table 1.1lists the flowchart symbol drawing, the name of the flowchart
symbol in Microsoft Office (with aliases in parentheses), and a short description of where and
how the flowchart symbol is used.
Table 1.1: Flowchart Symbols
SYMBOL
NAME
(ALIAS)
DESCRIPTION

Flow Line
(Arrow,
Connector)
Flow line connectors show the direction that the process
flows.

Terminator
(Terminal
Point, Oval)
Terminators show the start and stop points in a process.

Data
(I/O)
The Data flowchart shape indicates inputs to and outputs
from a process. As such, the shape is more often referred
to as an I/O shape than a Data shape.

Document
Pretty self-explanatory - the Document flowchart symbol
is for a process step that produces a document.

Process
Show a Process or action step. This is the most common
symbol in flowcharts.

Decision
Indicates a question or branch in the process flow.
Typically, a Decision flowchart shape is used when there
are 2 options (Yes/No, No/No-Go, etc.)

Connector
(Inspection)
This symbol is typically small and is used as a Connector
to show a jump from one point in the process flow to
another. Connectors are usually labeled with capital letters
(A, B, AA) to show matching jump points. They are handy
for avoiding flow lines that cross other shapes and flow
lines. They are also handy for jumping to and from a sub-
processes defined in a separate area than the main
flowchart.
Downloaded from: annauniversityedu.blogspot.com
Page 5
Predefined
Process
(Subroutine)
A Predefined Process symbol is a marker for another
process step or series of process flow steps that are
formally defined elsewhere. This shape commonly depicts
sub-processes (or subroutines in programming flowcharts).

Preparation
As the names states, any process step that is a Preparation
process flow step, such as a set-up operation.

Magnetic
Disk
(Database)
The most universally recognizable symbol for a data
storage location, this flowchart shape depicts a database.

1.3.4 Control Structures of Pseudocode and Flowcharts
Each control structures can be built from the basic elements as shown below.
Sequence: A sequence is a series of steps that take place one after another. Each step is
represented here by a new line.

Our sequence example of changing gears could be described as follows :
Pseudocode
Flowchart
BEGIN
1st Gear
2nd Gear
3rd Gear
4th Gear
5th Gear
END

Pseudocode
Flowchart

BEGIN
Statement
Statement
END

Downloaded from: annauniversityedu.blogspot.com
Page 6
Selection : A Selection is a decision. Some decisions may be answered as Yes or No. These
are called binary selections. Other decisions have more than two answers. These are
called multiway selections.
A binary selection may be described in pseudocode and flow chart as follows :
Pseudocode
Flowchart
IF (question) THEN
statement
ELSE
statement
ENDIF

An example of someone at a set of traffic lights follows :
Pseudocode
Flowchart
IF (lights are green) THEN
Go
ELSE
Stop
ENDIF

A Multiway Selection may be described as follows :
Pseudocode
Flowchart
CASEWHERE (question)
Alternative 1: Statement
Alternative 2 : Statement
OTHERWISE : Statement
ENDCASE

Downloaded from: annauniversityedu.blogspot.com
Page 7
An example of someone at a set of traffic lights follows :
Pseudocode
Flowchart
CASEWHERE Lights are :
Green : Go
Amber : Slowdown
Red : Stop
ENDCASE

Repetition: A sequence of steps which are repeated a number of times, is called repetition.
For a repeating process to end, a decision must be made. The decision is usually called a test.
The position of this test divides repetition structures into two types : Pre-test and Post-test
repetitions.
Pre-test repetitions (sometimes called guarded loops) will perform the test before any part
of the loop occurs.
Post-test repetitions (sometimes called un-guarded loops) will perform the test after the
main part of the loop (the body) has been performed at least once.
Pre-test repetitions may be described in as follows :
Pseudocode
Flowchart
WHILE (question)
Statement
ENDWHILE

Downloaded from: annauniversityedu.blogspot.com
Page 8
A traffic lights example follows :
Pseudocode
Flowchart
WHILE (lights are not green)
wait
ENDWHILE

Post-test repetitions may be described as follows:

A traffic lights example follows :
Pseudocode
Flowchart
REPEAT
Wait
UNTIL lights are green

Pseudocode
Flowchart
REPEAT
Statement
UNTIL (Question)

Downloaded from: annauniversityedu.blogspot.com
Page 9
Sub-Programs: A sub-program is a self-contained part of a larger program. The use of sub-
programs helps with "Top-Down" design of an algorithm, by providing a structure through
which a large and unwieldy solution may be broken down into smaller, more manageable,
components.
A sub-program is described as:
Pseudocode
Flowchart
subprogram

Consider the total concept of driving a car. This activity is made up of a number of sub-
processes which each contribute to the driver arriving at a destination. Therefore, driving may
involve the processes of "Starting the car"; "Engaging the gears"; "Speeding up and slowing
down"; "Steering"; and "Stopping the car".
A (not very detailed) description of driving may look something like:
Pseudocode
Flowchart
BEGIN
Start Car
Engage Gears
Navigate Car
Stop Car
END

Downloaded from: annauniversityedu.blogspot.com
Page 10

GE8151 Problem Solving and Python Programming Notes Unit 1 -5

GE8151 Problem Solving and Python Programming Notes Unit 1 -5

Download this file to view remaining 143 pages