Midnight Maranatha Infinite Discoveries at Night
[[index	Home]]/Semester 4/Strategi Algoritmik

Pertemuan 9 - Struktur Data Pohon - Branch & Bound (B&B)

Unduh Spreadsheet:
TSP-BB.xlsx

Pertemuan 9

7 Mei 2026

Informasi

Masuk lagi 28 Mei 2026 (2 minggu kedepan tidak ada kelas)
Tugas besar akan diumumkan jika sudah ada

Struktur Data Pohon - Branch & Bound (B&B)

Contoh Bound: (1, 4, 2, no solution)

	Q1	Q2	Q3	Q4
x1	Q
x2				Q
x3	x	Q	x	x
x4	x	x	x	x

Solution tersebut belum main cost

Dengan cost

Matrix:

Link to original

Pertemuan 10 - Backtracking

Unduh spreadhseet:
Backtrack2021-rev.xlsx

Transclude of pertemuan-10

Pertemuan 11 - String Matching + Tugas Besar

String Matching

Pertemuan 11 - Strategi Algoritmik

String Matching

View PDF: Strago_StringMatching_2022.pdf

Definisi:

• Teks T —> n karaketer
• Pola/Pattern (P) -> m karakter

Intinya

Kita mencari Pola (P) pada Teks (T)

Contoh:

• T: “the rain in spain stays mainly on the plain”
• P: “main”

Konsep String

String S:

a	n	d	r	e	w
0	1	2	3	4	5
Substring: S[i…j] (dari indeks i sampai j)
Prefix: S[0…i] (dari indeks 0 sampai i)
Suffix: S[i…m-1] (dari indeks i sampai akhir)

Algoritma yang digunakan

Untuk melakukan string matching

1. Algoritma Brute Force

Geser satu indeks, lalu coba cocokan, geser lagi jika belum cocok sampai akhir

Kasus terburuk dari algoritma Brute Force: O(mn), algoritma Brute Force berjalan cepat jika jumlah karakter uniknya besar (banyak karakter yang unik)

Jika jumlah karakter uniknya kecil, malah memperlambat algoritma Brute Force, karena bisa saja pencocokan sampai indeks akhir baru salah, ini memperlambat!!

Contoh worst case:

• T: aaaaaaaaaaah
• P: aaah

Setiap kali iterasi, maka algoritma akan memerika aaa, lalu h tidak match, ini memperlambat!

2. Algoritma Boyer-Moore

Berdasarkan 2 teknik:

• looking-glass
• character-jump

Langkah-langkah
0. Membuat tabel Last Occurence (tabel yang berisi indeks terakhir dari masing-masing karakter unik T pada P)

1. Lakukan matching dengan indeks terakhir P sampai awal, juga mundur pada T

Kasus 1: x pada T lebih kiri di P
Kasus 2: x pada T lebih kanan di P
Kasus 3: x pada T tidak ada di P

Booyer-Moore worst case running time: O(nm + A)
Berjalan lambat jika A (jumlah karakter unik) kecil, tetapi cepat jika A besar

3. Algoritma KMP (Knuth-Morris-Pratt)

Mulainya dari ke 0, berbeda dengan BM yang dari belakang

KMP akan menggunakan prefix dan suffix

Berbeda dengan BM, KMP menjadi $j_{\text{new}}$, sedangkan BM mencari $i_{\text{new}}$

Lalu, karena yang terpanjang sama adalah 2 karakter, maka $j_{\text{new}}$ = 2

Insight

Jika salah/mismatch di j = 0, maka geser 1 saja

Contoh:

Dengan:

KMP memiliki kompleksitas O(m+n) —> sangat cepat

KMP bekerja kurang baik jika A (jumlah karakter unik) meningkat, karena ketidakcocokan akan meningkat, KMP berjalan cepat jika mismatch terjadi di akhir P (pola)

Link to original

Informasi Tugas Besar

Informasi Tugas Besar - Strategi Algoritmik

Tugas Besar untuk implementasi Strategi Algoritma dalam suatu persoalan.
Tugas berkelompok, maksimal 3 orang.

Submisi Tugas Besar :

• Aplikasi
• Laporan
• Presentasi Tugas Besar

Laporan Tugas Besar terdiri dari

1. Deskripsi Persoalan
2. Deskripsi Solusi
3. Deskripsi hasil pengujian (tampilan input/output)
4. Lampiran kode sumber

---

Kelompok Tugas Besar:

Kelompok	Nama
Kelompok 1	Kevin Kornelius Martadinata Henry Ferdynand Budiana
Kelompok 2	Ferdi Gunawan Yoel Kristianto Allegra Rochintaniawan Al-Nazhari
Kelompok 3	Youlanda Nelva Haezer Naufal Eka Fadhlurohman Maliq Athaya Rinaldi
Kelompok 4	Errvin Junius Rafael Adiputra Febrian Timotius Sugianto
Kelompok 5	Me Gavin Malik Setiawan Miracle Steven Gerrald
Kelompok 6	Juan Alexander Valentino Hose Hans Maulana Budiputra
Kelompok 7	Bryan Christian Miercoles Gearald Christoffer Freederich Marco Octavian
Kelompok 8	Dave Andrew Effrain David Martoyo

---

Topik dan Ketentuan tugas Besar

Bahasa Pemrograman Bebas

Progress Report:

• Apa yang sudah dikerjakan
• Apa yang akan dikerjakan

Submisi tugas besar:

• Laporan
• Presentasi Aplikasi Tugas Besar (Minggu ke-15)

Laporan Tugas Besar terdiri dari

• Deskripsi Persoalan
• Deskripsi hasil pengujian aplikasi (tampilan input/output)
• Lampiran kode sumber

Topik kita: Topik B (Knapsack)

---

Our Draft

Draft Plan Tugas Besar kita:

1. Konsep Aplikasi

   • Berbasis Static Website (HTML, CSS, JavaScript). No server/database, biar praktis.
   • Fitur wajib: Input data barang (n >= 8), kapasitas W, proses Backtracking (DFS) + Pruning, output tabel barang, solusi optimal, serta statistik (jumlah node & waktu eksekusi).

2. Strategi & Fokus Utama

   • Fokus utama kita ada di LAPORAN. Kita bakal lakukan testing massal dengan banyak skenario data.
   • Menampilkan banyak grafik analisis di dalam laporan (misal: grafik jumlah barang vs jumlah node, waktu eksekusi dengan vs tanpa pruning, dll).

3. Garis Besar Langkah Kerja

   • Tahap 1: Bikin core algoritma backtracking & fungsi pruning di JS.
   • Tahap 2: Bikin UI input/output sederhana menggunakan HTML & CSS.
   • Tahap 3: Running test sebanyak-banyaknya untuk ambil data statistiknya.
   • Tahap 4: Susun Laporan (Deskripsi persoalan, deskripsi solusi, grafik hasil pengujian, screenshot UI, dan lampiran kode).

Rincian detail timeline dan pembagian tugasnya bisa kita obrolin bareng-bareng nanti pas kumpul. Sila beri masukan ya!

Link to original

Henry2

String_Matching Explanation

Material Source

IN244-Strategi Algoritmik > P12-String Matching > Slides teori
Powerpoint slides will not be included here to prevent redundancy

Warning! This file can not be exported effectively by default.

If still needed to be exported:

• Lower the downscale percent is required for the contents to be universally exists
• Plugin Fast Text Color is used [obsidian://show-plugin?id=fast-text-color] There will be no color text (Obsidian community plugin) to guide the step-by-step algorithm.
  • Had been fixed by using another plugin
    obsidian://show-plugin?id=colored-text

Boyer-Moore Algorithm

The Boyer-Moore Algorithm: Core Heuristics and Case Analysis

The Boyer-Moore algorithm relies fundamentally on two core techniques to optimize pattern matching. The first is the looking-glass technique, which dictates searching for the pattern P within the text T by moving backward, starting the character comparison from the last character in P. The second is the character-jump technique, which triggers a calculated shift whenever a mismatch occurs at the condition where T[i] equals P[j] evaluates to false. Depending on the nature of the mismatched character in the text, the algorithm determines its next move based on three distinct possible cases.

The Three Shift Cases in Boyer-Moore, in-depth theoretical explanation

Case 1: The Mismatched Character Exists in the Pattern

Please note that the string tracking starts from the last

Rule: If the pattern P contains the mismatched character from the text (denoted as x), the pattern P is shifted to the right. The structural goal of this shift is to perfectly align the occurrence of the character x within the pattern P with the mismatched character T[i] located in the text.

Example: If the text T is currently evaluating “xa” and the pattern P is “xcba”. First iteration, T[i] = P[j] is correct because both is “a”. Then a mismatch occurs at the character ‘x’. The algorithm immediately shifts the indices i and j to the right so that the ‘x’ in “xcba” aligns directly with the ‘x’ in the text.

Case 2: The Mismatched Character Exists, but Case 1 is Impossible

Rule: If the pattern P contains the character x, but executing the alignment shift described in Case 1 is not possible (because it would result in moving the pattern backward), the algorithm simply shifts the pattern P to the right by exactly one character, aligning it at T[i+1].

Example: Consider a text T containing “xax” and a pattern P of “cwax”. A mismatch happens, and while ‘x’ is present in the pattern, it is positioned after the current index position j. Therefore, the algorithm shifts the pattern one position to the right to generate a new j position and resume comparison.

Case 3: The Mismatched Character is NOT in the Pattern

Rule: If neither Case 1 nor Case 2 applies because the mismatched character x does not exist within the pattern P at all, the pattern P is shifted significantly to place P[0] in alignment with T[i+1].

Example: If the text T evaluates “xa” against a pattern P of “dcba”, there is no ‘x’ present in the pattern. Consequently, the algorithm slides the pattern entirely, shifting the i and j indices completely past the mismatched ‘x’ to establish a new j position.

Visualizing the Last Occurrence Function

To execute these character jumps efficiently during the search process, the Boyer-Moore algorithm performs preprocessing on both the pattern P and the target alphabet A to construct a last occurrence function, represented as L().

• The L() function maps every letter found in the alphabet A into an integer value.

• Specifically, L(x) is defined as the largest index i such that P[i] equals x, or it returns -1 if the character x does not appear in the pattern P at all.

• In this context, x represents any letter within the defined alphabet A.

Based on an example where the pattern P is “abacab” and the alphabet A consists of {a, b, c, d}, here is the step-by-step visualization of the mapped L() table:

Character (x)	a	b	c	d
Last Occurrence $L(x)$	4	5	3	-1

Note: The values in the table are derived directly from the largest 0-based index position of each respective character within the string “abacab”.

---

Example

Boyer Moore Algorithm

• String T (Text):
  “a pattern matching algorithm”
• String P (Searching):
  “rithm”

Core Concept: Heuristic Search

The Boyer-Moore algorithm searches for a pattern P within a text T by moving backward through the pattern (Looking-Glass Technique). When a mismatch occurs, it calculates a strategic leap to bypass multiple invalid alignments simultaneously (Character-Jump Technique).

T (Text) = “a pattern matching algorithm” (Length: 28)
P (Pattern) = “rithm” (Length: 5)

Preprocessing: Last Occurrence Function $L(x)$

The Last Occurrence Table

Before searching, the algorithm maps every character in the pattern to its rightmost index. If a character is not in the pattern, its value defaults to -1[.

Character ($x$)	r	i	t	h	m	All others (a, p, e, n, space, etc.)
$L(x)$	0	1	2	3	4	-1

---

Step 1: First Alignment

Looking-Glass Technique

The character comparison strictly begins from the last character in the pattern P.

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
T	a		p	a	t	t	e	r	n		m	a	t	c	h	i	n	g		a	l	g	o	r	i	t	h	m
P	r	i	t	h	m
P[j]	0	1	2	3	4

• Rationale: We compare $P[4]$ (‘m’) with $T[4]$ (‘t’). They mismatch.
• The mismatched text character is $x$ = ‘t’.
• Case Occurred = Case 1: The character ‘t’ exists in the pattern P at index 2 ($L(\text{’t’})=2$)
• Action: Shift P to the right to align the occurrence of ‘t’ in P with the mismatched ‘t’ in the text.
• Shift Amount: $j-L(x)=4-2=2$. Move P to the right 2 times.

---

Step 2

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
T	a		p	a	t	t	e	r	n		m	a	t	c	h	i	n	g		a	l	g	o	r	i	t	h	m
P			r	i	t	h	m
P[j]			0	1	2	3	4

• Rationale: Compare $P[4]$ (‘m’) with $T[6]$ (‘e’). Mismatch.
• The mismatched text character is $x$ = ‘e’.
• Case Occurred = Case 3: The character ‘e’ does NOT exist anywhere in the pattern P ($L(\text{’e’})=-1$).
• Action: Shift the entire pattern completely past the mismatch to align $P[0]$ with $T[i+1]$ (which is index 7).
• Shift Amount: $j-L(x)=4-(-1)=5$. Move P to the right 5 times.

---

Step 3

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
T	a		p	a	t	t	e	r	n		m	a	t	c	h	i	n	g		a	l	g	o	r	i	t	h	m
P								r	i	t	h	m
P[j]								0	1	2	3	4

• Rationale: Compare $P[4]$ (‘m’) with $T[11]$ (‘a’). Mismatch.
• The mismatched text character is $x$ = ‘a’.
• Case Occurred = Case 3: The character ‘a’ does NOT exist in P ($L(\text{’a’})=-1$).
• Action: Shift P completely past ‘a’ to align $P[0]$ with index 12.
• Shift Amount: 5. Move P to the right 5 times.

---

Step 4

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
T	a		p	a	t	t	e	r	n		m	a	t	c	h	i	n	g		a	l	g	o	r	i	t	h	m
P													r	i	t	h	m
P[j]													0	1	2	3	4

• Rationale: Compare $P[4]$ (‘m’) with $T[16]$ (‘n’). Mismatch.
• The mismatched text character is $x$ = ‘n’.
• Case Occurred = Case 3: The character ‘n’ does NOT exist in P.
• Action: Shift P completely past ‘n’ to align $P[0]$ with index 17.
• Shift Amount: 5. Move P to the right 5 times.

---

Step 5

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
T	a		p	a	t	t	e	r	n		m	a	t	c	h	i	n	g		a	l	g	o	r	i	t	h	m
P																		r	i	t	h	m
P[j]																		0	1	2	3	4

• Rationale: Compare $P[4]$ (‘m’) with $T[21]$ (‘g’). Mismatch.
• The mismatched text character is $x$ = ‘g’.
• Case Occurred = Case 3: The character ‘g’ does NOT exist in P.
• Action: Shift P completely past ‘g’ to align $P[0]$ with index 22.
• Shift Amount: 5. Move P to the right 5 times.

---

Step 6

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
T	a		p	a	t	t	e	r	n		m	a	t	c	h	i	n	g		a	l	g	o	r	i	t	h	m
P																							r	i	t	h	m
P[j]																							0	1	2	3	4

• Rationale: Compare $P[4]$ (‘m’) with $T[26]$ (‘h’). Mismatch.
• The mismatched text character is $x$ = ‘h’.
• Case Occurred = Case 1: The character ‘h’ exists in the pattern P at index 3 ($L(\text{’h’})=3$).
• Action: Shift P to the right to align $P[3]$ (‘h’) with $T[26]$.
• Shift Amount: $j-L(x)=4-3=1$. Move P to the right 1 time.

---

Step 7 - Last (String Found)

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
T	a		p	a	t	t	e	r	n		m	a	t	c	h	i	n	g		a	l	g	o	r	i	t	h	m
P																								r	i	t	h	m
P[j]																								0	1	2	3	4

Iteration Process (Right to Left):

• Check $P[4]$ (‘m’) == $T[27]$ (‘m’) $\to$ Match! Move left.
• Check $P[3]$ (‘h’) == $T[26]$ (‘h’) $\to$ Match! Move left.
• Check $P[2]$ (‘t’) == $T[25]$ (‘t’) $\to$ Match! Move left.
• Check $P[1]$ (‘i’) == $T[24]$ (‘i’) $\to$ Match! Move left.
• Check $P[0]$ (‘r’) == $T[23]$ (‘r’) $\to$ Match!

Finalize

The entire pattern has been checked and matched successfully.
Thus, it is concluded that String P = “rithm” exists in T = “a pattern matching algorithm” at indices 23 to 27.

---

KMP (Knuth-Morris-Pratt) Algorithm

The Knuth-Morris-Pratt (KMP) Algorithm: Core Philosophy and Strategy

The Knuth-Morris-Pratt (KMP) algorithm searches for a pattern $P$ within a text $T$ in a progressive, left-to-right order. Unlike the naive brute-force method, KMP shifts the pattern much more intelligently when a mismatch occurs. By precomputing a failure function from the pattern itself, the algorithm knows exactly how far to slide the pattern ahead, completely eliminating the need to backtrack through characters in the text that have already been evaluated.

The Three Operational Cases in KMP String Matching

During the search phase, the algorithm maintains a text index $i$ and a pattern index $j$. At each step, it evaluates the relationship between the current characters and chooses its next action based on three distinct logic cases:

Case 1: The Characters Match ($P[j]==T[i]$)

• Rule: If the character in the pattern matches the current character in the text, the algorithm advances forward. If the matched character is the last character of the pattern ($j==m-1$), the pattern has been fully located within the text. Otherwise, both pointers are incremented by 1 to check the next sequential alignment.

Example: If you are matching the pattern “abacab” against a text, and the first three characters “aba” successfully match, both index pointers $i$ and $j$ increment continuously together to verify the fourth character.

Case 2: Character Mismatch with a Partial Match History ($P[j]\ne T[i]$ and $j>0$)

• Rule: If a mismatch occurs but some characters have already been successfully matched (indicated by $j>0$), the algorithm does not reset back to the beginning of the pattern. Instead, it references the precomputed failure function to update the pattern pointer to $j=F(j-1)$. This shifts the pattern to the right by aligning the largest proper prefix of the matched substring that is also a valid suffix of that substring.

Example: Consider searching for the pattern $P=$ “abaaba” inside the text $T=$ “abaabx”. A mismatch happens at index $j=5$ because $P[5]=\text{’a’}$ does not match $T[5]=\text{’x’}$. Because $j>0$, the algorithm computes the longest prefix of “abaab” that is also a suffix of “baab”, which is “ab” (length of 2). It shifts the pattern by 3 spaces, automatically safety-skipping redundant checks and seamlessly resuming the comparison at len("abaab") - len("ab) = $j_{\text{new}}=5-2=2$.

Case 3: Character Mismatch at the Absolute Start of the Pattern ($P[j]\ne T[i]$ and $j==0$)

• Rule: If a mismatch occurs immediately on the very first character of the pattern ($j==0$), it means there is no historical matching prefix to build upon. The pattern cannot shift backwards any further. Therefore, the pattern stays fixed relative to its starting alignment, and the text pointer is incremented by 1 ($i=i+1$) to evaluate the next character position in the text.

Example: If your text begins with the character ‘c’ and your search pattern is “abacab”, a mismatch occurs immediately at the first step ($j=0$). Since no partial match exists, the algorithm slides the pattern past ‘c’ by incrementing the text index $i$ to check the next position.

Preprocessing: Visualizing the KMP Failure Function Table

To run seamlessly without physical text backtracking, the KMP algorithm maps out the pattern’s self-similar structures before running the main text search. This is formally saved as the failure function, $F(k)$, which records the size of the largest prefix of $P[\mathrm{0..}k]$ that is also a suffix of $P[\mathrm{1..}k]$.

Note

Failure Function $F(k)$ can also be generally referred online as Longest Proper Prefix (LPS)

Based on the example provided for the pattern $P=$ “abacab”, here is the precomputed step-by-step failure function table:

Index (k)	0	1	2	3	4
Pattern Character $P[k]$	a	b	a	c	a
Failure Function $F(k)$	0	0	1	0	1

Note: For instance, $F(4)=1$ because for the substring $P[\mathrm{0..4}]=$ “abaca”, the longest proper prefix that is also a matching suffix is simply “a”, which yields a length of 1.

---

Brief Example

KMP algorithm
T = “abaabx”
P = “abaaba”

Solution

0	1	2	3	4	5	6	7	8
a	b	a	a	b	x
a	b	a	a	b	a
			a	b	a	a	b	a
No need to repeat ab in abaaba, continue comparing abaaba

Find largest prefix (start) of:
”a b a a b” (P[0..j-1])
That is the suffix (end) of:
“b a a b” (P[1..j-1])

Failure Function

Defined as F(k) which is the size of the largest prefix P[0,,k] that is the suffix of P[1..k]

| Index |0|1|2|3|4|5|
|---|---|---|---|---|---|
| String |a|b|a|a|b|a|
|F(k)|0|||||
Nothing repeated, continue

| Index |0|1|2|3|4|5|
|---|---|---|---|---|---|
| String |a|b|a|a|b|a|
|F(k)|0|0||||
Nothing repeated, continue

| Index |0|1|2|3|4|5|
|---|---|---|---|---|---|
| String |a|b|a|a|b|
|F(k)|0|0|1|||
String “a” is repeated. F(k) = 1

| Index |0|1|2|3|4|5|
|---|---|---|---|---|---|
| String |a|b|a|a|b|
|F(k)|0|0|1|1||
String “a” is repeated. F(k) = 1

| Index |0|1|2|3|4|5|
|---|---|---|---|---|---|
| String |a|b|a|a|b|
|F(k)|0|0|1|1|2|
String “ab” is repeated. F(k) = 2

---

Full Example: KMP Algorithm

Core Concept: Failure Function

The Knuth-Morris-Pratt (KMP) algorithm searches for a pattern $P$ within a text $T$ in a progressive, left-to-right order. The Failure Function $F(k)$ is precomputed strictly from the pattern itself, completely eliminating the need to backtrack through evaluated characters.

T = “abacaabaccabacabaabb”
P = “abacab”

Preprocessing: Failure Function $F(k)$

Longest Prefix Suffix (LPS)

$F(k)$ records the size of the largest proper prefix of $P[\mathrm{0..}k]$ that is also a suffix.
Note: $F(4)=1$ because for the substring $P[\mathrm{0..4}]$ (“abaca”), the longest proper prefix that is also a matching suffix is simply “a”.

Index ($k$)	0	1	2	3	4	5
Pattern $P[k]$	a	b	a	c	a	b
$F(k)$	0	0	1	0	1	2

---

Step 1: First Mismatch

Initial Phase

During the search phase, the algorithm maintains a text index i and a pattern index j. If the character in the pattern matches the current character in the text, the algorithm advances forward.

If first value matches, increment i and j by one.

if matched:
	i += 1
	j += 1

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
T	a	b	a	c	a	a	b	a	c	c	a	b	a	c	a	b	a	a	b	b
P	a	b	a	c	a	b
P[j]	0	1	2	3	4	5

When it is a mismatch and j != 0:

Rule: Mismatch with Partial History

The algorithm references the precomputed failure function to update the pattern pointer to $j=F(j-1)$.

if not matched:
	if j != 0:
		j = F(k) # This will be executed
	else:
		i += 1 

Reminder:
k = j - 1
k = 5 - 1 = 4
F(4) = 1

So, the new pattern index j will be 1. The pattern shifts to align P[1] with T[5].

---

Step 2: Evaluating Shifted Alignment

i	…	4	5	6	7	8	9	10	11	…
T	…	a	a	b	a	c	c	a	b	…
P		a	b	a	c	a	b
P[j]		0	1	2	3	4	5

There is another mismatch spot at T[5] = 'a' and P[1] = 'b'.

if not matched:
	if j != 0:
		j = F(k) # Executed

k = 1 - 1 = 0
F(0) = 0

So the new pattern index j becomes 0. Align P[0] with T[5].

---

Step 3: Match Continued until Next Mismatch

Match successfully continues from T[5] and P[0].

i	…	5	6	7	8	9	10	11	12	…
T	…	a	b	a	c	c	a	b	a	…
P		a	b	a	c	a	b
P[j]		0	1	2	3	4	5

Mismatch occurs at T[9] = 'c' and P[4] = 'a'.

if not matched:
	if j != 0:
		j = F(k) # Executed

k = 4 - 1 = 3
F(3) = 0
New j = 0.

---

Step 4: Instant Mismatch

Rule: Absolute Start Mismatch

If a mismatch occurs immediately on the very first character of the pattern ($j==0$), there is no historical matching prefix. The pattern stays fixed, and the text pointer is incremented by 1 ($i=i+1$).

i	…	8	9	10	11	12	13	14	15	…
T	…	c	c	a	b	a	c	a	b	…
P			a	b	a	c	a	b
P[j]			0	1	2	3	4	5

String mismatches instantly (j == 0).

if not matched:
	if j != 0:
		j = F(k)
	else:
		i += 1 # This will be executed

Increment T[i] by 1. Text pointer i becomes 10.

---

Step 5: Solution Found!

i	…	10	11	12	13	14	15	16	17	18	19
T	…	a	b	a	c	a	b	a	a	b	b
P		a	b	a	c	a	b
P[j]		0	1	2	3	4	5

Strings Matched!

Match Complete

If the matched character is the last character of the pattern ($j==m-1$), the pattern has been fully located within the text[.

---

Continued - Step 6

In case we want to continue the String Matching to find other occurrences.
Treat it as if a mismatch happened to safely slide it forward:

j = 5 (matched completely)
k = 5
j = F(5) = 2

i	…	14	15	16	17	18	19
T	…	a	b	a	a	b	b
P				a	c	a	b
P[j]				0	1	2	3

• Match at T[16] and P[0].
• Mismatch at T[17] and P[1].
• Algorithm safely bounds its way to the end of the string.

At this point, index i reached its end. Stop the program.

if i >= 19:
	return

Link to original

Pertemuan 12 - Program Dinamis

Pertemuan 12 - Strategi Algoritmik

Program Dinamis

Memiliki lebih banyak keputusan, tidak seperti algoritma Greedy yang hanya memiliki 1 keputusan dan belum tentu optimal

Mundur:

Tahap 4

s	f4(s) (total cost)	X4 (nyampe ke)
8	3	10
9	4	10
Tahap 3

s	8	9	f3(s) (min cost)	X3 (nyampe ke)
5	1+3 = 4	4+4 = 8	4	8
6	9	7	7	9
7	6	7	6	8
Tahap 2

s	5	6	7	f2(s) (min cost)	X2 (nyampe ke)
2	7+4 = 11	4+7 = 11	12	11	5 atau 6
3	3+4 = 7	9	10	7	5
4	8	8	11	8	5 atau 6
Tahap 1

s	2	3	4	f1(s)	X1
1	2+11 = 13	11	11	11	3 atau 4

Maju

Contoh untuk Knapsack 0/1

Tahap 1 - Item 1 (Weight = 2, Profit = 65)

y	f0(y)	65 + f0(y-2)	f1(y)	(x1, x2, x3)
0	0	$-\infty$	0	(0,0,0)
1	0	$-\infty$	0	(0,0,0)
2	0	65 + 0	65	(1,0,0)
3	0	65 + 0	65	(1,0,0)
4	0	65 + 0	65	(1,0,0)
5	0	65 + 0	65	(1,0,0)
Tahap 2 - Item 2 (Weight = 3, Profit = 80)

y	f1(y)	80 + f1(y-3)	f2(y)	(x1, x2, x3)
0	0	$-\infty$	0	(0,0,0)
1	0	$-\infty$	0	(0,0,0)
2	65	$-\infty$	65	(1,0,0)
3	65	80	80	(0,1,0)
4	65	80	80	(0,1,0)
5	65	80+65 = 145	145	(1,1,0)
Tahap 3 - Item 3 (Weight = 1, Profit = 30)

y	f2(y)	30 + f2(y-3)	f3(y)	(x1, x2, x3)
0	0	$-\infty$	0	(0,0,0)
1	0	30+0	30	(0,0,1)
2	65	30+0	65	(1,0,0)
3	80	30+65	95	(1,0,1)
4	80	30+80	110	(0,1,1)
5	145	30+80	145	(1,1,0)

Link to original

Prepare Kuis Strategi Algoritmik

Prepare Kuis Strategi Algoritmik

Referensi soal:

Materi 1: Program Dinamis

Daftar Item:

N	Weight	Profit
1	2	15
2	3	12
3	2	8
4	2	10
Kapasitas Knapsack W = 6

Item 1 - Weight = 2, Profit = 15

y	f0(y)	15 + f0(y-2)	f1(y)	(x1, x2, x3, x4)
0	0	$-\infty$	0	(0,0,0,0)
1	0	$-\infty$	0	(0,0,0,0)
2	0	15	15	(1,0,0,0)
3	0	15	15	(1,0,0,0)
4	0	15	15	(1,0,0,0)
5	0	15	15	(1,0,0,0)
6	0	15	15	(1,0,0,0)
Item 2 - Weight = 3, Profit = 12

y	f1(y)	15 + f0(y-3)	f2(y)	(x1, x2, x3, x4)
0	0	$-\infty$	0	(0,0,0,0)
1	0	$-\infty$	0	(0,0,0,0)
2	15	$-\infty$	15	(1,0,0,0)
3	15	12	15	(1,0,0,0)
4	15	12	15	(1,0,0,0)
5	15	12 + 15	27	(1,1,0,0)
6	15	12 + 15	27	(1,1,0,0)
dst…

Materi 2: Algoritma Backtracking

a. gambarkan graf dari peta di atas

b. Gunakan algoritma backtracking, m=4

---
config:
  theme: redux
---
flowchart TB
    A(("1")) -- "x1 = 1" --> B(("2"))
    B -- "x2 = 1" --> C(("3"))
    B -- "x2 = 2" --> D(("4"))
    C --> n1["B"]
    D -- "x3 = 1" --> n2(("5"))
    n2 --> n3["B"]
    D -- "x3 = 2" --> n4(("6"))
    n4 -- "x4 = 1" --> n5(("7"))
    n4 -- "x4 = 2" --> n6(("8"))
    n4 -- "x4 = 3" --> n7(("9"))
    n5 --> n8["B"]
    n6 --> n9["B"]
    n7 -- "x5 = 1" --> n10(("10"))
    n7 -- "x5 = 2" --> n11(("11"))
    n10 --> n12["B"]
    n11 --> n13["B"]
    n7 -- "x5 = 3" --> n14(("12"))
    n14 -- "x6 = 1" --> n15(("13"))
    n15 --> n16["B"]
    n14 -- "x6 = 2" --> n17(("14"))
    n17 --> n18["B"]
    n14 -- "x6 = 3" --> n19(("15"))
    n19 --> n20["B"]
    n14 -- "x6 = 4" --> n21(("16"))
    n21 -- "x7 = 1" --> n22(("17"))

    n1@{ shape: text}
    n3@{ shape: text}
    n8@{ shape: text}
    n9@{ shape: text}
    n12@{ shape: text}
    n13@{ shape: text}
    n16@{ shape: text}
    n18@{ shape: text}
    n20@{ shape: text}

Materi 3: Branch & Bounds

$\infty$	9	$\infty$	8		-8		$\infty$	1	$\infty$	0
10	$\infty$	14	$\infty$		-10		0	$\infty$	4	$\infty$
8	15	$\infty$	9		-8		0	7	$\infty$	1
12	11	10	$\infty$		-10		2	1	0	$\infty$
							0	-1	0	0	Total R
											37
							$\infty$	0	$\infty$	0
							0	$\infty$	4	$\infty$
							0	6	$\infty$	1
							2	0	0	$\infty$
Dengan demikian, mulai

	A	B	C	D
A	$\infty$	0	$\infty$	0
B	0	$\infty$	4	$\infty$
C	0	6	$\infty$	1
D	2	0	0	$\infty$
dari A, cari terkecil, ditemukan ke B atau D terkecil, lakukan reduksi sub-matrix A-B

	A	B	C	D					A	B	C	D
A	$\infty$	$\infty$	$\infty$	$\infty$				A	$\infty$	$\infty$	$\infty$	$\infty$
B	0	$\infty$	4	$\infty$		-0		B	0	$\infty$	4	$\infty$
C	0	$\infty$	$\infty$	1		-0		C	0	$\infty$	$\infty$	1
D	2	$\infty$	0	$\infty$		-0		D	2	$\infty$	0	$\infty$
						Total			-0	-0	-0	-1
						R =
						38			A	B	C	D
								A	$\infty$	$\infty$	$\infty$	$\infty$
								B	0	$\infty$	4	$\infty$
								C	0	$\infty$	$\infty$	0
								D	2	$\infty$	0	$\infty$
dari A, coba ke D

	A	B	C	D
A	$\infty$	$\infty$	$\infty$	$\infty$
B	0	$\infty$	4	$\infty$
C	0	6	$\infty$	$\infty$
D	2	0	0	$\infty$
Tidak ada reduksi baris dan kolom, sehingga R = 37, artinya ke D lebih baik daripada B

dari A-D, cari terkecil, ditemukan B dan C terkecil, langsung aja ke C

	A	B	C	D
A	$\infty$	$\infty$	$\infty$	$\infty$
B	0	$\infty$	$\infty$	$\infty$
C	0	6	$\infty$	$\infty$
D	$\infty$	$\infty$	$\infty$	$\infty$
Tidak ada reduksi baris dan kolom, sehingga R = 37, artinya ke C lebih baik daripada ke B

dari A-D-C, cari terkecil, tinggal B doang

	A	B	C	D
A	$\infty$	$\infty$	$\infty$	$\infty$
B	0	$\infty$	$\infty$	$\infty$
C	0	$\infty$	$\infty$	$\infty$
D	$\infty$	$\infty$	$\infty$	$\infty$
Tidak ada reduksi baris dan kolom, sehingga R = 37
Jalur selesai A-D-C-B, sekarang balik ke A lagi

	A	B	C	D
A	$\infty$	$\infty$	$\infty$	$\infty$
B	$\infty$	$\infty$	$\infty$	$\infty$
C	$\infty$	$\infty$	$\infty$	$\infty$
D	$\infty$	$\infty$	$\infty$	$\infty$
ok, pokoknya R = 37, dah gitu aja

Materi 4: String Matching

Fungsi Lo (Last Occurence)???
P = abaca
T = cabadaecdabacadca

Gunakan algoritma Boyer Moore

Link to original