Module 1 (Algorithms)

Data Structures
LESSON 1: ALGORITHMS
Algorithm
 Any method of solving a certain kind of problem.

 A precise method usable by a computer for the solution of a problem.
 A finite set of instructions which, if followed accomplishes a particular
task. Finite:bounded in a temporal
steps
Guiding Principles Unambiguous:having clearly
defined meaning
 Input
o 0 or more quantities which are externally supplied.
 Output
o At least 1 quantity is produced.
 Finiteness
o Must terminate after a finite number of steps; traceability.
 Definiteness
o Each instruction must be clear and unambiguous.
 Effectiveness
o Basic and feasible.
C.S. View
Machines for executing algorithms involve the study of various fabrications

and organizations for algorithms to be carried out. Languages for describing
algorithms
2 phases:
Language design
Translation
Foundation of Algorithms
 Can a particular task be accomplished by a computing device?

 What is the minimum number of operations for any algorithm to
perform a certain function?
Analysis of Algorithms
 Know the behavior of the algorithm.
 This includes the pattern and performance profile of an algorithm, that
can be measured in terms of its execution time and the amount of
space consumed.
How to create programs:
Requirements:
Information given (input) and the results to be produced (output)
must be explicitly specified.
Understand the problem.
Design:
Write an algorithm that will solve the problem according to the
requirement.
Analysis:
Trying to come up with another algorithm and compare it with the
previous one.
Urdaneta City University 1

College of Computer Studies
Data Structures
Refinement and Coding:

A representation is chosen and a complete version of the program is
made.
Verification:
Consist of 3 aspects:
 Program
 Proving
 Testing and Debugging
Example 1:
Problem: Accept N inputs and get their sum
Requirement:
Input: Set of N integers
Output: Sum of N integers
Design:
Set a temporary variable to 0.
For each value entered, add the value to the temporary
variable.
Refinement and Coding:
tempsum = 0;
for(i=1; i<=n; i++)
{
scanf(x);
tempsum=tempsum + x;
}
How to analyze programs:
Two Phases:
1. Priori Estimates:
Obtain a function which bounds the algorithm’s complexity time. The

amount of time a single execution will take or the number of times a
statement is executed. However, it is possible to know the exact
amount of time to execute any command unless:
a. the machine we are executing is known;
b. machine instruction set
c. time required by each machine instruction;
d. translation of the compiler from source to machine lang.
2. Posteriori Estimates:
Something to do with memory spaces consumed.
Example:
Use of arrays vs. linked-list
Algorithms:
Scenario: You have a friend arriving at the airport and your friend needs to
get from the airport to your house.

Data Structures
Here are four different algorithms that you might give your friend for getting
to your home:
 The taxi algorithm:

1. Go to the taxi stand.
2. Get in a taxi.
3. Give the driver my address.
 The call-me algorithm:
1. When your plane arrives, call my cell phone.
2. Meet me outside baggage claim.
 The rent-a-car algorithm:
1. Take the shuttle to the rental car place.
2. Rent a car.
3. Follow the directions to get to my house.
 The bus algorithm:
1. Outside baggage claim, catch bus number 70.
2. Transfer to bus 14 on Main Street.
3. Get off on Elm street.
4. Walk two blocks north to my house.
In computer programming, there are often many different ways -- algorithms

-- to accomplish any given task. Each algorithm has advantages and
disadvantages in different situations.

Data Structures
Applying Algorithms in numerical calculations:

A1 A2 A3 A4
 7 * ( 10 + ( 6 - 2 ))
A
Algorithm:
1. 6 - 2 = 4 (A) 1. Subtract A3 to A4.
2. 10 + 4 = 14 (B) 2. Add A2 and A.
3. 7 *14 = 98 3. Multiply A1 by B.
A1 A2 A3 A4 B1 B2 B3
 (75 + ( 3 * ( 2 + 3 ) ) ) / ( 6 * ( 2 + 3 ) )
A D
B
E
C
1. 2 + 3 = 5 (A) 1. Add A3 and A4.

2. 3 * 5 = 15 (B) 2. Multiply A2 by A.
3. 75 + 15 = 90 (C) 3. Add A1 and B.
4. 2 + 3 = 5 (D) 4. Add B2 and B3.
5. 6 * 5 = 30 (E) 5. Multiply B1 by D.
6. 90 / 30 = 3 6. Divide C by E.

Data Structures
ARRAYS
Array – collection of similar data elements. It is a data structure stored in
memory.
Array Variable – can be distinguished through a pair of square brackets and

on specified number inside the square brackets[].
Single or One-Dimensional Array – array with a single index.
Syntax:
data_type_array[size];
Examples:
int num[5];
char name[80];
float area[3];
Graphical Representation
int grade[7];
95 88 93 91 90 87 93
It stores a maximum of 7 integers.
Individual value of grade[7]

grade[0]=95;
grade[1]=88;
grade[2]=93;
grade[3]=91;
grade[4]=90;
grade[5]=87;
grade[6]=93;

Data Structures
Syntax for accepting values Syntax for Displaying Values
/*This code will accept 5 integers /*This code will print the value of
from the user.*/ num[5]*/
int grade[5],x; printf(“%d”, num[5]);
printf(“Enter 5 numbers:\n”) /*This code will print the numbers

from 0 to 10*/
for(x=0;x<5;x++)
{ for (x=0;x<=10;x++)
scanf(“%d”,&grade[x]); {
} printf(“\n %d”,num[x])
}
Example 1: (Single Dimensional Array)
/*This array program gets the sum of 10 numbers inside the array*/
#include<stdio.h>
main(){
int x, sum=0, num[5];
printf("Enter 5 numbers:");
for(x=0;x<5;x++)
{
scanf("%d",&num[x]);
sum = sum + num[x];
}
printf("%d",sum);
}
Example 2: (Single Dimensional Array)
/*This array program finds the smallest and largest number*/
#include<stdio.h>
main(){
int x,num[5],min,max;
printf("Enter five numbers:");
for(x=0;x<5;x++)
{
scanf("%d",&num[x]);
}
min=num[0];
max=num[0];
for(x=0;x<5;x++)
{
if(min>num[x])
min = num[x];
else
if(max<num[x])
max=num[x];
}
printf("\nThe minimum number: %d",min);

Data Structures
printf("\nThe maximum number: %d",max);


Module 1 (Algorithms)

Uploaded by

Copyright:

Available Formats

Module 1 (Algorithms)

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Module 1 (Algorithms)

Uploaded by

Copyright:

Available Formats

Data Structures

 Any method of solving a certain kind of problem.

Machines for executing algorithms involve the study of various fabrications

 Can a particular task be accomplished by a computing device?

How to create programs:

Urdaneta City University 1

Refinement and Coding:

Problem: Accept N inputs and get their sum

Refinement and Coding:

How to analyze programs:

Obtain a function which bounds the algorithm’s complexity time. The

Something to do with memory spaces consumed.

Urdaneta City University 2

 The taxi algorithm:

In computer programming, there are often many different ways -- algorithms

Urdaneta City University 3

Applying Algorithms in numerical calculations:

1. 2 + 3 = 5 (A) 1. Add A3 and A4.

Urdaneta City University 4

Array Variable – can be distinguished through a pair of square brackets and

Single or One-Dimensional Array – array with a single index.

It stores a maximum of 7 integers.

Individual value of grade[7]

Urdaneta City University 5

Syntax for accepting values Syntax for Displaying Values

int grade[5],x; printf(“%d”, num[5]);

printf(“Enter 5 numbers:\n”) /*This code will print the numbers

Example 1: (Single Dimensional Array)

int x, sum=0, num[5];

Example 2: (Single Dimensional Array)

/*This array program finds the smallest and largest number*/

printf("Enter five numbers:");

printf("\nThe minimum number: %d",min);

Urdaneta City University 6

printf("\nThe maximum number: %d",max);

Urdaneta City University 7

You might also like

/This array program finds the smallest and largest number/