#### TweeSearch 2

##### 1Format

You should treat this assignment like an exam. Therefore, you should do this work without consulting course staff except for critical issues (broken links, possible assignment typo, etc.).

##### 2Theme Song

Rockin’ Robin by Bobby Day

##### 3Problem

You remember TweeSearch 1. Now we’re going to build on it.

Previously, each old tweet was treated in isolation. In reality, many tweets are parts of threads, i.e., they have a parent tweet. Therefore, the Tweet structure now has a field, parent, of type Option<Tweet>. The none option indicates that the tweet has no parent.

You will again define search, with the same parameters. However, the way we perform the search is somewhat different, as defined below.

First, we define the notion of a tweet’s relevance. If a tweet has no parent, then its relevance is exactly its overlap. If a tweet does have a parent, then its relevance is $(0.25 \times r_p) + (0.75 \times o_t)$ where $$r_p$$ is the relevance of its parent and $$o_t$$ is the overlap of the tweet itself with the new tweet.

The third argument to search is the relevance threshold (inclusive).

All tweets that satisfy the relevance threshold should be included in the result, which is again sorted in order of most to least relevant.

Finally, note that multiple tweets can have the same parent (because two tweets may have responded to the parent tweet).This should remind you of our discussion about DAGs. You need to eliminate duplicates in your response, where duplicates are defined by identical.

Template

Submission Form