Tugas 1 Praktikum Struktur Data: Array, Linked List, OOP

Tugas 1 Praktikum Struktur Data: Array, Linked List, OOP

Kembali ke Struktur Data (dengan Python)

Tugas ini diberikan pada hari dan tanggal: Minggu, 22 Oktober 2023

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

https://bit.ly/SoalTugas1PrakStrukdat2023Ganjil

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 1 ini adalah:

    Kelas SIAK_Tugas1PrakStrukdat_Nama Lengkap_NPM.ipynb

    Contoh penamaan yang benar:

    Kelas C_Tugas1PrakStrukdat_Charles Antony Richard Hoare_2234567890.ipynb

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

    https://bit.ly/KumpulTugas1PrakStrukdat2023Ganjil

  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_Tugas1PrakStrukdat_Charles Antony Richard Hoare_2234567890_revisi.ipynb

    Kelas C_Tugas1PrakStrukdat_Charles Antony Richard Hoare_2234567890_revisi2.ipynb

    Kelas C_Tugas1PrakStrukdat_Charles Antony Richard Hoare_2234567890_revisi3.ipynb

    (Revisi boleh dilakukan berkali-kali.)

  7. Dengan durasi pengerjaan sekitar 2 (dua) minggu, tenggat waktu (deadline) pengumpulan Tugas 1 ini (termasuk revisi) adalah Minggu, 5 November 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 1 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 1 Praktikum Struktur Data adalah:

    Bisma Rohpanca Joyosumarto (ID LINE: bisma_joyosumarto)

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

Soal:

Untuk masing-masing dari kelima soal berikut ini, setelah menulis kode Anda, buatlah contoh running atau contoh penggunaannya (angka/data yang digunakan tidak harus sama dengan contoh di soal).

Nilai maksimal apabila tiap linked list yang terlibat di contoh running yang Anda buat juga ditampilkan dengan print_all dan juga graphviz.

  1. Menambahkan elemen array ke ujung linked list

    1. Diberikan suatu linked list dan suatu array atau list, buatlah fungsi add_array_to_sllist yang menambahkan masing-masing elemen array atau list tersebut ke ujung linked list.

    2. Mengingat bahwa insertion pada ujung linked list adalah O(n), bagaimana kompleksitas waktu (time complexity) dari fungsi yang Anda buat? Berikan argumen atas jawaban Anda (tidak harus berupa tabel running time, boleh berupa paragraf).

    Nilai maksimal apabila Anda berhasil membuat fungsi yang O(n) (atau lebih tepatnya O(n) + O(m), di mana n adalah ukuran mula-mula dari linked list dan m adalah ukuran array).

    Contoh penggunaan fungsi:

    >>> linkedlist1 = SLList()
>>> linkedlist1.head = SLNode(89)
>>> linkedlist1.head.next = SLNode(43)
>>> array1 = np.array([64, -12, 35, 98])
>>> add_array_to_sllist(linkedlist1, array1)
>>> linkedlist1.print_all()
head -> 89 -> 43 -> 64 -> -12 -> 35 -> 98 -> None

  2. Linked list menjadi array

    Diberikan suatu linked list, buatlah fungsi sllist_to_array yang mengubahnya menjadi array. Nilai maksimal apabila definisi fungsi tidak melibatkan fitur .append maupun comprehension (baik list comprehension, set comprehension, maupun tuple comprehension).

    Contoh penggunaan fungsi:

    >>> linkedlist1 = SLList()
>>> array1 = np.array([10, 30, -47, 73])
>>> add_array_to_sllist(linkedlist1, array1)
>>> linkedlist1.print_all()
head -> 10 -> 30 -> -47 -> 73 -> None
>>> array2 = sllist_to_array(linkedlist1)
>>> print(array2)
[ 10  30 -47  73]

  3. Sorting suatu linked list

    1. Diberikan suatu linked list, buatlah fungsi get_sorted_sllist yang mengembalikan (return) linked list tersebut dalam keadaan sudah terurut, di mana node dengan nilai data terkecil lah yang ditunjuk oleh head (sedangkan node dengan data terbesar ada di ujung linked list).

    2. Bagaimana kompleksitas waktu (time complexity) dari fungsi yang Anda buat? Berikan argumen atas jawaban Anda (tidak harus berupa tabel running time, boleh berupa paragraf).

    Nilai maksimal apabila

    • Anda berhasil membuat fungsi yang O(n log n)

    • Fungsi yang Anda buat menghasilkan linked list baru tanpa mengubah linked list yang menjadi input

    Contoh penggunaan fungsi:

    >>> linkedlist1 = SLList()
>>> array1 = np.array([10, -3, 97, -48])
>>> add_array_to_sllist(linkedlist1, array1)
>>> linkedlist2 = get_sorted_sllist(linkedlist1)
>>> linkedlist2.print_all()
head -> -48 -> -3 -> 10 -> 97 -> None

    Hint: untuk soal ini, tidak ada larangan, linked list akan diperlakukan bagaimana hingga nantinya memperoleh linked list yang sudah terurut. Bahkan, apabila misalnya linked list ingin diubah menjadi bentuk lain terlebih dahulu, yang nantinya diubah kembali menjadi linked list, itu juga tidak masalah. Selama hasilnya adalah linked list yang terurut, tidak ada cara yang salah. Silakan berkreativitas :)

  4. Membuat method

    Modifikasi definisi class linked list agar fungsi yang telah Anda buat di soal nomor 1, 2, dan 3 bisa digunakan sebagai method, misalnya bernama add_array, to_array, dan get_sorted

    Contoh penggunaan method:

    >>> linkedlist1 = SLList()
>>> array1 = np.array([81, -45, -27, 39])
>>> linkedlist1.add_array(array1)
>>> linkedlist2 = linkedlist1.get_sorted()
>>> array2 = linkedlist2.to_array()
>>> print(array2)
[-45 -27  39  81]

  5. Penggabungan linked list dengan +

    Modifikasi definisi class linked list agar dua linked list bisa “ditambahkan”. Berikut contoh yang berhasil:

    >>> linkedlist1 = SLList()
>>> linkedlist1.add_array([9, 6, 2, 7])
>>> linkedlist2 = SLList()
>>> linkedlist2.add_array([10, 58, 3])
>>> linkedlist3 = linkedlist1 + linkedlist2
>>> linkedlist3.print_all()
head -> 9 -> 6 -> 2 -> 7 -> 10 -> 58 -> 3 -> None

    Hint: gunakan operator overloading.