Determine the number of distinct items

Reference no: EM133389638

Use the Random class to create a list (System.Collections.Generic.List) with 10,000 random integers in the range [0, 20,000] (give or take a few hundred in that range is fine). Then determine how many distinct integers are in the list with 3 different approaches. Also, have them run in the order listed below. Do not change the order.

To be clear: You are not allowed to use ready implementations of Distinct. A note on what you're doing: you're taking an array of numbers and conceptually just removing duplicates and counting
how many are left. If the input array was {1,1,3,5,6,6,7,7,7,9} then the distinct number set is {1,3,5,6,7,9}, implying 6 distinct numbers.

Question 1. Do not alter the list in any way and use a hash set to determine the number of distinct integers in the list. The result will be included in the output, which is discussed more below. Also, include in the output information about the time complexity of this method. Be careful with this and describe how you determined it.

Question 2. Do not alter the list in any way and determine the number of distinct items it contains while keeping the storage complexity (auxiliary) at O(1). This means that you cannot dynamically allocate any memory. If you have an algorithm that would require more storage if the list had more items, then it is not O(1) storage complexity. Moreover, you cannot allocate additional lists, arrays, or containers of any sort.

Question 3. Sort the list (use built-in sorting functionality) and then use a new algorithm to determine the number of distinct items with O(1) storage, no dynamic memory allocation, and O(n) time complexity. Do not alter the list further after sorting it. Determine the number of distinct items in O(n) time (not including the sorting time, which you can ignore), where n is the number of items in the list.

Reference no: EM133389638

Questions Cloud

Retrieve the current values of the input elements : Create a file called hwork-1.js and add it to the bottom of the html as a script. Add an event listener to the button so that it calls a makeSentence function

How did george washington come to be involved : How did George Washington come to be involved? Were they important to the eventual outcome? How does George Washington's life connect to the major themes

Compute bmi and max-heart rate : Compute BMI and max-heart rate. Following the ntnu.edu/cerg/hrmax Maximum Heart Rate Calculator and develop something similar

How did george washington come to be involved in american : How did George Washington come to be involved in the American revolution? Were they important to the eventual outcome? How does George Washington's life connect

Determine the number of distinct items : Determine the number of distinct items in O(n) time (not including the sorting time, which you can ignore), where n is the number of items in the list

How did the southern colonies operate before the revolution : How did the Southern colonies operate before the Revolution? Who was in charge? How did they govern themselves? How was the economy run?

Special education progress mark datasets : What type of auditing would you do on special education progress mark datasets in an elementary school

What modern social movements do you see parallels : What modern social movements do you see parallels with in protests which took place before and during the American Revolution? What are the limitations of those

What steps did woodrow wilson take to avoid american : What steps did Woodrow Wilson take to avoid American involvement in the First World War? How did minorities in America participate in the First World War?

User Account

All Pages