{
"metadata": {
"name": "",
"signature": "sha256:d4fc3de09192603fa37d6f7af6e6d5010959a5805bd038dbcc61a0b3e8b08bf9"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Programming with Python\n",
"#### Stefan Güttel, [guettel.com](http://guettel.com)\n",
"\n",
"## Exercises: Analysis of algorithms"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Problem 1.** Write a function `LCM(a, b)` that returns the [least common multiple](http://en.wikipedia.org/wiki/Least_common_multiple) of integers `a` and `b`. Avoid computing any products bigger than `LCM(a, b)` itself (big products may cause [overflow errors](http://en.wikipedia.org/wiki/Arithmetic_overflow) in many languages; in others, like Python, they can cause slower computation).\n",
"\n",
"If either `a = 0` or `b = 0`, we define `LCM(a, b) = 0`.\n",
"\n",
"**Hint:** Use the [formula based on the prime factorization of a number](http://en.wikipedia.org/wiki/Least_common_multiple#Finding_least_common_multiples_by_prime_factorization)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Problem 2.** Write a function `LCM(L)` that returns the [least common multiple](http://en.wikipedia.org/wiki/Least_common_multiple) of all the elements in list `L`. Avoid computing any products bigger than `LCM(L)` itself.\n",
"\n",
"If either of the elements in `L` is a zero, we define `LCM(L) = 0`.\n",
"\n",
"**Hint:** Use the [formula based on the prime factorization of a number](http://en.wikipedia.org/wiki/Least_common_multiple#Finding_least_common_multiples_by_prime_factorization).\n",
"\n",
"**Note:** Make sure that the function works properly for any list `L`, including an empty one (this should raise an appropriate error).\n",
"\n",
"**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.\n",
"\n",
"**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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Problem 3a.** What is the worst-case complexity of\n",
"1. the sequential search?\n",
"2. the selection sort?\n",
"3. the binary search algorithm?\n",
"\n",
"**Problem 3b.** Assume that you have an unsorted list. Which of the following is faster and why?\n",
"1. search for an element in the list sequentially, **or**\n",
"2. sort the list using the selection sort and then search for the element using the binary search algorithm."
]
}
],
"metadata": {}
}
]
}