Data Structure And
algorithms(hal-115)
Lecture 3,4
Algorithms
Algorithms (Definition)
An Algorithm (pronounced AL-go-rith-um)
is a sequence of instructions specifying
the steps required to accomplish some
task.OR
An algorithm is a finite step by step list of
well defined instruction for solving a
particular problem.Or
Algorithm is a step by step procedure to
solve a problem.
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
Algorithm -- Examples
A cooking recipe.
The rules of how to play a game.
VCR instructions.
Directions for driving from A to B.
A car repair manual.
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
Computer Algorithms
A computer program is another example of an
algorithm.
To make a computer do anything, you have to
write a computer program. To write a computer
program you have to tell the computer step by
step, exactly what you want to do.
The computer then executes the program
following each step to accomplish the end goal.
When you telling the computer what to do, you
also get to choose how its going to do it. Thats
where computer algorithms come in.
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
From Algorithms to Programs
Problem
Algorithm: A sequence
of instructions describing
how to do a task (or
process)
C Program
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
Examples:
Suppose Add two number a & b and store
in c.
Steps:
Step1: Initialize variable a and b [a=1, b=1]
Step2: Declare variable c.
Steps3: Add variables and store in other
variable [ c= a+b].
Steps4:Print output [c].
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
Implement of Algorithm in C
Void main()
{
int a,b,c; //declaration of variables
a=1,b=1; //initialize variable a and b
c=a+b; // add a and b and store result in c
printf(%d,&c); // print output
}
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
Example:- Algorithm:
Drive_To_Uni
Steps
...etc...etc...etc...
{
1. find car keys
52. find parking space
2. disable car alarm
53. pull into parking
3. open car door
space
4. get in car
54. turn off engine
5. shut car door
55. remove keys from
6. put keys in ignition
ignition
7. start car
56. open car door
8. back car out of
driveway
57. get out
9. drive to end of street
58. shut car door
10. turn right
59. lock car door
11. drive to end of street
60. enable alarm
12. turn left
...etc...etc...etc
} Gull, Dept of
Prepared by: Miss Humera
Information System,KKU
Controls Structures
A control structure or logic structure is a structure that
controls the logical sequences in which programs
instructions are executed.
OR
Control flow or Control structures refers to the order in which
the individual statements, instructions, are executed.
Algorithms and their equivalent computer programs are
more easily understood if they mainly use these types of
control structures.
An algorithm or computer program is usually not limited
to a linear sequence of instructions. During its process it
may bifurcate, repeat code or take decisions.
In algorithm design structure, three types of control
structure are used to form the logic of program.
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
Control Structures Cont.
i.
ii.
iii.
I.
Sequential Logic or sequential Flow.
Selection Logic or Conditional Flow.
Iteration Logic or Repetitive Flow.
Sequential Logic: In sequence control
structure, one program statement following
another logical order.
OR
Steps are executed one after one
i.e Step1 Step2Step3Step4So on
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
10
2. Selection Logic
Selection logic employs a number of conditions
which leads to a selection of one out of several
alternatives conditions.
The selection control structure also known as IFTHEN-ELSE structure.
Its offers two paths to follow when a decision must
be made by a program.
The selection control structure fall into 3 types:
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
11
Selection control structure types:
Single Alterative: (One Condition):
This structure has the form:
IF condition, then
[Module A ]
End of IF structure.
------------------------------------Algorithm:
step1: start
step2: if today is wed then goto step3.
Step3: print today is wed
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
Step4: End/Exit
12
Double Alterative:
This structure has the form
IF condition, then
[Module A]
Else
[Module B]
End of IF Structure
------------------------------
Algorithm:
Step1: start
Step2: if a=1 then goto step3
Step3: Print a=1
Else
Step4: print a!=1
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
Step5: End/Exit.
13
Multiple Alterative:
This structure has
Algorithm:
the form.
IF condition1, then
[Module A] Else
IF condition2, then
[Module B] Else
IF condition3, then
[Module C]
Else
[Module D]
Step1: start
Step2: if a=1 then goto step3
Step3: print a=1.
else
Step4: if a=2 then goto step5
Step5: print a=2.
Else
Step6: if a=3 then goto step7
Step7: print a=3.
Else
Step8: print a!=1,2,3
Step9: End/Exit.
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
14
3. Iteration Logic OR Repetitive Flow
In this iteration or loop control structure a
process may be repeat as long as the
condition remain true.
In this control structure, we use either
two types of structure involving loops.
For Loop
While Loop
For loop is used to repeat a process until a
fix number of times
While loop is used to repeat a process or
instructions until our condition is true.
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
15
Iteration logic Example:
Algorithm:
Step1:
Step2:
for{
Step3:
Step4:
Step5:
Step6:
Step7:
}
Else
Step8:
start
declare variable x as interger
assign value 1 to x variable.
if x<=5 then goto step5
print value of x.
add 1 to x (x++)
goto step4
End
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
16
Program (For Loop)
void main()
{
int x;
Output:
Variable
declaration
Assignment
of a value.
for(x=1;x<=5;x++)
{
printf(\n x=%d,x);
}
}
Format string
check
condition
(value of x)
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
x=1
x=2
x=3
x=4
x=5
Increament
statement ( add 1
to x)
17
Program (while loop)
void main ()
{
int x=3;
OUTPUT:
Data Structure
Data Structure
while(x!=1)
{
printf(\nData Structure);
x--;
}
same as
x = x- 1;
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
18
Complexity of an Algorithm:
The analysis of algorithm is a major task in computer
science. In order to compare algorithm, we must
have some criteria to measure the efficiency or
complexity of an algorithm.
Efficiency of an algorithm depends on two major
criteria.
First one is run time of that algorithm.
Second is space.
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
19
We implement different data structures, some data
structure takes more space but improves the run time
and some take less space but its run time is slow.
Lets suppose space is fixed of an algorithm then only
run time will be considered for obtaining the
complexity.
We take three cases for complexity of algorithms.
Best Case
Worst Case
Average Case
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
20
Best Case: In this case, the algorithm takes less
time to execute or algorithm searches the element in
first time.
Worst Case: In this case, algorithm takes more time
to execute or its fail to achieve its goal or in this case,
algorithm finds the element at end or searching of
element is fail.
Average Case: Here we take probability with list of
data. Average case algorithm should be average
number of steps but since data can be at any place,
so finding exact behavior of algorithm is difficult.
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
21
FLOWCHART
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
22
FLOWCHART
A program flowchart is a graphical representation of
how process works.
OR
A program flowchart is a chart that graphical present the
detail series of steps (algorithm or logical flow)
needed to solve a programming problem.
The program flowchart can be likened to the blueprint
of a building.
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
23
Meaning of a flowchart:
A flowchart is a diagrammatic representation that
illustrates the sequence of operation to be performed
to get the solution of a problem.
Flowcharts facilitate communication between the
programmers and business people.
Flowchart play a vital role in the programming of a
problem and are quite helpful in understanding the
logic of complicated and lengthy problems.
Once the flowchart is drawn, it becomes easy to write
the program in any
high level language.
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
24
Design the Flowchart
The flowchart is drawn according to define rules and
using standard flowchart symbols.
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
25
Symbols of FlowChart
Terminator: An oval
flowchart indicating the start
and end of process.
Process: A rectangular
shape indicating a normal
process flow step or
calculation or assigning of
values to variables.
Data: A parallelogram shape
indicating any statement that
causes data to be input to a
program or output from the
program.
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
26
Symbols of Flowchart:
Decision: A diamond shape
indicating conditional steps.
Diamond shape have two
paths (True/False or Yes/No)
Connector: A small, labelled
circular shape used to
indicate a jump in the
process flow.
Arrows: Arrows are used to
connect symbols and
indicates the sequence of
operations.
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
27
Example:
Program:
Start
Void main()
{
int a=1;
Int a=1
NO
if(a=1)
{
printf(a is equal to 1);
}
}
Prepared by: Miss Humera Gull, Dept of
Information System,KKU
If a=1
YES
Print a=1
End
28
