[3 Pandhittaya] ฝึกทำโจทย์ Data Structures and Algorithms

วันนี้ผู้เขียนจะขอนำโจทย์ในวิชา data structure มาอธิบายกันนะคะ ทั้งนี้ผู้อ่านควรมีความรู้พื้นฐานในรายวิชากันมาบ้างแล้ว แล้วจึงมาทำความเข้าใจโจทย์ประยุกต์เหล่านี้ ผู้เขียนหวังว่าบทความนี้จะมีประโยชน์ไม่มากก็น้อย มาเริ่มกันเลยค่ะ

R-8.25 Consider the example of a breadth-first traversal given in Figure 8.17. Using the annotated numbers from that figure, describe the contents of the queue before each pass of the while loop in Code Fragment 8.14. To get started, the queue has contents {1} before the first pass, and contents {2,3,4} before the second pass.

แปลโจทย์: จากรูปให้อธิบาย breadth-first traversal ที่เกิดขึ้นหลังจบ loop ใน code ดังกล่าว เริ่มต้นในคิวจะมี {1} ก่อนจะผ่านรอบแรก และก่อนผ่านรอบสองจะมี {2,3,4}

#Algorithm for performing a breadth-first traversal of a tree
Algorithm breadthfirst(T):
Initialize queue Q to contain T.root( )
while Q not empty do
p = Q.dequeue( ) {p is the oldest entry in the queue}
perform the “visit” action for position p
for each child c in T.children(p) do
Q.enqueue(c) {add p’s children to the end of the queue for later visits}

breadth-first traversal เป็นการเข้าถึงข้อมูลแบบทีละชั้น ดังภาพ

ซึ่ง code ดังกล่าวมีการทำงาน 2 ส่วนหลักๆ

Dequeue ข้อมูลออก 1 ตัว
Enqueue ลูกของคิวในข้อ 1

รอบแรกก่อนเข้าลูปมี {1} จากนั้นเข้าไปทำงานใน code จะทำการ dequeue 1 ออก เหลือ { } และ enqueue ลูกของ 1 ได้แก่ 2,3,4 เช่นเดียวกับรอบที่ 2 ทำการ dequeue 2 ออก จากนั้น enqueue ลูกของ 2 ได้แก่ 5 และ 6 จึงได้ผลเป็น {3,4,5,6}

ก่อนเข้าลูปคิวจะมีค่า {1} และหลังจบลูปในแต่ละรอบจะมีค่าตามนี้

{2,3,4}
{3,4,5,6}
{4,5,6,7,8,9,10,11}
{5,6,7,8,9,10,11,12,13,14,15,16}
{6,7,8,9,10,11,12,13,14,15,16}
{7,8,9,10,11,12,13,14,15,16}
{8,9,10,11,12,13,14,15,16}
{9,10,11,12,13,14,15,16}
{10,11,12,13,14,15,16}
{11,12,13,14,15,16}
{12,13,14,15,16}
{13,14,15,16}
{14,15,16}
{15,16}
{16}

R-12.7 Suppose we are given two n-element sorted sequences A and B each with distinct elements, but potentially some elements that are in both sequences. Describe an O(n)-time method for computing a sequence representing the union A∪B (with no duplicates) as a sorted sequence.

แปลโจทย์: สมมติว่าเรามีเซต A และ B ที่มีอย่างละ n ข้อมูล จงหา O(n)-time ในการเรียงข้อมูลของ A∪B (ไม่มีข้อมูลซ้ำ)

ตอบ: นำข้อมูลใน A และ B มารวมกันจากนั้นทำการ scan ลบข้อมูลที่ซ้ำกันออก จะได้ C = A∪B ซึ่ง O(n)-time ก็ยังคงใช้ได้เหมือนเดิม เพียงแต่ n ใหม่ จะไม่เท่ากับ n เก่า (ไม่เท่ากับ 2n ด้วยเพราะลบข้อมูลซ้ำ)

C-12.31 Consider a version of deterministic quick-sort where we pick as our pivot the median of the d last elements in the input sequence of n elements, for a fixed, constant odd number d ≥ 3. What is the asymptotic worst-case running time of quick-sort in this case?

แปลโจทย์: quick sort ที่เลือก pivot จากค่ามัธยฐานจากจำนวน d ค่าสุดท้ายของชุดข้อมูล โดยกำหนดค่า d เป็นเลขคี่ d ≥ 3 จงหาเวลาในกรณีที่แย่ที่สุด

ตอบ: การเลือก pivot จากค่ามัธยฐานสามารถลดโอกาสการเกิดกรณีที่แย่ที่สุด (worst-case) ได้ แต่ไม่ 100% ดังนั้นกรณีแย่ที่สุดของ quick sort นี้จะเป็นเช่นเดียวกับกรณีปกติที่เลือก pivot จากการ random คือจะใช้เวลา O(n^2)

C-14.43 Implement an algorithm that returns a cycle in a directed graph , if one exists.

แปลโจทย์: จงคิด algorithm ที่ใช้ตรวจสอบว่า directed graph (กราฟที่มีเส้นทาง) นั้นมี cycle ภายในกราฟหรือไม่

สร้างโปรแกรมที่ใช้สร้าง direct graph ขึ้นมา ภายในโปรแกรมจะต้องสามารถ addEdge คือเพิ่มเส้นทางจากโหนดถึงโหนด และสามารถตรวจสอบได้ว่ากราฟมี cycle หรือไม่ ซึ่งจะใช้วิธีตรวจสอบโดยการให้โหนดนั้นๆ เดินทางไปตาม addEdge ถ้าเดินทางกลับมาที่จุดเดิมได้ หมายความว่ามี cycle ในกราฟ

จากตัวอย่าง code ทำการสร้างกราฟที่มีลักษณะดังนี้