{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lab 04: Duplicates\n",
    "\n",
    "- **Name**:  Domer McDomerson\n",
    "- **Netid**: dmcdomer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Activity 1: Brute-Force"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def has_duplicates_bf(phrase):\n",
    "    ''' Use brute-force to determine whether or not the phrase contains duplicate words. '''\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "LYRICS = [\n",
    "    \"But I've got a blank space, baby dnd I'll write your name\",\n",
    "    \"Cause we never go out of style, We never go out of style.\",\n",
    "    \"Baby, I'm just gonna shake, shake, shake, shake, shake, I shake it off, I shake it off\",\n",
    "    \"So take a look what you've done, Cause, baby, now we got bad blood\",\n",
    "    \"Ooh, look what you made me do, Look what you made me do\",\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_lyrics(function, display=True):\n",
    "    ''' Check each lyric in LYRICS list.  Only print the result if display is True. '''\n",
    "    for lyric in LYRICS:\n",
    "        if display:\n",
    "            print('{} -> {}'.format(lyric, function(lyric)))\n",
    "        else:\n",
    "            function(lyric)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "check_lyrics(has_duplicates_bf, display=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Benchmarking"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%timeit check_lyrics(has_duplicates_bf, display=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Reflection\n",
    "\n",
    "1. Describe the flow control of your `has_duplicates_bf` function.  How did it detect if there was a duplicate word?\n",
    "\n",
    "    <font color=\"red\">Response here</font>\n",
    "\n",
    "2. What is the algorithmic complexity of your `has_duplicates_bf` function?\n",
    "\n",
    "    <font color=\"red\">Response here</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Activity 2: Sort and Scan"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def has_duplicates_sc(phrase):\n",
    "    ''' Sort and then scan phrase to see if it contains any duplicate words '''\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "check_lyrics(has_duplicates_sc, display=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Benchmarking"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%timeit check_lyrics(has_duplicates_sc, display=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reflection\n",
    "\n",
    "1. Describe the flow control of your `has_duplicates_sc` function.  How did it detect if there was a duplicate word?\n",
    "    \n",
    "    <font color=\"red\">Response here</font>\n",
    "\n",
    "2. What is the algorithmic complexity of your `has_duplicates_sc` function?\n",
    "\n",
    "    <font color=\"red\">Response here</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Activity 3: Sort and Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(values, target):\n",
    "    start = 0\n",
    "    end   = len(values) - 1\n",
    "    \n",
    "    while start <= end:\n",
    "        midpoint = (start + end) // 2\n",
    "        middle   = values[midpoint]\n",
    "        \n",
    "        if middle == target:\n",
    "            return True\n",
    "        \n",
    "        if middle > target:\n",
    "            end   = midpoint - 1\n",
    "        else:\n",
    "            start = midpoint + 1\n",
    "            \n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def has_duplicates_bs(phrase):\n",
    "    ''' Sort and then perform binary search on phrase to determine if it contains duplicate words '''\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "check_lyrics(has_duplicates_bs, display=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Benchmarking"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%timeit check_lyrics(has_duplicates_bs, display=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reflection\n",
    "\n",
    "1. Describe the flow control of your `has_duplicates_bs` function.  How did it detect if there was a duplicate word?\n",
    "\n",
    "    <font color=\"red\">Response here</font>\n",
    "\n",
    "2. What is the algorithmic complexity of your `has_duplicates_bs` function?\n",
    "\n",
    "    <font color=\"red\">Response here</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Activity 4: Reflection\n",
    "\n",
    "Examining the results of Activities 1, 2, and 3, what can you say about the relationship between algorithmic complexity and real world performance?\n",
    "\n",
    "<font color=\"red\">Response here</font>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python3",
   "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}