Vanilla is one of the most complex tastes in the world; itcontains hundreds of different organic compounds that contribute toits flavor. Suppose a group of food enthusiasts are given n samplesof vanilla: s1, …, sn by a sceptic. The sample is either aMexican vanilla specimen or a Bourbon (French) vanilla specimen.The foodies are given each pair (si,sj) of vanillas to taste, andthey must collectively decide whether (a) both are the same type ofvanilla, (b) they are different types of vanilla, or (c) theycannot decide. Note: all pairs are tested, including pairs such as(si, si), (sj, si) and (si, sj), but not all pairs have ‘same’ or‘different’ decisions.
At the end of the tasting, suppose the foodies have made mjudgements of ‘same’ or ‘different’. Give an algorithm that takesthese m judgements and de- termines whether they are consistent.The m judgements are consistent if there is a way to label eachsample si with ‘Mexican’ or ‘Bourbon’ such that for everytaste-test (si,sj) labelled ‘same’, both si and sj have the samelabel, and for every taste-test labelled ‘different’, both si andsj are labelled differently. Your algorithm should run in time O(m+ n).
Expert Answer
Answer to Vanilla is one of the most complex tastes in the world; it contains hundreds of different organic compounds that contrib…