{ "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": {} } ] }