wk11/MY470_wk11_lecture.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### MY470 Computer Programming\n",
    "# Graph Algorithms\n",
    "### Week 11 Lecture"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Overview\n",
    "\n",
    "We will practice thinking about abstract data types, algorithm design, and complexity analysis:\n",
    "\n",
    "* Stacks and queues\n",
    "* Trees and graphs\n",
    "* Breadth-first search\n",
    "* Depth-first search\n",
    "---\n",
    "* Course summary \n",
    "* The final assignment\n",
    "* Next steps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Stacks and Queues\n",
    "\n",
    "* Abstract data types\n",
    "* Examples of a linear data structure (e.g., a list)\n",
    "\n",
    "|               | STACK           |QUEUE  |\n",
    "| ------------- |:-------------:| :-----:|\n",
    "| Visualization         | ![Stack](figs/stack.png \"Stack\") | ![Queue](figs/queue.png \"Queue\") |\n",
    "| Ordering principle      | Last-in first-out     |   First-in first-out |\n",
    "| Applications               | backtracking, syntax evaluation, memory management for recursive function calls            |  buffering   |\n",
    "| Examples               | the Back button in your browser, checking if parentheses are balanced, depth-first search  |    printing queue, call center waiting times, breadth-first search |\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Implementing a Stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Stack:\n",
    "    def __init__(self):\n",
    "        \"\"\"Create a new stack that is empty.\"\"\"\n",
    "        self.items = []\n",
    "\n",
    "    def is_empty(self):\n",
    "        \"\"\"Return True if the stack is empty, False otherwise.\"\"\"\n",
    "        return self.items == []\n",
    "\n",
    "    def push(self, item):\n",
    "        \"\"\"Add a new item to the top of the stack.\"\"\"\n",
    "        self.items.append(item)\n",
    "\n",
    "    def pop(self):\n",
    "        \"\"\"Remove the top item from the stack and return it.\"\"\"\n",
    "        return self.items.pop()\n",
    "\n",
    "    def peek(self):\n",
    "        \"\"\"Return the top item from the stack without modifying the stack.\"\"\"\n",
    "        return self.items[len(self.items) - 1]\n",
    "\n",
    "    def size(self):\n",
    "        \"\"\"Return the number of items on the stack.\"\"\"\n",
    "        return len(self.items)\n",
    "        \n",
    "s = Stack()\n",
    "s.push(1)\n",
    "s.push(2)\n",
    "s.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Exercise 1: What is the time complexity of `push()` and `pop()`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Implementing a Queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        \"\"\"Create a new queue that is empty.\"\"\"\n",
    "        self.items = []\n",
    "\n",
    "    def is_empty(self):\n",
    "        \"\"\"Return True if the queue is empty, False otherwise.\"\"\"\n",
    "        return self.items == []\n",
    "\n",
    "    def enqueue(self, item):\n",
    "        \"\"\"Add a new item to the rear of the queue.\"\"\"\n",
    "        # We will assume that the rear is at position 0\n",
    "        self.items.insert(0, item)\n",
    "\n",
    "    def dequeue(self):\n",
    "        \"\"\"Remove the first item from the front of the queue and return it.\"\"\"\n",
    "        # We will assume that the front is at the end of the list\n",
    "        return self.items.pop()\n",
    "\n",
    "    def size(self):\n",
    "        \"\"\"Return the number of items in the queue.\"\"\"\n",
    "        return len(self.items)\n",
    "        \n",
    "q = Queue()\n",
    "q.enqueue(1)\n",
    "q.enqueue(2)\n",
    "q.dequeue()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Exercise 2: What is the time complexity of `enqueue()` and `dequeue()`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Trees\n",
    "\n",
    "* Abstract data type for hierarchical data structures\n",
    "* Can be defined recursively: *A tree consists of a root, and zero or more subtrees. There is an edge from the root to the root of each subtree.*\n",
    "* Examples\n",
    "    * XML, HTML, JSON files\n",
    "    * File and database systems\n",
    "    * Search trees (an alternative data structure to hash tables and sorted lists)\n",
    "\n",
    "![Tree](figs/tree.png \"Tree\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Graphs\n",
    "\n",
    "* Abstract data type for relational data structures\n",
    "* Examples\n",
    "    * Transportation networks, social networks, computer networks\n",
    "\n",
    "\n",
    "![Graphs](figs/graph.png \"Graph\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Implementing a Graph\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    \n",
    "    def __init__(self, name):\n",
    "        \"\"\"Assume name is string\"\"\"\n",
    "        self.name = name\n",
    "    \n",
    "    def get_name(self):\n",
    "        return self.name\n",
    "    \n",
    "    def __str__(self):\n",
    "        return self.name\n",
    "    \n",
    "    \n",
    "class Edge(object):\n",
    "    \n",
    "    def __init__(self, src, dest):\n",
    "        \"\"\"Assume src and dest are of type Node\"\"\"\n",
    "        self.src = src\n",
    "        self.dest = dest\n",
    "    \n",
    "    def get_source(self):\n",
    "        return self.src\n",
    "    \n",
    "    def get_destination(self):\n",
    "        return self.dest\n",
    "    \n",
    "    def __str__(self):\n",
    "        return self.src.get_name() + '->' + self.dest.get_name()\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class DiGraph(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.nodes = []\n",
    "        self.edges = {}\n",
    "        \n",
    "    def has_node(self, node):\n",
    "        return node in self.nodes\n",
    "    \n",
    "    def add_node(self, node):\n",
    "        if self.has_node(node):\n",
    "            raise ValueError('Duplicate node')\n",
    "        self.nodes.append(node)\n",
    "        self.edges[node] = []\n",
    "    \n",
    "    def add_edge(self, edge):\n",
    "        src = edge.get_source()\n",
    "        dest = edge.get_destination()\n",
    "        if not self.has_node(src) or not self.has_node(dest):\n",
    "            raise ValueError('Node not in graph')\n",
    "        self.edges[src].append(dest)\n",
    "        \n",
    "    def get_children(self, node):\n",
    "        return self.edges[node]\n",
    "    \n",
    "    def __str__(self):\n",
    "        result = ''\n",
    "        for src in self.nodes:\n",
    "            for dest in self.edges[src]:\n",
    "                result += src.get_name() + '->' + dest.get_name() + '\\n'\n",
    "        return result[:-1]  # omit final newline\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0->1\n",
      "0->2\n",
      "0->3\n",
      "2->6\n",
      "3->6\n",
      "4->0\n",
      "4->1\n",
      "4->7\n",
      "5->1\n",
      "5->2\n",
      "6->5\n",
      "6->7\n",
      "6->8\n",
      "7->2\n",
      "7->5\n",
      "8->3\n"
     ]
    }
   ],
   "source": [
    "g = DiGraph()\n",
    "# Create six nodes labeled from 0 to 8\n",
    "nodes = [Node(str(i)) for i in range(9)]\n",
    "# Create an edge list corresponding to visualization above\n",
    "edges = [(0, 1), (0, 2), (0, 3), \n",
    "         (2, 6), (3, 6), (4, 0), \n",
    "         (4, 1), (4, 7), (5, 1), (5, 2), \n",
    "         (6, 5), (6, 7), (6, 8), \n",
    "         (7, 2), (7, 5), (8, 3)]\n",
    "for i in nodes:\n",
    "    g.add_node(i)\n",
    "for i, j in edges:\n",
    "    g.add_edge(Edge(nodes[i], nodes[j]))\n",
    "\n",
    "print(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## What Is the Shortest Path between Two Nodes?\n",
    "\n",
    "![Stuttgart-Vaihingen](figs/stuttgart-vaihingen.png \"Stuttgart-Vaihingen\") \n",
    "Image source: https://www.researchgate.net/publication/1947309_Active_Walker_Model_for_the_Formation_of_Human_and_Animal_Trail_Systems\n",
    "\n",
    "* Map directions\n",
    "* Message routing on peer-to-peer computer networks\n",
    "* Optimal solutions to puzzles (e.g. Rubik's cube, Word Ladder)\n",
    "* Plant and facility layout for operations\n",
    "* Arbitrage opportunities in finance (converting assets across markets)\n",
    "* Finding central actors in social networks (betweenness centrality)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## What Is the Shortest Path between Two Nodes?\n",
    "\n",
    "![Example of shortest path](figs/shortest_path.png \"Example of shortest path\") \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Breadth-First vs. Depth-First Search\n",
    "\n",
    "* Serach algorithms for graphs and trees\n",
    "* Similar Big-O\n",
    "* Which one is preferable depends on task and graph structure\n",
    "\n",
    "|                 | BREADTH FIRST  |DEPTH FIRST  |\n",
    "| --------------- |:--------------:| :-----:|\n",
    "| Visualization   | ![BFS](figs/bfs.png \"BFS\") | ![DFS](figs/dfs.png \"DFS\") |\n",
    "| Implementation  | Queue + iteration        | Stack + recursion |\n",
    "| Efficiency      | $O(N + E)$     | $O(N + E)$ |\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Breadth-First Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current BFS path: 3\n",
      "Current BFS path: 3->6\n",
      "Current BFS path: 3->6->5\n",
      "Current BFS path: 3->6->7\n",
      "Current BFS path: 3->6->8\n",
      "Current BFS path: 3->6->5->1\n",
      "The shortest path is: 3->6->5->1\n"
     ]
    }
   ],
   "source": [
    "def print_path(path):\n",
    "    \"\"\"Assume path is a list of Nodes.\n",
    "    Return a string representation of the path.\n",
    "    \"\"\"\n",
    "    result = ''\n",
    "    for i in range(len(path)):\n",
    "        result += str(path[i])\n",
    "        if i != len(path) - 1:\n",
    "            result += '->'\n",
    "    return result\n",
    "        \n",
    "def bfs(graph, start, end, to_print=False):\n",
    "    \"\"\"Assume graph is a DiGraph, start and end are Nodes.\n",
    "    Return a shortest path from start to end in graph.\n",
    "    Path is returned as a list of Nodes.\n",
    "    \"\"\"\n",
    "    # Initialize the path que\n",
    "    init_path = [start]\n",
    "    path_q = Queue()\n",
    "    path_q.enqueue(init_path)\n",
    "    \n",
    "    while path_q.size() > 0:\n",
    "        # Get the next path in line\n",
    "        current_path = path_q.dequeue()\n",
    "        if to_print:\n",
    "            print('Current BFS path:', print_path(current_path))\n",
    "        # If the last node in the path is the one \n",
    "        # we are looking for, return and exit\n",
    "        last_node = current_path[-1]\n",
    "        if last_node == end:\n",
    "            return current_path\n",
    "        # If not, extend the path with the last node's neighbor\n",
    "        # and add to the path que\n",
    "        for nbr in graph.get_children(last_node):\n",
    "            if nbr not in current_path:   # avoid cycles\n",
    "                path_q.enqueue(current_path + [nbr])\n",
    "\n",
    "sp = bfs(g, nodes[3], nodes[1], True)\n",
    "print('The shortest path is:', print_path(sp))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Analysis of Breadth-First Search\n",
    "\n",
    "* The `while` loop is executed at most one time for each node $N$ in the graph (a star graph)\n",
    "* The `for` loop is executed at most one time for each edge $E$ in the graph (a chain)\n",
    "* In the worst case scenario, you will cover every node and every edge, so the time complexity of BFS is $O(N + E)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def bfs(graph, start, end, to_print=False):\n",
    "    \"\"\"Assume graph is a DiGraph, start and end are Nodes.\n",
    "    Return a shortest path from start to end in graph.\n",
    "    Path is returned as a list of Nodes.\n",
    "    \"\"\"\n",
    "    # Initialize the path que\n",
    "    init_path = [start]\n",
    "    path_q = Queue()\n",
    "    path_q.enqueue(init_path)\n",
    "    \n",
    "    while path_q.size() > 0:\n",
    "        # Get the next path in line\n",
    "        current_path = path_q.dequeue()\n",
    "        if to_print:\n",
    "            print('Current BFS path:', print_path(current_path))\n",
    "        # If the last node in the path is the one \n",
    "        # we are looking for, return and exit\n",
    "        last_node = current_path[-1]\n",
    "        if last_node == end:\n",
    "            return current_path\n",
    "        # If not, extend the path with the last node's neighbor\n",
    "        # and add to the path que\n",
    "        for nbr in graph.get_children(last_node):\n",
    "            if nbr not in current_path:   # avoid cycles\n",
    "                path_q.enqueue(current_path + [nbr])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Depth-First Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current DFS path: 3\n",
      "Current DFS path: 3->6\n",
      "Current DFS path: 3->6->5\n",
      "Current DFS path: 3->6->5->1\n",
      "Current DFS path: 3->6->5->2\n",
      "Current DFS path: 3->6->7\n",
      "Current DFS path: 3->6->7->2\n",
      "Current DFS path: 3->6->7->5\n",
      "Current DFS path: 3->6->8\n",
      "The shortest path is: 3->6->5->1\n"
     ]
    }
   ],
   "source": [
    "def dfs(graph, start, end, to_print=False):\n",
    "    \"\"\"Assume graph is a DiGraph, start and end are Nodes.\n",
    "    Return a shortest path from start to end in graph.\n",
    "    Shortest path is returned as a list of Nodes.\n",
    "    \"\"\"\n",
    "    \n",
    "    # Recursive function inside wrapper function\n",
    "    def dfs_rec(graph, start, end, path, shortest, to_print=False):\n",
    "        path = path + [start]\n",
    "        if to_print:\n",
    "            print('Current DFS path:', print_path(path))\n",
    "        # Base case: the last node in the path is the one we are looking for\n",
    "        if start == end:\n",
    "            return path\n",
    "        # Recursive case: keep going deeper if the current path is shorter than \n",
    "        # the shortest so far\n",
    "        for nbr in graph.get_children(start):\n",
    "            if nbr not in path:   # avoid cycles\n",
    "                if shortest == None or len(path) < len(shortest):\n",
    "                    new_path = dfs_rec(graph, nbr, end, path, shortest, to_print)\n",
    "                    if new_path != None:\n",
    "                        shortest = new_path\n",
    "        return shortest\n",
    "    \n",
    "    return dfs_rec(graph, start, end, [], None, to_print)\n",
    "\n",
    "sp = dfs(g, nodes[3], nodes[1], True)\n",
    "print('The shortest path is:', print_path(sp))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* In the worst case scenario, you will cover every node and every edge, so the time complexity of DFS is $O(N + E)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Graph Algorithms\n",
    "\n",
    "* Stacks and queues are useful data abstractions for linear data structures, with many different applications\n",
    "* Trees and graphs are important data abstractions for relational data\n",
    "* Breadth-first search and depth-first search are simple algorithms for searching in a tree or a graph. Their Big-O time complexity is the same, but one may be more preferable than the other depending on the nature of the task and the structure of the graph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "-------\n",
    "\n",
    "* **Lab**: Useful Python modules and libraries\n",
    "* **Final assignment**: Link e-mailed to you today. Assignment is **due at 12:00 noon on Monday January 15th, 2024**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### MY470 Computer Programming\n",
    "# Course Summary and Next Steps\n",
    "### Week 11 Extra"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Course Summary\n",
    "\n",
    "### Theory\n",
    "\n",
    "* Data structures and control flow\n",
    "* Modularity — functions and classes\n",
    "* Optimization — basic algorithm analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Practice\n",
    "\n",
    "* Python and a bit of R\n",
    "* Writing professional code\n",
    "* Approaching a problem computationally"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Essential Programming Skills: Legibility\n",
    "\n",
    "![Legibility](figs/legibility.jpg \"Legibility\")\n",
    "\n",
    "* Use comments\n",
    "* Use function specifications\n",
    "* Use informative names for variables\n",
    "* Use spaces around operators\n",
    "* Separate blocks of related code with empty lines\n",
    "* Follow conventions (see PEP 8 guide)\n",
    "* Be consistent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Essential Programming Skills: Modularity\n",
    "\n",
    "![Modularity](figs/modularity.jpg \"Modularity\")\n",
    "\n",
    "* Use functions and/or classes\n",
    "* Use modules (`.py` files)\n",
    "* Keep related code in same module\n",
    "* Use informative names for functions, classes, and modules"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Essential Programming Skills: Optimization\n",
    "\n",
    "![Optimization](figs/optimization.jpg \"Optimization\")\n",
    "\n",
    "* Analyze order of growth and consider alternative approaches\n",
    "* Remove unnecessary operations\n",
    "* Consolidate loops\n",
    "* Try and rewrite nested loops\n",
    "* Use list comprehensions/functional programming  and built-in functions/methods whenever possible"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Final Assignment: Data\n",
    "\n",
    "* All article edits on Romanian Wikipedia since it started until the end of 2006\n",
    "* Edits are grouped by article and sorted in reverse chronological order\n",
    "\n",
    "| Variable   | Explanation   \n",
    "|:-----------|:-------\n",
    "| title      | title of the edited article               \n",
    "| time       | time in the format YYYY-MM-DD HH:MM:SS when the edit was completed  \n",
    "| revert     | 1 if the edit was detected to revert to a previous article version, 0 otherwise \n",
    "| version    | an integer indicating a unique state of the article, generally increasing over time; -1 indicates the article was empty (usually due to vandalism); if the same number appears more than once, then the article was exactly in the same state at these different time points  \n",
    "| user       | the editor's username or if not logged in, the editor's IP address   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Final Assignment: Task\n",
    "\n",
    "* Conflict on Wikipedia\n",
    "  * Who reverted whom?\n",
    "  * Which reverts were reciprocated?\n",
    "  * Were the editors involved in reciprocated reverts of similar seniriority?\n",
    "* Note\n",
    "  * Can use Copilot but work independently\n",
    "     * Asking ChatGPT, classmates, roommates, family members, online Q&A forums, etc. is NOT allowed\n",
    "  * Can use Moodle forum for clarifying questions if the instructions are ambiguous\n",
    "  * These are real data and there may be many micro-decisions you need to make for how to deal with data errors. Document these in comments in your code\n",
    "  * The three parts are connected so if you cannot solve a preceeding part, manually code a small set of data as it should have been processed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Final Assignment: Expectations\n",
    "\n",
    "### Written in Python\n",
    "\n",
    "* **You CANNOT use advanced data manipulation and analysis libraries such as `pandas`, `sqlite`, `networkx`!**\n",
    "* You are allowed to use smaller, more specific modules such as `pickle` and `datetime` \n",
    "* You are also allowed to use math libraries such as `numpy` for calculations\n",
    "\n",
    "### Legible\n",
    "\n",
    "* Enough said...\n",
    "\n",
    "### Modular\n",
    "\n",
    "* Use functions and .py files\n",
    "* OOP is optional; if you decide to use it, do it well!\n",
    "\n",
    "### Reasonably optimized\n",
    "\n",
    "1. Make it run\n",
    "2. Review and analyze it \n",
    "3. If you can make it cleaner and faster, rewrite it"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Final Assignment: Assessment\n",
    "\n",
    "* Code runs and makes an attempt to solve problem: **+ 10%**\n",
    "\n",
    "* Code produces the correct output: **+ 40%**\n",
    "    * Print/plot requested output \n",
    "    * Do it neatly (e.g. on new lines, with annotation but without unnecessary output)\n",
    "* Code is modular: **+ 10%**\n",
    "    * Use functions and/or classes\n",
    "    * Group functions in modules (.py files)\n",
    "    * Group functions by use and name modules accordingly (DO NOT name \"problem1\" and similar!)\n",
    "    * Import modules into `.ipynb` file and call functions/methods; do not include long blocks of code there\n",
    "\n",
    "* Code is legible and well-documented: **+ 10%**\n",
    "    * Follow conventions and PEP8 guidelines\n",
    "    * Write docstrings\n",
    "    * Include comments\n",
    "\n",
    "* Code is optimized in terms of order of growth (**both time and space**) and actual performance: **+ 30%**\n",
    "    1. Make it run\n",
    "    2. Review and analyze it \n",
    "    3. If you can make it faster, rewrite it"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Next Steps\n",
    "\n",
    "* Finish the Guttag book\n",
    "* Make use of other resources online\n",
    "    * [Coursera](https://www.coursera.org/)\n",
    "    * [MIT OpenCourseWare](https://ocw.mit.edu/index.htm)\n",
    "    * [Code School](http://tryr.codeschool.com/)\n",
    "    * ... and [many others](https://github.com/lse-my470/lectures/blob/master/resources.md)\n",
    "* Read code at any opportunity\n",
    "    * E.g., browse through open-source code on GitHub\n",
    "* Write code at any opportunity\n",
    "* Practice, practice, practice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Your GitHub Profile\n",
    "\n",
    "* Please **DO NOT upload any course materials, including problem sets, your answers, or example answers** \n",
    "    * These are private and should not be shared\n",
    "    * You can post your code for the final assignment but you need to remove the instructions and data (any of the content that came from us)\n",
    "* Employers look at GitHub stats and profiles so if you have more substantive code, upload it\n",
    "    * E.g. data collection or analysis for your MSc dissertion\n",
    "    * E.g. code that you think others may use (such as API to scrape a public website) – include documentation!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## General Advice 1\n",
    "\n",
    "### There is no need to start from scratch — reuse your previous code or start from someone else's code\n",
    "\n",
    "![Not sure if I am a good programmer or just good at googling](figs/good_programmer.jpg \"Not sure if I am a good programmer or just good at googling\") \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## General Advice 2\n",
    "\n",
    "### It's not you — debugging is frustrating \n",
    "\n",
    "\n",
    "> — What's the most used language in prorgamming?\n",
    ">\n",
    "> — Profanity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## General Advice 3\n",
    "\n",
    "### Welcome to the community!\n",
    "\n",
    "See, for example, **https://www.reddit.com/r/ProgrammerHumor/**\n",
    "\n",
    "> How to tell if my office mate is working?\n",
    "> ![How to tell if my office mate is working?](figs/programming.png \"How to tell if my office mate is working?\") "
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}