{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

cs1001.py , Tel Aviv University, Fall 2017-2018

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Recitation 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We have written a program that checks if a positive integer (or range of integers) satisfies the Collatz conjecture (using \"while\" and \"for\" loops). We have also covered the basics of lists and list functions and solved an exercise (demonstrating list comprehension). Finally, we have discussed functions, short circuit evaluation and analyzed the efficiency of the functions we saw.\n", "\n", "#### Takeaways:\n", "\n", "
    \n", "
  1. Sometimes its beneficial to implement even abstract problems in order to see the \"big picture\" (in the context of Collatz).
    2. \n", "
  2. Lists can be a highly modular and useful data structure. Make sure that you understand their functionality and also their limits (figuratively and literally).
    3. \n", "
  3. Functions can be used in one another (max2 in max3_v3) and can be composed together.
    4. \n", "
  4. When analyzing a function's performance, think about the input that will cause the largest amount of work and then measure how many operations the function does.
    5. \n", "
  5. Using short circuit evaluation, if e.g. you have a long \"and\" condition, place the part that is most easy to compute first since if it is false, all other parts of the condition will not be computed.
    6. \n", "
\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Code for printing several outputs in one cell (not part of the recitation):" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from IPython.core.interactiveshell import InteractiveShell\n", "InteractiveShell.ast_node_interactivity = \"all\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Collatz Conjecture" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Zoom out of a Collatz tree:\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Check conjecture for a single number:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "please enter an iteger: 2738\n", "2738 is OK\n" ] } ], "source": [ "m = int(input(\"please enter an iteger: \"))\n", "n = m\n", "\n", "while n != 1:\n", "# print(n)\n", " if n % 2 == 0:\n", " n = n//2\n", " else:\n", " n = 3*n + 1\n", "# print(1)\n", "print (m, \"is OK\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Check conjecture for a range of numbers (using a \"for\" loop):" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "please enter an iteger limit: 10\n", "1 is OK\n", "2 is OK\n", "3 is OK\n", "4 is OK\n", "5 is OK\n", "6 is OK\n", "7 is OK\n", "8 is OK\n", "9 is OK\n", "10 is OK\n" ] } ], "source": [ "limit = int(input(\"please enter an iteger limit: \"))\n", "\n", "for m in range(1,limit+1):\n", " n = m\n", " while n != 1:\n", " if n % 2 == 0:\n", " n = n//2\n", " else:\n", " n = 3*n + 1\n", " print (m, \"is OK\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Check conjecture for a range of numbers (using a \"while\" loop):" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "please enter an iteger limit: 10\n", "1 is OK\n", "2 is OK\n", "3 is OK\n", "4 is OK\n", "5 is OK\n", "6 is OK\n", "7 is OK\n", "8 is OK\n", "9 is OK\n", "10 is OK\n" ] } ], "source": [ "limit = int(input(\"please enter an iteger limit: \"))\n", "\n", "orig_num = 1\n", "while orig_num <= limit:\n", " n = orig_num\n", " while n != 1:\n", " if n % 2 == 0:\n", " n = n//2\n", " else:\n", " n = 3*n + 1\n", " print (orig_num, \"is OK\")\n", " orig_num += 1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Lists - Basics" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "3.14" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "[2, 3.14]" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "'python'" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lst = [1,2,3.14, \"python\"]\n", "lst[2]\n", "lst[1:3]\n", "lst[-1]" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[1, 2, 3.14, 'python', -2, 5, -2, 5]" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "[1, 2, 3.14, 'python', -2, 5, -2, 5]" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lst2 = [-2, 5]\n", "lst+lst2\n", "lst = lst + lst2\n", "lst" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[3, 'amir']" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "'amir'" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" }, { "ename": "IndexError", "evalue": "list index out of range", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mIndexError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0mlst\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[0mlst\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0mlst\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m3\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mIndexError\u001b[0m: list index out of range" ] } ], "source": [ "lst = [1,2, [3, \"amir\"]]\n", "lst[-1]\n", "lst[2][1]\n", "lst[3] # no such element" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Common List functions" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "6" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "3" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "[3, 43, 64, 859, 3535]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "['a', 'b', 't', 'z']" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "['z', 'a', 't', 'b', 'c']" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "['z', 'a', 't', 'b', 'c', 'c']" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "['z', 'a', 't', 'b', 'c', 'c', ['z']]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "['z', 'a', 't', 'b', 'c', 'c', ['z'], 'a', 'm', 'i', 'r']" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lst = [1,2,3]\n", "sum(lst)\n", "len(lst)\n", "lst = [859,3,43,3535,64]\n", "sorted(lst)\n", "lst = [\"z\", \"a\", \"t\", \"b\"]\n", "sorted(lst)\n", "lst.append(\"c\")\n", "lst\n", "lst.extend([\"c\"])\n", "lst\n", "lst.append([\"z\"])\n", "lst\n", "lst.extend(\"amir\")\n", "lst" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "13035144" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "88850888" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "88850888" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "id(lst)\n", "lst = lst + [\"d\"]\n", "id(lst)\n", "lst.extend([\"d\"]) # in-place\n", "id(lst)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Iterating over lists" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "Using while loop" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "z\n", "a\n", "t\n", "b\n", "c\n", "c\n", "['z']\n", "a\n", "m\n", "i\n", "r\n", "d\n", "d\n", "d\n", "d\n" ] } ], "source": [ "i = 0\n", "while i < len(lst):\n", " print(lst[i])\n", " i += 1" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "Using for loop with range" ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "z\n", "a\n", "t\n", "b\n", "c\n", "c\n", "['z']\n", "a\n", "m\n", "i\n", "r\n", "d\n", "d\n", "d\n", "d\n" ] } ], "source": [ "for i in range(len(lst)):\n", " print(lst[i])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "Using for loop over elements" ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "collapsed": false, "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "z\n", "a\n", "t\n", "b\n", "c\n", "c\n", "['z']\n", "a\n", "m\n", "i\n", "r\n", "d\n", "d\n", "d\n", "d\n" ] } ], "source": [ "for e in lst:\n", " print(e)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercise: given grades, how many are there above average?" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "#### solution 1: using loops" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "How many grades? 3\n", "enter a grade: 59\n", "enter a grade: 95\n", "enter a grade: 88\n", "2 grades above average!\n" ] } ], "source": [ "count = int(input(\"How many grades? \"))\n", "\n", "grades = [] # [-1]*count\n", "above = 0\n", "# s = 0\n", "\n", "for i in range(count):\n", " g = float(input(\"enter a grade: \"))\n", " grades = grades + [g]\n", "# grades[i] = g\n", "# s += g\n", " \n", "s = sum(grades)\n", "avg = s / count\n", "\n", "for g in grades:\n", " if g > avg:\n", " above += 1\n", "print(above, \" grades above average!\")" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "#### Solution 2: using list comprehension" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "List comprehension example:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[6, 8, 10]" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "[6, 8, 10]" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "collection = [1,2,3,4,5]\n", "lst = []\n", "for var in collection:\n", " if var > 2:\n", " lst.append(2*var)\n", " \n", "lst2 = [2 * var for var in collection if var > 2]\n", "\n", "lst\n", "lst2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Revised solution:" ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "How many grades? 3\n", "enter a grade: 59\n", "enter a grade: 95\n", "enter a grade: 88\n", "2 grades above average!\n" ] } ], "source": [ "count = int(input(\"How many grades? \"))\n", "\n", "grades = [] # [-1]*count\n", "above = 0\n", "# s = 0\n", "\n", "for i in range(count):\n", " g = float(input(\"enter a grade: \"))\n", " grades = grades + [g]\n", "# grades[i] = g\n", "# s += g\n", " \n", "s = sum(grades)\n", "avg = s / count\n", "\n", "above_lst = [g for g in grades if g > avg]\n", "above = len(above_lst)\n", "print(above, \" grades above average!\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Functions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### At most 1 comparison:" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "100" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def max2(a, b):\n", " if a >= b:\n", " return a\n", " else:\n", " return b\n", "\n", "max2(99, 100)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### At most 4 comparisons:" ] }, { "cell_type": "code", "execution_count": 50, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "100" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def max3_v1(a,b,c):\n", " if a >= b and a >= c:\n", " return a\n", " elif b >= a and b >= c:\n", " return b\n", " else:\n", " return c\n", "max3_v1(99, 98, 100)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### At most 2 comparisons:" ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "100" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def max3_v2(a,b,c):\n", " if a >= b:\n", " if a >= c:\n", " return a\n", " else:\n", " return c\n", " else:\n", " if b >= c:\n", " return b\n", " else:\n", " return c\n", " \n", "max3_v2(100, 98, 99)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### At most 2 comparisons:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def max3_v3(a,b,c):\n", " max_ab = max2(a,b)\n", " total_max = max2(c, max_ab)\n", " return total_max" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Short circuit evaluation" ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "False" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "False and True\n", "# 3//0 and False\n", "False and 3//0\n", "True or 3//0" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.4.4" } }, "nbformat": 4, "nbformat_minor": 1 }