week02.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 02 Conditionals and Loops"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code blocks in Python\n",
    "\n",
    "A block is a group of programming statements. Python *requires* the use of indentation to indicate a code block. A group of statements having the same amount of indentation belong to the same code block.\n",
    "\n",
    "In the textbook material for this week you will encounter code that contains indentation. It is important that you pay attention to the presence (and absence) of indentation.\n",
    "\n",
    "Most Python programmers use 4 spaces for each level of indentation and most dedicated Python IDEs will replace the TAB character with 4 spaces. If you are using a plain text editor (as opposed to a dedicated Python code editor) it is critically important that you not mix tabs and spaces for your indentation. Doing so will almost certainly result in the Python interpreter/compiler to report that there is an error in your code.\n",
    "\n",
    "The problem with tabs in many text editors is that pressing the tab key inserts a single tab character but the editor draws the tab character as though it were some fixed number of spaces (often 4, unfortunately)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Textbook section *1.3 If statements*\n",
    "\n",
    "A simple Python program runs each line of code in order from the top of the program to the bottom. For example, the following program imports the `random` module (which contains functions that allow the programmer to generate random numbers), assigns to `x` a random value between 0 and 1, inclusive, prints `x`, and prints 'Goodbye'. Run the program a few times to confirm that the program randomly outputs 0 or 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "x = random.randint(0, 1)\n",
    "print(x)\n",
    "print('Goodbye')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The order in which lines of code are run is called the *control flow* of the program. The control flow of simple programs can be illustrated using a diagram called a [flowchart](https://en.wikipedia.org/wiki/Flowchart). The flowchart for the example above is:\n",
    "\n",
    "![](week02/flow.png)\n",
    "\n",
    "In a flowchart rounded rectangles are called terminals and indicate the start and end of a program. Normal rectangles are called processes and can be used to represent one or more statements. Diamonds indicate a decision representing a true/false condition that determines which one of two paths that the program will take. Lines with arrows called flowlines connect elements of the flowchart indicating the order of various operations (or the flow through the program).\n",
    "\n",
    "**NOTE** The textbook uses a non-standard flowchart convention; it uses rounded rectangles for decisions instead of terminals.\n",
    "\n",
    "Suppose that we want print the string `Heads` if `x` is equal to 0 and `Tails` otherwise (like in the `flip.py` program from the textbook). It should be clear to the reader that the control flow of such a program can take one of two different paths depending on the value of `x`. The flowchart for such a program is:\n",
    "\n",
    "![](week02/if.png)\n",
    "\n",
    "The part of the diagram shaded in gray corresponds to the Python if statement. The Python program corresponding to the flowchart is shown in the next cell. Run the program a few times to convince yourself that it randomly prints `Heads` and `Tails`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "x = random.randint(0, 1)\n",
    "\n",
    "if x == 0:\n",
    "    print('Heads')\n",
    "else:\n",
    "    print('Tails')\n",
    "    \n",
    "print('Goodbye')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`random.randint(x, y)` returns a random integer value between x and y (inclusive).\n",
    "\n",
    "The indentation in the program above is important. The block of code that is run when the condition `x == 0` is equal to `True` is indented one level relative to the `if` keyword. The `else` keyword has the same level of indentation as the `if` keyword. The block of code that is run when the condition `x == 0` is equal to `False` is indented one level relative to the `else` keyword.\n",
    "\n",
    "The colons after the condition `x == 0` and after the `else` keyword are required.\n",
    "\n",
    "**Exercise 1** Un-indent the line `print('Heads')` and run the program. What happens? Re-indent the line after completing this exercise.\n",
    "\n",
    "**Exercise 2** Un-indent the line `print('Tails')` and run the program. What happens? Re-indent the line after completing this exercise.\n",
    "\n",
    "**Exercise 3** Indent the line `print('Goodbye')` and run the program several times. Does it print `Goodbye` after printing `Heads`? Does it print `Goodbye` after printing `Tails`? Can you explain why the modified program does not always print `Goodbye`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An if statement does not require an else block. For example, a modified version of the absolute value example from the textbook is shown in the next cell:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "x = random.randint(-10, 10)\n",
    "print('x: ' + str(x))\n",
    "\n",
    "if x < 0:\n",
    "    x = -x\n",
    "    \n",
    "print('absolute value of x: ' + str(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The flowchart for the example above is:\n",
    "\n",
    "![](week02/abs.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 4** The following cell contains a small program that prints the smaller value of two integers `x` and `y`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "x = random.randint(-10, 10)\n",
    "y = random.randint(-10, 10)\n",
    "print('x: ' + str(x))\n",
    "print('y: ' + str(y))\n",
    "if x < y:\n",
    "    min = x\n",
    "else:\n",
    "    min = y\n",
    "print('min: ' + str(min))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Modify the program so that it does not use an `else` part in the if statement and still correctly computes and prints the minimum of the two values."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Textbook section *1.3 While statements*\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The while statement is an example of a looping statement. A loop allows the programmer to repeat a block of code called the *loop body*. The while statement will repeat the code in the loop body as long as the loop condition is equal to `True`. A flowchart for a while loop looks like the following:\n",
    "\n",
    "![](week02/while.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A while loop starts by evaluating a condition called the *loop condition*; if the loop condition is equal to `True` then the statements in a block of code called the *loop body* are run once. After running the loop body, control flow returns to the loop condition. When the loop condition evaluates to `False` the loop stops running (without running the code in the loop again) and control flow goes to the code after the loop.\n",
    "\n",
    "The code before the loop typically initializes one or more variables used in the loop condition and/or body.\n",
    "\n",
    "The loop body typically changes the values of the variables used in the loop condition so that the loop condition eventually evaluates to `False`.\n",
    "\n",
    "A simple while loop that counts from 0 to 9 is shown in the cell below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "i = 0\n",
    "while i < 10:\n",
    "    print(i)\n",
    "    i = i + 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The variables `i`, `j`, and `k` are commonly used as loop variables when a simple counter is required. A while loop that computes the sum of the natural numbers 0 through 9 is shown in the following cell:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "i = 0\n",
    "sum = 0\n",
    "while i < 10:\n",
    "    sum = sum + i\n",
    "    i = i + 1\n",
    "print('sum: ' + str(sum))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 5** Modify the sum example to compute the sum of the values `i` through 9 where `i` is a value between 1 and 8 (inclusive).\n",
    "\n",
    "**Exercise 6** Modify the sum example to compute the sum of the values `m` through `n` where `m` and `n` are integer values and `m <= n` is `True`.\n",
    "\n",
    "**Exercise 7** The [Collatz conjecture](https://en.wikipedia.org/wiki/Collatz_conjecture) is a well known conjecture in mathematics that can be implemented using a while loop. It can be stated as follows:\n",
    "\n",
    "* start with some positive integer value $n$\n",
    "* while $n$ is not equal to 1\n",
    "    * if $n$ is odd then set $n = 3n + 1$\n",
    "    * else set $n = n / 2$\n",
    "    \n",
    "The conjecture is that $n$ will eventually be equal to 1 although no one has been able to prove that this is in fact true.\n",
    "\n",
    "Write a small Python program that prints out the sequence of values that $n$ takes on inside the loop body of the Collatz conjecture algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 7\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Textbook section *1.3 For statements*\n",
    "\n",
    "A for loop is another type of loop that is traditionally used when the programmer knows the number of times that the loop should run. Technically, a for loop in Python runs once for each element of a sequence. We will study the list sequence in detail next week, but for now, we will use a sequence called a *range*.\n",
    "\n",
    "A range represents an arithmetic sequence [or progression](https://en.wikipedia.org/wiki/Arithmetic_progression): A sequence of numbers where the difference between consecutive terms is constant.\n",
    "\n",
    "In Python, the following statements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "n = random.randint(10, 15)   # random value between 10 and 15\n",
    "r = range(n)\n",
    "print(r)\n",
    "print(list(r))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "creates a range object representing the sequence $0, 1, ..., n-1$. Notice that the sequence does not include $n$.\n",
    "\n",
    "Also notice that printing a range object is not very helpful for learning how the range function works. One way to see all of the values of the range is to make a list object containing the value of the range and then printing the list; again, we will study lists in detail next week.\n",
    "\n",
    "The starting value of the sequence can also be specified. The statements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "m = random.randint(0, 5)     # random value between 0 and 5\n",
    "n = random.randint(10, 15)   # random value between 10 and 15\n",
    "r = range(m, n)\n",
    "print(r)\n",
    "print(list(r))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "creates a range object representing the sequence $m, m+1, ..., n-1$. Notice that the sequence does not include $n$.\n",
    "\n",
    "Finally, the step size between values of the sequence can also be specified. The statements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "m = random.randint(0, 5)     # random value between 0 and 5\n",
    "n = random.randint(10, 15)   # random value between 10 and 15\n",
    "d = random.randint(2, 4)     # random value between 2 and 4\n",
    "r = range(m, n, d)\n",
    "print(r)\n",
    "print(list(r))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "creates a range object representing the sequence $m, m+d, ..., (m+kd)$ where $(m+kd)$ is the largest integer less than $n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 8** Create and print a range object representing the sequence $0, 1, ..., 9$.\n",
    "\n",
    "**Exercise 9** Create and print a range object representing the sequence $5, 6, ..., 9$.\n",
    "\n",
    "**Exercise 10** Create and print a range object representing the sequence $2, 4, ..., 8$.\n",
    "\n",
    "**Exercise 11** Create and print a range object representing the sequence $9, 8, ..., 0$.\n",
    "\n",
    "**Exercise 12** Create and print a range object representing the sequence $8, 6, ..., 0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercises 8-12\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A for loop runs once for each element in a sequence. For example, a for loop written using the sequence $0, 1, ..., 9$ will run a total of 10 times. Each time the loop runs, the value of sequence is available inside of the loop. For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(0, 10):\n",
    "    print('i: ' + str(i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The example above uses a for loop to loop over the elements of the sequence $0, 1, ..., 9$. Each time the loop runs, the loop variable `i` is equal to an element of the sequence:\n",
    "\n",
    "* the first time the loop runs `i` is equal to the first element of the sequence\n",
    "* the second time the loop runs `i` is equal to the second element of the sequence\n",
    "* the third time the loop runs `i` is equal to the third element of the sequence, and so on\n",
    "\n",
    "until all of the values of the sequence have been used."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "for loops are often used when the programmer knows the number of times that a loop should run. For example, suppose that we wanted to print the character `*` five times on the same line; a for loop can be used to easily to so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 5\n",
    "for i in range(n):\n",
    "    print('*', end = '')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 13** Use a for loop to compute the sum of the natural numbers $0, 1, 2, ..., 1000$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 13\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 14** Use a for loop to compute the sum of the natural numbers $100, 101, ..., 200$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 14\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 15** Use a for loop to run an experiment 1000 times. The experiment you should run has the following steps:\n",
    "\n",
    "1. set x to be a random integer between 1 and 6 (use `randint` or `randrange` to generate the random integer\n",
    "2. set y to be a random integer between 1 and 6 (use `randint` or `randrange` to generate the random integer\n",
    "3. compute the sum `x + y`\n",
    "\n",
    "Count the total number of times that the sum `x + y` is equal to 7 and then divide that total by 1000 and print the result. The result is approximately equal to the odds of rolling a 7 using two six-sided dice (which you can loop up online)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 15\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Textbook section *1.3 Nesting*\n",
    "\n",
    "It is possible (and common) to use a loop inside of another loop. For example, the following program prints 8 rows of 5 stars:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = 8\n",
    "n = 5\n",
    "for i in range(m):\n",
    "    for j in range(n):\n",
    "        print('*', end = '')\n",
    "    print()   # print a newline character; i.e., go to the start of the next line"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is often easier to reason about this sort of structure from the inside out. Ask yourself \"What does the inner loop do?\"\n",
    "\n",
    "> Answer: It prints 5 stars on one line\n",
    "\n",
    "Now, using your answer ask yourself \"What does the outer loop do?\"\n",
    "\n",
    "> Answer: It prints 5 stars on one line followed by a new line character a total of 8 times.\n",
    "\n",
    "**Exercise 16** Use a pair of nested loops print out a 5-by-5 multiplication table for the numbers 1 through 5. You should print something that looks like:\n",
    "\n",
    "```\n",
    "1 2 3 4 5 \n",
    "2 4 6 8 10 \n",
    "3 6 9 12 15 \n",
    "4 8 12 16 20 \n",
    "5 10 15 20 25 \n",
    "```\n",
    "\n",
    "More advanced programmers might try to print a nicely aligned table of values (look up formatted strings):\n",
    "\n",
    "```\n",
    "  1  2  3  4  5\n",
    "  2  4  6  8 10\n",
    "  3  6  9 12 15\n",
    "  4  8 12 16 20\n",
    "  5 10 15 20 25\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 16\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The inner loop variable often depends on the outer loop variable. For example, the following program prints a triangular pattern of stars:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 5\n",
    "for i in range(n):\n",
    "    for j in range(n - i):\n",
    "        print('*', end = '')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This sort of structure is harder to reason about because the inner loop depends on the outer loop. The tracing strategy discussed in the textbook is one way to reason about such a program:\n",
    "\n",
    "| i | output |\n",
    "| :-: | :- |\n",
    "| 0 | `*****` |\n",
    "| 1 | `****` |\n",
    "| 2 | `***` |\n",
    "| 3 | `**` |\n",
    "| 4 | `*` |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The table simply tabulates the output for each value of `i`:\n",
    "\n",
    "* when `i` is 0, the inner loop prints 5 stars followed by a newline\n",
    "* when `i` is 1, the inner loop prints 4 stars followed by a newline\n",
    "* when `i` is 2, the inner loop prints 3 stars followed by a newline\n",
    "* when `i` is 3, the inner loop prints 2 stars followed by a newline\n",
    "* when `i` is 4, the inner loop prints 1 star followed by a newline\n",
    "\n",
    "**Exercise 17** Modify the previous program so that it prints a triangle where the vertical edge is on the right hand side of the triangle. *Hint: On each line you need to print some number of blank spaces before printing the stars. Use a third loop to print the blank spaces.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 17\n"
   ]
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}