ࡱ> %'$!` \'bjbj\\ .6>>\    " Q2J "l l l l l "L$hfnl l nnl l 888n:l l 8n888l > 4 :8!0Q8QLQ8Q8>@,8l$. Qnnnn$    Assignment 1 Write Up Analysis of Optimizations Used: The two most time consuming operations in this project were building the Patricia tree from the dictionary file, and searching every valid boggle combination for a word match. In order to speed up the program it was obvious that these operations needed to be scrutinized first. Building the Patricia tree from the dictionary file was relatively straightforward, consisting of a read from file and insert method. Reading from the file is strictly linear using the built-in java.io.* library functions, but the insertion method was greatly configurable. My implementation closely resembles the algorithm described in lecture, but it adds handling for additional cases such as a blank tree or a null child node. All in all, optimizations were minimal for this phase of the boggle project. Conversely, the search phase has a very useful optimization which speeds up all cases of runtime considerably. The backbone of the speed-up was a change in the standard method for progressing through all combinations of words formulated by the boggle rules. A standard implementation would check all cases for each and every letter, for example if you had a 2x2 cube A B C D It would check A, AC, ACD, ACDB, AB, ABD, ABDC, B, BA, BAC, BACD, BD, BDC, BDCA, C, CD, CDB, CDBA, CA, CAB, CABD, D, DC, DCA, DCAB, DB, DBA, DBAC DBACusing the Patricia search function 28 times. A glance at the words shows that probably only one word would have matched a dictionary entry (CAB), and it is reasonable to say this method is inefficient. An improved method uses the structure of the Patricia tree to our advantage and continues down paths only when a valid word is possible. Also, because the rules state that words need to be at least three letters, we dont need to call the Patricia search if the length of our formed word is less then three. Our new implementation would check ACD, ABD, ABDC, BAC, BACD, BDC, CDB, CAB, CABD, DCA, and DBA calling the Patricia search function only 11 times. This improvement is even more remarkable when increasing the size of the cube, because as the size of the boggle word increases- the chance of being a prefix for any existing word in the dictionary decreases. Initially I used the check everything method for finding words in the boggle cube, and it worked fine with really small cubes (3x3). Then I tested my program with a 6x6 cube. I waited for about a minute, went to the kitchen and made a sandwich, made a phone call to the DMV, did a load of laundryand it still was progressing through the word possibilities. After switching to the improved method, the 6x6 cube took less then 50ms according to my system clock(I tested a 100x100 cube just to see what would happen and the search phase took just barely over 6 seconds). Analysis of the Worst Case Complexity for the Algorithm: The absolute worst case for my algorithm would be a cube where every combination of letters produced a valid word or valid prefix. I cannot possibly imagine a cube that would fit the worst case in our situation (bigger then a 2x2 cube), but nevertheless it may exist in some other situation. The search method for a square of k size would be very complex due to the rules of boggle, but is between k^k and k^2k. Hypothesis for the average case complexity: I hypothesize that the average runtime of my program will resemble a function f(k) = 8*k where k is the size of a side of the boggle cube. This is why: There are 17576 combinations of three letters in the English alphabet however most three letter combinations are not a word or prefix of any word. I did a quick sample word prefixes and found that in the first 269 words of our dictionary there were only 15 unique prefixes of three letters, if this trend were to continue in our dictionary we would have only about 3500 unique prefixes of three letters, thereby ending the thread of boggle combinations of three letters in about 80% of the cases (assuming every letter has a equal likelihood of being on the boggle board for simplicity). As a boggle string gets longer, even less prefix possibilities exist; for guessing purposes Ill say that only 20% of the strings that matched or were a prefix with three letters will match or be a prefix with four letters. At this point the drop off becomes even more extreme as the number of possible words in the dictionary shrinks to about 10% of those that survived the last cut. Therefore only 1 in 5 combos will go beyond 3, 1 in 25 will go beyond 4 letters, and 1 in 250 will go beyond 5 letters. Additionally, there are 8 maximum possibilities for 3 letters in our boggle board. This roughly makes the average number of times search is called in our program 8*k. The total runtime= (constant time to build Patricia tree) + (time to build Boggle board) + (time to find Boggle words) + (time to sort and remove duplicates of found words) + (time to print out words). Results of Experimentations: Next page(Times in ms). Patricia tree build time average: 1547 ms Sort/Delete/Output to file average: 16 ms  EMBED Excel.Sheet.8   SUM()  Discussion of Experiment Procedure: I added counters to my driver file to measure the results of different sized boards. I generated three different boards for each size and ran the program three times for each to average out the figures. The experiment attempted to show the relationship of the size of the boggle board with the total runtime, and number of times the Patricia search (String) function was called. The results show that there is a constant runtime of around 1581ms that is not related to the search (String) function. I singled out the Patricia tree building section of the program and found that it took on average 1540ms. Additionally Id like to add that measuring time in this program is largely dependent on outside factors(such as CPU speed, load, ect) and oddly favors some times over others. I believe the number of times search () was called is more important because it shows how good my optimization improved the standard implementation. Explanation of Experimental Results: As you can see, my hypothesis was not very close to my results. There was no way for me to guess what the run-time would be, but I do believe that I proved that as the size of the boggle board gets larger, the runtime increases. I was also right in assuming that the runtime for building the Patricia tree was more or less a constant time, as was the runtime for the other parts of the program. My predictions were too low for a couple reasons: they did not take into account the distribution of letters increasing the chances for valid prefixes; the formula was based on assumptions from small samples; the formula did not take into account the number of found words impacting the number of times search was run. The first problem was known before the results, I simply did not go sufficiently in depth to calculate distribution of letters into my predictions. The second problem was a limited time problem; if the accuracy of the hypothesis and the project was really important, I would not have settled on a small sample. The third problem was an oversight, it makes sense that with the greater number of found words, the more times search(String) would have been called. I should of made a guess at the average number of words found and formulated it into my hypothesis. Conclusion: The results of the experiment were somewhat startling but not shocking or puzzling. I think the most educational part of the process was the optimization of the code, it really made a difference when I changed the searching procedure and perhaps I should have compared before and after optimization in my experiment as well. There are still some additional optimizations that I could revisit(sort, recursion minimization) if needed later on in the educational process, and I made sure that my code was very well documented if I do. 34789:WvQ S T { 1 2 [ ` e f '(|}~g~'(-.23EFNOPûdzǯǯǯǯǯǧ矛h53h<'hY#5hY#h(lhV) hV) h ">*h}h}>*h}h " hnhnhnh{Ih]/Ch<' h?5 h<'5h<'h<'5h<'h?5h?=9:T U 3PQv`gd_Kgd?gdY#$a$gd?\'PQ&7=uwIuwؼ~h*jhb2hrB*OJQJU^Jph!jG hrCJPJUVaJhb2B*OJQJ^Jph$jhb2B*OJQJU^Jphhc@haHh?{h<'h<'hhQ95h=LVhXfh_Kh!hhQ9h<'h535hX h(hkhYH7hycjhY#h53'vw'KL_  !!%"%.%/%F'G'H'`gdaHgdrgd?%&'?IKL(0_   n!!!"%-%.%/%n%E'\'ºh!h<'h<'5 hc@5h<'hc@5hc@haHh<'hrh<'haH5h<'hr5h53B*OJQJ^Jph$jhb2B*OJQJU^Jphhb2B*OJQJ^JphhhQ9B*OJQJ^Jph!H'I'J'K'L'M'N'O'P'Q'R'S'T'U'V'W'X'Y'Z'['\'gd?,1h/ =!"#$% #Dd Nrb  c $A? ?3"`?"msCԥV!;EnID&@=AsCԥV!;Ens CeIx͝]lTglR[UShDh`RaZIHI4]4 {m ɓR!*@<  D7BZEC%BMg;׺{v=?{zH! { I!&gׯB,'UϲGGڲ(T>ޓ#;@mTwdGkϨm=*G|{H?b?\;u\T7'fɩSm_p|]QpU\-νK=c1sM܇<. Cf|w߆J{d;j[ v_ݶ1/`ss+T&ܧ`o{aqv>ؾo=v26ݶqVdm;n[l`'cmu7vCdl%^fMGRKo~4l\A 3 sв]騁ak|nl:jD:jd!-ۥ&gv-HG[-~(tb|YK"2lϭRGmHGm [se6m 6mRGۑ3lۉlQ(̌+ l:ډta Ӳ]h.m.vHGݐϻ-ۥ^A:za{V 0|l::tta; |ֲ]99vHG-ۥ>D:aV#3|l:tta|ɲ]2e2ev+HGW+W,ۥ"]eخ٪IIf\ϓRG7n2l7!oZKB:Ű݂|e.ut6ve; b?[uT)udmO.uF&h æ6.uT%uTŰzۥDet[RGD=ΰ=.gjjqՀjgz zz.uTtT˰Ղjg ks::NNV̸l: " ((=ۥQl:jD:jd!?gQQ$g"HGf\QDzK"2l^.uh?öt_zK@::RGo"ɰ)gqg!C !!.ut0vttXzKA::°RGo!Ű%gq g  .ut$vttRzKB::ŰRG ð#]hښBY񚵆zE0auz||1_ nv'/O/8oѓxxC=/]7cW(&~}PXw771[ګn\{Z9tO_`)"q-^[A;6gxG˟toU~O='%t2~>^klA6kyj[NK8G`uOM n|?kM(w-XlP\"Zc@SKc[\99 _mms?%sB/ۢ9T|OP4b c l:Զ`{^gBZ~A6MȂbl t?O.w}{{sM5V~E_.猷1B|hWǟ\W?<27}-X}O3g\R|/*sFvsFH8۫o w-UT٦4P6 $BNg+eugrrsRll <}r/+ w"j[))E<.V=X΃~EcTE6m񭋅"O=GuD-SS,V-1f|94|T<}T>L[jj+"}? t>L[qT>|a_9Iת oDs v3sWnkw@]oӖ"WY w3A߹ w3~}el~!8L~!ǚRߥ?mwu DCB"}[A?s~+RY1!1DŽfc&as簏8`9 q!o8qg(as < q!tstt":dA*5my@lX9o4>Bc{}kN(~>׸7ϷϫOmkqfcu ׻y]@2Jm$eE_.·iNZ܈BDVa#0s?J6s(1G3B?]4|虒a= =#e:1xOP!D3TC'xԇyxOY޳tS{ɃIȃyrzLȃXu<&!pmz<>˵RX_M0m2 y}6?yPf^o=U"ԵKq]br:iIe.ˈk\.Fz/#H{E}^1j _5L,۴]Et?ՄӖܕu(j%_cyϘ`j(3Ho"bG5MDk2O5-lo%氀9lUjx [x2{+@4xo%aMxo%jW*/_fixiqX@5K8V &V-Mi};+jnw~I5K'\nB>X,Y#i,ҪY"0(ýGFAGԧ'+:(1eG)&|6%,Y|VE~*u.#rVϋB?o~ȅcD.dG)]&|䂙_!k ki"_Qg#}Џi"4 կDM2 uEfa2 v[}-%L~WTak<'L2u51ޟu˘E1,GcZ?u=zG=h'"Sͣܲ'|KxMW!*͜[lUٺ[7fnlCma3ېcd"s7+ZV˰sk1[7bf̹m 1l\ 9f2\j~/ٖ3lˁmedDl [%UZKVð[ed edkAl- [ XKNɰu[edۃ0l{med edGl [?[K6 ۀedFl 0 [K16ưۘedn0l7ed˓ly`듞8b;ΰҳ]Alg3vFzKQ6ʰۨllma3hމ Xqv}?۾Oo Y h  !"#4&)35+,-./0126C89:;<=>?@ABRoot Entry  F7(Data #WordDocument .6ObjectPool17_1199557526 F10b3Ole CompObjfObjInfo  FMicrosoft Excel WorksheetBiff8Excel.Sheet.89q Oh+'0@H\p  josh baer  josh baer Microsoft Excel@t @Z吏 Workbook *SummaryInformation( DocumentSummaryInformation81Table7Q F\p josh baer Ba= =--<X@"1Arial1Arial1Arial1Arial1Arial"$"#,##0_);\("$"#,##0\)!"$"#,##0_);[Red]\("$"#,##0\)""$"#,##0.00_);\("$"#,##0.00\)'""$"#,##0.00_);[Red]\("$"#,##0.00\)7*2_("$"* #,##0_);_("$"* \(#,##0\);_("$"* "-"_);_(@_).))_(* #,##0_);_(* \(#,##0\);_(* "-"_);_(@_)?,:_("$"* #,##0.00_);_("$"* \(#,##0.00\);_("$"* "-"??_);_(@_)6+1_(* #,##0.00_);_(* \(#,##0.00\);_(* "-"??_);_(@_)"Yes";"Yes";"No""True";"True";"False""On";"On";"Off"],[$ -2]\ #,##0.00_);[Red]\([$ -2]\ #,##0.00\)                + ) , *  H `Sheet1T AverageTest 1Test 2Test 3Size = 1Size = 3Size = 5Size = 7Size = 9 Predicted# of times search() was calledV ] F  dMbP?_*+%"??U}           l@@(@#@ %B~ @ @X@@@@#UUUUU@ %BF@l@h@$@#@ %BM@(@h@l@#UUUUU@ %B #P@ %B ~ @  ~ R@  @d@@@# @ % B  z@d@@@# UUUUU@ % B   @@d@@# UUUUU9@ % B #҂@ % B ~ d@  !i@  ܒ@@d@$@#x@ %B@d@ @@#̙@ %B(@d@d@@#UUUUU@ %B #UUUUU@ %B ~ @  x@1 l@\@\@@#@ %BX@@@@#̙@ %B@@\@@#H@ %B #UUUUU@ %B ~ @  !@  2PW"WSSS.WSSSEWSSSAWSSS>@7 ՜.+,0 PXd lt| 1A Sheet1  WorksheetsOh+'0|  8 D P\dlt Joshua Baer josh baerLݧ17 ^UߗQ 0wSummaryInformation( DocumentSummaryInformation8$CompObjq Normal.dot Kirk Pruhs4Microsoft Office Word@%5@M @{՜.+,0 hp|  8L  Joshua Baer TitleD@D NormalCJ_HaJmH nHsH tHDAD Default Paragraph FontRiR  Table Normal4 l4a (k(No List$L$ ?Date\69:TU3   P Q   vw'KL_!"./FGHIJKLMNOPQRSTUVWXYZ[^0000000000000000000000000000000000000000000000000000000000000000000000000P\'vH'\'\'%\: _1199554756 _1199554906 _1199554915 _1199554991 _1199554997 _1199555025 _1199555036 _1199555167 _1199555268 _1199555405 _1199555428 _1199555566 _1199556068 _1199556560 _1199556629 _1199556672 _1199556967 _1199557526^@@@@@@@@@ @ @ @ @ @@@@@^^X #_X T`X v#aX T#aa^dd^8*urn:schemas-microsoft-com:office:smarttagsCity9*urn:schemas-microsoft-com:office:smarttagsState9*urn:schemas-microsoft-com:office:smarttagsplace ae 03^k m ^33339 w'J"-^^ X V) b2 "Y#<'53YH7hQ9c@]/C{I_K=LVXfycj(lm?{nrN]}?d(aHeV!Zk@P')\@@UnknownGz Times New Roman5Symbol3& z Arial?5 z Courier New;SimSun[SO"qh&{8824dLL 2HP)??2 Joshua Baer josh baer Kirk Pruhs  FMicrosoft Office Word Document MSWordDocWord.Document.89q