Describe an algorithm that determined whether or not a particular value appeared
ID: 3833508 • Letter: D
Question
Describe an algorithm that determined whether or not a particular value appeared in a list. Recall that the intersection of two sets is a set consisting of the elements that appear in both sets and that the union of two sets is a set consisting of all the elements that appear in either set (listed exactly once).
A. Let a1, a2, ... an be a sequence of n distinct (no repeats) values and let b1, b2, ... bm be a sequence of m distinct (no repeats) values. Develop and describe in pseudocode an algorithm that prints the values that are in both lists (i.e., the intersection).
B. Use summation notation to represent the number of comparisons that your algorithm makes in the worst case and then evaluate that summation.
C. Let a1, a2, ... an be a sequence of n distinct (no repeats) values and let b1, b2, ... bm be a sequence of m distinct (no repeats) values. Develop and describe in pseudocode an algorithm that prints the values that are in either list (ie, the union) but do not print the same value more than once.
D. use summation notation to represent the number of comparisons that your algorithm makes in the worst case and then evaluate that summation.
Explanation / Answer
A. For every a1, a2, ...., am, check if its present in b array. If yes, then print it.
Algo:
for i in 1 to m:
for j in 1 to n:
if b[i] = a[j]:
print b[i]
break
B. This uses n comparions for each a[i]. i.e. summation from i=1 to m (n) = m*n
C. Print all a[i]'s For B[i]'s check if they are present in a array. If yes, don't print
Algo:
for i in 1 to n:
print a[i]
for i in 1 to m:
flag = 0
for j in 1 to n:
if a[j] = b[i]:
flag = 1
break
if(!flag)
print b[i]
D. For every element in B, it makes n comparisons => m*n comparisons
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.