<commit_before>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework 7\n",
    "## Due Date:  Wednesday, October 25th at 11:59 PM"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 1:  Linked List Class\n",
    "Write a linked list class called `LinkedList`.  Remember, a singly linked list is made up of nodes each of which contain a value and a pointer.  The first node is called the \"head node\".\n",
    "\n",
    "Here are the required methods:\n",
    "* `__init__(self, head)` where `head` is the value of the head node.  You could make the head node an attribute.\n",
    "* `__len__(self)`: Returns the number of elements in the linked list.\n",
    "* `__getitem__(self, index)` returns the value of the node corresponding to `index`.  Include checks to make sure that `index` is not out of range and that the user is not trying to index and empty list.\n",
    "* `__repr__(self)` returns `LinkedList(head_node)`.\n",
    "* `insert_front(self, element)` inserts a new node with value `element` at the beginning of the list.\n",
    "* `insert_back(self, element)` inserts a new node with value `element` at the end of the list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 2:  Binary Tree Class\n",
    "A binary search tree is a binary tree with the invariant that for any particular node the left child is smaller and the right child is larger. Create the class `BinaryTree` with the following specifications:\n",
    "\n",
    "`__init__(self)`: Constructor takes no additional arguments\n",
    "\n",
    "`insert(self, val)`: This method will insert `val` into the tree\n",
    "\n",
    "`remove(self, val)`: This will remove `val` from the tree. Upon removal the left child will take the place of the node if it exists, otherwise the right child. The subtree from the left or right child will propagate up in the same manner.\n",
    "\n",
    "`getValues(self. depth)`: Return a list of the entire row of nodes at the specified depth with `None` at the index if there is no value in the tree. The length of the list should therefore be $2^{\\text{depth}}$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 3:  Peer Evaluations\n",
    "Evaluate the members of your group for Milestone 1.  Please follow the instructions in the provided survey.  The survey can be found here:  [Milestone 1 Peer Evaluation](https://harvard.az1.qualtrics.com/jfe/form/SV_0JnuXbE5QjLCrKB)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 4:  Course Evaluation\n",
    "Please take the [Course Evaluation](https://docs.google.com/forms/d/e/1FAIpQLSdDyrtf_aByU4xNeLMSmDrFCJ2OLDrK1Q7ZoeTd2Whf_cdRrw/viewform?usp=sf_link)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3<commit_msg>Clarified a few points on HW7.<commit_after>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework 7\n",
    "## Due Date:  Wednesday, October 25th at 11:59 PM"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 1:  Linked List Class\n",
    "Write a linked list class called `LinkedList`.  Remember, a singly linked list is made up of nodes each of which contain a value and a pointer.  The first node is called the \"head node\".\n",
    "\n",
    "Here are the required methods:\n",
    "* `__init__(self, head)` where `head` is the value of the head node.  You could make the head node an attribute.\n",
    "* `__len__(self)`: Returns the number of elements in the linked list.\n",
    "* `__getitem__(self, index)` returns the value of the node corresponding to `index`.  Include checks to make sure that `index` is not out of range and that the user is not trying to index and empty list.\n",
    "* `__repr__(self)` returns `LinkedList(head_node)`.\n",
    "* `insert_front(self, element)` inserts a new node with value `element` at the beginning of the list.\n",
    "* `insert_back(self, element)` inserts a new node with value `element` at the end of the list.\n",
    "\n",
    "Note:  An alternative implementation is to create a `Node` class.  You are not required to make a `Node` class but you may if you prefer that implementation.  Please don't steal that implementation from the online forums.  I've seen those too."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 2:  Binary Tree Class\n",
    "A binary search tree is a binary tree with the invariant that for any particular node the left child is smaller and the right child is larger. Create the class `BinaryTree` with the following specifications:\n",
    "\n",
    "`__init__(self)`: Constructor takes no additional arguments\n",
    "\n",
    "`insert(self, val)`: This method will insert `val` into the tree\n",
    "\n",
    "`remove(self, val)`: This will remove `val` from the tree. Upon removal the left child will take the place of the node if it exists, otherwise the right child. The subtree from the left or right child will propagate up in the same manner.\n",
    "\n",
    "`getValues(self. depth)`: Return a list of the entire row of nodes at the specified depth with `None` at the index if there is no value in the tree. The length of the list should therefore be $2^{\\text{depth}}$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is a sample output:\n",
    "\n",
    "```python\n",
    "bt = BinaryTree()\n",
    "arr = [20, 10, 17, 14, 3, 0]\n",
    "for i in arr:\n",
    "    bt.insert(i)\n",
    "\n",
    "print(\"Height of binary tree is {}.\\n\".format(len(bt)))\n",
    "for i in range(len(bt)):\n",
    "    print(\"Level {0} values: {1}\".format(i, bt.getValues(i)))\n",
    "```\n",
    "\n",
    "```\n",
    "Height of binary tree is 4.\n",
    "\n",
    "Level 0 values: [20]\n",
    "Level 1 values: [10, None]\n",
    "Level 2 values: [3, 17, None, None]\n",
    "Level 3 values: [0, None, 14, None, None, None, None, None]\n",
    "```\n",
    "\n",
    "Note that you do not need to format your output in this way.  Nor are you required to implement a `__len__` method to compute the height of the tree.  I did this because it was convenient for illustration purposes.  This example is simply meant to show you some output at each level of the tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 3:  Peer Evaluations\n",
    "Evaluate the members of your group for Milestone 1.  Please follow the instructions in the provided survey.  The survey can be found here:  [Milestone 1 Peer Evaluation](https://harvard.az1.qualtrics.com/jfe/form/SV_0JnuXbE5QjLCrKB)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 4:  Course Evaluation\n",
    "Please take the [Course Evaluation](https://docs.google.com/forms/d/e/1FAIpQLSdDyrtf_aByU4xNeLMSmDrFCJ2OLDrK1Q7ZoeTd2Whf_cdRrw/viewform?usp=sf_link)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
{'fraction_non_alphanumeric': 0.14114639397201292, 'fraction_numerical': 0.010764262648008612, 'mean_word_length': 3.201808931599774, 'pattern_counts': {'":': 53, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3675115', 'n_tokens_mistral': 2497, 'n_tokens_neox': 2393, 'n_words': 918}