array-list.ipynb

balanced-bsts-demo.ipynb

binary-search-trees.ipynb

bst-ds-demo.ipynb

hashtable-demo.ipynb

iterators-demo.ipynb

lang-intro-part1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python Language Intro (Part 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Agenda\n",
    "\n",
    "1. Language overview\n",
    "2. White space sensitivity\n",
    "3. Basic Types and Operations\n",
    "4. Statements & Control Structures\n",
    "5. Functions\n",
    "6. OOP (Classes, Methods, etc.)\n",
    "7. Immutable Sequence Types (Strings, Ranges, Tuples)\n",
    "8. Mutable data structures: Lists, Sets, Dictionaries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 1. Language overview\n",
    "\n",
    "Note: this is *not* a language course! Though I'll cover the important bits of the language (and standard library) that are relevant to class material, I expect you to master the language on your own time.\n",
    "\n",
    "Python ...\n",
    "\n",
    "- is *interpreted*\n",
    "- is *dynamically-typed* (vs. statically typed)\n",
    "- is *automatically memory-managed*\n",
    "- supports *procedural*, *object-oriented*, *imperative* and *functional* programming paradigms\n",
    "- is designed (mostly) by one man: Guido van Rossum (aka “benevolent dictator”), and therefore has a fairly *opinionated* design\n",
    "- has a single reference implementation (CPython)\n",
    "- version 3 (the most recent version) is *not backwards-compatible* with version 2, though the latter is still widely used\n",
    "- has an interesting programming philosophy: \"There should be one — and preferably only one — obvious way to do it.\" (a.k.a. the \"Pythonic\" way) — see [The Zen of Python](https://www.python.org/dev/peps/pep-0020/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "# by default, only the result of the last expression in a cell is displayed after evaluation.\n",
    "# the following forces display of *all* self-standing expressions in a cell.\n",
    "\n",
    "from IPython.core.interactiveshell import InteractiveShell\n",
    "InteractiveShell.ast_node_interactivity = \"all\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. White Space Sensitivity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python has no beginning/end block markers! Blocks must be correctly indented (4 spaces is the convention) to delineate them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if True:\n",
    "    print('In if-clause')\n",
    "else:\n",
    "    print('In else-clause')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in range(5):\n",
    "    print('In for loop body')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def foo():\n",
    "    print('In function definition')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Basic Types and Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Python, variables do not have types. *Values* have types (though they are not explicitly declared). A variable can be assigned different types of values over its lifetime."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 2 # starts out an integer\n",
    "print(type(a)) # the `type` function tells us the type of a value\n",
    "\n",
    "a = 1.5\n",
    "print(type(a))\n",
    "\n",
    "a = 'hello'\n",
    "print(type(a))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that all the types reported are *classes*. I.e., even types we are accustomed to thinking of as \"primitives\" (e.g., integers in Java) are actually instances of classes. **All values in Python are objects!**\n",
    "\n",
    "There is no dichotomy between \"primitive\" and \"reference\" types in Python. **All variables in Python store references to objects.** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# int: integers, unlimited precision\n",
    "1\n",
    "500\n",
    "-123456789\n",
    "6598293784982739874982734"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# basic operations\n",
    "1 + 2\n",
    "1 - 2\n",
    "2 * 3\n",
    "2 * 3 + 2 * 4\n",
    "2 / 5\n",
    "2 ** 3 # exponentiation\n",
    "abs(-25)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# modulus (remainder) and integer division\n",
    "10 % 3\n",
    "10 // 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# floating point is based on the IEEE double-precision standard (limit to precision!)\n",
    "2.5\n",
    "-3.14159265358924352345\n",
    "1.000000000000000000000001"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# mixed arithmetic \"widens\" ints to floats\n",
    "3 * 2.5\n",
    "1 / 0.3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Booleans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "True\n",
    "False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "not True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "True and True\n",
    "False and True\n",
    "True and False\n",
    "False and False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "True or True\n",
    "False or True\n",
    "True or False\n",
    "False or False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# relational operators\n",
    "1 == 1\n",
    "1 != 2\n",
    "1 < 2\n",
    "1 <= 1\n",
    "1 > 0\n",
    "1 >= 1\n",
    "1.0 == 1\n",
    "1.0000000000000000001 == 1\n",
    "type(1) == type(1.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# object identity (reference) testing\n",
    "x = 1000\n",
    "y = 1000\n",
    "x == x\n",
    "x is x\n",
    "x is not x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x == y\n",
    "x is y\n",
    "x is not y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# but Python caches small integers! so ...\n",
    "x = 5\n",
    "y = 5\n",
    "x == y\n",
    "x is y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Strings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# whatever strings you want\n",
    "'hello world!'\n",
    "\"hello world!\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# convenient for strings with quotes:\n",
    "print('she said, \"how are you?\"')\n",
    "print(\"that's right!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'hello' + ' ' + 'world'\n",
    "'thinking... ' * 3\n",
    "'*' * 80"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Strings are an example of a *sequence* type; https://docs.python.org/3.5/library/stdtypes.html#typesseq\n",
    "\n",
    "Other sequence types are: *ranges*, *tuples* (both also immutable), and *lists* (mutable).\n",
    "\n",
    "All immutable sequences support the [common sequence operations](https://docs.python.org/3/library/stdtypes.html#common-sequence-operations), and mutable sequences additionally support the [mutable sequence operations](https://docs.python.org/3/library/stdtypes.html#mutable-sequence-types)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# indexing\n",
    "greeting = 'hello there'\n",
    "greeting[0]\n",
    "greeting[6]\n",
    "len(greeting)\n",
    "greeting[len(greeting)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# negative indexes\n",
    "greeting[-1]\n",
    "greeting[-2]\n",
    "greeting[-len(greeting)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# \"slices\"\n",
    "greeting[0:11]\n",
    "greeting[0:5]\n",
    "greeting[6:11]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# default slice ranges\n",
    "greeting[:11]\n",
    "greeting[6:]\n",
    "greeting[:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# slice \"steps\"\n",
    "greeting[::2]\n",
    "greeting[::3]\n",
    "greeting[6:11:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# negative steps\n",
    "greeting[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# other sequence ops\n",
    "greeting\n",
    "greeting.count('e')\n",
    "greeting.index('e')\n",
    "greeting.index('e', 2)\n",
    "'e' in greeting\n",
    "'z' not in greeting\n",
    "min(greeting)\n",
    "max(greeting)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Strings also support a large number of [type-specific methods](https://docs.python.org/3/library/stdtypes.html#string-methods)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Type \"Conversions\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Constructors for most built-in types exist that create values of those types from other types:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# making ints\n",
    "int('123')\n",
    "int(12.5)\n",
    "int(True)\n",
    "\n",
    "# floats\n",
    "float('123.123')\n",
    "\n",
    "# strings\n",
    "str(123)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Operators/Functions as syntactic sugar for special methods"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "5 + 6\n",
    "(5).__add__(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyInt(int):\n",
    "    def __add__(self, other):\n",
    "        return self * other"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = MyInt(5)\n",
    "b = MyInt(6)\n",
    "a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "abs(-2.8)\n",
    "(-2.8).__abs__()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'hello' + ' ' + 'world'\n",
    "'hello'.__add__(' ').__add__('world')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `None`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**`None`** is like \"null\" in other languages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# often use as a default, initial, or \"sentinel\" value\n",
    "\n",
    "x = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "note: notebooks do not display the result of expressions that evaluate to None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = None\n",
    "b = 100\n",
    "c = None\n",
    "a\n",
    "b\n",
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "some functions return `None`, so when we call them, there is no \"Out\" cell"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('Hello')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### \"Truthiness\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All objects in Python can be evaluated in a Boolean context (e.g., as the condition for an `if` statement). Values for most types act as `True`, but some act (conveniently, usually) as `False`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if True: # try numbers, strings, other values here\n",
    "    print('tests as True')\n",
    "else:\n",
    "    print('tests as False')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What tests as `False`?"
   ]
  }
 ],
 "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.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}

lang-intro-part2.ipynb

lang-intro-part3.ipynb

linked-list-demo.ipynb

linked-structures-demo.ipynb

on-recursion-demo.ipynb

priority-queues-demo.ipynb

searching-sorting-timing.ipynb

stacks-and-queues-demo.ipynb