Proof of Master Theorem, it should contain 3 parts for the 3 scenarios in the master theorem.
Closest pair of points (programming): For more details, please refer to the attachment
To implement a binary search tree in C or Python, you need a Node. A Node has a data field and two links, the left child (lc) and rc.
lc or rc point to a Node. If lc or rc point to nothing, we denote it as a Nil. In the class, I draw square nodes for Nils, and circular nodes for internal nodes.
Show that the number of square nodes is n+1 if there are n circular nodes.
- Finish the proof, amortized cost for a single operation applied to dynamic table is constant, expansion and contraction are allowed.
- Compute A_1(1), A_2(1), A_3(1), A_4(1).