13 Ide dan Topik Proyek Struktur Data Menarik Untuk Pemula [2022]

Dalam dunia ilmu komputer, struktur data mengacu pada format yang berisi kumpulan nilai data, hubungan mereka, dan fungsi yang dapat diterapkan pada data. Struktur data mengatur data sehingga dapat diakses dan dikerjakan dengan algoritma tertentu secara lebih efektif. Dalam artikel ini, kami akan membuat daftar beberapa proyek struktur data yang berguna untuk membantu Anda belajar, membuat, dan berinovasi!

Dasar-dasar Struktur Data

Struktur data dapat diklasifikasikan ke dalam tipe dasar berikut:

• Array
• Daftar Tertaut
• tumpukan
• antrian
• pohon
• Tabel hash
• Grafik

Memilih pengaturan yang sesuai untuk data Anda merupakan bagian integral dari pemrograman dan proses pemecahan masalah. Dan Anda dapat mengamati bahwa struktur data mengatur tipe data abstrak dalam implementasi konkret. Untuk mencapai hasil itu, mereka menggunakan berbagai algoritma, seperti pengurutan, pencarian, dll. Mempelajari struktur data adalah salah satu bagian penting dalam kursus ilmu data.

Dengan munculnya data besar dan analitik, mempelajari dasar-dasar ini menjadi hampir penting bagi para ilmuwan data. Pelatihan biasanya menggabungkan berbagai proyek struktur data untuk memungkinkan sintesis pengetahuan dari pengalaman kehidupan nyata. Berikut adalah daftar topik untuk Anda mulai!

Ide Proyek Struktur Data

1. Pohon pencarian biner yang tidak jelas

Item, seperti nama, nomor, dll. dapat disimpan dalam memori dalam urutan yang diurutkan yang disebut pohon pencarian biner atau BST. Dan beberapa dari struktur data ini dapat secara otomatis menyeimbangkan ketinggiannya ketika item sewenang-wenang dimasukkan atau dihapus. Oleh karena itu, mereka dikenal sebagai BST self-balancing. Lebih lanjut, ada implementasi yang berbeda dari tipe ini, seperti BTrees, pohon AVL, dan pohon merah-hitam. Tetapi ada banyak eksekusi lain yang kurang dikenal yang dapat Anda pelajari. Beberapa contoh termasuk pohon AA, 2-3 pohon, pohon splay, pohon kambing hitam, dan treaps.

Anda dapat mendasarkan proyek Anda pada alternatif ini dan mengeksplorasi bagaimana mereka dapat mengungguli BST lain yang banyak digunakan dalam skenario yang berbeda. Misalnya, pohon splay dapat terbukti lebih cepat daripada pohon merah-hitam dalam kondisi lokalitas temporal yang serius.

2. BST mengikuti algoritma memoization

Memoisasi terkait dengan pemrograman dinamis. Dalam BST memoizing reduksi, setiap node dapat memoize fungsi dari subtree-nya. Perhatikan contoh BST orang yang diurutkan berdasarkan usia mereka. Sekarang, biarkan node anak menyimpan pendapatan maksimum setiap individu. Dengan struktur ini, Anda dapat menjawab pertanyaan seperti, “Berapa pendapatan maksimum orang berusia antara 18,3 dan 25,3?” Itu juga dapat menangani pembaruan dalam waktu logaritmik.

Selain itu, struktur data seperti itu mudah dilakukan dalam bahasa C. Anda juga dapat mencoba mengikatnya dengan Ruby dan API yang nyaman. Gunakan antarmuka yang memungkinkan Anda menentukan 'lambda' sebagai fungsi pemesanan dan fungsi memoisasi subpohon Anda. Secara keseluruhan, Anda dapat mengharapkan BST memoisasi pengurangan menjadi BST yang menyeimbangkan diri dengan sedikit pembukuan tambahan.

Checkout: Jenis Pohon Biner

3. Waktu penyisipan tumpukan

Saat mencari proyek struktur data , Anda ingin menemukan masalah berbeda yang diselesaikan dengan pendekatan kreatif. Salah satu pertanyaan penelitian unik tersebut menyangkut waktu penyisipan kasus rata-rata untuk struktur data tumpukan biner. Menurut beberapa sumber online, ini adalah waktu konstan, sementara yang lain menyiratkan bahwa ini adalah waktu log(n).

Tetapi Bollobas dan Simon memberikan jawaban yang didukung secara numerik dalam makalah mereka yang berjudul, “Penyisipan acak berulang ke dalam antrian prioritas.” Pertama, mereka mengasumsikan skenario di mana Anda ingin memasukkan n elemen ke dalam tumpukan kosong. Mungkin ada 'n!' kemungkinan pesanan untuk hal yang sama. Kemudian, mereka mengadopsi pendekatan biaya rata-rata untuk membuktikan bahwa waktu penyisipan terikat oleh konstanta 1,7645.

4. Treap optimal dengan parameter pengubah prioritas

Treaps adalah kombinasi dari BSTs dan heaps. Struktur data acak ini melibatkan penetapan prioritas khusus ke node. Anda dapat memilih proyek yang mengoptimalkan serangkaian parameter di bawah pengaturan yang berbeda. Misalnya, Anda dapat mengatur preferensi yang lebih tinggi untuk node yang diakses lebih sering daripada yang lain. Di sini, setiap akses akan memicu proses dua kali lipat:

• Memilih nomor acak
• Mengganti prioritas node dengan nomor tersebut jika ditemukan lebih tinggi dari prioritas sebelumnya

Sebagai hasil dari modifikasi ini, pohon akan kehilangan bentuk acaknya. Tampaknya node yang sering diakses sekarang berada di dekat akar pohon, sehingga menghasilkan pencarian yang lebih cepat. Jadi, bereksperimenlah dengan struktur data ini dan coba mendasarkan argumen Anda pada bukti.

Di akhir proyek, Anda dapat membuat penemuan orisinal atau bahkan menyimpulkan bahwa mengubah prioritas node tidak memberikan banyak kecepatan. Bagaimanapun, ini akan menjadi latihan yang relevan dan berguna.

5. Proyek penelitian tentang pohon kd

Pohon k-dimensi atau pohon kd mengatur dan mewakili data spasial. Struktur data ini memiliki beberapa aplikasi, terutama dalam pencarian kunci multi-dimensi seperti pencarian tetangga dan jangkauan terdekat. Berikut adalah bagaimana pohon kd beroperasi:

• Setiap simpul daun dari pohon biner adalah titik k-dimensi
• Setiap node non-daun membagi hyperplane (yang tegak lurus terhadap dimensi itu) menjadi dua setengah ruang
• Subtree kiri dari node tertentu mewakili titik-titik di sebelah kiri hyperplane. Demikian pula, subpohon kanan dari simpul itu menunjukkan titik-titik di bagian kanan.

Anda dapat menyelidiki satu langkah lebih jauh dan membuat pohon kd self-balanced di mana setiap simpul daun akan memiliki jarak yang sama dari akar. Selain itu, Anda dapat mengujinya untuk menemukan apakah pohon seimbang tersebut terbukti optimal untuk jenis aplikasi tertentu.

Dengan ini, kami telah membahas lima ide menarik yang dapat Anda pelajari, selidiki, dan coba. Sekarang, mari kita lihat beberapa proyek lagi tentang struktur data dan algoritma.

Baca: Gaji Data Scientist di India

6. Perjuangan Ksatria

Dalam proyek ini, kita akan memahami dua algoritma yang sedang bekerja – BFS dan DFS. BFS adalah singkatan dari Breadth-First Search dan menggunakan struktur data Antrian untuk menemukan jalur terpendek. Sedangkan, DFS mengacu pada Depth-First Search dan melintasi struktur data Stack.

Sebagai permulaan, Anda memerlukan struktur data yang mirip dengan pohon biner. Sekarang, anggaplah Anda memiliki papan catur standar 8 X 8, dan Anda ingin menunjukkan gerakan ksatria dalam permainan. Seperti yang Anda ketahui, gerakan dasar ksatria dalam catur adalah dua langkah ke depan dan satu langkah ke samping. Menghadap ke segala arah dan diberi belokan yang cukup, ia dapat berpindah dari kotak mana pun di papan ke kotak lainnya.

Jika Anda ingin mengetahui cara paling sederhana ksatria Anda dapat berpindah dari satu kotak (atau simpul) ke kotak lain dalam pengaturan dua dimensi, pertama-tama Anda harus membuat fungsi seperti di bawah ini.

• knight_plays([0,0], [1,2]) == [[0,0], [1,2]]
• knight_plays([0,0], [3,3]) == [[0,0], [1,2], [3,3]]
• knight_plays([3,3], [0,0]) == [[3,3], [1,2], [0,0]]

Selanjutnya, proyek ini akan membutuhkan tugas-tugas berikut:

• Membuat skrip untuk permainan papan dan malam
• Memperlakukan semua kemungkinan gerakan ksatria sebagai anak-anak dalam struktur pohon
• Memastikan bahwa setiap gerakan tidak keluar dari papan
• Memilih algoritma pencarian untuk menemukan jalur terpendek dalam kasus ini
• Menerapkan algoritma pencarian yang sesuai untuk menemukan kemungkinan perpindahan terbaik dari kotak awal ke kotak akhir.

7. Struktur data cepat dalam bahasa sistem non-C

Pemrogram biasanya membangun program dengan cepat menggunakan bahasa tingkat tinggi seperti Ruby atau Python tetapi mengimplementasikan struktur data dalam C/C++. Dan mereka membuat kode yang mengikat untuk menghubungkan elemen. Namun, bahasa C diyakini rawan kesalahan, yang juga dapat menyebabkan masalah keamanan. Di sinilah letak ide proyek yang menarik.

Anda dapat menerapkan struktur data dalam bahasa tingkat rendah modern seperti Rust atau Go, lalu mengikat kode Anda ke bahasa tingkat tinggi. Dengan proyek ini, Anda dapat mencoba sesuatu yang baru dan juga mengetahui cara kerja binding. Jika upaya Anda berhasil, Anda bahkan dapat menginspirasi orang lain untuk melakukan latihan serupa di masa mendatang dan mendorong orientasi kinerja struktur data yang lebih baik.

Baca juga: Ide Proyek Ilmu Data untuk Pemula

8. Mesin pencari untuk struktur data

Perangkat lunak ini bertujuan untuk mengotomatisasi dan mempercepat pilihan struktur data untuk API tertentu. Proyek ini tidak hanya mendemonstrasikan cara baru untuk merepresentasikan struktur data yang berbeda tetapi juga mengoptimalkan serangkaian fungsi untuk melengkapi inferensi pada struktur data tersebut. Kami telah menyusun ringkasannya di bawah ini.

• Proyek mesin pencari struktur data membutuhkan pengetahuan tentang struktur data dan hubungan antara metode yang berbeda.
• Ini menghitung waktu yang dibutuhkan oleh setiap struktur data komposit yang mungkin untuk semua metode.
• Akhirnya, ia memilih struktur data terbaik untuk kasus tertentu.

Baca: Ide Proyek Data Mining

9. Aplikasi direktori telepon menggunakan daftar tertaut ganda

Proyek ini dapat mendemonstrasikan cara kerja aplikasi buku kontak dan juga mengajari Anda tentang struktur data seperti array, daftar tertaut, tumpukan, dan antrian. Biasanya, manajemen buku telepon mencakup operasi pencarian, pengurutan, dan penghapusan. Sebuah fitur khas dari permintaan pencarian di sini adalah bahwa pengguna melihat saran dari daftar kontak setelah memasukkan setiap karakter. Anda dapat membaca kode sumber proyek yang tersedia secara bebas dan meniru yang sama untuk mengembangkan keterampilan Anda.

10. Pengindeksan spasial dengan quadtrees

Struktur data quadtree adalah tipe khusus dari struktur pohon, yang secara rekursif dapat membagi ruang 2-D datar menjadi empat kuadran. Setiap simpul hierarkis dalam struktur pohon ini memiliki nol atau empat anak. Ini dapat digunakan untuk berbagai tujuan seperti penyimpanan data yang jarang, pemrosesan gambar, dan pengindeksan spasial.

Pengindeksan spasial adalah tentang eksekusi yang efisien dari kueri geometris terpilih, yang membentuk bagian penting dari desain aplikasi geo-spasial. Misalnya, aplikasi berbagi perjalanan seperti Ola dan Uber memproses kueri geografis untuk melacak lokasi taksi dan memberikan pembaruan kepada pengguna. Fitur Teman Terdekat Facebook juga memiliki fungsi serupa. Di sini, meta-data terkait disimpan dalam bentuk tabel, dan indeks spasial dibuat secara terpisah dengan koordinat objek. Tujuan masalahnya adalah untuk menemukan titik terdekat dengan titik tertentu.

Anda dapat mengejar proyek struktur data quadtree di berbagai bidang, mulai dari pemetaan, perencanaan kota, dan perencanaan transportasi hingga manajemen dan mitigasi bencana. Kami telah memberikan garis besar singkat untuk mendorong keterampilan pemecahan masalah dan analitis Anda.

Tujuan: Membuat struktur data yang memungkinkan operasi berikut:

• Masukkan lokasi atau ruang geometris
• Cari koordinat lokasi tertentu
• Hitung jumlah lokasi dalam struktur data di area tertentu yang berdekatan

11. Proyek berbasis grafik pada struktur data

Anda dapat mengambil proyek tentang penyortiran topologi grafik. Untuk ini, Anda memerlukan pengetahuan sebelumnya tentang algoritma DFS. Inilah perbedaan utama antara kedua pendekatan:

• Kami mencetak sebuah simpul & kemudian secara rekursif memanggil algoritma untuk simpul yang berdekatan di DFS.
• Dalam penyortiran topologi, pertama-tama kita memanggil algoritma untuk simpul yang berdekatan secara rekursif. Dan kemudian, kami mendorong konten ke dalam tumpukan untuk dicetak.

Oleh karena itu, algoritma pengurutan topologi mengambil grafik asiklik terarah atau DAG untuk mengembalikan array node.

Mari kita perhatikan contoh sederhana memesan resep pancake. Untuk membuat panekuk, Anda memerlukan seperangkat bahan tertentu, seperti telur, susu, tepung atau campuran panekuk, minyak, sirup, dll. Informasi ini, bersama dengan jumlah dan porsinya, dapat dengan mudah direpresentasikan dalam grafik.

Tetapi sama pentingnya untuk mengetahui urutan yang tepat dari penggunaan bahan-bahan ini. Di sinilah Anda dapat menerapkan pemesanan topologi. Contoh lain termasuk membuat bagan prioritas untuk mengoptimalkan kueri basis data dan jadwal untuk proyek perangkat lunak. Berikut adalah ikhtisar proses untuk referensi Anda:

• Panggil algoritma DFS untuk struktur data graf untuk menghitung waktu selesai untuk simpul
• Simpan simpul dalam daftar dengan urutan waktu selesai menurun
• Jalankan pengurutan topologi untuk mengembalikan daftar yang dipesan

12. Representasi numerik dengan daftar akses acak

Dalam representasi yang telah kita lihat di masa lalu, elemen numerik umumnya disimpan di Tumpukan Binomial. Tetapi pola-pola ini juga dapat diimplementasikan dalam struktur data lainnya. Okasaki telah datang dengan teknik representasi numerik menggunakan daftar akses acak biner. Daftar ini memiliki banyak keuntungan:

• Mereka memungkinkan penyisipan dan penghapusan dari awal
• Mereka mengizinkan akses dan pembaruan pada indeks tertentu

Ketahui lebih lanjut: Enam Struktur Data yang Paling Umum Digunakan di R

13. Editor teks berbasis tumpukan

Editor teks biasa Anda memiliki fungsi mengedit dan menyimpan teks saat sedang ditulis atau diedit. Jadi, ada beberapa perubahan pada posisi kursor. Untuk mencapai efisiensi tinggi, kami memerlukan struktur data yang cepat untuk penyisipan dan modifikasi. Dan array karakter biasa membutuhkan waktu untuk menyimpan string.

Anda dapat bereksperimen dengan struktur data lain seperti buffer celah dan tali untuk menyelesaikan masalah ini. Tujuan akhir Anda adalah untuk mencapai penggabungan yang lebih cepat daripada string biasa dengan menempati ruang memori yang lebih kecil.

Kesimpulan

Keterampilan struktur data membentuk landasan pengembangan perangkat lunak, terutama dalam hal mengelola kumpulan data besar dalam ekosistem digital saat ini. Perusahaan terkemuka seperti Adobe, Amazon, dan Google merekrut berbagai posisi pekerjaan yang menguntungkan dalam struktur data dan domain algoritma. Dan dalam wawancara, perekrut tidak hanya menguji pengetahuan teoretis Anda, tetapi juga keterampilan praktis Anda. Jadi, praktikkan proyek struktur data di atas untuk mewujudkannya!

Jika Anda penasaran untuk belajar tentang ilmu data, lihat Program PG Eksekutif IIIT-B & upGrad dalam Ilmu Data yang dibuat untuk para profesional yang bekerja dan menawarkan 10+ studi kasus & proyek, lokakarya praktis, bimbingan dengan pakar industri, 1 -on-1 dengan mentor industri, 400+ jam pembelajaran dan bantuan pekerjaan dengan perusahaan-perusahaan top.