Lembar kerja Algoritma & kompleksitas dengan jawaban

Lembar kerja Algoritma & kompleksitas gratis yang dapat dicetak: 8 soal dari mudah hingga tingkat ujian, dengan kunci jawaban. Cetak atau simpan sebagai PDF.

Lembar kerja baruBerlatih online dengan petunjuk

Untuk pengajar: gratis untuk dicetak, disalin, dan dipakai di kelas. Setiap lembar kerja baru punya nilai baru dan kunci jawabannya sendiri. Tautan ke ExamProblems di halaman mata kuliah Anda sangat kami hargai.

Nama: ____________________   Tanggal: ____________

1.Mudah

Notasi manakah yang menyatakan batas bawah (lower bound) pertumbuhan?

  1. AO (Big O)
  2. BΩ (Big Omega)
  3. Co (little o)
  4. DΘ (Big Theta)
2.Mudah

Manakah yang tumbuh paling lambat ketika n menjadi besar?

  1. AO(n²)
  2. BO(log n)
  3. CO(n)
  4. DO(n log n)
3.Mudah

Berapa kompleksitas waktu depth-first search pada graf yang disimpan sebagai adjacency list?

  1. AO(E log V)
  2. BO(V²)
  3. CO(V × E)
  4. DO(V + E)
4.Sedang

Pemrograman dinamis (dynamic programming) berguna ketika suatu masalah memiliki:

  1. AHanya input acak
  2. BTidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah
  3. CSubmasalah yang tumpang tindih dan substruktur optimal
  4. DSatu loop saja
5.Sedang

Dengan koin 1, 3, dan 4 serta jumlah 6, berapa koin yang dipakai metode greedy "koin terbesar dulu" dibandingkan solusi optimal?

  1. AGreedy memakai 4 koin; optimalnya 3
  2. BGreedy memakai 3 koin; optimalnya 3
  3. CGreedy memakai 2 koin; optimalnya 2
  4. DGreedy memakai 3 koin; optimalnya 2
6.Sedang

Berapa kompleksitas waktu dari: for i = 1 to n: for j = 1 to i: lakukan kerja O(1)?

  1. AO(n³)
  2. BO(n²)
  3. CO(n)
  4. DO(n log n)
7.Sulit

Mengambil kedua titik ujung dari setiap sisi dalam maximal matching menghasilkan vertex cover. Seberapa baik cover ini?

  1. ASelalu merupakan minimum vertex cover
  2. BKualitasnya tidak diketahui dibandingkan optimum
  3. CPaling banyak dua kali ukuran minimum vertex cover
  4. DPaling banyak log n kali minimum
8.Sulit

Dengan teorema master, T(n) = 8T(n/2) + O(n²) memiliki solusi:

  1. AΘ(n³)
  2. BΘ(n²)
  3. CΘ(n log n)
  4. DΘ(n² log n)

Kunci jawaban

  1. 1. B · Ω (Big Omega)
  2. 2. B · O(log n)
  3. 3. D · O(V + E)
  4. 4. C · Submasalah yang tumpang tindih dan substruktur optimal
  5. 5. D · Greedy memakai 3 koin; optimalnya 2
  6. 6. B · O(n²)
  7. 7. C · Paling banyak dua kali ukuran minimum vertex cover
  8. 8. A · Θ(n³)

Penyelesaian lengkap langkah demi langkah: latih topik ini di examproblems.com.