Fall 2019 ITCS 8114 AlgoDS

ฤดูใบไม้ร่วง -2019-ITCS-8114-Algods

ที่เก็บนี้มีโครงการและการมอบหมายแน่นอน "ITCS 6114/8114: อัลกอริทึมและโครงสร้างข้อมูล" หลักสูตรนี้ดำเนินการในภาคเรียนฤดูใบไม้ร่วงปี 2019 ซึ่งเป็นส่วนหนึ่งของปริญญาเอกของฉันที่ UNC Charlotte

รายชื่อโครงการ

• โครงการที่ 1: อัลกอริทึมการเรียงลำดับการเปรียบเทียบ
• โครงการที่ 2: อัลกอริทึมกราฟ (เส้นทางที่สั้นที่สุดของซิงเก
• โครงการที่ 3: อัลกอริทึมการจับคู่รูปแบบ

ด้านล่างคุณจะพบคำอธิบายและข้อกำหนดของโครงการ หากต้องการรับรายละเอียดโปรดไปที่ไดเรกทอรีโครงการที่เกี่ยวข้อง

โครงการที่ 1: อัลกอริทึมการเรียงลำดับการเปรียบเทียบ

---

ใช้อัลกอริทึมการเรียงลำดับต่อไปนี้และเปรียบเทียบ คุณสามารถใช้ภาษาการเขียนโปรแกรมใด ๆ (เช่น C/C ++, Java, Python, C#) ในโครงการนี้คุณสามารถทำงานคนเดียวหรือเป็นทีมสองคน

1. เรียงลำดับ
2. การเรียงลำดับ
3. HEAPSORT [ใช้เวกเตอร์และแทรกหนึ่งรายการในแต่ละครั้ง]
4. In-place Quicksort (รายการสุ่มใด ๆ หรือรายการแรกหรือรายการสุดท้ายของอินพุตของคุณสามารถหมุนได้)
5. ดัดแปลง Quicksort
   • ใช้ค่ามัธยฐานของสามเป็นเดือย
   • สำหรับขนาดย่อยขนาดเล็กที่มีขนาด <= 10 ให้ใช้การเรียงลำดับการแทรก

คำแนะนำการดำเนินการ:

1. เรียกใช้อัลกอริทึมเหล่านี้สำหรับขนาดอินพุตที่แตกต่างกัน (เช่น n = 1,000, 2000, 4000, 5000, 10,000 .. 40000, 50000) คุณจะสุ่มสร้างหมายเลขสำหรับอาร์เรย์อินพุตของคุณ บันทึกเวลาดำเนินการ (จำเป็นต้องใช้ค่าเฉลี่ยตามที่กล่าวไว้ในชั้นเรียน) และพล็อตทั้งหมดในกราฟเดียวกับขนาดอินพุต โปรดทราบว่าคุณจะเปรียบเทียบอัลกอริทึมการเรียงลำดับเหล่านี้สำหรับชุดข้อมูลเดียวกัน
2. นอกจากนี้ยังสังเกตและแสดงผลงานปัจจุบันของสองกรณีพิเศษต่อไปนี้:
   • อาร์เรย์อินพุตถูกเรียงลำดับแล้ว
   • อาร์เรย์อินพุตถูกเรียงลำดับย้อนกลับ

รูปแบบการให้คะแนน:

คำแนะนำในการส่ง:

• การอัปโหลดผ้าใบ
  1. รายงานที่มีรูปแบบดีครอบคลุมโครงสร้างข้อมูลที่เลือกการวิเคราะห์ความซับซ้อนผลลัพธ์และรหัส
  2. อัปโหลดรหัสโปรแกรมสำหรับการดำเนินการ ตรวจสอบให้แน่ใจว่าคุณให้ readme สำหรับ TA
• นอกจากนี้รายงานสำเนารายงานที่ไม่มีรหัสให้ฉันในชั้นเรียน

โครงการที่ 2: อัลกอริทึมกราฟ (เส้นทางที่สั้นที่สุดของซิงเก

---

ในโครงการนี้คุณจะใช้อัลกอริทึมกราฟสองตัวที่กล่าวถึงด้านล่าง หมายเหตุ: คุณสามารถทำงานคนเดียวหรือในทีมสูงสุดสองคน

ปัญหาที่ 1: ค้นหาแผนผังเส้นทางที่สั้นที่สุดในกราฟทั้งแบบกำกับและไม่ได้บอกทิศทางสำหรับจุดยอดแหล่งที่กำหนด สมมติว่าไม่มีขอบลบในกราฟของคุณ คุณจะพิมพ์แต่ละเส้นทางและค่าใช้จ่ายเส้นทางสำหรับแหล่งที่มา

ปัญหาที่ 2: ให้กราฟที่เชื่อมต่อ, ไม่ได้ทิศทาง, ถ่วงน้ำหนัก, ค้นหาต้นไม้ที่ทอดยาวโดยใช้ขอบที่ลดน้ำหนักทั้งหมดหรือไม่ (?) = ∑ _{(u, v) ∈T} ? (?,?) ใช้อัลกอริทึม Kruskal เพื่อค้นหา Tree -Spanning Tree ขั้นต่ำ (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 สำหรับกำกับ) จากบรรทัดที่สองมันกล่าวถึงขอบทั้งหมดและน้ำหนักของมัน (เช่น ???? (?,?) และน้ำหนักของมันคือ 1 บรรทัดสุดท้ายเป็นตัวเลือกถ้าได้รับมันแสดงถึงโหนดต้นทาง

คำแนะนำในการส่ง:

• รายงานที่มีรูปแบบดีครอบคลุมคำอธิบายสั้น ๆ ของอัลกอริทึมแต่ละตัวโครงสร้างข้อมูลที่เลือกรันไทม์ของรหัสของคุณอินพุต/เอาต์พุตตัวอย่างคำสั่งเพื่อเรียกใช้โปรแกรมของคุณได้อย่างง่ายดาย
• สำหรับแต่ละปัญหาให้เรียกใช้โปรแกรมของคุณสำหรับกราฟสี่แบบที่คุณเลือก ใช้การตัดสินของคุณเพื่อกำหนดกราฟทดสอบที่คุณคิดว่าน่าสนใจและสมเหตุสมผล ตัวอย่างเช่น:
• กราฟที่ไม่ได้กำกับ: อย่างน้อย 7 โหนดและ 12 ขอบ
• กราฟกำกับ: อย่างน้อย 7 โหนดและ 15 ขอบ
• ทำความสะอาดรหัสสำหรับ TA เพื่อดำเนินการ
• คุณสามารถใช้ภาษาการเขียนโปรแกรมใด ๆ (เช่น C/C ++, Java, Python ฯลฯ )
• หากทำงานในทีมสมาชิกทั้งสองจะต้องส่งทุกอย่างแยกกัน
• สำเนารายงานของคุณให้ฉันโดยตรง หนึ่งสำเนาต่อทีม

รูปแบบการให้คะแนน:

โครงการที่ 3: อัลกอริทึมการจับคู่รูปแบบ

---

หมายเหตุ: คุณสามารถทำงานคนเดียวหรือในทีมสูงสุดสามคน

สำหรับการมอบหมายนี้คุณจะใช้อัลกอริทึมการจับคู่รูปแบบเพียงสามแบบที่คุณเลือกจากรายการที่ระบุด้านล่าง

• อัลกอริธึมกำลังเดรัจฉาน
• อัลกอริทึม Boyer-Moore-Horspool
• อัลกอริทึม Knuth-Morris-Pratt
• อัลกอริทึม Boyer-Moore
• ระบบอัตโนมัติ จำกัด สำหรับการจับคู่รูปแบบ

การทดลอง:

• เปรียบเทียบอัลกอริทึมสามรายการสำหรับข้อความและรูปแบบอินพุตที่แตกต่างกัน อย่างน้อย 10 กรณีที่แตกต่างกัน
• พูดถึงจำนวนการเปรียบเทียบที่จำเป็นในตารางสำหรับแต่ละกรณีสำหรับแต่ละอัลกอริทึม

การส่ง:

• รายงานที่มีรูปแบบที่ดีซึ่งครอบคลุมคำอธิบายสั้น ๆ ของอัลกอริทึมแต่ละตัวโครงสร้างข้อมูลที่ใช้รันไทม์ของรหัสของคุณอินพุต/เอาต์พุตตัวอย่างคำสั่งเพื่อเรียกใช้โปรแกรมของคุณได้อย่างง่ายดาย
• ทำความสะอาดรหัสสำหรับ TA เพื่อดำเนินการ
• คุณสามารถใช้ภาษาการเขียนโปรแกรมใด ๆ (เช่น C/C ++, Java, Python ฯลฯ )
• หากทำงานในทีมสมาชิกทั้งสองยังต้องส่งทุกอย่างแยกกัน
• Hardcopyof รายงานของคุณให้ฉันโดยตรง หนึ่งสำเนาต่อทีม

รูปแบบการให้คะแนน:

• 3 x 15 = 45 คะแนน: สำหรับการใช้อัลกอริทึมสาม
• 20 คะแนน: สำหรับการทดลอง
• 10 คะแนน: รายงาน