The Role of Algorithms in Computing
Download
Report
Transcript The Role of Algorithms in Computing
Design and Analysis of Algorithms
تصميم وتحليل الخوارزميات
) عال311(
Chapter 1
Introduction to Algorithms
1
Computational problems
• A computational problem specifies an input-output
relationship
What does the input look like?
What should the output be for each input?
• Example 1:
5
Input: an integer number n
Output: Is the number odd ( ?)هل الرقم فردي أو الtrue
• Example 2:
20
4
72
3
Input: array of numbers
Output: the minimum number in the array
18
3
• Example 3:
Input: array of numbers 20 4 72 3
18
Output: the same array sorted (ascending )تصاعديا
3
4
2
18
20
72
Algorithms
• Algorithm is:
1. A tool for solving a well-specified computational problem
2. A sequence of instructions describing how to do a task or process
Input
•
Algorithm
Output
Algorithms must be:
Correct: For each input produce an appropriate output
Efficient: run as quickly as possible, and use as little memory as possible
3
The Problem-solving Process
Analysis
Problem
specification
Design
Algorithm
Implementation
Program
Compilation
Executable
(solution)
4
From Algorithms to Programs
Problem
Algorithm: A sequence of
instructions describing how
to do a task (or process)
C Program
5
Simple Algorithms
Example1 (Min Algorithm)
•
INPUT: a sequence of n numbers,
T is an array of n elements
20
4
T[1], T[2], …, T[n]
•
OUTPUT: the smallest number among them
72
3
18
min = T[1]
for i = 2 to n do
{
if T[i] < min
min = T[i]
}
Output min
• Max, Min take time = n
6
Simple Algorithms (cont.)
•
•
Algorithms can be implemented in any programming language
Usually we use “pseudo-code” to describe algorithms
• Example 2 (MAX algorithm):
•
•
INPUT: a sequence of n numbers,
T is an array of n elements
T[1], T[2], …, T[n]
OUTPUT: the largest (biggest) number among them
Max = T[1]
for i = 2 to n do
{
if T[i] > Max
Max = T[i]
}
Output Max
7