Skip to content

Instantly share code, notes, and snippets.

@steven-tey

steven-tey/CS110 Session 7.1 Pre-Class Work.ipynb

Last active October 21, 2019 17:07
Show Gist options
  • Save steven-tey/79bbe703b72dfabd8302eff5e51d561d to your computer and use it in GitHub Desktop.
Save steven-tey/79bbe703b72dfabd8302eff5e51d561d to your computer and use it in GitHub Desktop.
Download ZIP
CS110 Session 7.1 Pre-Class Work
Display the source blob
Display the rendered blob
Raw
CS110 Session 7.1 Pre-Class Work.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\\rightarrow$Run All).\n",
"\n",
"Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"NAME = \"Steven Tey\"\n",
"COLLABORATORS = \"\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "b829d01fa88366d60630dae1299fa764",
"grade": false,
"grade_id": "cell-d94cea4a211410ce",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"# CS110 Pre-class Work 7.1\n",
"\n",
"## Part A. Median Heap (watch this [video explanation](https://www.youtube.com/watch?v=756_8C9YBZQ&list=PLF_a-qBXTGFektoI6JUOTRL36JlvD04BR&index=5&t=0s) or read this [description](https://stackoverflow.com/a/15319593/7946759))\n",
"\n",
"Throughout this pre-class work, please use the following definition of median: the median of a list of numbers is the one in the middle of the list when the list is ordered. When such the middle element can’t be determined (i.e., in a list of even length), the average of the two middle elements is the median. For example, 5 is the median of [-1,2,4,5,8,10,12], and (5+7)/2=6 is the median of [1,2,3,5,7,8,10,11].\n",
"\n",
"Using the idea from Lesson 3.2, we can use a pair of heaps to create a data structure which allows fast access to the median. Use the heapq module in python to create both a max-heap and a min-heap. Note that by default, the heapq module in python only creates min-heaps, but if we multiply elements by -1 when we store them, then we can also create max-heaps.\n",
"\n",
"\n",
"## Question 1.\n",
"Write a function `add_to_median_heap(minh, maxh, elem)`. It must accept a min heap, a max heap, and an element to add.\n"
]
},
{
"cell_type": "code",
"execution_count": 125,
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "3f8e0bb0de793ce786eba2f6715d69b3",
"grade": false,
"grade_id": "cell-50cb08de70712ee7",
"locked": false,
"schema_version": 1,
"solution": true
}
},
"outputs": [],
"source": [
"import heapq\n",
"\n",
"def add_to_median_heap(minh, maxh, elem):\n",
" \n",
" # Base case for maxh\n",
" if len(maxh) == 0:\n",
" maxh.append(elem)\n",
" \n",
" # When there is no imbalance in the length of the maxh and the minh\n",
" elif abs(len(maxh) - len(minh)) == 0: \n",
" if elem <= minh[0]:\n",
" maxh.append(elem)\n",
" heapq._heapify_max(maxh)\n",
" else:\n",
" minh.append(elem)\n",
" heapq.heapify(minh)\n",
" \n",
" # When the maxh has one extra element than the minh\n",
" elif len(maxh) - len(minh) == 1:\n",
" # Base case for minh\n",
" if len(minh) == 0:\n",
" if elem > maxh[0]:\n",
" minh.append(elem)\n",
" heapq.heapify(minh)\n",
" else:\n",
" minh.append(heapq.heappushpop(maxh, elem))\n",
" heapq._heapify_max(maxh)\n",
" heapq.heapify(minh) \n",
" elif elem <= minh[0]:\n",
" minh.append(heapq.heappushpop(maxh, elem))\n",
" heapq._heapify_max(maxh)\n",
" heapq.heapify(minh)\n",
" else:\n",
" minh.append(elem)\n",
" heapq.heapify(minh)\n",
" \n",
" # When the minh has one more element than the maxh\n",
" elif len(minh) - len(maxh) == 1:\n",
" if elem <= minh[0]:\n",
" maxh.append(elem)\n",
" heapq._heapify_max(maxh)\n",
" else:\n",
" maxh.append(heapq.heappushpop(minh, elem))\n",
" heapq._heapify_max(minh)\n",
" heapq.heapify(maxh)\n",
"\n",
" return (minh, maxh)"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "47ae2ae64e7e5a094e32b8e29577ebd2",
"grade": false,
"grade_id": "cell-b62f7899e36af96f",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Question 2\n",
"Write a function `median(minh, maxh)`. It must return the median element.\n"
]
},
{
"cell_type": "code",
"execution_count": 126,
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "4fdb08f74f611846be80db8164227117",
"grade": false,
"grade_id": "cell-43ce866dd1dc2d5b",
"locked": false,
"schema_version": 1,
"solution": true
}
},
"outputs": [],
"source": [
"def median(minh, maxh):\n",
" if len(maxh) > len(minh):\n",
" return(maxh[0])\n",
" elif len(minh) > len(maxh):\n",
" return(minh[0])\n",
" else:\n",
" return((maxh[0] + minh[0])/2)"
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "9f79f245efea8c7b7d7c444af36ad997",
"grade": true,
"grade_id": "cell-673faa69bf330eda",
"locked": true,
"points": 0,
"schema_version": 1,
"solution": false
}
},
"outputs": [],
"source": [
"# Please ignore this cell. This cell is for us to implement the tests \n",
"# to see if your code works properly. "
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "ea112ad1eac7cf41487236cf22381071",
"grade": false,
"grade_id": "cell-ec86b3a3c5adaedf",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Question 3.\n",
"\n",
"Uncomment and run the testing code given below to test your functions. It should print out numbers ranging from 1 to 50, in that order."
]
},
{
"cell_type": "code",
"execution_count": 129,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1\n",
"2\n",
"3\n",
"4\n",
"5\n",
"6\n",
"7\n",
"8\n",
"9\n",
"10\n",
"11\n",
"12\n",
"13\n",
"14\n",
"15\n",
"16\n",
"17\n",
"18\n",
"19\n",
"20\n",
"21\n",
"22\n",
"23\n",
"24\n",
"25\n",
"26\n",
"27\n",
"28\n",
"29\n",
"30\n",
"31\n",
"32\n",
"33\n",
"34\n",
"35\n",
"36\n",
"37\n",
"38\n",
"39\n",
"40\n",
"41\n",
"42\n",
"43\n",
"44\n",
"45\n",
"46\n",
"47\n",
"48\n",
"49\n",
"50\n"
]
}
],
"source": [
"minh = []\n",
"maxh = []\n",
"for a in range(1,100,2):\n",
" add_to_median_heap(minh, maxh, a)\n",
" print(\"%.0f\" % median(minh, maxh)) "
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "be3a94b3063c99a265c7b868e45a5f69",
"grade": false,
"grade_id": "cell-11d4510a48c38394",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Question 4.\n",
"What’s the worst case complexity to build a median heap using `add_to_median_heap`?"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "4ddd5b5c6be74e7306bd08ee76a1b858",
"grade": true,
"grade_id": "cell-c8e33ebdc8aaf328",
"locked": false,
"points": 0,
"schema_version": 1,
"solution": true
}
},
"source": [
"The time complexity of the add_to_median_heap is $O(N log N)$, since there are log N layers in each heap and since we are comparing all of the N elements with the root of both heaps before using heap insertion to insert the element into the right position in either of the heaps. Although there are 2 heaps - maxh and minh - the comparison only has to be done once with the root of each heap. Therefore, when you multiply the number of layers ($log N$) of each heap by the time complexity to process each element ($N$), that will give us a time complexity of $O(N log N)$."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "8a1276ebbad9b1292badcb9090c8a910",
"grade": false,
"grade_id": "cell-dada08b7f913c96f",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Question 5.\n",
"What’s the worst case complexity of `median`?"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "7d67e5e84a28b798ba456d72603533f0",
"grade": true,
"grade_id": "cell-c061920faa337890",
"locked": false,
"points": 0,
"schema_version": 1,
"solution": true
}
},
"source": [
"$O(1)$ - we are just comparing the roots of both ``minh`` and ``maxh``, and returning the appropriate median, this takes a constant time and doesn't increase as the number of elements increase."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "73694bd23377143032d5224818a389b7",
"grade": false,
"grade_id": "cell-fcf89277dcd46cbe",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Question 6.\n",
"\n",
"How does this way of finding the median compare with the vanilla way of sorting the list and pick the middle element? Use arguments based on efficiency or clearity of the respective algorithms."
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "733fe35313ebf5888c622423bb7462b4",
"grade": true,
"grade_id": "cell-1f31afecda9730a7",
"locked": false,
"points": 0,
"schema_version": 1,
"solution": true
}
},
"source": [
"The average time complexity for this method is $O(n) + O(1)$. \n",
"\n",
"This is considerably faster than the vanilla way, since that takes $O(N log N)$ even with the fastest method. Plus, we don't need to sort the list again and again whenever a new input is added and the list grows bigger and bigger."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "d4869e0b17f0248df4c3ae91668257e8",
"grade": false,
"grade_id": "cell-695c23986b831032",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## [Optional] Question 7.\n",
"\n",
"Is it possible to extend this idea to any percentile? If it is, then write code to do so. If it’s not possible, prove why it is not possible."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "c293e85a4cf43662dc635c9e0f511be4",
"grade": true,
"grade_id": "cell-4d0c197e6d484338",
"locked": false,
"points": 0,
"schema_version": 1,
"solution": true
}
},
"outputs": [],
"source": [
"# YOUR CODE HERE\n",
"raise NotImplementedError()"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "bd7ff85760b2e8303c3b4482b6ca44b2",
"grade": false,
"grade_id": "cell-3cba7ecc0de11f1b",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Part B. Quickselect\n",
"\n",
"Quicksort can be modified to find the $k$-th smallest element in an unordered list. This is known as quickselect. It does this by choosing a partition (as in quicksort). Once the list has been partitioned then we know how many elements lie to the left and to the right of the partition. This allows us to recursively call quickselect on the correct sublist.\n",
"\n",
"## Question 1.\n",
"\n",
"Write a function `qselect(lst, k)`, which takes both a list and an index $k$. The function must then return the $k$-th smallest item in the list.\n"
]
},
{
"cell_type": "code",
"execution_count": 91,
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "3714ebe85f9dbc77eb3bb3c106a009ea",
"grade": false,
"grade_id": "cell-fb9c2bc9d5b4bc92",
"locked": false,
"schema_version": 1,
"solution": true
}
},
"outputs": [],
"source": [
"def qselect(lst, k):\n",
"\n",
" def partition(A, p, r, idx):\n",
"\n",
" # base case\n",
" if r == p:\n",
" return A[p]\n",
"\n",
" # Choosing a pivot randomly\n",
" pivot_index = random.randint(p, r)\n",
"\n",
" # Swap the first element of the list with the pivot\n",
" A[p], A[pivot_index] = A[pivot_index], A[p]\n",
"\n",
" # Partition function from Session 5.2 \n",
" i = p\n",
" for j in range(p+1, r+1):\n",
" if A[j] < A[p]:\n",
" i += 1\n",
" A[i], A[j] = A[j], A[i]\n",
"\n",
" A[i], A[p] = A[p], A[i]\n",
"\n",
" # Partition recursively for one half of the partition\n",
" if idx == i:\n",
" return A[i]\n",
" elif idx < i:\n",
" return partition(A, p, i-1, idx)\n",
" else:\n",
" return partition(A, i+1, r, idx)\n",
"\n",
" if lst is None or len(lst) < 1:\n",
" return None\n",
"\n",
" if k < 0 or k > len(lst) - 1:\n",
" raise IndexError()\n",
"\n",
" return partition(lst, 0, len(lst) - 1, k)"
]
},
{
"cell_type": "code",
"execution_count": 92,
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "5ee41421528107f7ae195a7197a5d6d9",
"grade": true,
"grade_id": "cell-85a25ed6a1f62a66",
"locked": true,
"points": 0,
"schema_version": 1,
"solution": false
}
},
"outputs": [],
"source": [
"import random\n",
"random.seed(123) # introducing a seed for reproducibility purposes\n",
"lst1 = list(range(100))\n",
"random.shuffle(lst1)\n",
"lst2 = []\n",
"for a in range(100):\n",
" lst2.append(qselect(lst1, a))\n",
"assert(lst2 == list(range(100)))"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "54fddc25ea0529f44aa6653b18ff7745",
"grade": false,
"grade_id": "cell-8013044acd03642a",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Question 2.\n",
"Uncomment and run the testing code given below to test your function. It should print out integers from 0 to 99.\n"
]
},
{
"cell_type": "code",
"execution_count": 93,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0\n",
"1\n",
"2\n",
"3\n",
"4\n",
"5\n",
"6\n",
"7\n",
"8\n",
"9\n",
"10\n",
"11\n",
"12\n",
"13\n",
"14\n",
"15\n",
"16\n",
"17\n",
"18\n",
"19\n",
"20\n",
"21\n",
"22\n",
"23\n",
"24\n",
"25\n",
"26\n",
"27\n",
"28\n",
"29\n",
"30\n",
"31\n",
"32\n",
"33\n",
"34\n",
"35\n",
"36\n",
"37\n",
"38\n",
"39\n",
"40\n",
"41\n",
"42\n",
"43\n",
"44\n",
"45\n",
"46\n",
"47\n",
"48\n",
"49\n",
"50\n",
"51\n",
"52\n",
"53\n",
"54\n",
"55\n",
"56\n",
"57\n",
"58\n",
"59\n",
"60\n",
"61\n",
"62\n",
"63\n",
"64\n",
"65\n",
"66\n",
"67\n",
"68\n",
"69\n",
"70\n",
"71\n",
"72\n",
"73\n",
"74\n",
"75\n",
"76\n",
"77\n",
"78\n",
"79\n",
"80\n",
"81\n",
"82\n",
"83\n",
"84\n",
"85\n",
"86\n",
"87\n",
"88\n",
"89\n",
"90\n",
"91\n",
"92\n",
"93\n",
"94\n",
"95\n",
"96\n",
"97\n",
"98\n",
"99\n"
]
}
],
"source": [
"import random\n",
"random.seed(123) # introducing a seed for reproducibility purposes\n",
"lst = list(range(100))\n",
"random.shuffle(lst)\n",
"for a in range(100):\n",
" print(qselect(lst, a))"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "3fede812466807c2a250ab3c6427f75c",
"grade": false,
"grade_id": "cell-e7a965de7bb56aa3",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Question 3.\n",
"\n",
"Write down the recurrence relation for your code."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "6fb3d2481f5df1b96c902e5446844f87",
"grade": true,
"grade_id": "cell-24144607b3ffade3",
"locked": false,
"points": 0,
"schema_version": 1,
"solution": true
}
},
"source": [
"$T(n) = T(\\frac{n}{2}) + c$\n",
"\n",
"This gives us a time complexity of $O(log n)$.\n",
"\n",
"This is because we are splitting the list into two and just performing qselect on half of the list only. The term $c$ is the time complexity to find the pivot - which is chosen randomly. "
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "311ee23a32dbc3ba43d3bba0d433871b",
"grade": false,
"grade_id": "cell-fd740516f4259f3c",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Question 4.\n",
"\n",
"Solve the recurrence relation for quickselect in the best case.\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "78416da569a0269f78967b11d7b93332",
"grade": true,
"grade_id": "cell-c125f4742933e820",
"locked": false,
"points": 0,
"schema_version": 1,
"solution": true
}
},
"source": [
"$T(n) = T(\\frac{n}{2})$\n",
"\n",
"In the best case scenario, when the first element is the median, this gives us a time complexity of $O(1)$."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "7cc9c5e0531e8ece71be2ff60ee65995",
"grade": false,
"grade_id": "cell-e281cecc190fd662",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Question 5.\n",
"\n",
"Solve the recurrence relation for quickselect in the worst case."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "f4cceeaea59e48c3fabdb8d19e302db5",
"grade": true,
"grade_id": "cell-852c3a71d8c2d7c1",
"locked": false,
"points": 0,
"schema_version": 1,
"solution": true
}
},
"source": [
"$T(n) = T(n-1)$\n",
"\n",
"This gives us a time complexity of $O(n^2)$.\n",
"\n",
"This is when we are starting with the pivot being on the extreme end of the spectrum - either the biggest element or the smallest element in the list"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment