Struktur Data & Algoritme (Data Structures & Algorithms)

Struktur Data & Algoritme (Data Structures & Algorithms) Wrap Up

Denny ([email protected]) Suryana Setiawan ([email protected]) Fakultas Ilmu Komputer Universitas Indonesia Semester Genap - 2004/2005 Version 2.0 - Internal Use Only

Objectives „

Mengulas kembali dan merangkum konsep-konsep penting dalam kuliah Struktur Data dan Algoritme

SDA/WRAP-UP/V2.0/2

1

Struktur Data dan Algoritme „

Data structure (aka ADT – Abstract Data Type) = representation + operations „ operation allowed may vary between data structure • • • •

„

insert delete access (find / get) update

Algoritme „ Suatu set instruksi yang harus diikuti oleh computer untuk memecahkan suatu masalah. „ Program harus berhenti dalam batas waktu yang wajar (reasonable) „ Tidak terikat pada programming language atau bahkan paradigma pemrograman (mis. Procedural vs Object-Oriented) SDA/WRAP-UP/V2.0/3

Struktur Data dan Algoritme „

„

Mengapa dalam penyimpanan data diperlukan sebuah struktur? „ Supaya lebih mudah/efisien dalam pengaksesan/pemrosesan data tersebut Mengapa struktur data penting? Bukankan hanya algoritme saja yang menentukan running time? „ Problem: mencari sebuah integer dalam data-data yang terurut „ Algoritme: binary search!!! „ Struktur data: • binary search pada array? • binary search pada linked list? doubly linked list? „

Struktur data mana yang lebih efisien? SDA/WRAP-UP/V2.0/4

2

Struktur Data dan Algoritme „

Contoh Lain: „ Problem: mengevaluasi ekspresi: (5 + 2) * 7 „ menggunakan struktur data Stack

„

struktur data + algoritme = program Algorithms require the use of a proper representation of data to achieve efficiency

„

„ „

Struktur data membantu tercapainya Component Reusability. Menerapkan konsep OO paradigm: encapsulation, information-hiding dan abstraction. SDA/WRAP-UP/V2.0/5

Analisa Algoritme: what? „

Mengukur jumlah sumber daya (time dan space) yang diperlukan oleh sebuah algoritme

„

Waktu yang diperlukan (running time) oleh sebuah algoritme cenderung tergantung pada jumlah input yang diproses.

Î Running time dari sebuah algoritme adalah fungsi dari jumlah inputnya „

Selalu tidak terikat pada platform (mesin + OS), bahasa pemrograman, kualitas kompilator atau bahkan paradigma pemrograman (mis. Procedural vs Object-Oriented)

SDA/WRAP-UP/V2.0/6

3

Analisa Algoritme: how? „

„

Notasi O (sering disebut sebagai “notasi big-Oh”) „ Digunakan sebagai bahasa untuk membahas efisiensi dari sebuah algoritme: log n, linier, n log n, n2, n3, ... „ Big Oh digunakan untuk merepresentasikan laju pertumbuhan (growth rate) Dominant Term „ Mengapa hanya suku yang memiliki pangkat tertinggi/dominan saja yang diperhatikan? „ Untuk n yang besar, suku dominan lebih mengindikasikan perilaku dari algoritme. „ Untuk n yang kecil, suku dominan tidak selalu mengindikasikan perilakunya, tetapi program dengan input kecil umumnya berjalan sangat cepat sehingga kita tidak perlu perhatikan. SDA/WRAP-UP/V2.0/7

Orde Fungsi Running-Time Function c log N log2 N N N log N N2 N3 2N N!

Name Constant Logarithmic Log-squared Linear N log N Quadratic Cubic Exponential Factorial SDA/WRAP-UP/V2.0/8

4

Fungsi Running-Time „

Untuk input yang sedikit, beberapa fungsi lebih cepat dibandingkan dengan yang lain.

SDA/WRAP-UP/V2.0/9

Fungsi Running-Time (2) „

Untuk input yang besar, beberapa fungsi runningtime sangat lambat - tidak berguna.

SDA/WRAP-UP/V2.0/10

5

Sorting „ „ „

Sorting = pengurutan Sorted = terurut menurut kaidah tertentu Sorting umumnya dipakai dalam pre-processing untuk mempercepat proses-proses berikutnya. „ misalnya: • mencari elemen Î binary search • menghilangkan duplikasi

SDA/WRAP-UP/V2.0/11

Bubble Sort „ „ „

Idea: Gelembung udara (ringan) dalam air akan naik ke atas, air (berat) yang di atasnya akan turun. Worst case: O(n2) Best case: O(n) -- when? why?

SDA/WRAP-UP/V2.0/12

6

Selection sort & Insertion sort „

„

„

Incremental approach „ 2 array: terurut dan tidak terurut „ Awalnya array yang terurut kosong. Kosong Æ sorted „ Ambil 1 elemen dari array yang tidak terurut, masukkan ke array yang terurut sedemikian rupa sehingga tetap menjaga keterurutan data (invariant). „ Lakukan sebanyak n kali. Selection: „ Ambil 1 element yang terkecil dari array yang tidak terurut Î O(n) „ letakkan di paling belakang di array yang terurut Î O(1) Insertion: „ Ambil 1 element (yang mana saja) dari array yang tidak terurut Î O(1) „ sisipkan di posisi yang benar dalam array yang terurut supaya array tetap terurut Î O(n) SDA/WRAP-UP/V2.0/13

Merge Sort & Quick sort „ „

Divide and Conquer approach Î Recursive Merge sort: „ Divide: bagi array menjadi 2 bagian yang sama besar Î O(1) „ Conquer: • kalau panjang array 0 atau 1 Æ sudah terurut • menggabungkan (merge) dua array yang sudah terurut Î O(n)

Dilakukan log n kali (best case dan worst case) Quick sort: „ Divide: bagi array menjadi 2 bagian Î O(n) „

„

• bagian 1 berisi elemen < pivot • bagian 2 berisi elemen >= pivot „

Conquer:

„

Dilakukan log n kali (best case), n kali (worst case) Î tergantung cara pemilihan pivot. SDA/WRAP-UP/V2.0/14

• menyambungkan bagian 1 dan bagian 2 Î O(1)

7

Other Sorting Algorithms „ „

„

Shell Sort Heap Sort „ Menggunakan struktur data heap „ Heapify Î O(n) „ Percolate Down O(log n) dilakukan n kali „ Total: O(n log n) Bucket Sort / Postman Sort „ Tukang Pos mengurutkan surat berdasarkan kode pos (5 digit). „ Running time: O(nk) • k = jumlah digit

„

External Sorting Algorithms „ Jumlah data >>> jumlah memory yang tersedia SDA/WRAP-UP/V2.0/15

Struktur Data „

Linked List vs. Array „ representation/storage: • contiguous vs. non-contiguous • growable (dynamic size) vs. static • overhead?

Access? Stack vs. Queue „ Access? „ Implementation of Stack and Queue „

„

• Linked List vs. Array

SDA/WRAP-UP/V2.0/16

8

Struktur Data „

Tree „ Binary Tree • Representation? • Traversing: • DFS: Pre-Order, In-Order, Post-Order • BFS: Level-Order „ „

Binary Search Tree (BST) Balanced BST • AVL Tree: Height as balancing information • Red-Black Tree: Colour as balancing information

„ „

n-ary Tree Balanced n-ary Tree • Complete Tree: but node can have x children or y children • 2-3 Tree, a-b Tree • External Data Structure: B Tree, B+Tree

„

Trie SDA/WRAP-UP/V2.0/17

Struktur Data „

Hash Table „ Hash Function: map key to address „ Collition resolution: • Closed Hashing (aka Open addressing) • Linear Probing Æ primary clustering • Quadratic Probing Æ secondary clustering • Double Hashing • Open Hasing (aka Separate Chaining)

„

Priority Queue „ Implemented using Heap • Insert: Percolate Up – O(log n) • Delete: Percolate Down – O(log n) • Heapify SDA/WRAP-UP/V2.0/18

9

Graph „

Terminology „ vertices/nodes (simpul) „ edges (sisi/busur) „ adjacent vertices „ undirected vs. directed graph „ degree (of a vertex), for directed graph: in-degree, outdegree „ unweighted vs. weighted graph „ path, simple path, cycle „ DAG (Directed Acyclic Graph) „ connected graph „ subgraph

SDA/WRAP-UP/V2.0/19

Graph „

Representation „ Edge List „ Adjancency List „ Adjancency Matrix Which representation is the best? Graph Problem: „ Topological Sorting „ Shortest Path: Djikstra „ Minimum Spanning Tree: Prim, Kruskal „

„

SDA/WRAP-UP/V2.0/20

10

Selamat Ujian!

SDA/WRAP-UP/V2.0/21

11