API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 21st, 2019
83
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 18.76 KB | None | 0 0
raw download clone embed print report
  1. {
  2. "cells": [
  3. {
  4. "cell_type": "markdown",
  5. "metadata": {},
  6. "source": [
  7. "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",
  8. "\n",
  9. "Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
  10. ]
  11. },
  12. {
  13. "cell_type": "code",
  14. "execution_count": null,
  15. "metadata": {},
  16. "outputs": [],
  17. "source": [
  18. "NAME = \"Abraham Esquivel\"\n",
  19. "COLLABORATORS = \"\""
  20. ]
  21. },
  22. {
  23. "cell_type": "markdown",
  24. "metadata": {},
  25. "source": [
  26. "---"
  27. ]
  28. },
  29. {
  30. "cell_type": "markdown",
  31. "metadata": {
  32. "deletable": false,
  33. "editable": false,
  34. "nbgrader": {
  35. "checksum": "fe57a13a2ba710371e280641c9f21c35",
  36. "grade": false,
  37. "grade_id": "cell-90b6f68e307cf4d7",
  38. "locked": true,
  39. "schema_version": 1,
  40. "solution": false
  41. }
  42. },
  43. "source": [
  44. "# CS110 Pre-class Work 4.2\n",
  45. "\n",
  46. "## Part A. The Hire-Assistant Problem.\n",
  47. "\n",
  48. "Imagine that you need to hire a new assistant. Every day an agency sends a new assistant for you to interview. If the assistant is better than your current assistant, then you fire your current assistant and you hire the better assistant. You may assume that assistant quality is uniformly distributed between 0 and 1.\n",
  49. "\n",
  50. "## Question 1.\n",
  51. "Write a function, named hire_assistant, that takes applicants (a list of the numbers that represent the level of qualification of the applicants; the higher the number, the better qualified), and returns the number hires if the applicants are presented in the exact same order as the input list applicants. Note that your function should not randomize anything (or else it would be called a randomized algorithm)."
  52. ]
  53. },
  54. {
  55. "cell_type": "code",
  56. "execution_count": null,
  57. "metadata": {
  58. "deletable": false,
  59. "nbgrader": {
  60. "checksum": "3e823066b88c3701b5aa6feb0b29ea00",
  61. "grade": false,
  62. "grade_id": "cell-d011f5f4707fe41a",
  63. "locked": false,
  64. "schema_version": 1,
  65. "solution": true
  66. }
  67. },
  68. "outputs": [],
  69. "source": [
  70. "def hire_assistant(applicants):\n",
  71. " \"\"\"\n",
  72. " Return the number of assistant hired.\n",
  73. " Inputs:\n",
  74. " - applicants: a list of the numbers that represent the level of qualification of \n",
  75. " the applicants; the higher the number, the better qualified\n",
  76. " \n",
  77. " Outputs:\n",
  78. " - hires: Number of assistants hired\n",
  79. " \"\"\"\n",
  80. " # YOUR CODE HERE\n",
  81. " best=[applicants[0]] #Add the first person in line and from there the other candidates\n",
  82. " #will be compared against the current (and undesirable) assistant\n",
  83. " count=0 #This will be the counter to see if someone was hired. The counter will either be 1 or 0\n",
  84. " \n",
  85. " for i in range(len(applicants)):\n",
  86. " if applicants[count]>=best[(len(best)-1)]: #This for loop represents the process of interviews\n",
  87. " best.append(applicants[count]) #This adds the best candidates in the best list\n",
  88. " count=count+1\n",
  89. " \n",
  90. " \n",
  91. " return(count)\n",
  92. "\n",
  93. " raise NotImplementedError()\n",
  94. "print(hire_assistant([-1,-2,-3,-4]))\n"
  95. ]
  96. },
  97. {
  98. "cell_type": "code",
  99. "execution_count": null,
  100. "metadata": {
  101. "deletable": false,
  102. "editable": false,
  103. "nbgrader": {
  104. "checksum": "1cf91a3b99ed87bfe9ea81d9a9252e16",
  105. "grade": true,
  106. "grade_id": "cell-66778b97ad66f71e",
  107. "locked": true,
  108. "points": 1,
  109. "schema_version": 1,
  110. "solution": false
  111. }
  112. },
  113. "outputs": [],
  114. "source": [
  115. "assert(hire_assistant([1])==1)\n",
  116. "assert(hire_assistant([-1, -2, -3, -4])==1)"
  117. ]
  118. },
  119. {
  120. "cell_type": "markdown",
  121. "metadata": {
  122. "deletable": false,
  123. "editable": false,
  124. "nbgrader": {
  125. "checksum": "950e8b4c047988bb6493460be72d1bc7",
  126. "grade": false,
  127. "grade_id": "cell-e5d810828093b20d",
  128. "locked": true,
  129. "schema_version": 1,
  130. "solution": false
  131. }
  132. },
  133. "source": [
  134. "## Question 2. \n",
  135. "Assuming the applicants are presented in a random order, write a function that receives the number of applicants as input and returns the average number of assistants hired.\n",
  136. "\n",
  137. "**N.B.:** Don’t forget to run the simulation several times for each given number of applicants to better estimate the number of hires (please refer to task 3 of the Study Guide)."
  138. ]
  139. },
  140. {
  141. "cell_type": "code",
  142. "execution_count": null,
  143. "metadata": {
  144. "deletable": false,
  145. "nbgrader": {
  146. "checksum": "7038d9d8cc9239d5ca15f5d21aa986e3",
  147. "grade": true,
  148. "grade_id": "cell-b223520ca72942a0",
  149. "locked": false,
  150. "points": 0,
  151. "schema_version": 1,
  152. "solution": true
  153. }
  154. },
  155. "outputs": [],
  156. "source": [
  157. "import random\n",
  158. "def experimental_hires(N):\n",
  159. " # YOUR CODE HERE\n",
  160. " random.shuffle(N)\n",
  161. " print(N)\n",
  162. " best=[N[0]] #Add the first person in line and from there the other candidates\n",
  163. " #will be compared against the current (and undesirable) assistant\n",
  164. " count=0 #This will be the counter to see if someone was hired. The counter will either be 1 or 0\n",
  165. " \n",
  166. " for i in range(len(N)):\n",
  167. " if N[count]>=best[(len(best)-1)]: #This for loop represents the process of interviews\n",
  168. " best.append(N[count]) #This adds the best candidates in the best list\n",
  169. " count=count+1\n",
  170. " \n",
  171. " n=(count,\"number of assistants hired. List\",best[1:]) \n",
  172. " return(n)\n",
  173. "\n",
  174. " raise NotImplementedError()\n",
  175. " \n",
  176. "print(experimental_hires([-1,-3,8,12]))"
  177. ]
  178. },
  179. {
  180. "cell_type": "markdown",
  181. "metadata": {
  182. "deletable": false,
  183. "editable": false,
  184. "nbgrader": {
  185. "checksum": "7f78b31a96cb5ddc8eb534ab037d9fee",
  186. "grade": false,
  187. "grade_id": "cell-a55a7b3d12ef78bb",
  188. "locked": true,
  189. "schema_version": 1,
  190. "solution": false
  191. }
  192. },
  193. "source": [
  194. "## Question 3.\n",
  195. "\n",
  196. "Use the function below, `analytical_hires(N)`, which returns the analytical expected number of hires, given the number of applicants, along with the function you created in question 2 to create a graph with two curves such that:\n",
  197. "* The x-axis shows the total number of applicants (make sure label the x-axis)\n",
  198. "* The y-axis shows the average number of hires (make sure label the y-axis)\n",
  199. "* The graph contains two curves;\n",
  200. " * Curve 1: the theoretical performance estimates computed calls to the function `analytical_hires`.\n",
  201. " * Curve 2: the simulated or experimental estimates using the function you created in question 2.\n"
  202. ]
  203. },
  204. {
  205. "cell_type": "code",
  206. "execution_count": null,
  207. "metadata": {
  208. "deletable": false,
  209. "editable": false,
  210. "nbgrader": {
  211. "checksum": "1e514458253b863a6c69ce09ccd2d9de",
  212. "grade": false,
  213. "grade_id": "cell-4092502cb05933d4",
  214. "locked": true,
  215. "schema_version": 1,
  216. "solution": false
  217. }
  218. },
  219. "outputs": [],
  220. "source": [
  221. "def analytical_hires(N):\n",
  222. " \"\"\"\n",
  223. " Return the analytical expected number of hires if there are N applicants\n",
  224. " Inputs:\n",
  225. " - N: Number of applicants\n",
  226. " Outputs:\n",
  227. " - hires: Average number of assistants hired\n",
  228. " \"\"\"\n",
  229. " # from the textbook, we know that the analytical result is \n",
  230. " # 1 + 1/2 + 1/3 + ... + 1/N\n",
  231. " hires = 0\n",
  232. " for n in range(N):\n",
  233. " hires += 1/(n+1)\n",
  234. " return hires"
  235. ]
  236. },
  237. {
  238. "cell_type": "code",
  239. "execution_count": null,
  240. "metadata": {
  241. "deletable": false,
  242. "nbgrader": {
  243. "checksum": "055b3a48707a83f9330ab3b00c45144a",
  244. "grade": true,
  245. "grade_id": "cell-f9c07920c069ce20",
  246. "locked": false,
  247. "points": 0,
  248. "schema_version": 1,
  249. "solution": true
  250. }
  251. },
  252. "outputs": [],
  253. "source": [
  254. "# YOUR CODE HERE\n",
  255. "import matplotlib.pyplot as plt\n",
  256. "import random\n",
  257. "import numpy as np\n",
  258. "def experimental_hires(N):\n",
  259. " # YOUR CODE HERE\n",
  260. " np.array((random.shuffle(N)),dtype=object)\n",
  261. " print(N)\n",
  262. " best=[N[0]] #Add the first person in line and from there the other candidates\n",
  263. " #will be compared against the current (and undesirable) assistant\n",
  264. " count=0 #This will be the counter to see if someone was hired. The counter will either be 1 or 0\n",
  265. " \n",
  266. " for i in range(len(N)):\n",
  267. " if N[count]>=best[(len(best)-1)]: #This for loop represents the process of interviews\n",
  268. " best.append(N[count]) #Th\n",
  269. " count=count+1\n",
  270. " \n",
  271. " n=(count,\"number of assistants hired. List\",best[1:]) \n",
  272. " return(n)\n",
  273. "\n",
  274. " raise NotImplementedError()\n",
  275. " \n",
  276. "def analytical_hires(N):\n",
  277. " \"\"\"\n",
  278. " Return the analytical expected number of hires if there are N applicants\n",
  279. " Inputs:\n",
  280. " - N: Number of applicants\n",
  281. " Outputs:\n",
  282. " - hires: Average number of assistants hired\n",
  283. " \"\"\"\n",
  284. " # from the textbook, we know that the analytical result is \n",
  285. " # 1 + 1/2 + 1/3 + ... + 1/N\n",
  286. " hires = 0\n",
  287. " for n in range(len(N)):\n",
  288. " hires += 1/(n+1)\n",
  289. " return hires\n",
  290. "\n",
  291. "def plot(N):\n",
  292. " np.array(N, dtype=object)\n",
  293. " x=len(N)\n",
  294. " Curve1y= analytical_hires(N)\n",
  295. " Curve2y= experimental_hires(N)\n",
  296. " plt.plot(x,Curve1y,'r',) #################################################\n",
  297. " plt.plot(x,Curve2y,'b')\n",
  298. " plt.xlabel(\"Number of applicants\") #This section builds the plot\n",
  299. " plt.ylabel(\"Number of hires\")\n",
  300. " plt.show() #################################################\n",
  301. " raise NotImplementedError()\n"
  302. ]
  303. },
  304. {
  305. "cell_type": "markdown",
  306. "metadata": {
  307. "deletable": false,
  308. "editable": false,
  309. "nbgrader": {
  310. "checksum": "f5c0fc54ac7e38140eacf7a0d3877a00",
  311. "grade": false,
  312. "grade_id": "cell-8720f8d8a6a98422",
  313. "locked": true,
  314. "schema_version": 1,
  315. "solution": false
  316. }
  317. },
  318. "source": [
  319. "## Question 4.\n",
  320. "\n",
  321. "Plot a graph with the x-axis showing the total number of applicants and the y-axis showing the probability that exactly one assistant is hired."
  322. ]
  323. },
  324. {
  325. "cell_type": "code",
  326. "execution_count": null,
  327. "metadata": {
  328. "deletable": false,
  329. "nbgrader": {
  330. "checksum": "99500575978918dad34be4dfe49fff36",
  331. "grade": true,
  332. "grade_id": "cell-d3fe1b7d6d175ad7",
  333. "locked": false,
  334. "points": 0,
  335. "schema_version": 1,
  336. "solution": true
  337. }
  338. },
  339. "outputs": [],
  340. "source": [
  341. "# YOUR CODE HERE\n",
  342. "raise NotImplementedError()"
  343. ]
  344. },
  345. {
  346. "cell_type": "markdown",
  347. "metadata": {
  348. "deletable": false,
  349. "editable": false,
  350. "nbgrader": {
  351. "checksum": "998ef0b673bc47c929e5543e6f86ccb2",
  352. "grade": false,
  353. "grade_id": "cell-2bd2500c3ca4cf02",
  354. "locked": true,
  355. "schema_version": 1,
  356. "solution": false
  357. }
  358. },
  359. "source": [
  360. "## [Optional] Question 5.\n",
  361. "Assume that an assistant is able to perform an amount of work each day that is equal to their “quality”. You have a total amount of work M that needs to be accomplished. Your costs are as follows:\n",
  362. "* X = daily salary for the assistant,\n",
  363. "* Y = fee to the employment agency,\n",
  364. "* Z = retrenchment fee for the old assistant.\n",
  365. "\n",
  366. "Try to formulate an optimal stopping rule (ie. at what point should one stop requesting new potential hires from the agency?) Make any necessary assumptions to ensure the problem is well-formulated.\n"
  367. ]
  368. },
  369. {
  370. "cell_type": "code",
  371. "execution_count": null,
  372. "metadata": {
  373. "deletable": false,
  374. "nbgrader": {
  375. "checksum": "43b6a51878665a39b0ede1313448eaa6",
  376. "grade": true,
  377. "grade_id": "cell-af2f0291eced6982",
  378. "locked": false,
  379. "points": 0,
  380. "schema_version": 1,
  381. "solution": true
  382. }
  383. },
  384. "outputs": [],
  385. "source": [
  386. "# YOUR CODE HERE\n",
  387. "raise NotImplementedError()"
  388. ]
  389. },
  390. {
  391. "cell_type": "markdown",
  392. "metadata": {
  393. "deletable": false,
  394. "editable": false,
  395. "nbgrader": {
  396. "checksum": "b0c67a7805b6596f1ba87521c45df302",
  397. "grade": false,
  398. "grade_id": "cell-92211f5b42929c46",
  399. "locked": true,
  400. "schema_version": 1,
  401. "solution": false
  402. }
  403. },
  404. "source": [
  405. "## Part B. The Hat Check Problem.\n",
  406. "\n",
  407. "There is a coat check at a party, where an attendant stores everyone’s hat while they attend the party. The attendant receives the N hats from everyone attending (all attendees come with a hat). Unfortunately, the coat check attendant forgets which hat belongs to whom. Rather than admitting a mistake, the attendant simply returns random hats back to the party goers. \n",
  408. "What is the average number of correct hats returned? Here are some guiding questions to help you to simulate this problem. \n",
  409. "\n",
  410. "## Question 1. \n",
  411. "Knowing that everyone’s hats are unique and every guest has a hat. Do you need to generate a random sample in a similar way as what you did for the hiring assistant problem? "
  412. ]
  413. },
  414. {
  415. "cell_type": "markdown",
  416. "metadata": {
  417. "deletable": false,
  418. "nbgrader": {
  419. "checksum": "259c6115bee56676178f28ab36d6db2f",
  420. "grade": true,
  421. "grade_id": "cell-e786799fc4eb1499",
  422. "locked": false,
  423. "points": 0,
  424. "schema_version": 1,
  425. "solution": true
  426. }
  427. },
  428. "source": [
  429. "That would be the case, only if we want to know who got the right hat. In this case, it can be built a similar code"
  430. ]
  431. },
  432. {
  433. "cell_type": "markdown",
  434. "metadata": {
  435. "deletable": false,
  436. "editable": false,
  437. "nbgrader": {
  438. "checksum": "c9f8182f3dd59f572cb797f373fb7464",
  439. "grade": false,
  440. "grade_id": "cell-e2f68e2bd4c2d099",
  441. "locked": true,
  442. "schema_version": 1,
  443. "solution": false
  444. }
  445. },
  446. "source": [
  447. "## Question 2. \n",
  448. "Which of the following commands do you think is the Pythonic way to implement that? \n",
  449. "```\n",
  450. "import numpy as np\n",
  451. "n = 100 #the number of party attendants `\n",
  452. "```\n",
  453. "**Command 1. **\n",
  454. "```\n",
  455. "hat_list = [np.random.integers(0,n) for i in range(n)]`\n",
  456. "```\n",
  457. "**Command 2.**\n",
  458. "```\n",
  459. "hat_list = list(range(n)) \n",
  460. "np.random.shuffle(hat_list) \n",
  461. "```\n",
  462. "**Command 3.**\n",
  463. "```\n",
  464. "hat_list = np.random.sample(n)\n",
  465. "```"
  466. ]
  467. },
  468. {
  469. "cell_type": "markdown",
  470. "metadata": {
  471. "deletable": false,
  472. "nbgrader": {
  473. "checksum": "b5e83025692b2772640e9e58f0f36af1",
  474. "grade": true,
  475. "grade_id": "cell-b8da78e72c1c0738",
  476. "locked": false,
  477. "points": 0,
  478. "schema_version": 1,
  479. "solution": true
  480. }
  481. },
  482. "source": [
  483. "Command 2"
  484. ]
  485. },
  486. {
  487. "cell_type": "markdown",
  488. "metadata": {
  489. "deletable": false,
  490. "editable": false,
  491. "nbgrader": {
  492. "checksum": "ec25d5c32cc709928fa50666f21d9808",
  493. "grade": false,
  494. "grade_id": "cell-8915979a0b8cf6ce",
  495. "locked": true,
  496. "schema_version": 1,
  497. "solution": false
  498. }
  499. },
  500. "source": [
  501. "## Question 3.\n",
  502. "Now write a function `hat_check(N)` that has: \n",
  503. "* Input: N the number of party attendants. \n",
  504. "* Output: the number of hats correctly returned despite the fact that hats are randomly handed back to the guests.\n",
  505. "\n",
  506. "You should use the command you picked for question 2. "
  507. ]
  508. },
  509. {
  510. "cell_type": "code",
  511. "execution_count": null,
  512. "metadata": {
  513. "deletable": false,
  514. "nbgrader": {
  515. "checksum": "c37f6cdc2ca8cbb92644fa2746445779",
  516. "grade": true,
  517. "grade_id": "cell-c8499aeb1b1d76c7",
  518. "locked": false,
  519. "points": 0,
  520. "schema_version": 1,
  521. "solution": true
  522. }
  523. },
  524. "outputs": [],
  525. "source": [
  526. "# YOUR CODE HERE\n",
  527. "raise NotImplementedError()"
  528. ]
  529. },
  530. {
  531. "cell_type": "markdown",
  532. "metadata": {
  533. "deletable": false,
  534. "editable": false,
  535. "nbgrader": {
  536. "checksum": "1ff8b95312de63513a2107ffb7ab9d5a",
  537. "grade": false,
  538. "grade_id": "cell-086d4cc0fc5b0155",
  539. "locked": true,
  540. "schema_version": 1,
  541. "solution": false
  542. }
  543. },
  544. "source": [
  545. "## Question 4.\n",
  546. "\n",
  547. "Plot a curve with the x-axis showing the total number of party attendants and the y-axis showing the average number of hats correctly returned. As always, remember to run several trials. "
  548. ]
  549. },
  550. {
  551. "cell_type": "code",
  552. "execution_count": null,
  553. "metadata": {
  554. "deletable": false,
  555. "nbgrader": {
  556. "checksum": "c4d1251529b962f3d3ce28f6ac9f244e",
  557. "grade": true,
  558. "grade_id": "cell-597031ea2a5a512a",
  559. "locked": false,
  560. "points": 0,
  561. "schema_version": 1,
  562. "solution": true
  563. }
  564. },
  565. "outputs": [],
  566. "source": [
  567. "# YOUR CODE HERE\n",
  568. "raise NotImplementedError()"
  569. ]
  570. },
  571. {
  572. "cell_type": "markdown",
  573. "metadata": {
  574. "deletable": false,
  575. "editable": false,
  576. "nbgrader": {
  577. "checksum": "aad5d529ed9af56148bfc12691cdb950",
  578. "grade": false,
  579. "grade_id": "cell-f74b2078132a5177",
  580. "locked": true,
  581. "schema_version": 1,
  582. "solution": false
  583. }
  584. },
  585. "source": [
  586. "## [Optional] Question 5.\n",
  587. "As $N$ tends to infinity, the number of correct hats returned tends towards a well-known statistical distribution. State the distribution with all its parameters. Plot several samples using your code. Does the empirical distribution match your theoretical prediction?"
  588. ]
  589. },
  590. {
  591. "cell_type": "markdown",
  592. "metadata": {
  593. "deletable": false,
  594. "nbgrader": {
  595. "checksum": "33f94a80e6d5d9c371e6c39790bd67eb",
  596. "grade": true,
  597. "grade_id": "cell-32fe26c1d99fdd2a",
  598. "locked": false,
  599. "points": 0,
  600. "schema_version": 1,
  601. "solution": true
  602. }
  603. },
  604. "source": [
  605. "YOUR ANSWER HERE"
  606. ]
  607. }
  608. ],
  609. "metadata": {
  610. "kernelspec": {
  611. "display_name": "Python 3",
  612. "language": "python",
  613. "name": "python3"
  614. },
  615. "language_info": {
  616. "codemirror_mode": {
  617. "name": "ipython",
  618. "version": 3
  619. },
  620. "file_extension": ".py",
  621. "mimetype": "text/x-python",
  622. "name": "python",
  623. "nbconvert_exporter": "python",
  624. "pygments_lexer": "ipython3",
  625. "version": "3.6.5"
  626. }
  627. },
  628. "nbformat": 4,
  629. "nbformat_minor": 2
  630. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!