Fall 2019 ITCS 8114 AlgoDS

FARD-2019-ITCS-8114-Algods

يحتوي هذا المستودع على المشاريع والواجبات بالطبع "ITCS 6114/8114: الخوارزميات وهياكل البيانات" . تم أخذ هذه الدورة في فصل الخريف 2019 ، كجزء من درجة الدكتوراه في UNC Charlotte.

قائمة المشروع

• المشروع 1: خوارزميات الفرز المستندة إلى المقارنة
• المشروع 2: خوارزميات الرسم البياني (أقصر مسار الفردي المصدر والحد الأدنى من شجرة الامتداد)
• المشروع 3: خوارزميات مطابقة الأنماط

ستجد أدناه وصف ومتطلبات المشاريع. للحصول على التفاصيل ، يرجى الانتقال إلى دليل المشروع المقابل.

المشروع 1: خوارزميات الفرز المستندة إلى المقارنة

---

تنفيذ خوارزميات الفرز التالية ومقارنتها. يمكنك استخدام أي لغة برمجة (على سبيل المثال C/C ++ ، Java ، Python ، C#). في هذا المشروع ، يمكنك العمل بمفردك أو كفريق واحد.

1. نوع الإدراج
2. دمج الفرز
3. Heapsort [على أساس المتجه ، وأدخل عنصرًا واحدًا في وقت واحد]
4. في مكان Quicksort (أي عنصر عشوائي أو العنصر الأول أو الأخير من إدخالك يمكن أن يكون محورًا).
5. تعديل Quicksort
   • استخدم متوسط ​​ثلاثة كمحور.
   • بالنسبة لمشكلات فرعية صغيرة من الحجم <= 10 ، استخدم نوع الإدراج.

تعليمات التنفيذ:

1. قم بتشغيل هذه الخوارزميات لأحجام المدخلات المختلفة (على سبيل المثال N = 1000 ، 2000 ، 4000 ، 5000 ، 10000 .. 40000 ، 50000). ستقوم بإنشاء أرقام بشكل عشوائي لمجموعة الإدخال الخاصة بك. سجل وقت التنفيذ (بحاجة إلى أخذ المتوسط ​​كما هو موضح في الفصل) ورسمها جميعًا في رسم بياني واحد مقابل حجم الإدخال. لاحظ أنك ستقارن خوارزميات الفرز هذه لنفس مجموعة البيانات.
2. لاحظ أيضًا والأداء الحالي للحالتين الخاصتين التاليتين:
   • تم فرز صفيف الإدخال بالفعل.
   • يتم فرز مجموعة الإدخال بشكل عكسي.

مخطط الدرجات:

تعليمات التقديم:

• تحميل قماش
  1. تقرير جيد التنسيق يغطي هياكل البيانات المختارة وتحليل التعقيد والنتائج والرمز.
  2. تحميل رمز البرنامج للتنفيذ. تأكد من تقديم ReadMe لـ TA.
• بالإضافة إلى ذلك ، فصوص التقرير بدون رمز لي في الفصل.

المشروع 2: خوارزميات الرسم البياني (أقصر مسار الفردي المصدر والحد الأدنى من شجرة الامتداد)

---

في هذا المشروع ، سوف تقوم بتنفيذ خوارزميات رسم بياني المذكورة أدناه. ملاحظة: يمكنك العمل بمفردك أو في فريق من اثنين كحد أقصى.

المشكلة 1: ابحث عن أقصر شجرة مسار في كل من الرسوم البيانية المرجحة الموجهة وغير الموجهة لقمة رأس مصدر معينة. افترض أنه لا توجد ميزة سلبية في الرسم البياني الخاص بك. سوف تقوم بطباعة كل تكلفة مسار ومسار لمصدر معين.

المشكلة 2: بالنظر إلى رسم بياني متصل ، غير موجه ، مرجح ، ابحث عن شجرة تمتد باستخدام الحواف التي تقلل من الوزن الكلي؟ (؟) = ∑ _{(u ، v) ∈T} ؟ (؟ ،؟). استخدم خوارزمية Kruskal للعثور على الحد الأدنى من شجرة الامتداد (MST). سوف تقوم بطبع حواف الشجرة والتكلفة الإجمالية لإجابتك.

تنسيق الإدخال: لكل مشكلة ، ستأخذ إدخال من ملف نصي. قل أنك تريد تشغيل الخوارزمية على الرسم البياني التالي غير الموجود. سيكون تنسيق الملف المقابل:

 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

هنا ، يمثل الرقمين الأولين عدد القمم والحواف. الرسالة u تعني الرسم البياني غير الموجود (D للتوجيه). من السطر الثاني ، يذكر جميع الحواف ووزنه (على سبيل المثال ؟؟؟؟؟

تعليمات التقديم:

• تقرير جيد التنسيق يغطي وصفًا قصيرًا لكل خوارزمية ، بنية البيانات المختارة ، وقت تشغيل الكود الخاص بك ، عينة الإدخال/الإخراج ، تعليمات لتشغيل البرنامج بسهولة.
• لكل مشكلة ، قم بتشغيل البرنامج لأربعة رسومات بيانية مختلفة من اختيارك. استخدم حكمك لتحديد الرسوم البيانية للاختبار التي تعتقد أنها مثيرة للاهتمام ومعقولة. على سبيل المثال:
• رسم بياني غير موجه: ما لا يقل عن 7 عقد و 12 حواف
• الرسم البياني الموجه: ما لا يقل عن 7 عقد و 15 حواف
• رمز نظيف لتنفيذ TA.
• يمكنك استخدام أي لغة برمجة (على سبيل المثال C/C ++ ، Java ، Python ، إلخ)
• إذا عملت في فريق ، يتعين على كلا الأعضاء تقديم كل شيء بشكل منفصل.
• Hardcopy من تقريرك إلي مباشرة ؛ نسخة واحدة لكل فريق.

مخطط الدرجات:

المشروع 3: خوارزميات مطابقة الأنماط

---

ملاحظة: يمكنك العمل بمفردك أو في فريق من ثلاثة أقصى.

بالنسبة لهذه المهمة ، ستقوم بتنفيذ ثلاثة خوارزميات مطابقة أنماط فقط من اختيارك من القائمة الواردة أدناه.

• خوارزمية القوة الغاشمة
• Boyer-moore-horspool خوارزمية
• خوارزمية Knuth-Morris-Pratt
• خوارزمية بوير مور
• أتمتة محدودة لمطابقة الأنماط

تجربة:

• قارن ثلاث خوارزميات لعدة نص وأنماط إدخال مختلفة ؛ ما لا يقل عن 10 حالات مختلفة
• اذكر عدد المقارنات المطلوبة في جدول لكل حالة ، لكل خوارزمية

استسلام:

• تقرير جيد التنسيق يغطي وصفًا قصيرًا لكل خوارزمية ، بنية البيانات المستخدمة ، وقت تشغيل الكود ، عينة الإدخال/الإخراج ، تعليمات لتشغيل البرنامج بسهولة.
• رمز نظيف لتنفيذ TA.
• يمكنك استخدام أي لغة برمجة (على سبيل المثال C/C ++ ، Java ، Python ، إلخ)
• إذا عملت في فريق ، فلا يزال يتعين على كلا الأعضاء تقديم كل شيء بشكل منفصل.
• Hardcopyof تقريرك إلي مباشرة ؛ نسخة واحدة لكل فريق.

مخطط الدرجات:

• 3 × 15 = 45 نقطة: لتنفيذ ثلاث خوارزميات
• 20 نقطة: للتجربة
• 10 نقاط: تقرير