Course
Course No.: CSE2207
Course Title: Algorithms
Course Teacher:
C T h [Link] Khairul
Kh i l Hasan
H (P i )
(Paris)
Contact: Provided in Google Classroom
Department of Computer Science and Engineering
Ahsanullah University of Science and Technology
1
Paris
Text Books
Introduction to Algorithms
Third Edition
by Thomas H. Cormen, Leiserson, Rivest & Stein
Fundamentals of Computer Algorithms
S
Secondd Edition
Editi
by Horowitz, Sartaj Sahni, & Rajasekaran
2
Paris
Hope/Assumption: Topics Covered
in Previous Semesters
Sorting Algorithms: Bubble, Selection, Insertion, Quick,
Merge
Heap, Heapify, Heapsort
Priority Queue
Linear Search, Binary Search
Tree Binary Search Tree
Tree,
Graph, BFS, DFS
3
Paris
Algorithm: Definition
An algorithm is a finite set of instructions
that, if followed, accomplishes a particular
task.
Input (x, y) Input (x, y) z=x+y
Output (z) z=x+y Input (x, y)
z=x+y O t t (z)
Output ( ) O t t (z)
Output ( )
4
Paris
Algorithm:
Chatacteristics/Criteria/Properties
(1) Input: Zero or more quantities that are externally supplied.
(2) Output:
O t t At least
l t one quantity
tit is
i produced.
d d
(3) Definiteness: Each instruction is clear and unambiguous.
Not permitted: 7/0, add 7 or 8 to x, √
√-1,
1, 0/0
(4) Finiteness: If we trace out the instructions of an algorithm,
then for all cases, the algorithm terminates after finite
number of steps.
steps
(5) Effectiveness: Every instruction must be very basic so that it
can be carried out, in principle, by a person using only pencil
and paper.
paper It is not enough
eno gh that each operation be definite as
in criterion 3; it also must be feasible.
5
Paris
Algorithm vs. Program
Algorithm Program
Written at Design time Written at Implementation time
He who has Domain Knowledge
g Programmer
g
Written in any language Written in Programming Language
H/W and S/W independent H/W and S/W dependent
C Analyze
Can A l C Test
Can T t
6
Paris
Algorithm: Effectiveness/ Why
efficient algorithm needed (1)
Suppose, Time complexity of Insertion sort: c1n2
Merge sort: c2n lg n [lg n= lg2n]
Insertion sort requires 2n2 [c1=2] instructions
Merge sort requires 50n lg n [c2=50] instructions
Computer A executes 10 billion(1010) instructions/sec [Insertion]
Computer B executes 10 million(107) instructions/sec [Merge]
So, A is 1000 times faster than B
Sort n=10 million (107) numbers
7
Paris
Algorithm: Effectiveness/ Why
efficient algorithm needed (2)
Computer A takes, 2
2*(10
(107)2 / 1010 = 20,000 sec
= more than 5.5 hours
[ 1010 instructions -------- 1 sec
1 instruction -------- 1 / 1010 sec
2*(107)2 instructions -------- 2*(107)2 / 1010 sec ]
Computer B takes, 50*(107) lg 107 / 107) = 1163 sec
= less than 20 minutes
B runs more than 17 times faster than A
8
Paris
Practice for Exam
Exercises:
Cormen ((Page
g - 14):
) 1.2-2,, 1.2-3
Problem:
Cormen (Page - 14): 1-1
9
Paris
Next Class
Topic:
y of Insertion Sort
Analysis
Prerequisite:
Insertion Sort Algorithm
10
Paris
Thank You
11
Paris
Stay Safe
12
Paris
