DSA

Definisi struktur data, algoritma, dan hubungan keduanya dalam pemecahan masalah komputasi.

Mengapa pemilihan struktur data dan algoritma menentukan kualitas solusi perangkat lunak.

Pengelompokan struktur data: linier, non-linier, statis, dinamis, dan homogen.

Paradigma algoritma: brute force, divide and conquer, greedy, dynamic programming, dan backtracking.

Strategi belajar struktur data dan algoritma secara efektif dengan pola bertahap, latihan, dan refleksi.

Soal latihan dan refleksi untuk menguji pemahaman konsep dasar DSA pada Section pengenalan.

Sejarah singkat C++, karakteristik bahasa modern, dan alasan memilih C++ sebagai bahasa utama Course DSA.

Cara memasang compiler C++ (GCC, Clang, MSVC) di Linux, macOS, dan Windows beserta verifikasinya.

Menyiapkan Visual Studio Code dengan ekstensi C++ serta file tasks.json, launch.json, dan c_cpp_properties.json untuk DSA.

Anatomi program C++ modern: header, fungsi main, std::vector, dan operasi dasar pengolahan data.

Empat tahap kompilasi C++: preprocessing, kompilasi, assembling, dan linking beserta cara memeriksanya.

Mengotomatiskan build C++ multi-file dengan CMake: CMakeLists.txt, target, variabel, dan best practices.

Tipe fundamental, inisialisasi, dan konversi tipe di C++.

Operator aritmetika, logika, perbandingan, bitwise, dan precedence.

if, else, switch, dan operator ternary.

for, while, do-while, dan range-based for loop.

Definisi fungsi, parameter, return value, overload, dan rekursi dasar.

Array C-style: deklarasi, akses, dan keterbatasannya.

std::string, std::string_view, dan operasi umum.

Pointer, reference, dan perbedaan pass-by-value/reference.

Dasar OOP di C++ untuk memodelkan struktur data.

Generic programming dengan function dan class template.

Stack vs heap, new/delete, RAII, dan kebocoran memori.

Mengapa kita perlu menganalisis kompleksitas algoritma dan apa yang dimaksud dengan kompleksitas waktu serta kompleksitas ruang.

Cara mengukur dan menghitung time complexity algoritma sebagai fungsi dari ukuran input.

Cara mengukur kompleksitas ruang (memori tambahan) yang dipakai algoritma sebagai fungsi dari ukuran input.

Definisi formal notasi Big-O sebagai batas atas asimptotik dan cara menentukannya dari sebuah fungsi.

Definisi formal notasi Big-Omega sebagai batas bawah asimptotik dari sebuah fungsi.

Definisi formal notasi Big-Theta sebagai batas ketat asimptotik yang menggabungkan Big-O dan Big-Omega.

Cara menghitung time complexity berbagai pola loop: tunggal, bersarang, logaritmik, dan dengan pertambahan non-trivial.

Cara menganalisis time complexity fungsi rekursif dengan recurrence relation, recursion tree, dan substitusi.

Analisis amortisasi: aggregate, accounting, dan potential method untuk operasi yang kadang mahal tetapi rata-rata murah.

Tabel referensi komprehensif kompleksitas algoritma umum dan cara membandingkan dua algoritma secara sistematis.

Empat pendekatan utama analisis algoritma: worst case, average case, best case, dan amortized.

Teknik membuktikan kebenaran algoritma iteratif dengan loop invariant: inisialisasi, maintenance, dan termination.

Prinsip induksi matematis: kasus dasar, langkah induksi, dan penerapannya dalam pembuktian algoritma.

Membuktikan kebenaran algoritma klasik: linear search dan insertion sort dengan loop invariant serta induksi matematis.

Cara menurunkan recurrence relation dari algoritma rekursif dan menyelesaikannya dengan substitution, recursion tree, dan master theorem.

Formula siap pakai untuk menyelesaikan recurrence T(n) = a·T(n/b) + f(n) dengan tiga kasus berbeda dan contoh nyata.

Karakteristik array: akses acak, kontigu di memori, ukuran tetap.

Insert, delete, search, dan update pada array.

Perbedaan array C-style, std::array, dan std::vector.

Penggunaan std::vector sebagai array dinamis: capacity, reserve, dan iterator invalidation.

Matriks sebagai array 2D: row-major vs column-major dan implikasi cache.

Operasi matriks: transpose, perkalian, rotasi 90 derajat, dan spiral traversal.

Precompute prefix sum untuk range sum query O(1), versi 1D dan 2D.

Range update O(1) dengan difference array dan materialisasi via prefix sum.

Jendela geser ukuran tetap dan variabel untuk subarray optimal.

Dua pointer untuk pencarian pasangan, partisi, dan subarray optimal.

Struktur data untuk range query idempotent O(1): min, max, gcd.

Karakteristik linked list dan kapan dipakai.

Implementasi singly linked list dengan template C++.

Linked list dengan pointer prev dan next untuk traversal dua arah.

Variasi linked list yang tail menunjuk ke head; cocok untuk round-robin.

Reverse, find middle, detect cycle, dan merge sorted list.

Class template lengkap dengan destructor, copy/move semantics, dan iterator.

Ownership node, RAII, smart pointer untuk mencegah leak.

Pola klasik: palindrome, remove nth from end, intersection.

Struktur LIFO untuk undo, evaluasi ekspresi, dan call stack.

Tiga varian: array, linked list, dan std::stack<T, Container>.

Struktur FIFO untuk BFS, scheduling, dan buffer.

Array circular, linked list, dan std::queue.

Ring buffer dengan trik modulo untuk kapasitas tetap.

Double-ended queue — operasi O(1) di kedua ujung.

Stack dengan invariant terurut untuk NGE, histogram, dan sejenisnya.

Deque dengan invariant terurut untuk sliding window extremum.

Parenthesis matching, infix-postfix, BFS, dan topological sort.

Memetakan key ke nilai hash untuk akses cepat.

Sifat hash function yang baik dan contohnya.

Strategi menangani tabrakan hash.

Collision resolution dengan linked list per bucket.

Collision resolution dengan probing: linear, quadratic, double.

Hash container STL dan penggunaannya.

Rata-rata vs worst case, faktor load, dan resizing.

Counting, deduplikasi, frequency map, two-sum.

Pencarian sekuensial O(n) yang bekerja pada data apa pun.

Pencarian O(log n) pada data terurut dengan divide and conquer.

Lower bound, upper bound, dan binary search dengan predikat kustom.

Trik binary search pada domain solusi, bukan pada array input.

Pencarian maksimum/minimum fungsi unimodal dalam O(log n).

Jump search, exponential search, dan interpolation search.

Tabel kompleksitas, decision tree, dan panduan memilih algoritma.

Definisi, in-place, stabil, dan kompleksitas umum.

Sorting sederhana O(n^2) dengan pertukaran tetangga.

Memilih elemen minimum lalu menempatkannya.

Menyisipkan elemen ke posisi yang benar.

Divide and conquer stabil O(n log n).

Divide and conquer dengan pivot, rata-rata O(n log n).

Sorting berbasis heap, O(n log n) in-place.

Sorting non-comparison untuk range kecil.

Sorting digit-per-digit, O(d*(n+b)).

Membagi elemen ke bucket lalu mengurutkan masing-masing.

Pengertian stabilitas dan kapan penting.

Sorting tanpa memori tambahan signifikan.

Tabel kompleksitas dan rekomendasi penggunaan.

Fungsi yang memanggil dirinya sendiri untuk menyelesaikan sub-masalah.

Dua komponen wajib agar rekursi berhenti dan benar.

Bagaimana compiler mengelola frame pemanggilan rekursif.

Trade-off rekursif vs iteratif: keterbacaan, overhead, depth limit.

Rekursi dengan dua atau lebih panggilan diri — pemicu ledakan eksponensial.

Eksplorasi pohon kemungkinan dengan pemilihan, eksplorasi, dan undo.

Memotong cabang yang tidak menjanjikan lebih awal.

Membangkitkan permutasi dan kombinasi dengan rekursi.

Membangkitkan semua subset suatu himpunan.

Branching factor, depth, dan kompleksitas total algoritma backtracking.

Definisi tree, root, leaf, dan edge.

Parent, child, sibling, ancestor, descendant, height, depth.

Tree dengan maksimal dua child per node.

Pre-order, in-order, post-order, level-order.

BST: sifat pengurutan dan operasi dasar.

Insert, delete, search, dan successor.

Konsep balancing untuk menjamin O(log n).

BST self-balancing dengan rotation.

BST self-balancing dengan warna node.

Prefix tree untuk pencarian string.

Struktur data range query O(log n).

Binary Indexed Tree untuk prefix sum O(log n).

Pola soal klasik: LCA, diameter, path sum.

Definisi heap dan sifat heap-order.

Varian heap dan penggunaannya.

Insert, extract, heapify, dan peek.

Membangun heap dari array dalam O(n).

Container adapter STL untuk priority queue.

Mencari k elemen terbesar/terkecil dengan heap.

Aplikasi heap untuk menggabungkan k array terurut.

Dijkstra, scheduling, median stream, dan kasus lain.

Definisi graph: vertices, edges, dan jenis-jenis graph.

Degree, path, cycle, connected, dan istilah lain.

Perbedaan graph berarah dan tidak berarah.

Graph dengan bobot pada edge.

Representasi graph sebagai matriks.

Representasi graph sebagai daftar tetangga.

Representasi graph sebagai daftar edge.

Perbandingan representasi: kompleksitas dan kapan dipakai.

BFS dan DFS dasar.

Menemukan komponen terhubung dengan DFS/BFS.

Mendeteksi cycle pada directed dan undirected graph.

Cek apakah graph bipartit dengan coloring.

Struktur data Union-Find untuk graph.

Pola soal klasik berbasis graph: flood fill, jumlah pulau, friend circles, dan topological sort.

BFS level-by-level dengan queue.

DFS mendalam dengan rekursi atau stack.

Urutan topologis DAG dengan Kahn atau DFS.

Ikhtisar algoritma shortest path.

Shortest path single-source dengan bobot non-negatif.

Shortest path dengan deteksi negative cycle.

All-pairs shortest path O(n^3).

Konsep MST dan algoritma klasik.

MST berbasis sorting edge dan DSU.

MST berbasis priority queue greedy.

Algoritma Kosaraju dan Tarjan untuk SCC.

Menemukan titik dan jembatan kritis dengan DFS lowlink.

Ford-Fulkerson dan Edmonds-Karp.

Karakteristik algoritma greedy dan kapan cocok.

Sifat pilihan greedy yang menghasilkan solusi optimal global.

Memilih aktivitas maksimum yang tidak tumpang tindih.

Penjadwalan interval untuk memaksimalkan throughput.

Knapsack yang membolehkan pecahan barang.

Kompresi data berbasis frekuensi karakter.

Penjadwalan tugas dengan deadline dan profit.

Teknik membuktikan greedy menghasilkan solusi optimal.

Definisi DP: optimal substructure dan overlapping subproblems.

DP top-down: simpan hasil sub-masalah di cache untuk menghindari recomputation.

DP bottom-up: bangun tabel secara iteratif dari sub-masalah terkecil.

Cara merancang state DP: parameter yang dibutuhkan untuk mengambil keputusan.

Cara menulis recurrence: pilihan apa yang tersedia di setiap state?

Progresi dari rekursi naif O(2^n) ke memo O(n) ke tabulation O(n) ke space-optimized O(1).

DP 1D paling klasik: jumlah cara naik tangga dengan langkah 1 atau 2.

DP klasik: jumlah minimum koin atau jumlah cara untuk membentuk nilai tertentu.

0/1 knapsack: maximasi nilai dengan batasan kapasitas. DP 2D dan optimasi ruang 1D.

DP 2D klasik: subsequence terpanjang yang sama pada dua string, plus rekonstruksi.

DP O(n²) dan optimasi O(n log n) dengan patience sorting.

DP 2D: jumlah minimum operasi insert, delete, replace untuk mengubah satu string ke string lain.

DP pada interval [i, j] dengan mencoba semua titik potong k. Contoh: matrix chain multiplication.

DP pada pohon: post-order traversal, dp[u] sebagai fungsi dp[v] anak-anaknya.

DP dengan state bitmask untuk himpunan kecil (n ≤ 20). Contoh klasik: TSP.

Teknik lanjutan: divide and conquer optimization, convex hull trick, monotone queue, Knuth optimization.

std::string, std::string_view, dan encoding.

Pengantar masalah pencocokan pola pada string.

Pencocokan pola brute force O(n*m).

KMP dengan failure function O(n+m).

Z-function untuk pattern matching dan struktur string.

Pencocokan pola dengan rolling hash.

Pencocokan multiple pattern secara serentak.

Hash substring dalam O(1) update.

Array berisi indeks suffix terurut.

LCP array dan Kasai algorithm.

Pola soal klasik: palindrome, anagram, compression.

Membaca soal dengan cermat: input, output, constraint, dan klasifikasi tipe masalah.

Kerangka berpikir dari brute force ke solusi optimal: brute force → pola → optimasi → verifikasi.

Solusi paling sederhana sebagai baseline; enumerasi semua kemungkinan secara sistematis.

Membagi masalah jadi sub-masalah, menyelesaikan, lalu menggabungkan — disertai Master Theorem.

Strategi dua indeks yang bergerak konvergen atau paralel — recap cepat dan variasi lanjutan.

Recap cepat window geser dan variasi lanjutan: K-distinct, sum ≤ K, permutation in string.

Recap prefix sum 1D dan ekstensi ke 2D plus kombinasi dengan difference array.

Teknik difference array 2D, event counting, dan aplikasi paint problem.

Memetakan nilai besar ke indeks kecil agar segment tree dan BIT tetap efisien.

Memproses event terurut oleh koordinat untuk solusi geometri dan interval.

Membagi masalah jadi dua, selesaikan tiap bagian, lalu gabungkan untuk memangkas 2^n menjadi 2^(n/2).

Tabel keputusan memilih struktur data berdasarkan operasi yang dominan.

Definisi formal Big-O via limit, growth rates, dan Big-O sebagai himpunan fungsi.

Properti logaritma dan eksponen yang menjadi dasar analisis binary search dan kompleksitas.

Properti aritmetika modulo: penjumlahan, perkalian, pengurangan, dan pembagian via invers.

Algoritma Euclidean untuk FPB dan KPK, plus std::gcd/std::lcm di C++17.

Definisi bilangan prima, primality test trial division, optimasi 6k±1.

Menemukan semua prima hingga n dalam O(n log log n), plus linear sieve dan segmented sieve.

Menguraikan bilangan menjadi faktor primanya via trial division; aplikasi jumlah dan sum pembagi.

Prinsip dasar penghitungan: product rule, sum rule, inclusion-exclusion, pigeonhole.

Rumus P(n,k), C(n,k), identitas Pascal, dan komputasi modular dengan precompute faktorial.

Probabilitas diskrit: sample space, event, conditional, expected value, dengan simulasi Monte Carlo.

Pangkat cepat O(log n) secara rekursif dan iteratif, dengan modular exponentiation dan aplikasi Fermat.

Invers modulo via Fermat's little theorem dan Extended Euclidean; pembagian modular.

DSU dengan path compression dan union by rank.

Struktur tree untuk range query dan update.

Update range pada segment tree secara tertunda.

BIT untuk prefix query O(log n).

Struktur idempotent O(1) query tanpa update.

Struktur data yang menjaga versi lamanya.

Set terurut dengan akses by index (__gnu_pbds).

Tree dengan operasi k-th element.

Struktur data untuk string panjang dengan operasi cepat.

Mo's algorithm, sqrt decomposition, dan teknik lain.

Algoritma yang memakai keacakan untuk expected complexity.

Analisis amortisasi dengan aggregate, accounting, potential method.

Menyelesaikan masalah geometri dengan menyapu garis.

Algoritma geometri: convex hull, point in polygon.

Operasi bit dan DP bitmask untuk himpunan kecil.

Trik bitwise: popcount, leading zero, swap.

Max flow, min cost flow, dan aplikasinya.

Bipartite matching dengan Hungarian dan Hopcroft-Karp.

Suffix automaton, suffix tree, dan pemrosesan string lanjutan.

Algoritma pendekatan untuk masalah NP-hard.

Kelas P, NP, NP-hard, dan reduksi.

vector, deque, list, array, forward_list.

set, map, multiset, multimap.

unordered_set dan unordered_map dengan hash.

Kategori iterator dan operasinya.

sort, binary_search, lower_bound, dan algoritma lain di <algorithm>.

Ranges C++20 untuk komposisi algoritma yang ekspresif.

Fungsi comparator, operator<, dan std::less.

Fungsi anonim untuk callback dan comparator.

Tipe komposit untuk pengelompokan nilai heterogen.

Ringkasan kompleksitas operasi tiap container STL.

Pass-by-value vs pass-by-reference: kapan masing-masing dipakai.

Mengapa const penting dan kapan dipakai.

std::move, rvalue reference, dan efisiensi transfer.

unique_ptr, shared_ptr, weak_ptr untuk manajemen memori otomatis.

Template lanjutan: specialization, SFINAE, concepts.

Exception, error code, dan std::expected.

Deteksi dan pencegahan overflow.

Menghindari UB, dangling, dan use-after-free.

Membuat comparator untuk struct dan priority_queue.

Optimasi I/O, cache, dan performa kode DSA.

Pendekatan pengujian untuk algoritma: unit, edge, property.

GoogleTest atau Catch2 untuk menguji fungsi.

Kasus batas wajib: kosong, satu elemen, maksimum.

Menguji sifat algoritma dengan input acak.

Membandingkan solusi cepat vs solusi brute force.

GDB dasar dan strategi isolasi bug.

AddressSanitizer, UndefinedBehaviorSanitizer.

Jebakan UB umum dan cara mendeteksinya.

Mengukur waktu eksekusi dan menemukan bottleneck.

Ekosistem CP: judge, kontes, dan rating.

I/O parsing cepat untuk format CP.

sync_with_stdio(false) dan cin tie.

Mengestimasi kompleksitas dari batasan soal.

Konversi n ke kompleksitas maksimum yang diterima.

Manajemen waktu: pick easy, skip, revisit.

Kesalahan umum: overflow, off-by-one, RE/TLE.

Snippet kode yang sering dipakai di kontes.

Cara mengevaluasi dan meningkatkan solusi setelah kontes: baca editorial, upsolve, dan refleksi.

Indexing, ranking, dan trie pada search engine sederhana.

Collaborative filtering sederhana berbasis graph.

Topological sort dan priority queue untuk scheduler.

Shortest path pada peta dan grid.

Tokenisasi, stemming, dan string matching.

Implementasi LRU cache dengan hash + linked list.

Simulasi queue sistem layanan.

Sampling, hashing, dan external sort.

Roadmap personal berbasis tujuan dan waktu.

Spaced repetition dan deliberative practice.

Cara membaca editorial solusi secara efektif.

Belajar dari berbagai pendekatan.

Cara komunikasi Big-O saat wawancara.

Kerangka komunikasi: clarify, plan, code, test.

Pola soal populer di wawancara teknis: two pointers, sliding window, DP, dan lainnya.

Self-assessment rubric untuk mengukur kemampuan DSA.

Bangun tool terminal yang merender linked list, binary tree, dan graph sebagai ASCII art.

Benchmark bubble, insertion, merge, quick, heap, dan std::sort pada dataset acak, terurut, dan terbalik.

Bangun search engine sederhana berbasis inverted index dengan ranking TF-IDF.

Cari jalur terpendek pada grid 2D berbobot dengan algoritma Dijkstra.

Simulasikan CPU scheduler dengan priority queue dan aturan FCFS, SJF, priority-based.

Selesaikan 8-puzzle dengan BFS, DFS, dan A* heuristic.