- Give an algorithm to find the greatest common factor of integers stored in a list. For example, if the list is [20 30 50], then 10 is the greatest common factor since no integer greater than 10 can divide every number in the list.
- [*0 points if not met] The algorithm must solve the following problem:
Input: a list of integers L
Output: the greatest common factor of all numbers in the list.
- Provide an explanation of how your algorithm works
- Formal pseudocode of the algorithm
- A proof that the algorithm is correct
- A symbolic runtime analysis of the algorithm (tight big-oh analysis)
Simplifying Assumptions:
- Each integer in the list has d digits.
- For this question, you may assume the following function exists, and has a runtime of O(d), where d is the number of digits in any integer in the list:
function gcf(a, b) //a and b are integers. (Wikipedia: Euclid’s algorithm)
1 while b != 0 do
2 t ← b
3 b ← a mod b
4 a ← t
5 end while
6 return a
0 comments