API tools faq
paste
Advertisement
olemis

Coursera algs4partII-004 - Assignment 1

olemis
Dec 25th, 2014
408
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 19.47 KB | None | 0 0
raw download clone embed print report
  1. Algorithms, Part II
  2. by Kevin Wayne, Robert Sedgewick
  3.  
  4. Programming Assignment 1: WordNet | wordnet.zip
  5. Submission time Wed-24-Dec 21:28:41
  6. Raw Score 98.14 / 100.00
  7. Feedback See the Assessment Guide for information on how to read this report.
  8. Assessment Summary
  9. Compilation: PASSED
  10. Style: FAILED
  11. Findbugs: No potential bugs found.
  12. API: PASSED
  13.  
  14. Correctness: 34/35 tests passed
  15. Memory: 4/4 tests passed
  16. Timing: 16/16 tests passed
  17.  
  18. Aggregate score: 98.14% [Correctness: 65%, Memory: 10%, Timing: 25%, Style: 0%]
  19. Assessment Details
  20. The following files were submitted:
  21. ----------------------------------
  22. total 28K
  23. -rw-r--r-- 1 1.4K Dec 25 05:30 Outcast.java
  24. -rw-r--r-- 1 5.2K Dec 25 05:30 SAP.java
  25. -rw-r--r-- 1 5.0K Dec 25 05:30 WordNet.java
  26. -rw-r--r-- 1 4.7K Dec 25 05:30 studentSubmission.zip
  27.  
  28.  
  29. ******************************************************************************
  30. * compiling
  31. ******************************************************************************
  32.  
  33.  
  34. % javac SAP.java
  35. *-----------------------------------------------------------
  36. ================================================================
  37.  
  38. % javac WordNet.java
  39. *-----------------------------------------------------------
  40. ================================================================
  41.  
  42. % javac Outcast.java
  43. *-----------------------------------------------------------
  44. ================================================================
  45.  
  46.  
  47.  
  48. % checkstyle *.java
  49. *-----------------------------------------------------------
  50. SAP.java:4:8: Unused import - java.util.Map.Entry.
  51. SAP.java:26:1: File contains tab characters (this is the first instance).
  52. SAP.java:43:39: Name '_this' must match pattern '^[a-z][a-zA-Z0-9]*$|^[A-Z][A-Z_0-9]*$'.
  53. SAP.java:44:32: Anonymous inner class length is 22 lines (max allowed is 20).
  54. SAP.java:54:51: 'item' hides a field.
  55. SAP.java:92:26: Name '_v' must match pattern '^[a-z][a-zA-Z0-9]*$|^[A-Z][A-Z_0-9]*$'.
  56. SAP.java:96:26: Name '_w' must match pattern '^[a-z][a-zA-Z0-9]*$|^[A-Z][A-Z_0-9]*$'.
  57. SAP.java:125:57: '?' is not preceded with whitespace.
  58. SAP.java:125:57: Avoid inline conditionals.
  59. SAP.java:131:56: '?' is not preceded with whitespace.
  60. SAP.java:131:56: Avoid inline conditionals.
  61. SAP.java:131:67: ':' is not preceded with whitespace.
  62. SAP.java:132:68: '?' is not preceded with whitespace.
  63. SAP.java:132:68: Avoid inline conditionals.
  64. SAP.java:132:72: ':' is not preceded with whitespace.
  65. SAP.java:138:45: Name '_l' must match pattern '^[a-z][a-zA-Z0-9]*$|^[A-Z][A-Z_0-9]*$'.
  66. WordNet.java:28:1: File contains tab characters (this is the first instance).
  67. WordNet.java:78:17: Catching 'Exception' is not allowed.
  68. WordNet.java:85:9: Constructor definition in wrong order.
  69. Outcast.java:1:8: Unused import - java.util.Map.Entry.
  70. Outcast.java:23:1: File contains tab characters (this is the first instance).
  71. Outcast.java:36:37: Name '_d' must match pattern '^[a-z][a-zA-Z0-9]*$|^[A-Z][A-Z_0-9]*$'.
  72. Outcast.java:44:26: Name '_d' must match pattern '^[a-z][a-zA-Z0-9]*$|^[A-Z][A-Z_0-9]*$'.
  73. ================================================================
  74.  
  75.  
  76. % findbugs *.class
  77. *-----------------------------------------------------------
  78. ================================================================
  79.  
  80.  
  81. Testing the APIs of your programs.
  82. *-----------------------------------------------------------
  83. SAP:
  84.  
  85. WordNet:
  86.  
  87. Outcast:
  88.  
  89. ================================================================
  90.  
  91.  
  92. ******************************************************************************
  93. * correctness
  94. ******************************************************************************
  95.  
  96. Testing methods in SAP
  97. *-----------------------------------------------------------
  98. Running 19 total tests.
  99.  
  100. Test 1: test length() and ancestor() on fixed digraphs
  101. * digraph1.txt
  102. * digraph2.txt
  103. * digraph3.txt
  104. * digraph4.txt
  105. * digraph5.txt
  106. * digraph6.txt
  107. * digraph9.txt
  108. ==> passed
  109.  
  110. Test 2: check length() and ancestor() on WordNet digraph
  111. * 100 random vertex pairs in digraph-wordnet.txt
  112. ==> passed
  113.  
  114. Test 3: check length() and ancestor() on directed paths
  115. * 5
  116. * 10
  117. * 20
  118. * 50
  119. * 100
  120. ==> passed
  121.  
  122. Test 4: check length() and ancestor() on directed cycles
  123. * 5
  124. * 10
  125. * 20
  126. * 50
  127. * 100
  128. ==> passed
  129.  
  130. Test 5: check length() and ancestor() on complete graphs
  131. * 5
  132. * 10
  133. * 20
  134. * 50
  135. ==> passed
  136.  
  137. Test 6: check length() and ancestor() on tournament digraphs
  138. * 5
  139. * 10
  140. * 20
  141. * 50
  142. ==> passed
  143.  
  144. Test 7: check length() and ancestor() on complete binary trees
  145. * 5
  146. * 10
  147. * 20
  148. * 50
  149. * 100
  150. ==> passed
  151.  
  152. Test 8: check length() and ancestor() on random DAGs
  153. * 5 vertices, 8 edges
  154. * 10 vertices, 40 edges
  155. * 20 vertices, 100 edges
  156. ==> passed
  157.  
  158. Test 9: check length() and ancestor() on random rooted-in DAGs
  159. * 5 vertices, 8 edges
  160. * 10 vertices, 40 edges
  161. * 20 vertices, 100 edges
  162. ==> passed
  163.  
  164. Test 10: check length() and ancestor() on random rooted-out DAGs
  165. * 5 vertices, 8 edges
  166. * 10 vertices, 40 edges
  167. * 20 vertices, 100 edges
  168. ==> passed
  169.  
  170. Test 11: check length() and ancestor() on random rooted-in trees
  171. * 5 vertices
  172. * 10 vertices
  173. * 20 vertices
  174. ==> passed
  175.  
  176. Test 12: check length() and ancestor() on random rooted-out trees
  177. * 5 vertices
  178. * 10 vertices
  179. * 20 vertices
  180. ==> passed
  181.  
  182. Test 13: check length() and ancestor() on random simple digraphs
  183. * 5 vertices, 8 edges
  184. * 10 vertices, 40 edges
  185. * 20 vertices, 100 edges
  186. ==> passed
  187.  
  188. Test 14: check whether two SAP objects can be created at the same time
  189. * digraph1.txt and digraph2.txt
  190. * digraph3.txt and digraph4.txt
  191. * digraph5.txt and digraph6.txt
  192. * digraph2.txt and digraph1.txt
  193. ==> passed
  194.  
  195. Test 15: check whether SAP is immutable
  196. * digraph1.txt
  197. * digraph2.txt
  198. * digraph3.txt
  199. * digraph4.txt
  200. * digraph5.txt
  201. * digraph6.txt
  202. * digraph-ambiguous-ancestor.txt
  203. ==> passed
  204.  
  205. Test 16: test invalid arguments to length() and ancestor() in digraph1.txt
  206. * v = -1, w = 0
  207. * v = 0, w = -1
  208. * v = 13, w = 0
  209. * v = 0, w = 13
  210. * v = -1 2 7 , w = 1 4 6 10 11
  211. * v = 2 7 , w = -1 1 4 6 10 11
  212. * v = 13 2 7 , w = 1 4 6 10 11
  213. * v = 2 7 , w = 13 1 4 6 10 11
  214. ==> passed
  215.  
  216. Test 17: test length() and ancestor() with Iterable arguments
  217. * 100 random subsets of 1 and 1 vertices in digraph-wordnet.txt
  218. * 100 random subsets of 1 and 2 vertices in digraph-wordnet.txt
  219. * 100 random subsets of 2 and 1 vertices in digraph-wordnet.txt
  220. * 100 random subsets of 2 and 2 vertices in digraph-wordnet.txt
  221. * 100 random subsets of 3 and 11 vertices in digraph-wordnet.txt
  222. * 100 random subsets of 11 and 3 vertices in digraph-wordnet.txt
  223. * 100 random subsets of 0 and 5 vertices in digraph-wordnet.txt
  224. * 100 random subsets of 5 and 0 vertices in digraph-wordnet.txt
  225. * 100 random subsets of 0 and 0 vertices in digraph-wordnet.txt
  226. ==> passed
  227.  
  228. Test 18: Check Iterable version of length() and ancestor() with null arguments
  229. ==> passed
  230.  
  231. Test 19: random calls to length() and ancestor(), with probabilities
  232. p1 and p2, respectively
  233. * random calls in a random rooted DAG (20 vertices, 100 edges)
  234. (p1 = 0.5, p2 = 0.5)
  235. * random calls in a random digraph (20 vertices, 100 edges)
  236. (p1 = 0.5, p2 = 0.5)
  237. ==> passed
  238.  
  239.  
  240. Total: 19/19 tests passed!
  241.  
  242. ================================================================
  243.  
  244. ******************************************************************************
  245. * correctness (substituting reference SAP.java)
  246. ******************************************************************************
  247.  
  248. Testing methods in WordNet
  249. *-----------------------------------------------------------
  250. Running 14 total tests.
  251.  
  252. Test 1: test distance() of random noun pairs
  253. * 1000 pairs using synsets = synsets.txt; hypernyms = hypernyms.txt
  254. ==> passed
  255.  
  256. Test 2: test distance() of all noun pairs
  257. * synsets = synsets15.txt; hypernyms = hypernyms15Path.txt
  258. * synsets = synsets15.txt; hypernyms = hypernyms15Tree.txt
  259. * synsets = synsets6.txt; hypernyms = hypernyms6TwoAncestors.txt
  260. * synsets = synsets11.txt; hypernyms = hypernyms11AmbiguousAncestor.txt
  261. * synsets = synsets8.txt; hypernyms = hypernyms8ModTree.txt
  262. * synsets = synsets8.txt; hypernyms = hypernyms8WrongBFS.txt
  263. * synsets = synsets11.txt; hypernyms = hypernyms11ManyPathsOneAncestor.txt
  264. * synsets = synsets8.txt; hypernyms = hypernyms8ManyAncestors.txt
  265. ==> passed
  266.  
  267. Test 3: test distance() of random noun pairs
  268. * 1000 pairs using synsets = synsets100-subgraph.txt; hypernyms = hypernyms100-subgraph.txt
  269. * 1000 pairs using synsets = synsets500-subgraph.txt; hypernyms = hypernyms500-subgraph.txt
  270. * 1000 pairs using synsets = synsets1000-subgraph.txt; hypernyms = hypernyms1000-subgraph.txt
  271. ==> passed
  272.  
  273. Test 4: test sap() of random noun pairs
  274. * 1000 pairs using synsets = synsets.txt; hypernyms = hypernyms.txt
  275. ==> passed
  276.  
  277. Test 5: test sap() of all noun pairs
  278. * synsets = synsets15.txt; hypernyms = hypernyms15Path.txt
  279. * synsets = synsets15.txt; hypernyms = hypernyms15Tree.txt
  280. * synsets = synsets6.txt; hypernyms = hypernyms6TwoAncestors.txt
  281. * synsets = synsets11.txt; hypernyms = hypernyms11AmbiguousAncestor.txt
  282. * synsets = synsets8.txt; hypernyms = hypernyms8ModTree.txt
  283. * synsets = synsets8.txt; hypernyms = hypernyms8WrongBFS.txt
  284. * synsets = synsets11.txt; hypernyms = hypernyms11ManyPathsOneAncestor.txt
  285. * synsets = synsets8.txt; hypernyms = hypernyms8ManyAncestors.txt
  286. ==> passed
  287.  
  288. Test 6: test sap() of random noun pairs
  289. * 1000 pairs using synsets = synsets100-subgraph.txt; hypernyms = hypernyms100-subgraph.txt
  290. * 1000 pairs using synsets = synsets500-subgraph.txt; hypernyms = hypernyms500-subgraph.txt
  291. * 1000 pairs using synsets = synsets1000-subgraph.txt; hypernyms = hypernyms1000-subgraph.txt
  292. ==> passed
  293.  
  294. Test 7: check whether WordNet is immutable
  295. * synsets = synsets.txt; hypernyms = hypernyms.txt
  296. ==> passed
  297.  
  298. Test 8: check that constructor throws an IllegalArgumentException when the input is not a rooted DAG
  299. * synsets3.txt, hypernyms3InvalidTwoRoots.txt
  300. - failed to throw a java.lang.IllegalArgumentException
  301. * synsets3.txt, hypernyms3InvalidCycle.txt
  302. - failed to throw a java.lang.IllegalArgumentException
  303. * synsets6.txt, hypernyms6InvalidTwoRoots.txt
  304. - failed to throw a java.lang.IllegalArgumentException
  305. * synsets6.txt, hypernyms6InvalidCycle.txt
  306. - failed to throw a java.lang.IllegalArgumentException
  307. * synsets6.txt, hypernyms6InvalidCycle+Path.txt
  308. - failed to throw a java.lang.IllegalArgumentException
  309. ==> FAILED
  310.  
  311. Test 9: check that distance() and sap() throw an IllegalArgumentException
  312. when either argument is not a WordNet noun
  313. * synsets15.txt, hypernyms15Tree.txt, invalid noun = invalid
  314. * synsets15.txt, hypernyms15Tree.txt, invalid noun = b
  315. * synsets15.txt, hypernyms15Tree.txt, invalid noun = eleventeen
  316. * synsets15.txt, hypernyms15Tree.txt, invalid noun = INVALID
  317. ==> passed
  318.  
  319. Test 10: check isNoun()
  320. * synsets = synsets.txt; hypernyms = hypernyms.txt
  321. * synsets = synsets15.txt; hypernyms = hypernyms15Path.txt
  322. * synsets = synsets8.txt; hypernyms = hypernyms8ModTree.txt
  323. ==> passed
  324.  
  325. Test 11: check nouns()
  326. * synsets = synsets.txt; hypernyms = hypernyms.txt
  327. * synsets = synsets15.txt; hypernyms = hypernyms15Path.txt
  328. * synsets = synsets8.txt; hypernyms = hypernyms8ModTree.txt
  329. ==> passed
  330.  
  331. Test 12: check whether two WordNet objects can be created at the same time
  332. * synsets1 = synsets15.txt; hypernyms1 = hypernyms15Tree.txt
  333. synsets2 = synsets15.txt; hypernyms2 = hypernyms15Path.txt
  334. * synsets1 = synsets.txt; hypernyms1 = hypernyms.txt
  335. synsets2 = synsets15.txt; hypernyms2 = hypernyms15Path.txt
  336. ==> passed
  337.  
  338. Test 13: call distance(), sap(), and isNoun() with null arguments
  339. * synsets15.txt, hypernyms15Path.txt
  340. ==> passed
  341.  
  342. Test 14: random calls to isNoun(), distance(), and sap(), with
  343. probabilities p1, p2, and p3, respectively
  344. * 100 random calls (p1 = 0.5, p2 = 0.5, p3 = 0.0)
  345. * 100 random calls (p1 = 0.5, p2 = 0.0, p3 = 0.5)
  346. * 100 random calls (p1 = 0.0, p2 = 0.5, p3 = 0.5)
  347. * 100 random calls (p1 = 0.2, p2 = 0.4, p3 = 0.4)
  348. ==> passed
  349.  
  350.  
  351. Total: 13/14 tests passed!
  352.  
  353. ================================================================
  354.  
  355. ******************************************************************************
  356. * correctness (substituting reference SAP.java and WordNet.java)
  357. ******************************************************************************
  358.  
  359. Testing methods in Outcast
  360. *-----------------------------------------------------------
  361. Running 2 total tests.
  362.  
  363. Test 1: test outcast() on WordNet digraph
  364. (synsets = synsets.txt; hypernyms = hypernyms.txt)
  365. * outcast2.txt
  366. * outcast3.txt
  367. * outcast4.txt
  368. * outcast5.txt
  369. * outcast5a.txt
  370. * outcast7.txt
  371. * outcast8.txt
  372. * outcast8a.txt
  373. * outcast8b.txt
  374. * outcast8c.txt
  375. * outcast9.txt
  376. * outcast9a.txt
  377. * outcast10.txt
  378. * outcast10a.txt
  379. * outcast11.txt
  380. * outcast12.txt
  381. * outcast12a.txt
  382. * outcast17.txt
  383. * outcast20.txt
  384. * outcast29.txt
  385. ==> passed
  386.  
  387. Test 2: test outcast() on WordNet subgraph
  388. (synsets = synsets50000-subgraph.txt; hypernyms = hypernyms50000-subgraph.txt)
  389. * outcast2.txt
  390. * outcast3.txt
  391. * outcast5.txt
  392. * outcast5a.txt
  393. * outcast7.txt
  394. * outcast8.txt
  395. * outcast8b.txt
  396. * outcast8c.txt
  397. * outcast9.txt
  398. * outcast10.txt
  399. * outcast11.txt
  400. ==> passed
  401.  
  402.  
  403. Total: 2/2 tests passed!
  404.  
  405. ================================================================
  406.  
  407. ******************************************************************************
  408. * memory
  409. ******************************************************************************
  410.  
  411. Computing memory of SAP
  412. *-----------------------------------------------------------
  413. Running 1 total tests.
  414.  
  415. student memory = 8019944 bytes
  416. reference memory = 8019944 bytes
  417. ratio = 1.00
  418. maximum allowed ratio = 2.50
  419.  
  420. vertices = 82192
  421. edges = 84505
  422.  
  423. Total: 1/1 tests passed!
  424.  
  425. ================================================================
  426.  
  427.  
  428.  
  429. Computing memory of WordNet
  430. *-----------------------------------------------------------
  431. Running 3 total tests.
  432.  
  433. Test 1a: test memory of WordNet object
  434. * synsets = synsets1000-subgraph.txt; hypernyms = hypernyms1000-subgraph.txt
  435. - student memory = 881048 bytes
  436. - reference memory = 1190720 bytes
  437. - number vertices = 1000
  438. - number of edges = 1008
  439. - student / reference ratio = 0.7
  440. - maximum allowed rato = 2.0
  441.  
  442. ==> passed
  443.  
  444. Test 1b: test memory of WordNet object
  445. * synsets = synsets5000-subgraph.txt; hypernyms = hypernyms5000-subgraph.txt
  446. - student memory = 4383648 bytes
  447. - reference memory = 5912456 bytes
  448. - number vertices = 5000
  449. - number of edges = 5059
  450. - student / reference ratio = 0.7
  451. - maximum allowed rato = 2.0
  452.  
  453. ==> passed
  454.  
  455. Test 1c: test memory of WordNet object
  456. * synsets = synsets10000-subgraph.txt; hypernyms = hypernyms10000-subgraph.txt
  457. - student memory = 10437736 bytes
  458. - reference memory = 13776128 bytes
  459. - number vertices = 10000
  460. - number of edges = 10087
  461. - student / reference ratio = 0.8
  462. - maximum allowed rato = 2.0
  463.  
  464. ==> passed
  465.  
  466. Total: 3/3 tests passed!
  467.  
  468. ================================================================
  469.  
  470.  
  471.  
  472. ******************************************************************************
  473. * timing
  474. ******************************************************************************
  475.  
  476. Timing SAP
  477. *-----------------------------------------------------------
  478. Running 7 total tests.
  479.  
  480. Test 1: time SAP constructor
  481. * digraph-wordnet.txt
  482. - student solution time = 0.10 seconds
  483. - maximum allowed time = 1.00 seconds
  484. ==> passed
  485.  
  486. Test 2a-c: time length() and ancestor() with random pairs of vertices
  487. * digraph-wordnet.txt
  488. - reference solution calls per second: 182119.33
  489. - student solution calls per second: 202164.00
  490. - reference / student ratio: 0.90
  491.  
  492. => passed student <= 25000x reference
  493. => passed student <= 2500x reference
  494. => passed student <= 250x reference
  495. => BONUS student <= 10.0x reference
  496.  
  497. Test 3a-c: time length() and ancestor() with random sets of 5 vertices
  498. * digraph-wordnet.txt
  499. - reference solution calls per second: 40318.00
  500. - student solution calls per second: 55642.00
  501. - reference / student ratio: 0.72
  502.  
  503. => passed student <= 10000x reference
  504. => passed student <= 1000x reference
  505. => passed student <= 100x reference
  506. => BONUS student <= 10.0x reference
  507.  
  508.  
  509. Total: 9/7 tests passed!
  510.  
  511. ================================================================
  512.  
  513.  
  514.  
  515. ******************************************************************************
  516. * timing (substituting reference SAP.java)
  517. ******************************************************************************
  518.  
  519. Timing WordNet
  520. *-----------------------------------------------------------
  521. Running 8 total tests.
  522.  
  523. Test 1: timing WordNet constructor
  524. * synsets = synsets.txt; hypernyms = hypernyms.txt
  525. - student constructor time = 1.90 seconds
  526. - maximum allowed time = 10.00 seconds
  527. ==> passed
  528.  
  529. Test 2: check that exactly one SAP object created per WordNet object
  530. ==> passed
  531.  
  532. Test 3a-c: timing sap() and distance() with random nouns
  533. * synsets = synsets.txt; hypernyms = hypernyms.txt
  534. - reference solution calls per second: 44430.60
  535. - student solution calls per second: 2004.40
  536. - reference / student ratio: 22.17
  537.  
  538. => passed student <= 10000x reference
  539. => passed student <= 1000x reference
  540. => passed student <= 100x reference
  541. => FAILED student <= 10x reference
  542. => FAILED student <= 5x reference
  543.  
  544. Test 4: timing isNoun() with random nouns
  545. * synsets = synsets.txt; hypernyms = hypernyms.txt
  546. - reference solution calls per second: 382927.00
  547. - student solution calls per second: 592821.00
  548. - reference / student ratio: 0.65
  549. - allowed ratio: 2.00
  550. ==> passed
  551.  
  552. Total: 6/8 tests passed!
  553.  
  554. ================================================================
  555.  
  556.  
  557.  
  558. ******************************************************************************
  559. * timing (with reference SAP.java and WordNet.java)
  560. ******************************************************************************
  561.  
  562. Timing Outcast
  563. *-----------------------------------------------------------
  564. Running 1 total tests.
  565.  
  566. 2.86 seconds to build WordNet
  567.  
  568. Computing time to find outcasts. Total time must not exceed 5 seconds.
  569.  
  570.  
  571. filename N time
  572. -----------------------------
  573. outcast4.txt 4 0.00
  574. outcast5.txt 5 0.01
  575. outcast5a.txt 5 0.01
  576. outcast5.txt 5 0.01
  577. outcast7.txt 7 0.00
  578. outcast8.txt 8 0.01
  579. outcast8a.txt 8 0.01
  580. outcast8b.txt 8 0.01
  581. outcast8c.txt 8 0.01
  582. outcast9.txt 9 0.01
  583. outcast9a.txt 9 0.01
  584. outcast10.txt 10 0.00
  585. outcast10a.txt 10 0.00
  586. outcast11.txt 11 0.00
  587. outcast12.txt 12 0.01
  588. outcast12a.txt 12 0.01
  589. outcast20.txt 20 0.02
  590. outcast29.txt 29 0.02
  591. => passed, total elapsed time: 0.16
  592.  
  593. Total: 1/1 tests passed!
  594.  
  595. ================================================================
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!