Algorithms Activity 2
CSC301: Data Structures and Algorithms
Algorithm2.1: Describe an efficient algorithm for finding the ten largest elements in an array of size N.
What is the running time of your algorithm? (O notation)
- Assume MyArray is an array, and it is already defined
- Write the steps of the algorithm either as a Java program or a pseudocode
Algorithm 10Largest ( …………………………………………………………… )
Input: …………………………………………………………………………………………………………………………
Output: An Array, 10LargestElements, containing the 10 largest elements
of the input array
Begin
10LargestElements = ……………………………………………………………
…………………………………………………………… { // Repeat 10 times
// Find the maximum value in MyArray excluding the ones already stored
CurrentMaxIndex = ……………………………………………………………
For …………………………………………………………… {
If ((…………………………………………………………… NOT IN ……………………………………………………………) AND
(…………………………………………………………… > ……………………………………………………………)
currentMaxIndex = ……………………………………………………………
}
// Store its index in the 10LargestElements array
Add …………………………………………………………… to ……………………………………………………………
}
Return ……………………………………………………………
End
Time complexity Analysis:
- The first loop repeats …………………………………………………………… times, which is
constant, and does not depend on then input array.
- The second loop repeats exactly …………………………………………………………… times to
find the largest element making sure to ignore the previously
found elements, so its time complexity ……………………………………………………………
- The instruction to record the index of the second largest element
is repeated only by the first loop …………………………………………………………… times.
So, its time complexity is …………………………………………………………….
- Therefore, the overall time is …………………………………………………………… which is
…………………………………………………………….
CSC301-Data Structures and Algorithms
Algorithm2.2: An array MyArray contains N integers taken from the interval [0,4N], with repetitions
allowed. Describe an efficient algorithm for determining the element that occurs the most often in
MyArray. What is the running time of your algorithm? (O notation)
– Assume MyArray is an array and it is already defined
– Write the steps of the algorithm either as a Java program or a pseudocode
Algorithm highestOccurrences (MyArray[N])
Input: An array of N elements
Output: Element in the array that occurs the most often
Begin
// Declare an extra array of size 4N which will be used as counters
// for the stored numbers; call it counters. Initialize it to zeros.
Counters = Array[4N]
For ……………………………………………………………
Counters[i] = ……………………………………………………………
………………………………………………… { // Repeat for all elements stored in the array
// Take the value stored in myArray and use it as an index
// addressing counters array. Increment the addressed location by 1
…………………………………………………………………………………………………………………………
}
// Find the maximum value in the counters array
currentMaxIndex = ……………………………………………………………
…………………………………………………………………………………………………………………………
If (…………………………………………………………………………………………………………………………)
currentMaxIndex = ……………………………………………………………
// Output the index of the maximum value; this is the element in MyArray
// that occurs the most often in
Return ……………………………………………………………
End
Time complexity Analysis:
- The first loop repeats …………………………………………………………… times, so its time
complexity ……………………………………………………………
- The second loop repeats also …………………………………………………………… times, so
its time complexity ……………………………………………………………
- The third loop repeats vtimes to find the largest counter, so its
time complexity ……………………………………………………………
- The instruction to return the index of the maximum value is
executed only ……………………………………………………………. So, its time complexity is
…………………………………………………………….
- Therefore, the overall time is O(……………………………………………………………) =
O(……………………………………………………………)which is O(……………………………………………………………).
CSC301-Data Structures and Algorithms 2