Class Notes (1,100,000)
CA (620,000)
Queen's (10,000)
CISC (500)
Lecture 1

CISC 235 Lecture Notes - Lecture 1: Autocomplete


Department
Computing
Course Code
CISC 235
Professor
Robin W Dawes
Lecture
1

Page:
of 3
CISC$235:)Lecture)1:)
!
"#$%&#!'#(()*'!)*(%!(+#!,-./#0(!1(!+1*23!4!'15#!(+#!061,,!1!7&%.6#8!(%!(+)*9!
1.%-(:!
!
;+#!<=>%)*!?18#!
!
;+),!),!1!@=761A#&!'18#!-,)*'!<!0%)*,B!!;+#!0%)*,!C)66!.#!-,#2!(%!'#*#&1(#!1!
,#D-#*0#!%$!E!F+#12,G!1*2!;!F(1)6,GB!!H10+!761A#&!C)66!0+%%,#!1!,#D-#*0#!%$!
6#*'(+!<I!$%&!#J1876#!K61A#&!L!8)'+(!0+%%,#!EE;!1*2!K61A#&!@!8)'+(!0+%%,#!
;E;B!!M$(#&!(+#!761A#&,!+15#!0+%,#*!(+#)&!,#D-#*0#,3!(+#!0%)*,!1&#!(%,,#2!(%!
0&#1(#!1*!)*)()16!,#D-#*0#!%$!6#*'(+!<B!!4$!(+#!)*)()16!,#D-#*0#!81(0+#,!(+#!
,#D-#*0#!0+%,#*!.A!#)(+#&!761A#&3!(+1(!761A#&!C)*,!(+#!'18#B!!N(+#&C),#3!
(+#!$)&,(!0%)*!),!(%,,#2!1'1)*!1*2!122#2!(%!(+#!#*2!%$!(+#!,#D-#*0#B!!;+),!
7&%0#,,!%$!&#=(%,,)*'!(+#!O%62#,(O!0%)*!1*2!122)*'!)(!(%!(+#!#*2!%$!(+#!
,#D-#*0#!),!0%*()*-#2!-*()6!%*#!%$!(+#!(C%!0+%,#*!,#D-#*0#,!%00-&,B!!;+#!
761A#&!C+%,#!,#D-#*0#!0%8#,!-7!$)&,(!),!(+#!C)**#&B!
!
P%&!#J1876#3!,-77%,#!(+#!761A#&,!0+%%,#!EE;!1*2!;E;3!1,!1.%5#B!!;+#!
0%)*,!1&#!(%,,#2!1*2!(+#!)*)()16!,#D-#*0#!),!;;EB!!;+),!2%#,!*%(!81(0+!#)(+#&!
0+%,#*!,#D-#*0#!,%!(+#!$)&,(!0%)*!F;G!),!(%,,#2!1'1)*B!!Q-77%,#!)(!0%8#,!-7!
EB!!;+),!),!122#2!(%!(+#!#*2!%$!(+#!,#D-#*0#3!,%!(+#!0%)*!,#D-#*0#!),!*%C!
;EEB!!;+),!),!,()66!*%(!1!81(0+!$%&!#)(+#&!761A#&3!,%!(+#!O%62#,(O!0%)*!F;G!),!
&#8%5#2!1*2!(%,,#2!1'1)*B!!Q-77%,#!)(!0%8#,!-7!EB!!;+),!),!122#2!(%!(+#!
#*2!%$!(+#!,#D-#*0#3!')5)*'!EEEB!!Q()66!*%!81(0+3!,%!(+#!%62#,(!0%)*!FEG!),!
&#8%5#2!1*2!(%,,#2B!Q-77%,#!)(!0%8#,!-7!;B!!;+),!122#2!(%!(+#!#*2!%$!(+#!
,#D-#*0#3!,%!(+#!0%)*!,#D-#*0#!),!*%C!EE;B!!;+),!81(0+#,!(+#!,#D-#*0#!
0+%,#*!.A!K61A#&!L3!,%!,+#!C)*,!(+#!'18#B!
!
F4(!),!7%,,).6#!(%!761A!(+#!'18#!C)(+!/-,(!%*#!0%)*:!(%,,!(+#!0%)*!&#7#1(#26A!
1*2!9##7!(&109!%$!(+#!61,(!<!(%,,#,!=!)$!(+#!61,(!<!(%,,#,!81(0+!(+#!,#D-#*0#!
0+%,#*!.A!%*#!%$!(+#!761A#&,3!(+1(!761A#&!C)*,BG!
!
E#&#!1&#!(+#!D-#,()%*,:!!1,,-8)*'!(+1(!(+#!0%)*,!1&#!.161*0#2!F#10+!+1,!RBS!
7&%.1.)6)(A!%$!0%8)*'!-7!E!1*2!RBS!7&%.1.)6)(A!%$!0%8)*'!-7!;G!1*2!(+#&#!),!
*%!$-**A!.-,)*#,,!)*5%65#2!)*!(+#!(%,,)*'3!),!(+),!1!$1)&!'18#!F)B#B!1&#!.%(+!
761A#&,!#D-166A!6)9#6A!(%!C)*G!%&!2%#,!%*#!761A#&!+15#!1*!1251*(1'#T!!U#663!4!
C)66!1*,C#&!(+1(!%*#!BBB!2#,7)(#!(+#!$1)&*#,,!%$!(+#!0%)*!(%,,)*'3!)(!),!*%(!1!
$1)&!'18#B!!Q%!(+#!$%66%C=-7!D-#,()%*,!1&#:!!
!!!!C+)0+!761A#&!+1,!1*!1251*(1'#T!
!!!!C+1(!,(&1(#'A!,+%-62!,+#!-,#!(%!)*0&#1,#!+#&!0+1*0#!%$!C)**)*'T!
!
U#!C)66!&#(-&*!(%!(+),!BBB!
!
!
!
;-&*)*'!(%!(+#!,-./#0(!%$!21(1!,(&-0(-&#,3!C#!0%*,)2#&#2!1!$#C!7&%.6#8,:!
!
LB!!E%C!C%-62!A%-!%&'1*)V#!1!2)0()%*1&A!(%!$10)6)(1(#!1-(%=0%876#(#!1*2W%&!
,7#66=0+#09)*'T!
!
@B!!E%C!C%-62!A%-!&#7&#,#*(!(+#!,(&-0(-&#!%$!(+#!4*(#&*#(!,%!1,!(%!
#$$)0)#*(6A!2#(#&8)*#!'%%2!&%-(#,!$%&!#81)6T!
!
<B!!E%C!C%-62!A%-!,#'8#*(!1*!)81'#!$)6#!,%!1,!(%!8)*)8)V#!(+#!$)6#!,)V#T!
!
XB!!E%C!C%-62!A%-!#$$)0)#*(6A!,(%&#!1!6),(!%$!O$%&.)22#*O!C%&2,3!,%!(+1(!1*A!
C%&2!0%-62!.#!D-)096A!(#,(#2!$%&!8#8.#&,+)7!)*!(+#!6),(3!)$!A%-!C#&#!C)66)*'!
(%!+15#!1!,8166!7#&0#*(1'#!%$!O100#7(1.6#O!C%&2,!$16,#6A!&#7%&(#2!1,!.#)*'!
)*!(+#!6),(T!!HD-)516#*(6A3!+%C!C%-62!A%-!,(%&#!1!6),(!%$!#J),()*'!-,#&=*18#,3!
,%!(+1(!C+#*!1!*#C!-,#&!,#6#0(,!1!-,#&=*18#!A%-!01*!D-)096A!2#(#&8)*#!)$!)(!
+1,!16&#12A!.##*!(19#*!=!1'1)*3!1!,8166!*-8.#&!%$!O$16,#!7%,)()5#O!&#,-6(,!),!
100#7(1.6#B!
!
SB!!Q-77%,#!A%-!+12!1!21(1!,#(!C+)0+!C1,!,%!61&'#!(+1(!)(!+12!(%!.#!,(%&#2!
%*!1*!#J(#&*16!+1&2!2&)5#3!,%!(+1(!100#,,)*'!(+#!21(1!),!,)'*)$)01*(6A!,6%C#2!
.A!(+#!,7##2!%$!0%88-*)01()%*!.#(C##*!A%-&!0%87-(#&!1*2!(+#!#J(#&*16!
,(%&1'#!2#5)0#B!!E%C!C%-62!A%-!%&'1*)V#!(+#!21(1!%*!(+#!#J(#&*16!2&)5#!(%!
%7()8)V#!(+#!7&%0#,,!%$!100#,,)*'!166!#6#8#*(,!%$!(+#!,#(!(+1(!8##(!0#&(1)*!
0&)(#&)1!F$%&!#J1876#3!)$!(+#!21(1!&#7&#,#*(,!,(-2#*(,!C#!8)'+(!C1*(!(%!
100#,,!166!,(-2#*(,!C+%,#!,(-2#*(!*-8.#&,!.#')*!C)(+!ORYOGT!
!
ZB!!E%C!C%-62!A%-!0&#1(#!1!,#0-&#!6%')*!,A,(#8!C)(+!-,#&*18#,!1*2!
71,,C%&2,!)*!C+)0+!(+#!71,,C%&2,!1&#!*%(!,(%&#23!#5#*!)*!1*!#*0&A7(#2!
$%&83!1*AC+#&#T!
!
;+#,#!7&%.6#8,!166!+15#!(C%!(+)*',!)*!0%88%*:!#10+!%*#!
!!!!!!!=!)*5%65#,!%&'1*)V)*'!)*$%&81()%*!
!!!!!!!=!+1,!1!71&()0-61&!'%16!
!
;+),!)66-,(&1(#,!(+#!$)&,(!1*2!0&-0)16!7%)*(!1.%-(!0+%%,)*'!1!21(1!,(&-0(-&#!(%!
%&'1*)V#!1!,#(!%$!)*$%&81()%*!=!C#!*##2!(%!9*%C!C+1(!C#!C1*(!(%!2%!C)(+!
)(B!!Q%8#!21(1!,(&-0(-&#,!1&#!71&()0-61&6A!,-)(#2!$%&!,#1&0+)*'!(+#!,#(3!C+)6#!
%(+#&,!1&#!%7()816!$%&!122)*'!1*2!2#6#()*'!8#8.#&,!%$!(+#!,#(3!%&!$)*2)*'!
,-.,#(,3!#(0B!!;+-,!C#!*##2!(%!(+)*9!1.%-(!(+#!(A7#,!%$!%7#&1()%*,!C#!81A!
*##2!(%!)876#8#*(!$%&!1!21(1!,#(3!,)*0#!(+#,#!C)66!2#$)*)(#6A!)*$6-#*0#!%-&!
2#0),)%*B!!!
!
Q%8#!%$!(+#!8%&#!0%88%*!%7#&1()%*,!)*06-2#!
!!!!=!122!1*!#6#8#*(!(%!(+#!,#(!!
!!!!=!&#8%5#!1*!#6#8#*(!$&%8!(+#!,#(!!F(+#,#!$)&,(!(C%!%7#&1()%*,!2%!*%(!
*#0#,,1&)6A!'%!(%'#(+#&:!,%8#!21(1!,#(,!*#5#&!'&%C3!1*2!,%8#!*#5#&!
,+&)*9G!
!!!!=!1((10+!#J(&1!21(1!(%!1*!#6#8#*(!F,-0+!1,!122)*'!1!*#C!#81)6!122&#,,!(%!
1!7#&,%*!)*!A%-&!0%*(10(!,#(G!
!!!!=!,#1&0+!$%&!1!71&()0-61&!#6#8#*(!F(+),!+1,!(C%!$%&8,:!O4,!J!)*!(+#!,#(TO!1*2!
OU+1(!),!J[,!6%01()%*!)*!(+#!,#(TOG!
!!!!=!,%&(!(+#!,#(!
!!!!=!$)*2!(+#!81J!1*2W%&!8)*!#6#8#*(!)*!(+#!,#(!
!!!!=!7#&$%&8!1!&1*'#!D-#&A!%*!(+#!,#(!F$)*2!166!#6#8#*(,!J!,-0+!(+1(!1!\]!J!\]!
.3!$%&!,%8#!,7#0)$)#2!1!1*2!.!516-#,G!
!!!!=!$)*2!1!,-.,#(!%$!(+#!,#(!.1,#2!%*!%*#!%&!8%&#!1((&).-(#,!F,-0+!1,!O$)*2!
166!&#2!,7%&(,!01&,!)*!(+#!O^#+)06#,!$%&!,16#O!!,#(G!
!
N*#!'%16!%$!(+),!0%-&,#!),!(%!')5#!A%-!1*!-*2#&,(1*2)*'!%$!81*A!%$!(+#!8%,(!
)87%&(1*(!21(1!,(&-0(-&#,!1*2!(+#)&!,(&#*'(+,!1*2!C#19*#,,#,3!,%!(+1(!
C+#*!)876#8#*()*'!1*!16'%&)(+8!A%-!01*!0+%%,#!1!21(1!,(&-0(-&#!(+1(!),!
C#66=,-)(#2!(%!(+#!7&%.6#8B!
!
!
!