CS_Notes/index.html at master · TPB-Notes/CS_Notes · GitHub

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
<!DOCTYPE html>

<html lang="en">

<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <meta name="mobile-web-app-capable" content="yes">
    <title>
        CS Notes - HackMD
    </title>
    <link rel="icon" type="image/png" href="https://tpb1908-hackmd.herokuapp.com/favicon.png">
    <link rel="apple-touch-icon" href="https://tpb1908-hackmd.herokuapp.com/apple-touch-icon.png">

    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/twitter-bootstrap/3.3.7/css/bootstrap.min.css" integrity="sha256-916EbMg70RQy9LHiGkXzG8hSg9EdNy97GazNG/aiY1w=" crossorigin="anonymous" />
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.min.css" integrity="sha256-eZrrJcwDc/3uDhsdt61sL2oOBY362qM3lon1gyExkL0=" crossorigin="anonymous" />
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/ionicons/2.0.1/css/ionicons.min.css" integrity="sha256-3iu9jgsy9TpTwXKb7bNQzqWekRX7pPK+2OLj3R922fo=" crossorigin="anonymous" />
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/octicons/3.5.0/octicons.min.css" integrity="sha256-QiWfLIsCT02Sdwkogf6YMiQlj4NE84MKkzEMkZnMGdg=" crossorigin="anonymous" />
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/prism/1.5.1/themes/prism.min.css" integrity="sha256-vtR0hSWRc3Tb26iuN2oZHt3KRUomwTufNIf5/4oeCyg=" crossorigin="anonymous" />
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.7.0/styles/github-gist.min.css" integrity="sha256-tAflq+ymku3Khs+I/WcAneIlafYgDiOQ9stIHH985Wo=" crossorigin="anonymous" />
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/emojify.js/1.1.0/css/basic/emojify.min.css" integrity="sha256-UOrvMOsSDSrW6szVLe8ZDZezBxh5IoIfgTwdNDgTjiU=" crossorigin="anonymous" />
    <style>
        @import url(https://fonts.googleapis.com/css?family=Source+Sans+Pro:400,400italic,600,600italic,300italic,300|Source+Serif+Pro|Source+Code+Pro:400,300,500&subset=latin,latin-ext);.markdown-body{font-family:-apple-system,BlinkMacSystemFont,Segoe UI,Roboto,Helvetica,Arial,sans-serif;font-size:16px;line-height:1.5;word-wrap:break-word}.markdown-body:after,.markdown-body:before{display:table;content:""}.markdown-body:after{clear:both}.markdown-body>:first-child{margin-top:0!important}.markdown-body>:last-child{margin-bottom:0!important}.markdown-body a:not([href]){color:inherit;text-decoration:none}.markdown-body .absent{color:#c00}.markdown-body .anchor{float:left;padding-right:4px;margin-left:-20px;line-height:1}.markdown-body .anchor:focus{outline:none}.markdown-body blockquote,.markdown-body dl,.markdown-body ol,.markdown-body p,.markdown-body pre,.markdown-body table,.markdown-body ul{margin-top:0;margin-bottom:16px}.markdown-body hr{height:.25em;padding:0;margin:24px 0;background-color:#e7e7e7;border:0}.markdown-body blockquote{padding:0 1em;color:#777;border-left:.25em solid #ddd}.markdown-body blockquote>:first-child{margin-top:0}.markdown-body blockquote>:last-child{margin-bottom:0}.markdown-body .loweralpha{list-style-type:lower-alpha}.markdown-body h1,.markdown-body h2,.markdown-body h3,.markdown-body h4,.markdown-body h5,.markdown-body h6{margin-top:24px;margin-bottom:16px;font-weight:600;line-height:1.25}.markdown-body h1 .octicon-link,.markdown-body h2 .octicon-link,.markdown-body h3 .octicon-link,.markdown-body h4 .octicon-link,.markdown-body h5 .octicon-link,.markdown-body h6 .octicon-link{color:#000;vertical-align:middle;visibility:hidden}.markdown-body h1:hover .anchor,.markdown-body h2:hover .anchor,.markdown-body h3:hover .anchor,.markdown-body h4:hover .anchor,.markdown-body h5:hover .anchor,.markdown-body h6:hover .anchor{text-decoration:none}.markdown-body h1:hover .anchor .octicon-link,.markdown-body h2:hover .anchor .octicon-link,.markdown-body h3:hover .anchor .octicon-link,.markdown-body h4:hover .anchor .octicon-link,.markdown-body h5:hover .anchor .octicon-link,.markdown-body h6:hover .anchor .octicon-link{visibility:visible}.markdown-body h1 code,.markdown-body h1 tt,.markdown-body h2 code,.markdown-body h2 tt,.markdown-body h3 code,.markdown-body h3 tt,.markdown-body h4 code,.markdown-body h4 tt,.markdown-body h5 code,.markdown-body h5 tt,.markdown-body h6 code,.markdown-body h6 tt{font-size:inherit}.markdown-body h1{font-size:2em}.markdown-body h1,.markdown-body h2{padding-bottom:.3em;border-bottom:1px solid #eee}.markdown-body h2{font-size:1.5em}.markdown-body h3{font-size:1.25em}.markdown-body h4{font-size:1em}.markdown-body h5{font-size:.875em}.markdown-body h6{font-size:.85em;color:#777}.markdown-body ol,.markdown-body ul{padding-left:2em}.markdown-body ol.no-list,.markdown-body ul.no-list{padding:0;list-style-type:none}.markdown-body ol ol,.markdown-body ol ul,.markdown-body ul ol,.markdown-body ul ul{margin-top:0;margin-bottom:0}.markdown-body li>p{margin-top:16px}.markdown-body li+li{margin-top:.25em}.markdown-body dl{padding:0}.markdown-body dl dt{padding:0;margin-top:16px;font-size:1em;font-style:italic;font-weight:700}.markdown-body dl dd{padding:0 16px;margin-bottom:16px}.markdown-body table{display:block;width:100%;overflow:auto;word-break:normal;word-break:keep-all}.markdown-body table th{font-weight:700}.markdown-body table td,.markdown-body table th{padding:6px 13px;border:1px solid #ddd}.markdown-body table tr{background-color:#fff;border-top:1px solid #ccc}.markdown-body table tr:nth-child(2n){background-color:#f8f8f8}.markdown-body img{max-width:100%;box-sizing:content-box;background-color:#fff}.markdown-body img[align=right]{padding-left:20px}.markdown-body img[align=left]{padding-right:20px}.markdown-body .emoji{max-width:none;vertical-align:text-top;background-color:transparent}.markdown-body span.frame{display:block;overflow:hidden}.markdown-body span.frame>span{display:block;float:left;width:auto;padding:7px;margin:13px 0 0;overflow:hidden;border:1px solid #ddd}.markdown-body span.frame span img{display:block;float:left}.markdown-body span.frame span span{display:block;padding:5px 0 0;clear:both;color:#333}.markdown-body span.align-center{display:block;overflow:hidden;clear:both}.markdown-body span.align-center>span{display:block;margin:13px auto 0;overflow:hidden;text-align:center}.markdown-body span.align-center span img{margin:0 auto;text-align:center}.markdown-body span.align-right{display:block;overflow:hidden;clear:both}.markdown-body span.align-right>span{display:block;margin:13px 0 0;overflow:hidden;text-align:right}.markdown-body span.align-right span img{margin:0;text-align:right}.markdown-body span.float-left{display:block;float:left;margin-right:13px;overflow:hidden}.markdown-body span.float-left span{margin:13px 0 0}.markdown-body span.float-right{display:block;float:right;margin-left:13px;overflow:hidden}.markdown-body span.float-right>span{display:block;margin:13px auto 0;overflow:hidden;text-align:right}.markdown-body code,.markdown-body tt{padding:0;padding-top:.2em;padding-bottom:.2em;margin:0;font-size:85%;background-color:rgba(0,0,0,.04);border-radius:3px}.markdown-body code:after,.markdown-body code:before,.markdown-body tt:after,.markdown-body tt:before{letter-spacing:-.2em;content:"\A0"}.markdown-body code br,.markdown-body tt br{display:none}.markdown-body del code{text-decoration:inherit}.markdown-body pre{word-wrap:normal}.markdown-body pre>code{padding:0;margin:0;font-size:100%;word-break:normal;white-space:pre;background:transparent;border:0}.markdown-body .highlight{margin-bottom:16px}.markdown-body .highlight pre{margin-bottom:0;word-break:normal}.markdown-body .highlight pre,.markdown-body pre{padding:16px;overflow:auto;font-size:85%;line-height:1.45;background-color:#f7f7f7;border-radius:3px}.markdown-body pre code,.markdown-body pre tt{display:inline;max-width:auto;padding:0;margin:0;overflow:visible;line-height:inherit;word-wrap:normal;background-color:transparent;border:0}.markdown-body pre code:after,.markdown-body pre code:before,.markdown-body pre tt:after,.markdown-body pre tt:before{content:normal}.markdown-body .csv-data td,.markdown-body .csv-data th{padding:5px;overflow:hidden;font-size:12px;line-height:1;text-align:left;white-space:nowrap}.markdown-body .csv-data .blob-line-num{padding:10px 8px 9px;text-align:right;background:#fff;border:0}.markdown-body .csv-data tr{border-top:0}.markdown-body .csv-data th{font-weight:700;background:#f8f8f8;border-top:0}.markdown-body kbd{display:inline-block;padding:3px 5px;font-size:11px;line-height:10px;color:#555;vertical-align:middle;background-color:#fcfcfc;border:1px solid #ccc;border-bottom-color:#bbb;border-radius:3px;box-shadow:inset 0 -1px 0 #bbb}.news .alert .markdown-body blockquote{padding:0 0 0 40px;border:0 none}.activity-tab .news .alert .commits,.activity-tab .news .markdown-body blockquote{padding-left:0}.task-list-item{list-style-type:none}.task-list-item label{font-weight:400}.task-list-item.enabled label{cursor:pointer}.task-list-item+.task-list-item{margin-top:3px}.task-list-item-checkbox{float:left;margin:.31em 0 .2em -1.3em!important;vertical-align:middle;cursor:default!important}.markdown-body{font-family:-apple-system,BlinkMacSystemFont,Segoe UI,Roboto,Helvetica Neue,Helvetica,Arial,sans-serif;padding-top:40px;padding-bottom:40px;max-width:758px;overflow:visible!important}.markdown-body pre{border:inherit!important}.markdown-body code{color:inherit!important}.markdown-body pre code .wrapper{display:-moz-inline-flex;display:-ms-inline-flex;display:-o-inline-flex;display:inline-flex}.markdown-body pre code .gutter{float:left;overflow:hidden;-webkit-user-select:none;user-select:none}.markdown-body pre code .gutter.linenumber{text-align:right;position:relative;display:inline-block;cursor:default;z-index:4;padding:0 8px 0 0;min-width:20px;box-sizing:content-box;color:#afafaf!important;border-right:3px solid #6ce26c!important}.markdown-body pre code .gutter.linenumber>span:before{content:attr(data-linenumber)}.markdown-body pre code .code{float:left;margin:0 0 0 16px}.markdown-body .gist .line-numbers{border-left:none;border-top:none;border-bottom:none}.markdown-body .gist .line-data{border:none}.markdown-body .gist table{border-spacing:0;border-collapse:inherit!important}.markdown-body code[data-gist-id]{background:none;padding:0}.markdown-body code[data-gist-id]:after,.markdown-body code[data-gist-id]:before{content:""}.markdown-body code[data-gist-id] .blob-num{border:unset}.markdown-body code[data-gist-id] table{overflow:unset;margin-bottom:unset}.markdown-body code[data-gist-id] table tr{background:unset}.markdown-body[dir=rtl] pre{direction:ltr}.markdown-body[dir=rtl] code{direction:ltr;unicode-bidi:embed}.markdown-body .alert>p{margin-bottom:0}.markdown-body pre.flow-chart,.markdown-body pre.graphviz,.markdown-body pre.mermaid,.markdown-body pre.sequence-diagram{text-align:center;background-color:inherit;border-radius:0;white-space:inherit}.markdown-body pre.flow-chart>code,.markdown-body pre.graphviz>code,.markdown-body pre.mermaid>code,.markdown-body pre.sequence-diagram>code{text-align:left}.markdown-body pre.flow-chart>svg,.markdown-body pre.graphviz>svg,.markdown-body pre.mermaid>svg,.markdown-body pre.sequence-diagram>svg{max-width:100%;height:100%}.markdown-body pre>code.wrap{white-space:pre-wrap;white-space:-moz-pre-wrap;white-space:-pre-wrap;white-space:-o-pre-wrap;word-wrap:break-word}.markdown-body .alert>p,.markdown-body .alert>ul{margin-bottom:0}.vimeo,.youtube{cursor:pointer;display:table;text-align:center;background-position:50%;background-repeat:no-repeat;background-size:contain;background-color:#000;overflow:hidden}.vimeo,.youtube{position:relative;width:100%}.youtube{padding-bottom:56.25%}.vimeo img{width:100%;object-fit:contain;z-index:0}.youtube img{object-fit:cover;z-index:0}.vimeo iframe,.youtube iframe,.youtube img{width:100%;height:100%;position:absolute;top:0;left:0}.vimeo iframe,.youtube iframe{vertical-align:middle;z-index:1}.vimeo .icon,.youtube .icon{position:absolute;height:auto;width:auto;top:50%;left:50%;transform:translate(-50%,-50%);color:#fff;opacity:.3;-webkit-transition:opacity .2s;transition:opacity .2s;z-index:0}.vimeo:hover .icon,.youtube:hover .icon{opacity:.6;-webkit-transition:opacity .2s;transition:opacity .2s}.slideshare .inner,.speakerdeck .inner{position:relative;width:100%}.slideshare .inner iframe,.speakerdeck .inner iframe{position:absolute;top:0;bottom:0;left:0;right:0;width:100%;height:100%}.MJX_Assistive_MathML{display:none}.ui-infobar{position:relative;z-index:2;max-width:758px;margin-top:25px;margin-bottom:-25px;color:#777}.ui-toc{position:fixed;bottom:20px;z-index:10000}.ui-toc-label{opacity:.3;background-color:#ccc;border:none}.ui-toc-label,.ui-toc .open .ui-toc-label{-webkit-transition:opacity .2s;transition:opacity .2s}.ui-toc .open .ui-toc-label{opacity:1;color:#fff}.ui-toc-label:focus{opacity:.3;background-color:#ccc;color:#000}.ui-toc-label:hover{opacity:1;background-color:#ccc;-webkit-transition:opacity .2s;transition:opacity .2s}.ui-toc-dropdown{margin-top:23px;margin-bottom:20px;padding-left:10px;padding-right:10px;max-width:45vw;width:25vw;max-height:70vh;overflow:auto;text-align:inherit}.ui-toc-dropdown>.toc{max-height:calc(70vh - 100px);overflow:auto}.ui-toc-dropdown[dir=rtl] .nav{padding-right:0;letter-spacing:.0029em}.ui-toc-dropdown a{overflow:hidden;text-overflow:ellipsis;white-space:pre}.ui-toc-dropdown .nav>li>a{display:block;padding:4px 20px;font-size:13px;font-weight:500;color:#767676}.ui-toc-dropdown .nav>li:first-child:last-child > ul,.ui-toc-dropdown .toc.expand ul{display:block}.ui-toc-dropdown .nav>li>a:focus,.ui-toc-dropdown .nav>li>a:hover{padding-left:19px;color:#000;text-decoration:none;background-color:transparent;border-left:1px solid #000}.ui-toc-dropdown[dir=rtl] .nav>li>a:focus,.ui-toc-dropdown[dir=rtl] .nav>li>a:hover{padding-right:19px;border-left:none;border-right:1px solid #000}.ui-toc-dropdown .nav>.active:focus>a,.ui-toc-dropdown .nav>.active:hover>a,.ui-toc-dropdown .nav>.active>a{padding-left:18px;font-weight:700;color:#000;background-color:transparent;border-left:2px solid #000}.ui-toc-dropdown[dir=rtl] .nav>.active:focus>a,.ui-toc-dropdown[dir=rtl] .nav>.active:hover>a,.ui-toc-dropdown[dir=rtl] .nav>.active>a{padding-right:18px;border-left:none;border-right:2px solid #000}.ui-toc-dropdown .nav .nav{display:none;padding-bottom:10px}.ui-toc-dropdown .nav>.active>ul{display:block}.ui-toc-dropdown .nav .nav>li>a{padding-top:1px;padding-bottom:1px;padding-left:30px;font-size:12px;font-weight:400}.ui-toc-dropdown[dir=rtl] .nav .nav>li>a{padding-right:30px}.ui-toc-dropdown .nav .nav>li>ul>li>a{padding-top:1px;padding-bottom:1px;padding-left:40px;font-size:12px;font-weight:400}.ui-toc-dropdown[dir=rtl] .nav .nav>li>ul>li>a{padding-right:40px}.ui-toc-dropdown .nav .nav>li>a:focus,.ui-toc-dropdown .nav .nav>li>a:hover{padding-left:29px}.ui-toc-dropdown[dir=rtl] .nav .nav>li>a:focus,.ui-toc-dropdown[dir=rtl] .nav .nav>li>a:hover{padding-right:29px}.ui-toc-dropdown .nav .nav>li>ul>li>a:focus,.ui-toc-dropdown .nav .nav>li>ul>li>a:hover{padding-left:39px}.ui-toc-dropdown[dir=rtl] .nav .nav>li>ul>li>a:focus,.ui-toc-dropdown[dir=rtl] .nav .nav>li>ul>li>a:hover{padding-right:39px}.ui-toc-dropdown .nav .nav>.active:focus>a,.ui-toc-dropdown .nav .nav>.active:hover>a,.ui-toc-dropdown .nav .nav>.active>a{padding-left:28px;font-weight:500}.ui-toc-dropdown[dir=rtl] .nav .nav>.active:focus>a,.ui-toc-dropdown[dir=rtl] .nav .nav>.active:hover>a,.ui-toc-dropdown[dir=rtl] .nav .nav>.active>a{padding-right:28px}.ui-toc-dropdown .nav .nav>.active>.nav>.active:focus>a,.ui-toc-dropdown .nav .nav>.active>.nav>.active:hover>a,.ui-toc-dropdown .nav .nav>.active>.nav>.active>a{padding-left:38px;font-weight:500}.ui-toc-dropdown[dir=rtl] .nav .nav>.active>.nav>.active:focus>a,.ui-toc-dropdown[dir=rtl] .nav .nav>.active>.nav>.active:hover>a,.ui-toc-dropdown[dir=rtl] .nav .nav>.active>.nav>.active>a{padding-right:38px}.markdown-body[lang^=ja]{font-family:-apple-system,BlinkMacSystemFont,Segoe UI,Roboto,Helvetica Neue,Helvetica,Arial,Hiragino Kaku Gothic Pro,\\30D2\30E9\30AE\30CE\89D2\30B4 Pro W3,Osaka,Meiryo,\\30E1\30A4\30EA\30AA,MS Gothic,"\FF2D\FF33   \30B4\30B7\30C3\30AF",sans-serif}.ui-toc-dropdown[lang^=ja]{font-family:Source Sans Pro,Helvetica,Arial,Meiryo UI,MS PGothic,"\FF2D\FF33   \FF30\30B4\30B7\30C3\30AF",sans-serif}.markdown-body[lang=zh-tw]{font-family:-apple-system,BlinkMacSystemFont,Segoe UI,Roboto,Helvetica Neue,Helvetica,Arial,PingFang TC,Microsoft JhengHei,\\5FAE\8EDF\6B63\9ED1,sans-serif}.ui-toc-dropdown[lang=zh-tw]{font-family:Source Sans Pro,Helvetica,Arial,Microsoft JhengHei UI,\\5FAE\8EDF\6B63\9ED1UI,sans-serif}.markdown-body[lang=zh-cn]{font-family:-apple-system,BlinkMacSystemFont,Segoe UI,Roboto,Helvetica Neue,Helvetica,Arial,PingFang SC,Microsoft YaHei,\\5FAE\8F6F\96C5\9ED1,sans-serif}.ui-toc-dropdown[lang=zh-cn]{font-family:Source Sans Pro,Helvetica,Arial,Microsoft YaHei UI,\\5FAE\8F6F\96C5\9ED1UI,sans-serif}.ui-affix-toc{position:fixed;top:0;max-width:15vw;max-height:70vh;overflow:auto}.back-to-top,.expand-toggle,.go-to-bottom{display:block;padding:4px 10px;margin-top:10px;margin-left:10px;font-size:12px;font-weight:500;color:#999}.back-to-top:focus,.back-to-top:hover,.expand-toggle:focus,.expand-toggle:hover,.go-to-bottom:focus,.go-to-bottom:hover{color:#563d7c;text-decoration:none}.back-to-top,.go-to-bottom{margin-top:0}.ui-user-icon{width:20px;height:20px;display:block;border-radius:3px;margin-top:2px;margin-bottom:2px;margin-right:5px;background-position:50%;background-repeat:no-repeat;background-size:contain}.ui-user-icon.small{width:18px;height:18px;display:inline-block;vertical-align:middle;margin:0 0 .2em}small span{line-height:22px}small .dropdown{display:inline-block}small .dropdown a:focus,small .dropdown a:hover{text-decoration:none}.unselectable{-moz-user-select:none;-webkit-user-select:none;-o-user-select:none;user-select:none}@media print{blockquote,div,img,pre,table{page-break-inside:avoid!important}a[href]:after{font-size:12px!important}}.markdown-body.slides{position:relative;z-index:1;color:#222}.markdown-body.slides:before{content:"";display:block;position:absolute;top:0;left:0;right:0;bottom:0;z-index:-1;background-color:currentColor;box-shadow:0 0 0 50vw}.markdown-body.slides section[data-markdown]{position:relative;margin-bottom:1.5em;background-color:#fff;text-align:center}.markdown-body.slides section[data-markdown] code{text-align:left}.markdown-body.slides section[data-markdown]:before{content:"";display:block;padding-bottom:56.23%}.markdown-body.slides section[data-markdown]>div:first-child{position:absolute;top:50%;left:1em;right:1em;transform:translateY(-50%);max-height:100%;overflow:hidden}.markdown-body.slides section[data-markdown]>ul{display:inline-block}.markdown-body.slides>section>section+section:after{content:"";position:absolute;top:-1.5em;right:1em;height:1.5em;border:3px solid #777}body{font-smoothing:subpixel-antialiased!important;-webkit-font-smoothing:subpixel-antialiased!important;-moz-osx-font-smoothing:auto!important;text-shadow:0 0 1em transparent,1px 1px 1.2px rgba(0,0,0,.004);-webkit-overflow-scrolling:touch;font-family:Source Sans Pro,Helvetica,Arial,sans-serif;letter-spacing:.025em}.focus,:focus{outline:none!important}::-moz-focus-inner{border:0!important}body.modal-open{overflow-y:auto;padding-right:0!important}
    </style>
    <!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
    <!-- WARNING: Respond.js doesn't work if you view the page via file:// -->
    <!--[if lt IE 9]>
    	<script src="https://cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv.min.js" integrity="sha256-3Jy/GbSLrg0o9y5Z5n1uw0qxZECH7C6OQpVBgNFYa0g=" crossorigin="anonymous"></script>
    	<script src="https://cdnjs.cloudflare.com/ajax/libs/respond.js/1.4.2/respond.min.js" integrity="sha256-g6iAfvZp+nDQ2TdTR/VVKJf3bGro4ub5fvWSWVRi2NE=" crossorigin="anonymous"></script>
		<script src="https://cdnjs.cloudflare.com/ajax/libs/es5-shim/4.5.9/es5-shim.min.js" integrity="sha256-8E4Is26QH0bD52WoQpcB+R/tcWQtpzlCojrybUd7Mxo=" crossorigin="anonymous"></script>
    <![endif]-->
</head>

<body>
    <div id="doc" class="markdown-body container-fluid"><h1 id="cs-notes"><a class="anchor hidden-xs" href="#cs-notes" title="cs-notes"><span class="octicon octicon-link"></span></a>CS Notes</h1><h1 id="beginning-of-paper-1-content"><a class="anchor hidden-xs" href="#beginning-of-paper-1-content" title="beginning-of-paper-1-content"><span class="octicon octicon-link"></span></a>Beginning of Paper 1 content</h1><h1 id="programming"><a class="anchor hidden-xs" href="#programming" title="programming"><span class="octicon octicon-link"></span></a>Programming</h1><p><strong>Memory</strong> The location where instructions and data are stored on the computer</p><p><strong>Algorithm</strong> A sequence of steps that can be followed to complete a task. The sequence must always terminate</p><p><strong>Syntax</strong> The rules of how words are used within a given language</p><p><strong>Memory address</strong> A specific location in memory where instructions or data are stored</p><p><strong>Pointer</strong> A data item that identifies a particular element in a data structure</p><p><strong>Array</strong> A set of related items stored under a single identifier</p><p><strong>Element</strong> A single item within a set or list</p><p><strong>Record</strong> A single line of a text file</p><p><strong>Subroutine/Procedure/Subprogram/Routine</strong> A name block of code designed to carry out a specific task</p><p><strong>Function</strong> A subroutine that returns a value</p><p><strong>Exception handling</strong> The process of dealing with events that cause the current subroutine to stop</p><p><strong>Procedural programming languages</strong> Languages where the programmer specifies the steps that must be carried out in order to achieve a result</p><p><strong>Imperative programming languages</strong> Languages based on giving the computer commands or procedures to follow</p><p><strong>Hierarchy chart</strong> A diagram that shows the design of a system from the top down</p><p><strong>Structure chart</strong> Similar to a hierarchy chart with the addition of showing how data is passed around the system</p><p><strong>Top-down approach</strong> A design process in which you start at the top of the process and work down into smaller and smaller sub-processes</p><p><strong>Modular design</strong> A method of system design that breaks a whole system down into smaller units, or modules</p><p><strong>Class</strong> A class defines methods and fields that capture the common characteristics of objects</p><h2 id="encapsulation"><a class="anchor hidden-xs" href="#encapsulation" title="encapsulation"><span class="octicon octicon-link"></span></a>Encapsulation</h2><p>Encapsulation is the concept of keeping the data and code within the same object.</p><p><strong>Method</strong> The code or routines contained within a class</p><p><strong>Properties</strong> The defining features of an object or a class in terms of its data</p><p>A class defines properties, methods and how they will behave.<br>
An object is an instance of a class, containing its methods and the data defined in the class.</p><h2 id="inheritance"><a class="anchor hidden-xs" href="#inheritance" title="inheritance"><span class="octicon octicon-link"></span></a>Inheritance</h2><p><strong>Inheritance</strong> The concept that properties and methods in one class can be shared with a subclass</p><h3 id="class-diagrams-for-inheritance"><a class="anchor hidden-xs" href="#class-diagrams-for-inheritance" title="class-diagrams-for-inheritance"><span class="octicon octicon-link"></span></a>Class diagrams for inheritance</h3><p><strong>Class diagrams</strong> A way of representing the relationship between classes</p><p>Class diagrams are hierarchical in structure, with the base class at the top and sub-classes beneath.</p><ul>
<li>The subclass inherits the properties and method of the base class</li>
<li>Arrows are used to show the direction of inheritance</li>
<li>Each class is represented with a box made up of three sections to include the class name, properties, and methods</li>
</ul><h2 id="instantiation"><a class="anchor hidden-xs" href="#instantiation" title="instantiation"><span class="octicon octicon-link"></span></a>Instantiation</h2><p><strong>Instantiation</strong> The process of creating an object from a class.</p><h2 id="polymorphism-and-overriding"><a class="anchor hidden-xs" href="#polymorphism-and-overriding" title="polymorphism-and-overriding"><span class="octicon octicon-link"></span></a>Polymorphism and overriding</h2><p><strong>Polymorphism</strong> The ability of different types of data to be manipulated with the same method</p><p>Polymorphism allows a method to be redefined, overridden, to work with the changes made to the sub-class.</p><h2 id="abstract-virtual-and-static-methods"><a class="anchor hidden-xs" href="#abstract-virtual-and-static-methods" title="abstract-virtual-and-static-methods"><span class="octicon octicon-link"></span></a>Abstract, virtual, and static methods</h2><p>Static methods can be used without an instance of the class being instantiated</p><p>Virtual methods are defined in the base class but can be overridden by the method in the sub-class where it is used.</p><p>Abstract methods are not supplied in the base class, but must be provided in the subclass</p><h2 id="aggregation"><a class="anchor hidden-xs" href="#aggregation" title="aggregation"><span class="octicon octicon-link"></span></a>Aggregation</h2><p>Aggregation is a method of creating new objects that contain existing object, based on the way in which objects are related.</p><p>All of the objects exist in their own right, but their is a relationship between them.</p><h2 id="composition-aggregation"><a class="anchor hidden-xs" href="#composition-aggregation" title="composition-aggregation"><span class="octicon octicon-link"></span></a>Composition aggregation</h2><p><strong>Composition aggregation</strong> Creating an object that contains objects, and will cease to exist if the containing object is destroyed</p><h2 id="association-aggregation"><a class="anchor hidden-xs" href="#association-aggregation" title="association-aggregation"><span class="octicon octicon-link"></span></a>Association aggregation</h2><p><strong>Association aggregation</strong> Creating an object that contains other objects, which can continue to exist even if the containing object is destroyed</p><h2 id="design-principles"><a class="anchor hidden-xs" href="#design-principles" title="design-principles"><span class="octicon octicon-link"></span></a>Design principles</h2><ul>
<li>
<p><strong>Encapsulate what varies</strong>: Properties and methods are subdivided into as many classes as needed to reflect the real-life scenario</p>
</li>
<li>
<p><strong>Favour composition over inheritance</strong>: This refers to the way in which classes and objects are instantiated. Composition is less error prone and enables simpler maintenance</p>
</li>
<li>
<p><strong>Program to interfaces, not implementation</strong>:Interface methods are widely used. When a class is created that adheres to the methods in the interface, it can be seen as an implementation of the interface. Programs can be written based on interfaces rather than each individual implementation of a class. If a class needs to be amended, this can be done with reference to the interface, meaning that there will be little or no impact on the other classes in the program</p>
</li>
</ul><h1 id="data-structures"><a class="anchor hidden-xs" href="#data-structures" title="data-structures"><span class="octicon octicon-link"></span></a>Data structures</h1><h2 id="data-structures-and-abstract-data-types"><a class="anchor hidden-xs" href="#data-structures-and-abstract-data-types" title="data-structures-and-abstract-data-types"><span class="octicon octicon-link"></span></a>Data structures and abstract data types</h2><p><strong>Data structure</strong> A common format for storing large volumes of related data, which is an implementation of an abstract data type</p><p><strong>Abstract data type</strong> A conceptual model of how data can be stored and the operations can be carried out on the data</p><p><strong>File</strong> A collection of related data</p><h3 id="binary-files"><a class="anchor hidden-xs" href="#binary-files" title="binary-files"><span class="octicon octicon-link"></span></a>Binary files</h3><p>Binary files contain binary codes and usually some header information</p><h3 id="static-and-dynamic-data-structures"><a class="anchor hidden-xs" href="#static-and-dynamic-data-structures" title="static-and-dynamic-data-structures"><span class="octicon octicon-link"></span></a>Static and dynamic data structures</h3><p><strong>Static data structure</strong> A method of storing data where the amount of data stored is fixed</p><p><strong>Dynamic data structure</strong> A method of storing data where the amount of data stored will vary as the program is being run</p><p><strong>Heap</strong> A pool of unused memory that can be allocated to a dynamic data structure</p><p><strong>Stack</strong> A data structure where the last item added is the first item removed</p><p><strong>Queue</strong> A data structure where the last item added is the first item removed</p><table>
<thead>
<tr>
<th>Static</th>
<th>Dynamic</th>
</tr>
</thead>
<tbody>
<tr>
<td>Inefficient as memory is allocated that may not be needed</td>
<td>Efficient as the amount of memory varies as needed</td>
</tr>
<tr>
<td>Fast access to each item of data as the memory location is fixed when the program is written</td>
<td>Slower access as the memory location is allocated at run-time</td>
</tr>
<tr>
<td>Memory addresses allocated will be contiguous so quicker to access</td>
<td>Memory addresses allocated may be fragmented, resulting in slower access</td>
</tr>
<tr>
<td>Structures are a fixed size, making them more predictable to work with</td>
<td>Structures vary in size so there needs to be a mechanism for knowing the size of the current structure</td>
</tr>
<tr>
<td>The relationship between different elements of data does not change</td>
<td>The relationship between different elements of data will change as the program is run</td>
</tr>
</tbody>
</table><h2 id="stacks-and-queues"><a class="anchor hidden-xs" href="#stacks-and-queues" title="stacks-and-queues"><span class="octicon octicon-link"></span></a>Stacks and queues</h2><h3 id="stacks"><a class="anchor hidden-xs" href="#stacks" title="stacks"><span class="octicon octicon-link"></span></a>Stacks</h3><p><strong>Stack</strong> A last in first out structure</p><p>The stack pointer stores where the stop of the stack is.</p><h4 id="pushing-to-a-stack"><a class="anchor hidden-xs" href="#pushing-to-a-stack" title="pushing-to-a-stack"><span class="octicon octicon-link"></span></a>Pushing to a stack</h4><pre><code class="python hljs"><span class="hljs-keyword">if</span> stack_pointer &lt; stack.size:
    stack_pointer += <span class="hljs-number">1</span>
    stack_array[stack_pointer] = data_item
<span class="hljs-keyword">else</span>:
    error(<span class="hljs-string">"Stack full"</span>)
</code></pre><h4 id="popping-from-the-stack"><a class="anchor hidden-xs" href="#popping-from-the-stack" title="popping-from-the-stack"><span class="octicon octicon-link"></span></a>Popping from the stack</h4><pre><code class="python hljs"><span class="hljs-keyword">if</span> stack_pointer &gt; <span class="hljs-number">0</span>:
    data_item = stack_array[stack_pointer]
    stack_pointer -= <span class="hljs-number">1</span>
<span class="hljs-keyword">else</span>:
    error(<span class="hljs-string">"The stack is empty"</span>)
</code></pre><h4 id="stack-frames"><a class="anchor hidden-xs" href="#stack-frames" title="stack-frames"><span class="octicon octicon-link"></span></a>Stack frames</h4><p><strong>Stack frame</strong> A collection of data about a subroutine call</p><p>The stack frame contains the parameters to the subroutine call, its local variables, and its return address.</p><p><strong>Call stack</strong> A type of stack used to store information about active subroutines and functions within a program</p><p><strong>Interrupt</strong> A signal sent by a device or program to the processor requesting its attention</p><p><strong>Recursion</strong> The process of a subroutine calling itself</p><h3 id="queues"><a class="anchor hidden-xs" href="#queues" title="queues"><span class="octicon octicon-link"></span></a>Queues</h3><p><strong>Queue</strong> A first in first out structure</p><p><strong>Linear queue</strong> A first in first out structure organised as a line of data</p><p><strong>Circular queue</strong> A first in first out structure implemented as a ring where the front and rear pointers can wrap around from the end to the start of the array</p><p><strong>Priority queue</strong> A variant of a first in first out structure where some data types may leave out of sequence if they have a higher priority than other data items</p><h2 id="graphs-and-trees"><a class="anchor hidden-xs" href="#graphs-and-trees" title="graphs-and-trees"><span class="octicon octicon-link"></span></a>Graphs and trees</h2><p><strong>Graph</strong> A mathematical structure that models the relationship between pairs of objects</p><p><strong>Graph theory</strong> The underlying mathematical principles behind the use of graphs</p><p><strong>Arc</strong> A join or relationship between two nodes, also known as an edge</p><p><strong>Vertex/Vertices</strong> An object in a graph, also known as a node</p><p><strong>Weighted graph</strong> A graph that has a data value labelled on each edge</p><p><strong>Undirected graph</strong> A graph when the relationship between the vertices is two way</p><p><strong>Directed graph</strong> A graph when the relationship between the vertices is one way</p><p><strong>Latency</strong> The time delay that occurs when transmitting data between devices</p><h3 id="adjacency-lists-and-matrices"><a class="anchor hidden-xs" href="#adjacency-lists-and-matrices" title="adjacency-lists-and-matrices"><span class="octicon octicon-link"></span></a>Adjacency lists and matrices</h3><p><strong>Adjacency list</strong> A data structure that stores a list of nodes with their adjacent values</p><p>A weighted graph may be stored in an adjacency list by writing each adjacency of a pair of the adjacent node and the weight of the edge</p><p><strong>Adjacency matrix</strong> A data structure set up as a two dimensional array that shows whether there is an edge between each node</p><table>
<thead>
<tr>
<th>Adjacency list</th>
<th>Adjacency matrix</th>
</tr>
</thead>
<tbody>
<tr>
<td>Only stores data where there is an edge, requiring less memory</td>
<td>Stores a value for every combination, requiring more memory</td>
</tr>
<tr>
<td>The list must be parsed to identify whether particular adjacencies exist</td>
<td>Adjacencies can be identified more quickly as every combination is stored</td>
</tr>
<tr>
<td>Where there are not many edges, a sparse graph, this method would be more suitable</td>
<td>Where there are many edges, a dense graph, this method would be more suitable</td>
</tr>
</tbody>
</table><h3 id="trees"><a class="anchor hidden-xs" href="#trees" title="trees"><span class="octicon octicon-link"></span></a>Trees</h3><p><strong>Tree</strong> A data structure similar to a graph, containing no loops</p><p><strong>Rooted tree</strong> A tree in which one vertex has been designated as the root</p><p><strong>Node</strong> An object in a graph</p><p><strong>Edge</strong> A join of relationship between nodes</p><p><strong>Root</strong> The starting node in a rooted data structure from which all other nodes branch off</p><p><strong>Parent</strong> A type of node in a tree, where there are further nodes below it</p><p><strong>Leaf</strong> A node that does not have any other nodes beneath it</p><h4 id="binary-search-tree"><a class="anchor hidden-xs" href="#binary-search-tree" title="binary-search-tree"><span class="octicon octicon-link"></span></a>Binary search tree</h4><p><strong>Binary search tree</strong> A tree where each node can only have up to two child nodes attached to it</p><h5 id="binary-tree-implementation"><a class="anchor hidden-xs" href="#binary-tree-implementation" title="binary-tree-implementation"><span class="octicon octicon-link"></span></a>Binary tree implementation</h5><p>This implementation uses three arrays:</p><ul>
<li>The first stores the data</li>
<li>The second stores the left pointers</li>
<li>The right stores the right pointers</li>
</ul><h4 id="tree-traversal"><a class="anchor hidden-xs" href="#tree-traversal" title="tree-traversal"><span class="octicon octicon-link"></span></a>Tree traversal</h4><p>Pre-order for copying a tree</p><p>In-order for a binary search tree or outputting the contents of a binary search tree in ascending order</p><p>Post-order for Infix to RPN conversions, producing an infix expression from a tree, or emptying a tree</p><h2 id="hash-tables-and-dictionaries"><a class="anchor hidden-xs" href="#hash-tables-and-dictionaries" title="hash-tables-and-dictionaries"><span class="octicon octicon-link"></span></a>Hash tables and dictionaries</h2><p><strong>Hash table</strong> A data structure that stores key value pairs based on an index calculated from an algorithm</p><h3 id="hash-tables"><a class="anchor hidden-xs" href="#hash-tables" title="hash-tables"><span class="octicon octicon-link"></span></a>Hash tables</h3><p><strong>Hashing algorithm</strong> An algorithm that creates a unique index from given items of key data</p><p><strong>Cache</strong> A high speed temporary area of memory</p><p>Features and problems for a hashing algorithm:</p><ul>
<li>Numeric value needs to be generated from the data to perform the calculation</li>
<li>Unique indices must be generated. Non-unique indices are collisions which must be coped with</li>
<li>The indices must be uniformly distributed to avoid clustering</li>
<li>The algorithm must be capable of producing the necessary number of unique indices</li>
<li>The algorithm must balance efficiency and complexity</li>
</ul><p><strong>Collision</strong> When a hashing algorithm produces the same index for two or more different keys</p><p><strong>Clustering</strong> When a hashing algorithm produces indices that are not randomly distributed</p><p><strong>Load factor</strong> The ratio of the number of indices available to how many there are in total</p><p><strong>Index</strong> The location where values will be stored, calculated from the key</p><p><strong>Chaining</strong> A technique for generating a unique index when there is a collision by adding the key value to a list stored at the same index</p><p><strong>Rehashing</strong> The process of running the hashing algorithm again when a collision occurs</p><h3 id="dictionaries"><a class="anchor hidden-xs" href="#dictionaries" title="dictionaries"><span class="octicon octicon-link"></span></a>Dictionaries</h3><p><strong>Dictionary</strong> A data structure that maps keys to data</p><p><strong>Associative array</strong> A two dimensional structure containing key value pairs of data</p><h2 id="vectors"><a class="anchor hidden-xs" href="#vectors" title="vectors"><span class="octicon octicon-link"></span></a>Vectors</h2><p>Vectors can be represented as values stored in a list.</p><p>Vectors can also be represented as a function.<br>
A function maps an input to an output.<br>
F:S -&gt; R<br>
F is the function that creates the vector<br>
S is the complete set of values that the function can be applied to<br>
R is the potential outputs of the function</p><p><strong>Magnitude</strong> The size of the vector<br>
<strong>Direction</strong> The direction of the vector<br>
<strong>Components</strong> The values within a vector</p><h3 id="vector-addition"><a class="anchor hidden-xs" href="#vector-addition" title="vector-addition"><span class="octicon octicon-link"></span></a>Vector addition</h3><p>Vectors are added by adding the respective components of the vectors</p><h3 id="scalar-vector-multiplication"><a class="anchor hidden-xs" href="#scalar-vector-multiplication" title="scalar-vector-multiplication"><span class="octicon octicon-link"></span></a>Scalar vector multiplication</h3><p><strong>Scalar</strong> A real value used to multiply a vector to scale the vector</p><h3 id="dot-product"><a class="anchor hidden-xs" href="#dot-product" title="dot-product"><span class="octicon octicon-link"></span></a>Dot product</h3><p><strong>Dot product</strong> The process of combining two vectors to calculate a single number.</p><p>A.B = A<sub>x</sub>B<sub>x</sub>+ A<sub>y</sub>B<sub>y</sub></p><h3 id="convex-combinations"><a class="anchor hidden-xs" href="#convex-combinations" title="convex-combinations"><span class="octicon octicon-link"></span></a>Convex combinations</h3><p><strong>Convex hull</strong> A spatial representation of the vector space between two vectors</p><p><strong>Convex combination</strong> A method of multiplying vectors that produces a resulting vector within the convex hull</p><p><strong>Vector space</strong> A collection of elements that can be formed by adding or multiplying vectors together</p><p>Performing a convex combination is either multiplying one vector by either a scalar or another vector</p><p>D = αAB + βAC</p><p>Where AB and AC are the two vectors.</p><p>α and β represent the real numbers that each vector will be multiplied by.</p><p>α and β must both be greater than or equal to 0, and αβ must equal 1. D will then fall within the vector space.<br>
<em>Surely if either is 0, then αβ != 1?</em></p><h3 id="uses-of-the-dot-product"><a class="anchor hidden-xs" href="#uses-of-the-dot-product" title="uses-of-the-dot-product"><span class="octicon octicon-link"></span></a>Uses of the dot product</h3><p>Given two vectors u and v, it is possible to generate parity using bitwise AND and XOR operations.</p><p>Where u = [1,1,1,1] and v = [1,0,1,1], the dot product would be u.v = 1.<br>
This is calculated by performing arithmetic over GF(2) where GF has two elements 0 and 1.<br>
This calculation finds the parity bit for even t parity.<br>
The first vector will always be [1,1,1,1].</p><p>uv. = [1,1,1,1].[1,0,1,1]<br>
= 1 AND 1 XOR 1 AND 0 XOR 1 AND 1 XOR 1 AND 1<br>
= 1 XOR 0 XOR 1 XOR 1<br>
= 1</p><p>Arithmetic over GF(2) can be summarised in two small tables.<br>
Multiplication can be achieved by the bitwise AND operation, and addition can be achieved by the bitwise XOR operation.</p><h1 id="algorithms"><a class="anchor hidden-xs" href="#algorithms" title="algorithms"><span class="octicon octicon-link"></span></a>Algorithms</h1><h2 id="graph-and-tree-traversal"><a class="anchor hidden-xs" href="#graph-and-tree-traversal" title="graph-and-tree-traversal"><span class="octicon octicon-link"></span></a>Graph and tree traversal</h2><p><strong>Implementation</strong> Creating code to produce a programmed solution</p><p><strong>Depth first</strong> A method for traversing a graph that starts at a chosen node and explores as far as possible along each branch away from the starting node before backtracking</p><p><strong>Breadth first</strong> A method for traversing a graph that explores nodes closest to the starting node first before progressively exploring nodes that are further away</p><p>Method for depth first traversal</p><table>
<thead>
<tr>
<th>Explanation</th>
<th>Current node</th>
<th>Visited nodes</th>
</tr>
</thead>
<tbody>
<tr>
<td>Selected the node to start [A]</td>
<td>A</td>
<td></td>
</tr>
<tr>
<td>Mark node a as visited. Choose a node that is connected to A [B] and recursively call the search routine to explore this node</td>
<td>A</td>
<td>A</td>
</tr>
<tr>
<td>Mark Node B as visited. Choose a node that is connected to B and has not been visited [C] (recurse)</td>
<td>B</td>
<td>A, B</td>
</tr>
<tr>
<td>As above with C. Choosing D</td>
<td>C</td>
<td>A, B, C</td>
</tr>
<tr>
<td>As above with D. Choosing E</td>
<td>D</td>
<td>A, B, C, D</td>
</tr>
<tr>
<td>Mark node E as visited. All connecting nodes have been visited, so unwind recursion. There are no nodes left to visit so terminate</td>
<td>E</td>
<td>A, B, C, D, E</td>
</tr>
</tbody>
</table><p>In pseudocode</p><pre><code class="python hljs"><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">traverse</span><span class="hljs-params">(node n)</span>:</span>
    visited.add(n)
    <span class="hljs-comment"># Do something with the node</span>
    <span class="hljs-keyword">for</span> node <span class="hljs-keyword">in</span> n.neighbours:
        <span class="hljs-keyword">if</span> node <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> visited:
            traverse(n)
</code></pre><p>Method for breadth first traversal</p><table>
<thead>
<tr>
<th>Explanation</th>
<th>Contents of queue</th>
</tr>
</thead>
<tbody>
<tr>
<td>Add the initial node to the queue</td>
<td>A</td>
</tr>
<tr>
<td>Add all adjacent nodes which are not already fully explored to the queue</td>
<td>A, B</td>
</tr>
<tr>
<td>Remove A from the queue as it is fully explored</td>
<td>B</td>
</tr>
<tr>
<td>Add all nodes that are adjacent to B and not already fully explored to the queue</td>
<td>B, C, E</td>
</tr>
<tr>
<td>Remove B from the queue as fully explored</td>
<td>C, E</td>
</tr>
<tr>
<td>Add all the nodes that are adjacent to C and not already fully explored to the queue</td>
<td>C, E, D</td>
</tr>
<tr>
<td>Remove C from the queue as it is already fully explored</td>
<td>E, D</td>
</tr>
<tr>
<td>Add all nodes that are adjacent to E and not already fully explored to the queue</td>
<td>E, D</td>
</tr>
<tr>
<td>Remove E from the queue as fully explored</td>
<td>D</td>
</tr>
<tr>
<td>Remove D from the queue as fully explored. Terminate as queue empty</td>
<td></td>
</tr>
</tbody>
</table><p><em>Book says remove E and then shows the queue as containing only E</em></p><p><strong>Binary tree</strong> A structure where each node can only have up to two child nodes attached to it</p><p><strong>Pre-order</strong> A method of traversing a tree by visiting the root, traversing the left subtree, and traversing the right subtree</p><p><strong>In-order</strong> A method of traversing a tree by traversing the left subtree, visiting the root, and traversing the right subtree</p><p><strong>Post-order</strong> A method of traversing a tree by traversing the left subtree, traversing the right subtree, and visiting the root</p><p><strong>Traversal</strong> The process of reading data from a tree or graph by visiting all of the nodes</p><p><strong>Binary search</strong> A technique for searching sorted data that splits the dataset in half repeatedly until the search data is found</p><h2 id="dijkstra’s-shortest-path-algorithm"><a class="anchor hidden-xs" href="#dijkstra’s-shortest-path-algorithm" title="dijkstra’s-shortest-path-algorithm"><span class="octicon octicon-link"></span></a>Dijkstra’s shortest path algorithm</h2><p><strong>Single source</strong> The shortest path is calculated from a single starting point</p><h2 id="reverse-polish-notation"><a class="anchor hidden-xs" href="#reverse-polish-notation" title="reverse-polish-notation"><span class="octicon octicon-link"></span></a>Reverse Polish notation</h2><p><strong>Infix</strong> Expressions written with operators within operands</p><p><strong>Polish/Prefix notation</strong> Expressions with operators before operands</p><p><strong>Reverse Polish/Postfix notation</strong> Expressions with operators after operands</p><h3 id="evaluating-postfix-expressions"><a class="anchor hidden-xs" href="#evaluating-postfix-expressions" title="evaluating-postfix-expressions"><span class="octicon octicon-link"></span></a>Evaluating postfix expressions</h3><ul>
<li>Create a stack</li>
<li>For each element:
<ul>
<li>If the element is an operand, push it onto the stack</li>
<li>If the element is an operator, pop twice to get A and B respectively. Calculate B O A and push it to the stack</li>
</ul>
</li>
</ul><p>Example 4 3 * 6 2 * /</p><table>
<thead>
<tr>
<th>Step</th>
<th>Stack</th>
</tr>
</thead>
<tbody>
<tr>
<td>Push 4</td>
<td>4</td>
</tr>
<tr>
<td>Push 3</td>
<td>4, 3</td>
</tr>
<tr>
<td>Evaluate 4 * 3</td>
<td>12</td>
</tr>
<tr>
<td>Push 6</td>
<td>12, 6</td>
</tr>
<tr>
<td>Push 2</td>
<td>12, 6, 2</td>
</tr>
<tr>
<td>Evaluate 6 * 2</td>
<td>12, 12</td>
</tr>
<tr>
<td>Evaluate 12 / 12</td>
<td>1</td>
</tr>
</tbody>
</table><p><strong>In order traversal</strong> A method of extracting data from a binary tree that will result in an infix expression</p><p><strong>Post-order traversal</strong> A method of extracting data from a binary tree that will result in postfix expressions</p><p><strong>Pre-order traversal</strong> A method of extracting data from a binary tree that will result in prefix expressions</p><h3 id="conversion-of-infix-to-postfix"><a class="anchor hidden-xs" href="#conversion-of-infix-to-postfix" title="conversion-of-infix-to-postfix"><span class="octicon octicon-link"></span></a>Conversion of infix to postfix</h3><ul>
<li>Create an empty stack for keeping op</li>
</ul><h3 id="applications-of-postfix"><a class="anchor hidden-xs" href="#applications-of-postfix" title="applications-of-postfix"><span class="octicon octicon-link"></span></a>Applications of postfix</h3><p>Some languages are specifically designed to be stack-oriented and would therefore be ideally suited to this application.<br>
In these cases, the interpreter or compiler checks all of the syntax with reference to the postfix notation of each expression.</p><h2 id="sorting-algorithms"><a class="anchor hidden-xs" href="#sorting-algorithms" title="sorting-algorithms"><span class="octicon octicon-link"></span></a>Sorting algorithms</h2><h3 id="bubble-sort"><a class="anchor hidden-xs" href="#bubble-sort" title="bubble-sort"><span class="octicon octicon-link"></span></a>Bubble sort</h3><p><strong>Bubble sort</strong> A technique for putting data in order by repeatedly stepping through an array, comparing adjacent elements and swapping them if necessary until the array is in order</p><ol>
<li>Iterate through each element
<ol>
<li>Iterate through each element</li>
<li>If the outer element is greater, swap them</li>
</ol>
</li>
<li>When no swap is made in inner loop break</li>
</ol><p>In each iteration, the largest element will be moved to the end.</p><p>Enhanced bubble sort decreases the size of the inner loop by 1 each time, as the last element is now correct.</p><h3 id="merge-sort"><a class="anchor hidden-xs" href="#merge-sort" title="merge-sort"><span class="octicon octicon-link"></span></a>Merge sort</h3><p><strong>Merge sort</strong> A technique for putting data in order by splitting lists into single elements and then merging them back together</p><h4 id="splitting-procedure"><a class="anchor hidden-xs" href="#splitting-procedure" title="splitting-procedure"><span class="octicon octicon-link"></span></a>Splitting procedure</h4><p>Split the array into halves, and repeat on each sub-array until the arrays can no longer be divided into integer parts.</p><h4 id="merging-procedure"><a class="anchor hidden-xs" href="#merging-procedure" title="merging-procedure"><span class="octicon octicon-link"></span></a>Merging procedure</h4><p>Assume that the lists to be merged are already sorted</p><p>Compare the first element of each list, adding the new number to the merged list.<br>
Repeat the process, comparing the first element in each list and placing the lowest item in the merged list</p><h1 id="computational-thinking"><a class="anchor hidden-xs" href="#computational-thinking" title="computational-thinking"><span class="octicon octicon-link"></span></a>Computational thinking</h1><h2 id="abstraction-and-automation"><a class="anchor hidden-xs" href="#abstraction-and-automation" title="abstraction-and-automation"><span class="octicon octicon-link"></span></a>Abstraction and automation</h2><p><strong>Problem solving</strong> The process of finding a solution to real-life problems</p><p><strong>Automation</strong> Creating a computer model of a real-life situation and putting it into action</p><p><strong>Logical reasoning</strong> The process of using a given set of facts to determine whether new facts are true or false</p><p><em>a fact is “a thing that is known or proved to be true.” so the definition above is crap</em></p><p>Automation requires putting models (abstractions of real world objects/phenomena) into action to solve problems:</p><h3 id="abstraction"><a class="anchor hidden-xs" href="#abstraction" title="abstraction"><span class="octicon octicon-link"></span></a>Abstraction</h3><p>The concept of abstraction is to reduce problems to their essential features.<br>
This allows a problem to be viewed from a high level, concentrating on the key aspects of designing a solution whilst ignoring the detail.</p><p>Once a solution has been identified for the current problem, a feature of abstraction is that the abstraction from one problem can be applied to another similar problem which shares the same common features.</p><h4 id="representational-abstraction"><a class="anchor hidden-xs" href="#representational-abstraction" title="representational-abstraction"><span class="octicon octicon-link"></span></a>Representational abstraction</h4><p><strong>Representational abstraction</strong> The process of removing unnecessary details so that only information that is required to solve the problem remains</p><p>This is the process of removing unnecessary details until it is possible to represent the problem in a way that can be solved.</p><h4 id="abstraction-by-generalisation-or-categorisation"><a class="anchor hidden-xs" href="#abstraction-by-generalisation-or-categorisation" title="abstraction-by-generalisation-or-categorisation"><span class="octicon octicon-link"></span></a>Abstraction by generalisation or categorisation</h4><p><strong>Abstraction by generalisation or categorisation</strong> The concept of reducing problems by putting similar aspects of a problem into hierarchical categories</p><p>This process involves identifying common characteristics of representations so that more general representations can be developed.</p><p><strong>Procedural abstraction</strong> The concept that all solutions can be broken down into a series of procedures or subroutines</p><p>At the design stage it is sufficient for the programmer to work out what each procedure will do without defining how it will do it.<br>
The procedure may in turn call other procedures although it does not need to know how these work in order to call them.<br>
This is the basis for top down design.<br>
Other considerations include what event will trigger the procedure, how procedures will link together, including any possible side effects, and how errors will be handled.</p><p><strong>Functional abstraction</strong> Breaking down a complex problem into a series of reusable functions</p><p>Similar to procedural abstraction, functional abstraction focuses on common functions that can be used to solve problems.<br>
Functions are a feature of procedural languages. Functions can be created for any common procedure and functions can be built on top of other functions producing higher levels of abstraction.<br>
All the program needs is for the parameters to be input into the function in order to generate a result.<br>
Using functions reduces complexity as the function only needs to be written once.</p><p><strong>Problem abstraction</strong> The process of reducing a problem down to its simplest components until the underlying processing requirements that solve the problem are identified</p><p>For example, satnavs use vectors and a variation of Dijkstra’s algorithm, neither of which were developed specifically for the satnav, but both of which have been adopted to create the required solution.</p><p><strong>Data abstraction</strong> Hiding how data is represented so that it is easier to build a new kind of data object (e.g. building a stack from an array)</p><h4 id="information-hiding"><a class="anchor hidden-xs" href="#information-hiding" title="information-hiding"><span class="octicon octicon-link"></span></a>Information hiding</h4><p><strong>Information hiding</strong> The process of hiding all details of an object that do not contribute to its essential characteristics</p><p>An example is where a GUI is used.<br>
The complexity of the calculations used to generate the displayed information is hidden. If the method of route calculation was changed, it would not necessarily affect the interface. Information hiding separates the user interface from the actual implementation of the program.</p><h4 id="composition-and-decomposition"><a class="anchor hidden-xs" href="#composition-and-decomposition" title="composition-and-decomposition"><span class="octicon octicon-link"></span></a>Composition and decomposition</h4><p><strong>Composition</strong> Building up a whole system from smaller units</p><p><strong>Decomposition</strong> Breaking down a large task into a series of subtasks</p><h2 id="finite-state-machines"><a class="anchor hidden-xs" href="#finite-state-machines" title="finite-state-machines"><span class="octicon octicon-link"></span></a>Finite state machines</h2><p><strong>Finite state machine</strong> Any device that stores its current status and whose status can change as the result of an input</p><h3 id="state-transition-diagrams"><a class="anchor hidden-xs" href="#state-transition-diagrams" title="state-transition-diagrams"><span class="octicon octicon-link"></span></a>State transition diagrams</h3><p><strong>State transition diagram</strong> A visual representation of a finite state machine using circles and algorithms</p><p><strong>Accepting state</strong> The state that identifies whether an input has been accepted</p><p><strong>State transition table</strong> A tabular representation of a finite state machine, showing inputs, current state, and next state</p><h3 id="finite-state-machines-with-outputs"><a class="anchor hidden-xs" href="#finite-state-machines-with-outputs" title="finite-state-machines-with-outputs"><span class="octicon octicon-link"></span></a>Finite state machines with outputs</h3><p><strong>Mealy machine</strong> A finite state machine which outputs data</p><p><strong>Shift cipher</strong> A simple substitution cipher where the letters are coded by moving a certain amount forwards or backwards in the alphabet</p><h2 id="turing-machines"><a class="anchor hidden-xs" href="#turing-machines" title="turing-machines"><span class="octicon octicon-link"></span></a>Turing machines</h2><p><strong>Turing machine</strong> A theoretical model of computation</p><p>A Turing machine has an infinitely long tape divided into cells, as well as a read write head</p><ul>
<li>Each cell contains a symbol, which can be blank</li>
<li>The read write head can either read what is in the cell or write into the cell. It can also erase the current contents of the cell</li>
<li>The tape can move left or right one cell at a time so that every cell is accessible by the read write head</li>
<li>The machine can halt at any point if it enters a halting state or the entire input has been processed</li>
</ul><p>Turing machines require:</p><ul>
<li>A start state</li>
<li>A halting state</li>
<li>An alphabet that lists acceptable symbols</li>
<li>A transition function indicating what should be written at each cell and whether to move left or right based on the input read</li>
</ul><h3 id="universal-turing-machine"><a class="anchor hidden-xs" href="#universal-turing-machine" title="universal-turing-machine"><span class="octicon octicon-link"></span></a>Universal Turing machine</h3><p><strong>Universal Turing machine</strong> A machine that can simulate a Turing machine by reading a description of the machin along with the input of its own tape</p><p>Rather than defining each individual process within a single machine, the universal machine takes two inputs:</p><ul>
<li>A description of all the individual Turing machines required to perform the calculations</li>
<li>All the inputs required for the calculations</li>
</ul><h2 id="regular-and-context-free-languages"><a class="anchor hidden-xs" href="#regular-and-context-free-languages" title="regular-and-context-free-languages"><span class="octicon octicon-link"></span></a>Regular and context free languages</h2><p><strong>Regular expression</strong> Notation that contains a string of characters that can be matched to the contents of a set</p><p><strong>Regular language</strong> Any language that a finite state machine will accept</p><table>
<thead>
<tr>
<th>Regular expression</th>
<th>Meaning</th>
<th>Strings produced</th>
</tr>
</thead>
<tbody>
<tr>
<td><code>a|b|c</code></td>
<td>a or b or c</td>
<td>a, b, c</td>
</tr>
<tr>
<td><code>abc</code></td>
<td>a and b and c</td>
<td>abc</td>
</tr>
<tr>
<td><code>a*bc</code></td>
<td>zero or more a followed by b and c</td>
<td>bc, abc, aabc, aaabc</td>
</tr>
<tr>
<td><code>(a|b)c</code></td>
<td>a or b and c</td>
<td>ac, bc</td>
</tr>
<tr>
<td><code>a+bc</code></td>
<td>one or more a and b and c</td>
<td>abc, aabc, aaabc</td>
</tr>
<tr>
<td><code>ab?c</code></td>
<td>a and either zero or one b and c</td>
<td>ac, abc</td>
</tr>
</tbody>
</table><h3 id="searching-strings"><a class="anchor hidden-xs" href="#searching-strings" title="searching-strings"><span class="octicon octicon-link"></span></a>Searching strings</h3><table>
<thead>
<tr>
<th>Expression</th>
<th>Definition</th>
<th>Example</th>
</tr>
</thead>
<tbody>
<tr>
<td><code>.</code></td>
<td>Any character</td>
<td>.ole would match mole, hole, ect</td>
</tr>
<tr>
<td><code>[]</code></td>
<td>Matches to a single character within the brackets</td>
<td><code>[mh]ole</code> would match to mole and hole, but not vole</td>
</tr>
<tr>
<td><code>[^]</code></td>
<td>Matches to any character except those in the brackets</td>
<td><code>[^m]ole</code> would match to hole and vole, but not mole</td>
</tr>
<tr>
<td><code>*</code></td>
<td>Matches the preceding characters zero or more times</td>
<td><code>m*ole</code> would match ole, mole, mmole etc</td>
</tr>
</tbody>
</table><h3 id="context-free-languages"><a class="anchor hidden-xs" href="#context-free-languages" title="context-free-languages"><span class="octicon octicon-link"></span></a>Context free languages</h3><p><strong>Context free language</strong> An unambiguous way of describing the syntax of a language useful where the language is complex</p><p>Regular expressions map directly to state transition diagrams.<br>
However, there are situations where the grammar used within a language is too complex to be defined by regular expressions.</p><p>the key problem with regular expressions is that they only work when matching or counting other symbols in a string where there is a finite limit.</p><p>Consider a binary palindrome. It is not possible to create a regular expression that describes the syntax as there is no regular expression that can describe how each letter is used.</p><p>When the counting and matching is infinite, a context free language is needed.<br>
Context free languages can also support notation for recursion and are sometimes a clearer way of defining syntax even where regular expressions can be used.</p><h3 id="backus-naur-form-bnf"><a class="anchor hidden-xs" href="#backus-naur-form-bnf" title="backus-naur-form-bnf"><span class="octicon octicon-link"></span></a>Backus-Naur form (BNF)</h3><p><strong>Backus-Naur Form</strong> A form of notation for describing the syntax used by a programming language</p><p>BNF produces a set of acceptable strings, which effectively describe the rules of the language.<br>
It uses a set of rules that define the language in the format:</p><pre><code>&lt;S&gt; ::= &lt;alternative1&gt; | &lt;alternative2&gt; | &lt;alternative3&gt;

&lt;alternative1&gt; ::= &lt;alternative2&gt; | &lt;alternative4&gt;

&lt;alternative4&gt; ::= terminal
</code></pre><p>BNF works by replacing the symbol on the left with the symbols on the right until the string is defined.<br>
The idea is to keep going until you reach a terminal, which is a rule that cannot be broken down any further.</p><p>In the example above:</p><ul>
<li>Each symbol or element is enclosed within chevrons</li>
<li>The <code>::=</code> symbol means ‘is replace with’ and defines the rule for the symbol</li>
<li>Each symbol needs to be split down further until you reach a terminal</li>
</ul><p>To define integers a BNF expression may look like this:</p><pre><code>&lt;integer&gt; ::= &lt;digit&gt; | &lt;digit&gt; &lt;integer&gt;
&lt;digit&gt; :: = 0|1|2|3|4|5|6|7|8|9
</code></pre><p>This defines an integer as either a digit or a digit followed by another integer.<br>
A digit is defined as the number 0 to 9 and this is a terminal as there is no further rule needed to define digits.</p><p>This expression would be recursive as the integer is defined in terms of itself.</p><p>Consider customer details held in a database:</p><pre><code>&lt;customerdetails&gt; ::= &lt;name&gt; &lt;address&gt;
&lt;name&gt; ::= &lt;title&gt; &lt;firstname&gt; &lt;lastname&gt;
&lt;address&gt; ::= &lt;housenumber&gt; &lt;streetname&gt; &lt;town&gt; &lt;country&gt; &lt;postcode&gt;
...
&lt;housenumber&gt; ::= &lt;integer&gt;
// integer as above
</code></pre><p>This shows how BNF can produce simple rules which can be written as:</p><ul>
<li>Customer dtails must be made up of name and address</li>
<li>Name must be made up of title, first name, and last name</li>
<li>Address must be made up of house number, street name, town, country, and postcode</li>
<li>House number must be made up of an integer</li>
</ul><p>This is only a partial BNF definition and could be continued to further split down the name into a series of acceptable characters, or the postcode into a series of letters and numbers.</p><h3 id="syntax-diagrams"><a class="anchor hidden-xs" href="#syntax-diagrams" title="syntax-diagrams"><span class="octicon octicon-link"></span></a>Syntax diagrams</h3><p>BNF expressions, or any kind of context free language, can be represented as a syntax diagram.</p><ul>
<li>An oval shape represents a terminal element</li>
<li>A rectangular shape represents a non-terminal element and will therefore have another syntax diagram that breaks it down into more detail</li>
<li>A rectangular shape with an arrowed path around it represents a non-terminal element that may be used more than once</li>
</ul><p><strong>Syntax diagram</strong> A method of visualising rules written in a context-free language</p><p>Syntax diagrams are modular so there are likely to be many syntax diagrams required to represent a whole language.<br>
Each has an entry point and exit point to identify the start and end of each particular part.</p><h2 id="maths-for-regular-expressions"><a class="anchor hidden-xs" href="#maths-for-regular-expressions" title="maths-for-regular-expressions"><span class="octicon octicon-link"></span></a>Maths for regular expressions</h2><h3 id="sets"><a class="anchor hidden-xs" href="#sets" title="sets"><span class="octicon octicon-link"></span></a>Sets</h3><p>A set is a collection of unordered values where each value appears only once in the set.<br>
The values in the set are sometimes referred to as elements, objects, or members.</p><p><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-1-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mrow class=&quot;MJX-TeXAtom-ORD&quot;><mi mathvariant=&quot;double-struck&quot;>N</mi></mrow><mo>=</mo><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mn>3</mn><mo>,</mo><mn>4</mn><mo>,</mo><mn>5</mn><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>}</mo><mtext>&amp;#xA0;The natural numbers</mtext></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-1" style="width: 22.646em; display: inline-block;"><span style="display: inline-block; position: relative; width: 18.548em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1018.5em 2.923em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-2"><span class="texatom" id="MathJax-Span-3"><span class="mrow" id="MathJax-Span-4"><span class="mi" id="MathJax-Span-5" style="font-family: STIXGeneral;">ℕ</span></span></span><span class="mo" id="MathJax-Span-6" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mo" id="MathJax-Span-7" style="font-family: STIXGeneral; padding-left: 0.31em;">{</span><span class="mn" id="MathJax-Span-8" style="font-family: STIXGeneral;">0</span><span class="mo" id="MathJax-Span-9" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-10" style="font-family: STIXGeneral; padding-left: 0.207em;">1</span><span class="mo" id="MathJax-Span-11" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-12" style="font-family: STIXGeneral; padding-left: 0.207em;">2</span><span class="mo" id="MathJax-Span-13" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-14" style="font-family: STIXGeneral; padding-left: 0.207em;">3</span><span class="mo" id="MathJax-Span-15" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-16" style="font-family: STIXGeneral; padding-left: 0.207em;">4</span><span class="mo" id="MathJax-Span-17" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-18" style="font-family: STIXGeneral; padding-left: 0.207em;">5</span><span class="mo" id="MathJax-Span-19" style="font-family: STIXGeneral;">,</span><span class="mo" id="MathJax-Span-20" style="font-family: STIXGeneral; padding-left: 0.207em;">.</span><span class="mo" id="MathJax-Span-21" style="font-family: STIXGeneral; padding-left: 0.207em;">.</span><span class="mo" id="MathJax-Span-22" style="font-family: STIXGeneral; padding-left: 0.207em;">.</span><span class="mo" id="MathJax-Span-23" style="font-family: STIXGeneral; padding-left: 0.207em;">}</span><span class="mtext" id="MathJax-Span-24" style="font-family: STIXGeneral;">&nbsp;The natural numbers</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.309em; border-left: 0px solid; width: 0px; height: 1.191em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow class="MJX-TeXAtom-ORD"><mi mathvariant="double-struck">N</mi></mrow><mo>=</mo><mo fence="false" stretchy="false">{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mn>3</mn><mo>,</mo><mn>4</mn><mo>,</mo><mn>5</mn><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo fence="false" stretchy="false">}</mo><mtext>&nbsp;The natural numbers</mtext></math></span></span><script type="math/tex" id="MathJax-Element-1">\mathbb{N} = \{0, 1, 2, 3, 4, 5, ...\} \text{ The natural numbers}</script></span></p><p><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-2-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mrow class=&quot;MJX-TeXAtom-ORD&quot;><mi mathvariant=&quot;double-struck&quot;>Z</mi></mrow><mo>=</mo><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>{</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><mo>&amp;#x2212;</mo><mn>3</mn><mo>,</mo><mo>&amp;#x2212;</mo><mn>2</mn><mo>,</mo><mo>&amp;#x2212;</mo><mn>1</mn><mo>,</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mn>3</mn><mo>,</mo><mo>.</mo><mo>.</mo><mo>,</mo><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>}</mo><mtext>&amp;#xA0;The integers</mtext></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-25" style="width: 24.541em; display: inline-block;"><span style="display: inline-block; position: relative; width: 20.085em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1020.03em 2.923em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-26"><span class="texatom" id="MathJax-Span-27"><span class="mrow" id="MathJax-Span-28"><span class="mi" id="MathJax-Span-29" style="font-family: STIXGeneral;">ℤ</span></span></span><span class="mo" id="MathJax-Span-30" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mo" id="MathJax-Span-31" style="font-family: STIXGeneral; padding-left: 0.31em;">{</span><span class="mo" id="MathJax-Span-32" style="font-family: STIXGeneral;">.</span><span class="mo" id="MathJax-Span-33" style="font-family: STIXGeneral; padding-left: 0.207em;">.</span><span class="mo" id="MathJax-Span-34" style="font-family: STIXGeneral; padding-left: 0.207em;">.</span><span class="mo" id="MathJax-Span-35" style="font-family: STIXGeneral; padding-left: 0.207em;">,</span><span class="mo" id="MathJax-Span-36" style="font-family: STIXGeneral; padding-left: 0.207em;">−</span><span class="mn" id="MathJax-Span-37" style="font-family: STIXGeneral;">3</span><span class="mo" id="MathJax-Span-38" style="font-family: STIXGeneral;">,</span><span class="mo" id="MathJax-Span-39" style="font-family: STIXGeneral; padding-left: 0.207em;">−</span><span class="mn" id="MathJax-Span-40" style="font-family: STIXGeneral;">2</span><span class="mo" id="MathJax-Span-41" style="font-family: STIXGeneral;">,</span><span class="mo" id="MathJax-Span-42" style="font-family: STIXGeneral; padding-left: 0.207em;">−</span><span class="mn" id="MathJax-Span-43" style="font-family: STIXGeneral;">1</span><span class="mo" id="MathJax-Span-44" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-45" style="font-family: STIXGeneral; padding-left: 0.207em;">0</span><span class="mo" id="MathJax-Span-46" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-47" style="font-family: STIXGeneral; padding-left: 0.207em;">1</span><span class="mo" id="MathJax-Span-48" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-49" style="font-family: STIXGeneral; padding-left: 0.207em;">2</span><span class="mo" id="MathJax-Span-50" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-51" style="font-family: STIXGeneral; padding-left: 0.207em;">3</span><span class="mo" id="MathJax-Span-52" style="font-family: STIXGeneral;">,</span><span class="mo" id="MathJax-Span-53" style="font-family: STIXGeneral; padding-left: 0.207em;">.</span><span class="mo" id="MathJax-Span-54" style="font-family: STIXGeneral; padding-left: 0.207em;">.</span><span class="mo" id="MathJax-Span-55" style="font-family: STIXGeneral; padding-left: 0.207em;">,</span><span class="mo" id="MathJax-Span-56" style="font-family: STIXGeneral; padding-left: 0.207em;">}</span><span class="mtext" id="MathJax-Span-57" style="font-family: STIXGeneral;">&nbsp;The integers</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.309em; border-left: 0px solid; width: 0px; height: 1.253em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow class="MJX-TeXAtom-ORD"><mi mathvariant="double-struck">Z</mi></mrow><mo>=</mo><mo fence="false" stretchy="false">{</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><mo>−</mo><mn>3</mn><mo>,</mo><mo>−</mo><mn>2</mn><mo>,</mo><mo>−</mo><mn>1</mn><mo>,</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mn>3</mn><mo>,</mo><mo>.</mo><mo>.</mo><mo>,</mo><mo fence="false" stretchy="false">}</mo><mtext>&nbsp;The integers</mtext></math></span></span><script type="math/tex" id="MathJax-Element-2">\mathbb{Z} = \{..., -3, -2, -1, 0, 1, 2, 3, ..,\} \text{ The integers}</script></span></p><p><strong>Natural number</strong> A positive integer including zero</p><p><strong>Set building</strong> The process of creating sets by describing them using notation rather than listing the elements</p><p><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-3-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>=</mo><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>{</mo><mi>x</mi><mrow class=&quot;MJX-TeXAtom-ORD&quot;><mo stretchy=&quot;false&quot;>|</mo></mrow><mi>x</mi><mo>&amp;#x2208;</mo><mrow class=&quot;MJX-TeXAtom-ORD&quot;><mi mathvariant=&quot;double-struck&quot;>N</mi></mrow><mo>&amp;#x2227;</mo><mi>x</mi><mo>&amp;#x2265;</mo><mn>1</mn><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>}</mo></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-58" style="width: 11.58em; display: inline-block;"><span style="display: inline-block; position: relative; width: 9.48em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1009.38em 2.923em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-59"><span class="mi" id="MathJax-Span-60" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-61" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mo" id="MathJax-Span-62" style="font-family: STIXGeneral; padding-left: 0.31em;">{</span><span class="mi" id="MathJax-Span-63" style="font-family: STIXGeneral; font-style: italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.003em;"></span></span><span class="texatom" id="MathJax-Span-64"><span class="mrow" id="MathJax-Span-65"><span class="mo" id="MathJax-Span-66" style="font-family: STIXVariants;">|</span></span></span><span class="mi" id="MathJax-Span-67" style="font-family: STIXGeneral; font-style: italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.003em;"></span></span><span class="mo" id="MathJax-Span-68" style="font-family: STIXGeneral; padding-left: 0.31em;">∈</span><span class="texatom" id="MathJax-Span-69" style="padding-left: 0.31em;"><span class="mrow" id="MathJax-Span-70"><span class="mi" id="MathJax-Span-71" style="font-family: STIXGeneral;">ℕ</span></span></span><span class="mo" id="MathJax-Span-72" style="font-family: STIXGeneral; padding-left: 0.259em;">∧</span><span class="mi" id="MathJax-Span-73" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.259em;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.003em;"></span></span><span class="mo" id="MathJax-Span-74" style="font-family: STIXGeneral; padding-left: 0.31em;">≥</span><span class="mn" id="MathJax-Span-75" style="font-family: STIXGeneral; padding-left: 0.31em;">1</span><span class="mo" id="MathJax-Span-76" style="font-family: STIXGeneral;">}</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.309em; border-left: 0px solid; width: 0px; height: 1.191em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>=</mo><mo fence="false" stretchy="false">{</mo><mi>x</mi><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false">|</mo></mrow><mi>x</mi><mo>∈</mo><mrow class="MJX-TeXAtom-ORD"><mi mathvariant="double-struck">N</mi></mrow><mo>∧</mo><mi>x</mi><mo>≥</mo><mn>1</mn><mo fence="false" stretchy="false">}</mo></math></span></span><script type="math/tex" id="MathJax-Element-3">A = \{x | x \in \mathbb{N} \land x \geq 1\}</script></span></p><ul>
<li><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-4-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-77" style="width: 0.771em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.617em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1000.57em 2.718em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-78"><span class="mi" id="MathJax-Span-79" style="font-family: STIXGeneral; font-style: italic;">A</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 0.941em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi></math></span></span><script type="math/tex" id="MathJax-Element-4">A</script></span> is the name of the sets</li>
<li>The braces <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-5-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>{</mo><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>}</mo></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-80" style="width: 1.181em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.976em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1000.87em 2.923em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-81"><span class="mo" id="MathJax-Span-82" style="font-family: STIXGeneral;">{</span><span class="mo" id="MathJax-Span-83" style="font-family: STIXGeneral;">}</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.309em; border-left: 0px solid; width: 0px; height: 1.191em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mo fence="false" stretchy="false">{</mo><mo fence="false" stretchy="false">}</mo></math></span></span><script type="math/tex" id="MathJax-Element-5">\{\}</script></span> represent the contents of the set</li>
<li><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-6-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>x</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-84" style="width: 0.566em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.464em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.949em 1000.46em 2.718em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-85"><span class="mi" id="MathJax-Span-86" style="font-family: STIXGeneral; font-style: italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.003em;"></span></span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 0.691em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math></span></span><script type="math/tex" id="MathJax-Element-6">x</script></span> represents the actual values of the set, defined after the pipe <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-7-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mrow class=&quot;MJX-TeXAtom-ORD&quot;><mo stretchy=&quot;false&quot;>|</mo></mrow></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-87" style="width: 0.412em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.31em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1000.21em 2.923em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-88"><span class="texatom" id="MathJax-Span-89"><span class="mrow" id="MathJax-Span-90"><span class="mo" id="MathJax-Span-91" style="font-family: STIXVariants;">|</span></span></span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.309em; border-left: 0px solid; width: 0px; height: 1.191em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false">|</mo></mrow></math></span></span><script type="math/tex" id="MathJax-Element-7">|</script></span></li>
<li>The pipe means such, meaning that the equation after defines the values of <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-8-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>x</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-92" style="width: 0.566em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.464em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.949em 1000.46em 2.718em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-93"><span class="mi" id="MathJax-Span-94" style="font-family: STIXGeneral; font-style: italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.003em;"></span></span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 0.691em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math></span></span><script type="math/tex" id="MathJax-Element-8">x</script></span></li>
<li><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-9-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mo>&amp;#x2208;</mo></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-95" style="width: 0.822em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.669em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.898em 1000.62em 2.769em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-96"><span class="mo" id="MathJax-Span-97" style="font-family: STIXGeneral;">∈</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.122em; border-left: 0px solid; width: 0px; height: 0.816em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mo>∈</mo></math></span></span><script type="math/tex" id="MathJax-Element-9">\in</script></span> means “is a member of”</li>
<li><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-10-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mrow class=&quot;MJX-TeXAtom-ORD&quot;><mi mathvariant=&quot;double-struck&quot;>N</mi></mrow></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-98" style="width: 0.873em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.72em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1000.67em 2.718em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-99"><span class="texatom" id="MathJax-Span-100"><span class="mrow" id="MathJax-Span-101"><span class="mi" id="MathJax-Span-102" style="font-family: STIXGeneral;">ℕ</span></span></span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 0.941em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow class="MJX-TeXAtom-ORD"><mi mathvariant="double-struck">N</mi></mrow></math></span></span><script type="math/tex" id="MathJax-Element-10">\mathbb{N}</script></span> is the natural numbers</li>
<li><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-11-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mo>&amp;#x2227;</mo></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-103" style="width: 0.771em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.617em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.898em 1000.57em 2.769em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-104"><span class="mo" id="MathJax-Span-105" style="font-family: STIXGeneral;">∧</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.122em; border-left: 0px solid; width: 0px; height: 0.816em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mo>∧</mo></math></span></span><script type="math/tex" id="MathJax-Element-11">\land</script></span> means “and”</li>
<li><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-12-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>x</mi><mo>&amp;#x2265;</mo><mn>1</mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-106" style="width: 2.769em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.257em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1002.15em 2.82em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-107"><span class="mi" id="MathJax-Span-108" style="font-family: STIXGeneral; font-style: italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.003em;"></span></span><span class="mo" id="MathJax-Span-109" style="font-family: STIXGeneral; padding-left: 0.31em;">≥</span><span class="mn" id="MathJax-Span-110" style="font-family: STIXGeneral; padding-left: 0.31em;">1</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.184em; border-left: 0px solid; width: 0px; height: 1.066em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi><mo>≥</mo><mn>1</mn></math></span></span><script type="math/tex" id="MathJax-Element-12">x \geq 1</script></span> means that <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-13-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>x</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-111" style="width: 0.566em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.464em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.949em 1000.46em 2.718em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-112"><span class="mi" id="MathJax-Span-113" style="font-family: STIXGeneral; font-style: italic;">x<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.003em;"></span></span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 0.691em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math></span></span><script type="math/tex" id="MathJax-Element-13">x</script></span> must satisfy this inequality to be part of the set</li>
</ul><p><strong>Member</strong> A value or element that belongs to a set</p><h4 id="the-binary-set"><a class="anchor hidden-xs" href="#the-binary-set" title="the-binary-set"><span class="octicon octicon-link"></span></a>The binary set</h4><p>The binary set is usually denoted <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-14-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi mathvariant=&quot;normal&quot;>&amp;#x03A3;</mi><mo>=</mo><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>}</mo></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-114" style="width: 5.33em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.357em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1004.25em 2.923em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-115"><span class="mi" id="MathJax-Span-116" style="font-family: STIXGeneral;">Σ</span><span class="mo" id="MathJax-Span-117" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mo" id="MathJax-Span-118" style="font-family: STIXGeneral; padding-left: 0.31em;">{</span><span class="mn" id="MathJax-Span-119" style="font-family: STIXGeneral;">0</span><span class="mo" id="MathJax-Span-120" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-121" style="font-family: STIXGeneral; padding-left: 0.207em;">1</span><span class="mo" id="MathJax-Span-122" style="font-family: STIXGeneral;">}</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.309em; border-left: 0px solid; width: 0px; height: 1.191em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">Σ</mi><mo>=</mo><mo fence="false" stretchy="false">{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo fence="false" stretchy="false">}</mo></math></span></span><script type="math/tex" id="MathJax-Element-14">\Sigma = \{0, 1\}</script></span></p><p>This shows that the elements of the set of binary values are <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-15-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mn>0</mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-123" style="width: 0.669em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.515em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1000.51em 2.718em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-124"><span class="mn" id="MathJax-Span-125" style="font-family: STIXGeneral;">0</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 0.941em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>0</mn></math></span></span><script type="math/tex" id="MathJax-Element-15">0</script></span> or <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-16-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mn>1</mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-126" style="width: 0.669em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.515em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1000.41em 2.718em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-127"><span class="mn" id="MathJax-Span-128" style="font-family: STIXGeneral;">1</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 0.941em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn></math></span></span><script type="math/tex" id="MathJax-Element-16">1</script></span>.<br>
to build a set of all binary strings containing two bits, you would use <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-17-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><msup><mi mathvariant=&quot;normal&quot;>&amp;#x03A3;</mi><mn>2</mn></msup></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-129" style="width: 1.335em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.078em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.232em 1001.08em 2.359em -999.997em); top: -2.2em; left: 0em;"><span class="mrow" id="MathJax-Span-130"><span class="msubsup" id="MathJax-Span-131"><span style="display: inline-block; position: relative; width: 1.078em; height: 0px;"><span style="position: absolute; clip: rect(3.179em 1000.62em 4.152em -999.997em); top: -3.993em; left: 0em;"><span class="mi" id="MathJax-Span-132" style="font-family: STIXGeneral;">Σ</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -4.352em; left: 0.617em;"><span class="mn" id="MathJax-Span-133" style="font-size: 70.7%; font-family: STIXGeneral;">2</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.205em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 1.128em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi mathvariant="normal">Σ</mi><mn>2</mn></msup></math></span></span><script type="math/tex" id="MathJax-Element-17">\Sigma^2</script></span> where the <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-18-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><msup><mrow class=&quot;MJX-TeXAtom-ORD&quot;></mrow><mn>2</mn></msup></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-134" style="width: 0.515em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.412em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.232em 1000.41em 2.359em -999.997em); top: -2.2em; left: 0em;"><span class="mrow" id="MathJax-Span-135"><span class="msubsup" id="MathJax-Span-136"><span style="display: inline-block; position: relative; width: 0.412em; height: 0px;"><span style="position: absolute; clip: rect(3.845em 1000em 4.152em -999.997em); top: -3.993em; left: 0em;"><span class="texatom" id="MathJax-Span-137"><span class="mrow" id="MathJax-Span-138"></span></span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -4.352em; left: 0em;"><span class="mn" id="MathJax-Span-139" style="font-size: 70.7%; font-family: STIXGeneral;">2</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.205em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 1.128em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mrow class="MJX-TeXAtom-ORD"></mrow><mn>2</mn></msup></math></span></span><script type="math/tex" id="MathJax-Element-18">{}^2</script></span> indicates two bits.</p><p><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-19-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><msup><mi mathvariant=&quot;normal&quot;>&amp;#x03A3;</mi><mn>2</mn></msup><mo>=</mo><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>{</mo><mn>00</mn><mo>,</mo><mn>01</mn><mo>,</mo><mn>01</mn><mo>,</mo><mn>10</mn><mo>,</mo><mn>11</mn><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>}</mo></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-140" style="width: 12.4em; display: inline-block;"><span style="display: inline-block; position: relative; width: 10.146em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.591em 1010.04em 2.923em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-141"><span class="msubsup" id="MathJax-Span-142"><span style="display: inline-block; position: relative; width: 1.078em; height: 0px;"><span style="position: absolute; clip: rect(3.179em 1000.62em 4.152em -999.997em); top: -3.993em; left: 0em;"><span class="mi" id="MathJax-Span-143" style="font-family: STIXGeneral;">Σ</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -4.352em; left: 0.617em;"><span class="mn" id="MathJax-Span-144" style="font-size: 70.7%; font-family: STIXGeneral;">2</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span class="mo" id="MathJax-Span-145" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mo" id="MathJax-Span-146" style="font-family: STIXGeneral; padding-left: 0.31em;">{</span><span class="mn" id="MathJax-Span-147" style="font-family: STIXGeneral;">00</span><span class="mo" id="MathJax-Span-148" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-149" style="font-family: STIXGeneral; padding-left: 0.207em;">01</span><span class="mo" id="MathJax-Span-150" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-151" style="font-family: STIXGeneral; padding-left: 0.207em;">01</span><span class="mo" id="MathJax-Span-152" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-153" style="font-family: STIXGeneral; padding-left: 0.207em;">10</span><span class="mo" id="MathJax-Span-154" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-155" style="font-family: STIXGeneral; padding-left: 0.207em;">11</span><span class="mo" id="MathJax-Span-156" style="font-family: STIXGeneral;">}</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.309em; border-left: 0px solid; width: 0px; height: 1.378em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi mathvariant="normal">Σ</mi><mn>2</mn></msup><mo>=</mo><mo fence="false" stretchy="false">{</mo><mn>00</mn><mo>,</mo><mn>01</mn><mo>,</mo><mn>01</mn><mo>,</mo><mn>10</mn><mo>,</mo><mn>11</mn><mo fence="false" stretchy="false">}</mo></math></span></span><script type="math/tex" id="MathJax-Element-19">\Sigma^2 = \{00, 01, 01, 10, 11\}</script></span></p><p>In some cases the number of elements may be infinite.</p><p><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-20-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>=</mo><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>{</mo><msup><mn>0</mn><mi>n</mi></msup><msup><mn>1</mn><mi>n</mi></msup><mrow class=&quot;MJX-TeXAtom-ORD&quot;><mo stretchy=&quot;false&quot;>|</mo></mrow><mi>n</mi><mo>&amp;#x2265;</mo><mn>1</mn><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>}</mo></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-157" style="width: 8.968em; display: inline-block;"><span style="display: inline-block; position: relative; width: 7.328em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.693em 1007.23em 2.923em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-158"><span class="mi" id="MathJax-Span-159" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-160" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mo" id="MathJax-Span-161" style="font-family: STIXGeneral; padding-left: 0.31em;">{</span><span class="msubsup" id="MathJax-Span-162"><span style="display: inline-block; position: relative; width: 0.925em; height: 0px;"><span style="position: absolute; clip: rect(3.179em 1000.46em 4.152em -999.997em); top: -3.993em; left: 0em;"><span class="mn" id="MathJax-Span-163" style="font-family: STIXGeneral;">0</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -4.403em; left: 0.515em;"><span class="mi" id="MathJax-Span-164" style="font-size: 70.7%; font-family: STIXGeneral; font-style: italic;">n</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span class="msubsup" id="MathJax-Span-165"><span style="display: inline-block; position: relative; width: 0.925em; height: 0px;"><span style="position: absolute; clip: rect(3.179em 1000.41em 4.152em -999.997em); top: -3.993em; left: 0em;"><span class="mn" id="MathJax-Span-166" style="font-family: STIXGeneral;">1</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -4.403em; left: 0.515em;"><span class="mi" id="MathJax-Span-167" style="font-size: 70.7%; font-family: STIXGeneral; font-style: italic;">n</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span class="texatom" id="MathJax-Span-168"><span class="mrow" id="MathJax-Span-169"><span class="mo" id="MathJax-Span-170" style="font-family: STIXVariants;">|</span></span></span><span class="mi" id="MathJax-Span-171" style="font-family: STIXGeneral; font-style: italic;">n</span><span class="mo" id="MathJax-Span-172" style="font-family: STIXGeneral; padding-left: 0.31em;">≥</span><span class="mn" id="MathJax-Span-173" style="font-family: STIXGeneral; padding-left: 0.31em;">1</span><span class="mo" id="MathJax-Span-174" style="font-family: STIXGeneral;">}</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.309em; border-left: 0px solid; width: 0px; height: 1.253em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>=</mo><mo fence="false" stretchy="false">{</mo><msup><mn>0</mn><mi>n</mi></msup><msup><mn>1</mn><mi>n</mi></msup><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false">|</mo></mrow><mi>n</mi><mo>≥</mo><mn>1</mn><mo fence="false" stretchy="false">}</mo></math></span></span><script type="math/tex" id="MathJax-Element-20">A = \{0^n 1^n | n \geq 1 \}</script></span> would produce the set <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-21-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>{</mo><mn>01</mn><mo>,</mo><mn>0011</mn><mo>,</mo><mn>000111</mn><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>}</mo></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-175" style="width: 11.837em; display: inline-block;"><span style="display: inline-block; position: relative; width: 9.685em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1009.58em 2.923em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-176"><span class="mo" id="MathJax-Span-177" style="font-family: STIXGeneral;">{</span><span class="mn" id="MathJax-Span-178" style="font-family: STIXGeneral;">01</span><span class="mo" id="MathJax-Span-179" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-180" style="font-family: STIXGeneral; padding-left: 0.207em;">0011</span><span class="mo" id="MathJax-Span-181" style="font-family: STIXGeneral;">,</span><span class="mn" id="MathJax-Span-182" style="font-family: STIXGeneral; padding-left: 0.207em;">000111</span><span class="mo" id="MathJax-Span-183" style="font-family: STIXGeneral;">,</span><span class="mo" id="MathJax-Span-184" style="font-family: STIXGeneral; padding-left: 0.207em;">.</span><span class="mo" id="MathJax-Span-185" style="font-family: STIXGeneral; padding-left: 0.207em;">.</span><span class="mo" id="MathJax-Span-186" style="font-family: STIXGeneral; padding-left: 0.207em;">.</span><span class="mo" id="MathJax-Span-187" style="font-family: STIXGeneral; padding-left: 0.207em;">}</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.309em; border-left: 0px solid; width: 0px; height: 1.191em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mo fence="false" stretchy="false">{</mo><mn>01</mn><mo>,</mo><mn>0011</mn><mo>,</mo><mn>000111</mn><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo fence="false" stretchy="false">}</mo></math></span></span><script type="math/tex" id="MathJax-Element-21">\{01, 0011, 000111, ... \}</script></span> representing all binary strings with an equal number of 0s and 1s, with the 0s preceding the 1s.</p><h4 id="representing-a-set-in-a-programming-language"><a class="anchor hidden-xs" href="#representing-a-set-in-a-programming-language" title="representing-a-set-in-a-programming-language"><span class="octicon octicon-link"></span></a>Representing a set in a programming language</h4><p>Many programming languages have built in set-building routines.</p><ul>
<li>In Python <code>a = set([0, 1, 2, 3])</code> produces a set, as does <code>a = set(x**2 for x in [1, 2, 3])</code></li>
<li>In Haskell <code>[0..100]</code> produces a list containing the values 0 to 100, and <code>[x*2 | x &lt;- [0..100]]</code> produces a list of the doubles of these numbers</li>
<li>In C# <code>IEnumerable&lt;int&gt; numbers = Enumerable.Range(0, 9)</code> produces the integers 0 to 9. <code>var events = from num in numbers where num%2 == 0 select num;</code> would then extract the even numbers</li>
</ul><h4 id="the-empty-set"><a class="anchor hidden-xs" href="#the-empty-set" title="the-empty-set"><span class="octicon octicon-link"></span></a>The empty set</h4><p>The empty set is represented as either <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-22-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>{</mo><mo fence=&quot;false&quot; stretchy=&quot;false&quot;>}</mo></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-188" style="width: 1.181em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.976em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1000.87em 2.923em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-189"><span class="mo" id="MathJax-Span-190" style="font-family: STIXGeneral;">{</span><span class="mo" id="MathJax-Span-191" style="font-family: STIXGeneral;">}</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.309em; border-left: 0px solid; width: 0px; height: 1.191em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mo fence="false" stretchy="false">{</mo><mo fence="false" stretchy="false">}</mo></math></span></span><script type="math/tex" id="MathJax-Element-22">\{\}</script></span> or <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-23-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi mathvariant=&quot;normal&quot;>&amp;#x2205;</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-192" style="width: 0.669em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.515em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.693em 1000.51em 2.769em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-193"><span class="mi" id="MathJax-Span-194" style="font-family: STIXVariants;">∅</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.122em; border-left: 0px solid; width: 0px; height: 1.128em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">∅</mi></math></span></span><script type="math/tex" id="MathJax-Element-23">\emptyset</script></span></p><p><strong>Empty set</strong> The set that contains no values</p><h4 id="finite-and-infinite-sets"><a class="anchor hidden-xs" href="#finite-and-infinite-sets" title="finite-and-infinite-sets"><span class="octicon octicon-link"></span></a>Finite and infinite sets</h4><p>When a set is finite, it has cardinality which means that it can be counted using natural numbers.<br>
It can also be referred to as a countable set.</p><p>The cardinality of the set is the number of elements in the set.</p><p><strong>Countably infinite set</strong> Sets where the elements can be put into a one-to-one correspondence with the set of natural numbers</p><p><strong>Cartesian product <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-24-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>&amp;#x00D7;</mo><mi>B</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-195" style="width: 2.871em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.359em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1002.36em 2.718em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-196"><span class="mi" id="MathJax-Span-197" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-198" style="font-family: STIXGeneral; padding-left: 0.259em;">×</span><span class="mi" id="MathJax-Span-199" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.259em;">B</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 1.003em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>×</mo><mi>B</mi></math></span></span><script type="math/tex" id="MathJax-Element-24">A\times B</script></span></strong> Combining the elements of two or more sets to create a set of ordered pairs</p><p><strong>Union <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-25-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>&amp;#x222A;</mo><mi>B</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-200" style="width: 2.871em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.359em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1002.36em 2.769em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-201"><span class="mi" id="MathJax-Span-202" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-203" style="font-family: STIXGeneral; padding-left: 0.259em;">∪</span><span class="mi" id="MathJax-Span-204" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.259em;">B</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.122em; border-left: 0px solid; width: 0px; height: 1.003em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>∪</mo><mi>B</mi></math></span></span><script type="math/tex" id="MathJax-Element-25">A\cup B</script></span></strong> When two sets are joined and all of the elements of both sets are included in the joined set</p><p><strong>Intersection <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-26-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>&amp;#x2229;</mo><mi>B</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-205" style="width: 2.871em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.359em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1002.36em 2.769em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-206"><span class="mi" id="MathJax-Span-207" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-208" style="font-family: STIXGeneral; padding-left: 0.259em;">∩</span><span class="mi" id="MathJax-Span-209" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.259em;">B</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.122em; border-left: 0px solid; width: 0px; height: 1.003em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>∩</mo><mi>B</mi></math></span></span><script type="math/tex" id="MathJax-Element-26">A\cap B</script></span></strong> Describes which elements are common to both sets when the two sets are joined</p><p><strong>Difference <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-27-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>&amp;#x2296;</mo><mi>B</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-210" style="width: 3.128em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.564em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1002.56em 2.82em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-211"><span class="mi" id="MathJax-Span-212" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-213" style="font-family: STIXGeneral; padding-left: 0.259em;">⊖</span><span class="mi" id="MathJax-Span-214" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.259em;">B</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.184em; border-left: 0px solid; width: 0px; height: 1.066em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>⊖</mo><mi>B</mi></math></span></span><script type="math/tex" id="MathJax-Element-27">A\ominus B</script></span> or <span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-28-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mi mathvariant=&quot;normal&quot;>&amp;#x0394;</mi><mi>B</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-215" style="width: 2.41em; display: inline-block;"><span style="display: inline-block; position: relative; width: 1.949em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1001.95em 2.718em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-216"><span class="mi" id="MathJax-Span-217" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mi" id="MathJax-Span-218" style="font-family: STIXGeneral;">Δ</span><span class="mi" id="MathJax-Span-219" style="font-family: STIXGeneral; font-style: italic;">B</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 0.941em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mi mathvariant="normal">Δ</mi><mi>B</mi></math></span></span><script type="math/tex" id="MathJax-Element-28">A \Delta B</script></span></strong> Describes which elements differ when two sets are joined together</p><h4 id="subsets"><a class="anchor hidden-xs" href="#subsets" title="subsets"><span class="octicon octicon-link"></span></a>Subsets</h4><p>Where all the elements of one set are also contained within another set, it is said to be a subset.</p><p><strong>Subset</strong>  set where the elements of one are entirely contained within the other. This can include two sets that are exactly the same</p><p><strong>Proper subset</strong> Where one st is wholly contained within another and the other set has additional elements</p><h2 id="big-o-notation-and-classification-of-algorithms"><a class="anchor hidden-xs" href="#big-o-notation-and-classification-of-algorithms" title="big-o-notation-and-classification-of-algorithms"><span class="octicon octicon-link"></span></a>Big O notation and classification of algorithms</h2><h3 id="functions"><a class="anchor hidden-xs" href="#functions" title="functions"><span class="octicon octicon-link"></span></a>Functions</h3><p><strong>Function</strong> Relates each element of a set with the element of another set</p><p><strong>Domain</strong> All the values that may be input to a mathematical function</p><p><strong>Codomain</strong> All the values that may be output from a mathematical function</p><h3 id="big-o-notation"><a class="anchor hidden-xs" href="#big-o-notation" title="big-o-notation"><span class="octicon octicon-link"></span></a>Big O notation</h3><p>This notation is used to classify the time and space complexity of an algorithm.<br>
It considers the worst-case scenario.</p><p><strong>Constant time</strong> Where the time taken to run an algorithm does not vary with the input size</p><p><strong>Linear time</strong> When the time taken to run an algorithm increases in direct proportion with the input size</p><p><strong>Exponential time</strong> When the time taken to run an algorithm increases as an exponential function of the number of inputs</p><p><strong>Logarithmic time</strong> Where the time taken to run an algorithm increases or decreases in line with a logarithm</p><h3 id="tractable-and-intractable-problems"><a class="anchor hidden-xs" href="#tractable-and-intractable-problems" title="tractable-and-intractable-problems"><span class="octicon octicon-link"></span></a>Tractable and intractable problems</h3><p><strong>Tractable problem</strong> A problem that can be solved in an acceptable amount of time</p><p><strong>Intractable problem</strong> A problem that cannot be solved in an acceptable time frame</p><p><strong>Heuristic</strong> A method for producing a ‘rule of thumb’ to produce an acceptable solution to intractable problems</p><h3 id="unsolvable-problems"><a class="anchor hidden-xs" href="#unsolvable-problems" title="unsolvable-problems"><span class="octicon octicon-link"></span></a>Unsolvable problems</h3><p><strong>Unsolvable problem</strong> a problem that it has been proved cannot be solved on a computer</p><p><strong>Halting problem</strong> An example of an unsolvable problem where it is impossible to write a program that can work out whether another problem will halt given a particular input</p><p>The Halting problem demonstrates that there are some problems that cannot be solved by a computer</p><h1 id="beginning-of-paper-2-content"><a class="anchor hidden-xs" href="#beginning-of-paper-2-content" title="beginning-of-paper-2-content"><span class="octicon octicon-link"></span></a>Beginning of Paper 2 content</h1><h1 id="data-representation"><a class="anchor hidden-xs" href="#data-representation" title="data-representation"><span class="octicon octicon-link"></span></a>Data representation</h1><h2 id="number-systems"><a class="anchor hidden-xs" href="#number-systems" title="number-systems"><span class="octicon octicon-link"></span></a>Number systems</h2><p><strong>Natural numbers</strong> A positive integer including zero</p><p><strong>Integer</strong> Any whole positive or negative number including zero</p><p><strong>Rational numbers</strong> Any number that can be expressed as a ratio of integers</p><p><strong>Irrational number</strong> A number that cannot be represented as a fraction or ratio as the decimal form will contain an infinite number of values</p><p><strong>Real numbers</strong> Any positive or negative number with or without a fractional part</p><p><strong>Ordinal number</strong> A number used to identify position relative to other numbers</p><p><strong>Cardinal number</strong> A number that identifies the size of something</p><p><strong>Well ordered set</strong> A group of related numbers with a defined order</p><p>Ordinal numbers are used to identify the position of data within an ordered set.</p><h2 id="number-bases"><a class="anchor hidden-xs" href="#number-bases" title="number-bases"><span class="octicon octicon-link"></span></a>Number bases</h2><p><strong>Number base</strong> The number of digits available within a particular number system</p><p><strong>Bit</strong> A single binary digit from a binary number</p><p><strong>Byte</strong> A group of bits, usually 8</p><p><strong>Unit</strong> The grouping together of bits or bytes to form larger blocks of measurement</p><h2 id="the-binary-number-system"><a class="anchor hidden-xs" href="#the-binary-number-system" title="the-binary-number-system"><span class="octicon octicon-link"></span></a>The binary number system</h2><h3 id="adding-unsigned-binary-integers"><a class="anchor hidden-xs" href="#adding-unsigned-binary-integers" title="adding-unsigned-binary-integers"><span class="octicon octicon-link"></span></a>Adding unsigned binary integers</h3><p><strong>Unsigned binary</strong> Binary that represents positive numbers only</p><p>To add two numbers together in binary, first line up the numbers.<br>
Add the columns starting from the right hand side, carrying 11 to the next column,</p><h3 id="multiplying-unsigned-binary-integers"><a class="anchor hidden-xs" href="#multiplying-unsigned-binary-integers" title="multiplying-unsigned-binary-integers"><span class="octicon octicon-link"></span></a>Multiplying unsigned binary integers</h3><p>To multiply in binary, you multiple the first number be each of the digits of the second number in turn, starting from the right hand side.<br>
This means that you are multiplying each each digit by 0 or 1.<br>
You then do the same for the next digit, shifting your answers to the left as you would in decimal multiplication.</p><p>You can then carry out a binary addition to find the final answer.</p><pre><code>  11011 *
     11
------------
  11011 (1 * 11011)
 110110 (1 * 110110)
------------
1010001
------------
 1111
</code></pre><h3 id="two’s-complement"><a class="anchor hidden-xs" href="#two’s-complement" title="two’s-complement"><span class="octicon octicon-link"></span></a>Two’s complement</h3><p><strong>Two’s complement</strong> A method of working with signed binary values</p><p>Two’s complement is a method used to represent signed integers in binary form. This means that it can be used to represent positive and negative integers.</p><p>The first digit in a two’s complement integer has a negative value, and all of the other digits have positive values.</p><h4 id="adding-and-subtracting-using-two’s-complement"><a class="anchor hidden-xs" href="#adding-and-subtracting-using-two’s-complement" title="adding-and-subtracting-using-two’s-complement"><span class="octicon octicon-link"></span></a>Adding and subtracting using two’s complement</h4><p>Adding numbers together using two’s complement is the same as adding numbers together in decimal. You add up the total and carry values across to the next column.</p><p>In order to carry out subtractions, the method used is to convert the number to be subtracted to a negative value, and then to add it.</p><h3 id="fixed-point-numbers"><a class="anchor hidden-xs" href="#fixed-point-numbers" title="fixed-point-numbers"><span class="octicon octicon-link"></span></a>Fixed point numbers</h3><p>In order to represent real decimal numbers, fixed point representation can be used. In the same way that decimal has a decimal point, binary has a binary point. The numbers after the binary point represent fractions.</p><p><strong>Fixed point</strong> Where the decimal/binary point is fixed within a number</p><p>The binary point is not actually stored in the 8 bit code, its position is fixed by the programmer.</p><h3 id="floating-point-numbers"><a class="anchor hidden-xs" href="#floating-point-numbers" title="floating-point-numbers"><span class="octicon octicon-link"></span></a>Floating point numbers</h3><p><strong>Floating point</strong> Where the decimal/binary point can move within a number</p><p>In floating point, the binary point can be moved depending on the number that you are trying to represent. It ‘floats’ left to right rather than being in a fixed position.<br>
Floating point extends the fixed point technique.</p><p>A floating point number is made up of two parts, the mantissa and the exponent.<br>
In binary, the exponent and mantissa are used to allow the binary point to float. They are each two’s complement values.</p><p>To calculate the value of a floating point value, we first calculate the value of the mantissa and then multiply it by 2 to the power of the exponent.</p><p>This is equivalent to finding the value of the exponent, ‘floating’ the binary point to n places to the right if the exponent is n, and n places to the left if the exponent is -n, before evaluating the binary as a fixed point value.</p><h3 id="underflow-and-overflow"><a class="anchor hidden-xs" href="#underflow-and-overflow" title="underflow-and-overflow"><span class="octicon octicon-link"></span></a>Underflow and overflow</h3><p><strong>Overflow</strong> When a number is too large to be represented with the number of bits allocated</p><p><strong>Underflow</strong> When a number is too small to be represented with the number of bits allocated</p><h3 id="normalisation-and-precision"><a class="anchor hidden-xs" href="#normalisation-and-precision" title="normalisation-and-precision"><span class="octicon octicon-link"></span></a>Normalisation and precision</h3><p><strong>Normalisation</strong> A process for adjusting numbers onto a common scale</p><p><strong>Precision</strong> How close a value is to the true value</p><p>In order to be normalised, the first bit of the mantissa, after the binary point, should always be 1 for positive integers, or 0 for negative numbers and the bit before the binary point should be the opposite.</p><p>A normalised positive floating point number must start 0.1 and a normalised negative floating point number must start 1.0</p><h4 id="example"><a class="anchor hidden-xs" href="#example" title="example"><span class="octicon octicon-link"></span></a>Example</h4><p>Consider the number 108. The 8 bit binary equivalent of which is 01101100.</p><ul>
<li>The normalised mantissa would be 0.1101100</li>
<li>The binary point will have to be moved seven places to the right to convert it back to the original number</li>
<li>The exponent is therefore 7</li>
<li>The two’s complement value for 7 is 0111</li>
<li>Therefore the normalised representation of 108 is 0.11011000111</li>
</ul><h3 id="rounding-errors"><a class="anchor hidden-xs" href="#rounding-errors" title="rounding-errors"><span class="octicon octicon-link"></span></a>Rounding errors</h3><p>When working with decimal numbers, we are used to the idea of rounding numbers up or down. As a consequence, we will get rounding errors.</p><p>A similar phenomenon occurs with binary representation. If you attempt to convert 0.1 into binary you will find that you get a recurring number, so it is not possible to exactly represent it.</p><p>If you try to represent 1.95 with 8 bits and a fixed point 1.1111010 gives 1.953125 while 1.1111001 gives 1.943125. With 8 bits the nearest value is 0.003125 out.<br>
Extending the number of bits would allow for an answer closer to 1.95</p><h3 id="absolute-and-relative-errors"><a class="anchor hidden-xs" href="#absolute-and-relative-errors" title="absolute-and-relative-errors"><span class="octicon octicon-link"></span></a>Absolute and relative errors</h3><p>There are two main methods for calculating the degree of error in number that we use within a program.<br>
The absolute error is the actual numerical difference between the answer and the approximation.</p><p>The relative error is the absolute error divided by the true value.</p><h2 id="coding-systems"><a class="anchor hidden-xs" href="#coding-systems" title="coding-systems"><span class="octicon octicon-link"></span></a>Coding systems</h2><p><strong>Character code</strong> A binary representation of a particular letter, number, or special character</p><h3 id="ascii-and-unicode"><a class="anchor hidden-xs" href="#ascii-and-unicode" title="ascii-and-unicode"><span class="octicon octicon-link"></span></a>ASCII and Unicode</h3><p>The ASCII (American Standard Code for Information Interchange) was agreed upon. 7 bits of each byte are used to represent 128 characters, while the 8th bit can be used for checking.</p><p>ASCII has limitations:</p><ul>
<li>256 characters are not sufficient to represent all of the possible characters, numbers, and symbols</li>
<li>It was initially developed in English and therefore did not represent all of the other languages and scripts in the world</li>
<li>Widespread use of the web made it more important to have a universal international coding system</li>
<li>The range of platforms and programs has increased dramatically with more developers from around the world using a much wider range of characters</li>
</ul><p><strong>Unicode</strong> A standard binary coding system that has superseded ASCII</p><p>Unicode is being constantly developed and updated to include more languages and characters from around the world.</p><h3 id="error-checking-and-correction"><a class="anchor hidden-xs" href="#error-checking-and-correction" title="error-checking-and-correction"><span class="octicon octicon-link"></span></a>Error checking and correction</h3><p><strong>Parity bit</strong> A method of checking binary codes by counting the number of 0s or 1s in the code</p><h4 id="even-and-odd-parity"><a class="anchor hidden-xs" href="#even-and-odd-parity" title="even-and-odd-parity"><span class="octicon octicon-link"></span></a>Even and odd parity</h4><p>One method for detecting errors is to count the number of ones in each byte before the data is sent to see whether there is an even or odd number. At the receiving end the code can be checked to see whether the number is still odd or even.</p><ul>
<li>Even parity: The number of 1s in the code are counted. The parity bit is set to make the total number of 1s even</li>
<li>Odd parity: The number of 1s in the code are counted. The parity bit is set to make the total number of 1s odd</li>
</ul><h4 id="majority-voting"><a class="anchor hidden-xs" href="#majority-voting" title="majority-voting"><span class="octicon octicon-link"></span></a>Majority voting</h4><p><strong>Majority voting</strong> A method of checking for errors by producing the same data several times and checking it is the same each time</p><p>When the data is checked, you would expect to see patterns of three bits.<br>
When there is a discrepancy, you can use majority voting to see which bit occurs most frequently.</p><p>This principle can be applied on a larger scale. The Columbia space shuttle had at least four computers processing the same data and checking each other’s results.</p><h4 id="check-digits"><a class="anchor hidden-xs" href="#check-digits" title="check-digits"><span class="octicon octicon-link"></span></a>Check digits</h4><p><strong>Check digit</strong> A digit added to the end of binary data to check the data is accurate</p><p>Check digits are a common way of checking data, often when they are being entered into a computer.<br>
For example, check digits are used on the barcodes printed on goods at a supermarket.<br>
Like a parity bit, a check digit is a value that is added to the end of a number to try to ensure that the number is not corrupted.</p><p>The check digit is created by taking the digits that make up the number itself and using them in some way to create a single digit. The simplest, but most error prone is to add the digits of the number together and keep on adding the digits until you have only a single digit remaining.</p><p>The problem with this system is that if two numbers are transposed, the check digits will be the same. In order to overcome this, each number in the pattern is given a weighting. A common method for calculating a check digit is known as modulo 11.</p><pre><code>Original number 2 3 0 4 5
Weighting       6 5 4 3 2
Multiply        12 15 0 12 10
Add             12+15+0+12+10 = 49
Divide by 11 49/11 = 4R5
Subtract the remainder from 11 11 - 5 = 6
The check digit is 6 -&gt; 230456
</code></pre><h3 id="bit-mapped-graphics"><a class="anchor hidden-xs" href="#bit-mapped-graphics" title="bit-mapped-graphics"><span class="octicon octicon-link"></span></a>Bit mapped graphics</h3><p><strong>Bit mapped graphic</strong> An image made up of individual pixels</p><p><strong>Pixel</strong> An individual picture element</p><p><strong>Colour depth</strong> The number of bits or bytes allocated to represent the colour of a pixel in a bit-mapped graphic</p><p>Bitmaps may also contain metadata. Metadata is normally found at the beginning of the file in a header</p><h3 id="vector-graphics"><a class="anchor hidden-xs" href="#vector-graphics" title="vector-graphics"><span class="octicon octicon-link"></span></a>Vector graphics</h3><p>Vector graphics are created using objects and coordinates. A vector is a measure of quantity and direction.<br>
To rescale a vector image requires an adjustment of the coordinates. Therefore, the graphics are being controlled mathematically rather than being completely regenerated as with a bit map.<br>
An image created on the screen will be made up of lines and the scale and position of the lines will be adjusted as the screen display changes to create an image</p><p><strong>Vector graphic</strong> An image made up of objects and coordinates</p><p>Vector graphics have numerous advantages</p><ul>
<li>Vector graphics can be scaled perfectly</li>
<li>Two and three dimensional animations can be created using vector graphics</li>
<li>Less data is used for simple images</li>
</ul><p>The properties of each geometric object in the image are stored in a list.<br>
These attributes may include:</p><ul>
<li>Dimensions</li>
<li>Colours</li>
<li>Position</li>
<li>Line sizes</li>
<li>Text for text elements</li>
</ul><h3 id="analogue-and-digital-signals"><a class="anchor hidden-xs" href="#analogue-and-digital-signals" title="analogue-and-digital-signals"><span class="octicon octicon-link"></span></a>Analogue and digital signals</h3><p>Analogue data are data that are infinitely variable and are often represented in the form of a wave.</p><p>Digital data are often represented as discrete waves.</p><h4 id="analogue-to-digital-conversions"><a class="anchor hidden-xs" href="#analogue-to-digital-conversions" title="analogue-to-digital-conversions"><span class="octicon octicon-link"></span></a>Analogue to digital conversions</h4><p>The problem arises when we need to input analogue data into the computer or when we want to output digital data from the computer in analogue form.<br>
In order to do this, a converter is need.</p><p>One example of an analogue to digital converter (ADC) is a microphone. The microphone inputs sound in the form of changes in air pressure and then converts them into electrical signals.</p><p>Another example is a MIDI device for an acoustic guitar. This device fits beneath the strings on the guitar and when the strings are played they generate an analogue sound wave.<br>
The sound waves are picked up and converted to digital form.</p><p>MIDI uses event messages to control various properties of the sound.<br>
These messages are typically encoded in binary and provide communication between MIDI devices or between MIDI device and the processor.<br>
For a MIDI keyboard, an event message may contain data on:</p><ul>
<li>When to play a note</li>
<li>When to stop playing the note</li>
<li>Timing a note to play with other notes or sounds</li>
<li>Timing a note to play with other MIDI enabled devices</li>
<li>What pitch a note is</li>
<li>How loud to play the note</li>
<li>What effect to use when playing the note</li>
</ul><p>MIDI files have numerous advantages over other digital audio formats:</p><ul>
<li>MIDI files tend to be much smaller. This means that they require less memory and also load faster</li>
<li>MIDI files are completely editable as individual instruments can be selected and modified</li>
<li>MIDI supports a very wide range of instruments providing more choices for music production</li>
<li>MIDI files can produce a very high quality and authentic reproduction of the instrument</li>
</ul><h3 id="sound-sampling-and-synthesis"><a class="anchor hidden-xs" href="#sound-sampling-and-synthesis" title="sound-sampling-and-synthesis"><span class="octicon octicon-link"></span></a>Sound sampling and synthesis</h3><p>Sampling is the process of converting analogue sound waves into digital form to create what is commonly known as digitised or digital sound.<br>
This is sometimes referred to as analogue to digital conversion.<br>
An analogue sound wave is infinitely variable so in order to store this digitally, a series of reads at fixed intervals are taken from the wave in order to create the discrete data values that are defining a feature of binary data.<br>
These reading are then stored as binary codes.<br>
This is called sampling because you do not record every single change in amplitude of the waveform.</p><h4 id="sampling-an-analogue-wave"><a class="anchor hidden-xs" href="#sampling-an-analogue-wave" title="sampling-an-analogue-wave"><span class="octicon octicon-link"></span></a>Sampling an analogue wave</h4><p>The amplitude of the wave is only recorded at the point where each sample is taken. Other variations in the amplitude are not recorded.<br>
Therefore, to create an exact replica of the analogue sound would require a sample to be taken every time the amplitude of the wave changed even by a small amount.<br>
However, the human ear doesn’t notice very small changes, so sound can be faithfully created with fewer samples.<br>
Taking more samples allow more accurate reproduction of the original analogue sound.</p><h3 id="data-compression"><a class="anchor hidden-xs" href="#data-compression" title="data-compression"><span class="octicon octicon-link"></span></a>Data compression</h3><p><strong>Compression</strong> The process of reducing the number of bits required to represent data</p><p>Compression is the process of encoding with fewer bits, so that the files take up less memory</p><h4 id="lossless-compression"><a class="anchor hidden-xs" href="#lossless-compression" title="lossless-compression"><span class="octicon octicon-link"></span></a>Lossless compression</h4><p><strong>Run length encoding</strong> A method of compressing data by eliminating repeated data</p><p><strong>Dictionary based encoding</strong> A method of compressing text files</p><p>Lossless compression maintains all of the original data.</p><h4 id="lossy-compression"><a class="anchor hidden-xs" href="#lossy-compression" title="lossy-compression"><span class="octicon octicon-link"></span></a>Lossy compression</h4><p>There are cases where lossless compression still results in a large file as there is a limit to how small it can get, while still maintaining accuracy.</p><p>JPEG compression works by breaking an image into blocks of 8x8 pixels. In each block, the data is converted into frequencies. Some frequencies are considered more important than others.</p><p>In a high frequency image the human eye will not notice slight changes to large blocks of similar colours, however it will notice changes in areas with high contrast. These contrasting areas must be maintained.</p><h2 id="encryption"><a class="anchor hidden-xs" href="#encryption" title="encryption"><span class="octicon octicon-link"></span></a>Encryption</h2><p>Encryption is the process of scrambling data so that it cannot be understood by a third party unless they know the encryption method and key used.<br>
Decryption is the process of turning the scrambled data back into data that can be understood. Data is encrypted before it is transmitted and decrypted when it is received.</p><p><strong>Encryption</strong> The process of turning plaintext into scrambled ciphertext, which can only be understood if it is decrypted</p><p><strong>Decryption</strong> The process of deciphering encrypted data or messages</p><p><strong>Plaintext</strong> Data in human-readable form</p><p><strong>Ciphertext</strong> Data that has been encrypted</p><p><strong>Caeser cipher</strong> A substitution cipher where one character of plaintext is substituted for another, which becomes the ciphertext</p><p><strong>Vernam cipher</strong> A method of encryption that uses a one time pad to create ciphertext that is mathematically impossible to decrypt without the key</p><p><strong>Transposition cipher</strong> A method of encryption where the characters are rearranged to form an anagram</p><p><strong>Key</strong> THe data that is used to encrypt and decrypt the data</p><p><strong>Substitution cipher</strong> A method of encryption where one character is substituted for another to create ciphertext</p><p><strong>Polyalphabetic</strong> Using more than one alphabet</p><h3 id="frequency-analysis"><a class="anchor hidden-xs" href="#frequency-analysis" title="frequency-analysis"><span class="octicon octicon-link"></span></a>Frequency analysis</h3><p><strong>Frequency analysis</strong> The study of how often different letters or phrases are used</p><p>The Caesar cipher can be easily broken as certain letters are more frequently used than others and certain combinations of letters are also common.</p><h3 id="transposition-cipher"><a class="anchor hidden-xs" href="#transposition-cipher" title="transposition-cipher"><span class="octicon octicon-link"></span></a>Transposition cipher</h3><p>The letters of the message are transposed or rearranged to form an anagram. You must rearrange the letters according to a set pattern to make it possible to decrypt the message. One way of doing this is the railfence method where the message is split across several lines.</p><p><strong>Railfence cipher</strong> A type of transposition cipher that encodes the message by splitting it over rows</p><p><strong>Route cipher</strong> A type of transposition cipher that encodes the message by placing it into a grid</p><h3 id="vernam-cipher"><a class="anchor hidden-xs" href="#vernam-cipher" title="vernam-cipher"><span class="octicon octicon-link"></span></a>Vernam cipher</h3><p>The Vernam cipher is an example of a class of encryption techniques known as one-time pad techniques. The key that is used is a sequence of letters that should be as long as the plaintext that is being encoded. The key can be recorded on a pad, although in the Vernam case the key was written on a punched tape for input into the telex device.</p><p><strong>One time pad</strong> A key that is only used once to decrypt a message and is then discarded</p><p><strong>Baudot code</strong> A 5 digit character code that predates ASCII and Unicode</p><p>To encrypt a message, each character in the plaintext is combined with the character at the corresponding position in the key by converting the corresponding plaintext and key characters into a binary code, and using a logical XOR on these binary representations.</p><p>The ciphertext can be decrypted  using the same operation with the same key.</p><h3 id="computational-security"><a class="anchor hidden-xs" href="#computational-security" title="computational-security"><span class="octicon octicon-link"></span></a>Computational security</h3><p><strong>Computational security</strong> A concept of how secure data encryption is</p><p><strong>Computational hardness</strong> The degree of difficulty in cracking a cipher</p><p>Computational security means that cryptographers need to be aware of the ways in which their encryption could be cracked.</p><ul>
<li>Identifying commonly used techniques such as substitution or transposition, and the patterns that they create</li>
<li>Reverse engineering. The process of going step by step to work out how something has been put together</li>
<li>Dictionary attacks. The process of using a dictionary that contains common words and phrases. After each attempt to decrypt the text is made, the text can be compared to the dictionary to see if it matches</li>
<li>Brute force. Similar to a dictionary attack, but it takes much longer as it considers every permutation of characters that can be created</li>
</ul><h1 id="computer-systems"><a class="anchor hidden-xs" href="#computer-systems" title="computer-systems"><span class="octicon octicon-link"></span></a>Computer systems</h1><h2 id="hardware-and-software"><a class="anchor hidden-xs" href="#hardware-and-software" title="hardware-and-software"><span class="octicon octicon-link"></span></a>Hardware and software</h2><p><strong>Hardware</strong> A generic term for the physical parts of the computer, both internal and external</p><p><strong>Software</strong> A generic term for any program that can be run on a computer</p><h3 id="hardware"><a class="anchor hidden-xs" href="#hardware" title="hardware"><span class="octicon octicon-link"></span></a>Hardware</h3><p>External components (peripherals) are the components of the hardware such as the monitor, keyboard, mouse, and printer. The external components are used either to input or output data. Some storage devices are also external, such as flash drives.</p><h3 id="software"><a class="anchor hidden-xs" href="#software" title="software"><span class="octicon octicon-link"></span></a>Software</h3><h4 id="application-software"><a class="anchor hidden-xs" href="#application-software" title="application-software"><span class="octicon octicon-link"></span></a>Application software</h4><p>Application software refers to all of the programs that the user uses in order to complete a particular task.</p><p><strong>Application software</strong> Programs that perform specific tasks that would need doing even if computers did not exist. e.g. text editing</p><h4 id="system-software"><a class="anchor hidden-xs" href="#system-software" title="system-software"><span class="octicon octicon-link"></span></a>System software</h4><p>System software covers a range of programs that are concerned with the technical aspects of setting up and running the computer.</p><p>There are four main types of system software. Utility programs, library programs, translators, compilers and interpreters, and operating system software.</p><h5 id="utility-programs"><a class="anchor hidden-xs" href="#utility-programs" title="utility-programs"><span class="octicon octicon-link"></span></a>Utility programs</h5><p>This covers software that is written to carry out certain housekeeping tasks on the computer.<br>
They are normally supplied with the operating system and include</p><p><strong>Utility programs</strong> Programs that perform specific common tasks related to running the computer e.g. zipping files</p><h4 id="library-programs"><a class="anchor hidden-xs" href="#library-programs" title="library-programs"><span class="octicon octicon-link"></span></a>Library programs</h4><p>Library programs are utility programs in that they are written to carry out common tasks. The word library indicates that there will be a number of software tools available to the users of the system.</p><p><strong>Library programs</strong> Code, data, and resources that can be called by other programs</p><p>Whereas some utility programs are non-essential, library programs tend to be critical for the applications for which they were built.</p><h2 id="classification-of-programming-languages-and-translation"><a class="anchor hidden-xs" href="#classification-of-programming-languages-and-translation" title="classification-of-programming-languages-and-translation"><span class="octicon octicon-link"></span></a>Classification of programming languages and translation</h2><p><strong>Translators</strong> Software that converts programming language instructions into machine code</p><p><strong>Compiler</strong> A program that translates a high-level language into machine code by translating all of the code</p><p><strong>Assembler</strong> A program that translates a program written in assembly language into machine code</p><p><strong>Interpreter</strong> A program for translating a high-level language by reading each statement in the source code and immediately performing the action</p><p><strong>Operating system software</strong> A suite of programs designed to control the operations of the computer</p><p><strong>Virtual machine</strong> The concept that all of the complexities of using a computer are hidden from the user and other software by the operating system</p><h3 id="operating-system-software"><a class="anchor hidden-xs" href="#operating-system-software" title="operating-system-software"><span class="octicon octicon-link"></span></a>Operating system software</h3><p>The operating system carries out many tasks, such as:</p><ul>
<li>Controlling the start-up configuration of the computer</li>
<li>Recognising that a mouse button has been pressed and deciding what action to take</li>
<li>Sending signals to the hard disk controller, telling it what program to transfer to memory</li>
<li>Deciding which sections of memory to allocate to the program you are intending to use and manages memory to ensure all of the programs you want to run are allocated the space they need</li>
<li>Attempting to cope with errors as and when they occur</li>
<li>Making sure the computer shuts down properly</li>
<li>Controlling print queues</li>
<li>Managing the users on a network</li>
</ul><h3 id="resource-management"><a class="anchor hidden-xs" href="#resource-management" title="resource-management"><span class="octicon octicon-link"></span></a>Resource management</h3><p><strong>Resource management</strong> How an operating system manages hardware and software to optimise the performance of the computer</p><p><strong>Processor</strong> A device that carries out computation on data by following instructions, in order to produce an output</p><p><strong>Scheduling</strong> A technique to ensure that different users or different programs are able to work on the same computer system at the same time</p><p>The simplest way that an operating system can schedule access to the processor is to allocate each task a time slice. This means that each task is given an equal amount of processor time.<br>
Time slicing is a crude system because a praticular task might not need all or even any of its alloted time slice with the processor.</p><h3 id="managing-input-output-devices"><a class="anchor hidden-xs" href="#managing-input-output-devices" title="managing-input-output-devices"><span class="octicon octicon-link"></span></a>Managing input output devices</h3><p>The operating system controls the way in which the various input and output devices are allocated, controlled, and used by the programs that are using them, such as:</p><ul>
<li>Allocating print jobs to printers</li>
<li>Rendering the windows, frames, and dialog boxes to the screen</li>
<li>Controlling the read-write access to the hard disk</li>
</ul><p>Accessing some devices is a relatively slow process compared to the speed at which the processor can handle requests. At the same time there are likely to be competing request where several processes are waiting for the same device. Rather than waiting for each process to end before it can continue, the OS can effectively create a queue of commands that are waiting for the device and then handle each request in sequence or based on a priority.</p><p>Every input/output device has a device driver, which is a piece of software that enables the device to communicate with the OS. Device drivers are often built in to the OS or installed when new devices are attached. When the OS starts up it loads the various driver for all of the input/output devices it detects.</p><h3 id="memory-management"><a class="anchor hidden-xs" href="#memory-management" title="memory-management"><span class="octicon octicon-link"></span></a>Memory management</h3><p><strong>Memory management</strong> How the operating system uses RAM to optimise the performance of the computer</p><p>The operating system controls the use of main memory by creating a memory map, which shows which blocks of memory have been allocated to each astk. Tis way an operating system can control more than one task in the RAM at any one time.<br>
The amount of memory needed by each task is dependent on the size of the program itself, the variables that will be needed and any files that might be generated by the task, but it is up to the operating system to decide how much space can be allocated.</p><h4 id="virtual-memory-and-paging"><a class="anchor hidden-xs" href="#virtual-memory-and-paging" title="virtual-memory-and-paging"><span class="octicon octicon-link"></span></a>Virtual memory and paging</h4><p>In some cases, the application or file being accessed is too large to fit in RAM. In this case a process called virtual memory can be used.<br>
This involves using secondary storage such as a hard disk to store code or files that would normally be held in RAM. The operating system then uses part of the hard disk as if it is part of the RAM.<br>
An alternative method is to hold a kernel or central block of the code in RAM. Other sections of code known as pages are loaded from the secondary storage as and when they are needed. Using this method allows very large applications to run in a small section of RAM. This in turn frees up memory for other applications to use.</p><h3 id="file-management"><a class="anchor hidden-xs" href="#file-management" title="file-management"><span class="octicon octicon-link"></span></a>File management</h3><p><strong>File management</strong> How an operating system stores and retrieves files</p><h2 id="boolean-algebra"><a class="anchor hidden-xs" href="#boolean-algebra" title="boolean-algebra"><span class="octicon octicon-link"></span></a>Boolean algebra</h2><p><strong>Boolean expression</strong> An expression made up of Boolean operations</p><h3 id="simplifying-boolean-expressions"><a class="anchor hidden-xs" href="#simplifying-boolean-expressions" title="simplifying-boolean-expressions"><span class="octicon octicon-link"></span></a>Simplifying boolean expressions</h3><table>
<thead>
<tr>
<th>Identity name</th>
<th>AND Form</th>
<th>OR Form</th>
</tr>
</thead>
<tbody>
<tr>
<td>Identity</td>
<td><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-29-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mn>.1</mn><mo>=</mo><mi>A</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-220" style="width: 3.998em; display: inline-block;"><span style="display: inline-block; position: relative; width: 3.281em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1003.23em 2.718em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-221"><span class="mi" id="MathJax-Span-222" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mn" id="MathJax-Span-223" style="font-family: STIXGeneral;">.1</span><span class="mo" id="MathJax-Span-224" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mi" id="MathJax-Span-225" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.31em;">A</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 0.941em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mn>.1</mn><mo>=</mo><mi>A</mi></math></span></span><script type="math/tex" id="MathJax-Element-29">A.1 = A</script></span></td>
<td><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-30-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>+</mo><mn>0</mn><mo>=</mo><mi>A</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-226" style="width: 5.126em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.203em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1004.15em 2.769em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-227"><span class="mi" id="MathJax-Span-228" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-229" style="font-family: STIXGeneral; padding-left: 0.259em;">+</span><span class="mn" id="MathJax-Span-230" style="font-family: STIXGeneral; padding-left: 0.259em;">0</span><span class="mo" id="MathJax-Span-231" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mi" id="MathJax-Span-232" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.31em;">A</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.122em; border-left: 0px solid; width: 0px; height: 1.003em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>+</mo><mn>0</mn><mo>=</mo><mi>A</mi></math></span></span><script type="math/tex" id="MathJax-Element-30">A+0 = A</script></span></td>
</tr>
<tr>
<td>Null/Dominance</td>
<td><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-31-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mn>.0</mn><mo>=</mo><mn>0</mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-233" style="width: 3.896em; display: inline-block;"><span style="display: inline-block; position: relative; width: 3.179em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1003.18em 2.718em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-234"><span class="mi" id="MathJax-Span-235" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mn" id="MathJax-Span-236" style="font-family: STIXGeneral;">.0</span><span class="mo" id="MathJax-Span-237" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mn" id="MathJax-Span-238" style="font-family: STIXGeneral; padding-left: 0.31em;">0</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 0.941em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mn>.0</mn><mo>=</mo><mn>0</mn></math></span></span><script type="math/tex" id="MathJax-Element-31">A.0 = 0</script></span></td>
<td><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-32-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>+</mo><mn>1</mn><mo>=</mo><mn>1</mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-239" style="width: 5.023em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.101em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1004em 2.769em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-240"><span class="mi" id="MathJax-Span-241" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-242" style="font-family: STIXGeneral; padding-left: 0.259em;">+</span><span class="mn" id="MathJax-Span-243" style="font-family: STIXGeneral; padding-left: 0.259em;">1</span><span class="mo" id="MathJax-Span-244" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mn" id="MathJax-Span-245" style="font-family: STIXGeneral; padding-left: 0.31em;">1</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.122em; border-left: 0px solid; width: 0px; height: 1.003em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>+</mo><mn>1</mn><mo>=</mo><mn>1</mn></math></span></span><script type="math/tex" id="MathJax-Element-32">A+1 = 1</script></span></td>
</tr>
<tr>
<td>Idempotence</td>
<td><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-33-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>.</mo><mi>A</mi><mo>=</mo><mi>A</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-246" style="width: 4.408em; display: inline-block;"><span style="display: inline-block; position: relative; width: 3.589em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1003.54em 2.718em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-247"><span class="mi" id="MathJax-Span-248" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-249" style="font-family: STIXGeneral;">.</span><span class="mi" id="MathJax-Span-250" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.207em;">A</span><span class="mo" id="MathJax-Span-251" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mi" id="MathJax-Span-252" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.31em;">A</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 0.941em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>.</mo><mi>A</mi><mo>=</mo><mi>A</mi></math></span></span><script type="math/tex" id="MathJax-Element-33">A.A = A</script></span></td>
<td><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-34-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>+</mo><mi>A</mi><mo>=</mo><mi>A</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-253" style="width: 5.279em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.306em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1004.25em 2.769em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-254"><span class="mi" id="MathJax-Span-255" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-256" style="font-family: STIXGeneral; padding-left: 0.259em;">+</span><span class="mi" id="MathJax-Span-257" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.259em;">A</span><span class="mo" id="MathJax-Span-258" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mi" id="MathJax-Span-259" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.31em;">A</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.122em; border-left: 0px solid; width: 0px; height: 1.003em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>+</mo><mi>A</mi><mo>=</mo><mi>A</mi></math></span></span><script type="math/tex" id="MathJax-Element-34">A+A = A</script></span></td>
</tr>
<tr>
<td>Inverse</td>
<td><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-35-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>.</mo><mover><mi>A</mi><mo accent=&quot;false&quot;>&amp;#x00AF;</mo></mover><mo>=</mo><mn>0</mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-260" style="width: 4.255em; display: inline-block;"><span style="display: inline-block; position: relative; width: 3.486em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.386em 1003.49em 2.718em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-261"><span class="mi" id="MathJax-Span-262" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-263" style="font-family: STIXGeneral;">.</span><span class="munderover" id="MathJax-Span-264" style="padding-left: 0.207em;"><span style="display: inline-block; position: relative; width: 0.617em; height: 0px;"><span style="position: absolute; clip: rect(3.179em 1000.57em 4.152em -999.997em); top: -3.993em; left: 0.003em;"><span class="mi" id="MathJax-Span-265" style="font-family: STIXGeneral; font-style: italic;">A</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; clip: rect(3.537em 1000.62em 3.998em -999.997em); top: -4.711em; left: 0em;"><span class="mo" id="MathJax-Span-266" style=""><span style="display: inline-block; position: relative; width: 0.617em; height: 0px;"><span style="position: absolute; top: -3.993em; left: 0em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.412em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.105em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.259em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span class="mo" id="MathJax-Span-267" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mn" id="MathJax-Span-268" style="font-family: STIXGeneral; padding-left: 0.31em;">0</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 1.441em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>.</mo><mover><mi>A</mi><mo accent="false">¯</mo></mover><mo>=</mo><mn>0</mn></math></span></span><script type="math/tex" id="MathJax-Element-35">A.\overline{A} = 0</script></span></td>
<td><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-36-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>+</mo><mover><mi>A</mi><mo accent=&quot;false&quot;>&amp;#x00AF;</mo></mover><mo>=</mo><mn>1</mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-269" style="width: 5.126em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.203em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.386em 1004.1em 2.769em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-270"><span class="mi" id="MathJax-Span-271" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-272" style="font-family: STIXGeneral; padding-left: 0.259em;">+</span><span class="munderover" id="MathJax-Span-273" style="padding-left: 0.259em;"><span style="display: inline-block; position: relative; width: 0.617em; height: 0px;"><span style="position: absolute; clip: rect(3.179em 1000.57em 4.152em -999.997em); top: -3.993em; left: 0.003em;"><span class="mi" id="MathJax-Span-274" style="font-family: STIXGeneral; font-style: italic;">A</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; clip: rect(3.537em 1000.62em 3.998em -999.997em); top: -4.711em; left: 0em;"><span class="mo" id="MathJax-Span-275" style=""><span style="display: inline-block; position: relative; width: 0.617em; height: 0px;"><span style="position: absolute; top: -3.993em; left: 0em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.412em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.105em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.259em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span class="mo" id="MathJax-Span-276" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mn" id="MathJax-Span-277" style="font-family: STIXGeneral; padding-left: 0.31em;">1</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.122em; border-left: 0px solid; width: 0px; height: 1.441em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>+</mo><mover><mi>A</mi><mo accent="false">¯</mo></mover><mo>=</mo><mn>1</mn></math></span></span><script type="math/tex" id="MathJax-Element-36">A+\overline{A} = 1</script></span></td>
</tr>
<tr>
<td>Commutative</td>
<td><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-37-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>.</mo><mi>B</mi><mo>=</mo><mi>B</mi><mo>.</mo><mi>A</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-278" style="width: 5.689em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.664em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1004.61em 2.718em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-279"><span class="mi" id="MathJax-Span-280" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-281" style="font-family: STIXGeneral;">.</span><span class="mi" id="MathJax-Span-282" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.207em;">B</span><span class="mo" id="MathJax-Span-283" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mi" id="MathJax-Span-284" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.31em;">B</span><span class="mo" id="MathJax-Span-285" style="font-family: STIXGeneral;">.</span><span class="mi" id="MathJax-Span-286" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.207em;">A</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 0.941em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>.</mo><mi>B</mi><mo>=</mo><mi>B</mi><mo>.</mo><mi>A</mi></math></span></span><script type="math/tex" id="MathJax-Element-37">A.B = B.A</script></span></td>
<td><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-38-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>+</mo><mi>B</mi><mo>=</mo><mi>B</mi><mo>+</mo><mi>A</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-287" style="width: 7.533em; display: inline-block;"><span style="display: inline-block; position: relative; width: 6.15em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1006.1em 2.769em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-288"><span class="mi" id="MathJax-Span-289" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-290" style="font-family: STIXGeneral; padding-left: 0.259em;">+</span><span class="mi" id="MathJax-Span-291" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.259em;">B</span><span class="mo" id="MathJax-Span-292" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mi" id="MathJax-Span-293" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.31em;">B</span><span class="mo" id="MathJax-Span-294" style="font-family: STIXGeneral; padding-left: 0.259em;">+</span><span class="mi" id="MathJax-Span-295" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.259em;">A</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.122em; border-left: 0px solid; width: 0px; height: 1.003em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>+</mo><mi>B</mi><mo>=</mo><mi>B</mi><mo>+</mo><mi>A</mi></math></span></span><script type="math/tex" id="MathJax-Element-38">A+B = B+A</script></span></td>
</tr>
<tr>
<td>Associative</td>
<td><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-39-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mo stretchy=&quot;false&quot;>(</mo><mi>A</mi><mo>.</mo><mi>B</mi><mo stretchy=&quot;false&quot;>)</mo><mo>.</mo><mi>C</mi><mo>=</mo><mi>A</mi><mo>.</mo><mo stretchy=&quot;false&quot;>(</mo><mi>B</mi><mo>.</mo><mi>C</mi><mo stretchy=&quot;false&quot;>)</mo></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-296" style="width: 10.095em; display: inline-block;"><span style="display: inline-block; position: relative; width: 8.251em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1008.2em 2.871em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-297"><span class="mo" id="MathJax-Span-298" style="font-family: STIXGeneral;">(</span><span class="mi" id="MathJax-Span-299" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-300" style="font-family: STIXGeneral;">.</span><span class="mi" id="MathJax-Span-301" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.207em;">B</span><span class="mo" id="MathJax-Span-302" style="font-family: STIXGeneral;">)</span><span class="mo" id="MathJax-Span-303" style="font-family: STIXGeneral;">.</span><span class="mi" id="MathJax-Span-304" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.207em;">C<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.003em;"></span></span><span class="mo" id="MathJax-Span-305" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mi" id="MathJax-Span-306" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.31em;">A</span><span class="mo" id="MathJax-Span-307" style="font-family: STIXGeneral;">.</span><span class="mo" id="MathJax-Span-308" style="font-family: STIXGeneral; padding-left: 0.207em;">(</span><span class="mi" id="MathJax-Span-309" style="font-family: STIXGeneral; font-style: italic;">B</span><span class="mo" id="MathJax-Span-310" style="font-family: STIXGeneral;">.</span><span class="mi" id="MathJax-Span-311" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.207em;">C<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.003em;"></span></span><span class="mo" id="MathJax-Span-312" style="font-family: STIXGeneral;">)</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.247em; border-left: 0px solid; width: 0px; height: 1.191em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mo stretchy="false">(</mo><mi>A</mi><mo>.</mo><mi>B</mi><mo stretchy="false">)</mo><mo>.</mo><mi>C</mi><mo>=</mo><mi>A</mi><mo>.</mo><mo stretchy="false">(</mo><mi>B</mi><mo>.</mo><mi>C</mi><mo stretchy="false">)</mo></math></span></span><script type="math/tex" id="MathJax-Element-39">(A.B).C = A.(B.C)</script></span></td>
<td><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-40-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mo stretchy=&quot;false&quot;>(</mo><mi>A</mi><mo>+</mo><mi>B</mi><mo stretchy=&quot;false&quot;>)</mo><mo>+</mo><mi>C</mi><mo>=</mo><mi>A</mi><mo>+</mo><mo stretchy=&quot;false&quot;>(</mo><mi>B</mi><mo>+</mo><mi>C</mi><mo stretchy=&quot;false&quot;>)</mo></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-313" style="width: 13.681em; display: inline-block;"><span style="display: inline-block; position: relative; width: 11.222em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1011.17em 2.871em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-314"><span class="mo" id="MathJax-Span-315" style="font-family: STIXGeneral;">(</span><span class="mi" id="MathJax-Span-316" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-317" style="font-family: STIXGeneral; padding-left: 0.259em;">+</span><span class="mi" id="MathJax-Span-318" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.259em;">B</span><span class="mo" id="MathJax-Span-319" style="font-family: STIXGeneral;">)</span><span class="mo" id="MathJax-Span-320" style="font-family: STIXGeneral; padding-left: 0.259em;">+</span><span class="mi" id="MathJax-Span-321" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.259em;">C<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.003em;"></span></span><span class="mo" id="MathJax-Span-322" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mi" id="MathJax-Span-323" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.31em;">A</span><span class="mo" id="MathJax-Span-324" style="font-family: STIXGeneral; padding-left: 0.259em;">+</span><span class="mo" id="MathJax-Span-325" style="font-family: STIXGeneral; padding-left: 0.259em;">(</span><span class="mi" id="MathJax-Span-326" style="font-family: STIXGeneral; font-style: italic;">B</span><span class="mo" id="MathJax-Span-327" style="font-family: STIXGeneral; padding-left: 0.259em;">+</span><span class="mi" id="MathJax-Span-328" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.259em;">C<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.003em;"></span></span><span class="mo" id="MathJax-Span-329" style="font-family: STIXGeneral;">)</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.247em; border-left: 0px solid; width: 0px; height: 1.191em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mo stretchy="false">(</mo><mi>A</mi><mo>+</mo><mi>B</mi><mo stretchy="false">)</mo><mo>+</mo><mi>C</mi><mo>=</mo><mi>A</mi><mo>+</mo><mo stretchy="false">(</mo><mi>B</mi><mo>+</mo><mi>C</mi><mo stretchy="false">)</mo></math></span></span><script type="math/tex" id="MathJax-Element-40">(A+B)+C = A+(B+C)</script></span></td>
</tr>
<tr>
<td>Absorption</td>
<td><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-41-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>.</mo><mo stretchy=&quot;false&quot;>(</mo><mi>A</mi><mo>+</mo><mi>B</mi><mo stretchy=&quot;false&quot;>)</mo><mo>=</mo><mi>A</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-330" style="width: 7.38em; display: inline-block;"><span style="display: inline-block; position: relative; width: 6.048em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1006em 2.871em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-331"><span class="mi" id="MathJax-Span-332" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-333" style="font-family: STIXGeneral;">.</span><span class="mo" id="MathJax-Span-334" style="font-family: STIXGeneral; padding-left: 0.207em;">(</span><span class="mi" id="MathJax-Span-335" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-336" style="font-family: STIXGeneral; padding-left: 0.259em;">+</span><span class="mi" id="MathJax-Span-337" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.259em;">B</span><span class="mo" id="MathJax-Span-338" style="font-family: STIXGeneral;">)</span><span class="mo" id="MathJax-Span-339" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mi" id="MathJax-Span-340" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.31em;">A</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.247em; border-left: 0px solid; width: 0px; height: 1.191em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>.</mo><mo stretchy="false">(</mo><mi>A</mi><mo>+</mo><mi>B</mi><mo stretchy="false">)</mo><mo>=</mo><mi>A</mi></math></span></span><script type="math/tex" id="MathJax-Element-41">A.(A+B) = A</script></span></td>
<td><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-42-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>A</mi><mo>+</mo><mi>A</mi><mo>.</mo><mi>B</mi><mo>=</mo><mi>A</mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-341" style="width: 6.56em; display: inline-block;"><span style="display: inline-block; position: relative; width: 5.382em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.744em 1005.33em 2.769em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-342"><span class="mi" id="MathJax-Span-343" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-344" style="font-family: STIXGeneral; padding-left: 0.259em;">+</span><span class="mi" id="MathJax-Span-345" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.259em;">A</span><span class="mo" id="MathJax-Span-346" style="font-family: STIXGeneral;">.</span><span class="mi" id="MathJax-Span-347" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.207em;">B</span><span class="mo" id="MathJax-Span-348" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="mi" id="MathJax-Span-349" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.31em;">A</span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.122em; border-left: 0px solid; width: 0px; height: 1.003em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi><mo>+</mo><mi>A</mi><mo>.</mo><mi>B</mi><mo>=</mo><mi>A</mi></math></span></span><script type="math/tex" id="MathJax-Element-42">A+A.B = A</script></span></td>
</tr>
</tbody>
</table><h3 id="de-morgan’s-law"><a class="anchor hidden-xs" href="#de-morgan’s-law" title="de-morgan’s-law"><span class="octicon octicon-link"></span></a>De Morgan’s Law</h3><p><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-43-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mover><mrow><mi>A</mi><mo>.</mo><mi>B</mi></mrow><mo accent=&quot;false&quot;>&amp;#x00AF;</mo></mover><mo>=</mo><mover><mi>A</mi><mo accent=&quot;false&quot;>&amp;#x00AF;</mo></mover><mo>+</mo><mover><mi>B</mi><mo accent=&quot;false&quot;>&amp;#x00AF;</mo></mover></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-350" style="width: 6.662em; display: inline-block;"><span style="display: inline-block; position: relative; width: 5.433em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.386em 1005.43em 2.769em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-351"><span class="munderover" id="MathJax-Span-352"><span style="display: inline-block; position: relative; width: 1.693em; height: 0px;"><span style="position: absolute; clip: rect(3.179em 1001.64em 4.152em -999.997em); top: -3.993em; left: 0.003em;"><span class="mrow" id="MathJax-Span-353"><span class="mi" id="MathJax-Span-354" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-355" style="font-family: STIXGeneral;">.</span><span class="mi" id="MathJax-Span-356" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.207em;">B</span></span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; clip: rect(3.537em 1001.69em 3.998em -999.997em); top: -4.711em; left: 0em;"><span class="mo" id="MathJax-Span-357" style=""><span style="display: inline-block; position: relative; width: 1.693em; height: 0px;"><span style="position: absolute; top: -3.993em; left: 0em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 1.488em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.156em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.31em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.464em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.669em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.822em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.976em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 1.13em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 1.335em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span class="mo" id="MathJax-Span-358" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="munderover" id="MathJax-Span-359" style="padding-left: 0.31em;"><span style="display: inline-block; position: relative; width: 0.617em; height: 0px;"><span style="position: absolute; clip: rect(3.179em 1000.57em 4.152em -999.997em); top: -3.993em; left: 0.003em;"><span class="mi" id="MathJax-Span-360" style="font-family: STIXGeneral; font-style: italic;">A</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; clip: rect(3.537em 1000.62em 3.998em -999.997em); top: -4.711em; left: 0em;"><span class="mo" id="MathJax-Span-361" style=""><span style="display: inline-block; position: relative; width: 0.617em; height: 0px;"><span style="position: absolute; top: -3.993em; left: 0em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.412em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.105em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.259em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span class="mo" id="MathJax-Span-362" style="font-family: STIXGeneral; padding-left: 0.259em;">+</span><span class="munderover" id="MathJax-Span-363" style="padding-left: 0.259em;"><span style="display: inline-block; position: relative; width: 0.617em; height: 0px;"><span style="position: absolute; clip: rect(3.179em 1000.57em 4.152em -999.997em); top: -3.993em; left: 0.003em;"><span class="mi" id="MathJax-Span-364" style="font-family: STIXGeneral; font-style: italic;">B</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; clip: rect(3.537em 1000.62em 3.998em -999.997em); top: -4.711em; left: 0em;"><span class="mo" id="MathJax-Span-365" style=""><span style="display: inline-block; position: relative; width: 0.617em; height: 0px;"><span style="position: absolute; top: -3.993em; left: 0em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.412em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.105em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.259em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.122em; border-left: 0px solid; width: 0px; height: 1.441em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mover><mrow><mi>A</mi><mo>.</mo><mi>B</mi></mrow><mo accent="false">¯</mo></mover><mo>=</mo><mover><mi>A</mi><mo accent="false">¯</mo></mover><mo>+</mo><mover><mi>B</mi><mo accent="false">¯</mo></mover></math></span></span><script type="math/tex" id="MathJax-Element-43">\overline{A.B} = \overline{A} + \overline{B}</script></span></p><p><span class="mathjax"><span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-44-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mover><mrow><mi>A</mi><mo>+</mo><mi>B</mi></mrow><mo accent=&quot;false&quot;>&amp;#x00AF;</mo></mover><mo>=</mo><mover><mi>A</mi><mo accent=&quot;false&quot;>&amp;#x00AF;</mo></mover><mo>.</mo><mover><mi>B</mi><mo accent=&quot;false&quot;>&amp;#x00AF;</mo></mover></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-366" style="width: 6.662em; display: inline-block;"><span style="display: inline-block; position: relative; width: 5.433em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.386em 1005.43em 2.769em -999.997em); top: -2.559em; left: 0em;"><span class="mrow" id="MathJax-Span-367"><span class="munderover" id="MathJax-Span-368"><span style="display: inline-block; position: relative; width: 2.462em; height: 0px;"><span style="position: absolute; clip: rect(3.179em 1002.41em 4.203em -999.997em); top: -3.993em; left: 0.003em;"><span class="mrow" id="MathJax-Span-369"><span class="mi" id="MathJax-Span-370" style="font-family: STIXGeneral; font-style: italic;">A</span><span class="mo" id="MathJax-Span-371" style="font-family: STIXGeneral; padding-left: 0.259em;">+</span><span class="mi" id="MathJax-Span-372" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.259em;">B</span></span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; clip: rect(3.537em 1002.46em 3.998em -999.997em); top: -4.711em; left: 0em;"><span class="mo" id="MathJax-Span-373" style=""><span style="display: inline-block; position: relative; width: 2.462em; height: 0px;"><span style="position: absolute; top: -3.993em; left: 0em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 2.205em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.156em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.31em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.515em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.669em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.822em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 1.027em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 1.181em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 1.386em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 1.539em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 1.693em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 1.898em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 2.052em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span class="mo" id="MathJax-Span-374" style="font-family: STIXGeneral; padding-left: 0.31em;">=</span><span class="munderover" id="MathJax-Span-375" style="padding-left: 0.31em;"><span style="display: inline-block; position: relative; width: 0.617em; height: 0px;"><span style="position: absolute; clip: rect(3.179em 1000.57em 4.152em -999.997em); top: -3.993em; left: 0.003em;"><span class="mi" id="MathJax-Span-376" style="font-family: STIXGeneral; font-style: italic;">A</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; clip: rect(3.537em 1000.62em 3.998em -999.997em); top: -4.711em; left: 0em;"><span class="mo" id="MathJax-Span-377" style=""><span style="display: inline-block; position: relative; width: 0.617em; height: 0px;"><span style="position: absolute; top: -3.993em; left: 0em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.412em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.105em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.259em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span class="mo" id="MathJax-Span-378" style="font-family: STIXGeneral;">.</span><span class="munderover" id="MathJax-Span-379" style="padding-left: 0.207em;"><span style="display: inline-block; position: relative; width: 0.617em; height: 0px;"><span style="position: absolute; clip: rect(3.179em 1000.57em 4.152em -999.997em); top: -3.993em; left: 0.003em;"><span class="mi" id="MathJax-Span-380" style="font-family: STIXGeneral; font-style: italic;">B</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; clip: rect(3.537em 1000.62em 3.998em -999.997em); top: -4.711em; left: 0em;"><span class="mo" id="MathJax-Span-381" style=""><span style="display: inline-block; position: relative; width: 0.617em; height: 0px;"><span style="position: absolute; top: -3.993em; left: 0em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.412em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.105em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span><span style="position: absolute; top: -3.993em; left: 0.259em;"><span style="font-size: 70.7%; font-family: STIXGeneral;">⎯</span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span><span style="display: inline-block; width: 0px; height: 3.998em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.564em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.122em; border-left: 0px solid; width: 0px; height: 1.441em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mover><mrow><mi>A</mi><mo>+</mo><mi>B</mi></mrow><mo accent="false">¯</mo></mover><mo>=</mo><mover><mi>A</mi><mo accent="false">¯</mo></mover><mo>.</mo><mover><mi>B</mi><mo accent="false">¯</mo></mover></math></span></span><script type="math/tex" id="MathJax-Element-44">\overline{A+B} = \overline{A}.\overline{B}</script></span></p><h2 id="logic-gates"><a class="anchor hidden-xs" href="#logic-gates" title="logic-gates"><span class="octicon octicon-link"></span></a>Logic gates</h2><p><strong>Logic gate</strong> An electronic component used to perform boolean operations</p><h3 id="half-adder"><a class="anchor hidden-xs" href="#half-adder" title="half-adder"><span class="octicon octicon-link"></span></a>Half adder</h3><p>A half adder adds two single binary digits and accounts for carried values.</p><p><img src="https://i.imgur.com/e5RiTKr.png" alt=""></p><p>The output at S is the result of adding the two bits (1 if one of the two bits is 1, but not both), and the output at C is the carried bit if both input bits are 1.</p><h3 id="full-adder"><a class="anchor hidden-xs" href="#full-adder" title="full-adder"><span class="octicon octicon-link"></span></a>Full adder</h3><p>A full adder adds two single binary digits while accounting for a value carried in from a previous addition.</p><p><img src="https://i.imgur.com/Yvk8w0z.png" alt=""></p><p>The sum output is the XOR result of all three input bits.</p><p>The carry output is true if any pair of input bits are true.</p><h3 id="d-type-flip-flop"><a class="anchor hidden-xs" href="#d-type-flip-flop" title="d-type-flip-flop"><span class="octicon octicon-link"></span></a>D type flip flop</h3><p>The D type flip flop captures a value.</p><p><strong>Flip-flop</strong> A memory unit that can store one bit</p><p><strong>Edge-triggered D-type flip-flop</strong> A memory unit that changes state with each pulse of the clock</p><p><strong>Clock</strong> A device that generates a signal used to synchronise the components of the computer</p><p>In the case of an edge-triggered D-type flip-flop on each pulse of the clock, the flip-flop will change state. For each pulse, data coming from the input will be stored and continue to be output until the next trigger pulse is received.</p><p><strong>Ability to construct flip flop not required</strong></p><p><img src="https://upload.wikimedia.org/wikipedia/commons/9/99/Edge_triggered_D_flip_flop.svg" alt=""></p><h1 id="computer-organisation-and-architecture"><a class="anchor hidden-xs" href="#computer-organisation-and-architecture" title="computer-organisation-and-architecture"><span class="octicon octicon-link"></span></a>Computer organisation and architecture</h1><h2 id="internal-hardware-of-a-computer"><a class="anchor hidden-xs" href="#internal-hardware-of-a-computer" title="internal-hardware-of-a-computer"><span class="octicon octicon-link"></span></a>Internal hardware of a computer</h2><h3 id="processor"><a class="anchor hidden-xs" href="#processor" title="processor"><span class="octicon octicon-link"></span></a>Processor</h3><p><strong>Processor</strong> A device that carries out computation on data by following instructions, in order to produce an output</p><h3 id="main-memory"><a class="anchor hidden-xs" href="#main-memory" title="main-memory"><span class="octicon octicon-link"></span></a>Main memory</h3><p>Main memory is used to store data and instructions.</p><p><strong>Main memory</strong> Stores data and instructions that will be used by the processor</p><p><strong>Fetch-execute cycle</strong> The continuous process carried out by the processor when running programs</p><p><strong>Random Access Memory</strong> Stores data and can be read and written from</p><p><strong>Chip</strong> An electronic component contained within a thin slice of silicon</p><p>RAM is temporary storage space that can be accessed very quickly.<br>
RAM is volatile, meaning that whatever is stored on it will be lost once power is lost.</p><p><strong>Read only memory</strong> Stores data and can be read from, but not written to (unless programmable ROM)</p><p>ROM is non-volatile, and is usually writeable.</p><h3 id="addressable-memory"><a class="anchor hidden-xs" href="#addressable-memory" title="addressable-memory"><span class="octicon octicon-link"></span></a>Addressable memory</h3><p>Memory is made up of millions of addressable cells and the various instructions and data that make up a program will be stored across a number of cells. Each address can be uniquely identified.</p><h3 id="buses"><a class="anchor hidden-xs" href="#buses" title="buses"><span class="octicon octicon-link"></span></a>Buses</h3><p>Buses are groups of parallel microscopic wires that connect the processor to the various input and output controllers being used by the computer.</p><p><strong>Bus</strong> Microscopic parallel wires that transmit data between internal components</p><h4 id="data-bus"><a class="anchor hidden-xs" href="#data-bus" title="data-bus"><span class="octicon octicon-link"></span></a>Data bus</h4><p><strong>Data bus</strong> A bus used to transfer data between the processor and memory</p><p><strong>IO controller</strong> A component which controls the flow of information between the processor and the IO devices</p><p>The data bus connects the registers to each other and to memory. The amount of data that can be passed along the bus depends on how many wires are in the bus.</p><p><strong>Word length</strong> The number of bits that can be addressed, transferred, or manipulated as one unit</p><p><strong>Address bus</strong> A bus used to specify a physical address in memory so that the data bus can access it</p><h4 id="address-bus"><a class="anchor hidden-xs" href="#address-bus" title="address-bus"><span class="octicon octicon-link"></span></a>Address bus</h4><p>The address bus is unidirectional, from the processor into memory. The address bus is used by the processor and carries the memory address of the next instruction or data item. The address bus is therefore used to access anything that is stored in memory, not just instructions.</p><p>The size of the address bus is also measured in bits and represents the amount of memory that is addressable. An 8 bit bus would give only 256 directly addressable memory cells.</p><p><strong>Addressable memory</strong> The concept that data and instructions are stored in memory using discrete addresses</p><p><strong>Control bus</strong> A bus used to control the flow of data between the processor and other parts of the computer</p><h4 id="control-bus"><a class="anchor hidden-xs" href="#control-bus" title="control-bus"><span class="octicon octicon-link"></span></a>Control bus</h4><p>A bi-directional bus which sends control signals to the registers, the data and address buses.<br>
Data buses are sending data to and from memory while address buses send only to memory.</p><p>The control bus is used to ensure that the correct data is travelling to the right place at the right time. This involves synchronisation of signals and the control of access to the data and address buses which are being shared by a number of devices.</p><h4 id="io-controllers"><a class="anchor hidden-xs" href="#io-controllers" title="io-controllers"><span class="octicon octicon-link"></span></a>IO controllers</h4><p>The processor also receives and sends instructions and data to the various input and output devices connected to the computer.<br>
Controllers consist of their own circuitry that handle the data following between the processor and the device.<br>
Every device will have its own controller which allows new devices to be connected to the processor at any time.</p><p>A key feature of an IO controller is that it will translate signals from the device into the format required by the processor. There are many different devices and many different types of processor and it is the IO controller that provides the flexibility to add new devices without having to redesign the processor.</p><p>Another important feature is that the IO devices themselves respond relatively slowly compared to the processor. Therefore the IO controller is used to buffer data being sent between the processor and the device.</p><h3 id="von-neumann-and-harvard-architectures"><a class="anchor hidden-xs" href="#von-neumann-and-harvard-architectures" title="von-neumann-and-harvard-architectures"><span class="octicon octicon-link"></span></a>Von Neumann and Harvard architectures</h3><p><strong>Von Neumman architecture</strong> A technique for building a processor where data and instructions are stored in the same memory and accessed via buses</p><p><strong>Harvard architecture</strong> A technique for building a processor that uses separate buses and memory for data and instructions</p><p>The advantage of the Harvard architecture is that instructions and data are handled more quickly as they do not have to share the same bus.<br>
The Harvard architecture is widely used on embedded systems such as mobile phones, burglar alarms, etc, where there is a specific use, rather than being used within general purpose PCs.</p><p>Many such devices use digital signal processing. The idea of DSP is to take continuous real world data such as audio or video and then to compress it to enable faster processing. Chips that are optimised for DSP tend to have much lower power requirements.</p><h2 id="the-stored-program-concept-and-processor-components"><a class="anchor hidden-xs" href="#the-stored-program-concept-and-processor-components" title="the-stored-program-concept-and-processor-components"><span class="octicon octicon-link"></span></a>The stored program concept and processor components</h2><p><strong>Stored program concept</strong> The idea that instructions and data are stored together in memory</p><p><strong>Fetch-execute cycle</strong> The continuous process carried out by the processor when running programs</p><ul>
<li>Fetch- The processor fetches the program’s ntext instruction from memory. THe instruction will be stored at a memory address and will contain the instruction</li>
<li>Decode- The processor works out what the binary code at that address means</li>
<li>Execute- The processor carries out the instruction which may involve reading, writing, or performing a calculation</li>
</ul><p><img src="http://i.imgur.com/clPcpJN.png" alt=""></p><h3 id="the-control-unit"><a class="anchor hidden-xs" href="#the-control-unit" title="the-control-unit"><span class="octicon octicon-link"></span></a>The control unit</h3><p><strong>Control unit</strong> Part of the processor that manages the execution of instructions</p><p>The control unit supervises the fetch-execute cycle. The control unit also makes sure that all the data is being processed and routed correctly.</p><h3 id="arithmetic-logic-unit"><a class="anchor hidden-xs" href="#arithmetic-logic-unit" title="arithmetic-logic-unit"><span class="octicon octicon-link"></span></a>Arithmetic logic unit</h3><p><strong>Arithmetic Logic Unit</strong> Part of the processor that processes and manipulates data</p><p>The arithmetic logic unit carries out both arithmetic and logic.<br>
The ALU is sent an operation code and the operands.</p><h3 id="the-clock"><a class="anchor hidden-xs" href="#the-clock" title="the-clock"><span class="octicon octicon-link"></span></a>The clock</h3><p>All computers have an internal clock which generates a signal that is used to synchronise the operation of the processor and the movement of data around the other components of the computer</p><p><strong>Clock</strong> A device that generates a signal used to synchronise the components of a computer</p><h3 id="registers"><a class="anchor hidden-xs" href="#registers" title="registers"><span class="octicon octicon-link"></span></a>Registers</h3><p>The control unit needs somewhere to store details of the operation being dealt with by the fetch-execute cycle, and the ALU needs somewhere to put the results of any operation it carries out.</p><p><strong>Register</strong> A small section of temporary storage that is part of the processor</p><p><strong>Status register</strong> Keeps track of the various functions of the computer, such as if the result of the last calculation was positive or negative</p><p><strong>Interrupt register</strong> Stores details of incoming interrupts</p><p><strong>Current instruction register</strong> Stores the instructions that the CPU is currently decoding or executing</p><p><strong>Program counter</strong> Stores the address of the next instruction to be read from main memory</p><p><strong>Memory buffer register</strong> Stores data that is either written to or copied from the CPU</p><p><strong>Memory data register</strong> Another name for the memory buffer register</p><p><strong>Memory address register</strong> Stores the location of the address that data is either written to or copied from by the processor</p><p>A register must be large enough to hold an instruction.<br>
Some registers are general purpose while others are used for a specific purpose.</p><p>The status register keeps track of the status, such as if an overflow occurred during an arithmetic register.</p><p>The interrupt register is another type of status register, it stores details of any signals that have been received by the processor from other components attached to it.</p><h3 id="the-fetch-decode-execute-cycle"><a class="anchor hidden-xs" href="#the-fetch-decode-execute-cycle" title="the-fetch-decode-execute-cycle"><span class="octicon octicon-link"></span></a>The fetch-decode-execute cycle</h3><ul>
<li>Fetch: The program counter holds the address of the next instruction. The processor sends this address along the address bus to main memory. The contents of the memory location at that address are sent via the data bus to the current instruction register and the program counter is incremented. The details of addresses are initially loaded into the memory address register and the data is initially loaded into the memory buffer register. Some instructions need to load a number of words, so they may need to be fetched as successive parts of a single instruction.</li>
<li>Execute: THe processor then takes the instruction from the current instruction register and decides what to do with it by referring to the instruction set.This might be to send the contents of the memory buffer register to the arithmetic logic unit. Once the instruction that has just been taken from memory has been decoded, the processor carries out the instruction. It then goes back to the top of the cycle and fetches the next instruction. The results of any calculations are written either to a register or a memory location.</li>
</ul><h3 id="factors-affecting-processor-performance"><a class="anchor hidden-xs" href="#factors-affecting-processor-performance" title="factors-affecting-processor-performance"><span class="octicon octicon-link"></span></a>Factors affecting processor performance</h3><ul>
<li>Clock speed: It indicates how fast each instruction will be executed</li>
<li>Bus width: The processor needs to optimise the use of the clock pulse. One way of doing this is to increase the bus width.</li>
<li>Word length: Related to the data bus width. Computer systems with a greater word length can process more data at once</li>
<li>Multiple core: Several processors can be used to increase performance. The term core is used to define the components that enable instructions to be fetched and executed</li>
<li>Cache: Caching is a technique where instructions and data that are needed frequently are placed into a temporary area of memory separate from main memory. The cache can be accessed much more quickly than main memory</li>
</ul><h3 id="interrupts"><a class="anchor hidden-xs" href="#interrupts" title="interrupts"><span class="octicon octicon-link"></span></a>Interrupts</h3><p><strong>Interrupt</strong> A signal sent by a device or program to the processor requesting its attention</p><p>An additional step is added to the fetch-execute cycle. Between the completion of one execution and the start of the next a check is made to see if the interrupt register contains a new interrupt.</p><p>If an interrupt has occurred the processor will stop whatever it is doing to service the interrupt. This is done using the interrupt service routine.</p><p>The contents of the registers are placed onto the system stack. Once the interrupt has been processed the CPU will retrieve the values from the stack and place them in the correct registers.</p><p><strong>Interrupt service routine</strong> A routine to handle a particular type of interrupt</p><p><strong>Priorities</strong> A method for assigning importance to interrupts in order to process them in the right order</p><h4 id="priorities"><a class="anchor hidden-xs" href="#priorities" title="priorities"><span class="octicon octicon-link"></span></a>Priorities</h4><p>Sometimes the interrupt routine may be interrupted.<br>
In this case the processor will either place details of its current task on the stack or it will assess the priority of the interrupts and decide which one needs to be serviced first. Assigning different interrupts priority levels means that the most important signals are dealt with first.</p><table>
<thead>
<tr>
<th>Level</th>
<th>Type</th>
<th>Possible causes</th>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>Hardware failure</td>
<td>Power failure</td>
</tr>
<tr>
<td>2</td>
<td>Reset interrupt</td>
<td>Some computers have a reset button which resets the computer to its start-up position</td>
</tr>
<tr>
<td>3</td>
<td>Program error</td>
<td>The current application is about to crash, so the OS will attempt to recover</td>
</tr>
<tr>
<td>4</td>
<td>Timer</td>
<td>A timer interrupt is used as part of the time slicing process in a multitasking environment</td>
</tr>
<tr>
<td>4</td>
<td>IO</td>
<td>Incoming data from a keyboard or mouse etc</td>
</tr>
</tbody>
</table><h4 id="vectored-interrupt-mechanism"><a class="anchor hidden-xs" href="#vectored-interrupt-mechanism" title="vectored-interrupt-mechanism"><span class="octicon octicon-link"></span></a>Vectored interrupt mechanism</h4><p>Once the values of the registers have been pushed to the stack, the processor can handle the interrupt. This is done using a technique called vectored interrupt mechanism.</p><p><strong>Vectored interrupt mechanism</strong> A method of handling interrupts by pointing to the first memory address of the instructions needed</p><p>Each interrupt has an associated section of code that tells the processor how to deal with that particular interrupt.<br>
When the processor receives an interrupt it needs to know how to find that code. every type of interrupt has an associated memory address known as a vector.<br>
The vector points to the starting address of the code associated with each interrupt.</p><p>When an interrupt occurs, the processor identifies what kind of interrupt it is, then finds its associated interrupt vector. It then jumps to the address specified by the vector, from where it runs the interrupt service routine.</p><h2 id="the-processor-instruction-set-and-addressing-modes"><a class="anchor hidden-xs" href="#the-processor-instruction-set-and-addressing-modes" title="the-processor-instruction-set-and-addressing-modes"><span class="octicon octicon-link"></span></a>The processor instruction set and addressing modes</h2><p><strong>Instruction set</strong> the patterns of 0s and 1s that a particular processor recognises as commands, along with their associated meanings</p><p><strong>Opcode</strong> An operation code or instructions used in assembly language</p><p><strong>Operand</strong> A value or memory address that forms part of an assembly language instruction</p><p><strong>Addressing mode</strong> The way in which the operand is interpreted</p><p><strong>Assembly language</strong> A way of programming using mnemonics</p><p><strong>Mnemonics</strong> Short codes that are used as instructions when programming</p><h3 id="immediate-and-direct-addressing"><a class="anchor hidden-xs" href="#immediate-and-direct-addressing" title="immediate-and-direct-addressing"><span class="octicon octicon-link"></span></a>Immediate and direct addressing</h3><p><strong>Immediate addressing</strong> When the operand is the data to be used</p><p><strong>Direct addressing</strong> When the operand is the memory address or register number to load information from</p><h3 id="types-of-opcodes"><a class="anchor hidden-xs" href="#types-of-opcodes" title="types-of-opcodes"><span class="octicon octicon-link"></span></a>Types of opcodes</h3><p><strong>Data transfer operations</strong> Operations within an instruction set that move data around between the registers and memory</p><p><strong>Arithmetic operations</strong> Operations within an instruction set that perform basic maths</p><p><strong>Shift instructions</strong> Operations within an instruction set that move bits within a register</p><p><strong>Logical operations</strong> Operations within an instruction set that move the bits around within the operand</p><p><strong>Branch operations</strong> Operations within an instruction set that allow you to move from one part of the program to the other</p><h2 id="processor-performance"><a class="anchor hidden-xs" href="#processor-performance" title="processor-performance"><span class="octicon octicon-link"></span></a>Processor performance</h2><p>Processor performance is effected by:</p><ul>
<li>Multiple cores</li>
<li>Cache memory</li>
<li>Clock speed</li>
<li>Word length</li>
<li>Address bus width</li>
<li>Data bus width</li>
</ul><h2 id="external-hardware-devices"><a class="anchor hidden-xs" href="#external-hardware-devices" title="external-hardware-devices"><span class="octicon octicon-link"></span></a>External hardware devices</h2><h3 id="digital-camera"><a class="anchor hidden-xs" href="#digital-camera" title="digital-camera"><span class="octicon octicon-link"></span></a>Digital camera</h3><p><strong>Digital camera</strong> A device for creating images of photographs, which can be printed or transferred onto a computer to be manipulated and stored</p><ul>
<li>When a photograph is taken the shutter opens and lets light in through the lens</li>
<li>The light is focused onto a sensor, which is usually either a charge coupled device or a complementary metal oxide semiconductor</li>
<li>The sensors are made up of millions of transistors, each of which stores the data for one or more pixels</li>
<li>As the light hits the sensor it is converted into electrons and the amount of charge is recorded for each pixel</li>
<li>With light, all colours can be created from red, green, and blue. Therefore the camera will either have three different sensors, or use three different filters</li>
<li>The data are typically stored on removable storage devices, usually referred to as flash memory</li>
<li>Data are usually stored in compressed files</li>
<li>RAW files can also be generated, which are uncompressed and therefore contain all of the data from the original photograph</li>
<li>This digital data can be decoded and manipulated using specialised software</li>
</ul><p><strong>RGB filter</strong> red, green, and blue filters that light passes through in order to create all other colours</p><p><strong>Compression</strong> The process of reducing the size of a file</p><p><strong>Resolution</strong> The number of pixels used to create an image</p><h3 id="barcode-reader"><a class="anchor hidden-xs" href="#barcode-reader" title="barcode-reader"><span class="octicon octicon-link"></span></a>Barcode reader</h3><p><strong>Barcode reader</strong> A device that uses lasers or LEDS to read the black and white lines of a barcode</p><ul>
<li>A light, usually an LED or laser is passed over an image</li>
<li>Some form of light sensor is used to measure the intensity of light being reflected. This is converted into a current effectively generating a waveform. this could be achieved using a photodiode or a CCD sensor in the same way as the digital camera</li>
<li>White areas reflect most light and black areas least</li>
<li>The waveform is analogue and therefore needs to be converted into digital form using an analogue to digital converter</li>
<li>The signal is decoded into a form that can then be interpreted by software</li>
</ul><p>There are many different types of barcode.<br>
The most common is the universal product code which uses a series of black and white lines of four different widths that are encoded to represent the values 1 to 4. The numbers are below for a manual override and include a check digit.</p><p>Barcodes are used primarily for inputting product details at the point of sale.</p><p>More recently, the same technology has been applied to codes that are made up of blocks of black and white symbols rather than lines. One example is a QR code which can be used to encode a wider range of information than a barcode.</p><h3 id="radio-frequency-identification"><a class="anchor hidden-xs" href="#radio-frequency-identification" title="radio-frequency-identification"><span class="octicon octicon-link"></span></a>Radio frequency identification</h3><p><strong>Radio frequency identification</strong> A microscopic device that stores data and transmits it using radio waves. Usually used in tags to track items</p><ul>
<li>The tag, which can be microscopically small, contains a chip, which contains the data about the item and a modem to modulate and demodulate the radio signals</li>
<li>The tag also contains an antennae to send and receive signals</li>
<li>Tags can be either active, which means that they have their own power source, or passive, which means that they will pick up electromagnetic power when they are in range of an RFID reader</li>
<li>Signals and therefore data can be transmitted in both directions using radio frequencies. This may be over a short or long distance depending on what the tags are being used for and how they are powered. The typical range of RFID tags is between 1 and 100 metres</li>
<li>Tags may be used to simply track the physical location of the tagged item or the item may transmit data back</li>
</ul><p>Example use cases</p><ul>
<li>Tracking individuals, particularly vulnerable adults</li>
<li>Use in electronic passports</li>
<li>In credit and debit cards to make contactless payments</li>
<li>In transport and distribution to track shipments and deliveries</li>
<li>On high value items, such as artwork in museums or equipment in hospitals</li>
</ul><h3 id="laser-printer"><a class="anchor hidden-xs" href="#laser-printer" title="laser-printer"><span class="octicon octicon-link"></span></a>Laser printer</h3><p><strong>Laser printer</strong> A device that uses lasers and toner to create mono and colour prints</p><ul>
<li>A rotating drum inside the printer is coated in a chemical which holds an electric charge</li>
<li>The laser beam is reflected onto the drum and where the light hits the drum is discharged, effectively creating an image on the drum</li>
<li>As the drum rotates it picks up toner on the charged parts of the drum</li>
<li>Paper is passed over the drum and by giving the paper the opposite charge, the toner is transferred to the paper</li>
<li>The paper is heat treated to fuse the toner onto the paper</li>
</ul><p>To achieve colour printing, four different coloured toners are used, and the process of transferring the toner to the drum is repeated for each colour. In some printers, a transfer belt is used to hold the four-colour image and therefore transfer it just once from the belt to the paper.<br>
When printing, four colours are needed: cyan, magenta, yellow, and black.</p><h3 id="magnetic-hard-disk"><a class="anchor hidden-xs" href="#magnetic-hard-disk" title="magnetic-hard-disk"><span class="octicon octicon-link"></span></a>Magnetic hard disk</h3><p><strong>Hard disk</strong> A secondary storage device made up of metallic disks that stores data magnetically</p><p>Hard disks spin at speeds between 3600 and 15000 rpm as a series of heads read from and write to the disks. The heads to not actually touch the disks but float slightly above it by virtue of the speed at which the disk spins.</p><p>The surface of the disk is organised into concentric tracks and each track is split into sectors each of which can be individually addressed by the operating system. Because the head assembly can read any one of several disks, a cylinder reference is also used to identify which of the disks in the stack is being addressed.</p><p>Each sector has the same capacity and a large file will be stored over a number of sectors. The operating system groups sectors together into clusters to make storage easier to manage.</p><h3 id="optical-disk"><a class="anchor hidden-xs" href="#optical-disk" title="optical-disk"><span class="octicon octicon-link"></span></a>Optical disk</h3><p>Optical disk is a generic term for all variations of CD, DVD, and Blu-Ray that use laser technology to read and write data.<br>
An optical disk is made up of one single spiral track that starts in the middle and works its way to the edge of the CD. The laser will read the data that are contained within this track by reading the pits and lands in combination with a sensor that measures how much light is reflected.</p><p>For read-only optical disks, when data is written it is encoded as a series of pits or lands within the track. A protective layer is then put over the surface to prevent any corruption of the data.</p><p>For writeable optical disks, rather than using pits and lands, the disk is coated with a translucent photosensitive dye. When writing to the disk, the laser will alter the state of a dye spot that is coated onto the surface making it opaque.<br>
A write laser alters the density of the dye, and a read laster interprets the different densities to create binary patterns.</p><h3 id="solid-state-disk"><a class="anchor hidden-xs" href="#solid-state-disk" title="solid-state-disk"><span class="octicon octicon-link"></span></a>Solid state disk</h3><p>High speed access to memory is achieved using memory cards made up of semiconductors.<br>
Solid state drives use NAND memory and data is organised into blocks in a similar way to a traditional hard disk, with a controller managing the blocks of data.</p><p><strong>Controller</strong>  A device which manages access to and organises data into blocks</p><p><strong>Block</strong> The concept of storing data in set groups of bits and bytes of a fixed length</p><p><strong>Floating gate transistor</strong> A non-volatile transistor that stores data without a power source</p><p>A gloating gate transistor is able to trap and store charge.<br>
It contains two gates, a floating gate and a control gate.<br>
A thin layer of oxide is placed between the two gates, effectively trapping the charge inside the floating gate even when the power is turned off.</p><table>
<thead>
<tr>
<th></th>
<th>Hard disk</th>
<th>Solid state</th>
<th>Optical disk</th>
<th>Blu-Ray (OD)</th>
</tr>
</thead>
<tbody>
<tr>
<td>Typical capacity</td>
<td>High (1 TB)</td>
<td>Medium (500 GB)</td>
<td>Low (0.9-1.7 GB)</td>
<td>Low (25-50 GB)</td>
</tr>
<tr>
<td>Relative cost</td>
<td>Medium</td>
<td>High</td>
<td>Low</td>
<td>Low</td>
</tr>
<tr>
<td>Power consumption</td>
<td>High</td>
<td>Low</td>
<td>High</td>
<td>High</td>
</tr>
<tr>
<td>Speed of access</td>
<td>Medium</td>
<td>High</td>
<td>Low</td>
<td>Low</td>
</tr>
<tr>
<td>Latency</td>
<td>High</td>
<td>Low</td>
<td>Very high</td>
<td>High</td>
</tr>
<tr>
<td>Fragmentation</td>
<td></td>
<td>None</td>
<td></td>
<td></td>
</tr>
<tr>
<td>Reliability</td>
<td>Good</td>
<td>Very good</td>
<td>Fair</td>
<td>Fair</td>
</tr>
<tr>
<td>Physical size</td>
<td>Large</td>
<td>Small</td>
<td>Small</td>
<td>Small</td>
</tr>
</tbody>
</table><h1 id="moral-ethical-legal-and-cultural-issues"><a class="anchor hidden-xs" href="#moral-ethical-legal-and-cultural-issues" title="moral-ethical-legal-and-cultural-issues"><span class="octicon octicon-link"></span></a>Moral, ethical, legal, and cultural issues</h1><p><strong>Ethical issues</strong> Factors that define the set of moral values by which society functions</p><h2 id="use-and-misuse-of-data"><a class="anchor hidden-xs" href="#use-and-misuse-of-data" title="use-and-misuse-of-data"><span class="octicon octicon-link"></span></a>Use and misuse of data</h2><p>Most organisations collect data on an ongoing basis and much of these data are personal.<br>
this presents a number of issues:</p><ul>
<li>Personal privacy: A lot of data are stored online as a matter of routine and as individuals we may not have explicitly consented to them being collected and used</li>
<li>Data security: Much of the data are stored online or on networks connected to the Internet. How can we be sure they are safe from unauthorised users?</li>
<li>Misuse of data: Data collected for one purpose are used for a different purpose. In many cases data are sold on to other organisations.</li>
<li>‘Big Brother’: Many people have concerns that personal data are being used by government to monitor individuals and that this is a breach of our basic human rights</li>
<li>Online profile: Every time you do anything online, such as using social media, that data may stay online for years and contribute to what people know about you</li>
<li>Profiling: Large organisations often accumulate data in order to build up a profile of individuals. this could have a negative impact on an individual</li>
</ul><h3 id="banking-the-benefits-of-technology"><a class="anchor hidden-xs" href="#banking-the-benefits-of-technology" title="banking-the-benefits-of-technology"><span class="octicon octicon-link"></span></a>Banking- the benefits of technology</h3><p>Around 30 years ago, if you wanted to carry out any banking transaction you had to do it in the limited time that a bank was open. the invention of cash machines in the 1980s was a revolution that allowed customers constant access to their money. the invention of online banking in the 1990s meant that almost all transactions could be done at any time, including paying bills, setting up direct debits, and moving money from one account to another.</p><h3 id="banking-the-threat-of-technology"><a class="anchor hidden-xs" href="#banking-the-threat-of-technology" title="banking-the-threat-of-technology"><span class="octicon octicon-link"></span></a>Banking- The threat of technology</h3><p>According to some sources there are as many as 250,000 phishing attacks per year.<br>
Some customers have lost hundreds of thousand of pounds in individual attacks that use sophisticated software to emulate online banking websites.</p><h3 id="other-moral-and-social-issues"><a class="anchor hidden-xs" href="#other-moral-and-social-issues" title="other-moral-and-social-issues"><span class="octicon octicon-link"></span></a>Other moral and social issues</h3><p><strong>Unauthorised access</strong> Where computer systems or data are used by people who are not the intended users</p><ul>
<li>Unauthorised use of software: Some people believe that software is too expensive and that software companies are exploitative. Therefore, downloading or copying software is morally defendable</li>
<li>Inappropriate behaviour: There is evidence that people’s behaviour changes when they are online. In the worst cases this can lead to online abuse which may spread into the real world</li>
<li>Inappropriate content: There are large volumes of content on the Internet which many people consider to be inapprorpriate. This content may not be illegal, but there is conecrn about what effect it has on society</li>
<li>Freedom of speech: Some people believe that they should be able to say whatever they want, even if that offends other people. the Internet gives almost everyone the ability to do that. It therefore raises the issue of whether there should be some code that all internet users should adhere to when expressing their views</li>
<li>Unemployment: A broader social issue relates to the impact that new technology has on people’s working lives. Many businesses such as retail and banking no longer need to emply as many people in their stores and branches. On the other hand, they may create more jobs in IT for employees working in their online businesses</li>
<li>Access to the internet: It is difficult to know how many people have access to the Internet. Are those who do not have access disadvantaged?</li>
</ul><p><strong>Moral issues</strong> Factors that define how an individual acts and behaves</p><p><strong>Code of conduct</strong> A voluntary set of rules that defines the way in which individuals and organisations will behave</p><p>The British Computer Society has produced a code of conduct and a code of ethics that guide individuals and organisations on the use of computer systems.</p><p>The main principles are that members should:</p><ul>
<li>Always operate in the public interest</li>
<li>Have a duty to the organisation that they work for, or the college that they attend</li>
<li>Have a duty to the profession</li>
<li>Maintain professional competence and integrity</li>
</ul><h2 id="legal-issues"><a class="anchor hidden-xs" href="#legal-issues" title="legal-issues"><span class="octicon octicon-link"></span></a>Legal issues</h2><p><strong>Legal issues</strong> Factors that have been made into laws by the government</p><p>Legislators who enforce these laws have two main issues:</p><ul>
<li>Geographical limitations: Most UK laws only apply in the UK. With the global nature of the Internet it can be difficult to prove where a particular offence took place. Also, if the perpetrator breaks a UK law but they are based in another country, it can be difficult to prosecute them</li>
<li>Constant change: most acts are introduced in response to current events. As technology develops so rapidly, laws often become out of date quite quickly</li>
</ul><h3 id="data-protection-act"><a class="anchor hidden-xs" href="#data-protection-act" title="data-protection-act"><span class="octicon octicon-link"></span></a>Data Protection Act</h3><p>The Data Protection Act was introduced in 1984. it has since been updated to reflect the enormous changes in the use of information.<br>
It places controls on organisations and individuals that store personal data electronically.</p><p>The definition of personal data is any data on an individual where the person (known as the data subject) is alive and can be individually identified.</p><p>The Act states that any person or organisation storing personal data must register with the Information Commissioner, an independent organisation set up by the government to oversee Data Protection and Freedom of Information.</p><p>the Information Commissioner’s mission is:</p><p>"We shall develop respect for the private lives of individuals and encourage the openness and accountability of public authorities.</p><ul>
<li>by promoting good information handling practice and enforcing data protection and freedom of information legislation; and</li>
<li>by seeking to influence national and international thinking on privacy and information access issues."</li>
</ul><p>There are eight main principles behind the data Protection Act. Anyone processing data must comply with these eight enforcable principles of good practice.</p><p>Data must be:</p><ul>
<li>Fairly and lawfully processed</li>
<li>Processed for limited purposes</li>
<li>Adequate, relevant, and not excessive</li>
<li>Accurate</li>
<li>Not kept longer than necessary</li>
<li>Processed in accordance with the data subject’s rights</li>
<li>Secure</li>
<li>Not transferred to countries without adequate data protection</li>
</ul><p>Another feature of the Act is that data subjects have the right to know what data are stored about them by any particular individual or organization.<br>
These are known as subject access rights. If this information is incorrect then the data subject has the right to have it corrected. The organisation must be given notice and may charge a small fee to the data subject.</p><h3 id="freedom-of-information-act"><a class="anchor hidden-xs" href="#freedom-of-information-act" title="freedom-of-information-act"><span class="octicon octicon-link"></span></a>Freedom of information act</h3><p>The Freedom of Information Act extends the subject access rights of the Data Protection Act and gives general rights to access of information held by public authorities such as hospitals, doctors, dentists, the police, schools and colleges. Both Acts are overseen by the Information Commisioner.</p><p>The Act gives individuals access to both personal and non-personal data held by public authorities. the idea behind the Act was to provide more openness between the public and government agencies. Therefore, the agencies are obliged to give the public access to information and to respond to individual requests for information. Much of t</p><h3 id="computer-misuse-act"><a class="anchor hidden-xs" href="#computer-misuse-act" title="computer-misuse-act"><span class="octicon octicon-link"></span></a>Computer Misuse Act</h3><p><strong>Data misuse</strong> Using data for purposes other than for which it was collected</p><p>The Computer Misuse Act contains three specific offences related to computer usage:</p><ul>
<li>Unauthorised access to computer programs or data: This includes some forms of hacking including breaking through password protection and firewalls, decrypting files, or stealing another user’s identity</li>
<li>Unauthorised access with further criminal intent: An extension of the first offence where there is a clear intention to carry out a further criminal act such as an act of fraud or a copyright breach</li>
<li>Unauthorised modification of computer material: This includes falsifying bank details or exam grades, spreading viruses designed to corrupt data and programs and interfering with system files</li>
</ul><p>The Act was introduced before the widespread use of the Internet, which has lead to some problems with enforcement.</p><h3 id="regulation-of-investigatory-powers-act"><a class="anchor hidden-xs" href="#regulation-of-investigatory-powers-act" title="regulation-of-investigatory-powers-act"><span class="octicon octicon-link"></span></a>Regulation of Investigatory Powers Act</h3><p>The RIP Act was introduced to clarify the powers that government agencies have when investigating crime or suspected crime. It is not specific to the world of computing but was introduced partly to take account of changes in communication technology and the widespread use of the Internet.</p><p>There are five main parts to the Act.<br>
Part 1 relates to the interception of communications, including electronic data.<br>
Part 3 covers the investigation of electronic data protected by encryption.</p><p>It gives law enforcement agencies the right to intercept communications where there is suspicion of criminal activity. They also have the right to decipher these data if they are encrypted even if this means that the user must tell the police how to decrypt the data.</p><p>It also allows employers to monitor the computer activity of their employees during work time.</p><h3 id="copyright-designs-and-patents-act"><a class="anchor hidden-xs" href="#copyright-designs-and-patents-act" title="copyright-designs-and-patents-act"><span class="octicon octicon-link"></span></a>Copyright, Designs, and Patents Act</h3><p>This Act gives rights to the creators of certain kinds of material allowing them control over the way in which the material is used. The law covers the copying, adapting, and renting of materials.</p><p><strong>Copyright</strong> The legal ownership that applies to software, music, films, and other content</p><p>Copyright applies to all works, regardless of the format. Consequently, work produced on the Internet is also covered by copyright. It is illegal to produce pirate copies of software or run more versions on a network than have been paid for.<br>
It is an offence to adapt existing versions of software without permission. It is also an offence to download music or films without the permission of the copyright holder.</p><p>In computing, two techniques are used to protect copyright:</p><ul>
<li>Digital Rights Management: This uses access control software to limit the way in which users can control, use, copy, print, or edit digital content that they have bought</li>
<li>Licensing: normally used for software, this provides users with a paper based or digital proof that they have purchased software legally and details what they are allowed to do with the software</li>
</ul><h3 id="other-relevant-acts"><a class="anchor hidden-xs" href="#other-relevant-acts" title="other-relevant-acts"><span class="octicon octicon-link"></span></a>Other relevant acts</h3><ul>
<li>The Official secrets Act prevents the disclosure of government data relating to national security</li>
<li>The Defamation Act prevents people from making untrue statements about other which will lead to their reputation being damaged</li>
<li>The Obscence Publications Act and the Protection of Children Act prevent people from disseminating pornograhic or violent images</li>
<li>the Health and Safety Regulations provides regulation on the correct use of screens and is a specific addition to the Health and Safety at Work Act</li>
<li>The Equality Act makes it illegal to discriminate against anyone on the grounds of sex, sexual orientation, ethnicity, religion, disability, or age</li>
</ul><h2 id="cultural-issues"><a class="anchor hidden-xs" href="#cultural-issues" title="cultural-issues"><span class="octicon octicon-link"></span></a>Cultural issues</h2><p><strong>Cultural issues</strong> Factors that have an impact on the ways in which we function as a society</p><p>There are elements of computer use that have a cultural impact in that they can change our attitudes, beliefs, and actions:</p><ul>
<li>Over use of data: There are fears that we are becoming completely dependent on data. Many decisions about the way in which the country is run are based on data analysis</li>
<li>Invasive technologies: A lot of data are collected without our consent, such as satellite images</li>
<li>Over reliance on computers: What happens when computer systems fail?</li>
<li>Over reliance on technology companies: Two thirds of all Internet searches are done through Google. Wikipedia often appears on the front page of search results. This gives these two organisations a great influence over the information we access</li>
<li>‘Big Brother’ culture: With the increasing use of CCTV, the desire for national identity cards, and the monitoring of emails and mobile phone calls, some people believe that we are heading towards a society where everything is watched</li>
<li>Globalisation: As we become more connected to other cultures, we are more likely to be influenced by them</li>
</ul><h1 id="communication-and-networking"><a class="anchor hidden-xs" href="#communication-and-networking" title="communication-and-networking"><span class="octicon octicon-link"></span></a>Communication and networking</h1><h2 id="communication"><a class="anchor hidden-xs" href="#communication" title="communication"><span class="octicon octicon-link"></span></a>Communication</h2><p><strong>Serial transmission</strong> Data is transmitted one bit at a time down a single wire</p><p><strong>Parallel transmission</strong> Data is transmitted several bits at a time using multiple wires</p><p><strong>Bandwidth</strong> A measure of the capacity of the channel down which the data is being sent</p><p><strong>Bit rate</strong> The rate at which data is actually being transmitted</p><p><strong>Baud rate</strong> One baud represents one electronic state change per second. An electronic state change could encode multiple bits</p><p><strong>Latency</strong> The time delay that ocfurs when transmitting data between devices</p><h3 id="synchronous-and-asynchronous-data-transmission"><a class="anchor hidden-xs" href="#synchronous-and-asynchronous-data-transmission" title="synchronous-and-asynchronous-data-transmission"><span class="octicon octicon-link"></span></a>Synchronous and asynchronous data transmission</h3><p>In synchronous transmission, the two devices will synchronise their transmission signals. The computer sending the data will control the transmission rate to be in time with the device or computer receiving the signal. If two devices are not synchronised then data could be lost during transmission.</p><p>Once the devices are synchronised, data can be sent without any need for further information.</p><p>Asynchronous  transmission does not require the permanent synchronisation of the sender’s and receiver’s system clocks. Instead, it synchronises only for the duration of the transmission by sending additional bits of information called start and stop bits.</p><p><strong>Asynchronous data transmission</strong> Data is transmitted between two devices that do not share a common clock signal</p><p><strong>Start bit</strong> A bit used to indicate the start of a unit of data in asynchronous data transmission</p><p><strong>Stop bit</strong> A bit used to indicate the end of a unit of data in asynchronous data transmission</p><p><strong>Parity bit</strong> A method of checking binary codes by counting the number of 0s and 1s in the code</p><ul>
<li>The start bit causes the receiver to synchronise its clock to the same rate as the sender</li>
<li>Both devices have already agreed on how many bits of data will follow, whether parity is used, and how many stop bits there will be</li>
<li>The stop bit(s) indicate that the data has arrived so the processor on the receiver’s device can now handle those bits. The stop bit also also allows the receiver to identify when the next start bit arrives</li>
<li>If there is more data then another start bit will be sent and the cycle will continue</li>
<li>The sender’s device sends data as soon as it is available rather than waiting for the clock pulse or a synchronisation signal from the receiver</li>
</ul><p><strong>Synchronous data transmission</strong> Data is transmitted where the pulse of the clock of the sending and receiving devices are in time with each other</p><h3 id="protocols"><a class="anchor hidden-xs" href="#protocols" title="protocols"><span class="octicon octicon-link"></span></a>Protocols</h3><p><strong>Protocols</strong> Sets of rules</p><p><strong>TCP/IP</strong> A set of protocols for all TCP/IP transmissions</p><p><strong>HTTP</strong> The protocol to define the identification, request, and transfer of multimedia content over the internet</p><p><strong>FTP</strong> The protocol for handling file uploads and downloads</p><p>TCP/IP:</p><p>The Transmission Control Protocol/Internet Protocol is actually two protocols that are usually referred to as one and relate to the set of rules that govern the transmission of data around the Internet. Data sent around the Internet are split into packets. TCP/IP handles the routing and re-assembly of these data packets.</p><p>HTTP:<br>
The Hypertext Transfer Protocol is the set of rules governing the exchange of the different types of file that make up displayable web pages.</p><p>FTP:<br>
The File Transfer Protocol is similar to HTTP in that it provides the rules for the transfer of files on the Internet. FTP is commonly used when downloading files or uploading web pages to a server.</p><h2 id="networks"><a class="anchor hidden-xs" href="#networks" title="networks"><span class="octicon octicon-link"></span></a>Networks</h2><p><strong>Network</strong> Devices that are connected together to share data and resources</p><p><strong>Network adapter/Network Interface Card</strong> A card that enables devices to connect to a network</p><p><strong>Network topology</strong> The conceptual layout of a network</p><p><strong>Local Area Network</strong> A network over a small geographical distance, usually a single site and organisation</p><p><strong>Wide Area Network</strong> A network spread over a large geographical distance</p><p>Modern routers are actually a number of devices merged together into a single device:</p><ul>
<li>Receives every packet of data being transmitted, reads the header and forwards it to its destination</li>
<li>Acts as a firewall, preventing certain packets from being forwarded</li>
<li>Acts as an switch, creating a connection between two devices on a network</li>
<li>Provides a wireless access point transmitting a WIFI signal</li>
<li>Acts as a modem to convert digital signals to analogue so that they can be transmitted down standard telephone cables</li>
</ul><h3 id="star-topology"><a class="anchor hidden-xs" href="#star-topology" title="star-topology"><span class="octicon octicon-link"></span></a>Star topology</h3><p><strong>Star topology</strong> A way of connecting devices to a network where each device has a dedicated cable to a central computer or switch</p><p>Software may be stored centrally on the server and can be installed, upgraded, and maintained via the server. The server will also contain an operating system that controls the users’ access to the system and also includes various administration functions such as managing the print queue.</p><table>
<thead>
<tr>
<th>Advantages</th>
<th>Disadvantages</th>
</tr>
</thead>
<tbody>
<tr>
<td>Fast connection speed as each client has a cable</td>
<td>Expensive to set up due to cabling</td>
</tr>
<tr>
<td>Will not slow down when many users are online</td>
<td>If the cable fails, the client may not be able to receive data</td>
</tr>
<tr>
<td>Fault finding is simpler as individual faults are easier to trace</td>
<td>Difficult to install as multiple cables are needed, especially across multiple buildings</td>
</tr>
<tr>
<td>Relatively secure as each connection is unique</td>
<td>The server can get congested as all communications must pass through it</td>
</tr>
<tr>
<td>New clients can be added without affecting the other clients</td>
<td></td>
</tr>
<tr>
<td>If one cable or client fails, then only that client is affected</td>
<td></td>
</tr>
</tbody>
</table><h3 id="bus-topology"><a class="anchor hidden-xs" href="#bus-topology" title="bus-topology"><span class="octicon octicon-link"></span></a>Bus topology</h3><p><strong>Bus topology</strong> A network layout that uses one main data cable as a backbone to transmit data</p><table>
<thead>
<tr>
<th>Advantages</th>
<th>Disadvantages</th>
</tr>
</thead>
<tbody>
<tr>
<td>Only one main cable required</td>
<td>Less secure as data are transmitted down one cable</td>
</tr>
<tr>
<td>Easier to install than a star</td>
<td>Transmission times get slower when more users are on the network</td>
</tr>
<tr>
<td>Easy to add new clients</td>
<td>One cable affects all users</td>
</tr>
<tr>
<td></td>
<td>Less reliable and more difficult to find faults</td>
</tr>
</tbody>
</table><p><strong>Physical topology</strong> The way in which devices in a network are physically connected</p><p><strong>Logical topology</strong> The conceptual way in data is transmitted around a network</p><h3 id="client-server-networks"><a class="anchor hidden-xs" href="#client-server-networks" title="client-server-networks"><span class="octicon octicon-link"></span></a>Client-server networks</h3><p>In the star and bus topologies, the diagram shows a main server. Although the clients have local resources in terms of processing power, and storage capacity, they are controlled by the server. This emans that when new software is installed, it can be installed on the server and distributed.</p><p>The client may request</p><ul>
<li>Access to a printer</li>
<li>Providing a secure Internet connection</li>
<li>Access to email</li>
<li>Access to applications</li>
<li>Access to files</li>
</ul><p>This is the most common way of constructing a LAN with a large number of uses.</p><p><strong>Client-server</strong> A network methodology where one computer has the main processing power and storage and the other coputers act as client requesting services from the server</p><h3 id="peer-to-peer-networks"><a class="anchor hidden-xs" href="#peer-to-peer-networks" title="peer-to-peer-networks"><span class="octicon octicon-link"></span></a>Peer to peer networks</h3><p><strong>Peer-to-peer</strong> A network methodology where all devices in a network share resources between them rather than having a server</p><p>This is more common among smaller networks or for certain applications such as file-sharing. Peer-to-peer networks can be created without the need for a special network operating system.</p><h3 id="wireless-networks"><a class="anchor hidden-xs" href="#wireless-networks" title="wireless-networks"><span class="octicon octicon-link"></span></a>Wireless networks</h3><p><strong>Wireless Wide Area Network</strong> A WAN that does not use cables, but sends data using radio waves</p><p><strong>Media Access Control Adress</strong> A unique code that identifies a particular device on a network</p><p><strong>WiFi</strong> A standard method for connecting devices wirelessly to a network and to the Internet</p><p><strong>Wireless Local Area Network</strong> A LAN that does not use cables, but connects using radio waves</p><p>All devices on a network have a MAC address. This is encoded into the network interface card and is in the format of six groups of two hex digits.<br>
The first half of the MAC address is the manufacturer code and the second half is the unique device code allocated by that manufacturer.</p><p>Different communication devices are needed to create a wireless network, depending on the geographical coverage.</p><h3 id="protocols1"><a class="anchor hidden-xs" href="#protocols1" title="protocols1"><span class="octicon octicon-link"></span></a>Protocols</h3><p>There are a set of standards and protocols for wireless communications and WiFi to ensure that all devices are able to connect with each other and transmit and receive data. A protocol called Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) was developed to enable the various devices to transmit at high speeds without interfering with each other.</p><p>When data are sent around the networks, they are sent in frames with all the frames being re-assembled at the receiving end. Any device on the network may attempt to send frames. These frames can be picked up by any nodes or devices within range.<br>
Before each frame is sent, the devices use the CSMA/CA protocol to see whether the transmission medium is idle or whether another device is using it. If the transmission media is idle, the data are sent.<br>
Otherwise, each device will wait a random amount of time before trying again.</p><p>On receipt of the data, an acknoledgement is sent back to the sending device to confirm that the data have been received and not corrupted. If this is not received, again it will wait a random amount of time before resending.</p><p>An optional extension to the protocol is a system called Request to Send/Clear to Send (RTS/CTS), which works between the nodes on a network. The RTS sends a message to the receiving node or access point and if a CTS message is received, it knows that the node is idle and that the data frame can be sent.</p><p><strong>Request to Send/Clear to Send</strong> A protocol to ensure data does not collide when being transmitted on wireless networks</p><p><strong>Service Set Identiffier (SSID)</strong> A locally unique 32-character code that identifies a device on a wireless network</p><p>As alll of the data are being sent through radio waves rather than cables, each device needs a way of ensuring that it is connecting to the correct network. The standard method of doing this is to use the SSID in the header of each packet of data being sent.</p><p>Each code is locally unique to the particular WLAN that is being used, and therefore acts as an identifier allowing that frame of data to be transmitted.<br>
The network interface card must also be programmed with the same ID so that the device can connect to the WLAN in the first place.</p><h3 id="network-security"><a class="anchor hidden-xs" href="#network-security" title="network-security"><span class="octicon octicon-link"></span></a>Network security</h3><p>Wireless technology can be less secure than a wired system. This is because the signals are asier to intercept.<br>
There are a number of steps that can be taken to increase the level of security on a wireless network:</p><ul>
<li>Change the SSID from the default value and hide it from transmission</li>
<li>Ensure that all devices are WiFi Protected Access compliant</li>
<li>Use strong encryption</li>
<li>Create a white list of MAC addresses that are known to be trustworthy</li>
</ul><p><strong>WiFi Protected Access</strong> A protocol for encrypting data and ensuring security on Wifi Networks</p><h2 id="the-internet"><a class="anchor hidden-xs" href="#the-internet" title="the-internet"><span class="octicon octicon-link"></span></a>The Internet</h2><p><strong>Internet</strong> A global network of networks</p><h3 id="uniform-resource-locator"><a class="anchor hidden-xs" href="#uniform-resource-locator" title="uniform-resource-locator"><span class="octicon octicon-link"></span></a>Uniform resource locator</h3><p>A URL is the full address used to find files on the Internet.</p><p>The contentds of the file that a URL locates will vary depending on the Internet protocol being used. When HTTP is used, it finds an index.html file.</p><p><strong>Uniform resource locator</strong> A method for identifying the location of resources on the Internet</p><p>The address is made of several parts:</p><ul>
<li>The protocol being used</li>
<li>The domain name</li>
<li>The filename to locate the specific file needed</li>
</ul><h4 id="domain-name"><a class="anchor hidden-xs" href="#domain-name" title="domain-name"><span class="octicon octicon-link"></span></a>Domain name</h4><p><strong>Domain name</strong> The recognisable name of a domain on the Internet</p><p><strong>Fully qualified domain name</strong> A domain name including the host server, e.g. www or ftp</p><p>The domain name identifies organisations or groups on the Internet.</p><ul>
<li>co indicates a company</li>
<li>com indicates a commercial organisation</li>
<li>gov indicates a government</li>
<li>ac indicates an academic institution</li>
<li>sch indicates a school</li>
<li>org indicats a non commercial organisation</li>
<li>net indicates a company providing Internet services</li>
<li>A two letter country code such as “uk” indicates the country</li>
</ul><h4 id="ip-address"><a class="anchor hidden-xs" href="#ip-address" title="ip-address"><span class="octicon octicon-link"></span></a>IP Address</h4><p><strong>Internet Protocol (IP) address</strong> A unique number that identifies devices on a network</p><p>Every domain name is mapped to a number. A domain name server is used to translate the domain name to an IP address.</p><p><strong>Domain name server (DNS)</strong> A server that contains domain names and associated IP addresses</p><p>Some IP addresses are classed as private or non-routable addresses. Typically these are the IP addresses used by devices on a private network.<br>
The IP address is needed in order to route data around the network, however it does not need to be made public as that device is not diretly connected to the Internet. It is hidden behind a router or firewall. Non-routable addresses only have to be unique within the LAN and therefore do not need to be alloacted on a global basis.</p><p>When connection to the Internet is required, the device will be connected to a router or proxy server in order to connect. In this case the IP address of that router or server needs to be a public or routable address in which case it becomes a unique address that is registered under the domain name system.</p><h3 id="ports"><a class="anchor hidden-xs" href="#ports" title="ports"><span class="octicon octicon-link"></span></a>Ports</h3><p><strong>Port</strong> Used to identify a particular process or application on a network</p><p><strong>POP3</strong> A protocol for receiving emails</p><p>The port is a 16 bit number attached to the IP address. By addressing that port, a process or application will be accessed on the client.</p><p>When a client sends a request to the server using a well-knon port, the server needs to respond back to a client port and not the well known port on the client side. Therefore a source port must be sent as part of the client request.</p><p><strong>Secure shell (SSH) protocol</strong> A protocol for remote access to computers</p><h3 id="network-address-translation"><a class="anchor hidden-xs" href="#network-address-translation" title="network-address-translation"><span class="octicon octicon-link"></span></a>Network Address Translation</h3><p>The system that is used to match private IP addresses to public ones is called Network Address Translation.<br>
This has two main advantages:</p><ul>
<li>A unique IP address is not needed for every device on a network, only on the router or server that is physicallly connected. This means that only the public address needs to be registered with the DNS system</li>
<li>There is an increased level of security as the private IP address is not being broadcast over the Internet, making that device more secure from unauthorised access</li>
</ul><p><strong>Domain name server (DNS) system</strong> A system of connected domain name servers that provides the IP addresses of every website on the internet</p><p>The router will track connections and maintain a list of mappings between private IP addresses and port numbers and the corresponding public address. It does this by adding entries to a translation table which act as a look-up between the internal IP address and the external IP address.</p><p>The following is a common way that NAT can work when a workstation on the internal network wants to load data from a server on the Internet:</p><ul>
<li>The workstation on the internal network sends a packet to the server on the Internet to request some data, including its own internal IP address and port number in the packet so that the server knows where to return the data to</li>
<li>The router replaces the internal IP address and port number in the packet with its external IP address and a port number that it generates. This port number will be unique to this communication, within a certain time frame</li>
<li>The router stores the mapping information from the internal IP address and port number to external port number in the translation table</li>
<li>Data sent back from the server will be received by the router which will look up the port number in the translation table to identify which machine on the intrnal network sent the request to the server</li>
<li>The router’s IP address in the packet will be replaced with the originating workstation’s IP address and port number, as read from the translation table</li>
<li>The reply packet can then be sent on to the originating workstation</li>
<li>Where the translation table does not contain a match to a port number in a packet received from a computer on the Internet, the packet is dropped because it is not a packet sent in response to a request from within the network and may be a security issue</li>
<li>The internal IP address and port are never made public on the external network</li>
</ul><h3 id="port-forwarding"><a class="anchor hidden-xs" href="#port-forwarding" title="port-forwarding"><span class="octicon octicon-link"></span></a>Port Forwarding</h3><p>Port forwarding is commonly used when a server inside a private network, with a non-routable IP address, is to be used to provide services to clients on the Internet. As the server has non-routable IP address, it cannot be accessed directly from the Internet.<br>
Therefore, the client on the Internet must use the public IP address of the router that connects the private network with the server on it to initiate a connection. This router can be programmed so that request sent to a particular port number are forwarded to a device with a specific IP address within the network.</p><p><strong>Port forwarding</strong> A method of routing data through additional ports</p><h3 id="sockets"><a class="anchor hidden-xs" href="#sockets" title="sockets"><span class="octicon octicon-link"></span></a>Sockets</h3><p>A network socket is an endpoint of a communication flow across a computer network. Sockets are created in software not hardware. A TCP/IP socket is made up from the combination of an IP address and port number.</p><p><strong>Socket</strong> An endpoint of a communication flow across a computer network</p><p>Sockets can be created at any time to enable a network connection to be established to or from a computer.<br>
For example Client A is being used on a LAN with a local IP adress 192.168.233.100 and wishes to request a web page from server B which has IP address 192.168.233.2. As a web page is being requested, port 80 on the server will be used so Client A will send its request to 192.168.233.2:80.</p><p>In the request, Client A will include its own IP address and port number that has been temporarily generated for this communication. The client will listen on this port number for a reply.<br>
The transport layer of the TCP/IP stack uses the port number to direct packets to the correct application</p><h3 id="subnet-masking"><a class="anchor hidden-xs" href="#subnet-masking" title="subnet-masking"><span class="octicon octicon-link"></span></a>Subnet masking</h3><p>IP addresses are split into a network identifier and a host identifier.<br>
The network may be a local network, or it could be a remote network and the device could be a computer or printer etc.</p><p><strong>Subnet masking</strong> A method of dividing a network into multiple smaller networks</p><p>Addresses are split up this way to make networks easier to manager and to make the routing of data more efficient.</p><p>When a computer on a network sends data to another computer, it needs to identify whether it is on the same subnet as the other computer. If it is, it can send data to it directly. If it is not, it will send data to the relevant router or gateway, which will in turn send the data on to the correct subnet and computer.</p><p><strong>Gateway</strong> A node on a network that acts as a connection point to another network with different protocols</p><p>A gateway may be used to connect two different company networks together.</p><p>The gateway carries out all of the protocol conversion required to enable the two networks to work together.</p><p>To identify whether the destination computer is on the same subnet, the sending computer needs to look at the network portion of the destination IP address to see if it is the same as its own.</p><p>To do this a subnet mask is used, which uses the bitwise logical AND to eliminate the irrelevant bits.</p><pre><code>01111000.10110000.10000110.00100000 Full IP of sending computer
11111111.11111111.11111111.00000000 AND Subnet mask
01110000.10110000.10000110.00000000 Network ID of sending computer

01111000.10110000.10000110.01001011 Full IP address of destination
11111111.11111111.11111111.00000000 AND Subnet mask
01110000.10110000.10000110.00000000 = Network ID of destination computer
</code></pre><p>As the sending computer and destination computer have the same network ID, the data can be sent directly. Otherwise the data would be sent to a router that would forward the transmission to the subnet that the destination computer is on.</p><h3 id="ipv4-and-ipv6"><a class="anchor hidden-xs" href="#ipv4-and-ipv6" title="ipv4-and-ipv6"><span class="octicon octicon-link"></span></a>IPV4 and IPV6</h3><p>The original 32 bit code is not enough to provide a sufficient number of permutations for the number of devices present on the Internet. Consequently, IPV6 was created, which uses 128 bits represented as eight groups of four hex numbers.</p><h3 id="dynamic-host-configuration-protocol"><a class="anchor hidden-xs" href="#dynamic-host-configuration-protocol" title="dynamic-host-configuration-protocol"><span class="octicon octicon-link"></span></a>Dynamic Host Configuration Protocol</h3><p>IP addresses are defined as either static or dynamic. Static IP addresses are ones that are assigned and then never change. Dynamic IP addresses are allocated every time a device connects to a network.</p><p><strong>Dynamic Host Configuration Protocol (DCHP)</strong> A set of rules for allocating locally unique IP addresses to devices as they connect to a network</p><p>A dedicated DHCP server is used on the network and handles the requests by managing the pool of available IP addresses, usually within a defined range of numbers depending on how the network is physically configured.</p><h3 id="domain-name-server"><a class="anchor hidden-xs" href="#domain-name-server" title="domain-name-server"><span class="octicon octicon-link"></span></a>Domain name server</h3><p>Once allocated, the domain names of websites are mapped to unique IP addresses and this information is stored in databases on large servers.</p><p>There are hundreds of DNSs in use around the world, all of which are connected to each other.</p><h4 id="internet-registries"><a class="anchor hidden-xs" href="#internet-registries" title="internet-registries"><span class="octicon octicon-link"></span></a>Internet registries</h4><p>The organisation that oversees the allocation of domain names and IP addresses is called ICANN, the Internet Corporation for Assigned Names and Numbers.<br>
They have a department called the Internet Assigned Numbers Authority (IANA) who manage five further organisations called Regional Internet Registries. Each of these has a defined region of the world and therefore a defined set of IP addresses that they are responsible for allocating.</p><p><strong>Internet registries</strong> Organisations who allocate and administer domain names and IP addresses</p><p><strong>Regional Internet Registries</strong> Organisations that allocate and administer domain names and IP addresses in different parts of the world</p><h3 id="routing-and-gateways"><a class="anchor hidden-xs" href="#routing-and-gateways" title="routing-and-gateways"><span class="octicon octicon-link"></span></a>Routing and gateways</h3><p>Any transmission will be routed through a number of nodes before a connection is established between the sender and the reveiver. The router is used to send the data to the appropriate node on the network. It knows where to send it as each piece of data is sent as a packet, and it will read the header information in each packet of data being sent.</p><p><strong>Packet</strong> A block of data being transmitted</p><p>Data packets are often transmitted between networks as well as around them. Sometimes the networks will be dissimilar in that they use different protocols. A gateway must be used to convert between the two protocols.</p><p>Routing finds the optimum route between the sender and the receiver, which may be made up of many nodes. At each stage of the routing process, the data packets are sent to the next router in the path, often with reference to a routing table. The routing table stores information on the possible routes that each data packet may take between nodes on its path from sender to receiver.</p><p><strong>Routing</strong> The process of directing packets of data between networks</p><h3 id="packet-switching"><a class="anchor hidden-xs" href="#packet-switching" title="packet-switching"><span class="octicon octicon-link"></span></a>Packet switching</h3><p>One of the methods used to send data across networks is called packet switching. Data sent over the Internet is broken down into smaller chunks called packets. Each packet will also contain additional information including a packet sequence number, a source and destination address, and a checksum</p><h3 id="packet-switching1"><a class="anchor hidden-xs" href="#packet-switching1" title="packet-switching1"><span class="octicon octicon-link"></span></a>Packet switching</h3><p>One of the methods used to send data across networks is called packet switching. Data sent over the Internet is broken down into smaller chunks called packets. Each packet will also contain additional information including a packet sequence number, a source and destination address, and a checksum. Packets of data are normally made up of a header, body, and footer.</p><p><strong>Packet switching</strong> A method for transmitting packetes of data via the quickest route on a network</p><table>
<thead>
<tr>
<th>Part</th>
<th>Contents</th>
</tr>
</thead>
<tbody>
<tr>
<td>Header</td>
<td>MAC address of sender and receiver<br>The sender and receiver IP address<br>Protocol in use<br>Packet number or sequence number</td>
</tr>
<tr>
<td>Body</td>
<td>The actual data</td>
</tr>
<tr>
<td>Footer</td>
<td>A checksum</td>
</tr>
</tbody>
</table><p>The checksum is used to identify any errors. It could be generated by adding the values in the packet.</p><p>Each packet can take a different route to its destination as it can be reassembled at the other end regardless of the sequence in which the packets are receieved. The packets are routed via the least congested and therefore quickest route. Data are transferred quicker using this method and are more secure as the packets take different routes.</p><h2 id="internet-security"><a class="anchor hidden-xs" href="#internet-security" title="internet-security"><span class="octicon octicon-link"></span></a>Internet security</h2><h3 id="firewall"><a class="anchor hidden-xs" href="#firewall" title="firewall"><span class="octicon octicon-link"></span></a>Firewall</h3><p><strong>Firewall</strong> Hardware or software for protecting against unauthorised access to a network</p><p>An organisation that has a LAN will have a number of computers linked together, which will all have access to internal information.<br>
The LAn may also allow users to acces the Internet, and this is a vulnerability.</p><p>One method of creating a firewall is packet filtering. It uses two network interface cards, one for the LAN and one for the Internet. When data packets are received through the Internet NIC, they can be examined before being passed around internally via the LAN NIC. Firewall stoftware is used to examine the packets to ensure that they do not contain any unauthorised data. At a basic level, the header of each packet can be examined to check that it has come from a recognised source.</p><p><strong>Packet filtering</strong>  atechnique for examining the contents of packets on a network and rejecting them if they do not conform to certain rules</p><p>Firewall software may also facilitate logging of all data so that it can be traced.<br>
This allows automatic warnings to be generated.</p><p>A more sophisticated firewall may examine the contents of each data packet.<br>
This is called stateful inspection and also involves the firewall examining where each data packet has come from. It keeps track of all open communication channels and therefore knows the context of each packet it receieves.</p><p><strong>Stateful inspection</strong> A technique for examining the contents of packets on a network and rejecting them if they do not form part of a recognised communication</p><h3 id="proxy-server"><a class="anchor hidden-xs" href="#proxy-server" title="proxy-server"><span class="octicon octicon-link"></span></a>Proxy server</h3><p>One security mesaure that can be used is a proxy server. By routing through a proxy server, there is no direct connection between the computer on the LAN and the Internet. Instead, all requests get passed through a proxy server and can be evaluated to ensrue that they cme from a legitimate source or to filter  users so that they only have access to specific websites.</p><h3 id="privatepublic-key-encryption"><a class="anchor hidden-xs" href="#privatepublic-key-encryption" title="privatepublic-key-encryption"><span class="octicon octicon-link"></span></a>Private/Public key encryption</h3><p><strong>Symmetric encryption</strong> Where both the sender and receiver use the same key to encrypt and decrypt the data</p><p>The problem with symmetric encryption is that the the receiver must know the key. This is an inherent weakness with this system as if the key is intercepted is would be possible work out what it is, therefore making all further communications vulnerable.</p><p><strong>Asymmetric encryption</strong> Where public and private key are used to encrypt and decrypt data</p><p><strong>Private key</strong> A code used to encrypt/decrypt data that is only known by one user but is mathematically linked to a corresponding public key</p><p><strong>Public key</strong> A code used to encrypt/decrypt data that can be made public and is linked to a corresponding private key</p><p>Suppose there are two computers A and B:</p><ul>
<li>A will have a private key known only to A</li>
<li>A will also have a public key, mathematically related to the private key. Anyone can access it</li>
<li>B will also have a private key and a related public key</li>
<li>For A to send a secure message to B, A will first encrypt the message using B’s public key</li>
<li>As the private and public keys are related, the message can only be decrypted by B using B’s private key</li>
<li>As no-one else knows B’s private key, even if the message were intercepted, it could not be decrypted</li>
</ul><h3 id="digital-certificates-and-signatures"><a class="anchor hidden-xs" href="#digital-certificates-and-signatures" title="digital-certificates-and-signatures"><span class="octicon octicon-link"></span></a>Digital certificates and signatures</h3><p><strong>Digital certificate</strong> A method of ensuring that an encrypted message is from a trusted source as they have a certificate from a Certification Authority</p><p><strong>Certification Authority</strong> A trusted organisation that provides digitaol certificates and signatures</p><p>Digital certificates, sometimes referred to as Secure Socket Layer certificates, were introduced to encourage people to do business on the Inernet, as many consumers were concerned about fraud.</p><p>Websites using digital certificates usually advertise the fact prominently on the site using the logo of the Certification Authority.</p><p>A digital signature is another method of ensuring the authenticity of the sender.</p><p><strong>Digital signature</strong> A method of ensuring that an encrypted message is from a trusted source, as they have a unique, encrypted signature verified by a Certification Authority.</p><p>Suppose A wants to send b a message with a digital signature:</p><ul>
<li>A hashes the message</li>
<li>The hash is encrypted with A’s private key</li>
<li>The encrypted hash is appened to the message</li>
<li>The message is encrypted using B’s public key</li>
<li>The encrypted message is sent to B</li>
<li>B decrypts the message with B’s private key</li>
<li>B decrypts the hash with A’s public key to get the original hash</li>
<li>The decrypted message is hashed again, reproducing the message digest</li>
<li>The message has not been tampered with if the decrypted message digest is the same as the reproduced digest</li>
</ul><h3 id="trojan"><a class="anchor hidden-xs" href="#trojan" title="trojan"><span class="octicon octicon-link"></span></a>Trojan</h3><p><strong>Trojan</strong> Malware that is hidden within another file on your computer</p><p>the distingushing feature of a Trojan is that it is hidden away inside another file and that it is not always obvious that a computer is infected.</p><p>The Trojan does not replicate itself in the same way as other malware, and can therefore remain undetected.</p><p>The Flam malware, is being classed as a new generation of superbug that is part Torjan, part worm, and part virus. It is quite large at 20MB. Once it has installed itself it has the capability to monitor network traffic, access data and programs, take screenshots, record converstaions, and monitor keystrokes.</p><h3 id="viruses"><a class="anchor hidden-xs" href="#viruses" title="viruses"><span class="octicon octicon-link"></span></a>Viruses</h3><p><strong>Virus</strong> A generic term for malware where the program attaches itself to another file in order to infect a computer</p><p>The defining feature of a virus is that it replicates itself and can therefore cause extensive damage to  networks.</p><h3 id="worms"><a class="anchor hidden-xs" href="#worms" title="worms"><span class="octicon octicon-link"></span></a>Worms</h3><p><strong>Worm</strong> Malware or a type of virus that replicates itself and spreads around a computer system. It does not need to be attached to another file in order to infect a computer</p><h3 id="protecting-against-malware"><a class="anchor hidden-xs" href="#protecting-against-malware" title="protecting-against-malware"><span class="octicon octicon-link"></span></a>Protecting against malware</h3><p>Users can attempt to protect their computers:</p><ul>
<li>Use anti virus software and other anti malware software, and keep it up ot date</li>
<li>Keep the operating system up to date</li>
<li>Use a firewall</li>
<li>Do not open attachments or click on pop-ups</li>
<li>Operate a white list of trusted sites</li>
<li>Ensure sites use HTTPS, digital signatures, and certificates</li>
<li>Use paswords on programs and files</li>
<li>Encrypt data files</li>
</ul><p>Programmers can:</p><ul>
<li>Select a programming language with built in security features</li>
<li>Use recognised encryption techniques for all data stored within the program</li>
<li>Set administrative rights as part of the program and carefully control access and permission rights for different users</li>
<li>Don’t load up lots of Internet services unless they are needed</li>
<li>Thoroughly test the code, specifically for known security issues</li>
<li>Keep code up to date</li>
<li>Never trust the user</li>
</ul><p>System administrators can:</p><ul>
<li>Ensure that requests are coming from recognised sources</li>
<li>Use a network firewall and use the packet filtering and sateful inspection techniques</li>
<li>use encryption techniques and ensure digital certificates and signatures are used and are up to date</li>
<li>Keep anti-virus software up to date</li>