Design and Analysis of Algorithm

Design and Analysis of Algorithm Week 1: Introduction Dr. Putu Harry Gunawan1 1 Department

of Computational Science School of Computing Telkom University

Dr. Putu Harry Gunawan (Telkom University)

Design and Analysis of Algorithm

1 / 41

Outline

1

Introduction About this course Beginning of Algorithm The efficiency of algorithm

2

Exercise Rules Skilled Group Careful Group Smart Group

3

Homeworks



2 / 41

Outline

1


2


3

Homeworks



3 / 41

Goals

Sebelum UTS: 1

Mahasiswa mampu untuk mejelaskan kompleksitas waktu pada suatu algoritma

2

Mahasiswa mampu menganalisis kompleksitas suatu algoritma.

Setelah UTS: 1

Mahasiswa mampu membedakan tipe dan karakteristik masing-masing algoritma.

2

Mahasiswa mampu merancang suatu algoritma berdasarkan contoh-contoh algoritma yang sudah diberikan.



4 / 41

References

Figure : Main reference. Dr. Putu Harry Gunawan (Telkom University)


5 / 41

Grading

TUGAS 15% KUIS 20% UTS 25% TUGAS BESAR 15% UAS 25% NB: Bonus jika absensi mencapai 100% (Membuat buku tugas yang akan dikumpul setiap pengumpulan tugas)



6 / 41

Outline

1


2


3

Homeworks



7 / 41

What is algorithm? An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.



8 / 41

Algorithm

An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time. Can be represented various forms Unambiguity/clearness Effectiveness Finiteness/termination Correctness



9 / 41

Example of computational domain

Statement of problem: Input: A sequence of n numbers < a1 , a2 , · · · , an > Output: A reordering of the input sequence < a10 , a20 , · · · , an0 > so that ai0 ≤ aj0 whenever i < j

Instance: The sequence < 5, 3, 2, 8, 3 > Algorithms: Selection sort Insertion sort Merge sort (many others)



10 / 41

Some well-known of computational domain Sorting Searching Shortest paths in a graph Minimum spanning tree Primality testing Traveling salesman problem Knapsack problem Chess Towers of Hanoi Program termination Some of these problems dont have efficient algorithms, or algorithms at all!



11 / 41

Basic Issues Related to Algorithms

How to design algorithms How to express algorithms Proving correctness Efficiency (or complexity) analysis Theoretical analysis Empirical analysis

Optimality



12 / 41

Algorithms and design strategies

Brute force Divide and conquer Decrease and conquer Transform and conquer Greedy approach Dynamic programming Backtracking and branch-and-bound Space and time tradeoffs



13 / 41

Analysis algorithms

How good is the algorithm? Correctness Time efficiency Space efficiency

Does there exist a better algorithm? Lower bounds Optimality



14 / 41

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) = ?



15 / 41


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) = ? Euclids 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)



15 / 41


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) = ? Euclids 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



15 / 41


Exercise: Make an algorithm for computing the gcd(m,n)!



16 / 41


Exercise: Make an algorithm for computing the gcd(m,n)! 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 6= 0 do r ← m mod n m←n n←r return m



16 / 41

Another method to compute gcd

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



17 / 41



Is this slower than Euclids algorithm? How much slower?



17 / 41



Is this slower than Euclids algorithm? How much slower? O(n), if n ≤ m , vs O(log n)



17 / 41

Outline

1


2


3

Homeworks



18 / 41

Efficiency

Pertimbangan Memilih algoritma : Kebenaran Tepat guna (efektif) output sesuai dengan inputnya sesuai dengan permasalahan

Kemudahan/ kesederhanaan Untuk dipahami Untuk diprogram (proses coding)



19 / 41

Efficiency

Pertimbangan Memilih algoritma : Kecepatan Algoritma: Berkaitan dengan kecepatan eksekusi program Hemat Biaya: mengacu pada kebutuhan memory



20 / 41

Efficiency

Keempatnya sulit dicapai bersamaan, dan biasanya yang diutamakan adalah efisiensi (cepat dan hemat) Analisis Algoritma : menganalisis efisiensi algoritma, yang mencakup : efisiensi waktu (kecepatan)→ banyaknya operasi yang dilakukan efisiensi memori → struktur data dan variabels yang digunakan



21 / 41

Efficiency

Algoritma yang bagus adalah algoritma yang efisien Algoritma yang efisien ialah algoritma yang meminimumkan kebutuhan waktu dan ruang/memori. Kebutuhan waktu dan ruang suatu algoritma bergantung pada ukuran masukan (n), yang menyatakan jumlah data yang diproses.



22 / 41

Efficiency

Question: Mana yang lebih baik : menggunakan algoritma yang waktu eksekusinya cepat dengan komputer standard atau menggunakan algoritma yang waktunya tidak cepat tetapi dengan komputer yang cepat? ¡Watch Video¿



23 / 41

Efficiency

Misal dipunyai : Algoritma dengan waktu eksekusi dalam orde 2n Sebuah komputer dengan kecepatan 10−4 × 2n n = 10 → 1/10 detik n = 20 → 2 menit n = 30 →lebih dari satu hari n = 38 → 1 tahun



24 / 41

Efficiency

Misal dipunyai : Algoritma dengan waktu eksekusi dalam orde 2n Sebuah komputer dengan kecepatan 10−6 x2n n = 45 → 1 tahun



25 / 41

Efficiency

Misal dipunyai : Algoritma dengan waktu eksekusi dalam orde n3 Sebuah komputer dengan kecepatan 10−4 xn3 n = 900 → 1 hari n = 6800 → 1 tahun



26 / 41

Efficiency Misal dipunyai : Mengapa kita memerlukan algoritma yang efisien? Lihat grafik di bawah ini.



27 / 41

Outline

1


2


3

Homeworks



28 / 41

Rules

Make a group Each group consists of 5 or more peoples Choose a leader Prepare the answer sheet



29 / 41

Outline

1


2


3

Homeworks



30 / 41

Problem 1

Buatlah algoritma untuk membuat Jus Nanas! Usahakan menggunakan sintax-syntax berikut sebanyak mungkin Comment

repeat loop

Assignment

conditional

Logical

case

relational

input

while loop

output

for loop

procedure



31 / 41

Problem 1

Buatlah algoritma untuk membuat kopi! Usahakan menggunakan sintax-syntax berikut sebanyak mungkin Comment

repeat loop

Assignment

conditional

Logical

case

relational

input

while loop

output

for loop

procedure



32 / 41

Problem 2

Buatlah algoritma untuk membuat Sambal Balado! Usahakan menggunakan sintax-syntax berikut sebanyak mungkin Comment

repeat loop

Assignment

conditional

Logical

case

relational

input

while loop

output

for loop

procedure



33 / 41

Problem 2

Buatlah algoritma untuk membuat Lumpia Basah! Usahakan menggunakan sintax-syntax berikut sebanyak mungkin Comment

repeat loop

Assignment

conditional

Logical

case

relational

input

while loop

output

for loop

procedure



34 / 41

Outline

1


2


3

Homeworks



35 / 41

Problem 3

Given the following algorithm:

if the input 60, 35, 81, 98, 14, 47, what is the output?



36 / 41

Outline

1


2


3

Homeworks



37 / 41

Problem 4

Design a algorithm that reads as its inputs the (x, y ) coordinates of the endpoints of two line segments P1 , Q1 and P2 , Q2 and determines whether the segments have a common point.



38 / 41

Problem 5

Design an algorithm for the following problem: Given a set of n points in the Cartesian plane, determine whether all of them lie on the same circumference.



39 / 41

Homeworks Compare two algorithms of shorting problem, give an analysis and a comment for the each algorithms. Compare two algorithms of searching problem, give an analysis and a comment for the each algorithms. Prove the following relations 1 2 3

1 + 2 + 3 + · · · + n = n(n+1) 2 1 + 3 + 5 + · · · + (2n − 1)P= n2 n if n ∈ Z and n ≥ 0, then i=0 i · i! = (n + 1)! − 1

Compute the following sums. 1 2 3 4 5

Pn+1 1 Pi=3 n+1 i Pi=3 n−1 i(i + 1) Pi=0 n j+1 3 i=0 Pn Pn i=1 j=1 ij



40 / 41

The end of week 1

Thank you for your attention!



41 / 41

Design and Analysis of Algorithm

Recommend Documents