Fall 2019 ITCS 8114 AlgoDS

Fall-2019-ITCS-8114-Algods

Repositori ini berisi proyek dan penugasan tentu saja "ITCS 6114/8114: Algoritma dan Struktur Data" . Kursus ini telah diambil pada musim gugur 2019 semester, sebagai bagian dari gelar PhD saya di UNC Charlotte.

Daftar Proyek

• Proyek 1: Algoritma penyortiran berbasis perbandingan
• Proyek 2: Algoritma Grafik (Singles-Source Shortest Path dan Minimum Spanning Tree)
• Proyek 3: Algoritma pencocokan pola

Di bawah ini Anda akan menemukan deskripsi dan persyaratan proyek. Untuk mendapatkan detailnya, silakan buka direktori proyek yang sesuai.

Proyek 1: Algoritma penyortiran berbasis perbandingan

---

Terapkan algoritma penyortiran berikut dan bandingkan. Anda dapat menggunakan bahasa pemrograman apa pun (misalnya C/C ++, Java, Python, C#). Dalam proyek ini, Anda dapat bekerja sendiri atau sebagai tim dua.

1. Sort Penyisipan
2. Gabungan
3. Heapsort [berbasis vektor, dan masukkan satu item sekaligus]
4. In-place quicksort (item acak atau item pertama atau item terakhir dari input Anda dapat berupa pivot).
5. Quicksort yang dimodifikasi
   • Gunakan median-of-tiga sebagai pivot.
   • Untuk sub-masalah kecil ukuran <= 10, gunakan sortir penyisipan.

Instruksi eksekusi:

1. Jalankan algoritma ini untuk ukuran input yang berbeda (misalnya N = 1000, 2000, 4000, 5000, 10000 .. 40000, 50000). Anda akan secara acak menghasilkan angka untuk array input Anda. Catat waktu eksekusi (perlu mengambil rata -rata seperti yang dibahas di kelas) dan plot semuanya dalam satu grafik terhadap ukuran input. Perhatikan bahwa Anda akan membandingkan algoritma penyortiran ini untuk set data yang sama.
2. Juga mengamati dan menyajikan kinerja dari dua kasus khusus berikut:
   • Array input sudah diurutkan.
   • Array input disortir secara terbalik.

Skema penilaian:

Instruksi pengiriman:

• Unggah kanvas
  1. Laporan yang diformat dengan baik yang mencakup struktur data yang dipilih, analisis kompleksitas, hasil dan kode.
  2. Unggah kode program untuk dieksekusi. Pastikan Anda memberikan readme untuk TA.
• Selain itu, hardcopy laporan tanpa kode kepada saya di kelas.

Proyek 2: Algoritma Grafik (Singles-Source Shortest Path dan Minimum Spanning Tree)

---

Dalam proyek ini, Anda akan menerapkan dua algoritma grafik yang disebutkan di bawah ini. Catatan: Anda dapat bekerja sendiri atau dalam tim yang terdiri dari dua maks.

Masalah 1: Temukan pohon jalur terpendek di grafik terarah yang diarahkan dan tidak diarahkan untuk simpul sumber yang diberikan. Asumsikan tidak ada tepi negatif dalam grafik Anda. Anda akan mencetak setiap jalur dan biaya jalur untuk sumber yang diberikan.

Masalah 2: Diberikan grafik yang terhubung, tidak terarah, tertimbang, temukan pohon spanning menggunakan tepi yang meminimalkan berat total? (?) = ∑ _{(u, v) ∈T} ? (?,?). Gunakan algoritma Kruskal untuk menemukan minimum spanning tree (MST). Anda akan mencetak tepi pohon dan total biaya jawaban Anda.

Format Input: Untuk setiap masalah, Anda akan mengambil input dari file teks. Katakanlah Anda ingin menjalankan algoritma pada grafik yang tidak diarahkan berikut. Format file yang sesuai adalah:

 6  10 U
A  B  1
A  C  2
B  C  1
B  D  3
B  E  2
C  D  1
C  E  2
D  E  4
D  F  3
E  F  3
A

Di sini, dua angka pertama mewakili jumlah simpul dan tepi. Huruf U adalah singkatan dari grafik yang tidak diarahkan (D untuk diarahkan). Dari baris kedua, ia menyebutkan semua tepi dan beratnya (misalnya ???? (?,?) Dan bobotnya 1. Baris terakhir adalah opsional. Jika diberikan, itu mewakili simpul sumber.

Instruksi pengiriman:

• Laporan yang diformat dengan baik yang mencakup deskripsi singkat dari setiap algoritma, struktur data yang dipilih, runtime kode Anda, input/output sampel, instruksi untuk menjalankan program Anda dengan mudah.
• Untuk setiap masalah, jalankan program Anda untuk empat grafik pilihan Anda yang berbeda. Gunakan penilaian Anda untuk mendefinisikan grafik uji yang menurut Anda menarik dan masuk akal. Misalnya:
• Grafik tidak terarah: setidaknya 7 node dan 12 tepi
• Grafik terarah: setidaknya 7 node dan 15 tepi
• Kode bersih untuk dieksekusi TA.
• Anda dapat menggunakan bahasa pemrograman apa pun (misalnya C/C ++, Java, Python, dll.)
• Jika bekerja di tim, kedua anggota diharuskan mengirimkan semuanya secara terpisah.
• Hardcopy laporan Anda kepada saya secara langsung; satu salinan per tim.

Skema penilaian:

Proyek 3: Algoritma pencocokan pola

---

Catatan: Anda dapat bekerja sendiri atau dalam tim yang terdiri dari tiga maks.

Untuk tugas ini, Anda hanya akan menerapkan tiga algoritma pencocokan pola pilihan Anda dari daftar yang diberikan di bawah ini.

• Algoritma brute-force
• Algoritma Boyer-Moore-Horspool
• Algoritma Knuth-Morris-Pratt
• Algoritma Boyer-Moore
• Otomatisasi terbatas untuk pencocokan pola

Percobaan:

• Bandingkan tiga algoritma untuk beberapa teks dan pola input yang berbeda; setidaknya 10 kasus berbeda
• Sebutkan jumlah perbandingan yang diperlukan dalam tabel untuk setiap kasus, untuk setiap algoritma

Penyerahan:

• Laporan yang diformat dengan baik yang mencakup deskripsi singkat dari setiap algoritma, struktur data yang digunakan, runtime kode Anda, input/output sampel, instruksi untuk menjalankan program Anda dengan mudah.
• Kode bersih untuk dieksekusi TA.
• Anda dapat menggunakan bahasa pemrograman apa pun (misalnya C/C ++, Java, Python, dll.)
• Jika bekerja di tim, kedua anggota itu diminta untuk mengirimkan semuanya secara terpisah.
• Hardcopy dari laporan Anda kepada saya secara langsung; satu salinan per tim.

Skema penilaian:

• 3 x 15 = 45 poin: Untuk menerapkan tiga algoritma
• 20 poin: untuk percobaan
• 10 poin: Laporkan