This is a question on Algorithms. Please answer the full question clearly. Read

Question

This is a question on Algorithms. Please answer the full question clearly. Read the entire question. There are several parts. Thank you.

Suppose you have a list of words and your goal is to find the duplicate words. You may assume that the words are at most 20 bytes long. What is the size of the input? Design two different methods for this problem: one that is linear time in the average case, and one that is worst-case efficient. Analyze the complexity of your methods and briefly explain why they work correctly.

Explanation / Answer

Size of the input:

There is no restriction in size of input. It will be number of words present in list multiplied by each word size (20 bytes, at most size).

It also depends on implementation language. There is some limit for maximum number of elements (words) a list can store. The same holds goods for set used in algorithm.

The same solution will hold goods for average case and worsts case complexity.

Algorithm:

1. Define a set (S) of type string

2. Define a set (RES) to store duplicate word

3. For each word (W) in the list

4.     Try to Insert W in S, If Un-successful

5.         then add W in RES

6.     End If

7. End For

8. RES will store unique duplicate words.

Explanation:

We are iterating list only once and checking/inserting item in set constant time.

Complexity: O(n), where n is size of list.

For worst case: All words will be same

For n words in list each taking constant time O(1) time for checking/adding in set, with some constant time in start and end. This makes overall time complexity as O(n).

Why: It will go in 5th line, which in turn will take O(1) time but a more instruction to insert in RES for each word in.

Correctness of algorithm:

For each word of the list except first one, FALSE will be returned while trying to insert it in set S, stating this word has occurred earlier in the list, and the word has been added in set RES that stores duplicate words. First word will return TRUE while inserting in set S, stating first occurrence of the word.

For Average Case: Some words will be unique and some will be duplicated

For n words in list each taking constant time O(1) time for checking/adding in set, with some constant time in start and end. This makes overall time complexity as O(n).

Why: Line number 5 hit only for duplicated elements which takes constant time. This again makes overall time complexity as O(n).

Correctness of algorithm:

For each word of the list which are duplicate, FALSE will be returned while trying to insert it in set S, stating this word has occurred earlier in the list, and the word has been added in set RES that stores duplicate words. Else TRUE will be returned and the word has been added in set S, stating first occurrence of the word.

Note:

We are keeping in mind that while adding word in set, it returns Boolean status. If status is TRUE, word has been added, else word has not been added.

Set maintains unique words. So, RES will contain unique duplicate words

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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