2. ในกรณีของ Binomial coefficient เมื่อใช้ Dynamic Programming
a. จงหา space efficiency ในเทอมของ O(n)
b. จงหา O(n) สำหรับการคำนวณกรณีต่อไปนี้ C(n,1) C(n,2) C(n,n/2) เมื่อ n เป็นจำนวนคู่
c. จงเขียนโค้ดเมื่ออินพลีเมนต์ ด้วยวิธี Memorization
3. พิจารณาโค้ดต่อไปนี้ และหาจำนวนครั้งของการบวกที่เกิดขึ้น
Binom (n,k)
........if (k==0) or (k==n) return 1;
........else return Binom(n-1,k-1) + Binom(n-1,k);
4. จากกราฟต่อไปนี้
|0 1 0 0|
|0 0 1 0|
|0 0 0 1|
|0 0 0 0|
ให้ใช้ Warshall Algorithm ในการหา transitive closure และเขียนโปรแกรมเพื่อทดสอบผลการทำงาน
5. จงออกแบบอัลกอริธีมที่มีประสิทธิภาพในการหา longest path ใน DAG
6. พิจารณากราฟต่อไปนี้
๐ จงใช้ prim algorithm ในการหา MST
๐ จงใช้ Kruskal algorithm ในการหา MST
7. codeword ที่ยาวที่สุดที่เป็นไปได้สำหรับการใช้ huffman coding กับ alphabet n ตัว คือเท่าไร
ไม่มีความคิดเห็น:
แสดงความคิดเห็น