PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN
BÀI 1
THUẬT TOÁN VÀ CÁC VẤN ĐỀ LIÊN QUAN
Khoa Công nghệ Thông tin - UTEHY
1
10/31/2022
Bộ môn Công nghệ Phần mềm,�Khoa Công nghệ Thông tin,�Trường Đại học Sư phạm Kỹ thuật Hưng Yên
Nội dung
Khoa Công nghệ Thông tin - UTEHY
2
10/31/2022
Khái niệm thuật toán
2
Mục tiêu bài học
1
Tại sao phải phân tích thuật toán �
3
Những vấn đề phát sinh trong phân tích và thiết kế thuật toán �
4
Tổng kết bài học
5
1. Mục tiêu bài học
Khoa Công nghệ Thông tin - UTEHY
3
10/31/2022
4
10/31/2022
WHY STUDY: Design & Analysis of Algorithms
5
10/31/2022
WHY STUDY: Design & Analysis of Algorithms
Design and Analysis of Algorithms
L1.6
7
10/31/2022
7
Objectives
8
10/31/2022
8
Course Outcomes
After completing the course, students should be able to:
9
10/31/2022
9
Course Outcomes (Contd…)
5. Practice the main algorithm design strategies of Brute Force, Divide & Conquer, Greedy methods, Dynamic Programming, Backtracking and Branch & Bound and implement examples of each.
6. Implement the most common sorting and searching algorithms and perform their complexity analysis.
7. Solve problems using the fundamental graph algorithms including DFS, BFS, SSSP and APSP, transitive closure, topological sort, and the minimum spanning tree algorithms.
8. Evaluate, select and implement algorithms in programming context.
10
10/31/2022
10
NỘI DUNG MÔN HỌC
What is an algorithm?
An algorithm is a list of steps (sequence of unambiguous instructions ) for solving a problem that transforms the input into the output.
�
11
10/31/2022
“computer”
problem
algorithm
input
output
Difference between Algorithm and Program
12
10/31/2022
S.No | Algorithm | Program |
1 | Algorithm is finite | Program need not to be finite |
2 | Algorithm is written using natural language or algorithmic language | Programs are written using a specific programming language |
Fundamentals of Algorithm and Problem Solving
13
10/31/2022
Problem Solving Techniques
i. List major tasks
ii. List subtasks,sub-subtasks & so on
b) (Formal Design)
i. Create formal design from task lists
ii. Desk check design
7. Translate the program into machine language
8. Test the program
i. If necessary debug the program
14
10/31/2022
Basic Issues Related to Algorithms
15
10/31/2022
PROPERTIES OF AN ALGORITHM
DAA - Unit - I Presentation Slides
16
10/31/2022
DAA - Unit - I Presentation Slides
17
10/31/2022
Some Important Problem Types
17
Why study algorithms?
18
Example: Google’s PageRank Technology
Euclid’s Algorithm
Problem: Find gcd(m,n), the greatest common divisor of two nonnegative, not both zero integers m and n
Examples: gcd(60,24) = 12, gcd(60,0) = 60, gcd(0,0) = ?
Euclid’s algorithm is based on repeated application of equality
gcd(m,n) = gcd(n, m mod n)
until the second number becomes 0, which makes the problem
trivial.
Example: gcd(60,24) = gcd(24,12) = gcd(12,0) = 12
19
Two descriptions of Euclid’s algorithm
Step 1 If n = 0, return m and stop; otherwise go to Step 2
Step 2 Divide m by n and assign the value of the remainder to r
Step 3 Assign the value of n to m and the value of r to n. Go to� Step 1.�
while n ≠ 0 do
r ← m mod n
m← n
n ← r
return m
20
Other methods for computing gcd(m,n)
Consecutive integer checking algorithm
Step 1 Assign the value of min{m,n} to t
Step 2 Divide m by t. If the remainder is 0, go to Step 3;� otherwise, go to Step 4
Step 3 Divide n by t. If the remainder is 0, return t and stop;� otherwise, go to Step 4
Step 4 Decrease t by 1 and go to Step 2
21
Is this slower than Euclid’s algorithm? How much slower?
O(n), if n <= m , vs O(log n)
Other methods for gcd(m,n) [cont.]
Middle-school procedure
Step 1 Find the prime factorization of m
Step 2 Find the prime factorization of n
Step 3 Find all the common prime factors
Step 4 Compute the product of all the common prime factors� and return it as gcd(m,n)
Is this an algorithm?
How efficient is it?
22
Time complexity: O(sqrt(n))
Sieve of Eratosthenes
Input: Integer n ≥ 2
Output: List of primes less than or equal to n
for p ← 2 to n do A[p] ← p
for p ← 2 to n do
if A[p] ≠ 0 //p hasn’t been previously eliminated from the list� j ← p* p
while j ≤ n do
A[j] ← 0 //mark element as eliminated
j ← j + p
Example: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
23
Time complexity: O(n)
Two main issues related to algorithms
24
Analysis of algorithms
25
Algorithm Efficiency
26
10/31/2022
27
10/31/2022
Algorithm Analysis
28
10/31/2022
Algorithm Analysis (Contd…)
29
10/31/2022
Algorithm Analysis (Contd…)
30
10/31/2022
31
10/31/2022
Faster Algorithm vs. Faster CPU
31
32
10/31/2022
Algorithm Design Techniques
32
Algorithm Classification
33
Sorting (I)
34
Sorting (II)
35
Selection Sort
Algorithm SelectionSort(A[0..n-1])
//The algorithm sorts a given array by selection sort
//Input: An array A[0..n-1] of orderable elements
//Output: Array A[0..n-1] sorted in ascending order
for i 🡨 0 to n – 2 do
min 🡨 i
for j 🡨 i + 1 to n – 1 do
if A[j] < A[min]
min 🡨 j
swap A[i] and A[min]
36
Searching
37
Input: sorted array a_i < … < a_j and key x;
m 🡨(i+j)/2;
while i < j and x != a_m do
if x < a_m then j 🡨 m-1
else i 🡨 m+1;
if x = a_m then output a_m;
Time: O(log n)
Example of computational problem: sorting
Here, all data are held in primary memory during the sorting process.
Here, it uses primary memory for the data currently being sorted and uses secondary storage for string data.
38
10/31/2022
Types of Sorting
39
10/31/2022
Selection Sort
Suppose A is an array which consists of ‘n’ elements namely A[l], A[2], . . . , A[N]. The selection sort algorithm will works as follows.
b. Interchange A[LOC] and A[1].
c. Now, A[1] is sorted.
2. Step 2: a. Find the location of the second smallest element in the list A[2], . . . , A[N] and put it in the second position.
b. Interchange A[LOC] and A[2].
c. Now, A[1] and A[2] is sorted. Hence, A[l] ≤ A[2].
3. Step 3: a. Find the location of the third smallest element in the list A[3], . . . , A[N] and put it in the third position.
b. Interchange A[LOC] and A[3].
c. Now, A[1], A[2] and A[3] is sorted. Hence, A[l] ≤ A[2] ≤ A[3].
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .
N-1. Step N–1 : a. Find the location of the smallest element in the list A[A–1] and A[N].
b. Interchange A[LOC] and A[N–1] & put into the second last position.
c. Now, A[1], A[2], …..,A[N] is sorted. Hence, A[l] ≤ … ≤ A[N–1] ≤A[N].
40
10/31/2022
DAA - Unit - I Presentation Slides
41
10/31/2022
Some Well-known Computational Problems
42
10/31/2022
Some of these problems don’t have efficient algorithms, or algorithms at all!
BÀI TẬP
43
10/31/2022
Some of these problems don’t have efficient algorithms, or algorithms at all!
DAA - Unit - I Presentation Slides
44
10/31/2022