UTS Pemrograman Lanjut 2025

1. Contoh C++ untuk setiap kompleksitas

// log n: pembagian dua berulang
for (int i=n; i>1; i/=2) work();
// n: satu kunjungan per elemen
for (int i=0; i<n; ++i) work();
// n log n: n elemen, log n putaran
for (int i=0; i<n; ++i) for (int j=n; j>1; j/=2) work();
// n²: semua pasangan
for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) work();
// 2ⁿ: dua cabang di tiap tingkat
void subset(int i, int n) { if (i==n) { work(); return; }
    subset(i+1,n); subset(i+1,n); }
// n!: enumerasi permutasi n elemen berbeda
sort(a.begin(), a.end());
do { work(); } while (next_permutation(a.begin(), a.end()));

Asumsikan work() O(1); biaya mencetak atau menyalin seluruh permutasi akan menambah faktor n.

2. Mencari waktu minimum

a. Predikat monoton: valid(t) bernilai benar jika floor(t/2)+floor(t/3)+floor(t/7) ≥ 8. Secara umum:

bool valid(long long t, const vector<long long>& p, long long jobs) {
    if (t < 0) return false;
    long long total = 0;
    for (auto time : p) {
        long long add = t / time;
        if (add >= jobs - total) return true; // hindari overflow
        total += add;
    }
    return false;
}

b. Kode sumber memakai variabel awal z tanpa nilainya; ambil asumsi z=16, pangkat dua yang melampaui jawaban, x awal −1. Pemeriksaan x+b: b=16 uji 15 valid; b=8 uji 7 tidak valid sehingga x=7, lalu 15 valid; b=4 uji 11 valid; b=2 uji 9 valid; b=1 uji 8 tidak valid sehingga x=8, lalu 9 valid. Ada 5 putaran luar dan 7 evaluasi valid, dengan 2 penambahan x; hasil x+1=9. Pada t=8 selesai 4+2+1=7 pekerjaan, sedangkan pada t=9 selesai 4+3+1=8. Jumlah iterasi berubah jika z yang dipilih berbeda.

3. Representasi graf

Indeks 0 Bundaran UNDIP (U), 1 Widya Puraya (W), 2 Jembatan Katak (J), 3 Psikologi Baru (P), 4 FSM (F). Graf (a) tidak berarah berbobot: edge U–W:3, U–J:2, U–P:8, J–P:4, W–P:5, W–F:5, P–F:1. Graf (b) berarah tanpa bobot: U→W, U→J, J→P, W→P, W→F, P→F.

using E = pair<int,int>; // (tujuan, bobot)
vector<vector<E>> adjA = {
 {{1,3},{2,2},{3,8}}, {{0,3},{3,5},{4,5}},
 {{0,2},{3,4}}, {{0,8},{1,5},{2,4},{4,1}}, {{1,5},{3,1}}
};
vector<tuple<int,int,int>> edgesA = {
 {0,1,3},{0,2,2},{0,3,8},{2,3,4},{1,3,5},{1,4,5},{3,4,1}
};
vector<vector<int>> adjB = {{1,2},{3,4},{3},{4},{}};
vector<pair<int,int>> edgesB = {{0,1},{0,2},{2,3},{1,3},{1,4},{3,4}};
// Matriks dibangun dari edge list; 0 berarti tidak ada sisi.
int matrixA[5][5] = {}, matrixB[5][5] = {};
for (auto [u,v,w] : edgesA) matrixA[u][v] = matrixA[v][u] = w;
for (auto [u,v] : edgesB) matrixB[u][v] = 1;

4. Dijkstra pada graf (a)

vector<int> shortest(const vector<vector<E>>& adj, int start) {
    const int INF = 1000000000;
    vector<int> dist(adj.size(), INF);
    priority_queue<E, vector<E>, greater<E>> pq; // (jarak, simpul)
    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 (d+w < dist[v]) {
            dist[v]=d+w; pq.push({dist[v],v});
        }
    }
    return dist;
}

Ambil awal U sebagai contoh. Jarak awal U=0; perbarui J=2, W=3, P=8. Dari J perbarui P=6; dari W perbarui F=8; dari P perbarui F=7. Hasil U=0, J=2, W=3, P=6 dan F=7, dengan lintasan ke F U→J→P→F. Semua bobot tidak negatif, memenuhi syarat Dijkstra.

5. Banyak simpul terjangkau pada graf (b)

int reachable(const vector<vector<int>>& g, int start) {
    vector<bool> seen(g.size(), false);
    stack<int> st; st.push(start); seen[start] = true;
    int count = 0;
    while (!st.empty()) {
        int u=st.top(); st.pop(); ++count;
        for (int v : g[u]) if (!seen[v]) {
            seen[v]=true; st.push(v);
        }
    }
    return count;
}

reachable(adjB,3) menghasilkan 2: P sendiri dan F. Kunjungan ditandai saat masuk stack agar setiap simpul dihitung satu kali; kompleksitas O(V+E).