{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Midterm training exercises with solution" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Difficulty 1\n", "\n", "Build function convertGrade which takes as parameter an integer number and returns the string:
\n", "\n", "Strategy: to check whether a number x is a divisor you obviously use the fact that the remainder of n divided by x is 0. To create the list, start with an empty one [ ] and then go through the numbers from 2 to **N**-1 and append the divisors that you find one after the other.\n", "\n", "After you have done it, describe its complexity in terms of divisions and find a way to optimize the code reducing the computational complexity." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[2, 4, 5, 10, 20, 25, 50]\n" ] } ], "source": [ "def divisors(N):\n", " result=[]\n", " i=2\n", " while(i<=N-1):\n", " if N%i==0:\n", " result.append(i)\n", " i=i+1\n", " return result\n", "\n", "# complexity is clearly N-2 divisions\n", "\n", "def divisors(N):\n", " result=[]\n", " i=2\n", " while(i<=N/2): # here the optimization, it is not necessary to search for divisors after N/2\n", " if N%i==0:\n", " result.append(i)\n", " i=i+1\n", " return result\n", "\n", "print(divisors(100))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Difficulty 4\n", "\n", "Build function secret which takes as parameter a string and returns the same string with each consonant replaced by the same consonant, an \"o\" and again the same consonant. Vowels are vowels=['a','e','i','o','u','A','E','I','O','U']\n", "\n", "For example, Secret(\"hello\") returns \"hohelollolo\"." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def secret(s):\n", " vowels=['a','e','i','o','u','A','E','I','O','U']\n", " r=\"\"\n", " for x in s:\n", " if x in vowels:\n", " r+=x\n", " else:\n", " r+=x+\"o\"+x\n", " return r\n", "print(secret(\"hello\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Difficulty 4+1 (would be 3+1 if I had put a little more of strategy)\n", "\n", "Build function countLetters which takes as input a string S and returns a list with the number of vowels followed by the number of non-vowels (including spaces and whatever) in S. The vowels are \"a\",\"e\",\"i\",\"o\",\"u\",\"A\",\"E\",\"I\",\"O\",\"U\".\n", "\n", "For example, if countLetters(\"Paolo\") returns [3,2].\n", "\n", "Strategy: create a list of vowels using copy&paste from my list above. Set up two counters, one for vowels and one for non-vowels. Scan the string and increment the appropriate counter.\n", " \n", "Draw the flowchart for this procedutre.\n", "\n", "What is its computational complexity in terms of additions?" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[3, 2]\n" ] } ], "source": [ "def countLetters(S):\n", " vowels=[\"a\",\"e\",\"i\",\"o\",\"u\",\"A\",\"E\",\"I\",\"O\",\"U\"]\n", " i=0\n", " c1=0\n", " c2=0\n", " while(iDifficulty 4+1+2 with strategy 1, 6+1+2 with strategy 2
\n", "\n", "Build function triangle which takes as parameter a positive integer number N and prints a triangle such as, for example, triangle(8):\n", "
1\n", "
22\n", "
333\n", "
4444\n", "
55555\n", "
666666\n", "
7777777\n", "
88888888\n", "\n", "Then draw the flowchart of this function.\n", "\n", "Then state and comment the computational complexity of this function only for strategy 2 in terms of int additions and string concatenations.\n", "\n", "\n", "Strategy 1: you have to set up one loop. Inside you build the string using string multiplication and printing the string immediately at each iteration of the loop.\n", " \n", "Strategy 2: you have to set up two while loops, using i as index for the external one and j as index for the internal one. I suggest to start both index from 1 and not 0. In the internal one you build the string attaching the numbers one after the other i times. At the end of the external one you print the string." ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1\n", "22\n", "333\n", "4444\n", "55555\n", "666666\n", "7777777\n", "88888888\n", "1\n", "22\n", "333\n", "4444\n", "55555\n", "666666\n", "7777777\n", "88888888\n" ] } ], "source": [ "def triangle1(N):\n", " i=1\n", " while(i<=N):\n", " j=1\n", " s=str(i)\n", " print(s*i)\n", " i+=1\n", "\n", " \n", "def triangle2(N):\n", " i=1\n", " while(i<=N):\n", " j=1\n", " s=str(i)\n", " while(jDifficulty 5\n", "\n", "Build function sumFrac which takes as input an integer positive number N, checks that it is correct and returns a string containing the operations that you have done as 1/1+1/2+1/3+…+1/N= and the result.\n", "\n", "For example: sumFrac(7) returns 1/1+1/2+1/3+1/4+1/5+1/6+1/7=2.59285714286 (it returns everything, including the left side of the equality!)\n", "\n", "Strategy: after checking for the validity of the input using type function, set up a summing variable equal to 0 and an empty string variable. Loop from 1 to N and at each step add the appropriate fraction to your sum and the appropriate text to your string. Then return the string with the sum. The only thing you should pay attention to is chopping away the extra character which might appear in your string." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1/1+1/2+1/3+1/4+1/5+1/6+1/7 = 2.5928571428571425\n", "1/1+1/2+1/3+1/4+1/5+1/6+1/7+1/8 = 2.7178571428571425\n", "Error, N is 0\n", "None\n", "Error, N is -1\n", "None\n" ] } ], "source": [ "def sumFrac(N):\n", " if type(N)!=int or N<1:\n", " print(\"Error, N is \",N)\n", " else:\n", " mysum=0\n", " s=\"\"\n", " i=1\n", " while i<=N:\n", " mysum=mysum+1/i\n", " s=s+\"1/\"+str(i)+\"+\"\n", " i=i+1\n", " return s[:-1]+\" = \"+str(mysum) # I use :-1 to skip the last + character\n", " \n", "print(sumFrac(7)) \n", "print(sumFrac(8))\n", "print(sumFrac(0))\n", "print(sumFrac(-1))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Difficulty 8\n", "\n", "Build function secondMax which takes as input a list of numbers with at least two elements and returns the second largest number of the list.\n", "