Problem 1. identifying most and least frequently co-occurring word-pairs in an article. (20 points)

Given an article (for example, this one at nytimes.com)(https://www.nytimes.com/2014/11/11/books/liu-cixins-the-three-body-problem-is-published-in-us.html), design an algorithm to find the top 100 most frequently co-occurring word-pairs and the top 20 least frequently co-occurring word-pairs in this article. Two words (i.e., a word-pair) are said to co-occur if they appear in the same sentence. The frequency of a word-pair is defined as the number of sentences that contain this word-pair. When ranking the word-pairs by frequency, if two or more word-pairs have the same frequency, each of them will occupy a separate rank. (It doesn't matter which goes first or second.)

For instance, the last sentence in the above article Its really a milestone in Chinese science fiction. contain the following word pairs:

('it's', 'really')

('it's', 'a')

('it's', 'milestone')

('it's', 'in')

('it's', 'Chinese')

('it's', 'science')

('it's', 'fiction')

('really', 'a')

('really', 'milestone')

('really', 'in')

('really', 'Chinese')

('really', 'science')

('really', 'fiction')

('a', 'milestone')

('a', 'in')

('a', 'Chinese')

('a', 'science')

('a', 'fiction')

('milestone', 'in')

('milestone', 'Chinese')

('milestone', 'science')

('milestone', 'fiction')

('in', 'Chinese')

('in', 'science')

('in', 'fiction')

('Chinese', 'science')

('Chinese', 'fiction')

('science', 'fiction')

Note that the order of two words doesn't matter in a word-pair. That is, the word pair ('science', 'fiction') is the same as ('fiction', 'science'). Also, all the tokens are case-insensitive. Please consider to convert them to all lower-case. In the interest of simplicity, we will only consider co-occurring word pairs that consist of two different words. For instance, we will NOT consider ('the', 'the') as a co-occurring pair in the sentence "This is the best place in the world."

You can assume that you have access to a subroutine, sentenceSplitter(article), that can accurately segment an article into separate sentences and return these sentences in an array-like data structure.

You can also assume that you have access to another routine tokenizer( sentence), that can accurately identify the individual words contained in the input sentence and return these words in another array-like data structure.

Please describe your algorithm unambiguously using pseudo code with necessary comments in English.

Problem 2. Identifying frequent itemsets of size 1 and 2. (20 points)

Given

P={p_1, p_2, ..., p_m}, the set of products available at a local grocery store;

D={T_1, T_2, ..., T_N}, the set of N transactions that were completed at this store in the past year, where each T_i (i in [1,N]) is a subset of P. If you relate this to your grocery shopping experience at a local store, say Trader Joe's, P will be all the products available at Trader Joe's. Each transaction T_i would correspond to all the products that one put in his/her shopping cart/basket

min_freq, a user-specified parameter (e.g., 5%).

A product is said to be frequent if it occurs in at least min_freq of the transactions in D. By the same token, a pair of products is said to be frequent if it occurs in at least min_freq of the transactions in D. Also, it's straightforward to prove the following claim: if a product is not frequent, none of the pairs that involve this product will be frequent. Use this claim to design an algorithm to find all the frequent products and frequent product pairs in D. Represent your algorithm in pseudo code.