activities/a02_searching-sorting-hash.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DSCI 512 Lecture 2 Activities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## True/False questions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. If I have to search inside a list $1000$ times, it is better to first sort the list and then use binary search, rather than just using linear search.\n",
    "2. The best sorting algorithms run in $O(n \\log n)$ time.\n",
    "3. The elements of a `set` are maintained in sorted order for fast searching.\n",
    "4. Searching for a key in a `dict` takes $O(1)$ time, but searching for a value takes $O(n)$.\n",
    "5. If two Python objects have different hashes, then they will end up in different buckets in the hash table."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answers:**\n",
    "\n",
    "1. In terms of Big O analysis, $n \\log n + 1000 \\log n$ is $O(n \\log n)$ so it techincally grows faster than $1000n$. But practically, $n \\log n + 1000 \\log n$ overtakes $1000n$ only for very large values of $n$. Therefore, it is a good idea to sort the list first and then use binary search for look up.\n",
    "2. True\n",
    "3. False, they live in a hash table which isn't sorted\n",
    "4. True\n",
    "5. False, they may end up the same after modding."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Old quiz questions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q1\n",
    "\n",
    "Suppose you are given a list called `word_frequency` containing all unique words and their frequencies (the number of times each word occurs) from all published work by William Shakespeare. The words are sorted alphabetically. For example, the list might look like this (but much longer):\n",
    "\n",
    "```\n",
    "[(\"act\",102), (\"hath\",41), (\"thee\",18324), (\"thou\",1390)]\n",
    "```\n",
    "\n",
    "If you wanted to find the most frequently occurring word, would you use linear or binary search? Briefly justify your answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:**\n",
    "\n",
    "Linear. Binary search can be used on the keys but not on the values because the values aren't sorted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q2\n",
    "\n",
    "Consider the following four data structures containing a collection of strings:\n",
    "\n",
    "   - (a) an unsorted list\n",
    "   - (b) a list, sorted alphabetically\n",
    "   - (c) Python's `set` data structure\n",
    "   - (d) Python's `dict` data structure\n",
    "\n",
    "For each of the following operations, which data structure(s) is/are the worst and which data structure(s) is/are the best. Justify your answers (one way would be to use O notation). Note that you may need to list more than one data structure.\n",
    "\n",
    "**NOTE:** In my answers I didn't use `dict` at all since I don't think it really applies here, or at least it depends on whether the strings are being stored as keys or values. If keys then `dict` is the same as `set`, if values then `dict` is the same as unsorted list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answers:**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Determining whether or not the collection includes the string \"supercalifragilisticexpialidocious\".\n",
    "\n",
    "- worst: unsorted list -> $O(n)$\n",
    "- best: set -> $O(1)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Inserting the new string \"aardvark\". Assume we already know that \"aardvark\" is not present in the data structure.\n",
    "\n",
    "- worst: sorted list -> $O(\\log n)$ to find where it goes, and $O(n)$ to move things around after insertion, so $O(n)$ overall.\n",
    "- best: unsorted list, set -> both $O(1)$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finding the string that comes LAST alphabetically.\n",
    "\n",
    "- worst: unsorted list, set -> both $O(n)$\n",
    "- best: sorted list -> $O(1)$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.6 ('dsci512')",
   "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.10.6"
  },
  "vscode": {
   "interpreter": {
    "hash": "833530e805897aab5e7a30ee530b0bcb4cd19373b840f29eae5897b61b26002e"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}