review_final.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CS 2337.001 Final Review [Fall 2019]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Topics\n",
    "\n",
    "- [Vectors](#vectors) (ch. 21)\n",
    "- [Linked Lists](#linkedlists) (ch. 16)\n",
    "- [Stacks](#stacks) (ch. 17)\n",
    "- [Queues](#queues) (ch. 17)\n",
    "- [Trees](#trees) (ch. 19)\n",
    "- [Graphs](#graphs) (ch. 20)\n",
    "- [Hashing](#hashing) (not in textbook - look at the powerpoint on eLearning)\n",
    "- [Algorithms](#algorithms) (not really in the textbook either, but look at your discrete math notes for 3.2 and 3.3 to get the basic ideas of big O)\n",
    "- [Other Things](#other)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Author's note:** Once again I tried to be as accurate as possible, but I probably missed some things! Feel free to submit a pull request [here](https://github.com/lizgw/cs2337review) if there's something that needs fixing.\n",
    "\n",
    "For more info about Jupyter Lab & how it works, check out this demo: https://mybinder.org/v2/gh/QuantStack/xeus-cling/stable?filepath=notebooks/xcpp.ipynb\n",
    "\n",
    "(all image examples from the textbook: *C++ Programming*, 8th edition by D.S. Malik)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "// this is here so all the examples below work! make sure you run this first :)\n",
    "#include <iostream> \n",
    "using namespace std;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Vectors<a name=\"vectors\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Vectors** are the C++ equivalent of Java's `ArrayList`. A vector is a dynamic array that grows as necessary.\n",
    "\n",
    "Arrays (and by extension, vectors) are **random access structures**. You don't have to traverse a list to get to an element, you can just access it by its index (compared to traversing a linked list/binary tree/etc).\n",
    "\n",
    "Another thing to note is that vectors aren't necessarily sorted (as opposed to something like a binary search tree).\n",
    "\n",
    "Also, vectors, like smart pointers, automatically deallocate once they leave scope.\n",
    "\n",
    "Vectors are sequence containers, part of the **standard template library**. If you want all the (overly) specific details, check out the textbook chapter, but the important part is understanding how to use vectors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <vector> // don't forget to do this!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vectors are a templated class, so you need to include the type when you declare one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "vector<int> numList(10); // 10 is the size we want to start with\n",
    "vector<string> wordList;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Accessing Vector Elements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "cout << numList[0] << endl;\n",
    "cout << numList.at(0) << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above two lines essentially do the same thing, but using `[]` is faster because it doesn't check bounds. `.at()` is slower, but safer.\n",
    "\n",
    "Vectors are **contiguous**: there aren't holes/gaps between elements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adding Elements to a Vector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Neither `[]` or `.at()` will cause the vector to expand if you're trying to add a new element. For that, use `vec.push_back(elem)`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vector Operations & Methods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- `vec.capacity()` returns the maximum number of elements the vector can hold without reallocation\n",
    "- `vec.size()` returns the number of elements currently inside the vector, will always be <= `vec.capacity()`\n",
    "- `vec.empty()` returns a boolean stating whether or not the vector is empty\n",
    "- `vec.clear()` removes all elements from the vector\n",
    "- `vec.erase(pos)` removes the element at position `pos` (which is an iterator, not an int!)\n",
    "- `vec.insert(pos, elem)` inserts `elem` at position `pos` (which is an iterator again)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iterators<a name=\"iterators\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Iterators** allow for quick iteration through a vector (and some other data types)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "vector<int> testList;\n",
    "\n",
    "for (int i : {1, 2, 3, 4, 5}) {\n",
    "    testList.push_back(i); // push_back adds the item to the end of the vector\n",
    "}\n",
    "\n",
    "vector<int>::iterator iter; // create an iterator\n",
    "iter = testList.begin(); // start it at the beginning of the list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "for (iter = testList.begin(); iter != testList.end(); ++iter) {\n",
    "    cout << *iter << endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`++iter` moves to the next item in the list, while `*iter` returns the value of the list at that position."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linked Lists<a name=\"linkedlists\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A **linked list** is a collection of **nodes**, each one containing data and a link to the next node.\n",
    "\n",
    "![Linked List](linkedlist1.png)\n",
    "\n",
    "The address of the first node in the list is called the **head**. The **next** property of the last element in the list is `nullptr`. Elements are not necessarily contiguous in memory (because they're dynamically allocated!)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Traversing a Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you set `head = head.next`, then you're losing access to the head and creating a memory leak!\n",
    "\n",
    "Use a `current` pointer instead:\n",
    "\n",
    "```cpp\n",
    "// start at the head\n",
    "Node current = head;\n",
    "// loop until we reach the end of the list\n",
    "while (current != nullptr) {\n",
    "    \n",
    "    // (do something)\n",
    "    \n",
    "    // move to the next node in the list\n",
    "    current = current->next;\n",
    "}\n",
    "```\n",
    "\n",
    "You can also use an [iterator](#iterators)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Inserting into a Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "example list: m -> n -> p -> q\n",
    "\n",
    "Steps (to insert after `p`):\n",
    "1. create a new node, `x`\n",
    "2. assign `x`'s data value\n",
    "3. set `x`'s link to `p->next`\n",
    "4. set `p`'s link to `x`\n",
    "\n",
    "(Look at table 16-1 on page 1091 in the textbook for a nice visual representation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Deleting a Node from a Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "example list: a -> b -> c -> d\n",
    "\n",
    "To delete `b`:\n",
    "1. save a temporary reference to `b`\n",
    "2. set `a->next` to `b->next`\n",
    "3. delete `b`\n",
    "\n",
    "Make sure to use `delete` to avoid memory leaks! If you want to destroy the entire list, make sure to `delete` each node individually, not just the head."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Other Types of Linked Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A **doubly-linked list** has nodes that point forward *and backward* in the list.\n",
    "\n",
    "A **circular linked list** is where the last node has a pointer to the first node."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Stacks<a name=\"stacks\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A **stack** is a data structure where insertion and deletion only happen at one end of the list (the top). Stacks are **Last In First Out** data structures - you can only access the most recent element you put in. Think of a stack of books - you can't get to the one at the bottom of the stack without moving all the other ones first."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- push: add an element to the top of the stack\n",
    "- pop: remove the element at the top of the stack (doesn't return it)\n",
    "- top: return the element at the top of the stack (but don't remove it)\n",
    "- check if empty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prefix, Infix, and Postfix Notation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're used to doing math with **infix** notation: the operators are in between the operands. For example:\n",
    "\n",
    "```\n",
    "(3 + 5) * 2 = 16\n",
    "```\n",
    "\n",
    "**Prefix** aka **Polish** notation places the operators before the operands. This allows you to leave out parenthesis:\n",
    "\n",
    "```\n",
    "* + 3 5 2  = 16\n",
    "```\n",
    "\n",
    "**Postfix** aka **Reverse Polish** notation places operators after the operands. You don't need parenthesis with this either.\n",
    "\n",
    "```\n",
    "3 5 + 2 * = 16\n",
    "```\n",
    "\n",
    "Computers use postfix when performing operations & keep track of everything with a stack. The general algorithm is:\n",
    "\n",
    "- read through the expression, pushing operands onto the stack\n",
    "- when you reach an operator:\n",
    "    - pop the number of operands needed\n",
    "    - do the math\n",
    "    - push the result to the stack\n",
    "- when the stack is empty, you're done\n",
    "\n",
    "ex: `a b + c d e / - * f +` is `(a + b) * (c - d / e) + f` in inorder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stacks & Recursion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Any function written using recursion can be rewritten without it, often using stacks. Think of the \"call stack\" in recursion - the first recursive call gets pushed to the bottom of the stack & is resolved last."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Queues<a name=\"queues\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A **queue** is a **first in first out** data structure - think of a line at a restaurant. Elements are added at the back and removed from the front."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Queue Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- add element to rear\n",
    "- remove element from front\n",
    "- return back\n",
    "- return front\n",
    "- check if empty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Trees<a name=\"trees\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Binary Tree](tree.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Binary Trees** consist of **nodes**. Each node (parent) has a left and right **subtree** (children) (which can be `nullptr`).\n",
    "\n",
    "Binary trees don't have duplicate elements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Tree Vocab"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **leaf**: a node with no children\n",
    "- **node level**: the number of links on the path from the root to that node\n",
    "    - the level of the root is 0\n",
    "- **tree height**: the number of nodes on the longest path from root to leaf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tree Traversals\n",
    "\n",
    "These are all recursive functions!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Inorder\n",
    "\n",
    "The root will be processed in between the left and right subtrees."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. process the left subtree\n",
    "2. process the current node\n",
    "3. process the right subtree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Preorder\n",
    "\n",
    "The root is processed first."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. process the node\n",
    "2. process the left subtree\n",
    "3. process the right subtree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Postorder\n",
    "\n",
    "The root is processed last."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. process the left subtree\n",
    "2. process the right subtree\n",
    "3. process the node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Traversal Trick"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To figure out the order of each traversal for a specific tree, draw around each node, hitting it on 3 sides. The first side shows the node's position in a preorder traversal, the middle is inorder, and the last is postorder.\n",
    "\n",
    "![Tree Traversals](tree-traversals.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Search Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Binary search trees are always sorted. A node's left child has a value less than its parent, and a node's right child has a value greater than the parent's value.\n",
    "\n",
    "ex:\n",
    "\n",
    "```\n",
    "   2\n",
    "  / \\\n",
    " 1   3\n",
    "```\n",
    "\n",
    "### BST Algorithms\n",
    "#### Searching for a value\n",
    "- check each element starting at the root\n",
    "    - if the value of the current element is the value we're searching for, we found it\n",
    "- if the value we're searching for is less than the value at the current node, move to the left child.\n",
    "    - otherwise, the value we're searching for is greater than the value at the current node, so move to the right child\n",
    "- if we've reached `nullptr`, then that element does not exist in the tree\n",
    "\n",
    "#### Inserting a value into the tree\n",
    "(remember, BSTs don't store duplicate values!)\n",
    "- create a new node\n",
    "- traverse the tree, use a trailing pointer so you always have access to the current node's parent\n",
    "    - if the new value is less than the current node's value, go left, otherwise, go right\n",
    "- once the current node is null, we've reached a leaf\n",
    "- add the new node as a child of the current node's parent (attach it to a leaf)\n",
    "\n",
    "#### Deleting a node from a tree\n",
    "When deleting, there are 4 basic cases:\n",
    "1. we're deleting a leaf\n",
    "    - just set the parent's link to nullptr\n",
    "    - deallocate the memory\n",
    "2. we're deleting a node with a left subtree\n",
    "    - temporarily save the node\n",
    "    - replace its parent's link with a link to the left subtree\n",
    "    - deallocate the memory\n",
    "3. we're deleting a node with a right subtree\n",
    "    - (same as above but move the link to the right subtree)\n",
    "4. we're deleting a node with both a left and right subtree\n",
    "    - find the **inorder predecessor**, or the rightmost leaf of the node's left subtree\n",
    "    - change the node's value to the value of the inorder predecessor\n",
    "    - delete the inorder predecessor's node (it'll be a leaf, so follow those steps)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graphs<a name=\"graphs\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A **graph** is a collection of **nodes** or **verticies** that are connected to each other with **edges**.\n",
    "\n",
    "Graphs can be **undirected**, where an edge can be followed in both directions (ie, the edge from A to B is also used to get from B to A)\n",
    "\n",
    "![Undirected graph](undirected-graph.png)\n",
    "\n",
    "Graphs can also be **directed**, where edges have order. The edge from A to B cannot be used to get from B to A.\n",
    "\n",
    "![directed graph](directed-graph.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph Vocab"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **subgraph**: a graph that contains a subset of the vertices and edges of the parent graph. (ex: if all edges and vertices of graph H are also in graph G, then H is a subgraph of G)\n",
    "- **adjacent** vertices are vertices that are connected by an edge\n",
    "- **loop**: when an edge connects a vertex to itself\n",
    "- **paralell edges** are associated with the same pair of vertices\n",
    "- **simple graph**: has no loops or paralell edges\n",
    "- **simple path**: all vertices on the path (except for maybe the first and last) are distinct\n",
    "- **cycle**: a simple path where the first and last vertices are the same (ex: A -> B -> C -> A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Representing Graphs\n",
    "### Using an Adjacency Matrix\n",
    "For a graph with n vertices, the matrix is an n by n matrix where the entry is 0 unless there's an edge between those verticies.\n",
    "\n",
    "Essentially, it's a 2D array. If node 3 and node 4 are connected, then `matrix[3][4]` is `1`.\n",
    "\n",
    "For undirected graphs, the matrix is symmetric across the diagonal (`matrix[3][4]` will be the same as `matrix[4][3]`).\n",
    "\n",
    "### Using an Adjacency List\n",
    "For each vertex, there's a linked list where each node is another adjacent vertex.\n",
    "\n",
    "ex: in a graph, vertex A has edges to vertices B and C. The adjacency list for A looks like this:\n",
    "```\n",
    "A -> B -> C\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Traversing a Graph\n",
    "Use an array to keep track of which vertices have been visited.\n",
    "\n",
    "### Depth-first traversal\n",
    "(similar to a preorder traversal in a binary tree)\n",
    "For each vertex, if it hasn't been visited before, visit it and start a depth-first traversal at that node (it's recursive!).\n",
    "\n",
    "### Breadth-first traversal\n",
    "(similar to a level-by-level traversal of a binary tree)\n",
    "For each vertex, if it hasn't been visited before, add it to a queue and mark it as visited.\n",
    "    Then, as long as the queue isn't empty, get the next vertex from it, add all of its adjacent vertices to the queue and mark them as visited."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Shortest Path Algorithm\n",
    "(won't be in-depth on the exam)\n",
    "A **weighted graph** has a weight, or cost, for each edge, representing how difficult it is to move from one edge to the next. The **shortest path** is a path from one node to another with the smallest total weight.\n",
    "\n",
    "The **Shortest path algorithm**, or **Dijkstra's Algorithm**, is used to find the shortest path from a given vertex.\n",
    "\n",
    "[Here's a good video](https://www.youtube.com/watch?v=GazC3A4OQTE) that explains it - just remember that you keep going after you get to the last node because there might be a shorter path another way."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Minimal Spanning Tree\n",
    "A **tree** is also a graph, but a graph is not necessarily a tree (think how squares are rectangles but rectangles aren't always squares). A tree is just a graph where there's a unique path to any node.\n",
    "\n",
    "A **spanning tree** is a subgraph of a graph where all vertices of the graph are in it. A **minimal spanning tree** is a spanning tree with the smallest weight. Essentially, a graph with all of the same vertices, but the smallest weight possible in connecting all the vertices. **Prim's Algorithm** is used to find minimal spanning trees.\n",
    "\n",
    "### Finding a Minimal Spanning Tree by Hand\n",
    "1. write a list of edges ordered by weight\n",
    "2. shade/highlight edges from the list until each node is connected, starting with the smallest weights\n",
    "    - if the edge forms a cycle, don't include it in the tree\n",
    "3. add the total weights to find the weight of the MST\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hashing<a name=\"hashing\"></a>\n",
    "## Hash Functions\n",
    "A **hash function** takes a key and returns an index that shows where the corresponding value is stored in an array. Any hash function must guarantee that the index produced is a valid index.\n",
    "\n",
    "[Here's a video](https://www.youtube.com/watch?v=b4b8ktEV4Bg) that explains the basics of what hashing is, but towards the end it goes more in depth than the exam will. [This video](https://www.youtube.com/watch?v=MfhjkfocRR0) explains hashing & hash tables, then goes into chaining collision resolution.\n",
    "\n",
    "### Perfect Hash Functions\n",
    "If the data to be hashed is known in advance, the hash function can be based on it. A **minimal perfect hash function** has no collisions or empty cells, which is rare! A fixed set size is needed in order to do this.\n",
    "\n",
    "## Collisions\n",
    "When two different keys produce the same index, that's a **collision**. There are a few ways to solve it, but we need to avoid **clustering**, where too many elements are stored too close to each other, because it makes lookup slower.\n",
    "\n",
    "**Open addressing** is when on a collision, you try positions in the probing sequence until either space is found (or the element is found in case of a search) or the structure is full.\n",
    "\n",
    "### Linear Probing\n",
    "Look at the next space until there's an opening. This creates clustering! A slightly better way to do it is to use **quadratic probing**, where you square the index instead of just going to the next one. That creates secondary clustering, but it's not as much of a problem.\n",
    "\n",
    "### Random Probing\n",
    "Using the same seed produces the same sequence of random numbers. Using random numbers as a probing sequence helps with clustering.\n",
    "\n",
    "### Double Hashing\n",
    "The best approach.\n",
    "\n",
    "### Chaining\n",
    "At each index, there's a linked list that contains the values in the list. The table never overflows because you can just keep adding onto the linked list if there are collisions, but it gets slower as the lists get longer. Space requirements can be high because it needs to allocate space for pointers.\n",
    "\n",
    "### Bucket Addressing\n",
    "All colliding elements are stored in the same position. For each address, a **bucket** is allocated to store data (unsorted). Buckets can fill up."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithms<a name=\"algorithms\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When writing and comparing algorithms, we need a way to determine how they perform in terms of speed and memory.\n",
    "\n",
    "`o(h)` is used to measure efficiency.\n",
    "\n",
    "`T(n)` is used to measure time, but actually it's the number of steps the algorithm takes to solve the problem.\n",
    "\n",
    "`S(n)` is space (memory) efficiency.\n",
    "\n",
    "When we're comparing, we only care about the most significant term. For example, if the equation that represents an algorithm's runtime is `2n^2 + 4n + 7`, the `n^2` is the only part that matters.\n",
    "\n",
    "`o(n^2)` > `o(n)`, but the `o(n)` algorithm is better because it runs faster."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Other Things to Review & Focus On<a name=\"other\"></a> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- past quizzes\n",
    "- BST traversals\n",
    "- linked list algorithms, especially insertion\n",
    "- finding a minimal span tree by hand (write out the list of edges!)\n",
    "- comparing algorithms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++14",
   "language": "C++14",
   "name": "xcpp14"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "-std=c++14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}