/
CMPUT 291 W10: Mini-Project 2 Spec.mht
12262 lines (10651 loc) · 412 KB
/
CMPUT 291 W10: Mini-Project 2 Spec.mht
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
Content-Type: multipart/related; start=<op.mhtml.1268932508943.35dba95d6a4e4158@142.244.153.197>; boundary=----------5WOaLEeyljv2qAP5B4Ec8h
Content-Location: http://moodle.cs.ualberta.ca/mod/resource/view.php?id=15745
Subject: =?utf-8?Q?CMPUT=20291=20W10:=20Mini-Project=202=20Spec?=
MIME-Version: 1.0
------------5WOaLEeyljv2qAP5B4Ec8h
Content-Disposition: inline; filename=view.htm
Content-Type: text/html; charset=utf-8; name=view.htm
Content-ID: <op.mhtml.1268932508943.35dba95d6a4e4158@142.244.153.197>
Content-Location: http://moodle.cs.ualberta.ca/mod/resource/view.php?id=15745
Content-Transfer-Encoding: Quoted-Printable
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.=
org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns=3D"http://www.w3.org/1999/xhtml" dir=3D"ltr" lang=3D"en" xml=
:lang=3D"en">
<head>
<meta http-equiv=3D"Content-Type" content=3D"text/html; charset=3Dut=
f-8" />
<link rel=3D"stylesheet" type=3D"text/css" href=3D"http://moodle.cs.ualb=
erta.ca/theme/standard/styles.php" />
<link rel=3D"stylesheet" type=3D"text/css" href=3D"http://moodle.cs.ualb=
erta.ca/theme/uoa/styles.php" />
<script type=3D"text/javascript" src=3D"http://moodle.cs.ualberta.ca/li=
b/yui/yahoo/yahoo-min.js"></script><script type=3D"text/javascript" src=
=3D"http://moodle.cs.ualberta.ca/lib/yui/event/event-min.js"></script><s=
cript type=3D"text/javascript" src=3D"http://moodle.cs.ualberta.ca/lib/=
yui/connection/connection-min.js"></script><script type=3D"text/javascri=
pt" src=3D"http://moodle.cs.ualberta.ca/lib/swfobject/swfobject.js"></s=
cript><script type=3D"text/javascript">
var flashversion =3D swfobject.getFlashPlayerVersion();
YAHOO.util.Connect.asyncRequest('GET','http://moodle.cs.ualberta.ca/lo=
gin/environment.php?sesskey=3DSEBvlUyeqJ&flashversion=3D'+flashversi=
on.major+'.'+flashversion.minor+'.'+flashversion.release);
</script>
<!--[if IE 7]>
<link rel=3D"stylesheet" type=3D"text/css" href=3D"http://moodle.cs.=
ualberta.ca/theme/standard/styles_ie7.css" />
<![endif]-->
<!--[if IE 6]>
<link rel=3D"stylesheet" type=3D"text/css" href=3D"http://moodle.cs.=
ualberta.ca/theme/standard/styles_ie6.css" />
<![endif]-->
<meta name=3D"keywords" content=3D"moodle, CMPUT 291 W10: Mini-Proje=
ct 2 Spec " />
<title>CMPUT 291 W10: Mini-Project 2 Spec</title>
<link rel=3D"shortcut icon" href=3D"http://moodle.cs.ualberta.ca/the=
me/uoa/favicon.ico" />
<script type=3D"text/javascript" src=3D"http://moodle.cs.ualberta.ca=
/lib/speller/spellChecker.js"></script>
<!--<style type=3D"text/css">/*<![CDATA[*/ body{behavior:url(http://mood=
le.cs.ualberta.ca/lib/csshover.htc);} /*]]>*/</style>-->
<script type=3D"text/javascript" src=3D"http://moodle.cs.ualberta.ca/lib=
/javascript-static.js"></script>
<script type=3D"text/javascript" src=3D"http://moodle.cs.ualberta.ca/lib=
/javascript-mod.php"></script>
<script type=3D"text/javascript" src=3D"http://moodle.cs.ualberta.ca/lib=
/overlib/overlib.js"></script>
<script type=3D"text/javascript" src=3D"http://moodle.cs.ualberta.ca/lib=
/overlib/overlib_cssstyle.js"></script>
<script type=3D"text/javascript" src=3D"http://moodle.cs.ualberta.ca/lib=
/cookies.js"></script>
<script type=3D"text/javascript" src=3D"http://moodle.cs.ualberta.ca/lib=
/ufo.js"></script>
<script type=3D"text/javascript" src=3D"http://moodle.cs.ualberta.ca/lib=
/dropdown.js"></script> =
<script type=3D"text/javascript" defer=3D"defer">
//<![CDATA[
setTimeout('fix_column_widths()', 20);
//]]>
</script>
<script type=3D"text/javascript">
//<![CDATA[
function openpopup(url, name, options, fullscreen) {
var fullurl =3D "http://moodle.cs.ualberta.ca" + url;
var windowobj =3D window.open(fullurl, name, options);
if (!windowobj) {
return true;
}
if (fullscreen) {
windowobj.moveTo(0, 0);
windowobj.resizeTo(screen.availWidth, screen.availHeight);
}
windowobj.focus();
return false;
}
function uncheckall() {
var inputs =3D document.getElementsByTagName('input');
for(var i =3D 0; i < inputs.length; i++) {
inputs[i].checked =3D false;
}
}
function checkall() {
var inputs =3D document.getElementsByTagName('input');
for(var i =3D 0; i < inputs.length; i++) {
inputs[i].checked =3D true;
}
}
function inserttext(text) {
text =3D ' ' + text + ' ';
if ( opener.document.forms['theform'].message.createTextRange && opene=
r.document.forms['theform'].message.caretPos) {
var caretPos =3D opener.document.forms['theform'].message.caretPos;
caretPos.text =3D caretPos.text.charAt(caretPos.text.length - 1) =3D=
=3D ' ' ? text + ' ' : text;
} else {
opener.document.forms['theform'].message.value +=3D text;
}
opener.document.forms['theform'].message.focus();
}
function getElementsByClassName(oElm, strTagName, oClassNames){
var arrElements =3D (strTagName =3D=3D "*" && oElm.all)? oElm.all : oEl=
m.getElementsByTagName(strTagName);
var arrReturnElements =3D new Array();
var arrRegExpClassNames =3D new Array();
if(typeof oClassNames =3D=3D "object"){
for(var i=3D0; i<oClassNames.length; i++){
arrRegExpClassNames.push(new RegExp("(^|\\s)" + oClassNames[i].replac=
e(/\-/g, "\\-") + "(\\s|$)"));
}
}
else{
arrRegExpClassNames.push(new RegExp("(^|\\s)" + oClassNames.replace(/\=
-/g, "\\-") + "(\\s|$)"));
}
var oElement;
var bMatchesAll;
for(var j=3D0; j<arrElements.length; j++){
oElement =3D arrElements[j];
bMatchesAll =3D true;
for(var k=3D0; k<arrRegExpClassNames.length; k++){
if(!arrRegExpClassNames[k].test(oElement.className)){
bMatchesAll =3D false;
break;
}
}
if(bMatchesAll){
arrReturnElements.push(oElement);
}
}
return (arrReturnElements)
}
//]]>
</script>
</head>
<body class=3D"mod-resource course-253 dir-ltr lang-en_utf8" id=3D"mod-=
resource-view">
<div id=3D"page">
<div id=3D"header-home">
<div class=3D"headermain"><img alt=3D'Department of Computing Sc=
ience' src=3D'http://moodle.cs.ualberta.ca/theme/uoa/logo.jpg' /></div>
</div>
<!-- Faculty of Science and University of Alberta links -->
<div id=3D"header-green-bar">
<div><a href=3D"http://www.uofaweb.ualberta.ca/science/"><img alt=3D'F=
aculty of Science' id=3D"science" src=3D'http://moodle.cs.ualberta.ca/th=
eme/uoa/science.gif' /></a></div>
<div><a href=3D"http://www.ualberta.ca/"><img alt=3D'University of Alb=
erta' id=3D"uofa_top" src=3D'http://moodle.cs.ualberta.ca/theme/uoa/uofa=
_top.gif' /></a></div>
</div>
<!-- Computing Science logo -->
<div id=3D"comp-science">
<a href=3D"http://www.cs.ualberta.ca"><img alt=3D'Department of Comput=
ing Science logo' src=3D'http://moodle.cs.ualberta.ca/theme/uoa/cs_logo.=
gif' /></a>
</div>
<!-- end -->
<div class=3D"headermenu"><div class=3D"navigation">
<ul><li><form action=3D"http://moodle.cs.ualberta.ca/mod/resource/view.p=
hp" onclick=3D"this.target=3D'_top';"><fieldset class=3D"invisiblefield=
set"><input type=3D"hidden" name=3D"id" value=3D"15675" /><button type=3D=
"submit" title=3D"Previous activity"><span class=3D"arrow ">◀</sp=
an><span class=3D"accesshide " > Previous activity</span></button><=
/fieldset></form></li><li><form action=3D"http://moodle.cs.ualberta.ca/c=
ourse/jumpto.php" method=3D"get" id=3D"navmenupopup" class=3D"popupform=
"><div><select id=3D"navmenupopup_jump" name=3D"jump" onchange=3D"self.l=
ocation=3Ddocument.getElementById('navmenupopup').jump.options[document.=
getElementById('navmenupopup').jump.selectedIndex].value;">
<option value=3D"http://moodle.cs.ualberta.ca/mod/forum/view.php?id=3D=
13882" style=3D"background-image: url(http://moodle.cs.ualberta.ca/theme=
/uoa/pix/mod/forum/icon.gif);">News Forum</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/forum/view.php?id=3D=
14454" style=3D"background-image: url(http://moodle.cs.ualberta.ca/theme=
/uoa/pix/mod/forum/icon.gif);">Course Discussion</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/resource/view.php?i=
d=3D14455" style=3D"background-image: url(http://moodle.cs.ualberta.ca/t=
heme/uoa/pix/mod/resource/icon.gif);">Course Outline</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/resource/view.php?i=
d=3D14456" style=3D"background-image: url(http://moodle.cs.ualberta.ca/t=
heme/uoa/pix/mod/resource/icon.gif);">Check My Grades</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/resource/view.php?i=
d=3D14457" style=3D"background-image: url(http://moodle.cs.ualberta.ca/t=
heme/uoa/pix/mod/resource/icon.gif);">Reference Materials</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/resource/view.php?i=
d=3D14458" style=3D"background-image: url(http://moodle.cs.ualberta.ca/t=
heme/uoa/pix/mod/resource/icon.gif);">Lab Information</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/resource/view.php?i=
d=3D14459" style=3D"background-image: url(http://moodle.cs.ualberta.ca/t=
heme/uoa/pix/mod/resource/icon.gif);">Course Policies</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/resource/view.php?i=
d=3D14460" style=3D"background-image: url(http://moodle.cs.ualberta.ca/t=
heme/uoa/pix/mod/resource/icon.gif);">Contact Information</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/feedback/view.php?i=
d=3D14827" style=3D"background-image: url(http://moodle.cs.ualberta.ca/t=
heme/uoa/pix/mod/feedback/icon.gif);">Midterm Course Survey</option>
<optgroup label=3D"Topic 2"> <option value=3D"http://moodle.cs.ualb=
erta.ca/mod/resource/view.php?id=3D14656" style=3D"background-image: url=
(http://moodle.cs.ualberta.ca/theme/uoa/pix/mod/resource/icon.gif);">Ass=
ignment 1 Spec</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/resource/view.php?i=
d=3D14657" style=3D"background-image: url(http://moodle.cs.ualberta.ca/t=
heme/uoa/pix/mod/resource/icon.gif);">ER Modeling Example</option>
</optgroup> <optgroup label=3D"Topic 4"> <option value=3D"http://=
moodle.cs.ualberta.ca/mod/resource/view.php?id=3D14465" style=3D"backgro=
und-image: url(http://moodle.cs.ualberta.ca/theme/uoa/pix/mod/resource/i=
con.gif);">SQL Plus Tutorial</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/resource/view.php?i=
d=3D15036" style=3D"background-image: url(http://moodle.cs.ualberta.ca/t=
heme/uoa/pix/mod/resource/icon.gif);">Assignment 2 spec</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/resource/view.php?i=
d=3D15049" style=3D"background-image: url(http://moodle.cs.ualberta.ca/t=
heme/uoa/pix/mod/resource/icon.gif);">Assignment 1 solution</option>
</optgroup> <optgroup label=3D"Topic 5"> <option value=3D"http://=
moodle.cs.ualberta.ca/mod/resource/view.php?id=3D14989" style=3D"backgro=
und-image: url(http://moodle.cs.ualberta.ca/theme/uoa/pix/mod/resource/i=
con.gif);">Local Oracle guide</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/resource/view.php?i=
d=3D14990" style=3D"background-image: url(http://moodle.cs.ualberta.ca/t=
heme/uoa/pix/mod/resource/icon.gif);">SQL roots</option>
</optgroup> <optgroup label=3D"Topic 6"> <option value=3D"http://=
moodle.cs.ualberta.ca/mod/resource/view.php?id=3D14992" style=3D"backgro=
und-image: url(http://moodle.cs.ualberta.ca/theme/uoa/pix/mod/resource/i=
con.gif);">Oracle date and time functions</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/assignment/view.php=
?id=3D15038" style=3D"background-image: url(http://moodle.cs.ualberta.ca=
/theme/uoa/pix/mod/assignment/icon.gif);">Assignment 2 submission</optio=
n>
</optgroup> <optgroup label=3D"Topic 7"> <option value=3D"http://=
moodle.cs.ualberta.ca/mod/resource/view.php?id=3D15438" style=3D"backgro=
und-image: url(http://moodle.cs.ualberta.ca/theme/uoa/pix/mod/resource/i=
con.gif);">Mini-Project 1 Spec</option>
</optgroup> <optgroup label=3D"Topic 8"> <option value=3D"http://=
moodle.cs.ualberta.ca/mod/resource/view.php?id=3D15491" style=3D"backgro=
und-image: url(http://moodle.cs.ualberta.ca/theme/uoa/pix/mod/resource/i=
con.gif);">Mini-Project 1 Groups</option>
</optgroup> <optgroup label=3D"Topic 10"> <option value=3D"http:/=
/moodle.cs.ualberta.ca/mod/assignment/view.php?id=3D15439" style=3D"back=
ground-image: url(http://moodle.cs.ualberta.ca/theme/uoa/pix/mod/assignm=
ent/icon.gif);">Mini-Proj 1 Submission Page</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/resource/view.php?i=
d=3D15675" style=3D"background-image: url(http://moodle.cs.ualberta.ca/t=
heme/uoa/pix/mod/resource/icon.gif);">Midterm solution</option>
</optgroup> <optgroup label=3D"Topic 11"> <option value=3D"http:/=
/moodle.cs.ualberta.ca/mod/resource/view.php?id=3D15745" selected=3D"sel=
ected" style=3D"background-image: url(http://moodle.cs.ualberta.ca/theme=
/uoa/pix/mod/resource/icon.gif);">Jump to...</option>
<option value=3D"http://moodle.cs.ualberta.ca/mod/resource/view.php?i=
d=3D15747" style=3D"background-image: url(http://moodle.cs.ualberta.ca/t=
heme/uoa/pix/mod/resource/icon.gif);">Mini-Project 2 groups</option>
</optgroup> <optgroup label=3D"Topic 12"> <option value=3D"http:/=
/moodle.cs.ualberta.ca/mod/resource/view.php?id=3D15721" style=3D"backgr=
ound-image: url(http://moodle.cs.ualberta.ca/theme/uoa/pix/mod/resource/=
icon.gif);">Mini Project 1 Demos</option>
</optgroup> <optgroup label=3D"Topic 13"> <option value=3D"http:/=
/moodle.cs.ualberta.ca/mod/assignment/view.php?id=3D15746" style=3D"back=
ground-image: url(http://moodle.cs.ualberta.ca/theme/uoa/pix/mod/assignm=
ent/icon.gif);">Mini-Project 2 submission</option>
</optgroup></select><input type=3D"hidden" name=3D"sesskey" value=3D=
"SEBvlUyeqJ" /><div id=3D"noscriptnavmenupopup" style=3D"display: inline=
;"><input type=3D"submit" value=3D"Go" /></div><script type=3D"text/java=
script">
//<![CDATA[
document.getElementById("noscriptnavmenupopup").style.display =3D "none"=
;
//]]>
</script></div></form></li><li><form action=3D"http://moodle.cs.ualberta=
.ca/mod/resource/view.php" onclick=3D"this.target=3D'_top';"><fieldset=
class=3D"invisiblefieldset"><input type=3D"hidden" name=3D"id" value=3D=
"15747" /><button type=3D"submit" title=3D"Next activity"><span class=3D=
"accesshide " >Next activity </span><span class=3D"arrow ">▶=
</span></button></fieldset></form></li></ul>
</div></div>
<!-- start if statement -->
<br />
<div class=3D"navbar clearfix">
<div class=3D"breadcrumb"><h2 class=3D"accesshide " >You are her=
e</h2> <ul>
<li class=3D"first"><a onclick=3D"this.target=3D'_top'" href=3D"http://=
moodle.cs.ualberta.ca/">Computing Science Courses</a></li><li> <span cla=
ss=3D"accesshide " >/ </span><span class=3D"arrow sep">▶</sp=
an> <a onclick=3D"this.target=3D'_top'" href=3D"http://moodle.cs.ualber=
ta.ca/course/view.php?id=3D253">CMPUT 291 W10</a></li><li> <span class=3D=
"accesshide " >/ </span><span class=3D"arrow sep">▶</span> <=
a onclick=3D"this.target=3D'_top'" href=3D"http://moodle.cs.ualberta.ca=
/mod/resource/index.php?id=3D253">Resources</a></li><li> <span class=3D"=
accesshide " >/ </span><span class=3D"arrow sep">▶</span> Mi=
ni-Project 2 Spec</li></ul></div>
<div class=3D"navbutton"> </div>
</div>
<!-- END OF HEADER -->
<div id=3D"content"><div class=3D"box generalbox generalboxcontent b=
oxaligncenter clearfix">
<h3 align=3D"center">CMPUT291 - Winter 2010<br /> </h3>
<h2 align=3D"center">Mini-Project 2</h2>
<p><br />
=
</p><div align=3D"center"><em> =
<b> Due </b>: April 2nd at 5pm <br />
</em></div>
<p>
<br />
</p><h3>Clarifications:</h3>
You are responsible for monitoring the course
discussion forum in moodle and this section of the project specification=
=
for more details or clarifications. =
There will be no clarification after <i>one day prior to the due =
date </i>.
After one day prior to the due date, <b><u>if you find anything that is
still ambiguous, you have to make your reasonable assumptions and =
document
it in your report</u></b>.
<ul><li> None.
</li></ul>
<p>
</p><h3> Introduction </h3>
The goal of this project is to teach the concept of working with
data in the physical layer. This is done by building an information
retrieval system, using the Berkeley DB library =
for operating on files and indices. =
Your job in this project is to write programs that keep
data in files and maintain indices that provide basic searches =
over data.
Your project will be evaluated on the basis of 80% of the mark for =
the implementation of the functionalities listed here, 15% for the =
report =
and 5% for group coordination. =
The implementation is assessed in a demo session, and is further
broken down to two phases with 15% of the mark allocated for Phase 1 =
and 65% for Phase 2. Another 15% of the mark will be assigned for the =
documentation and quality of your source code and for your design =
document. =
5% of the mark is assigned for group coordination and project =
break-down.
<p>
</p><h3>Group work policy</h3>
You will be doing this project with one other partner from the 291 =
class. =
Your group information
from mini-project 1 is copied to <a href=3D"http://moodle.cs.ualberta.ca=
/mod/resource/view.php?id=3D15747">mini-project
2 groups</a> page on the assumption
that you would be working in the same group. If you decide
to change groups, please notify the instructor.
It is assumed that both group members contribute somewhat equally to the=
project, hence they would receive the same mark. In case of =
difficulties within a group and when a partner is not lifting his/her =
weight, make sure to document all your contributions. If there is a =
break-up, each group member will get credit only for his/her portion of =
the work completed (losing the mark for any work either not completed or=
completed by the partner). For the same reason, a break-up should be =
your last resort. =
<h3> Task </h3>
<p>
You are given a data file, which you will use to
construct your indices. Data in this file looks like this:<br /></p><pre=
>1|Guess Who's Coming to Dinner|2010-02-02T01:18:58|Cop 663|Guess Who's =
Coming to Dinner is a 1967 American drama film...<span style=3D"font-fam=
ily: trebuchet ms,verdana,arial,helvetica,sans-serif;"><br /></span>2|Mo=
ntreal Protocol|2010-01-25T15:47:26|Arthur Rubin|The Montreal Protocol o=
n Substances That Deplete the Ozone Layer...<span style=3D"font-family: =
trebuchet ms,verdana,arial,helvetica,sans-serif;"><br /></span>3|Vulcan,=
Alberta|2010-01-03T21:11:41||Vulcan is a town located midway between th=
e cities of Calgary and Lethbridge,...<br /></pre><p>Here is a <a href=3D=
"http://moodle.cs.ualberta.ca/file.php/253/assignments/W10/10.txt">
</a><a href=3D"http://moodle.cs.ualberta.ca/file.php/253/assignments/W10=
/10.txt">small
sample</a> of a data file with 10 records (here is <a href=3D"http://mo=
odle.cs.ualberta.ca/file.php/253/assignments/W10/1k.txt">a
medium-size file</a> and here is <a href=3D"http://moodle.cs.ualberta.c=
a/file.php/253/assignments/W10/100k.txt">a bit larger file</a>).
Each line in the file describes a Wikipedia page in the following =
format:
the first field is a =
unique id, the second field is a page title, the third field is a =
time-stamp,
the fourth field is the userid or the name of a person who contributed =
toward
the article and the last field is the textual content of the page.
Fields are separated by '|', whereas =
terms are separated by space or punctuations. The end of a line is =
marked =
by a newline character. It is assumed that the characters "<i>|</i>=
" =
and <i>the newline</i> cannot appear in the content of a field.
Your job is to create indices, following Phases 0 and 1, and use
those indices to process the queries in Phases 2.
</p><h3> Phase 0: Inverting the Data File</h3>
<p>
This step is pretty much done for you. To construct an index on terms =
that =
appear in a field such as title, you generally need to invert the file.
As an example, for the 3-record sample given above, here is an inverted =
file on contributor terms (with each term followed by another line that =
contains the ids of all documents that have that=C2=A0 term in the contr=
ibutor field):</p><pre>663<br />1<br />arthur<br />2<br />cop<br />1<br =
/>rubin<br />2<br /></pre><p>For the data files provided, here are the i=
nverted files (provided for =
your convenience). Note that each inverted entry is broken down into two=
=
lines to =
possibly make it easier to process. Also all terms in the inverted files=
are changed to lowercase to make searching for a match easier.<br />
</p><ul><li>Inverted files on <a href=3D"http://moodle.cs.ualberta.ca/fi=
le.php/253/assignments/W10/10-titleW.txt">title</a>, <a href=3D"http://m=
oodle.cs.ualberta.ca/file.php/253/assignments/W10/10-userW.txt">contribu=
tor </a>and <a href=3D"http://moodle.cs.ualberta.ca/file.php/253/assignm=
ents/W10/10-textW.txt">text</a> for <a href=3D"http://moodle.cs.ualberta=
.ca/file.php/253/assignments/W10/10.txt">the small data file</a><br /></=
li><li>Inverted files on <a href=3D"http://moodle.cs.ualberta.ca/file.ph=
p/253/assignments/W10/1k-titleW.txt">title</a>, <a href=3D"http://moodle=
.cs.ualberta.ca/file.php/253/assignments/W10/1k-userW.txt">contributor <=
/a>and <a href=3D"http://moodle.cs.ualberta.ca/file.php/253/assignments/=
W10/1k-textW.txt">text </a>for <a href=3D"http://moodle.cs.ualberta.ca/f=
ile.php/253/assignments/W10/1k.txt">the medium-sized data file</a></li><=
li>=C2=A0Inverted files on <a href=3D"http://moodle.cs.ualberta.ca/file.=
php/253/assignments/W10/100k-titleW.txt">title</a>, <a href=3D"http://mo=
odle.cs.ualberta.ca/file.php/253/assignments/W10/100k-userW.txt">contrib=
utor </a>and <a href=3D"http://moodle.cs.ualberta.ca/file.php/253/assign=
ments/W10/100k-textW.txt">text </a>for <a href=3D"http://moodle.cs.ualbe=
rta.ca/file.php/253/assignments/W10/100k.txt">the larger data =
file</a></li></ul>To save both some bandwidth and your time in downloadi=
ng these files, all these files are also available at ~c291/pub/prj2file=
s.<br />
<h3> Phase 1: Building Indexes</h3>
<p>
Given a data file (e.g. data.txt) and inverted files on title =
(e.g. titleW.txt), contributor (e.g. userW.txt) and text (e.g. textW.txt=
),
create the following four indexes:
(1) a B+-tree on terms from title (as keys) and document ids =
(as data), (2) a B+-tree on terms from contributor (as keys) and =
document =
ids (as data), (3) a B+-tree on terms from text (as keys) and document =
ids
(as data), and (4) a hash index on document ids (as keys) and all other =
fields (as =
data).
Your program would get the names of data and inverted files as =
arguments, and would produce three index files called
<i>ti.idx</i>, <i>co.idx</i>, <i>tx.idx</i> and <i>doc.idx</i>. =
</p><p>
Check out the utilities <i>db_load</i> and <i>db_dump</i>. They can be =
useful in
loading your indexes (in particular if you don't want to write more than=
a few =
lines of code) and testing their correctness.
</p><h3> Phase 2: Data Retrieval </h3>
<p>
Given the index files <i>ti.idx</i>, <i>co.idx</i>, <i>tx.idx</i> and <i=
>doc.idx</i>
=
created in Phase 1 respectively on title, contributor, textual content =
and =
document id, write a program that =
processes queries as follows.
Each query returns the id and the title of matching pages.
Here are some examples of queries:
</p><ol><li><i>ti:university</i>
</li><li><i>ti:university ti:alberta</i>
</li><li><i>co:chris ti:university tx:alberta</i>
</li><li><i>tx:university of alberta</i>
</li><li><i>tx:university of % co:joe</i> =
</li></ol>
<p>
The first query returns pages that have the term <i>university</i> in =
their
titles, whereas the second query returns pages with both the terms =
<i>university</i> and <i>alberta</i> in their titles.
The third query returns pages that have the term <i>chris</i> in the =
contributor
field, <i>university</i> in title and <i>alberta</i> in text.
The fourth query returns pages with the phrase <i>university of alberta<=
/i>
in their texts. Finally the last query returns pages that have a phrase =
starting
with <i>university of</i> in their title and <i>joe</i> in their =
contributor =
fields.
</p><p>
More formally, each query defines some conditions that must be satisfied=
by the terms (and phrases) extracted from title, contributor and text fi=
elds of
the matching pages. =
A condition can be either an exact or a partial match; a condition can =
also =
be in the form of a conjunction of other conditions. For simplicity,
partial matches are restricted to prefix matches only (i.e. the wild =
card
% can only appear at the end of a term or phrase).
The terms <i>ti:</i>, <i>co:</i> and <i>tx:</i> are reserved words and =
indicate
the fields to be matched; these terms cannot be used in the query text =
for
any other reason. Similarly, the character % is a special
character indicating a wild card and it cannot appear in the query text =
for =
any other reason. =
</p><h3> Testing </h3>
At demo time, your code will be tested under a TA account.
You will be given the name of a data file and three inverted files, =
and will be asked to
build the indices discussed above. You will then be asked to run your =
query interface
which will allow us to test your system.
We would follow a 5 minute rule, meaning that if you cannot create your =
indices in Phase 1 in less than 5 minutes, the TAs will have to move to =
the next group.
<p>
The demo will be run using the source code submitted and nothing else.
Make sure your submission includes every file that is needed. =
There will be a limited time for each demo.
</p><p>
Every group will book a time slot convenient to all group members
to demo their projects. =
At demo time, all group members must be present. =
The TA will be asking you to perform various tasks and show how your
application is handling each task. A mark will be assigned to your demo
on the spot after the testing.
</p><p>
<b>Important Constraint:</b> You can make no assumption on the size
of any of the files you are working with, meaning your programs
must be independent of the data file sizes. =
We will be using a relatively large file for =
testing and you don't want your program to break down in our tests, =
resulting
in a poor mark! That said, you can make very few reasonable assumptions =
(such as =
the =
inverted list of a term can fit in main memory) and state them in your =
report.
</p><h3> Instructions for Submissions </h3>
<p> =
Your submission includes (1) the source code for phases 1 and 2 and any =
makefile or script that you may need to compile your code, and (2) a =
short =
report. Your source code must include at least two programs, i.e. one =
for =
each phase. Your program for Phase 2 would implement a simple query =
interface
either in Java, C or C++. For phase 1, you can have more than =
one program (in Java, C, C++ or Perl) and can make use of any Unix =
command and
scripting language (e.g. Perl, bash) that runs under Linux on lab =
machines, =
as long as you clearly document in your report how and =
in what sequence the programs or commands should run.
The source code is submitted as follows:
</p><ul><li> Create a single gzipped tar file with all your source code =
and additional files you may need for your demo. Name the file
<i>prj2code.tgz</i>. =
</li><li> Submit your project tarfile in the <a href=3D"http://moodle.cs=
.ualberta.ca/mod/assignment/view.php?id=3D15746">project
submission site</a>. =
</li></ul>
<p> Your report must be type-written and submitted in hardcopy =
at the designated drop boxes
located on the first floor of CSC building, across from the room 1-45
before the due date. Your report cannot exceed 3 pages in length.
</p><p>
The report includes =
(1) a general overview of your system and its design and instructions fo=
r running your code for phases 1 and 2,
(2) a description of your algorithm for evaluating queries, in =
particular
evaluating conjunctive queries and wild cards and an analysis of the =
efficiency of your algorithm, (3) a description of your test cases, and =
(4) your group work strategy discussing how the work was divided and coo=
rdinated and any success or failure stories. Also include any assumption=
you =
have made or any possible limitations your
code may have.
</p>
</div><div class=3D"modified">Last modified: Thursday, 18 March 2010, 1=
2:53 AM</div></div><div id=3D"footer"><p class=3D"helplink"></p><div cla=
ss=3D"logininfo">You are logged in as <a href=3D"http://moodle.cs.ualbe=
rta.ca/user/view.php?id=3D562&course=3D253">John Nguyen</a> (<a hr=
ef=3D"http://moodle.cs.ualberta.ca/login/logout.php?sesskey=3DSEBvlUyeqJ=
">Logout</a>)</div><div class=3D"homelink"><a href=3D"http://moodle.cs.=
ualberta.ca/course/view.php?id=3D253">CMPUT 291 W10</a></div> <di=
v class=3D"validators"><ul>
<li><a href=3D"http://validator.w3.org/check?verbose=3D1&s=
s=3D1&uri=3Dhttp%3A%2F%2Fmoodle.cs.ualberta.ca%2Fmod%2Fresource%2Fvi=
ew.php%3Fid%3D15745">Validate HTML</a></li>
<li><a href=3D"http://www.contentquality.com/mynewtester/cynth=
ia.exe?rptmode=3D-1&url1=3Dhttp%3A%2F%2Fmoodle.cs.ualberta.ca%2Fmod%=
2Fresource%2Fview.php%3Fid%3D15745">Section 508 Check</a></li>
<li><a href=3D"http://www.contentquality.com/mynewtester/cynth=
ia.exe?rptmode=3D0&warnp2n3e=3D1&url1=3Dhttp%3A%2F%2Fmoodle.cs.u=
alberta.ca%2Fmod%2Fresource%2Fview.php%3Fid%3D15745">WCAG 1 (2,3) Check<=
/a></li>
</ul></div>
</div>
<!-- start compsci footer -->
<div id=3D"navbar_bottom">
<ul>
<li><a href=3D"http://ugweb.cs.ualberta.ca/contact/">Help Desk</a></li=
>
<li><a href=3D"http://www.cs.ualberta.ca/">Computing Science Home</a><=
/li>
<li class=3D"no-border"><a href=3D"http://www.science.ualberta.ca/">Fa=
culty of Science</a></li>
</ul>
</div>
<div id=3D"footer_uofa">
<div class=3D"ualogo">
<a href=3D"http://www.ualberta.ca"><img alt=3D'Moodle' src=3D'http://m=
oodle.cs.ualberta.ca/theme/uoa/uofa_logo.gif' /></a></div>
<div id=3D"copyright">
<ul>
<li>Copyright © 2002-2008</li>
<li><a href=3D"http://www.ualberta.ca">University of Alberta</a></li>
<li><a href=3D"http://www.uofaweb.ualberta.ca">UofA Web Project</a></l=
i>
<li><a href=3D"http://www.uofaweb.ualberta.ca/privacy/">Privacy Policy=
</a></li>
</ul>
</div>
</div>
<!-- end -->
</div>
</body>
</html>
------------5WOaLEeyljv2qAP5B4Ec8h
Content-Disposition: inline; filename=styles.css
Content-Type: text/css; charset=utf-8; name=styles.css
Content-Location: http://moodle.cs.ualberta.ca/theme/standard/styles.php
Content-Transfer-Encoding: Quoted-Printable
/**************************************
* THEME NAME: standard
*
* Files included in this sheet:
*
* standard/styles_layout.css
* /mod/assignment/styles.php
* /mod/choice/styles.php
* /mod/data/styles.php
* /mod/feedback/styles.php
* /mod/lesson/styles.php
* /mod/scorm/styles.php
* /mod/workshop/styles.php
* /blocks/blog_tags/styles.php
* /blocks/calendar_month/styles.php
* /blocks/calendar_upcoming/styles.php
* /blocks/course_summary/styles.php
* /blocks/login/styles.php
* /blocks/news_items/styles.php
* /blocks/quiz_results/styles.php
* /blocks/rss_client/styles.php
* /blocks/search_forums/styles.php
* /grade/report/grader/styles.php
* /grade/report/user/styles.php
**************************************/
/***** standard/styles_layout.css start *****/
/*******************************************************************
styles_layout.css
This CSS file contains all layout definitions like positioning,
floats, margins, padding, borders etc.
Styles are organised into the following sections:
core
forms
header
footer
admin
blocks
blog
calendar
course
doc
grades
login
message
notes
mymoodle
question
tabs
tags
user
various modules
*******************************************************************/
/***
*** Core
***/
h1.main,
h2.main,
h3.main,
h4.main,
h5.main,
h6.main {
text-align: center;
}
#layout-table {
width:100%;
border-collapse:separate;
margin-top: 8px;
}
#layout-table #left-column,
#layout-table #middle-column,
#layout-table #right-column
{
vertical-align:top;
}
#layout-table #middle-column {
padding-left:12px;
padding-right:12px;
}
.clearer {
clear:both;
margin:0;
padding:0;
height:1px;
border:none;
background:transparent;
display:block;
}
.clearfix {
min-width: 0;
/* overflow: hidden; */
}
.clearfix:after {
/* content: "<!-- -->"; */
content: ".";
display: block;
height: 0;
clear: both;
visibility: hidden;
}
#redirect {
text-align: center;
margin-top:10%;
}
#redirect #message {
}
#redirect #continue {
}
/* .clearfix {display: inline-table;} */
/* Hides from IE-mac \*/
* html .clearfix {height: 1%;}
.clearfix {display: block;}
/* End hide from IE-mac */
.mdl-align {
text-align: center;
}
.mdl-left {
text-align: left;
}
.mdl-right {
text-align: right;
}
.continuebutton {
text-align: center;
}
form {
margin-bottom:0;
}
table {
border-spacing: 0;
border-collapse: collapse;
}
a img {
border:none;
}
img.userpicture,
img.grouppicture {
border: 0;
}
#grouppicture {
text-align: center;
}
div.groupselector {
float: left;
margin-top: 3px;
margin-bottom: 3px;
}
#addmembersform table {
margin-left: auto;
margin-right: auto;
}
.notifyproblem {
text-align: center;
padding: 10px;
}
.notifysuccess {
text-align:center;
padding: 10px;
}
.notifytiny {
text-align:left;
padding: 0;
}
.singlebutton form,
.singlebutton div {
display:inline;
}
.box {
clear: both;