Description

---

Question 1: AVL Trees

AVL Trees are a type of self-balancing binary search tree (BST), similar in purpose to red-black trees.

The defining property of an AVL tree is:

For every node $n$ in the tree,

$$\left|\text{height}(n.\text{left})-\text{height}(n.\text{right})\right|\le 1$$

This means the heights of the left and right subtrees of any node differ by at most 1.

Let:

• $h$ = height of the AVL tree

• $n$ = number of nodes in the tree

The goal of this problem is to analyze the relationship between $h$ and $n$.

---

(A)

Prove that:

n≥Fhn \ge F_hn≥Fh​

where FhF_hFh​ is the hthh^{\text{th}}hth Fibonacci number, defined as:

F0=1,F1=1,F2=2,…F_0 = 1,\quad F_1 = 1,\quad F_2 = 2,\quad \ldotsF0​=1,F1​=1,F2​=2,…

Hint:
Use strong induction with two base cases:

1. First prove the statement for AVL trees of height $0$ and $1$.

2. Then assume the statement holds for all AVL trees of height $\le h$, and prove it for height $h+1$.

---

(B)

It is known that for all $k\ge 30$:

Fk≥1.5kF_k \ge 1.5^kFk​≥1.5k

Using this fact and the result from part (A), show that:

$$h=\Theta (\log n)$$

---

(C)

Consider inserting a node into an AVL tree.

• The left image shows an AVL tree before insertion.

• The right image shows the tree after performing a BST insertion, which violates the AVL property.

You are given an image illustrating this situation.

Task:
Describe a sequence of left and/or right rotations that restores the AVL property.

For each rotation:

• Specify which node is the root of the rotation

• Specify whether it is a left or right rotation

You may include diagrams or images if you wish (ensure they are uploaded with the notebook).

---

Question 2: Bloom Filters

A Bloom filter is a probabilistic data structure used to maintain a set $S$ of keys.

It supports:

• Insertion of keys

• Membership queries (“Is key $k$ in the set?”)

Bloom filters are useful when keys are complex objects (e.g., packets, images) that are expensive to compare.

---

Bloom Filter Structure

• A Boolean array $T$ of size $m$

• $l$ independent hash functions h1,h2,…,hlh_1, h_2, \ldots, h_lh1​,h2​,…,hl​

Initially:

$$T[i]=\text{FALSE}\text{for all }i$$

To insert a key $k$:

1. Compute:

   h1(k),h2(k),…,hl(k)h_1(k), h_2(k), \ldots, h_l(k)h1​(k),h2​(k),…,hl​(k)

2. Set:

   T[h1(k)]=T[h2(k)]=⋯=T[hl(k)]=TRUET[h_1(k)] = T[h_2(k)] = \cdots = T[h_l(k)] = \text{TRUE}T[h1​(k)]=T[h2​(k)]=⋯=T[hl​(k)]=TRUE

Note: A Bloom filter is not a hash table, although both use hash functions.

---

(A)

To test whether a key $k$ belongs to the set, we check whether:

T[h1(k)],T[h2(k)],…,T[hl(k)]T[h_1(k)], T[h_2(k)], \ldots, T[h_l(k)]T[h1​(k)],T[h2​(k)],…,T[hl​(k)]

are all TRUE.

Explain whether this method can result in:

• A false positive

• A false negative

---

(B)

Assume the hash functions are uniform, meaning:

P(hi(k)=j)=1m\mathbb{P}(h_i(k) = j) = \frac{1}{m}P(hi​(k)=j)=m1​

for any key $k$, hash function hih_ihi​, and table cell $j$.

If $n$ keys are inserted into the Bloom filter, compute the probability that a given cell $T[j]$ remains FALSE.

---

(C)

Using the result from part (B), estimate the probability of a false positive, i.e., the probability that all $l$ cells:

T[i1],T[i2],…,T[il]T[i_1], T[i_2], \ldots, T[i_l]T[i1​],T[i2​],…,T[il​]

are TRUE for a key that was never inserted.