---
# System prepended metadata

title: DSA yong liu HW 3

---

# DSA yong liu HW 3
## Exercise 7.4-5 in CLRS Textbook
## Problem 7-2 in CLRS Text book
## 11.2-1
For the i-th hashed key $k_i$, $E\{X_i\}$ is the expectation value, of the number of times $k_i$ being collided by those key, $j$'s, hashed afterward. 
$$ E\{X_i\} = \sum_{j > i} 1 \Pr\{h(k_j)) = h(k_i)\} = \sum_{j > i} 1 / m = (n - i) / m $$
$$ \sum_{i = 1}^n E\{X_i\} = \sum_{i = 1}^n \frac{n - i}{m} = \frac{n^2 - n(n + 1) / 2}{m} = \frac{n^2 - n}{2m}.$$

## 12.2-9
- T is a BST.  
- x has no childs.  
- x.parent is y.  
- x is y.Lchild, or, x is y.Rchild.
- We want to satisfy:
    - y.key is the smallest key in T larger than x.key 
        - I.e., **y is x.successor**
    - y.key is the largest key in T smaller than x.key
        - I.e., **y is x.predecessor**



### soln
- x is y.Lchild
    - try to fing x.successor
        - try to go to the bottum right of x.Lsubtree.
x is a leaf.
Go up left.
It is y.
    - Try to fing x.predecessor.
        - Not y, but we have got we want. 

- x is y.Rchild
    -  try to fing x.predecessor
        - Try to go to the bottum right of x.Lsubtree.
x is a leaf.
Go up left.
It is y.
        - Try to fing x.successor.
Not y, but we have got we want. 
