Tugas 2 Praktikum Struktur Data: Stack, Queue, dan berbagai Binary Tree

Kembali ke Struktur Data (dengan Python)

Tugas ini diberikan pada hari dan tanggal: Sabtu, 25 November 2023

Link soal dan petunjuk tugas (yaitu link menuju halaman ini):

https://bit.ly/SoalTugas2PrakStrukdat2023Ganjil

Petunjuk umum:

  1. Kerjakan secara individu.

  2. Kerjakan tugas ini menggunakan bahasa pemrograman Python dengan file format berupa interactive Python notebook (yaitu file berbentuk .ipynb BUKAN .py), yang bisa dibuat misalnya menggunakan Jupyter Notebook atau Google Colaboratory.

  3. Harap sertakan penjelasan untuk setiap variabel yang digunakan dan setiap proses secara singkat di sebelah (atas/bawah/kanan) barisnya (dengan comment, #). Selain itu, sertakan juga penjelasan kode (yang bisa mencakupi idenya apa, bagaimana cara eksekusinya, atau tentang algoritma yang digunakan) pada cell di sebelah (atas/bawah) kode.

  4. Format nama file untuk Tugas 2 ini adalah:

    Kelas SIAK_Tugas2PrakStrukdat_Nama Lengkap_NPM.ipynb

    Contoh penamaan yang benar:

    Kelas C_Tugas2PrakStrukdat_Evgenii Mikhailovich Landis_2234567890.ipynb

  5. Pengumpulan Tugas 2 dilakukan ke Google Forms berikut ini:

    https://bit.ly/KumpulTugas2PrakStrukdat2023Ganjil

  6. Apabila ada yang ingin direvisi setelah pengumpulan, lakukan pengumpulan ulang di Google Forms yang sama, tambahkan keterangan bahwa ada revisi, dan tambahkan kata “revisi” pada bagian akhir nama file, contohnya menjadi

    Kelas C_Tugas2PrakStrukdat_Evgenii Mikhailovich Landis_2234567890_revisi.ipynb

    Kelas C_Tugas2PrakStrukdat_Evgenii Mikhailovich Landis_2234567890_revisi2.ipynb

    Kelas C_Tugas2PrakStrukdat_Evgenii Mikhailovich Landis_2234567890_revisi3.ipynb

    (Revisi boleh dilakukan berkali-kali.)

  7. Dengan durasi pengerjaan sekitar 2 (dua) minggu, tenggat waktu (deadline) pengumpulan Tugas 2 ini (termasuk revisi) adalah Sabtu, 9 Desember 2023, 23.59 WIB.

  8. Sesuai standar Universitas Indonesia, plagiarisme dilarang keras dan bisa menyebabkan nilai tugas praktikum menjadi nol untuk semua pihak yang terlibat, tanpa peringatan apapun. Namun, Anda boleh langsung menggunakan kode yang ada di modul praktikum.

  9. Module atau package Python yang boleh digunakan (di-import) untuk Tugas 2 ini hanyalah numpy dan graphviz. Apabila Anda berniat ingin menggunakan module lain, harap konfirmasikan ke narahubung terlebih dahulu (bisa saja diperbolehkan).

  10. Narahubung untuk Tugas 2 Praktikum Struktur Data adalah:

    Bisma Rohpanca Joyosumarto (ID LINE: bisma_joyosumarto)

    Silakan hubungi narahubung di atas apabila ada yang ingin ditanyakan atau dikonfirmasikan.

Soal:

  1. Buatlah fungsi print_reverse() yang menerima satu string, membuat suatu ArrayStack (untuk tipe data atau dtype yang sesuai, dengan ukuran yang memadai), memasukkan tiap huruf/karakter dari string yang diinput ke dalam stack tersebut, kemudian melakukan pop terus-menerus hingga stack kosong sambil menampilkan tiap huruf yang di-pop. Pastikan tiap huruf ditampilkan di baris yang sama (kecuali apabila memang ada newline di dalam string yang menjadi input).

    Contoh penggunaan fungsi:

    >>> print_reverse("Satu dua tiga")
agit aud utaS

    Hint: dtype yang sesuai adalah untuk menyimpan huruf/karakter (di mana tiap elemen di array berupa string dengan panjang \(\le 1\)), yaitu dtype=str atau sama saja dtype="<U1"

  2. Buatlah fungsi odd_even_others_sep() yang menerima suatu list, lalu menggunakan sejumlah SLQueue (boleh memilih antara SLLinQueue atau SLCircQueue, sama saja) untuk memisahkan antara tiga kategori yaitu

    1. bilangan ganjil

    2. bilangan genap

    3. data selain bilangan bulat

    dengan menjaga relative order (yaitu tanpa mengubah urutan data di kategori yang sama), kemudian mengembalikan list baru di mana ketiga kategori tersebut sudah dikelompokkan/terpisah dengan baik.

    Contoh penggunaan fungsi:

    >>> list_lama = [1, 2, "rumput", 3.14, 5, 6, 7, "mobil", 8]
>>> hasil = odd_even_others_sep(list_lama)
>>> print(hasil)
[1, 5, 7, 2, 6, 8, "rumput", 3.14, "mobil"]

    Hint: cobalah satu queue per kategori.

  3. Buatlah fungsi get_char_tree() yang menerima suatu string (misal memiliki panjang n), lalu membuat suatu ArrayBintree untuk menyimpan huruf/karakter (pilih dtype yang sesuai), dengan height yang memadai, kemudian memasang n elemen pertama di representasi array nya menjadi n huruf/karakter yang ada di string, sisanya string kosong (dengan emptydata=""). Lalu, ArrayBintree tersebut di-return. Berikan contoh penggunaan fungsinya dan tampilkan gambar dari pohon yang dihasilkan.

    Contoh penggunaan fungsi:

    >>> testpohon = get_char_tree("strukturdata")
>>> display(testpohon.get_digraph_simple())

    testpohon4

    Hint:

    • Jika n adalah panjang/ukuran string, height yang sesuai untuk ArrayBintree adalah

    \[h = \lceil \log_2 \left(n+1\right) \rceil -1\]

    • numpy menyediakan fungsi logaritma np.log yaitu \(\ln \left( x \right)\), dan juga fungsi ceiling np.ceil yaitu \(\lceil x \rceil\) (jangan lupa meng-convert hasil np.ceil menjadi tipe data int)

    • Berdasarkan sifat logaritma, \(\log_2 \left(x\right) = \frac{\ln x}{\ln 2}\)

  4. Buatlah fungsi max_heap_sort_descending() yang menerima suatu array numpy (bukan list), memasukkan semua elemen array yang diinput ke dalam suatu ArrayMaxHeap, kemudian membentuk suatu array baru dengan mengeluarkan satu-satu elemen dari max heap tersebut, lalu me-return array baru tersebut.

    Contoh penggunaan fungsi:

    >>> array1 = np.array([10, 5, 20, 70, 30, 45])
>>> array2 = max_heap_sort_descending(array1)
>>> print(array2)
[70 45 30 20 10  5]

    Hint: dtype untuk ArrayMaxHeap bisa disamakan dengan tipe data dari elemen-elemen yang ada di array yang diinput.

  5. BST vs. AVL

    1. Buatlah fungsi get_bst() yang menerima suatu list atau array, melakukan insertion untuk tiap elemen list/array ke suatu LinkedBST, kemudian me-return LinkedBST tersebut.

    2. Serupa, buatlah fungsi get_avl() yang menerima suatu list atau array, melakukan insertion untuk tiap elemen list/array ke suatu LinkedAVL, kemudian me-return LinkedAVL tersebut.

    3. Buatlah array numpy berisi tiap digit di NPM Anda.

    4. Gunakan fungsi max_heap_sort_descending() dengan array yang Anda buat di poin (c) untuk memperoleh array baru yang terurut secara menurun.

    5. Gunakan fungsi get_bst() dan get_avl() tersebut untuk memperoleh suatu LinkedBST dan suatu LinkedAVL dari array yang Anda peroleh di soal poin (d). Abaikan error insertion. Kemudian, tampilkan gambar keduanya.

    6. Binary tree memiliki height -1 jika kosong, memiliki height 0 jika berisi satu node saja, dan memiliki height 1 jika berisi dua node saja (atau tiga node jika complete). Berapa kah height dari LinkedBST dan dari LinkedAVL yang Anda peroleh di soal poin (e)? Mana yang lebih dangkal/pendek?

    Contoh penggunaan fungsi:

    >>> arrayNPM = np.array([2, 1, 0, 6, 6, 3, 5, 5, 8, 1])
>>> arrdesc = max_heap_sort_descending(arrayNPM)
>>> contohbst = get_bst(arrdesc)
>>> contohavl = get_avl(arrdesc)
>>> display(contohbst.get_digraph_simple())

    contohbst
    >>> display(contohavl.get_digraph_simple())

    contohavl