Modul Persiapan Olimpiade Sains Nasional (OSN) Informatika

Buku ini disusun sebagai panduan komprehensif bagi siswa yang bercita-cita meraih prestasi dalam ajang Olimpiade Sains Nasional (OSN) bidang Informatika. Modul ini dirancang secara sistematis, mencakup materi-materi inti yang menjadi fondasi utama dalam kompetisi OSN, mulai dari dasar-dasar algoritma hingga teknik pemrograman tingkat lanjut yang kerap muncul dalam soal-soal olimpiade.

Struktur buku terdiri dari beberapa bab tematik yang disusun berdasarkan kurikulum dan kecenderungan soal OSN Informatika dari tahun-tahun sebelumnya. Setiap bab memuat penjelasan teori yang ringkas namun mendalam, contoh soal yang relevan, serta latihan-latihan bertingkat yang membantu pembaca memahami dan menguasai setiap konsep. Buku ini tidak hanya mengedepankan hafalan rumus, tetapi juga mendorong pembentukan pola pikir algoritmik, pemecahan masalah secara logis, dan keterampilan rekayasa perangkat lunak dalam skala kompetisi.

Materi dalam buku ini mencakup topik-topik seperti:

Dasar-dasar algoritma dan kompleksitas waktu

Struktur data dasar dan lanjutan (array, linked list, stack, queue, tree, graph, dsb.)

Teknik rekursi dan divide and conquer

Dynamic programming dan greedy algorithm

Graph theory dan pencarian jalur (BFS, DFS, Dijkstra, dsb.)

Teknik simulasi dan ad hoc problem

Implementasi pemrograman kompetitif dalam bahasa Python dan C++

Selain menyajikan teori dan soal latihan, buku ini juga dilengkapi dengan:

Strategi belajar mandiri dan pengaturan waktu latihan

Kumpulan soal-soal OSN Informatika tingkat kabupaten, provinsi, dan nasional yang telah diadaptasi ulang untuk latihan

Penjelasan dan pembahasan mendalam terhadap soal-soal tingkat lanjut

Tips dan trik dari alumni OSN serta pembina berpengalaman

Modul ini cocok digunakan secara individu maupun dalam bimbingan kelompok belajar. Bagi guru dan pembina, buku ini dapat menjadi sumber rujukan untuk menyusun materi pelatihan yang terstruktur dan berbobot. Untuk siswa, buku ini adalah bekal penting dalam membangun kepercayaan diri dan ketangguhan dalam menghadapi tantangan kompetisi.

Harapannya, buku ini tidak hanya melatih keterampilan teknis, tetapi juga menumbuhkan semangat kompetitif, ketekunan dalam belajar, dan kecintaan terhadap bidang informatika. Dengan pendekatan yang sistematis, latihan yang intensif, dan semangat pantang menyerah, buku ini menjadi jembatan menuju prestasi gemilang di panggung Olimpiade Sains Nasional.

1. 1

2. Daftar Isi
Daftar Isi...........................................................................................................................................................................................1
Modul 1: Dasar-dasar Pemrograman.....................................................................................................................................5
Tujuan Pembelajaran.............................................................................................................................................................5
Ringkasan Teori.......................................................................................................................................................................5
1. Struktur Dasar Program C++......................................................................................................................................5
2. Tipe Data............................................................................................................................................................................5
3. Operator.............................................................................................................................................................................5
4. Input/Output...................................................................................................................................................................5
5. Percabangan.....................................................................................................................................................................6
6. Perulangan........................................................................................................................................................................6
7. Fungsi.................................................................................................................................................................................6
Aktivitas Praktikum................................................................................................................................................................7
Latihan 1: Program Hello World....................................................................................................................................7
Latihan 2: Hitung Luas Persegi Panjang.....................................................................................................................7
Latihan 3: Bilangan Ganjil atau Genap........................................................................................................................7
Latihan 4: Fungsi Faktorial.............................................................................................................................................8
Tugas Mandiri...........................................................................................................................................................................8
Pertanyaan Refleksi................................................................................................................................................................9
Modul 2: Operasi Logika dan Bitwise..................................................................................................................................10
Tujuan Pembelajaran...........................................................................................................................................................10
Ringkasan Teori.....................................................................................................................................................................10
1. Operator Logika (Boolean)........................................................................................................................................10
2. Operator Bitwise...........................................................................................................................................................10
3. Tabel Kebenaran............................................................................................................................................................11
4. Modus Ponens (Logika Proposisional)..................................................................................................................11
Aktivitas Praktikum..............................................................................................................................................................11
Latihan 1: Simulasi Tabel Kebenaran Dua Variabel..............................................................................................11
Latihan 2: Implementasi XOR Dua Bilangan...........................................................................................................12
Latihan 3: Implementasi Modus Ponens..................................................................................................................12
Tugas Mandiri.........................................................................................................................................................................13
Pertanyaan Refleksi..............................................................................................................................................................13
Modul 3: Aritmetika dan Teori Bilangan...........................................................................................................................14
Tujuan Pembelajaran...........................................................................................................................................................14
Ringkasan Teori.....................................................................................................................................................................14
1. Operasi Dasar Bilangan Bulat...................................................................................................................................14
2. Paritas dan Keterbagian.............................................................................................................................................14
3. Bilangan Prima..............................................................................................................................................................14
4. Operasi Modular...........................................................................................................................................................15
5. Perpangkatan Modular..............................................................................................................................................15
Aktivitas Praktikum..............................................................................................................................................................15
Latihan 1: Program Pengecekan Bilangan Prima...................................................................................................15
Latihan 2: Implementasi Sieve of Eratosthenes.....................................................................................................16
Latihan 3: Program Operasi Modular dan Perpangkatan Modular................................................................16
Tugas Mandiri.........................................................................................................................................................................17
Pertanyaan Refleksi..............................................................................................................................................................17
Modul 4: Aturan Berhitung dan Kombinatorika.............................................................................................................18
2

3. Tujuan Pembelajaran...........................................................................................................................................................18
Ringkasan Teori......................................................................................................................................................................18
1. Permutasi.........................................................................................................................................................................18
2. Kombinasi.......................................................................................................................................................................18
3. Segitiga Pascal................................................................................................................................................................18
4. Prinsip Pigeonhole.......................................................................................................................................................19
5. Prinsip Inklusi-Eksklusi.............................................................................................................................................19
6. Probabilitas Dasar........................................................................................................................................................19
Aktivitas Praktikum..............................................................................................................................................................19
Latihan 1: Program Menghitung Kombinasi dan Permutasi.............................................................................19
Latihan 2: Program Menampilkan Segitiga Pascal...............................................................................................20
Latihan 3: Simulasi Probabilitas Sederhana (Melempar Dadu).......................................................................21
Tugas Mandiri.........................................................................................................................................................................21
Pertanyaan Refleksi..............................................................................................................................................................22
Modul 5: Rekursi........................................................................................................................................................................23
Tujuan Pembelajaran...........................................................................................................................................................23
Ringkasan Teori.....................................................................................................................................................................23
1. Konsep Rekursi..............................................................................................................................................................23
2. Deret Fibonacci.............................................................................................................................................................23
3. Backtracking..................................................................................................................................................................23
Aktivitas Praktikum.............................................................................................................................................................24
Latihan 1: Fungsi Rekursif untuk Faktorial............................................................................................................24
Latihan 2: Fungsi Rekursif untuk Fibonacci..........................................................................................................24
Latihan 3: Backtracking untuk Pencarian Subset.................................................................................................25
Latihan 4: Rekursi untuk Pencocokan Kata (Pattern Matching)...................................................................25
Tugas Mandiri........................................................................................................................................................................26
Pertanyaan Refleksi..............................................................................................................................................................26
Modul 6: Pencarian dan Pengurutan..................................................................................................................................27
Tujuan Pembelajaran...........................................................................................................................................................27
Ringkasan Teori.....................................................................................................................................................................27
1. Pencarian (Searching)................................................................................................................................................27
2. Pengurutan (Sorting)..................................................................................................................................................27
Aktivitas Praktikum.............................................................................................................................................................28
Latihan 1: Implementasi Linear Search....................................................................................................................28
Latihan 2: Implementasi Binary Search...................................................................................................................28
Latihan 3: Implementasi Bubble Sort........................................................................................................................29
Latihan 4: Implementasi Quicksort...........................................................................................................................29
Latihan 5: Implementasi Heapsort.............................................................................................................................29
Tugas Mandiri........................................................................................................................................................................30
Pertanyaan Refleksi..............................................................................................................................................................30
Modul 7: Strategi Pemecahan Masalah...............................................................................................................................31
Tujuan Pembelajaran...........................................................................................................................................................31
Ringkasan Teori......................................................................................................................................................................31
1. Brute Force......................................................................................................................................................................31
2. Greedy...............................................................................................................................................................................31
3. Divide and Conquer......................................................................................................................................................31
4. Dynamic Programming (DP)....................................................................................................................................31
Aktivitas Praktikum..............................................................................................................................................................31
Latihan 1: Brute Force untuk Subset Sum................................................................................................................31
Latihan 2: Greedy untuk Penyusunan Koin............................................................................................................32
Latihan 3: Divide and Conquer untuk Mencari Nilai Maksimum..................................................................32
3

4. Latihan 4: Dynamic Programming - Fibonacci Bottom-Up...............................................................................33
Latihan 5: Dynamic Programming - Knapsack 0/1..............................................................................................33
Tugas Mandiri........................................................................................................................................................................34
Pertanyaan Refleksi..............................................................................................................................................................34
Modul 8: Struktur Data............................................................................................................................................................35
Tujuan Pembelajaran...........................................................................................................................................................35
Ringkasan Teori.....................................................................................................................................................................35
1. Tipe Data Primitif.........................................................................................................................................................35
2. Array dan String...........................................................................................................................................................35
3. Stack dan Queue............................................................................................................................................................35
4. Binary Heap...................................................................................................................................................................35
5. Disjoint Set (Union-Find)..........................................................................................................................................35
6. Fenwick Tree / Segment Tree..................................................................................................................................35
Aktivitas Praktikum.............................................................................................................................................................36
Latihan 1: Array dan String...........................................................................................................................................36
Latihan 2: Stack dan Queue...........................................................................................................................................36
Latihan 3: Binary Heap (Min Heap)..........................................................................................................................37
Latihan 4: Disjoint Set (Union-Find).........................................................................................................................37
Latihan 5: Fenwick Tree (Binary Indexed Tree)...................................................................................................38
Tugas Mandiri........................................................................................................................................................................38
Pertanyaan Refleksi..............................................................................................................................................................38
Modul 9: Graf dan Tree............................................................................................................................................................40
Tujuan Pembelajaran..........................................................................................................................................................40
Ringkasan Teori.....................................................................................................................................................................40
1. Tree....................................................................................................................................................................................40
2. Graf....................................................................................................................................................................................40
3. Penjelajahan Graf.........................................................................................................................................................40
4. Shortest Path.................................................................................................................................................................40
5. Minimum Spanning Tree (MST)............................................................................................................................40
Aktivitas Praktikum..............................................................................................................................................................41
Latihan 1: Representasi Graf (Adjacency List)........................................................................................................41
Latihan 2: DFS dan BFS...................................................................................................................................................41
Latihan 3: Dijkstra............................................................................................................................................................42
Latihan 4: Kruskal (Minimum Spanning Tree).....................................................................................................43
Tugas Mandiri........................................................................................................................................................................44
Pertanyaan Refleksi..............................................................................................................................................................44
4

5. Modul 1: Dasar-dasar Pemrograman
Tujuan Pembelajaran
Setelah mengikuti modul ini, peserta diharapkan mampu:
Memahami struktur dasar program C++
Menggunakan berbagai tipe data dan operator
Melakukan input dan output menggunakan cin dan cout
Menggunakan percabangan if dan switch
Menggunakan perulangan for, while, dan do-while
Membuat dan memanggil fungsi dengan parameter
Ringkasan Teori
1. Struktur Dasar Program C++
#include <iostream>
using namespace std;
int main() {
// kode program ditulis di sini
return 0;
}
2. Tipe Data
int: bilangan bulat
float, double: bilangan desimal
char: karakter tunggal
bool: nilai logika (true/false)
3. Operator
Aritmatika: +, -, *, /, %
Relasi: ==, !=, <, >, <=, >=
Logika: &&, ||, !
4. Input/Output
int x;
cin >> x;
5

6. cout << "Nilai x adalah: " << x << endl;
5. Percabangan
a. If-Else
if (x > 0)
cout << "Positif";
else
cout << "Negatif atau nol";
b. Switch
switch (nilai) {
case 1: cout << "Satu"; break;
case 2: cout << "Dua"; break;
default: cout << "Lainnya";
}
6. Perulangan
a. For
for (int i = 0; i < 5; i++) {
cout << i << " ";
}
b. While
int i = 0;
while (i < 5) {
cout << i << " ";
i++;
}
c. Do-While
int i = 0;
do {
cout << i << " ";
i++;
} while (i < 5);
7. Fungsi
int tambah(int a, int b) {
return a + b;
6

7. }
Aktivitas Praktikum
Latihan 1: Program Hello World
Deskripsi: Tulis program pertama Anda untuk menampilkan teks ke layar.
Contoh Kode:
#include <iostream>
using namespace std;
int main() {
cout << "Hello, World!" << endl;
return 0;
}
Latihan 2: Hitung Luas Persegi Panjang
Deskripsi: Buat program untuk membaca panjang dan lebar, lalu menghitung luasnya.
Contoh Kode:
#include <iostream>
using namespace std;
int main() {
int panjang, lebar;
cout << "Masukkan panjang: ";
cin >> panjang;
cout << "Masukkan lebar: ";
cin >> lebar;
int luas = panjang * lebar;
cout << "Luas = " << luas << endl;
return 0;
}
Latihan 3: Bilangan Ganjil atau Genap
Deskripsi: Buat program untuk memeriksa apakah bilangan yang dimasukkan adalah ganjil
atau genap.
Contoh Kode:
7

8. #include <iostream>
using namespace std;
int main() {
int bil;
cout << "Masukkan bilangan: ";
cin >> bil;
if (bil % 2 == 0)
cout << "Bilangan genap" << endl;
else
cout << "Bilangan ganjil" << endl;
return 0;
}
Latihan 4: Fungsi Faktorial
Deskripsi: Buat fungsi untuk menghitung faktorial dari sebuah bilangan.
Contoh Kode:
#include <iostream>
using namespace std;
int faktorial(int n) {
int hasil = 1;
for (int i = 1; i <= n; i++) {
hasil *= i;
}
return hasil;
}
int main() {
int x;
cout << "Masukkan bilangan: ";
cin >> x;
cout << "Faktorial dari " << x << " adalah " << faktorial(x) << endl;
return 0;
}
Tugas Mandiri
1.Buat program yang menerima tiga bilangan, lalu menentukan bilangan terbesar.
2.Buat fungsi untuk menghitung nilai pangkat (misalnya 3^4 = 81).
3.Buat program dengan perulangan while untuk menampilkan angka 1 sampai 10.
8

9. Pertanyaan Refleksi
1.Apa perbedaan antara while dan do-while?
2.Kapan sebaiknya menggunakan switch dibanding if?
3.Apa keuntungan menggunakan fungsi dalam program?
9

10. Modul 2: Operasi Logika dan Bitwise
Tujuan Pembelajaran
Setelah menyelesaikan modul ini, peserta diharapkan mampu:
Menggunakan operator logika &&, ||, ! dalam ekspresi boolean
Menggunakan operator bitwise &, |, ^, ~, <<, >> untuk manipulasi bit
Memahami dan menyusun tabel kebenaran dua variabel
Mengimplementasikan logika proposisional seperti modus ponens
Membedakan antara operasi logika dan operasi bitwise dalam C++
Ringkasan Teori
1. Operator Logika (Boolean)
Digunakan untuk menggabungkan kondisi logika dalam ekspresi:
&& : dan logika
|| : atau logika
! : negasi
Contoh:
bool hasil = (x > 5) && (x < 10);
2. Operator Bitwise
Digunakan untuk operasi pada representasi biner:
& : AND bitwise
| : OR bitwise
^ : XOR bitwise
~ : NOT bitwise
<< : left shift
>> : right shift
Contoh:
int a = 6; // 0110
int b = 3; // 0011
int c = a & b; // 0010 → hasil = 2
10

11. 3. Tabel Kebenaran
Tabel yang menunjukkan semua kemungkinan kombinasi nilai logika dua variabel dan hasil
operasinya.
ABA&&BA || BA^B
00 0 0 0
010 1 1
10 0 1 1
11 1 1 0
4. Modus Ponens (Logika Proposisional)
Jika P → Q dan P benar, maka Q juga benar.
Contoh dalam kode:
bool p = true;
bool q = false;
if (p && !q) {
cout << "Modus ponens tidak terpenuhi (kontradiksi)" << endl;
}
Aktivitas Praktikum
Latihan 1: Simulasi Tabel Kebenaran Dua Variabel
Deskripsi: Buat program untuk menampilkan semua kemungkinan nilai logika dari dua
variabel dan hasil dari &&, ||, dan ^.
Contoh Kode:
#include <iostream>
using namespace std;
int main() {
cout << "A B | A&&B A||B A^B\n";
for (int a = 0; a <= 1; a++) {
for (int b = 0; b <= 1; b++) {
cout << a << " " << b << " | ";
cout << (a && b) << " ";
cout << (a || b) << " ";
cout << (a ^ b) << endl;
}
}
return 0;
11

12. }
Latihan 2: Implementasi XOR Dua Bilangan
Deskripsi: Buat program yang menerima dua bilangan bulat, lalu mencetak hasil operasi XOR
bitwise.
Contoh Kode:
#include <iostream>
using namespace std;
int main() {
int x, y;
cout << "Masukkan dua bilangan: ";
cin >> x >> y;
int hasil = x ^ y;
cout << x << " XOR " << y << " = " << hasil << endl;
return 0;
}
Latihan 3: Implementasi Modus Ponens
Deskripsi: Implementasikan logika proposisional modus ponens menggunakan if.
Contoh Kode:
#include <iostream>
using namespace std;
int main() {
bool p, q;
cout << "Masukkan nilai P (0 atau 1): ";
cin >> p;
cout << "Masukkan nilai Q (0 atau 1): ";
cin >> q;
if (p) {
if (q)
cout << "Modus ponens terpenuhi: Q benar" << endl;
else
cout << "Kontradiksi! P benar tapi Q salah" << endl;
} else {
cout << "Tidak diketahui apakah Q benar" << endl;
}
return 0;
}
12

13. Tugas Mandiri
1.Buat program untuk menunjukkan operasi bitwise AND, OR, dan NOT pada dua
bilangan bulat.
2.Buat program yang menggunakan operator << dan >> untuk mengalikan dan
membagi bilangan bulat dengan 2.
3.Buat program yang menerima tiga proposisi p, q, dan r, lalu mengevaluasi logika (p
∧ q) → r.
Pertanyaan Refleksi
1.Apa perbedaan mendasar antara operator && dan & dalam C++?
2.Apakah operator ^ memiliki arti yang sama dalam logika dan bitwise? Jelaskan.
3.Bagaimana cara merepresentasikan P → Q dalam bentuk operator logika dasar?
13

14. Modul 3: Aritmetika dan Teori Bilangan
Tujuan Pembelajaran
Setelah menyelesaikan modul ini, peserta diharapkan mampu:
Melakukan operasi dasar bilangan bulat, seperti penjumlahan, pengurangan, perkalian,
pembagian
Memahami dan menerapkan operasi modular dan perpangkatan modular
Mengidentifikasi bilangan prima
Mengimplementasikan algoritma Sieve of Eratosthenes untuk mencari bilangan prima
Memahami paritas (ganjil/genap) dan keterbagian bilangan
Ringkasan Teori
1. Operasi Dasar Bilangan Bulat
Bilangan bulat dapat dikenai operasi aritmatika dasar:
Penjumlahan (+), Pengurangan (-), Perkalian (*), Pembagian (/)
Modulus (%) untuk sisa pembagian
Contoh:
int a = 17, b = 5;
cout << "a / b = " << a / b << endl; // 3
cout << "a % b = " << a % b << endl; // 2
2. Paritas dan Keterbagian
Bilangan ganjil jika n % 2 == 1
Bilangan genap jika n % 2 == 0
Keterbagian: a habis dibagi b jika a % b == 0
3. Bilangan Prima
Bilangan prima adalah bilangan lebih dari 1 yang hanya memiliki dua faktor, yaitu 1 dan
dirinya sendiri.
Contoh bilangan prima: 2, 3, 5, 7, 11, 13, 17, 19, 23, ...
14

15. 4. Operasi Modular
Operasi dilakukan dalam lingkup modulo tertentu.
Contoh:
int a = 7, b = 5;
int mod = 4;
cout << "(a + b) % mod = " << (a + b) % mod << endl; // 0
5. Perpangkatan Modular
Menghitung (a^b) mod m secara efisien, biasanya dengan metode modular exponentiation.
Algoritma cepat: Jika b genap, (a^b) mod m = ((a^(b/2)) mod m)^2 mod m
Jika b ganjil, (a^b) mod m = (a * (a^(b-1)) mod m) mod m
Aktivitas Praktikum
Latihan 1: Program Pengecekan Bilangan Prima
Deskripsi: Buat program untuk mengecek apakah suatu bilangan adalah bilangan prima.
Contoh Kode:
#include <iostream>
using namespace std;
bool isPrima(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
int n;
cout << "Masukkan bilangan: ";
cin >> n;

if (isPrima(n))
cout << n << " adalah bilangan prima." << endl;
else
cout << n << " bukan bilangan prima." << endl;

15

16. return 0;
}
Latihan 2: Implementasi Sieve of Eratosthenes
Deskripsi: Buat program untuk mencetak semua bilangan prima hingga n menggunakan
metode Sieve of Eratosthenes.
Contoh Kode:
#include <iostream>
#include <vector>
using namespace std;
void sieve(int n) {
vector<bool> prima(n+1, true);
prima[0] = prima[1] = false;

for (int p = 2; p * p <= n; p++) {
if (prima[p]) {
for (int i = p * p; i <= n; i += p)
prima[i] = false;
}
}

for (int i = 2; i <= n; i++) {
if (prima[i])
cout << i << " ";
}
cout << endl;
}
int main() {
int n;
cout << "Cetak bilangan prima sampai: ";
cin >> n;
sieve(n);
return 0;
}
Latihan 3: Program Operasi Modular dan Perpangkatan Modular
Deskripsi: Buat program untuk menghitung hasil dari (a^b) mod m menggunakan metode
exponentiation by squaring.
Contoh Kode:
#include <iostream>
16

17. using namespace std;
long long modExponentiation(long long a, long long b, long long m) {
long long hasil = 1;
a = a % m;

while (b > 0) {
if (b % 2 == 1)
hasil = (hasil * a) % m;
b = b / 2;
a = (a * a) % m;
}
return hasil;
}
int main() {
long long a, b, m;
cout << "Masukkan a, b, dan m (untuk menghitung (a^b) mod m): ";
cin >> a >> b >> m;
cout << "(a^b) mod m = " << modExponentiation(a, b, m) << endl;
return 0;
}
Tugas Mandiri
1.Buat program untuk menentukan jumlah bilangan prima antara 1 hingga n.
2.Implementasikan program untuk mengecek apakah suatu bilangan dapat ditulis
sebagai hasil perkalian dua bilangan prima.
3.Buat program untuk menghitung (a * b) mod m tanpa menyebabkan overflow untuk a, b
besar.
Pertanyaan Refleksi
1.Mengapa kita menggunakan i * i <= n dalam pengecekan bilangan prima, bukan i <= n?
2.Apa keuntungan utama menggunakan algoritma Sieve dibandingkan cek prima satu per
satu?
3.Jelaskan secara singkat prinsip perpangkatan modular cepat.
17

18. Modul 4: Aturan Berhitung dan
Kombinatorika
Tujuan Pembelajaran
Setelah menyelesaikan modul ini, peserta diharapkan mampu:
Memahami konsep permutasi dan kombinasi, serta dapat menghitungnya
Memahami dan membangun segitiga Pascal
Memahami prinsip pigeonhole dan prinsip inklusi-eksklusi
Mampu membuat simulasi sederhana terkait probabilitas
Ringkasan Teori
1. Permutasi
Permutasi adalah susunan berurutan dari sejumlah objek.
Rumus permutasi dari n objek yang diambil r:
P(n,r)=
n!
(n−r)!
2. Kombinasi
Kombinasi adalah pemilihan objek tanpa memperhatikan urutan.
Rumus kombinasi dari n objek yang diambil r:
C(n,r)=
n!
r!(n−r)!
3. Segitiga Pascal
Struktur segitiga angka di mana setiap angka adalah jumlah dari dua angka di atasnya. Baris
ke-n berhubungan langsung dengan kombinasi C(n, k).
Contoh awal:
1
18

19. 1 1
1 2 1
1 3 3 1
1 4 6 4 1
4. Prinsip Pigeonhole
Jika n benda dimasukkan ke dalam m kotak, dan n > m, maka pasti ada kotak yang berisi lebih
dari satu benda.
5. Prinsip Inklusi-Eksklusi
Untuk dua himpunan A dan B:
|A∪B|=|A|+|B|−|A∩B|
Untuk tiga himpunan:
|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|
6. Probabilitas Dasar
Peluang kejadian adalah:
P(E)=
jumlahkejadianyangdiharapkan
jumlahseluruhkejadian
Contoh: Peluang mendapatkan angka 6 saat melempar dadu =
1
6
Aktivitas Praktikum
Latihan 1: Program Menghitung Kombinasi dan Permutasi
Deskripsi: Buat program untuk menghitung permutasi dan kombinasi menggunakan fungsi
faktorial.
Contoh Kode:
#include <iostream>
using namespace std;
long long faktorial(int n) {
long long hasil = 1;
for (int i = 1; i <= n; i++) {
19

20. hasil *= i;
}
return hasil;
}
long long permutasi(int n, int r) {
return faktorial(n) / faktorial(n - r);
}
long long kombinasi(int n, int r) {
return faktorial(n) / (faktorial(r) * faktorial(n - r));
}
int main() {
int n, r;
cout << "Masukkan n dan r: ";
cin >> n >> r;

cout << "Permutasi P(n, r) = " << permutasi(n, r) << endl;
cout << "Kombinasi C(n, r) = " << kombinasi(n, r) << endl;

return 0;
}
Latihan 2: Program Menampilkan Segitiga Pascal
Deskripsi: Buat program untuk membentuk segitiga Pascal hingga baris ke-n.
Contoh Kode:
#include <iostream>
using namespace std;
long long kombinasi(int n, int r) {
long long hasil = 1;
if (r > n - r) r = n - r; // optimasi
for (int i = 0; i < r; i++) {
hasil *= (n - i);
hasil /= (i + 1);
}
return hasil;
}
int main() {
int n;
cout << "Masukkan jumlah baris segitiga Pascal: ";
cin >> n;

for (int i = 0; i < n; i++) {
for (int spasi = 0; spasi < n-i-1; spasi++) {
cout << " ";
}
20

21. for (int j = 0; j <= i; j++) {
cout << kombinasi(i, j) << " ";
}
cout << endl;
}
return 0;
}
Latihan 3: Simulasi Probabilitas Sederhana (Melempar Dadu)
Deskripsi: Buat program simulasi melempar dadu 1000 kali dan menghitung frekuensi
munculnya setiap angka.
Contoh Kode:
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
int frekuensi[7] = {0}; // indeks 1-6

srand(time(0)); // seed random

for (int i = 0; i < 1000; i++) {
int lemparan = rand() % 6 + 1;
frekuensi[lemparan]++;
}

for (int i = 1; i <= 6; i++) {
cout << "Angka " << i << " muncul " << frekuensi[i] << " kali." <<
endl;
}

return 0;
}
Tugas Mandiri
1.Modifikasi program segitiga Pascal agar bisa menampilkan segitiga dalam format
piramida rata tengah.
2.Buat program untuk menghitung peluang mendapatkan bilangan genap dalam satu kali
lemparan dadu.
3.Buat program untuk menghitung peluang minimal satu pasangan orang memiliki bulan
lahir yang sama dari 20 orang menggunakan prinsip pigeonhole.
21

22. Pertanyaan Refleksi
1.Apa perbedaan utama antara permutasi dan kombinasi?
2.Bagaimana prinsip pigeonhole digunakan dalam masalah nyata?
3.Jelaskan hubungan antara segitiga Pascal dengan kombinasi C(n, k).
22

23. Modul 5: Rekursi
Tujuan Pembelajaran
Setelah menyelesaikan modul ini, peserta diharapkan mampu:
Memahami konsep dasar rekursi dan bagaimana membentuk fungsi rekursif
Mengimplementasikan pemecahan masalah berbasis rekursi, seperti deret Fibonacci
dan faktorial
Menggunakan rekursi untuk menyelesaikan permasalahan yang memerlukan
eksplorasi banyak kemungkinan (backtracking)
Menyusun solusi untuk masalah pencocokan kata atau subset dengan pendekatan
rekursif
Ringkasan Teori
1. Konsep Rekursi
Rekursi adalah teknik pemrograman di mana fungsi memanggil dirinya sendiri untuk
menyelesaikan submasalah yang lebih kecil.
Struktur dasar fungsi rekursif:
Basis kasus (base case): kondisi akhir yang menghentikan rekursi
Pemanggilan rekursif (recursive call): memanggil fungsi itu sendiri
Contoh umum: Faktorial
n!=n×(n−1)! dengan 0!=1
2. Deret Fibonacci
Deret bilangan di mana:
F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)
3. Backtracking
23

24. Backtracking adalah metode untuk mencari solusi dengan mencoba semua kemungkinan
secara sistematis dan mundur jika suatu kemungkinan tidak valid.
Contoh umum: mencari semua subset dari sebuah array, menyelesaikan puzzle, atau
pencocokan pola.
Aktivitas Praktikum
Latihan 1: Fungsi Rekursif untuk Faktorial
Deskripsi: Menghitung faktorial dari bilangan bulat positif.
Contoh Kode:
#include <iostream>
using namespace std;
int faktorial(int n) {
if (n == 0) return 1;
return n * faktorial(n - 1);
}
int main() {
int n;
cout << "Masukkan bilangan: " ;
cin >> n;
cout << "Faktorial: " << faktorial(n) << endl;
return 0;
}
Latihan 2: Fungsi Rekursif untuk Fibonacci
Deskripsi: Menampilkan bilangan Fibonacci ke-n secara rekursif.
Contoh Kode:
#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
24

25. int main() {
int n;
cout << "Masukkan indeks Fibonacci ke-n: " ;
cin >> n;
cout << "Fibonacci ke-" << n << " adalah: " << fibonacci(n) << endl;
return 0;
}
Latihan 3: Backtracking untuk Pencarian Subset
Deskripsi: Mencetak semua subset dari array menggunakan rekursi dan backtracking.
Contoh Kode:
#include <iostream>
#include <vector>
using namespace std;
void cetakSubset(vector<int>& arr, int index, vector<int>& subset) {
if (index == arr.size()) {
cout << "{ ";
for (int val : subset) cout << val << " ";
cout << "}" << endl;
return;
}
// tidak ambil elemen saat ini
cetakSubset(arr, index + 1, subset);
// ambil elemen saat ini
subset.push_back(arr[index]);
cetakSubset(arr, index + 1, subset);
subset.pop_back(); // backtrack
}
int main() {
vector<int> arr = {1, 2, 3};
vector<int> subset;
cetakSubset(arr, 0, subset);
return 0;
}
Latihan 4: Rekursi untuk Pencocokan Kata (Pattern Matching)
Deskripsi: Mengecek apakah suatu kata dapat dibentuk dari kombinasi huruf-huruf tertentu
secara rekursif.
25

26. Contoh Kode:
#include <iostream>
#include <string>
using namespace std;
bool cocok(string target, string kumpulan, int i = 0) {
if (i == target.length()) return true;
for (int j = 0; j < kumpulan.length(); j++) {
if (target[i] == kumpulan[j]) {
string baru = kumpulan;
baru.erase(j, 1); // hapus huruf yang dipakai
if (cocok(target, baru, i + 1)) return true;
}
}
return false;
}
int main() {
string target = "kode";
string kumpulan = "dekop";

if (cocok(target, kumpulan))
cout << "Bisa disusun" << endl;
else
cout << "Tidak bisa disusun" << endl;
return 0;
}
Tugas Mandiri
1.Buat fungsi rekursif untuk menghitung pangkat a^b.
2.Modifikasi program subset agar hanya mencetak subset dengan jumlah elemen genap.
3.Gunakan backtracking untuk mencari semua solusi dari puzzle labirin 4x4 yang hanya
bisa maju ke kanan atau ke bawah.
Pertanyaan Refleksi
1.Apa yang terjadi jika fungsi rekursif tidak memiliki basis kasus?
2.Mengapa backtracking penting dalam kompetisi algoritma?
3.Apa perbedaan utama antara rekursi dan iterasi?
26

27. Modul 6: Pencarian dan Pengurutan
Tujuan Pembelajaran
Peserta diharapkan mampu:
Memahami perbedaan antara pencarian linear dan biner
Mengimplementasikan algoritma pencarian secara efisien
Menerapkan berbagai metode pengurutan klasik seperti bubble sort, quicksort, dan
heapsort
Menganalisis kompleksitas waktu dari masing-masing algoritma
Ringkasan Teori
1. Pencarian (Searching)
Linear Search: Mencari elemen satu per satu dari awal sampai akhir.
Binary Search: Hanya bekerja pada array yang telah diurutkan; membagi array
menjadi dua dan mencari di bagian yang relevan.
Kompleksitas:
Linear Search: O(n)
Binary Search: O(log n)
2. Pengurutan (Sorting)
Bubble Sort: Tukar elemen bersebelahan jika tidak terurut. Kompleksitas O(n²).
Insertion Sort: Sisipkan elemen ke tempat yang tepat dalam subarray yang sudah
terurut. Kompleksitas O(n²).
Quicksort: Pilih pivot, pisahkan elemen lebih kecil dan lebih besar, lalu sort rekursif.
Kompleksitas rata-rata O(n log n).
Mergesort: Bagi array menjadi dua, sort masing-masing, lalu gabungkan. Kompleksitas
O(n log n).
Heapsort: Gunakan heap (struktur data berbentuk pohon) untuk mengambil elemen
terbesar/kecil satu per satu. Kompleksitas O(n log n).
27

28. Aktivitas Praktikum
Latihan 1: Implementasi Linear Search
#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++)
if (arr[i] == key) return i;
return -1;
}
int main() {
int data[] = {5, 3, 8, 4, 2};
int n = 5, key = 4;
int index = linearSearch(data, n, key);
if (index != -1)
cout << "Ditemukan di indeks: " << index << endl;
else
cout << "Tidak ditemukan" << endl;
return 0;
}
Latihan 2: Implementasi Binary Search
#include <iostream>
#include <algorithm>
using namespace std;
int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1;
}
int main() {
int data[] = {2, 3, 4, 5, 8};
int n = 5, key = 5;
int index = binarySearch(data, n, key);
if (index != -1)
cout << "Ditemukan di indeks: " << index << endl;
else
cout << "Tidak ditemukan" << endl;
return 0;
}
28

29. Latihan 3: Implementasi Bubble Sort
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(arr[j], arr[j+1]);
}
int main() {
int data[] = {5, 1, 4, 2, 8};
int n = 5;
bubbleSort(data, n);
for (int i = 0; i < n; i++) cout << data[i] << " ";
return 0;
}
Latihan 4: Implementasi Quicksort
#include <iostream>
using namespace std;
void quickSort(int arr[], int low, int high) {
if (low >= high) return;
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++)
if (arr[j] < pivot) swap(arr[++i], arr[j]);
swap(arr[i+1], arr[high]);
quickSort(arr, low, i);
quickSort(arr, i+2, high);
}
int main() {
int data[] = {10, 7, 8, 9, 1, 5};
int n = 6;
quickSort(data, 0, n-1);
for (int i = 0; i < n; i++) cout << data[i] << " ";
return 0;
}
Latihan 5: Implementasi Heapsort
#include <iostream>
29

30. using namespace std;
void heapify(int arr[], int n, int i) {
int largest = i; // root
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n/2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n-1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
int data[] = {4, 10, 3, 5, 1};
int n = 5;
heapSort(data, n);
for (int i = 0; i < n; i++) cout << data[i] << " ";
return 0;
}
Tugas Mandiri
1.Bandingkan kinerja bubble sort dan quicksort untuk array besar (≥ 1000 elemen).
2.Implementasikan insertion sort dan bandingkan hasilnya dengan bubble sort.
3.Tambahkan fitur pencarian pada array yang sudah diurutkan hasil dari heapsort.
Pertanyaan Refleksi
1.Mengapa binary search tidak bisa digunakan pada array yang belum terurut?
2.Dalam kondisi apa bubble sort lebih baik daripada quicksort?
3.Mengapa heapsort tidak membutuhkan ruang tambahan seperti mergesort?
30

31. Modul 7: Strategi Pemecahan Masalah
Tujuan Pembelajaran
Peserta diharapkan mampu:
Memahami berbagai paradigma pemecahan masalah: brute force, greedy, divide-and-
conquer, dynamic programming
Menerapkan pendekatan yang tepat untuk menyelesaikan masalah yang diberikan
Menganalisis efisiensi dan batasan dari masing-masing metode
Ringkasan Teori
1. Brute Force
Mencoba semua kemungkinan solusi secara eksplisit. Cocok untuk ukuran input kecil.
Kompleksitas biasanya eksponensial.
2. Greedy
Memilih langkah optimal secara lokal dengan harapan mendapatkan solusi global yang
optimal. Cocok untuk masalah seperti penyusunan uang koin, aktivitas terjadwal, MST, dsb.
3. Divide and Conquer
Memecah masalah menjadi sub-masalah yang lebih kecil, menyelesaikan secara rekursif, lalu
menggabungkannya. Contoh: mergesort, binary search, maximum subarray.
4. Dynamic Programming (DP)
Memecah masalah menjadi sub-masalah yang tumpang tindih dan menyimpan hasilnya
(memoization/tabulasi). Contoh klasik: knapsack, fibonacci, LCS, LIS.
Aktivitas Praktikum
Latihan 1: Brute Force untuk Subset Sum
31

32. #include <iostream>
using namespace std;
bool subsetSum(int arr[], int n, int target) {
int totalSubsets = 1 << n;
for (int i = 0; i < totalSubsets; i++) {
int sum = 0;
for (int j = 0; j < n; j++)
if (i & (1 << j)) sum += arr[j];
if (sum == target) return true;
}
return false;
}
int main() {
int arr[] = {3, 1, 5, 9};
int target = 10;
int n = 4;
cout << (subsetSum(arr, n, target) ? "Ada subset" : "Tidak ada subset")
<< endl;
return 0;
}
Latihan 2: Greedy untuk Penyusunan Koin
#include <iostream>
#include <vector>
using namespace std;
void coinChange(vector<int>& coins, int amount) {
sort(coins.rbegin(), coins.rend());
for (int coin : coins) {
int count = amount / coin;
amount %= coin;
cout << "Koin " << coin << ": " << count << " buah\n";
}
}
int main() {
vector<int> coins = {100, 25, 10, 5, 1};
int amount = 289;
coinChange(coins, amount);
return 0;
}
Catatan: Strategi greedy ini tidak selalu optimal untuk semua set koin.
Latihan 3: Divide and Conquer untuk Mencari Nilai Maksimum
32

33. #include <iostream>
using namespace std;
int findMax(int arr[], int low, int high) {
if (low == high) return arr[low];
int mid = (low + high) / 2;
return max(findMax(arr, low, mid), findMax(arr, mid + 1, high));
}
int main() {
int arr[] = {1, 3, 7, 2, 5, 10, 6};
int n = 7;
cout << "Maksimum: " << findMax(arr, 0, n - 1) << endl;
return 0;
}
Latihan 4: Dynamic Programming - Fibonacci Bottom-Up
#include <iostream>
using namespace std;
int fibonacci(int n) {
int dp[n+1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++)
dp[i] = dp[i -1] + dp[i-2];
return dp[n];
}
int main() {
int n = 10;
cout << "Fibonacci ke-" << n << ": " << fibonacci(n) << endl;
return 0;
}
Latihan 5: Dynamic Programming - Knapsack 0/1
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
for (int i = 1; i <= n; i++)
for (int w = 0; w <= W; w++)
if (wt[i-1] <= w)
dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
else
dp[i][w] = dp[i -1][w];
return dp[n][W];
33

34. }
int main() {
vector<int> val = {60, 100, 120};
vector<int> wt = {10, 20, 30};
int W = 50;
cout << "Nilai maksimum: " << knapsack(W, wt, val, val.size()) << endl;
return 0;
}
Tugas Mandiri
1.Modifikasi program subset sum untuk mencetak semua subset yang menghasilkan
jumlah target.
2.Ubah pendekatan greedy menjadi dynamic programming untuk masalah koin (coin
change dengan jumlah koin minimum).
3.Uji kecepatan antara fibonacci rekursif dan fibonacci bottom-up untuk nilai n = 40.
Pertanyaan Refleksi
1.Dalam kasus apa brute force masih layak digunakan?
2.Apa syarat utama agar pendekatan greedy menghasilkan solusi optimal?
3.Apa kelebihan pendekatan DP dibanding divide-and-conquer biasa?
34

35. Modul 8: Struktur Data
Tujuan Pembelajaran
Peserta diharapkan mampu:
Memahami konsep dan implementasi struktur data dasar hingga menengah.
Menggunakan struktur data secara tepat untuk menyelesaikan masalah
komputasional.
Menulis dan menganalisis kode yang melibatkan array, string, stack, queue, heap,
disjoint set, dan segment/Fenwick tree.
Ringkasan Teori
1. Tipe Data Primitif
Meliputi int, char, bool, float, dan double. Digunakan sebagai dasar dalam membangun
struktur data lain.
2. Array dan String
Array adalah struktur data linear dengan akses indeks langsung.
String di C++ diwakili oleh std::string dengan berbagai fungsi built-in seperti substr(),
find(), dan length().
3. Stack dan Queue
Stack: LIFO (Last In First Out) → digunakan dalam undo operation, DFS, dsb.
Queue: FIFO (First In First Out) → digunakan dalam BFS, antrian proses, dsb.
4. Binary Heap
Struktur pohon biner lengkap, digunakan dalam implementasi priority_queue.
5. Disjoint Set (Union-Find)
Digunakan untuk mengetahui komponen yang saling terhubung. Efisien dengan path
compression dan union by rank.
6. Fenwick Tree / Segment Tree
35

36. Digunakan untuk menangani kueri interval (range query) dan pembaruan titik (point update)
dalam array.
Aktivitas Praktikum
Latihan 1: Array dan String
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
cout << "Masukkan string: ";
cin >> s;
cout << "Panjang string: " << s.length() << endl;
cout << "Kebalikan: ";
for (int i = s.length() - 1; i >= 0; i--)
cout << s[i];
cout << endl;
return 0;
}
Latihan 2: Stack dan Queue
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int main() {
stack<int> s;
queue<int> q;
for (int i = 1; i <= 5; i++) {
s.push(i);
q.push(i);
}
cout << "Stack (LIFO): ";
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << "\nQueue (FIFO): ";
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
return 0;
36

37. }
Latihan 3: Binary Heap (Min Heap)
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(10);
minHeap.push(5);
minHeap.push(8);
while (!minHeap.empty()) {
cout << minHeap. top() << " ";
minHeap.pop();
}
return 0;
}
Latihan 4: Disjoint Set (Union-Find)
#include <iostream>
#include <vector>
using namespace std;
vector<int> parent;
int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]); // path compression
}
void unionSet(int a, int b) {
a = find(a);
b = find(b);
if (a != b) parent[a] = b;
}
int main() {
int n = 5;
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
unionSet(0, 1);
unionSet(1, 2);
cout << (find(0) == find(2) ? "Tersambung\n" : "Tidak tersambung\n" );
cout << (find(3) == find(4) ? "Tersambung\n" : "Tidak tersambung\n" );
return 0;
37

38. }
Latihan 5: Fenwick Tree (Binary Indexed Tree)
#include <iostream>
#include <vector>
using namespace std;
class FenwickTree {
vector<int> bit;
int n;
public:
FenwickTree(int size) : n(size) {
bit.assign(n+1, 0);
}
void update(int idx, int val) {
for (++idx; idx <= n; idx += idx & -idx)
bit[idx] += val;
}
int query(int idx) {
int res = 0;
for (++idx; idx > 0; idx -= idx & -idx)
res += bit[idx];
return res;
}
};
int main() {
FenwickTree ft(10);
ft.update(2, 5);
ft.update(4, 3);
cout << "Jumlah dari indeks 0 sampai 4: " << ft.query(4) << endl;
return 0;
}
Tugas Mandiri
1.Implementasikan fungsi pencocokan substring sederhana (naive string match)
menggunakan std::string.
2.Buatlah simulasi undo/redo menggunakan dua stack.
3.Implementasikan queue menggunakan dua stack.
4.Tambahkan union by rank pada implementasi Disjoint Set.
5.Ubah Fenwick Tree menjadi segment tree untuk operasi maksimum.
Pertanyaan Refleksi
38

39. 1.Dalam kasus apa kita menggunakan stack dibanding queue?
2.Apa perbedaan utama antara segment tree dan Fenwick tree?
3.Bagaimana kita mengetahui bahwa sebuah struktur data cocok digunakan dalam
sebuah kasus?
39

40. Modul 9: Graf dan Tree
Tujuan Pembelajaran
Peserta diharapkan mampu:
Memahami konsep dasar tree dan graf dalam teori dan implementasinya.
Menerapkan teknik traversal graf (BFS dan DFS).
Menggunakan algoritma shortest path dan minimum spanning tree dalam penyelesaian
masalah graf.
Ringkasan Teori
1. Tree
Tree adalah graf terhubung tanpa siklus.
Rooted Tree memiliki satu node sebagai akar dan struktur arah dari atas ke bawah.
Sering digunakan dalam struktur data seperti trie, binary tree, dsb.
2. Graf
Terdiri dari simpul (node) dan sisi (edge).
Bisa berarah atau tak berarah, berbobot atau tak berbobot.
Representasi: adjacency list, adjacency matrix, dan edge list.
3. Penjelajahan Graf
DFS (Depth-First Search): menyelam ke kedalaman simpul dahulu.
BFS (Breadth-First Search): menjelajah level per level.
4. Shortest Path
Dijkstra: untuk graf berbobot non-negatif.
Bellman-Ford: untuk graf berbobot negatif.
Floyd-Warshall: untuk all-pairs shortest path.
5. Minimum Spanning Tree (MST)
Kruskal: berdasarkan urutan sisi berbobot minimum.
40

41. Prim (Jarnik): dimulai dari satu simpul, menambah sisi minimum ke node yang belum
dikunjungi.
Aktivitas Praktikum
Latihan 1: Representasi Graf (Adjacency List)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 5;
vector<vector<int>> adj(n);
adj[0] = {1, 2};
adj[1] = {0, 3};
adj[2] = {0, 4};
adj[3] = {1};
adj[4] = {2};
for (int i = 0; i < n; i++) {
cout << "Node " << i << ": ";
for (int v : adj[i]) cout << v << " ";
cout << endl;
}
return 0;
}
Latihan 2: DFS dan BFS
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> adj;
vector<bool> visited;
void dfs(int node) {
visited[node] = true;
cout << node << " ";
for (int neighbor : adj[node])
if (!visited[neighbor])
dfs(neighbor);
}
void bfs(int start) {
queue<int> q;
41

42. q.push(start);
visited[start] = true;
while (!q.empty()) {
int node = q.front(); q.pop();
cout << node << " ";
for (int neighbor : adj[node])
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
int main() {
int n = 5;
adj.resize(n);
visited.assign(n, false);
adj[0] = {1, 2};
adj[1] = {0, 3};
adj[2] = {0, 4};
adj[3] = {1};
adj[4] = {2};
cout << "DFS: ";
dfs(0);
cout << "\nBFS: ";
visited.assign(n, false);
bfs(0);
return 0;
}
Latihan 3: Dijkstra
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
void dijkstra(int start, vector<vector<pii>>& adj, vector< int>& dist) {
priority_queue<pii, vector<pii>, greater<>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
42

43. pq.push({dist[v], v});
}
}
}
}
int main() {
int n = 5;
vector<vector<pii>> adj(n);
adj[0] = {{1, 10}, {2, 5}};
adj[1] = {{3, 1}};
adj[2] = {{1, 3}, {3, 8}, {4, 2}};
adj[3] = {{4, 4}};
adj[4] = {{3, 6}};
vector<int> dist(n, 1e9);
dijkstra(0, adj, dist);
for (int i = 0; i < n; i++)
cout << "Jarak dari 0 ke " << i << ": " << dist[i] << endl;
return 0;
}
Latihan 4: Kruskal (Minimum Spanning Tree)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
int u, v, w;
bool operator<(Edge const& other) { return w < other.w; }
};
vector<int> parent;
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
parent[a] = b;
return true;
}
int main() {
int n = 5;
vector<Edge> edges = {
{0, 1, 10}, {0, 2, 6}, {0, 3, 5},
{1, 3, 15}, {2, 3, 4}
43

44. };
parent.resize(n);
for (int i = 0; i < n; ++i) parent[i] = i;
sort(edges.begin(), edges.end());
int total = 0;
for (Edge e : edges) {
if (unite(e.u, e.v)) {
total += e.w;
cout << e.u << " - " << e.v << " : " << e.w << endl;
}
}
cout << "Total bobot MST: " << total << endl;
return 0;
}
Tugas Mandiri
1.Modifikasi program BFS untuk mencetak level masing-masing simpul.
2.Implementasikan Floyd-Warshall untuk all-pairs shortest path.
3.Terapkan Prim’s algorithm menggunakan priority queue.
4.Tambahkan deteksi siklus pada graf tak berarah menggunakan DFS.
5.Kembangkan program DFS untuk menghitung jumlah komponen terhubung.
Pertanyaan Refleksi
1.Dalam situasi apa kita menggunakan BFS daripada DFS?
2.Apa keunggulan Dijkstra dibanding Bellman-Ford?
3.Mengapa pada MST kita tidak boleh membentuk siklus?
44

45. 45