วันนี้ผมจะขอนำโจทย์ในวิชา data structure จากหนังสือ data structure & algorithm in python มาอธิบายครับ ทั้งนี้ผู้อ่านควรมีความรู้พื้นฐานในรายวิชากันมาบ้างแล้ว แล้วจึงมาทำความเข้าใจโจทย์ประยุกต์เหล่านี้ ผู้เขียนหวังว่าบทความนี้จะมีประโยชน์ไม่มากก็น้อยครับ
R-8.3 Give a justification of Proposition 8.4.
จากโจทย์เขาให้เรามาให้เหตุผลใน ข้อ 8.4 นะครับ
What is the running time of a call to T. height(p) when called on a position p distinct from the root of T? (See Code Fragment 8.5.)
จากโจทย์ข้อ 8.4 ระยะเวลารันที่เรียกใช้ ฟังชั่น T.height(p) เมื่อ p ไม่ได้อยู่ที่ root ของ t (ดูจาก Code Fragment 8.5)
เราจะใช้ function height ก็ตอนที่เราต้องการทราบถึงตำแหน่งของ Node แต่ละ Node
C-8.58 Let T be a tree with n positions. Define the lowest common ancestor (LCA) between two positions p and q as the lowest position in T that has both p and q as descendants (where we allow a position to be a descendant of itself). Given two positions p and q, describe an efficient algorithm for finding the LCA of p and q. What is the running time of your algorithm?
จากโจทย์ ให้สร้าง tree และกำหนดให้ Lowest common ancestor (LCA) ระหว่าง 2 ตำแหน่ง p,q และในตำแหน่งต่ำสุดของ Tree จะเป็นลูกหลานของ p,q ก็ได้ และอธิบายการหา LCA
จากโค้ดเราก็จะสร้าง Tree ได้ตามรูปข้างล่าง
LCA ของ 4,5 ก็คือ 2 LCA ของ 4,6 ก็คือ 1 LCA ของ 3,4 ก็คือ 1 LCA ของ 2,4 ก็คือ 2
R-12.14 Following our analysis of randomized quick-sort in Section 12.3.1, show that the probability that a given input element x belongs to more than 2logn subproblems in size group i is at most 1/n2. จากโจทย์ให้เราทำ Quick sort แบบที่เขาอธิบายใน section 12.3.1 แล้วแสดงค่าถ้าให้ input ค่า x มากกว่า 2logn ในกลุ่ม i ต้องมีมากกว่า 1/n2
นี่ก็คือ Code Algorithm ขอ Quick Sort นะครับ เราสามารถตัวเลขที่เราต้องการเรียงได้เลยครับ
C-12.53 Read documenation of the reverse keyword parameter of Python’s sorting functions, and describe how the decorate-sort-undecorate paradigm could be used to implement it, without assuming anything about the key type.
รูปด้านบนก็จะเป็น Code ตัวอย่างของการ decorate แต่ละ element กับ undecorate แต่ละ element นะครับ
R-14.29 Repeat Exercise R-14.28 for Figure 14.8 that illustrates a directed DFS traversal.
Describe the meaning of the graphical conventions used in Figure 14.8 illustrating a DFS traversal. What do the line thicknesses signify? What do the arrows signify? How about dashed lines?
จากโจทย์ถามว่า จาก illustrating a DFS traversal. เส้นทีบในรูป หัวลูกศร หรือ เส้นปะคืออะไร
เส้นทึบ คือ discovery edge หรือ tree edge
เส้นปะ คือ เส้นที่เชื่อมต่อกับ ancestor ใน DFS Tree
หัวลูกศร คือ ตำแหน่งที่บอกว่าจากปลายลูกศรเดินทางไปยังหัวลูกศร
C-14.65 Show that if all the weights in a connected weighted graph G are distinct, then there is exactly one minimum spanning tree for G.
จากโจทย์ ให้เราแสดงว่าถ้า น้ำหนักในการเชื่อมต่อกันที่ การฟ G ที่ต่างกันใน minimum spanning tree
หลักการคือ กำหนดให้หลักการหาเรียกว่า MST (minimum spanning tree ) ตามโครงสร้าง กราฟ data structure และ the order of the edges when ordered by weight. ให้สมมติว่า MST A ไม่ซ้ำกันเลย และมีอีก spanning tree ที่น้ำหนักเท่ากันหมด (MST B) ให้ e1 ไปอยู่ใน A แต่ไม่อยู่ใน B และ B ควรมี e2 อย่างน้อยที่ไม่ได้อยู่ใน A และกำหนดใน e1 น้ำหนักน้อยกว่า e2 เนื่องจาก B เป็น MST, {e1} B จึงจ้องมี cycle และแทนที่ e2 ด้วย e1 ผลใน B ก็คือ {e1} B – {e2} ซึ่งทำให้มีน้ำหนักน้อยกว่าเมื่อเทียบกับ B ข้อขัดแย้งคือ เมื่อเราถือว่า B เป็น minimum spanning tree แต่มันกลับไม่เป็นเช่นนั้น
สามารถดู Video เพิ่มเติมได้ทางด้านล่างครับ
