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

Question

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 transactions that were completed at this store in the past year, where each T_i (i in [1,N]) is a subset of P;

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.

Explanation / Answer

Pseudo Algorithm

Steps:

Pseudo code:

P={p_1, p_2, ..., p_m}

D={T_1, T_2, ..., T_N}

Frequency_of_prod={0,0,…..,0} //m elements initial frequency of products

Min_freq_prod={};

Int main()

{

Int min_freq;

//Take min_frequency amount in percentage eg 5%

Scanf("%d", min_freq):

//It indicate that the product should repeat atleast 5 time in 100 transaction

// so it is trivial that product should be involved in atleast (5/100)*N transaction to be declared as min_frequent product.

//Loop thorough all the products and find their frequencies;

Count=0;

For(j=0;j<N;j++)

{

// Increase the count of product which is involved in j^th Transacation.

// eg if j^th transaction involve product 3. then increment count of Frequency_of_prod[3]

Frequency_of_prod[Prod_involved_in_j_th_transaction]=Frequency_of_prod[Prod_involved_in_j_th_transaction]+1;

}

//End of this loop we will have Frequency_of_prod array with respective frequency of products.

//Now loop over Frequency_of_prod array to find which are frequenct.

Min_freq_prod_count=0;

For(i=0;i<m;i++)

{

         // product if frequent if it is repeated athleast min_freq*N/100.

If( Frequency_of_prod[i] >= min_freq*N/100 )

{

// store the product number which are frequent.

// we will get all frequent product in Min_freq_prod array.

Min_freq_prod[Min_freq_prod_countj++]=I;

}

}

// by end of this loop we should have all the product which are frequent in Min_freq_prod array

// Print al the frequent product

// Now all pairs of Min_freq_prod array represent the pairs which are frequent as every product number of Min_freq_prod array is frequent.

For (i=0;<Min_freq_prod_count;i++)

{

For(j=i+1;i<Min_freq_prod_count;j++)

{

//Print ( Min_freq_prod[i] Min_freq_prod[j]) pair as frequent.

}

}

}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.