Programming with Python

Stefan Güttel, guettel.com

Exercises: Analysis of algorithms

Problem 1. Write a function LCM(a, b) that returns the least common multiple of integers a and b. Avoid computing any products bigger than LCM(a, b) itself (big products may cause overflow errors in many languages; in others, like Python, they can cause slower computation).

If either a = 0 or b = 0, we define LCM(a, b) = 0.

Hint: Use the formula based on the prime factorization of a number.

Problem 2. Write a function LCM(L) that returns the least common multiple of all the elements in list L. Avoid computing any products bigger than LCM(L) itself.

If either of the elements in L is a zero, we define LCM(L) = 0.

Hint: Use the formula based on the prime factorization of a number.

Note: Make sure that the function works properly for any list L, including an empty one (this should raise an appropriate error).

Problem 2a. Try to write LCM in a way that it can be invoked by an arbitrary number of arguments, i.e., LCM(a), LCM(a, b), LCM(a, b, c), etc.

Note: Problem 2a is not covered in the course materials and, as such, it requires some Googling efforts. It will not be a part of the tests.

Problem 3a. What is the worst-case complexity of

  1. the sequential search?
  2. the selection sort?
  3. the binary search algorithm?

Problem 3b. Assume that you have an unsorted list. Which of the following is faster and why?

  1. search for an element in the list sequentially, or
  2. sort the list using the selection sort and then search for the element using the binary search algorithm.