[1 Pokavin] ฝึกทำโจทย์ Data Structures and Algorithms

R-8.5 Describe an algorithm, relying only on the BinaryTree operations, that counts the number of leaves in a binary tree that are the left child of their respective parent.

จากตัว Binary Tree ข้างต้นจะเห็นได้ว่ามีตัวฟังชั่น def num_children ในการนับ child ของตัว Parent โดยทำงานจากการเทียบ Node

C-8.56 The indented parenthetic representation of a tree T is a variation of the parenthetic representation of T (see Code Fragment 8.25) that uses indentation and line breaks as illustrated in Figure 8.24. Give an algorithm that prints this representation of a tree.

R-12.10 Show that the best-case running time of quick-sort on a sequence of size n with distinct elements is Ω(nlogn).

จากรูปจะเห็นว่า จำนวนปัญหา(ด้านซ้ายมือ)กับจำนวนที่ต้องทำการ Sort(ด้านขวามือ) ของ Quick sort จะมีค่าเท่ากับ nlogn ซึ่งคือ best case running time ของ Quick sort นั้นเอง

C-12.51 Given an unsorted sequence S of n comparable elements, and an integer k, give an O(nlogk) expected-time algorithm for finding the O(k) elements that have rank n/k, 2 n/k, 3 n/k, and so on.
จากโจทย์ให้ยกตัวอย่างด้วยการแบ่งแบบ n/k, 2 n/k น่าจะเป็นการ sort แบบ Shell Sort ดังนั้น นี้คือตัวอย่างของการ Sort แบบ Shell sort โดย n/k จะมีค่าเท่ากับ gap ในโค้ด

R-14.27 There are eight small islands in a lake, and the state wants to build seven bridges to connect them so that each island can be reached from any other one via one or more bridges. The cost of constructing a bridge is proportional to its length. The distances between pairs of islands are given in the following table.
Find which bridges to build to minimize the total construction cost.

C-14.63 Consider the following greedy strategy for finding a shortest path from vertex start to vertex goal in a given connected graph. 1: Initialize path to start. 2: Initialize set visited to {start}. 3: If start=goal, return path and exit. Otherwise, continue. 4: Find the edge (start,v) of minimum weight such that v is adjacent to start and v is not in visited. 5: Add v to path. 6: Add v to visited. 7: Set start equal to v and go to step 3. Does this greedy strategy always find a shortest path from start to goal? Either explain intuitively why it works, or give a counterexample.
ตัวอย่างของ Greedy strategy Shortest Path หรือ Dijkstra’s Algorithm