Faculty of Computer and Artificial Intelligence

Sadat University

Analysis and Design of Algorithms (CS 302)

Lecture :1

“Introduction”

Dr.Sara A Shehab
 Introduction
❑ What is an algorithm?
A simple, unambiguous, mechanical procedure to
carry out some task.

❑ Why algorithm instead of program?

1. Writing an algorithm is simpler (we don’t need to

worry about the detailed implementation, or the
language syntax).

2. An algorithm is easier to read than a program written

in, for instance, C.

2
 Introduction (Cont..)
❑ How to represent an algorithm?

1. Give a description in your own language, e.g.

English, Spanish, …

2. Pseudo code

3. Graphical

3
 Algorithm Efficiency
▪ Some algorithms are more efficient than others
▪ The complexity of an algorithm is a function describing
the efficiency of the algorithm in terms of the amount of
data the algorithm must process.
▪ There are two main complexity measures of the
efficiency of an algorithm
1. Time Complexity
2. Space Complexity
4
 Time Complexity
▪ Time Complexity is a function describing the amount of
time an algorithm takes in terms of the amount of input
to the algorithm
▪ "Time" can mean the number of memory accesses
performed, the number of comparisons between
integers, the number of times some inner loop is
executed.

5
 Space Complexity
▪ Space complexity is a function describing the amount of
memory (space) an algorithm takes in terms of the
amount of input to the algorithm.
▪ Space complexity is sometimes ignored because the
space used is minimal and/or obvious, but sometimes it
becomes as important an issue as time.

6
 Big Oh notation
• For run time complexity analysis we use big Oh notation.
• We have chosen to use big Oh notation for a few
reasons, the most important of which is that it provides
an abstract measurement by which we can judge the
performance of algorithms without using mathematical
proofs.

7
❑ The following list explains some of the most common
big Oh notations:

• O(1) constant: the operation doesn't depend on the size of

its input, such as adding a node to the tail of a linked list.

• O(n) linear: the run time complexity is proportionate to the

size of n.

• O(log n) logarithmic: normally associated with algorithms

that break the problem into smaller chunks per each
invocation, such as searching a binary search tree.

• O(n log n) just n log n: usually associated with an

algorithm that breaks the problem into smaller chunks per
each invocation, and then takes the results of these smaller
chunks and stitches them back together, such as quick sort.

8
 Pseudocode
➢ Pseudocode is not an actual programming language.
➢ So it cannot be compiled into an executable program.
➢ It uses short terms or simple English language syntaxes to
write code for programs before it is actually converted into a
specific programming language.
➢ And there is no pseudocode standard syntax and so at times
it becomes slightly confusing when writing Pseudocode and
so let us understand pseudo code with an example.
9
 Pseudocode Example
1
Pseudocode Example 2
3
BEGIN

4 Number n1,n2
Design the algorithm and 5
6 Input n1
flowchart that finds and 7
8 Input n2
display the larger of the two 9
10 IF (n1>n2) THEN
numbers given different from 11
12
OUTPUT(n1+" is higher")
ELSE IF(n2>n1)
13 OUTPUT(n2+" is higher")
each other. 14 ELSE
15 OUTPUT("n1=n2")
16 END IF
17 END
18

10
 Pseudocode Example

Pseudocode Example 1
2 BEGIN
3
Perform the application that 4 Number b,h
5
,area
calculates the area of the 6
7 Input b
8
triangle whose height and 9 Input h
1
0
base length entered by the 1
area=(b*h)/2
OUTPUT (Area of Triangle is "+area)
1
END
keyboard. 1
2
1
3

11
 Flow-Chart

A flowchart is simply a graphical representation of steps.

It shows steps in sequential order and is widely used in
presenting the flow of algorithms, workflow or
processes. Typically, a flowchart shows the steps as
boxes of various kinds, and their order by connecting
them with arrows.

12
Flow-Chart

13
 Flow-Chart Example

Here is an example that shows how

flowchart can be used in showing a
simple summation process.

14
 Flow-Chart Example
Flowchart Example – Calculate Profit and Loss

15
 Analysis of Algorithms
1. Best Case
2. Average case
3. Worst Case

16
 Design of Algorithms
1. Divide-and-Conquer

2. Greedy

3. Dynamic Programming

4. Backtracking & Branch-and-Bound

17